Learning non-cooperative game for load balancing under self-interested distributed environment

Graphical abstractDisplay Omitted HighlightsProvide a unified framework which characterizes inter or intra interactions.Enhance fairness among self-interested schedulers by Nash equilibrium of non-cooperative game.Propose a fairness aware scheme by reinforcement learning, adaptable without prior knowledge.Validate its fairness and effectiveness under varied utilization, heterogeneity, and size by simulation. Resources in large-scale distributed systems are distributed among several autonomous domains. These domains collaborate to produce significantly higher processing capacity through load balancing. However, resources in the same domain tend to be cooperative, whereas those in different domains are self-interested. Fairness is the key to collaboration under a self-interested environment. Accordingly, a fairness-aware load balancing algorithm is proposed. The load balancing problem is defined as a game. The Nash equilibrium solution for this problem minimizes the expected response time, while maintaining fairness. Furthermore, reinforcement learning is used to search for the Nash equilibrium. Compared with static approaches, this algorithm does not require a prior knowledge of job arrival and execution, and can adapt dynamically to these processes. The synthesized tests indicate that our algorithm is close to the optimal scheme in terms of overall expected response time under different system utilization, heterogeneity, and system size; it also ensures fairness similar to the proportional scheme. Trace simulation is conducted using the job workload log of the Scalable POWERpallel2 system in the San Diego Supercomputer Center. Our algorithm increases the expected response time by a maximum of 14%. But it improves fairness by 1227% in contrast to Opportunistic Load Balancing, Minimum Execution Time, Minimum Completion Time, Switching Algorithm, and k-Percent Best.