Succinct representation of static packet classifiers

ABSTRACT

We develop algorithms for the compact representation of the 1- and 2-dimensional tries that are used for Internet packet classification. Our compact representations are experimentally compared with competing compact representations for 1- and multi-dimensional packet classifiers and found to simultaneously reduce the number of memory accesses required for a lookup as well as the memory required to store the classifier.

REFERENCES

• 1: F. Baboescu, S. Singh, and G. Varghese, "Packet classification for core routers: Is there an alternative to CAMs?," in IEEE INFOCOM, 2003.
• 2: 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
• 3: Will Eatherton , George Varghese , Zubin Dittia, Tree bitmap: hardware/software IP lookups with incremental updates, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997160]
• 4: A. Hari, S. Suri, and G. Parulkar, "Detecting and resolving packet filter conflicts," in IEEE INFOCOM, 2000.
• 5: Ellis Horowitz , Dinesh Mehta , Sartaj Sahni, Fundamentals of Data Structures in C++, W. H. Freeman & Co., New York, NY, 1995
• 6: Internet Routing Table Statistics. [Online]. Available: http://www. merit.edu/ipma/routing_table
• 7: Guy Joseph Jacobson, Succinct static data structures, Carnegie Mellon University, Pittsburgh, PA, 1988
• 8: S. Kumar, J. Turner, P. Crowley, and M. Mitzenmacher, "Hexa: Compact data structures for faster packet processing," in Proc. IEEE Int. Conf. Network Protocols (ICNP), 2007.
• 9: B. Lampson, V. Srinivasan, and G. Varghese, "IP lookup using multi-way and multi-column search," in IEEE INFOCOM, 1998.
• 10: Huan Liu, Routing Table Compaction in Ternary CAM, IEEE Micro, v.22 n.1, p.58-64, January 2002 [doi>10.1109/40.988690]
• 11: Haibin Lu , Sartaj Sahni, O(logW) multidimensional packet classification, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.462-472, April 2007 [doi>10.1109/TNET.2007.892845]
• 12: Haibin Lu , Sartaj Sahni, Conflict detection and resolution in two-dimensional prefix router tables, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1353-1363, December 2005 [doi>10.1109/TNET.2005.860108]
• 13: Sumeet Singh , Florin Baboescu , George Varghese , Jia Wang, Packet classification using multidimensional cutting, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863980]
• 14: Wencheng Lu , Sartaj Sahni, Packet Classification Using Pipelined Two-Dimensional Multibit Tries, Proceedings of the 11th IEEE Symposium on Computers and Communications, p.808-813, June 26-29, 2006 [doi>10.1109/ISCC.2006.118]
• 15: Wencheng Lu, Packet Classification Using Two-Dimensional Multibit Tries, Proceedings of the 10th IEEE Symposium on Computers and Communications, p.849-854, June 27-30, 2005 [doi>10.1109/ISCC.2005.118]
• 16: W. Lu and S. Sahni, Succinct Representation of Packet Classifier [On-line]. Available: http://www.cise.ufl.edu/~wlu/papers/hsst.pdf
• 17: J. Lunteren, "Searching very large routing tables in fast SRAM," in Proc. ICCCN, 2001.
• 18: J. Lunteren, "Searching very large routing tables in wide embedded memory," in Proc. GLOBECOM, 2001.
• 19: J. Munro and S. Rao, "Succinct representation of data structures," in Handbook of Data Structures and Applications, D. Mehta and S. Sahni, Eds. Boca Raton, FL: Chapman & Hall/CRC, 2005.
• 20: 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
• 21: BGP Routing Table Analysis Reports. [Online]. Available: http://bgp. potaroo.net
• 22: Routing Information Service Raw Data, RIS [Online]. Available: http:// data.ris.ripe.net
• 23: M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," IEEE Network, vol. 15, no. 2, pp. 8-23, Mar.-Apr. 2001.
• 24: S. Sahni, K. Kim, and H. Lu, "Data structures for one-dimensional packet classification using most-specific-rule matching," Int. J. Foundations of Computer Science, vol. 14, no. 3, pp. 337-358, 2003.
• 25: V. Srinivasan , G. Varghese , S. Suri , M. Waldvogel, Fast and scalable layer four switching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.191-202, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 26: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 27: Haoyu Song , Jonathan Turner , John Lockwood, Shape Shifting Tries for Faster IP Route Lookup, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.358-367, November 06-09, 2005 [doi>10.1109/ICNP.2005.36]
• 28: Haoyu Song , Jonathan Turner , Sarang Dharmapurikar, Packet classification using coarse-grained tuple spaces, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185354]
• 29: Xuehong Sun , Yiqiang Q. Zhao, An On-Chip IP Address Lookup Algorithm, IEEE Transactions on Computers, v.54 n.7, p.873-885, July 2005 [doi>10.1109/TC.2005.107]
• 30: D. Taylor and J. Turner, "Classbench: A packet classification benchmark," in Proc. IEEE INFOCOM, 2005.
• 31: D. Taylor and J. Turner, "Scalable packet classification using distributed crossproducting of field labels," in Proc. IEEE INFOCOM, 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
dynamic programming, one- and two-dimensional tries, packet classification, succinct representation