Linear programming-based heuristic algorithms for interconnecting token rings via source routing bridges

Linear programming-based heuristic algorithms for interconnecting token rings via source routing bridges

0.00 Avg rating0 Votes
Article ID: iaor20002977
Country: United States
Volume: 6
Issue: 1
Start Page Number: 149
End Page Number: 166
Publication Date: Jan 2000
Journal: Journal of Heuristics
Authors: , ,
Keywords: programming: linear, communications, heuristics
Abstract:

We develop a method to determine the topology of a network that interconnects a number of token rings using source routing bridges. The purpose is to compute a topology that provides low response delays for network users at a minimal cost of bridge installations. We formulate this network design problem as a mixed binary integer linear program. We develop effective heuristic algorithms. The algorithms exploit the topology and routing solutions of the linear programming relaxation in a sophisticated manner which we believe is new in the literature. The model incorporates performance issues, such as network stability, bridge overflow, back pressure effect and broadcast storm, that are specific to the underlying communication technology. By formally incorporating these performance issues, we tighten the model formulation and improve the quality of the LP bound considerably. Computational results are reported for problems with up to 20 token rings and 190 potential bridge locations.

Reviews

Required fields are marked *. Your email address will not be published.