Concept of load balancing along with sender initiated algorithm

• Load balancing is a technique in which workload is distributed across multiple computers or other resources to get optimal resource utilization, minimum time delay, maximize throughput and avoid overload.
• Load balancing scheme can be characterized as static and dynamic load balancing.
• In dynamic load balancing scheme, tasks are transferred during execution from the heavily loaded processor to lightly loaded one.
• In dynamic load balancing, at run time the changes are made to the distribution of work which uses the information about load that is current or recent for making distribution decisions.
• A sender-initiated load balancing strategy is used by dynamic load balancing scheme.

Basic Idea:

An overloaded node (sender) tries to send a task to an under loaded node (receiver).

Information policy:

Demand-driven: Upon identification of a node as a sender, load information from other nodes is collected. Among the possible load indexes, consider only CPU queue length.

Transfer policy: CPU queue threshold T for all nodes. Initiated when a task arrives.

Threshold based: A sender is a node, originating a task that makes its local CPU queue length exceed a threshold T. A receiver is a node that, by accepting a given task, would not exceed T.

Selection policy:

Newly arrived tasks or newly started processes without requiring preemption.

Location policy:

1. Random: No information exchange, Useless transfer are possible. Select any node to transfer the task at random. The selected node X may be overloaded. If transferred task is treated as new arrival then X may transfer the task again.
2. Threshold: Nodes are sequentially polled in random order. Poll nodes until a receiver is found which is done up to the Poll Limit nodes. If none is a receiver then the sender commits to the task.
3. Shortest: A random subset of nodes is polled and the one with the shortest queue length is chosen. Main aim is to choose the best receiver node rather than the first suitable one.

Stability of the algorithm:

• In high load scenarios there won’t (likely) be receivers, but polling would still keep on, triggered more and more frequently as task arrival rate increases.
• The algorithm overhead can become higher and higher, eventually overcoming the service capacity of the system, causing system instability.