Groupe d’études et de recherche en analyse des décisions


On the Design Problem of Multitechnology Networks


In this article we propose a model for the topological design problem of multitechnology networks that includes the location of switches and their port configuration, the design of an access network (with single and double access links) and a backbone network. The model specifically takes into account different types of modular switches where each type is characterized by its cost, its capacity in terms of the number of slots, and by its switch fabric capacity. The multitechnology qualifier stems from the fact that several technologies and rates can be used in the access network. The proposed model is of the integer-programming variety, and in order to find a good solution, we propose a starting heuristic that provides an initial solution and the tabu-search algorithm to improve the solution. Lower bounds are proposed and used to assess the performance of the tabu-based approach. Numerical results for randomly generated problems with up to 500~clients and 50~potential switch sites are presented. The tabu-search algorithm produced solutions that were, on average, within 2.11% of the best lower bound.

, 20 pages

Ce cahier a été révisé en mai 2001