Queues Applied to Telecoms

Toky Basilide Ravaliminoarimalalason holds a PhD in Cognitive Sciences applied to telecommunications and is a telecommunications engineer. He teaches at the Polytechnic Higher School, the Doctoral School in Engineering Sciences and Techniques and Innovation at the University of Antananarivo, Madagascar. He is also responsible for the radio planning and innovation of an African telecommunications operators group based in Madagascar. Falimanana Randimbindrainibe is Professor at the Polytechnic Higher School, the Doctoral School in Engineering Sciences and Techniques and Innovation at the University of Antananarivo, Madagascar.

Notations xi

Preface xxi

Part 1 Typical Processes in Queues 1

Chapter 1 The Poisson Process 3

1.1 Review of the exponential distribution 3

1.1.1 Definitions 3

1.1.2 The properties of an exponential distribution 4

1.2 Poisson process 10

1.2.1 Definitions 10

1.2.2 Properties of the Poisson process 12

1.3 Exercises 16

Chapter 2 Markov Chains 21

2.1 Markov chains in discrete time 21

2.1.1 Definitions 21

2.1.2 Evolution of a stochastic vector over time 26

2.1.3 Asymptotic behavior 30

2.1.4 Holding time in a state 32

2.1.5 Time-reversible chain 33

2.1.6 Reversible Markov chains 34

2.1.7 Kolmogorov’s criterion 34

2.2 Markov chains in continuous time 35

2.2.1 Definitions 35

2.2.2 Evolution over time 38

2.2.3 Resolving the state equation 41

2.2.4 Asymptotic behavior 42

2.3 Birth and death process 43

2.3.1 Definition 43

2.3.2 Infinitesimal stochastic generator 43

2.3.3 Stationary distribution 44

2.4 Exercises 45

Part 2 Queues 51

Chapter 3 Common Queues 53

3.1 Arrival process of customers in a queue 53

3.1.1 The Poisson process 53

3.1.2 Using the Poisson distribution Rho(lambda) 54

3.1.3 Exponential distribution of delay times 55

3.2 Queueing systems 57

3.2.1 Notation for queueing systems 58

3.2.2 Little distributions 59

3.2.3 Offered traffic 60

3.3 M/M/1 queue 60

3.3.1 Stationary distribution 61

3.3.2 Characteristics of the M/M/1 queue 62

3.3.3 Introducing a factor of impatience 64

3.4 M/M/(Infinity) queue 65

3.5 M/M/n/n queue 66

3.5.1 Stationary distribution 67

3.5.2 Erlang-B formula 67

3.5.3 Characteristics of the M/M/n/n queue 68

3.6 M/M/n queue 68

3.6.1 Stationary distribution 69

3.6.2 Erlang-C formula 70

3.6.3 Characteristics of the M/M/n queue 70

3.7 M/GI/1 queue 71

3.7.1 Stationary distribution 71

3.7.2 Characteristics of the M/GI/1 queue 73

3.8 Exercises 74

Chapter 4 Product-Form Queueing Networks 79

4.1 Jackson networks 80

4.1.1 Definition of a Jackson network 80

4.1.2 Stationary distribution 81

4.1.3 The particular case of the Jackson theorem for open networks 84

4.1.4 Generalization of Jackson networks: BCMP networks 84

4.2 Whittle networks 85

4.2.1 Definition of a Whittle network 85

4.2.2 Stationary distribution 88

4.2.3 Properties of a Whittle network 88

4.3 Exercise 89

Part 3 Teletraffic 91

Chapter 5 Notion of Teletraffic 93

5.1 Teletraffic and its objectives 93

5.2 Definitions 94

5.2.1 Measures in teletraffic 94

5.2.2 Sources and resources 95

5.2.3 Requests and holding time 96

5.2.4 Traffic 97

5.3 Measuring and foreseeing traffic 101

5.3.1 Traffic and service quality 101

5.3.2 Measuring traffic 102

5.3.3 Markovian model of traffic 102

5.3.4 Economy and traffic forecasting 103

5.4 Exercises 103

Chapter 6 Resource Requests and Activity 107

6.1 Infinite number of sources 107

6.1.1 Distribution of requests in continuous time 107

6.1.2 Distribution of requests in discrete time 110

6.1.3 Duration of activity distributions 113

6.1.4 Distribution of busy sources 115

6.2 Finite number of sources 115

6.2.1 Modeling with birth and death processes 116

6.2.2 Distribution of requests 117

6.3 Traffic peaks and randomness 118

6.3.1 Traffic peaks 118

6.3.2 Pure chance traffic 119

6.4 Recapitulation 119

6.5 Exercises 120

Chapter 7 The Teletraffic of Loss Systems 123

7.1 Loss systems 124

7.1.1 Definitions 124

7.1.2 Blocking and loss 124

7.2 The Erlang model 126

7.2.1 Infinite number of resources 127

7.2.2 Finite number of resources 128

7.2.3 Erlang-B formula 131

7.2.4 Dimensioning principles 132

7.3 Engset model 133

7.3.1 Sufficient number of resources 133

7.3.2 Insufficient number of resources 135

7.3.3 On the Engset loss formula 137

7.4 Imperfect loss systems 137

7.4.1 Loss probability in an imperfect system with limited and constant accessibility 137

7.4.2 Losses in a system with limited and variable accessibility 138

7.5 Exercises 138

Chapter 8 Teletraffic in Delay Systems 143

8.1 Delay system 143

8.1.1 Description 143

8.1.2 Characteristics of delay 144

8.2 Erlang model 145

8.2.1 Infinitely long queue 145

8.2.2 Erlang-C formula 146

8.2.3 Distribution of delays 147

8.3 Finite waiting capacity model 150

8.3.1 Queues of finite length 150

8.3.2 Limitations affecting the delay 151

8.4 Palm model 151

8.4.1 M/M/n/N/N queue 152

8.4.2 Characteristics of traffic 153

8.5 General distribution model for activity 153

8.5.1 The Pollaczek--Khinchine formula 153

8.5.2 Activity with a constant duration 154

8.6 Exercises 155

Part 4 Answers to Exercises 161

Chapter 9 Chapter 1 Exercises 163

Chapter 10 Chapter 2 Exercises 171

Chapter 11 Chapter 3 Exercises 185

Chapter 12 Chapter 4 Exercise 197

Chapter 13 Chapter 5 Exercises 201

Chapter 14 Chapter 6 Exercises 205

Chapter 15 Chapter 7 Exercises 207

Chapter 16 Chapter 8 Exercises 211

Part 5 Appendices 219

Appendix 1 221

Appendix 2 227

References 233

Index 235