OSA's Digital Library

Optics Express

Optics Express

  • Editor: Michael Duncan
  • Vol. 14, Iss. 23 — Nov. 13, 2006
  • pp: 10990–10995
« 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)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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.

© 2006 Optical Society of America

1. Introduction

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.

  1. cj : 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;
  2. c* j : Dynamic cost of link j; it is determined by cj and the current state of the network.
  3. pwj : Number of primary wavelengths on link j.
  4. fwj : Number of free wavelengths on link j.
  5. rwj : Number of reserved backup wavelengths on link j.
  6. crn : Connection request n.
  7. pn : Primary path for crn .
  8. bn : Backup path for crn .
  9. sppq : The qth segment path of p.
  10. sbpq : Segment-backup path for sppq .
  11. (sbpq1 , sbpq2 ) : Takes value of 1, if the source nodes of p and sbpq1 are same, the destination nodes of p and sbpq2 are same, and (sbpq1 , sbpq2 ) protect the common part of p; otherwise, 0.
  12. |M|: Number of elements in set M.
  13. vje : 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

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

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.

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

4: Choose two segment-backup paths A-F-G-D and C-H-I-E that can satisfy (sbABCDEAFGD ,sbABCDECHIE )=1 as the result from step5.

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

table-icon
View This 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.

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

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

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

  1. S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave. Technol. 21, 870-883 (2003). [CrossRef]
  2. 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]
  3. 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]
  4. Y. Wang, Q. Zeng, 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, B. Mukherjee, "New and improved approaches for shared-path protection in WDM mesh networks," J. Lightwave. Technol. 22, 1223-1232 (2004). [CrossRef]
  6. J. Suurballe, R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks,  14, 325-326 (1984). [CrossRef]
  7. 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).
  8. M. Barbehenn, "A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices," IEEE Trans. Comp. 47, 263 (1998). [CrossRef]

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.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited