Online Virtual Machine Placement for Increasing Cloud Provider's Revenue

Cost savings have become a significant challenge in the management of data centers. In this paper, we show that, besides energy consumption, service level agreement (SLA) violations also severely degrade the cost-efficiency of data centers. We present online VM placement algorithms for increasing cloud provider's revenue. First, First-Fit and Harmonic algorithm are devised for VM placement without considering migrations. Both algorithms get the same performance in the worst-case analysis, and equal to the lower bound of the competitive ratio. However, Harmonic algorithm could create more revenue than First-Fit by more than 10 percent when job arriving rate is greater than 1.0. Second, we formulate an optimization problem of maximizing revenue from VM migration, and prove it as NP-Hard by a reduction from 3-Partition problem. Therefore, we propose two heuristics: Least-Reliable-First (LRF) and Decreased-Density-Greedy (DDG). Experiments demonstrate that DDG yields more revenue than LRF when migration cost is low, yet leads to losses when SLA penalty is low or job arriving rate is high, due to the large number of migrations. Finally, we compare the four algorithms above with algorithms adopted in Openstack using a real trace, and find that the results are consistent with the ones using synthetic data.