Mesh-based Survivable Transport Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking

1. Orientation to Transport Networks and Technology.

Aggregation of Service Layer Traffic into Transport Demands. Concept of Logical versus Physical Networks: Virtual Topology. Multiplexing and Switching. Concept of Transparency. Layering and Partitioning. Plesiochronous Digital Hierarchy (PDH). SONET / SDH. SONET Overheads. Generic SONET Terminal Multiplexer. Generic SONET Add/Drop Multiplexer. Digital Cross-Connect Systems. Hubs, Grooming and Backhaul. Fundamental Efficiency of Edge Grooming and Core Transport. Broadband ISDN and Asynchronous Transfer Mode (ATM). Concept of Label-Switching: The Basis of ATM and MPLS. Multi-Protocol Label Switching (MPLS). Network Planning Aspects of Transport Networks. Modularity and Economy-of-Scale. Fiber Route Structures. Network Redundancy. Shared-Risk Entities and Fault Multiplication. Demand Patterns. Short and Long-Term Transport Network Planning Contexts.

2. Internet Protocol and Optical Networking.

Increasing Network Efficiency. DWDM and Optical Networking. Coarse and Dense WDM. Optical Amplifiers. Regenerators. Optical Add/drop Multiplexers (OADMs). Transparent, Opaque and Translucent Optical Networks. Routing and Wavelength Assignment (RWA) Problem. Optical Cross-Connects (OXC). Wavelength Path Optical Cross-connect (WP-OXC). Optical Cross-Connect for Virtual Wavelength Paths (VWP-OXC). Partial Wavelength Converting OXC (PVWP-OXC). Data-Centric Payloads and Formats for the Transport Network. Computer Interconnect and SAN. Gigabit Ethernet (GbE) and 10 Gb/s Ethernet (10GbE). Enhancing SONET for Data Transport. Generalized Framing Procedure (GFP). Virtual Concatenation (VC). Link Capacity Adjustment Scheme (LCAS). Optical Service Channels and Digital Wrapper. Optical Service Channel (OSC). Digital Wrapper. IP-Centric Control of Optical Networks. Basic Internet Protocols. TCP. OSPF. Multi-Protocol Label Switching (MPLS). Extensions for IP-Centric Control of Optical Networks. OSPF-TE. Link Management Protocol (LMP). MPlS and Generalized MPLS (GMPLS). Constraint-Based Routing Label Distribution Protocol (CR-LDP). Network Planning Issues. Does IP-Centric Control Also Imply an “All-router” Network? Concept of a “Transport Stabilized” Internet.

3. Failure Impacts, Survivability Principles, and Measures of Survivability.

Transport Network Failures and Their Impacts. Causes of Failure. Crawford's Study. Effects of Outage Duration. Is 50 ms Restoration Necessary? Survivability Principles from the Ground Up. Physical Layer Survivability Measures. Physical Protection Methods. Reducing Physical Protection Costs with Restoration Schemes. Physical Layer Topology Considerations. The Problem of Diversity Integrity. Survivability at the Transmission System Layer. “Linear” Transmission Systems. Automatic Protection Switching (APS). Reversion. “Extra Traffic” Feature. AIS Concept. Hitless Switching. Unidirectional Path-Switched Rings (UPSR). Bidirectional Line-Switched Rings (BLSR). Resilient Packet Rings (RPR). Ring Covers. Generalized Loopback Networks. System Layer Protection Without 100% Redundancy: p-Cycles. Logical Layer Survivability Schemes. Concepts of Protection, Restoration and Distributed Preplanning. Span Restoration or Span Protection. Meta-mesh. p-Cycles. Path Restoration. Shared-Backup Path Protection (SBPP). Segmented or Short-Leap Shared Protection (SLSP). GMPLS Automatic Reprovisioning as a Restoration Mechanism. Service Layer Survivability Schemes. Comparative Advantages of Different Layers for Survivability. Measures of Outage and Survivability Performance. McDonald's ULE. The (U,D,E) Framework for Quantifying Service Outages. Measures of Network Survivability. Restorability. Reliability. Availability. Concept of “Unavailability”. Series Unavailability Relationships. Parallel Unavailability Relationships. Series-Parallel Reductions. Network Reliability. Two-Terminal Network Reliability. Factoring the Graph and Conditional Decomposition. Expected Loss of Traffic and of Connectivity. Expected Loss of Traffic (ELT). Annual Expected Downtime of Connection (AEDC).

