Research On Protection Algorithms In Survivable WDM Mesh Networks

With the rapid development of Internet, the tremendous required demand in bandwidth issue a real challenge to our communication networks. The Wavelength Division Multiplexing (WDM) technology has made it possible to carry huge data in a single fiber and it will become the core of the next generation backbone networks. Since a single wavelength channel has the transmission rate of over several gigabits per second, the failure of a network component (e.g., fiber link, cross-connect, etc) can cause the failures of several light-paths and leads to large data loss. Therefore, the survivable design is becoming more and more important in reliable WDM mesh optical networks. The strategy of survivability can be classified into two types: protection and restoration. Protection means the backup resources will be reserved during the setup of the working path to against the future unknown failure and while in restoration, no backup resource will be pre-reserved, when the failure occurs, the failed connection will dynamically search the available resources to implement the recovery. Generally, protection can provide faster recovery than restoration and many researchers are focus on the protection metrics, so in this dissertation the authors mainly investigate the protection design in survivable WDM mesh optical networks, including: segment protection design, differentiated reliability protection design, SRLG (Shared Risk Link Group) constrained protection design and traffic recovery time constrained protection design.By the routing metrics, protection schemes can be classified into path protection, link protection and segment protection. The main idea of segment protection is to divide the working path into several segments (named working segments) and provide backup segments for each of them. Compared with path protection, segment protection can achieve shorter traffic recovery time for a modest sacrifice in wavelength resource utilization ratio. Many researchers have investigated the algorithms of how to partition the working path and provide the backup segments. The most conventional way is to partition the working path into segments first and then compute the backup segments, this method is inflexible because once the working path is determined, the partition of the working path is determined too. This inflexible way to partition the working path can not guarantee to find the proper backup segments successfully. So in Chapter 2, the authors provide an algorithm named RSSP (Recursive Shared Segment Protection) to figure out a more flexible way to partition the working path. The hop length of each backup segment is constrained in RSSP to shorten the traffic recovery time. Considering that the traffic recovery time is not only correlated with the length of backup segment, but also the length of working segment. Only constrain the hop length of the backup segment can not 100% shorten the traffic recovery time so that the authors provide another algorithm named HCSPP (Hop Constrained Sub-Path Protection) to fix the problem, HCSPP constrain the hop lengths of both working and backup segments to further shorten the traffic recovery time.By different requirements of reliability, the service provider can assign reasonable resources to serve different users to optimize the network resource utilization. In chapter 3, the authors study the dedicated protection algorithms with Differentiated Reliability (DiR), the main contributions include: 1) analyze the DiR computing problem and the traffic recovery process in the dedicated path and segment protection model. 2) Propose a dynamic heuristic protection algorithm named SDPA-DiR (Segment Dedicated Protection Algorithm-Differentiated Reliability) which only protects a part of working path but not the entire working path, compared with the end-to-end path protection metrics, SDPA-DiR can save lots of wavelength resources and further shorten the traffic recovery time. 3) According to SDPA-DiR, the authors make some improvement and provide another algorithm named IMP-DiR (Improved SDPA-DiR), the simulation results show that IMP-DiR can futher shorten the backup path and improve the network resource utilization ratio.The Shared-Risk-Link-Group (SRLG) is a group of network links that share a common physical resource (fiber, cable and conduit, etc) whose failure will cause the failures of all the links in the group. It has been proved that deriving an SRLG-disjoint path pair for a given source-destination node pairs is NP-C problem. So the most conventional way is to compute the working path first and then compute the backup path after removing all the links on the working path and all the links which have some common SRLG with the working path, sometimes this method can not find the SRLG-disjoint path pairs in the network even when they exist, this is the so-called "trap" problem. In chapter 4, the authors research the protection problem under SRLG constraint and propose an algorithm named Pd-SPP (Partial SRLG-disjoint Shared Path Protection) to solve the problem; Pd-SPP adopts two methods to avoid "trap": 1) Use K shortest paths algorithm to compute several candidate working paths and then try to compute the complete SRLG-disjoint backup paths. 2) Introduce the concept of partial SRLG-disjoint which means the working path and the corresponding backup path could have some common SRLG if their simultaneous failure probability is low enough. This is useful in the condition where no complete SRLG-disjoint path pairs exist. The authors also consider the simultaneous failure probability in the backup sharing to further improve the network resource utilization ratio and lower the blocking probability.In survivable WDM mesh optical networks, the main target of protection design is to achieve fast traffic recovery after the failure, so the traffic recovery time is a key parameter to measure a protection algorithm. Compare with the traditional end-to-end path protection metrics, the segment protection can achieve faster recovery and many researchers constrain the hop length of backup path to shorten the traffic recovery time, but all the methods above are the "best effort" approaches, they can not strictly and accurately guarantee the traffic recovery time. So in chapter 5, the authors investigate the problem and the main contributions include: 1) analyze the traffic recovery process in the shared segment protection model and deduce the computing of traffic recovery time. Then the authors set the delay for each link properly and use a "delay constraint shortest path algorithm" to compute the candidate backup segments, each candidate backup segment and the corresponding candidate working segment can 100% guarantee the traffic recovery time. 2) When computing the candidate backup segments, the authors consider the backup sharing and the SRLG-disjoint constraint. 3) According the candidate backup segments, an auxiliary graph is constructed to choose the backup segments set with the minimal cost. The authors propose an algorithm named TC-SSPP (Traffic recovery time Constrained Shared Sub-Path Protection) to solve the problem above and the simulation results show that the algorithm has very good performance.