Trading packet headers for packet processing

ABSTRACT

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. Thus it pays to add information to packet headers to make packet processing easier. While this is an old idea, we describe several specific new mechanisms based on this principle. We describe a new technique, source hashing, which can provide O(1) lookup costs at the Data Link, Routing, and Transport layers. Source hashing is especially powerful when combined with the old idea of a flow ID; the flow identifier allows packet processing information to be cached, and source hashing allows efficient cache lookups. Unlike Virtual Circuit Identifiers (VCIs), source hashing does not require a round trip delay for set up. In an experiment with the BSD Packet Filter implementation, we found that adding a flow ID and a source hash improved packet processing costs by a factor of 7. We also found a 45% improvement when we conducted a similar experiment with IP packet forwarding. We also describe two other new techniques: threaded indices, which allows fast VCI-like lookups for datagram protocols like IP; and a Data Manipulation Layer, which compiles out all the information needed for Integrated Layer Processing into an easily accessible portion of each packet.

REFERENCES

• AP93: Mark B. Abbott , Larry L. Peterson, Increasing network throughput by integrating protocol layers, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.600-610, Oct. 1993 [doi>10.1109/90.251918]
• BN84: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• BP93: D. Banks and M. Prudence. A highperformance network architecture for a PA- RISC workstation. IEEE Journal on Selected Areas in Communications, February 1993.
• CJRS89: D.D. Clark, V. Jacobson, J. Romkey, and H. Salwen. An analysis of TOP processing overhead. IEEE Commun,cations, 27(6):23-29, June 1989.
• CLR90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• CT90: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• Fel93: David C. Feldmeier, A data labelling technique for high-performance protocol processing and its consequences, ACM SIGCOMM Computer Communication Review, v.23 n.4, p.170-181, Oct. 1993
• Hin94: R. Hinden. Editor, Internet Protocol, version 6 (IPv6) specification. Draft, October 1994.
• Jai92: Raj Jain. A comparison of hashing schemes for address lookups in computer networks. IEEE Transactions on Communications, COM- 40(10):1570-1573, October 1992.
• KLS86: Nancy P. Kronenberg , Henry M. Levy , William D. Strecker, VAXcluster: a closely-coupled distributed system, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.130-146, May 1986 [doi>10.1145/214419.214421]
• MJ93: S. McCanne and V. Jacobson. The BSD Packet Filter: A New Architecture for Userlevel Packet Capture. In USENIX Technzcal Conference Procee&ngs, pages 259-269, Winter 1993.
• Par93: Craig Partridge, Gigabit networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• Per92: Radia Perlman, Interconnections: bridges and routers, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• SP90: J.P.G. Sterbernz and G. M. Parulkar. Axon: A high speed communication architecture for distributed applications. In Proceedings of IEEE INFOCOMM '90, San F~ansisco, CA, pages 415-425, June 1990.
• SRC84: J. H. Saltzer , D. P. Reed , D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.277-288, Nov. 1984 [doi>10.1145/357401.357402]
• Tan81: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• vECGS92: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance