Minimum dynamic update for shortest path tree construction

Bin Xiao, Qingfeng ZhuGe, Edwin H.M. Sha

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationConference Record / IEEE Global Telecommunications Conference
Number of pages5
Publication statusPublished - 1 Dec 2001
Externally publishedYes
EventIEEE Global Telecommunicatins Conference GLOBECOM'01 - San Antonio, TX, United States
Duration: 25 Nov 200129 Nov 2001


ConferenceIEEE Global Telecommunicatins Conference GLOBECOM'01
Country/TerritoryUnited States
CitySan Antonio, TX


  • OSPF
  • Routing
  • Shortest path tree

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Global and Planetary Change

Cite this