An adaptive task allocation technique for green cloud computing

Abstract

The rapid growth of todays IT demands reflects the increased use of cloud data centers. Reducing computational power consumption in cloud data center is one of the challenging research issues in the current era. Power consumption is directly proportional to a number of resources assigned to tasks. So, the power consumption can be reduced by a demotivating number of resources assigned to serve the task. In this paper, we have studied the energy consumption in cloud environment based on varieties of services and achieved the provisions to promote green cloud computing. This will help to preserve overall energy consumption of the system. Task allocation in the cloud computing environment is a well-known problem, and through this problem, we can facilitate green cloud computing. We have proposed an adaptive task allocation algorithm for the heterogeneous cloud environment. We applied the proposed technique to minimize the makespan of the cloud system and reduce the energy consumption. We have evaluated the proposed algorithm in CloudSim simulation environment, and simulation results show that our proposed algorithm is energy efficient in cloud environment compared to other existing techniques.

1 Introduction

Cloud computing has been developed as one of the creative platforms which give dependable, virtualized and adaptable cloud resources over the Internet. To utilize these resources, the cloud customers do not require any hardware or software infrastructure. They can lease the cloud resources on demand from any place on the planet just by spending for that utilized resources like electricity supply. The cloud user got these resources from the cloud service providers (CSPs) through laptops, PCs, mobile devices, etc. The CSP offers membership to the clients for different services like infrastructure as a service (IaaS), platform as a service (PaaS) and software as a service (SaaS).

Scheduling or allocation is the procedure of choosing how to submit resources to a variety of conceivable tasks. This allocation of resources is a basic and critical job for any business perspectives. The resource allocation in the cloud environment is carried out by the CSP. If the cloud resources are scheduled properly, then the effectiveness and performance of the system will be enhanced [1, 2]. Therefore, resource scheduling strikes a significant role in a system for getting successful and productive results. It increases throughput and also balances the computing load to avoid overloading and underloading [3]. This scheduling or allocation problem is a well-known NP-complete problem [4]. Therefore, suboptimal solutions are proposed for the allocation problem. Various researchers work on this scheduling problem by considering different objectives like energy consumption, resource utilization, makespan, load balancing, guaranteeing Quality of Service (QoS), enhancing throughput and Service Level Agreement (SLA) completion [1,2,3, 5, 6]. Here, in this work, makespan minimization is taken as primary objective along with the energy consumption of the system. Three crucial factors affect the task allocation in the cloud environments [7]. Those are waiting time in the task queue, execution time, and the relative performance of the off-premise cloud compared to the on-premise machines. The users could achieve the optimal turnaround time if they know the waiting time in the task queue, and the execution time in the cloud environment. However, this knowledge for the user is not available in advance. The problem of this work can be expressed as follows. Given a set of tasks, a set of virtual machines (VMs), and an arrangement of evaluations values in the form of an expected time to compute (ETC) matrix to demonstrate how well every VM can perform each task, such that the aggregate evaluations values are maximized [8, 19]. An ETC matrix has the expected execution time of all task one by one in different VMs. This ETC matrix introduces the heterogeneity of tasks as well as the resources (i.e., VMs). A single task can be executed in different VMs with different execution times which represent machine heterogeneity. Similarly, a single VM takes a different amount of time to execute different tasks that represent task heterogeneity.

Energy-efficient data centers address green cloud computing system. Green cloud is a new terminology in the computing world in which consolidation of user requests or cloud resources plays a significant role. The green cloud system has various distinct components such as the energy consumed for computation, communication and the physical infrastructure of a data center. To optimize the energy consumption of a cloud data center, either one can go for the allocation of user requests (tasks) to the existing finite set of VMs or can for the distribution of cloud resources (VMs) to a finite set of physical hosts. In this work, the mapping of a batch of tasks to VMs is performed. Among the three service models, the IaaS has a tendency to give a more fertile ground to reduce makespan as well as energy by task allocation.

Definition 1

(Makespan) Makespan is the maximum time required to complete a finite number of tasks by a VM among all virtual machines after allocation of tasks to VMs.

Definition 2

(Server availability) A physical server is available when the server has sufficient computing resources to host the required number of virtual machines.

Contributions: This work has the following key contributions:

• It presented a system model that includes a host model, virtual machine model and task model.

• It presented an adaptive allocation of tasks to virtual machines that adjust the execution time of tasks dynamically.

• It evaluated the effect of different scenarios for makespan and energy consumption of the cloud system.

• It provided a comparative analysis among our algorithm, baseline (random) algorithm and round Robin algorithm.

The remaining work is organized as follows: Sect. 2 discusses literature that focused on this problem and its solution. Section 3 discusses the problem statement along with some assumptions required for the system. The next section describes system model including task and resource model. Section 5 presents the proposed algorithm followed by a hand-tracing example. In Sect. 6, the evaluation of the algorithm is illustrated. Finally, we conclude our work with the future scope.

2 Related work

Research in the area of cloud computing attracted greater attention in the recent times due to the huge capabilities in the IT field. Task allocation in the cloud environment is one of the important research problems in order to optimize time, energy, cost, etc. [9]. In [1], Rimal and Maier have proposed an approach for the scheduling the workflow to minimize makespan, the task execution costs, and to use the idle cloud resources effectively. They have only considered the CPU-intensive task and dealt with both structured and unstructured workflow scheduling. They have compared their approach with the FCFS, EAST (Extensible Argonne Scheduling System) backfilling and minimum completion time scheduling policies.

Several states correspond to the different energy consumptions of the CPU, main memory and secondary storage. From the recent work, it is found that most processors support running state, idle state, sleep state and off state. In [12], Mills-Tettey et al. have explained the allocation problem with changing costs using bipartite graph where the edge cost varies. For the solution of their problem, they have used a dynamic Hungarian algorithm, and they have presented correctness proofs of the algorithm including its efficiency. In [13], a near-optimal solution of task assignment problem is proposed to maximize the cumulative profit or to reduce the energy cost of the cloud data center. They have compared their work with the random algorithm in the cloud environment. In [14], Penner et al. have presented an algorithm for task distribution that dynamically adjusts the costs based on the previous allocation. The goal is to provide load balancing and collocating task executions.

Beloglazov et al. [2] proposed an architectural framework and principles for green cloud computing. Their method includes architectural principles for energy-efficient management of clouds and energy-efficient resource allocation policies. In their work, the authors have validated their approach by a performance evaluation study using the CloudSim toolkit. A collaboration of optimization scheduling and estimation techniques with the power consumption in a cloud environment is shown in [3]. This technique improves the performance for green cloud computing. A randomized algorithm is proposed for task allocation [15] by reducing both time and space complexities. A middleware is proposed for performing a hybrid simulation of large-scale critical systems [16]. This middleware allows a multi-objective optimization approach to optimize the simulation task allocation on a private cloud.

To improve the performance of the cloud system and also to conserve energy consumption of the data centers, we propose an algorithm for the allocation of cloud tasks to the cloud resources. We found that the resource allocation using the round Robin and baseline (random allocation) algorithms is well accepted by a large number of researchers [20,21,22,23]. Hence, we have compared the performance of our proposed technique with these standard algorithms using simulation analysis. The random-based task allocation algorithm assigns tasks to VMs on a random basis without any constraint.

3 Problem statement

The assignment problem of a huge number of tasks to a finite number of VMs in the cloud environment is addressed as task allocation problem. There are n number of tasks $\{T_1, T_2,\ldots ,T_n \}$ and m number of VMs in the cloud system. The assignment of these n tasks to m VMs should be efficient so that the makespan, as well as the energy consumption of the system, is optimized. Makespan of the system is calculated from the Execution Time of Virtual machine (ETV) set.

$$\begin{aligned} \text {Makespan}\,(M) =M\text {ax}(\text {ETV}_{i}) \end{aligned}$$

(1)

Here ETV$_{i}$ represents the execution time of ith virtual machine. Our objective is to minimize M as in Eq. (1). Another important performance parameter is energy consumption of the cloud system to execute a finite number of heterogeneous tasks.

The energy consumption of the system is calculated by adding the energy consumption of individual VMs using Eq. (2).

$$\begin{aligned} \text {Energy consumption}\,(E)=\sum \limits _{i=1}^m E_i \end{aligned}$$

(2)

