Systems with multiple servers under heavy-tailed workloads

Abstract

The heavy-tailed nature of Internet flow sizes, web pages and computer files can cause non-preemptive scheduling policies to have a large average response time. Since there are numerous communication and distributed processing systems where preempting jobs can be quite expensive, reducing response times under this constraint is a pressing issue. One proposal for tackling non-preemption is through the use of multiple servers: classify jobs according to size and assign a server to each class. Unfortunately, in most systems of interest, job sizes are unknown. An alterative is to queue all jobs together in a central-queue and assign them in a FCFS fashion to the next available server. But, this has been believed to yield large response times. In this paper, we argue that this is not the case, so long as there are enough servers. The question then is: what is the right number of servers, and is this small enough to be practical? Despite the large amount of prior work in analyzing the behavior of a central-queue system, no existing models are accurate for the case of heavy-tailed size distributions. Our main contribution is a simple yet accurate model for a central-queue with multiple servers. This model accurately predicts the right number of servers, and the average and variance of the response time of the system. Hence, it can be used to improve the performance of some real systems, such as multi-server supercomputing centers and multi-channel communication systems. © 2005 Elsevier B.V. All rights reserved.