Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.