Computer System Modelling

Lecturer: Professor I.M. Leslie (iml@cl.cam.ac.uk)

No. of lectures: 12

Prerequisite course: Probability

Aims

The aims of this course are to introduce the concepts and principles of analytic modelling, operational analysis and simulation, with particular emphasis on computer and communications systems.

Lectures

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

• Operational analysis Simple operational quantities. Weakness of assumptions. Bottleneck analysis. Applicability.

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

Objectives

At the end of the course students should

• be able to build simple Markov models and understand the assumptions which are used in their application to a real system

• be able to solve simple birth-death processes

• understand that in general, as utilisation of a system approaches unity, its response time becomes unbounded

• understand the tradeoffs between different types of modelling techniques

• be able to perform a bottleneck analysis of a system

• be aware of the issues in building a simulation of a computer system

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.
Lazowska, E.D., Zahorjan, J., Graham, G.S. & Sevcik, K.C. (1984). Quantitative System Performance. Prentice-Hall.