• 算法设计与分析 • 下一篇
收稿日期:
2019-03-20
出版日期:
2020-03-03
发布日期:
2020-03-03
基金资助:
Received:
2019-03-20
Online:
2020-03-03
Published:
2020-03-03
摘要: 为了实现高速网包分类,本文提出一种多核并行的包分类算法。该算法基于维度分解和位向量(Bit Vector, BV)的思想,将规则集分解为多个维度,在对网包进行分类时,采用包内并行方案,将多个维度的结果进行多核并行合并,缩短单个包的处理时间,提升系统吞吐能力,并且能保证输出顺序与包输入顺序一致。实验结果表明,并行算法在Cavium OCTEON CN6645多核网络处理器平台上能达到每秒92700条规则的预处理速度和5.37 Mpps的吞吐性能,当网包大于等于256 Byte时,能实现10 Gbps的线速处理,性能高于同等条件下的HiCut算法和PCIU算法。
中图分类号:
唐志斌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-. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||