IP路由查找算法的研究

摘要

近些年来，互联网得到了极大的发展，越来越多的人利用互联网来通信，于是网络业务急剧增加。据调查，自从1997年后Internet的网络业务流量和带宽以及网络骨干路由器的接口速率以每半年增长一倍的速度增长，由此导致骨干路由器每秒需要转发的报文数量也随之剧增。
　　 而在路由器处理巨量业务的过程中，最重要同时也是最耗时的一步就是查找路由表。因此，快速的IP路由查找算法是实现高速分组转发的关键。而且IP路由查找算法的空间复杂度和时间复杂度以及高效的实现方法一直是研究的热点问题，也可以说这些因素目前还是网络发展的瓶颈。由此可见IP路由查找算法的优劣直接影响当前和未来的Internet网络的整体性能。
　　 在此背景下，本文提出了一种基于硬件的快速IP路由查找算法：并行前缀长度猜测算法(PPLS,parallel prefix length speculation)，以及该算法的改进算法—基于Trie的PPLS算法。与传统路由查找算法不同的是，本文提出的算法给出了一种IP前缀长度猜测机制。也就是当一个分组来的时候，该算法先猜测分组目的地址所对应前缀的长度，然后以猜测到的长度为基准通过精确匹配来进一步确认。这样大大减少了查找时间，同时还减少了查找过程中所用到的存储空间。
　　 首先，本文介绍IP路由查找算法的发展现状，以及一些相关背景技术。然后，分析和比较了现有IP路由查找方法，为引出本文最终所要提出的新的路由查找思路和算法做准备。接下来，我们详细描述了本文提出的IP路由查找算法：并行前缀长度猜测算法，并在此基础上提出了另一种改进算法，所以第三章是本文的核心章节。然后搭建了的仿真平台，给出了具体的仿真结果，并与其他传统方法进行了性能比较。最后第五章总结了我们的工作，并讨论了进一步研究的方向。

目录

文摘

英文文摘

论文说明：图表目录、缩略词表

声明

第一章绪论

1.1IP路由查找算法与IP地址结构

1.2IP路由查找算法的发展概述

1.3本文工作的意义和价值

1.4本文的内容安排

第二章现有路由查找算法的研究及相关技术

2.1现有IP路由查找算法概述

2.1.1基于trie的IP路由查找算法

2.1.2基于CAM的路由查找策略

2.1.3基于转发表的路由查找策略

2.2相关技术的介绍

2.3本章小结

第三章 IP路由查找算法的新思路—并行前缀长度猜测算法

3.1索引技术概论

3.2并行前缀长度猜测算法--PPLS

3.2.1原理描述

3.2.2 PPLS算法描述

3.2.3应用实例

3.3基于trie的并行前缀长度猜测算法--PPLS with trie

3.3.1原理描述

3.3.2算法描述

3.3.3关于trie结构的进一步改进模型

3.4路由表更新

3.4.1 PPLS算法更新

3.3.2 PPLS with trie算法路由更新

3.5 PPLS算法优化

3.5.1回执次数优化

3.5.2链表深度优化

3.5.3存储空间的优化

3.6 PPLS with trie算法优化

3.6.1 PPLS with trie查找效率优化

3.6.2 PPLS with trie存储空间的优化

3.7关于PPLS与PPLS with trie的说明

3.8前缀分布对PPLS算法的影响

3.9本章小结

第四章 PPLS模拟仿真及实验数据分析

4.1 PPLS仿真结果及分析

4.2基于trie的PPLS算法仿真

4.3与其他方法的比较

4.3.1与trie的对比

4.3.2与基于索引的路由查找算法比较

4.4本章小结

第五章全文总结

5.1本文研究工作总结

5.2未来的研究方向

致谢

参考文献

个人简历及在校期间研究成果