35: Queueing Networks

"Nature seems to reach many of her ends by long circuitous routes." —Rudolph LotzeLecture outline: How can we analyze a network of queues?

Preamble: Queueing system as a service centers; Types of service centers.

1. Queueing Networks (QN): Introduction and Classification

What is a QN?

Open and Closed QNs

QNs for modeling computer systems

Workload based classification of QNs

Solution of QNs

State space of a QN;

Separable QNs; Product-form Queueing Networks (PFQNs)

Properties of Poisson processes

Burke’s theorem; Feedforward and Feedback QNs.

Jackson’s theorem; Jackson Networks

Open Jackson Networks; Closed Jackson (Gordon-Newell QNs)

BCMP QNs

2. QN models for data networks:

Queueing theory in computer networks: Leonard Kleinrock’s contributions.

Modeling data networks: exact formula for average network delay

Dependence of packet length, service times, and inter-arrival times.

Kleinrock’s independence assumption.

Primary reference for this lecture:

“The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling” by Raj Jain; Chapter 32: “Queueing Networks”.

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 4: “Queueing Network Model Inputs and Outputs”.

2. “Performance Evaluation of Computer and Communication Systems” by Le Boudec, Chapter 8: “Queuing Theory For Those Who Cannot Wait”, Section 8.4: “Definitions for Queueing Networks”

3. “Performance Evaluation of Computer and Communication Systems” by Le Boudec, Chapter 8: “Queuing Theory For Those Who Cannot Wait”, Section 8.9.4: “Queueing Network Analysis”

4. “Data Networks” by Bersekas and Gallager; Chapter 3: Delay Models in Data Networks.