TY - GEN
T1 - Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward
AU - Gandhi, Anshul
AU - Doroudi, Sherwin
AU - Harchol-Balter, Mor
AU - Scheller-Wolf, Alan
PY - 2013/7/22
Y1 - 2013/7/22
N2 - 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 our development of a new technique, Recursive Renewal Reward (RRR), for solving Markov chains with a repeating structure. RRR 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 RRR makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, RRR 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.
AB - 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 our development of a new technique, Recursive Renewal Reward (RRR), for solving Markov chains with a repeating structure. RRR 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 RRR makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, RRR 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.
KW - Performance
KW - Queueing theory
KW - Resource allocation
UR - http://www.scopus.com/inward/record.url?scp=84880229157&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880229157&partnerID=8YFLogxK
U2 - 10.1145/2494232.2465760
DO - 10.1145/2494232.2465760
M3 - Conference contribution
AN - SCOPUS:84880229157
SN - 9781450319003
T3 - Performance Evaluation Review
SP - 153
EP - 166
BT - SIGMETRICS 2013 - Proceedings of the 2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
T2 - 2013 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2013
Y2 - 17 June 2013 through 21 June 2013
ER -