An extended fault-tolerant link-state routing protocol in the internet

J. Wu, X. Lin, Jiannong Cao

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

2 Citations (Scopus)


Link-state routing protocols, such as OSPF and IS-IS, are widely used on the Internet. In link-state routing protocols, global network topology is first collected at each node. A shortest path tree (SPT) is then constructed by applying Dijkstra's shortest path algorithm at each node. Link-state protocols normally require the flooding of new information to the entire (sub)network after changes in any link state (including link faults). Narvaez et al. (2000) proposed a fault-tolerant link-state routing protocol without flooding. The idea is to construct a shortest restoration path for each uni-directional link fault. Faulty link information is distributed only to the nodes in the restoration path and only one restoration path is constructed. It is shown that this approach is loop-free. However, the approach of Narvaez et al. is inefficient when a link failure is bi-directional, because a restoration path is uni-directional and routing tables of nodes in the path are partially updated. In addition, two restoration paths may be generated for each bi-directional link fault. We extend the Narvaez protocol to efficiently handle a bi-directional link fault by making the restoration path bi-directional. Several desirable properties of the proposed extended routing protocol are also explored.
Original languageEnglish
Title of host publication[Missing Source Name from PIRA]
Number of pages7
ISBN (Print)0769511538
Publication statusPublished - 2001
EventInternational Conference on Parallel and Distributed Systems [ICPADS] -
Duration: 1 Jan 2001 → …

Publication series

NameInternational Conference on Parallel and Distributed Systems. Proceedings
ISSN (Print)1521-9097


ConferenceInternational Conference on Parallel and Distributed Systems [ICPADS]
Period1/01/01 → …


  • Fault tolerant computing, telecommunication network routing, protocols, Internet

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'An extended fault-tolerant link-state routing protocol in the internet'. Together they form a unique fingerprint.

Cite this