CAPACITY ASSIGNMENT IN COMPUTER-COMMUNICATION NETWORKS WITH UNRELIABLE LINKS

This paper considers the problem of selecting the optimum capacities o f the links in a computer communication network which employs unreliab le links. Given the nodes, links, link probabilities, grade of service and cost functions of the network, the objective of this problem is t o find the optimum link capacities that minimize the network design co st, subject to the constraint equation involving the grade of service. This is essentially a combinatorial optimization problem. A general m ethematical model for this problem is formulated and a set of feasible solutions is obtained using Lagrangean relaxation and subgradient opt imization techniques. A simulation study has been performed to verify the model, and favourable results obtained for a variety of nontrivial networks.