1. Introduction

In Wavelength-Division-Multiplexing (WDM) optical networks, a wavelength channel has the transmission rate of over several gigabits per second, so that the failures may lead to a lot of traffic blocked. Therefore, the survivability is a key issue in WDM optical networks. Since the single-link failure is dominant in WDM optical networks, previous papers mostly focus on the protection for single-link failure [1–5].

The simple methods in [2–4] are so-called Two-Step Algorithm (TSA) which first computes a primary path and follows to compute a link-disjoint backup path for each connection request. Although TSA has low time complexity, the limitation of TSA is that it cannot find a solution in trap situation even though a solution exists [5], so that more connection requests may be blocked in trap situation and the consequence is that the blocking probability may be high.

To overcome the trap problem, some papers proposed the algorithm called Trap Avoidance based on Suurballe’s Algorithm (TASA) [6, 7], which has low time complexity and also can find two link-disjoint paths from the source node to destination node for each connection request (i.e., one primary path and one link-disjoint backup path). However, the limitation of TASA is that it cannot provide the good ability of sharing backup resources, so that the resource utilization ratio of TASA may be low.

To overcome the trap problem meanwhile to obtain better performance than TASA, in this paper we propose a new heuristic algorithm called Quick Method with Shared Protection (QASP) to tolerate the single-link failure in WDM optical networks. From the theoretic analysis and simulation results in the below sections, we can see that QASP not only can avoid the trap problem but also has better performances than TASA.

The rest of this paper is organized as follows. Section 2 elaborates on network model and the heuristic algorithm. Section 3 presents the simulation results and analysis. Section 4 is for conclusions.

2. System model and heuristic algorithm

2.1 Network model

The network topology can be denoted as G(N,L,W)for a given WDM mesh network, where N is the set of nodes, L is the set of fiber links, and W is the set of available wavelengths per fiber link. Assume each connection requires the bandwidth of a wavelength channel. The shortest path algorithm, i.e., Dijkstra’s algorithm, is applied to compute the routes. Some important notations are introduced as follows.

2.2 Trap avoidance in TASA and QMSP

1) TASA method: The idea of TASA is to use Suurballe’s algorithm to compute one primary path and one link-disjoint backup path from the source node to destination node for each connection request. The process of TASA can be briefly presented as follows [6, 7]:

Step1: Compute a shortest primary path through Dijkstra’s algorithm.

Step2: Remove the links traversed by the primary path. If the source node and destination node in the residual network is disconnected, go to step3; otherwise, compute a shortest backup path through Dijkstra’s algorithm.

Step3: Take the reversed direction for the links traversed by primary path obtained in step1 and compute a shortest testing path through Dijkstra’s algorithm. Remove the links traversed by both primary path and testing path, re-compute a new shortest primary path through Dijkstra’s algorithm, and go back to step2. (After this step, the link-disjoint backup path can be found in step2.)

Based on the process of TASA, we present an illustration in Fig. 1. We assume that there is a connection request from source node A to destination node E. In Fig. 1(a), we can find the shortest primary path A-B-C-D-E from step1. However, the primary path is also a trap path from step2. Therefore, in Fig. 2(b) we take the reversed direction for the links traversed by the primary path, compute a shortest testing path A-F-G-D-C-H-I-E, remove the links C-D (or D-C) traversed by both the primary path and testing path, and re-compute a new primary path A-F-G-D-E from step3. In Fig. 2(c), we can thus obtain the shortest backup path A-B-C-H-I-E from step2. Therefore, the trap problem can be effectively avoided.

 

Fig. 1. Illustration of TASA based on Suurballe’s algorithm: (a) a primary path A-B-C-D-E; (b) a testing path A-F-G-D-C-H-I-E; (c) a primary path A-F-G-D-E and a link-disjoint backup path A-B-C-H-I-E.

Download Full Size | PDF

 

Fig. 2. Illustration of QMSP based on Dijkstra’s algorithm: (a) a primary path A-B-C-D-E; (b) two segment-backup paths A-F-G-D and C-H-I-E.

Download Full Size | PDF

2) QMSP method: The idea of QMSP is to assign one primary path and two link-disjoint segment-backup paths based on Dijskatra’s algorithm for each connection request, if the link-disjoint backup path cannot be found. The detailed process of QMSP is shown in Table 1.

Based on the process of QMSP, we present an illustration in Fig. 2. We assume that there is a connection request from source node A to destination node E. In a simple method TSA, the primary path is A-B-C-D-E that is a trap path since the link-disjoint backup path cannot be found. Therefore, this connection request will be blocked. However, QMSP can find the feasible solution as follows:

1: Find the primary path A-B-C-D-E in Fig. 2(a) from step1.

2: Use Dijkstra’s algorithm to compute the link-disjoint routes with primary path from source node A to all other nodes from step2, and record the potential segment-backup paths (i.e., A-F-B and A-F-G-D) in Fig. 2(a) from step3.

3: Use Dijkstra’s algorithm to compute the link-disjoint routes with primary path from destination node E to all other nodes, and reversely record the potential segment-backup path (i.e., C-H-I-E) in Fig. 2(a) from step4.

4: Choose two segment-backup paths A-F-G-D and C-H-I-E that can satisfy (${\mathit{\text{sb}}}_{A\mathit{-}B\mathit{-}C\mathit{-}D\mathit{-}E}^{A\mathit{-}F\mathit{-}G\mathit{-}D}$ ,${\mathit{\text{sb}}}_{A\mathit{-}B\mathit{-}C\mathit{-}D\mathit{-}E}^{C\mathit{-}H\mathit{-}I\mathit{-}E}$ )=1 as the result from step5.

In Fig. 2(b), we can see that the two segment-backup paths A-F-G-D and C-H-I-E can protect any single-link failure. Therefore, the trap problem can be avoided and this connection request can be successfully established.

From the above analysis, it is obvious that TASA and QMSP both can avoid the trap problem. However, compared to TASA, QMSP has two advantages, i.e., better resource utilization ratio and lower time complexity, presented in the following subsections.

Table 1. Process of QMSP

View Table

2.3 Backup Resources in TASA and QMSP

The first advantage of QMSP is that it may save more backup resources than TASA. In Fig. 3, we assume there is a connection request from source node A to destination node E.

In TASA, the primary path is A-F-G-D-E and the link-disjoint backup path is A-B-C-I-J-E in Fig. 3(a). We can see that there are five new wavelengths needed (four new primary wavelengths and one new backup wavelength) since four backup wavelengths already reserved on links B-C, C-I, I-J and J-E can be shared.

In Fig. 3(b), QMSP can find two feasible solutions; that is, the segment-backup paths of first solution are A-F-G-D and B-I-J-E, and the segment-backup paths of second solution are A-F-G-D and C-I-J-E. From the first solution in Fig. 3(c), one primary path A-B-C-D-E and two segment-backup paths A-F-G-D and B-I-J-E consume five new wavelengths (four new primary wavelengths and one new backup wavelength) since four backup wavelengths already reserved on links A-F, F-G, G-D, I-J and J-E can be shared. From the second solution in Fig. 3(d), one primary path A-B-C-D-E and two segment-backup paths A-F-G-D and C-I-J-E only consumes four new wavelengths (four new primary wavelengths and zero new backup wavelength) since six backup wavelengths already reserved on links A-F, F-G, G-D, C-I, I-J and J-E can all be shared. Therefore, we can choose the second solution as the result since it can save more resources and obtain better resource utilization ratio than TASA. The reason for this is that there is only one solution can be found in TASA while there may be many solutions can be found in QMSP, so that we can choose the best one in QMSP as the result that may have higher probability to near the optimal than TASA.

 

Fig. 3. Backup resources for TASA and QMSP: (a) backup resources in TSAS ; (b) multiple segment-backup paths; (c) a solution for QMSP; (d) another solution for QMSP.

Download Full Size | PDF

2.4 Time complexity in TASA and QMSP

With TASA, in the worst case TSAS will run one time of Dijsktra’s algorithm with time complexity O[(|N|+|L|)log(|N|)] to compute the initial primary path in step1, run one time of Dijkstra’s algorithm to compute the testing path in setp3, run one time of Dijkstra’s algorithm to compute the new primary path in step3, and run one time of Dijkstra’s algorithm to compute the backup path in setp2. Therefore, the time complexity of TASA is approximately O[4(|N|+|L|)log(|N|)]. With QMSP, in the worst case QMSP will run one time of Dijsktra’s algorithm to compute the primary path in step1, run one time of Dijkstra’s algorithm to compute all potential paths from the source node to all other nodes in setp2, and run one time of Dijkstra’s algorithm to compute all potential paths from the destination node to all other nodes in step4. Thus, the time complexity of TASA is approximately O[3(|N|+|L|)log(|N|)]. It is obvious that QMSP has lower time complexity than TASA.

3. Simulation results and analysis

We simulate a dynamic network environment with the assumptions that connection requests arrival according to an independent Poisson process with arrival rate β, and the connections holding time is negative exponentially distributed 1/µ, then, the network load is β/µ Erlang. In simulation, we let µ=1 and each request bandwidth is a wavelength. We assume there are no waiting queues in the network, so if a connection request was blocked, it would be abandoned immediately. The test network is shown in Fig. 4, where each node-pair is interconnected by a bi-directional fiber link that has 20 wavelengths and each node has the wavelength conversion capacity. The basic link-cost is equal to the link length assumed to 100. We compare the performances for TSA, TASA and QMSP in resource utilization and blocking probability.

 

Fig. 4. Test network topology: National network.

Download Full Size | PDF

Figure 5(a) shows the performance of Resources Consumed Ratio (RCR) that is the ratio of total backup resources over total primary resources. Bigger RCR means more backup resources consumed and lower resource utilization ratio. We can see that, compared to TSA and TASA, QMSP has the best resources utilization ratio since the RCR of QMSP is the smallest. The reason for this is that TSA or TASA only can use one primary path and one backup path while QMSP not only can use one primary path and one backup path but also can use some better solution with two segment-backup paths with less backup resources consumed (see subsection 2.3). Therefore, QMSP can save more resources and obtain better resources utilization ratio than TSA and TASA.

 

Fig. 5. (a) Resource Consumed Ratio (RCR); (b) Blocking Probability (BR)

Download Full Size | PDF

In Fig. 5(b), it is obvious that QMSP has the lowest blocking probability. The reason for QMSP outperforming TASA is that QMSP has better resources utilization ratio than TASA, so that more free resources can be used by the new connection requests and the consequence is that the blocking probability is lower. The reasons for QMSP outperforming TSA are: 1) QMSP can effectively avoid the trap problem by using two segment-backup paths (see subsection 2.2) so that more connections can be established and the consequence is that the blocking probability can be reduced; 2) QMSP has better resources utilization ratio than TSA so that the blocking probability is lower.

In Fig. 5, we can obtain the improvements of resource utilization ratio for QMSP over TASA and TSA both are about 7%, and the improvements of blocking probability for QMSP over TASA and TSA are about 9% and 16% respectively, which are significant and promising.

4. Conclusion

This paper has proposed a new heuristic algorithm called QMSP to protect the single-link failure in survivable WDM optical networks. Compared to previous algorithms, QMSP not only has lower time complexity but also can obtain better resources utilization ratio and lower blocking probability.