于明，王振安，王东菊

(大连理工大学信息与通信工程学院，辽宁大连116024)

互联网应用的快速发展给路由器技术带来了极大的挑战，如何提高路由器的转发速度已成为下一代网络技术的研究热点［1］。在影响路由器报文转发速度的众多因素中，路由查找方法的设计是极为关键的一个环节［2］。

相对于传统的路由查找方法，如基于Trie树的路由查找方法、基于HASH的路由查找方法和基于内容可寻址存储器(content addressable memory，CAM)的硬件实现方法等［3］，基于Bloom滤波器的路由查找方法出现相对较晚，但其在查找时间和存储空间方面的优异性能却引起了研究人员的广泛关注。2003年，Sarang.D等首次将Bloom滤波器引入到路由查找中［4］，将不同长度的IP地址前缀存储在不同的Bloom滤波器中，待查询的IP地址并行输入到所有Bloom滤波器中，并根据滤波器的查询结果探测相应的选路表，以确定报文转发的下一跳信息。实验结果表明，该方法在查找时间和存储空间方面较之传统的路由查找方法有了较大提升。其不足之处是［5］:1)选路表的探测次数与Bloom滤波器的个数直接相关，当出现误称的滤波器增多时，无效探测次数会随之增多，导致路由查找时间增长;2)不同长度的地址前缀对应的选路表大小不均，无法保证路由查找性能的最优化。

为了解决上述问题，Haoyu.S等提出了一种基于分布式Bloom滤波器结构的路由查找方法［6］，该方法是将一个完整的Bloom滤波器分成k个大小相同的子部分，并将哈希函数重新分组，每组中哈希函数的数量与前缀长度的数量相对应。……