Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.17677 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917506308898816 |
|---|---|
| author | Banerjee, Sayan Budhiraja, Amarjit Loeser, Eva |
| author_facet | Banerjee, Sayan Budhiraja, Amarjit Loeser, Eva |
| contents | We study $n$ parallel queues in an extreme heavy-traffic regime: each server works at rate $n$, while jobs arrive to a dispatcher at rate $n^2-(a-b)\sqrt{n}$, with fixed $a>b>0$. Arrivals are routed by a marginal join-the-shortest-queue policy: a small stream of rate $b\sqrt{n}$ joins the current shortest queue, while the remaining stream of rate $n^2-a\sqrt{n}$ is routed uniformly at random. This policy greatly reduces communication cost relative to full JSQ, while improving load balancing and offering a natural mechanism for premium jobs to join shorter queues.
Under diffusive scaling, we prove limit theorems for the ranked queue lengths and associated gap process. The limit is an infinite-dimensional reflected Atlas process, with reflection at the origin and rank-based drift acting on the lowest particle. Its dynamics depend only on $b$, the shortest-queue arrival rate, while $a$ enters through the choice of invariant distribution. We prove well-posedness of this reflected infinite Atlas model and characterize a one-parameter family of product-form stationary gap distributions, parametrized by $a$ and $b$.
To connect the diffusion limit with the stationary behavior of the queueing system, we introduce a related "system with pauses'' that agrees with the original dynamics at diffusion scale but admits an exact open Jackson network representation. This yields explicit finite-$n$ stationary gap distributions, whose heavy-traffic limits select the corresponding product-form invariant laws of the infinite reflected Atlas process. As consequences, we obtain sharp asymptotics for the lowest-ranked queues, system imbalance, and average queue length, quantifying the tradeoff between communication cost and load-balancing performance relative to random routing and full join-the-shortest-queue policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17677 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rank Based Routing in Large Server Systems under Extreme Congestion Banerjee, Sayan Budhiraja, Amarjit Loeser, Eva Probability We study $n$ parallel queues in an extreme heavy-traffic regime: each server works at rate $n$, while jobs arrive to a dispatcher at rate $n^2-(a-b)\sqrt{n}$, with fixed $a>b>0$. Arrivals are routed by a marginal join-the-shortest-queue policy: a small stream of rate $b\sqrt{n}$ joins the current shortest queue, while the remaining stream of rate $n^2-a\sqrt{n}$ is routed uniformly at random. This policy greatly reduces communication cost relative to full JSQ, while improving load balancing and offering a natural mechanism for premium jobs to join shorter queues. Under diffusive scaling, we prove limit theorems for the ranked queue lengths and associated gap process. The limit is an infinite-dimensional reflected Atlas process, with reflection at the origin and rank-based drift acting on the lowest particle. Its dynamics depend only on $b$, the shortest-queue arrival rate, while $a$ enters through the choice of invariant distribution. We prove well-posedness of this reflected infinite Atlas model and characterize a one-parameter family of product-form stationary gap distributions, parametrized by $a$ and $b$. To connect the diffusion limit with the stationary behavior of the queueing system, we introduce a related "system with pauses'' that agrees with the original dynamics at diffusion scale but admits an exact open Jackson network representation. This yields explicit finite-$n$ stationary gap distributions, whose heavy-traffic limits select the corresponding product-form invariant laws of the infinite reflected Atlas process. As consequences, we obtain sharp asymptotics for the lowest-ranked queues, system imbalance, and average queue length, quantifying the tradeoff between communication cost and load-balancing performance relative to random routing and full join-the-shortest-queue policies. |
| title | Rank Based Routing in Large Server Systems under Extreme Congestion |
| topic | Probability |
| url | https://arxiv.org/abs/2605.17677 |