构造最短路径树的动态算法综述

A Review of Dynamic Algorithms for the Shortest Path Tree Construction:A survey

对于以链路状态(Link state)为路由协议的大规模网络来说,根据网络流量和拓扑结构的变化来快速调整自身路由表的信息,是非常关键的问题。网络中链路状态发生变化有四种情况:链路费用的增加,链路费用的减少,节点失效,新节点的加入。回顾了以往所提出的具有关键意义的动态算法,分析了它们的创新点;其次,指出了相关文献中提出的应对网络拓扑变化的处理算法的不足之处,并提出了综合处理各种情况的思路。

In large scale network, in which routing protocol is based on link state, it is a key problem topromptly update the routing tables in terms of the network flow and its topology. The changes for the linkstate are. the increase in link cost, the decrease in link cost, the inaetive nodes, new nodes added in. Thispaper firstly reviews all the important algorithms and analyzed their innovative point; Secondly, it pointsout the faults in relevant articles which put forward the algorithms to deal with topological change, andwhat＇s more, proposes a new way to deal with the conditions together.