Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

Daniela Hurtado-Lange*, Siva Theja Maguluri

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.

Original languageEnglish (US)
Pages (from-to)616-622
Number of pages7
JournalOperations Research Letters
Volume49
Issue number4
DOIs
StatePublished - Jul 2021

Keywords

  • Heavy-traffic optimality
  • Load balancing
  • Power-of-d choices
  • Throughput optimality

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems'. Together they form a unique fingerprint.

Cite this