PERFORMANCE-CHARACTERISTICS OF A LOAD BALANCING ALGORITHM

The behavior of a graph coloring-based, distributed load balancing alg orithm for a network of processors is evaluated in terms of the averag e response time of the system. A fundamental correspondence between av erage response time and Euclidean system distance (a measure of load i mbalance) is analytically demonstrated. This relationship leads to the proposal of tools intended to be used in the analysis of load balanci ng methods. Simulation studies were conducted and are found to support the theoretical results. (C) 1995 Academic Press, Inc.