Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-23T23:57:20.142Z Has data issue: false hasContentIssue false
  • English
  • Français

SCALING PROPERTIES OF QUEUES WITH TIME-VARYING LOAD PROCESSES: EXTENSIONS AND APPLICATIONS

Published online by Cambridge University Press:  03 March 2021

Rein Vesilo Open the ORCID record for Rein Vesilo [Opens in a new window] ,
Mor Harchol-Balter  and
Alan Scheller-Wolf
Rein Vesilo
Affiliation:
School of Engineering, Macquarie University, Sydney, Australia E-mail: [email protected]
Mor Harchol-Balter
Affiliation:
Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
Alan Scheller-Wolf
Affiliation:
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

New computing and communications paradigms will result in traffic loads in information server systems that fluctuate over much broader ranges of time scales than current systems. In addition, these fluctuation time scales may only be indirectly known or even be unknown. However, we should still be able to accurately design and manage such systems. This paper addresses this issue: we consider an M/M/1 queueing system operating in a random environment (denoted M/M/1(R)) that alternates between HIGH and LOW phases, where the load in the HIGH phase is higher than in the LOW phase. Previous work on the performance characteristics of M/M/1(R) systems established fundamental properties of the shape of performance curves. In this paper, we extend monotonicity results to include convexity and concavity properties, provide a partial answer to an open problem on stochastic ordering, develop new computational techniques, and include boundary cases and various degenerate M/M/1(R) systems. The basis of our results are novel representations for the mean number in system and the probability of the system being empty. We then apply these results to analyze practical aspects of system operation and design; in particular, we derive the optimal service rate to minimize mean system cost and provide a bias analysis of the use of customer-level sampling to estimate time-stationary quantities.

Keywords

