a.k.a. Analytic tools for system design

TBA.

When designing a network protocol, distributed system, etc., it is essential to be able to quantify the performance impacts of design choices along the way. For example, should we invest in more buffer space or a faster processor? One fast disk or multiple slower disks? How should requests be scheduled? What dispatching policy will work best? Ideally, one would like to make these choices before investing the time and money to build a system. This class will teach students how to answer this type of "what if" question by introducing students to analytic performance modeling, the tools necessary for rigorous system design. The course will focus on the mathematical tools of performance analysis (which include stochastic modeling, scheduling theory, and queueing theory) but will also highlight applications
of these tools to real systems.
*This course is targeted for graduate students and advanced undergraduates. Students should have a strong background in probability.*

**Adam Wierman**, adamw@caltech.edu

Office Hours: TBA

TBA

We will be using "Performance Modeling and design of computer systems" by Mor Harchol-Balter as our primary textbook. However, some good reference texts that I will be making use of are listed here.

This is a preliminary breakdown that may change during the term.

- Class participation (attendance and interaction in the discussions) -- 10%
- Homeworks -- 70%
- Final -- 20%

You're likely going to be stuck with my handwritten notes...I'll try to keep them legible! Because of that, I recommend taking notes yourself during class because I will occasionally say important things that won't be reflected in the notes. Also, note that there are very likely typos in the notes. When you find them, let me know and I'll correct them.

- A first stochastic process
- DTMCs
- The celebrated (and demonized) Poisson Process
- From DTMCs to CTMCs

- PASTA and the M/M/1
- Little's Law
- M/M/m and M/M/m/m

- Queueing networks
- Beyond the M/M/*: Phase-type Distributions
- Beyond the M/M/*: The M/GI/1
- More on the M/GI/1
- Moving to the GI/GI/1: Lindley's equation
- An aside: How to compare random variables

- Non-preemptive, blind scheduling
- Processor Sharing and PLCFS
- Non-preemptive, size-based scheduling
- SRPT: Simple, greedy, and optimal

- A tale of tails
- Queueing games

- A quick review

Homeworks will be assigned every 1-2 weeks. Some of the problems will be challenging, so please start early. Most assignments will be primarily proofs, however there will be an occasional problem that requires you to build a simulator and/or do numeric experiments. **We assume that you can code and use Matlab/Mathematica.**

- Homework 1: A probability refresher
- Homework 2: Practice with DTMCs
- Homework 3: Practice with CTMCs
- Homework 4: Queueing games
- Homework 5: Queueing networks and PH distributions
- Homework 6: Transform world
- Homework 7: Scheduling

You will receive one homework every week or so. These will typically require a significant amount of work, and you should start immediately and come to office hours to discuss questions. Please do not search the web for help on the homework problems. It is difficult to develop good homework problems, and thus you may come across similar problems if you search the web for help.

You are strongly encouraged to collaborate with your classmates on these problems, but each person must write up the final solutions **individually**. You should note on your homework specifically which problems were a collaborative effort and with whom.

Assignments will typically be due on Friday at 1pm. If the assignment is turned in by Monday at 8am the late penalty is 15 points; if it is turned in by the following Wednesday the late penalty is 30 points. Homeworks will not be accepted after this point unless there are special circumstances that you have discussed with the professor before the original due date.

- CMU, Performance Modeling, Mor Harchol-Balter
- CUHK, Computer System Performance Evaluation, John C.S. Lui
- Columbia, Stochastic Models I, Ward Whitt
- TuE, Queueing Theory, Ivo Adan
- Columbia, Performance Modeling and Evaluation, Ed Coffman
- Helsinki University, Queueing Theory, Jorma Virtamo
- UMASS Amherst, Performance Evaluation, Don Towsley

- S. M. Ross, Introduction to Probability Models
- S. M. Ross, Stochastic Processes
- R. W. Wolff, Stochastic Modeling and the Theory of Queues
- L. Kleinrock, Queueing Systems, Vol. I: Theory
- L. Kleinrock, Queueing Systems, Vol. II: Computer Applications
- S. Karlin and H. M. Taylor, A First Course in Stochastic Processes
- S. I. Resnick, Adventures in Stochastic Processes
- W. Whitt, Stochastic Process Limits

- R. Conway, W. Maxwell, and L. Miller, Theory of Scheduling
- Michael Pinedo, Scheduling Theory, Algorithms, and Systems

- H. Kobayashi and B. L. Mark, System Modeling and Analysis
- E. Lazowska, J. Zahorjan, S. Graham, K. Sevcik, Quantitative System Performance
- D. Menasce, V. Almeida, and L. Dowdy, Capacity Planning and Performance Modeling
- R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling

- D. P. Bertsekas and J. N. Tsitsiklis, Introduction to Probability
- M. Mitzenmacher and Upfal, Probability and Computing
- K.L. Chung, A Course in Probability Theory
- W. Feller, An Introduction to Probability Theory and Its Applications
- P. Billingsley, Probability and Measure