Course material 2010–11

##

Computer Systems Modelling

*Lecturer: Dr R.J. Gibbens and Dr C-K. Chau*

*No. of lectures:* 12

*Prerequisite courses: Probability, Mathematical Methods for
Computer Science*

**Aims**

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

**Lectures**

**Introduction to modelling.**Overview of analytic techniques and simulation. Little’s law.**Introduction to discrete event simulation.**Applicability to computer system modelling and other problems. Advantages and limitations of simulation approaches.**Random number generation methods and simulation techniques.**Review of statistical distributions. Statistical measures for simulations, confidence intervals and stopping criteria. Variance reduction techniques. [2 lectures]**Simple queueing theory.**Stochastic processes: introduction and examples. The Poisson process. Advantages and limitations of analytic approaches.**Birth-death processes, flow balance equations.**Birth-death processes and their relation to queueing systems. The M/M/1 queue in detail: existence and when possible solution for equilibrium distribution, mean occupancy and mean residence time.**Queue classifications, variants on the M/M/1 queue and applications to queueing networks.**Extensions to variants of the M/M/1 queue. Queueing networks. [2 lectures]**The M/G/1 queue and its application.**The Pollaczek-Khintchine formula and related performance measures. [2 lectures]**Randomized algorithms I.**Hashing, bloom filters and streaming algorithms.**Randomized algorithms II.**Random access protocols, random routing, random load balancing.

**Objectives**

At the end of the course students should

- be able to build simple Markov models and understand the critical modelling assumptions;
- be able to solve simple birth-death processes;
- understand that in general as the utilization of a system increases towards unity then the response time will tend to increase -- often dramatically so;
- understand the tradeoffs between different types of modelling techniques;
- be aware of the issues in building a simulation of a computer system and analysing the results obtained;
- be familiar with different types of randomized algorithm.

**Reference books**

* Ross, S.M. (2002). *Probability models for computer science*. Academic Press.

Mitzenmacher, M. & Upfal, E. (2005). *Probability and computing: randomized algorithms and probabilistic analysis*. Cambridge University Press.

Jain, A.R. (1991). *The art of computer systems performance analysis*. Wiley.

Kleinrock, L. (1975). *Queueing systems, vol. *1*. Theory*. Wiley.