基于快速搜索树的路由查表算法

• 作者: 张勇 谭兴晔 雷振明
• 来源期刊: 计算机应用研究
• 关键词: IP路由查找 最长前缀匹配 搜索树 Bloom Filters 哈希
• 年，卷（期）: 2005,（7）
• 所属期刊栏目: 网络通信
• 页码范围: 226-228,233
• 页数: 4页
• 分类号: TP393
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2005.07.080

摘要

根据路由表中前缀的分布特点,将路由集合分割成几个子集,然后分别针对每个子集建立搜索树来实现路由查表.借助哈希压缩索引表使搜索树的深度降低到3,加快了搜索树的查找速度.而Bloom Filters的应用,使几乎平均一次搜索树的查找就可以完成一次路由查表.该算法可以满足OC-768链路的处理速度要求,支持达106数量级的路由表项,适于硬件流水线方式实现,具有很高的实用价值.这种方法用到IPv6同样可以收到很好的效果.