|
Computer Sciences Seminar Shortest Path Tree Update for Network Routing
Bin Xiao Abstract Algorithms for computing the Shortest Path Tree (SPT) have been extensively studied for decades for link state protocols, such as the Open Shortest Path First (OSPF) and IS-IS routing protocols. However, the traditional static algorithm, such as the Dijkstra algorithm, is very inefficient for updating SPT when only a small number of links are changed in a network. By using this static algorithm, every router in the network area will recompute the SPT whenever there is a link state change. The re-computation of each router may cause routing table instability by making unnecessary changes in an existing SPT, because there may have multiple shortest paths from a source node to a destination in a network area. This talk therefore explores the dynamic algorithms for SPT update. Besides the research for unicast routing protocol in the network, efficient SPT construction is also related to many other research areas, such as network multicast routing protocols, ad hoc mobile networks, transportation models, robot motion planning, VLSI design etc. In this talk, a weight-difference graph G* is introduced to reveal the underlying properties of SPT update. Based on this fundamental understanding, new, efficient dynamic algorithms are proposed for updating SPT. During the update process, only significant elements that contribute to the construction of new SPT from the old one will be focused on. These algorithms require the least computation time as well as the number of updates in routing table among the dynamic methods in literature. This talk presents a formal analysis of algorithm complexity (the best known) and the experimental result. Furthermore, such algorithms can be easily generalized to solve the SPT updating problem in a graph with negative edges, and to deal with edge/node deletion and insertion in a network topology. Bio |