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

Many-server queues;Stochastic comparison;Kingman’s bound;Renewal process;Halfin-Whitt regime;Heavy tails;Weak convergence;Large deviations;Gaussian process;Stable law

Li, Yuan ; Goldberg, David Industrial and Systems Engineering Maguluri, Siva Theja Foley, Robert Ayhan, Hayriye Xu, Jun ; Goldberg, David

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Many-server queues;    Stochastic comparison;    Kingman’s bound;    Renewal process;    Halfin-Whitt regime;    Heavy tails;    Weak convergence;    Large deviations;    Gaussian process;    Stable law;   

Others  :  https://smartech.gatech.edu/bitstream/1853/60118/1/LI-DISSERTATION-2017.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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.