cubic polynomialM/M/1 single-server queuemonotonicityrandom environmentsamplingtime varying load
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 36 , Issue 3 , July 2022 , pp. 690 - 731
Copyright
Copyright © The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abate, J. & Whitt, W. (1987). Transient behavior of the M/M/1 queue: starting at the origin. Queueing Systems 2: 41–65.CrossRefGoogle Scholar
Abate, J. & Whitt, W. (1988). Simple spectral representations for the M/M/1. Queueing Systems 3: 321–346.CrossRefGoogle Scholar
Abate, J. & Whitt, W. (1988). Transient behavior of the M/M/1 queue via Laplace transforms. Advances in Applied Probability 20(1): 145–178.CrossRefGoogle Scholar
Abate, J. & Whitt, W. (1989). Calculating time-dependent performance measures for M/M/1 queue. IEEE Transactions on Communications 37(10): 1102–1104.CrossRefGoogle Scholar
Abate, J., Kijama, M., & Whitt, W. (1989). Decompositions of the M/M/1 transition function. Queueing Systems 9(3): 323–336.CrossRefGoogle Scholar
Arjas, E. (1972). On the use of a fundamental identity in the theory of semi-Markov queues. Advances in Applied Probability 4(2): 271–284.CrossRefGoogle Scholar
Baccelli, F. & Massey, W.A. (1989). A sample path analysis of the M/M/1 queue. Journal of Applied Probability 26(2): 418–422.CrossRefGoogle Scholar
Bailey, N.T.J. (1954). A continuous time treatment of a simple queue using generating functions. Journal of the Royal Statistical Society: Series B (Methodological) 16(2): 288–291.Google Scholar
Bolot, J.-C. & Shankar, A.U. (1995). Optimal least-squares approximations to the transient behavior of the stable M/M/1 queue. IEEE Transactions on Communications 43(2/3/4): 1293–1298.CrossRefGoogle Scholar
Champernowne, D.G. (1956). An elementary method of solution of the queueing problem with a single server and constant parameters. Journal of the Royal Statistical Society: Series B (Methodological) 18(1): 125–128.Google Scholar
Chan, C.W., Dong, J., & Green, L.V. (2016). Queues with time-varying arrivals and inspections with applications to hospital discharge policies. Operations Research 65(2): 469–495.CrossRefGoogle Scholar
Çinlar, E. (1967). Queues with semi-Markov arrivals. Journal of Applied Probability 4(2): 365–379.CrossRefGoogle Scholar
Çinlar, E. (1967). Time dependence of queues with semi-Markov services. Journal of Applied Probability 4(2): 356–364.CrossRefGoogle Scholar
Clarke, A.B. (1956). A waiting line process of Markov type. Annals of Mathematical Statistics 27(2): 452–459.CrossRefGoogle Scholar
Conolly, B.W. & Langaris, C. (1993). On a new formula for the transient state probabilities for M/M/1 queues and computational implications. Journal of Applied Probability 30(1): 237–246.CrossRefGoogle Scholar
Day, D. & Romero, L. (2006). Roots of polynomials expressed in terms of orthogonal polynomials. SIAM Journal on Numerical Analysis 43(5): 1969–1987.CrossRefGoogle Scholar
Gupta, V., Harchol-Balter, M., Scheller-Wolf, A., & Yechiali, U. (2006). Fundamental characteristics of queues with fluctuating load. ACM SIGMETRICS Performance Evaluation Review 34(1): 203–215.CrossRefGoogle Scholar
Haghighi, A.M. & Mishev, D.P. (2013). Difference and differential equations with applications in queueing theory. Hoboken, New Jersey: John Wiley & Sons.CrossRefGoogle Scholar
Hampshire, R.C., Harchol-Balter, M., & Massey, W.A. (2006). Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates. Queueing Systems 53(1–2): 19–30.CrossRefGoogle Scholar
Kumar, B.K. & Arivudainambi, D. (2000). Transient solution of an M/M/1 queue with catastrophes. Computers & Mathematics with Applications 40: 1233–1240.CrossRefGoogle Scholar
Latouche, G. & Ramaswami, V. (1999). Introduction to matrix analytic methods in stochastic modeling. Philadelphia, Pennsylvania: American Statistical Association and the Society for Industrial and Applied Mathematics.CrossRefGoogle Scholar
Medhi, J. (2003). Stochastic models in queueing theory, 2nd ed. Amsterdam: Academic Press.Google Scholar
Neuts, M. (1966). The single server queue with Poisson input and semi-Markov service times. Journal of Applied Probability 3(1): 202–230.CrossRefGoogle Scholar
Neuts, M. (1978). The M/M/1 queue with randomly varying arrival and service rates. Management Science 15(4): 139–168.Google Scholar
Neuts, M.F. (1981). Matrix-geometric solutions in stochastic models: an algorithmic approach. New York: Dover Publications.Google Scholar
Purdue, P. (1974). The M/M/1 queue in a Markovian environment. Operations Research 22(3): 562–569.CrossRefGoogle Scholar
Ramaswami, V. (1980). The N/G/1 queue and its detailed analysis. Advances in Applied Probability 12(1): 222–261.CrossRefGoogle Scholar
Sharma, O.P. (1990). Markovian queues. Chichester: Ellis Horwood.Google Scholar
Sharma, O.P. & Bunday, B.D. (1997). A simple formula for the transient state probabilities of an M/M/1/∞ queue. Optimization 40(1): 79–84.CrossRefGoogle Scholar
Stidham, S. Jr (2009). Optimal design of queueing systems. Boca Raton, Florida: Chapman and Hall/CRC.CrossRefGoogle Scholar
Tarabia, A.M.K. (2002). A new formula for the transient behaviour of a non-empty M/M/1/∞ queue. Applied Mathematics and Computation 132: 1–10.CrossRefGoogle Scholar
van de Coevering, M.C.T. (1995). Computing transient performance measures for the M/M/1 queue. OR Spektrum 17: 19–22.CrossRefGoogle Scholar
Whitt, W. (2016). Queues with time-varying arrival rates. A bibliography. Working paper.Google Scholar
Yechiali, U. & Naor, P. (1971). Queueing problems with heterogeneous arrivals and service. Operations Research 19(3): 722–734.CrossRefGoogle Scholar