Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization

Abstract

This paper considers a Markov decision model for profit maximization of a cloud computing service provider catering to customers submitting jobs with firm real-time random deadlines. Customers are charged on a per-job basis, receiving a full refund if deadlines are missed. The service provider leases computing resources from an infrastructure provider in a two-tier scheme: long-term leasing of basic infrastructure, consisting of heterogeneous parallel service nodes, each modeled as a multi-server queue, and short-term leasing of external servers. Given the intractability of computing an optimal dynamic resource allocation and job routing policy, maximizing the long-run average profit rate, the paper addresses the design, implementation and testing of low-complexity heuristics. The policies considered are a static policy given by an optimal Bernoulli splitting, and three dynamic index policies based on different index definitions: individually optimal (IO), policy improvement (PI) and restless bandit (RB) indices. The paper shows how to implement efficiently each such policy, and presents a comprehensive empirical comparison, drawing qualitative insights on their strengths and weaknesses, and benchmarking their performance in an extensive study.

published

References in corpus (2)

• Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach
• Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies

Cited by in corpus (6)

• Markovian restless bandits and index policies: A review
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits
• A fast-pivoting algorithm for Whittle's restless bandit index
• Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits
• Optimal control policies for resource allocation in the Cloud: comparison between Markov decision process and heuristic approaches
• Solving Poisson's equation for birth-death chains: Structure, instability, and accurate approximation