Here $E_{i}$ is the energy consumption of ith VM, $1 \le i \le m$. A virtual machine can be in one state, i.e., active or idle. So, to calculate the energy consumption of a VM, both active and idle state energy consumptions are added. The idle state time of a VM is calculated by subtracting the active state time from the makespan of the system. $A_{i}$ Joules/Million Instruction (J/MI) is the energy consumption of ith VM in an active state, and $I_{i}$ J/MI is in an idle state. The energy consumption of a VM in idle state ($I_{i})$ is 60% of $A_{i}$ [5]. The energy consumption of a virtual machine mainly depends on the speed (Million Instruction Per Second, MIPS) of the VM as in Eq. (3) adopted from [10, 11] and (4).

$$\begin{aligned} A_i= & {} 10^{-8}\times \left( {\text {MIPS}_i } \right) ^{2}\,\text {J/MI} \end{aligned}$$

(3)

$$\begin{aligned} I_i= & {} 0.6\times A_i\,\text {J/MI} \end{aligned}$$

(4)

Energy consumption of all VMs is required to calculate the total energy consumption of the system (E) by using Eq. (5).

$$\begin{aligned} E_{{i}} =\text {ETV}_i \times A_i +\left( {M-\text {ETV}_i } \right) \times I_i \end{aligned}$$

(5)

Fig. 1

Two bipartite graphs with eight tasks and four VMs

Table 1 ETC matrix of eight tasks and four VMs

Let say G = {T, V, E} be a bipartite graph as shown in Fig. 1, T the set of tasks, V the set of VMs and E the set of edges that represent the allocation.

It assumes a matrix edge cost, ET $C_{ij}, 0 \le i \le n, 0 \le j \le m$, where n is the total number of tasks and m is the total number of VMs. Missing edge has a higher ETC value, i.e., infinity as illustrated in Table 1. If a task cannot be assigned to a VM, then we make the corresponding ETC value as infinity ($\infty$).

3.1 Assumptions

Virtualization technology supports the creation of multiple VMs on any of the possible host. The workload submitted to the cloud is considered to be in the form of tasks. The scheduler allocates the tasks to VMs of different hosts for execution. In order to solve the task allocation problem in the cloud environment, we have considered the following assumptions.

• Each task is assigned to a single virtual machine.

• Tasks cannot be preempted once they begin to execute on a VM.

• When a VM executes a task, there are no priority distributions between the tasks with the VM.

• A VM cannot remain idle when the tasks are in the waiting queue of the VM.

• Each VM has a single core.

• There is no failure of VM during execution of tasks.

• The tasks are independent in nature.

4 System model

In this section, we present a scheduling model for a cloud data center along with the task model and VM model in a cloud data center. The scheduling model of a cloud data center where the CSP schedules the task of users to the cloud resources is shown in Fig. 2. Here, we have an assumption that the cloud system has enough resources to provide services to the cloud user. The cloud users ($\text {User}_1, \text {User}_{2}, {\ldots }, \text {User}_{n}$) submit their tasks to the CSP, and all tasks ($T_{1}, T_{2}, {\ldots }, T_{n})$ are in a task queue. The task classifier classifies all tasks into a CPU-bound task set, urgent CPU-bound task set, IO-bound task set, urgent IO-bound task set, and all classified tasks are submitted to the respective task queue. CPU-bound tasks and urgent CPU-bound tasks are submitted to the SCHEDULER1, and the tasks are allocated among x number of CPU-bound virtual machines ($\text {CV}_{1}, \text {CV}_{2}, {\ldots }, \text {CV}_{x}$). Similarly, all IO-bound tasks and urgent IO-bound tasks are submitted to the SCHEDULER2, and the tasks are allocated among y number of IO-bound virtual machines ($\text {IV}_{1} , \text {IV}_{2}, {\ldots }, \text {IV}_{y}$). Both schedulers schedule the urgent tasks first, and if the urgent tasks queue is empty, then they assign regular CPU-bound and IO-bound tasks to the respective VMs.

4.1 Task model

