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

论文摘要

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

论文目录

• 摘要
• Abstract
• 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 研究展望
• 参考文献
• 致谢
• 个人简历及在学期间发表的学术论文与研究成果