Advisors: Dr. David Goldberg

Committee members:

Dr. Robert Foley

Dr. Hayriye Ayhan

Dr. Siva Theja Maguluri 

Dr. Jun Xu

Date and Time: May 9th (Tuesday), 2017, at 11:00 AM

Location: ISyE Main Building Room 228 - Executive Classroom

Summary:

For a FCFS GI/GI/n model queue, when the number of servers n is large, the direct analysis of various performance metrics is generally analytically intractable. Therefore methods like developing bounds and heavy-traffic approximation are crucial to help us understand the system. A particularly popular heavy-traffic regime is the so-called Halfin-Whitt regime, under which the number of servers n grows large and the traffic intensity ρ converges to unity simultaneously under some square-root staffing rule, allowing the system to strike a balance between quality and efficiency. However, all known bounds for general multi-server queues in this setting suffer from several fundamental shortcomings, such as holding only asymptotically or involving non-explicit constants.  Furthermore, even less is known in the presence of heavy-tailed distributions in the model. This thesis primarily addresses these problems. 

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 1/(1-ρ), across all notions of heavy traffic, including both the classical and Halfin-Whitt settings. In particular, supposing that the inter-arrival and service times, distributed as random variables A and S, have finite rth moment for some r > 2, and letting μ_A (μ_S) denote 1/E[A] (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[(Aμ_A)^r],  E[(Sμ_S)^r], r, and 1/(1-ρ).

In the second part of this thesis, we consider the FCFS GI/GI/n queue in the Halfin-Whitt heavy traffic regime, in the presence of heavy-tailed distributions.  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^(1/2), is tight in the Halfin-Whitt regime. Furthermore, we develop simple and explicit bounds on the stationary queue length in that regime. For the setting where instead the inter-arrival times have an Pareto tail with index 1<α<2, we extend recent results of [Hurvich and Reed, 2016], by proving for general service time distribution, the sequence of stationary queue length distributions, normalized by n^(1/α), is tight (under their scaling, which we refer to as the Halfin-Whitt-Reed scaling regime).

In the third part of this thesis, we further investigate the large deviation behaviors of the limits of the sequence of scaled stationary queue length in the presence of heavy-tailed inter-arrival and/or service times. When service times have a Pareto tail with index 1<α<2 and inter-arrival times have finite second moment, we bound the large deviations behavior of the limiting process and derive a matching lower bound when inter-arrival times are Markovian.  We find that the large deviation behavior of the limit has a sub-exponential decay, differing fundamentally from the exponentially decaying tails known to hold in the light-tailed setting. For the setting where instead the inter-arrival times have a Pareto tail with index 1<α<2, we are again able to bound the large-deviations behavior of the limit, and find that our derived bounds do not depend on the particular service time distribution, and are in fact tight even for the case of deterministic service times.