Asymptotically optimal open-loop load balancing

Jonatha Anselmi 1
1 CQFD - Quality control and dynamic reliability
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : In many distributed computing systems, stochastically arriving jobs need to be assigned to servers with the objective of minimizing waiting times. Many existing dispatching algorithms are basically included in the SQ(d) framework: Upon arrival of a job, d≥2 servers are contacted uniformly at random to retrieve their state and then the job is routed to a server in the best observed state. One practical issue in this type of algorithm is that server states may not be observable, depending on the underlying architecture. In this paper, we investigate the assignment problem in the open-loop setting where no feedback information can flow dynamically from the queues back to the controller, i.e., the queues are unobservable. This is an intractable problem, and unless particular cases are considered, the structure of an optimal policy is not known. Under mild assumptions and in a heavy-traffic many-server limiting regime, our main result proves the optimality of a subset of deterministic and periodic policies within a wide set of (open-loop) policies that can be randomized or deterministic and can be dependent on the arrival process at the controller. The limiting value of the scaled stationary mean waiting time achieved by any policy in our subset provides a simple approximation for the optimal system performance.
Type de document :
Article dans une revue
Queueing Systems, Springer Verlag, 2017, pp.1-23. 〈10.1007/s11134-017-9547-9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01614892
Contributeur : Jonatha Anselmi <>
Soumis le : mercredi 11 octobre 2017 - 15:32:51
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

Collections

Citation

Jonatha Anselmi. Asymptotically optimal open-loop load balancing. Queueing Systems, Springer Verlag, 2017, pp.1-23. 〈10.1007/s11134-017-9547-9〉. 〈hal-01614892〉

Partager

Métriques

Consultations de la notice

76