Multi-core Parallelism Packet Classification Algorithm Based on Dimensions Decomposition

doi:10.3969/j.issn.1006-2475.2020.02.001

Abstract

Abstract: In order to achieve high-speed packet classification, a multi-core parallelism packet classification algorithm is proposed in this paper. Based on the idea of dimension decomposition and Bit Vector (BV), the algorithm parallelizes the classification process with multiple cores using the intra-packet scheme, which shortens the processing time of single packet, improves the system throughput, and ensures that the output sequence is consistent with the input sequence. The experimental results show that the parallelism algorithm can achieve 92700 rules per second in terms of preprocessing speed and 5.37 Mpps throughput on the Cavium OCTEON CN6645 multi-core network processor platform. When the packet size is larger than or equal to 256 Byte, the parallelism algorithm can achieve 10 Gbps line speed processing, and its performance is higher than that of HiCut and PCIU algorithm under the same conditions.

Key words: packet classification, dimension decomposition, multi-core parallelism, bit vector, in order

CLC Number:

TP393

TANG Zhi-bin1,2， ZENG Xue-wen1,2， CHEN Xiao1,2 . Multi-core Parallelism Packet Classification Algorithm Based on Dimensions Decomposition[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2020.02.001.

References

［1］井丽南,叶晓舟,陈晓. 决策树网包分类算法综述［J］. 网络新媒体技术, 2018,7(2):1-11.
［2］ AHMED O, AREIBI S. An efficient application-specific instruction-set processor for packet classification［C］// 2013 International Conference on Reconfigurable Computing and FPGAs (ReConFig). IEEE, 2013:1-6.
［3］ BI X A, LUO X H, SUN Q. Branch tire packet classification algorithm based on single-linkage clustering［J］. Mathematics and Computers in Simulation, 2019,155:78-91.
［4］ AVUDAIAMMAL R, SWARNALATHA A, SEETHALAKSHMI P. Network processor based high speed packet classifier for multimedia applications［J］. Wireless Personal Communications, 2018,98(1):1219-1236.
［5］亓亚烜,李军. 高性能网包分类理论与算法综述［J］. 计算机学报, 2013,36(2):408-421.
［6］王敏,邰铭. 基于FPGA的报文分类技术［J］. 计算机工程与设计, 2015,36(4):920-924.
［7］ QI Y X, XU L H, YANG B H, et al. Packet classification algorithms: From theory to practice［C］// IEEE INFOCOM 2009. IEEE, 2009:648-656.
［8］ TAYLOR D E. Survey and taxonomy of packet classification techniques［J］. ACM Computing Surveys (CSUR), 2005,37(3):238-275.
［9］ CHEN Y H, OGUNTOYINBO O. Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks［J］. Computer Communications, 2009,32(2):349-356.
［10］ROTTENSTREICH O, KESLASSY I, HASSIDIM A, et al. On finding an optimal TCAM encoding scheme for packet classification［C］// 2013 Proceedings IEEE INFOCOM. IEEE, 2013:2049-2057.
［11］SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching［C］// ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. ACM, 1998:191-202.
［12］SRINIVASAN V, SURI S, VARGHESE G. Packet classification using tuple space search［J］. ACM SIGCOMM Computer Communication Review, 1999,29(4):135-146.
［13］LAKSHMAN T V, STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching［J］. ACM SIGCOMM Computer Communication Review, 1998,28(4):203-214.
［14］BABOESCU F, VARGHESE G. Scalable packet classification［J］. ACM SIGCOMM Computer Communication Review, 2001,31(4):199-210.
［15］GUPTA P, MCKEOWN N. Packet classification on multiple fields［J］. ACM SIGCOMM Computer Communication Review, 1999,29(4):147-160.
［16］XU B, JIANG D Y, LI J. HSM: A fast packet classification algorithm［C］// IEEE the 19th International Conference on Advanced Information Networking and Applications (AINA'05). IEEE, 2005:987-992.
［17］AHMED O, AREIBI S, FAYEK D. PCIU: An efficient packet classification algorithm with an incremental update capability［C］// Proceedings of the 2010 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS'10). IEEE, 2010:81-88.
［18］GUPTA P, MCKEOWN N. Packet classification using hierarchical intelligent cuttings［C］// Hot Interconnects VII. 1999,40.
［19］SINGH S, BABOESCU F, VARGHESE G, et al. Packet classification using multidimensional cutting［C］// Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. ACM, 2003:213-224.
［20］QU Y R, ZHOU S J, PRASANNA V K. Scalable many-field packet classification on multi-core processors［C］// 2013 25th International Symposium on Computer Architecture and High Performance Computing. IEEE, 2013:33-40.
［21］QU Y R, ZHANG H H, ZHOU S J, et al. Optimizing many-field packet classification on FPGA, multi-core general purpose processor, and GPU［C］// 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS). IEEE, 2015:87-98.
［22］MA Y, BANERJEE S, LU S, et al. Leveraging parallelism for multi-dimensional packetclassification on software routers［J］. ACM SIGMETRICS Performance Evaluation Review, 2010,38(1):227-238.
［23］张唯唯,张玉洁. 基于GPU的并行报文分类方法［J］. 计算机与现代化, 2014(11):9-14.
［24］尚秋里,王劲林,陈晓,等. 多核网络协议栈可扩展性解耦设计［J］. 网络新媒体技术, 2017,6(5):15-19.
［25］井丽南,陈晓,叶晓舟. 面向SDN的网包分类算法综述［J］. 网络新媒体技术, 2018,7(4):5-14.
［26］TAYLOR D E, TURNER J S. Classbench: A packet classification benchmark［J］. IEEE/ACM Transactions on Networking, 2007,15(3):499-511.

[1]	ZHANG Wei-wei, ZHANG Yu-jie. Parallel Packet Classification Method Based on GPU [J]. Computer and Modernization, 2014, 0(11): 9-14.
[2]	SUN Shu-rong;WANG Yong-li. FMI: A Mobile Mechine to Mechine Community System to Find Missing Items [J]. Computer and Modernization, 2011, 1(2): 29-32.