What Queueing Theory Teaches us About Computer Systems Design
Computer Science Dept, Carnegie Mellon University
Morning: SUNDAY, June 14th
Based on the new textbook,
Cambridge University Press, 2013:
THE TALK SLIDES ARE HERE:
Abstract of Tutorial
The primary purpose of this tutorial is to explore fundamental
questions in computer systems design and learn what answers queueing
theory provides. Examples of such questions include:
We will cover the standard terms that come up in queueing:
- Given a choice between a single (fast) machine or many (slow)
machines, which is preferable and when?
- What are good "load balancing" policies, and when does it make
sense to balance load?
- How do high job size variability and heavy-tailed workloads affect
the choice of a scheduling policy?
- If the arrival rate doubles, and the service capacity doubles, does
that mean that response time should stay the same?
- What are the differences one should watch for in designing
closed-loop systems (where a new job only starts when a job
completes) as compared with open systems (where job arrivals are
independent of completions)?
- If a scheduling policy favors one set of jobs, does it necessarily
hurt other jobs, and by how much?
- What are the big lessons in capacity provisioning? How many
"spare" servers does one need? What about setup times? How much
does replication help?
We will follow the textbook, "Performance Modeling & Design of
Computer Systems," whose outline is given here .
- What is load? What is throughput?
- What is an open system versus a closed system?
- What is an Exponential distribution? What is a heavy-tailed distribution?
- What is a Poisson process?
- What is the Inspection Paradox?
- What is a continuous-time Markov Chain?
- What is a "setup time?"
- What is an M/M/1, M/G/1, G/G/1, M/M/k, M/G/k, etc?
- What are the common scheduling policies, and how do they compare?
- What is the effect of priority on response time?
- What are the common load balancing policies, and how do they compare?
- What is Square-root Staffing?
- What are Jackson networks of queues, and what's known about these?
All my talks are highly interactive and fun. This talk will include LOTS of PRIZES!
Target Audience and Prerequisites
The target audience is ISCA attendees who are interested in an
introduction to analytical performance modeling, for use in their
work. There are NO prerequisites. No math background is needed.
Tutorial will focus on lessons and intuitions, rather than derivations.
Mor Harchol-Balter is a Professor in the Computer Science at Carnegie
Professor Harchol-Balter is heavily involved in the ACM SIGMETRICS
research community, where she served as Technical Program Chair for
Sigmetrics 2007 and as General Chair for Sigmetrics 2013. Mor's work
focuses on designing new resource allocation policies (load balancing
policies, power management policies, and scheduling policies) for
server farms and distributed systems in general. She is known for her
work in queueing analysis, workload characterization, and systems
Professor Harchol-Balter has won a large number of teaching awards and
is known for highly entertaining technical talks . She has graduated
many PhD students, most of whom are now professors in top academic