Physics Computer Science
Computer Science-2021.gz:143354
Computer Science
6f520494e7ea7225042ae25ce5d81e290f4dfd53
Performance of particle swarm optimization bin packing algorithm for dynamic virtual machine placement for the consolidation of cloud server

Infrastructure as a service offered by the cloud computing is one of the most important service. It allows physical machines to get virtualized by creating many instances of virtual machines. Mapping virtual machines on physical machine has become the major challenge in cloud data centres. The dynamic virtual machine placement methods are used to solve this issue with objectives like maximizing the resource utilization, minimizing the energy consumption and maximizing the scalability of data centres. In this paper a virtual machine placement-based bin packaging algorithm is proposed and analysed with four different fitness strategies to obtain the optimal solution. The unimodal (Sphere, Step) and multimodal (Graywang and Rastridge) benchmark functions are used with proposed algorithm for the analysis and obtain the quantitative measurements. The results show that optimizing the mass of particles using the best fitting strategy reduces the energy consumption, resource utilization and improved the scalability of data centres.


Introduction
Cloud computing based on internet has the powerful architecture that the user has to pay only for the services they have used. The three basic components in cloud computing are (i)Client computer, where the end user can interact with cloud, (ii) Distributed servers, where the servers are distributed among different places, (iii) Data centres, where they are the compilation of servers [1]. In cloud datacentres the cloud service providers have been attracted by millions of clients, who are sharing resources using servers. By adding virtualization technologies to the servers, it enables virtual machines (VM) live migration and allows the VM to be freely moved among physical machines (PM). Therefore, several VM can be packed on a single PM known as IOP Publishing doi: 10.1088/1757-899X/1110/1/012007 2 server consolidation [2]. Server Consolidation allows datacentres to improve resource utilization and energy efficiency by placing the virtual machines on the required capacity of the PM [3].
In placing the VM on PM leads to inefficient utilization of the resources, where VMs are periodically reallocated using live migration according to their current resource demand. In order to minimize the number of PM, workload should be balanced and the idle servers are switched to low-power modes which reduce the overall energy consumption and cost. There are many studies has been committed to solve the VM placement, load balancing, energy consumption and cost profit in cloud [4]. We contribute three steps in this research work, (i) The entire service request are considered as particles, grouped ordered to form a group and hunt for good solution.
A virtual machine placement technique-based bin packing algorithm (VMBP) to get an optimal solution, (ii) it is placed in bins, where bins represent a PM and items represents the VM to find the efficient placement of VM. The process of finding solution using particle swarm optimization technique (PSO) embed bin packing (BP) with best fit strategy leads to resource utilization and energy consumption. (iii) The benchmark functions such as Sphere, Step, Graywang and Rastridge are applied to evaluate the VMBP algorithm. It uses the exponential decreasing inertia weight, so that to replace it to the linear inertia weight for autonomous groups particles and to get better balance global search and local search of the algorithm for improving the algorithm's ability [11].
The remainder of the paper is organized as follows, in section 2, related works are discussed, in section 3, the system model for PSO and BP algorithm is explained, and section 4 presents the details of proposed algorithm VMBP followed by section 5 presents the simulation setup and results obtained. In section 6 concludes the paper with discussing the results and future research directions.

Related Works
An energy organization system is planned for the housing zone based on the experimental algorithm to attain the load gain in grid area network and a hybrid genetic-wind-driven (GWD) algorithm is proposed for the load of single homes and multiple homes. There are two types of instance is taken for consideration that single is on-demand case and added is reserved case, the proposed pricing schema algorithm, which is used to reduce the cost of cloud data centres [5]. In the Integration and green camp tutorial, a spatial awareness reduction system (SAPFT) for VM migration was proposed [6]. Energy optimization is performed using an numeral quadratic polynomial (IQP) with linear and quadratic constraints for the data center [7]. The information focus on management and configuration process is designed to be an optimization problem. Because the problem is unpredictable, a cross non-natural bee and group optimization algorithm is projected to optimize the cloud using smart tool resources [8][9], a VM placement optimization algorithm for location identification, to reduce the number of PM identifications. Effective and efficient resource management in grid computing [9].
A data center provides a virtualized stage to switch the vast volume of facility needs from the user. They need properties to run their requests with virtual machines, which can be provisioned and achieved by on-demand. The facts focus administrator must reply to numerous on-demand resource needs by defining where VM are located and how the possessions are owed to them. Assignment of VM is the most exciting part in fog datacentre [10].

System Model
The virtual machine placement problem in datacentre is formulated as bin packing problem of placing the VMs. Many research works focus only on single criterion for virtual machine placement, but real-world problems require multi objective situation, therefore considered the problem of VMP is formulated as multi objective optimization problem and simultaneously optimize resource wastage and energy consumption.

Particle Swarm Optimization problem (PSO)
The PSO method is a swarm-intelligence-based experimental technique for the answer of optimization tricky. It is unpretentious, optimistic and controlling technique. It duplicates the common performance of fishes and birds [12]. In PSO each individual possible solution can be modulated as a particle that moves through the problem in search space S n [13,14]. The position of each particle is determined by the vector Yi € S n and its movement by the velocity of the particle Vi € S n , as shown below, Let Yi (Z+1) denotes the position of i th particle at iteration (z+1). Vi (Z+1) is the velocity of i th particle at iteration (z+1). The position of the particle is changed by adding a velocity Vi (z) to the current position. For each particle, fitness function is based on its own experience (the decisions that it has made so far and the success of each decision) and the knowledge of the performance of other individual particle in its neighborhood. Since the relative importance of these two factors can vary from one decision to another, it is reason to apply random weights to each part, and therefore the velocity will be determined in below equation (2).
The velocity update equation in (2) has three major components, x The first component w referred to as "inertia," It refers to the tendency of the particle to continue in the same direction it has been traveling. x The second component is the best position of the particle pb: (whose corresponding fitness value is called the particle's best), scaled by a random weight c1 * rand (r1).
x The third component is the velocity update equation of the best particle position found by any swarm gb: (whose corresponding fitness value is called global best), scaled by another random weight c2 * rand (r2).

Bin Packing problem (BP)
The tricky can be seen as bin padding problem with adjustable bin sizes, where boxes represent the PM and objects are the VM to be packed. Bin padding tricky is used to parcel the extreme number of VM into a minor number of PM [15,16]. The main purpose of bin padding is to avoid consumption of resources, save energies and reduce price. BP problem can occur in two dimensions therefore in that there are two solutions, (i) Exact called heuristic solutions, are very complex and expensive in terms of computing time, (ii) Approximation called meta heuristic solutions are reliable and the results are obtained very fast. The algorithms used to get this meta heuristic solutions are first fit, next fit, best fit and worst fit [17]. The BP algorithm with best fit strategy has the items are placed in bin with the order they arrived. Therefore, place the next item in bin where its capacity is closest. In cloud data center, there are huge amount of service requests from the user, the cloud service provider who respond to the service request want resources to path their requests by private virtual machines, which can be provisioned and accomplished by on-demand.
However, the usage of resources and consumption of energy is increased so, to reduce the usage of resources the entire service request from the cloud user is considered as particles. In PSO technique, the number of units mix to make a group. The units initialized by assigning the random position of the unit. In every iteration each unit is updated by two" best" values, the one is the best position of the particle that is the fitness value of particle's best called pbest, as well as the another is the best position of the swarm that is the fitness value of particle's best called gbest is found. Then compare the fitness value of pbest value better than gbest if it is true, set the pbest value as gbest. Then update speed and location of the unit, repeat the iteration until the optimal solution is obtained. The updated unit position referred as items and placed in bin. Then, if the item sizes are greater than bin sizes then the VM are placed in bins, an efficient virtual machine placement is done are shown in Fig.4.1.the structure diagram of VMBP algorithm.  The Pseudo code for VMBP has two steps is shown in Fig.4.2, Step 1: Each unit has approximately place and it shows a probable explanation of the aptness function in search space where search space is a set of all probable positions. Each unit i maintains two routes in search space where, commercial route Yi = [yi1, yi2.. Step 2: Each particle is updated as items in bin packing algorithm with best fit statergy. The best fit allocates the items to a bin which has the smallest sufficient space among the free Step 1: For each particle Initialize Yi and Vi

Calculate aptness value
If aptness value better than pbesti Set pbesti as current particle position End For each particle Choose the pbesti value with best fitness value and set as gbesti Calculate particle velocity Then Update the particle position IOP Publishing doi:10.1088/1757-899X/1110/1/012007 6 available space. The minimum item is calculated using the formula min(item size > bin size) if found then place it to that bin or leave the items and check for further items. Repeat the process until the items are placed. The process of finding possible solution using PSO algorithm and embedding bin packing with best fit strategy leads to resource utilization and energy consumption.

Simulation Setup
The VMBP algorithm is used to solve VMP problem. In PSO technique a number of particles integrate to make a swarm and search for good solution. The efficiency in finding solution for benchmark functions with a lower number of particles and iterations leads to extremely simple procedure, easy implementation and very fast convergence rate. The parameters used in this algorithm are the 'number of particles', where PSO take real numbers as particles, it can be set as (x1, x2, x3…X10), 'dimension of particles' which is taken for 30 dimensions for each benchmark functions, 'range of particles' determined as per the benchmark functions and 'Vmax' determines the maximum velocity change of one particle during one iteration. The updated particle velocity of each particles is considered as the PM used in cloud. Therefore, by using the bin packing algorithm with best fit strategy the PM is placed in VM, here occurs resource utilization. In order to test the VMBP algorithm, the number of service request from the cloud user is difficult to handle, where benchmark functions are used to evaluate the algorithm in an efficient manner. Four well known unimodal and multimodal functions parameters are listed in the Tab.1. These functions are used to test good cases because of their nonlinearity and oscillation around the optimal solutions, so there exists a high probability for each optimization technique to trap into local optima. There are two types of benchmark functions namely unimodal functions and multimodal functions. The function having a single optimal solution is unimodal i.e., Sphere and Step. Sphere function contains no local optima and provides a smooth gradient towards global optima and Step function contains infinite number of global minima. Multimodal functions have two are more optimal solutions i.e., Graywang and Rastridge. Graywang function has many widespread local minima, which is regularly distributed and Rastridge function has several local minima and the locations of minima are regularly distributed [19,20].

Experimental Result
To evaluate the multi objective algorithm VMBP with objectives like the resource utilization, energy consumption and scalability of data centres the open-source integrated development environment NetBeans IDE is used. The first part of this section discusses about the resource utilization by decreasing the number of active PM. The next part of the section discusses about the scalability of datacentres. In the rest of the section discuss about the consumption of energy using benchmark functions fitness value.
Resource utilization: In cloud datacentres each user requests single or additional applications with an predictable value of deal that needs a certain number of resources. The datacentre respond to the user desires for VMs are to be located to existing resources. The available resources are to be placed as well as resource utilization also needed for an efficient placement of VM. Therefore, in VMBP algorithm the number of particles taken to make a swarm is updated with position and velocity and the updated particles are taken as items for which they are placed in bin using best fit strategy. The minimum number of ten particles is taken for experiment is considered as ten cloud user requests. Using the algorithm VMBP the ten-user request for PM strives to consolidate ten PM in nine VM resulting in higher resource utilization is shown in Tab.2. The number of physical machines is taken as X axis and the number of virtual machines is taken as Y axis. In VMBP algorithm the minimum bin is calculated and fits the item to the bin shows the placement of virtual machines is done. Therefore, result proves that effectively resource utilization takes place in VMBP placement algorithm are shown in Fig.5.1. Scalability of cloud datacentres: In cloud data center scalability is the ability of PM working well when it is improved or changed in size. Therefore, VMBP algorithm with best fit strategy shows the placement of PM in VM has been changed the size of PM proves the efficient scalability of cloud data centres.
Comparison of benchmark functions fitness value for energy consumption: In VMBP algorithm the fitness value is calculated and compared with four different benchmark functions Sphere, Step, Graywang and Rastridge. The maximum number of iterations for benchmark functions are set to 100 because iterative procedure does not converge at all, the changes in the estimates from iteration to iteration do not get smaller and may even get larger. The fitness value is nothing but the distance travelled by each particle to form a swarm is calculated and compared with average value of benchmark functions. The Tab.3: shows the fitness value table for different benchmark functions. We estimate the energy reduction in formation of each particle to make a swarm using the benchmark functions range. This is calculated by measuring the total energy consumption for all the particles to make a swarm. The minimum fitness value of sphere function is 39.64,step function is 39.88,Graywang is 44.27 and Rastridge is 39.92 therefore sphere function has got excellent performance of minimum fitness value in a given range. The maximum fitness value is also compared for all the benchmark functions to prove the highest point in a given range. The maximum fitness value of sphere function is 62.48, step function is 70.79, Graywang is 70.29 and Rastridge is 62.80 therefore step function has got excellent performance of in comparing maximum fitness value. Depends upon the average fitness value the sphere function travelled a less distance of 48.22, to make a swarm so sphere function has got the least energy consumption when compared with other three functions.
We can observe that in cloud data centres the placement of VM consumes energy will be better by using this VMBP algorithm with fitness value will achieve less energy consumption.

Number of Iterations
Fitness value

Sphere function
Step function

Conclusion and future work
In this paper the problem of dynamic virtual machine placement is expressed as a multi objective optimization tricky targeting to concurrently optimize maybe inconsistent purposes including a well-organized resource utilization, energy consumption and scalability of datacentres. In VMBP algorithm the particles integrate to make swarm and fitness value of swarm is calculated using the benchmark functions. The average fitness value of benchmark functions unimodal (Sphere, Step) and multimodal (Graywang and Rastridge) is compared and efficient energy consumption is obtained. The best fit strategy is used to get the efficient placement of virtual machines. Experimental result obtained shows VMBP algorithm has enhanced the resource utilization, reduces the energy consumption, and improves scalability of datacentres. Four benchmark functions are used to verify the VMBP algorithm for energy consumption. In the future, the projected algorithm will be verified on further benchmark functions for the projected effort.