一种基于计数型Bloom Filter的报文分类算法  

Packet Classification Algorithm Based on Counting Bloom Filter

作　　者：邹睿 肖达 肖睿卿 刘胜利 

机构地区：[1]数学工程与先进计算国家重点实验室,河南郑州450001

出　　处：《信息工程大学学报》2015年第5期584-589,共6页Journal of Information Engineering University

基　　金：国家科技支撑计划资助项目(2012BAH47B01);河南省科技攻关项目(102102210544);上海科学技术委员会科研计划资助项目(13DZ1108800)

摘　　要：实现网络报文的快速分类是保证网络服务质量的前提。通过使用bloom filter查询技术和"双并行"查找策略,设计实现了一种基于双并行查找的报文分类算法DPS(double parallel search)。算法通过修改计数型bloom filter的结构来实现对收到的数据报文进行分类规则的快速查询匹配。在规则的查询过程中,算法使用"双并行"查找策略来提高查询的速度。通过与一般的bloom filter算法相比较得出,DPS算法在保证分类速度的基础上,有效降低了时空复杂度和报文分类的错误率,通过实验验证了DPS算法的有效性。Fast network packet classification is the premise of network service quality. By using the Bloom Filter query technology and double parallel search strategy, this paper designs and imple- ments an improved packet classification algorithm DPS （Double Parallel Search）. DPS achieves fast query and matching for classification rules by modifying the structure of Counting Bloom Filter. In the process of rules query, DPS uses double parallel search strategy to improve the query speed. A comparison with the general Bloom Filter algorithm shows that DPS effectively reduces the time and space complexity and the error rate of packet classification without compromising the classification speed. The effectiveness of DPS is verified by experiments.

关 键 词：报文分类 BLOOM FILTER 特征向量 DPS 双并行 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]