摘要
根据路由表中前缀的分布特点,将路由集合分割成几个子集,然后分别针对每个子集建立搜索树来实现路由查表。借助哈希压缩索引表使搜索树的深度降低到3,加快了搜索树的查找速度。而BloomFilters的应用,使几乎平均一次搜索树的查找就可以完成一次路由查表。该算法可以满足OC768链路的处理速度要求,支持达106数量级的路由表项,适于硬件流水线方式实现,具有很高的实用价值。这种方法用到IPv6同样可以收到很好的效果。
This paper describes a novel algorithm for implementing high speed IP routing lookups which splits the route rules into several subsets according to the prefix length distributions and constructs fast search trees for each subset. Using the hash compression index tables and Bloom Filters the speed of lookup is improved dramatically. This scheme can be easily implemented in hardware using a pipeline fashion and the results of the experimental and application show that it is practical and efficient. This approach is equally attractive for IPv6.
出处
《计算机应用研究》
CSCD
北大核心
2005年第7期226-228,233,共4页
Application Research of Computers
基金
国家重大自然科学基金资助项目(69896240)
"211工程"重点学科建设项目