4. Graph Theory, Routing, and Optimization.

Graph Theory Related to Transport Networking. Set Concepts and Notation. Graph Theory as it Relates to Transport Networks. Transport Network Terminology. Distinct and Disjoint Routes. Data Representations of Graphs. Computational Complexity. Asymptotic Notation. P and NP. Shortest Path Algorithms. Concepts of Labeling and Scanning. The Dijkstra Algorithm. Bhandari's Modified Dijkstra Algorithms. BFS Dijkstra. Modified Dijkstra. k-Shortest Path Algorithms. All Distinct Routes. Maximum Flow: Concept and Algorithm. The Min-Cut Max-Flow Theorem. Maximum Flow Algorithm. The Trap Topology. k-Shortest Paths as an Approximation to Maximum Flow. Shortest Disjoint Path Pair. Finding Biconnected Components of a Graph. The Cut-Tree. Finding All Cycles of a Graph. Fundamental Set of Cycles. Depth-First Search for Cycle Enumeration. Optimization Methods for Network Design. Linear and Integer Programming. The Role and Limitations for Mathematical Programming. General Symbolic Form of an LP or ILP. Example Development of an Optimization Model. Making the Problem an Integer Linear Program. Duality. Unimodularity and Special Structures. Network Flow Problems. The Transportation Problem. Two-Terminal MCNF (or Minimum Cost Routing). Maximum Flow as an MCNF. Multi-Commodity Maximum Flow (MCMF). Maximum Sum Multi-Commodity Maximum Flow (MS-MCMF). Maximum Concurrent MCMF (MConMF). Techniques for Formulating LP/ILP Problems. Mutual Exclusion. Switching. Peak Minimizing. Bicriteria Studies and Pareto Optimal Solutions. Representing Routes and Graph Topology. Modularity of Capacity. Implicit Representation of Functionality. Tips for Getting the Solutions. Lagrangean Techniques. Vector-Matrix Notation for an LP Problem. Lagrange Multipliers. Extension to Inequalities. Lagrangean Relaxation and the Lagrangean Dual. Complexity of LP and ILP. Other Combinatorial Optimization Methods: Meta-Heuristics. Simulated Annealing. Genetic Algorithms. Tabu Search. Comparison of Optimization Techniques.

5. Span-Restorable and Span-Protected Mesh Networks.

Updating the View of Span Restoration. Operational Concepts for Span Restoration. Details of the Span Restoration (SR) Concept. Concept of Distributed Self-Healing Mesh Restoration and DRAs. Self-Organizing Nodal Interaction via Statelets. Distributed Protection Preplanning with a DRA. The Working Capacity Envelope Concept for Dynamic Demands. Demand-Adaptive Definition of the Working Capacity Envelope. Concept of First-Failure Protection and Second-Failure Restoration. Spare Capacity Design of Span-Restorable Mesh Networks. Overview of the Problem. Basic Node-Arc Formulation. Basic Arc-Path Formulation. Herzberg and Bye's Hop-Limited Formulation. Large-Scale Practicality of Hop-Limited Arc-Path SCA. Concept of a Threshold Hop Limit. Cut-Oriented Formulations of the SCA Problem. Venables' Iterated Cutsets Method for SCA. Summary: A Complete Cut-Oriented SCA Methodology. Jointly Optimized Working and Spare Capacity Assignment. Joint Capacity Allocation (JCA) Model. Isolated Nodal Bounding Considerations. Effect of Capacity Balance on Redundancy. Understanding the JCA Benefit. Operational Strategy for JCA-Based Incremental Capacity Planning. The Forcer Concept. Forcer Analysis Procedure. Modular Span-Restorable Mesh Capacity Design. Modular-Aware Spare Capacity Allocation (MSCA). Modular Joint Capacity Allocation (MJCA). Comparative Results with the Modular Design Formulations. Modeling Modularity with Per-Channel Provisioning Costs. A Generic Policy for Generating Eligible Route Sets. Generating Eligible Restoration Route Sets. Generating Eligible Route Sets for Working Paths. Chain Optimized Mesh Design for Low Connectivity Graphs. The Meta-Mesh Concept. Chain Subnetworks Under Ordinary SCA or JCA. Logical Chain Bypass Spans. Restoration in the Bypassed Chains. Design Method to Effect the Meta-Mesh Concept. Sample Results. Span-Restorable Capacity Design with Multiple Service Classes. How Multi-QoP Span Restoration Works. Multi-QoP Capacity Design. Multi-QoP MJCA. Sample Results on Multi-QoP Designs. Approximation Models for Multi-QoP Design. Maximum Revenue Multi-QoP Design. Incremental Capacity Planning for Span-Restorable Networks. What Value for Rearrangeability? Bicriteria Design Methods for Span-Restorable Mesh Networks. Bicriteria Design for Reducing Restoration Path Lengths. Bicriterion Design for Maintenance Risk Reduction. Bicriterion Design for Best Efforts and Preemptible Services.

