An Online Auction Mechanism for Dynamic Virtual Cluster Provisioning in Geo-Distributed Clouds.

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought; (2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and $(1+2\log \mu)$<alternatives> <inline-graphic xlink:href="wu-ieq1-2601905.gif"/></alternatives>-competitiveness in social welfare, where $\mu$<alternatives> <inline-graphic xlink:href="wu-ieq2-2601905.gif"/></alternatives> is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving $O(\log \mu)$ <alternatives><inline-graphic xlink:href="wu-ieq3-2601905.gif"/></alternatives> -competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We investigate auction design in different cases of resource cost functions in the system. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations. [ABSTRACT FROM PUBLISHER]