Back to search

Georgia Institute of Technology

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

Abstract

dc:description.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 μ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 × 10

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/60118

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Yuan. Stochastic comparison approach to multi-server queues: Bounds, heavy tails and large deviations. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/60118