In the cloud environment, a large number of cloud users submit their independent tasks to the cloud service provider and access services from the cloud without understanding the system infrastructure. The tasks are heterogeneous in terms of length of the tasks and resource requirement of the tasks. There are n (finite) number of tasks, and the set is $T = \{T_{1}, T_{2}, {\ldots }, T_{n}\}$. Each task ${T_i}, 1 \le i \le n$ has five tuples, i.e., ${{T_i}} = \{W_{i}, \text {CPU}_{i}, M_{i}, \lambda _{i}, R_{i}\}$, where $W_{i}$ is the workload of service $T_{i}$ in terms of MI, CPU$_{i}$ is the CPU time required for the service $T_{i}, M_{i}$ is the main memory requirement for the service $T_{i}, \lambda _{i}$ is the bandwidth requirement of service $T_{i}$ and $R_{i}$ represents the task type. $R_{i}$ value is 0 if $T_{i}$ CPU-intensive, 1 if $T_{i}$ urgent CPU-intensive, 2 if $T_{i}$ IO-intensive and 3 if $T_{i}$ urgent IO-intensive.

Fig. 2

An adaptive scheduling model for cloud system

4.1.1 Resource model

A cloud system can be developed from a single data center or from multiple data centers according to the resource requirement. To consider a general cloud system model, the data center set D has p number of data centers, i.e., $D = \{D_{1}, D_{2},{\ldots }, D_{p}\}$. Each data center has numerous hosts (and the set of hosts on ith data center is $H_{i} = \{H_{i1}, H_{i2}, {\ldots }, H_{i|Hi|}\}$) in the cloud environment. Each host $H_{ij}, 1 \le i \le p, 1 \le j \le {\vert }H{\vert }$ can be modeled as six tuples, i.e., $H_{ij} =\{\text {PE}_{ij}, S_{ij},M_{ij},\text {SS}_{ij}, \lambda _{ij}, \text {VMM}_{ij}\}$, where

• $H_{ij}$ represents jth host of ith data center.

• ${PE}_{ij}$ is the number of processing elements or cores of $H_{ij}$.

• $S_{ij}$ is the processing speed of $H_{ij}$ in terms of MIPS.

• $M_{ij}$ is the host main memory size of $H_{ij}$.

• ${SS}_{ij}$ is the secondary memory size of $H_{ij}.$

• $\lambda _{ij}$ is the total bandwidth provided to $H_{ij}$.

• ${\text {VMM}}_{ij}$ is the Virtual Machine Manager (VMM) running on the host $H_{ij}$.

One of the major advantages of cloud system is virtualization of cloud resources. This virtualization mechanism provides flexibility of partitioning the resources of the host into various virtual machines. A VMM, which is running on a host, is mainly responsible for the maintenance of all VMs on that host. Each host $H_{ij}$ has finite number of virtual machines (and the set of VMs on jth host of ith data center is $V_{ij} =\left\{ {V_{ij,}^1 V_{ij,}^2 \ldots ,V_{ij}^k } \right\} )$. Each VM has five tuples, i.e., $V_{ij}^k =\left\{ {\text {PE}_{ij,}^k S_{ij,}^k M_{ij,}^k \text {SS}_{ij,}^k \lambda _{ij}^k } \right\}$.

• $V_{ij}^k$ represents kth VM running on jth host of ith data center.

• $\text {PE}_{ij}^k$ is the number of processing elements or cores of $V_{ij}^k$.

• $S_{ij}^k$ is the processing speed of $V_{ij}^k$ in terms of MIPS.

• $M_{ij}^k$ is the main memory size of $V_{ij}^k$.

• $\text {SS}_{ij}^k$ is the secondary memory size of $V_{ij}^k$.

• $\lambda _{ij}^k$ is the total bandwidth provided to $V_{ij}^k$.

5 Proposed task allocation algorithm

This section discusses the details of the proposed scheduling algorithm, and the purpose is to reduce the overall energy consumption by minimizing the makespan of the system. For Algorithm 1: Adaptive Task Allocation Algorithm (ATAA), the ETC matrix of all tasks of a queue is provided as input. There are four queues for the task because of four type of tasks as shown in Fig. 2. Therefore, the ATAA algorithm is applied for all four-task queues. The ETC matrix has the completion time of tasks on all virtual machines according to the type of tasks. The output of ATAA algorithm is ET vector, which has time required by all VMs. Initially, the time required by all VMs, ET is set to zero. The tasks are allocated to the cloud resources (VMs) batch-wise. Batch size of the tasks is same as the total number of VMs. To allocate one batch of tasks, a portion of ETC matrix is required, i.e., BETC. This BETC is modified by adding the previous execution time of corresponding VM and forms the modified ETC (METC) matrix. In RowUpdate, the smallest element of each row is subtracted from the elements of that row. In ColumnUpdate, the smallest element of each column is subtracted from the elements of that column. Then, the Assigned METC subroutine is called after which the allocation of tasks is determined by using the marking procedure.

