Analysis and Control of Correlated Web Server Queues

The research literature is rich with studies that demonstrate various degrees of correlation in the arrival processes found in Web server environments. All of these previous studies either have assumed the arrival process of each Web server to be independent of the corresponding service process or have completely ignored this important issue. Using data from commercial Web servers, we demonstrate the existence of considerable dependencies between arrival times and service times, in addition to a strong dependence structure within the arrival process, and then we explore a likely causal model of this cross correlation. A mathematical approximation of Web server performance is derived, based on heavy-traffic stochastic-process limits, that captures both the correlations within the arrival process and the correlations between the arrival and service processes. We then demonstrate that the results from our approximation, which is asymptotically exact, are in very good agreement with simulation results across all traffic intensities. Our mathematical analysis is further exploited to revisit certain scheduling issues in Web server environments. In particular, we consider a scheduling approach that provides expected response times relatively close to those under the optimal shortest remaining processing time policy while also maintaining better variance properties.