Finite Time Convergence to Stationarity of M/M/N Queues: A Lyapunov-Poincaré Approach

Service systems like data centers and ride-hailing are popularly modeled as queueing systems in the literature. Such systems are primarily studied in the steady state due to its analytical traceability. However, almost all applications in real life do not operate in a steady state, and so, there is a clear discrepancy in translating theoretical queueing results to practical applications. To this end, we provide a finite time convergence for a simple M/M/n queue, providing a stepping stone toward understanding the transient behavior of more general queueing systems. M/M/n queue exhibits a phase-transition at the so-called Halfin-Whitt regime. We obtain a tight characterization of the finite time queue length distribution in the super-Halfin-Whitt regime, all the way until the phase transition at Halfin-Whitt. We also obtain a finite-time bound for the distance to stationarity for the sub-Halfin-Whitt regime as well, along with other finite-time statistics such as mean queue length and tail bound.

To prove such a result, we employ the Lyapunov-Poincaré approach, where we first carefully design a Lyapunov function to obtain a negative drift outside a bounded set. Within the bounded set, we get a handle on the behavior using a local version of the canonical path method to obtain a local Poincaré inequality. A key aspect of our methodological contribution is in obtaining tight guarantees in these two regions, which when combined give us tight mixing time bounds. Moreover, our approach has the potential to be generalized to other settings beyond M/M/n systems.