Two strategies for spare capacity placement in mesh restorable networks

Because the problem of optimal spare capacity placement in a mesh-restorable network is NP-hard, the authors consider two heuristic strategies to solve the spare capacity placement problem in a near-optimal way within reasonable time constraints. The spare link placement algorithm (SLPA) is based on the principle of iterative link addition to produce the greatest incremental change in network restorability. SLPA is shown theoretically and experimentally to have polynomial time complexity. The iterated cutsets heuristic (ICH) formulates spare capacity placement as a linear programming problem subject to constraints based on a subset of cutsets of the network. Iteration and heuristic rules are used to develop the constraint set required by ICH. Theoretical time complexities are assessed for both SLPA and ICH. Comparative experimental tests on 36 trial networks are discussed. ICH network designs require slightly less redundant capacity. On average, SLPA placed 5% more spare capacity than ICH