File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/INFOCOM.2014.6847966
- Scopus: eid_2-s2.0-84904289472
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Dynamic resource provisioning in cloud computing: a randomized auction approach
Title | Dynamic resource provisioning in cloud computing: a randomized auction approach |
---|---|
Authors | |
Issue Date | 2014 |
Publisher | IEEE 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? |
Abstract | This 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 Identifier | http://hdl.handle.net/10722/201093 |
ISBN | |
ISSN | 2020 SCImago Journal Rankings: 1.183 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhang, L | en_US |
dc.contributor.author | Li, Z | en_US |
dc.contributor.author | Wu, C | en_US |
dc.date.accessioned | 2014-08-21T07:13:33Z | - |
dc.date.available | 2014-08-21T07:13:33Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.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 | en_US |
dc.identifier.isbn | 978-14799-3360-0 | - |
dc.identifier.issn | 0743-166X | - |
dc.identifier.uri | http://hdl.handle.net/10722/201093 | - |
dc.description.abstract | This 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.language | eng | en_US |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359 | - |
dc.relation.ispartof | IEEE Infocom Proceedings | en_US |
dc.title | Dynamic resource provisioning in cloud computing: a randomized auction approach | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Wu, C: cwu@cs.hku.hk | en_US |
dc.identifier.authority | Wu, C=rp01397 | en_US |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/INFOCOM.2014.6847966 | - |
dc.identifier.scopus | eid_2-s2.0-84904289472 | - |
dc.identifier.hkuros | 232121 | en_US |
dc.identifier.spage | 433 | - |
dc.identifier.epage | 441 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 140822 | - |
dc.identifier.issnl | 0743-166X | - |