Abstract
The problem considered is that of estimating the tail stationary probability for two exponential server queues in series fed by renewal arrivals. We compute the tail of the marginal queue length distribution at the second queue. The marginal at the first queue is known by the classical result for the GI/M/1 queue. The approach involves deriving necessary and sufficient conditions on the paths of the arrival and virtual service processes in order to get a large queue size at the second queue. We then use large deviations estimates of the probabilities of these paths, and solve a constrained convex optimization problem to find the most likely path leading to a large queue size. We find that the stationary queue length distribution at the second queue has an exponentially decaying tail, and obtain the exact rate of decay.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. Anantharam, The optimal buffer allocation problem, IEEE Trans. Inform. Theory 35 (1989) 721–725.
V. Anantharam and A. Ganesh, Correctness within a constant of an optimal buffer allocation rule of thumb, IEEE Trans. Info. Theory 40 (1994) 871–882.
V. Anantharam, P. Heidelberger and P. Tsoucas, Analysis of rare events in continuous time Markov chains via time reversal and fluid approximations, IBM Research Report RC 16280 (1990).
S. Asmussen,Applied Probability and Queues (Wiley, 1987).
D. Bertsimas, I. Paschalidis and J. Tsitsiklis, On the large deviations behaviour of acyclic networks of G/G/1 queues, submitted to Ann. Appl. Prob.
R. Blahut,Principles and Practice of Information Theory (Addison-Wesley, 1987).
C.S. Chang, Stability, queue length and delay of deterministic and stochastic queueing networks, IEEE Trans. Autom.Control 39 (1994) 913–931.
C.S. Chang, Sample path large deviations and intree networks, IBM Research Report RC 19118 (1993).
C.S. Chang, P. Heidelberger, S. Juneja and P. Shahabuddin, Effective bandwidth and fast simulation of ATM intree networks, Perform. Eval. 20 (1994) 45–66.
G. de Veciana and J. Walrand, Effective bandwidths: call admission, traffic policing and filtering for ATM networks, to appear in Queueing Systems.
G. de Veciana and J. Walrand, Decoupling bandwidths for networks: a decomposition approach to resource management, Memorandum No. UCB/ERL M93/50, University of California, Berkeley (1993).
A. Dembo and O. Zeitouni,Large Deviations Techniques and Applications (Jones and Bartlett, 1993).
N. Duffield and N. O'Connell, Large deviations and overflow probabilities for the general single server queue, with applications, to appear in Proc. Camb. Phil. Soc.
M.R. Frater, T.M. Lennon and B.D.O. Anderson, Optimally efficient estimation of the statistics of rare events in queueing networks, IEEE Trans. Autom. Control 36 (1991) 1395–1405.
A. Ganesh, Stationary tail probabilities in exponential server tandems with renewal arrivals, Ph.D. Thesis, Cornell University (1995).
A. Ganesh and V. Anantharam, Stationary tail probabilities in exponential server tandems with renewal arrivals, in:Stochastic Networks, IMA Volumes in Mathematics and its Applications, Vol. 71, eds. F. P. Kelly and R. J. Williams (Springer, 1995).
P.W. Glynn and W. Whitt, Logarithmic asymptotics for steady-state tail probabilities in a single-server queue, to appear in J. Appl. Prob.
R.M. Loynes, The stability of queues with non-independent inter-arrival and service times, Proc. Camb. Phil. Soc. 58 (1962) 497–520.
J.E. Marsden,Elementary Classical Analysis, (W.H. Freeman, 1993).
A. Mogulskii, Large deviations for trajectories of multi-dimensional random walks, Theor. Prob. Appl. 21 (1976) 300–315.
N. O'Connell, Large deviations in queueing networks, DIAS Technical Report DIAS-APG-9413.
S. Parekh and J. Walrand, A quick simulation method for excessive backlogs in networks of queues, IEEE Trans. Autom. Control 34 (1989) 54–66.
P. Tsoucas, Rare events in series of queues, J. Appl. Prob. 29 (1992) 168–175.
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF grant NCR 88-57731 and the AT & T Foundation.
Rights and permissions
About this article
Cite this article
Ganesh, A., Anantharam, V. Stationary tail probabilities in exponential server tandems with renewal arrivals. Queueing Syst 22, 203–247 (1996). https://doi.org/10.1007/BF01149173
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01149173