Cloud computing is a newly emerging distributed system which is evolved from Grid computing. Task scheduling is the core research of cloud computing which studies how to allocate the tasks among the physical nodes, so that the tasks can get a balanced allocation or each task's execution cost decreases to the minimum, or the overall system performance is optimal. Unlike task scheduling based on time or cost before, aiming at the special reliability requirements in cloud computing, we propose a non-cooperative game model for reliability-based task scheduling approach. This model takes the steady-state availability that computing nodes provide as the target, takes the task slicing strategy of the schedulers as the game strategy, then finds the Nash equilibrium solution. And also, we design a task scheduling algorithm based on this model. The experiments can be seen that our task scheduling algorithm is better than the so-called balanced scheduling algorithm.
For balanced task scheduling, @cite_11 @cite_12 @cite_17 proposed some models and task scheduling algorithms in distributed system with the market model and game theory. @cite_9 @cite_8 introduced a balanced grid task scheduling model based on non-cooperative game. QoS-based grid job allocation problem is modeled as a cooperative game and the structure of the Nash bargaining solution is given in @cite_30 . In @cite_15 , Wei and Vasilakos presented a game theoretic method to schedule dependent computational cloud computing services with time and cost constrained, in which the tasks are divided into subtasks. The above works generally take the scheduler or job manager as the participant of the game, take the total execution time of tasks as the game optimization goals and give the proof of the existence of the Nash equilibrium solution and the solving Nash equilibrium solution algorithm, or model the task scheduling problem as a cooperative game and give the structure of the cooperative game solution.
@cite_30 @cite_11 @cite_8 @cite_9 @cite_15 @cite_12 @cite_17
2122144684 2138978154 2129059987 2143611771 2132104966
A grid differs from traditional high performance computing systems in the heterogeneity of the computing nodes as well as the communication links that connect the different nodes together. In grids there exist users and service providers. The service providers provide the service for jobs that the users generate. Typically the amount of jobs generated by all the users are more than any single provider can handle alone with any acceptable quality of service (QoS). As such, the service providers need to cooperate and allocate jobs among them so that each is providing an acceptable QoS to their customers. QoS is of particular concerns to service providers as it directly affects customers' satisfaction and loyalty. In this paper, we propose a game theoretic solution to the QoS sensitive, grid job allocation problem. We model the QoS based, grid job allocation problem as a cooperative game and present the structure of the Nash Bargaining Solution. The proposed algorithm is fair to all users and represents a Pareto optimal solution to the QoS objective. One advantage of our scheme is the relatively low overhead and robust performance against inaccuracies in performance prediction information. We applied techniques from game theory to help formulate and analyze solutions to two systems problems: discouraging selfishness in multi-hop wireless networks and enabling cooperation among ISPs in the Internet. It proved difficult to do so. This paper reports on our experiences and explains the issues that we encountered. It describes the ways in which the straightforward use of results from traditional game theory did not fit well with the requirements of our problems. It also identifies an important characteristic of the solutions we did eventually adopt that distinguishes them from those available using game theoretic approaches. We hope that this discussion will help to highlight formulations of game theory which are well-suited for problems involving computer systems. Load balancing is a very important and complex problem in computational grids. A computational grid differs from traditional high-performance computing systems in the heterogeneity of the computing nodes, as well as the communication links that connect the different nodes together. There is a need to develop algorithms that can capture this complexity yet can be easily implemented and used to solve a wide range of load-balancing scenarios. In this paper, we propose a game-theoretic solution to the grid load-balancing problem. The algorithm developed combines the inherent efficiency of the centralized approach and the fault-tolerant nature of the distributed, decentralized approach. We model the grid load-balancing problem as a noncooperative game, whereby the objective is to reach the Nash equilibrium. Experiments were conducted to show the applicability of the proposed approaches. One advantage of our scheme is the relatively low overhead and robust performance against inaccuracies in performance prediction information. Cloud computing is a natural evolution for data and compute centers with automated systems management, workload balancing, and virtualization technologies. Cloud-based services integrate globally distributed resources into seamless computing platforms. In an open cloud computing framework, scheduling tasks with guaranteeing QoS constrains presents a challenging technical problem. This paper presents a game theoretic method to schedule dependent computational cloud computing services with time and cost constrained. An evolutionary mechanism is designed to fairly and approximately solve the NP-hard scheduling problem. We study the nature of sharing resources in distributed collaborations such as Grids and peer-to-peer systems. By applying the theoretical framework of the multi-person prisoner's dilemma to this resource sharing problem, we show that in the absence of incentive schemes, individual users are apt to hold back resources, leading to decreased system utility. Using both the theoretical framework as well as simulations, we compare and contrast three different incentive schemes aimed at encouraging users to contribute resources. Our results show that soft-incentive schemes are effective in incentivizing autonomous entities to collaborate, leading to increased gains for all participants in the system.