基于前缀值的IPv6路由查找算法研究

摘要

随着互联网的迅猛发展，计算机网络的应用已经渗入到各个领域中，网络在整个经济的发展中的作用越来越重要，带来的价值也越来越多。与此同时，传统的IPv4协议已经不能完全满足需要，而仅仅32位的IP地址也已日趋耗尽。下一代互联网NGI(Next Generation Internet)的核心协议——IPv6正吸引着学术界和产业界的目光，并得到了广泛的关注和认可。 与IPv4相比，IPv6具有很多优点，比如IPv6使用128位的IP地址，从而能提供超大的地址空间；IPv6的报头更简洁、扩展性更好；IPv6能够更好的支持即插即用、服务质量和移动性等。但是在路由查找方面，IPv6仍然遵循最长匹配的原则。而现有的大多数路由查找算法只能适应IPv4环境下的32位前缀，它们有的不能够应用到IPv6中，或者是应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。因此，128位的IPv6地址给路由查找带来了新的挑战，而随着IPv6网络规模的日趋扩大，寻找高性能的IPv6路由查找算法也势在必行。 本文深入研究了IPv6地址特征、IPv6地址分配策略和IPv6骨干网路由表的特点，再结合对前缀区间和前缀层次的研究，提出了一种适合于IPv6的高性能路由查找算法。通过使用真实路由表和模拟路由表对该算法进行测试，测试结果表明该算法的可扩展性非常出色，它能够支持数据量达到200K的大路由表。与经典算法在同样环境下相比，结果也表明该算法在平均查找速度和内存消耗方面都有一定的优势。出色的性能和对大路由表的支持，使得该算法能够应用到IPv6骨干网路由器中。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究内容和论文结构

第二章技术背景

2.1路由表查找

2.2 CIDR

2.3最长前缀匹配

2.4性能评价指标

第三章已有路由查找算法及性能分析

3.1二叉Trie树

3.2路径压缩Patricia

3.3多分支Trie树

3.4层次压缩树LC-trie

3.5基于硬件的算法

3.6已有的IPv6路由查找算法

3.7性能比较

第四章IPv6地址分配策略及路由表特征

4.1 IPv6地址特征

4.2 IPv6地址分配策略

4.3 IPv6骨干网路由表的特点

4.3.1路由条目数

4.3.2前缀长度分布

4.3.3下一跳的数目

4.3.4.路由前缀各16位的特点

4.3.5前缀层次

4.3.6路由冗余

4.4大规模IPv6路由表的预测和产生

第五章PRPL算法

5.1算法技术基础

5.1.1前缀区间

5.1.2前缀层次结构

5.1.3前缀层次树

5.2算法数据结构

5.3算法实现

5.3.1构建数据结构

5.3.2路由查找

5.3.3路由更新

第六章性能分析与比较

6.1实验环境和实验方法

6.2性能分析

6.3内存占用比较

6.3.1真实路由表时内存占用比较

6.3.2模拟路由表时内存占用比较

6.4平均查找速度比较

6.4.1真实路由表时平均查找速度比较

6.4.2模拟路由表时平均查找速度比较

第七章总结与展望

7.1全文总结

7.2研究展望

参考文献

致 谢

作者攻读学位期间发表的学术论文目录