An Algorithm for Designing Survivable Networks

Abstract

In this paper, we consider the design of telecommunications networks using high-capacity transport facilities that can survive under a single-link failure scenario. The model considers three priority levels for circuits: high, normal, and low. Each high-priority circuit is assigned a primary path and a link-disjoint alternate path. The model ensures that all high-priority circuits can be rerouted in case of a link failure by preempting low-priority circuits if necessary. The problem is formulated as an integer program solved by a heuristic Lagrangean-relaxation technique and a partial branch-and-bound approach.