Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T18:07:05.507Z Has data issue: false hasContentIssue false
  • English
  • Français

The probability of large queue lengths and waiting times in a heterogeneous multiserver queue I: Tight limits

Part of: Markov processes Limit theorems Special processes

Published online by Cambridge University Press:  01 July 2016

John S. Sadowsky  and
Wojciech Szpankowski
John S. Sadowsky*
Affiliation:
Arizona State University
Wojciech Szpankowski*
Affiliation:
Purdue University
*
* Postal address: Department of Electrical Engineering, Arizona State University, Tempe, AZ 85287–5706, USA.
** Postal address: Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a multiserver queuing process specified by i.i.d. interarrival time, batch size and service time sequences. In the case that different servers have different service time distributions we say the system is heterogeneous. In this paper we establish conditions for the queuing process to be characterized as a geometrically Harris recurrent Markov chain, and we characterize the stationary probabilities of large queue lengths and waiting times. The queue length is asymptotically geometric and the waiting time is asymptotically exponential. Our analysis is a generalization of the well-known characterization of the GI/G/1 queue obtained using classical probabilistic techniques of exponential change of measure and renewal theory.

Keywords

QUEUEING THEORYHARRIS RECURRENT MARKOV CHAINSFOSTER–LYAPUNOV THEORYMARKOV ADDITIVE PROCESSESRENEWAL THEORY

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60F10: Large deviations 60J05: Discrete-time Markov processes on general state spaces 60K15: Markov renewal processes, semi-Markov processes 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 27 , Issue 2 , June 1995 , pp. 532 - 566
Copyright
Copyright © Applied Probability Trust 1995 

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.)

Footnotes

Supported by the National Science Foundation (NCR-9003007).

Supported by the National Science Foundation (NCR-9206315 and CCR-9201078), AFOSR (90–0107), and by the National Library of Medicine (R01 LM05118).

References

Aldous, D., Hofri, M. and Szpankowski, W. (1992) Maximum size of a dynamic data structure: hashing with lazy deletion revisited. SIAM J. Computing 21, 713–732.Google Scholar
Arjas, E., Nummelin, E. and Tweedie, R. L. (1978) Uniform limit theorems for non-singular renewal and Markov renewal processes. J. Appl. Prob. 15, 112–125.Google Scholar
Athreya, K. B., Mcdonald, D. and Ney, P. (1978) Limit theorems for semi-Markov processes and renewal theory for Markov chains. Ann. Prob. 6, 788–797.Google Scholar
Bucklew, J. A., Ney, P. and Sadowsky, J. S. (1990) Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob. 27, 44–59.CrossRefGoogle Scholar
Feller, W. (1971) An Introduction to Probability and its Applications, Vol. II. Wiley, New York.Google Scholar
Iglehart, D. L. (1989) Extreme values in the GI/G/1 queue. Ann Math. Statist. 43, 627–635.CrossRefGoogle Scholar
Meyn, S. P. and Tweedie, R. L. (1992) Stability of Markovian processes I: criteria for discrete time chains. Adv. Appl. Prob. 24, 542–574.Google Scholar
Meyn, S. P. and Tweedie, R. L. (1993) Markov Chains and Stochastic Stability. Springer-Verlag, New York.Google Scholar
Neuts, M. and Takahashi, Y. (1981) Asymptotic behavior of the stationary distribution in the GI/PH/c queue with heterogeneous servers. Z. Wahrscheinlichkeitsth. 57, 441–452.Google Scholar
Ney, P. and Nummelin, E. (1984) Some limit theorems for Markov additive processes. Proc. Symp. on Semi-Markov Models, Brussels.Google Scholar
Nummelin, E. (1984) General Irreducible Markov Chains and Non-negative Operators. Cambridge University Press.Google Scholar
Sadowsky, J. S. (1991) Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. Autom. Control 36, 1383–1394.CrossRefGoogle Scholar
Sadowsky, J. S. (1993) On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inf. Theory 39, 119–128.Google Scholar
Sadowsky, J. S. and Szpankowski, W. (1992) Maximum queue length and waiting time revisited: G/G/c queue. Prob. Eng. Inf. Sci. 6, 157–170.Google Scholar
Takahashi, Y. (1981) Asymptotic exponentiality of the tail of the waiting-time distribution in a PH/PH/c queue. Adv. Appl. Prob. 25, 391–403.Google Scholar