Recommended Organization for Graduate Class (with choices)
IMPORTANT: Prior to Class: Ask students to read Chpt 3 in their book
carefully and do all the exercises in preparation for the class. Chpt
3 reviews undergraduate probability, which is a prerequisite.
WEEK 1:
- Chpt 1 (motivating examples)
- Chpt 2 (queueing notation)
- Recitation: Reviews Chpt 3 distributions and reviews series summation.
Assign homework on Chpt 3 questions to make sure that people
are up on the prerequisite background.
WEEK 2:
- Chpt 4 (generating random variables for simulation)
- Chpt 5 (time averages versus ensemble averages)
-- Note that if your class is less mathy, you can just skim Chpt 5.
It's not entirely necessary, but words like "convergence",
"time average" and "ensemble average" come up later in the text.
WEEK 3:
- Chpt 6 (operational laws)
- Chpt 7 (operational laws -- "what if" analysis)
WEEKS 4 + 5:
- Chpt 8 (Discrete-time Markov Chains)
- Chpt 9 (Ergodicity Theory)
-- Note: Chpt 9 is very math heavy. Personally, I teach all the proofs, but I think most people will prefer to simply skim the chapter, maybe doing
out the proofs in the case of finite-state chains and then just
discussing the intuition in the case of infinite-state chains.
WEEK 6:
- Chpt 10.1 (I only cover the Google PageRank example, but I sometimes have
recitation cover section 10.2. )
- Chpt 11 (Exponential & Poisson)
Week 7:
- Chpt 12 (Converting from Discrete-time Markov Chains to Continuous-time MCs)
- Chpt 13 (M/M/1)
Week 8:
- Chpt 14 (M/M/k and M/M/k/k)
- Chpt 15 (Capacity Provisioning) This is a really important chapter, because
the application is so relevant today.
CHOICE POINT:
At this point, you have a choice as to whether to cover "networks of queues" or not.
- If you cover "networks of queues," I recommend covering
Chpt 16, 17, maybe 18, skip 19. Later cover Chpt 22.
- If you skip "networks of queues," you will skip straight to Chpt 20.
WEEK 9: This is an optional week
- Chpt 16 (Networks of queues)
- Chpt 17 (Networks of queues)
- Chpt 18 (Networks of queues)
WEEK 10:
- Chpt 20 (Heavy tailed workloads)
- Chpt 21 (Matrix-analytic methods)-- This is optional and can be skipped as well. If you cover it, I recommend using recitation to help go through examples.
WEEK 11:
- Chpt 23 (M/G/1)
- Chpt 24 (Task Assignment in Server Farms) --
You won't be able to finish this in a single lecture.
CHOICE POINT:
At this point, you have a choice as to whether to cover
"transforms" or not.
I recommend that you skip tranforms the first time that you're teaching,
because they usually take a long time to teach.
- If you cover transforms, you will need: Chpt 25, 26, 27
- If you skip transforms, you will skip: Chpt 25, 26, 27
Note that Chpt 27 on Power Management is pretty nice, but it requires
understanding the M/G/1/setup queue, whose performance we derive using
transforms. If you skip transforms, you can still cover the chapter,
but just give students the formula for mean response time in the M/G/1/setup.
I'm assuming below that you skip transforms.
WEEK 12:
- Chpt 28 (Scheduling in M/G/1)-- I recommend doing without transforms at first
- Chpt 29 (Scheduling in M/G/1)-- I recommend doing without transforms at first
- Chpt 30 (Scheduling in M/G/1)-- I recommend doing without transforms at first
WEEK 13:
- Chpt 31 (Scheduling in M/G/1) -- I recommend doing without transforms at first
- Chpt 32 (Scheduling in M/G/1) -- I recommend doing without transforms at first
WEEK 14:
- Chpt 33 (Scheduling and Fairness)
I recommend assigning weekly homework, since there are a lot of concepts being covered. I am available at all times to help out instructors. If you are teaching this class, please send me email:
harchol@cs.cmu.edu.
Back to Mor's Home Page .