The supermarket model with arrival rate tending to one

Abstract

In the supermarket model, there are $n$ queues, each with a single server. Customers arrive in a Poisson process with arrival rate $\lambda n$, where $\lambda =\lambda (n)\in (0,1)$. Upon arrival, a customer selects $d=d(n)$ servers uniformly at random, and joins the queue of a least-loaded server amongst those chosen. Service times are independent exponentially distributed random variables with mean~1. In this paper, we analyse the behaviour of the supermarket model in a regime where $\lambda (n)$ tends to~1, and $d(n)$ tends to infinity, as $n\to \infty$. For suitable triples $(n,d,\lambda )$, we identify a subset $\mathcal{N}$ of the state space where the process remains for a long time in equilibrium. We further show that the process is rapidly mixing when started in $\mathcal{N}$, and give bounds on the speed of mixing for more general initial conditions.

64 pages

Cited by in corpus (2)

• Economies-of-scale in resource sharing systems: tutorial and partial review of the QED heavy-traffic regime
• Reward Processes and Performance Simulation in Supermarket Models with Different Servers