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/mu_1 ge rho_2 = lambda_2/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 }$. Let $Y$ be the same random walk as $X$ but only constrained on ${y in {mathbb Z}^2: y(2)=0}$ and its jump probabilities for the first component reversed. Let $partial B ={y in {mathbb Z}^2: y(1) = y(2) }$ and let $tau$ be the first time $Y$ hits $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 systems first busy cycle). Stability of $X$ implies $p_n$ decays exponentially in $n$ when the process starts off $partial A_n.$ 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)$ with exponentially vanishing relative error. Let $r = (lambda_1 + lambda_2)/(mu_1 + mu_2)$; for $r^2 < rho_2$ and $rho_1 eq 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 < 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).$
Download