Elastic virtual machine placement in cloud computing network environments

The growth of cloud computing and the need to support the ever increasing number of applications introduces new challenges and gives rise to various optimization problems, such as calculating the number and location of virtual machines instantiating cloud services to minimize a well-defined cost function. This paper introduces a novel cloud computing network architecture that allows for the formulation of the optimization as an Uncapacitated Facility Location (UFL) problem, where a facility corresponds to an instantiation of a particular service (e.g. a virtual machine). Since UFL is not only difficult (NP-hard and requires global information), but also its centralized solution is non-scalable, the approach followed here is distributed and elastic, and relays local information to improve scalability. In particular, virtual machine replication and merging are proposed and analyzed ensuring overall cost reduction. In addition, a policy that employs virtual machine replication and merging along with migration is proposed to reduce the overall cost for using a service. The efficiency of this policy and its limitations are analyzed and discussed, with simulation results supporting the analytical findings and demonstrating a significant overall cost reduction when the proposed policy is implemented.