基于布鲁姆过滤器的面向IP包识别的CPBF算法*

李龙飞 贺占庄 史阳春

(西安微电子技术研究所 集成电路设计部， 陕西 西安 710065)

基于布鲁姆过滤器的面向IP包识别的CPBF算法*

李龙飞 贺占庄 史阳春

(西安微电子技术研究所 集成电路设计部， 陕西 西安 710065)

针对现有布鲁姆过滤器在流识别应用中对每个IP包进行相同的处理，未考虑IP包识别失效代价和硬件开销的问题，提出一种面向IP包识别的算法——CPBF(Classified and Pipelined Bloom Filter).该算法通过引入IP头中服务类型作为识别失效代价的判断依据对IP包进行分类，根据分类结果采取不同数目的Hash函数进行映射，降低高失效代价IP包的识别失效率；同时在Hash计算中采用流水机制加速识别速率；基于概率论、微分方程等相关知识对CPBF算法进行了描述和理论分析，最后在FPGA上对算法进行实现和实验.结果表明，与标准布鲁姆过滤器、多维布鲁姆过滤器相比，CPBF在具有较低的识别失效率和硬件开销的同时，也能保持较高的识别速率.

布鲁姆过滤器；CPBF算法；IP包识别；识别失效代价；Hash函数

随着40 Gbps和100 Gbps以太网标准的相继提出，网络带宽已经不再是阻碍服务器性能的瓶颈.相反，CPU处理速度的增长远不及网络带宽的增长，且二者之间的速度差逐年增大[1].因此，在网络带宽变得越来越大，CPU处理速度保持一定的情况下，如何保证CPU对网络数据流的有效处理成了国内外学术界面临的一项极具挑战性的课题.

通过网络流识别将用户更关心的IP数据包优先交付给CPU处理是一种解决CPU处理能力与网络带宽不平衡问题的……