Cost-Aware Task Scheduling in Cloud Computing Environment

Published Online May 2017 in MECS

Cloud computing appeared as a new generation allowing the users to use the computational resources and various services in cloud environment. Self-service provisioning provided by cloud computing offers the users by deploying their own computing resources. The services in cloud computing are divided into three main types of services: Software as a Service (SaaS), Platform as a Service (PaaS), and Infrastructure as a Service (IaaS) [1]. The software as a service provides the software for the user, in other words, the user can use the required software/application rather than buying it all the time. The platform as a service provides platform service for users to run the application and check the output. The infrastructure as a service provides infrastructure service in virtual platform for the user to achieve various virtual kinds of work, like processing, storage, servers etc. [2].

In cloud computing, the users can access the services on any device, anytime and anywhere [3]. Cloud computing helps users to pay only for what they need from computing resources. These services are provided over the internet where the paid model is based on the principle of pay as you use. Whether we recognize it or not, we are most likely already using cloud-based services. YouTube and Google are two recognized companies which introduced cloud-based software as a free and on-line service to billions of users. Google, for example, hosts a collection of online productivity tools and applications in the cloud computing environment [4].

The main distinction between cloud computing and other techniques is the virtualization technology. The virtualization technique plays an important role in cloud system to manage the resources’ hardware [3].

In virtualization, various virtual machines (VMs) can be created and run on a single physical machine by sharing the resources for all VMs [5]. The virtual machine executes the mapped tasks and meets the Quality of Service (QoS) constraints where the aim of QoS is to minimize the cost of processing a task based on user budget constraint [6]. The service provider needs huge returns on investment. The broker serves as a mediator between user and Cloud Service Provider (CSP) in cloud computing. It determines where to assign the task sent by the user to the resources offered by the service provider [7]. To satisfy user’s requirements and utilize resources efficiently, we should use the most efficient task scheduling and load balancing strategies [8]. Cloud computing differs from distributed environment computing (cluster and grid), where task scheduling on the cloud environment is complicated. There are many types of resources with various performance parameters, differentiated cost, in addition to deadline and budget constraints [9]. The function of task scheduling strategy is to map the tasks to the resources, while the function of load balancing strategy is to balance the loads between resources in the cloud computing system. Both these strategies work together to achieve integrity in cloud computing. Task scheduling in cloud computing has two steps. First step involves provisioning resources while the second step involves sending the tasks to the suitable resource for execution [10].

Moreover, cost is a big challenge for scheduling tasks in cloud computing. The cost of each resource like CPU, memory, storage, etc., should be calculated [11].

In cloud computing, the resources are heterogeneous at different data centers. So, classical scheduling algorithms such as FCFS, shortest job first and priority etc., are not recommendable. Some effective scheduling techniques are required which can optimize and enhance the overall performance of scheduling algorithm. The scheduling algorithm should provide user satisfaction at the end [7].

The main contribution of this paper is to examine how to reduce the cost of task execution time, memory, bandwidth, and storage based on task priority while processing tasks in several virtual machines by ensuring estimated finishing time to be as less as possible.

This paper is divided into the following sections. The related work is presented in section two. Section three presents the proposed approach. In section four, the result of experiments is illustrated. Evaluation performance is shown in section five. Finally, the conclusion is provided in section six.

• II.    Related Work

Nowadays, there are plenty of scheduling algorithms, each one had its own constraints that used to efficiently schedule the task on the resources. For example, Selvarani and Sadhasivam [12] concentrated on scheduling groups of tasks in cloud computing when resources have different cost and computation performance. The scheduling method employed an enhanced scheduling algorithm based on the cost for an effective mapping of tasks to the resources in order to enhance the ratio of computation and communication.

In addition, Ruben et al. [13] tackled this problem by proposing a set of heuristics to cost-effectively schedule deadline-constrained computational applications on both private infrastructure and public cloud providers. The heuristics took into consideration the transfer and computational cost of each data in addition to data transfer times

Gaurav Raj and Sonika Setia [14]. proposed an efficient communication scheme between broker and VMs for assigning the task. The optimum time and cost could be obtained by utilizing Broker Virtual Machine Communication Framework (BVCF). Scheduling over virtual machine and tasks and Retransmission of those tasks was the major point of the proposed work. The execution of tasks was analyzed over Round Robin and FCFS scheduling policies.

