Advanced

Migration algorithms for automated load balancing

Widell, Niklas LU (2004) In Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA
Abstract
As distributed systems continue to evolve, automatic resource 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... (More)
As distributed systems continue to evolve, automatic resource 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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA
editor
Gonzalez, Teofilo
publisher
ACTA Press
external identifiers
  • Scopus:11844253176
ISBN
0-88986-421-7
language
English
LU publication?
yes
id
ddf9e46e-1e89-4a81-bd17-a3ab7e68adbc (old id 532433)
date added to LUP
2007-09-25 14:01:07
date last changed
2016-10-13 04:39:16
@misc{ddf9e46e-1e89-4a81-bd17-a3ab7e68adbc,
  abstract     = {As distributed systems continue to evolve, automatic resource 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.},
  author       = {Widell, Niklas},
  editor       = {Gonzalez, Teofilo},
  isbn         = {0-88986-421-7},
  language     = {eng},
  publisher    = {ARRAY(0x7e0ef20)},
  series       = {Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems : November 9 - 11, 2004, MIT, Cambridge, USA},
  title        = {Migration algorithms for automated load balancing},
  year         = {2004},
}