Provisioning of requests for virtual machine sets with placement constraints in IaaS clouds

We study the problem of optimising the provisioning of collections of virtual machines (VMs) having different placement constraints (e.g., security and anti-collocation) and characteristics (e.g., memory and disk capacity), given a set of physical machines (PMs) with known specifications, in order to achieve the objective of maximising an IaaS cloud provider's revenue. We propose two approaches. The first is based on the formulation of the problem as an integer linear programming (ILP) problem, the solution to which provides an optimal VM placement. The second approach is a heuristic based on classifying the requests into different categories and satisfying the constraints in a particular order using a first fit decreasing (FFD) algorithm for multi-dimensional vector bin packing problem. Given a model of VM placement constraints, offered resources and requests with multiple VM types, both approaches devise a placement plan in a way that maximizes revenue, having due regard both to customer requirements and PM capacities. We evaluate the relative performance of the solutions by means of numerical experiments. The results suggest the optimal solution is not practical for medium to large problems, but it is encouraging that the placement plans of the heuristic are close to those of the optimal solution for smaller problem sizes. We use the heuristic to generate results for large scale placement problems; experiments suggest that it is practical in terms of its runtime efficiency and can provide an effective means of online VM-to-PM mapping.