More Web Proxy on the site http://driver.im/

article

Optimal in/out TCAM encodings of ranges

Authors:

Ori Rottenstreich,

Isaac Keslassy,

Avinatan Hassidim,

Ely PoratAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 24, Issue 1

Pages 555 - 568

https://doi.org/10.1109/TNET.2014.2382031

Published: 01 February 2016 Publication History

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.

References

[1]

D. E. Taylor, "Survey and taxonomy of packet classification techniques," Comput. Surveys, vol. 37, no. 3, pp. 238-275, 2005.

Digital Library

[2]

G. Varghese, Network Algorithmics. San Mateo, CA, USA: Morgan Kaufmann, 2004.

Digital Library

[3]

J. Chao and B. Liu, High Performance Switches and Routers. Hoboken, NJ, USA: Wiley, 2007.

[4]

J. Naous, D. Erickson, G. A. Covington, G. Appenzeller, and N. McKeown, "Implementing an OpenFlow switch on the NetFPGA platform," in Proc. ACM/IEEE ANCS, 2008, pp. 1-9.

Digital Library

[5]

NetLogic Microsystems, "NetLogic Microsystems,".

[6]

Renesas, Tokyo, Japan, "Renesas," [Online]. Available: http://www. renesas.com/

[7]

P. Gupta and N. McKeown, "Packet classification on multiple fields," in Proc. ACM SIGCOMM, 1999, pp. 147-160.

Digital Library

[8]

S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet classification using multidimensional cutting," in Proc. ACM SIGCOMM, 2003, pp. 213-224.

Digital Library

[9]

A. Bremler-Barr and D. Hendler, "Space-efficient TCAM-based classification using gray coding," IEEE Trans. Comput., vol. 61, no. 1, pp. 18-30, Jan. 2012.

Digital Library

[10]

K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, "Algorithms for advanced packet classification with ternary CAMs," in Proc. ACM SIGCOMM, 2005, pp. 193-204.

Digital Library

[11]

V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, "Fast and scalable layer four switching," in Proc. ACM SIGCOMM, 1998, pp. 191-202.

Digital Library

[12]

O. Rottenstreich, R. Cohen, D. Raz, and I. Keslassy, "Exact worst-case TCAM rule expansion," IEEE Trans. Comput., vol. 62, no. 6, pp. 1127-1140, Jun. 2013.

Digital Library

[13]

S. Suri, T. Sandholm, and P. R. Warkhede, "Compressing two-dimensional routing tables," Algorithmica, vol. 35, no. 4, pp. 287-300, 2003.

[14]

R. Draves, C. King, S. Venkatachary, and B. D. Zill, "Constructing optimal IP routing tables," in Proc. IEEE INFOCOM, 1999, pp. 88-97.

[15]

T. Sasao, "On the complexity of classification functions," in Proc. ISMVL, 2008, pp. 57-63.

Digital Library

[16]

Y.-K. Chang, C.-I. Lee, and C.-C. Su, "Multi-field range encoding for packet classification in TCAM," in IEEE INFOCOM Mini-Conf., 2011, pp. 196-200.

[17]

E. Spitznagel, D. E. Taylor, and J. S. Turner, "Packet classification using extended TCAMs," in Proc. IEEE ICNP, 2003, pp. 120-131.

Digital Library

[18]

H. Che, Z. Wang, K. Zheng, and B. Liu, "DRES: Dynamic range encoding scheme for TCAM coprocessors," IEEE Trans. Comput., vol. 57, no. 7, pp. 902-915, Jul. 2008.

Digital Library

[19]

A. X. Liu, C. R. Meiners, and Y. Zhou, "All-match based complete redundancy removal for packet classifiers in TCAMs," in Proc. IEEE INFOCOM, 2008, pp. 574-582.

[20]

C. R. Meiners, A. X. Liu, and E. Torng, "Bit weaving: A non-prefix approach to compressing packet classifiers in TCAMs," IEEE/ACM Trans. Netw., vol. 20, no. 2, pp. 488-500, Apr. 2012.

Digital Library

[21]

D. Applegate et al., "Compressing rectilinear pictures and minimizing access control lists," in Proc. SODA, 2007, pp. 1066-1075.

Digital Library

[22]

A. X. Liu, C. R. Meiners, and E. Torng, "TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs," IEEE/ACM Trans. Netw., vol. 18, no. 2, pp. 490-500, Apr. 2010.

Digital Library

[23]

C. R. Meiners, A. X. Liu, E. Torng, and J. Patel, "Split: Optimizing space, power, and throughput for TCAM-based classification," in Proc. ACM/IEEE ANCS, 2011, pp. 200-210.

Digital Library

[24]

C. R. Meiners, A. X. Liu, and E. Torng, "Topological transformation approaches to TCAM-based packet classification," IEEE/ACM Trans. Netw., vol. 19, no. 1, pp. 237-250, Feb. 2011.

Digital Library

[25]

O. Rottenstreich and I. Keslassy, "On the code length of TCAM coding schemes," in Proc. IEEE ISIT, 2010, pp. 1908-1912.

[26]

B. Schieber, D. Geist, and A. Zaks, "Computing the minimum DNF representation of Boolean functions defined by intervals," Discrete Appl. Math., vol. 149, no. 1-3, pp. 154-173, 2005.

Digital Library

[27]

E. Norige, A. X. Liu, and E. Torng, "A ternary unification framework for optimizing TCAM-based packet classification systems," in Proc. ACM/IEEE ANCS, 2013, pp. 95-104.

Digital Library

[28]

