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

article

Survey and taxonomy of packet classification techniques

Author:

David E. TaylorAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 37, Issue 3

Pages 238 - 275

https://doi.org/10.1145/1108956.1108958

Published: 01 September 2005 Publication History

Abstract

Packet classification is an enabling function for a variety of Internet applications including quality of service, security, monitoring, and multimedia communications. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. In general, there have been two major threads of research addressing packet classification, algorithmic and architectural. A few pioneering groups of researchers posed the problem, provided complexity bounds, and offered a collection of algorithmic solutions. Subsequently, the design space has been vigorously explored by many offering new algorithms and improvements on existing algorithms. Given the inability of early algorithms to meet performance constraints imposed by high speed links, researchers in industry and academia devised architectural solutions to the problem. This thread of research produced the most widely-used packet classification device technology, Ternary Content Addressable Memory (TCAM). New architectural research combines intelligent algorithms and novel architectures to eliminate many of the unfavorable characteristics of current TCAMs. We observe that the community appears to be converging on a combined algorithmic and architectural approach to the problem. Using a taxonomy based on the high-level approach to the problem and a minimal set of running examples, we provide a survey of the seminal and recent solutions to the problem. It is our hope to foster a deeper understanding of the various packet classification techniques while providing a useful framework for discerning relationships and distinctions.

References

[1]

Baboescu, F., Singh, S., and Varghese, G. 2003. Packet classification for core routers: Is there an alternative to CAMs? In IEEE Infocom.

[2]

Baboescu, F. and Varghese, G. 2001. Scalable packet classification. In ACM Sigcomm.

[3]

C. Bormann, Ed. 2001. RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP, and uncompressed. RFC 3095. IETF Network Working Group.

[4]

Chandranmenon, G. and Varghese, G. 1996. Trading packet headers for packet processing. IEEE/ACM Trans. Network. 4, 2 (April) 141--152.

[5]

Chang, F., Li, K., and chang Feng, W. 2003. Approximate packet classification caching. Tech. Rep. CSE-03-002, OGI School of Science and Engineering at OHSU.

[6]

Chvets, I. and MacGregor, N. H. 2002. Multi-zone caches for accelerating IP routing table lookups. In Proceedings of High-Performance Switching and Routing.

[7]

Crowley, P., Franklin, M., Hadimioglu, H., and Onufryk, P. 2002. Network Processor Design: Issues and Practices. Vol. 1. Morgan Kaufmann Publishers, Inc.

[8]

Decasper, D., Parulkar, G., Dittia, Z., and Plattner, B. 1998. Router plugins: A software architecture for next generation routers. In Proceedings of ACM Sigcomm.

[9]

Feldmann, A. and Muthukrishnan, S. 2000. Tradeoffs for Packet Classification. In IEEE Infocom.

[10]

Gibson, G., Shafai, F., and Podaima, J. 2000. Content addressable memory storage device. United States Patent 6,044,005. SiberCore Technologies, Inc.

[11]

Gupta, P. and McKeown, N. 1999a. Packet classification on multiple fields. In ACM Sigcomm.

[12]

Gupta, P. and McKeown, N. 1999b. Packet classification using hierarchical intelligent cuttings. In Hot Interconnects VII.

[13]

Hari, A., Suri, S., and Parulkar, G. 2000. Detecting and resolving packet filter conflicts. In Proceedings of IEEE Infocom.

[14]

Hennessy, J. L. and Patterson, D. A. 1996. Computer Architecture A Quantitative Approach, 2nd Ed. Morgan Kaufmann Publishers, Inc.

[15]

IBM Blue Logic. 2002. Embedded SRAM Selection Guide.

[16]

Kempke, R. A. and McAuley, A. J. 1998. Ternary CAM memory architecture and methodology. United States Patent 5,841,874. Motorola, Inc.

[17]

Kounavis, M. E., Kumar, A., Vin, H., Yavatkar, R., and Campbell, A. T. 2003. Directions in packet classification for network processors. In Second Workshop on Network Processors (NP2).

[18]

Lakshman, T. V. and Stiliadis, D. 1998. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In ACM SIGCOMM.

[19]

Li, K., Chang, F., Berger, D., and chang Fang, W. 2003. Architectures for packet classification caching. In Proceedings of IEEE ICON.

[20]

McAulay, A. J. and Francis, P. 1993. Fast routing table lookup using CAMs. In IEEE Infocom.

[21]

Micron Technology Inc. 2002a. 256Mb Double Data Rate (DDR) SDRAM. Datasheet.

[22]

Micron Technology Inc. 2002b. 36Mb DDR SIO SRAM 2-Word Burst. Datasheet.

[23]

Micron Technology Inc. 2003. Harmony TCAM 1Mb and 2Mb. Datasheet.

[24]

Montoye, R. K. 1994. Apparatus for storing “Don't Care” in a content addressable memory cell. United States Patent 5,319,590. HaL Computer Systems, Inc.

[25]

Newman, P., Minshall, G., and Huston, L. 1997. IP switching and gigabit routers. IEEE Communications Magazine.

[26]

Rekhter, Y., Davie, B., Katz, D., Rosen, E., and Swallow, G. 1997. Cisco systems' tag switching architecture overview. RFC 2105.

[27]

Rosen, E., Viswanathan, A., and Callon, R. 2001. Multiprotocol label switching architecture. RFC 3031.

[28]

Shah, N. 2001. Understanding network processors. Tech. Rep. Version 1.0, EECS, University of California, Berkeley (Sept.).

[29]

SiberCore Technologies Inc. 2002. SiberCAM Ultra-18M SCT1842. Product Brief.

[30]

Singh, S., Baboescu, F., Varghese, G., and Wang, J. 2003. Packet classification using multidimensional cutting. In Proceedings of ACM SIGCOMM. Karlsruhe, Germany.

[31]

Spitznagel, E., Taylor, D., and Turner, J. 2003. Packet classification using extended TCAMs. In Proceedings of IEEE International Conference on Network Protocols (ICNP).

[32]

Srinivasan, V. 2001. A packet classification and filter management system. Microsoft Research.

[33]

Srinivasan, V., Suri, S., and Varghese, G. 1999. Packet classification using tuple space search. In ACM SIGCOMM. 135--146.

[34]

Srinivasan, V., Suri, S., Varghese, G., and Waldvogel, M. 1998. Fast and scalable layer four switching. In ACM Sigcomm.

[35]

Taylor, D. E. and Turner, J. S. 2005a. ClassBench: A packet classification benchmark. In Proceedings of IEEE Infocom.

[36]

Taylor, D. E. and Turner, J. S. 2005b. Scalable packet classification using distributed crossproducting of field labels. In Proceedings of IEEE Infocom.

[37]

van Lunteren, J. 2001. Searching very large routing tables in wide embedded memory. In Proceedings of IEEE Globecom. 3, 1615--1619.

[38]

van Lunteren, J. and Engbersen, T. 2003. Fast and scalable packet classification. IEEE J. Select. Areas Comm. 21, 4 (May) 560--571.

[39]

Waldvogel, M., Varghese, G., Turner, J., and Plattner, B. 1997. Scalable high speed IP routing table lookups. In Proceedings of ACM SIGCOMM. 25--36.

[40]

Warkhede, P., Suri, S., and Varghese, G. 2001. Fast packet classification for two-dimensional conflict-free filters. In IEEE Infocom.

[41]

Woo, T. Y. C. 2000. A modular approach to packet classification: Algorithms and results. In IEEE Infocom.

[42]

Xilinx. 2003. Virtex-II Pro Platform FPGAs: Introduction and Overview. DS083-1 (v3.0).

Cited By

