Load balancing in heterogenous distributed systems

In most distributed systems, the work generated at a node is processed there; little sharing of computational resources is provided. In such systems it is possible for some nodes to be heavily loaded while others are lightly loaded, resulting in poor overall system performance. The purpose of load balancing is to improve performance by redistributing the workload among the nodes. In this paper four load balancing techniques are studied by simulations. The study is limited to a class of techniques where the jobs are lined up in a generic queue and sent to a central job dispatcher which allocates the job to a particular processor based upon the following criteria: nondeterministic routing, response time, system time and throughput. We propose an algorithm that reduces the computational complexity of algorithms ensuring minimum system time. Copyright (C) 1996 Elsevier Science Ltd.