This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Chamberland, S. Articles by Sansò, B. Search for Related Content

On the Design Problem of Multitechnology Networks

CRT and École Polytechnique de Montréal, C.P. 6079, Succ. Centre-ville, Montréal (Québec), H3C 3A7, Canada
GERAD and École Polytechnique de Montréal, C.P. 6079, Succ. Centre-ville, Montréal (Québec), H3C 3A7, Canada
stevenc{at}crt.umontreal.ca
bruni{at}crt.umontreal.ca

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 mutitechnology 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.

Key words: Network Design; Multitechnology Networks; Tabu Search; Access Network; Backbone Network
History: received January 1998; revised May 1999; revised June 2000; revised February 2001; accepted February 2001.