31: Introduction to Queuing Theory
"One of life's more disagreeable activities, namely, waiting in line, is the delightful subject of this book. One might reasonably ask, "What does it profit study such unpleasant phenomena?" - Leonard Kleinrock (Queueing Systems, Vol. 1).Lecture outline: A general introduction to queueing theory
Preamble: What is analytical modeling?
Preamble: In dynamic resource sharing, why have queues at all?
1. Queueing theory – a brief history
Erlang’s invention of queueing theory
An teletraffic example to illustrate some key concepts of queueing
An early look at the Erlang B formula in the example above
2. Queueing theory – an intuitive introduction
Deterministic queue vs. stochastic queue
Stability of queues: behavior of lightly, moderately, and heavily loaded queues
3. Queueing systems – classification.
Single server queues
Multiple single-server queues
Multiple server queues
Multiple server loss systems
Infinite server delay systems
Specification of queueing systems: Kendall’s notation.
Example of Kendall’s notation: M/M/1; M/G/1, etc.
Primary reference for this lecture:
“The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling” by Raj Jain; Chapter 30: “Introduction to Queueing Theory”.
Secondary references for this lecture:
1. “Quantitative System Performance: Computer System Analysis Using Queueing Network Models” by Lazowska, Zahorjan, Graham, and Sevcik [freely available online on authors website]; Chapter 1 and Chapter 2.
2. “Measuring Computer Performance: A Practitioner's Guide” by David Lilja; Chapter 11: “Queueing Analysis”
3. “Performance Evaluation of Computer and Communication Systems” by Le Boudec, Chapter 8: “Queuing Theory For Those Who Cannot Wait”
4. “Analyzing Computer System Performance with Perl::PDQ” by Neil Gunther; Chapter 2, “Getting the Jump on Queueing”
5. “Data Networks” by Bersekas and Gallager; Chapter 3: Delay Models in Data Networks.
6. "Queueing Analysis", William Stallings [link].