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

research-article

HybridTSS: A Recursive Scheme Combining Coarse- and Fine- Grained Tuples for Packet Classification

Authors:

Ori Rottenstreich,

Yi WangAuthors Info & Claims

APNet '22: Proceedings of the 6th Asia-Pacific Workshop on Networking

Pages 43 - 49

https://doi.org/10.1145/3542637.3542644

Published: 07 November 2023 Publication History

Abstract

The popular OpenFlow virtual switch Open vSwitch (OVS) uses a variant of Tuple Space Search (TSS) for packet classification. Although it is easy for rule updates, the lookup performance is poor. By introducing partial trees into TSS, the recently proposed CutTSS improves the lookup performance of TSS. However, it is challenging to replace TSS in OVS for two reasons: (1) the hand-tuned partitioning heuristics are rule-set dependent; (2) the complex and irregular data structures make it difficult to be integrated and maintained in real systems. To address these issues, we propose HybridTSS, a recursive TSS scheme for fast packet classification in OVS, which exploits three novel ideas: (1) the recursive partitioning based on reinforcement learning balances global rule partitions with low training complexity; (2) a hybrid TSS scheme combining coarse-grained and fine-grained tuples suppresses tuple explosion in TSS; (3) a heterogeneous search algorithm consisting of TSS and linear search adapts to characteristics of rules at different scales for fast lookups. Using ClassBench, we show that, while immune from the main drawbacks of CutTSS, HybridTSS retains the update performance of TSS, and achieves almost an order of magnitude higher lookup performance than TSS, making it an ideal packet classification algorithm for OVS.

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]

Florin Baboescu and George Varghese. 2001. Scalable Packet Classification. In ACM SIGCOMM.

[3]

Yeim-Kuan Chang. 2006. A 2-level TCAM architecture for ranges. IEEE Trans. Comput. 55, 12 (2006), 1614–1629.

Digital Library

[4]

Yeim-Kuan Chang. 2008. Efficient multidimensional packet classification with fast updates. IEEE Trans. Comput. 58, 4 (2008), 463–479.

Digital Library

[5]

Yeim-Kuan Chang and Chun-Sheng Hsueh. 2015. Range-enhanced packet classification design on FPGA. IEEE Transactions on Emerging Topics in Computing 4, 2 (2015), 214–224.

[6]

H. Jonathan. Chao and Bin Liu. 2007. High Performance Switches and Routers. In John Wiley & Sons, Ltd.

[7]

James Daly and et al. 2019. TupleMerge: Fast software packet processing for online packet classification. IEEE/ACM Transactions on Networking 27, 4 (2019), 1417–1431.

Digital Library

[8]

James Daly and Eric Torng. 2018. ByteCuts: Fast Packet Classification by Interior Bit Extraction. In IEEE INFOCOM.

[9]

Jeffrey Fong and et al. 2012. ParaSplit: A scalable architecture on FPGA for terabit packet classification. In IEEE Hot Interconnects.

[10]

Filippo Geraci, Marco Pellegrini, Paolo Pisati, and Luigi Rizzo. 2005. Packet classification via improved space decomposition techniques. In IEEE INFOCOM.

[11]

Pankaj Gupta and Nick McKeown. 1999. Packet classification on multiple fields. In ACM SIGCOMM.

[12]

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

[13]

Pankaj Gupta and Nick McKeown. 2001. Algorithms for packet classification. IEEE Network 15, 2 (2001), 24–32.

Digital Library

[14]

Peng He, Gaogang Xie, Kavé Salamatian, and Laurent Mathy. 2014. Meta-algorithms for software-based packet classification. In IEEE ICNP.

[15]

Weirong Jiang and Viktor K Prasanna. 2012. Scalable Packet Classification on FPGA. IEEE Transactions on Very Large Scale Integration Systems 20, 9(2012), 1668–1680.

Digital Library

[16]

