Speaker: Professor Kristen Gardner, Amherst College
Title: Scalable Load Balancing for Heterogeneous Systems
Abstract: Heterogeneity is becoming increasingly ubiquitous in modern largescale computer systems. Developing good load balancing policies for systems whose resources have varying speeds and capabilities is crucial in achieving low response times for jobs using these systems. Indeed, how best to dispatch jobs to servers is a classical and well-studied problem in the queueing literature. Yet nearly all existing work on large-scale systems assumes that the servers are homogeneous; unfortunately, policies that perform well in the homogeneous setting can cause unacceptably poor performance—or even instability—in heterogeneous systems. We propose novel policies in two settings. First, in the case where the dispatcher knows all server speeds, we design new, heterogeneity-aware versions of the “power-of-d-choices” Join the Idle Queue and Join the Shortest Queue policies. Unlike their heterogeneity-unaware counterparts, our policies use server speed information both when choosing which servers to query and when deciding where (among the queried servers) to dispatch jobs. Both of our policies are analytically tractable; our mean response time analyses are exact as the number of servers approaches infinity, under standard assumptions. Furthermore, our policies outperform well-known dispatching rules including the heterogeneity-aware Shortest Expected Delay policy. Second, in the case where the dispatcher has no information about server speeds, we introduce the Accomplishment Sampling heuristic, which enables the dispatcher to accurately identify fast servers and favor those servers when making dispatching decisions.
Bio: Kristy Gardner is an Assistant Professor in the Computer Science Department at Amherst College. Her research focuses on performance modeling and queueing theory; she is particularly interested in dispatching in large-scale systems. She received her PhD and MS in Computer Science from Carnegie Mellon University in 2017 and 2015 respectively, and her BA in Computer Science from Amherst College in 2012.