Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
- 1 July 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 70 (4) , 2517-2537
Abstract
Motivated by maximizing spot instances in cloud shared systems, in this work, we consider the problem of taking advantage of unused resources in highly dynamic cloud environments while preserving users’ performance. We introduce an online model for sharing resources that captures basic properties of cloud systems, such as unpredictable users’ demand patterns, very limited feedback from the system, and service level agreement (SLA) between the users and the cloud provider. We provide a simple and efficient algorithm for the single-resource case. For any demand patterns, our algorithm guarantees near-optimal resource utilization as well as high users’ performance compared with their SLA baseline. In addition to this, we validate empirically the performance of our algorithm using synthetic data and data obtained from Microsoft’s systems.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Service Provisioning Problem in Cloud and Multi-Cloud SystemsINFORMS Journal on Computing, 2016
- Online Convex Optimization in Dynamic EnvironmentsIEEE Journal of Selected Topics in Signal Processing, 2015
- Sharing buffer pool memory in multi-tenant relational database-as-a-serviceProceedings of the VLDB Endowment, 2015
- Heavy traffic optimal resource allocation algorithms for cloud computing clustersPerformance Evaluation, 2014
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- Stochastic models of load balancing and scheduling in cloud computing clusters2012
- Learning Curves and Stochastic Models for Pricing and Provisioning Cloud Computing ServicesService Science, 2011
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- Fast Approximation Algorithms for Fractional Packing and Covering ProblemsMathematics of Operations Research, 1995
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993