NDLI: Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters

Please wait, while we are loading the content...

Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters

Content Provider	ACM Digital Library
Author	Jain, Navendu Naor, Joseph (Seffi) Menache, Ishai Yaniv, Jonathan
Copyright Year	2015
Abstract	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 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 $\textit{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 (CC-kċss-1)-approximation algorithm for this objective, where $\textit{C}$ denotes cloud capacity, $\textit{k}$ is the maximal bound on parallelized execution (in practical settings, $\textit{k}$ < $\textit{C})$ and $\textit{s}$ is the slackness on the job completion time, that is, the minimal ratio between a specified deadline and the earliest finish time of a job. Our algorithm is based on utilizing dual fitting arguments over a strengthened linear program to the problem. Based on the new approximation algorithm, we construct truthful allocation and pricing mechanisms, in which reporting the true value and other properties of the job (deadline, work volume, and the parallelism bound) is a dominant strategy for all users. To that end, we extend known results for single-value settings to provide a general framework for transforming allocation algorithms into truthful 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 data-center job traces, and show that the revenues obtained under our mechanism are comparable with an $\textit{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.
Starting Page	1
Ending Page	29
Page Count	29
File Format	PDF
ISSN	23294949
e-ISSN	23294957
DOI	10.1145/2742343
Volume Number	2
Issue Number	1
Journal	ACM Transactions on Parallel Computing (TOPC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-04-13
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Resource allocation Cloud computing Economic models Scheduling algorithms Truthful mechanisms
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Modeling and Simulation Computer Science Applications Software Computational Theory and Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Towards Designing a Truthful Online Auction Framework for Deadline-aware Cloud Resource Allocation

An online auction framework for dynamic resource provisioning in cloud computing

A simulation of priority based earliest deadline first scheduling for cloud computing system

Adaptive resource allocation for preemptable jobs in cloud systems

PRISM: Fine-Grained Resource-Aware Scheduling for MapReduce

Heavy traffic optimal resource allocation algorithms for cloud computing clusters

A survey on resource allocation techniques in cloud computing

Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters

Similar Documents

Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Towards Designing a Truthful Online Auction Framework for Deadline-aware Cloud Resource Allocation

An online auction framework for dynamic resource provisioning in cloud computing

A simulation of priority based earliest deadline first scheduling for cloud computing system

Adaptive resource allocation for preemptable jobs in cloud systems

PRISM: Fine-Grained Resource-Aware Scheduling for MapReduce

Heavy traffic optimal resource allocation algorithms for cloud computing clusters

A survey on resource allocation techniques in cloud computing

Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters