text: Single node failures represent more than 85 of all node failures in the today's large communication networks 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 failures by suppressing the failure (instead of advertising it across the network), and routing messages to the destination via alternate paths that do not use the failed node. We compare our solution to that of Ref. [11] wherein the authors have presented a "Failure Insensitive Routing" protocol as 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.
  @cite_4: The increasing proportion of data traffic being carried in public networks is necessitating tractable and scalable algorithms in the design of ATM networks. In particular, the design of routing tables for ATM networks operated under the interim inter-switch signalling protocol (IISP) requires a significant amount of manual work in order to design and implement the underlying static routing tables that enable end-to-end connectivity as the network grows. This paper presents a scalable algorithm that generates IISP routing table entries such that no loops are created and so that connectivity is maintained between all origin destination nodes under single-link failures. The algorithm generates shortest (i.e., lowest-cost) primary and alternate paths for any single-link failure scenario, while also demonstrating that at least one such solution can be found for any network graph devoid of bridges. Note that re-routing for single-link failures is considered adequate when sufficient protection is provided at the lower network layers. The algorithm has been fully implemented in a practical software tool, with execution time being a polynomial function of the network complexity.
  @cite_7: As the Internet becomes the critical information infrastructure for both personal and business applications, survivable routing protocols need to be designed that maintain the performance of those services in the presence of failures. This paper examines the survivability of interdoamin routing protocols in the presence of routing failure events, and provides a backup route aware routing protocol that performs non-stop routing in the presence of failures. We demonstrate through simulation its effectiveness in preventing packet losses during transient routing failures.
  @cite_8: We investigate the single link failure recovery problem and its application to the alternate path routing problem for ATM networks, and the k-replacement edges for each edge of a minimum cost spanning tree. Specifically, given a 2-connected graph G, a specified node s, and a shortest paths tree Ts = e1, e2, . . . , eni1 of s, where ei = (xi, yi) and xi = parentTs(yi), find a shortest path from yi to s in the graph G for 1 · i · n i 1. We present an O(m + n log n) time algorithm for this problem and a linear time algorithm for the case when all weights are equal. When the edge weights are integers, we present an algorithm that takes O(m + Tsort(n)) time, where Tsort(n) is the time required to sort n integers. We establish a lower bound of ­(min(m p n, n 2 )) for the directed version of our problem under the path comparison model, where Ts is the shortest paths destination tree of s. We show that any solution to the single link recovery problem can be adapted to solve the alternate path routing problem in ATM networks. Our technique for the single link failure recovery problem is adapted to find the k-replacement edges for the tree edges of a minimum cost spanning tree in O(m + n log n) time.
  @cite_9: Dealing with network failures effectively is a major operational challenge for Internet service providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network-wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing (FIR). The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we prove that when no more than one link failure notification is suppressed, FIR always finds a loop-free path to a destination if one such path exists. We also formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF.
  @cite_0: With the emergence of voice over IP and other real-time business applications, there is a growing demand for an IP network with high service availability. Unfortunately, in today's Internet, transient failures occur frequently due to faulty interfaces, router crashes, etc., and current IP networks lack the resiliency needed to provide high availability. To enhance availability, we proposed failure inferencing based fast rerouting (FIFR) approach that exploits the existence of a forwarding table per line-card, for lookup efficiency in current routers, to provide fast rerouting similar to MPLS, while adhering to the destination-based forwarding paradigm. In our previous work, we have shown that the FIFR approach can deal with single link failures. In this paper, we extend the FIFR approach to ensure loop-free packet delivery in case of single router failures also, thus mitigating the impact of many scenarios of failures. We demonstrate that the proposed approach not only provides high service availability but also incurs minimal routing overhead.
summary: One popular approach of tackling the issues related to transient failures of network elements is that of using proactive recovery schemes . These schemes typically work by precomputing alternate paths at the network setup time for the failure scenarios, and then using these alternate paths to re-route the traffic when the failure actually occurs. Also, the information of the failure is suppressed in the hope that it is a transient failure. The local rerouting based solutions proposed in @cite_8 @cite_9 @cite_4 @cite_7 @cite_0 fall into this category.