Tata Institute of Fundamental Research
Uniform Geometric and Subgeometric Ergodicity for Multiclass Many Server Queues in Heavy Traffic
STCS Seminar
Speaker:
Aristotle Arapostathis (University of Texas
Department of Electrical and
Computer Engineering
Austin, Texas, United States
)
Organiser:
Sandeep K Juneja
Date:
Thursday, 22 Nov 2018, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: We study ergodic properties of multiclass multi-server queues, which are uniform over scheduling policies, as well as the size n of the system. The system is heavily loaded in the Halfin-Whitt regime, and the scheduling policies are work-conserving and preemptive. We provide a unified approach via ‘matching’ Foster-Lyapunov equations for both the limiting diffusion and the prelimit diffusion-scaled queueing processes simultaneously. We first study the limiting controlled diffusion, and we show that if the spare capacity (safety staffing) parameter is positive, then the diffusion is exponentially ergodic uniformly over all stationary Markov controls, and the invariant probability measures have sub-exponential tails. This result is sharp, since when there is no abandonment and the spare capacity parameter is negative, then the controlled diffusion is transient under any Markov control. In addition, we show that if all the abandonment rates are positive, the invariant probability measures have sub-Gaussian tails, regardless whether the spare capacity parameter is positive or negative.
Using the above results, we proceed to establish the corresponding ergodic properties for the diffusion-scaled queueing processes. In addition to providing a simpler proof of the results in Gamarnik and Stolyar [Queueing Syst. (2012) 71:25--51], we extend these results to GI/M/n+M queues with renewal arrival processes, albeit under the assumption that the mean residual life functions are bounded. For the Markovian model with Poisson arrivals, we obtain stronger results and show that the convergence to the stationary distribution is at a geometric rate uniformly over all work-conserving stationary Markov scheduling policies.
We then turn to the case when arrivals are heavy-tailed, or the system suffers from asymptotically negligible service interruptions. In these models, the Itô equations are driven by either (1) a Brownian motion and a pure-jump Levy process, or (2) an anisotropic Levy process with independent one-dimensional symmetric alpha-stable components, or (3) an anisotropic Lévy process and a pure-jump Lévy process. We identify conditions on the parameters in the drift, the Lévy measure and/or covariance function which result in subexponential and/or exponential ergodicity. We show that these assumptions are sharp. In addition, we show that for the queueing models described above with no abandonment, the rate of convergence is polynomial, and we provide a sharp quantitative characterization of this rate via matching upper and lower bounds (joint work with Hassan Hmedi, Guodong Pang and Nikola Sandric).
Bio: Ari Arapostathis is a professor at the Department of Electrical and Computer Engineering at the University of Texas at Austin. His research interests include analysis and estimation techniques for stochastic systems, stability properties of large-scale interconnected power systems, and stochastic and adaptive control theory. His main technical contributions are in the areas of adaptive control and estimation of stochastic systems with partial observations, controlled diffusions, adaptive control of nonlinear systems, geometric nonlinear theory, and stability of large scale interconnected power systems. His research is currently funded by the National Science Foundation (Division of Mathematical Sciences), Army Research Office (Applied Probability), and the Office of Naval Research. He is a Fellow of IEEE.
| Speaker: | Aristotle Arapostathis (University of Texas Department of Electrical and Computer Engineering Austin, Texas, United States ) |
| Organiser: | Sandeep K Juneja |
| Date: | Thursday, 22 Nov 2018, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: We study ergodic properties of multiclass multi-server queues, which are uniform over scheduling policies, as well as the size n of the system. The system is heavily loaded in the Halfin-Whitt regime, and the scheduling policies are work-conserving and preemptive. We provide a unified approach via ‘matching’ Foster-Lyapunov equations for both the limiting diffusion and the prelimit diffusion-scaled queueing processes simultaneously. We first study the limiting controlled diffusion, and we show that if the spare capacity (safety staffing) parameter is positive, then the diffusion is exponentially ergodic uniformly over all stationary Markov controls, and the invariant probability measures have sub-exponential tails. This result is sharp, since when there is no abandonment and the spare capacity parameter is negative, then the controlled diffusion is transient under any Markov control. In addition, we show that if all the abandonment rates are positive, the invariant probability measures have sub-Gaussian tails, regardless whether the spare capacity parameter is positive or negative.
Using the above results, we proceed to establish the corresponding ergodic properties for the diffusion-scaled queueing processes. In addition to providing a simpler proof of the results in Gamarnik and Stolyar [Queueing Syst. (2012) 71:25--51], we extend these results to GI/M/n+M queues with renewal arrival processes, albeit under the assumption that the mean residual life functions are bounded. For the Markovian model with Poisson arrivals, we obtain stronger results and show that the convergence to the stationary distribution is at a geometric rate uniformly over all work-conserving stationary Markov scheduling policies.
We then turn to the case when arrivals are heavy-tailed, or the system suffers from asymptotically negligible service interruptions. In these models, the Itô equations are driven by either (1) a Brownian motion and a pure-jump Levy process, or (2) an anisotropic Levy process with independent one-dimensional symmetric alpha-stable components, or (3) an anisotropic Lévy process and a pure-jump Lévy process. We identify conditions on the parameters in the drift, the Lévy measure and/or covariance function which result in subexponential and/or exponential ergodicity. We show that these assumptions are sharp. In addition, we show that for the queueing models described above with no abandonment, the rate of convergence is polynomial, and we provide a sharp quantitative characterization of this rate via matching upper and lower bounds (joint work with Hassan Hmedi, Guodong Pang and Nikola Sandric).
Bio: Ari Arapostathis is a professor at the Department of Electrical and Computer Engineering at the University of Texas at Austin. His research interests include analysis and estimation techniques for stochastic systems, stability properties of large-scale interconnected power systems, and stochastic and adaptive control theory. His main technical contributions are in the areas of adaptive control and estimation of stochastic systems with partial observations, controlled diffusions, adaptive control of nonlinear systems, geometric nonlinear theory, and stability of large scale interconnected power systems. His research is currently funded by the National Science Foundation (Division of Mathematical Sciences), Army Research Office (Applied Probability), and the Office of Naval Research. He is a Fellow of IEEE.
Using the above results, we proceed to establish the corresponding ergodic properties for the diffusion-scaled queueing processes. In addition to providing a simpler proof of the results in Gamarnik and Stolyar [Queueing Syst. (2012) 71:25--51], we extend these results to GI/M/n+M queues with renewal arrival processes, albeit under the assumption that the mean residual life functions are bounded. For the Markovian model with Poisson arrivals, we obtain stronger results and show that the convergence to the stationary distribution is at a geometric rate uniformly over all work-conserving stationary Markov scheduling policies.
We then turn to the case when arrivals are heavy-tailed, or the system suffers from asymptotically negligible service interruptions. In these models, the Itô equations are driven by either (1) a Brownian motion and a pure-jump Levy process, or (2) an anisotropic Levy process with independent one-dimensional symmetric alpha-stable components, or (3) an anisotropic Lévy process and a pure-jump Lévy process. We identify conditions on the parameters in the drift, the Lévy measure and/or covariance function which result in subexponential and/or exponential ergodicity. We show that these assumptions are sharp. In addition, we show that for the queueing models described above with no abandonment, the rate of convergence is polynomial, and we provide a sharp quantitative characterization of this rate via matching upper and lower bounds (joint work with Hassan Hmedi, Guodong Pang and Nikola Sandric).
Bio: Ari Arapostathis is a professor at the Department of Electrical and Computer Engineering at the University of Texas at Austin. His research interests include analysis and estimation techniques for stochastic systems, stability properties of large-scale interconnected power systems, and stochastic and adaptive control theory. His main technical contributions are in the areas of adaptive control and estimation of stochastic systems with partial observations, controlled diffusions, adaptive control of nonlinear systems, geometric nonlinear theory, and stability of large scale interconnected power systems. His research is currently funded by the National Science Foundation (Division of Mathematical Sciences), Army Research Office (Applied Probability), and the Office of Naval Research. He is a Fellow of IEEE.