Algorithms for designing survivable LAN-interconnection networks using transparent bridges

The performance and reliability of information systems built on a collection of interconnected Local Area Networks (LANs) are closely tied to the configuration of the underlying network topology. One way of interconnecting LANs is by using IEEE 802.1D standard bridges (a.k.a. transparent bridges). Transparent bridges use a spanning-tree on the physical network for message routing which is determined based on user-supplied parameters such as bridge IDs and the path cost assigned to each bridge port.;This thesis presents a new mathematical model for designing a survivable LAN-interconnection network which exactly incorporates the IEEE 802.1D standard algorithm for message routing. We model this capacitated survivable network design problem as an integer linear program. We present a relaxation of this model which can be used to generate lower bounds on the optimal value. Both models are NP-hard.;A solution procedure is developed to find both upper and lower bounds on the cost of an optimal network configuration. This procedure includes a tabu search algorithm applied to the original model, and a Lagrangian-dual based algorithm applied to the relaxed model. The latter consists of a subgradient optimization algorithm for solving the Lagrangian dual, and a Lagrangian heuristic that transforms solutions of the Lagrangian relaxation of the relaxed model to feasible solutions for the original problem. The Lagrangian relaxation of the relaxed model is decomposed into several minimum spanning tree problems, several shortest path problems and an uncapacitated two-vertex connected network design problem. The latter is further relaxed to a problem of finding a 1-tree on a complete graph, based on the parsimonious property of two-edge connected network design problems. Both tabu search and Lagrangian heuristic algorithms employ path cost adjustment heuristics and graph-theoretic heuristics (such as Pretzel, Quetzel and Two-Opt heuristics) for the local transformation of two-vertex-connected network-topology solutions.;The performance of each component algorithm is measured under varying traffic conditions through computational experiments. Network topologies obtained under varying traffic conditions are also examined. Finally, a case study is performed on the campus network at The University of Iowa.