基于维度分解的多核并行网包分类算法

doi:10.3969/j.issn.1006-2475.2020.02.001

摘要/Abstract

摘要： 为了实现高速网包分类，本文提出一种多核并行的包分类算法。该算法基于维度分解和位向量（Bit Vector， BV）的思想，将规则集分解为多个维度，在对网包进行分类时，采用包内并行方案，将多个维度的结果进行多核并行合并，缩短单个包的处理时间，提升系统吞吐能力，并且能保证输出顺序与包输入顺序一致。实验结果表明，并行算法在Cavium OCTEON CN6645多核网络处理器平台上能达到每秒92700条规则的预处理速度和5.37 Mpps的吞吐性能，当网包大于等于256 Byte时，能实现10 Gbps的线速处理，性能高于同等条件下的HiCut算法和PCIU算法。

关键词: 包分类, 维度分解, 多核并行, 位向量, 保序

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

中图分类号:

TP393

唐志斌1,2,曾学文1,2,陈晓1,2 . 基于维度分解的多核并行网包分类算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2020.02.001.

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.

参考文献

［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]	张羽1,2，郭春1,2，申国伟1,2，平源3. 一种基于信息熵的IDS告警预处理方法[J]. 计算机与现代化, 2020, 0(05): 111-.
[2]	蒋万明1,2，郭春1,2，蒋朝惠1,2. 一种基于BiLSTM的低速率DDoS攻击检测方法[J]. 计算机与现代化, 2020, 0(05): 120-.
[3]	杨丹1，2,陈君1，2,朱小勇1. 一种大视差场景下的实时视频拼接系统[J]. 计算机与现代化, 2020, 0(04): 19-.
[4]	曹永明. 一种无安全信道的模糊关键字搜索加密方案[J]. 计算机与现代化, 2020, 0(04): 42-.
[5]	左鹏,贺智谋,袁梦,张海阔,杨卫平. 基于加密传输的标识解析模型研究[J]. 计算机与现代化, 2020, 0(04): 46-.
[6]	王垚,李为,吴克河,崔文超. GBDT与LR融合模型在加密流量识别中的应用[J]. 计算机与现代化, 2020, 0(03): 93-.
[7]	贾冲，冯慧芳，杨振娟. 基于出租车GPS轨迹和POI数据的商业选址推荐[J]. 计算机与现代化, 2020, 0(02): 21-.
[8]	王骞，闫夏莉，叶崛宇，张海阔，李真辉 . 面向权威DNS的数据一致性保障机制[J]. 计算机与现代化, 2020, 0(02): 36-.
[9]	唐子焯1，吴克河1，李为1，张宪康2，崔阿军2 . 基于商密算法的视频终端安全接入系统的研究与实现[J]. 计算机与现代化, 2020, 0(02): 46-.
[10]	张创基 . 基于用户行为挖掘的融合社交网络推荐模型[J]. 计算机与现代化, 2020, 0(02): 55-.
[11]	麻朴方1,2，王劲林1,2，尤佳莉1,2. 一种基于马尔可夫模型的加速ICN路径收敛性的方法[J]. 计算机与现代化, 2020, 0(01): 28-.
[12]	廖怡1,2，盛益强1,2，王劲林1,2. 一种不完全可测环境下的覆盖网络构造方法[J]. 计算机与现代化, 2020, 0(01): 41-.
[13]	秦璐璐，周李京，王敏. 支持多关键字搜索的条件代理重加密[J]. 计算机与现代化, 2020, 0(01): 100-.
[14]	庄天益，许国艳，孙洁，周星熠，朱进. 一种基于贡献矩阵的有向网络节点关键度计算方法[J]. 计算机与现代化, 2019, 0(12): 108-.
[15]	王竹晓，张彭彭，李为，吴克河，崔文超，程瑞. 基于深度Q网络的电力工控网络异常检测系统[J]. 计算机与现代化, 2019, 0(12): 114-.