Multi-class queues and stochastic networks – LNMB Fall 2022
Course information on LNMB website
Announcement
Course description:
Complex stochastic systems, like communication systems, computer networks and manufacturing systems, may often be modeled as queueing networks with multiple nodes and/or multiple classes. The performance of these systems may be evaluated in terms of queue lengths, sojourn times or blocking probabilities. This course focuses on basic queueing networks for which performance measures can be obtained in closed form. First, the course focuses on a class of networks where the equilibrium distribution has a so-called product-form solution. Topics include the output theorem, reversibility, partial balance, quasi reversibility and product-form. Examples include Jackson networks, Kelly-Whittle networks, BCMP networks, loss networks and processor sharing networks. Second, the course considers the sojourn time distribution in simple networks. Third, computation of performance measures often requires effcient algorithms. To this end, Mean Value Analysis and approximation techniques will be studied.
Detailed content:
reversibility, stationarity, basic queues, output theorem, feedforward networks - partial balance, Jackson network, Kelly-Whittle netwerk, arrival theorem - quasi-reversibility, customer types, BCMP networks, bandwidth sharing networks - blocking, aggregation, decomposition - loss networks, insensitivity via phase-type distributions - sojourn time distribution in networks - MVA
Lecture notes:
- lecture notes
- lecture notes (updated version of chapter 1)
Additional material lectures 6 - 9:
- Norton's theorem:
www.sciencedirect.com/science/article/abs/pii/S0166531697000175 - Arrival theorem:
www.sciencedirect.com/science/article/abs/pii/S0166531696000454 - Network design: P. Whittle, section 9.7
Literature:
- R. Nelson, Probability, Stochastic Processes and Queueing Theory, 1995
- F.P. Kelly, Reversibility and Stochastic Networks, Wiley, 1979 (available on-line)
- R.W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice Hall, 1989
- R.J. Boucherie, N.M. van Dijk (editors), Queueing Networks – A Fundamental Approach, International Series in Operations Research and Management Science Vol 154, Springer, 2011
- P. Whittle, Systems in stochastic equilibrium, Wiley, 1986
- Handouts, slides and references to relevant additional literature will be made available at the lectures.
Prerequisites:
The participants should have followed courses in probability theory, stochastic processes and queueing theory.
Examination:
Take home problems.
Address of the lectureres:
Prof.dr. Richard J. Boucherie
Stochastic Operations Research; Department of Applied Mathematics; Faculty of Electrical Engineering, Mathematics, and Computer Science; University of Twente,
P.O. Box 217 NL-7500 AE Enschede
Phone: 053-4893432 Email: r.j.boucherie@utwente.nl
Schedule of lectures:
Sept 12, 19, 26: Lecture f2f in Utrecht
Oct 3: no class (but time to prepare the first exerciseset to be handed in Oct 10 before start of lecture).
Oct 10: Via a video lecture (prerecorded) feedback will be provided on the exercises. Video released in the afternoon.
Oct 10, 17, 24, 31, Nov 7: Lecture f2f in Utrecht
Nov 14: feedback f2f or on-line (to be discussed) on the second exerciseset to be handed in Nov 14 before start of lecture
SLIDES:
- slides lecture 1
- slides lecture 2
- slides lecture 3
- slides lecture 4
- slides lecture 5
- slides lecture 6 -- 8
VIDEOS:
Videos of lectures in 2022, see surfdrive
Videos of lectures in 2020:
- video lecture 1-1
- video lecture 1-2
- video lecture 2-1
- video lecture 2-2
- video lecture 3-1
- video lecture 3-2
- video lecture 4-1
- video lecture 4-2
- video lecture 5-1
- video lecture 5-2
- video lecture 6-1
- video lecture 6-1 on different equilibrium distributions used in the slides
- video lecture 6-2
- video lecture 7-1
- video lecture 7-2
EXercises:
- exercise set 1 (deadline October 10, 2022 before 11:00) video answers to exercises in set 1
- exercise set 2 (deadline November 14, 2022 before 11:00)
- provide explicit proofs of the results, i.e., you cannot state that the result is “by analogy with” result in book.
- hand in as single pdf file