论文研究 基于快速搜索树的路由查表算法.pdf

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