CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification (IEEE INFOCOM 2018, Best-in-Session Presentation Award)

  • Authors: Wenjun Li, Xianfeng Li, Hui Li, and Gaogang Xie
  • This work was conducted under the guidance of Wenjun Li and Gaogang Xie (Corresponding E-mail: wenjunli@pku.edu.cn).

 

Abstract

Efficient algorithmic solutions for multi-field packet classification have been a challenging problem for many years. This problem is becoming even worse in the era of Software Defined Network (SDN), where flow tables with increasing complexities are playing a central role in the forwarding plane of SDN. In this paper, we first conduct an unprecedented in-depth reasoning on issues that led to the unsuccess of the major quests for scalable algorithmic solutions. With the insights obtained, we propose a practical framework called CutSplit, which can exploit the benefits of cutting and splitting techniques adaptively. By addressing the central problem caused by uncontrollable rule replications suffered by the major efforts, CutSplit not only pushes the performance of algorithmic packet classification more closely to hardware-based solutions, but also reduces the memory consumption to a practical level. Moreover, our work achieves low pre-processing time for rule updates, a problem that has long been ignored by previous decision-trees, but is becoming more relevant in the context of SDN due to frequent updates of rules. Experimental results show that using ClassBench, CutSplit achieves a memory reduction over 10 times, as well as 3x improvement on performance in terms of the number of memory access on average.


CutSplit

In this paper, we first seek to understand the reasons behind the difficulty in designing scalable decision-trees for multi-field packet classification. After that, we make some novel observations on typical 5-tuple rule sets as well as OpenFlow based rule tables, which can help us separate rules into few subsets. Finally, we present a decision-tree scheme combing cutting and splitting for packet classification, which can improve storage efficiency and performance simultaneously. Moreover, our work achieves low pre-processing time for rule updates, a problem that has long been ignored by most previous decision-trees.


Supplementary Observations

The ratio of big rules for seed rule sets (Section IV_Part B).

 

Downloads

 

News

2017.12.1: CutSplit is to appear in IEEE INFOCOM 2018 and the website is under construction.

2018.04.21: Slides has been uploaded.

2018.04.25: Source code v1.0 has been uploaded.

2018.05.25: Win Best-in-Session Presentation Award.

2019.03.05: Source code v2.0 has been uploaded. BTW, today is my daughter (Yuhui Li)'s 3rd birthday. Wish her a happy birthday!

2019.08.22: Our extended work called CutTSS (Under Review) will be available soon, and in the new version of the source code that contains four algorithms (i.e, CutSplit, PSTSS, PartitionSort and CutTSS), we have added more evaluations for classification time and throughput. Please pay attention to the upcoming CutTSS.

2020.03.02: The extended work of CutSplit called CutTSS has been accepted by IEEE Journal on Selected Areas in Communications, Special Issue on Network Softwarization & Enablers (JSAC). Please pay attention to the upcoming CutTSS.

2021.08.01: Source code v3.0 (integrated into CutTSS) has been uploaded, and we have also fixed the problems of CutSplit (e.g., Segment error and misclassification).

2021.08.08: Source code v4.0 (integrated into CutTSS) has been uploaded, the modified CutSplit can acheive faster classification performance.

2022.03.17: Source code v4.1 has been uploaded, the revised code fixed the printing errors of HyperSplit in CutSplit.

 

Contact

My Contact Info.: wenjunli@pku.edu.cn, wenjun0816@qq.com.

 

 

  Extended Journal Paper: Tuple Space Assisted Packet Classification with High Performance on Both Search and Update (IEEE JSAC, 2020.07)