PERFORMANCE ANALYSIS OF COMMUNICATIONS NETWORKS AND SYSTEMS PIET VAN MIEGHEM Delft University of Technology cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press TheEdinburghBuilding,Cambridgecb22ru,UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Informationonthistitle:www.cambrid ge.org/9780521855150 © Cambridge University Press 2006 Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionof relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. Firstpublishedinprintformat 2006 isbn-13 978-0-511-16917-5 eBook (NetLibrary) isbn-10 0-511-16917-5 eBook (NetLibrary) isbn-13 978-0-521-85515-0 hardback isbn-10 0-521-85515-2 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls forexternalorthird-partyinternetwebsitesreferredtointhispublication,anddoesnot guaranteethatanycontentonsuchwebsitesis,orwillremain,accurateorappropriate. Waar een wil is, is een weg. to my father to my wife Saskia andmysonsVincent,NathanandLaurens Contents Preface xi 1 Introduction 1 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 3.7 Problems 59 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 v vi Contents 4.4 Examples of the non-linear transformation method 74 4.5 Linear combination of independent auxiliary random variables 78 4.6 Problem 82 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 Hölder, 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 7.6 Problems 132 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 8.5 Problems 155 9 Discrete-time Markov chains 157 9.1 Definition 157 Contents vii 9.2 Discrete-time Markov chain 158 9.3 The steady-state of a Markov chain 168 9.4 Problems 177 10 Continuous-time Markov chains 179 10.1 Definition 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 10.8 Problems 199 11 Applications of Markov chains 201 11.1 Discrete Markov chains and independent random vari- ables 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 11.7 Problems 228 12 Branching processes 229 12.1 The probability generating function 231 12.2 The limit (cid:90) of the scaled random variables (cid:90) 233 (cid:110) 12.3 The Probability of Extinction of a Branching Process 237 12.4 Asymptotic behavior of (cid:90) 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 Bene˘s 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 viii Contents 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 14.9 Problems 312 Part III Physics of networks 317 15 General characteristics of graphs 319 15.1 Introduction 319 15.2 The number of paths with (cid:109) 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 15.8 Problems 346 16 The Shortest Path Problem 347 16.1 The shortest path and the link weight structure 348 16.2 The shortest path tree in (cid:78) with exponential link (cid:81) weights 349 16.3 The hopcount (cid:107) in the URT 354 (cid:81) 16.4 The weight of the shortest path 359 16.5 The flooding time (cid:87) 361 (cid:81) 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 16.9 Problems 385 17 The e(cid:33)ciency of multicast 387 17.1 General results for (cid:106) ((cid:112)) 388 (cid:81) 17.2 The random graph (cid:74) ((cid:81)) 392 (cid:115) 17.3 The (cid:110)-ary tree 401 Contents ix 17.4 The Chuang—Sirbu law 404 17.5 Stability of a multicast shortest path tree 407 17.6 Proof of (17.16): (cid:106) ((cid:112)) for random graphs 410 (cid:81) 17.7 Proof of Theorem 17.3.1: (cid:106) ((cid:112)) for (cid:110)-ary trees 414 (cid:81) 17.8 Problem 416 18 The hopcount to an anycast group 417 18.1 Introduction 417 18.2 General analysis 419 18.3 The (cid:110)-ary tree 423 18.4 The uniform recursive tree (URT) 424 18.5 Approximate analysis 431 18.6 The performance measure (cid:20) in exponentially growing trees 432 Appendix A Stochastic matrices 435 Appendix B Algebraic graph theory 471 Appendix C Solutions of problems 493 Bibliography 523 Index 529