PROJECT TITLE :

Delay-Optimal Scheduling of VMs in a Queueing Cloud Computing System with Heterogeneous Workloads

ABSTRACT:

In this paper, the scheduling of virtual machines (VMs) in a cloud computing system with random arrivals of jobs of different types is investigated while taking into account the delay requirements of the jobs. The delay-optimal virtual machine scheduling in a cloud computing system is formulated as a multi-resource multi-class problem that aims to minimize the average job completion time. This type of problem is typically NP-hard. In order to find a solution to such a problem, we have first proposed a queuing model that buffers VM jobs of the same type in a single virtual queue. The virtual machine (VM) scheduling is then broken up into two parallel low-complexity algorithms by the queueing model. These algorithms are known as intra-queue buffering and inter-queue scheduling. While a min-min best fit (MM-BF) policy is used to schedule the jobs in different queues in order to make the most efficient use of the system's remaining resources, a shortest-job-first (SJF) policy is used to buffer the job requests in each queue based on the job lengths in ascending order. Both of these policies are used in conjunction with one another. We further propose a queue-length-based MaxWeight (QMW) policy based on Lyapunov drift to minimize the queue lengths of VM jobs. This policy, which we refer to as SJF-QMW, is intended to prevent job starvation from occurring for long-duration jobs that are run through SJF-MMBF. The results of the simulation show that both SJF-MMBF and SJF-QMW achieve a high throughput performance in terms of job hosting ratio and a low delay performance in terms of the average time it takes to finish a job.