Topological Design of Two-Level Telecommunication Networks with Modular Switches

Steven Chamberland (), Brunilde Sansò () and Odile Marcotte ()
Additional contact information
Steven Chamberland: CRT and Department of Electrical Engineering, École de Technologie Supérieure, 1100, Notre-Dame Ouest, Montréal (Québec), Canada H3C 1K3
Brunilde Sansò: GERAD and Department of Electrical Engineering and Computer Engineering, École Polytechnique de Montréal, C.P. 6079 Succ. Centre-Ville, Montréal (Québec), Canada H3C 3A7
Odile Marcotte: GERAD and Department of Computer Science, Université du Québec à Montréal, C.P. 8888 Succ. Centre-Ville, Montréal, (Québec), Canada H3C 3P8

Operations Research, 2000, vol. 48, issue 5, 745-760

Abstract: In this article we propose a mixed 0-1 linear programming model for the topological network design problem with modular switches such as the ones that will be used in asynchronous transfer mode (ATM) frame relay and other broadband networks. The model includes the location of switches, their configuration with respect to ports and multiplexers, the design of an access network with a star topology, and a backbone network with a fixed topology (ring or tree). To obtain a solution, we propose a greedy heuristic that provides a good starting solution, and a tabu search heuristic to improve the solution. Finally, we present an example of the application of the heuristics and results for a set of randomly generated problems with up to 500 users and 30 potential switch sites. For the hundreds of problems generated, the tabu algorithm produced solutions that were, on average, within 1.5% of the optimal solution, and in the worst case within 4.95% of the optimal solution.

Keywords: Communications:; topological; network; design (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.5.745.12412 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:5:p:745-760

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().