Dynamic Load Balancing In Distributed Systems In The Presence Of Delays A Regeneration-Theory Approach

A regeneration-theory approach is under taken to analytically characterize the average over all completion time in a distributed system. The approach considers the heterogeneity in the processing rates of the nodes as well as the random in the delays imposed by the communication medium. The optimal one-shot load balancing policy is developed and subsequently extended to develop an autonomous and distributed load-balancing policy that can dynamically reallocate incoming external loads at each node.

This adaptive and dynamic load balancing policy is implemented and evaluated in a two-node distributed system. The performance of the proposed dynamic load-balancing policy is compared to that of static policies as well as existing dynamic load-balancing policies by considering the average completion time per task and the system processing rate in the presence of random arrivals of the external loads.

Existing System:

Existing method for structured AMR applications was proposed in unfortunately, the overhead introduced by this DLB scheme is significant. Further, a parameter called threshold is used in this scheme which determines whether a load balancing process should be invoked; its value directly influence the efficiency of the overall DLB scheme. In this paper, we first present two improvements on this DLB scheme to reduce its overhead.

Then a detailed sensitivity analysis is provided to identify an optimal value for the parameter threshold. Experiments show that by interleaving grid splitting with direct grid movement and by employing non blocking communication, the execution time can be improved by up to and the overhead can be reduced.

Proposed System:

The computing power of any distributed system can be realized by allowing its constituent computational elements (CEs), or nodes, to work cooperatively so that large loads are allocated among them in a fair and effective manner. Any strategy for load distribution among CEs is called load balancing (LB). An effective LB policy ensures optimal use of the distributed resources whereby no CE remains in an idle state while any other CE is being utilized.

We characterize the expected value of the overall completion time for a given initial load under the centralized one-shot LB policy for an arbitrary number of nodes. The overall completion time is defined as the maximum over completion times for all nodes. We use the theory to optimize the selection of the LB instant and the LB again. A distributed and adaptive version of the one-shot is also developed and used to propose a sender-initiated DLB policy.

A continuous-time stochastic model has been formulated for the queues’ dynamics of a distributed computing system in the context of load balancing. The model takes into account the randomness in delay and allows random arrivals of external loads. At first, the model was simplified by relaxing external arrivals of loads and an optimization problem was formulated for minimizing the average overall completion time.

Module Description:

  • A Packet Consists of Two Kinds Of Data
  • Forwarding Input Switches to Centralized Switch
  • Dynamic Load Balancing
  • Forward the Packet Centralized Switch to Output Switch