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

research-article

DPPC-RE: TCAM-Based Distributed Parallel Packet Classification with Range Encoding

Authors:

Xin ZhangAuthors Info & Claims

IEEE Transactions on Computers, Volume 55, Issue 8

Pages 947 - 961

https://doi.org/10.1109/TC.2006.123

Published: 01 August 2006 Publication History

Abstract

Packet classification has been a critical data path function for many emerging networking applications. An interesting approach is the use of Ternary Content Addressable Memory (TCAM) to achieve deterministic, high-speed packet classification performance. However, apart from high cost and power consumption, due to slow growing clock rate for memory technology, in general, the traditional single TCAM-based solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the throughput performance. This scheme seamlessly integrates with a range encoding scheme which not only solves the range matching problem, but also ensures a balanced high throughput performance. A thorough theoretical worst-case analysis of throughput, processing delay, and power consumption, as well as the experimental results show that the proposed solution can achieve scalable throughput performance matching up to OC768 line rate or higher. The added TCAM storage overhead is found to be reasonably small for the five real-world classifiers studied.

References

[1]

V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Four Switching,” Proc. ACM SIGCOMM Conf., 1998.

Digital Library

[2]

T.V. Lakshman and D. Stiliadis, “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching,” Proc. ACM SIGCOMM Conf., 1998.

Digital Library

[3]

M. Buddhikot, S. Suri, and M. Waldvogel, “Space Decomposition Techniques for Fast Layer-4 Switching,” Proc. Conf. Protocols for High Speed Networks IV (PfHSN '99), 1999.

Digital Library

[4]

A. Feldmann and S. Muthukrishnan, “Tradeoffs for Packet Classification,” Proc. IEEE INFOCOM Conf., 2000.

[5]

F. Baboescu, S. Singh, G. Varghese, “Packet Classification for Core Routers: Is There an Alternative to CAMs?” Proc. IEEE INFOCOM Conf., 2003.

[6]

P. Gupta and N. McKeown, “Packet Classification on Multiple Fields,” Proc. ACM SIGCOMM Conf., 1999.

Digital Library

[7]

P. Gupta and N. McKeown, “Packet Classification Using Hierarchical Intelligent Cuttings,” IEEE Micro Magazine, vol. 20, no. 1, pp. 34-41, Jan.-Feb. 2000.

Digital Library

[8]

V. Srinivasan, S. Suri, and G. Varghese, “Packet Classification Using Tuple Space Search,” Proc. ACM SIGCOMM Conf., 1999.

Digital Library

[9]

S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification Using Multidimensional Cutting,” Proc. ACM SIGCOMM Conf., 2003.

Digital Library

[10]

E. Spitznagel, D. Taylor, and J. Turner, “Packet Classification Using Extended TCAMs,” Proc. 11th Int'l Conf. Network Protocol (ICNP '03), 2003.

Digital Library

[11]

T. Lakshman and D. Stiliadis, “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching,” ACM SIGCOMM Computer Comm. Rev., vol. 28, no. 4, pp. 203-214, Oct. 1998.

Digital Library

[12]

