The Effect of Heavy-Tailed Job Size Distributions on System Design

Mor Harchol-Balter, M.I.T. Laboratory for Computer Science

We consider several common questions in the design of computer systems: What is a good policy for assigning jobs to hosts in a distributed server? In what order should HTTP requests be scheduled within a Web server? What should the migration policy be in a Network of Workstations? For each problem, we show that the answer depends on the job size distribution, and the impact of the job size distribution is very great, affecting answers sometimes by orders of magnitude. We present measurements showing that job size distributions are commonly heavy-tailed. We show how to incorporate heavy-tailed job size distributions into the design of systems. This leads us to discover solutions to the above questions which are novel and effective.