Highly efficient spare capacity planning for generalized link restoration

We consider the problem of spare capacity allocation in mesh networks for link restoration. Only single link failures are considered and restored traffic is not split across multiple paths. In our model, links that are not part of the original transport network can also be used for restoration. This model, which is a generalized version, is different from the traditional model studied in literature. We present two heuristics to solve this problem and compare their performance with known lower bounds and the optimal solution. In numerous simulation experiments on randomly generated graphs containing up to 100 nodes, the heuristics often produced solutions within 3% of the lower bound for sparse graphs. The Integer Linear Programming solutions suggest that the heuristic solutions are closer to optimal than indicated by the deviation from the lower bounds. The results are optimal or near optimal (within 0.5% of the optimum values) for small graphs containing up to 8 nodes and 18 edges.