Large Deviations and Queues
What:
16-lecture course for Part III [Part III schedules]When:
Lent term 2005, Mondays and Wednesdays at 11am [Reporter lecture list]Where:
MR12Who:
Lectured by D.J.Wischik.Syllabus
Large deviations is a branch of probability concerned with rare events: their probabilities, and how they happen. The study of queues is concerned with estimating the distribution of queue length under random traffic, with characterizing traffic statistics, and with analyzing the performance of networks of queues and of scheduling systems like priority queues.
In the past 15 years, large deviations has been applied with great success to a variety of problems in queueing theory. The estimates it yields are simple, so that many of the details which make it hard to obtain exact answers disappear, yet they retain sufficient structure to make the answers relevant.
This course will give an introduction to abstract large deviations theory; but the focus will be on applying the theory to problems in queueing networks, particularly communications networks such as the Internet.
Large deviations.
Cramér's theorem. Large deviations principle. Principle of the largest term. Contraction principle. Sanov's theorem. Gärtner-Ellis theorem. Inverse contraction principle. Schilder's theorem.-
Queueing theory.
Queues. Large deviations for workload processes. Various scaling regimes. Overflow in queues. Priority queues. The output of a queue. Moderate deviations and heavy traffic theory. -
Application.
The Internet as a queueing network. Effective bandwidths and admission control. Long-range dependence and self-similarity. Fast simulation. Timescales and control loops. Internet switches.
Pre-requisite mathematics.
Knowledge of probability, optimization, and basic topology, at about second-year level, will be assumed.Suggested reading
- Big Queues, Ayalvadi Ganesh, Neil O'Connell, Damon Wischik. Springer, 2004.
- Large deviations techniques and applications, Amir Dembo & Ofer Zeitouni. Springer, 1998.
- Large deviations for performance analysis, Adam Shwartz & Alan Weiss. Chapman & Hall, 1995.
Teaching materials
Supplemental notes
- Common random variables [pdf]
- Cramér's theorem [pdf]
- LDP for single-server queue [pdf]
- Topology reference [pdf]
- Useful abstract LDPs [pdf] and concrete LDPs [pdf]
- Sample path LDP for traffic [pdf]
- A note on the Calculus of Variations [pdf]
- Examinable material [pdf]