基于IPv6的路由查找算法的研究与设计

摘要

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类结构的有机结合，继承了他们一些优秀的思想，并融合进论文算法中，对路由查找算法性能做了进一步的提升。

目录

摘要

第一章 绪论

1．1 研究背景与意义

1．2 主要创新点及内容

1．3 论文内容和论文结构

第二章 IPv6现状与技术概述

2．1 IPv6的发展现状

2．2 路由表与其作用

2．3 无类域问路由CIDR

2．4 Pv6地址结构

2．4．1 单播地址

2．4．2 组播地址和任播地址

2．5 骨干路由器IPv6地址前缀分布特点

2．6 本章小结

第三章 常用的IPv6路由查找算法

3．1．基于前缀长度的IPv6路由查找算法

3．1．1 Binary Trie

3．1．2 路径压缩Trie树

3．1．3 基于前缀长度的二分查找算法

3．2．基于前缀值的动态IPv6路由表查找算法

3．2．1 递归平衡多路径区间树的IPv6路由查找算法

3．2．2 用于动态路由器表的多前缀Trie

3．2．3 改进的基于Bloom Filter的IP路由查找方法

3．3 基于硬件的IPv6路由实现方法

3．4 本章小结

第四章 一种B-树和Bloom Filter相结合的路由查找算法

4．1．数据结构

4．1．2．B-Tree节点的数据结构

4．1．3 Bloom Filter的数据结构

4．2 路由查找过程

4．3 路由更新及算法性能分析

4．3．1 路由的更新过程

4．3．2 算法性能分析

4．4 实验验证

4．5 本章小结

第五章 一种段表和B-树相结合的IPv6路由查找算法

5．1 算法数据结构

5．1．1 算法思想与依据

5．1．2 B-树数据结构

5．1．3 段表的数据结构

5．2 算法实现过程

5．3 算法更新与性能分析

5．3．1 算法性能分析

5．3．2 算法更新

5．4 实验验证

5．5 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

攻读学位期间发表的学术论文与参加的研究工作

声明