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

• 作者: 乔庐峰 王乾 陈庆华
• 来源期刊: 通信技术
• 学科: 工学
• 关键词: 布隆过滤 路由查找 哈希算法 FPGA
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 网络与系统
• 页码范围: 1674-1679
• 页数: 6页
• 分类号: TP393|TN915.05
• 字数: 3379字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-0802.2020.07.016

摘要

作为一种具有过滤功能的数据结构,布隆过滤器在路由查找中正在被广泛应用.在路由查找中布隆过滤器主要用于预处理路由查询,因为路由表通常存储在片外的存储器中,布隆过滤可以将路由表中不存在的路由过滤掉,保证进入查找电路的都为有效路由,最大程度减少不必要的查找.我们的方案使用一种优化的布隆过滤器来加速最长前缀匹配,优化后的布隆过滤器可并行过滤避免了使用流水线技术带来的查找延迟,同时支持删除操作路由,路由更新后不需要重建过滤器降低了路由表的更新延迟.仿真结果表明使用不到2Mb的FPGA片内资源和外部DDR,我们的方案可实现每次查找平均一次片外访问.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	乔庐峰	陆军工程大学通信工程学院	10	3	1.0	1.0
2	陈庆华	陆军工程大学通信工程学院	9	3	1.0	1.0
3	王乾	陆军工程大学通信工程学院	1	0	0.0	0.0