APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES

Download

index.pdf

Date

2018-09-01

Author

Sezer, Ali Devin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

207
views

0
downloads

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.

Subject Keywords

Large deviations, Constrained random walks, Buffer overlow, Queueing systems, Exit times, Harmonic systems

URI

https://hdl.handle.net/11511/31800

Journal

JOURNAL OF APPLIED PROBABILITY

DOI

https://doi.org/10.1017/jpr.2018.60

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Excessive backlog probabilities of two parallel queues Unlu, Kamil Demirberk; Sezer, Ali Devin (2020-10-01) Let X be the constrained random walk on Z2 + with increments (1, 0), (-1, 0), (0, 1) and (0,-1); X represents, at arrivals and service completions, the lengths of two queues (or two stacks in computer science applications) working in parallel whose service and interarrival times are exponentially distributed with arrival rates.i and service rates mu i, i = 1, 2; we assume.i < mu i, i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume.1 =.1/mu 1 similar to.2 =.2/mu 2. Let tn be the first...
Approximation of the exit probability of a stable Markov modulated constrained random walk Kabran, Fatma Basoglu; Sezer, Ali Devin (2020-06-01) Let X be the constrained randomwalk on Z(+)(2) having increments (1, 0), (- 1, 1), (0,- 1) with jump probabilities lambda(M-k), mu(1)(M-k), and mu(2)(M-k) where M is an irreducible aperiodic finite state Markov chain. The process X represents the lengths of two tandem queues with arrival rate lambda(M-k), and service rates mu(1)(M-k), and mu(2)(M-k); the process M represents the random environment within which the system operates. We assume that the average arrival rate with respect to the stationary measur...
Approximation of excessive backlog probabilities of two parallel queues Ünlü, Kamil Demirberk; Sezer, Ali Devin (2018-07-25) Let X be the constrained random walk on Z 2 + with increments (1, 0), (−1, 0), (0, 1) and (0, −1) representing the lengths at service completion times of two queues with exponentially distributed interarrival and service times running in parallel. Denote the arrival and service rates by λ i , µ i , i = 1, 2; we assume λ i < µ i , i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume ρ 1 ≥ ρ 2. Let τ n be the first time X hits the line ∂A n = {x ∈ Z 2 : x(1)+x(2) = n}, i.e., when the sum ...
Exit probabilities of markov modulated constrained random walks Başoğlu Kabran, Fatma; Sezer, Ali Devin; Department of Financial Mathematics (2018) Let X be the constrained random walk on Z2+ with increments (0, 0), (1, 0), (−1, 1), (0, −1) whose jump probabilities are determined by the state of a finite state Markov chain M. X represents the lengths of two queues of customers (or packets, tasks, etc.) waiting for service from two servers working in tandem; the arrival of customers occur with rate λ(Mk), service takes place at rates μ1(Mk), and μ2(Mk) where Mk denotes the current state of the Markov chain M. We assume that the average arrival rate is l...
Factorization of Joint Probability Mass Functions into Parity Check Interactions Bayramoglu, Muhammet Fatih; Yılmaz, Ali Özgür (2009-07-03) We show that any joint probability mass function (PMF) can be expressed as a product of parity check factors an d factors of degree one with the help of some auxiliary variables, if the alphabet size is appropriate for defining a parity chec k equation. In other words, marginalization of a joint PMF is equivalent to a soft decoding task as long as a finite field can be constructed over the alphabet of the PMF. In factor graph terminology this claim means that a factor graph representing such a joint PMF alw...

Citation Formats

A. D. Sezer, “APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES,” JOURNAL OF APPLIED PROBABILITY, pp. 968–997, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31800.