A theory of auto-scaling for resource reservation in cloud services

DOI10.1287/STSY.2021.0091zbMATH Open1502.90039arXiv2005.13744OpenAlexW3030924737MaRDI QIDQ5046013FDOQ5046013

Authors: Konstantinos Psychas, Javad Ghaderi 

Publication date: 8 November 2022

Published in: Stochastic Systems (Search for Journal in Brave)

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 $1-1/e$ 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)=omega(logL)$, of reserved VM slots for high priority jobs that pack well.

Full work available at URL: https://arxiv.org/abs/2005.13744

Recommendations

• Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization
• Dynamic resource allocation in the cloud with near-optimal efficiency
• Choosing among heterogeneous server clouds
• Resource Allocation in Cloud Computing Via Optimal Control to Queuing Systems
• Computational Science and Its Applications – ICCSA 2004

zbMATH Keywords

resource allocationschedulingcloud computingfluid limitsloss systems

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Loss networks
• Stochastic on-line knapsack problems
• Online knapsack revisited
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Title not available (Why is that?)
• Large loss networks
• Queueing Networks and Markov Chains
• Unbounded knapsack problem: Dynamic programming revisited
• An exact algorithm for large unbounded knapsack problems
• A formal proof in Coq of Lasalle's invariance principle
• Optimization via trunk reservation in single resource loss systems under heavy traffic
• Optimal Control and Trunk Reservation in Loss Networks
• Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks
• An infinite server system with general packing constraints
• Adaptive Resource Provisioning for the Cloud Using Online Bin Packing
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Choosing among heterogeneous server clouds
• Large-scale heterogeneous service systems with general packing constraints

Cited In (4)

• Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization
• \texttt{DEPAS}: a decentralized probabilistic algorithm for auto-scaling
• SLA based resource allocation policies in autonomic environments
• Auto-scaling system in Apache spark cluster using model-based deep reinforcement learning

Uses Software

• Hadoop
• Azure
• GitHub

This page was built for publication: A theory of auto-scaling for resource reservation in cloud services

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5046013)