High-speed policy-based packet forwarding using efficient multi-dimensional range matching

ABSTRACT

The ability to provide differentiated services to users with widely varying requirements is becoming increasingly important, and Internet Service Providers would like to provide these differentiated services using the same shared network infrastructure. The key mechanism, that enables differentiation in a connectionless network, is the packet classification function that parses the headers of the packets, and after determining their context, classifies them based on administrative policies or real-time reservation decisions. Packet classification, however, is a complex operation that can become the bottleneck in routers that try to support gigabit link capacities. Hence, many proposals for differentiated services only require classification at lower speed edge routers and also avoid classification based on multiple fields in the packet header even if it might be advantageous to service providers. In this paper, we present new packet classification schemes that, with a worst-case and traffic-independent performance metric, can classify packets, by checking amongst a few thousand filtering rules, at rates of a million packets per second using range matches on more than 4 packet header fields. For a special case of classification in two dimensions, we present an algorithm that can handle more than 128K rules at these speeds in a traffic independent manner. We emphasize worst-case performance over average case performance because providing differentiated services requires intelligent queueing and scheduling of packets that precludes any significant queueing before the differentiating step (i.e., before packet classification). The presented filtering or classification schemes can be used to classify packets for security policy enforcement, applying resource management decisions, flow identification for RSVP reservations, multicast look-ups, and for source-destination and policy based routing. The scalability and performance of the algorithms have been demonstrated by implementation and testing in a prototype system.

REFERENCES

• 1: M.L. Bailey, B.Gopal, M.Pagels, L.L.Peterson, and P. Sarkar. PATHFINDER: A pattern-based packet classifter. In Proceedings of the First Symposium on Operating Systems Design adn Implementation, November 1994.
• 2: Mark de Berg , Marc van Kreveld , Jack Snoeyink, Two- and three-dimensional point location in rectangular subdivisions, Journal of Algorithms, v.18 n.2, p.256-277, March 1995 [doi>10.1006/jagm.1995.1010]
• 3: P. Van Erode Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977.
• 4: J. Boyle. RSVP Extensions for CIDR Aggregated Data Flows. in Internet Draft, http://www.internic.net/internetdrafts/draft-ietf-rsvp-cidr-ext-01.txt, 1997.
• 5: Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
• 6: Bernard Chazelle , Joel Friedman, Point location among hyperplanes and unidirectional ray-shooting, Computational Geometry: Theory and Applications, v.4 n.2, p.53-62, June 1994 [doi>10.1016/0925-7721(94)90009-4]
• 7: B. Chazelle and L.J. Guibas. Fractional cascading, i. a data structuring technique. Algorithmica, 1(2):133-62, 1986.
• 8: B. Chazelle and L.J. Guibas. Fractional cascading, ii. applications. Algorithmica, 1(2):163-191, 1986.
• 9: Kimberly Claire Claffy, Internet traffic characterization, University of California at San Diego, La Jolla, CA, 1994
• 10: D. Clark. Service Allocation Profiles. In Internet Draft, http://www.internic.net/internet-drafts/draftclark-diff-svc-alloc-00.txt, 1997.
• 11: K.L. Clarkson. New applications of random sampling in computational geometry. Discrete ~4 Computational Geometry, 2:195-222, 1987.
• 12: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 13: D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma, and L. Wei. Protocol independent multicast - sparse mode : Protocol specification. In RFC 2117, June 1997.
• 14: D. Estrin, J. Postel, and Y. Rekhter. Routing arbiter architecture. In ConneXions, volume 8, pages 2-7, August 1994.
• 15: V. Fuller et. al. Classless Inter-Domain Routing. In RFC1519, ftp://ds.internic.net/rfc/rfc1519, txt, June 1993.
• 16: J.C.Mogul, R.F.Rashid, and M.J.Accetta. The packet filter: An efficient mechanism for user level network code. Technical Report 87.2, Digital WRL, 1987.
• 17: Kimberly C. Claffy , George C. Polyzos , Hans-Werner Braun, Application of sampling methodologies to network traffic characterization, Conference proceedings on Communications architectures, protocols and applications, p.194-203, September 13-17, 1993, San Francisco, California, United States
• 18: T. Li and Y. Rekhter. Provider Architecture for Differentiated Services and Traffic Engineering (PASTE). In Internet Draft, http://www.internic.net/internetdrafts/draft-li-paste-00.txt, 1998.
• 19: 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, Winter 1994.
• 20: N. McKeown, V Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. In Proceedings of INFOCOM'96, pages 296-302, March 1996.
• 21: Mitsubishi, http://www, mit s ubis hichips, co m / eram / er am. ht m. eRAM- Memory and Logic on a chip, 1997.
• 22: Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063]
• 23: P. Van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of 16th IEEE Conference on Foundations of Computer Science, pages 75-84, 1975.
• 24: K. Thomson, G.J. Miller, and R. Wilder. Wide-area traffic patterns and characteristics. IEEE Network, December 1997.
• 25: Toshiba America Electronic Components. CMOS dRA- MASIC Families, 1997.
• 26: D. Waitzman, C. Partridge, and S. Deering. Distance Vector Multicast Routing Protocol. In RFC1075, fip ://ds. internic, net/rfc/rfc1075, txt, June 1993.
• 27: M. Yuhara, B.N. Bershad, C.Maeda, J.Eliot, and B. Moss. Efficient packet demultiplexing for multiple endpoints and large messages. In USENIX Technical Conference Proceedings, Winter 1994.
• 28: L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: A new resource reservation protocol. IEEE Network, 7(5):8-18, September 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.6 Internetworking
          Subjects: Routers

General Terms:
Design, Performance