STANFORD UNIVERSITY SCHOOL OF ENGINEERING
QUEUEING & SCHEDULING
IN PROCESSING NETWORKS
/ Autumn 2013
Announcements | Homework |
- Class Time: Mon/Wed 11:00-12:15, Place:
- Prof. Nick Bambos - Office Hours: Mon/Wed 1:30-2:30pm in Packard 238.
- TA: tbd.
- Admin. Associate: Lorrie Papadakis (firstname.lastname@example.org).
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.
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:
- 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.
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.
- The Nature of
fluctuations induce congestion, convexity of sojourn times and
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 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.
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 wireless networks.
- 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. Springer, 1991.
Brandt, P. Franken, B. Lisek. Stationary Stochastic Models, Wiley. 1992.
- X. Chao, M. Miyazawa, M. Pinedo.
Queueing Networks. Wiley, 1999.
- H. Chen, D. D. Yao. Fundamental of Queueing
Networks, Springer, 2001.
- 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 Press, 1995.
- 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.