Table of Contents
Preface xi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Networks 2
1.3 Traffic 3
1.4 Queues 5
1.5 Structure of the book 5
1.6 Bibliography 6
Chapter 2 Exponential Distribution 9
2.1 Definition 9
2.2 Discrete analog 10
2.3 An amnesic distribution 12
2.4 Minimum of exponential variables 13
2.5 Sum of exponential variables 15
2.6 Random sum of exponential variables 16
2.7 A limiting distribution 16
2.8 A "very" random variable 17
2.9 Exercises 18
2.10 Solution to the exercises 20
Chapter 3 Poisson Processes 23
3.1 Definition 23
3.2 Discrete analog 25
3.3 An amnesic process 27
3.4 Distribution of the points of a Poisson process 28
3.5 uperposition of Poisson processes 29
3.6 Subdivision of a Poisson process 30
3.7 A limiting process 30
3.8 A'Very" random process 30
3.9 Exercises 31
3.10 Solution to the exercises 32
Chapter 4 Markov Chains 35
4.1 Definition 36
4.2 Transition probabilities 36
4.3 Periodicity 37
4.4 Balance equations 38
4.5 Stationary measure 38
4.6 Stability and ergodicity 39
4.7 Finite state space 40
4.8 Recurrence and transience 41
4.9 Frequency of transition 42
4.10 Formula of conditional transitions 43
4.11 Chain in reverse time 43
4.12 Reversibility 44
4.13 Kolmogorov's criterion 46
4.14 Truncation of a Markov chain 47
4.15 Random walk 49
4.16 Exercises 51
4.17 Solution to the exercises 52
Chapter 5 Markov Processes 57
5.1 Definition 57
5.2 Transition rates 58
5.3 Discrete analog 59
5.4 Balance equations 60
5.5 Stationary measure 61
5.6 Stability and ergodicity 61
5.7 Recurrence and transience 63
5.8 Frequency of transition 63
5.9 Virtual transitions 64
5.10 Embedded chain 66
5.11 Formula of conditional transitions 68
5.12 Process in reverse time 68
5.13 Reversibility 70
5.14 Kolmogorov's criterion 70
5.15 Truncation of a reversible process 71
5.16 Product of independent Markov processes 73
5.17 Birth-death processes 74
5.18 Exercises 78
5.19 Solution to the exercises 78
Chapter 6 Queues 87
6.1 Kendall's notation 87
6.2 Traffic and load 88
6.3 Service discipline 90
6.4 Basic queues 91
6.5 A general queue 97
6.6 Little's formula 99
6.7 PASTA property 101
6.8 Insensitivity 101
6.9 PoUaczek-Khinchin's formula 102
6.10 The observer paradox 105
6.11 Exercises 108
6.12 Solution to the exercises 111
Chapter 7 Queuing Networks 119
7.1 Jackson networks 119
7.2 Traffic equations 120
7.3 Stationary distribution 122
7.4 Musta property 124
7.5 Closed networks 125
7.6 Whittle networks 127
7.7 Kelly networks 129
7.8 Exercises 131
7.9 Solution to the exercises 133
Chapter 8 Circuit Traffic 141
8.1 Erlang's model 141
8.2 Erlang's formula 142
8.3 Engset's formula 145
8.3.1 Model without blocking 146
8.3.2 Model with blocking 147
8.4 Erlang's waiting formula 149
8.4.1 Waiting probability 149
8.4.2 Mean waiting time 150
8.5 The multiclass Erlang model 151
8.6 Kaufman-Roberts formula 154
8.7 Network models 155
8.8 Decoupling approximation 157
8.9 Exercises 157
8.10 Solutions to the exercises 160
Chapter 9 Real-time Traffic 167
9.1 Flows and packets 167
9.2 Packet-level model 168
9.3 Flow-level model 171
9.4 Congestion rate 173
9.5 Mean throughput 174
9.6 Loss rate 176
9.7 Multirate model 177
9.8 Recursive formula 179
9.9 Network models 179
9.10 Gaussian approximation 181
9.11 Exercises 183
9.12 Solution to the exercises 185
Chapter 10 Elastic Traffic 191
10.1 Bandwidth sharing 191
10.2 Congestion rate 194
10.3 Mean throughput 195
10.4 Loss rate 197
10.5 Multirate model 199
10.6 Recursive formula 202
10.7 Network model 204
10.8 Exercises 205
10.9 Solution to the exercises 208
Chapter 11 Network Performance 215
11.1 IP access networks 215
11.1.1 Poisson arrivals 216
11.1.2 Finite population 217
11.1.3 Approximation 218
11.2 2G mobile networks 219
11.2.1 Voice traffic 219
11.2.2 Data traffic 221
11.3 3G mobile networks 223
11.3.1 Uplink 223
11.3.2 Downlink 225
11.4 3G+ mobile networks 228
11.4.1 Homogeneous case 228
11.4.2 Heterogeneous case 228
11.5 WiFi access networks 231
11.5.1 UDP traffic 233
11.5.2 TCP traffic 236
11.5.3 Random traffic 237
11.6 Data centers 238
11.6.1 Static routing 238
11.6.2 Greedy routing 239
11.6.3 Adaptive routing 240
11.7 Cloud computing 241
11.8 Exercises 242
11.9 Solution to the exercises 245
Index 251
