Dynamic shortest path tree update for multiple link state decrements

Bin Xiao, Jiannong Cao, Qingfeng Zhuge, Zili Shao, Edwin H M Sha

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

4 Citations (Scopus)


Previous approaches for the Shortest Path Tree (SPT) dynamic update are mainly focused on the case of one link state change. Little work has been done to the problem of deriving a new SPT based on its old one for multiple link state decrements in a network that applies link-state routing protocols. The complexity of this problem comes from that there is no accurate boundary of nodes to be updated in an updating process and that multiple decrements can be accumulated. In this paper, two dynamic algorithms (MaxR, MinD) are proposed to reduce the times for node updating. Compared with other algorithms for the SPT update of multiple edge weight decrements, our algorithms yield less number of times for node updated during the dynamic update process. Such achievement is attained by the mechanism of part nodes updating in a branch on the SPT after a particular node selection from a built node list. Simulation results are given to show our improvements.
Original languageEnglish
Title of host publicationGLOBECOM - IEEE Global Telecommunications Conference
Number of pages5
Publication statusPublished - 1 Dec 2004
EventGLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, United States
Duration: 29 Nov 20043 Dec 2004


ConferenceGLOBECOM'04 - IEEE Global Telecommunications Conference
Country/TerritoryUnited States
CityDallas, TX

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Dynamic shortest path tree update for multiple link state decrements'. Together they form a unique fingerprint.

Cite this