Virtual Machine Placement Using Genetic Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Cloud computing is a large scale distributed computing paradigm in which a pool of computing resources are available to the users via the Internet. Infrastructure-as a-Service (IaaS) is a computational service model applied in the cloud computing paradigm. Virtualization technologies can be used to support computing resource access by the users in this model. Virtual machine placement is the process of mapping virtual machines to physical machines. In other words, virtual machine placement is the process of selecting the most suitable host for the virtual machine.


In cloud computing, resources are shared and if they are not properly distributed then it will result into resource wastage. Another essential role of cloud computing platform is to dynamically balance the load amongst different servers in order to avoid hotspots and improve resource utilization. Most of the Virtual Machine scheduling algorithms consider only current system load and ignore the previous state of the system. The previous state of the machine gives valuable information about Quality of Service (QoS) i.e. it gives the delay that applications suffered by selecting a particular physical machine.


On a cloud computing Platform Dynamic resources can be effectively managed using virtualization technology. Users with more demanding service-level agreement (SLA) can be guaranteed by accommodating all resources into a Virtual machine Image and then mapping it on a physical machine. The virtual machine allocation problem can be divided into two stages. The first is the placement of virtual machines before the infrastructure starts to work. The second is the migration of a virtual machine between servers if there is under- or over-utilization of the hardware resource when the infrastructure is working. Optimal placement of Virtual machine placement can be categorized into 2 groups.

First group deals with the minimum number of physical machines required for current load. We use minimum Bin packing or knapsack problems for finding the number of physical machines. Second group deals with placement of virtual machines in physical machines place a major role in Quality of Service (QoS). If the two dependant virtual machines are placed on different physical machines then network delay places a major overhead in response time. The aim of this project is, in virtual machine scheduling considering previous data in current VM placement along with present state. By doing so we are able to minimise the number of physical servers used in data centre without compromising the quality of service (QoS) which existing algorithms have failed.

Problem statement:

In the current cloud computing environments, virtual machine resource scheduling only considers the current system conditions and ignores the previous state of system which causes the system load imbalance. There is lot of energy consumption because of inefficient usage of physical resources. In this project am going to develop an algorithm which places virtual machines on physical machines effectively so that it reduces the power consumption and maintains the quality of service (QoS). This can be achieved by using genetic algorithm, historical data and current state of the system.


Finding a genetic algorithm for virtual machine placement in a cloud which reduces the energy consumption and improves the Quality of Service (QoS). Energy consumption is reduced by limiting the number of physical machines used i.e. utilizing the physical machines more efficiently. QoS can be achieved by placing more dependant virtual machines as close as possible so that the communication delay should be minimum among them.

Literature Survey:

Virtual machine placement problem is very important. It helps in reducing the expenses that an organization spends on its infrastructure. The placement problem is a non deterministic problem. Following are some of the algorithms that have been used to solve the virtual machine placement problem.

Constraint Programming:

Constraint programming is a programming paradigm. The solution should satisfy the constraints on relations between variables. It is useful for combinatorial search problems. The virtual machine placement problem can be designed as a constraint programming problem as follows.

Constraint: Number of available physical machines and maximizes the global utility function.

Model: Find virtual machine allocation vectors

The use of constraint programming allows mapping of virtual to physical machines that are better than those found by heuristics based on local optimizations and that are frequently globally optimal in the number of physical machines used.

Bin Packing:

The bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used. Many variations of this problem are present, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. Most of the efficient bin packing algorithms use heuristics to accomplish results.

The virtual machine placement problem can be designed as a bin packing problem as follows. The Physical machines can be considered as bins and the virtual machines to be placed can be considered as objects to be filled in the bin.

Stochastic Integer Programming:

Stochastic programming is used for modelling optimization problems that involve uncertainty. Most of the real world problems include some unknown parameters. This cannot be captured by deterministic integer programming. Stochastic programming models take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal is to find some policy that is feasible for all (or almost all) the possible data instances and maximizes the expectation of some function of the decisions and the random variables. Stochastic Integer programming is useful in cases where actual demands are not known but the distribution of demands is known or can be estimated.

The virtual machine placement problem can be designed as a stochastic integer programming problem as follows. The demands and prices are known (or can be estimated) and the objective is to minimize the budget of the user.

Genetic Algorithm:

A genetic algorithm (GA) is a search technique used to find exact or approximate solutions to optimization and search problems. It is particularly useful in problems where objective functions dynamically change. Typically a genetic algorithm starts with a population of solution, applies genetic operators on this which finally results in an optimal solution. Genetic algorithms are categorized as global search heuristics. They are inspired by evolutionary biology such as inheritance, mutation, selection, and crossover. A typical genetic algorithm requires:

a genetic representation of the solution domain

a fitness function to evaluate the solution domain

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent.

Project plan:

In third semester I will survey existing algorithms and developing a new genetic algorithm for virtual machine placement. Creating a cloud setup and implementing the algorithm.

In fourth semester developing a method to find dependencies among VM’s using historical data and current request and migrating the virtual machines to achieve good Quality of Service (QoS)