File Download
Supplementary

postgraduate thesis: Online mechanisms for dynamic resource provisioning in cloud computing

TitleOnline mechanisms for dynamic resource provisioning in cloud computing
Authors
Issue Date2016
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Shi, W. [施維捷]. (2016). Online mechanisms for dynamic resource provisioning in cloud computing. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5760946
AbstractAuction mechanisms, which have recently attracted substantial attention, are efficient approaches to resource allocation and pricing in cloud computing. In contrast to fixed price policy, auction mechanism can adapt to realtime demand/supply changes, achieving maximal market efficiency and provider revenue. Cloud users arrive in an online fashion, requiring the provider to provision resources on demand, which complicates the design of the mechanism compared with online mechanisms. Although some online mechanisms have been proposed in this field, existing solutions are still not completely satisfactory, especially for heterogeneous types of Virtual Machines (VM) and bandwidth resources. In this thesis, we propose efficient online mechanisms for computational and communication resources provisioning, using techniques of primal-dual optimization and auction theory. We first investigate the online auctions for heterogeneous types of VMs with and without user budget, respectively. For the model without user budget, we propose a truthful online mechanism that timely responds to incoming users' demands and makes dynamic allocation decisions, while guaranteeing system efficiency, using the pricing curve technique. For the model with user budget constraint, we use primal-dual technique to decompose the online combinatorial optimization into a series of independent single-user optimization problems, and solve the single-user problem with randomized auctions. In both solutions, our mechanisms provision different types of VMs dynamically, adjusting the number of instances of VMs to realtime user demand. Next, we turn to bandwidth resource allocation in cloud computing. We novelly exploit the Shapley value in the auction mechanism design, and present the first dynamic pricing mechanism for inter-datacenter on-demand bandwidth. Our auctions, including both online and online version, are expressive enough to accept bids as a at bandwidth rate plus a time duration, or a data volume with a transfer deadline, and achieve approximately efficiency in social welfare. Finally, we combine the computational resources with the communication resources under a unified framework, and propose the first online algorithm for dynamic Virtual Cluster (VC) provisioning and pricing, which optimally places VCs, routes inter-VM traffic and charges a market-driven price for each VC. We use the pricing-curve method to design a social welfare maximizing auction, and then convert it to a revenue maximizing online auction using randomized payment boosting technique. Through theoretical analysis and trace-driven simulations, we rigorously examine the efficiency of our mechanisms comparing with both the theoretical optima and existing solutions.
DegreeDoctor of Philosophy
SubjectResource allocation - Mathematical models
Cloud computing
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/226744

 

DC FieldValueLanguage
dc.contributor.authorShi, Weijie-
dc.contributor.author施維捷-
dc.date.accessioned2016-06-30T04:24:02Z-
dc.date.available2016-06-30T04:24:02Z-
dc.date.issued2016-
dc.identifier.citationShi, W. [施維捷]. (2016). Online mechanisms for dynamic resource provisioning in cloud computing. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5760946-
dc.identifier.urihttp://hdl.handle.net/10722/226744-
dc.description.abstractAuction mechanisms, which have recently attracted substantial attention, are efficient approaches to resource allocation and pricing in cloud computing. In contrast to fixed price policy, auction mechanism can adapt to realtime demand/supply changes, achieving maximal market efficiency and provider revenue. Cloud users arrive in an online fashion, requiring the provider to provision resources on demand, which complicates the design of the mechanism compared with online mechanisms. Although some online mechanisms have been proposed in this field, existing solutions are still not completely satisfactory, especially for heterogeneous types of Virtual Machines (VM) and bandwidth resources. In this thesis, we propose efficient online mechanisms for computational and communication resources provisioning, using techniques of primal-dual optimization and auction theory. We first investigate the online auctions for heterogeneous types of VMs with and without user budget, respectively. For the model without user budget, we propose a truthful online mechanism that timely responds to incoming users' demands and makes dynamic allocation decisions, while guaranteeing system efficiency, using the pricing curve technique. For the model with user budget constraint, we use primal-dual technique to decompose the online combinatorial optimization into a series of independent single-user optimization problems, and solve the single-user problem with randomized auctions. In both solutions, our mechanisms provision different types of VMs dynamically, adjusting the number of instances of VMs to realtime user demand. Next, we turn to bandwidth resource allocation in cloud computing. We novelly exploit the Shapley value in the auction mechanism design, and present the first dynamic pricing mechanism for inter-datacenter on-demand bandwidth. Our auctions, including both online and online version, are expressive enough to accept bids as a at bandwidth rate plus a time duration, or a data volume with a transfer deadline, and achieve approximately efficiency in social welfare. Finally, we combine the computational resources with the communication resources under a unified framework, and propose the first online algorithm for dynamic Virtual Cluster (VC) provisioning and pricing, which optimally places VCs, routes inter-VM traffic and charges a market-driven price for each VC. We use the pricing-curve method to design a social welfare maximizing auction, and then convert it to a revenue maximizing online auction using randomized payment boosting technique. Through theoretical analysis and trace-driven simulations, we rigorously examine the efficiency of our mechanisms comparing with both the theoretical optima and existing solutions.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.subject.lcshResource allocation - Mathematical models-
dc.subject.lcshCloud computing-
dc.titleOnline mechanisms for dynamic resource provisioning in cloud computing-
dc.typePG_Thesis-
dc.identifier.hkulb5760946-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats