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

research-article

Leveraging parallelism for multi-dimensional packetclassification on software routers

Authors:

Suman Banerjee,

Cristian EstanAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 38, Issue 1

Pages 227 - 238

https://doi.org/10.1145/1811099.1811065

Published: 14 June 2010 Publication History

Abstract

We present a software-based solution to the multi-dimensional packet classification problem which can operate at high line speeds, e.g., in excess of 10 Gbps, using high-end multi-core desktop platforms available today. Our solution, called Storm, leverages a common notion that a subset of rules are likely to be popular over short durations of time. By identifying a suitable set of popular rules one can significantly speed up existing software-based classification algorithms. A key aspect of our design is in partitioning processor resources into various relevant tasks, such as continuously computing the popular rules based on a sampled subset of traffic, fast classification for traffic that matches popular rules, dealing with packets that do not match the most popular rules, and traffic sampling. Our results show that by using a single 8-core Xeon processor desktop platform, it is possible to sustain classification rates of more than 15 Gbps for representative rule sets of size in excess of 5-dimensional 9000 rules, with no packet losses. This performance is significantly superior to a 8-way implementation of a state-of-the-art packet classification software system running on the same 8-core machine. Therefore, we believe that our design of packet classification functions can be a useful classification building block for RouteBricks-style designs, where a core router might be constructed as a mesh of regular desktop machines.

References

[1]

A.J.McAulay and P. Francis. Fast routing table lookup using cams. In IEEE INFOCOM, 1993.

[2]

F. Chang, W. C. Feng, and K. Li. Approximate caches for packet classification. In IEEE INFOCOM, 2004.

[3]

E. Cohen and C. Lund. Packet classification in large isps: Design and evaluation of decision tree classifiers. In ACM SIGMETRICS, 2005.

Digital Library

[4]

M. Dobrescu, N. Egi, K. Argyraki, B.-G. Chun, and K. Fall. Routebricks: Exploiting parallelism to scale software routers. In SOSP, 2009.

Digital Library

[5]

Q. Dong, S. Banerjee, J. Wang, and D. Agrawal. Wire speed packet classification without tcams: a few more registers (and a bit of logic) are enough. In ACM SIGMETRICS, pages 253--264, June 2007.

Digital Library

[6]

Q. Dong, S. Banerjee, J. Wang, D. Agrawal, and A. Shukla. Packet classifiers in ternary cams can be smaller. In ACM SIGMETRICS, 2006.

Digital Library

[7]

P. Gupta and N. Mckeown. Packet classification using hierarchical intelligent cuttings. IEEE Micro, 20(1):34--41, January 2000.

Digital Library

[8]

C. R. Meiners, A. X. Liu, and E. Torng. Topological transformation approaches to optimizing tcam-based packet classification systems. In ACM SIGMETRICS, pages 73--84, 2009.

Digital Library

[9]

R. Morris, E. Kohler, J. Jannotti, and M. F. Kaashoek. The click modular router. In SOSP, pages 217--231, 1999.

Digital Library

[10]

C. Networks. Octeon network service processors. http://www.cavium.com/octeon software develop kit.html.

[11]

M. H. Overmars and A. F. van der Stappen. Range searching and point location among fat objects. Journal of Algorithms, 21:629--656, 1994.

Digital Library

[12]

Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li. Packet classification algorithms: From theory to practice. In IEEE INFOCOM, 2009.

[13]

S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. In ACM SIGCOMM, pages 213--224, August 2003.

Digital Library

[14]

E. Spitznagel, D. Taylor, and J. Turner. Packet classification using extended tcams. In ICNP, 2003.

Digital Library

[15]

V. Srinivasan, S. Suri, and G. Varghese. Packet classification using tuple space search. In ACM SIGCOMM, pages 135--146, 1999.

Digital Library

[16]

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

Digital Library

[17]

D. Taylor and J. Turner. Classbench: A packet classification benchmark. http://www.arl.wustl.edu/det3/ClassBench/index.htm.

[18]

T. Y. Woo. A modular approach to packet classification: algorithms and results. In IEEE INFOCOM, pages 1213--1222, 2000.

