Distributing Workload 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 distribution algorithms have been proposed in the literature. In a network of independently owned processors (e.g. a network of workstations), load distribution schemes
cannot consider the whole network as one unit and thus cannot try to optimize the overall performance. That is to say that load balancing schemes are not appropriate for this type of environment. Instead, the needs of each resource owner have to be considered. Therefore load sharing is more appropriate.
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. Other attempts have used priority schemes where remote jobs are run with lower scheduling priority than local jobs. These
styles of sharing are too restrictive in an environment where most resources are underutilized. Also, they do not scale well as the system load increases. We present a scheme that replaces these sharing approaches 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 a predefined amount. It simultaneously helps improve the service at heavily loaded nodes. We empirically compare the different approaches to load
distribution and show that it can be effective in a network of workstations.