In addition, Yogita and Mansi [15] depended on task scheduling policy for making efficient sending of tasks to available resources in cloud computing system. Their objective was to add cost based task scheduling, which benefits the user and dynamically optimized policy of resource allocation that is beneficial to the service provider. In addition, it enhanced communication, computation ratio, and utilization of resources available based on combining the user tasks before resource allocation.

Sheeja and Jayalekshmi [16] proposed an algorithm to balance the load in VMs efficiently by distributing the tasks between the VMs based on the foraging behavior of honey bees. If there were more than one under-loaded virtual machines, the most cost-efficient one was selected using Pareto dominance strategy. The result of this algorithm seemed efficient when evaluated with existing algorithms and it also decreased the cost of using virtual machine instances. While at the same year, Gang Zhao [17] proposed PSO modification algorithm to solve the scheduling of tasks problem in cloud computing. They quantified the cost of resource usage by a cost-aware fitness function, along with the fitness service for time cost, with the objective of decreasing both the time of the process and the resource utilization. Therefore they could reach a global optimal solution. The simulated cloud computing environment showed the effectiveness of their proposed algorithm.

In 2015, there were an enhancement as at [11] Nidhi Bansala et al. proposed QoS-driven scheduling to compute the cost of the task, then evaluated it with conventional task scheduling algorithm in cloud computing system. The results of QoS algorithm achieved good performance using the cost parameter.

Another recent novel algorithm in 2015, Verma and Kaushal [18] proposed Bi-Criteria of Priority according to Particle Swarm Optimization (BPSO) policy to schedule workflow tasks. The comparison and simulation were done with state-of-art algorithm. The result of the simulation proved that the extended BPSO algorithm has reduced the implementation cost of schedule as compared to the state-of-art algorithm based on the same deadline and budget constraints taking into account the exiting load of the resources. Furthermore in 2016, Moïse and Chou [19] solved cost optimization problem for scheduling DAGs on an infrastructure as a service cloud computing. They proposed optimal and heuristic scheduling policies and compared across a variety of DAGs using the price model from EC2.

The results of cost-aware heuristic algorithm when compared to other cost-oblivious DAG schedules that aim to reduce makespan or resource utilization, showed that it minimized cost by 20–50 % and achieved a cost within x1.16 of the optimal one.

• III.    Propsed approach

Cloud computing environment consists of many heterogeneous resources called data centers, which include a number of hosts (servers) that have several characteristics, where each host has a number of VMs with various configurations (CPU, memory, bandwidth and storage). The requests will be sent to resources from the user by the service provider. The service provider serves these requests with efficient algorithms. The service provider executes tasks in virtual machines using scheduling algorithms that are available on resources. In this proposed approach, we used two clusters with different configuration based on speed: fast speed cluster and slow speed cluster. The clusters have several VMs with different costs. These VMs are independent and parallel processing. The user requests are represented by a group of independent tasks T=T1, T2, T3,…..Tn.

In this paper, we used many abbreviations. Table 1

shows all the abbreviations used in our proposed approach.

Table1. Abbreviations used in the Proposed Approach.

Symbol	Explanation
VM	Virtual machine
VM L	Virtual machine load
DC	Data center
TL	Total Length task
Pe e num	Process element number
Pe • e mips	Process element million instructions per second
EFT	Estimated finishing time
Cost C	Total cost of CPU consumption
Cost R	Total cost of RAM consumption
Cost B	Total cost of bandwidth consumption
Cost S	Total cost of storage consumption
Fit	File input task
Fot	File output task
Cost CPU	Cost of the CPU resource
Cost RAM	Cost of the RAM resource
Cost Bw	Cost of the bandwidth resource
Cost Storage	Cost of the storage resource
C (VM)	Capacity of VM

