Network Traffic Engineering Stochastic Models and Applications

A comprehensive guide to the concepts and applications of queuing theory and traffic theory

Network Traffic Engineering: Models and Applications provides an advanced level queuing theory guide for students with a strong mathematical background who are interested in analytic modeling and performance assessment of communication networks.

The text begins with the basics of queueing theory before moving on to more advanced levels. The topics covered in the book are derived from the most cutting-edge research, project development, teaching activity, and discussions on the subject. They include applications of queuing and traffic theory in:

• LTE networks
• Wi-Fi networks
• Ad-hoc networks
• Automated vehicles
• Congestion control on the Internet

The distinguished author seeks to show how insight into practical and real-world problems can be gained by means of quantitative modeling. Perfect for graduate students of computer engineering, computer science, telecommunication engineering, and electrical engineering, Network Traffic Engineering offers a supremely practical approach to a rapidly developing field of study and industry.

ANDREA BAIOCCHI, PhD, is a Full Professor in the Department of Information Engineering, Electronics and Telecommunications of the University of Roma "La Sapienza". He has published over 160 papers on international journals and conference proceedings. He has participated to the Technical Program Committees of more than seventy international conferences. He served in the editorial board of the telecommunications technical journal published by Telecom Italia (currently TIM) for ten years.

Preface xv

Acronyms xvii

Part I Models for Service Systems

1 Introduction 3

1.1 Network Traffic Engineering: what, why, how 3

1.2 The art of modeling 7

1.3 An example: delay equalization 11

1.3.1 Model setting 12

1.3.2 Analysis by equations 13

1.3.3 Analysis by simulation 16

1.3.4 Takeaways 18

1.4 Outline of the book 18

1.4.1 Plan 18

1.4.2 Use 21

1.4.3 Notation 23

1.5 Further readings 24

Problems 25

2 Service systems and queues 27

2.1 Service system structure 27

2.2 Arrival and service processes 28

2.3 The queue as a service system model 32

2.4 Queues in equilibrium 33

2.4.1 Queues and stationary processes 33

2.4.2 Little’s law 37

2.5 Palm’s distributions for a queue 40

2.6 The traffic process 44

2.7 Performance metrics 46

2.7.1 Throughput 47

2.7.2 Utilization 49

2.7.3 Loss 49

2.7.4 Delay 51

2.7.5 Age of Information 51

Problems 54

3 Stochastic models for network traffic 59

3.1 Introduction 59

3.2 The Poisson process 60

3.2.1 Light versus heavy tails 65

3.2.2 Inhomogeneous Poisson process 66

3.2.3 Poisson process in multidimensional spaces 70

3.2.4 Testing for Poisson 80

3.3 The Markovian Arrival Process 83

3.4 Renewal processes 86

3.4.1 Residual interevent time and renewal paradox 91

3.4.2 Superposition of renewal processes 93

3.4.3 Alternating renewal processes 94

3.4.4 Renewal reward processes 95

3.5 Birthdeath processes 97

3.6 Branching processes 102 Problems 107

Part II Queues

4 Single server queues 113

4.1 Introduction and notation 113

4.2 The Embedded Markov Chain analysis of the M/G/1 queue 114

4.2.1 Queue length 116

4.2.2 Waiting time 120

4.2.3 Busy period and idle time 123

4.2.4 Remaining service time 126

4.2.5 Output process 127

4.2.6 Evaluation of the probabilities {a_k}k∈ℤ129

4.3 The M/G/1/K queue 130

4.3.1 Exact solution 130

4.3.2 Asymptotic approximation for large K 133

4.4 Numerical evaluation of the queue length PDF 141

4.5 A special case: the M/M/1 queue 143

4.6 Optimization of a single server queue 145

4.6.1 Maximization of net profit 146

4.6.2 Minimization of age of information 149

4.7 The G/M/1 queue 152

4.8 Matrixgeometric queues 159

4.8.1 Quasi BirthDeath (QBD) processes 159

4.8.2 M/G/1 and G/M/1 structured processes 161

4.9 A general result on single server queues 164

