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

Optics Express, Vol. 13, Issue 8, pp. 3087-3095 (2005)

http://dx.doi.org/10.1364/OPEX.13.003087

Acrobat PDF (142 KB)

### 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

## 2. Syetem model and problem analysis

### 2.1 Analysis of reliablility

*i*,

*j*) is denoted as

*R*

_{(i,j)}. At the beginning period of the foundation of the network,

*R*

_{(i,j)}can be determined by the fiber component manufacturers. After several years,

*R*

_{(i,j)}can be estimated by the failure rate based on past experience. The reliability of a light-path

*p*, denoted as

*R*

_{p}, is the multiplication of the reliabilities of these fiber links that are traversed by the light-path

*p*.

*P*

_{p}is 1-2-3-4-5. Each fiber link has its own reliability:

*R*

_{(i,i+1)}, (

*i*=1,2,3,4). We assume that the failures of the fiber links are independent. We can calculate the reliability of the primary path as

*R*

_{p}=Π

*R*

_{(i,i+1)}(

*i*=1,2,3,4). If

*R*

_{p}is less than the reliability of users’ requirement, then for the PSPA-DiR, we can choose 1-6-7-8-5 as the backup path (denoted as

*P*

_{b}) for the primary path, and the reliability of the backup path can be calculated as

*R*

_{b}=

*R*

_{(1,6)}·

*R*

_{(6,7)}·

*R*

_{(7,8)}·

*R*

_{(8,5)}. Then, the

*R*

_{c}that denotes the reliability of the connection can be calculated as

*P*

_{us}and its reliability is denoted as

*R*

_{us}; the second segment which will be protected is denoted as

*P*

_{ps}and its reliability is denoted as

*R*

_{ps}. For the SSPA, we only compute a backup path for the second segment

*P*

_{ps}. In Fig. 1, the

*P*

_{p}is 1-2-3-4-5, the

*P*

_{us}is 1-2-3, the

*P*

_{ps}is 3-4-5, and the backup path that is denoted as

*P*

_{bs}for the

*P*

_{ps}is 3-9-5. Then, the reliability of the connection is calculated as Eq. (2), where

*R*

_{c}=(reliability of the first segment)×(joint reliability of the second segment and its backup path).

*R*

_{r}denote the reliability of users’ requirement. Assume the reliability of each fiber link is 0.98 and the

*R*

_{r}=0.95. In Fig. 1, for the PSPA-DiR, we choose 1-6-7-8-5 as the backup path and get the

*R*

_{c}=0.99393 according to Eq. (1). For the SSPA, we choose 3-9-5 as the backup path to protect the second segment and get the

*R*

_{c}=0.95889 according to Eq. (2). It is obvious that the two protection mechanisms both satisfy the required reliability because both

*R*

_{c}are greater than

*R*

_{r}(=0.95). We can also see that, in Fig. 1, the second segment’s backup path is shorter than the primary’s backup path, and the SSPA uses less backup wavelengths (2 wavelengths for the

*P*

_{bs}) than the PSPA-DiR (4 wavelengths for the

*P*

_{b}), so that the SSPA has better resource utilization than the PSPA-DiR.

## 2.2 Cost function

*G*(

*N*,

*E*), where

*N*and

*E*are the sets of nodes and bi-directional fiber links, respectively. The capacity on link

*i*(∈

*E*) can be categorized into the following three types:

*Free capacity*, denoted as

*f*

_{i}, which are the free capacities that can be used by the following primary or backup paths.

*Reserved capacity*, denoted as

*RC*

_{i}, which are the reserved capacities by some backup paths.

*Working capacity*, denoted as

*W*

_{i}, 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.

*cw*

^{’}for finding a primary path (

*P*

_{P}) with requested bandwidth (

*RB*) is calculated as

*c*

_{i}and

*R*

_{Li}are the basic cost and reliability of link

*i*, respectively;

*k*is a parameter that can adjust the tradeoff between the basic cost and reliability along the chosen path (we set

*k*=1 in the later simulations). The reason that we introduce the link reliability into the link cost function is to find a less cost and higher-reliable primary path simultaneously. We can see from Eq. (3) that, those links which have higher reliabilities will have less link cost. If the primary paths traverse those links, it is more likely that the reliability of the primary paths are greater than users’ requirement and we do not need to compute the backup paths. Thus, the reserved wavelength resources will be saved.

*P*

