CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification (IEEE INFOCOM 2018)



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.


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).





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.

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.



My Contact Info.:,