Network Traffic Engineering - Stochastic Models and Applications

A comprehensive guide to the concepts and applications of queuing theory and traffic theoryNetwork 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 InternetThe 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.

List of contents

Preface xviiAcronyms xixPart I Models for Service Systems 11 Introduction 31.1 Network Traffic Engineering: What, Why, How 31.2 The Art of Modeling 81.3 An Example: Delay Equalization 131.3.1 Model Setting 141.3.2 Analysis by Equations 151.3.3 Analysis by Simulation 191.3.4 Takeaways 211.4 Outline of the Book 211.4.1 Plan 211.4.2 Use 251.4.3 Notation 271.5 Further Readings 29Problems 302 Service Systems and Queues 332.1 Service System Structure 332.2 Arrival and Service Processes 352.3 The Queue as a Service System Model 382.4 Queues in Equilibrium 402.4.1 Queues and Stationary Processes 402.4.2 Little's Law 452.5 Palm's Distributions for a Queue 492.6 The Traffic Process 532.7 Performance Metrics 562.7.1 Throughput 562.7.2 Utilization 592.7.3 Loss 592.7.4 Delay 612.7.5 Age of Information 62Summary and Takeaways 63Problems 653 Stochastic Models for Network Traffic 713.1 Introduction 713.2 The Poisson Process 723.2.1 Light versus Heavy Tails 783.2.2 Inhomogeneous Poisson Process 793.2.3 Poisson Process in Multidimensional Spaces 843.2.3.1 Displacement 893.2.3.2 Mapping 893.2.3.3 Thinning 903.2.3.4 Distances 913.2.3.5 Sums and Products on Point Processes 923.2.3.6 Hard Core Processes 943.2.4 Testing for Poisson 963.3 The Markovian Arrival Process 1003.4 Renewal Processes 1033.4.1 Residual Inter-Event Time and Renewal Paradox 1083.4.2 Superposition of Renewal Processes 1103.4.3 Alternating Renewal Processes 1113.4.4 Renewal Reward Processes 1133.5 Birth-Death Processes 1153.6 Branching Processes 121Summary and Takeaways 125Problems 126Part II Queues 1314 Single-Server Queues 1334.1 Introduction and Notation 1334.2 The Embedded Markov Chain Analysis of the M/G/1 Queue 1344.2.1 Queue Length 1364.2.2 Waiting Time 1414.2.3 Busy Period and Idle Time 1454.2.4 Remaining Service Time 1484.2.5 Output Process 1494.2.6 Evaluation of the Probabilities {ak}k element of Z 1514.3 The M/G/1/K Queue 1524.3.1 Exact Solution 1534.3.2 Asymptotic Approximation for Large K 1574.4 Numerical Evaluation of the Queue Length PDF 1664.5 A Special Case: the M/M/1 Queue 1684.6 Optimization of a Single-Server Queue 1704.6.1 Maximization of Net Profit 1714.6.2 Minimization of Age of Information 1744.6.2.1 General Expression of the Average Age of Information 1754.6.2.2 Minimization of the Age of Information for an M/M/1 Model 1774.7 The G/M/1 Queue 1784.8 Matrix-Geometric Queues 1854.8.1 Quasi Birth-Death (QBD) Processes 1864.8.2 M/G/1 and G/M/1 Structured Processes 1884.9 A General Result on Single-Server Queues 192Summary and Takeaways 194Problems 1955 Multi-Server Queues 1995.1 Introduction 1995.2 The Erlang Loss System 2015.2.1 Insensitivity Property of the Erlang Loss System 2115.2.2 A Finite Population Model 2135.2.3 Non-Poisson Input Traffic 2145.2.3.1 Wilkinson's Method 2175.2.3.2 Fredericks' Method 2185.2.4 Multi-Class Erlang Loss System 2215.3 Application of the Erlang Loss Model to Cellular Radio Access Network 2245.3.1 Cell Dimensioning under Quality of Service Constraints 2255.3.2 Number of Handoffs in a Connection Lifetime 2305.3.3 Blocking in a Cell with User Mobility 2325.3.4 Trade-off between Location Updating and Paging 2345.3.5 Dimensioning of a Cell with Two Service Classes 2365.4 The M/M/m Queue 2385.4.1 Finite Queue Size Model 2435.4.2 Resource Sharing versus Isolation 2445.5 Infinite Server Queues 2475.5.1 Analysis of Message Propagation in a Linear Network 252Summary and Takeaways 257Problems 2586 Priorities and Scheduling 2656.1 Introduction 2656.2 Conservation Law 2686.3 M/G/1 Priority Queueing 2726.3.1 Non-FCFS Queueing Disciplines 2736.3.2 Head-of-Line (HOL) Priorities 2766.3.3 Preempt-Resume Priorities 2836.3.4 Shortest Job First 2846.3.5 Shortest Remaining Processing Time 2866.3.6 The mu C Rule 2886.4 Processor Sharing 2896.4.1 The M/G/1 Processor Sharing Model 2906.4.2 Generalized Processor Sharing 2936.4.3 Weighted Fair Queueing 2986.4.4 Credit-Based Scheduling 3026.4.5 Deficit Round Robin Scheduling 3066.4.6 Least Attained Service Scheduling 3086.5 Miscellaneous Scheduling 3126.5.1 Scheduling on a Radio Link 3126.5.1.1 Proportional Fairness 3126.5.1.2 Multi-rate Orthogonal Multiplexing 3136.5.2 Job Dispatching 3186.6 Optimal Scheduling 3246.6.1 Anticipative Systems 3256.6.2 Server-Sharing, Nonanticipative Systems 3256.6.3 Non-Server-Sharing, Nonanticipative Systems 326Summary and Takeaways 327Problems 3277 Queueing Networks 3317.1 Structure of a Queueing Network and Notation 3317.2 Open Queueing Networks 3327.2.1 Optimization of Network Capacities 3457.2.2 Optimal Routing 3477.2.3 Braess Paradox 3507.3 Closed Queueing Networks 3557.3.1 Arrivals See Time Averages (ASTA) 3587.3.2 Buzen's Algorithm for the Computation of the Normalization Constant 3597.3.3 Mean Value Analysis 3607.4 Loss Networks 3697.4.1 Erlang Fixed-Point Approximation 3737.4.2 Alternate Routing 3787.5 Stability of Queueing Networks 3817.5.1 Definition of Stability 3857.5.2 Turning a Stochastic Discrete Queueing Network into a Deterministic Fluid Network 3877.6 Further Readings 390Appendix 391Summary and Takeaways 394Problems 3948 Bounds and Approximations 3998.1 Introduction 3998.2 Bounds for the G/G/1 Queue 4018.2.1 Mean Value Analysis 4048.2.2 Output Process 4068.2.3 Upper and Lower Bounds of the Mean Waiting Time 4078.2.4 Upper Bound of the Waiting Time Probability Distribution 4098.3 Bounds for the G/G/m Queue 4128.4 Approximate Analysis of Isolated G/G Queues 4168.4.1 Approximations from Bounds 4168.4.2 Approximation of the Arrival or Service Process 4178.4.3 Reflected Brownian Motion Approximation 4188.4.4 Heavy-traffic Approximation 4238.5 Approximate Analysis of a Network of G/G/1 Queues 4268.5.1 Superposition of Flows 4278.5.2 Flow Through a Queue 4288.5.3 Bernoulli Splitting of a Flow 4288.5.4 Putting Pieces Together: The Decomposition Method 4298.5.5 Bottleneck Approximation for Closed Queueing Networks 4428.6 Fluid Models 4438.6.1 Deterministic Fluid Model 4448.6.2 From Fluid to Diffusion Model 4528.6.3 Stochastic Fluid Model 4568.6.4 Steady-State Analysis 4598.6.4.1 Infinite Buffer Size (K = infinity ) 4628.6.4.2 Loss Probability 4638.6.5 First Passage Times 4668.6.6 Application of the Stochastic Fluid Model to a Multiplexer with ON-OFF Traffic Sources 468Summary and Takeaways 471Problems 472Part III Networked Systems and Protocols 4779 Multiple Access 4799.1 Introduction 4799.2 Slotted ALOHA 4829.2.1 Analysis of the Naïve Slotted ALOHA 4839.2.2 Finite Population Slotted ALOHA 4879.2.3 Stabilized Slotted ALOHA 4949.3 Pure ALOHA with Variable Packet Times 4999.4 Carrier Sense Multiple Access (CSMA) 5049.4.1 Features of the CSMA Protocol 5059.4.1.1 Clear Channel Assessment 5059.4.1.2 Persistence Policy 5069.4.1.3 Retransmission Policy 5079.4.2 Finite Population Model of CSMA 5099.4.3 Multi-Packet Reception CSMA 5139.4.3.1 Multi-Packet Reception 1-Persistent CSMA with Poisson Traffic 5159.4.3.2 Multi-Packet Reception Nonpersistent CSMA with Poisson Traffic 5199.4.4 Stability of CSMA 5239.4.5 Delay Analysis of Stabilized CSMA 5319.5 Analysis of the WiFi MAC Protocol 5349.5.1 Outline of the IEEE 802.11 DCF Protocol 5349.5.2 Model of CSMA/CA 5389.5.2.1 The Back-off Process 5409.5.2.2 Virtual Slot Time 5439.5.2.3 Saturation Throughput 5459.5.2.4 Service Times of IEEE 802.11 DCF 5499.5.2.5 Correlation between Service Times 5549.5.3 Optimization of Back-off Parameters 5569.5.3.1 Maximization of Throughput 5569.5.3.2 Minimization of Service Time Jitter 5619.5.4 Fairness of CSMA/CA 5659.6 Further Readings 570Appendix 572Summary and Takeaways 573Problems 57510 Congestion Control 57910.1 Introduction 57910.2 Congestion Control Architecture in the Internet 58310.3 Evolution of Congestion Control in the Internet 58710.3.1 TCP Reno 58810.3.1.1 TCP Congestion Control Operations 58910.3.1.2 NewReno 59310.3.1.3 TCP Congestion Control with SACK 59410.3.1.4 Congestion Window Validation 59510.3.2 TCP CUBIC 59610.3.3 TCP Vegas 59810.3.4 Data Center TCP (DCTCP) 60110.3.4.1 Marking at the Switch 60210.3.4.2 ECN-Echo at the Receiver 60310.3.4.3 Controller at the Sender 60310.3.5 Bottleneck Bandwidth and RTT (BBR) 60410.3.5.1 Delivery Rate Estimate 60710.3.5.2 StartUp and Drain 60810.3.5.3 ProbeBW 60910.3.5.4 ProbeRTT 61010.3.5.5 Pseudo-code of BBR Algorithm 61010.4 Traffic Engineering with TCP 61110.5 Fluid Model of a Single TCP Connection Congestion Control 61410.5.1 Classic TCP with Fixed Capacity Bottleneck Link 61510.5.2 Classic TCP with Variable Capacity Bottleneck Link 61710.5.2.1 Discretization of the Evolution Equations 62510.5.2.2 Accuracy of the Fluid Approximation of TCP 62710.5.3 Application to Wireless Links 63010.5.3.1 Random Capacity 63010.5.3.2 TCP over Cellular Link 63210.6 Fluid Model of Multiple TCP Connections Congestion Control 63510.6.1 Negligible Buffering at the Bottleneck 63510.6.2 Classic TCP with Drop Tail Buffer at the Bottleneck 63710.6.3 Classic TCP with AQM at the Bottleneck 63810.6.4 Data Center TCP with FIFO Buffer at the Bottleneck 63910.7 Fairness and Congestion Control 64210.8 Network Utility Maximization (NUM) 64510.9 Challenges to TCP 65210.9.1 Fat-Long Pipes 65310.9.2 Wireless Channels 65510.9.3 Bufferbloat 65610.9.4 Interaction with Applications 658Appendix 659Summary and Takeaways 664Problems 66511 Quality-of-Service Guarantees 66911.1 Introduction 66911.2 Deterministic Service Guarantees 67011.2.1 Arrival Curves 67311.2.2 Service Curves 67711.2.3 Performance Bounds 68111.2.4 Regulators 68311.2.5 Network Calculus 68811.2.5.1 Single Node Analysis 68911.2.5.2 End-to-End Analysis 69211.3 Stochastic Service Guarantees 70311.3.1 Multiplexing with Marginal Buffer Size 70311.3.2 Multiplexing with Non-Negligible Buffer Size 71111.3.3 Effective Bandwidth 71411.3.3.1 Definition of the Effective Bandwidth 71411.3.3.2 Properties of the Effective Bandwidth 71511.3.3.3 Effective Bandwidth of a Markov Source 71611.3.4 Network Analysis and Dimensioning 72111.4 Further Readings 727Appendix 728Summary and Takeaways 732Problems 733A Refresher of Probability, Random Variables, and Stochastic Processes 735A.1 Probability 735A.2 Random Variables 737A.3 Transforms of Probability Distribution Functions 739A.4 Inequalities and Limit Theorems 744A.4.1 Markov Inequality 744A.4.2 Chebychev Inequality 745A.4.3 Jensen Inequality 746A.4.4 Chernov Bound 746A.4.5 Union Bound 747A.4.6 Central Limit Theorem (CLT) 747A.5 Stochastic Processes 748A.6 Markov Chains 749A.6.1 Classification of States 750A.6.2 Recurrence 751A.6.3 Visits to a State 754A.6.4 Asymptotic Behavior and Steady State 756A.6.5 Absorbing Markov Chains 762A.6.6 Continuous-Time Markov Processes 763A.6.7 Sojourn Times in Process States 765A.6.8 Reversibility 766A.6.9 Uniformization 768A.7 Wiener Process (Brownian Motion) 769A.7.1 Wiener Process with an Absorbing Barrier 771A.7.2 Wiener Process with a Reflecting Barrier 772References 775Index 789

About the author

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.

Summary

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.

Product details

• Authors: a Baiocchi, Andrea Baiocchi
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 31.08.2020
• EAN: 9781119632436
• ISBN: 978-1-119-63243-6
• No. of pages: 816
• Subjects: Natural sciences, medicine, IT, technology > Technology > Electronics, electrical engineering, communications engineering; Informatik, Netzwerk, computer science, Systemtechnik, Kommunikationsnetze, Electrical & Electronics Engineering, Elektrotechnik u. Elektronik, Communication Technology - Networks, Kommunikationsnetz, Systemtechnik u. -management, Systems Engineering & Management, Client/Server-Technologie, Client/Server Technologies