We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 33 Issue 5
September  2018
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Supplements
Tong Shen, Da-Fang Zhang, Gao-Gang Xie, Xin-Yi Zhang. Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems[J]. Journal of Computer Science and Technology, 2018, 33(5): 1056-1071. DOI: 10.1007/s11390-018-1873-9
Citation: Tong Shen, Da-Fang Zhang, Gao-Gang Xie, Xin-Yi Zhang. Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems[J]. Journal of Computer Science and Technology, 2018, 33(5): 1056-1071. DOI: 10.1007/s11390-018-1873-9
shu

Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems

  • 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

Funds: 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.
More Information
  • Corresponding author:

    Da-Fang Zhang,E-mail:dfzhang@hnu.edu.cn

  • Received Date: May 27, 2017
  • Revised Date: April 12, 2018
  • Published Date: September 16, 2018
    Abstract
  • 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.
    • FullText(HTML)
    • References (31)
  • [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.
    • Relative Articles

  • Related Articles

    [1]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]. Journal of Computer Science and Technology, 2015, 30(6): 1233-1248. DOI: 10.1007/s11390-015-1596-0
    [2]Peyman Teymoori, Nasser Yazdani. Delay-Constrained Optimized Packet Aggregation in High-Speed Wireless Networks[J]. Journal of Computer Science and Technology, 2013, 28(3): 525-539. DOI: 10.1007/s11390-013-1353-1
    [3]Lei Zhao, Ji-Wen Yang. Resources Snapshot Model for Concurrent Transactions in Multi-Core Processors[J]. Journal of Computer Science and Technology, 2013, 28(1): 106-118. DOI: 10.1007/s11390-013-1315-7
    [4]Guang-Ming Tan, Ping Liu, Dong-Bo Bu, Yan-Bing Liu. Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture[J]. Journal of Computer Science and Technology, 2011, 26(5): 866-874. DOI: 10.1007/s11390-011-0185-0
    [5]Chao-Sheng Lin, Chun-Hsien Lu, Shang-Wei Lin, Yean-Ru Chen, Pao-Ann Hsiung. VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development[J]. Journal of Computer Science and Technology, 2011, 26(3): 448-462. DOI: 10.1007/s11390-011-1146-3
    [6]Shou-Shan Li, Chu-Ren Huang, Cheng-Qing Zong. Multi-Domain Sentiment Classification with Classifier Combination[J]. Journal of Computer Science and Technology, 2011, 26(1): 25-33. DOI: 10.1007/s11390-011-1108-9
    [7]Xiang-Yang Gong, Wen-Dong Wang, Shi-Duan Cheng. ERFC: An Enhanced Recursive Flow Classification Algorithm[J]. Journal of Computer Science and Technology, 2010, 25(5): 958-969. DOI: 10.1007/s11390-010-1076-5
    [8]Shu-Ming Chen, Jiang-Hua Wan, Jian-Zhuang Lu, Zhong Liu, Hai-Yan Sun, Yong-Jie Sun, Heng-Zhu Liu, Xiang-Yuan Liu, Zhen-Tao Li, Yi Xu, Xiao-Wen Chen. YHFT-QDSP: High-Performance Heterogeneous Multi-Core DSP[J]. Journal of Computer Science and Technology, 2010, 25(2): 214-224.
    [9]Xiao-Min Zhu, Pei-Zhong Lu. Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters[J]. Journal of Computer Science and Technology, 2009, 24(3): 434-446.
    [10]Sui Yuefei. Classification of the Index Sets of Low[n]~p and High [n]~p[J]. Journal of Computer Science and Technology, 1991, 6(3): 285-290.
    • Supplements (1)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Article views (38) PDF downloads (721) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return