Problems 167

5 Multiserver queues 171

5.1 Introduction 171

5.2 The Erlang loss system 173

5.2.1 Insensitivity property of the Erlang loss system 182

5.2.2 A finite population model 183

5.2.3 NonPoisson input traffic 184

5.2.4 Multiclass Erlang loss system 189

5.3 Application of the Erlang loss model to cellular radio access network 192

5.3.1 Cell dimensioning under Quality of Service constraints 193

5.3.2 Number of handoffs in a connection lifetime 198

5.3.3 Blocking in a cell with user mobility 199

5.3.4 Tradeoff between location updating and paging 201

5.3.5 Dimensioning of a cell with two service classes 202

5.4 The M/M/m queue 204

5.4.1 Finite queue size model 209

5.4.2 Resource sharing versus isolation 209

5.5 Infinite server queues 212

5.5.1 Analysis of message propagation in a linear network 216

Problems 221

6 Priorities and scheduling 227

6.1 Introduction 227

6.2 Conservation law 230

6.3 M/G/1 priority queueing 233

6.3.1 NonFCFS queueing disciplines 234

6.3.2 HeadOfLine (HOL) priorities 237

6.3.3 Preemptresume priority 243

6.3.4 Shortest Job First 244

6.3.5 Shortest Remaining Processing Time 245

6.3.6 The μC rule 247

6.4 Processor sharing 248

6.4.1 The M/G/1 Processor Sharing model 248

6.4.2 Generalized Processor Sharing 250

6.4.3 Weighted Fair Queueing 255

6.4.4 Creditbased scheduling 258

6.4.5 Deficit Round Robin scheduling 262

6.4.6 Least Attained Service scheduling 263

6.5 Miscellaneous scheduling 266

6.5.1 Scheduling on a radio link 266

6.5.2 Job dispatching 271

6.6 Optimal scheduling 276

6.6.1 Anticipative systems 277

6.6.2 Serversharing, nonanticipative systems 277

6.6.3 Nonserversharing, nonanticipative systems 278

Problems 279

7 Queueing networks 283

7.1 Structure of a queueing network and notation 283

7.2 Open queueing networks 284

7.2.1 Optimization of network capacities 295

7.2.2 Optimal routing 297

7.2.3 Braess paradox 300

7.3 Closed queueing networks 303

7.3.1 Arrivals See Time Averages (ASTA) 306

7.3.2 Buzen’s algorithm for the computation of the normalization constant 307

7.3.3 Mean Value Analysis 308

7.4 Loss networks 315

7.4.1 Erlang fixedpoint approximation 319

7.4.2 Alternate routing 323

7.5 Stability of queueing networks 326

7.5.1 Definition of stability 329

7.5.2 Turning a stochastic discrete queueing network into a deterministic fluid network 331

Appendix 334

Problems 337

8 Bounds and approximations 341

8.1 Introduction 341

8.2 Bounds for the G/G/1 queue 343

8.2.1 Mean Value Analysis 345

8.2.2 Output process 347

8.2.3 Upper and lower bounds of the mean waiting time 348

8.2.4 Upper bound of the waiting time probability distribution 350

8.3 Bounds for the G/G/m queue 352

8.4 Approximate analysis of isolated G/G queues 355

8.4.1 Approximations from bounds 356

8.4.2 Approximation of the arrival or service process 356

8.4.3 Reflected Brownian Motion approximation 358

8.4.4 Heavytraffic approximation 361

8.5 Approximate analysis of a network of G/G/1 queues 364

8.5.1 Superposition of flows 365

8.5.2 Flow through a queue 365

8.5.3 Bernoulli splitting of a flow 366

8.5.4 Putting pieces together: the decomposition method 366

8.5.5 Bottleneck approximation for closed queueing networks 378

8.6 Fluid models 379

8.6.1 Deterministic fluid model 379

8.6.2 From fluid to diffusion model 386

8.6.3 Stochastic fluid model 389

8.6.4 Steadystate analysis 392

8.6.5 First passage times 398

