Queues Applied to Telecoms E-Book

Toky Basilide Ravaliminoarimalalason

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 291

Veröffentlichungsjahr: 2022

Beschreibung

From queues to telecoms. Queues are, of course, omnipresent in our world, at the bank, the supermarket, the shops, on the road... and yes, they also exist in the domain of telecoms. Queues Applied to Telecoms studies the theoretical aspect of these queues, from Poisson processes, Markov chains and queueing systems to queueing networks. The study of the use of their resources is addressed by the theory of teletraffic. This book also outlines the basic ideas in the theory of teletraffic, presenting the teletraffic of loss systems and waiting systems. However, some applications and explanations are more oriented towards the field of telecommunications, and this book contains lectures and more than sixty corrected exercises to cover these topics. On your marks....

Leseprobe

Contents

Cover

Title Page

Copyright Page

Notations

Preface

Part 1. Typical Processes in Queues

Chapter 1. The Poisson Process

1.1. Review of the exponential distribution

1.2. Poisson process

1.3. Exercises

Chapter 2. Markov Chains

2.1. Markov chains in discrete time

2.2. Markov chains in continuous time

2.3. Birth and death process

2.4. Exercises

Part 2. Queues

Chapter 3. Common Queues

3.1. Arrival process of customers in a queue

3.2. Queueing systems

3.3. M/M/1 queue

3.4. M/M/∞ queue

3.5. M/M/n/n queue

3.6. M/M/n queue

3.7. M/GI/1 queue

3.8. Exercises

Chapter 4. Product-Form Queueing Networks

4.1. Jackson networks

4.2. Whittle networks

4.3. Exercise

Part 3. Teletraffic

Chapter 5. Notion of Teletraffic

5.1. Teletraffic and its objectives

5.2. Definitions

5.3. Measuring and foreseeing traffic

5.4. Exercises

Chapter 6. Resource Requests and Activity

6.1. Infinite number of sources

6.2. Finite number of sources

6.3. Traffic peaks and randomness

6.4. Recapitulation

6.5. Exercises

Chapter 7. The Teletraffic of Loss Systems

7.1. Loss systems

7.2. The Erlang model

7.3. Engset model

7.4. Imperfect loss systems

7.5. Exercises

Chapter 8. Teletraffic in Delay Systems

8.1. Delay system

8.2. Erlang model

8.3. Finite waiting capacity model

8.4. Palm model

8.5. General distribution model for activity

8.6. Exercises

Part 4. Answers to Exercises

Chapter 9. Chapter 1 Exercises

Chapter 10. Chapter 2 Exercises

Chapter 11. Chapter 3 Exercises

Chapter 12. Chapter 4 Exercise

Chapter 13. Chapter 5 Exercises

Chapter 14. Chapter 6 Exercises

Chapter 15. Chapter 7 Exercises

Chapter 16. Chapter 8 Exercises

Part 5. Appendices

Appendix 1

Appendix 2

References

Index

Other titles from iSTE in Mechanical Engineering and Solid Mechanics

Wiley End User License Agreement

List of Figures

Chapter 1

Figure 1.1.

Minimum of exponential distributions

Figure 1.2.

Sum of exponential distributions

Figure 1.3.

Geometric sum of exponential distributions

Figure 1.4.

Punctual process

Figure 1.5.

Superposition of Poisson processes

Figure 1.6.

Subdivision of a Poisson process

Chapter 2

Figure 2.1.

Transition graph

Figure 2.2.

Markov chain for a geometric distribution

Figure 2.3.

Time-reversible Markov chain

Figure 2.4.

Instants of changes of state

Figure 2.5.

Transition graph of a Markov chain in continuous time

Figure 2.6.

Birth and death process

Chapter 3

Figure 3.1.

Transition graph of the exponential distribution

Figure 3.2.

Infinitesimal generator of the exponential distribution

Figure 3.3.

Queueing system

Chapter 4

Figure 4.1.

Jackson routing

Chapter 5

Figure 5.1.

Requests and activity

Figure 5.2.

Breakdown of traffic into its different components

Figure 5.3.

Traffic carried by a GSM BTS in Antananarivo, Madagascar.

Chapter 6

Figure 6.1.

Birth and death process of requests

Chapter 7

Figure 7.1.

Comparison of Erlang and Poisson distributions.

