Online mechanisms for dynamic resource provisioning in cloud computing

Abstract

Auction mechanisms, which have recently attracted substantial attention, are efficient approaches to resource allocation and pricing in cloud computing. In contrast to fixed price policy, auction mechanism can adapt to realtime demand/supply changes, achieving maximal market efficiency and provider revenue. Cloud users arrive in an online fashion, requiring the provider to provision resources on demand, which complicates the design of the mechanism compared with online mechanisms. Although some online mechanisms have been proposed in this field, existing solutions are still not completely satisfactory, especially for heterogeneous types of Virtual Machines (VM) and bandwidth resources. In this thesis, we propose efficient online mechanisms for computational and communication resources provisioning, using techniques of primal-dual optimization and auction theory.

We first investigate the online auctions for heterogeneous types of VMs with and without user budget, respectively. For the model without user budget, we propose a truthful online mechanism that timely responds to incoming users' demands and makes dynamic allocation decisions, while guaranteeing system efficiency, using the pricing curve technique. For the model with user budget constraint, we use primal-dual technique to decompose the online combinatorial optimization into a series of independent single-user optimization problems, and solve the single-user problem with randomized auctions. In both solutions, our mechanisms provision different types of VMs dynamically, adjusting the number of instances of VMs to realtime user demand.

Next, we turn to bandwidth resource allocation in cloud computing. We novelly exploit the Shapley value in the auction mechanism design, and present the first dynamic pricing mechanism for inter-datacenter on-demand bandwidth. Our auctions, including both online and online version, are expressive enough to accept bids as a at bandwidth rate plus a time duration, or a data volume with a transfer deadline, and achieve approximately efficiency in social welfare.

Finally, we combine the computational resources with the communication resources under a unified framework, and propose the first online algorithm for dynamic Virtual Cluster (VC) provisioning and pricing, which optimally places VCs, routes inter-VM traffic and charges a market-driven price for each VC. We use the pricing-curve method to design a social welfare maximizing auction, and then convert it to a revenue maximizing online auction using randomized payment boosting technique.

Through theoretical analysis and trace-driven simulations, we rigorously examine the efficiency of our mechanisms comparing with both the theoretical optima and existing solutions.