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

A fast method for IP lookups based on Bloom filters

作　　者：于明[1] 王振安[1] 王东菊[1] 

机构地区：[1]大连理工大学信息与通信工程学院,辽宁大连116024

出　　处：《哈尔滨工程大学学报》2014年第10期1247-1252,共6页Journal of Harbin Engineering University

基　　金：国家自然科学基金资助项目(61172059);辽宁省博士启动基金资助项目(20111022)

摘　　要：针对IP路由查找中的最长前缀匹配问题,提出了一种基于Bloom滤波器的快速路由查找方法。首先,通过建立首字节索引表,减少了需要并行查询的Bloom滤波器的数量。其次,基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化,降低了查询过程对Bloom滤波器总数的需求。最后,将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联,实现了对路由更新的支持。理论分析表明,与现有方法相比,利用该方法进行路由查找可以实现更低的选路表平均探测次数,并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。To solve the problem of the longest prefix matching in IP routing lookups,a fast IP routing lookup method based on Bloom filters was proposed. A first-byte indexing table was established to reduce the number of Bloom filters to be queried in parallel. The number of Bloom filters was optimized based on the non-uniform distribution of the prefix lengths of IP addresses,so that the number of Bloom filters required in IP lookups was reduced. The update of routing tables was supported by associating a counter with each bit in the bit vectors of the basic Bloom filters. The theoretical analysis showed the proposed method is more efficient than the existing methods with less averaged number of times to probe into the route selection tables,and lowers its upper bound under the worst circumstances. Experimental results validated the efficacy of the proposed method and proved the accuracy of the performance analysis.

关 键 词：路由查找 最长前缀匹配 前缀汇聚 BLOOM滤波器 并行查询 路由表 IP网络 互联网 

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