Incentive-Based Scheduling for Market-Like
Computational Grids
Lijuan Xiao, Yanmin Zhu, Member, IEEE, Lionel M. Ni, Fellow, IEEE, and
Zhiwei Xu, Senior Member, IEEE
Abstract—A sustainable market-like computational grid has two characteristics: it must allow resource providers and resource consumers to make autonomous scheduling decisions, and both parties of providers and consumers must have sufficient incentives to stay and play in the market. In this paper, we formulate this intuition of optimizing incentives for both parties as a dual-objective scheduling problem. The two objectives identified are to maximize the success rate of job execution and to minimize fairness deviation among resources. The challenge is to develop a grid scheduling scheme that enables individual participants to make autonomous decisions while producing a desirable emergent property in the grid system; that is, the two systemwide objectives are achieved simultaneously. We present an incentive-based scheduling scheme, which utilizes a peer-to-peer decentralized scheduling framework, a set of local heuristic algorithms, and three market instruments of job announcement, price, and competition degree. The performance of this scheme is evaluated via extensive simulation using synthetic and real workloads. The results show that our approach outperforms other scheduling schemes in optimizing incentives for both consumers and providers, leading to highly successful job execution and fair profit allocation.
Index Terms—Computational grid, scheduling, incentive, peer to peer, market-like.
Ç
1 INTRODUCTION
GRID computing, which aims at enabling wide-area resource sharing and collaboration, is emerging as a promising distributed computing paradigm [1]. According to how they schedule computational jobs to resources, computational grids can be classified into two types: controlled and market-like grids. Both types involve sharing and collaboration among resource providers and resource consumers, and the scheduling schemes can be either centralized or decentralized. The key difference between the two lies inwho makes scheduling decisions. In a controlled grid, the grid system decides when to execute which job on which resource. In a market-like grid, such decisions are made by each resource provider/consumer, but all the individual participants utilize some market instruments such as price to achieve the grid systemwide objectives.
This paper focuses on the scheduling problem in marketlike computational grids. In particular, we address the issues of optimizing incentives for both resource consumers and resource providers so that every participant has sufficient incentive to stay and play, leading to a sustainable market. The main challenge, phrased as a scheduling problem, is to schedule jobs of consumers to resources of providers to optimize incentives for both parties. Most importantly, such objectives should be realized not by an omnipotent scheduler. Rather, the scheduling scheme should be autonomous. That is, each participant makes decisions on its own behalf, and the individual economic behaviors of all participants work together to accomplish resource scheduling, with optimized incentives being an emergent property of the grid system. Does such a scheme exist at all? The answer is not obvious.
We formulate the above scheduling problem and investigate market instruments and algorithms to solve the problem. We identify the successful-execution rate of jobs as the incentive for consumers and the inverse of fairness deviation as the incentive for providers. As even a subproblem of the formulated scheduling problem is
NP-complete (see Section 4.2), we develop a scheduling scheme (called IB) using local heuristics. Job announcement, competition degree (CD), and price are defined and used as market instruments. Four heuristic algorithms, local to each participant, are developed to utilize the market instruments and to optimize the incentives. Performance evaluation is conducted via extensive simulations, utilizing both statistically generated workloads and real workloads. The results show that the proposed IB scheme outperforms other schemes in optimizing incentives for both consumers and providers. The rest of this paper is organized as follows: Section 2 gives a formal problem statement. Section 3 contrasts with related work. Section 4 presents the incentive-based scheduling scheme in detail. Section 5 evaluates the performance of our scheme. Section 6 offers concluding
remarks.