Optimization-based Resource Allocation in Cloud Computing

Abstract

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.