Department of Computer Science and Technology

Part II CST

Course pages 2023–24

# Computer Systems Modelling

Principal lecturer: Prof Srinivasan Keshav
Taken by: Part II CST
Code: CSM
Term: Lent
Hours: 16 (online lectures and 8 examples classes)
Format: In-person lectures
Class limit: max. 20 students
Prerequisites: Data Science, Introduction to Probability
Moodle, timetable

Aims

The aims of this course are to introduce the concepts and principles of mathematical modelling

and simulation, with particular emphasis on using queuing theory and control theory for understanding the behaviour of computer and communications systems.

Syllabus

1.     Overview of computer systems modeling using both analytic techniques and simulation.

2.     Introduction to discrete event simulation.

a.     Simulation techniques

b.     Random number generation methods

c.     Statistical aspects: confidence intervals, stopping criteria

d.     Variance reduction techniques.

3.     Stochastic processes (builds on starred material in Foundations of Data Science)

a.     Discrete and continuous stochastic processes.

b.     Markov processes and Chapman-Kolmogorov equations.

c.     Discrete time Markov chains.

d.     Ergodicity and the stationary distribution.

e.     Continuous time Markov chains.

f.      Birth-death processes, flow balance equations.

g.     The Poisson process.

4.     Queueing theory

a.     The M/M/1 queue in detail.

b.     The equilibrium distribution with conditions for existence and common performance metrics.

c.     Extensions of the M/M/1 queue: the M/M/k queue, the M/M/infinity queue.

d.     Queueing networks. Jacksonian networks.

e.     The M/G/1 queue.

5.     Signals, systems, and transforms

a.     Discrete- and continuous-time convolution.

b.     Signals. The complex exponential signal.

c.     Linear Time-Invariant Systems. Modeling practical systems as an LTI system.

d.     Fourier and Laplace transforms.

6.     Control theory.

a.     Controlled systems. Modeling controlled systems.

b.     State variables. The transfer function model.

c.     First-order and second-order systems.

d.     Feedback control. PID control.

e.     Stability. BIBO stability. Lyapunov stability.

f.      Introduction to Model Predictive Control.

Objectives

At the end of the course students should

·       Be aware of different approaches to modeling a computer system; their pros and cons

·       Be aware of the issues in building a simulation of a computer system and analysing the results obtained

·       Understand the concept of a stochastic process and how they arise in practice

·       Be able to build simple Markov models and understand the critical modelling assumptions

·       Be able to solve simple birth-death processes

·       Understand and use M/M/1 queues to model computer systems

·       Be able to model a computer system as a linear time-invariant system

·       Understand the dynamics of a second-order controlled system

·       Design a PID control for an LTI system

·       Understand what is meant by BIBO and Lyapunov stability

Assessment

There will be one programming assignment to build a discrete event simulator and using it to simulate an M/M/1 and an M/D/1 queue (worth 15% of the final marks). There will also be two one-hour in-person assessments for the course on: Stochastic processes and Queueing theory (40%) and Signals, Systems, Transforms, and Control Theory (45%).

Reference books

Keshav, S. (2012)*. Mathematical Foundations of Computer Networking. Addison-Wesley. A customized PDF will be made available to class participants.

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

Kraniauskas, Peter. Transforms in signals and systems. Addison-Wesley Longman, 1992.

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