Abstract
Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Abate, G. Choudhury, D. Lucantoni, and W. Whitt, Asymptotic analysis of tail probabilities based on the computation of moments. The Annals of Applied Probability 5(4) (1995) 983–1007.
J. Abate, G. Choudhury, and W. Whitt, On the Laguerre method for numerically inverting Laplace transforms. INFORMS Journal on Computing 8 (1996) 413–427.
J. Abate, G. Choudhury, and W. Whitt, Numerical inversion of multidimensional Laplace transforms by the Laguerre method. Performance Evaluation 31(3–4) (1998) 229–243.
J. Abate and W. Whitt, The Fourier-series method for inverting transforms of probability distributions. Queueing Systems 10 (1992) 5–88.
J. Abate and W. Whitt, Numerical inversion of probability generating functions. Operations Research Letters 12(4) (1992) 245–251.
J. Abate and W. Whitt, Solving probability transform functional equations for numerical inversion. Operations Research Letters 12 (1992) 275–281.
J. Abate and W. Whitt, Numerical inversion of Laplace transforms of probability distributions. ORSA Journal on Computing 7(1) (1995) 36–43.
J. Abate and W. Whitt, Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25 (1997) 173–233.
J. C. P. Blanc, On the numerical inversion of busy-period related tranforms. Operations Research Letters 30 (2002) 33–42.
H. Bruneel, B. Steyaert, E. Desmet, and G.H. Petit, Analytic derivation of tail probabilities for queue lengths and waiting times in ATM multiserver queues. European Journal of Operational Research 76 (1994) 563–572.
G. Choudhury and D. Lucantoni, Numerical computation of the moments of a probability distribution from its transforms. Operations Research 44(2) (1996) 368–381.
G. Choudhury and W. Whitt, Computing transient and steady-state distributions in polling models by numerical transform inversion. Performance Evaluation 25 (1994) 267–292.
G. Choudhury and W. Whitt, Computing distributions and moments in polling models by numerical transform inversion. Performance Evaluation 25(4) (1996) 267–292.
M. Drmota, Systems of functional equations. Random Structures & Algorithms 10(1–2) (1997) 103–124.
A. Elwalid and D. Mitra, Analysis, approximations and admission control of a multi-service multiplexing system with priorities. In Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, (1995) 463–472.
G.A. Frolov and M.Y. Kitaev, A problem of numerical inversion of implicitly defined Laplace transforms. Computers Mathematics with Applications 36(5) (1998) 35–44.
K. Laevens and H. Bruneel, Discrete-time multiserver queues with priorities. Performance Evaluation 33(4) (1998) 249–275.
T. Maertens, J. Walraevens, and H. Bruneel, On priority queues with priority jumps. Performance Evaluation. To be published.
T. Sakurai, Numerical inversion for Laplace transforms of functions with discontinuities. Advances in Applied Probability 36(2) (2004) 616–642.
S. Shakkottai and R. Srikant, Many-sources delay asymptotics with applications to priority queues. Queueing Systems 39(2–3) (2001) 183–200.
R.L. Strawderman, Computing tail probabilities by numerical Fourier inversion: the absolutely continuous case. Statistica Sinica 14 (2004) 175–201.
V. Subramanian and R. Srikant, Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queues. Queueing Systems 34(1–4) (2000) 215–236.
A. Sughara, T. Takine, Y. Takahashi, and T. Hasegawa, Analysis of a non-preemptive priority queue with SPP arrivals of high class. Performance Evaluation 21 (1995) 215–238.
J. Walraevens, Discrete-time queueing models with priorities, PhD thesis, Ghent University (2004).
J. Walraevens, B. Steyaert, and H. Bruneel, Performance analysis of the system contents in a discrete-time non-preemptive priority queue with general service times. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL) 40(1–2) (2000).
J. Walraevens, B. Steyaert, and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling. Computers and Operations Research 30(12) (2003) 1807–1829.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Maertens, T., Walraevens, J. & Bruneel, H. Priority queueing systems: from probability generating functions to tail probabilities. Queueing Syst 55, 27–39 (2007). https://doi.org/10.1007/s11134-006-9003-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-006-9003-8