## 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 availability^{2} 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
${A}_{s}=\mathrm{MTBF}\u2215(\mathrm{MTBF}+\mathrm{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 model^{8} 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\left(e\right)$ denote the dynamic availability of channel $e$ , and ${A}_{0}\left(e\right)$ denote the original availability of channel $e$ , which relates to ${A}_{s}$ as shown in Sec. 1.

There exist two primary light paths ${L}_{1}\left(1f7g4\right)$ and ${L}_{2}\left(3h8i5e6\right)$ , for which full backup light path ${B}_{1}\left(1a2b3c4\right)$ and partial backup light path ${B}_{2}\left(3c4d5\right)$ 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 ${L}_{1}$ and ${L}_{2}$ . We can share the backup resource with primary light path ${L}_{3}$ $\left(1a2b3c4d5\right)$ , which comes from node 1 to node 5. While computing $A\left({L}_{1}\right)$ and $A\left({B}_{2}\right)$ , we needn’t consider the preempted probabilities of ${L}_{1}$ and ${L}_{2}$ . However, while computing $A\left({L}_{3}\right)$ , we should consider the probability of L3 being preempted by ${L}_{1}$ or ${L}_{2}$ when the failure occurs on ${L}_{1}$ or ${L}_{2}$ . Therefore, the link availability of $a$ , $b$ , and $c$ is variable. In order to meet the requested reliability of R-connection on ${L}_{3}$ , $A\left({L}_{3}\right)$ should be larger than $R\left({L}_{3}\right)$ . We calculate $A\left({L}_{3}\right)$ as

## 1

$$A\left({L}_{3}\right)=A\left(a\right)\bullet A\left(b\right)\bullet A\left(c\right)\bullet A\left(d\right).$$## 2.

## 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;
$P{L}_{i}$
is the
$i$
’th primary light path;
$B{L}_{i}$
is the backup of the
$i$
’th primary light path;
${S}_{i}$
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,
${H}_{l}$
, 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
$i\u220aN$
in
$G$
is replicated
$\mid W\mid $
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 $\mid W\mid $ wavelength panels in $LG$ . The link cost function of the modified route selection algorithm is

## 5

$$\text{cost}\left(e\right)=\text{delay}-\text{const}\bullet \mathrm{log}\left[A\left(e\right)\right]\left[(e\u220aE)\right].$$## 6

$$A\left(e\right)=\{\begin{array}{ll}0& \text{if}\phantom{\rule{0.3em}{0ex}}e\u220aPL\\ {A}_{0}\left(e\right)\bullet \prod _{i=1}^{\mid {H}_{e}\mid}{A}_{0}\left({h}_{i}\right)& \text{if}\phantom{\rule{0.3em}{0ex}}(e\u220aBL)\wedge ({h}_{i}\u220a{H}_{e})\wedge (M-1)\\ {A}_{0}\left(e\right)& \text{if}\phantom{\rule{0.3em}{0ex}}(e\u220aBL)\wedge (M=0)\end{array}\phantom{\}}.$$## 7.

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.

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.

Step 3: Find the shortest path $P{L}_{i}$ in $LG$ on the available panel $k$ . If $A\left(P{L}_{i}\right)>{R}_{i}$ , accept the call and map $P{L}_{i}$ 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.

Step 4: Find $B{L}_{i}$ for $P{L}_{i}$ 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 ${A}_{c}$ can be given using Eq. 7. If ${A}_{c}>{R}_{i}$ , accept the call and map $P{L}_{i}$ and $B{L}_{i}$ into the corresponding light path in $G$ .

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\left(V\right)$ , $O\left(1\right)$ , $O[(\mid L\mid +{\mid N\mid}^{2})\times \mid W\mid ]$ , $O({\mid L\mid}^{2}+{\mid N\mid}^{2})$ , and $O\left({\mid L\mid}^{2}\mid W\mid \right)$ . The overall complexity of DLA is $O(\mathrm{max}\{{\mid N\mid}^{2},{\mid L\mid}^{2}\}\times \mid W\mid )$ .

## 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.8\sim 1$
. (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 ${10}^{6}$ 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.8\sim 1$ ). 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.

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.

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