Optimization of computer networks: modeling and algorithms: a hands-on approach

✍ Scribed by Marino, Pablo Pavon

• Publisher: Wiley
• Year: 2016
• Tongue: English
• Leaves: 476
• Category: Library

✦ Synopsis

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

Title Page......Page 15
Copyright......Page 16
Table of Contents......Page 2
Dedication......Page 17
About the Author......Page 18
Preface......Page 19
Reader Requisites and Intended Audience......Page 21
Acknowledgments......Page 23
1.1 What is a Communication Network?......Page 24
1.2 Capturing the Random User Behavior......Page 27
1.3 Queueing Theory and Optimization Theory......Page 28
1.4 The Rationale and Organization of this Book......Page 29
Part One: Modeling......Page 36
2.1 Notation for Sets, Vectors and Matrices......Page 37
2.2 Network Topology......Page 39
2.4 Traffic Demands......Page 41
2.5 Traffic Routing......Page 44
References......Page 45
3.2 Delay......Page 46
3.3 Blocking Probability......Page 51
3.5 Network Congestion......Page 61
3.6 Network Cost......Page 62
3.7 Network Resilience Metrics......Page 63
3.8 Network Utility and Fairness in Resource Allocation......Page 69
3.9 Notes and Sources......Page 74
3.10 Exercises......Page 75
References......Page 78
4.1 Introduction......Page 81
4.2 Flow-Path Formulation......Page 82
4.3 Flow-Link Formulation......Page 91
4.4 Destination-Link Formulation......Page 95
4.5 Convexity Properties of Performance Metrics......Page 104
4.6 Problem Variants......Page 105
4.8 Exercises......Page 116
References......Page 120
5.1 Introduction......Page 122
5.2 Long-Term Capacity Planning Problem Variants......Page 123
5.3 Fast Capacity Allocation Problem Variants: Wireless Networks......Page 134
5.4 MAC Design in Hard-Interference Scenarios......Page 140
5.5 Transmission Power Optimization in Soft Interference Scenarios......Page 153
5.6 Notes and Sources......Page 157
5.7 Exercises......Page 158
References......Page 159
6.1 Introduction......Page 162
6.2 NUM Model......Page 163
6.3 Case Study: TCP......Page 166
6.4 Active Queue Management (AQM)......Page 176
6.5 Notes and Sources......Page 179
6.6 Exercises......Page 180
References......Page 181
7.1 Introduction......Page 185
7.2 Node Location Problems......Page 186
7.3 Full Topology Design Problems......Page 190
7.4 Multilayer Network Design......Page 197
7.6 Exercises......Page 199
References......Page 202
Part Two: Algorithms......Page 203
8.1 Introduction......Page 204
8.2 Convergence Rates......Page 206
8.3 Projected Gradient Methods......Page 207
8.4 Asynchronous and Distributed Algorithm Implementations......Page 214
8.5 Non-Smooth Functions......Page 218
8.6 Stochastic Gradient Methods......Page 219
8.7 Stopping Criteria......Page 222
8.8 Algorithm Design Hints......Page 223
8.9 Notes and Sources......Page 227
8.10 Exercises......Page 228
References......Page 229
9.1 Introduction......Page 231
9.2 Penalty Methods......Page 232
9.3 Adaptive Bifurcated Routing......Page 235
9.4 Congestion Control using Barrier Functions......Page 245
9.5 Persistence Probability Adjustment in MAC Protocols......Page 250
9.6 Transmission Power Assignment in Wireless Networks......Page 255
9.7 Notes and Sources......Page 260
9.8 Exercises......Page 261
References......Page 263
10.1 Introduction......Page 265
10.2 Adaptive Routing in Data Networks......Page 268
10.3 Backpressure (Center-Free) Routing......Page 275
10.4 Congestion Control......Page 282
10.5 Decentralized Optimization of CSMA Window Sizes......Page 285
10.6 Notes and Sources......Page 290
10.7 Exercises......Page 291
References......Page 293
11.1 Introduction......Page 295
11.2 Theoretical Fundamentals......Page 296
11.3 Cross-Layer Congestion Control and QoS Capacity Allocation......Page 303
11.4 Cross-Layer Congestion Control and Backpressure Routing......Page 305
11.5 Cross-Layer Congestion Control and Power Allocation......Page 308
11.6 Multidomain Routing......Page 312
11.7 Dual Decomposition in Non-Convex Problems......Page 316
11.8 Notes and Sources......Page 319
11.9 Exercises......Page 320
References......Page 323
12.1 Introduction......Page 325
12.2 Heuristic Design Keys......Page 329
12.3 Local Search Algorithms......Page 333
12.4 Simulated Annealing......Page 336
12.5 Tabu Search......Page 339
12.6 Greedy Algorithms......Page 342
12.7 GRASP......Page 343
12.8 Ant Colony Optimization......Page 345
12.9 Evolutionary Algorithms......Page 349
12.10 Case Study: Greenfield Plan with Recovery Schemes Comparison......Page 353
12.11 Notes and Sources......Page 359
12.12 Exercises......Page 360
References......Page 362
A.1 Convex Sets......Page 365
A.2 Convex and Concave Functions......Page 366
Reference......Page 378
B.1 Optimization Problems......Page 379
B.2 A Classification of Optimization Problems......Page 381
B.3 Duality......Page 391
B.4 Optimality Conditions......Page 399
B.5 Sensitivity Analysis......Page 408
B.6 Notes and Sources......Page 411
References......Page 412
C.1 Introduction......Page 415
C.2 Deterministic Machines and Deterministic Algorithms......Page 416
C.3 Non-Deterministic Machines and Non-Deterministic Algorithms......Page 419
C.4 �� and ���� Complexity Classes......Page 421
C.5 Polynomial Reductions......Page 423
C.6 ����-Completeness......Page 425
C.7 Optimization Problems and Approximation Schemes......Page 428
C.8 Complexity of Network Design Problems......Page 433
References......Page 434
D.1 Net2Plan......Page 437
D.2 On the Role of Net2Plan in this Book......Page 438
Index......Page 440
End User License Agreement......Page 473