Optimal energy-efficient placement of virtual machines with divisible sizes

•Allocation of virtual machines with divisible sizes is considered.•Load-dependent energy consumption of servers is allowed.•Energy consumption characteristics described by arbitrary functions.•The problem is a generalization of bin packing.•A polynomial-time algorithm yielding optimal results is pr...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2018-10, Vol.138, p.51-56
Main Authors: Halácsy, Gergely, Mann, Zoltán Ádám
Format: Article
Language:English
Subjects:
Analysis of algorithms
Bin packing
Cloud computing
Divisible item sizes
Virtual machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Allocation of virtual machines with divisible sizes is considered.•Load-dependent energy consumption of servers is allowed.•Energy consumption characteristics described by arbitrary functions.•The problem is a generalization of bin packing.•A polynomial-time algorithm yielding optimal results is provided. A key problem in the management of data centers is how to provision virtual machines based on the available physical machines, because an optimized placement can lead to significant reduction in energy consumption. This problem can be formulated as bin packing with heterogeneous bin types, where the cost of a bin depends on how full it is. We prove that under suitable conditions, an extended version of the First-Fit-Decreasing heuristic delivers optimal results for this problem.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2018.06.003