  Efficient virtual machine (VM) management can dramatically reduce energy
consumption in data centers. Existing VM management algorithms fall into two
categories based on whether the VMs' resource demands are assumed to be static
or dynamic. The former category fails to maximize the resource utilization as
they cannot adapt to the dynamic nature of VMs' resource demands. Most
approaches in the latter category are heuristical and lack theoretical
performance guarantees. In this work, we formulate dynamic VM management as a
large-scale Markov Decision Process (MDP) problem and derive an optimal
solution. Our analysis of real-world data traces supports our choice of the
modeling approach. However, solving the large-scale MDP problem suffers from
the curse of dimensionality. Therefore, we further exploit the special
structure of the problem and propose an approximate MDP-based dynamic VM
management method, called MadVM. We prove the convergence of MadVM and analyze
the bound of its approximation error. Moreover, MadVM can be implemented in a
distributed system, which should suit the needs of real data centers. Extensive
simulations based on two real-world workload traces show that MadVM achieves
significant performance gains over two existing baseline approaches in power
consumption, resource shortage and the number of VM migrations. Specifically,
the more intensely the resource demands fluctuate, the more MadVM outperforms.