Marios Evangelos Kanakis, Ramin Khalili, and Lin Wang. 2022. Machine Learning for Computer Systems and Networking: A Survey. Comput. Surveys (2022).

[17]

Maciej Kuźniar, Peter Perešíni, and Dejan Kostić. 2015. What you need to know about SDN flow tables. In International Conference on Passive and Active Network Measurement.

[18]

TV Lakshman and Dimitrios Stiliadis. 1998. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In ACM SIGCOMM.

[19]

Wenjun Li and et al. 2019. Memory-efficient recursive scheme for multi-field packet classification. IET Communications 13, 9 (2019), 1319–1325.

Digital Library

[20]

Wenjun Li and et al. 2019. A power-saving pre-classifier for TCAM-based IP lookup. Computer Networks 164(2019), 106898.

Digital Library

[21]

Wenjun Li and et al. 2019. TabTree: A TSS-assisted Bit-selecting Tree Scheme for Packet Classification with Balanced Rule Mapping. In ACM/IEEE ANCS.

[22]

Wenjun Li and et al. 2020. Tuple Space Assisted Packet Classification with High Performance on Both Search and Update. IEEE Journal on Selected Areas in Communications 38, 7(2020), 1555–1569.

[23]

Wenjun Li and Xianfeng Li. 2013. HybridCuts: A scheme combining decomposition and cutting for packet classification. In IEEE Hot Interconnects.

[24]

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.

[25]

Eric Liang, Hang Zhu, Xin Jin, and Ion Stoica. 2019. Neural packet classification. In ACM SIGCOMM.

[26]

Hyesook Lim and So Yeon Kim. 2010. Tuple pruning using Bloom filters for packet classification. IEEE Micro 30, 3 (2010), 48–59.

Digital Library

[27]

Nick McKeown and et al. 2008. OpenFlow: Enabling innovation in campus networks. In ACM SIGCOMM.

[28]

Ben Pfaff and et al. 2015. The design and implementation of Open vSwitch. In USENIX NSDI.

[29]

Yaxuan Qi and et al. 2009. Packet classification algorithms: From theory to practice. In IEEE INFOCOM.

[30]

Alon Rashelbach, Ori Rottenstreich, and Mark Silberstein. 2020. A Computational Approach to Packet Classification. In ACM SIGCOMM.

[31]

Alon Rashelbach, Ori Rottenstreich, and Mark Silberstein. 2022. Scaling Open vSwitch with a Computational Cache. In USENIX NSDI.

[32]

Ori Rottenstreich and et al. 2013. Compressing forwarding tables. In IEEE INFOCOM.

[33]

Ori Rottenstreich and et al. 2020. Cooperative rule caching for SDN switches. In IEEE CloudNet.

[34]

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

[35]

Haoyu Song, Jonathan Turner, and Sarang Dharmapurikar. 2006. Packet classification using coarse-grained tuple spaces. In ACM/IEEE ANCS.

[36]

Venkatachary Srinivasan, Subhash Suri, and George Varghese. 1999. Packet Classification using Tuple Space Search. In ACM SIGCOMM.

[37]

Venkatachary Srinivasan, George Varghese, Subhash Suri, and Marcel Waldvogel. 1998. Fast and Scalable Layer Four Switching. In ACM SIGCOMM.

[38]

David E Taylor. 2005. Survey and taxonomy of packet classification techniques. Comput. Surveys 37, 3 (2005), 238–275.

Digital Library

[39]

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

[40]

David E Taylor and Jonathan S Turner. 2007. ClassBench: A packet classification benchmark. IEEE/ACM Transactions on Networking 15, 3 (2007), 499–511.

Digital Library

[41]

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

[42]

Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. Machine learning 8, 3 (1992), 279–292.

[43]

Yao Xin and et al. 2021. KickTree: A Recursive Algorithmic Scheme for Packet Classification with Bounded Worst-Case Performance. In ACM/IEEE ANCS.

[44]

