Article

Free access

Packet classification using multidimensional cutting

Authors:

Florin Baboescu,

George Varghese,

Jia WangAuthors Info & Claims

SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 213 - 224

https://doi.org/10.1145/863955.863980

Published: 25 August 2003 Publication History

Abstract

This paper introduces a classification algorithm called phHyperCuts. Like the previously best known algorithm, HiCuts, HyperCuts is based on a decision tree structure. Unlike HiCuts, however, in which each node in the decision tree represents a hyperplane, each node in the HyperCuts decision tree represents a k--dimensional hypercube. Using this extra degree of freedom and a new set of heuristics to find optimal hypercubes for a given amount of storage, HyperCuts can provide an order of magnitude improvement over existing classification algorithms. HyperCuts uses 2 to 10 times less memory than HiCuts optimized for memory, while the worst case search time of HyperCuts is 50--500% better than that of HiCuts optimized for speed. Compared with another recent scheme, EGT-PC, HyperCuts uses 1.8--7 times less memory space while the worst case search time is up to 5 times smaller. More importantly, unlike EGT-PC, HyperCuts can be fully pipelined to provide one classification result every packet arrival time, and also allows fast updates.

References

[1]

P. Gupta and N. McKeown, "Packet classification using hierarchical intelligent cuttings," in Proc. Hot Interconnects, 1999.

[2]

"Packet classification on multiple fields," in SIGCOMM 99, 1999.

Digital Library

[3]

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

Digital Library

[4]

F. Baboescu and G. Varghese, "Scalable packet classification," in SIGCOMM, 2001.

Digital Library

[5]

F. Baboescu, S. Singh, and G. Varghese, "Packet classification for core routers: Is there an alternative to cams?" in INFOCOM, 2003.

[6]

A. Feldman and S. Muthukrishnan, "Tradeoffs for packet classification," in INFOCOM, 2000.

[7]

T. Woo, "A modular approach to packet classification: Algorithms and results," in INFOCOM, 2000.

[8]

V. Srinivasan et al, "Fast and scalable layer 4 switching," in SIGCOMM, 1998.

Digital Library

[9]

C. Matsumoto, "Cam vendors consider algorithmic alternatives," in EETimes, may 2002.

[10]

M. Degermark et al, "Small forwarding tables for fast routing lookups," in SIGCOMM, 1997.

Digital Library

[11]

M. Buddhikot et al, "Space decomposition techniques for fast layer-4 switching," in Proc. PHSN, 1999.

Digital Library

[12]

V.Srinivasan, S.Suri, and G.Varghese, "Packet classification using tuple space search," in SIGCOMM, 1999.

Digital Library

[13]

L. Qiu, G. Varghese, and S. Suri, "Fast firewall implementation for software and hardware based routers," in Proc. ICNP, 2001.

[14]

S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet classification using multidimensional cutting," in UCSD Technical Report CS2003-0736, 2003.

[15]

S. Singh and F. Baboescu, "Packet classification repository." {Online}. Available: http://ial.ucsd.edu/classification.

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
Li ZWang TLiu JZhang YMa TLiu K(2024)TuplePick: A High Stability Packet Classification based on Neural Network2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM60985.2024.00066(377-382)Online publication date: 4-Jun-2024
https://doi.org/10.1109/WoWMoM60985.2024.00066
Deng XXu MLi QWu WYang YZhang MZhou YWu J(2024)Exploring Dynamic Rule Caching Under Dependency Constraints for Programmable Switches: Theory, Algorithm, and ImplementationIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342209221:4(4830-4843)Online publication date: Aug-2024
https://doi.org/10.1109/TNSM.2024.3422092
Show More Cited By

Index Terms

Packet classification using multidimensional cutting
1. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers

Recommendations

Layer Partitioned Search Tree for Packet Classification
AINA '12: Proceedings of the 2012 IEEE 26th International Conference on Advanced Information Networking and Applications

Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves ...
Scalable packet classification with controlled cross-producting

Packet classification is central among traffic classification techniques that categorize packets with a traffic descriptor or with user-defined criteria. This categorization may make information accessible for quality of service or security handling on ...
Scalable packet classification based on rule categorization and cross-producting
Abstract
Packet classification performs multidimensional point location upon fields in packet headers to categorize packets into multiple forwarding classes based on pre-defined rules. It plays an important role for the data plane of software-defined ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

August 2003

432 pages

ISBN:1581137354

DOI:10.1145/863955

General Chairs:
Anja Feldmann
TU Munich
,
Martina Zitterbart
University of Karlsruhe
,
Program Chairs:
Jon Crowcroft
University of Cambridge
,
David Wetherall
University of Washington

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM03

Sponsor:

SIGCOMM03: Applications, Technologies, Architectures, and Protocols for Computer Communications

August 25 - 29, 2003

Karlsruhe, Germany

Acceptance Rates

SIGCOMM '03 Paper Acceptance Rate 34 of 319 submissions, 11%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

410
Total Citations
View Citations
1,570
Total Downloads

Downloads (Last 12 months)120
Downloads (Last 6 weeks)18

Reflects downloads up to 23 Sep 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
Li ZWang TLiu JZhang YMa TLiu K(2024)TuplePick: A High Stability Packet Classification based on Neural Network2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM60985.2024.00066(377-382)Online publication date: 4-Jun-2024
https://doi.org/10.1109/WoWMoM60985.2024.00066
Deng XXu MLi QWu WYang YZhang MZhou YWu J(2024)Exploring Dynamic Rule Caching Under Dependency Constraints for Programmable Switches: Theory, Algorithm, and ImplementationIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342209221:4(4830-4843)Online publication date: Aug-2024
https://doi.org/10.1109/TNSM.2024.3422092
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
Huang LZhu LYu JChen XZheng LZhang DWu C(2024)DOT: Towards Fast Decision Tree Packet Classification by Optimizing Rule Partitions2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639711(1-7)Online publication date: 8-Oct-2024
https://doi.org/10.1109/LCN60385.2024.10639711
Zhu LYu JHuang LLin HHuang KZhou ZZhang DChen XWu C(2024)TupleRadar: Accelerating Tuple Space Search in Packet Classification by Learned Index2024 IEEE/ACM 32nd International Symposium on Quality of Service (IWQoS)10.1109/IWQoS61813.2024.10682869(1-10)Online publication date: 19-Jun-2024
https://doi.org/10.1109/IWQoS61813.2024.10682869
Ou ZShih WHsieh TChang Y(2024)Improving Hierarchical Tree-Based Packet Classification by Reinforcement Learning2024 Fifteenth International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN61752.2024.10625263(336-341)Online publication date: 2-Jul-2024
https://doi.org/10.1109/ICUFN61752.2024.10625263
Gaur ARadhakrishnan SNarasimhan AAtiquzzaman M(2024)On Packet Classification with Multidimensional Range TreesICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10622775(1084-1089)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10622775
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
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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 Publication

Media

Figures

Other

Tables

View Table of Contents