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

A Routing Lookup Algorithm Based on Fast Search Trees

作　　者：谭兴晔[1] 张勇 雷振明[1] 

机构地区：[1]北京邮电大学ATM中心,北京100876 [2]Intel中国研究中心,北京100020

出　　处：《计算机应用研究》2005年第7期226-228,233,共4页Application Research of Computers

基　　金：国家重大自然科学基金资助项目(69896240);"211工程"重点学科建设项目

摘　　要：根据路由表中前缀的分布特点,将路由集合分割成几个子集,然后分别针对每个子集建立搜索树来实现路由查表。借助哈希压缩索引表使搜索树的深度降低到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.

关 键 词：IP路由查找 最长前缀匹配 搜索树 BLOOM FILTERS 哈希 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]