Browse Prior Art Database

Decentralized Load Balancing Algorithm for Dynamic Computer Networks

IP.com Disclosure Number: IPCOM000122430D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 101K

Publishing Venue

IBM

Related People

Reddy, HN: AUTHOR

Abstract

This article describe a decentralized load balancing algorithm for dynamic computer networks.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Decentralized Load Balancing Algorithm for Dynamic Computer Networks

      This article describe a decentralized load balancing
algorithm for dynamic computer networks.

      Multiprocessor systems as well as computer networks promise a
practical way to speed up solving computation intensive problems.
One of the problems in such networks is the management of computing
resources. Load balancing algorithms are used to achieve equal or
close to equal loading of the nodes in the system so that a speedup
as close to the ideal one as feasible can be obtained.  Load
balancing algorithms, proposed in the past, assume the knowledge of
global state  and configuration information. Consequently, they
result in  excessive communication overhead, out-dated status
information, and heavy demand on local computing resources and, even
more importantly, not being very fault-tolerant.

      In this article, we describe a decentralized load balancing
algorithm which processes at each node only the state information
about a small portion of the network, usually about the immediate
neighborhood of the node, and attempts to achieve global load
balancing by having each node act on its own, partial information.
LOAD BALANCING CRITERION

      A multiprocessor system is an undirected graph G = (N,E), with
N representing the processors and E the bi-directional communication
links between nodes. For any fixed integer H>=1, we define for every
node, n epsilon N, its H-neighborhood N(H,n) to be that set of nodes
which are no more than H hops away. For example, the 1-neighborhood
of node 6 in the rectangular processor grid (see figure below) is
{2,5, 7,10}; the 2-neighborhood of node 6 is
{1,2,3,5,7,8,9,10,11,14}, and so on.

      Our load balancing criterion is a local one: Each node, n,
inspects the loads of all nodes in its H-neighborhood N(H,n) for a
given fixed H>=1.  If the loads differ by more than 1 from each
other, the load balancing criterion is violated, or N(H,n) is
unbalanced; otherwise, N(H,n) is considered balanced. If the load
balancing criterion holds for all nodes, we say the entire computing
system G is balanced.  If the computing system does not satisfy the
load balancing criterion, individual loads on nodes must be
reassigned.
LOAD BALANCING ALGORITHM

      Each nod...