Path Routing in Mesh Optical Networks

List of Figures.

List of Tables.

Foreword.

Preface.

1 Optical Networking.

1.1 Evolution of Optical Network Architectures.

1.1.1 Transparent Networks.

1.1.2 Opaque Networks.

1.1.3 Translucent Networks.

1.2 Layered Network Architecture.

1.2.1 Optical Layer.

1.2.2 Logical Layer.

1.2.3 Service/Application Layer.

1.3 Multi-Tier Optical Layer.

1.3.1 One-Tier Network Architecture.

1.3.2 Two-Tier Network Architecture.

1.3.3 Network Scalability.

1.4 The Current State of Optical Networks.

1.5 Organization of the Book.

2 Recovery in Optical Networks.

2.1 Introduction.

2.2 Failure Recovery.

2.3 Fault Recovery Classifications.

2.4 Protection of Point-to-Point Systems.

2.4.1 (1 + 1) Protection.

2.4.2 (1 : 1) Protection.

2.4.3 (M :N) Protection.

2.5 Ring-Based Protection.

2.5.1 Failure Recovery in SONET Networks with Ring Topologies.

2.5.2 Ring-Based Failure Recovery in Optical Networks with Mesh Topologies.

2.6 Path-Based Protection.

2.6.1 Dedicated Backup Path Protection (DBPP) in Mesh Networks.

2.6.2 Shared Back Path Protection (SBPP) in Mesh Networks.

2.7 Link/Span-Based Protection.

2.8 Segment-Based Protection.

2.9 Island-Based Protection.

2.10 Mesh Network Restoration.

2.10.1 Centralized Restoration Techniques.

2.10.2 Distributed Restoration Techniques.

2.11 Multi-Layer Recovery.

2.12 Recovery Triggers and Signaling Mechanisms.

2.13 Conclusion.

3 Mesh Routing and Recovery Framework.

3.1 Introduction.

3.2 Mesh Protection and Recovery Techniques.

3.2.1 Link-Based Protection.

3.2.2 Path-Based Protection.

3.2.3 Segment-Based Protection.

3.3 Concept of Shared Risk Groups.

3.3.1 Shared Link Risk Groups.

3.3.2 Shared Node Risk Groups.

3.3.3 Shared Equipment Risk Groups.

3.4 Centralized vs Distributed Routing.

3.4.1 Centralized Routing.

3.4.2 Distributed Routing.

3.4.3 Centralized vs Distributed Routing Performance Results.

3.5 Conclusion.

4 Path Routing and Protection.

4.1 Introduction.

4.2 Routing in Path-Protected Mesh Networks.

4.3 Protection in Path-Protected Mesh Networks.

4.3.1 Dedicated Backup Path-Protected Lightpaths.

4.3.2 Shared Backup Path-Protected Lightpaths.

4.3.3 Preemptible Lightpaths.

4.3.4 Diverse Unprotected Lightpaths with Dual-Homing.

4.3.5 Multiple Simultaneous Backup Path-Protected Lightpaths.

4.3.6 Relaxing the Protection Guarantees.

4.3.7 Impact of Multi-Port Card Diversity Constraints.

4.4 Experiments and Capacity Performance Results.

4.4.1 Performance Results for Path-Based Protection Techniques.

4.4.2 Experiments with Multi-Port Card Diversity.

4.5 Recovery Time Analysis.

4.6 Recovery Time and Capacity Trade-Offs.

4.7 Conclusion.

5 Path Routing – Part 1: Complexity.

5.1 Introduction.

5.2 Network Topology Abstraction.

5.2.1 Service Definition.

5.2.2 Operational Models: Online vs Offline Routing.

5.3 Shortest-Path Routing.

5.3.1 Dijkstra’s Algorithm.

5.3.2 Dijkstra’s Algorithm Generalization to K-Shortest Paths.

5.3.3 Shortest-Path Routing with Constraints.

5.4 Diverse-Path Routing.

5.4.1 SRG Types.

5.4.2 Diverse-Path Routing with Default SRGs.

5.4.3 Diverse-Path Routing with Fork SRGs.

5.4.4 Diverse-Path Routing with General SRGs.

5.5 Shared Backup Path Protection Routing.

5.5.1 Protection Guarantees and Rules of Sharing.

5.5.2 Complexity of Shared Backup Path Protection Routing.

5.6 Routing ILP.

5.6.1 ILP Description.

5.6.2 Implementation Experience.

5.7 Conclusion.

5.8 Appendix.

5.8.1 Complexity of Diverse-Path Routing with General SRGs.

5.8.2 Complexity of SBPP Routing.

6 Path Routing – Part 2: Heuristics.

6.1 Introduction.

6.1.1 Operational Models: Centralized vs Distributed Routing.

6.1.2 Topology Modeling Example.

6.2 Motivating Problems.

6.2.1 Heuristic Techniques.

6.3 K-Shortest Path Routing.