6. Path Restoration and Shared Backup Path Protection.

Understanding Path Protection, Path Restoration and Path Segments. Is Path Restoration Just Span Restoration Without Loopbacks? Concept of Mutual Capacity in Path Restoration. Experiments Simulating GMPLS Auto Reprovisioning. Network Recovery From Node Loss. A Framework for Path Restoration Routing and Capacity Design. Specifying Failure Scenarios. Specifying Network Structure, Capacity and Eligible Routes. The Path Restoration Rerouting Problem. Concepts of Stub Release and Stub Reuse in Path Restoration. Lower Bounds on Redundancy. Master Formulation for Path Restoration Capacity Design. Simplest Model for Path Restoration Capacity Design. Comparative Study of Span and Path-Restorable Designs. Demand Dispersion and Routing Effects. Shared Backup Path Protection (SBPP). Infeasibility in Greedy Disjoint Path Pairs. Discounting the Shared Backup Path: Asymmetric Path Pairs. Disjoint Primary/Shared Backup Relationships: Venn Diagram. Optimal Design of Shared-Backup Path Protected Networks. Wavelength Assignment Under SBPP. SBPP Design with Limits on the Sharing of Spare Capacity. Capacity Effects of Sharing Limits in SBPP. Arc-Flow Models for SBPP. Lagrangean Relaxation for Path-Oriented Capacity Design Problems. Solution Method for the LR Problem for a Given m Vector. Iterative Maximization of the LR Problem on m. Heuristics for Path-Restorable Network Design. Phase 1 Heuristics—Design Construction. Modeling Existing Capacity. Minimum Incremental Cost Routing. Iterated-Dijkstra to Solve MIC_NF. Alternate Phase 1 Algorithm. Putting Modularity Considerations in the Iterative Heuristic. Concepts of Aggregating Prerouting and Pseudo-Cost Functions. Modular Minimum Incremental Cost Network Flow (mod_MIC_NF). Modular Minimal Incremental Cost Multi-Commodity Network Flow. Phase 2 Forcer-Oriented Design Improvement Heuristic. A Tabu Search Heuristic for Design Tightening. Simulated Allocation Type of Algorithm for Design Tightening. Efficiently Updating the Spare Capacity Design. Classifying Spans by Forcer Status. Path-Shift Strategies for Direct Forcer-Based Improvements.

7. Oversubscription-Based Design of Shared Backup Path Protection for MPLS or ATM.

Concept of Oversubscription. Historical Background and Some Misconceptions. Overview of MPLS Shared Backup Path Protection and ATM Backup VP Concepts. The Oversubscription Design Framework. Defining the Oversubscription Factor Xj,i. KST Algorithm for Backup Path Capacity Allocation. Oversubscription Effects with KST-Alg. Minimum Spare Capacity with Limits on Oversubscription. Minimum Peak Oversubscription with Given Spare Capacity. OS-3: Minimum Total Capacity with Limited Oversubscription. Related Bounds on Spare Capacity. Upper Bound Based on KST Algorithm. Lower Bound Based on the LP Relaxation of OS-1. Illustrative Results and Discussion. The Design Trade-off between Spare Capacity and Xtol. Statistics of Individual Xj,i Values under OS-1 Design. OS-2 Minimization of Oversubscription with Given Capacity. OS-3 Benefit of Jointly Optimizing Primary and Backup Paths. Determining the Maximum Tolerable Oversubscription. Simulation Design for Equivalent Bandwidth. Illustrative Results. Other Comments on Determining Xtol. Extension and Application to Multiple Classes of Service. Adaptive Link-Based Implementation of Priority Schemes.

