research-article

Public Access

Neural packet classification

Authors:

Ion StoicaAuthors Info & Claims

SIGCOMM '19: Proceedings of the ACM Special Interest Group on Data Communication

Pages 256 - 269

https://doi.org/10.1145/3341302.3342221

Published: 19 August 2019 Publication History

Abstract

Packet classification is a fundamental problem in computer networking. This problem exposes a hard tradeoff between the computation and state complexity, which makes it particularly challenging. To navigate this tradeoff, existing solutions rely on complex hand-tuned heuristics, which are brittle and hard to optimize.

In this paper, we propose a deep reinforcement learning (RL) approach to solve the packet classification problem. There are several characteristics that make this problem a good fit for Deep RL. First, many existing solutions iteratively build a decision tree by splitting nodes in the tree. Second, the effects of these actions (e.g., splitting nodes) can only be evaluated once the entire tree is built. These two characteristics are naturally captured by the ability of RL to take actions that have sparse and delayed rewards. Third, it is computationally efficient to generate data traces and evaluate decision trees, which alleviate the notoriously high sample complexity problem of Deep RL algorithms. Our solution, NeuroCuts, uses succinct representations to encode state and action space, and efficiently explore candidate decision trees to optimize for a global objective. It produces compact decision trees optimized for a specific set of rules and a given performance metric, such as classification time, memory footprint, or a combination of the two. Evaluation on Class-Bench shows that NeuroCuts outperforms existing hand-crafted algorithms in classification time by 18% at the median, and reduces both classification time and memory footprint by up to 3X.

Supplementary Material

MP4 File (p256-liang.mp4)

Download
1151.39 MB

References

[1]

Florin Baboescu, Sumeet Singh, and George Varghese. 2003. Packet classification for core routers: Is there an alternative to CAMs?. In IEEE INFOCOM.

[2]

Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016. OpenAI gym. arXiv preprint arXiv:1606.01540 (2016).

[3]

Li Chen, Justinas Lingys, Kai Chen, and Feng Liu. 2018. AuTO: Scaling Deep Reinforcement Learning for Datacenter-Scale Automatic Traffic Optimization. In ACM SIGCOMM.

Digital Library

[4]

Sandeep Chinchali, Pan Hu, Tianshu Chu, Manu Sharma, Manu Bansal, Rakesh Misra, Marco Pavone, and Sachin Katti. 2018. Cellular network traffic scheduling with deep reinforcement learning. In AAAI.

[5]

Ekin Dogus Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le. 2018. AutoAugment: Learning Augmentation Policies from Data. CoRR (2018).

[6]

Mo Dong, Tong Meng, Doron Zarchy, Engin Arslan, Yossi Gilad, Brighten Godfrey, and Michael Schapira. 2018. PCC Vivace: Online-Learning Congestion Control. In USENIX NSDI.

Digital Library

[7]

Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, Legg Shane, and Kavukcuoglu Koray. 2018. IMPALA: Scalable distributed Deep-RL with importance weighted actor-learner architectures. arXiv preprint arXiv:1802.01561 (2018).

[8]

Kousha Etessami and Mihalis Yannakakis. 2005. Recursive Markov decision processes and recursive stochastic games. In International Colloquium on Automata, Languages, and Programming. Springer, 891--903.

Digital Library

[9]

Jason Gauci, Edoardo Conti, Yitao Liang, Kittipat Virochsiri, Yuchen He, Zachary Kaden, Vivek Narayanan, and Xiaohui Ye. 2018. Horizon: Facebook's Open Source Applied Reinforcement Learning Platform. arXiv preprint arXiv:1811.00260 (2018).

[10]

Alex Graves, Abdel-Rahman Mohamed, and Geoffrey Hinton. 2013. Speech recognition with deep recurrent neural networks. In ICASSP.

[11]

Arthur Guez, Théophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Remi Munos, and David Silver. 2018. Learning to search with MCTSnets. arXiv preprint arXiv.1802.04697 (2018).

[12]

Pankaj Gupta and Nick McKeown. 1999. Packet classification on multiple fields. SIGCOMM CCR (1999).

Digital Library

[13]

