Article

Packet classification in large ISPs: design and evaluation of decision tree classifiers

Authors:

Carsten LundAuthors Info & Claims

SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 73 - 84

https://doi.org/10.1145/1064212.1064222

Published: 06 June 2005 Publication History

Abstract

Packet classification, although extensively studied, is an evolving problem. Growing and changing needs necessitate the use of larger filters with more complex rules. The increased complexity and size pose implementation challenges on current hardware solutions and drive the development of software classifiers, in particular, decision-tree based classifiers. Important performance measures for these classifiers are time and memory due to required high throughput and use of limited fast memory.We analyze Tier 1 ISP data that includes filters and corresponding traffic from over a hundred edge routers and thousands of interfaces. We provide a comprehensive view on packet classification in an operational network and glean insights that help us design more effective classification algorithms.We propose and evaluate decision tree classifiers with common branches. These classifiers have linear worst-case memory bounds and require much less memory than standard decision tree classifiers, but nonetheless, we show that on our data have similar average and worst-case time performance. We argue that common-branches exploit structure that is present in real-life data sets.We observe a strong Zipf-like pattern in the usage of rules in a classifier, where a very small number of rules resolves the bulk of traffic and most rules are essentially never used. Inspired by this observation, we propose traffic-aware classifiers that obtain superior average-case and bounded worst-case performance. Good average-case can boost performance of software classifiers that can be used in small to medium sized routers and are also important for traffic analysis and traffic engineering.

References

[1]

Controlling network access with access control lists, 2004. http://cisco.com/univercd/cc/td/doc/product/lan/cat6000/mod_icn/fwsm/fwsm_2_2/fwsm_cfg/mngacl.pdf

[2]

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

[3]

F. Baboescu and G. Varghese. Scalable packet classification. In Proc. of ACM SIGCOMM 2001, 2001.

Digital Library

[4]

S. Babu, R. Motwani, K. Munagala, I. Nishizawa, and J. Widom. Adaptive ordering of pipelined stream filters. In SIGMOD. ACM, 2004.

Digital Library

[5]

A. Brodnik, S. Carlsson, M. Degermark, and S. Pink. Small forwarding tables for fast ip lookups. In Proc. of ACM SIGCOMM 1997, pages 3--13, 1997.

Digital Library

[6]

G. Cheung and S. McCanne. Optimal routing table design for IP address lookups under memory constraints. In Proc. of IEEE Infocom 1999, 1999.

[7]

E. Cohen, A. Fiat, and H. Kaplan. Associative search in Peer to Peer networks: Harnessing latent semantics. In Proceedings of the IEEE INFOCOM'03 Conference, 2003.

[8]

E. Cohen, A. Fiat, and H. Kaplan. Efficient sequences of trials. In Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, 2003.

Digital Library

[9]

N. G. Duffield, C. Lund, and M. Thorup. Learn more, sample less: control of volume and variance in network measurements. IEEE Transactions on Information Theory. to appear.

Digital Library

[10]

U. Feige, L. Lovasz, and P. Tetali. Approximating min-sum set cover. In Proceedings of 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), volume 2462 of LLNCS, pages 94--107. Springer, 2002.

Digital Library

[11]

A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In Proc. of IEEE Infocom 2000, 2000.

[12]

Anja Feldmann, Albert G. Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, and Fred True. Deriving traffic demands for operational IP networks: methodology and experience. In SIGCOMM, pages 257--270, 2000.

Digital Library

[13]

P. Gupta, S. Lin, and N. McKeown. Routing lookups in hardware at memory access speeds. In Proc. of IEEE Infocom 1998, 1998.

[14]

P. Gupta and N. McKeown. Packet classification on multiple fields. In Proc. of ACM SIGCOMM 1999, 1999.

Digital Library

[15]

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

[16]

P. Gupta and N. McKeown. Algorithms for packet classification. IEEE Network, 15, 2001.

Digital Library

[17]

P. Gupta, B. Prabhakar, and S. Boyd. Near optimal routing lookups with bounded worst-case performance. In Proc. of IEEE Infocom 2000, 2000.

[18]

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

Digital Library

[19]

J. F. McMullen. Get secure with Cisco extended IP access control lists, 2001. http://techrepublic.com.com/5102-6265-1058307.html.

[20]

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

Digital Library

[21]

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

Digital Library

[22]

V. Srinivasan, S. Suri, and G. Varghese. Packet classification using tuple space search. In Proc. of ACM SIGCOMM 1999, 1999.

Digital Library

[23]

V. Srinivasan and G. Varghese. Faster IP lookups using controlled prefix expansion. In Proc. of ACM Sigmetrics 1998, 1998.

Digital Library

[24]

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

Digital Library

[25]

T. Woo. A modular approach for packet classfication: algorithms and results. In Proc. of IEEE Infocom 2000, 2000.

Cited By

