Analysis of techniques to improve protocol processing latency

ABSTRACT

This paper describes several techniques designed to improve protocol latency, and reports on their effectiveness when measured on a modern RISC machine employing the DEC Alpha processor. We found that the memory system---which has long been known to dominate network throughput---is also a key factor in protocol latency. As a result, improving instruction cache effectiveness can greatly reduce protocol processing overheads. An important metric in this context is the memory cycles per instructions (mCPI), which is the average number of cycles that an instruction stalls waiting for a memory access to complete. The techniques presented in this paper reduce the mCPI by a factor of 1.35 to 5.8. In analyzing the effectiveness of the techniques, we also present a detailed study of the protocol processing behavior of two protocol stacks---TCP/IP and RPC---on a modern RISC processor.

REFERENCES

• 1: AMD. Am7990: Local Area Network Controller for Ethernet.
• 2: 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, 1994.
• 3: Dileep Bhandarkar , Douglas W. Clark, Performance from architecture: comparing a RISC and a CISC with similar hardware organization, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.310-319, April 08-11, 1991, Santa Clara, California, 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: J. Bradley Chen , Brian N. Bershad, The impact of operating system structure on memory system performance, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.120-133, December 05-08, 1993, Asheville, North Carolina, United States
• 6: D. D. Clark, V. Jacobson, J. Romkey, and H. Salwen. An analysis of TCP processing overheads. IEEE Communications Magazine, 27(6):23-29, June 1989.
• 7: C. Dalton, G. Watson, D. Banks, C. Calamvokis, A. Edwards, and J. Lumley. Afterburner. IEEE Network, 7(4):35-43, July 1993.
• 8: Richard P. Draves , Brian N. Bershad , Richard F. Rashid , Randall W. Dean, Using continuations to implement thread management and communication in operating systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.122-136, October 13-16, 1991, Pacific Grove, California, United States
• 9: 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
• 10: A. Eustace. Personal communication, Oct. 1994.
• 11: Rajiv Gupta , Chi-Hung Chi, Improving instruction cache behavior by reducing cache pollution, Proceedings of the 1990 conference on Supercomputing, p.82-91, October 1990, New York, New York, United States
• 12: R. R. Heisch, Trace-directed program restructuring for AIX executables, IBM Journal of Research and Development, v.38 n.5, p.595-603, Sept. 1994
• 13: 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]
• 14: V. Jacobson. A high performance TCP/IP implementation. Presentation at the NRI Gigabit TCP Workshop, Mar. 18th-19th 1993.
• 15: Jonathan Kay , Joseph Pasquale, The importance of non-data touching processing overheads in TCP/IP, Conference proceedings on Communications architectures, protocols and applications, p.259-268, September 13-17, 1993, San Francisco, California, United States
• 16: 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
• 17: Henry Massalin, Synthesis: an efficient implementation of fundamental operating system services, Columbia University, New York, NY, 1992
• 18: S. McCanne and V. Jacobson. The BSD packet filter: A new architecture for user-level packet capture. In 1993 Winter USENIX Conference, San Diego, CA, Jan. 1993. USENIX.
• 19: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 20: L. McVoy and C. Staelin. lmbench: Portable tools for performance analysis. In Proceedings of the USENIX ~996 Technical Conference, pages 120-133, 1996.
• 21: David Mosberger , Larry L. Peterson, Making Paths Explicit in the Scout Operating System, University of Arizona, Tucson, AZ, 1996
• 22: David Mosberger , Larry L. Peterson , Patrick G. Bridges , Sean O''Malley, Analysis of Techniques to Improve Protocol Processing Latency, University of Arizona, Tucson, AZ, 1996
• 23: Sean W. O'Malley , Larry L. Peterson, A dynamic network architecture, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.110-143, May 1992 [doi>10.1145/128899.128901]
• 24: Sean O'Malley , Todd Proebsting , Allen Brady Montz, USC: a universal stub compiler, Proceedings of the conference on Communications architectures, protocols and applications, p.295-306, August 31-September 02, 1994, London, United Kingdom
• 25: John K. Ousterhout , Andrew R. Cherenson , Frederick Douglis , Michael N. Nelson , Brent B. Welch, The Sprite Network Operating System, Computer, v.21 n.2, p.23-36, February 1988 [doi>10.1109/2.16]
• 26: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 27: J. Postel. RFC-791: Internet Protocol. Available via ftp from ftp.nisc.sri.com, Sept. 1981.
• 28: J. Postel. RFC-793: Transmission Control Protocol. Available via ftp from ftp.nisc.sri.com, Sept. 1981.
• 29: Betty Prince, Memory in the fast lane, IEEE Spectrum, v.31 n.2, p.38-41, Feb. 1994 [doi>10.1109/6.259491]
• 30: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• 31: R. M. Stallman. Using and Porting GNU CC, 1992. Manuscript provided by the Free Software Foundation to document g c c.
• 32: 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]
• 33: M. Yuhara, B. N. Bershad, C. Maeda, and J. E. B. Moss. Efficient packet demultiplexing for multiple endpoints and large messages. In 1994 Winter USENIX Conference, pages 153-165, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures

          Nouns: RISC**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: TCP/IP

General Terms:
Algorithms, Design, Experimentation, Performance