The main idea in our approach is as illustrated in Fig. 1. The tasks are checked based on the priority where the users submit tasks to the resources of CSP that should be implemented based on user budget (task priority). The CSPs have several heterogeneous resources, whereas each resource has its cost and configuration. The SCA determines which virtual machine will consume less estimate finish time and cost for the execution of the tasks by checking task priority, so as to achieve load balancing between VMs clusters. The tasks will be distributed among the suitable virtual machines in clusters according to the following steps. Initially, the load is calculated in VMs based on Equation (1). Tasks priority are checked and the tasks with low priority will be sent to slow speed cluster, while the tasks with high priority will be sent to fast speed cluster. Then, the tasks are mapped to the VM that has less estimation finish time based on Equation (2). This step will obtain balancing between VMs being loaded into a cluster. VMs’ load is updated. Finally, the total cost of all resources is calculated using Equations (3), (4), (5), (6) and (7).

Calculate the load on VM [20] based on Equation (1).

n TL

VM Load (VM,) = ^=1—-

^{_          L}    C ( VM )

Where: C (VM) = is the Capacity of VM, it refers to Pe _num *Pe _mips . Pe _num is defined as number of process elements allocated, while Pe _mips is the amount of million instructions per second, TL is total task length.

Then, we calculate the estimated finishing time of the present task [21] on VMs cluster based on Equation (2).

Estimated Finishing Time (EFT) = VM_L + TL_r   (2)

Where: VML is VM load, TL total length of present task.

Calculate the total cost of processing (CPU) [22] for mapped tasks in each cluster resource (Slow, Fast) by using Equation (3).

n cost =     (        *Cost )

C  i"1=1 C(VM)

Then we calculate the total cost of RAM, bandwidth and storage of VM based on Equations (4), (5) and (6).

CostR = 2 n = 1((fit, + M ) * cosIram, )

CostB = 2 n = 1 ((fit, + fot,) * CostBw,)

Costs = 2 n = 1(( fit, + fot, )* Coststoragej)(6)

The total cost of all resources can be obtained by Equation (7).

Total cost= (Costc + CostB + CostR + Costs )

The algorithm of the proposed approach is:

Algorithm: Scheduling Cost Approach based on Cost

Priority (SCA)

Input: Set the available resources and unmapped tasks

Output: Show the consuming cost of all resources

Classify the resources into two clusters based on Capacity (speed) as follows:

For i =1 To m number of resources

If Capacity of VM i = low (low = 2000 C(VM)) Classify VM i as slow speed

If Capacity of VM i = high (high =2500 C(VM)) Classify VM i as fast speed

End for

For each task cost priority list

• -     if cost priority is low

• -       Send task to slow speed cluster

• -     if cost priority is high

• -       Send task to fast speed cluster

Each cluster receives task:

• 2    Calculate the load of VMs based on Equation (1). Calculate estimation finish time of task in each VMs cluster based on Equation (2).

Assign task to VM j with less estimation finish time End for

• 3    Calculate the cost of processing task based on Equations (3), (4), (5) and (6).

• 4    Calculate the total cost based on Equation (7).

  

  Fig.1. Proposed Approach of SCA

  
  

The main idea of SCA is to minimize the cost of resources that execute task by grouping the tasks into various categories based on user budget satisfaction (user cost priority) and then sending each group to different clusters. To achieve load balancing, we calculate the estimation finish time of the task in each VMs in a cluster and sending the task to VM that has less finish time.

• IV.    Experimental Results

For modelling and evaluating algorithms, the researchers are using CloudSim [23]. CloudSim is a simulation toolkit that supports modeling and simulation of virtualized cloud-based data center environments. [24].

The users submitted the tasks in CloudSim and categorized it into various tasks. The tasks are sent for scheduling through scheduling algorithm. Next, the user tasks with corresponding virtual machine are bound through the Data center Broker. The tasks are then run on the virtual machines [25]. In this work, experiments are operated in a simulation framework. Tasks are grouped into the VMs cluster in SCA manner. Each task will be assigned to the cluster type based on the cost priority (high, low).

The virtual machines are grouped into two clusters, one group as a slow cluster, while the other group as a fast cluster. We conducted six experiments for each algorithm. We implemented 75, 150 and 225 tasks on 4 VMs and 450, 525 and 600 tasks on 8 VMs.

Table 2 summarizes the distributed tasks on clusters in each experiment.

Table 2. Number of tasks executed in each cluster

