Scalable techniques for failure recovery and localization

Failure localization and recovery is one of the most important issues in network management to provide continuous connectivity to users. In this dissertation, we develop several algorithms for network failure localization and recovery. First, to achieve fast recovery using resilient multipath routing we introduce the concept of Independent Directed Acyclic Graphs (IDAGs). The algorithm developed in this dissertation: (1) provides multipath routing; (2) utilizes all possible edges; (3) guarantees recovery from single link failure; and (4) achieves all these with at most one bit per packet as overhead when routing is based on destination address and incoming edge.;Secondly, we introduce the concept of monitoring tours to uniquely localize all possible failures up to k links in arbitrary all-optical networks. We establish paths and cycles that can traverse the same link at most twice (forward and backward) and call them m-tours. Each tour is constructed such that any shared risk linked group (SRLG) failure results in the failure of a unique combination of m-tours. We demonstrate the validity of the proposed monitoring method through simulations. We show that our approach using m-tours significantly reduces the number of required monitoring locations and contributes to reducing monitoring cost and network management complexity through these simulation results. Finally, this dissertation studies the problem of uniquely localizing single network element failures involving a link/node using monitoring cycles, paths, and tours. We develop the necessary theories for monitoring single element failures using only one monitoring station and cycles/tours respectively. Through the simulations, we verify the effectiveness of our monitoring algorithms.