Why Segregating Short Jobs from Long Jobs under High Variability is Not Always a Win

This paper investigates the performance of task assignment policies for server farms as the variability of job sizes (service demands) approaches infinity. The Size-Interval-Task-Assignment policy (SITA), which separates short jobs from long jobs, has long been viewed as the panacea for dealing with high-variability job-size distributions. A very recent paper showed that this common wisdom is flawed: SITA can actually be inferior to the much simpler greedy policy, Least-Work-Left (LWL), for certain common job-size distributions, including many modal, hyperexponential, and Pareto distributions. The above finding leads one to question whether providing isolation for short jobs from long ones is inherently bad, or whether it is just SITA's strict isolation of short jobs that sometimes leads to poor performance. To answer this question, we consider a much more flexible policy, which we call "Cycle-Stealing" (CS). The CS policy is very similar to LWL, in that short jobs can go to any queue, but it still provides short jobs isolation from longs (one server is reserved for short jobs). While CS has many of the same properties as LWL, including high utilization of both servers, we prove, surprisingly, that, for high variability job sizes, CS performs poorly whenever SITA performs poorly. This result suggests that the notion of isolating short jobs from long jobs, under high variability workloads, is sometimes simply not the right thing to do