Introduction to Queuing Networks 3

Unit aims

To introduce stochastic models for the description and analysis of simple queues and queueing networks.

Unit description

Queues are a fact of life - in banks, supermarkets, health care, traffic etc. The modelling and evaluation of individual queueing systems (in terms of quantities such as customer arrival patterns, service demands, scheduling priorities for different customer classes, queue size and waiting times) has been a rich source of theory and application in applied probability and operational research. Networks of linked queueing systems have gained wide popularity for modelling and performance-evaluation in telecommunications, computer systems and manufacturing. 

The course will introduce relevant concepts in the context of a single server queue before going on to develop models and performance criteria applicable to more general networks. Applications will be explored through homework problems.

Relation to other units

This is one of a number of units that applies probabilistic methods, learnt in Probability 2, to models arising in the real world. Other such units include Information Theory, Financial Mathematics and Complex Networks.

Learning objectives

Students who successfully complete this unit should be able to:

  • identify the transition rates for simple Markov chains in discrete and continuous time from an informal description of the system;
  • construct Markov process models of simple queues and queueing networks, specified in terms of the transition rates, and understand the basic properties of such models;
  • define the concepts of reversed and reversible Markov processes and use them to construct equilibrium distributions for simple queueing networks;
  • compute the distribution of the queue size as seen in equilibrium by arrivals and departures;
  • compute appropriate performance measures for simple systems, particularly using Little's theorem.

Transferable skills

The ability to translate practical problems into mathematics and the construction of appropriate probabilistic models.

Syllabus

  1. Markov chains: Transition probabilities, Invariant distribution and balance equations, Reversibility, Birth and death chains.
  2. Continuous time Markov chains: Exponential distributions, Poisson processes, transition rates, embedded chain,  Invariant distribution and balance equations, Reversibility.
  3. Simple queueing models: Single-server and infinite server queues, Service disciplines, Performance measures, Little's theorem, Distributions seen by arriving and departing customers, Applications of reversibility, PASTA property, Insensitivity.
  4. Networks of queues: Traffic equations, Stability, Jackson networks, Revisibility, Kelly's lemma, Time reversal for networks, Invariant distributions for networks, Distributions seen by arriving customers, Product form distributions and insensitivity.

Reading and References

Students will be provided with comprehensive lecture notes.

Main text:F P Kelly, Reversibility and stochastic networks, Wiley, 1979.

Other recommended texts:

I Mitrani, Probabilistic modelling, Cambridge University Press, 1998.

J Walrand, An introduction to queuing networks, Prentice-Hall International, 1988.

M. Harchol-Balter, Performance modelling and design of computer systems, Cambridge University Press, 2013.

Unit code: MATH35800
Level of study: H/6 
Credit points: 10
Teaching block (weeks): 1 (7-12)
Lecturer: Dr Ayalvadi Ganesh

Pre-requisites

MATH20008 Probability 2

Co-requisites

None

Methods of teaching

Lectures and weekly problem sheets, from which work will be set and marked, with outline solutions handed out a fortnight later.

Methods of Assessment

The pass mark for this unit is 40.

The final mark is calculated as follows:

  • 100% 1 hour 30 minutes Examination in January

NOTE: Calculators are NOT allowed.

For information resit arrangements, please see the re-sit page on the intranet.

Please use these links for further information on relative weighting and marking criteria.

Further exam information can be found on the Maths Intranet.

Edit this page