Big Queues

Synopsis

Big Queues aims to give a simple and elegant account of how large deviations theory can be applied to queueing problems. It begins with an elementary large deviations result (for i.i.d. random variables), which is then used to analyse some simple queueing models. For more complicated models, however, more powerful tools are useful—namely, those provided by abstract large deviations theory. Later chapters give an introduction to this theory, and develop a framework for applying it to queueing problems. This framework covers large-buffer limits, many-flows limits, and long-range dependence. The final chapter gives some applications to telecommunications.

Online extras

Readers who liked these may also like Big Queues

• Large deviations techniques and applications, Amir Dembo & Ofer Zeitouni, 1998.
• Large deviations for performance analysis, Adam Shwartz & Alan Weiss, 1995.
• Performance guarantees in communication networks, Cheng-Shang Chang, 2000.
• Stochastic process limits, Ward Whitt, 2001.

Contents

1. The single-server queue.

   The single-server queueing model. One-dimensional large deviations. Application to queues with large buffers. Application to queues with many sources.

2. Large deviations in Euclidean spaces.

   Some examples. Principle of the largest term. Large deviations principle. Cumulant generating functions. Convex duality. Cramér's theorem. Sanov's theorem for finite alphabets. A generalisation of Cramér's theorem.

3. More on the single-server queue.

   Queues with correlated inputs. Queues with many sources and power-law scalings. Queues with large buffers and power-law scaling.

4. Introduction to abstract large deviations.

   Topology and metric spaces. Definition of LDP. The contraction principle. Other useful LDP results.

5. Continuous queueing maps.

   Introduction. An example: queues with large buffers. The general approach. Continuous functions. Some convenient notation. Queues with infinite buffers. Queues with finite buffers. Queueing delay. Priority queues. Processor sharing. Departures from a queue. Conclusion.

6. Large-buffer scalings.

   The space of input processes. Large deviations for partial sums processes. Linear geodesics. Queues with infinite buffers. Queues with finite buffers. Queueing delay. Departure process. Mean rate of departures. Quasi-reversibility. Scaling properties of networks. Statistical inference for the tail-behaviour of queues.

7. Many-flows scalings.

   Traffic scaling. Topology for sample paths. The sample path LDP. Example sample path LDPs. Applying the contraction principle. Queues with infinite buffers. Queues with finite buffers. Overflow and underflow. Paths to overflow. Priority queues. Departures from a queue.

8. Long range dependence.

   What is long range dependence? Implications for queues. Sample path LDP for fractional Brownian motion. Scaling properties. How does long range dependence arise? Philosophical difficulties with LRD modelling.

9. Moderate deviations scalings.

   Motivation. Traffic processes. Queue scalings. Shared buffers. Mixed limits.

10. Interpretations.

    Effective bandwidths. Numerical estimates. A global approximation. Scaling laws. Types of traffic.