A. X. Liu and M. G. Gouda, "Complete redundancy removal for packet classifiers in TCAMs," IEEE Trans. Parallel Distrib. Syst., vol. 21, no. 4, pp. 424-437, Apr. 2010.

Digital Library

[29]

K. Kogan et al., "SAX-PAC (Scalable and eXpressive PAcket Classification)," in Proc. ACM SIGCOMM, 2014, pp. 15-26.

Digital Library

[30]

O. Rottenstreich, A. Berman, Y. Cassuto, and I. Keslassy, "Compression for fixed-width memories," in Proc. IEEE ISIT, 2013, pp. 2379-2383.

[31]

G. Rétvári, J. Tapolcai, A. Kőrösi, A. Majdán, and Z. Heszberger, "Compressing IP forwarding tables: Towards entropy bounds and beyond," in Proc. ACM SIGCOMM, 2013, pp. 111-122.

Digital Library

[32]

O. Rottenstreich et al., "Compressing forwarding tables for datacenter scalability," IEEE J. Sel. Areas Commun., vol. 32, no. 1, pp. 138-151, Jan. 2014.

[33]

W. Jiang and V. K. Prasanna, "Scalable packet classification on FPGA," IEEE Trans. VLSI Syst., vol. 20, no. 9, pp. 1668-1680, Sep. 2012.

Digital Library

[34]

O. Rottenstreich et al., "Optimal In/Out TCAM encodings of ranges," Technion, Haifa, Israel, Tech. Rep., 2014 [Online]. Available: http://webee.technion.ac.il/people/or/publications/Optimal_TCAM_TR.pdf

[35]

D. E. Taylor and J. S. Turner, "ClassBench: A packet classification benchmark," in Proc. IEEE INFOCOM, 2005, vol. 3, pp. 2068-2079.

Cited By

M. DSk N(2024)TeRaIntegration, the VLSI Journal10.1016/j.vlsi.2024.10215396:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.vlsi.2024.102153
M DSk N(2023)Deterministic Approach for Range-enhanced Reconfigurable Packet Classification EngineACM Transactions on Reconfigurable Technology and Systems10.1145/358657716:2(1-26)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1145/3586577
Jung CKim SJang RMohaisen DNyang DYin HStavrou ACremers CShi E(2022)A Scalable and Dynamic ACL System for In-Network DefenseProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560606(1679-1693)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560606
Show More Cited By

Index Terms

Optimal in/out TCAM encodings of ranges

Recommendations

Finding nonequivalent classifiers in boolean space to reduce tcam usage

Packet classification is one of the major challenges today in designing high-speed routers and firewalls, as it involves sophisticated multi-dimensional searching. Ternary content addressable memory (TCAM) has been widely used to implement packet ...
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 ...
Space-Efficient TCAM-Based Classification Using Gray Coding

Ternary content-addressable memories (TCAMs) are increasingly used for high-speed packet classification. TCAMs compare packet headers against all rules in a classification database in parallel and thus provide high throughput unparalleled by software-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 24, Issue 1

February 2016

635 pages

ISSN:1063-6692

Editor:
R. Srikant
Dept. Elect. & Comput. Eng., Univ. Illinois at Urbana-Champaign, Urbana, IL

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2016

Accepted: 11 November 2014

Revised: 30 October 2013

Received: 17 March 2013

Published in TON Volume 24, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
107
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

M. DSk N(2024)TeRaIntegration, the VLSI Journal10.1016/j.vlsi.2024.10215396:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.vlsi.2024.102153
M DSk N(2023)Deterministic Approach for Range-enhanced Reconfigurable Packet Classification EngineACM Transactions on Reconfigurable Technology and Systems10.1145/358657716:2(1-26)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1145/3586577
Jung CKim SJang RMohaisen DNyang DYin HStavrou ACremers CShi E(2022)A Scalable and Dynamic ACL System for In-Network DefenseProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560606(1679-1693)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560606
Srinivasavarma VPydi SMahammad S(2022)Hardware-based multi-match packet classification in NIDS: an overview and novel extensions for improving the energy efficiency of TCAM-based classifiersThe Journal of Supercomputing10.1007/s11227-022-04377-878:11(13086-13121)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s11227-022-04377-8
Srinivasavarma VVidhyut SS N(2020)A TCAM-based Caching Architecture Framework for Packet ClassificationACM Transactions on Embedded Computing Systems10.1145/340910920:1(1-19)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1145/3409109
Pan MMacDavid RLandau-Feibish SRexford J(2020)Memory-Efficient Membership Encoding in SwitchesProceedings of the Symposium on SDN Research10.1145/3373360.3380842(110-116)Online publication date: 3-Mar-2020
https://dl.acm.org/doi/10.1145/3373360.3380842
Li WLiu XLe WLi HZhang H(2019)A Practical Range Encoding Scheme for TCAMsProceedings of the ACM SIGCOMM 2019 Conference Posters and Demos10.1145/3342280.3342346(163-165)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3342280.3342346
Vegesna SNara ASk N(2019)A Novel Rule Mapping on TCAM for Power Efficient Packet ClassificationACM Transactions on Design Automation of Electronic Systems10.1145/332810324:5(1-23)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3328103
Demianiuk VKogan KNikolenko S(2019)Approximate Classifiers with Controlled AccuracyIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737476(2044-2052)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737476
Norige ELiu ATorng ETorng ENorige ELiu A(2018)A Ternary Unification Framework for Optimizing TCAM-Based Packet Classification SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2018.280958326:2(657-670)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2809583
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents