Survivable multi-service telecommunication network design: Optimal and heuristic strategies

Abstract

We analyze the problem of providing a minimum cost multi-service network subject to one link failure scenarios. We consider a fully meshed network for which the origin-destination demand is satisfied by using direct or two hop-paths. Flows for any one service are bounded above on any link. We provide a large scale linear programming formulation of this problem which gives the optimal solution. Since solving this model for large networks is impractical an efficient heuristic is proposed and implemented.