Efficient scheduling in cloud networks using chakoos evolutionary algorithm

Đăng ngày 4/2/2019 3:56:30 PM | Thể loại: | Lần tải: 0 | Lần xem: 2 | Page: 5 | FileSize: 0.31 M | File type: PDF
Efficient scheduling in cloud networks using chakoos evolutionary algorithm. In this algorithm, the new approach is based on making the length of the critical path shorter and reducing cost of communication. Finally, the results obtained from implementation of the presented method show that this algorithm acts as same as other algorithms when it faces with graphs without communication cost. It performs quicker and better than some algorithms like DSC and MCP algorithms when it faces with the graphs involving communication cost.
International Journal of Computer Networks and Communications Security
VOL. 3, NO. 5, MAY 2015, 220–224
Available online at: www.ijcncs.org
E-ISSN 2308-9830 (Online) / ISSN 2410-0595 (Print)
Efficient Scheduling in Cloud Networks Using Chakoos
Evolutionary Algorithm
Msc. MASOUMEH ALIPORI1, 2 and PhD. HAMID HAJ SEYYED JAVADI3
1 Department of Computer Engineering, Science and Research Branch, Islamic Azad University,
Boroujerd, Iran
2 Department of Computer Engineering, Boroujerd Branch, Islamic Azad University, Boroujerd, Iran
3 Department of Applied Mathematics, Faculty of Mathematics and Computer Science, Shahed University,
Tehran, Iran
E-mail: 1alipori.m @gmail.com, 3hamid.h.s.javadi@gmail.com
ABSTRACT
Since scheduling of tasks graph is a NP-hard problem, considering approaches based on undeterminisitic
methods such as evolutionary processing, mostly genetic and chakoos algorithms will be effective.
Therefore, an efficient algorithm has been proposed for scheduling of tasks graph to obtain an appropriate
scheduling with minimum time. In this algorithm, the new approach is based on making the length of the
critical path shorter and reducing cost of communication. Finally, the results obtained from implementation
of the presented method show that this algorithm acts as same as other algorithms when it faces with graphs
without communication cost. It performs quicker and better than some algorithms like DSC and MCP
algorithms when it faces with the graphs involving communication cost.
Keywords: Cloud Computing, Scheduling, Tasks Graph, Chakoos Algorithm.
1
INTRODUCTION
management
of
resources
available
in
a
cloud.
Although
there
are
many
requests,
scheduling
Due Nowadays, cloud processing is one of the
cannot be performed manually in date center.
important
issues
in
information
technology.
In
In recent years, one of the most important and
cloud computing environment, each user may face
promising methods is “innovative methods inspired
with hundreds of virtual resources in executing the
from the nature” in order to solve such problems
task.
Cloud
computing
is
highly
dependent
on
and to find optimal answer for resources scheduling
virtualization.
problem. These methods are similar to natural or
In
fact,
resources
are
considered
as
virual
social systems. Some of these methods are genetic
machines. In this regard, allocating the tasks to
algorithm,
chakoos
optimization
algorithm
and
resources by the user is not possible (Fendelman et
optimization of particles swarm. Nature-oriented
al, 2009). The purpose of using cloud computing
algorithm is a global optimization technique based
systems
is
to
minimize
the
cost
of
using
the
on population. Due to its simple search mechanism,
resources by service provider and to maximize the
computing
efficiency,
complexity
and
easy
income
of
providing
service
in
application
implementation,
it can be
widely
used
in
most
programs
of
requesters.
In
order
to
reach
the
optimization fields (Houmar, 2012).
purpose, scheduling system performs two different
As it was explained in chapter 2, scheduling
tasks in a scheduling
system in a cloud to increase
principles involve some specific rules for most of
the rate of task completion, utility of resources and
available
systems.
After
determining
the
tasks
computing
power
(Lee
et
al,2010).
In
fact,
priorities and investigating accessible resources for
scheduling means allocation of resources to tasks.
allocation, scheduling operations are performed on
Hence,
scheduling
is
an
important
issue
in
the basis of special algorithms. Each algorithm can
221
M. Alipori and H. H. S. Javadi / International Journal of Computer Networks and Communications Security, 3 (5), May 2015
be optimal on the basis of system requirements
The number of eggs that have grown show the
such
as
minimizing
time,
minimizing
cost,
suitability of that area’s nests.
minimizing time and cost in specified proportions.
When more eggs can survive in an area, and they
In
figure
1,
the
scheduling
framework
can
be
can be saved, more profit will be assigned to that
observed in a cloud computing system (Lee and
area. Therefore, when most eggs are rescued, this
Geo, 2010). This figure shows that after receiving
situation is considered as a parameter whom COA
the request of user by the scheduler, the scheduler
is going to optimize. Chakoos search the best area
assigns tasks to virtual machines by the help of a
to
rescue
maximum
number
of eggs.
After the
cloud controller.
chickens become mature chakoos, they constitute
communities and groups. Each group has its own
habitat. The best habitat of all groups will be next
destination of chakoos in other groups. All groups
migrate toward the best current area. Each group
resides in the location near to the best current
location. By considering the number of chakoos
eggs and the distance of chakoos from the current
optimum
area,
laying
radius
is
computed
and
formed. Then, chakoos begin to lay eggs randomly
in the nests located inside the radius of laying. This
process continues until reaching to the best location
for laying (the area with the highest profit). The
Fig. 1. The framework of a scheduling system in cloud
computing environment.
maximum number of chakoos are collected in the
optimum location. Chakoos optimization algorithm
is one of the strongest and newest evolutionary
In economical scheduling, the purpose is to
allocate the resources to tasks, so the cost of
performing all tasks is minimized. Mouschaku and
Caratez (2011), in their own articles, explained that
optimization methods that have been introduced up
to now. This algorithm has been developed by Levy
flying instead of simple and random is tropic hike
(kokilavani and Gorj , 2011).
the proportion of the task to resources involves
three modes (equations (1-3)-(3-3)).
3
THE PROPOSED ALGORITHM
Each task is executed by a resource:
(j=iXi,j)=1 , where ij
(1-3)
This algorithm begins performing its task by the
initial population involving chakoos. Chakoos are
divided into some groups. Each group has some
eggs, and they are allocated to a special host bird.
Each resource can perform more than one task:
(j=iXi,j)1, where iI
(2-3)
After forming chakoos groups in various areas of
environment (search space of the problem), the
group with the best situation is selected as the
objective point for other chakoos for migration
A resource executes or does not execute a task:
Xi,j=0 or 1, (i,j)i*j
(3-3)
according to the selection of population members
and by using local search of chakoos (in terms of
completion time of previous task). It is difficult to
determine that each chakoos belongs to which group.
i: the current resource
j:the current task.
In order to solve this problem, chakoos are grouped
according to classification method of K-means
(usually, the value of k between 3-5 is adequate).
2
CHAKOOS OPTIMIZATION (COA)
After forming the chakoos groups, average profit of
the group is computed so that relative optimality of
Like other evolutionary algorithms, COA begins
its work with initial population of chakoos. The
population of chakoos has some eggs, and they put
them in the nest of some host birds. Those eggs that
are more similar to the eggs of host bird have more
chance to grow and become a mature chakoos.
Other eggs are detected by the host bird and die.
habitat is obtained for that group. Then, the group
having the highest profit value (optimality) is
selected as the objective group, and other groups
move toward that group. When chackoos move
toward the objective point, they do not pass through
all the routes toward the objective place. They just
pass through a part of the route, and there are some
deviations in that group.