Optimal Joint Syntheses of Base and Spare Telecommunication Networks

A telecommunication network is survivable if, following an arc failure, the interrupted traffic ca be redirected through the network via existing excess capactiy. The standard survivability problem consists in finding the least cost investistment in spare capacity to allow rerouting of a given base traffic. In this paper we consider the more involved problem of simultaneously designing the base traffic and the spare capacity investment. If the investment costs are linear, the problem can be formulated as a large scale structured linear program that we solve using different decomposition techniques, including the analytic center cutting plane method. The global analysis is performed under the assumption of local rerouting of the traffic, i.e., the interrupted traffic creates a local demand between the end points of the broken edge. More sophistificated telecommunication network management allows to break down the interrupted traffic into its individual demand components. We do not treat the simultaneous design of the base traffic and the spare capacity under a global rerouting strategy. We propose a two-step procedure. We determine firstthe base traffic and the spare capacity under the local rerouting strategy. We then compute the necessary spare capacity to secure the base traffic under the global rerouting strategy. Our solution technique are tested on a set of realistic problem