DPF: fast, flexible message demultiplexing using dynamic code generation

ABSTRACT

Fast and flexible message demultiplexing are well-established goals in the networking community [1, 18, 22]. Currently, however, network architects have had to sacrifice one for the other. We present a new packet-filter system, DPF (Dynamic Packet Filters), that provides both the traditional flexibility of packet filters [18] and the speed of hand-crafted demultiplexing routines [3]. DPF filters run 10-50 times faster than the fastest packet filters reported in the literature [1, 17, 18, 27]. DPF's performance is either equivalent to or, when it can exploit runtime information, superior to hand-coded demultiplexors. DPF achieves high performance by using a carefully-designed declarative packet-filter language that is aggressively optimized using dynamic code generation. The contributions of this work are: (1) a detailed description of the DPF design, (2) discussion of the use of dynamic code generation and quantitative results on its performance impact, (3) quantitative results on how DPF is used in the Aegis kernel to export network devices safely and securely to user space so that UDP and TCP can be implemented efficiently as user-level libraries, and (4) the unrestricted release of DPF into the public domain.

REFERENCES

• 1: M. L. Bailey, B. Gopal, M. A. Pagels, L. L. Peterson, and P. Sarkar. PATHFINDER: A pattern-based packet classifier. In Proceedings of the First Symposium on Operating Systems Design and Implementation, pages 115-123, November 1994.
• 2: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 3: D. D. Clark, V. Jacobson, J. Romkey, and H. Salwen. An analysis of TCP processing overhead. IEEE Communications Magazine, 27(6):23-29, June 1989.
• 4: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 5: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 6: Peter Druschel , Larry L. Peterson , Bruce S. Davie, Experiences with a high-speed network adaptor: a software perspective, Proceedings of the conference on Communications architectures, protocols and applications, p.2-13, August 31-September 02, 1994, London, United Kingdom
• 7: Aled Edwards , Greg Watson , John Lumley , David Banks , Costas Calamvokis , C. Dalton, User-space protocols deliver high performance to applications on a low-cost Gb/s LAN, Proceedings of the conference on Communications architectures, protocols and applications, p.14-23, August 31-September 02, 1994, London, United Kingdom
• 8: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 9: D. R. Engler, W. C. Hsieh, and M. F. Kaashoek. 'C: A language for high-level, efficient, and machine-independent dynamic code generation. In Proceedings of the 22th Annual Symposium on Principles of Programming Languages, 1995.
• 10: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 11: Dawson R. Engler , Todd A. Proebsting, DCG: an efficient, retargetable dynamic code generation system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.263-272, October 05-07, 1994, San Jose, California, United States
• 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: D. B. Johnson and W. Zwaenepoel. The Peregrine highperformance RPC system. Technical Report TR91-151, Rice University, March 1991.
• 14: M. Leone and P. Lee. Lightweight run-time code generation. In Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 97-106, Copenhagen, Denmark, June 1994.
• 15: Chris Maeda , Brian N. Bershad, Protocol service decomposition for high-performance networking, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.244-255, December 05-08, 1993, Asheville, North Carolina, United States
• 16: Henry Massalin, Synthesis: an efficient implementation of fundamental operating system services, Columbia University, New York, NY, 1992
• 17: S. McCanne and V. Jacobson. The BSD packet filter: A new architecture for user-level packet capture. In USENIX Technical Conference Proceedings, pages 259-269, San Diego, CA, Winter 1993. USENIX.
• 18: 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
• 19: Todd A. Proebsting , Charles N. Fischer, Linear-time, optimal code scheduling for delayed-load architectures, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.256-267, June 24-28, 1991, Toronto, Ontario, Canada
• 20: N. Ramsey and M. F. Fernandez. The New Jersey machinecode toolkit. In 1995 Winter USENIX, December 1995.
• 21: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: Chandramohan A. Thekkath , Henry M. Levy, Limits to low-latency communication on high-speed networks, ACM Transactions on Computer Systems (TOCS), v.11 n.2, p.179-203, May 1993 [doi>10.1145/151244.151247]
• 23: Chandramohan A. Thekkath , Henry M. Levy , Edward D. Lazowska, Separating data and control transfer in distributed operating systems, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.2-11, October 05-07, 1994, San Jose, California, United States
• 24: C.A. Thekkath, H.M. Levy, and E.D. Lazowska. Efficient support for multicomputing on ATM networks. Technical Report TR93-04-03, University of Washington, April 1993.
• 25: Chandramohan A. Thekkath , Thu D. Nguyen , Evelyn Moy , Edward D. Lazowska, Implementing network protocols at user level, Conference proceedings on Communications architectures, protocols and applications, p.64-73, September 13-17, 1993, San Francisco, California, United States
• 26: Thorsten von Eicken , Anindya Basu , Vineet Buch, Low-Latency Communication Over ATM Networks Using Active Messages, IEEE Micro, v.15 n.1, p.46-53, February 1995 [doi>10.1109/40.342017]
• 27: M. Yahara, B. Bershad, C. Maeda, and E. Moss. Efficient packet demultiplexing for multiple endpoints and large messages. InProceedings of the Winter 1994 USENIX Conference, 1994.

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:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Measurement, Performance