APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES


Creative Commons License

SEZER A. D.

JOURNAL OF APPLIED PROBABILITY, vol.55, no.3, pp.968-997, 2018 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 55 Issue: 3
  • Publication Date: 2018
  • Doi Number: 10.1017/jpr.2018.60
  • Journal Name: JOURNAL OF APPLIED PROBABILITY
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.968-997
  • Keywords: Large deviation, constrained random walk, buffer overflow, queueing system, exit time, harmonic system, LARGE DEVIATIONS, RANDOM-WALK, ALGORITHMS, SIMULATION, NETWORKS, BOUNDARY, EQUATION

Abstract

Let X be the constrained random walk on Z(+)(2) having increments (1, 0), (-1, 1), and (0, -1) with respective probabilities A lambda,mu 1, and mu 2 representing the lengths of two tandem queues. We assume that X is stable and mu 1 not equal mu 2. Let tau(n) be the first time when the sum of the components of X equals n. Let Y be the constrained random walk on Z x Z(+) having increments (-1, 0), (1, 1), and (0, -1) with probabilities lambda, mu(1), and mu(2). Let tau be the first time that the components of Y are equal to each other. We prove that Pn-xn(1),x(n)(2)(tau < infinity) approximates p(n)(x(n)) with relative error exponentially decaying in n for x(n) = [n(x)], x is an element of R-+(2), 0 < x(1) + x(2) < 1, x (1) > 0. An affine transformation moving the origin to the point (n, 0) and letting n -> infinity 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 P-y (tau < infinity) 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 HamiltonJacobi-Bellman equation on a manifold consisting of three copies of R-+(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.