Dynamic Resource Allocation in Cloud Com
Dynamic Resource Allocation in Cloud Com
Dynamic Resource Allocation in Cloud Com
4, 2017
– 83 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
1 Introduction
A cloud is created from numerous physical machines. Each physical machine runs
multiple virtual machines which are presented to the end-users, or so-called
clients, as the computing resources. The architecture of virtual machines is based
on physical computers with similar functionality. In cloud computing, a virtual
machine is a guest program with software resources which works like a real
physical computer [1]. Yet, high workload on virtual machines is one of the
challenges of cloud computing in the allocation of virtual machines. The task,
requested by a client, has to wait to be allocated to the work and the resources
needed. This strategy is independent of the executive priority of the tasks.
However, the client who owns the task may offer larger value for it to try to raise
his/her priority and eventually may succeed in taking control over the resources
needed. Users can consume services based on the service level agreement that
defines their needs of quality of service (QoS) parameters [2]. Yet, the
multipurpose nature of the scheduling in the cloud computing environment has
made it extremely difficult to manage. Therefore, scheduling has to create a
compromise between service quality costs to come up with a suitable service
which belongs to a multi-objective optimization problems family [3]. Several
methods are available for a multi-objective scheduling problem [4]. The current
methods of allocation of resources, such as FIFO [1] and Round-Robin [5] which
are used in the cloud, do unfair allocation regardless of priority between tasks.
Resource allocation in the cloud environment is utilized to achieve customer
satisfaction with minimal processing time. Reducing the fees of leasing resources
in addition to ensuring quality of service and improving throughput for trust and
satisfaction of the service provider is considered as another objective. In dynamic
scheduling, the basic idea is the request allocation at the time of implementation of
programs. In addition to the cost estimation, in the static method, dynamic
scheduling consists of two other main sections of system state estimation and
decision-making [6]. To recap, clients are interested in having their tasks
completed in the shortest possible time and at the minimum cost which cloud
servers should receive. On the other hand, the cloud providers are interested to
maximize the use of their resources and also to increase their profits. Obviously
these two objectives are in conflict with each other and often they are not satisfied
with the traditional methods of resource allocation and scheduling mechanisms
available [7]. Yet the goal is to direct the resource allocation to be performed in a
way that is acceptable to both the users and the suppliers.
Resource allocation is a technique that ensures the allocation to virtual machines
when multiple applications need different resources of CPU and input/output
memory [2]. In cloud computing there are two technical restrictions. Firstly, the
capacity of the machines is physically limited; secondly, priorities for the
implementation of the tasks should be in harmony with maximizing the efficiency
of resources. Ultimately, the waiting time and the completion time are to be
– 84 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
The average cost paid by the user for use of the resources
Efficiency caused by the impact of load balancing based on completion
time and cost of doing them.
To conduct this study in the realm of cloud computing system development, a
number of assumptions are made with the following characteristics. In these
– 85 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
2 Related Works
For resource allocation in distributed scheduling, Xu et al. [5] present a non-
dominated sorting genetic algorithm-based multi-objective method (NSGA-II)
[10]. They aimed at minimizing the time and cost in load balancing using
resources to achieve Pareto optimal front. They used self-adaptive crowding
distance (SCD) to overcome the crowding distance. In addition, in their proposed
method, a mutation operator is included in the traditional algorithm of NSGA-II to
avoid premature convergence. In this method, the strategy that the algorithm uses
for improving the efficiency and performance of the intersections, has not been
effective, as the solutions are trapped in local optimum.
Salimi et al. [14] introduced a multi-objective tasks’ scheduling using fuzzy
systems and standard NSGA-II algorithms for distributed computing systems in
[6]. The authors aimed at minimizing implementation time and costs while
increasing the productivity of resources. Their study is associated with the load
balancing in the distributed system. They use the indirect method and fuzzy
systems and do implementation of the third objective function to solve this
problem. However dealing with three objectives has not been efficiently done in
their work. In [7], Cheng provides an optimized hierarchical resource allocation
algorithm for workflows using a general heuristic algorithm. In this model, the
main objective is the coordination between the tasks and duties assigned to the
service. The purpose is to service in accordance with the operational needs to
perform properly the tasks and observe the priority between them. This model
accomplishes workflow tasks scheduling aimed at load balancing by(?) dividing
the tasks to different levels. Further, mapping and allocation of each level of tasks
to resources is directed according to the processing power.
Gomathi and Karthikey [8] introduce a method for assigning tasks in a distributed
environment using Hybrid Particle Swarm Optimization algorithm (HybPSO)
[11]. HybPSO is used to meet the user needs and increase the amount of load
balancing with productivity. The goal is to minimize the task completion time
among processors and create load balancing. This method assures that each task is
assigned to exactly one processor. In this method, each solution is shown as a
particle in the population; each particle is a vector with n dimension which is
defined for scheduling n independent tasks.
In [9], authors introduce a heuristic method based on particle swarm algorithm
[12] for tasks’ scheduling on distributed environment resources. Their model
considers the computational cost and the cost of data transfer. Their proposed
algorithm optimizes dynamic mapping tasks to resources using classical particle
swarm optimization algorithm and ultimately balances the system loads. This
optimization method is composed of two components. One of them is the
scheduling operations task and the other one is particle swarm algorithm (PSA) to
obtain an optimal mix of the tasks to resources’ mapping.
– 86 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
Table1 presents a summary of the related works done in the field of tasks’
scheduling. This table includes the objectives of tasks’ scheduling, the algorithms
used in these methods, the simulation environment of the algorithms, and the year
in which they were developed. Table1 does not include the GW and education-
based learning algorithms and/or any variations of these algorithms.
Table1
Summary of the works done in the field of resources’ allocation
Evolutionary
Author Environment Targets Year Simulation tool
Reduce the longest termination time
algorithm
Load balancing
Cheng [15] genetic Cloud among resources Java environment
Load balancing
Moallem [22] Ant colony Grid among resources GridSim
The literature review shows that traditional methods which are used for
optimization, may be definitive and accurate, yet they are often trapped in local
optimum. In fact, due to the dynamic nature of distributed environment and
– 87 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
3 Proposed Method
Methodology is based on bonding the algorithms of TLBO and GW. With such
hybridization, it is aimed at speeding up the process while maintaining the
improvement of local optimization and increasing the accuracy. In the following,
the problem is described. Further TLBO and GW algorithms are introduced as the
primary solutions to the described problem. The proposed methodology then
emerges from bonding of two algorithms.
– 88 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
As it is described in Figure 1 each node includes several jobs. Each job requires a
series of specific resources. The problem can be introduced as Job j1,j2,…,jn
and Resource R1,R2, … , Rm .
Figure 1
Resource allocation in a distributed environment
If in the particular example, the resources R1,R2, … , Rm have the same capacity
and processing power and j1,j2,…,jn all need 1% of the processing. The advanced
model can be defined in a form describing what jobs in which resources should be
used in order to achieve the maximum load balancing, average response time, and
minimum cost. For the exact solution of the problem, all possible allocation
modes must be calculated and the best mode chosen. Due to the large number of
modes (exponential), the problem is an example of set packing problems, which is
of NP-complete type.
Optimization function is defined for resource i and job j. yi is the number of
resources (package). The objective function and mathematical programming
model that should be optimized are as follows:
Min B = a * (1- L( y j ) )+ b *C ( y j ) + c *T ( y j )
(2)
S.t.
n n
Where :
ïì 1 ïì 1 resource j is used
x j = ïí , y j = ïí
job j is used
ïîï 0 job j isnot used ïîï 0 resource j isnot used
– 89 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
a, b, c are variable based on cloud system. The variable of Xij demonstrates that
the ith job is in jth virtual machines, and if its value is equal to 0, it means that there
is not any resource in jth virtual machine and if its value is equal to 1, it means that
there is enough resource to allocate the jth virtual machine. Every job has the
capacity of Wi. The first limitation indicates that total capacity of jobs can be
placed at the maximum - K - available resources. The second limitation shows the
maximum capacity of each virtual resource. bj is the capacity of each virtual
resource.
Figure 2
Grey wolves’ motion in haunting [30]
– 90 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
Figure 3
Updating wolves' position [30]
The Wolves’ leader is called alpha and is primarily responsible for the prey. The
second level of wolves, which helps the leader, is called beta. The third level of
wolves is called delta and is designed to support alpha and beta. The lowest level
is called Omega [31]. In general, the algorithm steps can be summarized as
follows:
The fitness of all solution levels are computed and three top solutions are
selected as Alpha, Beta, and Delta (Figure 2) until the end of the algorithm.
In fact, Alpha is the best fitness of solution. After Alpha, the Beta and Delta
are the best solutions respectively.
In each iteration, the three top solutions e.g. Alpha, Beta, and Delta have
the ability to estimate the prey position, conducting it in each iteration using
the following equations [30]:
(3)
D α = C 1 .X α - X , D β = C 2 .X β - X , D δ = C 3 .X δ - X
uur uur ur uur
uur uur uur ìï X 1 = ü
ï
uur ïï uur X
uura - Aur1.( D uura ) ïï
X 1+ X 2 + X 3 where ïí X 2 = ï
ur a ) ý
(4)
X (t + 1) = ïï uur uur a -
X uA
r 2 .( uD ï
3 ïïî X 3 = Xa- A 3 .( D a ) ïï
ïþ
First, the wolves put a ring around the prey, where Xp, is the hunting position
vector. A and C are hunting vector coefficients. X is the wolves' positions and t
stands for the stage of each iteration. D indicates the behavior of putting the ring
around the hunt [30]. In each iteration, after determining the positions of Alpha,
Beta, and Delta, the other solutions are updated in compliance with them. Hunting
– 91 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
information is defined by Alpha, Beta, and Delta. And the rest update their x
positions accordingly. In each iteration, vector and consequently vectors b and c
are updated. At the end of an iteration, Alpha wolf position is considered as the
optimal point. This value is A. A value of A is an option value which is between (-
2a, 2a). The absolute value of A is less than 1, so when the wolves are at the A
distance from the prey, attack happens. At a distance of more than one, it is
still(??) necessary that the wolves must converge toward each other [4]. In the GW
algorithm, some main parameters like initial population size, vector coefficients,
number of iterations, and the number of wolf levels are to be determined [32].
Then, the cost function of optimization which is minimized in this study is
introduced. Afterward, the initial population is formed randomly and the fitness
function is introduced. Then, in a loop on a regular basis, the position of the
wolves' level is determined and the fitness function is calculated, and, using them,
the new positions are calculated again. Iteration of this loop is specified according
to the initial parameters.
– 92 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
M1 M2 MA MB
Curve 1 Curve A
Curve 2 Curve B
. TA . TB
Figure 4
Average scores of students who were in classroom [33]
As it is shown in figure 4, the second teacher, with average scores of M2, has
acted better than the first teacher with average score of M1. TA is the first grade
teacher, who, with the best-case average scores of the first grade, MA, moves to the
TA. It means that the academic level of students is approaching that of their teacher
or equal with him/her. This creates a new population of the classroom which has
shown an average of MB and TB. In fact, the students do not reach the knowledge
level of the teachers, just close to it, which also depends on the level of classroom
ability. Gaussian probability function is defined as follow [34, 36]:
- ( x - m)2
1 2
f (X ) = e 2s (5)
s 2p
In this formula, μ is the average score of students, which is shown as M1 and M2 in
Figure 4.
– 93 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
and the solution is considered as initial population to start again. In this stage the
GW algorithm is implemented. If there is no improvement in GW algorithm,
according to the teaching and learning, it tries to find a better solution. If the
solution is trapped in local optimum, an algorithm based on teaching and learning
can introduce the new area of space based on training, which may improve
solution. Since the accuracy of GW algorithm in the local behaviour is high, after
each stage the position of wolves is determined. This position can be improved by
learning and training algorithms, and GW algorithm is implemented again. This
process increases the accuracy of GW algorithm. It should be considered that in
the GW algorithm, every wolf represents a solution in the solution space. The best
and the most successful solution will be chosen among them at any stage
according to the position of other wolves. The best solution of the GW is defined
as the initial solution for teaching and learning. After learning and training, its
output is implemented as the initial solution for the next iteration in the GW
algorithm. The proposed algorithm is presented in table 2:
Table 2
Pseudo code of the proposed algorithm
– 94 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
The main advantage of this algorithm is that if there was no improvement in grey
wolf algorithm, according to the teaching-learning process, we try to find a better
solution. If the problem is stuck in local optimum, teaching-learning process can
introduce the new area of space based on training phase, which may improve the
solution. Because of the accuracy of grey wolf algorithm in the local behavior
(defect of the grey wolf algorithm), after each iteration, the position of wolves is
updated. These positions can be improved by the teaching-learning algorithm, and
then grey wolf algorithm is repeated again. This process increases the accuracy of
grey wolf algorithm. Figure 5 illustrates flow diagram of proposed algorithm.
Figure 5
Flow diagram of proposed algorithm
– 95 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
4 Simulation
According to the assessment index, load imbalance and the number of resources
allocated are compared with each other. In this problem, Matlab is used to
simulate the proposed method and set a packing problem which is considered as a
model of resource allocation in cloud computing. Packages in the set packing are
considered as requests that are processed in the cloud virtual servers.
Amount of efficiency of each resource - Riefficiency - is equivalent to what
percentage of resource has been used compared to the total resource [28, 30, 35].
Formally, the coefficient of variation of resource efficiency is called lack of load
balancing. This variable indicates to what extent, there is a deviation of
productivity. According to statistical indicators, if this variable is zero, it means
that absolutely all resources are used. This variable is equal to the quotient of
productivity of standard deviation in resources when there are a number of
resources. When the variable is close to zero, load balancing is done better.
Standard deviation is:
1 N
s = å ( Ri - mean R i )2 (6)
N i = 1 efficiency
Load balancing factor (Flb) and load imbalance factor (NFlb) are introduced using
the following equations:
s . Ri
NFlb = i = 1...n
n (7)
C- s
Flb =
n (8)
Where C is the capacity of each resource or virtual machine.
Teaching-Learning simulation parameters have been set as follows:
maxIt = 500; % Maximum Number of Iterations
nPop = 250; %for each test must be updated Population Size
maxIt is the number of iterations for TLBO algorithm. nPop is the proportion of
the number of packages in an appliance packaging problem.
Grey Wolf simulation parameters have been set as follows:
max_iteration=500
Dim = number of your variables
a=0.0354, b=38.3055, c=1243.531
Coefficients a, b, c, have been selected according to the resource. Dim is the
number of packets in the packaging of appliance problem and max_iteration is the
number of iterations for the algorithm.
– 96 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
5 Experimental Results
There are 60 packages in the dataset binpack5 with the capacity of 100. Each
package has different value. The best way to obtain optimal solution is dividing
the sum of the values of packages by the capacity of 100. The optimal solution of
the allocation is 20 boxes. Our proposed method has achieved an approximate
solution of 23. The solution has acted better than the GW and TLBO algorithms
alone, as is shown in Table 3.
Table 3
Comparison of allocation with the proposed algorithm in dataset binpack5
In the second experiment, a set of binpacks was used. Hence, according to data
dispersion and increased capacity of boxes, the problem became more difficult,
but the results demonstrate that the proposed method is desirable. Figure 6
indicates this process. A comparison between the differences of optimum solution
show a high performance.
Compare Number of Allocated Bin's (Virtual Mavhine's) in Different Methods Compare Number of Allocated Bin's (Virtual Mavhine's) in Different Methods
450 220
TLBO TLBO
200
GWO GWO
400
Hybrid Hybrid
180
350 160
140
No # Bins
300
No # Bins
120
250 100
80
200
60
150
40
100 20
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
First Test (Data set Binpack1-Binpack4) second Test (Data set Binpack5-Binpack8)
Figure 6
Comparison of the hybrid method with other methods to achieve optimal solution
– 97 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
According to a recent article [36], CGA-CGT and HI-HB methods are providing
the best solution to set packing. The proposed hybrid method indicates a better
performance than the other two methods (Table 5).
Table 5
Comparison of the proposed method with HI_BP and CGA-CGT
350
Solution Number of Bin's
300
250
200
150
100
50
0
0 2 4 6 8 10 12 14 16
Tests
Figure 7
Solution’s difference between the proposed method and the optimal solution
Nflb index indicates lack of load balancing. Decreasing this index demonstrates
the increasing of load balancing in the cloud system. Increased load imbalance
further indicates that maximum resource capacity is used. This means that the
capacity of the resources is low. Therefore by increasing data, load balancing is
performed better in the proposed algorithm. Figure 8 shows the load imbalance
– 98 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
between the methods in the first and second experimental set. The load imbalance
index acts in a reverse manner compared with the load balancing index. Increasing
of data will increase the performance of load balancing. The training learning
method, due to the structure of incorrect understanding of training in the
experiments, doesn't have a good load balancing with more data. The proposed
method shows a good performance with increased data in load balancing. The load
balancing can be calculated by the lack of load balancing. Load balancing can
indicate appropriate allocation. The second experiment in Table 6 confirms the
fifth to eighth data set, and then related charts are presented in Figure 8.
Non Load Balancing in Virtual Machines in Cloud
Non Load Balancing between Virtual Machines in cloud
0.135
0.02
TLBO
TLBO
GWO GWO
0.13
0.018 Hybrid Hybrid
0.12
0.014
0.115
0.012
0.11
0.01
0.105
0.008 0.1
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
Data set's for Binpack1 to Binpack4 data set for Binpack5 to Binpack6
Figure 8
Load imbalance in the first test set (left) and load imbalance in the second test set (right)
Table 6
Comparison of the load imbalance between the proposed algorithm and other algorithms
Nflb-
Number Resource Nflb- Nflb-
Experiment Dataset Proposed
of Job capacity TLBO GWO
method
First Binpack1-U250_00 250 150 0.0145 0.0145 0.0145
First Binpack1-U250_01 250 150 0.0193 0.0195 0.0195
First Binpack2-U250_00 250 150 0.0138 0.0145 0.0145
First Binpack2-U250_01 250 150 0.0178 0.0195 0.0195
First Binpack3-U500_00 500 150 0.0159 0.0163 0.0170
First Binpack3-U500_01 500 150 0.0143 0.0147 0.0155
First Binpack4-U1000_00 1000 150 0.0097 0.0103 0.0113
First Binpack4-u1000_01 1000 150 0.0119 0.0127 0.140
Second Binpack5-T60_00 60 100 0.1304 0.1304 0.1304
Second Binpack5-T60_01 60 100 0.1304 0.1304 0.1304
Second Binpack6-T120_00 120 100 0.1023 0.1111 0.1111
Second Binpack6-T120_01 120 100 0.1013 0.1111 0.1111
Second Binpack7-T249_00 249 100 0.1010 0.1090 0.1170
Second Binpack7-T249_01 249 100 0.1203 0.1226 0.1263
Second Binpack8-T501_00 501 100 0.1107 0.1139 0.1211
Second Binpack8-T501_01 501 100 0.1219 0.1231 0.1257
– 99 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
Variable of relative changes percentage in comparison with the best answer can
demonstrate the accuracy of the algorithm. Therefore, we calculate Robust
Parameter Design (RPD) parameter, which is normalized change percentage
against the best answer where fheuristic is metaheuristic value and foptimal is optimal
value. The RPD equation is:
f heuristic - f optimal
RPD = 100 ´ (9)
f optimal
0.16
Prposal Method
0.14
GWO
0.12
0.1
RPD
0.08
0.06
0.04
0.02
0
0 2 4 6 8 10 12 14 16
NO OF TESTS
Figure 9
Relative changes’ percentage of the optimal solution
This criterion shows the performance of the algorithm with increase of the jobs
and indicates that the proposed method has appropriate performance with
increasing data. Table 7 demonstrates relative changes’ percentage in proposed
algorithm. The average of relative changes’ percentage is increased in an
appropriate way in experimental data and has a better flow than GW and TLBO
algorithms.
Table 7
RPD index in performance of proposed method
– 100 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
Conclusions
The performance of two relatively new optimization algorithms, i.e., TLBO and
GW, along with a hybrid form of these two algorithms in dynamic resource
allocation is described. To evaluate the performance of the proposed hybrid
algorithm, a comparison with the TLBO and GW algorithms is conducted and the
experimental results presented. It is reported that the proposed hybrid algorithm
performs more efficiently than utilizing only one of these algorithms. It is further
concluded that the main problem in the resource allocation of cloud scheduler is
the lack of convergence in the optimal solution. Optimization of objective
functions for the resource allocation at any time is one of the main problems in
dynamic resource allocation. The evaluation of experimental results indicate that
the proposed hybrid approach in high-volume data for resource allocation in cloud
scheduler has better performance than the other two methods.
Acknowledgment
This work has been sponsored by Hungarian National Scientific Fund under
contract OTKA 105846 and Research & Development Operational Program for
the project “Modernization and Improvement of Technical Infrastructure for
Research & Development of J. Selye University in the Fields of Nanotechnology
and Intelligent Space”, ITMS 26210120042, co-funded by the European Regional
Development Fund.
References
[1] J. Yao and H. Ju-Hou: Load Balancing Strategy of Cloud Computing Based
on Artificial Bee Algorithm, Information Management, Vol. 51, 2012, pp.
185-189
[2] S. Zhao, X. Lu, and X. Li: Quality of Service-based Particle Swarm
Optimization Scheduling in cloud Computing, Networks, Vol. 12, 2015, pp.
235-242
[3] A. Mosavi and A. Vaezipour: Reactive Search Optimization; Application to
Multiobjective Optimization Problems, Applied Mathematics, Vol. 3, 2012,
pp. 1572-1582
[4] S. Zhang and Y. Zhou: Grey Wolf Optimizer Based on Powell Local
Optimization Method for Clustering Analysis, Discrete Dynamics in Nature
and Society, Vol. 3, 2015
– 101 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
– 102 –
Acta Polytechnica Hungarica Vol. 14, No. 4, 2017
– 103 –
S. Mousavi et al. Dynamic Resource Allocation in Cloud Computing
– 104 –