基于分段分层和索引表的前缀区间IPV6路由查找算法

作     者：白晓庆 

作者单位：东北大学 

学位级别：硕士

导师姓名：党群

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：IPV6路由查找 前缀区间 分段分层 索引表 HASH表 

摘      要：在当前计算机网络飞速发展的步伐下,IPV4的局限性已经越发的显现出来了。除了安全性和性能方面的缺陷处,最主要的还是地址空间严重不足。 IPV6由于具有2128个地址,可以很好的解决地址空间不足的问题。然而IPV6的路由查找仍然遵守最长前缀匹配原则,所以地址长度的增加也导致了IPV6路由查找难度的增加。而目前的路由查找算法主要适用于IPV4,如果简单的套用到IPV6,会导致内存占用空间和读取次数都急距增加,性能急剧降低。而现有的IPV6路由查找算法都处在理论阶段,性能还不明确。因此寻找适用于IPV6的路由查找算法显得十分迫切。 本文深入分析了已有的路由查找算法,发现了基于前缀区间的二分查找法的缺陷,并提出前缀分层的改进方案,由此形成了本文算法的理论基础。深入研究了IPV6的地址分配策略,从世界的六个不同地点下载了IPV6真实路由表,并对其地址前缀的分布特点进行了深入分析和研究,形成了对本文算法的数据支撑。在以上理论研究和数据分析的基础上,提出了本文算法数据结构的三个部分：分段分层的前缀层次部分,数量最多的长度为32的前缀的索引表部分以及HASH表部分。并对每部分的数据结构特点进行了详细叙述,对本文算法的构建,更新,查找和删除过程也进行了详细介绍。并通过真实路由表和按其分布特点形成的模拟路由表对该算法的性能进行了对比测试。与Patricia trie和Radix trie在同样的软硬件环境下进行比较,表明该算法的构建速度,内存占用空间和平均查找速度以及可扩展性都占有很大优势。该算法的出色表现以及容易实现等特性使之能够达到IPV6主干网路由查找的性能要求。