计算机工程 ›› 2011, Vol. 37 ›› Issue (18): 112-114.doi: 10.3969/j.issn.1000-3428.2011.18.037

• 网络与通信 • 上一篇    下一篇

一种多维并行报文分类算法

王桐桐   

  1. (南京航空航天大学信息科学与技术学院,南京 210016)
  • 收稿日期:2011-03-16 出版日期:2011-09-20 发布日期:2011-09-20
  • 作者简介:王桐桐(1984-),男,硕士研究生,主研方向:并行算法,高性能路由器

Multi-dimensional Parallel Packet Classification Algorithm

WANG Tong-tong   

  1. (College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
  • Received:2011-03-16 Online:2011-09-20 Published:2011-09-20

摘要: 位并行、位向量和聚合位向量算法通过对多个域进行并行处理加快分类速度,但三者内存占用太大,不适用于大规则集。为此,提出一种压缩位并行算法,通过报文分类压缩每个域上的重复规则并重新组织规则集,从而缩短位图中位串的长度,减少内存空间的占用。实验结果证明,该压缩位并行算法在不影响运行速度的前提下,明显减少了空间占用。

关键词: 位并行, 位向量, 聚合位向量, 压缩位并行, 多维分类, 位串

Abstract: Bit parallel, Bit Vector(BV) and Aggregated Bit Vector(ABV) algorithms are the most representative of the parallel packet classification algorithm. The algorithms accelerate the classification speed by parallel processing multiple domains, but because the data structure used too much memory usage, not suitable for large rules sets of applications. To address this issue, Compressed Bit Parallel(CBP) algorithm is proposed, by compressing repeated rules on each domain, and reorganized set of rules, greatly reducing the length of bit string which in bit map, thus reducing memory space occupancy. Experimental result proves that the CBP algorithm in the firewall environment saving 35% memory than the BV algorithm, saving about 60% than the bit parallel algorithm, and the algorithm has a good performance under access control list environment.

Key words: bit parallel, Bit Vector(BV), Aggregated Bit Vector(ABV), Compressed Bit Parallel(CBP), multi-dimensional classification, bit string

中图分类号: