Approximation of excessive backlog probabilities of two tandem queues
Open Access
- 1 September 2018
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 55 (3) , 968-997
Abstract
LetXbe the constrained random walk on ℤ+2having increments (1,0), (-1,1), and (0,-1) with respective probabilities λ, µ1, and µ2representing the lengths of two tandem queues. We assume thatXis stable and µ1≠µ2. Let τnbe the first time when the sum of the components ofXequalsn. LetYbe the constrained random walk on ℤ×ℤ+having increments (-1,0), (1,1), and (0,-1) with probabilities λ, µ1, and µ2. Let τ be the first time that the components ofYare equal to each other. We prove thatPn-xn(1),xn(2)(τ<∞) approximatespn(xn) with relative errorexponentially decayinginnforxn=⌊nx⌋,x∈ℝ+2, 0<x(1)+x(2)0. An affine transformation moving the origin to the point (n,0) and lettingn→∞ connect theXandYprocesses. We use a linear combination of basis functions constructed from single and conjugate points on a characteristic surface associated withXto derive a simple expression for ℙy(τ<∞) in terms of the utilization rates of the nodes. The proof that the relative error decays exponentially innuses a sequence of subsolutions of a related Hamilton‒Jacobi‒Bellman equation on a manifold consisting of three copies of ℝ+2glued to each other along the constraining boundaries. We indicate how the ideas of the paper can be generalized to more general processes and other exit boundaries.Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Revisiting the Tail Asymptotics of the Double QBD Process: Refinement and Complete Solutions for the Coordinate and Diagonal Directions2012
- Random Perturbations of Dynamical Systems2012
- Rare Event Simulation using Monte Carlo Methods2009
- Stochastic Simulation: Algorithms and Analysis2007
- Distributed algorithms in an ergodic Markovian environmentRandom Structures & Algorithms, 2006
- Fundamentals of Queueing Networks2001
- Numerical Methods for Stochastic Control Problems in Continuous Time2001
- A Weak Convergence Approach to the Theory of Large Deviations1997
- Colliding stacks: A large deviations analysisRandom Structures & Algorithms, 1991
- Probabilistic analysis of some distributed algorithmsRandom Structures & Algorithms, 1991