Hybrid Metaheuristic Technique for Optimization of Virtual Machine Placement in Cloud

Chayan Bhatt; Sunita Singhal

doi:10.5391/IJFIS.2023.23.3.353

Original Article

Split Viewer

International Journal of Fuzzy Logic and Intelligent Systems 2023; 23(3): 353-364

Published online September 25, 2023

https://doi.org/10.5391/IJFIS.2023.23.3.353

Hybrid Metaheuristic Technique for Optimization of Virtual Machine Placement in Cloud

Chayan Bhatt and Sunita Singhal

Department of Computer Science and Engineering, Manipal University Jaipur, Jaipur, India

Correspondence to :
Sunita Singhal (sunita.singhal@jaipur.manipal.edu)

Received: March 10, 2023; Revised: June 8, 2023; Accepted: July 18, 2023

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

The massive growth in cloud users and applications has caused a tremendous increase in the number of virtual machine (VM) requests. Consequently, VM placement has become an important factor in the management of cloud datacenters and their resources. In this context, a new hybrid mechanism named simulated annealing-intelligent water drop cycle algorithm (SA-IWDCA) has been proposed that improves the computational efforts and convergence rate of the water cycle algorithm (WCA) to efficiently place VM in a heterogeneous cloud. WCA performs hybridization in two levels using preselection and memetic algorithms. In level one, an intelligent water drop (IWD) is invoked to generate and feed the initial VM solution to the WCA. At the second level, simulated annealing (SA) is used to improve the VM solution quality using neighborhood search and targeted approaches of temperature scheduling and acceptance probability. The proposed approach incorporates the energy consumption and resource management of datacenters, resulting in a minimum number of active servers and reduced resource dissipation. Extensive simulations and analysis using MATLAB showed that the SA-IWDCA performed significantly well and has shown an improvement of 25% in energy consumption and 20% in resource utilization as compared to other heuristic and metaheuristic approaches.

Keywords: Virtual machine placement, Cloud computing, Water cycle algorithm, Intelligent water drop, Simulated annealing, Energy consumption

1. Introduction

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Cloud computing has emerged as a demanding technology that has turned IT infrastructure into day-to-day utilities. Through cloud technology, numerous services such as data storage, security, database access, networking, analysis, and intelligence can be easily rendered to users via the Internet [1, 2]. It relieves its customers of operational costs, hardware maintenance, and management by providing multiple resources via the Internet. The cloud creates a cyberspace or virtual environment of computing resources with the help of virtualization, which involves developing several virtual machine (VM) on actual physical machines (PM), enabling different services and tasks requested by different users to be easily executed.

Because of a sudden increase in VM requests, energy dissipation and performance degradation significantly affected the operation of individual PM [3]. This has rendered energy saving as a notable agenda to be enhanced. Many researchers have attempted to efficiently consolidate their servers to minimize power consumption by reducing the number of activated servers [2, 4]. However, if the cloud servers are accommodated by many VMs, the servers become overloaded, resulting in performance degradation and poor user experience. Hence, while performing VM consolidation, considering resource utilization without ignoring the quality of services (QoS) is crucial. VM Placement is NP-hard combinatorial optimization problem [5] and it is tedious to retrieve a deterministic solution. Various heuristic and metaheuristic approaches have been applied by different researchers to solve the VM placement problems. Metaheuristic techniques have been successful in providing optimal solutions to problems, whereas heuristic approaches are limited to local optima. These algorithms successfully demonstrated better placement decisions for dynamic VM workloads.

In [1], a technique using grey wolf optimization (GWO) along with SA was designed to perform load balancing in a containerized cloud. The containerized cloud improves the system performance by enhancing the resource utilization and deadline miss rate of the active servers. The proposed method was compared with the genetic algorithm (GA) and particle swarm optimization (PSO) and showed optimal results in terms of load variation and makespan; however, it caused overhead owing to the large search space. Eswaran et al. [6] used an IWD to place a VM on cloud servers. The proposed metaheuristic was based on the movement and actions of water drops in rivers and functioned well for restoring resource utilization and effective power consumption but did not involve a real-world workload. Dubey and Sharma [9] enhanced a nature-based intelligent water drop (IWD) algorithm for optimal VM allocation. It optimizes the task execution in a secure cloud environment. A CloudSim simulation was used to analyze the aforementioned algorithm. The performance of the work showed better outcomes than other existing VM allocation policies in terms of host utilization, timespan, and efficiency; however, it was not applicable to the dynamic placement of VM. Karmakar et al. [12] proposed a high-performance multiobjective optimization technique that schedules frequently communicating VM of data centers in proximity to reduce communication costs and delays among the VM and improve the QoS of the system. Ant colony optimization (ACO) has been used to efficiently consolidate VM. It aims to reduce resource wastage by properly utilizing the resources of active servers, but requires a more efficient approach to solve the load balancing problem. In [13], different types of complex applications with different priorities and resource demands are involved. An approach handling priority, power, and traffic was framed to minimize the network and power consumption of a multidimensional and heterogeneous cloud data center, along with the consideration of resource utilization. The proposed work has been compared with a fat tree topology and it has shown a decrease of 29% in total network utilization, 18% in electricity consumption, and 68% in resource waste. This approach requires improvisation to introduce more prioritized attributes for applications and experiments. A new metaheuristic has been proposed in the literature [15], which functions to minimize the VM cost and energy consumption. The mechanism focuses on solving the VM problem but does not hold any approach for effective load balancing.

While performing an analytical study of the literature on cloud computing, the following research gaps were identified:

1. Several studies have focused on overcoming the problems of VM migration and power consumption. New VM placement mechanisms are required to enrich resource utilization and limit resource wastage and fragmentation, thereby maintaining a balance between the demand and supply of cloud providers and users [5, 7].
2. VM Placement algorithms must be applied to a real workload to validate their real robustness, in contrast to previous algorithms that do not involve real-world resource demands in their evaluation [6].
3. Traditional techniques generally focus on a few parameters to solve VM allocation problem [8, 9]. However, with an increase in workload demand, other core parameters cannot be ignored. Hence, new approaches are required to address multiple factors simultaneously, thereby addressing important issues, such as load balancing, resource utilization, QoS, SLA violations, network traffic, latency, and operational cost.

This paper presents a new simulated annealing-intelligent water drop cycle algorithm (SA-IWDCA) framework for solving VM placement problems based on the hybridization of nature-inspired IWD and water cycle algorithm (WCA) approaches integrated with SA.

• The proposed approach enhances the performance of the data center by properly utilizing and balancing the computing resources among the VM to reduce the number of active servers.
• The introduction of SA improved the productivity of the framework by performing multiple local searches using neighborhood configuration and refined the solution quality by involving its targeted approaches of temperature scheduling and cooling factors.
• Simulations and analytical studies were performed on three extensive datasets: i) a real workload trace of bitbrains, ii) a Normal distribution, and iii) application instances of Amazon EC2.

The remainder of this paper is organized as follows: Section 2 provides a basic overview of VM placement using different heuristic and metaheuristic techniques. Section 3 provides a detailed description of the proposed SA-IWDCA method. In Section 4, the SA-IWDCA is compared with the IWDCA, IWD, and WCA, and the simulation results are obtained. Finally, Section 5 concludes the paper and presents future aspects of the proposed work.

2. Problem Formulation

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

VM placement plays an important role in cloud environments. Cloud service providers continuously improve and update VM allocation policies to satisfy their users with their respective resource requests, considering the enhancement in energy saving approaches, resource utilization practices, and simultaneously maintaining the QoS of cloud data centers [14].

2.1 VM Placement

The VM placement problem is considered an NP-hard problem and can be formulated as a multidimensional bin-packing problem.

A cloud data center is developed by combining many homogeneous and heterogeneous M numbers of PM in the cloud, and is expressed as follows:

(1)PM={P1, P2, P3, P4, P5, …, Pn}.

Each PM holds its own set of computing resources, which include the ID, CPU, bandwidth, memory, and cores, as mentioned in

(2)PMi={PID, Pcpu, PBW, Pmem, Pcores}.

Here, P_ID denotes the identification number of a particular PM in the data center. P_cpu, P_BW, P_mem, and P_cores are the CPU capacity, bandwidth range, RAM capacity, and number of processing cores allocated to a particular PM, respectively.

Users send requests to a group of N virtual machines for their applications to be deployed on them or for the execution of different types of tasks. It is expressed as follows:

(3)VM={V1, V2, V3, V4, V5, …, Vm}.

A VM requires certain resources to execute user requests, which are represented as follows:

(4)VMi={Vid, Vcpu, VBW, Vmem}.

V_id is a unique number assigned to each VM for identification in the datacenter, and V_cpu, V_BW, and V_mem denote the CPU capacity, allocated bandwidth range, and memory capacity of the VM, respectively. The VM placement problem considers the following constraints [16] before allocating the VM to servers:

(5)i∑mi(Vid)≤Pid,

(6)i∑mi(Vm)≤Pm,

(7)i∑mi(Vcpu)≤Pcpu,

(8)i∑mi(VBW)≤PBW.

Constraint in Eq. (5) ensures that a VM is assigned to only one PM in the cloud datacenter. Constraints in Eqs. (6), (7), and (8) ensure that the resources requested by the VM do not exceed the resource capacity of the host PM.

2.2 Proposed Framework

This section introduces a new mechanism for the optimal allocation of VM to desirable servers in the cloud. The proposed SA-IWDCA was developed to minimize the energy consumption and resource dissipation of the PM. It aims to enhance and maintain the performance of a data center on a larger workload scale.

In the proposed method, the IWD utilizes its exploration capabilities and gradually generates the initial VM solution, whereas the WCA focuses on its exploitation properties and avoids premature convergence. With SA, the probability of reaching the global optimal solution increases because it concurrently evaluates multiple points in a larger search space. Hence, by integrating the advantages of the IWD, WCA, and SA, a new mechanism was developed to obtain improved results.

The algorithm comprises two prime levels. At the first level, the IWD acts as a preselection algorithm and develops an initial solution using a graph-based approach. The pregenerated solution is seeded into the WCA as the input. The WCA generates a few random solutions, combines them with previously generated solutions from the IWD, and performs multiple searches to improve all solutions. WCA classifies all solutions as sea, river, or stream based on their fitness values. The best solution, that is, the sea solution from the WCA is sent to the SA. SA creates different new configurations from the existing solution based on inversion, translation, and switching operations and accepts the new configuration as the global best solution if it proves to be better solution than that received from WCA. This process continues until it reaches the maximum number of iterations. Figure 1 shows a flowchart of the SA-IWDCA.

2.2.1 Intelligent water drop

The IWD is a population-based metaheuristic optimization algorithm [6]. It operates on the behavioral properties of water drop movements in rivers, lakes, and streams to find paths along different landforms.

The IWD was mapped in the form of a graph G = (V,E) to solve the VM placement problem. V depicts the VM nodes, and E refers to the connecting edges among the nodes. The basic concept of finding an optimal path or solution by IWD is to traverse from a starting node toward an unvisited node via connecting edges and continue traversing until all nodes in the graph are accessed. The procedure of the IWD algorithm depends on the following three attributes:

1. Velocity of the IWD
2. Soil on the IWD
3. Soil on the connecting edges.

The values of these attributes continues to change as the water drops to determine their paths. Initially, the IWD has some velocity to flow through the graph, but does not carry any soil. The connecting edges hold some soil but when it traverses from one node ‘i’ to another node ‘j’ via that connecting edge, IWD removes it. The gain in soil carried by the IWD is calculated using Eq. (9).

(9)soilIWD=soilIWD+δsoilIWD(i,j).

Here, δsoil^IWD(i, j) is the soil removed by IWD from the connecting edge while traveling from node i to node j.

Similarly, the amount of soil on the connecting edges is used to calculate the velocity of the IWD using Eq. (10). The velocity of the IWD is inversely proportional to the soil at the traversed edge. The IWD follows a path (connecting edge) with a greater velocity and a lesser amount of soil.

(10)δvelIWD(i,j)∝1soilIWD.

The amount of soil removed from the traversed edge by the IWD is calculated using Eq. (11) and is inversely proportional to the time required to reach the edge. The time required by an IWD to travel from one node to another is formulated using Eq. (12). Here, HUD denotes the probability of accepting a node for creating a path.

(11)δsoilIWD(i,j)∝1time(i,j),

(12)time(i,j)=HUDvelIWD.

The IWD finds a suitable path by selecting the edges with the minimum amount of soil. This process continues until all the nodes are traversed and an optimal path is obtained in the form of a VM placement solution. The algorithm terminates when it reaches the maximum number of iterations and the optimal VM solution is obtained as the output.

2.2.2 Water cycle algorithm

The WCA is a swarm-based metaheuristic technique that aims to find an optimal or near-optimal solution [17]. It performs its optimization by drawing inspiration from the flow of rainwater and small streams into rivers and the sea.

The WCA comprises less complicated user-defined parameters, enabling it to easily solve different types of optimization problems.

The WCA finds an optimal solution for VM placement through a water cycle process. The algorithm begins with a rain process, followed by the random generation of the initial population in the form of raindrops (the VM placement solution).

Subsequently, the raindrops are categorized into streams, rivers, and sea by evaluating their fitness values. The best raindrop, having the smallest fitness value, is selected as the sea, raindrops with fitness values closer to the sea value are chosen as rivers, and the remaining raindrops are defined as streams. The intensity of the flow of streams into the corresponding rivers and sea is then calculated using Eq. (13), and the intensity flow of the rivers into the sea is calculated using Eq. (14).

(13)λsea=Round{FseaFsea+∑r=1Rf(Riverr)}×S,

(14)λj=Round{F(River j)Fsea+∑r=1Rf(Riverr)}×S.

Here, λ_sea represents the number of streams flowing directly into the sea and λ_j represents the number of streams flowing into the jth river. F(sea) and F(River_j) hold the fitness values of the sea solution and jth river solution, respectively.

After evaluating the intensities of the rivers and streams, new positions for the streams and rivers (closer to the sea) are determined. The fitness values of streams are then compared with those of their corresponding rivers and seas, and if the value of a stream is lower than that of a river or sea, then that stream attains the position of the river or sea.

Similarly, if the fitness value of any of the rivers is lower than that of the sea, the river reaches the position of the sea and becomes a river. The positions of the sea, river, and streams are updated as given in Eqs. (15) and (16).

(15)Stream(newj,i)=Stream(j,i)+Rand×C×(Riveri(j)-Stream(i,j)),

(16)River(newj,i)=River(j,i)+Rand×C×(Seai-River(j,i)).

Stream_new and Stream(j, i) depict the new and old values of the stream, respectively. River_new and River(j, i) are the new and old river values, respectively. Sea_i represents the position of the sea, and Rand is a random number between [0, 1]. C is a value chosen between [1, 2] to generate the distance between the stream and river as well as river and sea. The best value for C is two. This process continues until it reaches the maximum number of iterations.

