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

Daniela Hurtado-Lange; Siva Theja Maguluri

doi:10.1016/j.orl.2021.06.010

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

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

5 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 language	English (US)
Pages (from-to)	616-622
Number of pages	7
Journal	Operations Research Letters
Volume	49
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2021.06.010
State	Published - Jul 2021

Funding

This work was partially supported by the National Science Foundation [NSF-CCF: 1850439 ]. Daniela Hurtado-Lange has partial funding from ANID/DOCTORADO BECAS CHILE/2018 [ 72190413 ]

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

Access to Document

10.1016/j.orl.2021.06.010

Cite this

@article{2ac4b6b37e7e442b97e3ea25ff2995a1,

title = "Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems",

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.",

keywords = "Heavy-traffic optimality, Load balancing, Power-of-d choices, Throughput optimality",

author = "Daniela Hurtado-Lange and Maguluri, {Siva Theja}",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = jul,

doi = "10.1016/j.orl.2021.06.010",

language = "English (US)",

volume = "49",

pages = "616--622",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

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

AU - Hurtado-Lange, Daniela

AU - Maguluri, Siva Theja

PY - 2021/7

Y1 - 2021/7

N2 - 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.

AB - 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.

KW - Heavy-traffic optimality

KW - Load balancing

KW - Power-of-d choices

KW - Throughput optimality

UR - http://www.scopus.com/inward/record.url?scp=85108888353&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108888353&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2021.06.010

DO - 10.1016/j.orl.2021.06.010

M3 - Article

AN - SCOPUS:85108888353

SN - 0167-6377

VL - 49

SP - 616

EP - 622

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

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

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this