26

JUL

2018

Comments are off

Dia 2 de agosto (quinta), 10h, na sala H324-B (bloco H do CT), receberemos o

prof. Sem Borst (Eindhoven University of Technology & Nokia Bell Labs)

O Sem é um consagrado pesquisador na área de

modelagem matemática de sistemas e pesquisa operacional, co-autor de

mais de 25 patentes e 170 artigos científicos, com passagem pela

indústria e academia, tendo recebido o ACM SIGMETRICS Achievement

Award em 2017 (em

https://www.sigmetrics.org/achievementaward-2017.shtml).

—

Palestrante: Sem Borst, Full Professor and Senior Researcher,

Eindhoven University of Technology & Nokia Bell Labs

Título:

Scalable Load Balancing in Networked Systems

Dia/horário/local:

2 de agosto (quinta), 10h, sala H324-B

Resumo:

We will discuss scalable load balancing algorithms, which provide

favorable delay performance in large-scale systems, and yet only

require minimal implementation overhead. Through the initial stages of

the talk we focus on a basic setup – commonly referred to as the

supermarket model – with a single dispatcher and N identical parallel

servers. A popular class of load balancing algorithms are so-called

JSQ(d) policies, where an incoming task is assigned to a server with

the shortest queue among d servers selected uniformly at random. As

the name reflects, this class includes the celebrated

Join-the-Shortest-Queue (JSQ) policy as a special case (d = N), which

has strong stochastic optimality properties.

In order to explore the fundamental trade-off between delay

performance and implementation overhead, we consider an asymptotic

regime where the total arrival rate and number of servers N grow large

in proportion and the diversity parameter d(N) depends on N. We show

that the fluid limit and the diffusion limit correspond to those for

the ordinary JSQ policy when d(N) tends to infinity and d(N) /

(sqrt(N) log(N)) tends to infinity, respectively, as the number of

servers N grows large. Thus, the optimality of the JSQ policy can be

retained at fluid level and diffusion level while reducing the amount

of communication overhead by nearly a factor N and sqrt(N) / log(N),

respectively. In addition, we analyze load balancing mechanisms which

leverage memory at the dispatcher in order to reduce the amount of

communication overhead further while maintaining low delay.

Bio resumida:

Sem Borst has been a professor in Stochastic Operations Research at

Eindhoven University of Technology since 1998. He also has a part-time

position with Nokia Bell Labs in Murray Hill, NJ, USA. His main

research areas are performance evaluation and resource allocation for

stochastic systems, in particular computer-communication networks. He

has published over 170 refereed papers and holds 28 patents in various

areas. Sem serves or has served on the editorial boards of several

journals, such as ACM Transactions on Modeling and Performance

Evaluation of Computing Systems, IEEE/ACM Transactions on Networking,

Mathematical Methods of Operations Research, Performance Evaluation,

Queueing Systems and Wireless Networks. He was recipient of the

best-paper awards at ACM SIGMETRICS/Performance 1992 and Infocom 2003,

the 1994 Gijs de Leve Prize, the 2001 Yosef Levy Prize, the 2005 Van

Dantzig Prize, and the 2017 ACM SIGMETRICS Achievement Award.