|
|
|
|
|
|
|
The explosive growth of Web-related services over the Internet is bringing millions of new users online, thus fueling an enormous demand for bandwidth. Wavelength Division Multiplexed (WDM) networks, employing wavelength routing have emerged as the dominant technology to satisfy this growing demand for bandwidth. As the amount of traffic carried has increased, any single failure can be catastrophic. Survivability becomes indispensable in such networks. Therefore, it is imperative to design networks that can quickly and efficiently recover from failures. Most research to date in survivable optical network design and operation focuses on single link failures, however, the occurrence of multiple-link failures are not uncommon in a network topology. Multi-link failure scenarios can arise out of two common situations. First, an arbitrary link may fail in the network, and before that link can be repaired, another link fails, thus creating a multi-link failure sequence. Secondly, i! t might happen in practice that two distinct physical links may be routed via the same common duct or physical channel. A failure at that shared physical location creates a logical multiple-link failure. Such instances where separate fiber optic links share a common failure structure is often referred to as SRLG (Shared-Risk Link Groups).
In this dissertation, we study survivability paradigms for surviving multiple link failures. We study the network design and upgrade problem in WDM backbone networks and formulate it using a simulated annealing based technique. This framework provides a cost effective way of upgrading the network by identifying how much resources to budget at each stage of network evolution. This results in significant cost reductions for the network service provider.
We study protection reconfiguration using two different survivability paradigms, namely sub-graph routing and shared mesh protection. Initially sub-graphs are defined taking into account link, SRLG, or node failures, and could, in the event of an unrelated or subsequent multi-link failure, incorporate the reactive form of sub-graph fault tolerance. Reactive sub-graph fault tolerance employs a recursive approach for tolerating numerous sequential overlapping failures. It can tolerate simultaneous multiple link failures by simply serializing the handling of each individual fault.
Connection re-routing and network reconfiguration is one of the primary challenges in sub-graph routing methodology. We propose a constrained subgraph routing methodology, which restricts the connections to be routed using the same trunk and channel in the subgraphs, thus minimizing reconfiguration. The subgraph based routing methodology is further explored to tolerate multiple link failures, in the form of shared-risk link groups and node failures.
The generalized diverse routing problem, for finding two diverse routes between a source and destination have been shown to be NP-Complete. Recent studies have also proven the NP-completeness of the SRLG diverse routing. We propose a polynomial time graph transformation algorithm for solving the diverse routing problem for certain specific SRLG's, which includes link-sets incident on a common node. The proposed graph transformation methodology for diverse routing, is also studied for shared-risk node group (SRNG) failures.
|
|
|
|
|
|
|
|