Correlated arrival processes in Internet servers is routinely observed via measurements. In this talk, we focus on multi-tiered systems with correlation in their arrival and/or service processes and on the impact of autocorrelation on system performance. We consider (a) systems with finite buffers (e.g., systems with admission control that effectively operate as closed systems ) and (b) systems with infinite buffers (i.e., systems that operate as open systems). We present experimental measurements and analytic models that show how autocorrelation in the arrival/service process propagates into the system and affects end-to-end performance.
For the case of finite buffer systems, we use measurements from a 3-tier e-commerce server under the TPC-W workload and show the presence and propagation of autocorrelated flows in {\em all} tiers of the system, despite the fact that the stochastic processes used to generate this session-based workload are independent. We attribute this effect to the existence of autocorrelation in the service process of one of the tiers. In contrast to systems with independent flows, autocorrelation in the service process may result in very high user system response times despite the fact that bottleneck resources are not highly utilized, and measured throughput and device utilization levels are modest. This, falsely indicates that the system can sustain higher capacities. We present a small queuing network that help us understand the above counter-intuitive behavior.
For the system with infinite buffer size, with performs as an open system, we present an analytic model that approximates the departure process of a BMAP/MAP/1 queue that admits batch correlated flows, and whose service time process may be also autocorrelated. A BMAP/MAP/1 queue can be considered as a basic building block of an analytic model of a multi-tiered system. This analytic model can be used to model each tier in isolation and to understand how autocorrelation can affect performance in multi-tiered systems with infinite buffers. We present results of the effectiveness of this approximation and conclude by comparing the performance effects of autocorrelation in multi-tired systems with finite and infinite buffers.