EE 621: Markov Chains and Queueing Systems
Instructor: Jayakrishnan Nair (home page)
TAs: TBA
Classes: Tue. and Fri., 5.30 - 7.00 pm (Slot 14), GG002
Prerequisites: A first course in probability (EE325 or EE601)
Office hours: TBA
All course-related communication will be handled via moodle.
Course
description
As the name suggests, this is a two-part
course. The first part will cover discrete and continuous time Markov
chains and their applications. In the second part of the course, we
will use our background on Markov chains to study modeling and
performance evaluation of queueing systems. We will cover the
following topics.
- Discrete-time Markov chains
- Introduction to Renewal Reward Theory
- Continuous-time Markov chains
- Markovian queueing models -- M/M/1, Erlang B & C
- Phase-type distributions and Matrix Analytic Methods
- M/G/1 mean value analysis via Renewal Reward
- M/G/1 transform analysis
- Scheduling policies in M/G/1: FCFS, LCFS, PLCFS, SRPT
- Burke's Theorem & Queueing Networks
Grading
- Homework assignments - 30%
- Quizzes (2) -- 20%
- Mid-term - 20%
- End-term - 30%
Note: A considerable weight is attached to homework assignments, which
will be handed out (almost) every two weeks. This is to encourage you
to spend time with the material being covered throughout the semester,
rather than concentrating the interaction around two discrete
events. While students are encouraged to discuss homework problems
with one another as well as the instructor/TAs, they are expected to
write their own solutions. Copying will result in
severe penalty.
Audit policy: Students auditing the course will be expected to give
both quizzes and submit all the homework assignments. A satisfactory
effort in these assignments is required for an audit grade. Appearing
in the mid-term and end-term exams will be optional for auditing
students.
References
The textbook for the course is Performance Modeling and Design of
Computer Systems by Mor Harchol-Balter. Other useful references
are:
Markov chains:
- Anurag Kumar's lecture notes on discrete event stochastic processes [link]
- R. G. Gallager, Stochastic Processes: Theory for applications
- J. R. Norris, Markov chains
Queueing systems:
- R. Wolff, Stochastic Modeling and the Theory of Queues
- Lecture notes on queueing theory by Ivo Adan and Jacques Resing [link]
- L. Kleinrock, Queueing Systems, Vol. 1 & 2