Tan CLi Z(2024)MultiSplit: An Efficient Algorithm for Packet Classification with Equivalent PriorityElectronics10.3390/electronics1315296713:15(2967)Online publication date: 27-Jul-2024
https://doi.org/10.3390/electronics13152967
Fazel-Najafabadi AAbbasi MAttar HAmer ATaherkordi AShokrollahi AKhosravi MSolyman A(2024)High-Performance Flow Classification of Big Data Using Hybrid CPU-GPU Clusters of Cloud EnvironmentsTsinghua Science and Technology10.26599/TST.2023.901008829:4(1118-1137)Online publication date: Aug-2024
https://doi.org/10.26599/TST.2023.9010088
Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2024)Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGAIEEE/ACM Transactions on Networking10.1109/TNET.2023.333038132:2(1707-1722)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3330381
Show More Cited By

Index Terms

Survey and taxonomy of packet classification techniques

Recommendations

Scalable Many-Field Packet Classification on Multi-core Processors
SBAC-PAD '13: Proceedings of the 2013 25th International Symposium on Computer Architecture and High Performance Computing

Packet classification matches a packet header against the predefined rules in a rule set, it is a kernel function that has been studied for decades. A recent trend in packet classification is to match a large number of packet header fields. For example, ...
A Survey of Packet Classification Tools and Techniques
ICCUBEA '15: Proceedings of the 2015 International Conference on Computing Communication Control and Automation

Network processors are evolving to meet the increased bandwidth demands placed on computer networks. Packet classification is one of the significant tasks performed by Network processors in this regard. It is accomplished through various algorithmic ...
A Decomposition-Based Approach for Scalable Many-Field Packet Classification on Multi-core Processors

As a kernel function in network routers, packet classification requires the incoming packet headers to be checked against a set of predefined rules. There are two trends for packet classification: (1) to examine a large number of packet header fields, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 37, Issue 3

September 2005

81 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/1108956

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2005

Published in CSUR Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

401
Total Citations
View Citations
5,418
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)13

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan CLi Z(2024)MultiSplit: An Efficient Algorithm for Packet Classification with Equivalent PriorityElectronics10.3390/electronics1315296713:15(2967)Online publication date: 27-Jul-2024
https://doi.org/10.3390/electronics13152967
Fazel-Najafabadi AAbbasi MAttar HAmer ATaherkordi AShokrollahi AKhosravi MSolyman A(2024)High-Performance Flow Classification of Big Data Using Hybrid CPU-GPU Clusters of Cloud EnvironmentsTsinghua Science and Technology10.26599/TST.2023.901008829:4(1118-1137)Online publication date: Aug-2024
https://doi.org/10.26599/TST.2023.9010088
Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2024)Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGAIEEE/ACM Transactions on Networking10.1109/TNET.2023.333038132:2(1707-1722)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3330381
Liao ZQian SZheng ZZhang JCao JXue GLi M(2024)PT-Tree: A Cascading Prefix Tuple Tree for Packet Classification in Dynamic ScenariosIEEE/ACM Transactions on Networking10.1109/TNET.2023.328902932:1(506-519)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3289029
Chang YChen H(2024)Partitioned 2D Set-Pruning Segment Trees with Compressed Buckets for Multi-Dimensional Packet ClassificationThe Computer Journal10.1093/comjnl/bxad13267:6(2189-2207)Online publication date: 2-Feb-2024
https://doi.org/10.1093/comjnl/bxad132
Lin HWang P(2024)Scalable packet classification based on rule categorization and cross-productingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2023.110116238:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.comnet.2023.110116
Karsten MSchmitt J(2024)A Brief History of Per-Flow QoS in the InternetFrom Multimedia Communications to the Future Internet10.1007/978-3-031-71874-8_4(46-60)Online publication date: 13-Sep-2024
https://doi.org/10.1007/978-3-031-71874-8_4
Lin HPan WWang P(2023)Packet Classification Using TCAM of Narrow EntriesTechnologies10.3390/technologies1105014711:5(147)Online publication date: 19-Oct-2023
https://doi.org/10.3390/technologies11050147
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
Rashelbach ARottenstreich OSilberstein M(2023)Scaling by Learning: Accelerating Open vSwitch Data Path With Neural NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2022.321514331:3(1230-1243)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3215143
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