A new heuristic algorithm with shared segment-backup paths for trap avoidance in survivable optical networks

doi:10.1364/OE.14.010990

« Show journal navigation

A new heuristic algorithm with shared segment-backup paths for trap avoidance in survivable optical networks

Lei Guo, Lemin Li, Jin Cao, and Hongfang Yu »View Author Affiliations

Optics Express, Vol. 14, Issue 23, pp. 10990-10995 (2006)
http://dx.doi.org/10.1364/OE.14.010990

View Full Text Article

Acrobat PDF (105 KB)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Article Navigation

▸ Article Outline
– Abstract
1. Introduction
2. System model and heuristic algorithm
4. Conclusion
– References and links

Article Tools
Full Text
Article Info
References
Cited By
Figures
Metrics
Download PDF

Viewing Equations in the
HTML Article

Optimal Viewing Recommendations

Full Text
Article Info
References (8)
Cited By
Figures (5)
Metrics

Abstract

This paper proposes a new heuristic algorithm, called Quick Method with Shared Protection (QMSP), to protect the single-link failure in survivable WDM optical networks. QMSP first computes one primary path for each connection request. If the primary path is a trap path, QMSP will compute two segment-backup paths to avoid the trap problem based on the routing policy. Compared to previous algorithms, QMSP not only has better time complexity but also can obtain higher resource utilization ratio and lower blocking probability.

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

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave. Technol. 21, 870–883 (2003). [CrossRef]

The simple methods in [2–4

R. He, H. Wen, L. Li, and G. Wang, “Shared sub-path protection algorithm in traffic-grooming WDM mesh networks,” Photonic Netw. Commun. 8, 239–249 (2004). [CrossRef]

] 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

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee, “New and improved approaches for sharedpath protection in WDM mesh networks,” J. Lightwave. Technol. 22, 1223–1232 (2004). [CrossRef]

], 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

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks , 14, 325–326 (1984). [CrossRef]

, 7

H. Wen, S. Wang, and L. Li, “A routing algorithm for finding low-cost pair of no shared-risk paths,” J. Electron. Info. Technol. 25, 824–830 (2003).

], 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.

c_j : Basic cost of link j; it is determined by many factors, e.g., the physical length of the link, the installation cost of the link, etc;
c* _j : Dynamic cost of link j; it is determined by c_j and the current state of the network.
pw_j : Number of primary wavelengths on link j.
fw_j : Number of free wavelengths on link j.
rw_j : Number of reserved backup wavelengths on link j.
cr_n : Connection request n.
p_n : Primary path for cr_n .
b_n : Backup path for cr_n .
${sp}_{p}^{q}$ : The qth segment path of p.
${sb}_{p}^{q}$ : Segment-backup path for ${sp}_{p}^{q}$ .
( ${sb}_{p}^{q 1}$ , ${sb}_{p}^{q 2}$ ) : Takes value of 1, if the source nodes of p and ${sb}_{p}^{q 1}$ are same, the destination nodes of p and ${sb}_{p}^{q 2}$ are same, and ( ${sb}_{p}^{q 1}$ , ${sb}_{p}^{q 2}$ ) protect the common part of p; otherwise, 0.
|M|: Number of elements in set M.
$v_{j}^{e}$ : Set of connections whose primary paths traverse link e and backup/segment-backup paths traverse link j.

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

J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks , 14, 325–326 (1984). [CrossRef]

, 7

H. Wen, S. Wang, and L. Li, “A routing algorithm for finding low-cost pair of no shared-risk paths,” J. Electron. Info. Technol. 25, 824–830 (2003).

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.

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.

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 (

{sb}_{A - B - C - D - E}^{A - F - G - D}

{sb}_{A - B - C - D - E}^{C - H - I - 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

Input: network information; a new connection request cr_n .

Output: p_n and b_n ; or p_n and (

{sb}_{n}^{q 1}

{sb}_{n}^{q 2}

); or NULL if no paths are available.

Step1: Adjust the costs of all links according to (1). Run Dijsktra’s algorithm to compute a least-cost primary path p_n . If p_n has been found, go to step2; otherwise, block the connection and return NULL.

c_{j}^{*} = {\begin{matrix} + \infty, If (f w_{j} = 0) \\ \frac{c_{j} • (∣ W ∣ + 1 - f w_{j})}{W}, Other \end{matrix}

(1)

Step2: Adjust the costs of all links according to (2). Run Dijsktra’s algorithm to compute the least cost routes from the source node to all other nodes. If the route from the source node to destination node has been found, record the route as backup path b_n ; otherwise, let b_n ←NULL. Go to step3.

c_{j}^{*} = {\begin{matrix} + \infty, If j \in p_{n} or f w_{j} + r w_{j} < v_{j}^{*} \\ \frac{c_{j} • (v_{j}^{*} + 1 - r w_{j})}{∣ W ∣}, Other \end{matrix}

(2)

Step3: Record all potential segment-backup paths

{sb}_{n}^{q}

obtained in step2. These potential segment-backup paths compose set S ₁.

Step4: Run Dijsktra’s algorithm to compute the least cost routes from the destination node to all other nodes, and reversely record all potential segment-backup paths

{sb}_{n}^{q}

. These potential segment-backup paths compose set S2.

Step5: Compare the backup resources computation of b_n (if b_n ≠NULL) and all possible pairs of two segment-backup paths satisfying (

{sb}_{n}^{q 1}

{sb}_{n}^{q 2}

)=1(∀q1∈S1,∀q2∈S2). Select the solution with least resources consumed as the final result. If the result can be found, go to Step6; otherwise, return NULL.

Step6: Update the reserved backup resources on all links traversed by the backup path or segment-backup paths, i.e., rw_j ←v* _j , (∀j∈b_n or (

{sb}_{n}^{q 1}

{sb}_{n}^{q 2}

)), where v* _j =max{|

v_{j}^{e}

|;∀e∈L} that means the backup resources can be shared by different backup paths if the corresponding primary paths are link-disjoint. Return the final result.

In the process, according to [2

R. He, H. Wen, L. Li, and G. Wang, “Shared sub-path protection algorithm in traffic-grooming WDM mesh networks,” Photonic Netw. Commun. 8, 239–249 (2004). [CrossRef]

] we know that (1) can improve the load balance, and (2) can improve the resource utilization ratio.

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.

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.

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)

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.

References and Links

1.	S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave. Technol. 21, 870–883 (2003). [CrossRef]
2.	R. He, H. Wen, L. Li, and G. Wang, “Shared sub-path protection algorithm in traffic-grooming WDM mesh networks,” Photonic Netw. Commun. 8, 239–249 (2004). [CrossRef]
3.	H. Wen, L. Li, R. He, H. Yu, S. Wang, and N. Song, “Dynamic grooming algorithms for survivable WDM mesh networks,” Photonic Netw. Commun. 7, 253–263 (2003). [CrossRef]
4.	Y. Wang, Q. Zeng, and H. Zhao, “Dynamic survivability in WDM mesh networks under dynamic traffic,” Photonic Netw. Commun. 6, 5–24 (2003). [CrossRef]
5.	C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee, “New and improved approaches for sharedpath protection in WDM mesh networks,” J. Lightwave. Technol. 22, 1223–1232 (2004). [CrossRef]
6.	J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks , 14, 325–326 (1984). [CrossRef]
7.	H. Wen, S. Wang, and L. Li, “A routing algorithm for finding low-cost pair of no shared-risk paths,” J. Electron. Info. Technol. 25, 824–830 (2003).
8.	M. Barbehenn, “A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices,” IEEE Trans. Comp. 47, 263 (1998). [CrossRef]

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4510) Fiber optics and optical communications : Optical communications

ToC Category:
Fiber Optics and Optical Communications

History
Original Manuscript: September 26, 2006
Revised Manuscript: October 20, 2006
Manuscript Accepted: October 25, 2006
Published: November 13, 2006

Citation
Lei Guo, Lemin Li, Jin Cao, and Hongfang Yu, "A new heuristic algorithm with shared segment-backup paths for trap avoidance in survivable optical networks," Opt. Express 14, 10990-10995 (2006)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-14-23-10990

Sort: Author | Year | Journal | Reset

References

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003). [CrossRef]
R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004). [CrossRef]
H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003). [CrossRef]
Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003). [CrossRef]
C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004). [CrossRef]
J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks, 14, 325-326 (1984). [CrossRef]
H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).
M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998). [CrossRef]

Barbehenn, M.
He, R.
Li, L.
Mukherjee, B.
Ou, C.
Ramamurthy, S.
Sahasrabuddhe, L.
Song, N.
Suurballe, J.
Tarjan, R.
Wang, G.
Wang, S.
Wang, Y.
Wen, H.
Yu, H.
Zang, H.
Zeng, Q.
Zhang, J.
Zhao, H.

IEEE Trans. Comp.

M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998). [CrossRef]

J. Electron. Info. Technol.

H. Wen, S. Wang, L. Li, "A routing algorithm for finding low-cost pair of no shared-risk paths," J. Electron. Info. Technol. 25, 824-830 (2003).

J. Lightwave. Technol.

C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004). [CrossRef]
S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003). [CrossRef]

Networks

J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks, 14, 325-326 (1984). [CrossRef]

Photonic Netw. Commun.

R. He, H. Wen, L. Li, G. Wang, "Shared sub-path protection algorithm in traffic-grooming WDM mesh networks," Photonic Netw. Commun. 8, 239-249 (2004). [CrossRef]
H. Wen, L. Li, R. He, H. Yu, S. Wang, N. Song, "Dynamic grooming algorithms for survivable WDM mesh networks," Photonic Netw. Commun. 7, 253-263 (2003). [CrossRef]
Y. Wang, Q. Zeng, H. Zhao, "Dynamic survivability in WDM mesh networks under dynamic traffic," Photonic Netw. Commun. 6, 5-24 (2003). [CrossRef]

2004, He, Photonic Netw. Commun.
2004, Ou, J. Lightwave. Technol.
2003, Wen, Photonic Netw. Commun.
2003, Wang, Photonic Netw. Commun.
2003, Wen, J. Electron. Info. Technol.
2003, Ramamurthy, J. Lightwave. Technol.
1998, Barbehenn, IEEE Trans. Comp.
1984, Suurballe, Networks

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Click here to see a list of articles that cite this paper