_{bs}) for the protected segment (

*P*

_{ps}) on the primary path, we should first define the corresponding cost function. With the requested bandwidth(

*RB*) and the found primary path(

*P*

_{p}), the

*reserved capacity*(

*RC*

_{i}) along link

*i*can be further divided into two types:

*cb*

^{’}for finding a backup path (

*P*

_{bs}) for protected segment (

*P*

_{ps}) with requested bandwidth (

*RB*) is calculated as

## 2.3 Recovery time

*P*

_{ps}), then the beginning node of the

*P*

_{ps}sends a wake-up signal (WUS) to activate the configuration of the backup path (

*P*

_{bs}). The configuration process along

*P*

_{bs}can be conducted in a pipeline manner. At last, the working traffic will be switched over to the backup path.

*δ*that is assumed as 10

*us*, the message-processing time

*p*at a node that is assumed as 20

*us*, the signal propagation time

*s*that depends on the distance of the links the signal travels, and the configuration delay

*ε*at all nodes along the backup path that is assumed as 5

*ms*. So the recovery time

*T*

_{r}is calculated as:

*n*

_{ps}and

*n*

_{b}are the number of nodes traveled by NIS and WUS, respectively. The signal propagation time

*s*is calculated as

*d*

_{ps}and

*d*

_{b}are the physical distance of fiber links traveled by NIS and WUS, respectively;

*u*is the speed of light traveling in the fiber (

*u*=2×10

^{8}m/s).

*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

*T*

_{r}. 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

*G*(

*N*,

*L*,

*W*) for a given meshed WDM optical network, where

*N*is the set of nodes,

*L*is the set of bi-directional fiber links (we suppose each link has two opposite fibers),

*W*is the set of wavelengths on a fiber. A connection request’s arrival is dynamically and only one connection arrives at a time. We assume each requested bandwidth is a wavelength and allow the full wavelength convertible capacity for each node. Before introducing the process of SSPA, we present the following symbols:

*L*

_{i}: the fiber link

*i*,

*L*

_{i}∈

*L*.

*N*

_{j}: the node

*j*,

*N*

_{j}∈

*N*.

*L*

_{i}. It can be determined by a long time experience as we mentioned in Section 2. We suppose that the reliability of each fiber link is independent.

*c*

_{i}: the basic cost of the link

*i*. It is determined by physical length of the fiber link, the expense of the installation of the fiber link, and so on.

_{i}for computing primary path and backup path respectively. They are determined by the basic cost of the link and the current network’s state.

*R*

_{(s,d)}: the connection request form source node

*s*to destination node

*d*.

*R*

_{r}: the reliability of the connection requested by the applications/users.

*P*

_{p}: the primary path for the connection request

*R*

_{(s,d)}.

*P*

_{b}: the backup path for the

*P*

_{p}.

*P*

_{b}and

*P*

_{p}should be link-disjoint.

*List*(

*L*

_{j}) for

*P*

_{p}: the set of all fiber links

*L*

_{j}that are traversed by

*P*

_{p}. We suppose there are

*n*fiber links traversed by

*P*

_{p}, and then

*j*=1, 2, 3…n.

*R*

_{p}: the reliability of the primary path

*P*

_{p}, calculated as

*M*: the “mid-node” on

*P*

_{p}. It can divide the

*P*

_{p}into two segments (unprotected-segment and protected-segment).

*P*

_{us},

*P*

_{ps}: the unprotected segment and the protected segment on

*P*

_{p}. They are separated by

*M*.

*P*

_{bs}: the backup path for the

*P*

_{ps}.

*P*

_{ps}and

*P*

_{bs}should be link-disjoint.

## 3.2 The process of SSPA

*Step 1*: Waiting for a request.

*Step 2*: Adjust the link cost

*L*

_{i}∈

*L*) according to Eq. (3) and compute the minimal-cost path

*P*

_{p}from node

*s*to node

*d*with the Dijkstra’s algorithm.

*P*

_{p}, then reject the request and go back to Step 1.

*R*

_{p}for the

*P*

_{p}.

*R*

_{p}≥

*R*

_{r}, then we do not need to assign the backup path for the

*P*

_{p}. Accept the request, allocate resources for

*P*

_{p}, and go back to Step 1.

*R*

_{p}<

*R*

_{r}, then we need to assign the backup path for the

*P*

_{p}. Record

*List*(

*L*

_{j}) for

*P*

_{p}and go to Step 3.

