Bidirectional Range Extension for TCAM-Based Packet Classi cation

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01059111
Contributor : Hal Ifip <>
Submitted on : Friday, August 29, 2014 - 1:27:56 PM
Last modification on : Friday, August 11, 2017 - 3:24:59 PM
Long-term archiving on : Sunday, November 30, 2014 - 10:42:17 AM

File

main.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Yan Sun, Min Sik Kim. Bidirectional Range Extension for TCAM-Based Packet Classi cation. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. pp.351-361, ⟨10.1007/978-3-642-12963-6_28⟩. ⟨hal-01059111⟩

Share

Metrics

Record views

88

Files downloads

157