Efficient Algorithms and Routing Protocols for Handling Transient Single Node Failures

A.M. Bhosle and T.F. Gonzalez (USA)


Network Protocols, Node Failure Recovery, Transient Node Failures, Alternate Path Routing.


Single node failures represent more than 85% of all node failures[7] in the today’s large communication net works such as the Internet. Also, these node failures are usually transient. Consequently, having the routing paths globally recomputed does not pay off since the failed nodes recover fairly quickly, and the recomputed routing paths need to be discarded. Instead, we develop algorithms and protocols for dealing with such transient single node fail ures by suppressing the failure (instead of advertising it across the network), and routing messages to the destina tion via alternate paths that do not use the failed node. We compare our solution to that of [11], which also discusses such a proactive recovery scheme for handling transient node failures. We show that our algorithms are faster by an order of magnitude while our paths are equally good. We show via simulation results that our paths are usually within 15% of the optimal for randomly generated graph with 100-1000 nodes.

Important Links:

Go Back