Optimization of Computer Networks

Pablo Pavon Marino, Professor, Technical University of Cartaginia, Spain. Professor Pavon Marino has a PhD in telecommunications and his research interests in the past 15 years have been in network optimization and planning. He also lectures in network optimization and planning courses for computer networks. He is the author or co-author of more than 100 journals and conference papers, and he is the originator of the Net2Plan open-source initiative which includes the Net2Plan tool and public repository of algorithms and network planning resources (www.net2plan.com). He has participated in the organizing and technical committees at multiple international conferences, and he is Technical Editor of the Optical Switch and Networking Journal.

About the author Preface Acknowledgments Companion Website 1 Introduction 3 1.1 What is a communication network? 3 1.2 Capturing the random user behavior 6 1.3 Queueing theory and optimization theory 7 1.4 The rationale and organization of this book 8 1.4.1 Part I: Modeling 9 1.4.2 Part II: Algorithms 10 1.4.3 Basic optimization requisites: Appendixes I, II, III 13 1.4.4 Net2Plan tool: Appendix IV 13 Part One Modeling 15 2 Definitions and notation 17 2.1 Notation for sets, vectors and matrices 17 2.1.1 Norm basics 17 2.1.2 Set basics 18 2.2 Network topology 19 2.3 Installed capacities 20 2.4 Traffic demands 21 2.4.1 Unicast, anycast, multicast demands 22 2.4.2 Elastic vs inelastic demands 23 2.5 Traffic routing 24 3 Performance metrics in networks 27 3.1 Delay 27 3.1.1 Link delay 27 3.1.2 End-to-end delay 31 3.1.3 Average network delay 31 3.1.4 Convexity properties 32 3.2 Blocking probability 32 3.2.1 Link blocking probability 32 3.2.2 Demand and network blocking probability 35 3.2.3 Other blocking estimations 36 3.2.4 Convexity properties 38 3.3 Average number of hops 39 3.4 Network congestion 39 3.5 Network cost 41 3.6 Network resilience metrics 42 3.6.1 Shared Risk Groups 44 3.6.2 Simplified availability calculations 45 3.6.3 General model 46 3.7 Network utility & fairness in resource allocation 48 3.7.1 Fairness in resource allocation 49 3.7.2 Fairness and utility functions 50 3.7.3 Convexity properties 52 3.8 Notes and sources 52 3.9 Exercises 54 4 Routing problems 57 4.1 Introduction 57 4.2 Flow-path formulation 59 4.2.1 Optimality analysis 60 4.2.2 Candidate path list pre-computation 62 4.2.3 Ranking of paths elaboration 63 4.2.4 Candidate Path List Augmentation (CPLA) 63 4.3 Flow-link formulation 66 4.3.1 Optimality analysis 68 4.4 Destination-link formulation 70 4.4.1 Obtaining the routing tables from xte variables 71 4.4.2 Some properties of the routing table representation 72 4.4.3 Comparing flow-based and destination-based routing 76 4.5 Convexity properties of performance metrics 76 4.6 Problem variants 77 4.6.1 Anycast routing 78 4.6.2 Multicast routing 78 4.6.3 Non-bifurcated routing 81 4.6.4 Integral routing 82 4.6.5 Destination-based shortest path routing 82 4.6.6 SRG-disjoint 1+1 dedicated protection routing 84 4.6.7 Shared restoration routing 85 4.6.8 Multi-hour routing 87 4.7 Notes and sources 88 4.8 Exercises 89 5 Capacity assignment problems 93 5.1 Introduction 93 5.2 Long-term capacity planning problem variants 94 5.2.1 Capacity planning for concave costs 94 5.2.2 Capacity planning with modular capacities 100 5.2.3 Multi-period capacity planning 102 5.3 Fast capacity allocation problem variants: wireless networks 104 5.3.1 The wireless channel 104 5.3.2 Wireless networks 106 5.3.3 Modeling wireless networks 107 5.4 MAC design in hard-interference scenarios 110 5.4.1 Optimization in random access networks 112 5.4.2 Optimization in carrier-sense networks 116 5.5 Transmission power optimization in soft interference scenarios 120 5.6 Notes and sources 123 5.7 Exercises 124 6 Congestion control problems 127 6.1 Introduction 127 6.2 NUM model 128 6.2.1 Utility functions for elastic and inelastic traffic 129 6.2.2 Fair congestion control 130 6.2.3 Optimality conditions 130 6.3 Case study: TCP 132 6.3.1 Window-based flow control 132 6.3.2 TCP Reno 134 6.3.3 TCP Vegas 139 6.4 Active Queue Management (AQM) 141 6.4.1 A simplified model of the TCP-AQM interplay 142 6.5 Notes and sources 144 6.6 Exercises 145 7 Topology design problems 147 7.1 Introduction 147 7.2 Node location problems 148 7.2.1 Problem variants 149 7.2.2 Results 150 7.3 Full topology design problems 152 7.3.1 Problem variants 154 7.3.2 Results 156 7.4 Multilayer network design 157 7.5 Notes and sources 160 7.6 Exercises 161 Part Two Algorithms 165 8 Gradient algorithms in network design 167 8.1 Introduction 167 8.2 Convergence rates 169 8.3 Projected gradient methods 170 8.3.1 Basic gradient projection algorithm 171 8.3.2 Scaled projected gradient method 172 8.3.3 Singular and ill-conditioned problems 174 8.4 Asynchronous and distributed algorithm implementations 175 8.5 Non-smooth functions 179 8.6 Stochastic gradient methods 180 8.7 Stopping criteria 183 8.8 Algorithm design hints 184 8.8.1 Dimensioning the step size 184 8.8.2 Discrete step length 185 8.8.3 Heavy-ball methods 186 8.9 Notes and sources 188 8.10 Exercises 188 9 Primal gradient algorithms 191 9.1 Introduction 191 9.2 Penalty methods 192 9.2.1 Interior penalty methods 192 9.2.2 Exterior penalty methods 193 9.3 Adaptive bifurcated routing 195 9.3.1 Optimality and stability 197 9.3.2 Implementation example 198 9.4 Congestion control using barrier functions 204 9.4.1 Implementation example 205 9.4.2 Exterior penalty 208 9.5 Persistence probability adjustment in MAC protocols 209 9.5.1 Implementation example 210 9.6 Transmission power assignment in wireless networks 214 9.6.1 Implementation example 216 9.7 Notes and sources 217 9.8 Exercises 219 10 Dual gradient algorithms 223 10.1 Introduction 223 10.2 Adaptive routing in data networks 226 10.2.1 Implementation example 229 10.3 Backpressure (center-free) routing 231 10.3.1 Implementation example 235 10.4 Congestion control 238 10.4.1 Implementation example 240 10.5 Decentralized optimization of CSMA window sizes 241 10.5.1 Implementation example 244 10.6 Notes and sources 245 10.7 Exercises 246 11 Decomposition techniques 249 11.1 Introduction 249 11.2 Theoretical fundamentals 250 11.2.1 Primal decomposition 251 11.2.2 Dual decomposition 253 11.2.3 Other decompositions 255 11.3 Cross-layer congestion control and QoS capacity allocation 257 11.3.1 Implementation example 259 11.4 Cross-layer congestion control and backpressure routing 259 11.4.1 Implementation example 261 11.5 Cross-layer congestion control and power allocation 262 11.5.1 Implementation example 264 11.6 Multidomain routing 265 11.6.1 Implementation example 268 11.7 Dual decomposition in non-convex problems 270 11.7.1 Implementation example 271 11.8 Notes and sources 272 11.9 Exercises 273 12 Heuristic algorithms 277 12.1 Introduction 277 12.1.1 What complexity theory tells that we cannot do 278 12.1.2 Our options 278 12.1.3 Organization and rationale of this chapter 279 12.2 Heuristic design keys 281 12.2.1 Heuristic types 281 12.2.2 Intensification vs. diversification 282 12.2.3 How to assess the solution quality 283 12.2.4 Stop conditions 283 12.2.5 Defining the cost or fitness function 284 12.2.6 Coding the solution 284 12.3 Local search algorithms 285 12.3.1 Design hints 285 12.4 Simulated annealing 286 12.4.1 Design hints 289 12.5 Tabu search 290 12.5.1 Design hints 291 12.6 Greedy algorithms 293 12.7 GRASP 294 12.8 Ant colony optimization 295 12.8.1 Design hints 297 12.9 Evolutionary algorithms 299 12.9.1 Design hints 300 12.10Case study: greenfield plan with recovery schemes comparison 303 12.10.1 Case study description 304 12.10.2Algorithm description 305 12.10.3 Combining heuristics and ILPs 308 12.10.4 Results 308 12.11Notes and sources 309 12.12Exercises 310 Appendix A Convex sets. Convex functions 313 A.1 Convex sets 313 A.2 Convex and concave functions 315 A.2.1 Convexity in differentiable functions 316 A.2.2 Strong convexity/concavity 318 A.2.3 Convexity in non-differentiable functions 318 A.2.4 Determining the curvature of a function 320 A.2.5 Sub-level sets 322 A.2.6 Epigraphs 324 A.3 Notes and sources 324 Appendix B Mathematical optimization basics 327 B.1 Optimization problems 327 B.2 A classification of optimization problems 329 B.2.1 Linear programming 329 B.2.2 Convex programs 332 B.2.3 Nonlinear programs 335 B.2.4 Integer programs 337 B.3 Duality 338 B.4 Optimality conditions 346 B.4.1 Optimality conditions in problems with strong duality 346 B.4.2 Graphical interpretation of KKT conditions 349 B.4.3 Optimality conditions in problems without strong duality 350 B.5 Sensitivity analysis 353 B.6 Notes and sources 356 Appendix C Complexity theory 357 C.1 Introduction 357 C.2 Deterministic machines and deterministic algorithms 358 C.2.1 Complexity of a deterministic algorithm 358 C.2.2 Worst-case algorithm complexity 359 C.2.3 Asymptotic algorithm complexity 360 C.2.4 Complexity is a real barrier 361 C.3 Non-deterministic machines and non-deterministic algorithms 362 C.3.1 Complexity of a non-deterministic algorithm 362 C.4 P and NP complexity classes 364 C.5 Polynomial reductions 365 C.5.1 A polynomial time reduction example 366 C.6 NP-completeness 367 C.6.1 An example proving NP-completeness for a problem 368 C.7 Optimization problems and approximation schemes 370 C.7.1 The NPO class 370 C.7.2 Approximation algorithms 371 C.7.3 PTAS reductions 372 C.7.4 NPO-complete problems 373 C.8 Complexity of network design problems 374 C.9 Notes and sources 374 Appendix D Net2Plan 369 D.1 Net2Plan 369 D.2 On the role of Net2Plan in this book 370 Index