On achieving optimal survivable routing for shared protection in survivable next-generation Internet

This paper proposes a suite of approaches to solve the survivable routing problem with shared protection. We first define in mathematics the maximum extent of resource sharing for a protection path given the corresponding working path according to the current network link-state. Then the problem of solving the least-cost Working & protection path-pair (in terms of the sum of the cost) is formulated into an Integer Linear Programming process. Due to the dependency of the protection path on its working path, however, I the formulation is not scalable with the network size, and takes an: extra effort to solve. Therefore, we introduce two heuristic algorithms, called Iterative Two-Step-Approach (ITSA) & Maximum Likelihood Relaxation (MLR), which aim to explore the approximating optimal solutions with less computation time. We evaluate the performance of the proposed schemes, and make a comparison with some reported counterparts. The simulation results show that the ITSA scheme, with a properly defined tolerance to optimality, can achieve the best performance at the expense of more computation time. On the other hand, MLR delivers a compromise between computation efficiency performance.