Skip to main content

IE 606: Analysis & Control of Queues

Prerequisite:  IE 611 or equivalent and instructor consent

 

Brief Description

This course is meant to teach topics in probability theory required for studying  queuing systems. This can also be viewed as an advance level course in probability and stochastic processes. Importantly, this course mainly focuses on  uncountable state space (e.g., $R^n$) stochastic processes.  After providing a systematic introduction to processes such as Martingales, Markov chains and Brownian motion, the focus shifts to queueing systems.  G/G/1 queues are discussed  and  their analysis is obtained after modeling them either with Brownian motion or Random Walk or Fluid limits. Towards the end, optimal scheduling policies are discussed.  Applciations other than queueing systems may also be discussed. Some of the topics might be omitted or added as the course progresses. 

Course contents

  1. Review: Conditional expectation, Convergence of Random Variables.
  2. Martingales: Super and Sub martingales, Doob’s inequalities, Martingale convergence theorems
  3. Markov chains and stability (general state space, e.g., Rn ) : Introduction, Psi irreducibility, Small sets, Transience and recurrence, Drift criterion, Ergodicity - Geometric and Uniform. Existence and continuity of stationary distribution for a decision feedback equalizer.
  4. Brownian motion: Definition, Properties (continuous paths, nowhere differentiability), Hitting times (one dimensional results), Functional Central Limit theorem.
  5. Controlled Queueing systems: Various models approximating the controlled queueing systems (G/G/1): Renewal processes, Random Walks, Brownian Motion and Fluid models Scheduling - Stabilizability, Optimal scheduling policies for fluid models.

References

  • Jean Jacod, Philip E. Protter, ”Probability Essentials”, Springer, 2003.
  • Sean Meyn and Richard L. Tweedie, ”Markov Chains and Stochastic Stability”, Springer-Verlag London Ltd, 1993.
  • P. Billingsley, ”Probability and Measure”, third ed., Wiley-Interscience, New York, 1995.
  • Sean Meyn ”Control techniques for complex networks”, Cambridge University Press, 2008.
  • Phillipe Robert, ”Stochastic Networks and Queues”, Springer 2003.
  • Relevant Research papers.