文档介绍：基于路由最短路径树的动态多节点删除算法基于路由最短路径树的动态多节点删除算法第37卷VlO】-?网络与通信?文章编号:10o0_-_3428(2011)05—0121—一13文献标识码:A中图分类号:TP393基于路由最短路径树的动态多节点删除算法粱德恒,姚国祥,官全龙(暨南大学信息科学技术学院,广州510632)摘要:,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,己更新节点不再被插入队列,,:最短路径;动态更新;路由算法;多节点DynamicMulti—nodeRemoveAlgorithmBased0nRoutingShortestPathTreeLIANGDe-heng,YAOGuo-xiang,GUANQuan-long(CollegeofInformationScienceandTechnology,JinnanUniversity,Guangzhou510632,China)[Abstract]Thispaperproposesamulti—noderemoveddynamicalgorithmbasedonroutingShortestPathTree(SPT).ThealgorithmestablishesanSPTupdatequeuetopreserveallthedescendentnodesofremovednodes;deletesnodesthatneededtoberemovedandtheirdescendentnodesfromoriginalSPT;,.[KeywordsIshortestpath;dynamicupdate;routingalgorithm;multi—nodeD0I:—,人们迫切希望得到高速网络进行信息交换,,如OSPF和Is—Is,每一个路由器都以自己为根生成一棵最短路径树,,当网络拓扑结构改变时,,高效的最短路径树(ShortestPathTree,SPT)更新算法将大大减少路由器的计算时间,:静态算法并没有借助旧SPT的有效信息而重新计算SPT,如Dijkstra;动态算法在旧SPT的基础上,只更新需要更新的节点,,,[1】的算法对链路权值的增加和减少分进行分类处理,其计算复杂度与静态方法相比得到减少,,文献【2—3][4—6】,[7】给出了网络节点增加或删除的解决方法,但在处理多个网络节点删除时,,本文提出一种基于路由最短路径树的多节点删除动态算法(Multi—nodeRemovedDynamicAlgorithmofShortestPathTree,MRDA—SPT).在CD—pletelyDynamicofShortestPathTree)t】算法中,当多个网络节点被删除时,先将这些节点分成2组,将其中一个节点放在第2组,,在I13的SPT中删除本组的节点并更新其子孙节点,生成临时SPT,然后再从第1组分出一个节点放在第2组,继续进行处理,直至第1