Scheduling Policies for Cloud Computing

Abstract

Cloud computing focuses on maximizing the effectiveness of the shared resources. Cloud resources are usually not only shared by multiple users but are also dynamically reallocated per demand. This can work for allocating resources to users. This leads to task scheduling as a core and challenging issue in cloud computing. This thesis gives different scheduling strategies and algorithms in cloud computing. For a common cloud user, there is a great potential to boost the performance of mobile devices by offloading computation-intensive parts of mobile applications to the cloud. However, this potential is hindered by a gap between how individual mobile devices demand computational resources and how cloud providers offer them. In this thesis, we present the design of utility-based uploads sharing strategy in cloud scenarios, which bridges the above gap through providing computation offloading as a service to mobile devices. Our scheme efficiently manages cloud resources for offloading requests to improve offloading performances of mobile devices, as well as to reduce the monetary cost per request of the provider. However, from the viewpoint of data centers, resource limitations in both bandwidth and computing triggers a variety of resource management problems. In this thesis, we discuss the tradeoff between locality and load balancing, along with the multi-layer topology of data centers. After that, we investigate the interrelationship between the time cost and the virtual machine rent cost, and formalize it as the parallel speedup pattern. We then design several algorithms by adopting the idea of minimizing the utility cost. Furthermore, we focus on the detail of MapReduce framework in Cloud. For different MapReduce phases, there are different resource requirements. We propose a new scheduling algorithm based on the idea of combining map shuffle pairs, which has better performance than the popular min-max time first algorithm in minimizing the average makespan of tasks in the job matrix. Directions for future research mainly focus on the large scale implementation of our proposed solution. There are a wide variety of open questions remaining with respect to the design of algorithms to minimize response time. Further, it is interesting and important to understand how to schedule in order to minimize other performance metrics.