A Introduction A. Cloud Definition The NISTA Introduction A. Cloud Definition The NIST

A Survey of Algorithms for Scheduling in
the cloud: In a metric basis

I
V
A Jane, II BJ. Hubert Shanathan, III Dr.L.Arockiam

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

IM. Phil Scholar, II PhD
Scholar, III Associate Professor

I, II, III Dept. 
of Computer Science,St. Joseph’s College, Trichy, Tamilnadu, India

I [email protected]

II [email protected]

III [email protected]

Abstract

Cloud computing is a
modern Technology that provides all types of resources to the users with the
help of internet. Resource management is the key factor that contributes the
performance in the cloud. Scheduling plays a prominent role in managing
resources in the cloud.  Scheduling also affects
cloud service provider by power consumption of the data center, for the organization,
it affects by cost and for environment by carbon emission. The Algorithms focused
on the metrics of scheduling such as throughput, response time, resource
utilization, fault tolerance and performance. This paper gives a detailed description
about various Scheduling algorithms in the cloud.

Keywords

Resource scheduling,
Cloud computing, Energy, Throughput, Response
time.

1. Introduction

A. Cloud Definition

The NIST (National
Institute of Standards and Technologies) 1 defines  a “cloud computing as a model for enabling
omnipresent and also expedient, which is on demand network access to a shared
pool of configurable computing resources (Eg: network, server, storage,
application, and service) that can be speeded provisioned and also be
discharged with list management attempts or service provider interaction”.

Cloud 2 is a technology
which is used for delivering computing services over internet. Cloud enables
organizations to use the resources effectively by the virtual machines. Virtual
machine 3 acts as a replica for a real machine and it also reduces costs and
effort for the organizations. Cloud is a technology which is used in an
efficient way of using the internet.

 

 

 

B. Cloud Features

The features of cloud computing,
consist of elasticity, pay-per use and flexible migration.  Elasticity of resources can be increased and
decreased according to the change in demand for  cloud. The cloud allows 4 end users to use
the resources automatically which are known as Self service provisioning. Cloud
measures the capacity of the provisioned resources and user pays (pay per use)
according to the resources utilized. Organization workloads are transferred
easily from one platform to another which reduces cost that means flexible migration
and cloud provides various service models to the users such as server, network
and storage. Cloud service models are divided into three types that are SaaS,
PaaS and IaaS.

In
SaaS Service model Cloud applications are delivered to the user via the
internet. The installation and maintenance of application software are done by the
cloud. In PaaS Cloud provides various platforms and environment to the users,
that allow the user to develop applications and deploy on the internet. In IaaS
Cloud provides resources by virtualization and high-level APIs uses the
internet.

 

C. Types of Cloud

The resource location
in the cloud is classified into three different categories that are Private,
Public, Hybrid 5. A private cloud is a type of a cloud that belongs to an
organization or a person. It allows restricted access to the users rather than
admin.

The authority for using
resources differs from admin to user. A private cloud is expensive, but secure
compared with the other cloud 6. Public cloud means all virtualized resources
in the cloud is openly shared among the users. Public cloud supports huge
number of customers with the help of internet. Hybrid cloud is a combination of
public and private cloud 7. It is based on depend purpose of the cloud for
customer interaction its public, for data starting it’s private.

 

D. Scheduling In Cloud

Scheduling plays
prominent role in the cloud 8. There are two types resource scheduling, static
and dynamic scheduling. Scheduling algorithm provides an efficient utilization
of resource. Important parameters of scheduling algorithms are cost, time and
energy these parameters are plays a vital role in QOS.RSA 9 is significant in
scheduling and allocating workload to the resources. Resource scheduling is a
delivery and allocation of resource to the virtualized environment. The main objective
10 of resource scheduling is recognizing the appropriate resource for
scheduling. Scheduling algorithms require some metrics to be satisfied that are
as follows

 The Table 1 depicts the detailed description
about Resource Scheduling Metrics in the cloud environment.

 

Table1:
Scheduling metrics

Metrics

Description

Response
time 11

The total amount of time cloud takes to
respond to a request for service.

Scalability
12

The ability of a cloud to increase the workload on its
current resources

Throughput
13

It is the amount of data moved successfully from one
cloud to another in a given time slot

Resource
utilization 14

Process of accomplishing the most of the resources
accessible

Makespan 15

It’s the total length of the schedule which means the
end of all jobs process

Performance
16

The action or process of performing a scheduling
successfully

Fault
tolerance 17

In
scheduling, it continuously runs even in failure.

2. Review of Literature

Bargaining based RSA

