Load balancing in large-scale systems with multiple dispatchers

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
2 Downloads (Pure)

Abstract

Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-$d$ policies. Specifically, JIQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit.
The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck.

Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.
Original languageEnglish
Title of host publication36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages1-9
ISBN (Electronic)978-1-5090-5336-0
ISBN (Print)978-1-5090-5337-7
DOIs
Publication statusPublished - 5 Oct 2017
Event36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, GA, USA - Atlanta, United States
Duration: 1 May 20174 May 2017
http://infocom2017.ieee-infocom.org/

Conference

Conference36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, GA, USA
Abbreviated titleINFOCOM2017
CountryUnited States
CityAtlanta
Period1/05/174/05/17
Internet address

Fingerprint

Resource allocation
Large scale systems
Servers
Fluids
Experiments

Cite this

van der Boor, M., Borst, S. C., & van Leeuwaarden, J. S. H. (2017). Load balancing in large-scale systems with multiple dispatchers. In 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia (pp. 1-9). Piscataway: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/INFOCOM.2017.8057012
van der Boor, M. ; Borst, S.C. ; van Leeuwaarden, J.S.H. / Load balancing in large-scale systems with multiple dispatchers. 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia. Piscataway : Institute of Electrical and Electronics Engineers, 2017. pp. 1-9
@inproceedings{4f04a5e3b2604c10946573ef5fca1641,
title = "Load balancing in large-scale systems with multiple dispatchers",
abstract = "Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-$d$ policies. Specifically, JIQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit.The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck.Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.",
author = "{van der Boor}, M. and S.C. Borst and {van Leeuwaarden}, J.S.H.",
year = "2017",
month = "10",
day = "5",
doi = "10.1109/INFOCOM.2017.8057012",
language = "English",
isbn = "978-1-5090-5337-7",
pages = "1--9",
booktitle = "36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia",
publisher = "Institute of Electrical and Electronics Engineers",
address = "United States",

}

van der Boor, M, Borst, SC & van Leeuwaarden, JSH 2017, Load balancing in large-scale systems with multiple dispatchers. in 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia. Institute of Electrical and Electronics Engineers, Piscataway, pp. 1-9, 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, GA, USA, Atlanta, United States, 1/05/17. https://doi.org/10.1109/INFOCOM.2017.8057012

Load balancing in large-scale systems with multiple dispatchers. / van der Boor, M.; Borst, S.C.; van Leeuwaarden, J.S.H.

36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia. Piscataway : Institute of Electrical and Electronics Engineers, 2017. p. 1-9.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Load balancing in large-scale systems with multiple dispatchers

AU - van der Boor, M.

AU - Borst, S.C.

AU - van Leeuwaarden, J.S.H.

PY - 2017/10/5

Y1 - 2017/10/5

N2 - Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-$d$ policies. Specifically, JIQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit.The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck.Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.

AB - Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-$d$ policies. Specifically, JIQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit.The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck.Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.

U2 - 10.1109/INFOCOM.2017.8057012

DO - 10.1109/INFOCOM.2017.8057012

M3 - Conference contribution

SN - 978-1-5090-5337-7

SP - 1

EP - 9

BT - 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

ER -

van der Boor M, Borst SC, van Leeuwaarden JSH. Load balancing in large-scale systems with multiple dispatchers. In 36th IEEE International Conference on Computer Communications (INFOCOM2017), 1-4 May 2017, Atlanta, Georgia. Piscataway: Institute of Electrical and Electronics Engineers. 2017. p. 1-9 https://doi.org/10.1109/INFOCOM.2017.8057012