Optimal design of centralized computer networks

Abstract

Abstract Major design problems for centralized computer networks are link layout and capacity assignment. The objective is to select link locations and capacities so that the average time delay required to transmit a message from any node to the central node does not exceed a specified maximum. The design problem is to find the least cost system which satisfies the time delay constraints for given levels of traffic. In this paper, we describe an algorithm to select globally optimum link capacities for specified tree structures. We also give a heuristic method for finding low cost tree structures. The methods have been programmed and are capable of handling networks with thousands of nodes. In addition, they can consider any finite set of link capacities with an arbitrary cost structure and do not depend on the mathematical model used to calculate average time delay.