Abstract

''Efficient Algorithms for Load Balancing in Static and Dynamic Networks''

Gokarna Sharma

Suresh Rai

Costas Busch

Jerry L. Trahan

Ramachandran Vaidyanathan

submitted to IEEE Transactions on Parallel and Distributed Systems, 2015

Abstract:

We consider the following fundamental load balancing problem: given any undirected connected graph and an initial weight distribution on the nodes, determine a schedule to move weights across edges so as to have (almost) equal weights on the nodes. Weights are moved across edges in rounds; and, in a round, weights are moved between the terminal nodes of an edge exactly once. We study this problem in both static and dynamic networks. Previous algorithms are slow in practice because they require many rounds of weight exchanges to balance the load. We present a class of algorithms that are efficient. The main idea is to consider weak topologies where a node exchanges load with its neighbors sequentially (one neighbor at a time) and the load at that node is updated before subsequent exchanges with other neighbors. Thorough simulations on six different network topologies, which have widely been used to model the topologies of many parallel and distributed applications, show that our algorithms balance load quite efficiently compared to previous algorithms. More precisely, the number of rounds of our algorithms is only 13-68% of the number of rounds of the previous algorithms in all the experimental settings under the same parameters.