Scalable Load Balancing in Interference-prone Queueing Systems

We study a dispatching problem in large-scale queueing systems, where each server independently alternates between serving jobs at a fast rate (when the server is functioning normally) and a slow rate (when the server is undergoing performance degradation). This problem arises in cloud computing when dispatching jobs to a large set of virtual machines (VMs) located across a variety of servers. As not all physical resources are easily partitioned across VMs on the same server, VMs frequently experience a temporary and unpredictable, yet detectable, performance degradation known as interference. We address load balancing in interference-prone VMs, where one must immediately dispatch each incoming job to minimize average response times. We propose several distributed dispatching policies that dispatch incoming requests based on the interference and busy status of a randomly sampled subset of the servers under the power-of-d-choices paradigm. Using mean-field analysis and the Recursive Renewal Reward technique, we evaluate the performance of these heuristics exactly in a variety of settings while deducing and proving several surprising results. In particular, we find that while using interference status information for dispatching can reduce the mean response time, using this information naively can be very costly.