Path Routing in Mesh Optical Networks

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.

Table of Contents:
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.