Paper Info
Title
Deadline-Constrained MapReduce Scheduling Based on Graph Modelling.
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.
Year
DOI
Venue
2014
10.1109/CLOUD.2014.63
IEEE CLOUD
Keywords
Field
DocType
MapReduce scheduling, data-intensive application, cloud computing, job deadline, bipartite graph modelling
Locality,Job shop scheduling,Computer science,Scheduling (computing),Bipartite graph,Real-time computing,Dynamic priority scheduling,Earliest deadline first scheduling,Software framework,Cloud computing,Distributed computing
Conference
ISSN
Citations 
PageRank 
2159-6182
3
0.37
References 
Authors
12
3
Name
Order
Citations
PageRank
Chien-Hung Chen1554.90
Jenn-Wei Lin213815.41
Sy-Yen Kuo32304245.46