Figure 7.2.

Erlang-B chart.

Chapter 8

Figure 8.1.

Abacus for Erlang-C formula.

Figure 8.2.

Markov chain for the Palm model

Figure 8.3.

Network from Exercise 8.3

Chapter 10

Figure 10.1.

Transition graph for Exercise 2.1

Figure 10.2.

Transition graph for Exercise 2.5

Figure 10.3.

Transition graph for Exercise 2.6

Figure 10.4.

Transition graph for Exercise 2.7

Figure 10.5.

Transition graph for Exercise 2.8

Figure 10.6.

Transition graph for Exercise 2.9.

Figure 10.7.

Transition graph for Exercise 2.10

Figure 10.8.

Transition graph for Exercise 2.11

Figure 10.9.

Transition graph for Exercise 2.12

Chapter 16

Figure 16.1.

Definition of response time – Exercise 8.7

List of Tables

Chapter 6

Table 6.1.

Continuous and discrete arrival processes

Table 6.2.

Distribution of source activity

Chapter 7

Table 7.1.

Offered traffic, loss probabilities and improvement functions

Chapter 8

Table 8.1.

Transaction characteristics

Table 8.2.

Proportion of traffic carried in connections

Chapter 15

Table 15.1.

Results for Exercise 7.2

Table 15.2.

Results for Exercise 7.4

Chapter 16

Table 16.1.

Number of terminals to install – Exercise 8.7

Table 16.2.

Summary of Exercise 8.9

Guide

Cover Page

Title Page

Copyright Page

Notations

Preface

Table of Contents

Begin Reading

Appendix 1

Appendix 2

References

Index

Other titles from iSTE in Mechanical Engineering and Solid Mechanics

Wiley End User License Agreement

Pages

i

ii

iii

iv

xi

xii

xiii

xiv

xv

xvi

xvii

xviii

xix

xx

xxi

xxii

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

Series EditorGuy Pujolle

Queues Applied to Telecoms

Courses and Exercises

Toky Basilide Ravaliminoarimalalason Falimanana Randimbindrainibe

First published 2022 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2022The rights of Toky Basilide Ravaliminoarimalalason and Falimanana Randimbindrainibe to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.

Library of Congress Control Number: 2022946967

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-78630-904-4

Notations

Numerals

0

Vector with coordinates of zeroMatrix with coordinates of zero

1

Matrix whose coordinates are all equal to 1

1

(

s

,

t

)

Indicator function of the interval (

s

,

t

)

Latin lower-case letters

a

i

,

j

,

k

Any constant indexed by

i, j

and

k

a

s

Distribution of the number of customers who arrive while another customer is being served

b

Offered traffic per free source

b

i

Normalization constant for a queue

i

c

Length of any pathAverage frequency of accepted requests

c

A

Average frequency of all requests

c

R

Average frequency of refused requests

d

Any durationDelay time

Average duration of a call

det

Determinant of a matrix

d

i

Duration of the

i

-th call

diag

Diagonal function for creating a diagonal matrix

d

q

Waiting time for delayed requests

dt

Very short interval of time

e

i

Vector whose

i

-th coordinate is equal to 1 and the others are zero

exp

Exponential with base

e

f

(

x

)

Probability density function for any random variable

fx

Probability density function for a random variable X

g

(

x

)

Probability density function for any random variable

h

Average holding time

h

(

X

)

Entropy of a random variable

X

h

i

Average duration of the i-th holding time

i

Any natural integerAny state of a Markov chain

i.i.d

Independent and identically distributed

i

k

Any state of a Markov chain

j

Any natural integerAny state of a Markov chain

k

Any natural integer

k

i

Any natural integer indexed by

i

l

Any natural integer

lim

Limit

ln

Natural logarithm

mErl

Milli-Erlang, unit of measurement for traffic

min

Minimum

n

Any natural integerNumber of service nodes in a delay systemNumber of nodes in a queueing networkNumber of resources

n

!

Factorial of a natural integer

n

n

i

Any natural integer indexed by

i

o

Little-o function

p

Any real number between 0 and 1Parameter of a geometric distribution

p

(

i, j

)

Coordinate

ij

of the transition matrix of a Markov chain

p

i

Any real number between 0 and 1Probability of leaving queue

i

p

ij

Probability of being routed from queue

i

to queue

j

