An optimal spare-capacity assignment model for survivable networks with hop limits

Abstract

The paper presents a new algorithm for spare-capacity assignment in survivable networks which use cross-connect systems as transmission hubs. The algorithm minimises total cost of spare capacity for required levels of network restoration following a single link failure (e.g. fibre cut) and limits the restoration routes to any predetermined hop limit. The algorithm is composed of two parts: Part 1 relies on a linear programming (LP) formulation (min-max) from which a lower bound solution is found; Part 2 rounds up the solution of Part 1 and uses a series of related LP schemes (max-flow), aimed at tightening the rounded-up assignment to a practical optimal solution which also supplies optimal restoration routes and capacities. For moderate networks an integer programming formulation of Part 1 can be used to obtain an optimal solution. A network example is analysed to illustrate the algorithm developed and to demonstrate its superiority over other schemes published in this area. In addition, a valuable trade-off between spare capacity and hop limit is presented.