Technical Report MSC-2011-12

Title: Truthful Mechanisms for Value-Based Scheduling in Cloud Computing
Authors: Jonathan Yaniv
Supervisors: Joseph (Seffi) Naor
Abstract: Cloud computing provides an attractive computation platform, in which computing resources (e.g., virtual machines, storage capacity) are rented to end-users under a utility pricing model. The most common pricing offering is a pay-as-you-go scheme, in which users are charged a fixed price per unit resource per hour. While this scheme is simple to implement, it does not support value-based scheduling, where users assign a value to their job and the cloud's goal is to schedule jobs to maximize aggregate value under job demand and capacity constraints.

In this work, we introduce a novel pricing and allocation approach for batch jobs (e.g., image processing, financial analytics, scientific simulations) on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which obtains a small approximation factor that approaches 2 as the number of servers increases, assuming that user valuations are known. An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources. Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion