2020 Markov Lecture

Load Balancing in Networked Systems: Scalable Algorithms and Resource Pooling Issues

Abstract

Load balancing algorithms play a crucial role in distributing service requests in large-scale parallel-resource systems such as data centers and cloud networks. Due to the massive size of these systems, implementation complexity of load balancing algorithms has emerged as a critical concern besides conventional performance metrics such as delay. In the first part of the talk we explore fundamental trade-offs between these two criteria in the baseline scenario of the celebrated supermarket model. We establish asymptotic universality properties for a broad class of randomized algorithms, and discuss some related resource pooling perspectives.

In the second part of the talk we move beyond the supermarket model, and turn to network settings and multi-class systems with compatibility constraints. These scenarios may arise due to heterogeneity issues and network topology and locality constraints which are increasingly common in data centers and cloud environments. We identify conditions in terms of the underlying compatibility graph in order for similar universality properties to hold in a many-server scenario, and leverage product-form distributions for related redundancy models to demonstrate resource pooling a heavy-traffic regime. Strikingly, across a wise range of scenarios, the performance of a fully flexible system can be matched even with quite stringent compatibility constraints.

Note: Based on joint work with Ellen Cardinaels, Johan van Leeuwaarden, Debankur Mukherjee (Georgia Tech) and Phil Whiting (Macquarie)

Bio