Optimal In/Out TCAM Encodings of Ranges
Authors:
- 9 January 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 24 (1) , 555-568
Abstract
Hardware-based packet classification has become an essential component in many networking devices. It often relies on ternary content-addressable memories (TCAMs), which compare the packet header against a set of rules. TCAMs are not well suited to encode range rules. Range rules are often encoded by multiple TCAM entries, and little is known about the smallest number of entries that one needs for a specific range. In this paper, we introduce the In/Out TCAM, a new architecture that combines a regular TCAM together with a modified TCAM. This custom architecture enables independent encoding of each rule in a set of rules. We provide the following theoretical results for the new architecture: 1) We give an upper bound on the worst-case expansion of range rules in one and two dimensions. 2) For extremal ranges, which are 89% of the ranges that occur in practice, we provide an efficient algorithm that computes an optimal encoding. 3) We present a closed-form formula for the average expansion of an extremal range.Keywords
Funding Information
- Israel Science Foundation (822/10, 1241/12)
- United States-Israel Binational Science Foundation (2012344)
- German-Israeli Foundation for Scientific Research and Development (GIF) (1161/2011)
- Israeli Centers of Research Excellence (I-CORE) (4/11)
- Gordon Fund for Systems Engineering
- Neptune Magnet Consortium
- Israel Ministry of Science and Technology
- Intel ICRI-CI Center
- Hasso Plattner Institute Research School
- Technion Funds for Security Research
- Erteschik and Greenberg Research Funds
This publication has 28 references indexed in Scilit:
- SAX-PAC (Scalable And eXpressive PAcket Classification)ACM SIGCOMM Computer Communication Review, 2014
- A Ternary Unification Framework for optimizing TCAM-based packet classification systems2013
- Compression for fixed-width memories2013
- All-Match Based Complete Redundancy Removal for Packet Classifiers in TCAMs2008
- Survey and taxonomy of packet classification techniquesACM Computing Surveys, 2005
- Algorithms for advanced packet classification with ternary CAMsACM SIGCOMM Computer Communication Review, 2005
- Computing the minimum DNF representation of Boolean functions defined by intervalsDiscrete Applied Mathematics, 2005
- Packet classification using multidimensional cutting2003
- Compressing Two-Dimensional Routing TablesAlgorithmica, 2003
- Packet classification on multiple fieldsACM SIGCOMM Computer Communication Review, 1999