q

Transition rate in a queueing networkDimensions of a queue

q

i

Parameter of the holding time distribution in state

i

Transition intensity from state

i

to state

i

q

i

Eigenvector of a matrix

q

ij

Transition intensity from state

i

to state

j

r

Any time

s

Any timeNumber of simultaneously busy sources

t

Any time

t'

Any time

t

i

Any time indexed by

i

Instant just after time

t

i

w

Average delay time of requests that must effectively wait

x

Vector for the number of customersAny column vectorState of a queueing network

x

i

Number of customers in queue

i

z

Variable of a generator function

Greek lower-case letters

ε

Infinitely small real positive number

θ

Period of time

λ

Parameter of an exponential distributionIntensity of an arrival process

λ

e

Intensity of an effective arrival process

λ

i

Parameter indexed by

i

for a random variable following an exponential distributionIntensity indexed by

i

of an arrival processEffective rate of arrival to queue

i

i

-th eigenvalue of a matrix

μ

Parameter for an exponential duration distributionInverse of the average duration of service

μ

i

Parameter indexed by

i

for an exponential duration distributionInverse of the average duration of service for a queue

i

Inverse of the average duration of class-

j

service for a queue

i

v

i

Intensity of the arrival process to queue

i

π

Any row vectorStationary distribution

π

i

i

-th coordinate of the stationary distribution

Derivative with respect to time of the function

π(t)

π(x)

Stationary distribution of state

x

ρ

Offered trafficLoad of a delay system

ρ

i

Load of the

i

-th queue in a network

σ

2

Variance of a random variable

τ

Inter-arrival of a punctual process

τ

n

n

-th inter-arrival of a punctual process

φ

i

Capacity of queue

i

Latin capital letters

A

Distribution of inter-arrivals to a delay system in the Kendall notation Offered traffic

Ã

Fictitious offered traffic

A

Infinitesimal stochastic generator

A

p

Lost traffic, refused traffic

AS

Almost surely

B

Distribution of durations of service of a delay system in the Kendall notationBlocking probability

B

1,

n

(

A

)

Erlang loss formula, first Erlang formula, Erlang-B

B

2,

n

(

A

)

Erlang waiting formula, second Erlang formula, Erlang-C

B

K

Normalization constant

B

k

Probability of having

k

busy resources

B

n

,

N

Blocking probability for

n

resources and

N

sources

B

(

n, p

)

Binomial distribution with parameters

n

and

p

C

s

Variation coefficient of the variable

S

D

Deterministic distributionPeriod or duration of observation Random variable of durations of service Probability of waiting

D

Diagonal matrix of eigenvalues for eigendecomposition of a matrix

D

t

Duration of service already received by a customer at instant

t

E

Loss probability

E

d

Loss probability due to source abandonment

Ɛ

(

n

,

λ

)

Erlang distribution with parameters

n

and

λ

E

(

X

)

Expected value of a random variable

X

E

k

Erlang distribution with parameter

k

E

n,N

Loss probability for

n

resources and

N

sources

Erl

Erlang, unit of measurement for traffic

F

n

,

N

Improvement factor for

n

resources and

N

sources

Inverse distribution function of the random variable

X

G

General distribution

G'

Derivative of

G

G

(

z

)

Generator function of a stationary distribution

G

x

(

z

)

Generator function of a random variable

X

GI

General and independent distribution

H

k

Hyper-exponential distribution of order

k

I

Number of queues

I

Identity matrix

Laplace transform

K

Any natural integerTotal population of customers able to access a delay systemTotal number of customers in a queueing network

K

π

Normalization constant

M

Markovian distribution

N

Any random variableAny natural integerCapacity of a delay systemNumber of sources

N

Vector for the number of customers in a queueing network

ℕ

Set of natural integers

ℕ*

Set of non-zero natural integers

N

(

s, t

)

Counting measure of a process between instants

s

and

t

N

i

(

s, t

)

Counting measure of the

i

-th process between instants

s

and

t

N

(

t

)

Counting measure of a process up to instant

t

Number of customers arriving in a queue during time

t

N

a

Number of calls during an observation period

N

i

Number of customers in the i-th node of the queueing network

N

k

Number of customers present in the system just after the departure of the

k

-th customer

N

q

Number of customers in a system queueNumber of waiting requests

N

qa

