Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23126
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.
URI: http://hdl.handle.net/10397/23126
ISSN: 1229-2370
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

7
Citations as of Apr 11, 2016

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Aug 15, 2017

Page view(s)

40
Last Week
5
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check



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