Computer systems design is full of conundrums:

•Given a choice between a single machine with speed s, or n machines each with speed s/n, which should we choose?

•If both the arrival rate and service rate double, will the mean response time stay the same?

•Should systems really aim to balance load, or is this a convenient myth?

•If a scheduling policy favors one set of jobs, does it necessarily hurt some other jobs, or are these “conservation laws” being misinterpreted?

•Do greedy, shortest-delay, routing strategies make sense in a server farm, or is what's good for the individual disastrous for the system as a whole?

•How do high job size variability and heavy-tailed workloads affect the choice of a scheduling policy?

•How should one trade off energy and delay in designing a computer system?

•If 12 servers are needed to meet delay guarantees when the arrival rate is 9 jobs/sec, will we need 12,000 servers when the arrival rate is 9,000 jobs/sec?

Tackling the questions that systems designers care about, this book brings queueing theory decisively back to computer science. The book is written with computer scientists and engineers in mind and is full of examples from computer systems, as well as manufacturing and operations research. Fun and readable, the book is highly approachable, even for undergraduates, while still being thoroughly rigorous and also covering a much wider span of topics than many queueing books. Readers benefit from a lively mix of motivation and intuition, with illustrations, examples, and more than 300 exercises – all while acquiring the skills needed to model, analyze, and design large-scale systems with good performance and low cost. The exercises are an important feature, teaching research-level counterintuitive lessons in the design of computer systems. The goal is to train readers not only to customize existing analyses but also to invent their own.

Table of Contents

I Introduction to Queueing

1 Motivating Examples of the Power of Analytical Modeling

2 Queueing Theory Terminology

II Necessary Probability Background

3 Probability Review

4 Generating Random Variables for Simulation

5 Sample Paths, Convergence, and Averages

III The Predictive Power of Simple Operational Laws: “What-If”

Questions and Answers

6 Little’s Law and Other Operational Laws

7 Modification Analysis: “What-If” for Closed Systems

IV From Markov Chains to Simple Queues

8 Discrete-Time Markov Chains

9 Ergodicity Theory

10 Real-World Examples: Google, Aloha, and Harder Chains∗

11 Exponential Distribution and the Poisson Process

12 Transition to Continuous-Time Markov Chains

13 M/M/1 and PASTA

V Server Farms and Networks: Multi-server, Multi-queue Systems

14 Server Farms: M/M/k and M/M/k/k

15 Capacity Provisioning for Server Farms

16 Time-Reversibility and Burke’s Theorem

17 Networks of Queues and Jackson Product Form

18 Classed Network of Queues

19 Closed Networks of Queues

VI Real-WorldWorkloads: High Variability and Heavy Tails

20 Tales of Tails: A Case Study of Real-World Workloads

21 Phase-Type Distributions and Matrix-Analytic Methods

22 Networks with Time-Sharing (PS) Servers (BCMP)

23 The M/G/1 Queue and the Inspection Paradox

24 Task Assignment Policies for Server Farms

25 Transform Analysis

26 M/G/1 Transform Analysis

27 Power Optimization Application

VII Smart Scheduling in the M/G/1

28 Performance Metrics

29 Scheduling: Non-Preemptive, Non-Size-Based Policies

30 Scheduling: Preemptive, Non-Size-Based Policies

31 Scheduling: Non-Preemptive, Size-Based Policies

32 Scheduling: Preemptive, Size-Based Policies

33 Scheduling: SRPT and Fairness

About the Author

Mor Harchol-Balter is an Associate Professor in the Computer Science Department at Carnegie Mellon University. She is a recipient of the McCandless Chair, the NSF CAREER award, the NSF Postdoctoral Fellowship in the Mathematical Sciences, multiple best paper awards and several teaching awards, including the Herbert A. Simon Award for Teaching Excellence and the campus-wide Teaching Effectiveness Award. She is a leader in the ACM SIGMETRICS/Performance community, for which she recently served as Technical Program Chair, and has served on the Technical Program Committee twelve times. Harchol-Balter's work integrates queueing theoretic analysis with low-level computer systems implementation. Her research is on designing new resource allocation policies (load balancing policies, power management policies and scheduling policies) for server farms and distributed systems in general, where she emphasizes integrating measured workload distributions into the problem solution.