Pankaj Gupta and Nick McKeown. 1999. Packet classification using hierarchical intelligent cuttings. In Hot Interconnects.

[14]

Pankaj Gupta and Nick McKeown. 2001. Algorithms for packet classification. (2001).

[15]

Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. 2017. Deep Reinforcement Learning that Matters. CoRR (2017).

[16]

Nathan Jay, Noga H. Rotman, P. Godfrey, Michael Schapira, and Aviv Tamar. 2018. Internet Congestion Control via Deep Reinforcement Learning. arXiv preprint arXiv:1810.03259 (2018).

[17]

Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane, and Patrick Eugster. 2014. SAX-PAC (scalable and expressive packet classification). In SIGCOMM CCR.

Digital Library

[18]

AN Kolmogorov and NA Dmitriev. 1947. Stochastic branching processes. In Doklady Akademi Nauk SSSR, Vol. 56. 7--10.

[19]

Vijay R. Konda and John N. Tsitsiklis. 2000. Actor-critic algorithms. In Advances in neural information processing systems.

[20]

Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. 2015. Deep Neural Decision Forests. In The IEEE International Conference on Computer Vision (ICCV).

Digital Library

[21]

Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The case for learned index structures. In SIGMOD.

Digital Library

[22]

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems.

Digital Library

[23]

Karthik Lakshminarayanan, Anand Rangarajan, and Srinivasan Venkatachary. 2005. Algorithms for advanced packet classification with ternary CAMs. In SIGCOMM CCR.

Digital Library

[24]

John Langford and Tong Zhang. 2008. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in neural information processing systems. 817--824.

Digital Library

[25]

Ian Lenz, Honglak Lee, and Ashutosh Saxena. 2015. Deep learning for detecting robotic grasps. The International Journal of Robotics Research (2015).

Digital Library

[26]

Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. 2016. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research (2016).

Digital Library

[27]

Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. 2018. Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection. The International Journal of Robotics Research (2018).

[28]

Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. 2016. Deep reinforcement learning for dialogue generation. arXiv preprint arXiv:1606.01541 (2016).

[29]

Wenjun Li, Xianfeng Li, Hui Li, and Gaogang Xie. 2018. CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification. In IEEE INFOCOM.

[30]

Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. 2018. RLlib: Abstractions for distributed reinforcement learning. In ICML.

[31]

Alex X Liu, Chad R Meiners, and Yun Zhou. 2008. All-match based complete redundancy removal for packet classifiers in TCAMs. In IEEE INFOCOM.

[32]

Yadi Ma and Suman Banerjee. 2012. A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification. In ACM SIGCOMM.

Digital Library

[33]

Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. 2016. Resource management with deep reinforcement learning. In ACM SIGCOMM HotNets Workshop.

Digital Library

[34]

Hongzi Mao, Ravi Netravali, and Mohammad Alizadeh. 2017. Neural adaptive video streaming with pensieve. In ACM SIGCOMM.

Digital Library

[35]

Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. 2016. Asynchronous methods for deep reinforcement learning. In ICML.

Digital Library

[36]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 (2013).

[37]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature (2015).

[38]

Mohammad Norouzi, Maxwell Collins, Matthew A. Johnson, David J. Fleet, and Pushmeet Kohli. 2015. Efficient non-greedy optimization of decision trees. In Advances in Neural Information Processing Systems. 1729--1737.

Digital Library

[39]

Stanley R Pliska. 1976. Optimization of multitype branching processes. Management Science 23, 2 (1976), 117--124.

Digital Library

[40]

Yaxuan Qi, Lianghong Xu, Baohua Yang, Yibo Xue, and Jun Li. 2009. Packet classification algorithms: From theory to practice. In IEEE INFOCOM.

[41]

Yun R. Qu, Hao H. Zhang, Shijie Zhou, and Viktor K. Prasanna. 2015. Optimizing many-field packet classification on FPGA, multi-core general purpose processor, and GPU. In ACM/IEEE Symposium on Architectures for Networking and Communications Systems.

Digital Library

[42]

John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. 2015. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438 (2015).

[43]

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017).

[44]

David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Graepel Thore, and Demis Hassabis. 2016. Mastering the game of Go with deep neural networks and tree search. Nature (2016).