8.6.6 Application of the stochastic fluid model to a multiplexer with ON-OFF traffic sources 400

Problems 403

Part III Networked Systems and Protocols

9 Multiple access 409

9.1 Introduction 409

9.2 Slotted ALOHA 411

9.2.1 Analysis of the na¨ıve Slotted ALOHA 412

9.2.2 Finite population Slotted ALOHA 416

9.2.3 Stabilized Slotted ALOHA 422

9.3 Pure ALOHA with variable packet times 426

9.4 Carrier Sense Multiple Access (CSMA) 431

9.4.1 Finite population model of CSMA 435

9.4.2 Multipacket reception CSMA 438

9.4.3 Stability of CSMA 447

9.4.4 Delay analysis of stabilized CSMA 452

9.5 Analysis of the WiFi MAC protocol 455

9.5.1 Outline of the IEEE 802.11 DCF protocol 456

9.5.2 Model of CSMA/CA 459

9.5.3 Optimization of backoff parameters 473

9.5.4 Fairness of CSMA/CA 481

Appendix 487

Problems 489

10 Congestion control 493

10.1 Introduction 493

10.2 Congestion control architecture in the Internet 497

10.3 Evolution of congestion control in the Internet 500

10.3.1 TCP Reno 500

10.3.2 TCP CUBIC 507

10.3.3 TCP Vegas 509

10.3.4 Data Center TCP (DCTCP) 512

10.3.5 Bottleneck Bandwidth and RTT (BBR) 514

10.4 Traffic engineering with TCP 520

10.5 Fluid model of a single TCP connection congestion control 522

10.5.1 Classic TCP with fixed capacity bottleneck link 523

10.5.2 Classic TCP with variable capacity bottleneck link 525

10.5.3 Application to wireless links 536

10.6 Fluid model of multiple TCP connections congestion control 540

10.6.1 Negligible buffering at the bottleneck 540

10.6.2 Classic TCP with droptail buffer at the bottleneck 541

10.6.3 Classic TCP with AQM at the bottleneck 542

10.6.4 Data Center TCP 543

10.7 Fairness and congestion control 545

10.8 Network Utility Maximization (NUM) 548

10.9 Challenges to TCP 553

10.9.1 Fatlong pipes 554

10.9.2 Wireless channels 556

10.9.3 Bufferbloat 557

10.9.4 Interaction with applications 558

Appendix 559

Problems 564

11 Quality of Service guarantees 567

11.1 Introduction 567

11.2 Deterministic service guarantees 568

11.2.1 Arrival curves 571

11.2.2 Service curves 575

11.2.3 Performance bounds 578

11.2.4 Regulators 579

11.2.5 Network calculus 584

11.3 Stochastic service guarantees 596

11.3.1 Multiplexing with marginal buffer size 596

11.3.2 Multiplexing with nonnegligible buffer size 603

11.3.3 Effective bandwidth 605

11.3.4 Network analysis and dimensioning 611

11.4 Further readings 616

Appendix 617

Problems 622

A Refresher of probability, random variables and stochastic processes 623

A.1 Probability 623

A.2 Random variables 625

A.3 Transforms of probability distribution functions 627

A.4 Inequalities and limit theorems 631

A.4.1 Markov inequality 631

A.4.2 Chebychev inequality 632

A.4.3 Jensen inequality 632

A.4.4 Chernov bound 633

A.4.5 Union bound 633

A.4.6 Central Limit Theorem (CLT) 634

A.5 Stochastic processes 634

A.6 Markov Chains 635

A.6.1 Classification of states 636

A.6.2 Recurrence 637

A.6.3 Visits to a state 640

A.6.4 Asymptotic behavior and steadystate 641

A.6.5 Absorbing Markov chains 646

A.6.6 Continuoustime Markov processes 647

A.6.7 Sojourn times in process states 649

A.6.8 Reversibility 650

A.6.9 Uniformization 651

A.7 Wiener process (Brownian Motion) 652

A.7.1 Wiener process with an absorbing barrier 654

A.7.2 Wiener process with a reflecting barrier 655

References 657

Index 669

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.