Migration Algorithms for Automated Load Balancing

N. Widell (Sweden)


Load balancing, resource allocation, dis tributed computing


As distributed systems continue to evolve, automatic re source management is becoming more and more impor tant. The resource management system must be able to dynamically handle large heterogeneous systems in a way that gives good performanceand resource utilization. In the performance context, allocating software modules to nodes in an efficient way is of high interest. This paper considers the problem of allocating software modules to processing nodes in an automatic dynamic manner using module mi gration algorithms. The module allocation problem is NP complete and many heuristics have been proposed. How ever, in systems where the workload changes over time, it may be infeasible to update module allocation often enough to handle changes in workload. This paper presents the Match-maker algorithm that performs load balancing by pairing overloaded nodes with under-loaded ones, initiat ing module migration within the pair. The paper presents a load balancing optimization problem, and uses the bench mark problem to evaluate the algorithm. In addition, the Match-maker algorithm is compared with other previously described algorithms for module migration. The Match maker algorithm is found to be fast and efficient in reducing load imbalance in distributed systems, especially for large systems.

Important Links:

Go Back