Breadcrumb

Introduction to Queueing Networks 34 (M5800)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: M5800 Introduction to Queueing Networks 34
  2. Level: M/7
  3. Credit point value: 10 credit points
  4. Year: 12/13
  5. First Given in this form: 08/09 at Level 6 and 7; 07/08 at Level 6
  6. Unit Organiser: Ayalvadi Ganesh
  7. Lecturer: Ayalvadi Ganesh
  8. Teaching block: 1
  9. Prerequisites: MATH 21400 Applied Probability 2

Unit aims

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

General Description of the Unit

Queues are a fact of life - 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 purposes in telecommunications, computer technology and manufacturing.

The course will introduce relevant concepts in the context of a single server queue and look at simple parallel and tandem systems, before going on to develop models and performance criteria applicable to more general networks.

Relation to Other Units

The units Information Theory, Financial Mathematics, Queuing Networks and Complex Networks apply probabilistic methods to problems arising in various fields.

Teaching Methods

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

Learning Objectives

Students who successfully complete this unit should be able to:

  • identify the transition rates for simple Markov processes from an informal description of the system;
  • construct Markov process models of simple 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;
  • use Little's theorem to compute appropriate performance measures for simple systems.

Assessment Methods

The final assessment mark for Introduction to Queueing Networks 34 is constructed as follows:

  • 80% of the mark is calculated from a 1½-hour written examination in April, consisting of THREE questions. The candidate's best TWO answers will be used for assessment. Calculators are not allowed.
  • 20% of the mark will be based on selected homework problems.

Award of Credit Points

To gain the credit points for the unit, students must: 

  • either pass the exam (i.e. gain a final assessment mark of 50 or over),
  • or gain a final assessment mark of at least 40 and hand in reasonable attempts for more than half the set homework problems.

Transferable Skills

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

Texts

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

Other recommended texts:

I Mitrani, Modelling of computer and communication systems, Cambridge University Press, 1998.
J Walrand, An introduction to queuing networks, Prentice-Hall International, 1988.

Syllabus

1. Introduction: Markov chains, Exponential distributions, Poisson processes.

2. Continuous time Markov processes: models, full balance equations, equilibrium distributions.

3. Reversibility: Detailed balance, birth and death processes, Kelly's lemma.

4. Queues: Single-server and infinite server queues; Jackson networks, traffic equations.

5. Arrival/Departure theorems: Distributions seen by arriving and departing customers, PASTA property

6. Performance measures: Little's theorem. Service disciplines, multiple queues.

7. Mean-field queueing models.