Analysis of Scheduling Policies under Correlated Job Sizes (CMU-CS-10-107)

Correlations in traffic patterns are an important facet of the workloads faced by real systems, and one that has far-reaching consequences on the performance and optimization of the systems involved. While there has been considerable amount of work on understanding the effect of correlations between successive interarrival times, there is very little analytical work in understanding the effect of correlations between successive service requirements (job sizes). All the prior work on analyzing the effects of correlated job sizes is limited to First-Come-First-Served scheduling. This leaves open fundamental questions such as: How do various scheduling policies interact with correlated job sizes? Can scheduling be used to mitigate the harmful effects of correlations? In this paper we take the first step towards answering these questions. We assume a simple and intuitive model for job size correlations and present the first asymptotic analysis of various common size-independent scheduling policies when the job size sequence exhibits high correlation. Our analysis reveals that the characteristics of various scheduling policies, as well as their performance relative to each other, are markedly different under the assumption of i.i.d. job sizes versus correlated job sizes. Further, among the class of size-independent scheduling policies, there is no single scheduling policy that is optimal for all degrees of correlations and thus any optimal policy must learn the correlations. We support the asymptotic analysis with numerical algorithms for exact performance analysis under an arbitrary degree of correlation, with simulations, and finally verify the lessons from our correlation model on real world traces.