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.
