An efficient algorithm for dynamic shortest path tree update in network routing

Bin Xiao, Jiannong Cao, Zili Shao, Edwin H.M. Sha

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)499-510
Number of pages12
JournalJournal of Communications and Networks
Volume9
Issue number4
DOIs
Publication statusPublished - 1 Jan 2007

Keywords

  • Dynamic update
  • Network routing
  • Open shortest path first (OSPF)
  • Shortest path tree (SPT)

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this