Dynamic shortest path tree update for multiple link state decrements
Bin Xiao, Jiannong Cao, Qingfeng Zhuge, Zili Shao, Edwin H.‐M. Sha · 2005
Previous approaches for the shortest path tree (SPT) dynamic update have mainly focused on the case of one link state change. Little work has been done on the problem of deriving a new SPT based on its old one for multiple link state decrements in a network that applies link-state routing protocols. The complexity of this problem comes from there being no accurate boundary of nodes to be updated in an updating process and that multiple decrements can be accumulated. Two dynamic algorithms (MaxR, MinD) are proposed to reduce the times for node updating. Compared with other algorithms for the SPT update of multiple edge weight decrements, our algorithms yield fewer times for node updates during the dynamic update process. Such an achievement is attained by the mechanism of part node updating in a branch on the SPT after a particular node selection from a built node list. Simulation results are given to show our improvements.