ANALYSIS OF SIMPLE ALGORITHMS FOR DYNAMIC LOAD BALANCING

The principle of load balancing is examined for dynamic resource alloc ation subject to certain constraints. The emphasis is on the performan ce of simple allocation strategies which can be implemented on-line. E ither finite capacity constraints on resources or migration of load ca n be incorporated into the setup. The load balancing problem is formul ated as a stochastic optimal control problem. Variants of a ''Least Lo ad Routing'' policy are shown to lead to a fluid type limit and to be asymptotically optimal.