Localizing link failures in all-optical networks using monitoring tours

In this paper, we introduce the concept of monitoring tours (m-tours) to uniquely localize all possible failures up to k links in 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. An m-tour is different from other existing schemes such as m-cycle and m-trail, which traverse a link at most once. Closed (open) m-tours start and terminate at the same (distinct) monitor location(s). Each tour is constructed such that any shared risk linked group (SRLG) failure results in the failure of a unique combination of closed and open m-tours. We prove that k-edge connectivity is a sufficient condition to localize all SRLG failures with up to k-link failures when only one monitoring station is employed. We introduce an integer linear program (ILP) and a greedy scheme to find the monitoring locations to uniquely localize any SRLG failures with up to k links. We provide a heuristic scheme to compute m-tours for a given network. 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 compared to previously developed techniques.