Modelos e algoritmos para problemas de atribuição de capacidade e roteamento em redes de comunicação

Abstract

The joint problem of selecting routing and a capacity for each link in a communication network is considered. We apply an alternative approach for some models that have been addressed for computer networks discrete capacity allocation and routing problems. The network topology and trac characteristics are assumed to be given. The goal is to obtain a feasible solution with minimum total cost, where the total cost include both leasing capacity and congestion costs. Heuristic algorithms withperformance guarantees based on lower bounds and on the separability of the objective function are proposed. A heuristic algorithm is proposed to solve the problem with nonbifurcated routing constraints. An implicit enumeration approach is proposed to solve exactly the capacity expansion problem with two capacity levels for each channel. Experiments were conducted to verify the performance and to conrmthe eciency of the proposed algorithms.