Deadline-constrained MapReduce scheduling based on graph modelling

Chien Hung Chen, Jenn Wei Lin, Sy Yen Kuo

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

MapReduce is a software framework for processing data-intensive applications with a parallel manner in cloud computing systems. There are also an increasing number of MapReduce jobs that require deadline guarantees. The existing deadline-concerning scheduling schemes do not consider the two problems in the MapReduce computing environment: slot performance heterogeneity and job time variation. In this paper, we utilize the Bipartite Graph modeling to propose a new MapReduce Scheduler called the BGMRS. The BGMRS can obtain the optimal solution of the deadline-constrained scheduling problem by transforming the problem into a well-known graph problem: minimum weighted bipartite matching. The BGMRS has the following features. It considers the heterogeneous cloud computing environment, such that the computing resources of some nodes cannot meet the deadlines of some jobs. As the job progresses, the BGMRS can dynamically find different computing resources for running the job without violating the job deadline. This is beneficial in the computing resource utilization. The BGMRS can also trade the data locality off against the deadline to make more jobs with deadline guarantees. If the available computing resources of the system cannot meet all job deadlines, the BGMRS can minimize the number of jobs with the deadline violation. Finally, simulation experiments are performed to demonstrate the effectiveness of the BGMRS in the deadline-constrained scheduling.

Original languageEnglish
Title of host publicationProceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014
EditorsCarl Kesselman
PublisherIEEE Computer Society
Pages416-423
Number of pages8
ISBN (Electronic)9781479950638
DOIs
StatePublished - 03 12 2014
Externally publishedYes
Event7th IEEE International Conference on Cloud Computing, CLOUD 2014 - Anchorage, United States
Duration: 27 06 201402 07 2014

Publication series

NameIEEE International Conference on Cloud Computing, CLOUD
ISSN (Print)2159-6182
ISSN (Electronic)2159-6190

Conference

Conference7th IEEE International Conference on Cloud Computing, CLOUD 2014
Country/TerritoryUnited States
CityAnchorage
Period27/06/1402/07/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

  • bipartite graph modelling
  • cloud computing
  • data-intensive application
  • job deadline
  • MapReduce scheduling

Fingerprint

Dive into the research topics of 'Deadline-constrained MapReduce scheduling based on graph modelling'. Together they form a unique fingerprint.

Cite this