A Methodology for Topological Design of Computer Communication Networks under Link Reliability Constraints

Abstract

This paper describes a method to design a cost effective computer communication network which employs unreliable links. The problem of selecting a capacity value for each link in a computer communication network is considered when different links have different reliabilities. The network topology and the total capacity of the network are given; a set of reliability values for the candidate links and the expected grade of service from the network are also available. The goal is to obtain the least costly feasible design where costs include both the link capacity and the link reliability. We present a general mathematical model for this problem and formulate the relevant constraint equations. The model is an improvement over our earlier work. Next, Lagrangean relaxation and subgradient optimization techniques are used to obtain an optimum solution for the model. The methodology is tested on several topologies, and, in all cases, good feasible solutions as well as tight lower bounds are obtained.