Large Deviations for Gaussian Queues – Modelling Communication Networks

Michel Mandjes, Centre for Mathematics and Computer Science (CWI) Amsterdam, The Netherlands, and Professor, Faculty of Engineering, University of Twente. At CWI Mandjes is a senior researcher and Director of the Advanced Communications Network group. He has published for 60 papers on queuing theory, networks, scheduling, and pricing of networks.

Preface and acknowledgments. 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.