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

摘要

针对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 meth⁃od 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 up⁃date of routing tables was supported by associating a counter with each bit in the bit vectors of the basic Bloom fil⁃ters. The theoretical analysis showed the proposed method is more efficient than the existing methods with less aver⁃aged number of times to probe into the route selection tables, and lowers its upper bound under the worst circum⁃stances. Experimental results validated the efficacy of the proposed method and proved the accuracy of the perform⁃ance analysis.