Computer Science Department
School of Computer Science, Carnegie Mellon University
Fundamental Characteristics of Queues
with Fluctuating Load
Varun Gupta, Mor Harchol-Balter
Alan Scheller-Wolf*, Uri Yechiali**
Keywords: Fluctuating load, MAP, MMPP, non-stationary arrivals/service,
Ross's conjecture, stochastic ordering
Systems whose arrival or service rates fluctuate over time are very common,
but are still not well understood analytically. Stationary formulas are poor
predictors of systems with fluctuating load. When the arrival and service
processes fluctuate in a Markovian manner, computational methods, such as
Matrix-analytic and spectral analysis, have been instrumental in the
numerical evaluation of quantities like mean response time. However, such
computational tools provide only limited insight into the functional
behavior of the system with respect to its primitive input parameters:
the arrival rates, service rates, and rate of fluctuation.
For example, the shape of the function that maps rate of fluctuation to
mean response time is not well understood, even for an M/M/1 system. Is
this function increasing, decreasing, monotonic? How is its shape affected
by the primitive input parameters? Is there a simple closed-form
approximation for the shape of this curve? Turning to user experience:
How is the performance experienced by a user arriving into a "high load"
period different from that of a user arriving into a "low load" period,
or simply a random user. Are there stochastic relations between these?
In this work, we provide the first answers to these fundamental questions.
*Tepper School of Business, Carnegie Mellon University
**Department of Statistics and Operations Research, School of Mathematical
Tel Aviv University, Israel.