File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Dynamic resource provisioning in cloud computing: a randomized auction approach

TitleDynamic resource provisioning in cloud computing: a randomized auction approach
Authors
Issue Date2014
PublisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359
Citation
The 33rd IEEE Conference on Computer Communications (IEEE INFOCOM 2014), Toronto, ON., 27 April-2 May 2014. In IEEE Infocom Proceedings, 2014, p. 433-441 How to Cite?
AbstractThis work studies resource allocation in a cloud market through the auction of Virtual Machine (VM) instances. It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. Social welfare maximization under dynamic resource provisioning is proven NP-hard, and modeled with a linear integer program. An efficient α-approximation algorithm is designed, with α ∼ 2.72 in typical scenarios. We then employ this algorithm as a building block for designing a randomized combinatorial auction that is computationally efficient, truthful in expectation, and guarantees the same social welfare approximation factor α. A key technique in the design is to utilize a pair of tailored primal and dual LPs for exploiting the underlying packing structure of the social welfare maximization problem, to decompose its fractional solution into a convex combination of integral solutions. Empirical studies driven by Google Cluster traces verify the efficacy of the randomized auction. © 2014 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/201093
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorZhang, Len_US
dc.contributor.authorLi, Zen_US
dc.contributor.authorWu, Cen_US
dc.date.accessioned2014-08-21T07:13:33Z-
dc.date.available2014-08-21T07:13:33Z-
dc.date.issued2014en_US
dc.identifier.citationThe 33rd IEEE Conference on Computer Communications (IEEE INFOCOM 2014), Toronto, ON., 27 April-2 May 2014. In IEEE Infocom Proceedings, 2014, p. 433-441en_US
dc.identifier.isbn978-14799-3360-0-
dc.identifier.issn0743-166X-
dc.identifier.urihttp://hdl.handle.net/10722/201093-
dc.description.abstractThis work studies resource allocation in a cloud market through the auction of Virtual Machine (VM) instances. It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. Social welfare maximization under dynamic resource provisioning is proven NP-hard, and modeled with a linear integer program. An efficient α-approximation algorithm is designed, with α ∼ 2.72 in typical scenarios. We then employ this algorithm as a building block for designing a randomized combinatorial auction that is computationally efficient, truthful in expectation, and guarantees the same social welfare approximation factor α. A key technique in the design is to utilize a pair of tailored primal and dual LPs for exploiting the underlying packing structure of the social welfare maximization problem, to decompose its fractional solution into a convex combination of integral solutions. Empirical studies driven by Google Cluster traces verify the efficacy of the randomized auction. © 2014 IEEE.-
dc.languageengen_US
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359-
dc.relation.ispartofIEEE Infocom Proceedingsen_US
dc.rightsIEEE Infocom. Proceedings. Copyright © IEEE Computer Society.-
dc.rights©2014 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleDynamic resource provisioning in cloud computing: a randomized auction approachen_US
dc.typeConference_Paperen_US
dc.identifier.emailWu, C: cwu@cs.hku.hken_US
dc.identifier.authorityWu, C=rp01397en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/INFOCOM.2014.6847966-
dc.identifier.scopuseid_2-s2.0-84904289472-
dc.identifier.hkuros232121en_US
dc.identifier.spage433-
dc.identifier.epage441-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 140822-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats