Truthful Double Auction Based VM Allocation for Revenue-Energy Trade-Off in Cloud Data Centers

With the advances in virtualization technologies, cloud has emerged as a flexible and cost-effective service paradigm by provisioning on-demand VM resources to users via a pay-per-use business model. In cloud data centers, effective resource provisioning is required with the aim of minimizing energy consumption and maximizing cloud provider's revenue. However, the existing mechanisms have either focused on the optimization of energy, or the profit of cloud service provider (CSP) while incurring inefficient resource allocation. Thus to address these fundamental research challenges and to balance the trade-off between energy and revenue, we propose a Vickrey-Clarke-Groves (VCG) based truthful double auction mechanism (TDAM). In this paper, first, we have formulated a joint optimization problem and prove it NP-hard by reducing it to a multi-dimensional bin-packing problem. Then we design TDAM, a truthful double auction scheme and propose an efficient winning bid algorithm for VM allocation and a VCG based mechanism for calculating payment of each bid. Being a double auction, TDAM allows both the buyers (VMs) and the sellers (PMs) to submit their bids and asks respectively, and performs allocation based on the energy consumption, while upholding truthfulness, in order to avoid falsification of the submitted bid or ask values. Through theoretical analysis and extensive experiments we show that the TDAM makes a significant contribution while maintaining truthfulness, individual rationality, economic efficiency, and has polynomial time complexity.

I. Introduction

Cloud computing provides flexible and cost-effective services by enabling on-demand provisioning of computational resources based on the pay-per-use business model. With the help of cloud platforms such as Amazon EC2 and Microsoft Azure, individual users can submit their request of required resources (e.g. CPU, memory, network bandwidth, and storage) to cloud service providers (CSPs). The CSPs then make resources available to users in the form of VMs in exchange for financial remuneration [1]. An efficient VM allocation is a challenging problem because while satisfying various user requirements, it has to maintain a trade-off between CSP's profit and energy cost minimization. In order to maximize the revenue, a CSP will always try to allocate as many VMs as possible which consequently increase the power consumption in terms of the number of active physical machines (PMs). Due to heterogeneity in the number of resources, an inefficient resource allocation may result in more number of PMs with a tremendous increase in energy consumption. Thus there must be a trade between the VMs requesting the cloud resources and PMs which are providing the resources. The auction is become one of the well-known trading forms as it allocates the resources of sellers to buyers and allows competitive price discovery as well as maintains efficient and fair resource allocation[2]. In this work, we propose a truthful double auction based mechanism (TDAM) for VM allocation. The key contributions of this work can be listed as follows: Firstly, the VM allocation problem of maximizing revenue and minimizing energy cost in cloud data centers is formulated as an NP- Hard problem then we design an efficient truthful double auction mechanism TDAM to solve it. Under this scheme, we have mainly proposed winning bid determination algorithm by using the maximum matching algorithm and then VCG based payment strategy for the winning bids. Secondly, with the help of theoretical analysis and simulations, it is shown that the TDAM follows truthfulness, individual rationality, and economic efficiency with polynomial time complexity. Finally, we have validated the desirable auction properties through extensive simulation.