Optimization of Computer Networks: Modeling and Algorithms: A Hands-On Approach

This book covers the design and optimization of computer networks applying a rigorous optimization methodology, applicable to any network technology.  It is organized into two parts. In Part 1 the reader will learn how to model network problems appearing in computer networks as optimization programs, and use optimization theory to give insights on them.  Four problem types are addressed systematically – traffic routing, capacity dimensioning, congestion control and topology design. Part 2 targets the design of algorithms that solve network problems like the ones modeled in Part 1. Two main approaches are addressed – gradient-like algorithms inspiring distributed network protocols that dynamically adapt to the network, or cross-layer schemes that coordinate the cooperation among protocols; and those focusing on the design of heuristic algorithms for long term static network design and planning problems. Following a hands-on approach, the reader will have access to a large set of examples in real-life technologies like IP, wireless and optical networks.  Implementations of models and algorithms will be available in the open-source Net2Plan tool from which the user will be able to see how the lessons learned take real form in algorithms, and reuse or execute them to obtain numerical solutions. An accompanying link to the author’s own Net2plan software enables readers to produce numerical solutions to a multitude of real-life problems in computer networks (www.net2plan.com).

Table of Contents:
About the Author xv Preface xvii Acknowledgments xxi 1 Introduction 1 1.1 What is a Communication Network? 1 1.2 Capturing the Random User Behavior 4 1.3 Queueing Theory and Optimization Theory 5 1.4 The Rationale and Organization of this Book 6 1.4.1 Part I: Modeling 6 1.4.2 Part II: Algorithms 7 1.4.3 Basic Optimization Requisites: Appendices I, II, and III 10 1.4.4 Net2Plan Tool: Appendix IV 11 Part I MODELING 2 Definitions and Notation 15 2.1 Notation for Sets, Vectors and Matrices 15 2.1.1 Norm Basics 15 2.1.2 Set Basics 16 2.2 Network Topology 17 2.3 Installed Capacities 19 2.4 Traffic Demands 19 2.4.1 Unicast, Anycast, and Multicast Demands 20 2.4.2 Elastic versus Inelastic Demands 21 2.5 Traffic Routing 21 References 22 3 Performance Metrics in Networks 23 3.1 Introduction 23 3.2 Delay 23 3.2.1 Link Delay 23 3.2.2 End-to-End Delay 27 3.2.3 Average Network Delay 27 3.2.4 Convexity Properties 27 3.3 Blocking Probability 28 3.3.1 Link Blocking Probability 28 3.3.2 Demand and Network Blocking Probability 30 3.3.3 Other Blocking Estimations 31 3.3.4 Convexity Properties 34 3.4 Average Number of Hops 34 3.5 Network Congestion 36 3.6 Network Cost 36 3.7 Network Resilience Metrics 37 3.7.1 Shared Risk Groups 40 3.7.2 Simplified Availability Calculations 41 3.7.3 General Model 41 3.8 Network Utility and Fairness in Resource Allocation 44 3.8.1 Fairness in Resource Allocation 44 3.8.2 Fairness and Utility Functions 45 3.8.3 Convexity Properties 47 3.9 Notes and Sources 47 3.10 Exercises 49 References 51 4 Routing Problems 53 4.1 Introduction 53 4.2 Flow-Path Formulation 54 4.2.1 Optimality Analysis 55 4.2.2 Candidate Path List Pre-Computation 58 4.2.3 Ranking of Paths Elaboration 58 4.2.4 Candidate Path List Augmentation (CPLA) 59 4.3 Flow-Link Formulation 61 4.3.1 Flow Conservation Constraints 62 4.3.2 Obtaining the Routing from xde Variables 63 4.3.3 Optimality Analysis 64 4.4 Destination-Link Formulation 65 4.4.1 Obtaining the Routing Tables from xte Variables 67 4.4.2 Some Properties of the Routing Table Representation 67 4.4.3 Comparing Flow-Based and Destination-Based Routing 71 4.5 Convexity Properties of Performance Metrics 71 4.6 Problem Variants 72 4.6.1 Anycast Routing 72 4.6.2 Multicast Routing 74 4.6.3 Non-Bifurcated Routing 75 4.6.4 Integral Routing 77 4.6.5 Destination-Based Shortest Path Routing 77 4.6.6 SRG-Disjoint 1+1 Dedicated Protection Routing 79 4.6.7 Shared Restoration Routing 80 4.6.8 Multi-Hour Routing 81 4.7 Notes and Sources 83 4.8 Exercises 83 References 86 5 Capacity Assignment Problems 88 5.1 Introduction 88 5.2 Long-Term Capacity Planning Problem Variants 89 5.2.1 Capacity Planning for Concave Costs 89 5.2.2 Capacity Planning with Modular Capacities 94 5.2.3 Multi-Period Capacity Planning 97 5.3 Fast Capacity Allocation Problem Variants: Wireless Networks 98 5.3.1 The Wireless Channel 99 5.3.2 Wireless Networks 100 5.3.3 Modeling Wireless Networks 101 5.4 MAC Design in Hard-Interference Scenarios 104 5.4.1 Optimization in Random Access Networks 105 5.4.2 Optimization in Carrier-Sense Networks 109 5.5 Transmission Power Optimization in Soft Interference Scenarios 113 5.6 Notes and Sources 116 5.7 Exercises 117 References 118 6 Congestion Control Problems 120 6.1 Introduction 120 6.2 NUM Model 121 6.2.1 Utility Functions for Elastic and Inelastic Traffic 121 6.2.2 Fair Congestion Control 122 6.2.3 Optimality Conditions 123 6.3 Case Study: TCP 124 6.3.1 Window-Based Flow Control 125 6.3.2 TCP Reno 126 6.3.3 TCP Vegas 131 6.4 Active Queue Management (AQM) 134 6.4.1 A Simplified Model of the TCP-AQM Interplay 135 6.5 Notes and Sources 136 6.6 Exercises 137 References 139 7 Topology Design Problems 141 7.1 Introduction 141 7.2 Node Location Problems 142 7.2.1 Problem Variants 143 7.2.2 Results 144 7.3 Full Topology Design Problems 146 7.3.1 Problem Variants 148 7.3.2 Results 150 7.4 Multilayer Network Design 152 7.5 Notes and Sources 154 7.6 Exercises 154 References 157 Part II ALGORITHMS 8 Gradient Algorithms in Network Design 161 8.1 Introduction 161 8.2 Convergence Rates 163 8.3 Projected Gradient Methods 164 8.3.1 Basic Gradient Projection Algorithm 165 8.3.2 Scaled Projected Gradient Method 165 8.3.3 Singular and Ill-Conditioned Problems 168 8.4 Asynchronous and Distributed Algorithm Implementations 169 8.5 Non-Smooth Functions 172 8.6 Stochastic Gradient Methods 174 8.7 Stopping Criteria 176 8.8 Algorithm Design Hints 177 8.8.1 Dimensioning the Step Size 177 8.8.2 Discrete Step Length 178 8.8.3 Heavy-Ball Methods 179 8.9 Notes and Sources 181 8.10 Exercises 181 References 182 9 Primal Gradient Algorithms 184 9.1 Introduction 184 9.2 Penalty Methods 185 9.2.1 Interior Penalty Methods 185 9.2.2 Exterior Penalty Methods 186 9.3 Adaptive Bifurcated Routing 188 9.3.1 Removing Equality Constraints 189 9.3.2 Optimality and Stability 190 9.3.3 Implementation Example 192 9.4 Congestion Control using Barrier Functions 197 9.4.1 Implementation Example 198 9.4.2 Exterior Penalty 200 9.5 Persistence Probability Adjustment in MAC Protocols 201 9.5.1 Implementation Example 203 9.6 Transmission Power Assignment in Wireless Networks 205 9.6.1 Implementation Example 207 9.7 Notes and Sources 210 9.8 Exercises 211 References 213 10 Dual Gradient Algorithms 214 10.1 Introduction 214 10.2 Adaptive Routing in Data Networks 217 10.2.1 Optimality and Stability 219 10.2.2 Implementation Example 219 10.3 Backpressure (Center-Free) Routing 221 10.3.1 Relation between 𝛾, ΔP, and Average Queue Sizes, Qnd 224 10.3.2 Implementation Example 225 10.4 Congestion Control 228 10.4.1 Optimality and Stability Conditions 229 10.4.2 Implementation Example 230 10.5 Decentralized Optimization of CSMA Window Sizes 231 10.5.1 Implementation Example 234 10.6 Notes and Sources 236 10.7 Exercises 236 References 238 11 Decomposition Techniques 240 11.1 Introduction 240 11.2 Theoretical Fundamentals 241 11.2.1 Primal Decomposition 241 11.2.2 Dual Decomposition 244 11.2.3 Other Decompositions 246 11.3 Cross-Layer Congestion Control and QoS Capacity Allocation 247 11.3.1 Implementation Example 249 11.4 Cross-Layer Congestion Control and Backpressure Routing 249 11.4.1 Implementation Example 252 11.5 Cross-Layer Congestion Control and Power Allocation 253 11.5.1 Implementation Example 254 11.6 Multidomain Routing 256 11.6.1 Implementation Example 258 11.7 Dual Decomposition in Non-Convex Problems 259 11.7.1 Implementation Example 261 11.8 Notes and Sources 261 11.9 Exercises 263 References 265 12 Heuristic Algorithms 266 12.1 Introduction 266 12.1.1 What Complexity Theory Tells us that We cannot Do 266 12.1.2 Our Options 267 12.1.3 Organization and Rationale of this Chapter 268 12.2 Heuristic Design Keys 270 12.2.1 Heuristic Types 270 12.2.2 Intensification versus Diversification 271 12.2.3 How to Assess the Solution Quality 271 12.2.4 Stop Conditions 272 12.2.5 Defining the Cost or Fitness Function 272 12.2.6 Coding the Solution 273 12.3 Local Search Algorithms 273 12.3.1 Design Hints 274 12.4 Simulated Annealing 276 12.4.1 Design hints 277 12.5 Tabu Search 278 12.5.1 Design Hints 280 12.6 Greedy Algorithms 281 12.7 GRASP 282 12.8 Ant Colony Optimization 283 12.8.1 Design Hints 286 12.9 Evolutionary Algorithms 288 12.9.1 Design Hints 289 12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison 291 12.10.1 Case Study Description 291 12.10.2 Algorithm Description 293 12.10.3 Combining Heuristics and ILPs 295 12.10.4 Results 296 12.11 Notes and Sources 297 12.12 Exercises 297 References 299 A Convex Sets. Convex Functions 301 A.1 Convex Sets 301 A.2 Convex and Concave Functions 303 A.2.1 Convexity in Differentiable Functions 303 A.2.2 Strong Convexity/Concavity 306 A.2.3 Convexity in Non-Differentiable Functions 306 A.2.4 Determining the Curvature of a Function 307 A.2.5 Sub-level Sets 310 A.2.6 Epigraphs 311 A.3 Notes and Sources 311 Reference 312 B Mathematical Optimization Basics 313 B.1 Optimization Problems 313 B.2 A Classification of Optimization Problems 315 B.2.1 Linear Programming 315 B.2.2 Convex Programs 318 B.2.3 Nonlinear Programs 320 B.2.4 Integer Programs 321 B.3 Duality 324 B.3.1 Dual Function 324 B.4 Optimality Conditions 330 B.4.1 Optimality Conditions in Problems with Strong Duality 330 B.4.2 Graphical Interpretation of KKT Conditions 333 B.4.3 Optimality Conditions in Problems Without Strong Duality 336 B.5 Sensitivity Analysis 337 B.6 Notes and Sources 339 References 340 C Complexity Theory 341 C.1 Introduction 341 C.2 Deterministic Machines and Deterministic Algorithms 342 C.2.1 Complexity of a Deterministic Algorithm 342 C.2.2 Worst-Case Algorithm Complexity 343 C.2.3 Asymptotic Algorithm Complexity 343 C.2.4 Complexity is a Real Barrier 345 C.3 Non-Deterministic Machines and Non-Deterministic Algorithms 346 C.3.1 Complexity of a Non-Deterministic Algorithm 347 C.4 N and NP Complexity Classes 347 C.5 Polynomial Reductions 349 C.5.1 A Polynomial Time Reduction Example 350 C.6 NP-Completeness 351 C.6.1 An Example Proving NP-Completeness for a Problem 352 C.7 Optimization Problems and Approximation Schemes 352 C.7.1 The NPʘ Class 353 C.7.2 Approximation Algorithms 354 C.7.3 PTAS Reductions 356 C.7.4 NPʘ-Complete Problems 356 C.8 Complexity of Network Design Problems 357 C.9 Notes and Sources 357 References 358 D Net2Plan 359 D.1 Net2Plan 359 D.2 On the Role of Net2Plan in this Book 360 Index 363