Radu et al 18
proposed continuous double action (CDA) mechanism that parley contrast between
the resource scheduler and resource manager of market based Continuous Double
Action (CDA) model. The scientific application relies on the task of a program output,
which is dependent on one another. The algorithm was implemented in the cloud SIM
and that model flow and relative error. This mechanism was suited only for
uniform workloads.

 

Energy based RSA

Wei  Wei et al 19 proposed a model based on the
Dynamic stacklberg game (CSBM-IISN) to allocate resources in the cloud.  The Hidden Markov chain model was developed to
increase the resource supplied to the end user. HMM was used to forecast the
service provider resources.After that (IISG) inaugurated to improve the
provider’s strategy and maximize the utilization of resource, but this model only
focused on reducing the price for the transaction.

 

Nasrin
Akhter  et al 20 discussed energy consumed by cloud
data centers and its causes. Review various algorithms which reduce energy
consumption of data center by proposed green computing

 

PSO –MC Algorithm

Xu
Zhe-Jun et
al 21 proposed a membrane computing theory with particle swarm optimization as
(PSO-MC). Membrane system used as a framework. That framework proceeds
particle’s local optimization for intermembarance after that particle swarm’s
global search and optimization for intermembarance by this it find the optimal
solution for resource scheduling. The algorithm only focused on reducing the
time.

 

Hybrid scheduling

Mihaela  et al 22 proposed an algorithm HySARC2.
The algorithm allocates all the resources into the group on hierarchical way
via two phases of execution. First phase allocates resources into groups and
the second phase, execute the scheduling algorithm. Their algorithm was
suitable for heterogeneous systems. Other type system is not considered.

 

EARTH: Energy – aware
autonomic resource scheduling in cloud computing:

Sukpal sing et al 23
proposed a framework for reducing the usage of energy in cloud data centers
based on fuzzy logic. Data centers energy consumption disturbs the environment
by carbon footprints and high amount operational cost to the organization. The
proposed framework worked in cloud SIM and the result satisfies various QoS
parameters such like self- healing (take action of sudden errors) self
-optimization (maximize) resource usage and cost, time efficiency) self-
configuration (competence to readjust resource) and self -protecting
(identifying and safeguarding the resource from cyber-attacks).

But this framework
result in only simulated result, there’s a possibility to get differ in real
world systems.  Even though the energy
consumption was reduced, but carbon emission was not considered.

 

ACO

Priyanka Mod et al 24
proposed an algorithm using ACO (Ant Colony Optimization) with some additional
genetic operations to improve the cloud performance. Their algorithm proceeded
to avoid a deadlock condition on the cloud hosts jobs are scheduled using ACO.
This algorithm reduces the resource consumption. But energy consumption was not
considered.

Young moon et al 25 proposed
slave ant based ant colony optimization algorithm. For task scheduling in
cloud. The main objective of this algorithm is to increase the capability of
the task scheduler assortment and strengthen planning’s adopted from slave
ants. Thus the algorithm avoids the global optimization problem, not
considering both heterogeneous clusters and cost.

 

PSO

Ali Al-Maamari  et al 26 proposed an algorithm comprised of
PSO with Dynamic Adoption to the cloud environment (DAPSO) Dynamic Adoptive PSO
was working on the basis of PSO algorithm. PSO was used to minimize the
makespan of the task set for optimize the run time and maximize the resource
utilization. The proposed algorithm is a dubbing of DAPSO and is called MOAPSO.
Their algorithm was more efficient than the PSO algorithm.

 

Meta heuristic

Mala Karla et al 27
discussed meta heuristic Technique based algorithms such as a PSO,ACO,GA and 2
novel Technique LCA, BAT. The final result shows that all Meta heuristic
algorithms are slower than deterministic algorithms and the solutions not
optimal.

 

Chung Ming Cheung et al
28 proposed Distributed Flow by Flow Fair Routing algorithm for maximizing
network resources. Their algorithm outperformed a static routing assignment
protocol. Their algorithm compared with DDFS (Distributed Dynamic Flow
Scheduling) and overcome drawbacks. Their algorithm only suitable for
homogeneous network link. Synthetic data only performed so the result may vary
in real world data.

 

Memory Based Load
Balancing Algorithm

Raghul  et al 29 has compared these both algorithms
(ECLB & FCFS) considering all the drawbacks they have come to a final
conclusion by reducing delay and execution time in the proposed algorithm MUUU.
The system (SPPS) works using the (MCLV) algorithm which was a more efficient
algorithm. The advantage of the proposed algorithm was the delay time and
execution times are reduced. The disadvantages are ample numbers of messages
are sent to the scheduler and similar clients are not clustered properly.

 

A Load Balancing Algorithm
Based on Processing Capacities of VMS in Cloud Computing

