In this paper the authors study the dynamic randomized load balancing model, which is often referred to as the supermarket model. Specifically, they study two load balancing policies for the supermarket model. In each case, jobs arrive at the bank of N servers according to a rate αN Poisson process, with α < 1. The servers each employ the same service discipline and the service times are iid with a given arbitrary distribution F(·) having mean 1. Service at each queue is assumed to be non-idling. The Join the Shortest Queue policy SQ(D) assigns each arrival to the shortest of D queues chosen independently and uniformly at random, where the shortest queue means the queue with the least number of jobs. With the Join the Last Loaded Queue policy LL(D) the arrival is instead assigned to the queue with the smallest amount of remaining work, or workload. In both cases, the D queues are chosen without replacement, from among the CN,D possible sets. Ties are assumed to be broken randomly, with the arriving job being assigned with equal probability to each of the queues. In this context the authors define an approach to analyze the limiting behavior of the equilibrium distribution, at a given queue, as N →∞, formulating a general statement (an ansatz). They consider several settings under which they are able to prove this ansatz and they state and prove three theorems that correspond to those settings. Leonardo Pasini
Matematica Review atout: (Bramson, Maury ; Lu, Yi ; Prabhakar, Balaji - "Asymptotic independence of queues under randomized load bilancing"- Queueing Syst. 71 (2012), no.3, 247–292.)
PASINI, Leonardo
2012-01-01
Abstract
In this paper the authors study the dynamic randomized load balancing model, which is often referred to as the supermarket model. Specifically, they study two load balancing policies for the supermarket model. In each case, jobs arrive at the bank of N servers according to a rate αN Poisson process, with α < 1. The servers each employ the same service discipline and the service times are iid with a given arbitrary distribution F(·) having mean 1. Service at each queue is assumed to be non-idling. The Join the Shortest Queue policy SQ(D) assigns each arrival to the shortest of D queues chosen independently and uniformly at random, where the shortest queue means the queue with the least number of jobs. With the Join the Last Loaded Queue policy LL(D) the arrival is instead assigned to the queue with the smallest amount of remaining work, or workload. In both cases, the D queues are chosen without replacement, from among the CN,D possible sets. Ties are assumed to be broken randomly, with the arriving job being assigned with equal probability to each of the queues. In this context the authors define an approach to analyze the limiting behavior of the equilibrium distribution, at a given queue, as N →∞, formulating a general statement (an ansatz). They consider several settings under which they are able to prove this ansatz and they state and prove three theorems that correspond to those settings. Leonardo PasiniI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
