Asymptotic independence of queues under randomized load balancing
Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-?N Poisson process, with ?<1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:1529, 1996), it was shown that when each arriving job is assigned to the shortest of D, D?2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N??. This is a substantial improvement over the case D=1, where queue sizes decay exponentially.
asymptotic independence load balancing join the shortest queue join the least loaded queue 60k25 68m20 90b15