The Design of an Efficient Load Balancing Algorithm Employing a Symmetric Balanced Incomplete Block Design

摘要

In order to maintain load balancing in distributed system, we should obtain workload information from all the nodes on network. It requires O(v~2) communication overhead, where v is the number of nodes. In this paper, we present a new synchronous dynamic distributed load balancing algorithm on a (v,k + 1,1)-configured network applying symmetric balanced incomplete block design, where v = k~2+k+l. Our algorithm needs only O(v(v~(1/2))) message overhead 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.