Home // ICN 2014, The Thirteenth International Conference on Networks // View article

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

Authors:
Ricardo Stegh Camati
Alcides Calsavara
Luiz Lima Jr

Keywords: cloud computing; virtual machine placement; knapsack problem; evaluation method;

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.

Pages: 253 to 260

Copyright: Copyright (c) IARIA, 2014

Publication date: February 23, 2014

Published in: conference

ISSN: 2308-4413

ISBN: 978-1-61208-318-6

Location: Nice, France

Dates: from February 23, 2014 to February 27, 2014