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

Multi-dimensional Parallel Packet Classification Algorithm

作　　者：王桐桐[1] 

机构地区：[1]南京航空航天大学信息科学与技术学院,南京210016

出　　处：《计算机工程》2011年第18期112-114,共3页Computer Engineering

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]