Cited By

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
Hong CLee KHwang JPark HYoo C(2018)KafeIEEE/ACM Transactions on Networking10.1109/TNET.2018.287975226:6(2734-2747)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2879752
Qu YPrasanna V(2016)Compact hash tables for decision-treesParallel Computing10.1016/j.parco.2015.12.00354:C(121-127)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.parco.2015.12.003
Show More Cited By

Index Terms

Leveraging parallelism for multi-dimensional packetclassification on software routers
1. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers

Recommendations

Leveraging parallelism for multi-dimensional packetclassification on software routers
SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

We present a software-based solution to the multi-dimensional packet classification problem which can operate at high line speeds, e.g., in excess of 10 Gbps, using high-end multi-core desktop platforms available today. Our solution, called Storm, ...
Exploiting Parallelism on GPUs and FPGAs with OmpSs
ANDARE '17: Proceedings of the 1st Workshop on AutotuniNg and aDaptivity AppRoaches for Energy efficient HPC Systems

This paper presents the OmpSs approach to deal with heterogeneous programming on GPU and FPGA accelerators. The OmpSs programming model is based on the Mercurium compiler and the Nanos++ runtime. Applications are annotated with compiler directives ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 38, Issue 1

Performance evaluation review

June 2010

382 pages

ISSN:0163-5999

DOI:10.1145/1811099

Issue’s Table of Contents

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2010
398 pages
ISBN:9781450300384
DOI:10.1145/1811039
General Chair:
Vishal Misra
Columbia University, USA
,
Program Chairs:
Paul Barford
University of Wisconsin-Madison, USA
,
Mark Squillante
IBM T.J. Watson Research Center, USA

Copyright © 2010 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2010

Published in SIGMETRICS Volume 38, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
385
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Hong CLee KHwang JPark HYoo C(2018)KafeIEEE/ACM Transactions on Networking10.1109/TNET.2018.287975226:6(2734-2747)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2879752
Qu YPrasanna V(2016)Compact hash tables for decision-treesParallel Computing10.1016/j.parco.2015.12.00354:C(121-127)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.parco.2015.12.003
Qu YZhang HZhou SPrasanna VBrebner GBachmutsky ADas C(2015)Optimizing Many-field Packet Classification on FPGA, Multi-core General Purpose Processor, and GPUProceedings of the Eleventh ACM/IEEE Symposium on Architectures for networking and communications systems10.5555/2772722.2772736(87-98)Online publication date: 7-May-2015
https://dl.acm.org/doi/10.5555/2772722.2772736
Chou CBhuyan L(2015)A multicore vacation scheme for thermal-aware packet processingProceedings of the 2015 33rd IEEE International Conference on Computer Design (ICCD)10.1109/ICCD.2015.7357166(565-572)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1109/ICCD.2015.7357166
Qu YPrasanna V(2015)Power-efficient range-match-based packet classification on FPGA2015 25th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2015.7293937(1-8)Online publication date: Sep-2015
https://doi.org/10.1109/FPL.2015.7293937
Qu YZhang HZhou SPrasanna V(2015)Optimizing many-field packet classification on FPGA, multi-core general purpose processor, and GPU2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS)10.1109/ANCS.2015.7110123(87-98)Online publication date: May-2015
https://doi.org/10.1109/ANCS.2015.7110123
Qu YZhou SPrasanna V(2015)A Decomposition-Based Approach for Scalable Many-Field Packet Classification on Multi-core ProcessorsInternational Journal of Parallel Programming10.1007/s10766-014-0325-643:6(965-987)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10766-014-0325-6
Qu YZhou SPrasanna V(2015)Packet Classification on Multi-core PlatformsHandbook on Data Centers10.1007/978-1-4939-2092-1_13(425-447)Online publication date: 17-Mar-2015
https://doi.org/10.1007/978-1-4939-2092-1_13
Dundjerski DTomašević M(2015)Graphical processing unit-based parallelization of the Open Shortest Path First and Border Gateway Protocol routing protocolsConcurrency and Computation: Practice & Experience10.1002/cpe.322327:1(237-251)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1002/cpe.3223
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 Issue’s Table of Contents