Programming language optimizations for modular router configurations

ABSTRACT

Networking systems such as Ensemble, the x-kernel, Scout, and Click achieve flexibility by building routers and other packet processors from modular components. Unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. This paper addresses the efficiency problems of one component-based router, Click, through optimization tools inspired in part by compiler optimization passes. This pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of CPU time Click requires to process a packet in a simple IP router by 34%. We present several optimization tools, describe how those tools affected the design of Click itself, and present detailed evaluations of Click's performance with and without optimization.

REFERENCES

• 1: Pentium Pro Family Developer's Manual, Volume 3, 1996. http://developer.intel.com/design/pro/manuals.
• 2: DIGITAL Semiconductor 21140A PCI Fast Ethernet LAN Controller Hardware Reference Manual, March 1998. http://developer.intel.com/design/network/manuals.
• 3: Andrew Begel , Steven McCanne , Susan L. Graham, BPF+: exploiting global data-flow optimization in a generalized packet filter architecture, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.123-134, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: Walid Dabbous , Sean O'Malley , Claude Castelluccia, Generating efficient protocol code from an abstract specification, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.60-72, August 28-30, 1996, Palo Alto, California, United States
• 5: Click Project. The Click modular router (Web site). http://www.pdos.lcs.mit.edu/click/.
• 6: Julian Elischer and Archie Cobbs. Netgraph. ftp://ftp.whistle.com/pub/archie/netgraph/index.html.
• 7: 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
• 8: 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]
• 9: Xiaoming Liu , Christoph Kreitz , Robbert van Renesse , Jason Hickey , Mark Hayden , Kenneth Birman , Robert Constable, Building reliable, high-performance communication systems from components, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.80-92, December 12-15, 1999, Charleston, South Carolina, United States
• 10: Jeffrey C. Mogul , K. K. Ramakrishnan, Eliminating receive livelock in an interrupt-driven kernel, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.217-252, Aug. 1997 [doi>10.1145/263326.263335]
• 11: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 12: David Mosberger , Larry L. Peterson , Patrick G. Bridges , Sean O'Malley, Analysis of techniques to improve protocol processing latency, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.73-84, August 28-30, 1996, Palo Alto, California, United States
• 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: Alastair Reid, Matthew Flatt, Leigh Stoller, Jay Lepreau, and Eric Eide. Knit: Component composition for systems software. In Proc. 4th ACM Symposium on Operating Systems Design and Implementation (OSDI 2000), pages 347-360, October 2000.
• 15: D. M. Ritchie. A stream input-output system. AT&T Bell Laboratories Technical Journal, 63(8):1897-1910, October 1984.
• 16: Oliver Spatscheck , Jørgen S. Hansen , John H. Hartman , Larry L. Peterson, Optimizing TCP forwarder performance, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.146-157, April 2000 [doi>10.1109/90.842138]
• 17: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 18: Elizabeth D. Zwicky , Simon Cooper , D. Brent Chapman, Building Internet firewalls (2nd ed.), O'Reilly & Associates, Inc., Sebastopol, CA, 2000