Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems  

作　　者：Tong Shen Da-Fang Zhang Gao-Gang Xie Xin-Yi Zhang 

机构地区：[1]College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China [2]Network Technology Research Center, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China [3]State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China [4]University of Chinese Academy of Sciences, Beijing 100049, China

出　　处：《Journal of Computer Science & Technology》2018年第5期1056-1071,共16页计算机科学技术学报（英文版）

基　　金：This work was supported by the National Basic Research 973 Program of China under Grant No. 2012CB315805 and the National Natural Science Foundation of China under Grant Nos. 61472130 and 61702174.

摘　　要：Packet classification has been studied for decades; it classifies packets into specific flows based on a given rule set. As software-defined network was proposed, a recent trend of packet classification is to scale the five-tuple model to multi-tuple. In general, packet classification on multiple fields is a complex problem. Although most existing software-based algorithms have been proved extraordinary in practice, they are only suitable for the classic five-tuple model and difficult to be scaled up. Meanwhile, hardware-specific solutions are inflexible and expensive, and some of them are power consuming. In this paper, we propose a universal multi-dimensional packet classification approach for multi-core systems. In our approach, novel data structures and four decomposition-based algorithms are designed to optimize the classification and updating of rules. For multi-field rules, a rule set is cut into several parts according to the number of fields. Each part works independently. In this way, the fields are searched in parallel and all the partial results are merged together at last. To demonstrate the feasibility of our approach, we implement a prototype and evaluate its throughput and latency. Experimental results show that our approach achieves a 40% higher throughput than that of other decomposed-based algorithms and a 43% lower latency of rule incremental update than that of the other algorithms on average. Furthermore, our approach saves 39% memory consumption on average and has a good scalability.Packet classification has been studied for decades; it classifies packets into specific flows based on a given rule set. As software-defined network was proposed, a recent trend of packet classification is to scale the five-tuple model to multi-tuple. In general, packet classification on multiple fields is a complex problem. Although most existing software-based algorithms have been proved extraordinary in practice, they are only suitable for the classic five-tuple model and difficult to be scaled up. Meanwhile, hardware-specific solutions are inflexible and expensive, and some of them are power consuming. In this paper, we propose a universal multi-dimensional packet classification approach for multi-core systems. In our approach, novel data structures and four decomposition-based algorithms are designed to optimize the classification and updating of rules. For multi-field rules, a rule set is cut into several parts according to the number of fields. Each part works independently. In this way, the fields are searched in parallel and all the partial results are merged together at last. To demonstrate the feasibility of our approach, we implement a prototype and evaluate its throughput and latency. Experimental results show that our approach achieves a 40% higher throughput than that of other decomposed-based algorithms and a 43% lower latency of rule incremental update than that of the other algorithms on average. Furthermore, our approach saves 39% memory consumption on average and has a good scalability.

关 键 词：MULTI-DIMENSIONAL MULTI-CORE packet classification 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O211.61[自动化与计算机技术—计算机科学与技术]