Sharing Jobs Among Independently Owned Processors

Abstract:

In many distributed systems it is possible to share the processing capabilities among the nodes. To accomplish this goal, a number of load balancing algorithms have been proposed in the literature. The purpose of this type of algorithms is to redistribute the system workload with the objective of equalizing the workload at each node. In a network of independently owned processors (e.g., a network of workstations), load balancing schemes cannot consider the whole network as one unit and thus try to optimize the overall performance. Instead, they have to consider the needs of the resource owners. For this type of environment load sharing is a more appropriate goal. Load sharing has been accomplished in some systems in an "all or nothing" fashion, i.e., if a node is idle then it becomes a candidate for executing a remote workload, otherwise it is not. This style of sharing is too restrictive in an environment where most resources are underutilized. We present a scheme that replaces this "all or nothing" approach with a gradual one, i.e., where each machine in the network determines the amount of sharing it is willing to do. The scheme, called High-Low, makes sure that the service provided to local jobs of a lightly loaded
node does not deteriorate by more than predefined amount. It simultaneously helps improve the service at heavily loaded nodes. We empirically show that load sharing in a network of workstations can be effective even with a simple-minded allocation of jobs.