Scalable load balancing in networked systems: universality properties and stochastic coupling methods

Research output: Contribution to conferencePaperAcademic

23 Downloads (Pure)

Abstract

We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of N single-server queues.
A popular class of load balancing algorithms are so-called power-of-d or JSQ(d) policies, where an incoming task is assigned to a server with the shortest queue among d servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case (d=N), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as N grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy (d=1) does not entail any communication overhead, but the mean waiting time remains constant as N grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where d(N) depends on N. We investigate what growth rate of d(N) is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to the exact growth rate of d(N), as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher.
Original languageEnglish
Number of pages22
Publication statusPublished - Jan 2018
EventInternational congress of mathematicians (ICM 2018) - Rio de Janeiro, Brazil
Duration: 1 Aug 20189 Aug 2018

Conference

ConferenceInternational congress of mathematicians (ICM 2018)
CountryBrazil
CityRio de Janeiro
Period1/08/189/08/18

Fingerprint

Resource allocation
Servers
Communication
Large scale systems
Data storage equipment
Fluids

Cite this

van der Boor, M., Borst, S., van Leeuwaarden, J., & Mukherjee, D. (2018). Scalable load balancing in networked systems: universality properties and stochastic coupling methods. Paper presented at International congress of mathematicians (ICM 2018), Rio de Janeiro, Brazil.
van der Boor, Mark ; Borst, Sem ; van Leeuwaarden, Johan ; Mukherjee, D. / Scalable load balancing in networked systems : universality properties and stochastic coupling methods. Paper presented at International congress of mathematicians (ICM 2018), Rio de Janeiro, Brazil.22 p.
@conference{137934948575491b90a02890cce0d654,
title = "Scalable load balancing in networked systems: universality properties and stochastic coupling methods",
abstract = "We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of N single-server queues. A popular class of load balancing algorithms are so-called power-of-d or JSQ(d) policies, where an incoming task is assigned to a server with the shortest queue among d servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case (d=N), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as N grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy (d=1) does not entail any communication overhead, but the mean waiting time remains constant as N grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where d(N) depends on N. We investigate what growth rate of d(N) is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to the exact growth rate of d(N), as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher.",
author = "{van der Boor}, Mark and Sem Borst and {van Leeuwaarden}, Johan and D. Mukherjee",
year = "2018",
month = "1",
language = "English",
note = "International congress of mathematicians (ICM 2018) ; Conference date: 01-08-2018 Through 09-08-2018",

}

van der Boor, M, Borst, S, van Leeuwaarden, J & Mukherjee, D 2018, 'Scalable load balancing in networked systems: universality properties and stochastic coupling methods' Paper presented at International congress of mathematicians (ICM 2018), Rio de Janeiro, Brazil, 1/08/18 - 9/08/18, .

Scalable load balancing in networked systems : universality properties and stochastic coupling methods. / van der Boor, Mark; Borst, Sem; van Leeuwaarden, Johan; Mukherjee, D.

2018. Paper presented at International congress of mathematicians (ICM 2018), Rio de Janeiro, Brazil.

Research output: Contribution to conferencePaperAcademic

TY - CONF

T1 - Scalable load balancing in networked systems

T2 - universality properties and stochastic coupling methods

AU - van der Boor, Mark

AU - Borst, Sem

AU - van Leeuwaarden, Johan

AU - Mukherjee, D.

PY - 2018/1

Y1 - 2018/1

N2 - We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of N single-server queues. A popular class of load balancing algorithms are so-called power-of-d or JSQ(d) policies, where an incoming task is assigned to a server with the shortest queue among d servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case (d=N), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as N grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy (d=1) does not entail any communication overhead, but the mean waiting time remains constant as N grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where d(N) depends on N. We investigate what growth rate of d(N) is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to the exact growth rate of d(N), as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher.

AB - We present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of N single-server queues. A popular class of load balancing algorithms are so-called power-of-d or JSQ(d) policies, where an incoming task is assigned to a server with the shortest queue among d servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case (d=N), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as N grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy (d=1) does not entail any communication overhead, but the mean waiting time remains constant as N grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where d(N) depends on N. We investigate what growth rate of d(N) is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to the exact growth rate of d(N), as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher.

M3 - Paper

ER -

van der Boor M, Borst S, van Leeuwaarden J, Mukherjee D. Scalable load balancing in networked systems: universality properties and stochastic coupling methods. 2018. Paper presented at International congress of mathematicians (ICM 2018), Rio de Janeiro, Brazil.