Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems

doi:10.1007/s11390-018-1873-9

	Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems
	Shen, Tong 1,2; Zhang, Da-Fang 1; Xie, Gao-Gang 2,3,4; Zhang, Xin-Yi 2,4
	2018-09-01
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	33 期号:5 页码:1056-1071
摘要	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 softwarebased 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
DOI	10.1007/s11390-018-1873-9
收录类别	SCI
语种	英语
资助项目	National Basic Research 973 Program of China[2012CB315805] ; National Natural Science Foundation of China[61472130] ; National Natural Science Foundation of China[61702174]
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Software Engineering
WOS记录号	WOS:000444564800012
出版者	SCIENCE PRESS
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4913
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Da-Fang
作者单位	1.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Network Technol Res Ctr, Beijing 100190, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100190, Peoples R China 4.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Shen, Tong,Zhang, Da-Fang,Xie, Gao-Gang,et al. Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2018,33(5):1056-1071.
APA	Shen, Tong,Zhang, Da-Fang,Xie, Gao-Gang,&Zhang, Xin-Yi.(2018).Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,33(5),1056-1071.
MLA	Shen, Tong,et al."Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 33.5(2018):1056-1071.