The design of centralized networks with reliability and availability constraints

We present a heuristic algorithm for the design of a communications network that consists of a central computer and geographically dispersed locations that communicate with the computer. The algorithm determines the layout of the links and assigns appropriate transmission facilities. The algorithm, based on the work of Frank, offers the following new features: (1) constraints on the availability and reliability of the network as well as on the expected delay; (2) the option to deploy duplicate-line links for higher availability; (3) the choice of a star or a minimum spanning tree layout for the initial solution. Sample problems are shown to illustrate the impact of the new features. In particular, we found that the additional constraints yielded networks with significantly improved performance at a moderate increase in cost.