1 May 2006 Availability analysis considering primary and backup sharing in wavelength-division multiplexed networks
Author Affiliations +
Optical Engineering, 45(5), 050505 (2006). doi:10.1117/1.2196435
Abstract
In survivable wavelength-division multiplexed networks, the backup resource can be shared by the primary light paths, which is called primary-backup sharing. We find that primary-backup sharing can have an effect on the link availability. We focus on routing under dynamic availability of the wavelength resource while the requested reliability of traffic has to be met, using the modified shortest path algorithm. We propose a new algorithm called the dynamic link availability algorithm and evaluate the performance of the proposed algorithm on the NSFNET.
Li, Jin, and Li: Availability analysis considering primary and backup sharing in wavelength-division multiplexed networks

1.

Introduction

In the research of survivability in wavelength-division multiplexed (WDM) mesh networks, the growing importance of differentiated reliability (DiR)1 is evident. Networks can provide multiple degrees of reliability by means of DiR. A service-level agreement (SLA)2 must be guaranteed for reliable connection provisioning.

The reliability of a component is the faultless probability considering its own failure. The differentiated reliable connections have different reliability requirements. Connection availability2 provides an important metric, which is helpful to facilitate cost-effective connection provisioning and relates to mean time between failure (MTBF) and mean time to repair (MTTR).3 Each functional element of WDM system is characterized by a known average a steady-state availability As=MTBF(MTBF+MTTR) .3

In Ref. 4, the authors present a shared protection scheme with DiR. It shows better performance than the dedicated path protection scheme. In Ref. 5, the reliability of a connection as a parameter has been considered to determine the link cost. A connection with the reliability requirement is called an R-connection.5 Compared to full protection and no protection schemes, it is efficient enough to provide enough partial backup light paths for primary light paths to enhance the reliability of the connections, but Ref. 5 does not consider the primary-backup sharing. In Ref. 6, in order to further raise the efficiency, primary-backup and backup-backup multiplexing is used to reduce blocking probability. In Ref. 7, the authors combined the notion of primary-backup sharing with multiclass traffic, which is classified with different priority. However, Refs. 6, 7 do not consider the different levels of fault tolerance requirement and the dynamic link availability.

We evaluate the connection availability to meet the service reliability requirement. We take into consideration routing the R-connection with DiR as well as the dynamic character of the link availability. The primary light path that contains the links shared with one or more backup light paths might be preempted while the failure occurs, so it has a preempted probability. The link availability has to be updated based on the situation of backup resources because the preempted probability must be considered. Therefore, the dynamic link availability has to be considered, if primary-backup sharing is allowed. The detailed reason why the link availability is variable in some cases is given in Sec. 2. We use a wavelength layered-graph model8 to route an R-connection, because it can reflect the dynamic availability of a wavelength channel. The availability of every link as a parameter has been considered to determine the link cost. By using the modified route selection algorithm, the R-connection with the largest availability and least hops can be found. This scheme results in better performance although part of the low-priority services may be preempted when the link failure occurs. However, this type of preemption is permitted on the condition that the SLA of traffic is met.

The remainder of the paper is organized as follows. Section 2 describes how to evaluate the dynamic availability. Section 3 presents an analytical model and dynamic link availability (DLA) algorithm. Section 4 presents the simulation results to evaluate the performance of the DLA. Finally, concluding remarks are included in Sec. 5.

2.

Problem Definition

Figure 1 gives an example of how to evaluate availability and how to consider primary-backup sharing. We let A(e) denote the dynamic availability of channel e , and A0(e) denote the original availability of channel e , which relates to As as shown in Sec. 1.

Fig. 1

Routing the R-connections allowing primary-backup sharing.

050505_1_1.jpg

There exist two primary light paths L1(1f7g4) and L2(3h8i5e6) , for which full backup light path B1(1a2b3c4) and partial backup light path B2(3c4d5) are provided, respectively.

