摘要
在已有的动态更新最短路径树(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.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2007年第4期860-864,共5页
Journal of Jilin University:Engineering and Technology Edition
基金
国家自然科学基金资助项目(60572131)
中兴通讯科研基金资助项目
关键词
计算机系统结构
路由协议
SPF算法
最短路径树
动态更新
computer systems organization
routing protocol
SPF algorithm
shortest path tree
dynamic update
