Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata
Contributor : Jonatha Anselmi Connect in order to contact the contributor
Submitted on : Wednesday, October 11, 2017 - 3:32:51 PM
Last modification on : Wednesday, November 3, 2021 - 3:59:49 AM




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



Record views