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

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]. 计算机与现代化, 2020, 0(02): 1-.

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, 2020, 0(02): 1-.

参考文献

［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, 年梅1, 张俊1, 2, 付鲁森1. 基于自编码器的网络流量异常检测[J]. 计算机与现代化, 2024, 0(12): 40-44.
[2]	肖军弼, 邱艺. 基于状态感知数据平面的SDN故障检测与恢复方案[J]. 计算机与现代化, 2024, 0(12): 116-123.
[3]	张泰1, 闫子豪2, 段洁2, 张志鸿2. 基于命名数据网络的车联网信息转发策略[J]. 计算机与现代化, 2024, 0(11): 19-27.
[4]	董重重, 赵聪, 吴悠, 张蕾, 张佳雯, 李志浩. 面向物联网终端设备的零信任动态评估方法[J]. 计算机与现代化, 2024, 0(11): 41-45.
[5]	王聪1, 杨文娟1, 丁兴旺2. 基于多模态信息融合的历史档案资源聚合模型[J]. 计算机与现代化, 2024, 0(10): 120-126.
[6]	马荟平1, 李鹏1, 2, 胡素君1. 基于贝叶斯攻击图的RFID系统安全博弈分析模型[J]. 计算机与现代化, 2024, 0(07): 93-99.
[7]	赵文博1, 向东1, 王玖斌2, 邓岳辉3, 张伟1, 康倩1, 李玉洁1. 基于改进黏菌算法与Tsallis熵的电力设备红外图像分割[J]. 计算机与现代化, 2024, 0(06): 70-75.
[8]	李爽1, 2, 叶宁1, 2, 徐康1, 2, 王甦1, 王汝传1, 2. 面向智慧养老的边缘计算卸载方法[J]. 计算机与现代化, 2024, 0(06): 95-102.
[9]	苏凯旋. 基于改进XGBoost模型的网络入侵检测研究[J]. 计算机与现代化, 2024, 0(06): 109-114.
[10]	袁红伟1, 常利军1, 郝家欢2, 樊娜2, 王超2, 罗闯2, 张泽辉2. 基于标签传播的轨迹兴趣点挖掘及隐私保护[J]. 计算机与现代化, 2024, 0(05): 46-54.
[11]	王东岳, 刘浩. 基于多智能体遗传算法的云平台抗虚假数据注入攻击方法 #br# #br#[J]. 计算机与现代化, 2024, 0(04): 21-26.
[12]	游嘉靖1, 2, 何月顺1, 何璘琳1, 钟海龙1, 2. 基于AHP-CNN的加密流量分类方法[J]. 计算机与现代化, 2024, 0(04): 83-87.
[13]	朱泳诗, 杨紫依, 赵良驹, 姚睿楚. 满足规模隐藏的动态加密多映射方案#br#[J]. 计算机与现代化, 0, (): 114-120.
[14]	王宏杰, 徐胜超, 杨波, 毛明扬, 蒋金陵. 基于SRv6技术的云网安全服务链自动编排方法[J]. 计算机与现代化, 2024, 0(01): 1-5.
[15]	胡崇佳, 刘金洲, 方立. 基于无监督域适应的室外点云语义分割[J]. 计算机与现代化, 2024, 0(01): 74-79.