A Sharing-Aware Greedy Algorithm for Virtual Machine Maximization

Service providers face multiple challenges in hosting an increasing number of virtual machine (VM) instances. Minimizing the utilization of system resources while maximizing the potential for profit are among the most common challenges. Recent studies have investigated memory reclamation techniques focused on virtual technologies, specifically page sharing, for minimizing the utilization of system resources. In this paper, we address the problem of sharing-aware VM maximization in a general sharing model which has as objective finding a subset of VMs that can be hosted by a server with a given memory capacity such that the total profit derived from hosting the subset of VMs is maximized. The sharing-aware VM maximization allocation problem has been shown to be NP-hard. Therefore, we design a greedy approximation algorithm for solving it. We determine the approximation ratio of our greedy algorithm and perform extensive experiments to investigate its performance against other VM allocation algorithms.