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

article

A Decomposition-Based Approach for Scalable Many-Field Packet Classification on Multi-core Processors

Authors:

Viktor K. PrasannaAuthors Info & Claims

International Journal of Parallel Programming, Volume 43, Issue 6

Pages 965 - 987

https://doi.org/10.1007/s10766-014-0325-6

Published: 01 December 2015 Publication History

Abstract

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, and (2) to use software-based solutions on multi-core general purpose processors and virtual machines. Although packet classification has been widely studied, most existing solutions on multi-core systems target the classic 5-field packet classification; it is not easy to scale up their performance with respect to the number of packet header fields. In this work, we present a decomposition-based packet classification approach; it supports large rule sets consisting of a large number of packet header fields. In our approach, range-tree and hashing are used to search the fields of the input packet header in parallel. The partial results from all the fields are represented in rule ID sets; they are merged efficiently to produce the final match result. We implement our approach and evaluate its performance with respect to overall throughput and processing latency for rule set size varying from 1 to 32 K. Experimental results on state-of-the-art 16-core platforms show that, an overall throughput of 48 million packets per second and a processing latency of 2,000 ns per packet can be achieved for a 32 K rule set.

References

[1]

OpenFlow Switch Specification V1.3.1, https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.3.1

[2]

Taylor, D.E.: Survey and taxonomy of packet classification techniques. ACM Comput. Surv. 37(3), 238---275 (2005)

Digital Library

[3]

Lakshminarayanan, K., Rangarajan, A., Venkatachary, S.: Algorithms for advanced packet classification with ternary CAMs. In Proceedings of the ACM SIGCOMM (pp. 193---204) (2005)

[4]

Baboescu, F., Singh, S., Varghese, G.: Packet classification for core routers: is there an alternative to CAMs? In: Proceedings of the IEEE INFOCOM, vol. 1, pp. 53---63 (2003)

[5]

Nikitakis, A., Papaefstathiou, I.: A memory-efficient FPGA-based classification engine. In: Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 802---807 (2008)

[6]

Ganegedara, T., Prasanna, V.K.: StrideBV: single chip 400G+ packet classification. In: 13th IEEE International Conference on High Performance Switching and Routing (HPSR), pp. 1---6 (2012)

[7]

Jiang, W., Prasanna, V.K.: Scalable packet classification on FPGA. IEEE Trans. VLSI Syst. 20(9), 1668---1680 (2012)

Digital Library

[8]

Dharmapurikar, S., Song, H., Turner, J., Lockwood, J.: Fast packet classification using bloom filters. In: ACM/IEEE Symposium on Architecture for Networking and Communications Systems (ANCS), pp. 61---70 (2006)

[9]

Koponen, T.: Software is the future of networking. In: Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), pp. 135---136 (2012)

[10]

Luo, Y., Cascon, P., Murray, E., Ortega, J.: Accelerating OpenFlow switching with network processors. In: Proceedings of the 2009 Symposium on Architectures for Networking and Communications Systems (ANCS), pp. 70---71 (2009)

[11]

AMD Multi-Core Processors, http://www.computerpoweruser.com/articles/archive/c0604/29c04/29c04

[12]

Intel Multi-Core Processors, http://www.cse.ohio-state.edu/~ panda/775/slides/intel_quad_core_06

[13]

Gupta, P., McKeown, N.: Algorithms for packet classification. IEEE Netw. 15(2), 24---32 (2001)

Digital Library

[14]

Song, H., Lockwood, J.W.: Efficient packet classification for network intrusion detection using FPGA. In: Proceedings of the 13th International Symposium on Field Programmable Gate Arrays (FPGA), pp. 238---245 (2005)

[15]

Brebner, G.: Softly defined networking. In: Proceedings of the 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), pp. 1---2 (2012)

[16]

Warkhede, P., Suri, S., Varghese, G.: Multiway range trees: scalable IP lookup with fast updates. Comput. Netw. 44(3), 289---303 (2004)

Digital Library

[17]

Zhong, P.: An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update. In: Proceedings of the International Conference on Computer Science and Service System (CSSS), pp. 2059---2063 (2011)

[18]

Pagh, R., Rodler, F.F.: Cuckoo Hashing. Springer, Berlin (2001)

[19]

Lakshman, T.V., Stiliadis, D.: High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In: Proceedings of the ACM SIGCOMM, pp. 203---214 (1998)

[20]

Zhou, S., Qu, Y.R., Prasanna, V.K.: Multi-core implementation of decomposition-based packet classification algorithms. In: Proceedings of the 12th International Conference on Parallel Computing Technologies (PaCT), pp. 105---119 (2013)

[21]

Taylor, D.E., Turner, J.S.: Scalable packet classification using distributed crossproducing of field labels. In: Proceedings of the IEEE INFOCOM, pp. 269---280 (2005)

[22]

Qu, Y.R., Zhou, S., Prasanna, V.K.: Scalable many-field packet classification on multi-core processors. In: Proceedings of the 25th International Symp. on Computer Architecture and High Performance Computing (SBAC-PAD), pp. 33---40 (2013)

