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

CPBF: an IP Package Identification Algorithm Using Bloom Filter

作　　者：李龙飞[1] 贺占庄[1] 史阳春[1] LI Long-fei HE Zhan-zhuang SHI Yang-chun(Department of Integrated Circuit Design, Xi , an Microelectronics Technology Inst itute, Xi ’ an 710065, Shaanxi, China）Abstract)

机构地区：[1]西安微电子技术研究所集成电路设计部,陕西西安710065

出　　处：《华南理工大学学报（自然科学版）》2017年第7期90-97,106,共9页Journal of South China University of Technology(Natural Science Edition)

基　　金：总装备部军用电子元器件型谱系列科研项目(1407XJ0900)~~

摘　　要：针对现有布鲁姆过滤器在流识别应用中对每个IP包进行相同的处理,未考虑IP包识别失效代价和硬件开销的问题,提出一种面向IP包识别的算法——CPBF(Classified and Pipelined Bloom Filter).该算法通过引入IP头中服务类型作为识别失效代价的判断依据对IP包进行分类,根据分类结果采取不同数目的 Hash函数进行映射,降低高失效代价IP包的识别失效率;同时在Hash计算中采用流水机制加速识别速率;基于概率论、微分方程等相关知识对CPBF算法进行了描述和理论分析,最后在FPGA上对算法进行实现和实验.结果表明,与标准布鲁姆过滤器、多维布鲁姆过滤器相比,CPBF在具有较低的识别失效率和硬件开销的同时,也能保持较高的识别速率.As the traditional Bloom filters adopt the same process for different IP packages and ignore not only IP package identification invalidation cost but also hardware resource in the process of flow identification, an algorithm called CPBF （Classified and Pipelined Bloom Filter） for IP package identification is presented. CPBF differentiates IP packages depending on ToS （Type of Service） , which can reflect their identification invalidation cost in some ways. In order to minimize the identification invalidation rate, different numbers of Hash functions are applied to different types of IP packages. Specifically, pipelined Hash functions are adopted to accelerate the identification speed. Moreover, on the basis of the theories of probability and differential equation, the description and analytical expression of CPBF are deduced. Finally, an implementation of CPBF is conducted on FPGA. The results indicate that CPBF is superior to standard Bloom filter and multi-dimensional Bloom filter because it helps achieve lower i -dentification invalidation rate and hardware resource cost without sacrificing identification speed.

关 键 词：布鲁姆过滤器 CPBF算法 IP包识别 识别失效代价 HASH函数 

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