Routing, flow, and capacity design in communication and computer networks

Team DDU......Page 1
Contents......Page 8
Foreword......Page 20
Preface......Page 22
PART I INTRODUCTORY NETWORK DESIGN......Page 30
1 Overview......Page 32
1.1 A Network Analogy......Page 33
1.2 Communication and Computer Networks, and Network Providers......Page 38
1.3 Notion of Traffic and Traffic Demand......Page 40
1.3.1 Traffic in the Internet......Page 41
1.3.2 Traffic in the Telephone Network......Page 46
1.3.3 Demand in the Transport Network......Page 49
1.4 A Simple Design Example......Page 51
1.5 Notion of Routing and Flows......Page 52
1.6 Architecture of Networks: Multi-Layer Networks......Page 54
1.7 Network Management Cycle......Page 56
1.8 Scope of the Book......Page 60
1.9 Naming and Numbering Convention......Page 64
1.10 Summary......Page 65
2 Network Design Problems-Notation and Illustrations......Page 66
2.1 A Network Flow Example in Link-Path Formulation......Page 67
2.2 Node-Link Formulation......Page 72
2.3 Notions and Notations......Page 74
2.4 Dimensioning Problems......Page 79
2.5 Shortest-Path Routing......Page 89
2.6 Fair Networks......Page 91
2.7 Topological Design......Page 94
2.8 Restoration Design......Page 95
2.9 *Multi-Layer Networks Modeling......Page 97
2.10 Summary......Page 103
Exercises for 2......Page 105
3 Technology-Related Modeling Examples......Page 106
3.1 IP Networks: Intra-Domain Traffic Engineering......Page 107
3.2 MPLS Networks: Tunneling Optimization......Page 111
3.3 ATM Networks: Virtual Path Design......Page 113
3.4 Digital Circuit-Switched Telephone Networks: Single–Busy Hour and Multi–Busy Hour Network Dimensioning......Page 115
3.5 SONET/SDH Transport Networks: Capacity and Protection Design......Page 119
3.6 SONET/SDH Rings: Ring Bandwidth Design......Page 123
3.7 WDM Networks: Restoration Design with Optical Cross-Connects......Page 125
3.8 IP Over SONET: Combined Two-Layer Design......Page 127
3.9 Summary and Further Reading......Page 130
Exercises for 3......Page 131
PART II DESIGN MODELING AND METHODS......Page 132
4 Network Design Problem Modeling......Page 134
4.1.1 Uncapacitated Problems......Page 135
4.1.2 Capacitated Problems......Page 141
4.2 Routing Restrictions......Page 144
4.2.1 Path Diversity......Page 145
4.2.2 Lower Bounds on Non-Zero Flows......Page 146
4.2.3 Limited Demand Split......Page 147
4.2.4 Integral Flows......Page 152
4.3.1 Modular Links......Page 153
4.3.2 Convex Cost and Delay Functions......Page 157
4.3.3 Concave Link Dimensioning Functions......Page 163
4.4 Budget Constraint......Page 169
4.5 Incremental NDPs......Page 170
4.6 Extensions of Problem Modeling......Page 171
4.6.1 Representing Nodes......Page 172
4.6.2 Capabilities of Link-Path Representation......Page 173
4.7 Summary and Further Reading......Page 174
Exercises for 4......Page 177
5 General Optimization Methods for Network Design......Page 180
5.1.1 Basic Facts About LP......Page 181
5.1.2 Duality in LP......Page 183
5.1.3 Simplex Method......Page 187
5.1.4 Interior Point Methods (IPM)......Page 189
5.2.1 The Branch-and-Bound (BB) Method......Page 191
5.2.2 The Branch-and-Cut (BC) Method......Page 195
5.2.3 The Cutting-Plane Method......Page 196
5.2.4 Dynamic Programming......Page 197
5.3.1 Local Search......Page 198
5.3.2 Simulated Annealing (SAN)......Page 199
5.3.3 Evolutionary Algorithm (EA)......Page 201
5.3.4 Simulated Allocation (SAL)......Page 202
5.3.5 Tabu Search (TS)......Page 205
5.3.6 Other Methods......Page 206
5.4.1 Lagrangian Relaxation (LR)......Page 207
5.4.2 Column Generation Technique for Candidate Path List Augmentation (CPLA)......Page 213
5.4.3 Benders\' Decomposition......Page 221
5.5 Gradient Minimization and Other Approaches for Convex Programming Problems......Page 223
5.5.1 The Flow Deviation (FD) Method......Page 224
5.5.2 The Gradient Projection (GP) Method......Page 225
5.5.3 Dual Method......Page 227
5.6 Special Heuristics for Concave Programming Problems......Page 228
5.6.1 Minimum First Derivative Length Path (MFDLP) Method......Page 229
5.6.2 Greedy Descent (GD) Method......Page 230
5.6.3 Numerical Example......Page 231
5.7 Solving Multi-Commodity Flow Problems......Page 232
5.7.2 Non-Bifurcated Flows......Page 233
5.7.3 Modular Links......Page 234
5.8 Summary and Further Reading......Page 235
Exercises for 5......Page 237
6 Location and Topological Design......Page 240
6.1 Node Location Problem......Page 241
6.1.1 Add Heuristic......Page 243
6.2 Joint Node Location and Link Connectivity Problem......Page 246
6.2.1 Design Formulation: One-Level......Page 247
6.2.2 Design Formulation: Two-Level......Page 252
6.2.3 Design Results......Page 255
6.3 Topological Design......Page 259
6.3.1 Discussion......Page 260
6.3.2 Design with Budget Constraint......Page 261
6.3.3 Design with Extended Objective......Page 263
6.3.4 Transit Nodes and Links Localization Problem......Page 264
6.3.5 Heuristic Algorithms......Page 268
6.3.6 Numerical Results......Page 271
6.4 Lower Bounds for Branch-and-Bound......Page 272
6.4.1 Case: Topological Design with Budget Constraint......Page 273
6.4.2 Case: Transit Node and Link Localization Problem......Page 275
6.5 Summary and Further Reading......Page 278
Exercises for 6......Page 280
7 Networks With Shortest-Path Routing......Page 282
7.1.1 Basic Problem Formulation......Page 285
7.1.2 Adjustments of the Basic Problem......Page 289
7.1.3 Minimum-Hop Routing versus Network Delay: An Illustration......Page 293
7.2.1 MIP Formulation of the Shortest-Path Routing Allocation Problem......Page 295
7.2.2 Duality and Shortest-Path Routing......Page 297
7.3.1 Weight Adjustment (WA)......Page 300
7.3.2 Simulated Annealing (SAN)......Page 301
7.3.3 Lagrangian Relaxation (LR)-Based Dual Approach......Page 302
7.4.1 Formulation of the Two-Phase Optimization Problem......Page 305
7.4.2 Solving Phase 1......Page 307
7.4.3 Solving Phase 2......Page 311
7.5 Impact Due to Stochastic Approaches......Page 312
7.6 Impact of Different Link Weight System......Page 314
7.7 Impact on Different Performance Measures......Page 318
7.8 Uncapacitated Shortest-Path Routing Problem......Page 320
7.9 Optimization of the Link Metric System under Transient Failures......Page 321
7.10 *NP-Completeness of the Shortest-Path Routing Allocation Problem......Page 324
7.11 *Selfish Routing and its Relation to Optimal Routing......Page 327
7.12 Summary and Further Reading......Page 332
Exercises for 7......Page 334
8 Fair Networks......Page 336
8.1.1 An Example......Page 337
8.1.2 Max-Min Fairness (MMF) Allocation Problem for Fixed Paths......Page 338
8.1.3 Proportional Fairness (PF) Allocation Problem for Fixed Paths......Page 343
8.2.1 Capacitated Problems for Flexible Paths......Page 345
8.2.3 Capacitated Problems With Non-Bifurcated Flows......Page 359
8.3 Design Problems for Proportional Fairness (PF)......Page 360
8.3.2 Uncapacitated Problems With a Budget Constraint......Page 361
8.3.3 Uncapacitated Problems With an Extended Objective Function......Page 367
8.3.4 Numerical Examples......Page 369
8.3.5 Minimum Delay......Page 374
8.4 Summary and Further Reading......Page 375
Exercises for 8......Page 377
PART III ADVANCED MODELS......Page 380
9 Restoration and Protection Design of Resilient Networks......Page 382
9.1.1 Characterization of Failure States......Page 383
9.1.2 Re-Establishment Mechanisms......Page 384
9.1.3 Protection by Diversity......Page 387
9.2.1 Link Restoration......Page 390
9.2.2 Hot-Standby Link Protection......Page 393
9.3.1 Unrestricted Reconfiguration......Page 394
9.3.2 Restricted Reconfiguration......Page 397
9.3.3 *Path Restoration With Situation-Dependent Back-up Paths......Page 401
9.3.4 *Path Restoration With Single Back-up Paths......Page 402
9.3.5 Hot-Standby Path Protection......Page 405
9.4.2 Modular Link Capacities and/or Integral Flows......Page 406
9.4.3 Budget Constraint......Page 408
9.4.4 *Routing Restrictions......Page 409
9.4.5 Separating Normal and Protection Capacity......Page 413
9.4.6 Separated Normal and Protection Design......Page 414
9.5.1 Link Capacity Restoration......Page 415
9.5.2 *Path Restoration......Page 418
9.6.1 Dynamic Routing Circuit-Switched Networks......Page 421
9.6.2 Backbone IP, MPLS, and ATM Networks......Page 423
9.6.3 Optical Systems, SONET/SDH, and WDM Networks......Page 426
9.7 Summary and Further Reading......Page 427
Exercises for 9......Page 429
10 Application of Optimization Techniques for Protection and Restoration Design......Page 432
10.1.1 Unrestricted Reconfiguration......Page 433
10.1.2 Restricted Reconfiguration......Page 436
10.1.3 Back-up Path Restoration......Page 440
10.1.4 Numerical Results......Page 442
10.2 Lagrangian Relaxation (LR) With Subgradient Maximization......Page 444
10.2.1 Unrestricted Reconfiguration......Page 446
10.2.2 Restricted Reconfiguration......Page 449
10.2.3 Back-up Path Restoration......Page 451
10.3.1 Unrestricted Reconfiguration......Page 452
10.3.2 Restricted Reconfiguration......Page 458
10.3.3 Numerical Results......Page 461
10.4 Modular Links......Page 464
10.5.1 Simulated Allocation (SAL)......Page 467
10.5.2 Simulated Annealing (SAN)......Page 473
10.5.3 Evolutionary Algorithm (EA)......Page 474
10.6.1 Design Problems......Page 475
10.6.2 Design Methods......Page 478
10.6.3 Numerical Results......Page 479
10.6.4 Remarks......Page 481
Exercises for 10......Page 482
11 Multi-Hour and Multi–Time-Period Network Modeling and Design......Page 484
11.1.1 Illustration of Multi-Hour Dimensioning......Page 485
11.1.2 Multi-Hour Dimensioning Models......Page 487
11.1.3 Multiple Services Case......Page 493
11.1.4 Algorithmic Approaches......Page 494
11.1.5 Computational Results......Page 496
11.1.6 Capacitated Case: Multi-Hour Routing......Page 501
11.2 Multi-Period Design......Page 503
11.2.1 Capacity Planning......Page 504
11.2.2 Multi-Period Flow Routing Problem......Page 509
11.2.3 Model Extensions......Page 512
11.2.5 Dynamic Programming......Page 515
11.2.6 A Hybrid Method......Page 516
11.3 Summary and Further Reading......Page 520
Exercises for 11......Page 522
12 Multi-Layer Networks: Modeling and Design......Page 524
12.1.1 Multi-Layer Technology-Related Example......Page 526
12.1.2 Network Dimensioning Involving Two Resource Layers......Page 529
12.1.3 Allocation Problems with Two Layers of Resources......Page 535
12.1.4 Extensions to More than Two Layers......Page 539
12.1.5 Optimization Methods for Multi-Layer Normal Design Problems......Page 542
12.2.1 The Case of Two Reconfigurable Layers......Page 544
12.2.2 Restoration Involving Only Reconfiguration of Lower Layer......Page 550
12.2.3 Restoration Involving Only Reconfiguration of Upper Layer......Page 551
12.2.4 Extensions......Page 552
12.2.5 Optimization Methods for Multi-Layer Restoration Design......Page 553
12.3.1 Mixed Two-Resource Layer Design With Multi-Hour Traffic and Restoration......Page 554
12.3.2 Multi-Layer Design Problems With Multi-Hour, Multi-Service Traffic......Page 558
12.3.3 Multi-Layer Design Through Layer Separation......Page 562
12.3.4 Failure Propagation......Page 563
12.4 Application of Decomposition Methods for Two-Layer Design......Page 564
12.4.1 LR With Subgradient Maximization of the Dual Function......Page 565
12.4.2 Benders\' Decomposition......Page 569
12.4.3 Path Generation......Page 578
12.5 Numerical Results......Page 582
12.6.1 Diversity and Restoration (with Multi-Hour Traffic)......Page 588
12.6.2 Gain With Dynamic Transport Over Static Transport (with Multi-Service, Multi-Hour Traffic)......Page 592
12.7 Grooming/Multiplex Bundling......Page 594
12.7.1 Illustration of Multi-Layer in the Presence of Grooming......Page 595
12.7.2 Special Cases when Grooming Nodes are Known......Page 597
12.7.3 A General Two Layer Formulation......Page 600
12.8 Summary and Further Reading......Page 603
Exercises for 12......Page 606
13 Restoration Design of Single- and Multi-Layer Fair Networks......Page 610
13.1.1 Problem Formulation and Iterative Solution......Page 611
13.1.2 Algorithm With Dual Non-Blocking Tests......Page 614
13.1.3 *Regular Sets of Blocking Situations......Page 616
13.1.4 Numerical Results......Page 620
13.2.1 Benders\' Decomposition......Page 626
13.2.2 Path Generation......Page 627
13.3.1 Three Basic Problems for Unrestricted Flow Restoration......Page 629
13.3.2 Numerical Examples......Page 632
13.3.3 Decomposition Methods for Two-Layer Networks......Page 637
13.4 Extensions......Page 638
13.5 Summary and Further Reading......Page 639
Exercises for 13......Page 640
A.1 Basic Notions......Page 642
A.2 Karush-Kuhn-Tucker (KKT) Optimality Conditions......Page 643
A.4 Numerical Methods for Finding Minima of Differentiable Problems......Page 645
A.5 Duality......Page 646
A.6 Duality for Convex Programs......Page 647
A.7 Duality for Convex Objective and Linear Constraints......Page 648
A.8 Subgradient Maximization of the Dual Function......Page 649
A.9 Subgradient Maximization of the Dual Function of Linear Programming Problems......Page 651
B.1 Introduction......Page 654
B.2 Complexity of a Problem......Page 655
B.3 Deterministic and Non-Deterministic Machines......Page 656
B.4 The Classes of Problems Known as P and NP......Page 658
B.5 Reducibility Relation between Problems......Page 659
B.7 The Satisfiability Problem and Cook\'s Theorem......Page 660
B.8 Network Flow Problems......Page 661
B.8.1 The D2CIF problem......Page 662
B.8.2 The U2CIF problem......Page 665
B.9 Final Remarks......Page 666
C.1 Introduction and Basic Notions......Page 668
C.2 Basic Shortest-Path Problem......Page 669
C.2.1 Dijkstra\'s Algorithm for Non-Negative Weights......Page 670
C.2.2 Shortest Paths With a Hop Limit......Page 671
C.2.3 Negative Weights......Page 673
C.3.1 K-Shortest Paths......Page 675
C.3.2 All Optimal Paths......Page 676
C.4.1 Shortest Sets of Edge-Disjoint Paths......Page 677
C.4.2 Shortest Sets of Vertex-Disjoint Paths......Page 679
D.1 Solving Linear Programming Problems using Maple,Matlab, and CPLEX......Page 682
D.2 Solving (Mixed) Integer Programming Problems Using CPLEX......Page 685
D.3 Modeling Using AMPL......Page 687
D.4 Final Remark......Page 689
List of Acronyms......Page 690
Solutions to Selected Exercises......Page 692
Bibliography......Page 708
Index......Page 742