A Resource-Aware Dynamic Load-balancing Techniques for Deadline Constrained Cloud Tasks


Cloud computing has emerged as an attractive platform to facilitate the computing needs of users over the Internet. The Cloud service providers acquire the computing resources (software and hardware) and assign them to the users on a pay-per-use mode. To e ectively utilize Cloud resources and achieve high user satisfaction, Cloud service providers demand ecient task scheduling algorithms. An ecient task scheduling algorithm should be fair and adaptive to improve resource utilization, meet task deadlines, minimize the makespan, reduce the task response time, and task rejection ratio. There are a number of task scheduling and load balancing algorithms, however, most of these scheduling algorithms fail to achieve ecient resource utilization and load-balancing. The main reason is that these algorithms are not resource and deadline-aware. Moreover, these algorithms execute tasks in batch mode, do not properly monitor/update the Virtual Machines (VMs) load and tasks execution status at run-time. To achieve high resource utilization, load balancing, minimized makespan, reduced task response time, and lower task rejection ratio, there is a need to have such dynamic scheduling algorithms which can monitor and update the VMs load along with tasks execution status at run- time. Furthermore, these algorithms should have a high capability to meet task deadlines and reduce the task rejection ratio. To overcome these issues, a resource aware dynamic load balancing technique for deadline constrained task has been proposed. The contribution of the proposed scheduling scheme has been divided into three parts.

The rst part of this thesis presents a Resource Aware Dynamic Load-balancer (RADL) for deadline constrained Cloud tasks. The RADL approach has the ability to evenly distribute the incoming workload of independent and compute-intensive tasks at run-time. In addition, RADL approach has the capability to accommodate the newly arrived tasks (with shorter deadlines) in ecient manner. The proposed approach consists of two schedulers namely RADL-Scheduler and ShifterScheduler (S-Scheduler). RADL-Scheduler allocates incoming tasks to a set of VMs based on minimum completion time. It also monitors/updates the task and VM status. S-Scheduler, nds a suitable position in the task queue of a VM for the incoming tasks with shorter deadlines. Experimental results show that the proposed approach has attained up to 67.74%, 303.57%, 259.2%, and 146.13% improvement in terms of average resource utilization, meeting tasks deadlines, lower makespan, and task response time respectively as compared to the state-of-the-art tasks scheduling heuristics.

In the literature, a number of task scheduling and load balancing schemes have been proposed. However, the majority of these scheduling heuristics focus either on a single evaluation parameter (i.e., makespan or resource utilization, etc.) or multiple evaluation parameters individually as a scheduling objective. Improving one parameter may not guarantee an increase in the overall performance of the Cloud. There is a need to have such algorithms that focus on improving the overall performance of the Cloud by taking into account multiple evaluation parameters. The second part of this thesis attempts to present, an Overall Performance-based Resource Aware Dynamic Load-balancer (OG-RADL) for deadline constrained Cloud tasks. OG-RADL has the ability to distribute the workload of independent and compute-intensive tasks according to the resource computation capability at run time. Moreover, a novel normalization technique is proposed that overcome the limitations of existing normalization techniques. The OG-RADL enhance load-balancing, support deadline constrained tasks, and improve the overall performance gain of the Cloud. The experimental result shows that the proposed approach OG-RADL outperforms as compared to existing task scheduling algorithms named DLBA, DC-DLBA, Dy-MaxMin, RALBA, PSSELB, and MODE in terms of the overall performance of the Cloud.

The objective of the Cloud users is to lease optimal resources that meet their demand with minimum cost and time. A number of heuristics and meta-heuristics based approaches have been proposed in the literature. The majority of the existing state-of-the-art task scheduling heuristics optimize a single parameter or multiple non-conicting parameters like makespan, throughput, response time, etc. However, in the real Cloud scenario, most of the time Cloud users demand for multi-objective based conicting Quality of Service (QoS) requirements i.e., task execution time and cost. Therefore, there is a need for schedulers that can provide a balanced solution for conicting parameters. For this purpose, meta-heuristics based algorithms are considered more ecient to provide an optimized solution for conicting objectives. In this part of the thesis, a modi ed PSO based Resource and Deadline Aware dynamic Load-balanced (PSO-RADL) algorithm is proposed. PSO-RADL can provide an optimized solution for the workload of independent and compute-intensive tasks with reasonable time and cost. Experimental results reveal that the PSO-RADL has gained up to 66%, 162%, 56%, 89%, 98%, and 97% enhancement in terms of makespan, average resource utilization, task response time, meeting task deadline, penalty cost, and total execution cost respectively as compared to existing state-of-the-art tasks scheduling heuristics.

Download full paper