可加速最长前缀匹配的布隆过滤查找方案  

Bloom Filter Search Scheme to Accelerate Longest Prefix Matching

作　　者：王乾 乔庐峰 陈庆华 WANG Qian;QIAO Lu-feng;CHEN Qing-hua(Institute of Communication Engineering,Army Engineering University of PLA,Nanjing Jiangsu 210001,China)

机构地区：[1]陆军工程大学通信工程学院,江苏南京210001

出　　处：《通信技术》2020年第7期1674-1679,共6页Communications Technology

摘　　要：作为一种具有过滤功能的数据结构,布隆过滤器在路由查找中正在被广泛应用。在路由查找中布隆过滤器主要用于预处理路由查询,因为路由表通常存储在片外的存储器中,布隆过滤可以将路由表中不存在的路由过滤掉,保证进入查找电路的都为有效路由,最大程度减少不必要的查找。我们的方案使用一种优化的布隆过滤器来加速最长前缀匹配,优化后的布隆过滤器可并行过滤避免了使用流水线技术带来的查找延迟,同时支持删除操作路由,路由更新后不需要重建过滤器降低了路由表的更新延迟。仿真结果表明使用不到2Mb的FPGA片内资源和外部DDR,我们的方案可实现每次查找平均一次片外访问。As a data structure with filtering function,Bloom filter is being widely used in route lookup.The Bloom filter is mainly used to preprocess routing queries in route lookup,because the routing table is usually stored in the off-chip memory.Bloom filtering can filter out routes that do not exist in the routing table,and ensure that all the routes that enter the search circuit are valid routes,thus to minimize the unnecessary searches.This scheme uses an optimized Bloom filter to accelerate the longest prefix matching.The optimized Bloom filter can filter in parallel to avoid the search delay caused by the use of pipeline technology,and at the same time,supports the delete operation route.There is no need to rebuild the filter after the route update,which reduces the update delay of the routing table.Simulation results indicate that,by using FPGA on-chip resources and external DDR less than 2Mb,this solution can achieve an average off-chip access for each route lookup.

关 键 词：布隆过滤 路由查找 哈希算法 FPGA 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TN915.05[自动化与计算机技术—计算机科学与技术]