A new approach to the joint selection of primary and secondary routes in a network with unreliable components is presented. The mathematical model captures the changes in the operational characteristics of the network as it adapts to failures. Lagrangian relaxation and subgradient optimization techniques are used to obtain good heuristic solutions to the problem, as well as lower bounds to be used as benchmarks against which the quality of the solution is assessed. Results of numerical experiments are reported, and directions for further enhancements of the model are discussed. >

The combined problem of selecting a primary route for each communicating pair and a capacity value for each link in computer communication networks is considered. The network topology and traffic characteristics are given: a set of candidate routes and of candidate capacities for each link are also available. The goal is to obtain the least costly feasible design where the costs include both capacity and queuing components. Lagrangean relaxation and subgradient optimization techniques were used to obtain verifiable solutions to the problem. The method was tested on several topologies, and in all cases good feasible solutions, as well as tight lower bounds, were obtained. The model can be generalized to deal with different classes of customers, characterized by different priorities, message lengths, and/or delay requirements.>