Gaussian Fluctuations for a Large Queuing Network
with Selection of the Shortest of Several Queues




Graham, Carl (Paris, France)
carl@cmapx.polytechnique.fr

We study a network introduced by Vvedenskaya, Dobrushin, and Karpelevich. Tasks on arrival are allocated a fixed number of queues and join the shortest one. We let the size of the network go to infinity. Previous results were laws of large numbers, in transient regimes and in equilibrium, showing in particular in the limit a super-exponential behavior of the tail probabilities. Here we give a rate of convergence by proving a functional central limit theorem, in transient regimes and in equilibrium. An important intermediate step is a spectral gap estimate.