Router plugins: a software architecture for next generation routers

ABSTRACT

Present day routers typically employ monolithic operating systems which are not easily upgradable and extensible. With the rapid rate of protocol development it is becoming increasingly important to dynamically upgrade router software in an incremental fashion. We have designed and implemented a high performance, modular, extended integrated services router software architecture in the NetBSD operating system kernel. This architecture allows code modules, called plugins, to be dynamically added and configured at run time. One of the novel features of our design is the ability to bind different plugins to individual flows; this allows for distinct plugin implementations to seamlessly coexist in the same runtime environment. High performance is achieved through a carefully designed modular architecture; an innovative packet classification algorithm that is both powerful and highly efficient; and by caching that exploits the flow-like characteristics of Internet traffic. Compared to a monolithic best-effort kernel, our implementation requires an average increase in packet processing overhead of only 8%, or 500 cycles/2.1ms per packet when running on a P6/233.

REFERENCES

• 1: Adiseshu, H., and Parulkar, G., "ssP: A State Setup Protocol", to be published
• 2: Atkinson, R., "Security Architecture for the lnternet Protocol", RFC 1825, August 1995
• 3: Jon C. R. Bennett , Hui Zhang, Hierarchical packet fair queueing algorithms, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.143-156, August 28-30, 1996, Palo Alto, California, United States
• 4: Bennett, J.C.R., and Zhang, H., "WF2Q: Worst-case Fair Weighted Fair Queueing", In Proceedings oflNFOCOM'96, March 1996
• 5: Cho, K., "A Framework for Alternate Queueing", In Proceedings of USENIX 1998, June 1998
• 6: Cisco Corporation, web pages on lOS, http://www, cisco.com/public/ sw-center/sw-ios.shtml
• 7: Decasper, D., et. al., "Router Plugins", Washington University Tech Report WUCS-98-08, February 1998
• 8: Deering, S., Hinden, R., "Internet Protocol, Version 6 (IPv6), Specification'', RFC 1883, December 1995
• 9: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 10: Dawson R. Engler , M. Frans Kaashoek, DPF: fast, flexible message demultiplexing using dynamic code generation, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.53-59, August 28-30, 1996, Palo Alto, California, United States
• 11: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 12: 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]
• 13: INRIA ftp site for IPv6 source code. ftp://fip.inria.fr/network/ipv6
• 14: Intel Corporation, web pages on VTUNE, http://developer, intel.com/ design/perftool/vtune/index.htm, 1997
• 15: Lampson, B., Srinivasan, V., Varghese, G., "IP Lookups using Multiway and Multicolumn Search", In Proceedings of tNFOCOM'98, April 1998
• 16: Steven Lin , Nick McKeown, A simulation study of IP switching, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.15-24, September 14-18, 1997, Cannes, France
• 17: Linux kernel packet filter implementation, http://wafu.netgate.net/ linux/index.htmI
• 18: Microsoft Corporation, "Update to Routing and Remote Access Service for Windows NT Server 4.0", Review and Evaluation Guide, March 1997
• 19: Microsoft Corporation, web pages on RRAS SDK, http://premium.microsoft.com/msdn/library/sdkdoc/pdnds! remacces 8085.htm
• 20: J. Mogul , R. Rashid , M. Accetta, The packer filter: an efficient mechanism for user-level network code, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.39-51, November 08-11, 1987, Austin, Texas, United States
• 21: David Mosberger, Scout: a path-based operating system, University of Arizona, Tucson, AZ, 1998
• 22: Reed, D., "IP Filter", http://www, cyber, com. au/users/darrenr/
• 23: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 24: Sklower, K., "A tree-based routing table for Berkeley Unix", Technical report, University of California, Berkley, 1993
• 25: V. Srinivasan , George Varghese, Faster IP lookups using controlled prefix expansion, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-10, June 22-26, 1998, Madison, Wisconsin, United States
• 26: Srinivasan, V., et al., "Fast Scalable Algorithms for Level Four Switching", In Proceedings of SIGCOMM'98, September 1998
• 27: Ion Stoica , Hui Zhang , T. S. Eugene Ng, A hierarchical fair service curve algorithm for link-sharing, real-time and priority services, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.249-262, September 14-18, 1997, Cannes, France
• 28: Suri, S., Varghese, G., Chandranmenon, G., "Leap Forward Virtual Clock", In Proceedings oflNFOCOM'97, April 1997
• 29: Tsuchiya, P., "A Search Algorithm for Table Entries with Non-contiguous Wildcarding", unpublished paper, 1992
• 30: Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high speed IP routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.25-36, September 14-18, 1997, Cannes, France
• 31: Zhang, L, et al., "RSVP: A New Resource ReSerVation Protocol", In IEEE Network Magazine, Vot. 7, No. 5., September 1993

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

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

Keywords:
high performance integrated services routing, modular router architecture, router plugins