计算机与现代化

• 算法设计与分析 •    下一篇

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

  

  1. (1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190;2.中国科学院大学,北京100049)
  • 收稿日期:2019-03-20 出版日期:2020-03-03 发布日期:2020-03-03
  • 基金资助:
    中国科学院先导专项课题(XDC02010801)

Multi-core Parallelism Packet Classification Algorithm Based on Dimensions Decomposition

  1. (1. National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences,  
    Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)
  • 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算法。

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

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

中图分类号: