一种基于分段式路由查找的布隆过滤方案  

A Bloom Filter Scheme Based on Segmented Routing Lookup

作　　者：张镱 丁帅 乔庐峰 陈庆华 刘熹 邹仕祥 ZHANG Yi;DING Shuai;QIAO Lufeng;CHEN Qinghua;LIU Xi;ZOU Shixiang(Army Engineering University of PLA,Nanjing Jiangsu 210001,China)

机构地区：[1]中国人民解放军陆军工程大学,江苏南京210001

出　　处：《通信技术》2022年第10期1300-1306,共7页Communications Technology

摘　　要：布隆过滤器作为一种高效的数据结构,被广泛应用于执行近似成员资格检查。针对资源功耗受到严格限制的星载路由器设计需求,提出了一种将布隆过滤器引入分段式路由查找的解决方案,在基于共享内存式查找的基础上提高查找效率,在保证最长前缀匹配的同时减少不必要的查找,尽力实现“一次查找,一次命中”。该方案还将布隆过滤器位数组中的每一位与一个计数器相关联,实现对路由更新的支持。将优化的布隆过滤单元在基于Xilinx Virtex-7的现场可编程门阵列(Field Programmable Gate Array,FPGA)开发平台上进行了仿真实现,给出了关键算法的仿真波形,验证了该方案的有效性及相关理论分析的正确性。As a highly efficient data structure,Bloom filters are widely used to perform approximate membership checking.Based on the design requirements of satellite onboard routers whose resource power consumption is strictly limited,a scheme of introducing Bloom filters into the segmented route lookup is proposed,which improves the lookups efficiency based on shared memory search,reduces unnecessary lookups while ensuring the longest prefix matching,aiming to realize a direct hit after a single lookup.This scheme also associates each bit in the bit array of Bloom filter with a counter to achieve the support of routing updates.The optimized Bloom filter module is simulated and implemented on the FPGA development platform based on Xilinx Virtex-7,and the simulation waveforms of the key algorithms validates the efficiency of the proposed scheme and proves the accuracy of the relative theoretical analyses.

关 键 词：布隆过滤器 星载路由器 分段式路由查找 最长前缀匹配 FPGA 

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