article

Scalable packet classification with controlled cross-producting

Author:

Pi-Chung WangAuthors Info & Claims

Computer Networks: The International Journal of Computer and Telecommunications Networking, Volume 53, Issue 6

Pages 821 - 834

https://doi.org/10.1016/j.comnet.2008.11.017

Published: 23 April 2009 Publication History

Abstract

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 the network. To make packet classification both fast and scalable, we propose a new algorithm that combines cross-producting with linear search. The new algorithm, Controlled Cross-producting, could improve the scalability of cross-producting significantly with respect to storage, while maintaining the search latency. In addition, we introduce several refinements and procedures for incremental update. We evaluate the performance of our scheme with filter databases of varying sizes and characteristics. Specifically, we experimented with 12 different types of filter databases, whose sizes vary from 16K to 128K. The experimental results demonstrate the feasibility and scalability of our scheme. A comparison with the prominent existing schemes further indicates that the proposed scheme takes less time and space.

References

[1]

A.W. Moore, D. Zuev, Internet traffic classification using Bayesian analysis techniques, in: Proceedings of ACM SIGMETRICS '05, 2005, pp. 50-60.

Digital Library

[2]

Gupta, P. and McKeown, N., Algorithms for packet classification. IEEE Network Magazine. v15 i2. 24-32.

[3]

Taylor, D.E., Survey and taxonomy of packet classification techniques. ACM Computing Survey. v37 i3. 238-275.

[4]

V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, Fast and scalable layer four switching, in: Proceedings of ACM SIGCOMM '98, 1998, pp. 191-202.

Digital Library

[5]

P. Gupta, N. McKeown, Packet classification on multiple fields, in: Proceedings of ACM SIGCOMM '99, 1999, pp. 147-160.

Digital Library

[6]

T. Lakshman, D. Stidialis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, in: Proceedings of ACM SIGCOMM '98, 1998, pp. 203-214.

Digital Library

[7]

T. Woo, A modular approach to packet classification: algorithms and results, in: Proceedings of IEEE INFOCOM '00, 2000, pp. 1213-1222.

[8]

V. Srinivasan, G. Varghese, S. Suri, Packet classification using tuple space search, in: Proceedings of ACM SIGCOMM '99, 1999, pp. 135-146.

Digital Library

[9]

A. Feldmann, S. Muthukrishnan, Tradeoffs for packet classification, in: Proceedings of IEEE INFOCOM '00, 2000, pp. 1193-1202.

[10]

M.M. Buddhikot, S. Suri, M. Waldvogel, Space decomposition techniques for fast layer-4 switching, in: Proceedings of IFIP Sixth International Workshop on High Speed Networks, 1999, pp. 25-42.

[11]

P. Gupta, N. McKeown, Packet classification using hierarchical intelligent cuttings, in: Proceedings of Hot Interconnects VII, 1999.

[12]

F. Baboescu, S. Singh, G. Varghese, Packet classification for core routers: Is there an alternative to cams? in: Proceedings of IEEE INFOCOM '03, 2003, pp. 53-63.

[13]

F. Baboescu, G. Varghese, Scalable packet classification, in: Proceedings of ACM SIGCOMM '01, 2001, pp. 199-210.

Digital Library

[14]

