skip to primary navigationskip to content

Department of Computer Science and Technology

Undergraduate

Course pages 2020–21

Computer Systems Modelling

Principal lecturer: Prof Srinivasan Keshav
Taken by: Part II CST 75%
Hours: 16 (16hrs lectures and 4 supervisions)
Class limit: max. 30 students
Prerequisites: Data Science, Introduction to Probability

Syllabus

  1. Overview of computer systems modeling using both analytic techniques and simulation.
  2. Introduction to discrete event simulation.
    1. Simulation techniques
    2. Random number generation methods
    3. Statistical aspects: confidence intervals, stopping criteria
    4. Variance reduction techniques.
  3. Stochastic processes (builds on starred material in Foundations of Data Science)
    1. Discrete and continuous stochastic processes.
    2. Markov processes and Chapman-Kolmogorov equations.
    3. Discrete time Markov chains.
    4. Ergodicity and the stationary distribution.
    5. Continuous time Markov chains.
    6. Birth-death processes, flow balance equations.
    7. The Poisson process.
  4. Queueing theory
    1. The M/M/1 queue in detail.
    2. The equilibrium distribution with conditions for existence and common performance metrics.
    3. Extensions of the M/M/1 queue: the M/M/k queue, the M/M/infinity queue. Queueing networks. Jacksonian networks.
    4. The M/G/1 queue. The Pollaczek-Khintchine formula and related performance measures.
  5. Signals, systems, and transforms
    1. Discrete- and continuous-time convolution.
    2. Signals. The complex exponential signal.
    3. Linear Time-Invariant Systems. Modeling practical systems as an LTI system.
    4. Fourier and Laplace transforms.
  6. Control theory.
    1. Controlled systems. Modeling controlled systems.
    2. State variables. The transfer function model.
    3. First-order and second-order systems.
    4. Feedback control. PID control.
    5. Stability. BIBO stability. Lyapunov stability.

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

Reference books

  • Keshav, S. (2012)*. Mathematical Foundations of Computer Networking. Addison-Wesley.
  • Kleinrock, L. (1975). Queueing systems, vol. 1. Theory. Wiley.
  • Jain, R. (1991). The art of computer systems performance analysis. Wiley.
  • Ross, S.M. (2002). Probability models for computer science. Academic Press.
  • Harchol-Balter, M. (2013). Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press.