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.
Type de document :
Communication dans un congrès
Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.351-361, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_28〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01059111
Contributeur : Hal Ifip <>
Soumis le : vendredi 29 août 2014 - 13:27:56
Dernière modification le : vendredi 11 août 2017 - 15:24:59
Document(s) archivé(s) le : dimanche 30 novembre 2014 - 10:42:17

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yan Sun, Min Sik Kim. Bidirectional Range Extension for TCAM-Based Packet Classi cation. Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.351-361, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_28〉. 〈hal-01059111〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

125