Mesh-based survivability offers many advantages, but the research,
educational and perational communications communities need to absorb new
concepts and ideas about network operation; letting the network self-organize
its own logical configuration for example. Operators also need to understand,
evaluate and adopt new methods and models for network design and planning. This
book is designed to contribute to enabling this evolution towards mesh-based
Table of Contents:
About the Book's Web Site www.ee.ualberta.ca/~grover/
Introduction and Outline.
1. Orientation to Transport Networks and
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
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
6. Path Restoration and Shared Backup Path
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.
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
11. Ring-Mesh Hybrids and Ring-to-Mesh
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