We consider a market-based resource allocation model for batch jobs in cloud
computing clusters. In our model, we incorporate the importance of the due date
of a job by which it needs to be completed rather than the number of servers
allocated to it at any given time. Each batch job is characterized by the work
volume of total computing units (e.g., CPU hours) along with a bound on maximum
degree of parallelism. Users specify, along with these job characteristics, their
desired due date and a value for finishing the job by its deadline. Given this
specification, the primary goal is to determine the scheduling of cloud computing
instances under capacity constraints in order to maximize the social welfare
(i.e., sum of values gained by allocated users). Our main result is a new *frac
CC-kfrac ss-1-approximation algorithm for this objective, where C denotes
cloud capacity, k is the maximal bound on parallelized execution (in
practical settings, *k << C$) and

Based on the new approximation algorithm, we construct truthful allocation and pricing mechanisms, in which reporting the job true value and properties (deadline, work volume and the parallelism bound) is a dominant strategy for all users. To that end, we provide a general framework for transforming allocation algorithms into ruthful mechanisms in domains of single-value and multi-properties. We then show that the basic mechanism can be extended under proper Bayesian assumptions to the objective of maximizing revenues, which is important for public clouds. We empirically evaluate the benefits of our approach through simulations on datacenter job traces, and show that the revenues obtained under our mechanism are comparable with an ideal fixed-price mechanism, which sets an on-demand price using oracle knowledge of users' valuations. Finally, we discuss how our model can be extended to accommodate uncertainties in job work volumes, which is a practical challenge in cloud settings.

}, author = {Navendu Jain and Ishai Menache and Seffi Naor and Jonathan Yaniv}, booktitle = {SPAA}, title = {Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=162441}, year = {2012}, }