Performance analysis of communications networks and systems

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

The Edinburgh Building, Cambridge cb2 2ru, UK

First published in print format

isbn-13 978-0-521-85515-0

isbn-13 978-0-511-16917-5

© Cambridge University Press 2006

2006

Information on this title: www.cambridge.org/9780521855150

This publication is in copyright. Subject to statutory exception and to the provision of

relevant collective licensing agreements, no reproduction of any part may take place

without the written permission of Cambridge University Press.

isbn-10 0-511-16917-5

isbn-10 0-521-85515-2

Cambridge University Press has no responsibility for the persistence or accuracy of urls

for external or third-party internet websites referred to in this publication, and does not

guarantee that any content on such websites is, or will remain, accurate or appropriate.

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org

hardback

eBook (NetLibrary)

eBook (NetLibrary)

hardback

Waar een wil is, is een weg.

to my father

to my wife Saskia

and my sons Vincent, Nathan and Laurens

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 Z of the scaled random variables Zn 233

12.3 The Probability of Extinction of a Branching Process 237

12.4 Asymptotic behavior of Z 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 m 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 NQ with exponential link

weights 349

16.3 The hopcount kQ in the URT 354

16.4 The weight of the shortest path 359

16.5 The flooding time WQ 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

16.9 Problems 385

17 The e!ciency of multicast 387

17.1 General results for jQ (p) 388

17.2 The random graph Js (Q) 392

17.3 The n-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): jQ (p) for random graphs 410

17.7 Proof of Theorem 17.3.1: jQ (p) for n-ary trees 414

17.8 Problem 416

18 The hopcount to an anycast group 417

18.1 Introduction 417

18.2 General analysis 419

18.3 The n-ary tree 423

18.4 The uniform recursive tree (URT) 424

18.5 Approximate analysis 431

18.6 The performance measure  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

Preface

Performance analysis belongs to the domain of applied mathematics. The

major domain of application in this book concerns telecommunications sys￾tems and networks. We will mainly use stochastic analysis and probability

theory to address problems in the performance evaluation of telecommuni￾cations systems and networks. The first chapter will provide a motivation

and a statement of several problems.

This book aims to present methods rigorously, hence mathematically, with

minimal resorting to intuition. It is my belief that intuition is often gained

after the result is known and rarely before the problem is solved, unless the

problem is simple. Techniques and terminologies of axiomatic probability

(such as definitions of probability spaces, filtration, measures, etc.) have

been omitted and a more direct, less abstract approach has been adopted.

In addition, most of the important formulas are interpreted in the sense of

“What does this mathematical expression teach me?” This last step justifies

the word “applied”, since most mathematical treatises do not interpret as

it contains the risk to be imprecise and incomplete.

The field of stochastic processes is much too large to be covered in a single

book and only a selected number of topics has been chosen. Most of the top￾ics are considered as classical. Perhaps the largest omission is a treatment

of Brownian processes and the many related applications. A weak excuse

for this omission (besides the considerable mathematical complexity) is that

Brownian theory applies more to physics (analogue fields) than to system

theory (discrete components). The list of omissions is rather long and only

the most noteworthy are summarized: recent concepts such as martingales

and the coupling theory of stochastic variables, queueing networks, schedul￾ing rules, and the theory of long-range dependent random variables that cur￾rently governs in the Internet. The confinement to stochastic analysis also

excludes the recent new framework, called Network Calculus by Le Boudec

and Thiran (2001). Network calculus is based on min-plus algebra and has

been applied to (Inter)network problems in a deterministic setting.

As prerequisites, familiarity with elementary probability and the knowl￾edge of the theory of functions of a complex variable are assumed. Parts in

the text in small font refer to more advanced topics or to computations that

can be skipped at first reading. Part I (Chapters 2—6) reviews probability

theory and it is included to make the remainder self-contained. The book

essentially starts with Chapter 7 (Part II) on Poisson processes. The Pois￾xi

xii Preface

son process (independent increments and discontinuous sample paths) and

Brownian motion (independent increments but continuous sample paths)

are considered to be the most important basic stochastic processes. We

briefly touch upon renewal theory to move to Markov processes. The theory

of Markov processes is regarded as a fundament for many applications in

telecommunications systems, in particular queueing theory. A large part

of the book is consumed by Markov processes and its applications. The

last chapters of Part II dive into queueing theory. Inspired by intriguing

problems in telephony at the beginning of the twentieth century, Erlang

has pushed queueing theory to the scene of sciences. Since his investiga￾tions, queueing theory has grown considerably. Especially during the last

decade with the advent of the Asynchronous Transfer Mode (ATM) and the

worldwide Internet, many early ideas have been refined (e.g. discrete-time

queueing theory, large deviation theory, scheduling control of prioritized

flows of packets) and new concepts (self-similar or fractal processes) have

