Stochastic comparison approach to multi-server queues: bounds, heavy tails and large deviations

Abstract

In the first part of this thesis, we consider the FCFS $GI/GI/n$ queue, and prove the first simple and explicit bounds that scale gracefully and universally as $\frac{1}{1-\rho}$ ($\rho$ being the corresponding traffic intensity), across both the classical and Halfin-Whitt heavy traffic settings. In particular, supposing that the inter-arrival and service times, distributed as random variables $A$ and $S$, have finite $r$th moment for some $r > 2$, and letting $\mu_A (\mu_S)$ denote $\frac{1}{\E[A]} (\frac{1}{\E[S]})$, our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay, expressed as simple and explicit functions of only $ \E\big[(A \mu_A)^r\big], \E\big[(S \mu_S)^r\big], r$, and $\frac{1}{1-\rho}$.

In the second part of this thesis, we prove that when service times have finite $1 + \epsilon$ moment for some $\epsilon > 0$ and inter-arrival times have finite second moment, the sequence of stationary queue length distributions, normalized by $n^{\frac{1}{2}}$, is tight in the Halfin-Whitt regime. Furthermore, we develop simple and explicit bounds on the stationary queue length in that regime. When the inter-arrival times have a Pareto tail with index $\alpha \in (1,2)$, we prove that in a generalized Halfin-Whitt regime, for general service time distributions, the sequence of stationary queue length distributions, normalized by $n^{\frac{1}{\alpha}}$, is tight.

In the third part of this thesis, when service times have a Pareto tail with index $\alpha \in (1,2)$ and inter-arrival times have finite second moment, we bound the large deviation behavior of the weak limits of the $n^{\frac{1}{2}}$ scaled stationary queue lengths in the Halfin-Whitt regime, and derive a matching lower bound when inter-arrival times are Markovian. We find that the tail of the limit has a \emph{sub-exponential} decay, differing fundamentally from the exponential decay in the light-tailed setting. When inter-arrival times have a Pareto tail with index $\alpha \in (1,2)$, we bound the large-deviation behaviors of the weak limits of the $n^{\frac{1}{\alpha}}$ scaled statioanry queue lengths in a generalized Halfin-Whitt regime, and find that our bounds are tight when service times are deterministic.