E. Spitznagel, D.E. Taylor, J.S. Turner, Packet classification using extended tcams, in: Proceedings of IEEE International Conference on Network Protocols (ICNP '03), 2003, pp. 120-131.

[15]

van Lunteren, J. and Engbersen, T., Fast and scalable packet classification. IEEE Journal on Selected Areas in Communications. v21 i4. 560-571.

[16]

Che, H., Wang, Z., Zheng, K. and Liu, B., Dres: dynamic range encoding scheme for tcam coprocessors. IEEE Transactions on Computers. v57 i7. 902-915.

[17]

A. Bremler-Barr, D. Hendler, Space-efficient tcam-based classification using gray coding, in: INFOCOM 2007, 26th IEEE International Conference on Computer Communications, IEEE, 2007, pp. 1388-1396.

Digital Library

[18]

Bremler-Barr, A., Hay, D., Hendler, D. and Farber, B., Layered interval codes for tcam-based classification. In: SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, ACM, New York, NY, USA. pp. 445-446.

[19]

Lakshminarayanan, K., Rangarajan, A. and Venkatachary, S., Algorithms for advanced packet classification with ternary cams. In: SIGCOMM '05: Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM, New York, NY, USA. pp. 193-204.

[20]

H. Liu, Efficient mapping of range classifier into ternary-cam, in: Hot Interconnects X, 2002, pp. 95-100.

[21]

G.V. Sumeet Singh, Florin Baboescu, J. Wang, Packet classification using multidimensional cutting, in: Proceedings of ACM SIGCOMM '03, 2003, pp. 213-224.

[22]

D.E. Taylor, J.S. Turner, Scalable packet classification using distributed crossproducting of field labels, in: Proceedings of IEEE INFOCOM '05, 2005, pp. 269-280.

[23]

Sun, X., Sahni, S.K. and Zhao, Y.Q., Packet classification consuming small amount of memory. IEEE/ACM Transactions on Networking. v13 i5. 1135-1145.

[24]

M. Waldvogel, G. Varghese, J. Turner, B. Plattner, Scalable high speed ip routing lookups, in: Proceedings of ACM SIGCOMM '97, 1997, pp. 25-36.

Digital Library

[25]

Wang, P.-C., Chan, C.-T., Hu, S.-C., Lee, C.-L. and Tseng, W.-C., High-speed packet classification for differentiated services in ngns. IEEE Transactions on Multimedia. v6 i6. 925-935.

[26]

Wang, P.-C., Lee, C.-L., Chan, C.-T. and Chang, H.-Y., Performance improvement of two-dimensional packet classification by filter rephrasing. IEEE/ACM Transactions on Networking. v15 i4. 906-917.

[27]

V. Srinivasan, A packet classification and filter management system, in: Proceedings of IEEE INFOCOM '01, 2001, pp. 1464-1473.

[28]

Karp, R.M., Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (Eds.), Complexity of Computer Computations, Plenum Press. pp. 85-103.

[29]

Lampson, B., Srinivasan, V. and Varghese, G., Ip lookups using multiway and multicolumn search. IEEE/ACM Transactions on Networking. v7 i4. 323-334.

[30]

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

[31]

Liu, H., Routing table compaction in ternary cam. IEEE Micro. v22 i1. 58-64.

[32]

Srinivasan, V. and Varghese, G., Fast address lookups using controlled prefix expansion. ACM Transctions on Computer Systems. v17 i1. 1-40.

[33]

Lu, H. and Sahni, S., O(logw) multidimensional packet classification. IEEE/ACM Transactions on Networking. v15 i2. 462-472.

[34]

Miguel, E.W.B., Ruiz-Sanchez, A. and Dabbous, W., Survey and taxonomy of ip address lookup algorithms. IEEE Network Magazine. v15 i2. 8-23.

[35]

H. Song, Design and evaluation of packet classification systems, Ph.D. Thesis, Department of Computer Science and Engineering, Washington University, 2006.

[36]

D.E. Taylor, J.S. Turner, Classbench: a packet classification benchmark, in: Proceedings of IEEE INFOCOM '05, 2005, pp. 2068-2079.

Cited By

Pao DLu Z(2019)A multi-pipeline architecture for high-speed packet classificationComputer Communications10.1016/j.comcom.2014.08.00454:C(84-96)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2014.08.004
Abdulhassan AAhmadi M(2018)Many-field packet classification using AMQ-R-treeJournal of High Speed Networks10.3233/JHS-18059224:3(219-241)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JHS-180592
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 with controlled cross-producting

Recommendations

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 ...
Performance improvement of two-dimensional packet classification by filter rephrasing

Packet classification categorizes incoming packets into multiple forwarding classes in a router based on predefined filters. It is important in fulfilling the requirements of differentiated services. To achieve fast packet classification, a new approach,...
Packet classification using multidimensional cutting
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier B.V. © 2008.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 23 April 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pao DLu Z(2019)A multi-pipeline architecture for high-speed packet classificationComputer Communications10.1016/j.comcom.2014.08.00454:C(84-96)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2014.08.004
Abdulhassan AAhmadi M(2018)Many-field packet classification using AMQ-R-treeJournal of High Speed Networks10.3233/JHS-18059224:3(219-241)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JHS-180592
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
Meng YKwok L(2014)Adaptive blacklist-based packet filter with a statistic-based approach in network intrusion detectionJournal of Network and Computer Applications10.5555/3170014.317017039:C(83-92)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.5555/3170014.3170170

View Options

View options

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 Issue’s Table of Contents