TY - JOUR

T1 - Performance of Global Load Balancing by Local Adjustment

AU - Hajek, Bruce

N1 - Funding Information:
Manuscript received April 26, 1989; revised April 10, 1990. This work was ,upported by the Joint Services Electronics Program under Grant No. N00014-90-5-1270.T his work was presented in part at the Eighteenth Conference on Stochastic Processes and Their Applications, University of Wisconsin, June 1989. The author is with the Coordinated Sciences Laboratory and the Department of Electrical and Computer Engineering, University of Illinois, 1101 W. Springfield Ave., Urbana, IL 61801. IEEE Log Number 9038009.

PY - 1990/11

Y1 - 1990/11

N2 - A set of M resource locations and a set of aM consumers are given. Each consumer requires a specified amount of resource and is constrained to obtain the resource from a specified subset of locations. The problem of assigning consumers to resource locations so as to balance the load among the resource locations as much as possible is considered. It is shown that there are assignments, termed uniformly most balanced assignments, that simultaneously minimize certain symmetric, separable, convex cost functions. The problem of finding such assignments is equivalent to a network flow problem with convex cost. Algorithms of both iterative and combinatorial type are given for computing the assignments. The distribution function of the load at a given location for a uniformly most balanced assignment is studied assuming that the set of locations each consumer can use is random. An asymptotic lower bound on the distribution function is given for M tending to infinity, and an upper bound is given on the probable maximum load. It is shown that there is typically a large set of resource locations that all have the maximum load, and that for large average loads the maximum load is near the average load.

AB - A set of M resource locations and a set of aM consumers are given. Each consumer requires a specified amount of resource and is constrained to obtain the resource from a specified subset of locations. The problem of assigning consumers to resource locations so as to balance the load among the resource locations as much as possible is considered. It is shown that there are assignments, termed uniformly most balanced assignments, that simultaneously minimize certain symmetric, separable, convex cost functions. The problem of finding such assignments is equivalent to a network flow problem with convex cost. Algorithms of both iterative and combinatorial type are given for computing the assignments. The distribution function of the load at a given location for a uniformly most balanced assignment is studied assuming that the set of locations each consumer can use is random. An asymptotic lower bound on the distribution function is given for M tending to infinity, and an upper bound is given on the probable maximum load. It is shown that there is typically a large set of resource locations that all have the maximum load, and that for large average loads the maximum load is near the average load.

UR - http://www.scopus.com/inward/record.url?scp=0025517260&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025517260&partnerID=8YFLogxK

U2 - 10.1109/18.59935

DO - 10.1109/18.59935

M3 - Article

AN - SCOPUS:0025517260

SN - 0018-9448

VL - 36

SP - 1398

EP - 1414

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

ER -