Research On Protection Algorithms In Survivable Mesh Networks

The emergence of wavelength-division multiplexing (WDM) technology has made it possible for a single fiber to carry huge data. In optical networks employing WDM technology, a single fiber failure will lead to huge data loss. Thus it is of paramount importance to study network survivability. There are two main survivable approaches: protection and restoration. In protection, backup resources are preassigned to connections. Upon the failure of network elements, the failed connections can be restored by using the pre-assigned backup resources. On the other hand, in restoration, no backup resources are pre-assigned. Upon the failure of network elements, the failed connections can be restored only if one can find sufficient free resources that can be used to carry the failed connections. Generally speaking, protection can provide faster recovery time than restoration. Due to this merit, we in this thesis study protection algorithms in survivable WDM mesh networks. Specifically, we place our focuses on the following aspects: segment protection, SRLG (Shared Risk Link Group) constraints, differentiated reliability (DiR) and multicast protection.Segment protection is new protection scheme that has high resource utilization ratio and rapid recovery time. Chapter 2 of this thesis addresses this scheme. The main contributions are as follows. 1) In segment protection, each working path is divided into several working segments (WS), each of them is protected by a backup segment (BS). Since two WSs may be overlapped with each other, it is possible that a link is protected by two BSs. This may lead to over-reservation of backup resources. To address this problem, this thesis proposes a novel algorithm and conducts extensive simulations to verify the performance of the algorithm. 2) Although the BSs derived by the segment protection scheme is short in many cases, it is possible that some BSs are still too long to achieve rapid restoration. Therefore, it is necessary to limit the length of BSs such that the hop length of each segment is within a given threshold. This thesis proposes a segment-based algorithm for the above problem.It has been well recognized that it is an NP-C problem to derive an SRLG-disjoint working/backup path pair for a given source-destination pair in survivable WDM mesh networks. To this regard, a general approach is to first derive the working path and then derive a backup path after removing from the network the links in the working path as well as the links that have the same SRLG with the working path. Using this approach, however, cannot derive a backup path when the working path is determined. This is the so-called "trap" problem. Traps may be caused by the network topology and by unreasonable backup resource reservation. Chapter 3 of this thesis addresses the problem of how to avoid traps. The main contributions are as follows. 1) Segment protection is an efficient approach to resolve the trap problem. However, it is still an open problem that, what on earth, how many segments is sufficient to avoid traps in real networks. To address this problem, this thesis conducts extensive simulations and finds that in most cases (over 99%) two segments are sufficient. According to this observation, this thesis further proposes a two-segment based algorithm. Results from extensive simulations demonstrat the good performance of the proposed algorithm. 2) As mentioned above, traps may be caused by unreasonable backup resource reservation. This thesis proposes a traffic-engineering-based algorithm for achieving reasonable backup resource reservation such that as more as possible traps can be reduced.A new trend in the design of optical networks is to route connections according to their reliability requirements. To achieve such a goal, an important problem is to design appropriate algorithms such that dynamic arrivals can be routed according to their reliability requirements. Chapter 4 addresses this problem. The main contributions of this chapter are as follows. 1) This thesis proposes two novel approximation algorithms for routing dynamic arrivals with reliability requirements in WDM mesh networks under the single failure assumption, when sharing of backup resource is not allowed. The basic idea of the first approximation algorithm is to generate an auxiliary graph and then compute a route in the auxiliary graph. By doing this, one cannot only find all the resources required to route a connection in a single step but also can avoid the deficit of existing algorithms that have to use multiple steps. On the other hand, the basic idea of the second approximation algorithm is to first compute a working path, generate an auxiliary graph according to the working path, and then derive a backup path for the working path such that the reliability requirement can be met. 2) This thesis proposes a novel heuristic algorithm under the single failure assumption when sharing of backup resources is allowed. 3) This thesis proposes a new algorithm under the independent failure assumption when sharing of backup resources is not allowed. Different from existing algorithms that only use one backup segment to protect the working path, the new proposed algorithm allows using multiple backup segments and is more resource efficient than existing ones.Due to the huge bandwidth offered by WDM networks, more and more bandwidth intensive multicast applications have emerged in recent years. In light-tree based multicast routing, any single fiber failure will disrupt multiple destinations such that they cannot correctly receive data. Therefore, it is of paramount importance to study the survivable routing problem, which has been a research topic in recent years. Chapter 5 addresses this problem. The main contributions of this chapter are as follows. 1) This thesis studies the problem of how to protect a given light-tree when sharing of backup resources is not allowed. A novel algorithm is proposed and compared with existing algorithms. 2) Due to the problem of survivable routing for multicast sessions is NP-C, most algorithms proposed in the literature are heuristic. This means that there are some redundant resources in the derived routing by these algorithms. For the first time in the literature, this thesis addresses this problem and proposes a novel algorithm for it. 3) As far as we know, existing algorithms for routing survivable multicast sessions do not allow backup resource sharing between different multicast sessions. This thesis proposes to allow sharing of backup resources and proposes a novel algorithm. Results from extensive simulations show the good performance of the proposed algorithm.