Table of contents for Path routing in mesh optical networks / Eric Bouillet ... [et al.].

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
Contents
1 Optical Networking 29
1.1 Evolution of Optical Networks . . . . . . . . . . . . . . . . . . . 30
1.1.1 Transparent Network Architecture . . . . . . . . . . . . . 36
1.1.2 Opaque Network Architecture . . . . . . . . . . . . . . . . 40
1.1.3 Translucent Network Architecture . . . . . . . . . . . . . 49
1.2 Layered Network Architecture . . . . . . . . . . . . . . . . . . . . 51
1.2.1 Optical Layer . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.2.2 Logical Layer . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.2.3 Service/Application Layer . . . . . . . . . . . . . . . . . . 57
1.3 Multi-Tier Optical Layer . . . . . . . . . . . . . . . . . . . . . . . 57
1.3.1 One-tier Network Architecture . . . . . . . . . . . . . . . 61
1.3.2 Two-tier Network Architecture . . . . . . . . . . . . . . . 64
1.3.3 Network Scalability . . . . . . . . . . . . . . . . . . . . . 68
1.4 The Current State of Optical Networks . . . . . . . . . . . . . . . 72
1.5 Organization of the Book . . . . . . . . . . . . . . . . . . . . . . 74
2 Recovery in Optical Networks 79
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.2 Failure Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.3 Fault Recovery Classifications . . . . . . . . . . . . . . . . . . . . 84
2.4 Protection of Point-to-Point Systems . . . . . . . . . . . . . . . . 94
2.4.1 (1+1) Protection . . . . . . . . . . . . . . . . . . . . . . . 94
2.4.2 (1:1) Protection . . . . . . . . . . . . . . . . . . . . . . . . 95
2.4.3 (M:N) Protection . . . . . . . . . . . . . . . . . . . . . . . 96
2.5 Ring-Based Protection . . . . . . . . . . . . . . . . . . . . . . . . 97
2.5.1 Failure Recovery in SONET Networks with Ring Topologies 97
2.5.2 Ring-Based Failure Recovery in Optical Networks with
Mesh Topologies . . . . . . . . . . . . . . . . . . . . . . . 100
2.6 Path-Based Protection . . . . . . . . . . . . . . . . . . . . . . . . 118
2.6.1 Dedicated Backup Path Protection (DBPP) in Mesh Networks
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
2.6.2 Shared Back Path Protection (SBPP) in Mesh Networks . 121
2.7 Link/Span-Based Protection . . . . . . . . . . . . . . . . . . . . . 124
2.8 Segment Protection . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9
10 CONTENTS
2.9 Island-Based Protection . . . . . . . . . . . . . . . . . . . . . . . 128
2.10 Mesh Network Restoration . . . . . . . . . . . . . . . . . . . . . . 133
2.10.1 Centralized Restoration Techniques . . . . . . . . . . . . . 136
2.10.2 Distributed Restoration Techniques . . . . . . . . . . . . . 136
2.11 Multi-layer Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 138
2.12 Recovery Triggers and Signaling Mechanisms . . . . . . . . . . . 146
2.13 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
3 Mesh Routing and Restoration Framework 153
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.2 Mesh Protection and Restoration Techniques . . . . . . . . . . . 156
3.2.1 Link-Based Protection . . . . . . . . . . . . . . . . . . . . 157
3.2.2 Path-Based Protection . . . . . . . . . . . . . . . . . . . . 159
3.2.3 Segment-Based Protection . . . . . . . . . . . . . . . . . . 164
3.3 Concept of Shared Risk Groups . . . . . . . . . . . . . . . . . . . 167
3.3.1 Shared Link Risk Groups . . . . . . . . . . . . . . . . . . 168
3.3.2 Shared Node Risk Groups . . . . . . . . . . . . . . . . . . 174
3.3.3 Shared Equipment Risk Groups . . . . . . . . . . . . . . . 175
3.4 Centralized vs Distributed Routing . . . . . . . . . . . . . . . . . 177
3.4.1 Centralized Routing . . . . . . . . . . . . . . . . . . . . . 178
3.4.2 Distributed Routing . . . . . . . . . . . . . . . . . . . . . 182
3.4.3 Centralized vs Distributed Routing Results . . . . . . . . 187
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4 Path Protection and Routing 195
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.2 Routing in Path-Protected Mesh Network . . . . . . . . . . . . . 197
4.3 Protection in Path-Protected Mesh Networks . . . . . . . . . . . 202
4.3.1 Dedicated Backup Path Protected Lightpaths . . . . . . . 203
4.3.2 Shared Backup Path Protected Lightpaths . . . . . . . . . 206
4.3.3 Pre-emptible Lightpaths . . . . . . . . . . . . . . . . . . . 215
4.3.4 Diverse Unprotected Lightpaths with Dual-Homing . . . . 216
4.3.5 Multiple Simultaneous Backup Path Protected Lightpaths 217
4.3.6 Relaxing the Protection Guarantees . . . . . . . . . . . . 220
4.3.7 Impact of Multi-Port Card Diversity Constraints . . . . . 225
4.4 Experiments and Capacity Performance Results . . . . . . . . . . 227
4.4.1 Performance Results for Path-Based Protection Techniques227
4.4.2 Experiments with Multi-Port Card Diversity . . . . . . . 230
4.5 Recovery Time Analysis . . . . . . . . . . . . . . . . . . . . . . . 232
4.6 Recovery Time and Capacity Trade-offs . . . . . . . . . . . . . . 238
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
CONTENTS 11
5 Routing - Part 1: Complexity 245
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
5.2 Network Topology Abstraction . . . . . . . . . . . . . . . . . . . 246
5.2.1 Service Definition . . . . . . . . . . . . . . . . . . . . . . . 248
5.2.2 Operational Models: Online vs Offline Routing . . . . . . 248
5.3 Shortest-Path Routing . . . . . . . . . . . . . . . . . . . . . . . . 249
5.3.1 Dijkstra?s Algorithm . . . . . . . . . . . . . . . . . . . . . 250
5.3.2 Dijkstra Generalization to K-Shortest Paths . . . . . . . . 250
5.3.3 Shortest-Path Routing with Constraints . . . . . . . . . . 252
5.4 Diverse-Path Routing . . . . . . . . . . . . . . . . . . . . . . . . 254
5.4.1 SRG Types . . . . . . . . . . . . . . . . . . . . . . . . . . 254
5.4.2 Diverse-Path Routing with Default SRGs . . . . . . . . . 255
5.4.3 Diverse-Path Routing with Type b SRGs . . . . . . . . . . 259
5.4.4 Diverse-Path Routing with General SRGs . . . . . . . . . 261
5.5 Shared Backup Path Protection Routing . . . . . . . . . . . . . . 262
5.5.1 Protection Guarantees and Rules of Sharing . . . . . . . . 262
5.5.2 Complexity of Shared Backup Path Protection Routing . 263
5.6 Routing ILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.6.1 ILP Description . . . . . . . . . . . . . . . . . . . . . . . . 264
5.6.2 Implementation Experience . . . . . . . . . . . . . . . . . 265
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
5.8 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
5.8.1 Complexity of Diverse-Path Routing with General SRGs . 269
5.8.2 Complexity of SBPP Routing . . . . . . . . . . . . . . . . 271
6 Routing - Part 2: Heuristics 275
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
6.1.1 Operational Models: Centralized vs Distributed Routing . 277
6.1.2 Topology Modeling Example . . . . . . . . . . . . . . . . 278
6.2 Motivating Problems . . . . . . . . . . . . . . . . . . . . . . . . . 279
6.2.1 Heuristic Techniques . . . . . . . . . . . . . . . . . . . . . 281
6.3 K-Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . 282
6.3.1 Yen?s K-Shortest Path Algorithm . . . . . . . . . . . . . . 284
6.3.2 Constrained Shortest-Path Routing . . . . . . . . . . . . . 286
6.4 Diverse-Path Routing . . . . . . . . . . . . . . . . . . . . . . . . 287
6.4.1 Best-Effort Path Diversity . . . . . . . . . . . . . . . . . . 289
6.5 Shared Backup Path Protection Routing . . . . . . . . . . . . . . 290
6.5.1 Heuristic 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 291
6.5.2 Heuristic 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 291
6.6 Routing Preemptible Services . . . . . . . . . . . . . . . . . . . . 293
6.7 General Constrained Routing Framework . . . . . . . . . . . . . 294
6.7.1 Implementation Experience . . . . . . . . . . . . . . . . . 296
6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
12 CONTENTS
7 Enhanced Routing Cost Model for SBPP Services 299
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
7.2 Routing Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
7.3 Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 308
7.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
7.4.1 Effect of _ . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
7.4.2 Effect of _ . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
8 Controlling Sharing 317
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
8.2 Express Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
8.2.1 Routing with Express Links . . . . . . . . . . . . . . . . . 321
8.2.2 Analysis and Results . . . . . . . . . . . . . . . . . . . . . 323
8.2.3 Express Links - Conclusion . . . . . . . . . . . . . . . . . 325
8.3 Limiting Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
8.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
8.3.2 Solution Alternatives . . . . . . . . . . . . . . . . . . . . . 326
8.3.3 Analysis of Capping . . . . . . . . . . . . . . . . . . . . . 328
8.3.4 Analysis of Load-balancing . . . . . . . . . . . . . . . . . 333
8.3.5 Limiting Sharing - Conclusion . . . . . . . . . . . . . . . . 335
8.4 Active Reprovisioning . . . . . . . . . . . . . . . . . . . . . . . . 336
8.4.1 Evaluation of Active Reprovisioning . . . . . . . . . . . . 337
8.4.2 Active Reprovisioning - Conclusion . . . . . . . . . . . . . 340
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
9 Path Computation with Partial Information 343
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
9.2 Complexity of the Deterministic Approach . . . . . . . . . . . . . 351
9.2.1 Complexity of the Failure Dependent Strategy . . . . . . 351
9.2.2 Complexity of the Failure Independent Strategy . . . . . 352
9.3 Probabilistic Approach . . . . . . . . . . . . . . . . . . . . . . . . 353
9.3.1 A Problem of Combinations . . . . . . . . . . . . . . . . . 354
9.3.2 Analogy with SRG Arrangement into a Set of Backup
Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
9.4 Probabilistic Routing Algorithm with Partial Information . . . . 359
9.5 Locally Optimized Channel Selection . . . . . . . . . . . . . . . . 363
9.5.1 Shared Mesh Protection Provisioning Using Vertex Coloring363
9.5.2 Implementation and Applications . . . . . . . . . . . . . . 365
9.6 Required Extensions to Routing Protocols . . . . . . . . . . . . . 367
9.7 Experiments and Results . . . . . . . . . . . . . . . . . . . . . . . 371
9.7.1 Accuracy and Distributions of Probability Functions . . . 371
9.7.2 Comparison of Deterministic Versus Probabilistic Weight
Functions on Real Networks . . . . . . . . . . . . . . . . . 373
9.7.3 Benefits of Locally Optimized Lightpath Provisioning . . 377
9.7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
CONTENTS 13
9.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
10 Lightpath Re-optimization 383
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
10.2 Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 387
10.2.1 Cost model . . . . . . . . . . . . . . . . . . . . . . . . . . 387
10.2.2 Online Routing Algorithm . . . . . . . . . . . . . . . . . . 389
10.3 Re-optimization Algorithm . . . . . . . . . . . . . . . . . . . . . 391
10.4 The Complexity of Re-optimization . . . . . . . . . . . . . . . . . 394
10.4.1 No Prior Placement of Protection Channels or Primary
Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10.4.2 Prior Placement of Protection Channels or Primary Paths 400
10.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
10.5.1 Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . 405
10.5.2 Real Networks . . . . . . . . . . . . . . . . . . . . . . . . 407
10.5.3 Static Network Infrastructure . . . . . . . . . . . . . . . . 409
10.5.4 Growing Network Infrastructure . . . . . . . . . . . . . . 411
10.5.5 Network Dynamic . . . . . . . . . . . . . . . . . . . . . . 414
10.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
11 Dimensioning of Path Protected Mesh Networks 417
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
11.2 Network and Traffic Modeling . . . . . . . . . . . . . . . . . . . . 420
11.3 Mesh Network Characteristics . . . . . . . . . . . . . . . . . . . . 422
11.3.1 Path Length Analysis . . . . . . . . . . . . . . . . . . . . 422
11.3.2 Protection-to-Working Capacity Ratio Analysis . . . . . . 428
11.3.3 Sharing Analysis . . . . . . . . . . . . . . . . . . . . . . . 430
11.4 Asymptotic Behavior of the Protection-to-Working Capacity Ratio432
11.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
11.4.2 General Results . . . . . . . . . . . . . . . . . . . . . . . . 435
11.5 Dimensioning Mesh Optical Networks . . . . . . . . . . . . . . . 442
11.5.1 Node Model and Traffic Conservation Equations . . . . . 442
11.5.2 Dimensioning Examples and Results . . . . . . . . . . . . 445
11.6 The Network Global Expectation Model . . . . . . . . . . . . . . 446
11.7 Accuracy of Analytical Estimates . . . . . . . . . . . . . . . . . . 455
11.8 Recovery Time Performance . . . . . . . . . . . . . . . . . . . . . 456
11.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
12 Service Availability in Path Protected Mesh Networks 463
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
12.2 Network Service Availability . . . . . . . . . . . . . . . . . . . . . 465
12.2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 465
12.2.2 Focus on Dual-Failure Scenarios . . . . . . . . . . . . . . 467
12.2.3 Reliability and Availability . . . . . . . . . . . . . . . . . 468
12.3 Service Availability in Path-Protected Mesh Networks . . . . . . 472
12.3.1 Dual Failure Recoverability . . . . . . . . . . . . . . . . . 473
14 CONTENTS
12.3.2 A Markov Model Approach to Service Availability . . . . 473
12.3.3 Modeling Sharing of Backup Channels . . . . . . . . . . . 478
12.3.4 Impact of Channel Protection . . . . . . . . . . . . . . . . 478
12.3.5 Impact of Re-provisioning . . . . . . . . . . . . . . . . . . 479
12.4 Service Availability in Path-Protected Single and Multi-Domain
Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
12.4.1 Network Recovery Architecture - Single Domain . . . . . 482
12.4.2 Network Recovery Architecture - Multiple Domains . . . 483
12.4.3 Results and Discussion . . . . . . . . . . . . . . . . . . . . 486
12.4.4 A Simple Model . . . . . . . . . . . . . . . . . . . . . . . 489
12.5 Servive Availability in Ring-Protected and Path-Protected Networks
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
12.5.1 Ring Availability Analysis . . . . . . . . . . . . . . . . . . 491
12.5.2 Results and Discussion . . . . . . . . . . . . . . . . . . . . 493
12.5.3 The Simple Model Again . . . . . . . . . . . . . . . . . . 496
12.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497

Library of Congress Subject Headings for this publication:

Optical communications.
Routing (Computer network management).