Resource Management Techniques for Multi-Stage Jobs with Deadlines Running on Clouds

The objective of this thesis is to devise effective resource management techniques for processing a workload comprising an open stream of multi-stage jobs on a distributed computing environment, such as a private cluster or a set of resources acquired a priori from a public cloud. Each job is associated with a service level agreement (SLA) characterized by an earliest start time, an execution time, and an end-to-end deadline. The two important operations in resource management that this thesis focuses on are resource allocation (matchmaking) and scheduling. Given a pool of jobs to execute, a matchmaking algorithm chooses the resources to be allocated to a given job, whereas a scheduling algorithm determines the order in which these jobs are to be executed for achieving the desired system objectives. Multi-stage jobs have multiple phases of execution and require processing from multiple system resources. Resource management techniques for processing MapReduce jobs (used for facilitating Big Data analytics), as well as other multi-stage jobs such as scientific workflows characterized by multiple phases of execution and different types of precedence relationships, are considered. The key techniques devised in this thesis research include: (1) resource management techniques based on decomposing the end-to-end deadline of a multi-stage job into components (e.g., sub-deadlines) each of which is associated with a specific task in the job, (2) alternative resource management algorithms that use optimization techniques, and (3) techniques for handling inaccuracy/error in user estimates of job execution times (submitted as part of the SLA). A comprehensive and rigorous performance evaluation of the resource management techniques is conducted using prototyping and measurement on a real system deployed on a cloud as well as simulation.