Take Action

Home | Faculty & Research Overview | Research

Research Details

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.


Working Paper


Prakirt Raj Jhunjhunwala, Daniela Hurtado Lange, Siva Theja Maguluri

Date Published



Jhunjhunwala, Prakirt Raj, Daniela Hurtado Lange, and Siva Theja Maguluri. 2024. Exponential Tail Bounds on Queues: A Confluence of Non-Asymptotic Heavy Traffic and Large Deviations.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more