Optimal Static Load Balancing in Distributed Computer Systems

Abstract

A distributed computer system that consists of a set of heterogeneous host computers connected in an arbitrary fashion by a communications network is considered. A general model is developed for such a distributed computer system, in which the host computers and the communications network are represented by product-form queuing networks. In this model, a job may be either processed at the host to which it arrives or transferred to another host. In the latter case, a transferred job incurs a communication delay in addition to the queuing delay at the host on which the job is processed. It is assumed that the decision of transferring a job does not depend on the system state, and hence is static in nature. Performance is optimized by determining the load on each host that minimizes the mean job response time. A nonlinear optimization problem is formulated, and the properties of the optimal solution in the special case where the communication delay does not depend on the source-destination pair is shown. Two efficient algorithms that determine the optimal load on each host computer are presented. The first algorithm, called the parametric-study algorithm, generates the optimal solution as a function of the communication time. This algorithm is suited for the study of the effect of the speed of the communications network on the optimal solution. The second algorithm is a single-point algorithm; it yields the optimal solution for given system parameters. Queuing models of host computers, communications networks, and a numerical example are illustrated. © 1985, ACM. All rights reserved.