File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2591971.2591980
- Scopus: eid_2-s2.0-84904343815
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: An online auction framework for dynamic resource provisioning in cloud computing
Title | An online auction framework for dynamic resource provisioning in cloud computing |
---|---|
Authors | |
Keywords | Cloud Computing Combinatorial Auction Online Algorithms Pricing Resource Allocation Truthful Mechanisms |
Issue Date | 2014 |
Publisher | ACM. |
Citation | Proceedings of the 2014 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Austin, Texas, USA, 16-20 June 2014, p. 71-83 How to Cite? |
Abstract | Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and resource allocation in cloud computing. This work, to the authors' knowledge, represents the first online combinatorial auction designed in the cloud computing paradigm, which is general and expressive enough to both (a) optimize system efficiency across the temporal domain instead of at an isolated time point, and (b) model dynamic provisioning of heterogeneous Virtual Machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio e+ 1 over e-1 3.30 in social welfare in typical scenarios. The framework consists of three main steps: (1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with an additive loss of 1 over e-1 in competitive ratio, (2) a randomized auction sub-framework that applies primal-dual optimization for translating a centralized co-operative social welfare approximation algorithm into an auction mechanism, retaining a similar approximation ratio while adding truthfulness, and (3) a primal-dual update plus dual fitting algorithm for approximating the one-shot optimization with a ratio λ close to e. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework, as well as its three independent modules, can be instructive in auction design for other related problems. |
Persistent Identifier | http://hdl.handle.net/10722/201097 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Shi, W | en_US |
dc.contributor.author | Zhang, L | en_US |
dc.contributor.author | Wu, C | en_US |
dc.contributor.author | Li, Z | en_US |
dc.contributor.author | Lau, FCM | 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 | Proceedings of the 2014 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Austin, Texas, USA, 16-20 June 2014, p. 71-83 | en_US |
dc.identifier.isbn | 9781450327893 | - |
dc.identifier.uri | http://hdl.handle.net/10722/201097 | - |
dc.description.abstract | Auction mechanisms have recently attracted substantial attention as an efficient approach to pricing and resource allocation in cloud computing. This work, to the authors' knowledge, represents the first online combinatorial auction designed in the cloud computing paradigm, which is general and expressive enough to both (a) optimize system efficiency across the temporal domain instead of at an isolated time point, and (b) model dynamic provisioning of heterogeneous Virtual Machine (VM) types in practice. The final result is an online auction framework that is truthful, computationally efficient, and guarantees a competitive ratio e+ 1 over e-1 3.30 in social welfare in typical scenarios. The framework consists of three main steps: (1) a tailored primal-dual algorithm that decomposes the long-term optimization into a series of independent one-shot optimization problems, with an additive loss of 1 over e-1 in competitive ratio, (2) a randomized auction sub-framework that applies primal-dual optimization for translating a centralized co-operative social welfare approximation algorithm into an auction mechanism, retaining a similar approximation ratio while adding truthfulness, and (3) a primal-dual update plus dual fitting algorithm for approximating the one-shot optimization with a ratio λ close to e. The efficacy of the online auction framework is validated through theoretical analysis and trace-driven simulation studies. We are also in the hope that the framework, as well as its three independent modules, can be instructive in auction design for other related problems. | - |
dc.language | eng | en_US |
dc.publisher | ACM. | - |
dc.relation.ispartof | Proceedings of the 2014 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems | en_US |
dc.subject | Cloud Computing | - |
dc.subject | Combinatorial Auction | - |
dc.subject | Online Algorithms | - |
dc.subject | Pricing | - |
dc.subject | Resource Allocation | - |
dc.subject | Truthful Mechanisms | - |
dc.title | An online auction framework for dynamic resource provisioning in cloud computing | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Wu, C: cwu@cs.hku.hk | en_US |
dc.identifier.email | Lau, FCM: fcmlau@cs.hku.hk | en_US |
dc.identifier.authority | Wu, C=rp01397 | en_US |
dc.identifier.authority | Lau, FCM=rp00221 | en_US |
dc.identifier.doi | 10.1145/2591971.2591980 | - |
dc.identifier.scopus | eid_2-s2.0-84904343815 | - |
dc.identifier.hkuros | 232126 | en_US |
dc.identifier.spage | 71 | - |
dc.identifier.epage | 83 | - |
dc.publisher.place | New York | - |