Performance of hierarchical load sharing in heterogeneous distributed systems

Performance of distributed systems can be improved by load sharing (i.e., distributing load from heavily loaded nodes to lightly loaded ones). Dynamic load sharing policies take system state into account in making job distribution decisions. The state information can be maintained in one of two basic ways: distributed or centralized. Two examples of distributed policies are the sender-initiated and receiver-initiated policies. While distribution of state information makes the distributed policies suitable for large distributed systems, they do suffer in performance. The centralized single coordinator policy is the best policy from the performance point of view in the absence of contention for the coordinator node. However, for large systems, the coordinator may become a bottleneck limiting the performance benefits of such a policy. In addition, the single coordinator causes fault-tolerance problems as the load distribution is dependent on this single coordinator node. Furthermore, in large hierarchically distributed networks (e.g., several LAN clusters connected by a WAN), consulting the central coordinator is expensive and leads to performance problems. The hierarchical policy minimizes these performance bottlenecks. In this paper, we compare the performance of the hierarchical load sharing policy with that of the two distributed policies and the centralized single coordinator policy in heterogeneous distributed systems. In order to see how close the hierarchical policy performs in comparison to the single coordinator policy, we have considered the scenario where the bottleneck problem does not exist in the centralized policy. We show that the hierarchical policy performs very similar to the single coordinator policy for all the various system and workload parameters considered in this study.