To balance or unbalance load in size-interval task allocation

Mor Harchol-Balter*, Rein Vesilo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

Server farms, consisting of a collection of hosts and a front-end router that dispatches incoming jobs to hosts, are now commonplace. It is well known that when job service requirements (job sizes) are highly variable, then the Size-Interval task assignment policy is an excellent rule for assigning jobs to hosts, since it provides isolation for short jobs by directing short jobs to one host's queue and long jobs to another host's queue. What is not understood is how to classify a short job versus a long job. For a long time it was believed that the size cutoff separating short jobs from long ones should be chosen to balance the load at the hosts in the server farm. However, recent literature has provided empirical evidence that load balancing is not always optimal for minimizing mean response time. This article provides the first analytical criteria for when it is preferable to unbalance load between two hosts using Size-Interval task assignment and in which direction the load should be unbalanced. Some very simple sufficient criteria are provided under which we prove that the short job host should be underloaded, and likewise for the long job host. These criteria are then used to prove that the direction of load imbalance depends on moment index properties related to the job size distribution. For example, under the Bounded Pareto (BP) job size distribution with parameter and a sufficiently high upper bound (the BP is well known to be a good model of empirical computer system workloads), we show that determines the direction of load imbalance. For <1, the short job host should be underloaded; for =1, load should be balanced; and for >1, the long job host should be underloaded. Many other job size distributions are considered as well. We end by showing that load unbalancing can have a dramatic impact on performance, reducing mean response time by an order of magnitude compared to load balancing in many common cases.

Original languageEnglish
Pages (from-to)219-244
Number of pages26
JournalProbability in the Engineering and Informational Sciences
Volume24
Issue number2
DOIs
Publication statusPublished - Apr 2010

Fingerprint Dive into the research topics of 'To balance or unbalance load in size-interval task allocation'. Together they form a unique fingerprint.

Cite this