LP-Based Heuristic Algorithms for Interconnecting Token Rings via Source Routing Bridges

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.