2.2.3 Simulated annealing

The SA is one of the most popular heuristic techniques for solving various problems. It operates on the principle of an annealing process, wherein a metal is heated and cooled slowly to obtain molded into a desired structure. SA was introduced to solve and generate global optimal solutions for VM placement problems [1, 10]. This is preferred because it performs a local search across a wider range while avoiding local optima. The mapping of the proposed technique with SA is illustrated as follows:

1) New neighboring configuration

An optimal VM placement solution from the WCA is used to generate a new neighboring configuration. The aim is to provide better placement solutions for VM placement problems. The following three techniques are used to create a new configuration from the existing placement solution:
- a) Inversion: In the inversion process, a few VM positions are swapped to create a new VM placement configuration (Figure 2).
- b) Translation: In this process, two or more consecutive VMs are positioned in front of a randomly selected sequence of two or more VMs to change the previous VM placement configuration (Figure 3).
- c) Switching: This technique randomly selects two VM and sets them into each other’s position (Figure 4).
  
  At each iteration, only one operation is performed randomly on the existing solution to generate a new placement configuration. This procedure helps achieve suboptimal results.
2) Acceptance criteria

The acceptance criterion determines whether to accept the new configuration or retain the existing solution for the next state. The decision is based on the acceptance probability, which is evaluated using

(17)If δ<expfitnessvalue(new)-fitnessvalue(old),then Best Placement=New Placement.

Here, δ has a value between [0, 1]. Fitnessvalue(new) is the fitness value of the new configuration, and the Fitnessvalue(old) is the fitness value of the current configuration.
3) Temperature scheduling

Temperature is an important parameter that controls execution in SA. The initial temperature is set and gradually decreases at each iteration. The scheduling of temperature determines whether to accept a new solution. The cooling process depicts a low probability of accepting worse solutions. In the proposed method, we have set the initial temperature as 1, 000°C and it decreases by 5°C at every iteration till it reaches zero.

3. Experiments

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

This section presents an experimental review and analysis of the proposed SA-IWDCA. We compared our proposed framework with different nature-inspired algorithms, that is, the IWDCA, IWD, and WCA, in terms of resource utilization, number of active PM, energy consumption, and resource fragmentation of the PM. The following subsections present the scenarios, datasets, and parameter-setting definitions, along with the final evaluation.

3.1 Analysis Parameters

3.1.1 Number of PM

The requested VM was hosted on an available PM. Systematic placement decisions of VM on the minimum number of servers addresse different issues of cloud datacenters, particularly energy consumption and operational costs.

3.1.2 Energy consumption

The CPU, disk storage, bandwidth, and memory of the PM significantly affect the energy consumption of data centers. Most of the energy is consumed during CPU utilization, which affects the overall energy consumption of cloud datacenters. The total energy consumption of the PM is evaluated as follows:

(18)Pi=(Pmax-Pidle)UiCPU+Pidle,

where P_max and P_idle represent the energy consumption of the servers when they are fully loaded and idle, respectively, and U_i_CPU is the CPU utilization rate of PM_i.

3.1.3 Resource utilization

Balancing resources can result in drastic changes in the performance and profits of cloud providers. The resource utilization of the PM was calculated using the following equations:

(19)AverageTotalResources=(PMCPU+PMRAM)/2,

(20)SDCPU=(cpu/AverageTotalResources-1)∧2,

(21)SDRAM=(ram/AverageTotalResources-1)∧2,

(22)Variance=sqrt(SDCPU+SDRAM).

The standard deviation and variance of the CPU as well as memory utilization of all hosts were calculated using Eqs. (20)–(22).

3.1.4 Resource fragmentation

Checking for resource fragmentation is crucial to achieve better resource utilization and enhanced performance. The PM resource fragmentation can be calculated using Eq. (23) as follows:

(23)Rf(j)=∑p,mNR(p)j-NR(m)j∑(d)NU(d)j,

where Rf(j) represents the resource fragmentation of jth PM. NR(m)j and NR(p)j represents the smallest normalized resource residual and another normalized residual resource of jth PM. Rf(j) provides the ratio between the difference of the smallest residual resource with the other residual resources and sum of normalized used resources of PM.

3.2 Experimental Setup

The effectiveness of SA-IWDCA must be tested under different circumstances to verify its reliability and robustness. Hence, the proposed mechanism was evaluated through experiments conducted using MATLAB 2020b. The hardware configuration used for implementing the proposed work had a 3.2 GHz CPU, 1 TB HDD, and 8 GB of RAM.

Because the performance of the proposed SA-IWDCA depends on the size and number of both VM and PM, different extensive scenarios along with resource variations of the requested VM have been considered to investigate the potential scalability of different algorithms. The algorithms were compared on three different datasets with VM in batches of 200, 400, 600, and 800. The first dataset consisted of VM requirements equivalent to the application instances of Amazon EC2. Table 1 lists the values for the instances used in the simulations.

The second dataset is the real-time workload trace GWA-T-12 bitbrains, which stores the performance metrics of VM from the distributed data centers of bitbrains. Bitbrains provides services and performs hosting and business computations for different enterprises. The values of the memory and CPU cores requested by the VM were extracted from the trace. For the third dataset, VM requests were generated using a normal distribution. It provides the VM resource requirements of the VM requests (μ, σ) and depicts the normal distribution having CPU and memory capacities as .

The performance parameters of the SA-IWDCA exhibited different effects for different values. When performing multiple experiments with different parameter combinations, a few values of the parameters that showed better optimal results were selected, as listed in Table 2.

Two different types of PM were considered, the key specifications of which are listed in Table 3. The power of the PM was 260 W when it was fully loaded and 170 W when it was idle. Moreover, we considered 90% as the server resource threshold for a physical server to adopt a VM.

3.3 Simulation Analysis

This section presents a simulation analysis of SA-IWDCA with respect to other VM placement algorithms. To obtain robust results, the average outcome of 20 independent executions is shown in Figures 5–7, separately illustrating a comparison among different datasets with respect to the number of active PM, resource utilization, energy consumption, and resource fragmentation of the PM.

3.3.1 Scenario 1

The performances of all bio-inspired algorithms for Dataset 1 are depicted in Figure 5. Figure 5(a) depicts the number of PM used by the respective algorithms for hosting and satisfying the VM resource requirements. The proposed SA-IWDCA outperformed the other algorithms by hosting a larger number of VM on a minimal number of PM. We observed that as the number of VM requests increased, the algorithm performed better, as it deployed more VM on fewer servers. Moreover, the simulation results become more improvised as the algorithm undergoes more iterations, and the effectiveness of the algorithms can be verified more precisely. Experiments were performed to evaluate the energy consumption of the respective algorithms to host 200, 400, 600, and 800 VM separately. Balancing computing resources and controlling the power consumption of PM can bring profitable costs for cloud providers. The proposed algorithm showed significant dominance over the other algorithms. Moreover, the IWDCA was comparably better than the IWD and WCA.

Moreover, only IWDCA competes with SA-IWCDA in terms of resource utilization and fragmentation. Both the IWD and WCA showed inferior performances compared to the SA-IWDCA and IWDCA in all cases. However, both IWD and WCA have nearly the same performance in terms of energy consumption, but the WCA was dominated by the IWD in terms of resource utilization. The power consumption of all four algorithms for hosting different VM was evaluated, and we observed that with an increase in the VM request workload, the power consumed by the resources also increases simultaneously. The SA-IWDCA has shown the minimum energy consumption rate in fulfilling the resource needs of its allocated VM compared to the others.

For 400 VM, SA-IWDCA has shown improvements of 15%, 22%, and 25% as compared with IWDCA, IWD, and WCA.

3.3.2 Scenario 2

Figure 6 depicts the analytical study of all the algorithms on Dataset 2 and we can observe that SA-IWDCA has the best VM placement.

3.3.3 Scenario 3

Figure 7 depicts the simulation results for Dataset 3. We can observe that SA-IWDCA involves less resource wastage and deploys more VM than IWDCA when the number of VM requests increases. The results obtained were owing to better placement decisions of SA-IWDCA, which established balanced and efficient resource management to curb resource fragmentation. Figure 7(c) shows the energy consumption of all four algorithms, among which SA-IWDCA has the smallest value and the WCA holds the largest value. The SA-IWDCA was optimized to place the VM in an extremely concentrated manner to minimize the active servers and energy consumption costs. The IWDCA performed satisfactorily. In the WCA and IWD algorithms, CPU utilization was balanced, but the activation of several servers lowered the utilization rate, resulting in performance degradation.

Figure 7(d) shows that the SA-IWDCA outperformed the IWDCA and other existing algorithms in terms of resource fragmentation. This is because the CPU and memory demands of the VM have a significant impact on the resource wastage of the PM, which is properly managed by the SA-IWDCA. Moreover, to overcome resource fragmentation, SA-IWDCA focuses on both the resource utilization of the server and the resource requests of the VM.

4. Conclusion

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Efficient VM allocation provides a boost and profitable business for cloud service providers. The proposed SA-IWDCA was developed to efficiently solve VM placement problems in cloud datacenters. The IWD explores a larger search space to avoid slipping into local optima traps using the probability heuristic function, whereas the WCA performs multiple local searches based on the functioning of the water cycle process to refine and discover the finest VM solution among the others. In addition, SA is used to locate the global minimum of a function in a large and discrete search space. The temperature scheduling and cooling factors facilitate the SA in moving closer toward the optimum VM solution. The primary objective of the proposed mechanism is to efficiently utilize PM resources and maintain the energy consumption of the PM by considering the QoS and resource fragmentation rate. The proposed work was designed under the simulation environment of the MATLAB platform, and the simulation results proved that the proposed technique performs well when considering energy consumption and resource utilization as priorities.

Conflict of Interest

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

No potential conflict of interest relevant to this article was reported.

Figures

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Fig. 1.

Flow chart of SA-IWDCA.

Fig. 2.

Inversion process.

Fig. 3.

Translation process.

Fig. 4.

Switching process.

Fig. 5.

Dataset 1: (a) number of active servers, (b) resource utilization of PM, (c) energy consumption of PM, and (d) resource fragmentation of PM.

Fig. 6.

Dataset 2: (a) number of active servers, (b) resource utilization of PM, (c) energy consumption of PM, and (d) resource fragmentation of PM.

Fig. 7.

Dataset 3: (a) number of active servers, (b) resource utilization of PM, (c) energy consumption of PM, and (d) resource fragmentation of PM.

Tables

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Table. 1.

Table 1. Amazon EC2 instances.

VM instances	CPU	Memory
T2. nano	1	0.5
T2. micro	1	1
T2. small	1	2
T2. medium	2	4
T2. large	2	8

Table. 2.

Table 2. Algorithm parameters.

Parameters	Value
Size of the population	15
Maximum Iteration	50
Value of initial soil	10,000
Velocity parameters: av, bv, cv	1
Soil parameters: as, bs	0.01
Probability constant (ρ)	0.9
No. of rivers	6
Random (Rnd)	2
Temperature (T)	1000

Table. 3.

Table 3. Server specification.

Server type	MIPS	Storage (GB)	Memory (GB)
HP ProLiant G4	1860	4	1000
HP ProLiant G5	2660	4	1000

References

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Patra, K, Misra, S, Sahoo, B, and Turuk, AK (2022). GWO-based simulated annealing approach for load balancing in cloud for hosting container as a service. Applied Sciences. 12. article no 11115
Kumar, M (2021). Suman, “Meta-heuristics techniques in cloud computing: applications and challenges. Indian Journal of Computer Science and Engineering (IJCSE). 12, 385-395. https://doi.org/10.21817/indjcse/2021/v12i2/211202055
Madhumala, RB, Tiwari, H, and Verma, D . Hybrid model for virtual machine optimization in cloud data center., Proceedings of 2021 5th International Conference on Intelligent Computing and Control Systems (ICICCS), 2021, Madurai, India, Array, pp.137-141. https://doi.org/10.1109/ICICCS51141.2021.9432149
Singhrova, A, and Anu, A (2020). Prioritized GA-PSO algorithm for efficient resource allocation in fog computing. Indian Journal of Computer Science Engineering. 11, 907-916. https://doi.org/10.21817/indjcse/2020/v11i6/201106205
Kumar, J, Singh, AK, and Mohan, A (2021). Resource-efficient load-balancing framework for cloud data center networks. ETRI Journal. 43, 53-63. https://doi.org/10.4218/etrij.2019-0294
Eswaran, S, Dominic, D, Natarajan, J, and Honnavalli, PB (2020). Augmented intelligent water drops optimisation model for virtual machine placement in cloud environment. IET Networks. 9, 215-222. https://doi.org/10.1049/iet-net.2019.0165
Azizi, S, Zandsalimi, MH, and Li, D (2020). An energy-efficient algorithm for virtual machine placement optimization in cloud data centers. Cluster Computing. 23, 3421-3434. https://doi.org/10.1007/s10586-02003096-0
Madhusudhan, HS, and Satish Kumar, T (2020). Energy and fault aware virtual machine allocation using machine learning for cloud infrastructure. International Journal of Advanced Science and Technology. 29, 2472-2482.
Dubey, K, and Sharma, SC (2022). An extended intelligent water drop approach for efficient VM allocation in secure cloud computing framework. Journal of King Saud University-Computer and Information Sciences. 34, 3948-3958. https://doi.org/10.1016/j.jksuci.2020.11.001
Dubey, K, Sharmaan, SC, and Nasr, AA . A simulated annealing based energy-efficient VM placement policy in cloud computing., Proceedings of 2020 International Conference on Emerging Trends in Information Technology and Engineering (ic-ETITE), 2020, Array, pp.1-5. https://doi.org/10.1109/ic-ETITE47903.2020.119
Alharbe, N, Aljohani, A, and Rakrouki, MA (2022). A fuzzy grouping genetic algorithm for solving a real-world virtual machine placement problem in a healthcare-cloud. Algorithms. 15. article no 128
Karmakar, K, Das, RK, and Khatua, S (2022). An ACO-based multi-objective optimization for cooperating VM placement in cloud data center. The Journal of Supercomputing. 78, 3039-3121. https://doi.org/10.1007/s11227-021-03978-z
Omer, S, Azizi, S, Shojafar, M, and Tafazolli, R (2021). A priority, power and traffic-aware virtual machine placement of IoT applications in cloud data centers. Journal of Systems Architecture. 115. article no 101996
Farzai, S, Shirvani, MH, and Rabbani, M (2020). Multi-objective communication-aware optimization for virtual machine placement in cloud datacenters. Sustainable Computing: Informatics and Systems. 28. article no 100374
Alhammadi, ASA, and Vasanthi, V . Multi-objective algorithms for virtual machine selection and placement in cloud data center., Proceedings of 2021 International Congress of Advanced Technology and Engineering (ICOTEN), 2021, Taiz, Yemen, Array, pp.1-7. https://doi.org/10.1109/ICOTEN52080.2021.9493496
Dubey, K, Nasr, AA, Sharma, SC, El-Bahnasawy, N, Attiya, G, and El-Sayed, A (2020). Efficient VM placement policy for data centre in cloud environment. Soft Computing: Theories and Applications. Singapore: Springer, pp. 301-309 https://doi.org/10.1007/978-981-15-0751-9_28
Eskandar, H, Sadollah, A, Bahreininejad, A, and Hamdi, M (2012). Water cycle algorithm: a novel metaheuristic optimization method for solving constrained engineering optimization problems. Computers & Structures. 110, 151-166. https://doi.org/10.1016/j.compstruc.2012.07.010

Biographies

Go to

Abstract
1. Introduction
2. Problem Formulation
3. Experiments
4. Conclusion
Conflict of Interest
Figures
Tables
References
Biographies

Chayan Bhatt is a research scholar at the Department of Computer Science Engineering of Manipal University, Jaipur, India since 2017. She has pursued an M.Tech from Manipal University, Jaipur. Her current research focuses on cloud computing and machine learning.

E-mail: chayan.bhatt53@gmail.com

Sunita Singhal is an associate professor at the School of Computing and Information Technology of Manipal University, Jaipur, India since 2016. She worked at the Birla Institute of Technology and Science (BITS), Pilani Campus, Pilani, India, in 2005. Her current research focuses on cloud computing, high-performance computing, the Internet of Things, and distributed computing. She has published several papers at international conferences and in journals over the past few years. She acted as a member of the organizing and program committees of many international conferences and workshops.

E-mail: sunita.singhal@jaipur.manipal.edu

Article

Original Article

International Journal of Fuzzy Logic and Intelligent Systems 2023; 23(3): 353-364

Published online September 25, 2023 https://doi.org/10.5391/IJFIS.2023.23.3.353

Hybrid Metaheuristic Technique for Optimization of Virtual Machine Placement in Cloud

Chayan Bhatt and Sunita Singhal

Department of Computer Science and Engineering, Manipal University Jaipur, Jaipur, India

Correspondence to:Sunita Singhal (sunita.singhal@jaipur.manipal.edu)

Received: March 10, 2023; Revised: June 8, 2023; Accepted: July 18, 2023

Abstract

Keywords: Virtual machine placement, Cloud computing, Water cycle algorithm, Intelligent water drop, Simulated annealing, Energy consumption

1. Introduction

While performing an analytical study of the literature on cloud computing, the following research gaps were identified:

1. Several studies have focused on overcoming the problems of VM migration and power consumption. New VM placement mechanisms are required to enrich resource utilization and limit resource wastage and fragmentation, thereby maintaining a balance between the demand and supply of cloud providers and users [5, 7].
2. VM Placement algorithms must be applied to a real workload to validate their real robustness, in contrast to previous algorithms that do not involve real-world resource demands in their evaluation [6].
3. Traditional techniques generally focus on a few parameters to solve VM allocation problem [8, 9]. However, with an increase in workload demand, other core parameters cannot be ignored. Hence, new approaches are required to address multiple factors simultaneously, thereby addressing important issues, such as load balancing, resource utilization, QoS, SLA violations, network traffic, latency, and operational cost.

• The proposed approach enhances the performance of the data center by properly utilizing and balancing the computing resources among the VM to reduce the number of active servers.
• The introduction of SA improved the productivity of the framework by performing multiple local searches using neighborhood configuration and refined the solution quality by involving its targeted approaches of temperature scheduling and cooling factors.
• Simulations and analytical studies were performed on three extensive datasets: i) a real workload trace of bitbrains, ii) a Normal distribution, and iii) application instances of Amazon EC2.

2. Problem Formulation

2.1 VM Placement

The VM placement problem is considered an NP-hard problem and can be formulated as a multidimensional bin-packing problem.

A cloud data center is developed by combining many homogeneous and heterogeneous M numbers of PM in the cloud, and is expressed as follows:

(1)

PM = {P_{1}, P_{2}, P_{3}, P_{4}, P_{5}, \dots, P_{n}} .

Each PM holds its own set of computing resources, which include the ID, CPU, bandwidth, memory, and cores, as mentioned in

(2)

{PM}_{i} = {P_{ID}, P_{cpu}, P_{BW}, P_{mem}, P_{cores}} .

Users send requests to a group of N virtual machines for their applications to be deployed on them or for the execution of different types of tasks. It is expressed as follows:

(3)

VM = {V_{1}, V_{2}, V_{3}, V_{4}, V_{5}, \dots, V_{m}} .

A VM requires certain resources to execute user requests, which are represented as follows:

(4)

{VM}_{i} = {V_{id}, V_{cpu}, V_{BW}, V_{mem}} .

(5)

i \sum^{m_{i}} (V_{id}) \leq P_{id},

(6)

i \sum^{m_{i}} (V_{m}) \leq P_{m},

(7)

i \sum^{m_{i}} (V_{cpu}) \leq P_{cpu},

(8)

i \sum^{m_{i}} (V_{BW}) \leq P_{BW} .

2.2 Proposed Framework

2.2.1 Intelligent water drop

1. Velocity of the IWD
2. Soil on the IWD
3. Soil on the connecting edges.

(9)

{s o i l}^{IWD} = {s o i l}^{IWD} + δ {s o i l}^{IWD} (i, j) .

Here, δsoil^IWD(i, j) is the soil removed by IWD from the connecting edge while traveling from node i to node j.

(10)

δ {v e l}^{IWD} (i, j) \propto \frac{1}{{s o i l}^{IWD}} .

(11)

δ {s o i l}^{I W D} (i, j) \propto \frac{1}{t i m e (i, j)},

(12)

time (i, j) = \frac{H U D}{{v e l}^{IWD}} .

2.2.2 Water cycle algorithm

The WCA comprises less complicated user-defined parameters, enabling it to easily solve different types of optimization problems.

(13)

λ_{s e a} = R o u n d {\frac{F_{s e a}}{F_{s e a} + \sum_{r = 1}^{R} f (R i v e r_{r})}} \times S,

(14)

λ_{j} = R o u n d {\frac{F (R i v e r j)}{F_{s e a} + \sum_{r = 1}^{R} f (R i v e r_{r})}} \times S .

(15)

S t r e a m (n e w_{j}, i) = S t r e a m (j, i) + R a n d \times C \times (R i v e r_{i} (j) - S t r e a m (i, j)),

(16)

R i v e r (n e w_{j}, i) = R i v e r (j, i) + R a n d \times C \times (S e a_{i} - R i v e r (j, i)) .

2.2.3 Simulated annealing

1) New neighboring configuration

An optimal VM placement solution from the WCA is used to generate a new neighboring configuration. The aim is to provide better placement solutions for VM placement problems. The following three techniques are used to create a new configuration from the existing placement solution:
- a) Inversion: In the inversion process, a few VM positions are swapped to create a new VM placement configuration (Figure 2).
- b) Translation: In this process, two or more consecutive VMs are positioned in front of a randomly selected sequence of two or more VMs to change the previous VM placement configuration (Figure 3).
- c) Switching: This technique randomly selects two VM and sets them into each other’s position (Figure 4).
  
  At each iteration, only one operation is performed randomly on the existing solution to generate a new placement configuration. This procedure helps achieve suboptimal results.
2) Acceptance criteria

The acceptance criterion determines whether to accept the new configuration or retain the existing solution for the next state. The decision is based on the acceptance probability, which is evaluated using

(17) $\begin{array}{l} If δ < {exp}^{fitnessvalue (new) - fitnessvalue (old)}, \\ then Best Placement = New Placement . \end{array}$

Here, δ has a value between [0, 1]. Fitnessvalue(new) is the fitness value of the new configuration, and the Fitnessvalue(old) is the fitness value of the current configuration.
3) Temperature scheduling

Temperature is an important parameter that controls execution in SA. The initial temperature is set and gradually decreases at each iteration. The scheduling of temperature determines whether to accept a new solution. The cooling process depicts a low probability of accepting worse solutions. In the proposed method, we have set the initial temperature as 1, 000°C and it decreases by 5°C at every iteration till it reaches zero.

3. Experiments

3.1 Analysis Parameters

3.1.1 Number of PM

3.1.2 Energy consumption

(18)

P_{i} = (P_{max} - P_{idle}) U_{i CPU} + P_{idle},

where P_max and P_idle represent the energy consumption of the servers when they are fully loaded and idle, respectively, and U_i_CPU is the CPU utilization rate of PM_i.

3.1.3 Resource utilization

Balancing resources can result in drastic changes in the performance and profits of cloud providers. The resource utilization of the PM was calculated using the following equations:

(19)

{Average}_{TotalResources} = ({PM}_{CPU} + {PM}_{RAM}) / 2,

(20)

{SD}_{CPU} = (cpu / {Average}_{TotalResources} - 1) \land 2,

(21)

{SD}_{RAM} = (ram / {Average}_{TotalResources} - 1) \land 2,

(22)

Variance = sqrt ({SD}_{CPU} + {SD}_{RAM}) .

The standard deviation and variance of the CPU as well as memory utilization of all hosts were calculated using Eqs. (20)–(22).

3.1.4 Resource fragmentation

Checking for resource fragmentation is crucial to achieve better resource utilization and enhanced performance. The PM resource fragmentation can be calculated using Eq. (23) as follows:

(23)

R f (j) = \frac{\sum p, mNR (p) j - NR (m) j}{\sum (d) NU (d) j},

3.2 Experimental Setup

3.3 Simulation Analysis

3.3.1 Scenario 1

For 400 VM, SA-IWDCA has shown improvements of 15%, 22%, and 25% as compared with IWDCA, IWD, and WCA.

3.3.2 Scenario 2

Figure 6 depicts the analytical study of all the algorithms on Dataset 2 and we can observe that SA-IWDCA has the best VM placement.

3.3.3 Scenario 3

Fig 1.

Download