An Algorithm for Resource Allocation Requiring Low Overhead Communication

A heuristic algorithm for allocating resource units to sites in a distributed system is presented. Starting with a given allocation of sites, the algorithm performs a series of optimizations involving pairs of sites in an attempt to improve the worst pair-wise imbalance present in the system; termination occurs when no further improvement is possible. After outlining the general form of the algorithm, which effectively defines an entire family of algorithms, we present theoretical results that speak to the performance of the algorithm as measured in the number of optimizations that can be done, the amount of control communication required and the worst case imbalance of the resulting allocation. Subsequently, two particular algorithms in the family are given and the results of a simulation study of their performance is presented