[45]

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. 2018. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science (2018).

[46]

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. 2017. Mastering the game of Go without human knowledge. Nature (2017).

[47]

Sumeet Singh, Florin Baboescu, George Varghese, and Jia Wang. 2003. Packet classification using multidimensional cutting. In ACM SIGCOMM.

Digital Library

[48]

Ed Spitznagel, David Taylor, and Jonathan Turner. 2003. Packet classification using extended TCAMs. In IEEE ICNP.

Digital Library

[49]

Venkatachary Srinivasan, Subhash Suri, and George Varghese. 1999. Packet classification using tuple space search. In SIGCOMM CCR.

Digital Library

[50]

Weibin Sun and Robert Ricci. 2013. Fast and flexible: parallel packet processing with GPUs and click. In ACM/IEEE Symposium on Architectures for Networking and Communications Systems.

Digital Library

[51]

Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems.

Digital Library

[52]

David E. Taylor and Jonathan S Turner. 2005. ClassBench: A packet classification benchmark. In IEEE INFOCOM.

[53]

David E. Taylor and Jonathan S Turner. 2005. Scalable packet classification using distributed crossproducing of field labels. In IEEE INFOCOM.

[54]

Asaf Valadarsky, Michael Schapira, Dafna Shahaf, and Aviv Tamar. 2017. Learning to route with Deep RL. In NIPS Deep Reinforcement Learning Symposium.

[55]

Balajee Vamanan, Gwendolyn Voskuilen, and T. N. Vijaykumar. 2010. EffiCuts: Optimizing Packet Classification for Memory and Throughput. In ACM SIGCOMM.

Digital Library

[56]

Hado Van Hasselt, Arthur Guez, and David Silver. 2016. Deep Reinforcement Learning with Double Q-Learning. In AAAI.

Digital Library

[57]

Matteo Varvello, Rafael Laufer, Feixiong Zhang, and TV Lakshman. 2016. Multilayer packet classification with graphics processing units. IEEE/ACM Transactions on Networking (2016).

Digital Library

[58]

Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge Graph Embedding by Translating on Hyperplanes. In AAAI.

Digital Library

[59]

Zheng Xiong, Wenpeng Zhang, and Wenwu Zhu. 2017. Learning decision trees with reinforcement learning. In NIPS Workshop on Meta-Learning.

[60]

Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Qiang Yang, and Stephen Lin. 2007. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE transactions on pattern analysis and machine intelligence (2007).

Digital Library

[61]

Jianchao Yang, Shuicheng Yang, Yun Fu, Xuelong Li, and Thomas Huang. 2008. Non-negative graph embedding. In CVPR.

[62]

Hyunho Yeo, Youngmok Jung, Jaehong Kim, Jinwoo Shin, and Dongsu Han. 2018. Neural adaptive content-aware internet video delivery. In USENIX OSDI.

Digital Library

[63]

Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. 2018. Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation. arXiv preprint arXiv.1806.02473 (2018).

Digital Library

[64]

Yasir Zaki, Thomas Pötsch, Jay Chen, Lakshminarayanan Subramanian, and Carmelita Görg. 2015. Adaptive congestion control for unpredictable cellular networks. In SIGCOMM CCR.

Digital Library

[65]

Ying Zheng, Ziyu Liu, Xinyu You, Yuedong Xu, and Junchen Jiang. 2018. Demystifying Deep Learning in Networking. In ACM SIGCOMM APNet Workshop.

Digital Library

[66]

Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2018. Graph Neural Networks: A Review of Methods and Applications. arXiv preprint arXiv.1812.08434 (2018).

Cited By

Tan CLi Z(2024)MultiSplit: An Efficient Algorithm for Packet Classification with Equivalent PriorityElectronics10.3390/electronics1315296713:15(2967)Online publication date: 27-Jul-2024
https://doi.org/10.3390/electronics13152967
Pan HHe PLi ZZhang PWan JZhou YDuan XZhang YXie G(2024)Hoda: a High-performance Open vSwitch Dataplane with Multiple Specialized Data PathsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629564(82-98)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629564
Li ZWang TLiu JZhang YMa TLiu K(2024)TuplePick: A High Stability Packet Classification based on Neural Network2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM60985.2024.00066(377-382)Online publication date: 4-Jun-2024
https://doi.org/10.1109/WoWMoM60985.2024.00066
Show More Cited By