The marking will be done for the elements row-wise first and if required then go for column-wise. If a single 0 is present in a row, then mark that 0 as gray color and strike all 0’s across the corresponding column. Similarly, for each column, we follow the same marking procedure as performed for the row. If the allocation is successful, then the ET vector is updated according to the allocation of a batch of tasks. If the allocation is not possible (or step 14 of ATAA algorithm is not satisfied), then Update METC subroutine is called which updates the C_METC matrix by using ticking procedure. Here, we tick all unassigned rows (i.e., the row with no marked zeros). If the ticked rows have a 0, then tick the corresponding columns, and if the ticked column has an assignment (i.e., marked zeros), then tick the corresponding rows. This ticking procedure will repeatedly be continued until no more ticking is possible. After that, lines are to be drawn through unticked rows and ticked columns. The smallest number ($\theta$) of the matrix that has no lines passing through is subtracted from the elements of the matrix that have one line passing through and add the $\theta$ value to the matrix elements that have two lines passing through. The updated METC matrix is returned to Algorithm 1, where again Algorithm 2 is called for the marking procedure. Then, again step 4: Assigned_METC subroutine is called and repeat this procedure till we have a successful allocation.

If the total number of tasks is n and the total number of VMs is m, then the loop started in step 4 of Algorithm 1 will run for $n=m$ times. Their inner loops, as well as subroutines, will run at most for $O(m^{2})$ times. Therefore, the time complexity of the allocation result after performing the ATAA algorithm is O(mn), $m \ll n$. Because the time complexity of Algorithm 2 and Algorithm 3 is $O(m^{2})$ which are called from Algorithm 1. Therefore, the time complexity of ATAA algorithm is $O(( n/m) \times (m^2+m^2+\ldots +k\, \text {times})) = O(mn), where\, k$ is an integer constant. The time complexity of the basic Hungarian algorithm for solving assignment problem is $O(n^{3})$ [12], which is larger than the time complexity of ATAA, i.e., $O(n^{2}) > O({mn})$.

5.1 Example

The explanation of the example will carry from the ETC matrix as shown in Table 1. There are eight tasks, and we have to allocate those tasks to four VMs so that the makespan is minimum. For this example, we consider four as the batch size of the tasks, which is same as the number of VMs. So, Table 1 is split into Tables 2 and 4. The step-by-step solution of the allocation problem for the given example is explained below with the corresponding remark (Table 3).

Table 2 ETC matrix of four tasks and four VMs

Table 3 Description of allocation problem for Table 2 data

Table 4 ETC matrix of four tasks and four VMs

Table 5 Description of allocation problem for Table 4 data

Table 4 has four tasks (T5 to T8) of Table 1 and is represented as BETC. Before allocation of tasks to the cloud resources (VMs), the addition of previous execution times of all VMs will be done and the updated matrix is shown in the second row of Table 5. The RowUpdate and ColumnUpdate methods are performed (Algorithm 1). As C_METC [1, 3] contains a single unmarked 0, that particular cell is colored as gray, and the striking operation is done on all the 0’s in the corresponding rows and columns. The marking operation is accomplished using column value also. In this case, we can mark C_METC [1, 4] and colored it as gray. Still, this algorithm (Algorithm 2) is not able to mark 0’s for each row and column. Therefore, we follow another procedure as stated in Algorithm 3. Primarily, tick all unassigned rows (rows 2 and 3) and the corresponding column (column 3) where 0 is present. If there is a marked 0 present in that particular column, then tick that row too (row 1). The next step of the algorithm allows crossing a line between the unticked rows and ticked columns. As shown in Table 5 (seventh row), we have colored the lines as light gray. Select the smallest number ($\theta$) in the matrix that has one line passing through it. Here, the smallest number is 1. Then, subtract the $\theta$ from the elements of the matrix that have no lines passing through it and add the particular to those two lines passing through it. After doing this, the updated matrix shown in Table 5 (eighth row) is obtained. Then, apply Algorithm 2 to this updated matrix as shown in the ninth row of Table 5. Then, we get the successful allocation result along with the execution time of each VM.