been proposed. Part III covers current research on the physics of networks.

This Part III is undoubtedly the least mature and complete. In contrast to

most books, I have chosen to include the solutions to the problems in an

Appendix to support self-study.

I am grateful to colleagues and students whose input has greatly improved

this text. Fernando Kuipers and Stijn van Langen have corrected a large

number of misprints. Together with Fernando, Milena Janic and Almer￾ima Jamakovic have supplied me with exercises. Gerard Hooghiemstra has

made valuable comments and was always available for discussions about

my viewpoints. Bart Steyaert eagerly gave the finer details of the generat￾ing function approach to the GI/D/m queue. Jan Van Mieghem has given

overall comments and suggestions beside his input with the computation of

correlations. Finally, I thank David Hemsley for his scrupulous corrections

in the original manuscript.

Although this book is intended to be of practical use, in the course of

writing it, I became more and more persuaded that mathematical rigor has

ample virtues of its own.

Per aspera ad astra

January 2006 Piet Van Mieghem

1

Introduction

The aim of this first chapter is to motivate why stochastic processes and

probability theory are useful to solve problems in the domain of telecommu￾nications systems and networks.

In any system, or for any transmission of information, there is always a

non-zero probability of failure or of error penetration. A lot of problems in

quantifying the failure rate, bit error rate or the computation of redundancy

to recover from hazards are successfully treated by probability theory. Often

we deal in communications with a large variety of signals, calls, source￾destination pairs, messages, the number of customers per region, and so on.

And, most often, precise information at any time is not available or, if it

is available, deterministic studies or simulations are simply not feasible due

to the large number of dierent parameters involved. For such problems, a

stochastic approach is often a powerful vehicle, as has been demonstrated

in the field of physics.

Perhaps the first impressing result of a stochastic approach was Boltz￾mann’s and Maxwell’s statistical theory. They studied the behavior of parti￾cles in an ideal gas and described how macroscopic quantities as pressure and

temperature can be related to the microscopic motion of the huge amount

of individual particles. Boltzmann also introduced the stochastic notion of

the thermodynamic concept of entropy V,

V = n log Z

where Z denotes the total number of ways in which the ensembles of parti￾cles can be distributed in thermal equilibrium and where n is a proportion￾ality factor, afterwards attributed to Boltzmann as the Boltzmann constant.

The pioneering work of these early physicists such as Boltzmann, Maxwell

and others was the germ of a large number of breakthroughs in science.

Shortly after their introduction of stochastic theory in classical physics, the

1

2 Introduction

theory of quantum mechanics (see e.g. Cohen-Tannoudji et al., 1977) was

established. This theory proposes that the elementary building blocks of

nature, the atom and electrons, can only be described in a probabilistic

sense. The conceptually di!cult notion of a wave function whose squared

modulus expresses the probability that a set of particles is in a certain state

and the Heisenberg’s uncertainty relation exclude in a dramatic way our

deterministic, macroscopic view on nature at the fine atomic scale.

At about the same time as the theory of quantum mechanics was being

created, Erlang applied probability theory to the field of telecommunica￾tions. Erlang succeeded to determine the number of telephone input lines

p of a switch in order to serve QV customers with a certain probability s.

Perhaps his most used formula is the Erlang E formula (14.17), derived in

Section 14.2.2,

Pr [QV = p] =

p

p!

Pp

m=0

m

m!

where the load or tra!c intensity  is the ratio of the arrival rate of calls to

the telephone local exchange or switch over the processing rate of the switch

per line. By equating the desired blocking probability s = Pr [QV = p], say

s = 1034, the number of input lines p can be computed for each load .

Due to its importance, books with tables relating s,  and p were published.

Another pioneer in the field of communications that deserves to be men￾tioned is Shannon. Shannon explored the concept of entropy V. He in￾troduced (see e.g. Walrand, 1998) the notion of the Shannon capacity of a

channel, the maximum rate at which bits can be transmitted with arbitrary

small (but non zero) probability of errors, and the concept of the entropy

rate of a source which is the minimum average number of bits per sym￾bol required to encode the output of a source. Many others have extended

his basic ideas and so it is fair to say that Shannon founded the field of

information theory.

A recent important driver in telecommunication is the concept of qual￾ity of service (QoS). Customers can use the network to transmit dierent

types of information such as pictures, files, voice, etc. by requiring a spe￾cific level of service depending on the type of transmitted information. For

example, a telephone conversation requires that the voice packets arrive at

the receiver G ms later, while a file transfer is mostly not time critical but

requires an extremely low information loss probability. The value of the

mouth-to-ear delay G is clearly related to the perceived quality of the voice

conversation. As long as G ? 150 ms, the voice conversation has toll qual￾ity, which is roughly speaking, the quality that we are used to in classical