Yao Xin and et al. 2022. FPGA-based Updatable Packet Classification using TSS-combined Bit-selecting Tree. IEEE/ACM Transactions on Networking(2022).

[45]

Yang Xu, Zhaobo Liu, Zhuoyuan Zhang, and H. Jonathan Chao. 2014. High-Throughput and Memory-Efficient Multimatch Packet Classification Based on Distributed and Pipelined Hash Tables. IEEE/ACM Transactions on Networking 22, 3 (2014), 982–995.

Digital Library

[46]

Sorrachai Yingchareonthawornchai, James Daly, Alex X Liu, and Eric Torng. 2016. A sorted partitioning approach to high-speed and fast-update OpenFlow classification. In IEEE ICNP.

[47]

Xinyi Zhang and et al. 2021. Fast Online Packet Classification With Convolutional Neural Network. IEEE/ACM Transactions on Networking 29, 6 (2021), 2765–2778.

Digital Library

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
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
Li ZZhang NXun HLiu JLuo PZhang YLiang TLiu KZhang WZhao W(2024)LearningTuple: A packet classification scheme with high classification and high updateComputer Networks10.1016/j.comnet.2024.110745(110745)Online publication date: Aug-2024
https://doi.org/10.1016/j.comnet.2024.110745
Show More Cited By

Index Terms

HybridTSS: A Recursive Scheme Combining Coarse- and Fine- Grained Tuples for Packet Classification
1. Networks
  1. Network algorithms
    1. Data path algorithms
      1. Packet classification

Recommendations

Virtual Network Isolation: Are We There Yet?
SecSoN '18: Proceedings of the 2018 Workshop on Security in Softwarized Networks: Prospects and Challenges

While multi-tenant cloud computing provides great benefits in terms of resource sharing, it introduces a new security landscape and requires strong network isolation guarantees between the tenants. Such network isolation is typically implemented using ...
Many-Field Packet Classification for Software-Defined Networking Switches
ANCS '16: Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems

Packet classification is a core problem for OpenFlow-based software-defined networking switches, which required 38 packet header fields per flow to be examined against thousands of rules in a ruleset. With the trend of continue growing number of fields ...
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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

APNet '22: Proceedings of the 6th Asia-Pacific Workshop on Networking

July 2022

110 pages

ISBN:9781450397483

DOI:10.1145/3542637

Copyright © 2022 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: 07 November 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

International Postdoctoral Exchange Fellowship Program of China
China Postdoctoral Science Foundation
Key-Area R&D Program of Guangdong Province
Guangdong Basic and Applied Basic Research Foundation
the Major Key Project of PCL
Basic Research Enhancement Program of China
National Key R&D Program of China
Natural Science Foundation of China

Conference

APNet 2022

APNet 2022: 6th Asia-Pacific Workshop on Networking

July 1 - 2, 2022

Fuzhou, China

Acceptance Rates

Overall Acceptance Rate 50 of 118 submissions, 42%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
50
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Dec 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
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
Li ZZhang NXun HLiu JLuo PZhang YLiang TLiu KZhang WZhao W(2024)LearningTuple: A packet classification scheme with high classification and high updateComputer Networks10.1016/j.comnet.2024.110745(110745)Online publication date: Aug-2024
https://doi.org/10.1016/j.comnet.2024.110745
Lin HWang P(2024)Scalable packet classification based on rule categorization and cross-productingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2023.110116238:COnline publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1016/j.comnet.2023.110116
Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2023)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: 10-Nov-2023
https://dl.acm.org/doi/10.1109/TNET.2023.3330381
Zhong JWei ZZhao SChen S(2022)TupleTree: A High-Performance Packet Classification Algorithm Supporting Fast Rule-Set UpdatesIEEE/ACM Transactions on Networking10.1109/TNET.2022.322720631:5(2027-2041)Online publication date: 12-Dec-2022
https://dl.acm.org/doi/10.1109/TNET.2022.3227206

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.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents