Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward

Anshul Gandhi, Sherwin Doroudi, Mor Harchol-Balter, Alan Scheller-Wolf

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

The M/M/k/setup model, where there is a penalty for turning servers on, is common in data centers, call centers, and manufacturing systems. Setup costs take the form of a time delay, and sometimes there is additionally a power penalty, as in the case of data centers. While the M/M/1/setup was exactly analyzed in 1964, no exact analysis exists to date for the M/M/k/setup with k>1. In this paper, we provide the first exact, closed-form analysis for the M/M/k/setup and some of its important variants including systems in which idle servers delay for a period of time before turning off or can be put to sleep. Our analysis is made possible by a new way of combining renewal reward theory and recursive techniques to solve Markov chains with a repeating structure. Our renewal-based approach uses ideas from renewal reward theory and busy period analysis to obtain closed-form expressions for metrics of interest such as the transform of time in system and the transform of power consumed by the system. The simplicity, intuitiveness, and versatility of our renewal-based approach makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, our renewal-based approach should be used to reduce the analysis of any 2-dimensional Markov chain which is infinite in at most one dimension and repeating to the problem of solving a system of polynomial equations. In the case where all transitions in the repeating portion of the Markov chain are skip-free and all up/down arrows are unidirectional, the resulting system of equations will yield a closed-form solution.

Original languageEnglish (US)
Pages (from-to)177-209
Number of pages33
JournalQueueing Systems
Volume77
Issue number2
DOIs
StatePublished - Jun 2014

Keywords

  • Performance
  • Queueing theory
  • Renewal reward
  • Repeating chains
  • Resource allocation

Fingerprint

Dive into the research topics of 'Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward'. Together they form a unique fingerprint.

Cite this