Dynamic load balancing with tokens

Céline Comte (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Efficiently exploiting the resources of data centers is a complex task that requires efficient and reliable load balancing and resource allocation algorithms. The former are in charge of assigning jobs to servers upon their arrival in the system, while the latter are responsible for sharing the server resources between their assigned jobs. These algorithms should adapt to various constraints, such as data locality, that restrict the feasible job assignments. In this paper, we propose a token-based algorithm that efficiently balances the load between the servers without requiring any knowledge on the job arrival rates and the server capacities. Assuming a balanced fair sharing of the server resources, we show that the resulting dynamic load balancing is insensitive to the job size distribution. Its performance is compared to that obtained under the best static load balancing and in an ideal system that would constantly optimize the resource utilization. We also make the connection with other token-based algorithms such as Join-Idle-Queue.

Original languageEnglish
Pages (from-to)76-88
Number of pages13
JournalComputer Communications
Volume144
DOIs
Publication statusPublished - 15 Aug 2019
Externally publishedYes

Keywords

  • Insensitivity
  • Load balancing
  • Order-independent queues
  • Whittle networks

Fingerprint Dive into the research topics of 'Dynamic load balancing with tokens'. Together they form a unique fingerprint.

  • Cite this