Minimum dynamic update for shortest path tree construction

Shortest path tree (SPT) computation is the major overhead for routers using any link-state routing protocols including the most widely used OSPF and IS-IS. Changes of link states are nowadays commonly occurred. It is not efficient and stable for network routing to use traditional static SPT algorithms to recompute the whole SPT whenever a change happens. In this paper, we present new dynamic algorithms to compute and update the SPT with the minimum computational overhead. And routing stability is achieved by having the minimum changes in the topology of an existing SPT when some link states are changed. To the authors' knowledge, our algorithms outperform the best existing ones in the literatures.