• 算法设计与分析 • 下一篇
收稿日期:
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] | 王宏杰, 徐胜超, 杨 波, 毛明扬, 蒋金陵. 基于SRv6技术的云网安全服务链自动编排方法[J]. 计算机与现代化, 2024, 0(01): 1-5. |
[2] | 胡崇佳, 刘金洲, 方 立. 基于无监督域适应的室外点云语义分割[J]. 计算机与现代化, 2024, 0(01): 74-79. |
[3] | 黄雨婷, 陈 麟, 林宏刚, . 基于渗流理论的关键信息基础设施网络资产重要性评估方法[J]. 计算机与现代化, 2023, 0(11): 51-56. |
[4] | 陈 晨, 庄 毅, 高 增. QoE驱动的SDN网络高可用传输框架[J]. 计算机与现代化, 2023, 0(11): 62-68. |
[5] | 李 想, 庄 毅. 利用XGBoost的路由算法关键故障点识别方法#br# #br#[J]. 计算机与现代化, 2023, 0(11): 75-81. |
[6] | 姜厚海, 庄 毅, 曹子宁. 一种基于流聚合与拥塞避免的SDN快速故障恢复方案[J]. 计算机与现代化, 2023, 0(10): 77-83. |
[7] | 王宏杰, 徐胜超. 基于希尔伯特相似度的云平台异常传输数据聚类方法[J]. 计算机与现代化, 2023, 0(09): 27-31. |
[8] | 杨柳青, 王 冲. 基于极大熵的Web服务资源个性化推荐方法[J]. 计算机与现代化, 2023, 0(09): 32-37. |
[9] | 姜厚海, 庄 毅, 曹子宁. 一种基于改进BDD的SDN可靠性评估算法[J]. 计算机与现代化, 2023, 0(09): 64-69. |
[10] | 肖 航, 李 鹏, 马荟平, 朱 枫, . 基于随机Petri网的RFID系统安全性分析模型[J]. 计算机与现代化, 2023, 0(09): 105-114. |
[11] | 陈 刚, 王志坚, 徐胜超. 基于可行点追踪-连续凸逼近的移动边缘计算任务卸载[J]. 计算机与现代化, 2023, 0(08): 93-97. |
[12] | 杨 波, 徐胜超. 基于SRv6服务链的云网专线场景安全防护方法[J]. 计算机与现代化, 2023, 0(08): 107-111. |
[13] | 雷依翰, 曹利峰, 韩孟达, 韩 雪. 软件定义天地一体化网络安全切换架构与方法[J]. 计算机与现代化, 2023, 0(08): 119-126. |
[14] | 王柳, 朱义鑫, 韩莉英. 融合Hits改进算法的意见领袖挖掘方法[J]. 计算机与现代化, 2023, 0(06): 39-42. |
[15] | 李金海, 胡旭. 基于百度贴吧的高校网络舆情热点话题分析[J]. 计算机与现代化, 2020, 0(09): 12-18. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||