OSA's Digital Library

Optics Express

Optics Express

  • Editor: Michael Duncan
  • Vol. 13, Iss. 8 — Apr. 18, 2005
  • pp: 3087–3095
« Show journal navigation

Dynamic segment shared protection algorithm for reliable wavelength-division-multiplexing mesh networks

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


Optics Express, Vol. 13, Issue 8, pp. 3087-3095 (2005)
http://dx.doi.org/10.1364/OPEX.13.003087


View Full Text Article

Acrobat PDF (142 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

With the maturation of the technology of Wavelength-Division-Multiplexing (WDM) in optical networks, the survivable design has become a key issue. In this paper, we propose a Segment Shared Protection Algorithm (SSPA), which is based on the reliability of the networks and the different levels of the fault tolerance requested by the users, to protect the single-link failure in WDM optical networks. The main idea of the SSPA is to provide a backup path for a segment, which is divided in accordance with the policy of the Differentiated Reliability (DiR), on the primary path of each connection request. Under the guarantee of the blocking probability and the connection’s reliability, the SSPA has higher resource utilization ratio and faster recovery time than the previous algorithm PSPA-DiR. We evaluate the effectiveness of the SSPA and the results are found to be promising.

© 2005 Optical Society of America

1. Introduction

Recently, some papers [3

3. C. Saradhi, M. Gurusamy, and L. Zhou, “Differentiated QoS for survivable WDM optical networks,” IEEE Commun. Mag. 42, 8–14 (2004). [CrossRef]

7

7. P. H. Ho, J. Tapolcai, and T. Cinkler, “Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels,” IEEE/ACM Tran.Networking. 12, 1105–1118 (2004). [CrossRef]

] studied the Differentiated Reliability (DiR) and presented the new algorithm that is called Path Shared Protection Algorithm with DiR (PSPA-DiR) for WDM optical networks. PSPA-DiR first computes a primary path for each connection request, and second computes the reliability of the primary path. If the reliability of the primary path satisfies users’ requirement, then we do not need to compute the backup path; otherwise, backup path should be computed. From the simulation results in [3

3. C. Saradhi, M. Gurusamy, and L. Zhou, “Differentiated QoS for survivable WDM optical networks,” IEEE Commun. Mag. 42, 8–14 (2004). [CrossRef]

5

5. L. Guo, H. Yu, and L. Li, “Joint routing-selection algorithm for a shared path with differentiated reliability in survivable wavelength-division-multiplexing mesh networks,” Opt. Express. 12, 2327–2337 (2004), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-11-2327 [CrossRef] [PubMed]

], we can find out that the PSPA-DiR has higher resource utilization ratio and lower blocking ratio than the PSPA. We also can see that, in PSPA-DiR, if the reliability of the primary path is less than users’ requirement, then a backup path will be assigned to protect the full primary path not the partial primary path (namely, the segment path). If we consider protecting the segment path, which can be divided according to the policy of the DiR, then the backup resources would be reduced and the resource utilization ratio would be further improved. Another advantage of the segment protection is that the length of the segment and the corresponding backup path is shorter than the length of the full primary path and the corresponding backup path, then when the failures occur, the recovery time of the segment protection will be shorter than the path protection [10

10. Pin-Han Ho and Hussein T. Mouftah, “A Novel Survivable Routing Algorithm for Shared Segment Protection in Mesh WDM Networks With Partial Wavelength Conversion,” IEEE JSAC. 22, 1548–1560 (2004).

].

2. Syetem model and problem analysis

2.1 Analysis of reliablility

Fig. 1. An illustration of path protection and segment protection

Rc=Rp+(1Rp)Rb
(1)

For the SSPA, we divide the primary path into two un-overlapped segments (how to divide the primary path will be discussed in Section 3): the first segment which will not be protected is denoted as Pus and its reliability is denoted as Rus ; the second segment which will be protected is denoted as Pps and its reliability is denoted as Rps . For the SSPA, we only compute a backup path for the second segment Pps . In Fig. 1, the Pp is 1-2-3-4-5, the Pus is 1-2-3, the Pps is 3-4-5, and the backup path that is denoted as Pbs for the Pps is 3-9-5. Then, the reliability of the connection is calculated as Eq. (2), where Rc =(reliability of the first segment)×(joint reliability of the second segment and its backup path).

Rc=Rus(Rps+(1Rps)Rbs)
(2)

2.2 Cost function

An advantage of shared protection lies in a larger degree of wavelength resource sharing. In this section, we will define the cost function for computing the primary and backup paths in SSPA to implement the wavelengths sharing.

(1) Free capacity, denoted as fi , which are the free capacities that can be used by the following primary or backup paths.

(2) Reserved capacity, denoted as RCi , which are the reserved capacities by some backup paths.

(3) Working capacity, denoted as Wi , which are the working capacities taken by some primary paths and can not be used for any other purpose until the corresponding primary path is released.

The cost function cw for finding a primary path (PP ) with requested bandwidth (RB) is calculated as

cwi={+fi<RBcik·log(RLI)fiRB
(3)

Fig. 2. Illustration of capacity along link i(∈E)

The cost function cb for finding a backup path (Pbs ) for protected segment (Pps ) with requested bandwidth (RB) is calculated as

cbi={εRBshiε+a·RBshifishi<RBshi+fi+shi+fi<RB
(4)

2.3 Recovery time

Fig. 3. Process of Recovery Time

Tr=δ+s+ε+p·(nps+nb)
(5)

where nps and nb are the number of nodes traveled by NIS and WUS, respectively. The signal propagation time s is calculated as

s=dps+dbu
(6)

This paper investigates the impact of routing strategy on recovery time, so the signal propagation time s, which is directly proportional to the physical distance of segment (or primary path) and the corresponding backup path, is the main contribution to the recovery time Tr . It is obvious that, in Fig. 3, the length of the segment and the corresponding backup path is shorter than the length of the full primary path and the corresponding backup path, then after the failures, the recovery time of the segment protection will be faster than the path protection according to Eq. (5) and Eq. (6).

3. Segment shared protection algorithm

3.1 Network model

Nj : the node j, NjN.

R (s,d): the connection request form source node s to destination node d.

Rr : the reliability of the connection requested by the applications/users.

Pp : the primary path for the connection request R (s,d).

Rp : the reliability of the primary path Pp , calculated as

Rp=LiList(Lj)forPpRLi
(7)

M: the “mid-node” on Pp . It can divide the Pp into two segments (unprotected-segment and protected-segment).

Pus , Pps : the unprotected segment and the protected segment on Pp . They are separated by M.

Rc : the connection’s reliability that is calculated as Eq. (2).

3.2 The process of SSPA

Step 1: Waiting for a request.

If the request is for establishing a connection, go to Step2.

Else, if the request is for releasing a connection, then update the network’s state and go back to Step 1.

If fail to find the Pp , then reject the request and go back to Step 1.

Else, compute the reliability Rp for the Pp .

If RpRr , then we do not need to assign the backup path for the Pp . Accept the request, allocate resources for Pp , and go back to Step 1.

Else, if Rp < Rr , then we need to assign the backup path for the Pp . Record List(Lj ) for Pp and go to Step 3.

Step 3: According to Eq. (8), find the maximal value of the m.

j=1,2mRLj>Rr,if(LjList(Lj)forPpandm<n)
(8)

If fail to find the Pbs , then go to Step 4.

Else, compute the reliability Rc according to Eq. (2).

If Rc <Rr , go to step 4.

Else, if RcRr , accept the request, record the allocated routes and resources, and go back to Step 1.

If fail to find the Pbs , tmp=tmp-1.

If tmp≥1, then go back to Step 4.

Else, reject the request and go back to Step 1.

Else, compute the reliability Rc according to Eq. (2).

If Rc <Rr , tmp=tmp-1.

If tmp≥1, go back to Step 4.

Else, reject the request and go back to Step 1.

Else, if RcRr , accept the request, record the allocated routes and resources, and go back to Step 1.

It is obvious that the PSPA-DiR is a special condition of SSPA when tmp=1 in Step 4. The complexity of the SSPA depends mostly on the running time of Dijkstra’s algorithm. The complexity of Dijkstra’s algorithm is O(N 2). By analyzing the process, the complexity of finding a primary path is O(N 2); the complexity of finding a backup path is no more than D×O(N 2), where D is the diameter of the network (D is defined as the number of hops of the longest path in the network). So we can determine that the complexity of SSPA is approximately O((D+1)N 2) for a connection request.

4. Simulation result

Fig. 4. test topologies

In accordance with [9

9. L. Guo, H. Yu, and L. Li, “A new shared-path protection algorithm under shared-risk link group constraints for survivable WDM mesh networks,” Opt. Commun. 246, 285–295 (2005). [CrossRef]

,12

12. L. Guo, H. Yu, and L. Li, “A new path protection algorithm for meshed survivable wavelength-division-multiplexing networks,” Lecture Notes in Computer Science. 3420, 68–75 (2005). [CrossRef]

], we introduce the BRPC (backup resources per connection) and the blocking probability (BP) to evaluate the performances. We also compare the recovery time (RT) as we discussed in Section II for the three algorithms.

A smaller BRPC means that we need to assign fewer wavelengths. It also means that there are fewer backup wavelengths in reserving along all the backup paths, that is, a higher resource utilization ratio or a higher degree of reserved resources sharing. A higher resource utilization ratio will lead to lower traffic blocking probability because the following requests can use more free wavelengths.

Fig. 5. comparison among the three schemes: SSPA, PSPA-DiR and PSPA using topologies N-21,N-17.

In Fig. 5 (ad), it is obvious that, in both test topologies, the SSPA performs lower blocking probability and higher resource utilization ratio than the other algorithms. The reason (see analysis in subsection 2.1) for this is that, the SSPA provides partial protection for the segment of primary path according to the differentiated reliability of the users’ requirements, and the reserved backup wavelengths are less than that of the PSPA and the PSPA-DiR, namely, more free wavelengths can be assigned to the following traffic routing, so the BP of the SSPA is lower. We can also see that the BP in a larger network (N-21) is lower than that in a smaller network (N-17) in all three schemes, because in a larger network more routes and wavelengths can be selected for the coming requests.

In Fig. 5(e) and (f), we can see that, in both test topologies, the SSPA performs faster recovery time than the PSPA-DiR and PSPA. The reason (see analysis in Subsection 2.3) for this is that, the length of the segment and the corresponding backup path is shorter than the length of the full primary path and the corresponding backup path, then after the failures, the recovery time of the segment protection will be shorter than the path protection according to Eq. (5) and Eq. (6).

In Fig. 5(ad), we can see that, when the Rr increases, the resource utilization ratio will become lower and the blocking probability will become higher. Because when Rr becomes larger, more primary paths need to be assigned backup paths and more wavelengths will be reserved, and then the resource utilization ratio will become lower. Lower resource utilization ratio will lead to higher blocking probability because less free wavelengths can be assigned to the following requests.

In Fig. 5(e) and (f), when the Rr increases, the recovery time of SSPA will become longer. The reason for this is that, if the Rr becomes larger, then we will compute a longer protected segment according to the Step 4 in the process of SSPA, and longer protected segment will lead to longer backup path. Thus, the length of the segment and the corresponding backup path will become larger, and this will lead to longer recovery time according to Eq. (5) and Eq. (6).

5. Conclusion

Acknowledgments

This research is supported by National Natural Science Foundation of China (NSFC) under grant No.60302010.

References and links

1.

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

2.

Y. Xiong, D. Xu, and C. Qiao, “Achieving fast and bandwidth-efficient shared-path protection,” J. Lightwave Technol. 21, 365–371 (2003). [CrossRef]

3.

C. Saradhi, M. Gurusamy, and L. Zhou, “Differentiated QoS for survivable WDM optical networks,” IEEE Commun. Mag. 42, 8–14 (2004). [CrossRef]

4.

C. V. Saradhi and C. S. R. Murthy, “Routing differentiated reliable connections in WDM optical networks,” Opt. Net. Mag. 3, 50–67 (2002).

5.

L. Guo, H. Yu, and L. Li, “Joint routing-selection algorithm for a shared path with differentiated reliability in survivable wavelength-division-multiplexing mesh networks,” Opt. Express. 12, 2327–2337 (2004), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-11-2327 [CrossRef] [PubMed]

6.

J. Zhang and B. Mukherjee, “A Review of fault management in WDM mesh networks: basic concepts and research challenges,” IEEE Network. 18, 41–48 (2004). [CrossRef]

7.

P. H. Ho, J. Tapolcai, and T. Cinkler, “Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels,” IEEE/ACM Tran.Networking. 12, 1105–1118 (2004). [CrossRef]

8.

D. Xu, Y. Xiong, and C. Qiao, “Novel algorithms for shared segment protection,” IEEE JSAC. 21, 1320–1331 (2003).

9.

L. Guo, H. Yu, and L. Li, “A new shared-path protection algorithm under shared-risk link group constraints for survivable WDM mesh networks,” Opt. Commun. 246, 285–295 (2005). [CrossRef]

10.

Pin-Han Ho and Hussein T. Mouftah, “A Novel Survivable Routing Algorithm for Shared Segment Protection in Mesh WDM Networks With Partial Wavelength Conversion,” IEEE JSAC. 22, 1548–1560 (2004).

11.

L. Guo, H. Yu, and L. Li, “Path protection algorithm with trade-off ability for survivable wavelength-division-multiplexing mesh networks,” Opt. Express. 12, 5834–5839 (2004), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-24-5834 [CrossRef] [PubMed]

12.

L. Guo, H. Yu, and L. Li, “A new path protection algorithm for meshed survivable wavelength-division-multiplexing networks,” Lecture Notes in Computer Science. 3420, 68–75 (2005). [CrossRef]

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

ToC Category:
Research Papers

History
Original Manuscript: February 28, 2005
Revised Manuscript: April 6, 2005
Published: April 18, 2005

Citation
Jin Cao, Lei Guo, Hongfang Yu, and Lemin Li, "Dynamic segment shared protection algorithm for reliable wavelength-division-multiplexing mesh networks," Opt. Express 13, 3087-3095 (2005)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-13-8-3087


Sort:  Journal  |  Reset  

References

  1. S. Ramamurthy, L.Sahasrabuddhe, B. Mukherjee, �??Survivable WDM mesh networks,�?? J. Lightwave Technol. 21, 870-883 (2003). [CrossRef]
  2. Y. Xiong, D. Xu, C. Qiao, �??Achieving fast and bandwidth-efficient shared-path protection,�?? J. Lightwave Technol . 21, 365-371 (2003). [CrossRef]
  3. C. Saradhi, M. Gurusamy, L. Zhou, �??Differentiated QoS for survivable WDM optical networks,�?? IEEE Commun. Mag. 42, 8-14 (2004). [CrossRef]
  4. C. V. Saradhi, C. S. R. Murthy, �??Routing differentiated reliable connections in WDM optical networks,�?? Opt. Net. Mag. 3, 50�??67 (2002).
  5. L. Guo, H. Yu, L. Li, �??Joint routing-selection algorithm for a shared path with differentiated reliability in survivable wavelength-division-multiplexing mesh networks,�?? Opt. Express. 12, 2327-2337 (2004), <a href="http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-11-2327">http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-11-2327</a> [CrossRef] [PubMed]
  6. J. Zhang, B. Mukherjee, �??A Review of fault management in WDM mesh networks: basic concepts and research challenges,�?? IEEE Network. 18, 41-48 (2004). [CrossRef]
  7. P. H. Ho, J. Tapolcai, T. Cinkler, �??Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels,�?? IEEE/ACM Tran. Networking. 12, 1105-1118 (2004). [CrossRef]
  8. D. Xu, Y. Xiong, C. Qiao, �??Novel algorithms for shared segment protection,�?? IEEE JSAC. 21, 1320-1331 (2003).
  9. L. Guo, H. Yu, and L. Li, �??A new shared-path protection algorithm under shared-risk link group constraints for survivable WDM mesh networks,�?? Opt. Commun. 246, 285-295 (2005). [CrossRef]
  10. Pin-Han Ho, Hussein T. Mouftah, �??A Novel Survivable Routing Algorithm for Shared Segment Protection in Mesh WDM Networks With Partial Wavelength Conversion,�?? IEEE JSAC. 22, 1548-1560 (2004).
  11. L. Guo, H. Yu, and L. Li, �??Path protection algorithm with trade-off ability for survivable wavelength-division-multiplexing mesh networks,�?? Opt. Express. 12, 5834-5839 (2004), <a href=" http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-24-5834">http://www.opticsexpress.org/abstract.cfm?URI=OPEX-12-24-5834</a> [CrossRef] [PubMed]
  12. L. Guo, H. Yu, and L. Li, "A new path protection algorithm for meshed survivable wavelength-division-multiplexing networks," Lecture Notes in Computer Science, 3420, 68-75 (2005). [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