*n*is the set of fiber links of

*List*(

*L*

_{j}) for

*P*

_{p}.

*M*to be the downstream node of the

*L*

_{m}, assign the unprotected segment that traverses the links

*L*

_{1},

*L*

_{2},…

*L*

_{m}to be

*P*

_{us}and the protected segment that traverses the links

*L*

_{m+1},

*L*

_{m+2},…

*L*

_{n}to be

*P*

_{ps}. Assume

*tmp*=

*m*. Adjust the link cost

*L*

_{i}∈

*L*) according to Eq. (4) and compute the minimal-cost backup path

*P*

_{bs}for the

*P*

_{ps}.

*P*

_{bs}, then go to Step 4.

*R*

_{c}<

*R*

_{r}, go to step 4.

*R*

_{c}≥

*R*

_{r}, accept the request, record the allocated routes and resources, and go back to Step 1.

*Step 4*: Let the

*M*to be the upstream node of the

*L*

_{tmp}renewedly, re-assign the unprotected segment that traverses the links

*L*

_{1},

*L*

_{2},…

*L*

_{tmp}

_{-1}to be

*P*

_{us}and the protected segment that traverses the links

*L*

_{tmp},

*L*

_{tmp}

_{+1},…

*L*

_{n}to be

*P*

_{ps}. Update the link cost

*L*

_{i}∈

*L*) according to Eq. (4) and compute the minimal-cost backup path

*P*

_{bs}for the new

*P*

_{ps}.

*P*

_{bs},

*tmp*=

*tmp*-1.

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

*R*

_{c}<

*R*

_{r},

*tmp*=

*tmp*-1.

*tmp*≥1, go back to Step 4.

*R*

_{c}≥

*R*

_{r}, accept the request, record the allocated routes and resources, and go back to Step 1.

*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

^{6}. We adopt the PSPA algorithm [4] and PSPA-DiR algorithm [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]

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

*R*

_{r}increases, the resource utilization ratio will become lower and the blocking probability will become higher. Because when

*R*

_{r}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.

*R*

_{r}increases, the recovery time of SSPA will become longer. The reason for this is that, if the

*R*

_{r}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

## References and links

1. | S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol. |

2. | Y. Xiong, D. Xu, and C. Qiao, “Achieving fast and bandwidth-efficient shared-path protection,” J. Lightwave Technol. |

3. | C. Saradhi, M. Gurusamy, and L. Zhou, “Differentiated QoS for survivable WDM optical networks,” IEEE Commun. Mag. |

4. | C. V. Saradhi and C. S. R. Murthy, “Routing differentiated reliable connections in WDM optical networks,” Opt. Net. Mag. |

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

6. | J. Zhang and B. Mukherjee, “A Review of fault management in WDM mesh networks: basic concepts and research challenges,” IEEE Network. |

7. | P. H. Ho, J. Tapolcai, and T. Cinkler, “Segment shared protection in mesh communications networks with bandwidth guaranteed tunnels,” IEEE/ACM Tran.Networking. |

8. | D. Xu, Y. Xiong, and C. Qiao, “Novel algorithms for shared segment protection,” IEEE JSAC. |

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

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

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. | L. Guo, H. Yu, and L. Li, “A new path protection algorithm for meshed survivable wavelength-division-multiplexing networks,” Lecture Notes in Computer Science. |

**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

- S. Ramamurthy, L.Sahasrabuddhe, B. Mukherjee, �??Survivable WDM mesh networks,�?? J. Lightwave Technol. 21, 870-883 (2003). [CrossRef]
- Y. Xiong, D. Xu, C. Qiao, �??Achieving fast and bandwidth-efficient shared-path protection,�?? J. Lightwave Technol . 21, 365-371 (2003). [CrossRef]
- C. Saradhi, M. Gurusamy, L. Zhou, �??Differentiated QoS for survivable WDM optical networks,�?? IEEE Commun. Mag. 42, 8-14 (2004). [CrossRef]
- C. V. Saradhi, C. S. R. Murthy, �??Routing differentiated reliable connections in WDM optical networks,�?? Opt. Net. Mag. 3, 50�??67 (2002).
- 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]
- 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]
- 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]
- D. Xu, Y. Xiong, C. Qiao, �??Novel algorithms for shared segment protection,�?? IEEE JSAC. 21, 1320-1331 (2003).
- 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]
- 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).
- 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]
- 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.