基于Bloom滤波器的快速路由查找方法

• 作者: 于明 王东菊 王振安
• 来源期刊: 哈尔滨工程大学学报
• 学科: 工学
• 关键词: 路由查找 最长前缀匹配 前缀汇聚 Bloom滤波器 并行查询 路由表 IP网络 互联网
• 年，卷（期）: 2014,（10）
• 页码范围: 1247-1252
• 页数: 6页
• 分类号: TP393
• 字数: 6054字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-7043.201306057

摘要

针对IP路由查找中的最长前缀匹配问题，提出了一种基于Bloom滤波器的快速路由查找方法。首先，通过建立首字节索引表，减少了需要并行查询的Bloom 滤波器的数量。其次，基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化，降低了查询过程对Bloom滤波器总数的需求。最后，将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联，实现了对路由更新的支持。理论分析表明，与现有方法相比，利用该方法进行路由查找可以实现更低的选路表平均探测次数，并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于明	大连理工大学信息与通信工程学院	10	43	4.0	6.0
2	王东菊	大连理工大学信息与通信工程学院	2	8	2.0	2.0
3	王振安	大连理工大学信息与通信工程学院	1	3	1.0	1.0