Performance Analysis of Workload Dependent Load Balancing Policies

Abstract

Load balancing plays a crucial role in achieving low latency in large distributed systems. Recent load balancing strategies often rely on replication or use placeholders to further improve latency. However assessing the performance and stability of these strategies is challenging and is therefore mostly simulation based. In this paper we introduce a unified approach to analyze the performance and stability of a broad class of workload dependent load balancing strategies. This class includes many replication policies, such as replicate below threshold, delayed replication and replicate only small jobs, as well as strategies for fork-join systems. We consider systems with general job size distributions where jobs may experience server slowdown. We show that the equilibrium workload distribution of the cavity process satisfies a functional differential equation (FDE) and conjecture that the cavity process captures the limiting behavior of the system as its size tends to infinity. The cavity process method assumes that the workload at the queues is independent and identically distributed. This way, one may focus on the behaviour of one queue, this method was introduced in [1] and is shown to yield exact results for SQ(d) with job size distribution that have a decreasing hazard rate and LL(d) with general job sizes.