TR-96-01: Hierarchical Load Sharing Policies for Distributed Systems

Performance of distributed systems can be improved by load sharing. Dynamic load sharing policies take the system state into account in making load distribution decisions. The system state information can be collected in a distributed manner or by a single central controller node. In the distributed scheme, each node gathers the current system state information before making a decision on load distri-bution. Load sharing policies based on this strategy typically probe a few randomly selected nodes for their status in order to find a suitable partner for load distribution. Two principal policies that have been studied extensively in the literature are the sender- initiated and receiver-initiated policies. In the centra-lized scheme, a central node (called the ‘coordinator’) is assigned the responsibility of collecting the system state information. Any other node that needs to distribute load consults the coordinator node for a suitable partner. The distributed 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. The distributed policies, on the other hand, are scalable to large systems whereas the centralized policy causes bottleneck problems for large systems. Another problem with the centralized scheme is that if the coordinator fails, the system defaults to ‘no-load sharing’ scenario. Here we propose a hierarchical load sharing policy that minimizes the drawbacks associated with the distributed and centralized policies while retaining their advantages. We propose and study the performance of the hierarchical load sharing policies. The results presented here show that the hierarchical policies inherit the merits of the centralized and distributed policies while minimizing the disadvantages associated with them.