Please use this identifier to cite or link to this item:
Title: An efficient algorithm for dynamic shortest path tree update in network routing
Authors: Xiao, B 
Cao, J 
Shao, Z 
Sha, EHM
Keywords: Dynamic update
Network routing
Open shortest path first (OSPF)
Shortest path tree (SPT)
Issue Date: 2007
Source: Journal of communications and networks, 2007, v. 9, no. 4, p. 499-510 How to cite?
Journal: Journal of Communications and Networks 
Abstract: Shortest path tree (SPT) construction is essential in high performance routing in an interior network using link state protocols. When some links have new state values, SPTs may be rebuilt, but the total rebuilding of the SPT in a static way for a large computer network is not only computationally expensive, unnecessary modifications can cause routing table instability. This paper presents a new update algorithm, dynamic shortest path tree (DSPT) that is computationally economical and that maintains the unmodified nodes mostly from an old SPT to a new SPT. The proposed algorithm reduces redundancy using a dynamic update approach where an edge becomes the significant edge when it is extracted from a built edge list Q. The average number of significant edges are identified through probability analysis based on an arbitrary tree structure. An update derived from significant edges is more efficient because the DSPT algorithm neglect most other redundant edges that do not participate in the construction of a new SPT. Our complexity analysis and experimental results show that DSPT is faster than other known methods. It can also be extended to solve the SPT updating problem in a graph with negative weight edges.
ISSN: 1229-2370
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Feb 15, 2019


Last Week
Last month
Citations as of Feb 11, 2019

Page view(s)

Last Week
Last month
Citations as of Feb 11, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.