Performance Analysis of Communications Networks and Systems

PERFORMANCE ANALYSIS OF COMMUNICATIONS NETWORKS AND SYSTEMS......Page 2
Contents......Page 6
Preface......Page 12
1 Introduction......Page 14
Part I Probability theory......Page 20
2.1 Probability theory and set theory......Page 22
2.1.1 The inclusion-exclusion formula......Page 25
2.2 Discrete random variables......Page 29
2.2.1 The expectation......Page 30
2.2.2 The probability generating function......Page 31
2.2.3 The logarithm of the probability generating function......Page 32
2.3 Continuous random variables......Page 33
2.3.2 The expectation......Page 35
2.3.3 The probability generating function......Page 37
2.3.4 The logarithm of the probability generating function......Page 38
2.4 The conditional probability......Page 39
2.5.1 Discrete random variables......Page 41
2.5.2 The covariance......Page 42
2.5.3 The linear correlation coecient......Page 43
2.5.5 The sum of independent random variables......Page 45
2.6 Conditional expectation......Page 47
3.1.1 The Bernoulli distribution......Page 50
3.1.2 The binomial distribution......Page 51
3.1.3 The geometric distribution......Page 52
3.1.4 The Poisson distribution......Page 53
3.2.1 The uniform distribution......Page 56
3.2.2 The exponential distribution......Page 57
3.2.3 The Gaussian or normal distribution......Page 59
3.3.1 The sum of independent exponential random variables......Page 60
3.3.2 The sum of independent uniform random variables......Page 62
3.3.3 The chi-square distribution......Page 63
3.4.1 The maximum and minimum of a set of independent random variables......Page 64
3.4.2 Order statistics......Page 65
3.5 Examples of other distributions\r......Page 67
3.6.1 Discrete random variables......Page 71
3.7 Problems......Page 72
4.1.1 Generation of two independent Gaussian random variables......Page 74
4.1.2 The -joint Gaussian probability distribution function......Page 75
4.1.3 Generation of correlated Gaussian random variables......Page 79
4.2 Generation of correlated random variables......Page 80
4.3 The non-linear transformation method......Page 81
4.3.1 Properties of as a function of......Page 82
4.3.2 Boundary cases......Page 85
4.4.1 Correlated uniform random variables......Page 87
4.4.2 Correlated exponential random variables......Page 88
4.4.3 Correlated lognormal random variables......Page 90
4.5 Linear combination of independent auxiliary random variables......Page 91
4.5.2 Correlated exponential random variables......Page 94
4.6 Problem......Page 95
5.1 The minimum (maximum) and in“mum (supremum)......Page 96
5.2 Continuous convex functions......Page 97
5.3 Inequalities deduced from the Mean Value Theorem......Page 99
5.4 The Markov and Chebyshev inequalities......Page 100
5.5 The Hölder, Minkowski and Young inequalities......Page 103
5.6 The Gauss inequality......Page 105
5.7 The dominant pole approximation and large deviations......Page 107
6.1.1 Summability......Page 110
6.1.2 Convergence of a sequence of random variables......Page 112
6.1.3 List of general theorems......Page 113
6.2 Law of Large Numbers\r......Page 114
6.3 Central Limit Theorem\r......Page 116
6.4.1 Scaling laws......Page 117
6.4.2 The Law of Extremal Types......Page 119
6.4.3 Examples......Page 120
Part II Stochastic processes......Page 126
7.1.1 Introduction and de.nitions......Page 128
7.1.2 Modeling a stochastic process from measurements......Page 130
7.2 The Poisson process......Page 133
7.3 Properties of the Poisson process......Page 135
7.4 The nonhomogeneous Poisson process......Page 142
7.5 The failure rate function......Page 143
7.6 Problems......Page 145
8 Renewal theory......Page 150
8.1.1 The distribution of the waiting time......Page 151
8.1.2 The renewal function m(t) = E[N(t)]\r......Page 153
8.1.3 The renewal equation......Page 154
8.1.4 A generalization of the renewal equation......Page 155
8.2 Limit theorems......Page 157
8.3 The residual waiting time......Page 162
8.4 The renewal reward process......Page 166
8.5 Problems......Page 168
9.1 Definition......Page 170
9.2 Discrete-time Markov chain......Page 171
9.2.1 De.nitions and classi.cation......Page 174
9.2.2 The hitting time......Page 176
9.2.3 Transient and recurrent states......Page 178
9.3.1 The irreducible Markov chain......Page 181
9.3.2 The average number of visits to a recurrent state......Page 183
9.3.3 Example: the two-state Markov chain......Page 188
9.4 Problems......Page 190
10.1 Definition......Page 192
10.2.1 The infinitesimal generator......Page 193
10.2.2 Algebraic properties of the infinitesimal generator......Page 196
10.2.3 Exponential sojourn times......Page 197
10.3 Steady-state......Page 200
10.4 The embedded Markov chain......Page 201
10.4.1 Uniformization......Page 202
10.4.2 A sampled-time Markov chain......Page 205
10.5 The transitions in a continuous-time Markov chain......Page 206
10.6 Example: the two-state Markov chain in continuous-time......Page 208
10.7 Time reversibility......Page 209
10.8 Problems......Page 212
11.1 Discrete Markov chains and independent random variables......Page 214
11.2 The general random walk......Page 215
11.2.1 The probability of gambler’s ruin......Page 217
11.2.2 The steady-state......Page 220
11.3 Birth and death process......Page 221
11.3.1 The steady-state......Page 222
11.3.2 A pure birth process......Page 223
11.3.3 Constant rate birth and death process......Page 227
11.4 A random walk on a graph......Page 231
11.5 Slotted Aloha......Page 232
11.5.1 The Markov chain......Page 233
11.5.2 Eciency of slotted Aloha and the oered trac......Page 236
11.6.1 A Markov model of the web......Page 237
11.6.2 Computation of the PageRank steady-state vector......Page 240
11.7 Problems......Page 241
12 Branching processes......Page 242
12.1 The probability generating function......Page 244
12.2 The limit of the scaled random variables......Page 246
12.3 The Probability of Extinction of a Branching Process......Page 250
12.4 Asymptotic behavior of......Page 253
12.5 A geometric branching processes......Page 256
13.1 A queueing system......Page 260
13.1.1 The arrival process......Page 261
13.1.2 The service process......Page 262
13.1.3 The queueing process......Page 263
13.1.4 The Kendall notation for queueing systems......Page 264
13.2 The waiting process: Lindley s approach......Page 265
13.3 The Benes approach to the unfinished work......Page 269
13.3.1 A constant service rate......Page 274
13.3.2 The steady-state distribution of the virtual waiting time......Page 275
13.4 The counting process......Page 276
13.4.1 Queue observations......Page 277
13.5 PASTA......Page 279
13.6 Little s Law......Page 280
14.1 The M/M/1 queue......Page 284
14.1.1 The system content in steady-state......Page 285
14.1.2 The virtual waiting time......Page 286
14.1.3 The departure process from the M/M/1 queue......Page 288
14.2.1 The M/M/m queue......Page 289
14.2.2 The M/M/m/m queue......Page 292
14.2.3 The M/M/1/K queue......Page 295
14.3 The M/G/1 queue......Page 296
14.3.1 The system content in steady-state......Page 298
14.3.2 The waiting time in steady-state......Page 300
14.4 The GI/D/m queue......Page 302
14.4.1 The steady-state of the GI/D/m queue......Page 303
14.4.2 The waiting time in a GI/D/m system......Page 306
14.5 The M/D/1/K queue......Page 309
14.5.1 The pdf of the buer occupancy in the M/D/1 queue......Page 310
14.6 The N*D/D/1 queue......Page 313
14.7 The AMS queue......Page 317
14.8 The cell loss ratio......Page 322
14.9 Problems......Page 325
Part III Physics of networks......Page 330
15.1 Introduction......Page 332
15.2 The number of paths with hops......Page 334
15.3 The degree of a node in a graph......Page 335
15.4 Connectivity and robustness......Page 338
15.5 Graph metrics......Page 341
15.6 Random graphs......Page 342
15.6.1 The number ( ) of connected random graphs in the class ( )......Page 345
15.6.2 The Erdös and Rényi asymptotic analysis......Page 347
15.6.3 Connectivity and degree......Page 350
15.6.4 Size of the giant component......Page 351
15.7.1 Bi-directional search......Page 353
15.7.2 Sparse large graphs and a branching process......Page 355
15.8 Problems......Page 359
16 The Shortest Path Problem......Page 360
16.1 The shortest path and the link weight structure......Page 361
16.2.1 The Markov discovery process......Page 362
16.2.2 The uniform recursive tree......Page 364
16.3.1 Theory......Page 367
16.3.2 Application of the URT to the hopcount in the Internet......Page 370
16.4 The weight of the shortest path......Page 372
16.5 The flooding time......Page 374
16.5.1 The asymptotic law for flooding time......Page 375
16.6.1 Recursion for Prh()......Page 379
16.6.2 The Average Number of Degree Nodes in the URT......Page 381
16.6.3 The degree of the shortest path tree in the complete graph with i.i.d. exponential link weights......Page 384
16.7.1 The Kruskal growth process of the MST......Page 386
16.7.2 The average weight of the minimum spanning tree......Page 389
16.8.1 The case k = N:E[D^(N-1)_N]......Page 393
16.8.3 The general case: E[D^k_N]......Page 394
16.9 Problems......Page 398
17 The efficiency of multicast......Page 400
17.1 General results for g_N(m)......Page 401
17.2 The random graph G_p(N)......Page 405
17.2.1 The hopcount of the shortest path tree......Page 406
17.2.2 The weight of the shortest path tree......Page 412
17.3 The k-ary tree......Page 414
17.4.1 Validity range of the Chuang-Sirbu law......Page 417
17.4.2 The effective power exponent ( )......Page 418
17.5 Stability of a multicast shortest path tree......Page 420
17.6 Proof of(17.16): g_N(m) for random graphs......Page 423
17.7 Proof of Theorem 17.3.1: g_N(m) for k-ary trees......Page 427
17.8 Problem......Page 429
18.1 Introduction......Page 430
18.2 General analysis......Page 432
18.3 The k-ary tree......Page 436
18.4.1 Recursion for Pr [h(m)=j]......Page 437
18.4.2 Analysis of the recursion relation......Page 442
18.5 Approximate analysis......Page 444
18.6 The performance measure in exponentially growing trees......Page 445
A.1 Eigenvalues and eigenvectors......Page 448
A.2 Hermitian and real symmetric matrices......Page 456
A.3 Vector and matrix norms......Page 458
A.3.1 Properties of norms......Page 459
A.3.2 Applications of norms......Page 462
A.4.1 The eigenstructure......Page 463
A.4.2 Example: the two-state Markov chain......Page 467
A.4.3 The tendency towards the steady-state......Page 468
A.5.2.1 Tri-diagonal Toeplitz bandmatrix......Page 470
A.5.3 A triangular matrix complemented with one subdiagonal......Page 481
B.1 The adjacency and incidence matrix......Page 484
B.2 The eigenvalues of the adjacency matrix......Page 488
B.3 The stochastic matrix P\r......Page 497
B.4 Eigenvalues and connectivity......Page 499
B.5 Random matrix theory......Page 500
B.5.1 The spectrum of the random graph G_p(N)......Page 501
B.5.2 Wigner’s Semicircle Law......Page 502
C.1 Probability theory (Chapter 2)......Page 506
C.2 Correlation (Chapter 4)......Page 509
C.3 Poisson process (Chapter 7)......Page 510
C.4 Renewal theory (Chapter 8)......Page 513
C.5 Discrete-time Markov chains (Chapter 9)......Page 516
C.6 Continuous-time Markov processes (Chapter 10)......Page 519
C.8 Queueing (Chapters 13 and 14)......Page 521
C.9 General characteristics of graphs (Chapter 15)......Page 526
C.10 The uniform recursive tree (Chapter 16)......Page 528
C.11 The efficiency of multicast (Chapter 17)......Page 535
Bibliography......Page 536
Index......Page 542