A Sender-Initiated Adaptive Load Balancing Scheme Based on Predictable State Knowledge*

Gil-Haeng LEE  Heung-Kyu LEE  Jung-Wan CHO  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.3   pp.209-221
Publication Date: 1996/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Sofware System
adaptive load balancing,  sender-initiated,  predictable state knowledge,  

Full Text: PDF(1.1MB)>>
Buy this Article

In an adaptive load balancing, the location policy to determine a destination node for transferring tasks can be classified into three categories: dynamic selection, random selection, and state polling. The dynamic selection immediately determines a destination node by exploiting the state information broadcasted from other nodes. It not only requires the overheads of collecting the state information, but may cause an unpredictable behavior unless the state information is accurate. Also, it may not guarantee even load distribution. The random selection determines a destination node at random. The state polling determines a destination node by polling other nodes. It may cause some problems such as useless polling, unachievable load balancing, and system instability. A new Sender-initiated Adaptive LOad balancing scheme (SALO) is presented to remedy the above problems. It determines a destination node by exploiting the predictable state knowledge and by polling the destination node. It can determine a good destination with minimal useless polling and guarantee even load distribution. Also, it has an efficient mechanism and good data structure to collect the state information simply. An analytic model is developed to compare with other well known schemes. The validity of the model is checked with an event-driven simulation. With the model and the simulation result, it is shown that SALO yields a significant improvement over other schemes, especially at high system loads.