SSA: a power and memory efficient scheme to multi-match packet classification

ABSTRACT

New network applications like intrusion detection systems and packet-level accounting require multi-match packet classification, where all matching filters need to be reported. Ternary Content Addressable Memories (TCAMs) have been adopted to solve the multi-match classification problem due to their ability to perform fast parallel matching. However, TCAM is expensive and consumes large amounts of power. None of the previously published multi-match classification schemes is both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new Set Splitting Algorithm (SSA). The main idea of SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least half the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low power consumption. We compare SSA with two best known schemes: MUD [1] and Geometric Intersection-based solutions [2]. Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75% to 95% reduction in power consumption. Compared with Geometric Intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet.

REFERENCES

• 1: 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
• 2: F. Yu and R. H. Katz, "Efficient Multi-Match Packet Classification with TCAM," Hot Interconnects, August, 2004.
• 3: "SNORT Network Intrusion Detection System." http://www.snort.org.
• 4: S. Dharmapurikar, M. Attig, and J. Lockwood, "Deep packet inspection using parallel bloom filters," IEEE Micro, 2004.
• 5: Young H. Cho , William H. Mangione-Smith, A pattern matching coprocessor for network security, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065641]
• 6: Christopher R. Clark , David E. Schimmel, Scalable Pattern Matching for High Speed Networks, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.249-257, April 20-23, 2004
• 7: Zachary K. Baker , Viktor K. Prasanna, Time and area efficient pattern matching on FPGAs, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968312]
• 8: M. Aldwairi, T. Conte, and P. Franzon, "Configurable string matching hardware for speedup up intrusion detection," Proc. Workshop on Architectural Support for Security and Anti-virus (WASSA) Held in Cooperation with ASPLOS XI, 2004.
• 9: Fang Yu , Randy H. Katz , T. V. Lakshman, Gigabit Rate Packet Pattern-Matching Using TCAM, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.174-183, October 05-08, 2004
• 10: F. Baboescu, S. Singh, and G. Varghese, "Packet Classification for Core Routers: Is there an alternatives to CAMs?," Proc. IEEE Infocom, 2003.
• 11: P. Gupta and N. McKeown, "Packet classification using hierarchical intelligent cuttings," Proc. Hot Interconnects, August, 1999.
• 12: 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
• 13: P. Gupta and N. McKeown, "Algorithms for Packet Classification," Proc. IEEE Network, 2001.
• 14: D. E. Taylor, "Survey Taxonomy of Packet Classification Techniques," Proc. Tech Report, WUCSE-2004-24, May 2003.
• 15: F. Zane, G. Narlikar, and A. Basu, "CoolCAMs: Power-Efficient TCAMs for Forwarding Engines," INFOCOM, March 2003.
• 16: Rina Panigrahy , Samar Sharma, Reducing TCAM Power Consumption and Increasing Throughput, Proceedings of the 10th Symposium on High Performance Interconnects HOT Interconnects (HotI'02), p.107, August 21-23, 2002
• 17: K. Zheng, H. Che, Z. Wang, and B. Liu, "an ultra high throughput and power efficient TCAM based IP lookup engine," Proc. IEEE Infocom, 2004.
• 18: Haoyu Song , John W. Lockwood, Efficient packet classification for network intrusion detection using FPGA, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046223]
• 19: 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
• 20: 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
• 21: 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
• 22: 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]
• 23: P. Crescenzi and V. Kann, "A compendium of NP optimization problems." http://www.nada.kth.se/~viggo/wwwcompendium/node145.html.
• 24: G. Andersson and L. Engebretsen, "Better Approximation Algorithms and Tighter Analysis for SET SPLITTING and NOT-ALL-EQUAL SAT," Proc. technical reports, ECCCTR: Electronic Colloquium on Computational Complexity, 1998.
• 25: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 26: M. Hidell, P. Sjödin, and O. Hagsand, "Router Architectures," Tutorial at Networking 2004.
• 27: M. Kobayashi, T. Murase, and A. Kuriyama, "A longest prefix match search engine for multi-gigabit ip processing," Proc. International Conference on Communications (ICC 2000).
• 28: H. Liu, "conference on Measurement and modeling of computer systems," Proc. Hot Interconnects, 2001.
• 29: "Measurement & Operations Analysis Team from the National Library for Applied Network Research (NLANR) project," 2001.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
TCAM, energy-efficient design, multiple-match, packet classification