ECE 605 - Winter 2018

ECE 605 - Queueing Systems

Instructor

Professor Ravi Mazumdar
Office: EIT 3141
Phone: (519) 888-4567 x37444
e-mail: mazum@uwaterloo.ca
Office hours: By appointment via email or see me after the lecture.

Lectures

Wednesday to Friday, 2.30 to 3.50 p.m. in room EIT 3141

Course website

LEARN

Course description

The principal aim of this course is a rigorous introduction to the underlying structures and models of queueing systems. This course will build on the knowledge of random processes and introduce the students to advanced topics in the modeling of point processes, the theory of Markov chains, regenerative phenomena, and the notions of Palm probabilities and associated calculus of point process models.

Course outline

  1. Review of Probability and Markov chains- classification of states, invariant distributions, ergodicity, coupling. Birth-death processes.
  2. Introduction to point processes: Poisson processes, stationary point processes, recurrence times, PASTA.
  3. From point processes to continuous time Markov chains. Reversibility. Insensitivity. Stability of Markov processes.
  4. Palm probabilities. Inversion formula, Neveu's exchange formula. Papangelou's formula, Rate Conservation Laws and the so-called H = G.
  5. Stationary queueing systems, Loynes construction, busy periods. Pathwise approach.
  6. Birth-death models and Markovian queues. M=M=: , M=G=1, GI=M=1 queues. Arrival and time stationary distributions. M=G=1 and loss models and insensitivity.
  7. Introduction to stochastic network models: Jackson, BCMP, network optimization and insensitivity. Randomized algorithms and the Power of Two.

Text and references

R. R. Mazumdar, Performance Modeling, Stochastic Networks, and Statistical Multiplexing, Synthesis Lectures on Communication Networks, Morgan and Claypool, San Francisco, 2010.

This book can be downloaded by UW students for free from a UW IP address from the following link:
http://www.morganclaypool.com/doi/abs/10.2200/S00504ED1V01Y201305CNT012

The following references are excellent for selected topics.

References

The first book listed below is excellent for both an intuitive approach as well as for applications of queueing models while the second is an authoritative source on Markov chains.

M. Harchol-Balter, Performance modelling and Design of Computer Systems, Cambridge University Press, 2013.

P. Bremaud; Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, Springer Texts in Mathematics 31, Springer-Verlag, N.Y. 1999. ISBN- 0-387-98509-3

Course evaluation

  • Weekly problem sets will be handed out. The onus is on you all to attempt them. Solutions will be posted.

  • There will be two simulation projects that will count for 10% of the grade.

  • There will be a midterm exam. The dates will be announced later.

  • In addition, there will be a nal examination.

  • Marks distribution: Projects 10% Midterm Exam 35%, Final Exam = 55%

Additional remarks

  • All exams will be open notes.
  • If you miss the midterm exam no make-up exam will be given. If you have a valid reason then your final grade will be based on your performance in the rest of the course.
  • Dishonesty will be dealt with harshly.