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.
- K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, "Algorithms for Advanced Packet Classification with Ternary CAMs," Proc. ACM Sigcomm, 2005. Google ScholarDigital Library
- F. Yu and R. H. Katz, "Efficient Multi-Match Packet Classification with TCAM," Hot Interconnects, August, 2004. Google ScholarDigital Library
- "SNORT Network Intrusion Detection System." http://www.snort.org.Google Scholar
- S. Dharmapurikar, M. Attig, and J. Lockwood, "Deep packet inspection using parallel bloom filters," IEEE Micro, 2004. Google ScholarDigital Library
- Y. H. Cho and W. H. MangioneSmith, "A Pattern Matching Coprocessor for Network Security," Proc. DAC, 2005. Google ScholarDigital Library
- C. R. Clark and D. E. Schimmel, "Scalable pattern matching for high speed networks," Proc. IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2004. Google ScholarDigital Library
- Z. K. Baker and V. K. Prasanna, "Time and area efficient pattern matching on FPGAs," Proc. International Symposium on Field Programmable Gate Arrays (FPGA), 2004. Google ScholarDigital Library
- 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.Google Scholar
- F. Yu, R. H. Katz, and T. V. Lakshman, "Gigabit Rate Packet Pattern Matching with TCAM," Proc. ICNP, Berlin, Germany, October, 2004. Google ScholarDigital Library
- F. Baboescu, S. Singh, and G. Varghese, "Packet Classification for Core Routers: Is there an alternatives to CAMs?," Proc. IEEE Infocom, 2003.Google ScholarCross Ref
- P. Gupta and N. McKeown, "Packet classification using hierarchical intelligent cuttings," Proc. Hot Interconnects, August, 1999.Google Scholar
- E. Spitznagel, D. Taylor, and J. Turner, "Classification Using Extended TCAMs," Proc. IEEE International Conference on Network Protocols (ICNP), 2003. Google ScholarDigital Library
- P. Gupta and N. McKeown, "Algorithms for Packet Classification," Proc. IEEE Network, 2001.Google ScholarDigital Library
- D. E. Taylor, "Survey Taxonomy of Packet Classification Techniques," Proc. Tech Report, WUCSE-2004-24, May 2003.Google Scholar
- F. Zane, G. Narlikar, and A. Basu, "CoolCAMs: Power-Efficient TCAMs for Forwarding Engines," INFOCOM, March 2003.Google Scholar
- R. Panigrahy and S. Sharma, "Reducing TCAM Power Consumption and Increasing Throughput," Proc. Hot Interconnects, 2001. Google ScholarDigital Library
- 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.Google Scholar
- H. Song and J. W. Lockwood, "Efficient packet classification for network intrusion detection using FPGA," Proc. International Symposium on Field Programmable Gate Arrays (FPGA), Monterey, USA, 2005. Google ScholarDigital Library
- V. Srinivasan and G. Varghese, "Faster IP lookups using controlled prefix expansion," Proc. ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 1998. Google ScholarDigital Library
- V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, "Fast and Scalable Layer Four Switching," Proc. Sigcomm, Spetember 1998. Google ScholarDigital Library
- P. Gupta and N. McKeown, "Packet classification on multiple fields," Proc. SIGCOMM, August 1999. Google ScholarDigital Library
- S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet Classification Using Multidimensional Cutting," Proc. Sigcomm, August 2003. Google ScholarDigital Library
- P. Crescenzi and V. Kann, "A compendium of NP optimization problems." http://www.nada.kth.se/~viggo/wwwcompendium/node145.html.Google Scholar
- 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.Google Scholar
- D. S. Johnson, "Approximation algorithms for combinatorial problems," Proc. the fifth annual ACM symposium on Theory of computing, 1973. Google ScholarDigital Library
- M. Hidell, P. Sjödin, and O. Hagsand, "Router Architectures," Tutorial at Networking 2004.Google Scholar
- 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).Google Scholar
- H. Liu, "conference on Measurement and modeling of computer systems," Proc. Hot Interconnects, 2001.Google Scholar
- "Measurement & Operations Analysis Team from the National Library for Applied Network Research (NLANR) project," 2001.Google Scholar
Index Terms
- SSA: a power and memory efficient scheme to multi-match packet classification
Recommendations
Efficient Multimatch Packet Classification for Network Security Applications
New network applications like intrusion detection systems and packet-level accounting require multimatch packet classification, where all matching filters need to be reported. Ternary content addressable memories (TCAMs) have been adopted to solve the ...
Split: Optimizing Space, Power, and Throughput for TCAM-Based Classification
ANCS '11: Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications SystemsUsing Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classication has become the de facto standard in industry because TCAMs facilitate constant time classication by comparing packet elds against ternary encoded rules in ...
Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks
In wavelength division multiplexing (WDM) networks, tens or hundreds of wavelengths can be transmitted over a single fiber. As transmission line speed goes to 10Gb/s and beyond, ternary CAM (TCAM) is usually employed for wire speed packet ...
Comments