DIMACS TR: 2002-41

Deferred Assignment Scheduling in Clustered Web Servers

Authors: Victoria Ungureanu, Phillip G. Bradford, Michael Katehakis and Benjamin Melamed.


This paper proposes new scheduling policies for clustered servers, which are based on job size. The proposed algorithms are shown to be efficient, simple and easy to implement. They differ from traditional methods in the way jobs are assigned to back-end servers. The main idea is to defer scheduling as much as possible in order to make better use of the accumulated information on job sizes. Furthermore, the proposed algorithms are designed to work effectively with the class of job-size distributions often encountered on the Internet. To gauge the efficacy of the proposed algorithms, the paper presents an empirical case study that shows these algorithms perform well on input from real-life trace data measured at Internet clustered servers.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-41.ps.gz
DIMACS Home Page