Lipan CMantoro TAyu M(2022)Neutralizing City's Cyber Infrastructure through the launch of Second Wave SYN-Flood Attacks2022 IEEE 8th International Conference on Computing, Engineering and Design (ICCED)10.1109/ICCED56140.2022.10010671(1-5)Online publication date: 28-Jul-2022
https://doi.org/10.1109/ICCED56140.2022.10010671
Wang P(2015)Packet classification with multiple decision trees2015 21st Asia-Pacific Conference on Communications (APCC)10.1109/APCC.2015.7412583(626-631)Online publication date: Oct-2015
https://doi.org/10.1109/APCC.2015.7412583
Trabelsi ZZeidan S(2014)IDS performance enhancement technique based on dynamic traffic awareness histograms2014 IEEE International Conference on Communications (ICC)10.1109/ICC.2014.6883446(975-980)Online publication date: Jun-2014
https://doi.org/10.1109/ICC.2014.6883446
Show More Cited By

Index Terms

Packet classification in large ISPs: design and evaluation of decision tree classifiers
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Packet classification in large ISPs: design and evaluation of decision tree classifiers
Performance evaluation review

Packet classification, although extensively studied, is an evolving problem. Growing and changing needs necessitate the use of larger filters with more complex rules. The increased complexity and size pose implementation challenges on current hardware ...
A Combined Classification Algorithm Based on C4.5 and NB
ISICA '08: Proceedings of the 3rd International Symposium on Advances in Computation and Intelligence

When our learning task is to build a model with accurate classification, C4.5 and NB are two very important algorithms for achieving this task because of their simplicity and high performance. In this paper, we present a combined classification ...
Building boosted classification tree ensemble with genetic programming
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Adaptive boosting (AdaBoost) is a method for building classification ensemble, which combines multiple classifiers built in an iterative process of reweighting instances. This method proves to be a very effective classification method, therefore it was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

June 2005

428 pages

ISBN:1595930221

DOI:10.1145/1064212

General Chairs:
Derek Eager
University of Saskatchewan, Canada
,
Carey Williamson
University of Calgary, Canada
,
Program Chairs:
Sem Borst
Bell Labs, USA & CWI, The Netherlands
,
John C. S. Lui
Chinese University of Hong Kong, China

ACM SIGMETRICS Performance Evaluation Review Volume 33, Issue 1
Performance evaluation review
June 2005
417 pages
ISSN:0163-5999
DOI:10.1145/1071690
Issue’s Table of Contents

Copyright © 2005 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: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMETRICS05

Sponsor:

SIGMETRICS05: 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

June 6 - 10, 2005

Alberta, Banff, Canada

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
1,002
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lipan CMantoro TAyu M(2022)Neutralizing City's Cyber Infrastructure through the launch of Second Wave SYN-Flood Attacks2022 IEEE 8th International Conference on Computing, Engineering and Design (ICCED)10.1109/ICCED56140.2022.10010671(1-5)Online publication date: 28-Jul-2022
https://doi.org/10.1109/ICCED56140.2022.10010671
Wang P(2015)Packet classification with multiple decision trees2015 21st Asia-Pacific Conference on Communications (APCC)10.1109/APCC.2015.7412583(626-631)Online publication date: Oct-2015
https://doi.org/10.1109/APCC.2015.7412583
Trabelsi ZZeidan S(2014)IDS performance enhancement technique based on dynamic traffic awareness histograms2014 IEEE International Conference on Communications (ICC)10.1109/ICC.2014.6883446(975-980)Online publication date: Jun-2014
https://doi.org/10.1109/ICC.2014.6883446
Antichi GCallegari CMoore AGiordano SAnastasi E(2014)JA-trie: Entropy-based packet classification2014 IEEE 15th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2014.6900878(32-37)Online publication date: Jul-2014
https://doi.org/10.1109/HPSR.2014.6900878
Trabelsi ZZhang LZeidan S(2014)Dynamic rule and rule‐field optimisation for improving firewall performance and securityIET Information Security10.1049/iet-ifs.2011.01468:4(250-257)Online publication date: Jul-2014
https://doi.org/10.1049/iet-ifs.2011.0146
Duan QAl-Shaer E(2013)Traffic-aware dynamic firewall policy management: techniques and applicationsIEEE Communications Magazine10.1109/MCOM.2013.655368151:7(73-79)Online publication date: Jul-2013
https://doi.org/10.1109/MCOM.2013.6553681
Mustafa UMasud MTrabelsi ZWood TAl Harthi Z(2013)Firewall performance optimization using data mining techniques2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC)10.1109/IWCMC.2013.6583682(934-940)Online publication date: Jul-2013
https://doi.org/10.1109/IWCMC.2013.6583682
Ma YBanerjee S(2012)A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classificationACM SIGCOMM Computer Communication Review10.1145/2377677.237774942:4(335-346)Online publication date: 13-Aug-2012
https://dl.acm.org/doi/10.1145/2377677.2377749
Ma YBanerjee SEggert LOtt JPadmanabhan VVarghese G(2012)A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classificationProceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication10.1145/2342356.2342428(335-346)Online publication date: 13-Aug-2012
https://dl.acm.org/doi/10.1145/2342356.2342428
Ujcich BKuang-Ching Wang Parker BSchmiedt D(2012)Thoughts on the Internet architecture from a modern enterprise network outage2012 IEEE Network Operations and Management Symposium10.1109/NOMS.2012.6211939(494-497)Online publication date: Apr-2012
https://doi.org/10.1109/NOMS.2012.6211939
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents