Deadline-Constrained MapReduce Scheduling Based on Graph Modelling

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.