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.
Published December 1997 , 30 pages
This cahier was revised in June 2000