Title: To queue or not to queue?: When FCFS is better than PS in a distributed system

Authors: Mor Harchol-Balter, Mark E. Crovella, and Cristina D. Murta

Date: October 31, 1997

Abstract:

We examine the question of whether to employ the first-come-first-served
(FCFS) discipline or the processor-sharing (PS) discipline at the nodes
in a distributed server system.  We are interested in the case in which
service times are drawn from a heavy-tailed distribution, and so have
very high variability.  Traditional wisdom in such a situation would
prefer the PS discipline, because it allows small tasks to avoid being
delayed behind large tasks in a queue.  However, we show that system
performance can actually be significantly better under FCFS queueing, if
a particular kind of task assignment is used.  By task assignment, we
mean an algorithm that inspects incoming tasks and assigns them to hosts
for service.  The policy we propose is called SITA-E: Size Interval Task
Assignment with Equal Load; it is a static policy that does not
incorporate feedback knowledge of the state of the hosts.  Surprisingly,
under SITA-E, FCFS queueing typically outperforms the PS discipline by a
factor of about two, as measured by mean waiting time and mean slowdown
(waiting time of task divided by its service time).  We analyze the
FCFS/SITA-E policy and compare it to the processor-sharing case; in
addition we compare it in simulation to a number of other policies.  We
show that the benefits of SITA-E are present even in small-scale
distributed systems (four or more hosts), and that SITA-E can in many
cases be more effective than a dynamic policy that takes into account
the current load at each host.  Finally we discuss issues in employing
this policy in distributed Web servers.