Performance analysis of communications networks and systems / Piet Van Mieghem.

Format:

Book

Author/Creator:

Van Mieghem, Piet.

Contributor:

Engineering Book Fund.

Language:

English

Subjects (All):

Computer networks.

Stochastic analysis.

Physical Description:

xii, 530 pages : illustrations ; 26 cm

Place of Publication:

Cambridge, UK ; New York : Cambridge University Press, 2006.

Summary:

This rigorous and self-contained book describes mathematical and, in particular, stochastic methods to assess the performance of networked systems. It consists of three parts: the first is a review of probability theory; part II covers the classical theory of stochastic processes (Poisson, renewal, Markov and queueing theory) which are considered to be the basic building blocks for performance evaluation studies; part III focuses on the relatively new field of the physics of networks. This part deals with the recently obtained insight that many very different large complex networks - such as the Internet, World Wide Web, proteins, utility infrastructures, social networks - evolve and behave according to more general common scaling laws. This understanding is useful when assessing the end-to-end quality of communications services, for example in Internet telephony, real-time video, and interacting games. Containing problems and solutions, the book is ideal for graduate students taking courses in performance analysis.

Contents:

Part I Probability theory 7

2 Random variables 9

2.1 Probability theory and set theory 9

2.2 Discrete random variables 16

2.3 Continuous random variables 20

2.4 The conditional probability 26

2.5 Several random variables and independence 28

2.6 Conditional expectation 34

3 Basic distributions 37

3.1 Discrete random variables 37

3.2 Continuous random variables 43

3.3 Derived distributions 47

3.4 Functions of random variables 51

3.5 Examples of other distributions 54

3.6 Summary tables of probability distributions 58

4 Correlation 61

4.1 Generation of correlated Gaussian random variables 61

4.2 Generation of correlated random variables 67

4.3 The non-linear transformation method 68

4.4 Examples of the non-linear transformation method 74

4.5 Linear combination of independent auxiliary random variables 78

5 Inequalities 83

5.1 The minimum (maximum) and infimum (supremum) 83

5.2 Continuous convex functions 84

5.3 Inequalities deduced from the Mean Value Theorem 86

5.4 The Markov and Chebyshev inequalities 87

5.5 The Holder, Minkowski and Young inequalities 90

5.6 The Gauss inequality 92

5.7 The dominant pole approximation and large deviations 94

6 Limit laws 97

6.1 General theorems from analysis 97

6.2 Law of Large Numbers 101

6.3 Central Limit Theorem 103

6.4 Extremal distributions 104

Part II Stochastic processes 113

7 The Poisson process 115

7.1 A stochastic process 115

7.2 The Poisson process 120

7.3 Properties of the Poisson process 122

7.4 The nonhomogeneous Poisson process 129

7.5 The failure rate function 130

8 Renewal theory 137

8.1 Basic notions 138

8.2 Limit theorems 144

8.3 The residual waiting time 149

8.4 The renewal reward process 153

9 Discrete-time Markov chains 157

9.2 Discrete-time Markov chain 158

9.3 The steady-state of a Markov chain 168

10 Continuous-time Markov chains 179

10.2 Properties of continuous-time Markov processes 180

10.3 Steady-state 187

10.4 The embedded Markov chain 188

10.5 The transitions in a continuous-time Markov chain 193

10.6 Example: the two-state Markov chain in continuous-time 195

10.7 Time reversibility 196

11 Applications of Markov chains 201

11.1 Discrete Markov chains and independent random variables 201

11.2 The general random walk 202

11.3 Birth and death process 208

11.4 A random walk on a graph 218

11.5 Slotted Aloha 219

11.6 Ranking of webpages 224

12 Branching processes 229

12.1 The probability generating function 231

12.2 The limit W of the scaled random variables W[subscript k] 233

12.3 The Probability of Extinction of a Branching Process 237

12.4 Asymptotic behavior of W 240

12.5 A geometric branching processes 243

13 General queueing theory 247

13.1 A queueing system 247

13.2 The waiting process: Lindley's approach 252

13.3 The Benes approach to the unfinished work 256

13.4 The counting process 263

13.5 PASTA 266

13.6 Little's Law 267

14 Queueing models 271

14.1 The M/M/1 queue 271

14.2 Variants of the M/M/1 queue 276

14.3 The M/G/1 queue 283

14.4 The GI/D/m queue 289

14.5 The M/D/1/K queue 296

14.6 The N*D/D/1 queue 300

14.7 The AMS queue 304

14.8 The cell loss ratio 309

Part III Physics of networks 317

15 General characteristics of graphs 319

15.2 The number of paths with j hops 321

15.3 The degree of a node in a graph 322

15.4 Connectivity and robustness 325

15.5 Graph metrics 328

15.6 Random graphs 329

15.7 The hopcount in a large, sparse graph with unit link weights 340

16 The Shortest Path Problem 347

16.1 The shortest path and the link weight structure 348

16.2 The shortest path tree in K[subscript N] with exponential link weights 349

16.3 The hopcount h[subscript N] in the URT 354

16.4 The weight of the shortest path 359

16.5 The flooding time T[subscript N] 361

16.6 The degree of a node in the URT 366

16.7 The minimum spanning tree 373

16.8 The proof of the degree Theorem 16.6.1 of the URT 380

17 The efficiency of multicast 387

17.1 General results for g[subscript N](m) 388

17.2 The random graph G[subscript p](N) 392

17.3 The k-ary tree 401

17.4 The Chuang-Sirbu law 404

17.5 Stability of a multicast shortest path tree 407

17.6 Proof of (17.16): g[subscript N](m) for random graphs 410

17.7 Proof of Theorem 17.3.1: g[subscript N](m) for k-ary trees 414

18 The hopcount to an anycast group 417

18.2 General analysis 419

18.3 The k-ary tree 423

18.4 The uniform recursive tree (URT) 424

18.5 Approximate analysis 431

18.6 The performance measure [eta] in exponentially growing trees 432

Appendix A Stochastic matrices 435

Appendix B Algebraic graph theory 471

Appendix C Solutions of problems 493.

Notes:

Includes bibliographical references (pages 523-528) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Engineering Book Fund.

ISBN:

0521855152

OCLC:

61702434

Publisher Number:

9780521855150 (hbk.)

Online:

Publisher description