[23]

Gupta, P., McKeown, N.: Classifying packets with hierarchical intelligent cuttings. IEEE Micro 20(1), 34---41 (2000)

Digital Library

[24]

Singh, S., Baboescu, F., Varghese, G., Wang, J.: Packet classification using multidimensional cutting. In: Proceedings of the ACM SIGCOMM, pp. 213---224 (2003)

[25]

Pong, F., Tzeng, N.-F., Tzeng, N.-F.: HaRP: rapid packet classification via hashing round-down prefixes. IEEE Trans. Parallel Distrib. Syst. 22(7), 1105---1119 (2011)

Digital Library

[26]

Ma, Y., Banerjee, S., Lu, S., Estan, C.: Leveraging parallelism for multi-dimensional packet classification on software routers. SIGMETRICS Perform. Eval. Rev. 38(1), 227---238 (2010)

[27]

Pus, V., Korenek, J., Korenek, J.: Fast and scalable packet classification using perfect hash functions. In: Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA), pp. 229---236 (2009)

[28]

Qu, Y.R., Zhou, S., Prasanna, V.K.: High-performance architecture for dynamically updatable packet classification on FPGA. In: Proceedings of the 9th ACM/IEEE Symposim on Architectures for Networking and Communications Systems (ANCS), pp. 125---136 (2013)

Cited By

Ghasemi BAhmadi MAlimohammadi H(2024)A neural gas network-based scheme for SDN many-field packet classificationThe Journal of Supercomputing10.1007/s11227-023-05564-x80:2(2601-2632)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11227-023-05564-x
Adiseshaiah MSailaja M(2023)A parallel decision-making design for highly speedy packet classificationMicroprocessors & Microsystems10.1016/j.micpro.2023.10482699:COnline publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104826
Lin HWang P(2023)TCAM-based packet classification for many-field rules of SDNsComputer Communications10.1016/j.comcom.2023.03.001203:C(89-98)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.comcom.2023.03.001
Show More Cited By

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, ...
Multi-core implementation of decomposition-based packet classification algorithms

Multi-field packet classification is a network kernel function where packets are classified based on a set of predefined rules. Decomposition-based classification approaches are of major interest to the research community because of the parallel search ...
Optimizing Many-field Packet Classification on FPGA, Multi-core General Purpose Processor, and GPU
ANCS '15: Proceedings of the Eleventh ACM/IEEE Symposium on Architectures for networking and communications systems

Due to the rapid growth of Internet, there is an increasing need for efficiently classifying packets with many header fields in large rule sets. For example, in Software Defined Networking (SDN), the OpenFlow table lookup can require 15 packet header ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Parallel Programming

International Journal of Parallel Programming Volume 43, Issue 6

December 2015

283 pages

ISSN:0885-7458

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghasemi BAhmadi MAlimohammadi H(2024)A neural gas network-based scheme for SDN many-field packet classificationThe Journal of Supercomputing10.1007/s11227-023-05564-x80:2(2601-2632)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11227-023-05564-x
Adiseshaiah MSailaja M(2023)A parallel decision-making design for highly speedy packet classificationMicroprocessors & Microsystems10.1016/j.micpro.2023.10482699:COnline publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104826
Lin HWang P(2023)TCAM-based packet classification for many-field rules of SDNsComputer Communications10.1016/j.comcom.2023.03.001203:C(89-98)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.comcom.2023.03.001
Yan BLiu QShen JLiang DZhao BOuyang L(2021)A survey of low-latency transmission strategies in software defined networkingComputer Science Review10.1016/j.cosrev.2021.10038640:COnline publication date: 1-May-2021
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100386
Abdulhassan AAhmadi M(2020)Many-field packet classification using CR-treeJournal of High Speed Networks10.3233/JHS-20063426:2(125-140)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.3233/JHS-200634
Alimohammadi HAhmadi M(2019)Clustering-based many-field packet classification in Software-Defined NetworkingJournal of Network and Computer Applications10.1016/j.jnca.2019.102428147:COnline publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.jnca.2019.102428
Abdulhassan AAhmadi M(2019)Cuckoo filter-based many-field packet classification using X-treeThe Journal of Supercomputing10.1007/s11227-019-02818-575:9(5667-5687)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s11227-019-02818-5
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
Lin HWang P(2016)TCAM-Based Packet Classification Using Multi-stage SchemeProceedings of the Fifth International Conference on Network, Communication and Computing10.1145/3033288.3033302(83-87)Online publication date: 17-Dec-2016
https://dl.acm.org/doi/10.1145/3033288.3033302
Hsieh CWeng NCrowley PRizzo LMathy L(2016)Many-Field Packet Classification for Software-Defined Networking SwitchesProceedings of the 2016 Symposium on Architectures for Networking and Communications Systems10.1145/2881025.2881036(13-24)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2881025.2881036
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents