Mixing time of Queuing Systems: From Erlang-C to Join-the-Shortest-Queue

Queueing theory has proved to be a successful tool for studying several service systems like analyzing data centers [12]. A popular approach is to study such systems in the steady-state owing to the tractability of analysis. However, these systems rarely operate in a steady state, so the theoretical analysis does not directly translate into real-life performance guarantees. Furthermore, a typical goal in the performance analysis of service systems is to understand queue length/waiting time behavior. However, it is not possible to obtain the exact queue length distribution except in special cases such as the M/M/1 queue [15]. So typically, one uses the steady-state behavior as a proxy for the finite-time behavior. However, this approximation is useful only when the system mixes quickly, i.e. approaches the steady-state behavior quickly. These discrepancies motivate us to analyze the rate of convergence to the steady state. Such a result allows one to better understand the applicability of the steady-state results. Moreover, sometimes it is not even possible to obtain the close form steady-state distribution of the system in many queuing systems, and therefore one results to asymptotic analysis such as heavy traffic analysis [8]. Recent works have characterized the rate of convergence in these regimes, thus obtaining a handle on the pre-asymptotic queue length behavior [9, 2]. Since these approximation errors are larger when one is further away from the asymptotic regime, and therefore one has a better handle on the stationary distribution when one is closer to the asymptotic regime. However, prior works suggest that the queuing systems mix slower as one gets closer to the asymptotic regimes, for example, in the Heavy Traffic regime [14, 15]. And so, it is important to characterize the goodness of the steady-state analysis and asymptotic analysis to the finite-time queue length behavior. Therefore, our objective is to establish the finite-time convergence to stationarity bounds of queuing systems, particularly the Join-the-Shortest-Queue policy.