Abstract:

Computation of the shortest path between two nodes in communication networks is the basis of the link state routing protocol. Based on the study on the present dynamic SPT algorithms, we propose a new completely dynamic SPT algorithm (DSPTID) for handling network topology changing. This algorithm establishes an SPT update queue and pays attention only to the changes of nodes and edges by making use of information provided by the existing SPT, which can achieve incremental update. When the topology of the network changes, the increase or decrease of edge weights can be processed by the DSPTID algorithm. The analysis of algorithm complexity and simulation results show that the DSPTID requires less update of nodes and has higher efficiency. 

Key words: shortest path;SPF algorithm;dynamic update;routing protocol