Maximizing Reliability in WDM Networks through Lightpath Routing

Hyang-Won Lee, Kayi Lee, Eytan H. Modiano

Abstract

We study the reliability maximization problem in WDM networks with random link failures. Reliability in these networks is defined as the probability that the logical network is connected, and it is determined by the underlying lightpath routing, network topologies and the link failure probability. By introducing the notion of lexicographical ordering for lightpath routings, we characterize precise optimization criteria for maximum reliability in the low failure probability regime. Based on the optimization criteria, we develop lightpath routing algorithms that maximize the reliability, and logical topology augmentation algorithms for further improving reliability. We also study the reliability maximization problem in the high failure probability regime.

Introduction

Modern communication infrastructures are typically structured in layers: an electronic logical layer (such as IP or SONET) is mapped onto a physical optical fiber layer using Wavelength Division Multiplexing (WDM). In this architecture, a single physical fiber link often carries multiple logical links (lightpaths). Consequently, the failure of a single physical fiber—due to aging, accidents, or natural disasters—can lead to "correlated failures," where multiple logical links are severed simultaneously, potentially disconnecting the logical network.

Traditional research in this field has focused on survivability, which ensures a network can withstand any single physical link failure. However, real-world scenarios often involve multiple simultaneous failures. This paper shifts the focus toward cross-layer reliability: the probability that the logical network remains connected given that every physical link has a random, independent probability of failure. Since finding the absolute optimal routing to maximize this probability is NP-hard, we propose scalable algorithms and a novel optimization framework to address the challenge.

Methodology

Lexicographical Ordering of Cut Vectors

A central innovation of this work is the use of lexicographical ordering to evaluate lightpath routings. Rather than simply maximizing the "Minimum Cross-Layer Cut" (MCLC)—the smallest number of physical failures required to disconnect the logical network—we analyze the entire "cut vector." This vector, denoted as $V = (N_1, N_2, ..., N_m)$, counts how many ways the network can be disconnected by exactly 1 failure, 2 failures, and so on.

We prove that in the low failure probability regime (where the probability $p$ of a link failing is small), maximizing reliability is equivalent to minimizing the cut vector lexicographically. This means first minimizing $N_1$, then $N_2$, and continuing through the vector. This approach ensures that the most likely failure scenarios are mitigated first.

Iterative optimization of the logical topology to minimize cut vectors.

The Iterative REROUTE Algorithm

To optimize the cut vector without the computational explosion of joint optimization, we developed an iterative approach. The algorithm selects one logical link at a time and seeks a more reliable physical path using an Integer Linear Program (ILP). To ensure scalability for large-scale carrier networks, we also introduced a $k$-shortest path approximation that balances computational speed with solution quality.

Logical Topology Augmentation

Beyond rerouting existing links, we explored how adding a limited number of strategic logical links (lightpaths) can improve reliability. Our augmentation algorithm identifies the most impactful placements for these new links to further harden the network against disconnection.

Evaluation and Results

Datasets

The algorithms were evaluated using three distinct network types:

  1. Extended NSFNET: A 14-node backbone topology with added links to test high connectivity.
  2. Random Logical Topologies: 350 generated graphs with varying node counts (6 to 12) and link densities.
  3. Qwest Case Study: A real-world inspired topology based on Qwest Communications' network maps, featuring 39 physical nodes and 20 logical nodes with 101 links.

Key Results

  • Optimization Performance: The proposed RR_MCF algorithm achieved the maximum possible MCLC value in 98% of test cases, significantly outperforming the previous state-of-the-art MCF algorithm, which only reached it 50% of the time.
  • Unreliability Reduction: In the Qwest case study, our iterative rerouting method reduced the probability of network disconnection by three orders of magnitude compared to standard baselines.
  • Robustness: Iteratively improving one link at a time proved highly effective. Even when starting from a sub-optimal initial routing, the algorithm consistently reached a high-quality local optimum.

Discussion: The Impact of Failure Regimes

An important finding of this research is that the optimal routing strategy shifts depending on the failure probability ($p$).

  • Low-Failure Regime: Under standard operating conditions, the priority is path disjointness. The algorithm chooses longer physical paths to ensure that logical links do not share physical fibers, thereby minimizing correlated failures.
  • High-Failure Regime: In disaster scenarios where $p$ is high, the priority shifts toward path length. Shorter paths are preferred because they minimize the "exposure" of each lightpath to potential failure points.
Optimal routing strategies in low vs. high failure probability regimes.

Conclusion and Future Work

This paper provides a rigorous framework for maximizing WDM network reliability through lexicographical optimization and iterative rerouting. While highly effective, challenges remain in computing cut vectors for extremely large, highly connected graphs. Future research will explore dynamic traffic demands, the role of reconfigurable optical add-drop multiplexers (ROADMs) in providing "reliability-on-the-fly," and the impact of geographically correlated failures, such as those caused by localized natural disasters.

Summary updated

Abstract

We study the reliability maximization problem in WDM networks with random link failures. Reliability in these networks is defined as the probability that the logical network is connected, and it is determined by the underlying lightpath routing, network topologies and the link failure probability. By introducing the notion of lexicographical ordering for lightpath routings, we characterize precise optimization criteria for maximum reliability in the low failure probability regime. Based on the optimization criteria, we develop lightpath routing algorithms that maximize the reliability, and logical topology augmentation algorithms for further improving reliability. We also study the reliability maximization problem in the high failure probability regime.
BibTeX
@article{lee2014maximizing,
  author = {Hyang-Won Lee and Kayi Lee and Eytan H. Modiano},
  title = {{Maximizing Reliability in WDM Networks through Lightpath Routing}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2014},
  url = {https://openreview.net/forum?id=Z6n4VNX36q},
}
Figure