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.
Evgenia Smirni is the William and Martha Claiborne Stephens Associate Professor at the College of William and Mary, Department of Computer Science, Williamsburg, Virginia 23187-8795 (esmirni@cs.wm.edu). She received her Diploma in Computer Engineering and Informatics from the University of Patras, Greece, in 1987, and her M.S. and Ph.D. in Computer Science from Vanderbilt University in 1993 and 1995, respectively. From August 1995 to June 1997 she had a postdoctoral research associate position at the University of Illinois at Urbana-Champaign. Her research interests include analytic modeling, stochastic models, Markov chains, matrix analytic methods, resource allocation policies, Internet systems, workload characterization, and modeling of distributed systems and applications. She has served as program co-chair of QEST'05 and of ACM SIGMETRICS/Performance'06. She is a member of ACM and IEEE.
