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.