Carleton University
Technical Report TR-98-02
January 1998
TR-98-02: A Comparative Study of Adaptive and Hierarchical Load Sharing Policies for Distributed Systems
Abstract
Dynamic load sharing policies take system state into account in making load distribution decisions. The state information can be maintained in one of two basic ways: distri- buted or centralized. Two principal types of policies that belong to the distributed scheme are the sender-initiated and receiver- initiated policies. In the centralized scheme, a central coordinator node is responsible for collecting system state information. Distri- buted policies do not perform as well as the centralized policy. Performance of distributed policies is sensitive to variance in job service times and inter-arrival times. Distributed policies, however, are scalable whereas the centralized policy can cause bottleneck and fault-tolerance problems for large systems. An adaptive distributed policy has been proposed that dynamically switches between sender-initiated and receiver-initiated policies depending on the system state. Here we propose a new global hierarchical load sharing policy that minimizes the drawbacks ass- ociated with the distributed and centralized policies while retaining hierarchical load sharing policy that minimizes the drawbacks ass- ociated with the distributed and centralized policies while retaining their advantages. We provide a performance comparison of these policies and show that the proposed hierarchical policy provides the best performance among the distributed and adaptive policies for all the various system and workload parameters considered.