Seminars & Colloquia

Evgenia Smirni

College of William and Mary

"Performance Impacts of Autocorrelation in Systems"

Monday December 04, 2006 10:30 AM
Location: 3211, EB II NCSU Centennial Campus
(Visitor parking instructions)


Abstract: Correlated arrival processes in Internet servers is routinely observed via measurements. In this talk, we focus on 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 that show how autocorrelation in the arrival/service process propagates into the system and affects end-to-end performance. We also illustrate how knowledge of autocorrelation can assist in the development of resource allocation policies.

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 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 helps us understand the above counter-intuitive behavior.

For a system with infinite buffer size, we consider the problem of load balancing in homogeneous cluster environments admitting jobs with high variability in their execution times. Load balancing in such environment has been shown to heavily depend on the policy's ability to direct jobs to servers according to the job size. The effectiveness of such policies is based on separating 'short' from 'long' jobs, by avoiding having short jobs waiting behind long jobs for service. We show that performance improvements due to this separation quickly vanishes if there the job arrival process to the cluster is autocorrelated. Based on this fact, we devise a new size-based policy (i.e., jobs are still directed to different servers according to their size) but all servers are not equally utilized so that the performance loss due to autocorrelated arrival flows is minimized.

Short Bio: 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 ( 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, IEEE, and the Technical Chamber of Greece.

Host: Harry Perros, Computer Science, NCSU

Back to Seminar Listings
Back to Colloquia Home Page