Exponential Tail Bounds on Queues: A Confluence of Non-Asymptotic Heavy Traffic and Large Deviations

In general, obtaining the exact steady-state distribution of queue lengths is not feasible. Therefore, we focus on establishing bounds for the tail probabilities of queue lengths. Specifically, we examine queueing systems under Heavy-Traffic (HT) conditions and provide exponentially decaying bounds for the tail probability of scaled queue length. Our bounds are not limited to asymptotic cases and are applicable even for non-asymptotic HT, and they get sharper as the system approaches HT. Consequently, we derive non-asymptotic convergence rates for the tail probabilities. Furthermore, our results offer bounds on the exponential rate of decay of the tail, which can be interpreted as non-asymptotic versions of Large Deviation (LD) results. We demonstrate our approach by presenting tail bounds for (i) a continuous time Join-the-shortest queue (JSQ) load balancing system, and (ii) a discrete time single-server queue. We not only bridge the gap between classical HT and LD regimes but also explore the large system HT regimes for JSQ. In these regimes, both the system size and the system load increase simultaneously. Our results also close a gap in the existing literature on the limiting distribution of JSQ in the super-NDS (a.k.a. super slowdown) regime, which is a contribution of independent interest.