Failure resilience is one of the desired properties in communication networks. A lot of schemes have been proposed to deal with the failure in optical layers, however, most existing protection schemes consider single link failures only. This is not realistic because it implies a dependency between link failures. Our algorithm aims to break this constraint and develop a new protection scheme for a more general model of independent link failures.
The problem can be formulated as follows: for a given primary path, find a backup path with minimum cost in terms of reserved bandwidth while providing a hard constraint on the protection success rate. We first model the problem using integer linear programming. Then we propose an approximation algorithm that can reduce the communication and computation overhead while guaranteeing the hard constraint on the protection success rate.
In our preliminary experiments, we investigate the performance of our algorithm in a network with 78 nodes and 122 links. The network topology is obtained from AT&T that is used in the ROLEX simulation. We evaluate the performance with respect to protection success rate, lightpath blocking rate, and wavelength usage ratio under various link failure rates and target protection success rates. Preliminary results show that our algorithm can always guarantee the target protection rate with a high bandwidth utilization rate. In addition, we compare our algorithm with the exclusive path protection and shared path protection schemes. Our algorithm can achieve a lower request blocking ratio and more efficient bandwidth usage while meeting the requirement of the pre-determined target protection success rate.