Breadcrumb

Introduction to Queuing Networks (MATH 35800)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: MATH 35800 Introduction to Queuing Networks
  2. Level: H/6
  3. Credit point value: 10 credit points
  4. Year: 12/13
  5. First Given in this form: 2006-7 as a 10cp unit, previously given as a 20cp unit Queueing
  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 - 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

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 assessment mark for Introduction to Queuing Networks 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.

Award of Credit Points

To gain credit points, students must either pass the unit, or get a mark of 30 or over in the unit and hand in reasonable attempts to three designated homework questions.

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.