research-article

Multi-Layer Packet Classification with Graphics Processing Units

Authors:

Matteo Varvello,

Feixiong Zhang,

T.V. LakshmanAuthors Info & Claims

CoNEXT '14: Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies

Pages 109 - 120

https://doi.org/10.1145/2674005.2674990

Published: 02 December 2014 Publication History

Abstract

The rapid growth of server virtualization has ignited a wide adoption of software-based virtual switches, with significant interest in speeding up their performance. In a similar trend, software-defined networking (SDN), with its strong reliance on rule-based flow classification, has also created renewed interest in multi-dimensional packet classification. However, despite these recent advances, the performance of current software-based packet classifiers is still limited, mostly by the low parallelism of general-purpose CPUs. In this paper, we explore how to accelerate packet classification using the high parallelism and latency-hiding capabilities of graphic processing units (GPUs). We implement GPU-accelerated versions for both linear and tuple search, currently deployed in virtual switches, and also introduce a novel algorithm called Bloom search. These algorithms are integrated with high-speed packet I/O to build GSwitch, a GPU-accelerated software switch. Our experimental evaluation shows that GSwitch is at least 7x faster than an equally-priced CPU classifier and is able to reach 10 Gbps with minimum-sized packets and a rule set containing 128K OpenFlow entries with 512 different wildcard patterns.

References

[1]

Open vswitch. http://openvswitch.org/.

[2]

BLOOM, B. H. Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM 7, 13 (July 1970), 442--426.

Digital Library

[3]

CASCARANO, N., ROLANDO, P., RISSO, F., AND SISTO, R. iNFAnt: NFA pattern matching on GPGPU devices. SIGCOMM Comput. Commun. Rev. (2010), 20--26.

Digital Library

[4]

CISCO. Nexus1000v. http://cisco.com/.

[5]

CONSORTIUM, O. S. Openflow switch specification. Tech. Rep. Version 1.1.0, Feb. 2011.

[6]

CURTIS, A. R., MOGUL, J. C., TOURRILHES, J., YALAGANDULA, P., SHARMA, P., AND BANERJEE, S. DevoFlow: Scaling Flow Management for High-Performance Networks. In Proc. ACM SIGCOMM (Toronto, Canada, Aug. 2011).

Digital Library

[7]

DERI, L. Improving Passive Packet Capture: Beyond Device Polling. In Proc. SANE (Amsterdam, The Netherlands, Sept. 2004).

[8]

DHARMAPURIKAR, S., KRISHNAMURTHY, P., AND TAYLOR, D. E. Longest Prefix Matching Using Bloom Filters. In Proc. ACM SIGCOMM (Karlsruhe, Germany, Aug. 2003).

Digital Library

[9]

FOSTER, N., HARRISON, R., FREEDMAN, M. J., MONSANTO, C., REXFORD, J., STORY, A., AND WALKER, D. Frenetic: a network programming language. SIGPLAN Not. 46 (2011), 279--291.

Digital Library

[10]

HAN, S., JANG, K., PARK, K., AND MOON, S. PacketShader: A GPU-Accelerated Software Router. In Proc. ACM SIGCOMM (New Dehli, India, Aug. 2010).

Digital Library

[11]

KANG, K., AND YANGDONG, D. Scalable packet classification via GPU metaprogramming. In DATE (Grenoble, France, Mar. 2011).

[12]

KHRONOS OPENCL WORKING GROUP. The opencl specification. http://khronos.org/.

[13]

LIN, C.-H., TSAI, S.-Y., LIU, C.-H., CHANG, S.-C., AND SHYU, J.-M. Accelerating String Matching Using Multi-threaded Algorithm on GPU. In Proc. GLOBECOM (Miami, FL, USA, Dec. 2010).

[14]

MU, S., ZHANG, X., ZHANG, N., LU, J., DENG, Y. S., AND ZHANG, S. IP routing processing with graphic processors. In Proc. DATE (Dresden, Germany, Mar. 2010).

Digital Library

[15]

NVIDIA. Profiler User's Guide -- CUDA Toolkit Documentation. http://docs.nvidia.com/cuda/profiler-users-guide/index.html/.

[16]

NVIDIA. GTX 580. http://geforce.com/hardware/desktop-gpus/geforce-gtx-580/.

[17]

OPENFLOW. Switching reference system. http://www.openflow.org/wp/downloads/.

[18]

OVERMARS, M. H., AND VAN DER STAPPEN, A. F. Range searching and point location among fat objects. Journal of Algorithms 21 (1996), 629--656.

Digital Library

[19]

PAGH, R., AND RODLER, F. F. Cuckoo Hashing. Journal of Algorithms 51, 2 (May 2004), 122--144.

Digital Library

[20]

RIZZO, L. Netmap: a novel framework for fast packet I/O. In Proc. USENIX (Boston, MA, June 2012).

Digital Library

[21]

SANDERS, J., AND KANDROT, E. CUDA by Example: An Introduction to General-Purpose GPU Programming, 1 ed. Addison-Wesley Professional, July 2010.

Digital Library

[22]

SONG, H., HAO, F., KODIALAM, M., AND LAKSHMAN, T. IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards. In Proc. IEEE INFOCOM (Rio de Janeiro, Brazil, Apr. 2009).

[23]

SRINIVASAN, V., SURI, S., AND VARGHESE, G. Packet Classification Using Tuple Space Search. In Proc. ACM SIGCOMM (Cambridge, USA, Aug. 1999).

Digital Library

[24]

TAYLOR, D. E., AND TURNER, J. S. ClassBench: A Packet Classification Benchmark. In Proc. IEEE INFOCOM (Hong Kong, China, Mar. 2004).

[25]

WANG, Y., ZU, Y., ZHANG, T., PENG, K., DONG, Q., LIU, B., MENG, W., DAI, H., TIAN, X., XU, Z., WU, H., AND YANG, D. Wire speed name lookup: a GPU-based approach. In Proc. NSDI (Lombard, IL, Apr. 2013).

Digital Library

[26]

ZHAO, J., ZHANG, X., WANG, X., AND XUE, X. Achieving O(1) IP lookup on GPU-based software routers. In Proc. ACM SIGCOMM (New Delhi, India, Aug. 2010).

Digital Library

Cited By

Abbasi MNajafabadi AElghali SZerrougui MKhosravi MNasser H(2022)High-performance pseudo-anonymization of virtual power plant data on a CPU clusterCluster Computing10.1007/s10586-021-03526-726:1(495-512)Online publication date: 15-Jan-2022
https://doi.org/10.1007/s10586-021-03526-7
Abbasi MNajafi ARafiee MKhosravi MMenon VMuhammad G(2021)Efficient Flow Processing in 5G-Envisioned SDN-Based Internet of Vehicles Using GPUsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.303825022:8(5283-5292)Online publication date: Aug-2021
https://doi.org/10.1109/TITS.2020.3038250
Abbasi MShokrollahi A(2020)Enhancing the performance of decision tree-based packet classification algorithms using CPU clusterCluster Computing10.1007/s10586-020-03081-7Online publication date: 16-Mar-2020
https://doi.org/10.1007/s10586-020-03081-7
Show More Cited By

Recommendations

Acceleration of grammatical evolution using graphics processing units: computational intelligence on consumer games and graphics hardware
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Several papers show that symbolic regression is suitable for data analysis and prediction in financial markets. Grammatical Evolution (GE), a grammar-based form of Genetic Programming (GP), has been successfully applied in solving various tasks ...
A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...
Parallel multi-level analytical global placement on graphics processing units
ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

GPU platforms are becoming increasingly attractive for implementing accelerators because they feature a larger number of cores with improved programmability. In this paper, we describe our implementation of a state-of-the-art academic multi-level ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '14: Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies

December 2014

438 pages

ISBN:9781450332798

DOI:10.1145/2674005

General Chairs:
Aruna Seneviratne
NICTA/UNSW, Australia
,
Christophe Diot
Technicolor, France
,
Jim Kurose
Umass, USA
,
Program Chairs:
Augustin Chaintreau
Columbia University, USA
,
Luigi Rizzo
University of Pisa, Italy

Copyright © 2014 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 December 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CoNEXT '14

Sponsor:

SIGCOMM

CoNEXT '14: Conference on emerging Networking Experiments and Technologies

December 2 - 5, 2014

Sydney, Australia

Acceptance Rates

CoNEXT '14 Paper Acceptance Rate 27 of 133 submissions, 20%;

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
252
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abbasi MNajafabadi AElghali SZerrougui MKhosravi MNasser H(2022)High-performance pseudo-anonymization of virtual power plant data on a CPU clusterCluster Computing10.1007/s10586-021-03526-726:1(495-512)Online publication date: 15-Jan-2022
https://doi.org/10.1007/s10586-021-03526-7
Abbasi MNajafi ARafiee MKhosravi MMenon VMuhammad G(2021)Efficient Flow Processing in 5G-Envisioned SDN-Based Internet of Vehicles Using GPUsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.303825022:8(5283-5292)Online publication date: Aug-2021
https://doi.org/10.1109/TITS.2020.3038250
Abbasi MShokrollahi A(2020)Enhancing the performance of decision tree-based packet classification algorithms using CPU clusterCluster Computing10.1007/s10586-020-03081-7Online publication date: 16-Mar-2020
https://doi.org/10.1007/s10586-020-03081-7
Csikor LDivakaran DKang MKőrösi ASonkoly BHaja DPezaros DSchmid SRétvári GMohaisen AZhang Z(2019)Tuple space explosionProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365431(292-304)Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1145/3359989.3365431
Liang EZhu HJin XStoica IWu JHall W(2019)Neural packet classificationProceedings of the ACM Special Interest Group on Data Communication10.1145/3341302.3342221(256-269)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3341302.3342221
Chang YChi T(2019)Hash-based OpenFlow Packet Classification on Heterogeneous System Architecture2019 Eleventh International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN.2019.8806091(300-305)Online publication date: Jul-2019
https://doi.org/10.1109/ICUFN.2019.8806091
Falamarzi RBahrambeigy BAhmadi MRajabzadeh A(2018)High-performance multi/many-core architectures with shared and private queues: Network processing approachesJournal of High Speed Networks10.3233/JHS-18058324:2(89-106)Online publication date: 29-Mar-2018
https://doi.org/10.3233/JHS-180583
Li WLi XLi HXie G(2018)CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet ClassificationIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8485947(2645-2653)Online publication date: Apr-2018
https://doi.org/10.1109/INFOCOM.2018.8485947
Dong XQian MJiang R(2018)Packet classification based on the decision tree with information entropyThe Journal of Supercomputing10.1007/s11227-017-2227-zOnline publication date: 10-Jan-2018
https://doi.org/10.1007/s11227-017-2227-z
Ousterhout APerry JBalakrishnan HLapukhov PAkella AHowell J(2017)FlexplaneProceedings of the 14th USENIX Conference on Networked Systems Design and Implementation10.5555/3154630.3154666(437-451)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3154630.3154666
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.

Figures

Tables

Media

View Table of Conten