Large Deviations for Gaussian Queues: Modelling Communication Networks

1 Introduction.

Part A: Gaussian traffic and large deviations.

2 The Gaussian source model.

2.1 Modeling network traffic.

2.2 Notation and preliminaries on Gaussian random variables.

2.3 Gaussian sources.

2.4 Generic examples-long-range dependence and smoothness.

2.5 Other useful Gaussian source models.

2.6 Applicability of Gaussian source models for network traffic.

3 Gaussian sources: validation, justification.

3.1 Validation.

3.2 Convergence of on-off traffic to a Gaussian process.

4 Large deviations for Gaussian processes.

4.1 Cram´er's theorem.

4.2 Schilder's theorem.

Part B: Large deviations of Gaussian queues.

5 Gaussian queues: an introduction.

5.1 Lindley's recursion, the steady-state buffer content.

5.2 Gaussian queues.

5.3 Special cases: Brownian motion and Brownian bridge.

5.4 A powerful approximation.

5.5 Asymptotics.

5.6 Large-buffer asymptotics.

6 Logarithmic many-sources asymptotics.

6.1 Many-sources asymptotics: the loss curve.

6.2 Duality between loss curve and variance function.

6.3 The buffer-bandwidth curve is convex.

7 Exact many-sources asymptotics.

7.1 Slotted time: results.

7.2 Slotted time: proofs.

7.3 Continuous time: results.

7.4 Continuous time: proofs.

8 Simulation.

8.1 Determining the simulation horizon.

8.2 Importance sampling algorithms.

8.3 Asymptotic efficiency.

8.4 Efficient estimation of the overflow probability.

9 Tandem and priority queues.

9.1 Tandem: model and preliminaries.

9.2 Tandem: lower bound on the decay rate.

9.3 Tandem: tightness of the decay rate.

9.4 Tandem: properties of the input rate path.

9.5 Tandem: examples.

9.6 Priority queues.

10 Generalized processor sharing.

10.1 Preliminaries on GPS.

10.2 Generic upper and lower bound on the overflow probability.

10.3 Lower bound on the decay rate: class 2 in underload.

10.4 Upper bound on the decay rate: class 2 in underload.

10.5 Analysis of the decay rate: class 2 in overload.

10.6 Discussion of the results.

10.7 Delay asymptotics.

11 Explicit results for short-range dependent inputs.

11.1 Asymptotically linear variance; some preliminaries.

11.2 Tandem queue with srd input.

11.3 Priority queue with srd input.

11.4 GPS queue with srd input.

11.5 Concluding remarks.

12 Brownian queues.

12.1 Single queue: detailed results.

12.2 Tandem: distribution of the downstream queue.

12.3 Tandem: joint distribution.

Part C: Applications.

13 Weight setting in GPS.

13.1 An optimal partitioning approach to weight setting.

13.2 Approximation of the overflow probabilities.

13.3 Fixed weights.

13.4 Realizable region.

14 A link dimensioning formula and empirical support.

14.1 Objectives, modeling, and analysis.

14.2 Numerical study.

14.3 Empirical study.

14.4 Implementation aspects.

15 Link dimensioning: indirect variance estimation.

15.1 Theoretical foundations.

15.2 Implementation issues.

15.3 Error analysis of the inversion procedure.

15.4 Validation.

16 A framework for bandwidth trading.

16.1 Bandwidth trading.

16.2 Model and preliminaries.

16.3 Single-link network.

16.4 Gaussian traffic; utility as a function of loss.

16.5 Sanov's theorem and its inverse.

16.6 Estimation of loss probabilities.

16.7 Numerical example.

Bibliography.

Index.