Fig. 3

Makespan comparison as shown in Scenario 1

6 Evaluation of the algorithm

The CloudSim 3.0.3 simulator is used to simulate the service allocation problem using the ATAA algorithm. The CloudSim simulator provides a generalized simulation framework for modeling purpose, simulation purpose and experimenting purpose in the cloud infrastructure [17, 18]. Let TH and MH represent task heterogeneity and machine heterogeneity, respectively. In this paper, we have adopted the range-based ETC generation algorithm [19]. The ETC matrix for simulation is formed by employing two uniform distributions $U{ (}1, \text {TH}{ )} \text { and } U{ (}1, \text {MH}{ ) }\text { and are realized as:} 1 + { (}\text {TH}- 1{ )} \times \text {rand}{ (}1{ )} \text { and } 1 + { (}\text {MH} - 1{ )} \times \text {rand}{ (}1{ )}$, where rand() function generates a value within (0, 1). For the ETC matrix generation, we have used $\text {TH}= 1000$ and $\text {MH}= 50$, respectively. We have compared the proposed algorithm with the baseline algorithm (where the allocation performed randomly, which means any task can be allocated to a VM with $1=m$ probability) and with the Round-Robin algorithm (which is the default scheduling algorithm in the CloudSim simulator). We have considered makespan and energy consumption of the system as performance metrics to evaluate the algorithm.

For the simulation purpose, we have considered a single data center with multiple heterogeneous hosts and ‘Xen’ as VMM. We have estimated tasks and resources with diverse requirements as the environment support for heterogeneous system modeling. The key properties of the elements for the simulation are:

• Speed of VM (MIPS) : 200, 400, 500, 800, 1000, 2000, 4000, 5000, 8000, 10,000;

• Main memory size (RAM) : 512, 1024, 2048, 4096, 8192, 16,384;

• We also varied the secondary storage size;

We have examined the performance of the cloud system in two different scenarios as follows.

Scenario 1

In this scenario, the number of virtual machines is fixed, i.e., 40, and the number of tasks varies from 100 to 1000 in the interval of 100. The makespan of the system is determined for each set of tasks (for all three algorithms), and the energy consumption is calculated. The comparison graph for this scenario is shown in Fig. 3 (makespan), and Fig. 4 (energy consumption).

Fig. 4

Energy consumption comparison as shown in Scenario 1

Fig. 5

Makespan comparison as shown in Scenario 2

Fig. 6

Energy consumption comparison as shown in Scenario 2

Scenario 2

In this scenario, the number of tasks is fixed, i.e., 500, and the number of VMs varies from 20 to 60 in the interval of 5. Here, also the makespan and energy consumption are calculated. The comparison graph for this scenario is shown in Fig. 5 (makespan) and Fig. 6 (energy consumption).

The makespan of the system increases when the number of input tasks increases for a fixed number of VMs as shown in Fig. 3. The makespan value is more when the number of VMs is less as displayed in Fig. 5. This makespan value is gradually reduced as the number of VMs increases as presented in the bar chart (Fig. 5). The energy consumption of the system increases rapidly when the number of tasks increases with a certain number of VMs as shown in Fig. 6. However, the energy consumption of the system increases slowly when the number of VMs increases as shown in Fig. 6. Here, the energy consumption rate is slow due to fixed number of tasks.

7 Conclusion

This paper incorporates a detailed evaluation of the system framework toward the resource distribution and task allocation in the cloud computing system. In this paper, we have proposed a novel task-scheduling algorithm ATAA in the cloud environment. We presented a system model including task model and resource model (includes host model, VM model) for the cloud environment. Due to the importance of urgent CPU-bound tasks and urgent IO-bound tasks for the proposed method, the percentage of execution of tasks before the deadline (i.e., one of the SLA constraints) is much more, i.e., a higher rate of execution achieved. The work in this paper also addresses the heterogeneity with the help of ETC matrix. A hand-traced example of the algorithm for given ETC is discussed which shows the basic steps of the algorithm. The principle of mathematical modeling is taken into consideration to evaluate the performance of the proposed allocation technique. The simulation results for the comparison of algorithms result in favor of ATAA algorithm. This finding can further lead to the dynamic form of resource allocation algorithms that permit preempted tasks according to a supplied priority.