A Multiple-Link Failures Enumeration Approach for Availability Analysis on Partially Disjoint Paths

Abstract:
Optical networks provide huge amounts of bandwidths to support services that demand high data transfer rates. However, these services also need to meet high availability requirements which are typically threatened by link failures. Availability can be increased by enabling multiple paths to route the service through the network by means of either protection and/or restoration schemes. In this context, efficient methods for computing the availability of a service than can be routed over multiple paths are needed. In particular, these methods need to consider that paths may not necessarily be fully disjoint as some links among them may be shared. As long as the required service availability can be met, partially disjoint paths can reduce cost as a single optical channel (wavelength) can be used on shared links based on split and select schemes. In this paper, a new method is proposed for computing the service availability on scenarios with multiple-link failures based on the enumeration of these scenarios. In particular, we demonstrate that the amount of scenarios can be reduced to speedup availability computation times, which introduces a bounded error on the results. This method is illustrated in the context of the availability aware routing problem, proposing both an ILP model and an heuristic to select the routing paths that can meet a target service availability at a minimum cost in terms of required links. Numerical results show that partially disjoint paths can offer cost-efficient solutions to this problem. Finally, a comparison on the computing times of the proposed method is analyzed, demonstrating that it can run up to one order of magnitude faster than a traditional method based on the factorization algorithm.