Topological expansion of multiple-ring metropolitan area networks

This paper presents a mixed 0-1 linear programming model for the metropolit an area network (MAN) expansion problem. The model includes the location of new switch sites, the update of the configuration of the switches (with re spect to port and shelf types), the update of the access network, and the e xpansion of the backbone (core) network. In addition, we consider that seve ral technologies (e.g., frame relay and asynchronous transfer mode) and rat es (e.g., OC-3 and OC-12) may be used in the access network. A multiple-rin g topology is chosen for the backbone network since it is sparse, therefore not too expensive, while providing protection against single-link or switc h failure. To find a good solution, we propose an initial heuristic that pr ovides a starting solution and a tabu-based heuristic to improve the soluti on. Finally, we present an illustrative example of a MAN design with its su ccessive expansions, followed by a systematic set of experiments designed t o assess the performance of the proposed algorithms. (C) 2000 John Wiley & Sons, Inc.