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

Complete dynamic algorithm for updating shortest path tree

作　　者：孙知信[1] 高艳娟[1] 王文鼐[2] 

机构地区：[1]南京邮电大学计算机学院,南京210003 [2]南京邮电大学通信工程学院,南京210003

出　　处：《吉林大学学报（工学版）》2007年第4期860-864,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金资助项目(60572131);中兴通讯科研基金资助项目

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]