Communicating systems & networks

Communicating

Systems &

Networks:

Traffic &

Performance

This page intentionally left blank

INNOVATIVE TECHNOLOG Y SERIES

INFORMATIO N SYSTEM S AN D NETWORK S

Communicating

Systems &

Networks:

Traffic &

Performance

Georges Fiche &

Gerard Hebuterne

London and Sterling, VA

First published in France in 2003 by Hermes Science entitled 'Trafic et performances des

reseaux de telecoms'

First published in Great Britain and the United States in 2004 by Kogan Page Science, an

imprint of Kogan Page Limited

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 licences issued by the CLA. Enquiries concerning reproduction

outside these terms should be sent to the publishers at the undermentioned addresses:

120 Pentonville Road 22883 Quicksilver Drive

London N1 9JN Sterling VA 20166-2012

UK USA

www.koganpagescience.com

© GET and Lavoisier, 2003

© Kogan Page Limited, 2004

The right of Georges Fiche and Gerard Hebuterne to be identified as the authors of this work

has been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

ISBN 1 9039 9635 X

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library.

Library of Congress Cataloging-in-Publication Data

Fiche, Georges.

[Trafic et performances des reseaux de telecoms. English]

Systems and communicating networks : traffic and performance / Georges

Fiche and Gerard Haebuterne.

p. cm. -- (Innovative technology series. Information systems and

networks)

ISBN 1-903996-35-X

1. Telecommunication--Traffic. 2. Computer networks. I. Haebuterne,

Gaerard. II. Title. III. Series.

TK5102.5F47 2004

621.382'l--dc22

2003024763

Typeset by Kogan Page

Printed and bound in Great Britain by Creative Print and Design (Wales), Ebbw Vale

Contents

Introduction xiii

1. Telecommunication Networks and Traffic 1

1.1. Network concepts 2

1.1.1. Network architectures 2

1.1.1.1. Network components 3

1.1.1.2. Network structures 4

1.1.2. Communication technologies: circuit and packet 7

1.1.2.1. Circuit switching 7

1.1.2.2. Packet switching 8

1.1.3. Main networks 10

1.1.3.1. Conventional fixed telephone network 11

1.1.3.2. No. 7 signalling network 12

1.1.3.3. Mobile networks 13

1.1.3.4. The internet network 17

1.1.3.5. The next generation network (NGN) 20

1.1.3.6. Private networks 23

1.2. Traffic concepts 25

1.2.1. Erlang concept 25

1.2.2. Traffic offered, traffic handled 27

1.2.3. Quality of service 28

1.2.4. Load profiles, load A and load B 28

1.2.5. Stationarity 30

1.2.6. The concept of busy hour call attempts (BHCA) 30

1.2.7. The user plane and the control plane 32

1.2.8. Characterisation of traffic 32

1.2.8.1. Characterisation of services 33

1.2.8.2. Traffic mix 34

1.2.8.3. Traffic matrix 34

1.2.8.4. "Node" level matrix 35

1.2.8.5. Network level matrix 38

vi Communicating Networks: Traffic and Performance

2. Quality of Service and Performance 41

2.1. Standardization organisms and norms 41

2.2. Quality of Service (QoS) 42

2.3. Network performance 44

2.3.1. End-to-end and intermediate performance parameters 44

2.3.1.1. Reference network configuration 45

2.3.1.2. Communication set-up reference diagram 45

2.3.1.3. Communication, transfer phase reference diagram 45

2.3.1.4. Disengagement reference diagram 46

2.3.2. Access, disengagement, and transfer phases 47

2.3.3. Parameter values 48

2.4. Traffic load conditions 49

2.4.1. Normal load, load A 50

2.4.2. High load, load B 51

2.4.3. Overload 52

2.5. Parameters and standards 55

2.5.1.Trafficability 56

2.5.1.1. Access and disengagement 56

2.5.1.2. Communication, user information transfer 60

2.5.2. Dependability parameters 63

2.5.2.1. Access 63

2.5.2.2. Transfer and disengagement 65

2.5.3. Performance during overload 66

2.5.4. Synthesis tables 67

2.5.4. l.Trafficability 68

2.5.4.2. Dependability parameters 69

3. Probability 71

3.1. Definition and properties of events 71

3.1.1. The concept of event 71

3.1.2. Complementary events 73

3.1.3. Properties of operations on events 73

3.1.3.1. Commutativity 73

3.1.3.2. Associativity 73

3.1.3.3.Distributivity 74

3.1.3.4. Difference 74

3.1.3.5. De Morgan rules 74

3.2. Probability 75

3.2.1. Definition 75

3.2.2. Basic theorems and results 75

3.2.2.1. Addition theorem 75

3.2.2.2. Conditional probability 76

3.2.2.3. Multiplication theorem 78

3.2.2.4. The a posteriori probability theorem 79

3.3. Random variable 80

Contents vii

3.3.1. Definition 80

3.3.2. Probability functions of a random variable 81

3.3.2.1. Notations 81

3.3.2.2. Distribution function or cumulated probability 81

3.3.2.3. Probability density function 81

3.3.3. Moments of a random variable 82

3.3.3.1. Moments about the origin 83

3.3.3.2. Central moments 83

3.3.3.3. Mean and variance 83

3.3.3.4. Examples of application 85

3.3.4. Pairs of random variables 86

3.3.4.1. Definition 87

3.3.4.2. Joint probability 87

3.3.4.3. Marginal probability of a pair of random variables 89

3.3.4.4. Conditional probability of a pair of random variables 89

3.3.4.5. Functions of a pair of random variables 90

3.3.4.6. Sum of independent random variables 92

3.3.4.7. Moments of the sum of independent random variables 94

3.3.4.8. Practical interest 96

3.4. Convolution 97

3.4.1. Definition 97

3.4.2. Properties of the convolution operation 98

3.4.2.1. The convolution is commutative 98

3.4.2.2. Convolution of exponential distributions 98

3.4.2.3. Convolution of normal distributions 98

3.5. Laplace transform 100

3.5.1. Definition 100

3.5.2. Properties 101

3.5.2.1. Fundamental property 101

3.5.2.2. Differentiation property 101

3.5.2.3. Integration property 102

3.5.2.4. Some common transforms 102

3.6. Characteristic function, generating function, z transform 106

3.6.1. Characteristic function 106

3.6.1.1. Definition 106

3.6.1.2. Properties 107

3.6.1.3. Inversion formula 107

3.6.1.4. Asymptotic law 110

3.6.1.5. Some usual transforms 114

3.6.2. Generating functions 115

3.6.2.1. Definition 115

3.6.2.2. Moments 116

3.6.2.3. Some usual transforms 116

3.6.2.4. Convolution 117

viii Communicating Networks: Traffic and Performance

4. Probability Laws 121

4.1. The (discrete) uniform distribution 122

4.2. The binomial law 123

4.3. The multinomial distribution 125

4.4. The geometric distribution 125

4.5. The hypergeometric distribution 127

4.6. The Poisson law 128

4.6.1. Relationship with the binomial law 130

4.7. The continuous uniform distribution 131

4.8. The normal (Gaussian) distribution 132

4.8.1. The sum of normal random variables 134

4.8.2. Statistical tables 135

4.8.3. The normal law as limiting distribution 136

4.9. The Chi-2 distribution 136

4.9.1. Limiting behaviour 137

4.10. The Student distribution 137

4.11. The lognormal distribution 138

4.12. The exponential and related distributions 139

4.12.1. The exponential distribution 139

4.12.2. The Erlang-k distribution 140

4.12.3. The hyperexponential distribution 143

4.12.4. Generalising: the Cox distribution 144

4.12.5. The Gamma distribution 144

4.13. The Weibull distribution 146

4.14. The logistic distribution 147

4.15. The Pareto distribution 148

4.16. A summary of the main results 150

4.16.1. Discrete distributions 150

4.16.2. Continuous distributions 152

5. Statistics 155

5.1. Descriptive statistics 156

5.1.1. Data representation 156

5.1.2. Statistical parameters 158

5.1.2.1.Fractiles 158

5.1.2.2. The sample mean 159

5.1.2.3. The sample variance 159

5.1.2.4. The moments 159

5.1.2.5. The mode 160

5.1.2.6. Other characterisations 160

5.2. Correlation and regression 161

5.2.1. Correlation coefficient 162

5.2.2. The regression curve 163

5.3. Sampling and estimation techniques 164

Contents ix

5.4. Estimation 167

5.4.1. Point estimation 168

5.4.2. Estimating confidence intervals 172

5.5. Hypothesis testing 179

5.5.1. Example: testing the value of the mean of a normal distribution 179

5.5.2. Chi-2 (Chi square) test: uniformity of a random generator 182

5.5.3. Test of the correlation 183

6. Reliability 185

6.1. Definition of reliability 185

6.2. Failure rate and bathtub curve 186

6.3. Reliability functions 187

6.4. Systems reliability 189

6.4.1. Reliability of non repairable systems 189

6.4.1.1. Reliability of the series configuration 189

6.4.1.2. Reliability of the parallel configuration 191

6.4.1.3. Reliability of the series - parallel configuration 192

6.4.1.4. Reliability of the parallel-series configuration 193

6.4.1.5. Complex configurations 194

6.4.1.6. Non repairable redundant configurations 195

6.4.2. Reliability and availability of repairable systems 197

6.4.2.1. State equations 197

6.4.2.2. Reliability of redundant repairable systems 199

6.4.2.3. Imperfect structures 206

6.4.3. Using Laplace transform 209

6.4.4. Matrix utilization 212

6.4.4.1. Exact resolution by inversion 214

6.4.4.2. Approximate solutions 218

6.5. Software reliability 219

6.5.1. Reliability growth model, early-life period 219

6.5.2. Useful-life period model 221

6.6. Spare parts calculation 224

6.6.1. Definitions 225

6.6.2. Periodical restocking 225

6.6.3. Continuous restocking 225

7. Queueing Theory 229

7.1. The basic service station: clients and servers 230

7.2. Arrival process 230

7.2.1. Renewal process 231

7.2.2. Poisson process 232

7.2.3. Where do the Poisson processes come into play? 234

7.3. Service process 235

7.3.1. Residual service time 235

7.3.2. The exponential law 236

x Communicating Networks: Traffic and Performance

7.3.3. Erlang laws 238

7.3.4. Hyperexponential law 238

7.4. Birth and death process 240

7.4.1. Notion of "state" 240

7.4.2. Markov chains 240

7.4.3. Birth and death processes 241

7.4.4. PASTA property (Poisson arrivals see time averages) 244

7.5. Classical queueing models 245

7.5.1. Kendall notation 245

7.5.2. General results 246

7.5.3. The queue M/M/1 248

7.5.3.1. State probabilities 248

7.5.3.2. Use of generating functions 251

7.5.3.3. Waiting distribution 253

7.5.4. The M/M/R/R model (Erlang model) 257

7.5.5. M/M/R queue 259

7.5.6. Limited-capacity models 264

7.5.7. M/M/ queue 265

7.5.8. Limited-population system: the Engset problem 266

7.6. More complex queues 270

7.6.1. The imbedded Markov chain method 271

7.6.2. The number of clients in system 271

7.6.3. Waiting times: Pollaczek formulae 275

7.6.3.1. Preliminary: calculation of remaining service time 275

7.6.3.2. The Pollaczek-Khintchine formula 276

7.6.3.3. Example 1: the M/M/1 queue 277

7.6.3.4. Example 2: the M/D/1 queue 277

7.6.3.5. Generalisation: Takacs formulae 277

7.6.4. The Benes method. Application to the M/D/1 system 278

7.7. The G/G/1 queue 279

7.7.1. Pollaczek method 279

7.7.2. Application to the stochastic relation of the queue to one

server (GI/G/1 queue) 282

7.7.3. Resolution of the integral equation 285

7.7.3.1. Application to the M/G/1 queue 285

7.7.3.2. Application to G/M/1 queue 291

7.8. Queues with priorities 295

7.8.1. Work conserving system 296

7.8.2. The HOL discipline 299

7.9. Use of approximate methods 300

7.9.1. Some approximate formulae 301

7.10. Appendix: Pollaczek transform 303

8. Simulation 305

8.1. Roulette simulation 306

Contents xi

8.2. Discrete-event simulation 308

8.3. Measurements and accuracy 311

8.3.1. Measurements 311

8.3.2. Accuracy 311

8.4. Random numbers 315

8.4.1. Generation according to a distribution 315

8.4.2. Generating pseudo-random variables 317

9. Models 321

9.1. Models for system control 322

9.1.1. The simple feedback system 322

9.1.2. Central server 323

9.1.3. Time sharing processor 326

9.1.4. Polling and token ring 328

9.1.5. Ethernet link 334

9.1.6. Benchmarks, processor modelling 341

9.1.7. Disc system 347

9.1.8. Managing a pool by blocks 353

9.1.9. Call repetition 357

9.1.10. Regulation 362

9.2. Transport plane models 368

9.2.1. Multi-bit rate traffic concentrator 368

9.2.1.1. Multi-bit rate Erlang model 368

9.2.1.2. Peakedness factor method 369

9.2.2. Multiplexing 373

9.2.2.1. Multiplexing of identical periodical sources 373

9.2.2.2. Multiplexing of bursty sources 378

9.2.2.3. Modelling of cell/packet part 379

9.2.2.4. Modelling of the burst part 382

9.2.3. Equivalent bandwidth 384

9.2.4. Modelling and multiplexing of IP traffic 387

9.2.4.1. Real time traffic 389

9.2.4.2. Elastic traffic 392

9.2.4.3. Global capacity 394

9.2.5. Series queue model (M/M...M/1) 394

9.2.6. Switching matrix 406

9.2.7. Switching network 409

9.2.7.1. Blocking calculation: Lee-Le Gall model 410

9.2.7.2. Multi-bit rate network case 417

9.2.7.3. Non-blocking networks 418

9.2.8. Traffic matrix, Kruithof method............ 421

10. Performance Methodology 427

10.1. Project life phases 427

10.2. Analysis of need 430

xii Communicating Networks: Traffic and Performance

10.2.1. Reference environments in traffic 430

10.2.2. Reference environments for dependability 437

10.2.3. Capacity and quality of service objects 438

10.3. Modelling 440

10.3.1. Message processing delay 442

10.3.2. Incoming call indication delay 444

10.3.3. Transfer delay for packets through a network and variation

in transfer delay 450

10.3.3.1. Calculation of transfer delay 451

10.3.3.2. Calculation of transfer delay variation 454

10.3.4. Call set-up delay 456

10.3.5. Dependability 460

10.4. On-load tests 465

10.4.1. Traffic performance tests 467

10.4.2. Overload tests 468

10.4.3. Dependability tests 469

10.4.4. General organisation of tests 470

10.5. Dimensioning 472

10.5.1. Dimensioning of the control of a mobile centre 473

10.5.2. Dimensioning of the links of a gateway 477

10.5.3. Dimensioning of maintenance stock 481

10.6. Operating monitoring 483

Conclusion 491

Appendix 1 493

Appendix2 501

Bibliography 519

Index 525

Introduction

This book originates from the desire to perpetuate expertise in the field of

performance evaluation, particularly for telecommunication systems and

networks. It is obviously impossible to translate into a single work all the

facets of an activity which encompasses many systems and a great variety of

domains such as standardization, modelling, measurement, fields trials,

observations etc. However, it rapidly becomes evident that performance study

through its different aspects is the expression of a real and unique discipline:

performance engineering. So it is worth writing a book whose contents is, as

much as possible, the synthesis of both the theoretical and the technical

knowledge which are the basis for good practice in this field.

In this respect this work aims to be both a tool for education in performance

engineering, and a guide to implementing performance activity, both in the

research laboratory and in industrial environment.

Research and industrial work are both demanding. The performance engineer

will have to juggle with equations, as well as with equipment in the lab or in

the field. His/her permanent search for efficiency, the necessity to use

tractable approximations, and his/her natural trend to perform experimental

measurements will not prevent him/her from mastering complex mathematical

models. As a matter of fact, it is the complete mastering of the analytical tools

together with their application to the whole set of system development phases

(from design to operation), which will lead to maximum efficiency, by making

possible the synthesis between theory and practice as required by market and

industrial constraints.

Therefore, in this book, we will deal equally with elementary calculations,

such as processor occupancy, the number of messages etc. as well as with

more complex computations such as multiplexer dimensioning in the case of

internet traffic. In the same way, we will use elementary probability

calculations or classical Markov models, as well as complex methods such as

Pollaczek's method for queueing systems evaluation. Lastly, again with

concern for efficiency, we always shall keep in mind the actual conditions of

xiv Communicating Networks: Traffic and Performance

application and particularly the order of magnitudes of the parameter values,

which will allow great simplification of the models.

A tool for education and a companion hand book for performance engineering

activity, this work is dedicated to the student who wishes to learn about

communicating systems and networks, probability and queueing theory, as

well as to the engineer and the researcher who desires to enlarge his/her

competence domains to other fields, such as reliability, statistics, quality of

service standardization, and methodology.

Several approached to this work are possible. Each chapter, relatively

independent from the others, deals with a subject in a way as progressive as

possible.

Chapters however are organized according to a logic whose motivation is

again the desire to teach the basics of the job of performance engineering. The

logic is as follows.

The first chapter presents the main characteristics and functions of major

telecommunication networks. These are indeed the subject of our performance

studies, whose objective is to evaluate their capacity to handle the traffic they

are offered. In this respect, we then shall present in the same chapter the basic

concepts of what is called teletraffic.

In the second chapter, we develop the generic aspects of quality of service

(QoS), through an overview of the main performance parameters such as

specified in the international standardisation organisms.

So, with these two chapters we have set the scene: the subject that we are

studying (the telecommunication systems and networks), and the reason why

we are interested in it (traffic handling and QoS). Now we have to deal with

the means needed for our studies, firstly with the basic theoretical tools.

The third chapter presents the theory of probability and introduces analytical

tools such as transform functions, which allow us to solve most of the

probabilistic problems that we will face.

The fourth chapter presents the main probability laws which will be of

continuous use in the rest of the book, in various domains such as statistic,

reliability, queueing, etc.