基于计数布鲁姆过滤器的快速多维包分类算法  

A Fast Multi-Dimensional Packet Classification Algorithm Using Counting Bloom Filter

作　　者：谢鲲[1] 赵姣姣[1] 张大方[2] 毕夏安[1] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082 [2]湖南大学软件学院,湖南长沙410082

出　　处：《电子学报》2010年第5期1046-1052,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60673155);国家自然科学基金重大研究计划(No.90718008);国家973重点基础研究发展计划(No.2007CB310702)

摘　　要：本文从数据包匹配规则的聚集特性出发,将计数布鲁姆过滤器和哈希表相结合,设计并实现了一种高效的多维包分类算法CBHT(Counting Bloom filter and Hash Table).基于包匹配规则的聚集特性,对于五维包分类问题,CBHT算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集,而后在此有限规则集中对后三维进行匹配.利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新.实验结果表明CBHT算法比现有的B2PC算法节省60%的硬件资源,包匹配访问内存次数平均低于B2PC算法22.8%.Considering the aggregation property of the rules which a packet matched, we combined counting bloom filter and hash table to design and implement an efficient multi-dimensional packet classification algorithm called CBHT（Counting Bloom filter and Hash Table）. Based on the aggregation property, for five-dimensional packet classification, we first got the small-scale rule set which matching the IP address using counting bloom filter. In this limited rule set we processed search on the other three dimensions. CBHT improves the speed of packet matching effectively and supports rule set＇ s dynamic update. The experimental results show that CBHT algorithm saves 60% of the hardware resources than B2PC algorithm and the number of average memory accesses lower than B2PC 22.8 %.

关 键 词：包分类 计数布鲁姆过滤器 哈希表 

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