article

Fundamental characteristics of queues with fluctuating load

Authors:

Mor Harchol-Balter,

Alan Scheller Wolf,

Uri YechialiAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 34, Issue 1

Pages 203 - 215

https://doi.org/10.1145/1140103.1140301

Published: 26 June 2006 Publication History

Abstract

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 paper, we provide the first answers to these fundamental questions.

References

[1]

J. Abate, G. Choudhury, W. Whitt, Asymptotics for Steady-State Tail Probabilities in Structured Markov Queueing Models, Commun. Statist.-Stoch. Mod. 10(1), pp. 99--143, 1994.

[2]

I. J. B. F. Adan, V. G. Kulkarni. Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times,QUESTA 45, pp. 113--134, 2003.

Digital Library

[3]

E. Arjas. On the Use of a Fundamental Identity in the Theory of Semi-Markov Queues, Adv. Appl. Prob. 4, pp. 271--284, 1972.

[4]

S. Asmussen, J. Møller. Calculation of the Steady State Waiting Time Distribution in GI/PH/c and MAP/PH/c Queues, QUESTA 37, pp. 9--29, 2001.

Digital Library

[5]

N. T. J. Bailey. A continuous time treatment of a simple queue using generating functions, J. R. Statist. Soc. B19, pp. 326--333, 1954.

[6]

G. L. Choudhury, A. Mandelbaum, M. I. Reiman, W. Whitt. Fluid and Diffusion Limits for Queues in Slowly Changing Environments, Stoch. Mod. 13, pp. 121--146, 1997.

[7]

E. Çinlar. Time Dependence of Queues with Semi-Markov Services, J. Appl. Prob. 4, pp. 356--364, 1967.

[8]

E. Çinlar. Queues with Semi-Markov Arrivals, J. Appl. Prob. 4, pp. 365--379, 1967.

[9]

A. B. Clark. A Waiting Line Process of the Markov Type, Ann. Math. Statist. 27, pp. 452--459, 1956.

[10]

J. H. A. de Smit. The Single Server Semi-Markov Queue, Stoch. Proc. and Appl. 22, pp. 37--50, 1986.

[11]

E. Gelenbe, C. Rosenberg. Queues with Slowly Varying Arrival and Service Processes, Man. Sci. 36(8), pp. 928--937, 1990.

Digital Library

[12]

V. Gupta, M. Harchol-Balter, A. Scheller Wolf, U. Yechiali. Fundamental Characteristics of Queues with Fluctuating Load, Technical Report CMU-CS-06-117, School of Computer Science, Carnegie Mellon University, 2006.

Digital Library

[13]

P. Harrison, H. Zatschler. Sojourn Time Distributions in Modulated G-Queues with Batch Processing, QEST 2004, Enschede, Netherlands, Los Alamitos, IEEE Computer Soc, pp. 90--99, 2004.

Digital Library

[14]

D. P. Heyman. On Ross's Conjectures about Queues with Non-Stationary Poisson Arrivals, J. Appl. Prob. 19, pp. 245--249, 1982.

[15]

C. Knessl, Y. P. Yang. An Exact Solution for an M(t)/M(t)/1 Queue with Time-Dependent Arrivals and Service, QUESTA 40, pp. 233--245, 2002.

Digital Library

[16]

D. M. Lucantoni, K. S. Meier-Hellstern, M. Neuts. A Single Server Queue with Server Vacations and a Class of Non-Renewal Arrival Processes Adv. App. Prob. 22, pp. 676--705, 1990.

[17]

D. M. Lucantoni, M. Neuts. Some Steady-State Distributions for the MAP/SM/1 Queue, Commun. Statist.-Stoch. Mod. 10(3), pp. 575--598, 1994.

[18]

W. A. Massey. Asymptotic Analysis of the Time Dependent M/M/1 Queue, Math. of OR 10(2), pp. 305--327, 1985.

Digital Library

[19]

I. Mitrani, R. Chakka. Spectral Expansion Solution for a Class of Markov Models: Application and Comparison with the Matrix-Geometric Method, Perf. Eval. 23(3), pp. 241--260, 1995.

Digital Library

[20]

N. Miyoshi, T. Rolski. Ross Type Conjectures on Monotonicity of Queues, Festschrift for D. Daley, P. Pollet and P. Taylor Eds. Australian & New Zealand J. of Stat. 46, pp. 121--132, 2004.

[21]

M. Neuts. The Single Server Queue with Poisson Input and Semi-Markov Service Times, J. Appl. Prob. 3, pp. 202--230, 1966.

[22]

M. Neuts. The M/M/1 Queue with Randomly Varying Arrival and Service Rates, OPSEARCH 15(4), pp. 139--168, 1978.

[23]

G. F. Newell. Queues with Time-Dependent Arrival Rates I -- The Transition Through Saturation, J. Appl. Prob 5, pp. 436--451, 1968.

[24]

G. F. Newell. Queues with Time-Dependent Arrival Rates II -- The Maximum Queue and the Return to Equilibrium, J. Appl. Prob 5, pp. 579--590, 1968.

[25]

G. F. Newell. Queues with Time-Dependent Arrival Rates III -- A Mild Rush Hour, J. Appl. Prob 5, pp. 591--606, 1968.

[26]

V. Ramaswami. The N/G/1 Queue and its Detailed Analysis, Adv. Appl. Prob. 12, pp. 222--261, 1980.

[27]

K. L. Rider. A Simple Approximation to the Average Queue Size in the Time-Dependent M/M/1 Queue, JACM 23(2), pp. 361--367, 1976.

Digital Library

[28]

T. Rolski. Queues with Non-Stationary Input Stream: Ross's Conjecture, Adv. Appl. Prob. 13, pp. 603--618, 1981.

[29]

S. Ross. Average Delay in Queues with Non-Stationary Poisson Arrivals, J. Appl. Prob. 15, pp. 602--609, 1978.

[30]

B. Sengupta. A Queue with Service Interruptions in an Alternating Random Env., OR 38(2), pp. 308--318, 1990.

Digital Library

[31]

B. Sengupta. The Semi-Markov Queue: Theory and Applications, Commun. Statist.-Stoch. Mod. 6(3), pp. 383--413, 1990.

[32]

T. Takine, Y. Matsumoto, T. Suda, T. Hasegawa. Mean Waiting Times in Nonpreemptive Priority Queues with Markovian Arrival and i.i.d. Service Processes, Perf. Eval. 20, pp. 131--149, 1994.

Digital Library

[33]

T. Takine, B. Sengupta. A Single Server Queue with Service Interruptions, QUESTA 26, pp. 285--300, 1997.

Digital Library

[34]

Y. Yang, C. Knessl. Asymptotic Analysis of the M/G/1 Queue with Time-Dependent Arrival Rates, QUESTA 26, pp. 23--68, 1997.

Digital Library

[35]

U. Yechiali, P. Naor. Queueing Problems with Heterogeneous Arrivals and Service, OR 19(3), pp. 722--734, 1971.

Digital Library

Cited By

Grosof IHong YHarchol-Balter MScheller-Wolf A(2023)The RESET and MARC techniques, with application to multiserver-job analysisPerformance Evaluation10.1016/j.peva.2023.102378162(102378)Online publication date: Nov-2023
https://doi.org/10.1016/j.peva.2023.102378
Houalef MBouchentouf AYahiaoui L(2022)A Multi-server Queue in a Multi-phase Random Environment with Waiting Servers and Customers’ Impatience Under Synchronous Working Vacation PolicyJournal of the Operations Research Society of China10.1007/s40305-021-00384-311:3(459-487)Online publication date: 17-Feb-2022
https://doi.org/10.1007/s40305-021-00384-3
Vesilo RHarchol-Balter MScheller-Wolf A(2021)SCALING PROPERTIES OF QUEUES WITH TIME-VARYING LOAD PROCESSES: EXTENSIONS AND APPLICATIONSProbability in the Engineering and Informational Sciences10.1017/S0269964821000048(1-42)Online publication date: 3-Mar-2021
https://doi.org/10.1017/S0269964821000048
Show More Cited By

Index Terms

Fundamental characteristics of queues with fluctuating load
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Queueing theory

Recommendations

