29-06-2013, 11:56 AM
THE ABOVE AVERAGE ALGORITHM
[attachment=56209]
Load Distributing Algorithm:
Some load distribution algorithms are
Sender Initiated algorithms
Receiver Initiated algorithms
Symmetrically Initiated algorithms
- THE ABOVE AVERAGE ALGORITHM
Adaptive algorithms
Receiver-Initiated algorithms:
In this algorithms, the load distributing activity is initiated from an underloaded node i.e receiver that is trying to obtain a task from an overloaded node i.e sender.
Symmetrically Initiated algorithms:
In this algorithm, both senders and receivers search for receivers and senders for task transfers.
So these algorithms have the advantages of both sender initiated and receiver initiated algorithms.
If the system load is low, the sender initiated component is more successful in finding underloaded nodes.
If the system load is high, the receiver initiated component is more successful in finding overloaded nodes.
Disadvantages:
However these symmetrically initiated algorithms are not immune from the disadvantages of sender and receiver initiated algorithms.
In sender initiated algorithm, task sending at high system loads leads to system instability.
In receiver initiated algorithm, a preemptive task transfer facility is necessary.
THE ABOVE AVERAGE ALGORITHM:
This is used to maintain the load at each node within an acceptable range of the system average.
Maintaining the load at each node at the exact system average, it leads to processor thrashing.
Sender Initiated component:
A sender broadcasts a TooHigh message, sets a TooHigh timeout alarm, and waits for the Accept message.
The receiver that receives a TooHigh message cancels its TooLow timeout sends an Accept message to the sender and increases its load value and sets an AwaitingTask timeout.
Increasing its load value prevents a receiver from over committing itself to accepting remote tasks.
On receiving the Accept message, if the node is still a sender, it chooses the best task to transfer and transfers it to the receiver who sends Accept message.
On receiving a TooLow message, it sends a TooHigh message to the node which sends TooLow message.
If sender does not get accept message within its TooHigh timeout, then the sender estimates that the average system load is too low. Then the sender broadcast a ChangeAverage message to increase the average load estimated to the other nodes.
Receiver Initiated component:
The receiver node broadcasts a TooLow message, sets a TooLow timeout alarm and waits for the TooHigh message.
If a TooHigh message is received, the receiver performs the same actions that it does under sender initiated component.
If the TooLow timeout expires before receiving any TooHigh messages, the receivers broadcasts a ChangeAverage message to decrease the average load estimate at the other nodes.