Implementation and evaluation of a QoS-capable cluster-based IP router

ABSTRACT

A major challenge in Internet edge router design is to support both high packet forwarding performance and versatile and efficient packet processing capabilities. The thesis of this research project is that a cluster of PCs connected by a high speed system area network provides an effective hardware platform for building routers to be used at the edges of the Internet. This paper describes a scalable and extensible edge router architecture called Panama, which supports a novel aggregate route caching scheme, a real-time link scheduling algorithm whose performance overhead is independent of the number of real-time flows, a highly efficient kernel extension mechanism to safely load networking software extensions dynamically, and an integrated resource scheduler which ensures that real-time flows with additional packet processing requirements still meet their end-to-end performance requirements. This paper describes the implementation and evaluation of the first Panama prototype based on a cluster of PCs and Myrinet.

REFERENCES

• 1: Dimitrios Stiliadis , Anujan Varma, Rate-proportional servers: a design methodology for fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.164-174, April 1998 [doi>10.1109/90.664265]
• 2: David Mosberger , Larry L. Peterson, Making paths explicit in the Scout operating system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.153-167, October 29-November 01, 1996, Seattle, Washington, United States
• 3: Norman C. Hutchinson , Larry L. Peterson, The X-Kernel: An Architecture for Implementing Network Protocols, IEEE Transactions on Software Engineering, v.17 n.1, p.64-76, January 1991 [doi>10.1109/32.67579]
• 4: P. Pradhan, T. Chiueh; "Cache Memory Design for Network Processors"; Proc. IEEE HPCA 2000.
• 5: "Discretization in Fluid Fairness: Formulation and Implications"; Technical Report (Author names hidden).
• 6: Tzi-cker Chiueh , Ganesh Venkitachalam , Prashant Pradhan, Integrating segmentation and paging protection for safe, efficient and transparent software extensions, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.140-153, December 12-15, 1999, Charleston, South Carolina, United States
• 7: "Intel Architecture Software Developer's Manual" (http://developer.intel.com/vtune/cbts/refman.htm)
• 8: J. Liedtke; "Improved Address Space Switching on Pentium Processors by Transparently Multiplexing User Address Spaces"; GMD technical report (http://i30www.ira.uka.de/publications/pubcat/As-pent.ps).
• 9: T. Chiueh, P. Pradhan; "High Performance IP Routing Table Lookup Using CPU Caching"; Proc. IEEE INFOCOM 1999.
• 10: Dan Decasper , Zubin Dittia , Guru Parulkar , Bernhard Plattner, Router plugins: a software architecture for next generation routers, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.229-240, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 11: J. Wroklawski; "Fast PC Routers"; (http://ana-www.lcs.mit.edu/anaweb/pcrouter.html).
• 12: "The ATOMIC-2 Project"; (http://www.isi.edu/div7/atomic2).
• 13: Larry L. Peterson , Scott C. Karlin , Kai Li, OS Support for General-Purpose Routers, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.38, March 28-30, 1999
• 14: Prashant Pradhan , Tzi-Cker Chiueh, Operating Systems Support for Programmable Cluster-Based Internet Routers, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.76, March 28-30, 1999
• 15: Robert Morris , Eddie Kohler , John Jannotti , M. Frans Kaashoek, The Click modular router, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.217-231, December 12-15, 1999, Charleston, South Carolina, United States
• 16: V. Vuppala, L. M. Ni; "Design of A Scalable IP Router"; Proc. IEEE Hot Interconnects 1997.
• 17: Michigan University and Merit Network. Internet Performance Measurement and Analysis (IPMA) Project. (http://nic.merit.edu/ipma).
• 18: Myricom Inc.; "LANai4.X specification"; (http://www.myri.com/scs/documentation/mug/development/LANai4.X.doc.txt).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Experimentation, Measurement, Performance