MapReduce Scheduling for Deadline-Constrained Jobs in Heterogeneous Cloud Computing Systems

MapReduce is a software framework for processing data-intensive applications with a parallel manner in cloud computing systems. Some MapReduce jobs have the deadline requirements for their job execution. The existing deadline-constrained MapReduce scheduling schemes do not consider the following two problems: various node performance and dynamical task execution time. In this paper, we utilize the Bipartite Graph modelling 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. In addition to meeting the deadline requirement, the BGMRS also takes the data locality into the computing resource allocation for shortening the data access time of a job. However, if the total available computing resources of the system cannot satisfy the deadline requirements of all jobs, the BGMRS can minimize the number of jobs with the deadline violation. Finally, both simulation and testbed experiments are performed to demonstrate the effectiveness of the BGMRS in the deadline-constrained scheduling.