Efficient Multi-Link Failure Localization Schemes in All-Optical Networks

Link failure localization has been an important and challenging problem for all-optical networks. The most general monitoring structure, called m-trail, is a light-path into which optical signals are launched and monitored. How to minimize the number of required m-trails is critical to the expense of this technique. Existing solutions are limited to localizing single link failure or handling only small networks. Moreover, some practical constraints, like lacking of knowledge of the failure quantity, are ignored. To overcome these limitations is prospective but quite challenging. To this end, we provide novel theoretical solution frameworks toward the multi-failure localization problem. On one hand, for small dense networks, we provide a tree-decomposition based algorithm; on the other hand, a random walk based localized algorithm for large scale sparse networks is proposed. In addition, we further adapt these two algorithms to cope with three practical constraints. Theoretical analysis and simulation results are included to prove the correctness and efficiency of the proposed schemes.