Quantifying Unfairness in Web Server Scheduling

This paper uses trace-driven simulation to study the unfairness properties of Web server scheduling strategies, such as Processor Sharing (PS) and Shortest Remaining Processing Time (SRPT). We use a general-purpose probe-based sampling approach to estimate the mean and variance of the job response time for different job sizes, for arbitrary arrival processes and service time distributions. The results illustrate two different aspects of unfairness called endogenous unfairness and exogenous unfairness. We quantify each, focusing on the mean and variance of slowdown conditioned on job size, for a range of system loads. Our work confirms recent theoretical results regarding the asymptotic convergence of scheduling policies with respect to slowdown, and illustrates typical performance results for a practical range of job sizes in an empirical workload. Finally, we show the sensitivities of SRPT and PS scheduling to selected characteristics of the arrival process and job size distribution