37: Analysis of Queueing Networks

"An algorithm must be seen to be believed." - Donald Knuth."Science is what we understand well enough to explain to a computer. Art is everything else we do. " - Donald Knuth.Lecture outline: Study of MVA techniques that allow computation of expected queue lengths in equilibrium for a closed separable system of queues

1) Analyzing open queuing networks

Arrival average and time-average

Arrival theorem (Poisson processes): the PASTA principle

Arrival theorem (Open Product-Form Queueing Networks [PFQNs])

Little's law

2) Mean value analysis (MVA)

Little's law applied to interactive closed QN

Arrival theorem (closed PFQNs)

3) Performance bounds

Asymptotic bounds

Transaction workload bounds

Batch workload bounds

Terminal workload bounds

Primary reference for this lecture:

“The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling” by Raj Jain; Chapter 34: “Mean-Value Analysis and Related Techniques”, and Chapter 35: “Convolution Algorithm”.

Secondary reference for this lecture:

"Mean Value Analysis: A Personal Account" by M Reiser.