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

维普资讯 第 37卷 第 4期 吉 林 大 学 学 报 (工 学 版 ) Vo1．37 NO．4 2007年 7月 JournalofJilinUniversity (EngineeringandTechnologyEdition) July2007 更新最短路径树的完全动态算法 孙知信 ，高艳娟 ，王文鼐 (1．南京邮电大学 计算机学院，南京 210003；2．南京邮电大学 通信工程学院，南京 210003) 摘 要：在 已有的动态更新最短路径树 (ShrotestPathTree，SPT)算法的基础上，提 出节点 生变化时更新SPT的方案，与SPT 中权值发生变化时更新SPT的方案相结合，提出处理网 拓扑变化的完全动态 SPT(CompletelyDynamicofShortestPathTree，CD_SPT)算法。 网络拓扑发生变化时，该算法对边的权值增加、减少的情况 ，节点加入、删除的情况进行分别 作，但其基本思想都是利用 已有SPT 的有用信息，只关注需要变化的边和节点，通过缩小计 规模来减少冗余计算，从而大大减少计算量。仿真试验结果表 明，cD_SPT算法具有更高的 率和更好的性能。 关键词：计算机系统结构；路 由协议；SPF算法；最短路径树 ；动态更新 中图分类号：TP393 文献标识码 ：A 文章编号 ：1671—5497(2007)04—0860—05 Completedynamicalgorithm forupdatingshortestpathtree SunZhi—xin ，GaoYan—juan，W angWen—ding (1．SchoolofComputerScienceandTechnology，NanjingUniversityofPostsand Telecommunications，Nanjing 210003，China；2．SchoolofCommunication，NanjingUniversityofPostsandTelecommunications，Nanjing210003， China) Abstract：A new completedynamicalgorithm forupdatingshortestpath (CD-SPT)treewasproposed 发 络 当 操 算 效 bycombiningtheexistingalgorithm forupdatingshortestpathtree (SPT)andthesolutionforSPT whenanodeisaddedordeleted．W hen thenetwork topologychanges，the increaseordecreaseof edge——weightand the addition or deletion ofnodes can be processed by the CD——SPT algorithm respectively．Thisalgorithm paysattentiononlytothechangesofnodesandedgesbytakingfullyuse oftheusefulinformationprovidedbytheexistingSPT．Computationoftheredundancycanbereduced byminimizing the computation scope，thusthe totalcomputation can be significantly reduced． SimulationexperimentverifiesthegoodperformanceandhighefficiencyoftheCD—SPT algorithm． Keywords：computer systemsorganization；routing protocol；SPF algorithm ；