Number of waiting requests given there is a wait

N

s

Number of customers in the system

NS

The event “a request arrives”

N

t

Number of customers in the system at instant

t

P

Transition matrix for a Markov chain

Transition matrix for a reversible Markov chain

ℙ

Probability function

Ƥ

(

λ

)

Poisson distribution with parameter

λ

P

ij

Coordinate

ij

of the transition matrix for a Markov chain

Coordinate

ij

of the transition matrix for a reversible Markov chain

Coordinate

ij

of the matrix

P

t

, where

P

has the coordinate

P

ij

Q

Transition matrix for the eigendecomposition of a matrix

R

Random variable for the number of simultaneously busy resources

ℝ

Set of real numbers

ℝ

+

Set of positive real numbers

S

Any sum of random variablesRandom variable for the number of simultaneously busy resources

S

n

Sum of

n

random variables

T

Half-life periodAny timeDuration of servicePeriod of observation

T

i

Time spent by the system in state

i

before changing to another state

T

ij

Time spent by the system in state

i

before changing to state

j

Set of possible values that the time can take

T

i

Instants of appearance in a punctual process

T

q

Time spent by a customer in the system queue

T

s

Time spent by a customer in the system

T

t

Punctual process indexed by time

t

W

Average delay time for all requests

X

Real random variableNumber of requests

X

i

Real random variable indexed by

i

X

(

t

)

Real random variable indexed by time

t

Punctual processMarkov chain

Reversible Markov chain

χ

Set of possible values a random variable can take State space

{

X

n

}

Sequence or family of random variables, stochastic process in discrete time

{

X

(

t

)}

Family of random variables, stochastic process in continuous time

Y

Carried traffic

Y

i

Any event indexed by

i

Random variable equal to the number of customers who arrived during the service of the

i

-th customerTraffic carried individually by the

i

-th resource

Y

n

Nominal traffic or maximal theoretical trafficCarried traffic for

n

resources

Z

Service discipline in a waiting space in the Kendall notation Traffic peakedness

ℤ

Set of relative integers

Greek capital letters

Δ

t

Any interval of time

Π

Matrix of the row coordinates

π

Φ

Balance function

Special notations

■

QED, “which was to be demonstrated”

≔

By definition, equal to

i↝ j

State

j

can be reached from state

i

of a Markov chain

i ~ j

State

j

can be reached from state

i

and vice versa

Number of

k

combinations from a set of

n

elements

⌊

X

⌋

Floor function of

X

⌈

X

⌉

Ceiling function of

X

Preface

Queues are omnipresent in communication networks functioning in packet mode. We find them in every computer, router and radio access point. They are veritable funnels whose purpose is to maximize the use of network resources. It is at this level that policies for sharing among users through scheduling and the selective rejection of packets are established. When numerous data transfers share the same link, the system made up of the ensemble of files being transferred can itself be seen as a virtual queue, distributed from servers where the files being transferred are stored.

By extension, network models with circuit switches are considered a particular type of queue, given that there is no wait, since flows are simply allowed or rejected. In certain cases, as with mobile phone networks or call centers, an operator can set up a system that places calls on hold for more or less time, with the hope that a resource might soon become available. Formally speaking, we should thus speak of waiting and rejection lines; usage, however, dictates that the simpler term “queue” be used.

The theorization of teletraffic consists of studying the uses of resources made available to users in any system, and more specifically systems with delay times. For the case of telecommunications, it provides a means for planning a network, or the components of this network.

We can cite a number of objectives in the study of teletraffic: controlling planning that has already been developed, discovering resources that have become available, detecting potential problems, detecting network configuration problems or the programming of a central modifying network routing algorithms in a dynamic way, providing the indications that will serve for planning.

This book deals with the theoretical aspect of these queues: from the Poisson process, Markov chains and queueing systems to queuing networks. The study of the use of their resources is called the theory of teletraffic. This work also sets out the fundamentals of the theory of teletraffic by presenting the teletraffic of loss systems and that of queueing systems. Certain applications or explanations are more oriented towards the field of telecommunications. This book contains lessons and more than 60 exercises with solutions.

As a prerequisite, the reader should understand the basics of probability, which would be very useful to better understand the content of this book. Probability notations also facilitate an understanding of certain points listed in this book.

June 2022

Part 1Typical Processes in Queues