STANFORD UNIVERSITY SCHOOL OF ENGINEERING
QUEUEING & SCHEDULING
IN PROCESSING NETWORKS
MS&E-335 / Autumn 2012
Announcements | Homework |
- 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
(firstname.lastname@example.org) Office Hours: Monday
5-6pm in Huang 304, and Tuesday 3-4pm in Huang B019.
- Admin. Associate: Lorrie Papadakis (email@example.com).
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.
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
understanding of probability and Markov chains will be useful background for
high-level structure of the course is following:
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.
Concepts and Results in Queueing Systems:
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.
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.
Generalized Little's Law: the backlog-to-delay dependence in
complex queuing systems, soft stability, simulation issues.
Nature of Queueing Delay: fluctuations induce congestion,
convexity of sojourn times and fluctuation-induced delay.
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
- Markovian Queueing
- 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.
and Product Form: quasi-reversible queues, networks of
quasi-reversible nodes, the Jackson
network model, multi-class queueing networks, the BCMP result.
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
- Lecture notes (will be posted on the website)
- Research papers (will be posted on the website)
- Special chapters from books (recommended)
- S. Asmussen.
Applied Probability and Queues, Wiley, 1987.
- F. Baccelli,
P. Bremaud. Elements of Queueing Theory.
- A. Brandt, P. Franken, B. Lisek. Stationary Stochastic Models, Wiley.
- X. Chao, M. Miyazawa, M. Pinedo. Queueing Networks. Wiley, 1999.
- H. Chen, D.
D. Yao. Fundamental of Queueing Networks,
- D. Gross, C. M. Harris.
Fundamentals of Queueing Theory - 3rd edition. Wiley, 1998.
- F. Kelly. Reversibility and
Stochastic Networks. Wiley. 1979.
- M. Y. Kitaev,
V. V. Rykov. Controlled Queueing Systems. CRC
- L. Kleinrock.
Queueing Systems I & II, Wiley, 1975.
- R. Serfozo.
Introduction to Stochastic Networks, Springer 1999.
- R. Wolff. Stochastic modeling
and the theory of queues. Prentice-Hall, 1989.
- J. Walrand.
Introduction to queueing networks. Prentice-Hall. 1989.