该论文回顾了现有的路由查找算法的一些问题,包括对于路由查找性能最敏感的两大指标:转发表的体积和平均内存访问次数方面的问题.在对现有算法分析的基础上提出了一套新的路由查找算法,主要内容包括以下的几个方面:1.首先针对现有的算法进行了归纳和总结:对现有路由查找算法进行分类、归纳和总结,在此基础上对它们的转发表信息冗余度、转发表体积和平均内存访问次数等等方面的性能进行分析.2.在上述分析的基础上,作者提出了一种被称为自适应分段多分搜索树(ASMS树:Adaptive Segmented Multiway Search)的查找树结构.这种树型结构可以根据实际路由前缀分布自适应的压缩转发表中的冗余信息,调整节点分支因子的大小,从而提高了单次内存访问所获取的信息量,同时也达到显著压缩转发表体积的目的.同时,文中研究并给出了针对该查找树的路由查找算法.ASMS树对转发表中冗余信息进行了压缩,这种压缩可以被看成是对转发表的预处理.理论上来说:每次路由更新都可能导致ASMS树的重构,而Internet中路由规则变化是非常频繁的,在每次路由规则变化时都进行ASMS树的重构会带来大量的开销,为此,文中还给出了一种简单有效的准渐进式更新算法.3.内存访问是路由表查找过程中的性能瓶颈,因此降低平均内存访问次数会有效的提高路由查找的效率.为了达到最优化的平均内存访问次数,需要采用动态规划的方法,这意味着生成算法本身异常复杂,运算量非常大.即使采用前面的准渐进式更新算法,可以预期ASMS树的重构仍然会相当频繁,因此采用动态规划算法不能满足实际应用的需求.为此,作者给出了两种针对平均内存访问次数优化的启发式ASMS树生成算法.这两种算法简单有效,均采用自项向下的工作模式.4.转发表的体积是路由查找算法另外一个重要性能指标.较小的转发表体积一方面可以提高路由查找过程中Cache的命中率,从而降低内存访问方面的开销:另一方面较小的转发表也意味着较好的扩展潜力,使得该查找算法可以适应于更加复杂的情况.作者给出了两种针对转发表体积优化的启发式ASMS树生成算法.这两种算法均采用自底向上的工作模式.进而,作者证明了这两种算法可以取得以"ASMS树节点数量最少"为最优准则时的最优解.最后,作者总结全文,综合了作者在该课题研究中的主要成果,并且提出了需要进一步研究和讨论的问题.