单播路由协议快速收敛算法的研究与应用
应用数学， 2011，硕士
【摘要】单源最短路径问题作为图论的一个基本问题,广泛运用于现实世界中.在这些应用领域,最短路径树需要存储并在拓扑变化后更新.静态最短路径算法在拓扑变化后无法利用已有的SPT信息,必须
重新计算一颗SPT.然而,动态最短路径算法则利用已有的SPT信息,增量的更新旧的SPT而实现SPT的计算.由此,提高了SPT的计算效率.动态最短路径算法在路由协议领域称之为ISPF(Incremental Shorest Path First). ISPF只需要更新最短路径发生变化的节点.不发生变化的节点不需要在SPT上更新.从而,提高路由计算效率并
降低网络路由的震荡.同时,动态最短路径算法的实现有利于单播路
由协议的PRC(Partial Route Compute). PRC对提高路由协议的运行效率具有重要意义.动态最短路径算法的研究已比较成熟.但是,大部分算法都是点更新算法,处理多链路权值减小的XiaoBin算法是分支更新算法,处理多链路权值增大的动态最短路径算法的研究却很少.
另一方面,已有的动态最短路径算法均没有实现负载均衡.然而,这是路由协议中PRC技术必须具备的功能.基于这些问题,本文对现有动
态最短路径算... 更多还原
【Abstract】 Single-Source Shortest Path as a basic problem
of Graph theory, is widely used in the real world. In these applications, SPT need store and update after topology changed.
Static SPT algorithms have to recomputed a new SPT after topology changed for they unable to use the information of the old SPT. Yet dynamic SPT algorithms update the old SPT to incremental compute a new SPT, therefore promote the efficiency of SPT computing.In routing area, dynamic SPT algorithms are called ISPF(Incremental Sh... 更多还原
【关键词】单播路由协议；SPT；动态最短路径算法；ISPF；PRC；【Key words】unicast routing protocols；SPT；dynamic SPT algorithm；ISPF；PRC；
摘要4-5
ABSTRACT 5
第一章绪论8-13
1.1 课题背景与意义8-9
1.2 课题研究历史与现状9-11
1.3 论文的主要贡献和创新点11
1.4 论文内容安排11-13
第二章单源最短路径问题13-20
2.1 单源最短路径问题定义及术语约定13-14
2.2 静态最短路径算法14-15
2.2.1 Bellman-Ford 算法14-15
2.2.2 Dijkstra 算法15
2.3 动态最短路径算法15-18
2.3.1 动态最短路径算法定义15
2.3.2 SWSF-FP 算法15-16
2.3.3 Narvaez 算法16-17
2.3.4 XiaoBin 算法17-18
2.4 本章小结18-20
第三章动态最短路径算法、改进与仿真20-43
3.1 多链路权值减小的XiaoBin 算法改进20-22
3.1.1 Nfixed 算法改进20-21
3.1.2 边检查改进21-22
3.2 多链路权值增大的动态最短路径算法22-32
3.2.1 单边算法处理多边权值变大存在的两个问题23-24
3.2.2 多链路权值增大最短路径算法24-28
3.2.3 算法分析28-29
3.2.4 实例29-30
3.2.5 复杂度分析30-32
3.3 动态最短路径算法的仿真实现32-42
3.3.1 拓扑生成32-33
3.3.2 公共数据结构设计33-38
3.3.3 初始SPT 计算38
3.3.4 动态最短路径算法实现38
3.3.5 实验设计38-39
3.3.6 仿真结果39-42
3.4 本章小结42-43
第四章PRC 算法设计43-61
4.1 PRC 介绍43-45
4.2 下一跳增量计算的算法设计45-47
4.3 实例47-48
4.4 动态最短路径算法的负载均衡扩展48-57
4.4.1 XiaoBin 算法的负载均衡扩展49-53
4.4.2 链路权值增加分支更新算法的负载均衡扩展53-57
4.5 PRC 算法57-58
4.6 实际拓扑的动态最短路径树更新58-60
4.7 本章小结60-61
第五章结论与展望61-63
5.1 总结61-62
5.2 展望62-63
致谢63-64
参考文献64-67