Skip to Main content Skip to Navigation
New interface
Conference papers

Reliable Service Allocation in Clouds

Olivier Beaumont 1, 2 Lionel Eyraud-Dubois 1, 2 Hubert Larchevêque 2, 1 
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : We consider several reliability problems that arise when allocating applications to processing resources in a Cloud computing platform. More specifically, we assume on the one hand that each computing resource is associated to a capacity constraint and to a probability of failure. On the other hand, we assume that each service runs as a set of independent instances of identical Virtual Machines, and that the Service Level Agreement between the Cloud provider and the client states that a minimal number of instances of the service should run with a given probability. In this context, given the capacity and failure probabilities of the machines, and the capacity and reliability demands of the services, the question for the cloud provider is to find an allocation of the instances of the services (possibly using replication) onto machines satisfying all types of constraints during a given time period. In this paper, our goal is to assess the impact of the reliability constraint on the complexity of resource allocation problems. We consider several variants of this problem, depending on the number of services and whether their reliability demand is individual or global. We prove several fundamental complexity results ($\#$P' and NP-completeness results) and we provide several optimal and approximation algorithms. In particular, we prove that a basic randomized allocation algorithm, that is easy to implement, provides optimal or quasi-optimal results in several contexts, and we show through simulations that it also achieves very good results in more general settings.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Lionel Eyraud-Dubois Connect in order to contact the contributor
Submitted on : Saturday, November 17, 2012 - 8:40:43 PM
Last modification on : Saturday, June 25, 2022 - 8:29:55 PM
Long-term archiving on: : Monday, February 18, 2013 - 3:42:54 AM


Files produced by the author(s)




Olivier Beaumont, Lionel Eyraud-Dubois, Hubert Larchevêque. Reliable Service Allocation in Clouds. IPDPS - 27th IEEE International Parallel & Distributed Processing Symposium, May 2013, Boston, United States. ⟨10.1109/IPDPS.2013.64⟩. ⟨hal-00743524v2⟩



Record views


Files downloads