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
About the Author :
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.
Review :
?This is an exceptional textbook smoothly linking optimization theory with practical issues of computer network design?Almost all chapters contain a special section entitled ?Notes and Sources? reviewing the key literature, a set of exercises for students, and a comprehensive list of references. The book is full of useful design hints, lists of potential problems facing designers, as well as illustrative examples. Unlike many textbooks on optimization, this work smartly combines the depth of mathematical analysis with a very good understanding of practical engineering issues. One of the important added values of this book is that the code of the devised algorithms implemented in the Net2Plan tool is accessible and algorithm convergence of the case studies is illustrated in empirical tests. To sum it up, this is an excellent textbook not only for engineering students but also for researchers and practicing engineers working in the area of computer and telecommunication network design.? - Andrzej Jajszczyk, AGH University of Science and Technology in Krakow, Poland
