EFFICIENT LOAD INFORMATION MANAGEMENT FOR LOAD SHARING IN DISTRIBUTED SYSTEMS

Central to effective load sharing in a distributed system is the load information manager (LIM) on each node that maintains system-wide state information. Two prominent techniques used for LIMs are probing on demand a few randomly selected nodes and periodic broadcast, in which the load information is exchanged by all nodes at fixed time intervals. In this paper, we investigate the accuracy and overheads of LIM techniques in homogeneous and heterogeneous distributed systems. For probing, we confirm the earlier result that for most realistic homogeneous and heterogeneous systems, probing a small fraction of the total nodes gives performance nearly as good as probing all nodes. However, we show that in a widely heterogeneous system, we need to probe a large number of nodes in order to achieve good performance. We propose two LIM strategies which aim at reducing message overhead. The first is a hybrid, Switching LIM (SLIM), which switches between probing and periodic broadcast modes of operation depending on the load condition. SLIM could find application in systems where a fixed bandwidth is allocated for load sharing purpose. The other, Predicting LIM (PLIM), exploits temporal correlation between load values to predict the loads at the remote nodes. Hence, the broadcast period can be substantially increased. We study the performance of these LIMs using an analytic model and stochastic and trace-driven simulation.