Ramdeep Kaur  et al 30 proposed Load Balancing algorithm
by comparing performance of Heuristic Load Balancing Algorithm and Round Robin
Algorithm. The proposed algorithm reduced the completion time with maximum
resource utilization. Their algorithm only solved the problems which exist in
the Round Robin and Heuristic Algorithm.

 

Task Based Load
Balancing Algorithm by Efficient utilization of VMS in cloud Computing    

Ramdeep
Kaur  et al 31 proposed Dynamic Load
Balancing Algorithm. Their Algorithm produced better results in average
response time, turnaround time and total cost. But, wait time, throughput is
not considered.

A
Packaged based Approach for Load Balancing in Cloud Computing

Amanpreet
Chawla  al 32 proposed Packet based
Load Balancing Algorithm. The motive of their algorithm is grouping of packages
and performs the virtual machine replication in Load Balancing. Outcome of
their Algorithm minimum execution time with low cost. Migration of  VM is difficult .

WAMLB:
Weighted Active Monitoring Load Balancing in cloud computing

Aditya
Narayan Singh  et al 33 Proposed
algorithm is based on weight of virtual machine and the final result overcome
the existing algorithm. VM status based task assigned so execution time was
minimized.CPU utilization was not considered.

LBBSRT:
An efficient SDN Load Balancing Scheme based on server response time 

Hong
Zhong et al 34 proposed algorithm that measured each server capacity and allocate
load based on the capacity. Final result shows that  minimum average server response time was
achieved with good scalability and low cost. Energy saving was not considered.

 

 

Load
Balancing in Cloud Computing environment using improved weighted Round Robin
Algorithm for Non-preemptive dependent Task

D
Chitra Devi et al 35 proposed algorithm based on the capability of each
virtual machine, the length of each requested job, and the interdependency of
multiple tasks. Their algorithm produced minimum response time, but the
migration of job in a VM was not considered.

Improvised
Bat algorithm for Load Balancing:Based Task Scheduling 

Behave
Raj et al 36 discussed new metaheuristic, Min-Min, Max-Min, Alpha-Beta and
produced as Improvised Bat Algorithm. Min-Min, Max-Min algorithm Task Execution
time was minimized and the task is optimistically distributed   but the processing time was huge.

Load
Balancing Mechanism using FUZZY Row Penalty Method in the cloud computing
environment

Narender
Kumar et al 37 proposed solution to load balancing problem using FUZZY
technique, which was used for solving the uncertain response time. FUZZY row
penalty method, was used for Load Balancing and Unbalanced FUZZY. Outcomes
shows scalability, increased performance, minimized overheads and neglecting
of   Bottle Neck problem.

 

3. Comparison of Resource Allocation
Algorithms

Table 2: Comparison of
Resource Allocation Algorithms

Title

   Limitations

Future Work  Parameters

Bargaining  RSA18

 

Uniform workloads.

 

Non uniform
workloads.

 

Energy  RSA19

Maximize the
utilization of resource, cost

Execution time

Energy  RSA20

Energy consumption

Resource utilization,
Server utilization

PSO –MC21

Reducing the
execution time

Other metrics not
considered

 

Hybrid scheduling
22

Execution time

Resource utilization

EARTH23

Energy consumption

Carbon emission

ACO24

Resource consumption.

 Energy consumption

ACO 25

Avoids the global optimum.

 

Cost, heterogeneous clusters
 

 

PSO26

 

Minimize the makespan

Server utilization
,scalability

Meta heuristic
27

All Meta heuristic
algorithms are slower than deterministic algorithms

Solutions not
optimal.

 

Meta heuristic
28

Maximize network
resources

Synthetic data only
performed so the result may vary in real world data.

MLBA 29

 

Delay time and
execution times

Similar clients are
not clustered properly.

VMLBA 30

Maximize resource
utilization.

Not suitable in all
problems

TLBA 31

Average response
time, turnaround time and total cost

Waiting time
throughput

PLBA 32

Minimum execution
time with low cost.

Migration of  VM

WAMLB 33

Execution time was
minimized

CPU utilization

LBBSRT  34

Minimum average
server response time, low cost

Energy saving

LBAWR35

Minimum response time

Migration

IBAT 36

Task Execution time
is minimized and the task is optimistically distributed

Processing time is
huge

Fuzzy 37

Scalability increased
performance, minimized overheads and neglecting of   Bottle Neck problem

 

Server utilization

 

Conclusion

Cloud computing
technology is developing day by day with huge number of new challenges. One of
them is scheduling. This paper mainly focuses on analyzing scheduling
algorithms which are used to maximize utilization of resources with minimum
energy consumption, reduces makespan, quality of service, cost and power
reduction. Many algorithms are proposed to give powerful scheduling, but since
the scheduling is critical, the more research can be done in this area for the
betterment of the results.