单播路由协议SPT动态最短路径算法ISPFPRC硕士论文.doc

单播路由协议快速收敛算法的研究与应用应用数学， 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 算法