随着互联网接入设备的指数增长,以及各种网络新业务的不断涌现,IPv4协议已经越来越不能满足需求,其首要问题就是地址空间不足。因此拥有128位地址的IPv6逐渐发展起来,以其巨大的优势将会得到长远的发展,并最终取代IPv4。IPv6的发展需要现有的路由器支持IPv6的寻址方案和地址格式,而路由器的主要功能之一就是对收到的IP分组进行选择转发。在目前链路速度已经达到光纤的情况下,制约分组转发速度的因素就是路由表查找算法。而现有的路由器及其路由查找机制都是基于IPv4设计的,直接应用到IPv6中其查找性能都差强人意,所以需要设计出一种支持IPv6的路由查找算法。本文对已有的路由查找算法进行了深入的分析,研究了各个算法的优缺点,比较了已有的IPv4算法移植到IPv6中的性能,从中发现支持IPv6的高速路由查找算法,若采用多种数据结构,并且取其各个算法结构的优点,扬长避短,可以设计出查找速度快、更新效率高、支持更长的地址前缀的IPv6路由查找算法。本文分析了已有的路由查找算法,IPv6地址的特性以及主干网路由表的前缀分布特点,并且借鉴了文献[1]中LFT哈希表结构简单、查找快速的优点,提出了以32bits为查找路由前缀起点的分段哈希表和多比特Trie树相结合的IPv6路由查找算法。该算法结构简单、查找效率高、易于更新,多数情况下只需一次内存访问就可查找到路由信息,提高了IPv6主干网路由器转发速度,以满足下一代互联网IPv6发展的需求。