Diverse routing for shared protection in survivable optical networks

This paper provides a suite of approaches to solving the survivable routing problem with shared protection. The problem diverse solving the least-cost working and protection path-pair (in terms of the sum of the cost) is formulated into Integer Linear Programming. We also introduce two heuristic algorithms, called Iterative Two-Step-Approach (ITSA) and Maximum Likelihood Relaxation (MLR), which aim to finding the approximating optimal solution within a limited amount of computation time. We examine the performance of the proposed schemes and make a comparison with some reported counterparts. It is observed that the ITSA scheme with a properly defined tolerance to the optimality can achieve the best performance at the expense of much longer computation time. MLR can provide an ultra-fast path selection process, which behaves as a good tradeoff between computation efficiency and performance.