On the impact of job size variability on heterogeneity-aware load balancing

Load balancing is one of the key components in many distributed systems as it heavily impacts performance and resource utilization. We consider a heterogeneous system where each server belongs to one of K classes and the speed of the server depends on its class. Two types of load balancing strategies are considered: arriving jobs are either immediately dispatched to a server class in a randomized manner, i.e., with probability $$p_k$$ p k a job is assigned to class k, or are dispatched based on their size, i.e., jobs with a size in $$[T_{k-1},T_k)$$ [ T k - 1 , T k ) are assigned to class k. Within each class a power of d choices rule is used to select the server that executes the job. For large systems and exponential job size durations the optimal probabilities $$p_k$$ p k to minimize the mean response time can be determined easily via convex optimization. In this paper we develop a mean field model (validated by simulation) to investigate how the optimal probabilities $$p_k$$ p k are affected by the higher moments and in particular by the variability of the job size distribution when the service discipline at each server is first-come-first-served. In addition, we make use of the cavity method to study the optimal thresholds $$T_k$$ T k in case the dispatching is based on the job size.