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


Topological Expansion of Multiple Ring Metropolitan Area Networks


This paper presents a mixed 0-1 linear programming model for the metropolitan area network (MAN) expansion problem. The model includes the location of new switch sites, the update of the configuration of the switches (with respect to port and shelf types), the update of the access network and the expansion of the backbone (core) network. In addition, we consider that several technologies (e.g., frame relay and asynchronous transfer mode) and rates (e.g., OC-3 and OC-12) may be used in the access network. A multiple ring topology is chosen for the backbone network since it is sparse, therefore not too expensive, while providing protection against single link or switch failure. In order to find a good solution, we propose an initial heuristic that provides a starting solution and a tabu-based heuristic to improve the solution. Finally, we present an illustrative example of a MAN design with its successive expansions, followed by a systematic set of experiments designed to assess the performance of the proposed algorithms.

, 30 pages

Ce cahier a été révisé en juin 2000