Design of an efficient load balancing algorithm on distributed networks by employing symmetric balanced incomplete block design
Oh-Sung Lee, M. Anshel, Ilyong Chung · IEE Proceedings - Communications · 2004
To maintain load balancing in a distributed system, it is necessary to obtain workload information from all the nodes in the network. This processing requires O(v2) communication complexity, where v is the number of nodes. The authors present a new synchronous dynamic distributed load balancing algorithm on a (v, k+1, 1)-configured network applying a symmetric balanced incomplete block design, where v=k2+k+1. The algorithm needs only O (v√v) communication complexity and each node receives workload information from all the nodes without redundancy. Therefore, load balancing is maintained since every link has the same amount of traffic for transferring workload information.