Solving the Virtual Machine Placement Problem as a Multiple Multidimensional Knapsack Problem

Ricardo Stegh Camati, Alcides Calsavara, Luiz A. de Paula Lima

International Conference on Networks · 2014 · 36 citations · 9 references

Concepts

Abstract

Effective placement of virtual machines in a cluster of physical machines is essential for optimizing the use of computational resources and reducing the probability of virtual machine reallocation. Many of previous works treat virtual machine placement as an instance of the bin packing problem, as they aim at saving energy. Alternatively, we propose an approach based on the multiple multidimensional knapsack problem, where the main concern is to maximize placement ratio. Several traditionally employed placement algorithms were re-implemented and new algorithms were defined by using such an approach. The algorithms were evaluated with respect to placement ratio, by employing a novel evaluation method that contemplates variation of computational resources heterogeneity in multiple dimensions and also variation of placement density. The experimental results showed that heterogeneity of resources among physical machines impairs the placement ratio, while heterogeneity of resources among virtual machines benefits it. It was also possible to observe that increase of density placement up to a certain point benefits the placement ratio.

References

9