A Theory of Auto-Scaling for Resource Reservation in Cloud Services
- 5 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (3), 27-32
- https://doi.org/10.1145/3453953.3453958
Abstract
We consider a distributed server system consisting of a large number of servers, each with limited capacity on multiple resources (CPU, memory, disk, etc.). Jobs with different rewards arrive over time and require certain amounts of resources for the duration of their service. When a job arrives, the system must decide whether to admit it or reject it, and if admitted, in which server to schedule the job. The objective is to maximize the expected total reward received by the system. This problem is motivated by control of cloud computing clusters, in which, jobs are requests for Virtual Machines or Containers that reserve resources for various services, and rewards represent service priority of requests or price paid per time unit of service by clients. We study this problem in an asymptotic regime where the number of servers and jobs' arrival rates scale by a factor L, as L becomes large. We propose a resource reservation policy that asymptotically achieves at least 1/2, and under certain monotone property on jobs' rewards and resources, at least 11/4 of the optimal expected reward. The policy automatically scales the number of VM slots for each job type as the demand changes, and decides in which servers the slots should be created in advance, without the knowledge of traffic rates. It effectively tracks a low-complexity greedy packing of existing jobs in the system while maintaining only a small number, g(L) = w(logL), of reserved VM slots for high priority jobs that pack well.Keywords
This publication has 22 references indexed in Scilit:
- Mean field and propagation of chaos in multi-class heterogeneous loss modelsPerformance Evaluation, 2015
- Heavy traffic optimal resource allocation algorithms for cloud computing clustersPerformance Evaluation, 2014
- Asymptotic optimality of BestFit for stochastic bin packingACM SIGMETRICS Performance Evaluation Review, 2014
- A Sharing-Aware Greedy Algorithm for Virtual Machine MaximizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraintsQueueing Systems, 2014
- VM consolidation: A real case based on OpenStack CloudFuture Generation Computer Systems, 2014
- Stochastic models of load balancing and scheduling in cloud computing clustersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Efficient Autoscaling in the Cloud Using Predictive Models for Workload ForecastingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Optimization via trunk reservation in single resource loss systems under heavy trafficThe Annals of Applied Probability, 1997
- Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networksAdvances in Applied Probability, 1995