+353-1-416-8900REST OF WORLD
+44-20-3973-8888REST OF WORLD
1-917-300-0470EAST COAST U.S
1-800-526-8630U.S. (TOLL FREE)

Network Traffic Engineering. Stochastic Models and Applications. Edition No. 1

  • Book

  • 816 Pages
  • October 2020
  • John Wiley and Sons Ltd
  • ID: 5838386

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.

Table of Contents

Preface xvii

Acronyms xix

Part I Models for Service Systems 1

1 Introduction 3

1.1 Network Traffic Engineering: What, Why, How 3

1.2 The Art of Modeling 8

1.3 An Example: Delay Equalization 13

1.3.1 Model Setting 14

1.3.2 Analysis by Equations 15

1.3.3 Analysis by Simulation 19

1.3.4 Takeaways 21

1.4 Outline of the Book 21

1.4.1 Plan 21

1.4.2 Use 25

1.4.3 Notation 27

1.5 Further Readings 29

Problems 30

2 Service Systems and Queues 33

2.1 Service System Structure 33

2.2 Arrival and Service Processes 35

2.3 The Queue as a Service System Model 38

2.4 Queues in Equilibrium 40

2.4.1 Queues and Stationary Processes 40

2.4.2 Little’s Law 45

2.5 Palm’s Distributions for a Queue 49

2.6 The Traffic Process 53

2.7 Performance Metrics 56

2.7.1 Throughput 56

2.7.2 Utilization 59

2.7.3 Loss 59

2.7.4 Delay 61

2.7.5 Age of Information 62

Summary and Takeaways 63

Problems 65

3 Stochastic Models for Network Traffic 71

3.1 Introduction 71

3.2 The Poisson Process 72

3.2.1 Light versus Heavy Tails 78

3.2.2 Inhomogeneous Poisson Process 79

3.2.3 Poisson Process in Multidimensional Spaces 84

3.2.3.1 Displacement 89

3.2.3.2 Mapping 89

3.2.3.3 Thinning 90

3.2.3.4 Distances 91

3.2.3.5 Sums and Products on Point Processes 92

3.2.3.6 Hard Core Processes 94

3.2.4 Testing for Poisson 96

3.3 The Markovian Arrival Process 100

3.4 Renewal Processes 103

3.4.1 Residual Inter-Event Time and Renewal Paradox 108

3.4.2 Superposition of Renewal Processes 110

3.4.3 Alternating Renewal Processes 111

3.4.4 Renewal Reward Processes 113

3.5 Birth-Death Processes 115

3.6 Branching Processes 121

Summary and Takeaways 125

Problems 126

Part II Queues 131

4 Single-Server Queues 133

4.1 Introduction and Notation 133

4.2 The Embedded Markov Chain Analysis of the MG∕1 Queue 134

4.2.1 Queue Length 136

4.2.2 Waiting Time 141

4.2.3 Busy Period and Idle Time 145

4.2.4 Remaining Service Time 148

4.2.5 Output Process 149

4.2.6 Evaluation of the Probabilities {ak}k∈ℤ 151

4.3 The MG∕1∕K Queue 152

4.3.1 Exact Solution 153

4.3.2 Asymptotic Approximation for Large K 157

4.4 Numerical Evaluation of the Queue Length PDF 166

4.5 A Special Case: the MM∕1 Queue 168

4.6 Optimization of a Single-Server Queue 170

4.6.1 Maximization of Net Profit 171

4.6.2 Minimization of Age of Information 174

4.6.2.1 General Expression of the Average Age of Information 175

4.6.2.2 Minimization of the Age of Information for an MM∕1 Model 177

4.7 The GM∕1 Queue 178

4.8 Matrix-Geometric Queues 185

4.8.1 Quasi Birth-Death (QBD) Processes 186

4.8.2 MG∕1 and GM∕1 Structured Processes 188

4.9 A General Result on Single-Server Queues 192

Summary and Takeaways 194

Problems 195

5 Multi-Server Queues 199

5.1 Introduction 199

5.2 The Erlang Loss System 201

5.2.1 Insensitivity Property of the Erlang Loss System 211

5.2.2 A Finite Population Model 213

5.2.3 Non-Poisson Input Traffic 214

5.2.3.1 Wilkinson’s Method 217

5.2.3.2 Fredericks’ Method 218

5.2.4 Multi-Class Erlang Loss System 221

5.3 Application of the Erlang Loss Model to Cellular Radio Access Network 224

5.3.1 Cell Dimensioning under Quality of Service Constraints 225

5.3.2 Number of Handoffs in a Connection Lifetime 230

5.3.3 Blocking in a Cell with User Mobility 232

5.3.4 Trade-off between Location Updating and Paging 234

5.3.5 Dimensioning of a Cell with Two Service Classes 236

5.4 The MMm Queue 238

5.4.1 Finite Queue Size Model 243

5.4.2 Resource Sharing versus Isolation 244

5.5 Infinite Server Queues 247

5.5.1 Analysis of Message Propagation in a Linear Network 252

Summary and Takeaways 257

Problems 258

6 Priorities and Scheduling 265

6.1 Introduction 265

6.2 Conservation Law 268

6.3 MG∕1 Priority Queueing 272

6.3.1 Non-FCFS Queueing Disciplines 273

6.3.2 Head-of-Line (HOL) Priorities 276

6.3.3 Preempt-Resume Priorities 283

6.3.4 Shortest Job First 284

6.3.5 Shortest Remaining Processing Time 286

6.3.6 The 𝜇C Rule 288

6.4 Processor Sharing 289

6.4.1 The MG∕1 Processor Sharing Model 290

6.4.2 Generalized Processor Sharing 293

6.4.3 Weighted Fair Queueing 298

6.4.4 Credit-Based Scheduling 302

6.4.5 Deficit Round Robin Scheduling 306

6.4.6 Least Attained Service Scheduling 308

6.5 Miscellaneous Scheduling 312

6.5.1 Scheduling on a Radio Link 312

6.5.1.1 Proportional Fairness 312

6.5.1.2 Multi-rate Orthogonal Multiplexing 313

6.5.2 Job Dispatching 318

6.6 Optimal Scheduling 324

6.6.1 Anticipative Systems 325

6.6.2 Server-Sharing, Nonanticipative Systems 325

6.6.3 Non-Server-Sharing, Nonanticipative Systems 326

Summary and Takeaways 327

Problems 327

7 Queueing Networks 331

7.1 Structure of a Queueing Network and Notation 331

7.2 Open Queueing Networks 332

7.2.1 Optimization of Network Capacities 345

7.2.2 Optimal Routing 347

7.2.3 Braess Paradox 350

7.3 Closed Queueing Networks 355

7.3.1 Arrivals See Time Averages (ASTA) 358

7.3.2 Buzen’s Algorithm for the Computation of the Normalization Constant 359

7.3.3 Mean Value Analysis 360

7.4 Loss Networks 369

7.4.1 Erlang Fixed-Point Approximation 373

7.4.2 Alternate Routing 378

7.5 Stability of Queueing Networks 381

7.5.1 Definition of Stability 385

7.5.2 Turning a Stochastic Discrete Queueing Network into a Deterministic Fluid Network 387

7.6 Further Readings 390

Appendix 391

Summary and Takeaways 394

Problems 394

8 Bounds and Approximations 399

8.1 Introduction 399

8.2 Bounds for the GG∕1 Queue 401

8.2.1 Mean Value Analysis 404

8.2.2 Output Process 406

8.2.3 Upper and Lower Bounds of the Mean Waiting Time 407

8.2.4 Upper Bound of the Waiting Time Probability Distribution 409

8.3 Bounds for the GGm Queue 412

8.4 Approximate Analysis of Isolated GG Queues 416

8.4.1 Approximations from Bounds 416

8.4.2 Approximation of the Arrival or Service Process 417

8.4.3 Reflected Brownian Motion Approximation 418

8.4.4 Heavy-traffic Approximation 423

8.5 Approximate Analysis of a Network of GG∕1 Queues 426

8.5.1 Superposition of Flows 427

8.5.2 Flow Through a Queue 428

8.5.3 Bernoulli Splitting of a Flow 428

8.5.4 Putting Pieces Together: The Decomposition Method 429

8.5.5 Bottleneck Approximation for Closed Queueing Networks 442

8.6 Fluid Models 443

8.6.1 Deterministic Fluid Model 444

8.6.2 From Fluid to Diffusion Model 452

8.6.3 Stochastic Fluid Model 456

8.6.4 Steady-State Analysis 459

8.6.4.1 Infinite Buffer Size (K = ∞) 462

8.6.4.2 Loss Probability 463

8.6.5 First Passage Times 466

8.6.6 Application of the Stochastic Fluid Model to a Multiplexer with ON-OFF Traffic Sources 468

Summary and Takeaways 471

Problems 472

Part III Networked Systems and Protocols 477

9 Multiple Access 479

9.1 Introduction 479

9.2 Slotted ALOHA 482

9.2.1 Analysis of the Naïve Slotted ALOHA 483

9.2.2 Finite Population Slotted ALOHA 487

9.2.3 Stabilized Slotted ALOHA 494

9.3 Pure ALOHA with Variable Packet Times 499

9.4 Carrier Sense Multiple Access (CSMA) 504

9.4.1 Features of the CSMA Protocol 505

9.4.1.1 Clear Channel Assessment 505

9.4.1.2 Persistence Policy 506

9.4.1.3 Retransmission Policy 507

9.4.2 Finite Population Model of CSMA 509

9.4.3 Multi-Packet Reception CSMA 513

9.4.3.1 Multi-Packet Reception 1-Persistent CSMA with Poisson Traffic 515

9.4.3.2 Multi-Packet Reception Nonpersistent CSMA with Poisson Traffic 519

9.4.4 Stability of CSMA 523

9.4.5 Delay Analysis of Stabilized CSMA 531

9.5 Analysis of the WiFi MAC Protocol 534

9.5.1 Outline of the IEEE 802.11 DCF Protocol 534

9.5.2 Model of CSMA/CA 538

9.5.2.1 The Back-off Process 540

9.5.2.2 Virtual Slot Time 543

9.5.2.3 Saturation Throughput 545

9.5.2.4 Service Times of IEEE 802.11 DCF 549

9.5.2.5 Correlation between Service Times 554

9.5.3 Optimization of Back-off Parameters 556

9.5.3.1 Maximization of Throughput 556

9.5.3.2 Minimization of Service Time Jitter 561

9.5.4 Fairness of CSMA/CA 565

9.6 Further Readings 570

Appendix 572

Summary and Takeaways 573

Problems 575

10 Congestion Control 579

10.1 Introduction 579

10.2 Congestion Control Architecture in the Internet 583

10.3 Evolution of Congestion Control in the Internet 587

10.3.1 TCP Reno 588

10.3.1.1 TCP Congestion Control Operations 589

10.3.1.2 NewReno 593

10.3.1.3 TCP Congestion Control with SACK 594

10.3.1.4 Congestion Window Validation 595

10.3.2 TCP CUBIC 596

10.3.3 TCP Vegas 598

10.3.4 Data Center TCP (DCTCP) 601

10.3.4.1 Marking at the Switch 602

10.3.4.2 ECN-Echo at the Receiver 603

10.3.4.3 Controller at the Sender 603

10.3.5 Bottleneck Bandwidth and RTT (BBR) 604

10.3.5.1 Delivery Rate Estimate 607

10.3.5.2 StartUp and Drain 608

10.3.5.3 ProbeBW 609

10.3.5.4 ProbeRTT 610

10.3.5.5 Pseudo-code of BBR Algorithm 610

10.4 Traffic Engineering with TCP 611

10.5 Fluid Model of a Single TCP Connection Congestion Control 614

10.5.1 Classic TCP with Fixed Capacity Bottleneck Link 615

10.5.2 Classic TCP with Variable Capacity Bottleneck Link 617

10.5.2.1 Discretization of the Evolution Equations 625

10.5.2.2 Accuracy of the Fluid Approximation of TCP 627

10.5.3 Application to Wireless Links 630

10.5.3.1 Random Capacity 630

10.5.3.2 TCP over Cellular Link 632

10.6 Fluid Model of Multiple TCP Connections Congestion Control 635

10.6.1 Negligible Buffering at the Bottleneck 635

10.6.2 Classic TCP with Drop Tail Buffer at the Bottleneck 637

10.6.3 Classic TCP with AQM at the Bottleneck 638

10.6.4 Data Center TCP with FIFO Buffer at the Bottleneck 639

10.7 Fairness and Congestion Control 642

10.8 Network Utility Maximization (NUM) 645

10.9 Challenges to TCP 652

10.9.1 Fat-Long Pipes 653

10.9.2 Wireless Channels 655

10.9.3 Bufferbloat 656

10.9.4 Interaction with Applications 658

Appendix 659

Summary and Takeaways 664

Problems 665

11 Quality-of-Service Guarantees 669

11.1 Introduction 669

11.2 Deterministic Service Guarantees 670

11.2.1 Arrival Curves 673

11.2.2 Service Curves 677

11.2.3 Performance Bounds 681

11.2.4 Regulators 683

11.2.5 Network Calculus 688

11.2.5.1 Single Node Analysis 689

11.2.5.2 End-to-End Analysis 692

11.3 Stochastic Service Guarantees 703

11.3.1 Multiplexing with Marginal Buffer Size 703

11.3.2 Multiplexing with Non-Negligible Buffer Size 711

11.3.3 Effective Bandwidth 714

11.3.3.1 Definition of the Effective Bandwidth 714

11.3.3.2 Properties of the Effective Bandwidth 715

11.3.3.3 Effective Bandwidth of a Markov Source 716

11.3.4 Network Analysis and Dimensioning 721

11.4 Further Readings 727

Appendix 728

Summary and Takeaways 732

Problems 733

A Refresher of Probability, Random Variables, and Stochastic Processes 735

A.1 Probability 735

A.2 Random Variables 737

A.3 Transforms of Probability Distribution Functions 739

A.4 Inequalities and Limit Theorems 744

A.4.1 Markov Inequality 744

A.4.2 Chebychev Inequality 745

A.4.3 Jensen Inequality 746

A.4.4 Chernov Bound 746

A.4.5 Union Bound 747

A.4.6 Central Limit Theorem (CLT) 747

A.5 Stochastic Processes 748

A.6 Markov Chains 749

A.6.1 Classification of States 750

A.6.2 Recurrence 751

A.6.3 Visits to a State 754

A.6.4 Asymptotic Behavior and Steady State 756

A.6.5 Absorbing Markov Chains 762

A.6.6 Continuous-Time Markov Processes 763

A.6.7 Sojourn Times in Process States 765

A.6.8 Reversibility 766

A.6.9 Uniformization 768

A.7 Wiener Process (Brownian Motion) 769

A.7.1 Wiener Process with an Absorbing Barrier 771

A.7.2 Wiener Process with a Reflecting Barrier 772

References 775

Index 789

Authors

Andrea Baiocchi