6.3.1 Yen’s K-Shortest Path Algorithm.

6.3.2 Constrained Shortest-Path Routing.

6.4 Diverse-Path Routing.

6.4.1 Best-Effort Path Diversity.

6.5 Shared Backup Path Protection Routing.

6.5.1 Sharing-Independent Routing Heuristic.

6.5.2 Sharing-Dependent Routing Heuristic.

6.6 Routing Preemptible Services.

6.7 General Constrained Routing Framework.

6.7.1 Implementation Experience.

6.8 Conclusion.

7 Enhanced Routing Model for SBPP Services.

7.1 Introduction.

7.2 Routing Metric.

7.3 Routing Algorithm.

7.4 Experiments.

7.4.1 Effect of   .

7.4.2 Effect of α.

7.5 Conclusion.

8 Controlling Sharing for SBPP Services.

8.1 Introduction.

8.2 Express Links.

8.2.1 Routing with Express Links.

8.2.2 Analysis and Results.

8.2.3 Express Links–Conclusion.

8.3 Limiting Sharing.

8.3.1 Example.

8.3.2 Solution Alternatives.

8.3.3 Analysis of Capping.

8.3.4 Analysis of Load-Balancing.

8.3.5 Limiting Sharing–Conclusion.

8.4 Analysis of Active Reprovisioning.

8.4.1 Evaluation of Active Reprovisioning.

8.4.2 Active Reprovisioning–Conclusion.

8.5 Conclusion.

9 Path Computation with Partial Information.

9.1 Introduction.

9.2 Complexity of the Deterministic Approach.

9.2.1 Complexity of the Failure Dependent Strategy.

9.2.2 Complexity of the Failure Independent Strategy.

9.3 Probabilistic Approach.

9.3.1 A Problem of Combinations.

9.3.2 Analogy with SRG Arrangement into a Set of Backup Channels.

9.4 Probabilistic Routing Algorithm with Partial Information.

9.5 Locally Optimized Channel Selection.

9.5.1 Shared Mesh Protection Provisioning Using Vertex Coloring.

9.5.2 Implementation and Applications.

9.6 Required Extensions to Routing Protocols.

9.7 Experiments and Performance Results.

9.7.1 Accuracy and Distributions of Probability Functions.

9.7.2 Comparison of Deterministic vs ProbabilisticWeight Functions on Real Networks.

9.7.3 Benefits of Locally Optimized Lightpath Provisioning.

9.7.4 Summary.

9.8 Conclusion.

10 Path Reoptimization.

10.1 Introduction.

10.2 Routing Algorithm.

10.2.1 Cost model.

10.2.2 Online Routing Algorithm.

10.3 Reoptimization Algorithm.

10.4 The Complexity of Reoptimization.

10.4.1 No Prior Placement of Protection Channels or Primary Paths.

10.4.2 Prior Placement of Protection Channels or Primary Paths.

10.5 Experiments.

10.5.1 Calibration.

10.5.2 Real Networks.

10.5.3 Static Network Infrastructure.

10.5.4 Growing Network Infrastructure.

10.5.5 Network Dynamics.

10.6 Conclusion.

11 Dimensioning of Path-Protected Mesh Networks.

11.1 Introduction.

11.2 Network and Traffic Modeling.

11.3 Mesh Network Characteristics.

11.3.1 Path Length Analysis.

11.3.2 Protection-to-Working Capacity Ratio Analysis.

11.3.3 Sharing Analysis.

11.4 Asymptotic Behavior of the Protection-to-Working Capacity Ratio.

11.4.1 Examples.

11.4.2 General Results.

11.5 Dimensioning Mesh Optical Networks.

11.5.1 Node Model and Traffic Conservation Equations.

11.5.2 Dimensioning Examples and Results.

11.6 The Network Global Expectation Model.

11.7 Accuracy of Analytical Estimates.

11.8 Recovery Time Performance.

11.9 Conclusion.

12 Service Availability in Path-Protected Mesh Networks.

12.1 Introduction.

12.2 Network Service Availability.

12.2.1 Motivation.

12.2.2 Focus on Dual-Failure Scenarios.

12.2.3 Reliability and Availability.

12.3 Service Availability in Path-Protected Mesh Networks.

12.3.1 Dual-Failure Recoverability.

12.3.2 A Markov Model Approach to Service Availability.

12.3.3 Modeling Sharing of Backup Channels.

12.3.4 Impact of Channel Protection.

12.3.5 Impact of Reprovisioning.

12.4 Availability in Single and Multiple Domains.

12.4.1 Network Recovery Architecture–Single Domain.

12.4.2 Network Recovery Architecture–Multiple Domains.

12.4.3 Results and Discussion.

12.4.4 A Simple Model.

12.5 Availability in Ring and Path-Protected Networks.

12.5.1 Ring Availability Analysis.

12.5.2 Results and Discussion.

12.5.3 The Simple Model Again.

12.6 Conclusion.

Bibliography.

Index.