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

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

本文从数据包匹配规则的聚集特性出发,将计数布鲁姆过滤器和哈希表相结合,设计并实现了一种高效的多维包分类算法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 %.