Performance of global load balancing of local adjustment

Abstract

A set of M resource locations and a set of a M 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. I. PROBLEM FORMULATION A. Integral Balance Problem ARGE SCALE load balancing problems arise in L many guises. They are encountered, for example, when several tasks are to be shared among several machines in a multiprocessor computer environment, or when traffic must be distributed over the communication links of a communication network. Such problems often call for a hierarchical solution in which a global balancing mechanism operates slowly using coarse, global information, while local balancing mechanisms use only readily available local information to orchestrate quick, local adjustments. In this paper we study a simple model for the problem faced by the local balancing mechanisms, which must typically operate under constraints. The constraints may be determined by a higher level control mechanism, or they may be imposed simply to reduce the cost (due, for example, to communication and storage) associated with shifting resource allocations. Consider, for example, the case of “alternate routing” in a communication network. A station may be assigned 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. This 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. (on a slow time scale) multiple paths to a given destination. Based on current traffic readings (obtained from local information and on a fast time scale) the station allocates its traffic over the set of assigned paths. The question arises as to how well traffic can be controlled if there are, say, c alternate paths for each source-destination pair. This question is very difficult to answer in general. Our problem can be viewed as a very special case in which each path is only two links long and a restricted network topology is assumed. The assignment of radios to stations in a cellular radio system is a special case of alternate routing in networks which is fairly close to the model we consider. A constraint is that radios must be assigned to nearby stations, and the goal is to balance the load among the stations. The main purpose of this paper is to study the performance of global load balancing by local adjustment. Specifically, we investigate how balanced the load is after balancing for a simple model that illustrates some interesting phenomena. For clarity, we will formulate the problem in terms of consumers and resource locations. Consider a set U of consumers and a set V of resource locations, and let M denote the cardinality of V, M = IVI. Suppose that consumer U requires the use of mu units of resource and can use at most Cu,, units from location U . We will be most interested in the case that N u ) , defined by N u ) = { c E V : C,,,, > O), is a small subset of V for each U . Also suppose that there is a load of size b, on resource location c from consumers other than those in U. We refer to (U, V , C) as a network, m as the consumer demand vector, and b as the base load vector. An admissible assignment vector is a vector f , f = ( fu,L: U E U, L‘ E V I , such that 0 sf,,,, 5 Cu, , . The interpretation is that f,,,, denotes the load on resource location LI due to consumer U . An assignment vector f meets the consumer demand if c f,,,, = mu, for U E U , (1) L t V and the total load on resource location U , x ( u ) , is given by X ( U ) = b, + f,,, , for U E V . (2)

Topics

    8 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)