Availability analysis considering primary and backup sharing in wavelength-division multiplexed networks

Yonggang Li; Yaohui Jin; Lemin Li

doi:10.1117/1.2196435

1 May 2006 Availability analysis considering primary and backup sharing in wavelength-division multiplexed networks

Yonggang Li, Yaohui Jin, Lemin Li

Author Affiliations +

Optical Engineering, Vol. 45, Issue 5, 050505 (May 2006). https://doi.org/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.

1. Introduction

In the research of survivability in wavelength-division multiplexed (WDM) mesh networks, the growing importance of differentiated reliability (DiR)¹ is evident. Networks can provide multiple degrees of reliability by means of DiR. A service-level agreement (SLA)² 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² 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).³ Each functional element of WDM system is characterized by a known average a steady-state availability $A_{s} = MTBF ∕ (MTBF + MTTR)$ .³

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.⁵ 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⁸ 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 $A_{0} (e)$ denote the original availability of channel $e$ , which relates to $A_{s}$ as shown in Sec. 1.

Fig. 1

Routing the R-connections allowing primary-backup sharing.

There exist two primary light paths $L_{1} (1 f 7 g 4)$ and $L_{2} (3 h 8 i 5 e 6)$ , for which full backup light path $B_{1} (1 a 2 b 3 c 4)$ and partial backup light path $B_{2} (3 c 4 d 5)$ 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}$ $(1 a 2 b 3 c 4 d 5)$ , which comes from node 1 to node 5. While computing $A (L_{1})$ and $A (B_{2})$ , we needn’t consider the preempted probabilities of $L_{1}$ and $L_{2}$ . However, while computing $A (L_{3})$ , 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 (L_{3})$ should be larger than $R (L_{3})$ . We calculate $A (L_{3})$ as

Eq. 1

A (L_{3}) = A (a) ∙ A (b) ∙ A (c) ∙ A (d) .

B_{1}

covers the segment

S_{1} (1 f 7 g 4)

of

L_{1}

.

B_{2}

covers the segment

S_{2} (3 h 8 i 5)

of

L_{2}

.

2.

A (S_{1}) = A_{0} (f) ∙ A_{0} (g),

A (S_{2}) = A_{0} (h) ∙ A_{0} (i) .

When the failure occurs among links of

S_{1}

and

S_{2}

, the probability

P_{b 1}

or

P_{b 2}

that

L_{3}

may be preempted by

L_{1}

or

L_{2}

can be calculated as

3.

P_{b 1} = 1 - A (S_{1}),

P_{b 2} = 1 - A (S_{2}) .

The availability of every channel can be calculated as

4.

A (a) = A_{0} (a) ∙ (1 - P_{b 1}),

A (b) = A_{0} (b) ∙ (1 - P_{b 1}),

A (c) = A_{0} (c) ∙ (1 - P_{b 1}) ∙ (1 - P_{b 2}),

A (d) = A_{0} (d) ∙ (1 - P_{b 2}) .

We can get the availability

A (L_{3})

of the primary light path

L_{3}

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: $P L$ is the set of primary light paths; $B L$ 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 $L G (V, E)$ is the layered-graph model, where each node $i ∊ N$ in $G$ is replicated $∣ W ∣$ times in $L G$ , the set of nodes in $L G$ is $V$ , and the set of edges in $L G$ is $E$ .

3.2.

Solution Approach

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

Eq. 5

cost (e) = delay - const ∙ \log [A (e)] [(e ∊ E)] .

A (e)

is given as follows:

Eq. 6

A (e) = {\begin{cases} 0 & if e ∊ P L \\ A_{0} (e) ∙ \prod_{i = 1}^{∣ H_{e} ∣} A_{0} (h_{i}) & if (e ∊ B L) \land (h_{i} ∊ H_{e}) \land (M - 1) \\ A_{0} (e) & if (e ∊ B L) \land (M = 0) \end{cases} .

The composite availability comprising of the primary and backup light path is calculated as follows:

7.

A_{c} = A (p) ∙ {A (r) + A (q) ∙ [1 - A (r)]} ∕ A (r)

[(p ∊ P L_{i}) \land (q ∊ B L_{i}) \land (r ∊ S_{i})] .

A formal description of the algorithms is given below:

Step 1: Map a network topology $G (N, L, W)$ into the corresponding layered graph $L G (V, E)$ . Let $M$ equal 1 and set the cost of edge in $L G$ 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 $L G$ on the available panel $k$ . If $A (P L_{i}) > 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 (V)$ , $O (1)$ , $O [(∣ L ∣ + {∣ N ∣}^{2}) \times ∣ W ∣]$ , $O ({∣ L ∣}^{2} + {∣ N ∣}^{2})$ , and $O ({∣ L ∣}^{2} ∣ W ∣)$ . The overall complexity of DLA is $O (\max {{∣ N ∣}^{2}, {∣ L ∣}^{2}} \times ∣ 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.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.

Fig. 2

Successful routes ratio performances.

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.

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,” 2887 –2891 (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., 22 (11), 2536 –2547 (2004). 0733-8724 Google Scholar

3.

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

4.

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

5.

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

6.

G. Mohan, C. SivaRam, and K. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., 9 553 –565 (2001). 1063-6692 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,” 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., 18 (10), 2130 –2137 (2000). https://doi.org/10.1109/49.887932 0733-8716 Google Scholar

Citation Download Citation

Yonggang Li, Yaohui Jin, and 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

Published: 1 May 2006

Access the abstract

JOURNAL ARTICLE
3 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

CITATIONS

Cited by 1 scholarly publication.

Explore citations on Lens.org

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Reliability

Multiplexing

Simulation of CCA and DLA aggregates

Failure analysis

Optical engineering

Lithium

Wavelength division multiplexing

1.

Introduction

2.

Problem Definition

Fig. 1

Eq. 1

2.

3.

4.

3.

Implementation

3.1.

Definitions

3.2.

Solution Approach

Eq. 5

Eq. 6

7.

4.

Performance Evaluation

Fig. 2

Fig. 3

5.

Conclusion

Acknowledgment

References

Show All Keywords

Keywords/Phrases

Search In:

Publication Years