学位论文 > 优秀研究生学位论文题录展示

单播路由协议快速收敛算法的研究与应用

作　者: 肖乾才
导　师: 李明奇
学　校: 电子科技大学
专　业: 应用数学
关键词: 单播路由协议 SPT 动态最短路径算法 ISPF PRC
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 31次
引　用: 0次
阅　读: 论文下载
 

内容摘要


单源最短路径问题作为图论的一个基本问题,广泛运用于现实世界中.在这些应用领域,最短路径树需要存储并在拓扑变化后更新.静态最短路径算法在拓扑变化后无法利用已有的SPT信息,必须重新计算一颗SPT.然而,动态最短路径算法则利用已有的SPT信息,增量的更新旧的SPT而实现SPT的计算.由此,提高了SPT的计算效率.动态最短路径算法在路由协议领域称之为ISPF(Incremental Shorest Path First). ISPF只需要更新最短路径发生变化的节点.不发生变化的节点不需要在SPT上更新.从而,提高路由计算效率并降低网络路由的震荡.同时,动态最短路径算法的实现有利于单播路由协议的PRC(Partial Route Compute). PRC对提高路由协议的运行效率具有重要意义.动态最短路径算法的研究已比较成熟.但是,大部分算法都是点更新算法,处理多链路权值减小的XiaoBin算法是分支更新算法,处理多链路权值增大的动态最短路径算法的研究却很少.另一方面,已有的动态最短路径算法均没有实现负载均衡.然而,这是路由协议中PRC技术必须具备的功能.基于这些问题,本文对现有动态最短路径算法进行深入分析,主要从以下四方面进行了研究.1.提出了一多链路权值增大的分支动态最短路径算法.仿真结果显示该算法相比XiaoBin点更新算法具有更好的时间效率以及更少的冗余计算.2.为了实现PRC,本文提出了一种基于动态最短路径算法的下一跳增量计算算法.3.为了将动态最短路径算法应用到路由协议中,本文提出了一种动态最短路径算法负载均衡扩展的方法,并由此对两个半动态最短路径算法进行了扩展.4.结合扩展的动态最短路径算法以及下一跳增量计算算法,提出了一种PRC的实现方案.

全文目录


摘要  4-5
ABSTRACT  5-8
第一章 绪论  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
作者在学期间取得的研究成果  67-68

相似论文

  1. 婴幼儿食物过敏流行病学调查,R725.9
  2. 镁碱代替钠碱用于杨木PRC-APMP工艺的研究,TS743.9
  3. ISIS多拓扑路由在路由器上的设计与实现,TN929.5
  4. 用HPLC法建立SPT抑制剂筛选模型的研究,R284
  5. 城市车载自组网路由协议的研究,TN929.5
  6. SPT薄穿通IGBT的设计,TN386
  7. 血府逐瘀制剂提取物对大鼠创伤刺激所致腹腔粘连防治作用的机理研究,R285.5
  8. Ad Hoc网络的单播和组播路由协议的研究,TN929.5
  9. 相位编码雷达若干关键技术研究,TN95
  10. 栀子提取物T9、TH抗单纯疱疹病毒1型作用机理研究,R285.5
  11. 人睾丸特异转录本基因（PRC-T）的克隆和研究,R321
  12. 华弘证券公司资产证券化业务定位研究,F832.39
  13. 我国住房抵押贷款证券化的模式分析,F832.51
  14. 国家农业学科信息门户平台设计实现,TP393.092
  15. 国家农业学科信息门户平台设计实现,TP393.092
  16. 兰州石化公司铁路专用线微机联锁控制系统的设计,U284.3
  17. SPT参与资产证券化的立法问题研究,D922.287
  18. 基于信托模式的银行信贷资产证券化研究,F832.51
  19. 一定条件下平行机排序问题的研究,O223
  20. 论中国资产证券化SPV模式的选择,D922.28

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com