Optimal load balancing and scheduling in a distributed computer system
Keith W. Ross, David D. W. Yao · Journal of the ACM · 1991
A broadcast communication network that interconnects multiple hosts N considered.A job generated by a host is either generic, m which case It can be processed at any of the hosts in the network, or dedicated, m which case it must be processed at the host from which it originates.It is assumed that each host can generate several types of dedicated jobs, where each type imposes a constraint on its average response time.The optimal design objective is twofold: First, to redistribute the generic jobs among the host computers in order to minimize the average response time, which shall be referred to as the load-balancing problem; second, for each host computer, to design a control that schedules the dedicated and the generic Jobs so that the response-time constraints are met for each of the dedicated traffic types.Despite its complexity, the model described above has some attractive features.Specifically, for a given allocation of the generic traffic, the scheduhng problem at each host can be solved as a polymatroid optimization problem.The underlying polymatroid structure leads to an efficient algorithm to determine, as a function of the offered load of generic traffic, the average delay of the generic jobs at any given host.Further analysis reveals that the delay functions at each of the hosts are convex and increasing.Therefore, an allocation algorlthm can be employed to solve the system-level load-balancing problem.An example is provided mdlcating that a substantial improvement m performance can be obtained by incorporating scheduling into the load-balancing procedure.