IEOR-DRO Seminar:Itai Gurvich (Cornell)

March 28, 2017 | 1:10pm - 2:20pm

IEOR-DRO Seminar:Itai Gurvich (Cornell)

Uris Hall 333
Title: Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue
 
Abstract: Central-limit (Brownian) approximations are widely used for performance analysis and optimization of queueing networks because of their tractability relative to the original queueing models. Their stationary distributions are used as proxies for those of the queues.
 
The convergence of suitably scaled and centered processes provides mathematical support for the use of these Brownian models. As with the central limit theorem, to establish convergence, one must impose assumptions directly on the primitives or, indirectly, on the parameters of a related optimization problem. These assumptions reflect an interpretation of the underlying parameters---a classification into so-called heavy-traffic regimes that specify a scaling relationship between the utilization and the arrival rate. Different interpretations lead to different limits and, in turn, to different approximations.
 
From a heuristic point of view, though, there is an immediate Brownian (i.e., normal) analogue of the queueing model that is derived directly from the primitives and requires no (limit) interpretation of the parameters. In this model, the drift is that of the original queue and the noise term is, loosely speaking, replaced by a Brownian motion with the same variance. This is intuitive and appealing as a tool, but lacks mathematical justification.
 
In this paper we prove that for the fundamental M/GI/1+GI queue, this direct intuitive (limitless approach) in fact works.
We prove that the Brownian model is accurate uniformly over families of patience distributions and universally in the heavy-traffic regime. The Brownian model maintains the tractability and appeal of the limit approximations while avoiding some of the assumptions that facilitate them.
 
To build mathematical support for the accuracy of this model, we introduce a framework built around ``queue families'' that allows us to treat various patience distributions simultaneously, and uncovers the role of a concentration property of the queue.
 


500 W. 120th St., Mudd 315, New York, NY 10027    212-854-2942                 
©2014 Columbia University