# 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:
SLIDES

#### 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:
- 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 cover the standard terms that come up in queueing:
- 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?

We will follow the textbook, "Performance Modeling & Design of
Computer Systems," whose outline is given here .
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.

#### Bio

Mor Harchol-Balter is a Professor in the Computer Science at Carnegie
Mellon University.
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
implementation.
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
institutions.