Dynamic cloud resource provisioning and pricing

Abstract

On-demand resource provisioning in cloud computing provides tailor-made resource packages to meet users' demands. Public clouds nowadays provide more and more elaborated types of VMs, but have yet to offer flexible dynamic VM assembly, due to the lack of a mature mechanism for pricing tailor-made VMs on the spot. To fulfill this research gap, this thesis investigates dynamic cloud resource provisioning and pricing in various problem settings.

We first study the offline setting of VM provisioning and pricing in geo-distributed cloud data centers via a one-time auction that achieves (i) truthfulness in expectation, (ii) polynomial running time in expectation, and (iii) $(1-\epsilon)$-optimal social welfare in expectation, where $\epsilon$ can be arbitrarily close to $0$. Our proposed mechanism applies the perturbation-based scheme for VM allocation and prices the customized VMs using a randomized VCG payment. The computation efficiency is proved by a novel application of smoothed analysis.

Next, we target a more realistic case of online VM auction design, where: (i) cloud users bid for resources into the future to assemble customized VMs with desired occupation durations; (ii) the cloud provider dynamically packs multiple types of resources on heterogeneous servers; (iii) the operational costs of servers are considered; (iv) both social welfare and the cloud provider's net profit are to be maximized. We propose posted-price mechanisms based on an online primal-dual optimization framework for both VM allocation and payment calculation; and a randomized reduction algorithm to convert the social welfare maximizing auctions to ones that provide a maximal expected profit for the provider. Our proposed online auctions achieve truthfulness, polynomial time, and good competitive ratios.

We further extend the online model to dynamic VM scaling, where customers can repeatedly bid for increasing VM resources in scale-up or scale-out option while the cloud provider has to allocate and price the incremental resources on the go. We identify that the offline optimization program with time-coupling bids is non-standard, with a submodular objective function and non-linear constraints. Thus existing primal-dual frameworks are not applicable. Surprisingly, through novel competitive analysis based on submodularity of the offline objective, we prove that a similar posted-price mechanism proposed for the previous scenario achieves a good competitive ratio for the scaling model. We also investigate the online VM auction in a stochastic model where bid arrivals are independently and identically distributed from an unknown distribution. Via a new application of learning-based online primal-dual framework and careful analysis using probability theory, we achieve a $(1-O(\epsilon))$-competitive ratio.

In addition, we also address cost minimization problems in two typical network service provisioning systems, Network Function Virtualization system and cloud Content Delivery Network. We leverage online learning theory and randomized rounding techniques, etc.~to solve these two problems. They may shed light on our future research on dynamic resource provisioning problem with more complicated structure of cost functions.

Apart from theoretical analysis, for each targeted scenario, we also conduct extensive simulation studies based on trace-driven data to validate the performance of each algorithm, comparing with the optima and existing schemes.