article

Scalable packet classification through rulebase partitioning using the maximum entropy hashing

Authors:

Moon Hae KimAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 6

Pages 1926 - 1935

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

Published: 01 December 2009 Publication History

Abstract

In this paper, we introduce a new packet classification algorithm, which can substantially improve the performance of a classifier. The algorithm is built on the observation that a given packet matches only a few rules even in large classifiers, which suggests that most of rules are independent in any given rulebase. The algorithm hierarchically partitions the rulebase into smaller independent subrulebases based on hashing. By using the same hash key used in the partitioning a classifier only needs to look up the relevant subrulebase to which an incoming packet belongs. For an optimal partitioning of rulebases, we apply the notion of maximum entropy to the hash key selection.We performed the detailed simulations of our proposed algorithm on synthetic rulebases of size 1 K to 500 K entries using real-life packet traces. The results show that the algorithm can significantly outperform existing classifiers by reducing the size of a rulebase by more than four orders of magnitude with just two-levels of partitioning. Both the time complexity and the space complexity of the algorithm exhibit linearity in terms of the size of a rulebase. This suggests that the algorithm can be a good scalable solution for medium to large rulebases.

References

[1]

P. Gupta and N. McKeown, "Packet classification on multiple fields," in Proc. ACM SIGCOMM, Aug. 1999, vol. 29, no. 4, pp. 149-160.

Digital Library

[2]

F. Baboescu and G. Varghese, "Scalable packet classification," in Proc. ACM SIGCOMM, Aug. 2001, vol. 31, no. 4, pp. 199-210.

Digital Library

[3]

"Flow Analysis of Passive Measurement Data," {Online}. Available: http://pma.nlanr.net/PMA/Datacube.html

[4]

T. V. Lakshman and D. Stiladis, "High-speed policy-based packet forwarding using efficient multi-dimensional range matching," in Proc. ACM SIGCOMM, Oct. 1998, vol. 28, no. 4, pp. 203-214.

Digital Library

[5]

V. Srinivasan, S. Suri, G. Varghese, and M. Valdvogel, "Fast and scalable layer four switching," in Proc. ACM SIGCOMM, Oct. 1998, vol. 28, no. 4, pp. 191-202.

Digital Library

[6]

V. Srinivasan, G. Varghese, and S. Suri, "Packet classification using tuple space search," in Proc. ACM SIGCOMM, Aug. 1999, vol. 29, no. 4, pp. 135-146.

Digital Library

[7]

M. M. Buddhikot, S. Suri, and M. Waldvogel, "Space decomposition techniques for fast layer-4 switching," in Proc. IFIP 6th Int. Workshop on Protocols for High Speed Netw., Aug. 1999, vol. 66, no. 6, pp. 277-283.

Digital Library

[8]

A. Feldmann and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. GBN and IEEE INFOCOM, Mar. 2000, pp. 1193-1202.

[9]

T. Woo, "A modular approach to packet classification: Algorithms and results," in Proc. IEEE INFOCOM, Mar. 2000, pp. 1213-1222.

[10]

P. Gupta and N. McKeown, "Packet classification using hierarchical intelligent cuttings," in Proc. Hot Interconn. VII, 1999, pp. 3-6.

[11]

R. B. Ash, Information Theory, 1st ed. New York: Dover, Nov. 1990.

[12]

H. Kim, J. Heo, L. Choi, and S. Kim, "Taming large classifiers with rule reference locality," in Proc. ICOIN, Feb. 2003, vol. 1, pp. 35-50.

[13]

IANA Port Number Assignment, Nov. 06, 2002 {Online}. Available: http://www.iana.org/assignments/port-numbers

[14]

Korea Network Information Center, {Online}. Available: http://www. nic.or.kr

[15]

Z. Yu, J. Wu, K. Xu, and M. Xu, "A fast IP classification algorithm applying to multiple fields," in Proc. IEEE Int. Conf. Commun., Jun. 2001, pp. 2058-2062.

[16]

E. D. Zwicky, S. Cooper, and D. B. Chapman, Building Internet Firewall, 2nd ed. New York: O'Reilly, 2000.

Digital Library

[17]

L. Choi, "Packet classification method through hierarchical rulebase partitioning," U.S. Patent Appl. No. 20050254502, May 2, 2005.

[18]

L. Choi, J. Heo, H. Kim, J. Joung, and S. Kim, "Scalable packet classification through maximum entropy hashing," in Proc. 3rd IFIP-TC6 Netw. 2004 Conf., May 2004, pp. 297-302.

[19]

C. Macián and P. Domschitz, "Advanced IP classification techniques for a hybrid routing node in a DWDM metropolitan network," in Proc. Eur. Conf. Netw. Opt. Commun., 1999, pp. 5-8.

[20]

F. Geraci, M. Pellegrini, and P. Pisati, "Packet classification via improved space decomposition techniques," in Proc. IEEE INFOCOM, Mar. 2005, vol. 1, pp. 304-312.

[21]

H. Hamed, A. El-Atawy, and E. Al-Shaer, "Adaptive statistical optimization techniques for firewall packet filtering," in Proc. IEEE INFOCOM, Apr. 2006, vol. 1, pp. 1-12.

[22]

C. Macian and R. Finthammer, "An evaluation of the key design criteria to achieve high update rates in packet classifiers," IEEE Netw., vol. 15, no. 6, pp. 24-29, Nov./Dec. 2001.

Digital Library

[23]

K. Zheng, Z. Liang, and Y. Ge, "Gear up the classifier: Scalable packet classification optimization framework via rule set pre-processing," in Proc. 11th IEEE ISCC, Jun. 2006, pp. 814-819.

Digital Library

[24]

J. van Lunteren and A. P. J. Engbersen, "Fast and scalable pacekt classification," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 560-571, May 2003.

Digital Library

[25]

H. Liu, "Efficient mapping of range classifier into ternary CAM," in Proc. 10th Symp. Hot Interconn., 2002, pp. 2-4.

Digital Library

Cited By

Avudaiammal RSwarnalatha ASeethalakshmi P(2018)Network Processor Based High Speed Packet Classifier for Multimedia ApplicationsWireless Personal Communications: An International Journal10.1007/s11277-017-4916-698:1(1219-1236)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s11277-017-4916-6
Chi LZhu X(2017)Hashing TechniquesACM Computing Surveys10.1145/304730750:1(1-36)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3047307
Pak WChoi Y(2017)High Performance and High Scalable Packet Classification Algorithm for Network Security SystemsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2015.244377314:1(37-49)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TDSC.2015.2443773
Show More Cited By

Index Terms

Scalable packet classification through rulebase partitioning using the maximum entropy hashing
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees
  2. Modeling and simulation
    1. Simulation evaluation
2. General and reference
  1. Cross-computing tools and techniques
    1. Performance

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, ...
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 ...
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

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 6

December 2009

331 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2009

Revised: 17 July 2006

Received: 03 November 2004

Published in TON Volume 17, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
278
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Avudaiammal RSwarnalatha ASeethalakshmi P(2018)Network Processor Based High Speed Packet Classifier for Multimedia ApplicationsWireless Personal Communications: An International Journal10.1007/s11277-017-4916-698:1(1219-1236)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s11277-017-4916-6
Chi LZhu X(2017)Hashing TechniquesACM Computing Surveys10.1145/304730750:1(1-36)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3047307
Pak WChoi Y(2017)High Performance and High Scalable Packet Classification Algorithm for Network Security SystemsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2015.244377314:1(37-49)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TDSC.2015.2443773
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
Lim HLee NJin GLee JChoi YYim C(2014)Boundary cutting for packet classificationIEEE/ACM Transactions on Networking10.1109/TNET.2013.225412422:2(443-456)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2254124

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.

Figures

Tables

Media

View Issue’s Table of Contents