Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (5): 1056-1071.doi: 10.1007/s11390-018-1873-9

Special Issue: Computer Architecture and Systems

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems

Tong Shen1,2, Student Member, CCF, IEEE, Da-Fang Zhang1,*, Senior Member, CCF, IEEE, Gao-Gang Xie2,3,4, Senior Member, CCF, Xin-Yi Zhang2,4   

  1. 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
  • Received:2017-05-28 Revised:2018-04-13 Online:2018-09-17 Published:2018-09-17
  • Contact: Da-Fang Zhang,
  • Supported by:
    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 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.

Key words: multi-dimensional; multi-core; packet classification;

[1] Suh M, Park S H, Lee B et al. Building firewall over the software-defined network controller. In Proc. the 16th International Conference on Advanced Communication Technology (ICACT), Feb. 2014, pp.744-748.
[2] Grimes J, McGuinness D. Mobile telecommunications billing routing system and method. U.S. Patent Application 10/541,908. Jan. 7, 2004.
[3] Lenzen C, Wattenhofer R. Tight bounds for parallel randomized load balancing. Distributed Computing, 2016, 29(2):127-142.
[4] Seddiki M S, Shahbaz M, Donovan S et al. FlowQoS:QoS for the rest of us. In Proc. the 3rd Workshop on Hot Topics in Software Defined Networking, Aug. 2014, pp.207-208.
[5] Hawilo H, Shami A, Mirahmadi M et al. NFV:State of the art, challenges, and implementation in next generation mobile networks (vEPC). IEEE Network, 2014, 28(6):18-26.
[6] McKeown N, Anderson T, Balakrishnan H et al. OpenFlow:Enabling innovation in campus networks. ACM SIGCOMM Computer Communication Review, 2008, 38(2):69-74.
[7] Spitznagel E, Taylor D, Turner J. Packet classification using extended TCAMs. In Proc. the 11th IEEE International Conference on Network Protocols, Nov. 2003, pp.120-131.
[8] Lakshminarayanan K, Rangarajan A, Venkatachary S. Algorithms for advanced packet classification with ternary CAMs. ACM SIGCOMM Computer Communication Review, 2005, 35(4):193-204.
[9] Qu Y R, Zhou S, Prasanna V K. Scalable many-field packet classification on multi-core processors. In Proc. the 25th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Oct. 2013, pp.33-40.
[10] Pfaff B, Pettit J, Koponen T et al. The design and implementation of Open vSwitch. In Proc. the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015, pp.117-130.
[11] Srinivasan V, Suri S, Varghese G. Packet classification using tuple space search. ACM SIGCOMM Computer Communication Review, 1999, 29(4):135-146.
[12] Gupta P, McKeown N. Algorithms for packet classification. IEEE Network, 2001, 15(2):24-32.
[13] Chiang D. A hierarchical phrase-based model for statistical machine translation. In Proc. the 43rd Annual Meeting on Association for Computational Linguistics, Jun. 2005, pp.263-270.
[14] Srinivasan V, Varghese G, Suri S et al. Fast and scalable layer four switching. ACM SIGCOMM Computer Communication Review, 1998, 28(4):191-202.
[15] Wang P C. Scalable packet classification with controlled cross-producting. Computer Networks, 2009, 53(6):821-834.
[16] Feldman A, Muthukrishnan S. Tradeoffs for packet classification. In Proc. the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2000, pp.1193-1202.
[17] Singh S, Baboescu F, Varghese G et al. Packet classification using multidimensional cutting. In Proc. the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Aug. 2003, pp.213-224.
[18] Vamanan B, Voskuilen G, Vijaykumar T N. EffiCuts:Optimizing packet classification for memory and throughput. ACM SIGCOMM Computer Communication Review, 2010, 40(4):207-218.
[19] Gupta P, McKeown N. Packet classification on multiple fields. ACM SIGCOMM Computer Communication Review, 1999, 29(4):147-160.
[20] Gupta P, McKeown N. Packet classification using hierarchical intelligent cuttings. Hot Interconnects VⅡ, 1999, 40.
[21] Baboescu F, Varghese G. Scalable packet classification. ACM SIGCOMM Computer Communication Review, 2001, 31(4):199-210.
[22] Varvello M, Laufer R, Zhang F et al. Multilayer packet classification with graphics processing units. IEEE/ACM Transactions on Networking, 2016, 24(5):2728-2741.
[23] Song H, Lockwood J W. Efficient packet classification for network intrusion detection using FPGA. In Proc. the 13th ACM/SIGDA International Symposium on Fieldprogrammable Gate Arrays, Feb. 2005, pp.238-245.
[24] Jiang W, Prasanna V K. Scalable packet classification on FPGA. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2012, 20(9):1668-1680.
[25] Lakshman T V, Stiliadis D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. ACM SIGCOMM Computer Communication Review, 1998, 28(4):203-214.
[26] Shen T, Zhang D. Rule Selector:A novel scalable model for high-performance flow recognition. In Proc. the 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, Aug. 2016, pp.1121-1128.
[27] Bentley J L, Friedman J H. Data structures for range searching. ACM Computing Surveys (CSUR), 1979, 11(4):397-409.
[28] Pagh R, Rodler F F. Cuckoo hashing. Journal of Algorithms, 2004, 51(2):122-144.
[29] Taylor D E, Turner J S. Classbench:A packet classification benchmark. IEEE/ACM Transactions on Networking (TON), 2007, 15(3):499-511.
[30] Baboescu F, Singh S, Varghese G. Packet classification for core routers:Is there an alternative to CAMs? In Proc. the 22nd Annual Joint Conference of the IEEE Computer and Communications, Mar. 2003, pp.53-63.
[31] Emmerich P, Gallenmlller S, Raumer D et al. MoonGen:A scriptable high-speed packet generator. In Proc. the ACM Conference on Internet Measurement Conference, Oct. 2015, pp.275-287.
[1] Lian-Lian Wu, Yu-Qi Wen, Xiao-Xi Yang, Bo-Wei Yan, Song He, Xiao-Chen Bo. Synthetic Lethal Interactions Prediction Based on Multiple Similarity Measures Fusion [J]. Journal of Computer Science and Technology, 2021, 36(2): 261-275.
[2] Xi-Te Wang, De-Rong Shen, Mei Bai, Tie-Zheng Nie, Yue Kou, Ge Yu. An Efficient Algorithm for Distributed Outlier Detection in Large Multi-Dimensional Datasets [J]. , 2015, 30(6): 1233-1248.
[3] Jiang-Zhou He, Wen-Guang Chen, Guang-Ri Chen, Wei-Min Zheng, Zhi-Zhong Tang, Han-Dong Ye . OpenMDSP:Extending OpenMP to Program Multi-Core DSPs [J]. , 2014, 29(2): 316-331.
[4] Jie Tang, Chen Liu, Shao-Shan Liu, Zhi-Min Gu, and Jean-Luc Gaudiot. Pinned OS/Services: A Case Study of XML Parsing on Intel SCC [J]. , 2013, 28(1): 3-13.
[5] Lei Zhao, Ji-Wen Yang. Resources Snapshot Model for Concurrent Transactions in Multi-Core Processors [J]. , 2013, 28(1): 106-118.
[6] Guang-Ming Tan (谭光明), Member, CCF, ACM, Ping Liu (刘萍), Member, CCF, ACM, Dong-Bo Bu (卜东波), Member, CCF, ACM, and Yan-Bing Liu (刘燕兵), Member, CCF, ACM. Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture [J]. , 2011, 26(5): 866-874.
[7] Dong-Rui Fan (范东睿), Member, CCF,IEEE, Xiao-Wei Li (李晓维), and Guo-Jie Li (李国杰), Fellow, CCF. New Methodologies for Parallel Architecture [J]. , 2011, 26(4): 578-587.
[8] Long Zheng (郑龙), Mian-Xiong Dong (董冕雄), Student Member, IEEE, Kaoru Ota, Hai Jin (金海), Senior Member, IEEE, Member, ACM, Song Guo, Senior Member, IEEE, Member, ACM, and Jun Ma (马俊), Student Member, IEEE. Energy Efficiency of a Multi-Core Processor by Tag Reduction [J]. , 2011, 26(3): 491-503.
[9] Chao-Sheng Lin (林朝圣), Chun-Hsien Lu (吕俊贤), Shang-Wei Lin (林尚威), Yean-Ru Chen (陈盈如), and Pao-Ann Hsiung (熊博安), Senior Member, ACM, IEEE. VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development [J]. , 2011, 26(3): 448-462.
[10] Ru-Hui Ma (马汝辉), Hai-Bing Guan (管海兵), Member, CCF, Er-Zhou Zhu (朱二周), Hong-Bo Yang (杨洪波), Yin-Dong Yang (杨吟东), and A-Lei Liang (梁阿磊), Member, CCF. Partitioning the Conventional DBT System for Multiprocessors [J]. , 2011, 26(3): 474-490.
[11] Xiang-Yang Gong (龚向阳), Wen-Dong Wang (王文东), Senior Member, CCF, and Shi-Duan Cheng (程时端). ERFC: An Enhanced Recursive Flow Classification Algorithm [J]. , 2010, 25(5): 958-969.
[12] Xiang Gao, Yun-Ji Chen, Huan-Dong Wang, Dan Tang, and Wei-Wu Hu. System Architecture of Godson-3 Multi-Core Processors [J]. , 2010, 25(2): 181-191.
[13] Shu-Ming Chen, Member, CCF, Jiang-Hua Wan, Jian-Zhuang Lu, Zhong Liu, Hai-Yan Sun, Yong-Jie Sun, Member, CCF,Heng-Zhu Liu, Member, CCF, Xiang-Yuan Liu, Zhen-Tao Li, Yi Xu, and Xiao-Wen Chen. YHFT-QDSP: High-Performance Heterogeneous Multi-Core DSP [J]. , 2010, 25(2): 214-224.
[14] Xiao-Min Zhu and Pei-Zhong Lu. Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters [J]. , 2009, 24(3): 434-446.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved