On the impact of job size variability on heterogeneity-aware load balancing
- PDF / 2,024,826 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 158 Views
On the impact of job size variability on heterogeneity-aware load balancing Ignace Van Spilbeeck1 · Benny Van Houdt1 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract 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 pk a job is assigned to class k, or are dispatched based on their size, i.e., jobs with a size in [Tk−1 , Tk ) 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 pk 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 pk 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 Tk in case the dispatching is based on the job size. Keywords Load balancing · Heterogeneous · Randomized · Size interval task assignment (SITA)
1 Introduction Consider a large distributed system consisting of N servers and a (number of) centralized dispatchers. Incoming jobs are assigned by the dispatcher(s) to the servers using a load balancing (LB) scheme. A very efficient manner to distribute the incoming jobs among the servers is to rely on a pure randomized assignment scheme or some form of round robin. While this allows very fast load balancing decisions, the resulting performance is known to be inferior to LB schemes that exploit information concerning the current system state, such
B
Benny Van Houdt [email protected] Ignace Van Spilbeeck [email protected]
1
Department of Mathematics and Computer Science, University of Antwerp - IMEC, Middelheimlaan 1, 2020 Antwerp, Belgium
123
Annals of Operations Research
as the queue lengths or server speeds. Examples of the latter include join-the-shortest-queue (JSQ) LB (Gupta et al. 2007) or the power-of-d-choices (POD) LB (Vvedenskaya et al. 1996; Mitzenmacher 2001). Under JSQ incoming jobs are assigned to the server containing the least number of jobs, while under POD d servers are selected uniformly at random and the job is assigned to the server with the shortest queue length among the d selected servers. When the system is heterogeneous, for instance when not all the servers have the same speed, the choice of the LB scheme becomes even more critical as LB schemes based on joining the server with the least number of jobs among a set of randomly selected servers
Data Loading...
