Georgia Institute of Technology
Stochastic comparison approach to multi-server queues: Bounds, heavy tails and large deviations
Abstract
dc:description.abstractIn 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 μA (μ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 μA)r\big], \E\big[(S μ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 + ε moment for some ε > 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 α \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}{α}, is tight. In the third part of this thesis, when service times have a Pareto tail with index α \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 α \in (1,2), we bound the large-deviation behaviors of the weak limits of the n\frac{1}{α} scaled statioanry queue lengths in a generalized Halfin-Whitt regime, and find that our bounds are tight when service times are deterministic.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Industrial and Systems Engineering
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Li, Yuan
- Advisor dc:contributor.advisor
-
- Goldberg, David A.
- Committee members dc:contributor.committeemember
-
- Maguluri, Siva Theja
- Foley, Robert
- Ayhan, Hayriye
- Xu, Jun
Subjects
dc:subject × 10Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/60118