Computer System Modelling

Lecturers: Dr S.A. Crosby and Dr F. Toomey
(sac@cl.cam.ac.uk )

No. of lectures: 12

Prerequisite course: Probability  

Introduction to modelling.

What is it, when is it useful? Overview of analytic techniques, operational analysis, simulation.

Simple queueing theory.

Stochastic processes, definition and examples. Restriction to tractable systems. Markov chains.

Birth-death processes, general flow balance equations.

Relation to queueing systems. The M-M-1 queue in detail: solution for state occupancy, average queue length, average residence time. General observations.

Queue classifications & variants on the M-M-1 queue & applications.

Extensions to birth-death models: series and parallel stages; the Er-M-1 and M-Er-1 queues. Multiple queue systems.

The M/G/1 queue and its application.

The Pollaczek Khintshine formula; performance measures; the non-preemptive priority queue.

Introduction to discrete event simulation.

Applicability to computer system modelling and other problems. Limitations of simulation models. The discrete event simulation algorithm; examples.

Random number generation methods, random variate generation.

Statistical measures for simulations, confidence intervals and stopping criteria. Distributed simulation.

Introduction to Large Deviation Theory.

Large Deviation Theory is a theory of rare events; it can be used to estimate the tails of probability distributions. In recent years, it has been used extensively in teletraffic theory. The aim of this set of lectures is to introduce students to the basic ideas of the theory and its application in computer systems and network modelling.

Large Deviation Theory continued.

What Large Deviation Theory is about, Cramér's Theorem and the Rate-Function, the connection with the Central Limit Theorem (why ``Large'' Deviations?), Large Deviations in Queuing Networks: effective bandwidths.

Recommended books:

Kleinrock, L. (1975). Queueing Systems. Vol. 1: Theory. Wiley.

Leung, C. (1988). Quantitative Analysis of Computer Systems. Wiley.

Jain, A.R. (1991). The Art of Computer Systems Performance Analysis. Wiley.