Performance of Global Load Balancing by Local Adjustment

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1398-1414
Number of pages17
JournalIEEE Transactions on Information Theory
Volume36
Issue number6
DOIs
StatePublished - Nov 1990

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Performance of Global Load Balancing by Local Adjustment'. Together they form a unique fingerprint.

  • Cite this