An energy-aware scheduling heuristic for distributed systems using non-cooperative games

Main concerns for scheduling policies of large-scale distributed computing systems are performance, scalability and energy efficiency. In this paper, we propose a multi-objective, batch-mode scheduling algorithm that manages tasks and resources in such systems using non-cooperative local games. The scheduling problem is modeled by profiling the various tasks and their dependencies. A set of independent, high-priority root tasks are identified as players in our game model. A group layout is given to the nodes in the distributed system based on geographic proximity. Each group plays non-cooperative games simultaneously to compute energy-aware Nash equilibrium schedules for the root tasks (step 1). A figure of merit called health is defined for each node based on its load, voltage and temperature. For each player i.e. task, the payoff for choosing a node is calculated based on its health and processing time for task on that node. Based on turnaround time of a Nash equilibrium schedule and rate of change in health of the associated group, another figure of merit called rate is calculated per group. Root tasks are allocated to group with maximum rate (step 2). Limits are specified on rate metric for optimal load balancing and energy conservation in the distributed system. Simulation results explain benefits of our algorithm by comparing our results with greedy approach and a heuristic based on cooperative games from recent literature. Our algorithm shows up to 37% improvement in health and 10-14% improvement in turnaround time.