Convergence of the dynamic load balancing problem to Nash equilibrium using distributed local interactions

Abstract

Load balancers distribute workload across multiple nodes based on a variation of the round robin algorithm, or a more complex algorithm that optimizes a specified objective or allows for horizontal scalability and higher availability. In this paper, we investigate whether robust load balancing can be achieved using a local co-operative mechanism between the resources (nodes). The local aspect of the mechanism implies that each node interacts with a small subset of the nodes that define its neighborhood. The co-operative aspect of the mechanism implies that a node may offload some of load to its neighbor nodes that have lesser load or accept jobs from neighbor nodes that have higher load. Each node is thus only aware of the state of its neighboring nodes and there is no central entity that has the knowledge of the state of all the nodes. We model the overall mechanism of load balancing based on local interactions as a congestion game and show that convergence to the Nash equilibrium is possible using only local interactions. We derive worst case bounds on the number of transfers (time) required to achieve global load balancing under this setup. We also include simulation results to demonstrate emergent global load balancing based only on local interactions and local information. © 2012 Elsevier Inc. All rights reserved.