Karthik Lakshminarayanan
Abstract
Ternary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using TCAMs: reducing range expansion and multi-match classification.Our first algorithm addresses the problem of expansion of rules with range fields to represent range rules in TCAMs, a single range rule is mapped to multiple TCAM entries, which reduces the utilization of TCAMs. We propose a new scheme called Database Independent Range PreEncoding (DIRPE) that, in comparison to earlier approaches, reduces the worst-case number of TCAM entries a single rule maps on to. DIRPE works without prior knowledge of the database, scales when a large number of ranges is present, and has good incremental update properties.Our second algorithm addresses the problem of finding multiple matches in a TCAM. When searched, TCAMs return the first matching entry; however, new applications require either the first few or all matching entries. We describe a novel algorithm, called Multi-match Using Discriminators (MUD), that finds multiple matches without storing any per-search state information in the TCAM, thus making it suitable for multi-threaded environments. MUD does not increase the number of TCAM entries needed, and hence scales to large databases.Our algorithms do not require any modifications to existing TCAMs and are hence relatively easy to deploy. We evaluate the algorithms using real-life and random databases.
- F. Baboescu, S. Singh, and G. Varghese. Packet Classification for Core Routers: Is there an Alternative to CAMs? In Proc. of IEEE INFOCOM, 2003.Google Scholar
Cross Ref
- J. Beale. Snort 2.1 Intrusion Detection, Second Edn. Syngress, 2004. Google ScholarDigital Library
- J. Bolaria and L. Gwennap. A Guide to Search Engines and Networking Memory. http://www.linleygroup.com/Reports/memory_guide.html, April 2004.Google Scholar
- Computer Associates. eTrust Intrusion Detection System. http://www3.ca.com.Google Scholar
- Cypress Semiconductor Corp. Content addressable memory. http://www.cypress.com/.Google Scholar
- Dell'oro. Layer3 Switch Router Market. July 2004.Google Scholar
- W. Eatherton. Full Tree Bit Map: Hardware/Software IP Lookup Algorithms with Incremental Updates. EE Masters Thesis, Washington University, April 1999.Google Scholar
- P. Gupta and N. McKeown. Packet Classification on Multiple Fields. In Proc. of ACM SIGCOMM, 1999. Google ScholarDigital Library
- Integrated Device Technology, Inc. Content addressable memory. http://www.idt.com/.Google Scholar
- Intel Corp. Intel IXP2800 Network Processor. http://www.intel.com/design/network/products/npfamily/ixp2800.htm.Google Scholar
- H. Liu. Efficient Mapping of Range Classifier into Ternary-CAM. In Proc. of Hot Interconnects, 2002. Google ScholarDigital Library
- Netlogic Microsystems. Content addressable memory. http://www.netlogicmicro.com/.Google Scholar
- S. Nilsson and G. Karlsson. Fast Address Look-Up for Internet Routers. Proceedings of IEEE Broadband Communications'98, Stuttgart, Germany, April 1998. Google ScholarDigital Library
- L. Qiu, G. Varghese, and S. Suri. Fast Firewall Implementations for Software and Hardware-based Routers. In Proc. of ICNP, 2001. Google ScholarDigital Library
- S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet Classification using Multidimensional Cutting. In Proc. of ACM SIGCOMM, 2003. Google ScholarDigital Library
- E. Spitznagel, D. Taylor, and J. Turner. Packet Classification Using Extended TCAMs. In Proc. of ICNP, 2003. Google ScholarDigital Library
- V. Srinivasan and G. Varghese. Faster IP Lookups using Controlled Prefix Expansion. ACM TOCS, February 1999. Google ScholarDigital Library
- V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel. Fast and Scalable Layer Four Switching. In Proc. of ACM SIGCOMM, 1998. Google ScholarDigital Library
- D. E. Taylor. Survey and Taxonomy of Packet Classification Techniques. Technical Report WUCSE-2004-24, Washington Univ., St. Louis, May 2004.Google Scholar
- D. E. Taylor and J. Turner. Scalable Packet Classification using Distributed Crossproducting of Field Labels. Technical Report WUCSE-2004-38, Washington Univ., St. Louis, 2004.Google Scholar
- P. Tsuchiya. A Search Algorithm for Table Entries with Non-contiguous Wildcarding. Unpublished document, 1992.Google Scholar
- J. van Lunteren and T. Engbersen. Fast and Scalable Packet Classification. IEEE JSAC, 21:560--571, May 2003. Google ScholarDigital Library
- G. Varghese. Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices. Morgan Kaufmann Publishers, Inc., 2004. Google ScholarDigital Library
- T. Y. C. Woo. A Modular Approach to Packet Classification: Algorithms and Results. In Proc. of IEEE INFOCOM, 2000.Google ScholarCross Ref
- F. Yu and R. H. Katz. Efficient Multi-Match Packet Classification with TCAM. In Proc. of HotI, 2004. Google ScholarDigital Library
Index Terms
- Algorithms for advanced packet classification with ternary CAMs
Recommendations
Algorithms for advanced packet classification with ternary CAMs
SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communicationsTernary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using ...
Hardware-based multi-match packet classification in NIDS: an overview and novel extensions for improving the energy efficiency of TCAM-based classifiers
AbstractNetwork intrusion detection systems (NIDS) require all the header matching rules to be reported which is termed as multi-match packet classification. Ternary content-addressable memories (TCAMs) are the preferred choice for performing hardware-...
Tcam-based multi-match packet classification using multidimensional rule layering
Ternary content addressable memory (TCAM) has superior performance for single-match packet classification but not the case for multi-match packet classification. The limitation is caused by TCAM architecture that reports only the first matching rule. To ...
Comments