H. Liu, “Effcient Mapping of Range Classier into Ternary CAM,” Proc. 10th Symp. High Performance Interconnects (HotI '02), Aug. 2002.

Digital Library

[13]

J. van Lunteren and A.P.J. Engbersen, “Dynamic Multi-Field Packet Classification,” Proc. Globecom '02 Conf., pp. 2215-2219, Nov. 2002.

[14]

IEEE J. Selected Areas in Comm., vol. 21, no. 4, pp.560-571, May 2003.

[15]

H. Che, Z. Wang, K. Zheng, and B. Liu, “DRES: Dynamic Range Encoding Scheme for TCAM Coprocessors,” technique report, Univ. of Texas at Arlington,

[16]

K. Zheng, C.C. Hu, H.B. Lu, and B. Liu, “An Ultra High Throughput and Power Efficient TCAM-Based IP Lookup Engine,” Proc. IEEE INFOCOM Conf., Apr. 2004.

[17]

J.L. Hennessy and D.A. Patterson, Computer Architecture: A Quantitative Approach, third ed. Morgan Kaufmann, 2002.

Digital Library

[18]

J. Turner, “Real-World Rule Databases,” St. Louis, Mo.: Washington Univ., 2004.

[19]

IEEE Trans. Computers, vol. 53, no. 12, pp. 1602-1614, 2004.

Digital Library

[20]

Cypress Ayama 10K/20K NSE Series TCAM products,

[21]

Intel Pentium IV Series CPU products,

[22]

F. Zane, G. Narlikar, A. Basu, “CoolCAMs: Power-Efficient TCAMs for Forwarding Engines,” Proc. IEEE INFOCOM '03, 2003.

[23]

Cisco CRS-1 Carrier Routing System,

[24]

Proc. IEEE INFOCOM '05, vol. 1, pp. 293-303, Mar. 2005.

[25]

H. Lu and S. Sahni, “O(log W) Multidimensional Packet Classification,” IEEE/ACM Trans. Networking, to appear.

[26]

H. Lu, “Improved Trie Partitioning for Cooler TCAMs,” Proc. IASTED Int'l Conf. Advances in Computer Science and Technology (ACST), 2004.

[27]

R. Panigrahy and S. Sharma, “Reducing TCAM Power Consumption and Increasing Throughput,” Proc. 10th Symp. High Performance Interconnects HOT Interconnects (HotI '02), 2002.

Digital Library

Cited By

Jin ZJia W(2022)P³FA: Unified Unicast/Multicast Forwarding Algorithm for High-Performance Router/SwitchIEEE Transactions on Consumer Electronics10.1109/TCE.2022.320028368:4(327-335)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCE.2022.3200283
Abbasi MRezaei HMenon VQi LKhosravi M(2021)Enhancing the Performance of Flow Classification in SDN-Based Intelligent Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301404422:7(4141-4150)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1109/TITS.2020.3014044
Abbasi MShokrollahi A(2020)Enhancing the performance of decision tree-based packet classification algorithms using CPU clusterCluster Computing10.1007/s10586-020-03081-723:4(3203-3219)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10586-020-03081-7
Show More Cited By

Index Terms

DPPC-RE: TCAM-Based Distributed Parallel Packet Classification with Range Encoding

Recommendations

Range Matching without TCAM Entries Expansion for Packet Classification
FCST '09: Proceedings of the 2009 Fourth International Conference on Frontier of Computer Science and Technology

Packet classification has been widely used in network security protection. A number of the major techniques for network security protection, such as Virtual Private Networks (VPN), firewalls, and Network Intrusion Detection Systems (NIDS), are all ...
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 ...
TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 55, Issue 8

August 2006

141 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 August 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jin ZJia W(2022)P³FA: Unified Unicast/Multicast Forwarding Algorithm for High-Performance Router/SwitchIEEE Transactions on Consumer Electronics10.1109/TCE.2022.320028368:4(327-335)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCE.2022.3200283
Abbasi MRezaei HMenon VQi LKhosravi M(2021)Enhancing the Performance of Flow Classification in SDN-Based Intelligent Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301404422:7(4141-4150)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1109/TITS.2020.3014044
Abbasi MShokrollahi A(2020)Enhancing the performance of decision tree-based packet classification algorithms using CPU clusterCluster Computing10.1007/s10586-020-03081-723:4(3203-3219)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10586-020-03081-7
Abbasi MVakilian SFanian AKhosravi M(2019)Ingredients to enhance the performance of two-stage TCAM-based packet classifiers in internet of things: greedy layering, bit auctioning and range encodingEURASIP Journal on Wireless Communications and Networking10.1186/s13638-019-1617-82019:1Online publication date: 30-Dec-2019
https://dl.acm.org/doi/10.1186/s13638-019-1617-8
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
Abbasi MRafiee M(2019)A calibrated asymptotic framework for analyzing packet classification algorithms on GPUsThe Journal of Supercomputing10.1007/s11227-019-02861-275:10(6574-6611)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11227-019-02861-2
Bremler-Barr AHarchol YHay DHel-Or YHarchol YBremler-Barr AHay DHel-Or Y(2018)Encoding Short Ranges in TCAM Without ExpansionIEEE/ACM Transactions on Networking10.1109/TNET.2018.279769026:2(835-850)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2797690
Lee JByun HMun JLim H(2017)Utilizing 2-D leaf-pushing for packet classificationComputer Communications10.1016/j.comcom.2017.02.005103:C(116-129)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.comcom.2017.02.005
Bremler-Barr AHarchol YHay DHel-Or YScheideler CGilbert S(2016)Encoding Short Ranges in TCAM Without ExpansionProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935769(35-46)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935769
Liu AMeiners CTorng E(2016)Packet classification using binary content addressable memoryIEEE/ACM Transactions on Networking10.1109/TNET.2016.253361324:3(1295-1307)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2016.2533613
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents