An Approximation Algorithm for Sharing-Aware Virtual Machine Revenue Maximization

作者：Rampersaud, Safraz; Grosu, Daniel^*

来源：IEEE Transactions on Services Computing, 2021, 14(1): 1-15.

DOI：10.1109/TSC.2017.2786728

• Approximation algorithm
• multilinear programming
• multidimensional knapsack
• sharing-aware
• virtual machine

Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this challenge should consider the sharing of memory pages among virtual machines (VMs) and the available capacity of each type of requested resources. We provide such solution by designing a greedy approximation algorithm for solving the sharing-aware virtual machine revenue maximization (SAVMRM) problem. The SAVMRM problem requires determining the set of VMs that can be instantiated on a given server such that the revenue derived from hosting the VMs is maximized. In addition, we model the SAVMRM problem as a multilinear binary program and optimally solve it, while accounting for page sharing and multiple resource constraints. We determine and analyze the approximability properties of our proposed greedy algorithm and evaluate it by performing extensive experiments using Google cluster workload traces. The experimental results show that under various scenarios, our proposed algorithm generates higher revenue than other VM allocation algorithms while achieving significant reduction of allocated memory.

• 出版日期2021-1-1