Performance of Global Load Balancing by Local Adjustment

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.