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

Link-state routing protocols, such as OSPF and IS-IS, are widely used in the Internet nowadays. In link-state routing protocols, global network topology is first collected at each node. A shortest path tree (SPT) is then constructed by applying the 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. recently 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, Narvaez' approach 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. In this paper, 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.