Ciclo de Seminários

Scalable Load Balancing in Networked Systems
Sem Borst, Full Professor and Senior Researcher, Eindhoven University of Technology & Nokia Bell Labs
2 de agosto (quinta), 10h, sala H324-B

Cartaz - Resumo - Slides

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.

A key facet of the supermarket model is that any task can be handled equally efficiently by any server, which provides analytical tractability but does not cover situations where the processing speeds of a specific task at the various servers may be different. These scenarios may arise due to data locality, task-server affinity relations, or broader compatibility constraints. In order to capture such heterogeneity features, we broaden the attention to network scenarios where the various servers are interconnected by some underlying graph topology G_N. Tasks arrive with rate lambda at each of the N servers, and each task is assigned to the server with the shortest queue among the one where it appears and its neighbors in the graph G_N. We establish conditions - in terms of the average degree and structure of the graph G_N - for the fluid-scaled and diffusion-scaled occupancy processes to be equivalent to those for the case of a clique. The results demonstrate that the optimality of a clique can be asymptotically achieved with far fewer connections, provided the graph topology G_N is suitably random.

Note: Based on joint work with Mark van der Boor, Johan van Leeuwaarden, Debankur Mukherjee and Phil Whiting.

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