A Game Approach to Multi-Servers Load Balancing with Load-Dependent Server Availability Consideration

In this paper, we focus on request migration strategies among multi-servers for load balancing. Different from the general load balancing problem, we consider it under a distributed, non-cooperative, and competitive environment. Due to the mentioned characteristics, we view our problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple servers, in which each server is informed with incomplete information of other servers. For each server, we define its expected response time as a disutility function and try to minimize its value. We also take into account server availability, which impacts the processing capacity of a server and thus its disutility. We solve the problem by employing variational inequality (VI) theory and prove that there exists a Nash equilibrium solution set for the formulated game. Then, we propose an iterative proximal algorithm (IPA) to compute a Nash equilibrium solution. The convergence of the IPA algorithm is also analyzed and we find that it converges to a Nash equilibrium. Finally, we conduct some numerical calculations to verify our theoretical analyses. The experimental results show that our proposed IPA algorithm converges to a Nash equilibrium very quickly and significantly decreases the disutilities of all servers by configuring a proper request migration strategy.