A Truthful (1 - ε)-Optimal Mechanism for On-Demand Cloud Resource Provisioning

On-demand resource provisioning in cloud computing provides tailor-made resource packages (typically in the form of VMs) to meet users' demands. Public clouds nowadays provide elaborated types of VMs, but have yet to offer the most flexible dynamic VM assembly, which is partly due to the lack of a mature mechanism for pricing tailor-made VMs. This work proposes an efficient randomized auction mechanism based on a novel application of smoothed analysis and randomized reduction, for dynamic VM provisioning and pricing in geo-distributed cloud data centers. To the best of our knowledge, it is the first one in literature that achieves (i) truthfulness in expectation, (ii) polynomial running time in expectation, and (iii) (1 - epsilon)-optimal social welfare in expectation for resource allocation, where epsilon can be arbitrarily close to 0. Our mechanism consists of three modules: (1) an exact algorithm to solve the NP-hard social welfare maximization problem, which has polynomial run-time in expectation, (2) a perturbation-based randomized resource allocation scheme which produces an allocation solution that is (1 - epsilon)-optimal and (3) an auction mechanism prices the customized VMs using a randomized VCG payment, with a guarantee in truthfulness in expectation. We validate the efficacy of the mechanism through theoretical analysis and trace-driven simulations.