Large deviations for Gaussian queues: modelling communication networks

Michel Mandjes9780470015230, 9780470515082, 0470015233

In recent years the significance of Gaussian processes to communication networks has grown considerably. The inherent flexibility of the Gaussian traffic model enables the analysis, in a single mathematical framework, of systems with both long-range and short-range dependent input streams.
Large Deviations for Gaussian Queues demonstrates how the Gaussian traffic model arises naturally, and how the analysis of the corresponding queuing model can be performed. The text provides a general introduction to Gaussian queues, and surveys recent research into the modelling of communications networks. Coverage includes: Discussion of the theoretical concepts and practical aspects related to Gaussian traffic models. Analysis of recent research asymptotic results for Gaussian queues, both in the large-buffer and many-sources regime. An emphasis on rare-event analysis, relying on a variety of asymptotic techniques. Examination of single-node FIFO queuing systems, as well as queues operating under more complex scheduling disciplines, and queuing networks. A set of illustrative examples that directly relate to important practical problems in communication networking. A large collection of instructive exercises and accompanying solutions.
Large Deviations for Gaussian Queues assumes minimal prior knowledge. It is ideally suited for postgraduate students in applied probability, operations research, computer science and electrical engineering. The book’s self-contained style makes it perfect for practitioners in the communications networking industry and for researchers in related areas.

---

Table of contents :
Large Deviations for Gaussian Queues……Page 4
Contents……Page 8
Preface and acknowledgments……Page 12
1 Introduction……Page 14
Part A: Gaussian traffic and large deviations……Page 20
2.1 Modeling network traffic……Page 22
2.2 Notation and preliminaries on Gaussian random variables……Page 24
2.3 Gaussian sources……Page 25
2.4 Generic examples–long-range dependence and smoothness……Page 27
2.5 Other useful Gaussian source models……Page 29
2.6 Applicability of Gaussian source models for network traffic……Page 35
3 Gaussian sources: validation, justification……Page 38
3.1 Validation……Page 39
3.2 Convergence of on-off traffic to a Gaussian process……Page 43
4.1 Cramér’s theorem……Page 50
4.2 Schilder’s theorem……Page 56
Part B: Large deviations of Gaussian queues……Page 66
5.1 Lindley’s recursion, the steady-state buffer content……Page 68
5.2 Gaussian queues……Page 71
5.3 Special cases: Brownian motion and Brownian bridge……Page 73
5.4 A powerful approximation……Page 75
5.5 Asymptotics……Page 77
5.6 Large-buffer asymptotics……Page 79
6.1 Many-sources asymptotics: the loss curve……Page 84
6.2 Duality between loss curve and variance function……Page 92
6.3 The buffer-bandwidth curve is convex……Page 101
7 Exact many-sources asymptotics……Page 104
7.1 Slotted time: results……Page 105
7.2 Slotted time: proofs……Page 106
7.3 Continuous time: results……Page 109
7.4 Continuous time: proofs……Page 111
8 Simulation……Page 120
8.1 Determining the simulation horizon……Page 121
8.2 Importance sampling algorithms……Page 124
8.3 Asymptotic efficiency……Page 126
8.4 Efficient estimation of the overflow probability……Page 127
9 Tandem and priority queues……Page 132
9.1 Tandem: model and preliminaries……Page 134
9.2 Tandem: lower bound on the decay rate……Page 136
9.3 Tandem: tightness of the decay rate……Page 141
9.4 Tandem: properties of the input rate path……Page 144
9.5 Tandem: examples……Page 147
9.6 Priority queues……Page 149
10 Generalized processor sharing……Page 158
10.1 Preliminaries on GPS……Page 160
10.2 Generic upper and lower bound on the overflow probability……Page 161
10.3 Lower bound on the decay rate: class 2 in underload……Page 165
10.4 Upper bound on the decay rate: class 2 in underload……Page 167
10.5 Analysis of the decay rate: class 2 in overload……Page 172
10.6 Discussion of the results……Page 173
10.7 Delay asymptotics……Page 175
11.1 Asymptotically linear variance; some preliminaries……Page 184
11.2 Tandem queue with srd input……Page 188
11.3 Priority queue with srd input……Page 192
11.4 GPS queue with srd input……Page 198
11.5 Concluding remarks……Page 203
12.1 Single queue: detailed results……Page 206
12.2 Tandem: distribution of the downstream queue……Page 209
12.3 Tandem: joint distribution……Page 213
Part C: Applications……Page 220
13 Weight setting in GPS……Page 222
13.1 An optimal partitioning approach to weight setting……Page 223
13.2 Approximation of the overflow probabilities……Page 227
13.3 Fixed weights……Page 230
13.4 Realizable region……Page 232
14 A link dimensioning formula and empirical support……Page 242
14.1 Objectives, modeling, and analysis……Page 245
14.2 Numerical study……Page 250
14.3 Empirical study……Page 254
14.4 Implementation aspects……Page 258
15 Link dimensioning: indirect variance estimation……Page 262
15.1 Theoretical foundations……Page 264
15.2 Implementation issues……Page 268
15.3 Error analysis of the inversion procedure……Page 269
15.4 Validation……Page 276
16.1 Bandwidth trading……Page 286
16.2 Model and preliminaries……Page 289
16.3 Single-link network……Page 292
16.4 Gaussian traffic; utility as a function of loss……Page 298
16.5 Sanov’s theorem and its inverse……Page 300
16.6 Estimation of loss probabilities……Page 305
16.7 Numerical example……Page 311
Bibliography……Page 316
Index……Page 338