STANFORD UNIVERSITY SCHOOL OF ENGINEERING

QUEUEING & SCHEDULING IN PROCESSING NETWORKS

MS&E-335 / Autumn 2012

Announcements    |    Homework    |    Lectures Notes

ADMINISTRATIVE INFORMATION

  • Class Time: Mon/Wed 11:00-12:15, Place: YE2E 155
  • Prof.  Nick Bambos - Office Hours: Mon/Wed 1:30-2:30pm in Packard 238.
  • TA: Praveen Bommannavar (bommanna@gmail.com)  Office Hours: Monday 5-6pm in Huang 304, and Tuesday 3-4pm in Huang B019.
  • Admin. Associate:  Lorrie Papadakis (lorriep@stanford.edu).

 

COURSE DESCRIPTION

This is an advanced course on modeling, analysis and design of queueing systems and stochastic processing networks. Its purpose is to introduce Stanford graduate students to modern concepts, important models and key results used in the study of queueing systems, preparing them for further targeted study and research in engineering fields where "queueing phenomena" play an important role in system performance. Such is the case in congestion management, throughput or yield maximization, task scheduling and resource allocation in a variety of engineering systems, ranging from computer communication networks, distributed computing and the Internet ... to production systems, supply chains, service systems, business operations etc.

The course aims to develop the student's intuition and technical ability in modeling and analyzing complex queueing systems and networks.  Despite its seemingly high mathematical level, most emphasis is placed on identifying and explaining the deep concepts and intuition associated with the issues under consideration.

Solid understanding of probability and Markov chains will be useful background for this course.

The high-level structure of the course is following:

  • Introduction to the Study of Queueing Systems: basic elements of queueing systems, the canonical model, queueing notation, brief review of the the M/M/1 queue - stability and backlog.

  • General Concepts and Results in Queueing Systems:
    • The Stability Problem of the G/G/1 Queue:  the G/G/1 queue model, flow stationarity and ergodicity, Lindlay's equations, Loyne's construction of the stationary regime and its finiteness problem, the pathwise coupling argument and uniqueness of the stationary regime, the stability of the G/G/1 queue and strong convergence to steady state, simulation and performance evaluation issues, feed-forward queueing networks.
    • Model Extensions and Processing Networks: the precedence constraint as a queueing modeling attribute, the subadditive ergodic theorem, parallel traffic intensity, stationary regimes, pathwise coupling, stability, networks with jobs with internal task structure.
    • The Generalized Little's Law: the backlog-to-delay dependence in complex queuing systems, soft stability, simulation issues.
    • The Nature of Queueing Delay: fluctuations induce congestion, convexity of sojourn times and fluctuation-induced delay.
  • Classical Results on Single-Node Queueing Systems: the M/GI/1 queue, embedded Markov chain, the PASTA property, Pollaczek-Khintchine formulas, the Takacs equation, the GI/M/1 queue, the GI/GI/1 queue, phase-type approximations, Brownian and fluid approximations.
  • Markovian Queueing Networks:
    • Preliminaries: stopping times, strong Markov property, Markov chains watched in a set, time reversal, the M/M/1 reversibility argument, Burke's result, jump chains.
    • Quasi-reversibility and Product Form: quasi-reversible queues, networks of quasi-reversible nodes, the Jackson network model, multi-class queueing networks, the BCMP result. 
  • Controlled Queueing Systems & Processing Networks: controlled Markov chains and the Lyapunov method, stochastic scheduling and resource allocation problems, the throughput maximization problem, queueing networks with interdependent resources, applications to packet scheduling in high-speed communication switches and wireless networks.

 

READING MATERIAL

 

  • Lecture notes (will be posted on the website)
  • Research papers (will be posted on the website)
  • Special chapters from books (recommended)

 

 

GENERAL REFERENCES

  1. S. Asmussen.  Applied Probability and Queues, Wiley, 1987.
  2. F. Baccelli, P. Bremaud. Elements of Queueing Theory. Springer, 1991.
  3. A. Brandt, P. Franken, B. Lisek. Stationary Stochastic Models, Wiley. 1992.
  4. X. Chao, M. Miyazawa, M. Pinedo. Queueing Networks. Wiley, 1999.
  5. H. Chen, D. D. Yao. Fundamental of Queueing Networks, Springer, 2001.
  6. D. Gross, C. M. Harris. Fundamentals of Queueing Theory - 3rd edition. Wiley, 1998.
  7. F. Kelly. Reversibility and Stochastic Networks. Wiley. 1979.
  8. M. Y. Kitaev, V. V. Rykov. Controlled Queueing Systems. CRC Press, 1995.
  9. L. Kleinrock. Queueing Systems I & II, Wiley, 1975.
  10. R. Serfozo. Introduction to Stochastic Networks, Springer 1999.
  11. R. Wolff. Stochastic modeling and the theory of queues. Prentice-Hall, 1989.
  12. J. Walrand. Introduction to queueing networks. Prentice-Hall. 1989.