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 Pasini
2012
5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/330781
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact