CAPACITY AND FLOW ASSIGNMENTS IN LARGE COMPUTER NETWORKS

Abstract

This paper presents a model and the corresponding solution method for the problem of jointly selecting a set of primary routes and assigning capacities to the links in a computer communication network. The network topology and the traffic characteristics are known; a set of candidate routes for each communicating pair of nodes, and a set of candidate capacities for each link are also given. The goal is to obtain the least costly feasible design, where the costs include both capacity and queuing components. The resulting combinatorial optimization problem is solved using Lagrangean relaxation and subgradient optimization techniques. The method was tested on several topologies, and in all cases good feasible solutions, as well as tight lower bounds were obtained.