8. Dual Failures, Nodal Bypass and Common Duct Effects on Design and Availability.

Are Dual Failures a Real Concern? Dual Failure Restorability Analysis of Span-Restorable Networks. Canonical Dual Failure Scenarios. Determining the Network Average Dual Failure Restorability, R2. Computational Approach. Models for the Restoration Process. Experimental Results. Relationship Between Dual Failure Restorability and Availability. Axioms and Role of Availability Analysis of Networks. Average Case Availability of Service Paths. Availability Calculation for a Specific Path. Implications for an Ultra-High Availability Class of Service. Link to the 1FP-2FR Concept. Dual Failure Availability Analysis for SBPP Networks. Experimental Comparison of SBPP and Span Restoration. Optimizing Spare Capacity Design for Dual Failures. Minimum Capacity to Withstand All Dual Failures (DFMC). Dual Failure Maximum Restorability (DFMR). Pure Redistribution of Spare Capacity to Enhance R2. Multi-Service Restorability Capacity Placement Design (MRCP). Experimental Results. Dual Failure Considerations Arising From Express Routes. Express Routes and Nodal Bypass. Does a Nodal Bypass Require Increased Spare Capacity? When Does Bypass Yield a Spare Capacity Reduction? Optimal Capacity Design with Bypasses. Minimum Spare Capacity Given a Set of Express Routes. Allowing the Model to Dimension the Express Routes. Maximum Port Elimination by Bypass at Minimum Spare Capacity. Sample Results. Iterative Optimization of Express Routes. Effects of Dual Failures Arising from Shared Risk Link Groups. Comparing Span SRLG and Bypass Dual-Failure Situations. Capacity Design for a Known Set of SRLGs. Effects of SRLGs on Spare Capacity. Randomly Occurring SRLGs. Availability Benefit of Coincident SRLG Design Coverage. Predicting the Impact of a Specific SRLG. Effects of Nodal Degree. Effects of Topological Location. Effects of Working Capacity Disparity. Benefit of Removing the Most Troublesome SRLGs. SRLG Effects on Other Protection Schemes.

9. Mesh Network Topology Design and Evolution.

Different Contexts and Benefits of Topology Planning. Topology Design for Working Flow Only. Branch Exchange. Cut Saturation. The MENTOR Algorithm. Yaged's Fixed Point Convergence Method. The Fixed Charge and Routing (FCR) Problem. Interacting Effects in Mesh-Survivable Topology. Experimental Studies of Mesh Capacity versus Graph Connectivity. How Economy of Scale Changes the Optimal Topology. The Single-Span Addition Problem. How “Partial Express” Flows Can Suggest New Spans. Frequency and Remoteness Metrics for Prospective Span Additions. Overall Study Technique for Single-Span Additions. The Complete Mesh Topology, Routing, and Spare Capacity Problem. Added Valid Knowledge Constraints. Relaxations. Complexity of MTRS. Sample Results: Studies with MTRS. Effect of Edge-to-Capacity Cost Ratio, W. Effect of Demand Intensity and Demand Pattern. A Three-Part Heuristic for MTRS. Step W1: Working-only Fixed Charge Plus Routing. Step S2: Reserve Network Fixed Charge and Sparing (RN-FCS). Step J3: Restricted MTRS for Final Topology Selection. Useful Bounds from Steps W1 and J3. Studies with the Three-Part Heuristic for MTRS. Method. Results. Discussion. Insights from the Three-Part Heuristic. Ezema's Edge-Limiting Criteria. Successive Inclusion Heuristic. Graph Sifting and Graph Repair for Topology Search. Graph Generation. Graph Testing. Repair Procedures. A Tabu Search Extension of the Graph Sifter Architecture. Range Sweeping Topology Search. Sample Results with Sweep Search. Overall Strategy and Applications for Topology Planning.

10. p-Cycles.

The Concept of p-Cycles. Why Straddling Spans Are So Significant. Historical Origins: Preconfiguration and the “Clamshell” Diagram. Other Important Properties of p-Cycles. Enhanced Rings. Cycle Covers and “Protection Cycles” per Ellinas et al. Optimal Capacity Design of Networks with p-Cycles. Concept of “Useful Paths” for p-Cycle Design. Maximum p-Cycle Restorability with a Given Spare Capacity. Minimum Spare Capacity for 100% p-Cycle Restorability. Adding a Span Capacity Constraint. Results with Basic Capacity Formulations. Joint Optimization of Working Path Routing and p-Cycle Placement. Application of p-Cycles to DWDM Networks. Wavelength Continuity—the WP case. Dark-Fiber p-Cycles: Protection without any Wavelength Conversion. p-Cycle Wavelength Path (WP) Design Problems. Summary and Discussion of p-Cycle Design Models. Schupke et al — Case Study for DWDM p-Cycles. VWP Results. Computation Times. Placing Wavelength Converters at the p-Cycle Access Points Only. Results with Jointly Optimized (VWP) p-Cycles. Heuristic and Algorithmic Approaches to p-Cycle Design. p-Cycle Efficiency Metrics. The “Perfect Score” for a p-Cycle. A Score-Based Design Assembly Algorithm. Preselection of Candidate p-Cycles: a Heuristic for MIP Solutions. Results with Preselection to Solve the Joint p-Cycle Design Problem. Zhang and Yang's Straddling Span Algorithm. Add and Join Operations on Primary p-Cycles. Application of Add/Join Operations to Design Improvement. General p-Cycle Merge Operation. Simulated Allocation Approach for Joint Design Algorithms. Concept of a Straddling Subnetwork and Domain Perimeter p-Cycles. Extra Straddling Relationships with Non-Simple p-Cycles. Hamiltonian p-Cycles and Homogeneous Networks. Concept of a Homogeneous Network. The Role of Hamiltonian p-Cycles in Ordinary Capacitated Designs. p-Cycle Design in Homogeneous Hamiltonian Networks. Lower Bounds for p-Cycles on a Hamiltonian Network. Semi-Homogeneous Networks Inspired by p-Cycles. An ADM-like Nodal Device for p-Cycles. Self-Organized p-Cycle Formation. Virtual p-Cycles in the MPLS Layer for Link and Node Protection. IP Link Restoration with MPLS p-Cycles. Network Design using MPLS p-Cycles for Link Restoration. Node-Encircling p-Cycles for Protection Against Node Loss. Types of Node-Encircling p-Cycles. Rerouting Mechanism with Node-Encircling p-Cycles. Generating Node Encircling p-Cycles. On the Prospect of Using Only Node-Encircling p-Cycles.

11. Ring-Mesh Hybrids and Ring-to-Mesh Evolution.

Integrated ADM Functions on DCS/OXC: an Enabler of Hybrids. Hybrids Based on the Ring-Access Mesh-Core Principle. Core and Access Network Partitioning. Access Ring Formation and Span Elimination. Mesh-Chain Hybrid Networks. Studies of Ring-Mesh and Mesh-Chain Hybrid Network Designs. Design of the Ring-Mesh Hybrids. Pure Mesh and Mesh-Chain Designs. Pure Ring Reference Designs. Results and Discussion. Optimal Design of Ring-Mesh Hybrids. Concept of a Single-Layer Ring-Mesh Hybrid Transport Network. Cost Modeling for Ring-Mesh Hybrids. Ring-Mesh Hybrid Design Model. Forcer Clipping Ring-Mesh Hybrids. The Forcer Clipping Hypothesis. Forcer Clipping Heuristics. Methodology for Tests of the Forcer Clipping Heuristics. Results and Discussion. Ring to Mesh Evolution via “Ring Mining”. Optimization Model for Pure Ring Mining. Ring Network Designs for Tests of Ring Mining. Test Results for Pure Ring Mining. Ring Mining with Minimum Cost Capacity Additions. Minimum Cost Evolutionary Strategy with Conversion Costs. Implementation of Ring Mining Strategies. Ring Mining to p-Cycles as the Target Architecture. Converting Rings into Modular p-Cycles: Nodal View. Network Level View of Evolution from Rings to p-Cycles.

Bibliography.

 

Index.