哈希表和多比特Trie树相结合的IPv6路由查找算法的研究

摘要

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

目录

文摘

英文文摘

图的目录

表的目录

1 绪论

1.1 研究背景

1.2 国内外研究历史与现状

1.2.1 分类IP路由查找

1.2.2 无类域间路由CIDR查找

1.2.3 IPv6路由查找

1.3 本文研究内容

1.4 本文的组织结构

2 相关技术概述

2.1 路由器的相关介绍

2.1.1 路由器在网络中的位置与作用

2.1.2 路由器的体系结构

2.1.3 路由器的工作原理

2.2 路由查找算法面临的问题

2.2.1 常规(分类)IP寻址与路由

2.2.2 无类域间路由CIDR和最长前缀匹配LPM

2.2.3 IPv6

2.3 IPv4路由表的前缀分布

2.4 IPv6路由技术

3 常用路由查找算法研究

3.1 基于Trie的路由查找算法

3.1.1 二叉Trie树(Binary Trie)

3.1.2 路径压缩Trie树(path-compressed Trie)

3.1.3 多比特Trie树(multibit Trie)

3.1.4 层次压缩Trie树(LC-Trie)

3.2 基于Hash的路由查找算法

3.2.1 基于前缀长度的二分路由查找算法

3.2.2 基于前缀值的二分路由查找算法

3.3 基于硬件的实现方法

3.3.1 基于CAM的查找实现机制

3.3.2 采用TCAM的查找实现机制

3.3.3 其它的一些硬件实现方法

3.4 把LMP查找转化为非重叠前缀查找

3.5 已有的IPv6路由查找算法

3.6 路由查找算法性能评价

3.7 已有IPv4算法移植到IPv6中的性能分析

4 IPv6的发展及特点

4.1 IPv6地址特点

4.1.1 IPv6地址表示和前缀表示

4.1.2 IPv6地址空间的分配

4.1.3 全局单播地址结构和分配策略

4.2 IPv6主干网中真实路由表的特征

5 分段哈希方法的IPv6路由查找算法

5.1 算法思想

5.2 算法数据结构

5.2.1 表的数据结构

5.2.2 树的数据结构

5.2.3 算法的整个数据架构

5.2.4 哈希函数的构造和冲突问题的解决

5.2.5 回退问题的解决

5.3 算法数据结构的初始化

5.4 查找过程

5.5 更新路由操作

6 算法性能分析

6.1 实验配置

6.1.1 IPv6路由表仿真工具

6.1.2 算法测试数据

6.2 性能分析

6.2.1 时间复杂度

6.2.2 存储空间的消耗

6.3 实验比较

6.3.1 平均查找速度比较

6.3.2 内存占用比较

7 总结与展望

7.1 全文总结

7.2 研究展望

参考文献

致谢

个人简历及在学期间发表的学术论文与研究成果