%0 Conference Proceedings
%T Bidirectional Range Extension for TCAM-Based Packet Classi cation
%+ School of Electrical Engineering and Computer Science (EECS)
%A Sun, Yan
%A Kim, Min Sik
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 9th International IFIP TC 6 Networking Conference (NETWORKING)
%C Chennai, India
%Y Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan
%I Springer
%3 NETWORKING 2010
%V LNCS-6091
%P 351-361
%8 2010-05-11
%D 2010
%R 10.1007/978-3-642-12963-6_28
%K packet classification
%K TCAM
%K bidirectional range extension
%Z Computer Science [cs]/Digital Libraries [cs.DL]Conference papers
%X Packet classification is a fundamental task for network devices such as edge routers, firewalls, and intrusion detection systems. Currently, most vendors use Ternary Content Addressable Memories (TCAMs) to achieve high-performance packet classification. TCAMs use parallel hardware to check all rules simultaneously. Despite their high speed, TCAMs have a problem in dealing with ranges efficiently. Many packet classification rules contain range specifications, each of which needs to be translated into multiple prefixes to store in a TCAM. Such translation may result in an exponential increase in the number of required TCAM entries. In this paper, we propose a bidirectional range extension algorithm to solve this problem. The proposed algorithm uses at most two TCAM entries to represent a range, and can be pipelined to deal with multiple range fields in a packet header. Since this algorithm assumes a non-redundant rule set, i.e., no range overlap between different rules, which can be obtained by applying our previous work on redundancy removal in TCAM using a tree representation of rules. Our experiments show a more than 75% reduction in the number of TCAM entries by applying the bidirectional range extension algorithm to realworld rule sets.
%G English
%2 https://inria.hal.science/hal-01059111/document
%2 https://inria.hal.science/hal-01059111/file/main.pdf
%L hal-01059111
%U https://inria.hal.science/hal-01059111
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-LNCS-6091
%~ IFIP-TC
%~ IFIP-TC6
%~ IFIP-NETWORKING
%~ IFIP-2010