ALCOMFT-TR-03-151

Robert Elsässer and Burkhard Monien
Diffusion Load Balancing in Static and Dynamic Networks
Paderborn. Work package 2. December 2003.

Abstract: The problem of balancing dynamically generated work load among the processors of a parallel or distributed system occurs in a wide range of applications. Several load balancing methods have been developed and analyzed. In this paper, we consider the load balancing method called diffusion, which belongs to the class of nearest neighbor load balancing algorithms.

First, we present several diffusion schemes, we describe their convergence rates, and analyze the balancing flow computed by these schemes. Due to the local behavior of diffusion, these schemes are especially well-suited for large networks. Furthermore, we show that simple schemes can be applied directly to dynamic networks, too. We also present a somehow related load balancing algorithm, which solves the so-called token distribution problem on static and dynamic networks, and compare the behavior of this algorithm with the behavior of diffusion. We conclude with a discussion about new strategies which improve the performance of simple diffusion schemes on static networks.

Postscript file: ALCOMFT-TR-03-151.ps.gz (105 kb).