具有高转发能力的路由器是构建高速网络的核心设备,路由器能否实现高性能转发是现在网络发展的关键因素之一。由于路由查找是转发过程中的关键环节,因此路由查找算法的速度直接影响着路由器的报文转发性能,它也成为了制约网络性能提高的主要瓶颈。路由查找技术的研究受到广泛重视,主要归结在两个方面:一是查找速度,二是内存消耗。本文围绕这两个方面,先对路由器的基本工作原理进行了简要介绍,并对现有的路由查找算法进行了综述和分类比较,对它们的空间复杂度和时间复杂度做了分析,在此基础上,针对不同的应用背景和需求提出了两个高性能算法。本文第三章中简单介绍了传统的基于Hash转发表的路由查找算法,并在此基础上进行了改进,提出了一种新的算法——基于可变级数的多级Hash转发表的路由查找算法。该算法首先把多级Hash存储结构思想用在设计转发表结构中,这种存储结构能够明显的降低内存访问次数,通常情况下,两次到三次访存就足够了,从根本上提升了路由查找的速度。其次,实现了级数的可定制性,使得在一套软件系统下,产品用户(路由器开发人员)可以根据路由器形态(内存、性能)在路由查找速度与所耗内存容量二者之间根据自己的需求权衡主次,来选择定制Hash表的级数。另外,本算法提出一种基于“父子关系”的节点添加思想,大大缩短了传统的Hash表查找方式中遍历冲突链的时间,最大限度的提高了查找效率。实验数据表明,该算法在时间上与内存消耗上与传统的算法相比都有明显的提升。本文第四章从转发表的存储结构上对传统的算法进行了改进,提出了对转发结构中的“前缀”和“下一跳”分离的存储结构;然后,对分离后的“前缀”与“下一跳”之间建立关联关系,使它们之间能够彼此快速的定位查找。本算法在空间上大大节省了内存需求;时间上避免了在下一跳地址信息发生改变时重刷转发表项缓慢的问题。实验数据表明本算法达到了优化现有算法的目的。上述两种路由查找算法中,基于可变级数Hash表的方法,既可应用于骨干网中的路由器包括核心路由器的高端路由器中来提高处理频率,又可以用在中等负载能力的中端路由器中,使其在处理速度与内存消耗上达到自己特定的需求,例如H3C公司的SR88路由器。基于分离存储结构的方法,可应用于内存容量不大,或者对内存消耗有限制的中、低端路由器中,例如H3C公司的AR49/39/29系列路由器。