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

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

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

中图分类号: 

• TP393