Dynamic Backfilling Algorithm to Increase Resource Utilization in Cloud Computing

Dynamic Backfilling Algorithm to Increase Resource Utilization in Cloud Computing

Suvendu Chandan Nayak (Veer Surendra Sai University of Technology, Burla and C. V. Raman College of Engineering, Bhubaneswar, India), Sasmita Parida (C V Raman College of Engineering, Bhubaneswar, India), Chitaranjan Tripathy (Veer Surendra Sai University of Technology, Burla, India) and Prasant Kumar Pattnaik (School of Computer Engineering, KIIT University, Bhubaneswar, India)
DOI: 10.4018/IJITWE.2019010101


In this article, the authors propose a novel backfilling-based task scheduling algorithm to schedule deadline-based tasks. The existing backfilling algorithm has some performance issues in comparison with the number of task scheduling in OpenNebula cloud platform. A lease could not be scheduled if it is not sorted with respect to its start time. In backfilling, a lease is selected in First Come First Serve (FCFS) to be backfilled from the queue in which some ideal resources can be found out and allocated to other leases. However, the scheduling performance is not better if there are similar types of leases to backfill. It requires a decision maker to resolve conflicts. The proposed approach schedules the number of tasks without any decision maker. An additional queue and the current time of the system is implemented to improve the scheduling performance. It performs quite satisfactorily in terms of number of a leases scheduling, and resource utilization. The performance result is compared with the existing backfilling algorithms.
Article Preview

1. Introduction

With rapid developments in cloud computing, a timely and important challenge is resource utilization. In cloud computing, a pool of resources is provided for the users to run their applications according to “pay per use”. However, the physical resources are limited in the capacity of CPU, memory, storage space, I/O devices, bandwidth and much more for the data center. The exact amount of resources should be provided to the user on demand, which avoids over-utilization and under-utilization (Zhang, Huang, & Wang, 2016). The idea of resource management is to utilize the resource as much as possible. The resource utilization can be achieved by implementing better task scheduling in cloud computing (Arabnejad, Barbosa, & Prodan, 2016). The challenges of resource utilization, direct us towards better task scheduling algorithms. In cloud computing, every data center contains multiple physical machines (PMs). In a single PM different virtual machine (VM) is created as per the user request for computing applications (Mustafa, Nazir, Hayat, ur Rehman Khan, & Madani, 2015). Moreover, the user requests may have different parameter constants, like different start time, execution time, number of nodes (Number of VMs) and deadlines (Nayak & Tripathy, 2016).

Different open source software cloud toolkits are used by cloud service providers to manage data centers and clouds. The OpenNebula is one of the popular open source cloud toolkit (Carlo, 2011; Parida, Nayak, & Priyadarshi, 2018). The Haizea is a lease manager used in the OpenNebula. It accepts user requests as a lease. Haizea, the scheduler supports different kinds of leases as: Best-effort lease, Advance reservation-style leases (AR) and Immediate lease (Borja Sotomayor, Montero, Llorente, & Foster, 2009a). When a best-effort lease is associated with a deadline, it is considered as a Deadline sensitive lease (Nathani, Chaudhary, & Somani, 2012; Nayak & Tripathy, 2016).

In a best-effort lease, the resources with different configurations are allocated as soon as they are available. There is no time limit to allocate resources for this type of lease. But if a time is associated with the best-effort lease to avail resources, it is considered as a deadline sensitive lease. The deadline sensitive lease should be scheduled within the deadline. In cloud computing, VMs are allocated as resources to lease. The creation of a VM is limited to a physical machine (Byun, Kee, Kim, & Maeng, 2011; B Sotomayor, Montero, Llorente, & Foster, 2008).

The Backfilling algorithm (Feitelson, 2005) is an optimized FCFS algorithm. It is used in Open Nebula to schedule the deadline sensitive leases. In backfilling algorithm all leases should be sorted according to their start time (ST). A new lease cannot be executed unless it is sorted according to its start time in the queue. Moreover, a lease is selected on FCFS among the similar leases to backfill (Nathani et al., 2012; Parida, Nayak, & Tripathy, 2015). Due to this selection procedure of the lease, some other leases are rejected and could not able to meet their deadline, even if there are sufficient resources (Nayak & Tripathy, 2016).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 14: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 13: 4 Issues (2018)
Volume 12: 4 Issues (2017)
Volume 11: 4 Issues (2016)
Volume 10: 4 Issues (2015)
Volume 9: 4 Issues (2014)
Volume 8: 4 Issues (2013)
Volume 7: 4 Issues (2012)
Volume 6: 4 Issues (2011)
Volume 5: 4 Issues (2010)
Volume 4: 4 Issues (2009)
Volume 3: 4 Issues (2008)
Volume 2: 4 Issues (2007)
Volume 1: 4 Issues (2006)
View Complete Journal Contents Listing