更新最短路径树的完全动态算法

吉林大学学报(工学版)

更新最短路径树的完全动态算法

孙知信¹，高艳娟¹，王文鼐²

1.南京邮电大学计算机学院，南京 210003； 2.南京邮电大学通信工程学院，南京 210003

收稿日期:2006-07-14 修回日期:2006-09-23 出版日期:2007-07-01 发布日期:2007-07-01
通讯作者: 孙知信

Complete dynamic algorithm for updating shortest path tree

Sun Zhi-xin¹, Gao Yan-juan¹，Wang Wen-ding²

1.School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003, China; 2. School of Communication, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Received:2006-07-14 Revised:2006-09-23 Online:2007-07-01 Published:2007-07-01
Contact: Sun Zhi-xin

摘要/Abstract

摘要： 在已有的动态更新最短路径树（Shrotest Path Tree，SPT）算法的基础上，提出节点发生变化时更新SPT的方案，与SPT中权值发生变化时更新SPT的方案相结合，提出处理网络拓扑变化的完全动态SPT(Completely Dynamic of Shortest Path Tree, CD_SPT )算法。当网络拓扑发生变化时，该算法对边的权值增加、减少的情况，节点加入、删除的情况进行分别操作，但其基本思想都是利用已有SPT的有用信息，只关注需要变化的边和节点，通过缩小计算规模来减少冗余计算，从而大大减少计算量。仿真试验结果表明，CD_SPT算法具有更高的效率和更好的性能。

关键词: 计算机系统结构, 路由协议, SPF算法, 最短路径树, 动态更新

Abstract: A new complete dynamic algorithm for updating shortest path (CD-SPT) tree was proposed by combining the existing algorithm for updating shortest path tree (SPT) and the solution for SPT when a node is added or deleted. When the network topology changes, the increase or decrease of edge-weight and the addition or deletion of nodes can be processed by the CD-SPT algorithm respectively. This algorithm pays attention only to the changes of nodes and edges by taking fully use of the useful information provided by the existing SPT. Computation of the redundancy can be reduced by minimizing the computation scope, thus the total computation can be significantly reduced. Simulation experiment verifies the good performance and high efficiency of the CDSPT algorithm.

Key words: computer systems organization, routing protocol, SPF algorithm, shortest path tree, dynamic update

中图分类号:

TP393

孙知信，高艳娟，王文鼐 . 更新最短路径树的完全动态算法[J]. 吉林大学学报(工学版), 2007, 37(04): 860-864.

Sun Zhi-xin, Gao Yan-juan，Wang Wen-ding . Complete dynamic algorithm for updating shortest path tree[J]. 吉林大学学报(工学版), 2007, 37(04): 860-864.

参考文献

相关文章 15

[1]	余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2]	张维维, 何家峰, 高国旺, 任丽莉, 申铉京. 基于博弈论的无线Mesh网络路由与信道分配联合优化算法[J]. 吉林大学学报(工学版), 2018, 48(3): 887-892.
[3]	董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[4]	赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[5]	刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[6]	董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[7]	于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[8]	邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[9]	魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[10]	郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[11]	魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[12]	车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[13]	冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[14]	董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[15]	匡哲君，师唯佳，胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed