Dynamic update of shortest path tree in OSPF

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

9 Citations (Scopus)

Abstract

The Shortest Path Tree (SPT) construction is a critical issue to the high performance routing in an interior network using link state protocols, such as Open Shortest Path First (OSPF) and IS-IS. In this paper, we propose a new efficient algorithm for dynamic SPT update to avoid the disadvantages (e.g. redundant computation) caused by static SPT update algorithms. The new algorithm is based on the understanding of the update procedure to reduce redundancy. Only significantly elements that contribute to the construction of new SPT from the old one will be focused on. The efficiency of our algorithm is improved because it only pay attention to the edges really count for the update process. The running time for the proposed algorithm is maximum reduced, which is shown through experimental results. Furthermore, our algorithm can be easily generalized to solve the SPT updating problem in a graph with negative weight edges and applied to the scenario of multiple edge weight changes.
Original languageEnglish
Title of host publicationProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Pages18-23
Number of pages6
Publication statusPublished - 16 Aug 2004
EventProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, Hong Kong
Duration: 10 May 200412 May 2004

Conference

ConferenceProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
CountryHong Kong
CityHong Kong
Period10/05/0412/05/04

ASJC Scopus subject areas

  • Computer Science(all)

Cite this