Asymptotic analysis of load distribution for Size-Interval task allocation with Bounded Pareto job sizes

Rein Vesilo*

*Corresponding author for this work

Research output: Contribution to journalArticle

9 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. When job service requirements (job sizes) are highly variable, the Size-Interval task assignment policy is an excellent rule for assigning jobs to hosts. 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 evidence that load balancing is not always optimal for minimizing mean response time. Previous collaborative work by the author presented simple sufficient criteria for determining which host should be underloaded in a two host system using Size-Interval task assignment. In this paper, we derive asymptotic closed-form expressions for the optimal size cutoff, separating short jobs from large jobs, and the optimal load point at the separation in a two-host system. The asymptotic expressions are for when the maximum job size in a Bounded Pareto distribution approaches infinity and are derived using perturbation analysis. We show that the asymptotics can be one of three forms depending on whether the system load (mean number of busy hosts) is less than 1, equal to 1 or greater than 1 with different mechanisms dominating in each case. Our results allow the effects of both load and tail index to be easily determined. Numerical analysis shows that the asymptotic expressions in most cases are very accurate.

Original languageEnglish
Article number4724312
Pages (from-to)129-137
Number of pages9
JournalProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
DOIs
Publication statusPublished - 2008

Keywords

  • Asymptotics
  • Bounded Pareto
  • Scheduling
  • Size-Interval
  • Task allocation

Fingerprint Dive into the research topics of 'Asymptotic analysis of load distribution for Size-Interval task allocation with Bounded Pareto job sizes'. Together they form a unique fingerprint.

  • Cite this