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

作     者：李龙飞 贺占庄 史阳春 LI Long-fei HE Zhan-zhuang SHI Yang-chun

作者机构：西安微电子技术研究所集成电路设计部陕西西安710065 

出 版 物：《华南理工大学学报（自然科学版）》 (Journal of South China University of Technology(Natural Science Edition))

年 卷 期：2017年第45卷第7期

页      面：90-97,106页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

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