An Approximation Algorithm for Sharing-Aware Virtual Machine Revenue Maximization

doi:10.1109/TSC.2017.2786728

Return

An Approximation Algorithm for Sharing-Aware Virtual Machine Revenue Maximization

2021-01-01

Daniel Grosu *

DOI：10.1109/TSC.2017.2786728

Original

Save

View PDF

Abstract

En 中文

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.

Keywords:

Approximation algorithm

multilinear programming

multidimensional knapsack

sharing-aware

virtual machine

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.