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**

August 2006

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.

50 pages

*Tepper School of Business, Carnegie Mellon University
**Department of Statistics and Operations Research, School of Mathematical Sciences,
Tel Aviv University, Israel.

Submission: Rev05/09

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by