Fast and scalable layer four switching

ABSTRACT

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port numbers. Layer Four switching unifies firewall processing, RSVP style resource reservation filters, QoS Routing, and normal unicast and multicast forwarding into a single framework. In this framework, the forwarding database of a router consists of a potentially large number of filters on key header fields. A given packet header can match multiple filters, so each filter is given a cost, and the packet is forwarded using the least cost matching filter.In this paper, we describe two new algorithms for solving the least cost matching filter problem at high speeds. Our first algorithm is based on a grid-of-tries construction and works optimally for processing filters consisting of two prefix fields (such as destination-source filters) using linear space. Our second algorithm, cross-producting, provides fast lookup times for arbitrary filters but potentially requires large storage. We describe a combination scheme that combines the advantages of both schemes. The combination scheme can be optimized to handle pure destination prefix filters in 4 memory accesses, destination-source filters in 8 memory accesses worst case, and all other filters in 11 memory accesses in the typical case.

REFERENCES

• 1: M. Bailey et al. PathFinder. Proceedings of OSDI 94.
• 2: S. Bradner. Next generation routers overview. Proc. of Nctworld {nterop 97.
• 3: D. Brent Chapman , Elizabeth D. Zwicky , Deborah Russell, Building Internet Firewalls, O'Reilly & Associates, Inc., Sebastopol, CA, 1995
• 4: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 5: Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
• 6: William R. Cheswick , Steven M. Bellovin, Firewalls and Internet security: repelling the wily hacker, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 7: Dan Decasper , Zubin Dittia , Guru Parulkar , Bernhard Plattner, Router plugins: a software architecture for next generation routers, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.229-240, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 8: S. Deering and R. }linden. Internet protocol, Version 6 (IPv6) specification RFC 1883. http: //ds. int erni c .net/rf c/rf c 1883. txt.
• 9: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 10: Digital Electronics Corporation. The DEC Alpha. http://www.dec.com.
• 11: 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
• 12: lntel. The pentium processor. (www.pentium.com.)
• 13: Intel. The Vtune performance measurement tool. (www. intel, com/design/perftool/vtune)
• 14: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.115-126, September 14-18, 1997, Cannes, France
• 15: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.203-214, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 16: B. Lampson, V. Srinivasan, and G. Varghese. IP Lookups using Multiway and Multicolumn Search. Proc. lnfocom 98, March 1998.
• 17: S. McCanne and V. Jacobson. The Berkeley Path Finder. Proc. of Winter USENIX 1993.
• 18: Nick McKeown , Martin Izzard , Adisak Mekkittikul , William Ellersick , Mark Horowitz, Tiny Tera: A Packet Switch Core, IEEE Micro, v.17 n.1, p.26-33, January 1997 [doi>10.1109/40.566194]
• 19: J. McQuillan. Layer 4 Switching. Data Communications, October 21, 1997
• 20: Merit Inc. IPMA statistics. (nic.merit.edu.)
• 21: P. Newman, G. Minshall, and L. Huston. IP Switching and Gigabit Routcrs. {EEE Communications Magazine, January 1997.
• 22: S. Nilsson , G. Karlsson, Fast address look-up for internet routers, Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications, p.11-22, April 01-03, 1998
• 23: C. Partridge. Locality and route caches. In NSF Workshop on {nternet Statistics Measurement and Analysis, San Diego, CA, USA, February 1996.
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 26: S. Suri, G. Varghese, M. Waldvogel, and V. Srinivasan. Layer Four Switching using Rectangle and Tuple Search. In preparation, 1998.
• 27: 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
• 28: Torrent systems, Inc. http://www.torrent.com
• 29: P. Tsuchiya. A search algorithm for table entries with non-contiguous wildcarding. Unpublished report, Bellcore.
• 30: J Turner. Design of a Gigabit ATM Switch. Proc. $IGCOMM 97, October 1997.
• 31: 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
• 32: L. Zhang et al. RSVP: A New Resource Reservation Protocol. {EEE Networks Magazine, Sept 1993.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Algorithms