33: Single-Server Queueing Systems

"A common slogan in the U.S. Army is, 'Hurry up and wait', such is the nature of the phenomena we wish to study." - Leonard Kleinrock (Queueing Systems, Vol. 1).Lecture outline: How can we analyze single-server queueing systems?

1. M/M/1 queues

State probabilities for M/M/1

Performance measures of M/M/1 queue

2. M/G/1 queues

Pollackzek-Khintchine (P-K) formula

Special case of M/G/1: the M/D/1 queue

Effect of variance in service distribution on performance

Effect of server utilization on performance

M/G/1 example: comparing exponential, lognormal and constant service times

Primary reference for this lecture:

“The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling” by Raj Jain; Chapter 31: “Analysis of a Single Queue”.

Secondary references for this lecture:

1. “Performance Evaluation of Computer and Communication Systems” by Le Boudec, Chapter 8: “Queuing Theory For Those Who Cannot Wait”, Section 8.3: “Classical Results for A Single Queue”

2. “Performance Evaluation of Computer and Communication Systems” by Le Boudec, Chapter 8: “Queuing Theory For Those Who Cannot Wait”, Section 8.9.2: “Case Study: Single Queue Analysis”

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