A SENDER-INITIATED ADAPTIVE LOAD BALANCING SCHEME BASED ON PREDICTABLE STATE KNOWLEDGE

In an adaptive load balancing, the location policy to determine a dest ination node for transferring tasks can be classified into three categ ories: dynamic selection, random selection, and state polling. The dyn amic selection immediately determines a destination node by exploiting the state information broadcasted from other nodes. It not only requi res the overheads of collecting the state information, but may cause a n unpredictable behavior unless the state information is accurate. Als o, it may not guarantee even load distribution. The random selec tion 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 insta bility. A new Sender-initiated Adaptive LOad balancing scheme (SALO) i s 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 use less polling and guarantee even load distribution. Also, it has an eff ocient mechanism and good data structure to collect the state informat ion simply. An analytic model is developed to compare with other well known schemes. The validity of the model is checked with an event-driv en simulation. With the model and the simulation result, it is shown t hat SALO yields a significant improvement over other schemes, especial ly at high system loads.