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].