Path Routing in Mesh Optical Networks
1st Edition
Will be published approx. on 5. October 2007
Book
Hardback
304 pages
978-0-470-01565-0 (ISBN)
Description
Transport networks evolved from DCS (Digital Cross-connect Systems)-based mesh architectures, to SONET/SDH (Synchronous Optical Networking/Synchronous Digital Hierarchy) ring architectures in the 1990's. In the past few years, technological advancements in optical transport switches have allowed service providers to support the same fast recovery in mesh networks previously available in ring networks while achieving better capacity efficiency and resulting in lower capital cost.
Optical transport networks today not only provide trunking capacity to higher-layer networks, such as inter-router connectivity in an IP-centric infrastructure, but also support efficient routing and fast failure recovery of high-bandwidth services. This is possible due to the emergence of optical network elements that have the intelligence required to efficiently control the network. Optical mesh networks will enable a variety of dynamic services such as bandwidth-on-demand, Just-In-Time bandwidth, bandwidth scheduling, bandwidth brokering, and optical virtual private networks that open up new opportunities for service providers and their customers alike.
Path Routing in Mesh Optical Networks combines both theoretical as well as practical aspects of routing and dimensioning for mesh optical networks. All authors have worked as technical leaders for the equipment vendor Tellium who implemented such capabilities in its product, and whose product was deployed in service provider networks.
Path Routing in Mesh Optical Networks
* Presents an in-depth treatment of a specific class of optical networks, i.e. path-oriented mesh optical networks
* Focuses on routing and recovery, dimensioning, performance analysis and availability in mesh optical networks.
* Explains and analyses routing specifically associated with Dedicated Backup Path Protection (DBPP) and Shared Backup Path Protection (SBPP) recovery architectures.
As most of the core backbone networks evolve to mesh topologies utilizing intelligent network elements for provisioning and recovery of services, Path Routing in MEsh Optical Networks will be an invaluable tool for both researchers and engineers in the industry who are responsible for designing, developing, deploying and maintaining mesh optical networks. It will also be a useful reference book for graduate students and university professors who are interested in optical networks or telecommunications networking.
With a foreword by Professor Wayne D. Grover, author of the book "Mesh-Based Survivable Networks".
Reviews / Votes
"Lecturers of advanced-communications courses, graduate students, and researchers will profit most from reading this book." (IEEE Communications, October 2008)More details
Product info
GB
Edition
1., Auflage
Language
English
Place of publication
United States
Publishing group
John Wiley & Sons Inc
Target group
Professional and scholarly
Product notice
sewn/stitched
Cloth over boards
Dimensions
Height: 255 mm
Width: 177 mm
Thickness: 24 mm
Weight
664 gr
ISBN-13
978-0-470-01565-0 (9780470015650)
Schweitzer Classification
Other editions
Additional editions
Eric Bouillet | Georgios Ellinas | Jean-Francois Labourdette
Path Routing in Mesh Optical Networks
E-Book
10/2007
Wiley
€112.99
Available for download
Persons
Dr. Jean-Francois Labourdette is manager of system engineering at Tellium. He is responsible for all network element and network management system engineering activities. Before that he was manager of network routing and design, where he was responsible for Tellium's routing architecture and algorithms, network dimensioning, and design studies.
Dr. Eric Bouillet is principal engineer at Tellium. He works on the design of optical networks and optimization of light-path provisioning and fault restoration algorithms. Before joining Tellium, Eric was a member of the technical staff in the Mathematical Sciences Research Center in Bell Labs/Lucent Technologies, working in the areas of routing in ATM and optical networks.
Georgios Ellinas is an Associate Professor of Electrical Engineering at City College of the City University of New York. Before joining City College, George was a senior network architect at Tellium Inc. In this role, he worked on light-path provisioning and fault restoration algorithms in optical mesh networks.
Ramu Ramamurthy is lead engineer in the Optical Switch Division at Ciena (Ciena's Optical Switch has been deployed in the worlds biggest optical mesh networks). At Ciena Ramu works on the design and development of Routing and Restoration algorithms and protocols for optical mesh networks. Before that he worked for Tellium, where Ramu was part of a team that implemented Tellium's routing and restoration algorithms for optical mesh networks. His work at Tellium has resulted in several patent applications, and he coauthored several widely referenced publications in leading journals and conferences.
Dr. Eric Bouillet is principal engineer at Tellium. He works on the design of optical networks and optimization of light-path provisioning and fault restoration algorithms. Before joining Tellium, Eric was a member of the technical staff in the Mathematical Sciences Research Center in Bell Labs/Lucent Technologies, working in the areas of routing in ATM and optical networks.
Georgios Ellinas is an Associate Professor of Electrical Engineering at City College of the City University of New York. Before joining City College, George was a senior network architect at Tellium Inc. In this role, he worked on light-path provisioning and fault restoration algorithms in optical mesh networks.
Ramu Ramamurthy is lead engineer in the Optical Switch Division at Ciena (Ciena's Optical Switch has been deployed in the worlds biggest optical mesh networks). At Ciena Ramu works on the design and development of Routing and Restoration algorithms and protocols for optical mesh networks. Before that he worked for Tellium, where Ramu was part of a team that implemented Tellium's routing and restoration algorithms for optical mesh networks. His work at Tellium has resulted in several patent applications, and he coauthored several widely referenced publications in leading journals and conferences.
Content
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.
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.