Optimization-based Resource Allocation in Cloud Computing
MetadataVis full innførsel
This thesis considers the resource allocation problem of a cloud service provider (SP), which provides at set of services delivered through the software-as-a-service model. The SP owns and operates a private cloud, but in periods of high demand, the SP also relies on infrastructure resources provided by a public cloud in the service provisioning. Even though the market for cloud computing services has been growing and is expected to grow further in the future, low quality of service (QoS) is seen as an important issue to be resolved by the cloud computing industry. The focused resource allocation problem translates to the problem of allocating appropriate resources to the services of the SP in a cost-efficient manner, and so that the QoS is in accordance with the requirements specified in the service level agreements (SLAs) between the provider and the users. This problem is represented as an optimization problem. However, analytic and simulation-based models are used to describe the relationship between a given allocation or resources to a service and the resulting QoS. This thesis consists of five research papers, and in short, these papers try to answer the following two interrelated questions: 1. Given a certain resource allocation to a service, does this service satisfy the QoS guarantees of the SLA? 2. How can the set of services offered by the SP be deployed in a cost-efficient manner, while ensuring the appropriate QoS? The two first papers of the thesis concern the former, which is answered by developing both analytic and simulation-based models. Whether the analytic or simulated-based approach should be preferred is dependent on the underlying properties of the services. The second question is considered in the three remaining papers, where optimization models are formulated and solved by both exact and inexact algorithms. Specifically, we provide exact algorithms based on branch and price (B&P) and metaheuristics based on the adaptive large neighborhood search (ALNS) framework. While the B&P approach can provide optimal solutions for small and medium-sized providers, the ALNS approach provides high-quality solutions more quickly.
Består avPaper 1: Gullhav, Anders N.; Nygreen, Bjørn; Heegaard, Poul Einar. Approximating the Response Time Distribution of Fault-tolerant Multi-tier Cloud Services. I: 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing. IEEE Computer Society 2013, s. 287-291. © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/10.1109/UCC.2013.56
Paper 2: Gullhav, Anders Nordby; Nygreen, Bjørn; Heegaard, Poul Einar. Simulation of the response time distribution of fault-tolerant multi-tier cloud services. Journal of Simulation 2016. Is not included due to copyright. Published version available at http://dx.doi.org/10.1057/s41273-016-0042-9
Paper 3: Gullhav, Anders N.; Nygreen, Bjørn. Deployment of replicated multi-tier services in cloud data centres. International Journal of Cloud Computing 2015 ;Volum 4.(2) s. 130-149 Published version available at http://dx.doi.org/10.1504/IJCC.2015.069273
Paper 4: Gullhav, Anders Nordby; Nygreen, Bjørn. A branch and price approach for deployment of multi-tier software services in clouds. Computers & Operations Research 2016 ;Volum 75. s. 12-27 © 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ Published version available at http://dx.doi.org/10.1016/j.cor.2016.05.007
Paper 5: Gullhav, Anders Nordby; Cordeau, Jean-Francois; Hvattum, Lars Magnus; Nygreen, Bjørn. Adaptive large neighborhood search heuristics for multi-tier service deployment problems in clouds. European Journal of Operational Research 2016 © 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ Published version available at http://dx.doi.org/10.1016/j.ejor.2016.11.003