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

布隆过滤器作为一种高效的数据结构,被广泛应用于执行近似成员资格检查。针对资源功耗受到严格限制的星载路由器设计需求,提出了一种将布隆过滤器引入分段式路由查找的解决方案,在基于共享内存式查找的基础上提高查找效率,在保证最长前缀匹配的同时减少不必要的查找,尽力实现“一次查找,一次命中”。该方案还将布隆过滤器位数组中的每一位与一个计数器相关联,实现对路由更新的支持。将优化的布隆过滤单元在基于Xilinx Virtex-7的现场可编程门阵列(Field Programmable Gate Array,FPGA)开发平台上进行了仿真实现,给出了关键算法的仿真波形,验证了该方案的有效性及相关理论分析的正确性。