Internet的快速发展使链路上传输的数据速度达到了 400Gbps,导致路由器的吞吐量和查找最佳出口的工作量也大大增加。路由器对每一个经过的数据报转发的快慢即路由转发速率是影响当前互联网数据吞吐量的关键,路由转发过程中的关键是路由表查找,因此设计一个合适的路由查找算法十分必要。相比于IPv4,IPv6的地址长度更长,这意味着IPv6的路由表表项数会更多,基于前缀长度的IPv4查找算法不能直接扩展到IPv6的查找。论文围绕基于IPv6的路由查找算法展开,分别给出了适用于目前路由表和将来大规模IPv6路由表的路由查找算法。主要工作包括:1、对IPv6单播地址结构和当前骨干路由器路由表分布特点进行了解析,提出了一种B-树和Bloom Filter相结合的IPv6路由查找算法(BTBF)。BTBF首先利用2-3树查找前缀前16bits值,如果正确匹配2-3树节点,那么通过节点中的位数组对于Bloom Filter的映射,将下一步查找转发到Bloom Filter。再计算Bloom Filter计数数组的二进制值通过Hash的方式映射到目的IP地址的存储位置从而获取下一跳。实验结果表明,BTBF相比于其他树形类和Bloom Filter类算法有效减少了查找时间和存储空间占用,能在路由表项数变化较大的情况下维持稳定的查找性能。2、基于二进制比特的Trie型数据结构面对大规模IPv6路由表时查找困难,因此引入了前缀区间的概念以适应大规模动态IPv6路由表查找,提出了一种段表与B-树相结合的IPv6路由查找算法。以α位为分割点将路由前缀分隔为前缀Indexα(P)和后缀Suffixα(P),Indexα(P)保存在段表中,段表为一个顺序表,可以根据的不同分别存储在段表的不同位置,具体的存储形式为Set(i),i前缀Indexα(P)的值。当段表查找阶段匹配成功后可以索引到B-树,然后在B-树中查找后缀Suffixα(P),并利用Cover(x)数组存储被节点区间包含的数据以解决B-树查找歧义问题。将段表和B-树进行结合查找的策略有效地减少了每个查找B-树的节点数,降低了查找深度,提高了查找效率。实验结果表明,该算法与其他的基于前缀区间的Trie树查找算法相比在查找时间和存储空间占用上占有优势,能够满足较大规模的路由表查找性能要求。近年来,研究人员针对IPv6的路由查找算法集中在基于前缀值查找算法研究上,我们在前人的研究基础上对B-树数据结构进行了探索与改进,与其他顺序表或Hash类结构的有机结合,继承了他们一些优秀的思想,并融合进论文算法中,对路由查找算法性能做了进一步的提升。