Index Terms

Neural packet classification
1. Networks
  1. Network algorithms
    1. Data path algorithms
      1. Packet classification
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Layer Partitioned Search Tree for Packet Classification
AINA '12: Proceedings of the 2012 IEEE 26th International Conference on Advanced Information Networking and Applications

Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves ...
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 ...
Efficient 2D Multibit Tries for Packet Classification

We develop fast algorithms to construct space-optimal constrained 2D multibit tries for Internet packet classifier applications. Experimental evidence suggests that space-optimal 2D multibit tries and their extensions using a bucket scheme are superior ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '19: Proceedings of the ACM Special Interest Group on Data Communication

August 2019

526 pages

ISBN:9781450359566

DOI:10.1145/3341302

General Chairs:
Jianping Wu
Tsinghua University, China
,
Wendy Hall
University of Southampton, UK

Copyright © 2019 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 the author(s) 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: 19 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

SIGCOMM '19

Sponsor:

SIGCOMM

SIGCOMM '19: ACM SIGCOMM 2019 Conference

August 19 - 23, 2019

Beijing, China

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
4,314
Total Downloads

Downloads (Last 12 months)485
Downloads (Last 6 weeks)25

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan CLi Z(2024)MultiSplit: An Efficient Algorithm for Packet Classification with Equivalent PriorityElectronics10.3390/electronics1315296713:15(2967)Online publication date: 27-Jul-2024
https://doi.org/10.3390/electronics13152967
Pan HHe PLi ZZhang PWan JZhou YDuan XZhang YXie G(2024)Hoda: a High-performance Open vSwitch Dataplane with Multiple Specialized Data PathsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629564(82-98)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629564
Li ZWang TLiu JZhang YMa TLiu K(2024)TuplePick: A High Stability Packet Classification based on Neural Network2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM60985.2024.00066(377-382)Online publication date: 4-Jun-2024
https://doi.org/10.1109/WoWMoM60985.2024.00066
Deng XXu MLi QWu WYang YZhang MZhou YWu J(2024)Exploring Dynamic Rule Caching Under Dependency Constraints for Programmable Switches: Theory, Algorithm, and ImplementationIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342209221:4(4830-4843)Online publication date: Aug-2024
https://doi.org/10.1109/TNSM.2024.3422092
Qiu CRen BLuo LTang GGuo D(2024)SFCPlanner: An Online SFC Planning Approach With SRv6 Flow SteeringIEEE Transactions on Network and Service Management10.1109/TNSM.2024.339294521:4(4625-4638)Online publication date: Aug-2024
https://doi.org/10.1109/TNSM.2024.3392945
Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2024)Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGAIEEE/ACM Transactions on Networking10.1109/TNET.2023.333038132:2(1707-1722)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3330381
Zhang JZeng CZhang HHu SChen K(2024)LiteFlow: Toward High-Performance Adaptive Neural Networks for Kernel DatapathIEEE/ACM Transactions on Networking10.1109/TNET.2023.329315232:1(627-642)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3293152
Liao ZQian SZheng ZZhang JCao JXue GLi M(2024)PT-Tree: A Cascading Prefix Tuple Tree for Packet Classification in Dynamic ScenariosIEEE/ACM Transactions on Networking10.1109/TNET.2023.328902932:1(506-519)Online publication date: Feb-2024
https://doi.org/10.1109/TNET.2023.3289029
Qi SRamakrishnan KChen J(2024)L²6GC: Evolving the Low-Latency Core for Future Cellular NetworksIEEE Internet Computing10.1109/MIC.2024.337665528:2(29-36)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1109/MIC.2024.3376655
Ou ZShih WHsieh TChang Y(2024)Improving Hierarchical Tree-Based Packet Classification by Reinforcement Learning2024 Fifteenth International Conference on Ubiquitous and Future Networks (ICUFN)10.1109/ICUFN61752.2024.10625263(336-341)Online publication date: 2-Jul-2024
https://doi.org/10.1109/ICUFN61752.2024.10625263
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Table of Contents