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

Ignace Spilbeeck () and Benny Houdt ()
Additional contact information
Ignace Spilbeeck: University of Antwerp - IMEC
Benny Houdt: University of Antwerp - IMEC

Annals of Operations Research, 2020, vol. 293, issue 1, No 17, 399 pages

Abstract: 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 $$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.

Keywords: Load balancing; Heterogeneous; Randomized; Size interval task assignment (SITA) (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03398-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:293:y:2020:i:1:d:10.1007_s10479-019-03398-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03398-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().