STANFORD UNIVERSITY SCHOOL OF ENGINEERING
QUEUEING & SCHEDULING
IN PROCESSING NETWORKS
MS&E-335 / Autumn 2015
Announcements | Homework |
Time: Tue/Thu 4:30-5:50 pm, room: Shriram 054
- Office Hours: Tue/Thu 6-7 pm in Packard 238.
- TA: tbd.
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.
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
- 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.
- 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.
- Lecture notes (will be posted
on the website)
- Research papers (will be
posted on the website)
- Special chapters from books
- S. Asmussen. Applied Probability and Queues, Wiley,
- F. Baccelli, P. Bremaud.
Elements of Queueing Theory. Springer, 1991.
- A. Brandt, P. Franken, B. Lisek. Stationary
Stochastic Models, Wiley. 1992.
- X. Chao,
M. Miyazawa, M. Pinedo. Queueing Networks.
Fundamental of Queueing Networks, Springer, 2001.
Gross, C. M. Harris. Fundamentals of Queueing Theory - 3rd edition. Wiley,
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.
Harchol-Balter, Performance Analysis &
Design of Computer Systems, Cambridge 2013.
- R. Wolff.
Stochastic modeling and the theory of queues. Prentice-Hall, 1989.
- J. Walrand. Introduction to queueing networks.