Experiments	No. of Tasks	Slow speed cluster	Fast speed cluster
1	75	46	29
2	150	63	38
3	225	140	85
4	450	280	170
5	525	328	197
6	600	375	225

Fig. 2 shows the number of tasks loaded into virtual machines in clusters.

Fig.2. Number of tasks into VMs Clusters

• V.    Performance Evaluation

Performance evaluation of our approach was conducted using six experiments with the same tasks in the same VMs. We evaluated and compared our proposed SCA with FCFS and SJF algorithms. The summarized result in Table 3, shows that our algorithm has better results by minimizing the total cost of CPU processing for all experiments than the other algorithms.

Table 3. Comparing total cost of CPU

Experiments	No. of Tasks	Total cost of CPU
		SCA	FCFS	SJF
1	75	11427	13725	14100
2	150	23525	27117	27462
3	225	35440	41030	40925
4	450	69952	82184	81539
5	525	81178	95560	95425
6	600	92595	109619	108645

We can observe from Fig. 3 that the performance of SCA is better in all experiments associated with the total cost of CPU than the other algorithms.

Fig.3. Total cost of CPU

The comparison of total cost of RAM is illustrated in Table 4 and Fig. 4. In all experiments, the performance of SCA is better than other algorithms.

Table 4. Comparing total cost of RAM

Experiments	No. of Tasks	Total cost of RAM
		SCA	FCFS	SJF
1	75	1161	1242	1242
2	150	2313	2475	2475
3	225	3465	3708	3708
4	450	6930	7425	7425
5	525	8073	8658	8658
6	600	9225	9900	9900

Fig.4. Total cost of RAM

Table 5 summarizes the results of all the implemented experiments and shows that SCA minimizes the total cost of bandwidth compared to FCFS and SJF.

Table 5. Comparing total cost of bandwidth

Experiments	No. of Tasks	Total cost of bandwidth
		SCA	FCFS	SJF
1	75	14220	15840	15840
2	150	28260	31500	31500
3	225	42300	47160	47160
4	450	84600	94500	94500
5	525	98460	110160	110160
6	600	112500	126000	126000

From Fig. 5 we observed that the performance of SCA is better in reducing the total cost of bandwidth than the state of the art scheduling algorithms.

Also in Table 6, the SCA achieves better performance in the total storage costs than the other algorithms, it is also clearly shown in Fig. 6.

Table 6. Comparing Total Cost of Storage

Experiments	No. of Tasks	Total cost of storage
		SCA	FCFS	SJF
1	75	1074	1128	1128
2	150	2142	2250	2250
3	225	3210	3372	3372
4	450	6420	6750	6750
5	525	7482	7872	7872
6	600	8550	9000	9000

Obviously, the total cost of our SCA approach for a variety of tasks processing efficiently satisfies the user budget satisfaction as summarized in Table 7.

The results in Fig. 7, shows the observed improvement achieved by SCA of the total cost of all resources of VM in all the experiments. The results of our proposed approach are significantly better than the FCFS and SJF.

Table 7. Comparing Total cost of all Resources

Experiments	No. of Tasks	Total cost of all resources
		SCA	FCFS	SJF
1	75	26808	30807	31182
2	150	54098	61092	61437
3	225	80950	91898	91457
4	450	161482	183464	184109
5	525	187711	214243	214378
6	600	214320	244545	245519

Exo 1 75 Ехо^15О ВП3 25 Ехо* *50 ВО-5 525 ЕХ0.6 6СО

NO OtTSSKS

Fig.7. Total cost of all Resources

Briefly, our proposed approach is efficient and capable of achieving the cost and improving the task scheduling.

• VI.    Conclusion

In this paper, we have presented the cost priority to schedule tasks on cloud resources that meet the user budget satisfaction. The Scheduling Cost Approach (SCA) calculates the cost of all resources. Each task is assigned based on task priority taking into consideration suitable resources for execution and distribution of load balancing between the VMs in clusters. We conducted six experiments to test the performance of our approach. The comparison of SCA was done with FCFS and SJF algorithms under same task priority and resource cost processing. The simulation results show that SCA has outperformed in all cases as compared to FCFS and SJF algorithms in reducing the cost of all resources.