Topological transformation approaches to optimizing TCAM-based packet classification systems

ABSTRACT

Several range reencoding schemes have been proposed to mitigate the effect of range expansion and the limitations of small capacity, large power consumption, and high heat generation of TCAM-based packet classification systems. However, they all disregard the semantics of classifiers and therefore miss significant opportunities for space compression.

In this paper, we propose new approaches to range reencoding by taking into account classifier semantics. Fundamentally different from prior work, we view reencoding as a topological transformation process from one colored hyperrectangle to another where the color is the decision associated with a given packet. We present two orthogonal, yet composable, reencoding approaches, domain compression and prefix alignment. Our techniques significantly outperform all previous reencoding techniques. In comparison with the state-of-the-art results, our experimental results show that our techniques achieve at least 7 times more space reduction in terms of TCAM space for an encoded classifier and at least 3 times more space reduction in terms of TCAM space for a reencoded classifier and its transformers.

REFERENCES

• 1: Cypress semiconductor. http://www.cypress.com/.
• 2: Integrated device technology. http://www.idt.com/.
• 3: David A. Applegate , Gruia Calinescu , David S. Johnson , Howard Karloff , Katrina Ligett , Jia Wang, Compressing rectilinear pictures and minimizing access control lists, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1066-1075, January 07-09, 2007, New Orleans, Louisiana
• 4: J. Bolaria and L. Gwennap. A guide to search engines and networking memory. http://www.linleygroup.com, 2004.
• 5: A. Bremler-Barr and D. Hendler. Space-efficient TCAM-based classification using gray coding. In proc 26th Annual IEEE Conf on Computer Communications (Infocom), May 2007.
• 6: Hao Che , Zhijun Wang , Kai Zheng , Bin Liu, DRES: Dynamic Range Encoding Scheme for TCAM Coprocessors, IEEE Transactions on Computers, v.57 n.7, p.902-915, July 2008 [doi>10.1109/TC.2007.70838]
• 7: Qunfeng Dong , Suman Banerjee , Jia Wang , Dheeraj Agrawal , Ashutosh Shukla, Packet classifiers in ternary CAMs can be smaller, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 8: R. Draves, C. King, S. Venkatachary, and B. Zill. Constructing optimal IP routing tables. In proc IEEE INFOCOM, pages 88--97, 1999.
• 9: Mohamed G. Gouda , Xiang-Yang Alex Liu, Firewall Design: Consistency, Completeness, and Compactness, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.320-327, March 24-26, 2004
• 10: Pankaj Gupta , Nick McKeown, Packet classification on multiple fields, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.147-160, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 11: P. Gupta and N. McKeown. Algorithms for packet classification. IEEE Network, 15(2):24--32, 2001.
• 12: 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
• 13: Karthik Lakshminarayanan , Anand Rangarajan , Srinivasan Venkatachary, Algorithms for advanced packet classification with ternary CAMs, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 14: Panos Lekkas, Network Processors: Architectures, Protocols and Platforms, McGraw-Hill, Inc., New York, NY, 2003
• 15: Alex X. Liu , Mohamed G. Gouda, Diverse Firewall Design, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.595, June 28-July 01, 2004
• 16: A.X. Liu and M.G. Gouda. Complete redundancy detection in firewalls. In proc 19th Annual IFIP Conf on Data and Applications Security, LNCS 3654, pages 196--209, August 2005.
• 17: A.X. Liu and M.G. Gouda. Complete redundancy removal for packet classifiers in tcams. IEEE Transactions on Parallel and Distributed Systems (TPDS), to appear. The conference version was published in the 19th Annual IFIP Conf on Data and Applications Security (DBSec), LNCS 3654, 2005.
• 18: A.X. Liu, C.R. Meiners, and Y. Zhou. All-match based complete redundancy removal for packet classifiers in TCAMs. In proc 27th Infocom, 2008.
• 19: Huan Liu, Efficient Mapping of Range Classifier into Ternary-CAM, Proceedings of the 10th Symposium on High Performance Interconnects HOT Interconnects, p.95, August 21-23, 2002
• 20: C.R. Meiners, A.X. Liu, and E. Torng. TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs. In proc ICNP, 2007.
• 21: C.R. Meiners, A.X. Liu, and E. Torng. Bit weaving: A non-prefix approach to compressing packet classifiers in tcams. Technical Report MSU-CSE-09-1, Department of Computer Science and Engineering, Michigan State University, January 2009.
• 22: Derek Pao , Yiu Keung Li , Peng Zhou, Efficient packet classification using TCAMs, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.18, p.3523-3535, 21 December 2006 [doi>10.1016/j.comnet.2006.01.009]
• 23: D. Pao, P. Zhou, B. Liu, and X. Zhang. Enhanced prefix inclusion coding filter-encoding algorithm for packet classification with ternary content addressable memory. IET Computers & Digital Techniques, 1(5):572--580, September 2007.
• 24: 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]
• 25: Ed Spitznagel , David Taylor , Jonathan Turner, Packet Classification Using Extended TCAMs, Proceedings of the 11th IEEE International Conference on Network Protocols, p.120, November 04-07, 2003
• 26: 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
• 27: S. Suri, T. Sandholm, and P. Warkhede. Compressing two-dimensional routing tables. Algorithmica, 35:287--300, 2003.
• 28: David E. Taylor, Survey and taxonomy of packet classification techniques, ACM Computing Surveys (CSUR), v.37 n.3, p.238-275, September 2005 [doi>10.1145/1108956.1108958]
• 29: D.E. Taylor and J.S. Turner. Classbench: A packet classification benchmark. In proc Infocom, 2005.
• 30: J. van Lunteren and T. Engbersen. Fast and scalable packet classification. IEEE Journals on Selected Areas in Communications, 21(4):560--571, 2003.
• 31: Fang Yu , T. V. Lakshman , Martin Austin Motoyama , Randy H. Katz, SSA: a power and memory efficient scheme to multi-match packet classification, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095905]
• 32: Kai Zheng , Hao Che , Zhijun Wang , Bin Liu , Xin Zhang, DPPC-RE: TCAM-Based Distributed Parallel Packet Classification with Range Encoding, IEEE Transactions on Computers, v.55 n.8, p.947-961, August 2006 [doi>10.1109/TC.2006.123]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Performance, Security

Keywords:
packet classification, range encoding, tcam