Information Technology Reference
In-Depth Information
Scheduler Based on Ant Colony Optimization.
In this algorithm, each ant works
independently and represents a VM “looking” for the best host to which it can be allo-
cated. When a VM is created in a datacenter, an ant is initialized and starts to work. A
master table containing information on the load of each host in the selected datacenter is
initialized. Subsequently, if an ant associated to the VM that is executing the algorithm
already exists, the ant is obtained from a pool of ants. If the VM does not exist in the
ant pool, then a new ant is created. To do this, first, a list of all suitable hosts belonging
to the selected datacenter in which can be allocated the VM is obtained.
Algorithm 1.
ACO-based Cloud scheduler: Core logic
Procedure
AntAlgorithm ()
Begin
step
1
initialize ()
While
=
maxSteps )
do
currentLoad
=
getHostLoadInformation ()
AntHistory . add ( currentLoad )
localLoadTable . update ()
if
( currentLoad
=
0.0)
break
else if
( random ()
<
mutationRate )
then
nextHost
=
randomlyChooseNextStep()
else
nextHost
=
chooseNextStep ()
end i f
mutationRate
=
mutationRate
−
decayRate
step
=
step
+
1
moveTo ( n e x t H o s t )
end while
deliverVMtoHost ()
End
(step
<
Then, the working ant and its associated VM is added to the ant pool and the ACO-
specific logic starts to operate (see Algorithm 1). In each iteration, the ant collects the load
information of the host that is visiting and adds this information to its private load history.
The ant then updates a load information table of visited hosts (localLoadTable.up-
date()), which is maintained in each host. This table contains information of the own
load of an ant, as well as load information of other hosts of the datacenter, which were
added to the table when other ants visited the host. Here, load refers to the total CPU
utilization within a host and is calculated taking into account the number of VMs that
are executing at a given time in each physical host.
When an ant moves from one host to another it has two choices: moving to a random
host using a constant probability or
mutation rate
, or using the load table information
of the current host (chooseNextStep()). The mutation rate decreases with a
decay
rate
factor as time passes, thus, the ant will be more dependent on load information
than to random choice. When an ant reads the information from a load table in a host,
the ant chooses the lightest loaded host in the table, i.e., each entry of the load infor-
mation table is evaluated and compared with the current load of the visited host. If the
load of the visited host is smaller than any other host provided in the load information
table, the ant chooses the host with the smallest load. This process is repeated until the
