Excessive Backlog Probabilities of Two Parallel Queues

Let $X$ be the constrained random walk on ${\mathbb{Z}}_{+}^2$ with increments $(1,0)$, $(-1,0)$, $(0,1)$ and $(0,-1)$; $X$ represents, at arrivals and service completions, the lengths of two queues working in parallel whose service and interarrival times are exponentially distributed with arrival rates ${\lambda }_i$ and service rates ${\mu }_i$, $i=1,2$; we assume ${\lambda }_i<{\mu }_i$, $i=1,2$, i.e., $X$ is assumed stable. Without loss of generality we assume ${\rho }_1={\lambda }_1\mathrm{/}{\mu }_1\ge {\rho }_2={\lambda }_2\mathrm{/}{\mu }_2$. Let ${\tau }_n$ be the first time $X$ hits the line $\partial A_n = {x \in {\mathbb Z}^2:x(1)+x(2) = n }$\mathrm{.}Let$Y$bethesamerandomwalkas$X$butonlyconstrainedon${y \in {\mathbb Z}^2: y(2)=0}$ and its jump probabilities for the first component reversed. Let $\mathrm{\partial }B=\{y\in {\mathbb{Z}}^2:y(1)=y(2)\}$ and let $\tau$ be the first time $Y$ hits $\mathrm{\partial }B$. The probability $p_n = P_x(\tau_n < \tau_0)$ is a key performance measure of the queueing system represented by $X$ (probability of overflow of a shared buffer during system’s first busy cycle). Stability of $X$ implies $p_n$ decays exponentially in $n$ when the process starts off $\mathrm{\partial }{A}_n\mathrm{.}$ We show that, for $x_n= \lfloor nx \rfloor$,$x \in {\mathbb R}+^2$,$x(1)+x(2) \le 1$,$x(1) > 0$,$P{(n-x_n(1),x_n(2))}( \tau < \infty)$approximates$P_{x_n}(\tau_n < \tau_0)$withexponentiallyvanishingrelativeerror\mathrm{.}Let$r = (\lambda_1 + \lambda_2)/(\mu_1 + \mu_2)$;for$r^2 < \rho_2$and$\rho_1 \neq \rho_2$, we construct a class of harmonic functions from single and conjugate points on a characteristic surface of $Y$ with which $P_y(\tau <\mathrm{\infty })$ can be approximated with bounded relative error. For $r^2={\rho }_1{\rho }_2$, we obtain $P_y(\tau < \infty) = r^{y(1)-y(2)} +\frac{r(1-r)}{r-\rho_2}\left( \rho_1^{y(1)} - r^{y(1)-y(2)} \rho_1^{y(2)}\right).$