At present, there is no free resource in this network and therefore any connections will be blocked if there is no primary-backup sharing. Consequently we use the notion of primary-backup sharing to route the connections, which have different reliability requirement. The links a , b , and c serve for L1 and L2 . We can share the backup resource with primary light path L3 (1a2b3c4d5) , which comes from node 1 to node 5. While computing A(L1) and A(B2) , we needn’t consider the preempted probabilities of L1 and L2 . However, while computing A(L3) , we should consider the probability of L3 being preempted by L1 or L2 when the failure occurs on L1 or L2 . Therefore, the link availability of a , b , and c is variable. In order to meet the requested reliability of R-connection on L3 , A(L3) should be larger than R(L3) . We calculate A(L3) as

1

A(L3)=A(a)A(b)A(c)A(d).
B1 covers the segment S1(1f7g4) of L1 . B2 covers the segment S2(3h8i5) of L2 .

2.

A(S1)=A0(f)A0(g),
A(S2)=A0(h)A0(i).
When the failure occurs among links of S1 and S2 , the probability Pb1 or Pb2 that L3 may be preempted by L1 or L2 can be calculated as

3.

Pb1=1A(S1),
Pb2=1A(S2).
The availability of every channel can be calculated as

4.

A(a)=A0(a)(1Pb1),
A(b)=A0(b)(1Pb1),
A(c)=A0(c)(1Pb1)(1Pb2),
A(d)=A0(d)(1Pb2).
We can get the availability A(L3) of the primary light path L3 through Eqs. 1, 2, 3, 4.

Through the above analysis, the availability of a link will be reduced when the link carries one or more backup light paths. Therefore, the link can only load lower priority traffic.

Note that, in order to avoid the domino effect, the backup light paths can’t be established for the primary light paths, which contain the links shared by one or more backup light paths.

3.

Implementation

3.1.

Definitions

The variables are defined as follows: PL is the set of primary light paths; BL is the set of backup light paths; PLi is the i ’th primary light path; BLi is the backup of the i ’th primary light path; Si is the protected segment of the i ’th primary light path; M is a Boolean variable, where 1 denotes the search for the primary light path, and 0 denotes the search for the backup light path; const is a parameter that is used to control the trade-off between availability and delay, Hl , is the set of all channels protected by channel l ; G(N,L,W) , is a network topology for a given WDM network, where N is the set of the nodes, L is the set of bidirectional links, and W is the set of nodes; and LG(V,E) is the layered-graph model, where each node iN in G is replicated W times in LG , the set of nodes in LG is V , and the set of edges in LG is E .

3.2.

Solution Approach

The topology G is mapped into LG as proposed in Ref. 8. There are W wavelength panels in LG . The link cost function of the modified route selection algorithm is

5

cost(e)=delayconstlog[A(e)][(eE)].
A(e) is given as follows:

6

A(e)={0ifePLA0(e)i=1HeA0(hi)if(eBL)(hiHe)(M1)A0(e)if(eBL)(M=0)}.
The composite availability comprising of the primary and backup light path is calculated as follows:

7.

Ac=A(p){A(r)+A(q)[1A(r)]}A(r)
[(pPLi)(qBLi)(rSi)].
A formal description of the algorithms is given below:
  1. Step 1: Map a network topology G(N,L,W) into the corresponding layered graph LG(V,E) . Let M equal 1 and set the cost of edge in LG according to Eq. 6.

  2. Step 2: Wait for an R -connection. If it is a connection request, go to Step 3. If it is a release request, go to Step 5.

  3. Step 3: Find the shortest path PLi in LG on the available panel k . If A(PLi)> Ri , accept the call and map PLi into the corresponding light path in G . M is set as 1. Update the cost of the edges on path according to Eq. 6. Go to step 2.

  4. Step 4: Find BLi for PLi in the same panel k . M is set as 0. Update the cost of the edges on path according to Eq. 6. The composed availability Ac can be given using Eq. 7. If Ac> Ri , accept the call and map PLi and BLi into the corresponding light path in G .

  5. Step 5: Update the cost of the edges corresponding to Eq. 6 while M equals 1. Release the light path and go to step 2.

In particular, the complexities of steps 1–5 are O(V) , O(1) , O[(L+N2)×W] , O(L2+N2) , and O(L2W) . The overall complexity of DLA is O(max{N2,L2}×W) .

4.

Performance Evaluation

The simulation is performed for a network environment NSFNET equipped with 14 nodes and 21 links, with the following assumptions: (1) The least requested reliability is set as 0.8. The requested reliability of connection is an uniform distributed random value between 0.81 . (2) The reliability of every link is set as 0.98. (3) Every link has 12 wavelengths. (4) const is set as 20. (5) The delay of each link is set as 1.

We randomly generate 106 source-destination pairs as the R-connection with Poisson distribution.

Figure 2 shows the simulation result for a successful routes ratio. The successful routes ratio denotes the fraction of the accepted R-connections. The least requested reliability is 0.8 (which means that the requested reliability is set as a uniformly distributed random value between 0.81 ). Both the partial backup and the DLA algorithm have better performance than the no-backup algorithm when the network-offered load is low. While the load is high, the partial backup algorithm is not much worse than the no-backup algorithm. Two factors lead to this result. The first is that many R-connections that have low requested reliability don’t need a backup resource. The second is that some R-connections have high requested reliability and occupied spare resources in the partial backup algorithm. The DLA algorithm has the best performance because of its primary-backup sharing and accurate descriptions of availability.

Fig. 2

Successful routes ratio performances.

050505_1_2.jpg

In Fig. 3, the least requested reliability increase from 0.7 to 0.95. The increment is 0.05. The network-offered load is set as 80 elang. Correspondingly, successful routes that every algorithm established depress along with increasing of the least requested reliability. No backup algorithm shows the worst performance while the least requested reliability is high because the R-connections that have the high reliability requirements can’t find the backup light paths to enhance their availability. The DLA algorithm shows the best performance among these three algorithms.

Fig. 3

Relationship of requested reliability and successful routes ratio.

050505_1_3.jpg

5.

Conclusion

The key contribution of this paper is considering the dynamic availability of wavelength links. This scheme allows the wavelength channels that run the backup light path to be shared by the primary light path. As a result, we have more resources to route the R-connections. Our DLA algorithm can describe link availability accurately. Through analysis and simulation, the advantages of this scheme outperform those of traditional ones. The performance of the algorithm is good for either high-reliability requirements or for low-reliability requirements.

Acknowledgment

Financial support from the National Natural Science Foundation of China (Grant No. 60502004) is gratefully acknowledged.

References

1.  A. Fumagalli and M. Tacca, “Differentiated reliability (DiR) in WDM rings without wavelength converters,” Proc. IEEE ICC’01, pp, 2887–2891 (Jun. 2001). Google Scholar

2.  H. Yurong, W. Wen, J. P. Heritage, and B. Mukherjee, “A generalized protection framework using a new link-State availability model for reliable optical networks,” J. Lightwave Technol.0733-8724 22(11), 2536–2547 (2004). Google Scholar

3.  D. Arci, D. Petecchi, G. Maier, A. Pattavina, and M. Tornatore, “Availability models for protection techniques in WDM networks,” Proc. Design Reliable Communication Networks, pp. 158–166 (2003). Google Scholar

4.  M. Tacca, A. Fumagalli, A. Paradisi, , “Differentiated reliability in optical networks: theoretical and practical results,” J. Lightwave Technol.0733-8724 21(11), 2576–2586 (2003). Google Scholar

5.  V. Saradhi and C. S. R. Murthy, “Routing differentiated reliable connections in single and multi-fiber WDM optical networks,” Proc. SPIE0277-786X 4599, 24–35 (Aug 2001). Google Scholar

6.  G. Mohan, C. SivaRam, and K. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw.1063-6692 9, 553–565 (Oct. 2001). Google Scholar

7.  A. Sen, B. H. Shen, B. Hao, H. Jayakumar, and S. Bandyopadhyay, “On a preemptive multi-class routing scheme with protection paths for WDM networks,” Proc. IEEE ICC’03, pp. 1417–1422 (2003). Google Scholar

8.  S. H. Xu, L. M. Li, and S. Wang, “Dynamic routing and assignment of wavelength algorithms in multifiber wavelength division multiplexing networks,” IEEE J. Sel. Areas Commun.0733-8716 10.1109/49.887932 18(10), 2130–2137 (Oct. 2000). Google Scholar

Yonggang Li, Yaohui Jin, Lemin Li, "Availability analysis considering primary and backup sharing in wavelength-division multiplexed networks," Optical Engineering 45(5), 050505 (1 May 2006). https://doi.org/10.1117/1.2196435
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top