Fundamental characteristics of queues with fluctuating load
SIGMETRICS '06/Performance '06: Proceedings of the joint international conference on Measurement and modeling of computer systems

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 ...
Stochastic inequalities for M/G/1 retrial queues with vacations and constant retrial policy

In this paper, we consider an M/G/1 retrial queue with vacations and we derive several stochastic comparison properties in the sense of strong stochastic ordering and convex ordering. The stochastic inequalities provide simple insensitive bounds for the ...
A Random Family of Queueing Systems with a Dynamic Priority Discipline

We consider a family {Σ_u, 0 ≤ u ≤ ∞} of single server queueing systems whose customers belong to two priority classes. They arrive in two independent Poisson processes and their service times are independent with general distributions for each ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 34, Issue 1

Performance evaluation review

June 2006

388 pages

ISSN:0163-5999

DOI:10.1145/1140103

Issue’s Table of Contents

SIGMETRICS '06/Performance '06: Proceedings of the joint international conference on Measurement and modeling of computer systems
June 2006
404 pages
ISBN:1595933190
DOI:10.1145/1140277
General Chair:
Raymond Marie
University of Rennes 1/IRISA, France
,
Program Chairs:
Peter Key
Microsoft Research, Cambridge, U.K.
,
Evgenia Smirni
College of William and Mary, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2006

Published in SIGMETRICS Volume 34, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
507
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Grosof IHong YHarchol-Balter MScheller-Wolf A(2023)The RESET and MARC techniques, with application to multiserver-job analysisPerformance Evaluation10.1016/j.peva.2023.102378162(102378)Online publication date: Nov-2023
https://doi.org/10.1016/j.peva.2023.102378
Houalef MBouchentouf AYahiaoui L(2022)A Multi-server Queue in a Multi-phase Random Environment with Waiting Servers and Customers’ Impatience Under Synchronous Working Vacation PolicyJournal of the Operations Research Society of China10.1007/s40305-021-00384-311:3(459-487)Online publication date: 17-Feb-2022
https://doi.org/10.1007/s40305-021-00384-3
Vesilo RHarchol-Balter MScheller-Wolf A(2021)SCALING PROPERTIES OF QUEUES WITH TIME-VARYING LOAD PROCESSES: EXTENSIONS AND APPLICATIONSProbability in the Engineering and Informational Sciences10.1017/S0269964821000048(1-42)Online publication date: 3-Mar-2021
https://doi.org/10.1017/S0269964821000048
Zhang HShi CQin CHua C(2016)Stochastic regret minimization for revenue management problems with nonstationary demandsNaval Research Logistics (NRL)10.1002/nav.2170463:6(433-448)Online publication date: Sep-2016
https://doi.org/10.1002/nav.21704
Terekhov DTran TDown DBeck J(2014)Integrating queueing theory and scheduling for dynamic scheduling problemsJournal of Artificial Intelligence Research10.5555/2693068.269308250:1(535-572)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.5555/2693068.2693082
Casale GTribastone MHarrison P(2014)Blending randomness in closed queueing network modelsPerformance Evaluation10.1016/j.peva.2014.09.00182:C(15-38)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.peva.2014.09.001
Kumar RLewis MTopaloglu H(2013)Dynamic service rate control for a single-server queue with Markov-modulated arrivalsNaval Research Logistics (NRL)10.1002/nav.2156060:8(661-677)Online publication date: 25-Nov-2013
https://doi.org/10.1002/nav.21560
Perel NYechiali U(2010)Queues with slow servers and impatient customersEuropean Journal of Operational Research10.1016/j.ejor.2009.02.024201:1(247-258)Online publication date: Feb-2010
https://doi.org/10.1016/j.ejor.2009.02.024
Bonomo OYechiali UReuveni S(2025)Queues with service resettingEuropean Journal of Operational Research10.1016/j.ejor.2024.12.044322:3(908-919)Online publication date: May-2025
https://doi.org/10.1016/j.ejor.2024.12.044
Chen ZSmith D(2021)MmWave M2M Networks: Improving Delay Performance of RelayingIEEE Transactions on Wireless Communications10.1109/TWC.2020.302671020:1(577-589)Online publication date: Jan-2021
https://doi.org/10.1109/TWC.2020.3026710
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents