Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T13:41:00.515Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximation of excessive backlog probabilities of two tandem queues

Part of: Limit theorems Markov processes Stochastic processes

Published online by Cambridge University Press:  16 November 2018

Ali Devin Sezer
Ali Devin Sezer*
Affiliation:
Middle East Technical University
*
* Postal address: Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let X be the constrained random walk on ℤ+2 having increments (1,0), (-1,1), and (0,-1) with respective probabilities λ, µ1, and µ2 representing the lengths of two tandem queues. We assume that X is stable and µ1≠µ2. Let τn be the first time when the sum of the components of X equals n. Let Y be 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 of Y are equal to each other. We prove that Pn-xn(1),xn(2)(τ<∞) approximates pn(xn) with relative error exponentially decaying in n for xn=⌊nx⌋, x ∈ℝ+2, 0<x(1)+x(2)<1, x(1)>0. An affine transformation moving the origin to the point (n,0) and letting n→∞ connect the X and Y processes. We use a linear combination of basis functions constructed from single and conjugate points on a characteristic surface associated with X to derive a simple expression for ℙy(τ<∞) in terms of the utilization rates of the nodes. The proof that the relative error decays exponentially in n uses a sequence of subsolutions of a related Hamilton‒Jacobi‒Bellman equation on a manifold consisting of three copies of ℝ+2 glued 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

Large deviationconstrained random walkbuffer overflowqueueing systemexit timeharmonic system

MSC classification

Primary: 60G50: Sums of independent random variables; random walks
Secondary: 60G40: Stopping times; optimal stopping problems; gambling theory 60F10: Large deviations 60J45: Probabilistic potential theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 55 , Issue 3 , September 2018 , pp. 968 - 997
Copyright
Copyright © Applied Probability Trust 2018 

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

[1]Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
[2]Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis. Springer, New York.Google Scholar
[3]Atar, R. and Dupuis, P. (1999). Large deviations and queueing networks: methods for rate function identification. Stoch. Process. Appl. 84, 255–296.Google Scholar
[4]Blanchet, J. (2013). Optimal sampling of overflow paths in Jackson networks. Math. Operat. Res. 38, 698–719.Google Scholar
[5]Blanchet, J. H., Leder, K. and Glynn, P. W. (2008). Efficient simulation of light-tailed sums: an old-folk song sung to a faster new tune. In Monte Carlo and Quasi-Monte Carlo Methods 2008, Springer, Berlin, pp. 227–258.Google Scholar
[6]Borovkov, A. A. and Mogul'skiĭ, A. A. (2001). Large deviations for Markov chains in the positive quadrant. Russian Math. Surveys 56, 803–916.Google Scholar
[7]Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, New York.Google Scholar
[8]Comets, F., Delarue, F. and Schott, R. (2007). Distributed algorithms in an ergodic Markovian environment. Random Structures Algorithms 30, 131–167.Google Scholar
[9]Dai, J. G. and Miyazawa, M. (2011). Reflecting Brownian motion in two dimensions: exact asymptotics for the stationary distribution. Stoch. Systems 1, 146–208.Google Scholar
[10]De Boer, P.-T. (2006). Analysis of state-independent importance-sampling measures for the two-node tandem queue. ACM Trans. Model. Comput. Simul. 16, 225–250.Google Scholar
[11]Dean, T. and Dupuis, P. (2009). Splitting for rare event simulation: a large deviation approach to design and analysis. Stoch. Process. Appl. 119, 562–587.Google Scholar
[12]Dupuis, P. and Ellis, R. S. (1997). A Weak Convergence Approach to the Theory of Large Deviations. John Wiley, New York.Google Scholar
[13]Dupuis, P. and Ellis, R. S. (1995). The large deviation principle for a general class of queueing systems. I. Trans. Amer. Math. Soc. 347, 2689–2751.Google Scholar
[14]Dupuis, P. and Wang, H. (2004). Importance sampling, large deviations, and differential games. Stoch. Stoch. Reports 76, 481–508.Google Scholar
[15]Dupuis, P. and Wang, H. (2007). Subsolutions of an Isaacs equation and efficient schemes for importance sampling. Math. Operat. Res. 32, 723–757.Google Scholar
[16]Dupuis, P. and Wang, H. (2009). Importance sampling for Jackson networks. Queueing Systems 62, 113–157.Google Scholar
[17]Dupuis, P., Leder, K. and Wang, H. (2007). Importance sampling for sums of random variables with regularly varying tails. ACM Trans. Model. Comput. Simul. 17, 14.Google Scholar
[18]Dupuis, P., Sezer, A. D. and Wang, H. (2007). Dynamic importance sampling for queueing networks. Ann. Appl. Prob. 17, 1306–1346.Google Scholar
[19]Durrett, R. (1996). Probability: Theory and Examples, 2nd edn. Duxbury, Belmont, CA.Google Scholar
[20]Flajolet, P. (1986). The evolution of two stacks in bounded space and random walks in a triangle. In Mathematical Foundations of Computer Science, 1986, Springer, Berlin, pp. 325–340.Google Scholar
[21]Foley, R. D. and McDonald, D. R. (2012). Constructing a harmonic function for an irreducible nonnegative matrix with convergence parameter R > 1. Bull. London Math. Soc. 44, 533–544.+1.+Bull.+London+Math.+Soc.+44,+533–544.>Google Scholar
[22]Freidlin, M. I. and Wentzell, A. D. (2012). Random Perturbations of Dynamical Systems, 2nd edn. Springer, Heidelberg.Google Scholar
[23]Glasserman, P. and Kou, S.-G. (1995). Analysis of an importance sampling estimator for tandem queues. ACM Trans. Model. Comput. Simul. 5, 22–42.Google Scholar
[24]Griffiths, P. A. (1989). Introduction to Algebraic Curves. American Mathematical Society, Providence, RI.Google Scholar
[25]Guillotin-Plantard, N. and Schott, R. (2006). Dynamic Random Walks: Theory and Applications. Elsevier, Amsterdam.Google Scholar
[26]Henderson, S. G. and Nelson, B. L. (eds) (2006). Handbooks in Operations Research and Management Science: Vol. 13, Simulation. North-Holland, Amsterdam.Google Scholar
[27]Ignatiouk-Robert, I. (2000). Large deviations of Jackson networks. Ann. Appl. Prob. 10, 962–1001.Google Scholar
[28]Ignatiouk-Robert, I. and Loree, C. (2010). Martin boundary of a killed random walk on a quadrant. Ann. Prob. 38, 1106–1142.Google Scholar
[29]Ignatyuk, I. A., Malyshev, V. A. and Scherbakov, V. V. (1994). Boundary effects in large deviation problems. Russian. Math. Surveys 49, 41–99.Google Scholar
[30]Juneja, S. and Nicola, V. (2005). Efficient simulation of buffer overflow probabilities in Jackson networks with feedback. ACM Trans. Model. Comput. Simul. 15, 281–315.Google Scholar
[31]Knuth, D. E. (1969). The Art of Computer Programming, Vol. 1, Fundamental Algorithms. Addison-Wesley, Reading, MA.Google Scholar
[32]Kobayashi, M. and Miyazawa, M. (2013). Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions. In Matrix-Analytic Methods in Stochastic Models, Springer, New York, pp. 145–185.Google Scholar
[33]Kurkova, I. A. and Malyshev, V. A. (1998). Martin boundary and elliptic curves. Markov Process. Relat. Fields 4, 203–272.Google Scholar
[34]Kushner, H. J. and Dupuis, P. (2001). Numerical Methods for Stochastic Control Problems in Continuous Time, 2nd edn. Springer, New York.Google Scholar
[35]Louchard, G. and Schott, R. (1991). Probabilistic analysis of some distributed algorithms. Random Structures Algorithms 2, 151–186.Google Scholar
[36]Louchard, G., Schott, R., Tolley, M. and Zimmermann, P. (1994). Random walks, heat equation and distributed algorithms. J. Comput. Appl. Math. 53, 243–274.Google Scholar
[37]Maier, R. S. (1991). Colliding stacks: a large deviations analysis. Random Structures Algorithms 2, 379–420.Google Scholar
[38]Maier, R. S. (1993). Large fluctuations in stochastically perturbed nonlinear systems: applications in computing. In 1992 Lectures in Complex Systems, Addison-Wesley, Reading, MA, pp. 501–517.Google Scholar
[39]McDonald, D. R. (1999). Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Prob. 9, 110–145.Google Scholar
[40]Miretskiy, D., Scheinhardt, W. and Mandjes, M. (2010). State-dependent importance sampling for a Jackson tandem network. ACM Trans. Model. Comput. Simul. 20, 15.Google Scholar
[41]Miyazawa, M. (2009). Tail decay rates in double QBD processes and related reflected random walks. Math. Operat. Res. 34, 547–575.Google Scholar
[42]Miyazawa, M. (2011). Light tail asymptotics in multidimensional reflecting processes for queueing networks. TOP 19, 233–299.Google Scholar
[43]Ney, P. and Nummelin, E. (1987). Markov additive processes. I. Eigenvalue properties and limit theorems. Ann. Prob. 15, 561–592.Google Scholar
[44]Nicola, V. F. and Zaburnenko, T. S. (2007). Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks. ACM Trans. Model. Comput. Simul. 17, 10.Google Scholar
[45]Parekh, S. and Walrand, J. (1989). A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Automatic Control 34, 54–66.Google Scholar
[46]Revuz, D. (1984). Markov Chains, 2nd edn. North-Holland, Amsterdam.Google Scholar
[47]Ridder, A. (2009). Importance sampling algorithms for first passage time probabilities in the infinite server queue. Europ. J. Operat. Res. 199, 176–186.Google Scholar
[48]Robert, P. (2003). Stochastic Networks and Queues. Springer, Berlin.Google Scholar
[49]Rubino, G. and Tuffin, B. (2009). Rare Event Simulation using Monte Carlo Methods. John Wiley, New York.Google Scholar
[50]Setayeshgar, L. and Wang, H. (2013). Efficient importance sampling schemes for a feed-forward network. ACM Trans. Model. Comput. Simul. 23, 21.Google Scholar
[51]Sezer, A. D. (2006). Dynamic Importance Sampling for Queueing Networks. Doctoral thesis. Division of Applied Mathematics, Brown University.Google Scholar
[52]Sezer, A. D. (2007). Asymptotically optimal importance sampling for Jackson networks with a tree topology. Preprint. Available at https://arxiv.org/abs/0708.3260.Google Scholar
[53]Sezer, A. D. (2009). Importance sampling for a Markov modulated queuing network. Stoch. Process. Appl. 119, 491–517.Google Scholar
[54]Sezer, A. D. (2010). Asymptotically optimal importance sampling for Jackson networks with a tree topology. Queueing Systems 64, 103–117.Google Scholar
[55]Sezer, A. D. (2015). Exit probabilities and balayage of constrained random walks. Preprint. Available at https://arxiv.org/abs/1506.08674.Google Scholar
[56]Sezer, A. D. and Özbudak, F. (2011). Approximation of bounds on mixed-level orthogonal arrays. Adv. Appl. Prob. 43, 399–421.Google Scholar
[57]Yao, A. C. (1981). An analysis of a memory allocation scheme for implementing stacks. SIAM J. Comput. 10, 398–403.Google Scholar