1. Introduction

The technology of wavelength-division-multiplexing optical networks has become the foundation of many large networks. A wavelength channel has a transmission rate greater than gigabits per second. If the fiber links fail, many connection streams will be dropped. Protection designs are important in wavelength-division multiplexing networks. The conventional protection schemes include dedicated protection, shared-link protection, shared-path protection [1], and shared subpath protection [2]. Because shared protection has better resource utilization ratios than dedicated protection, most of the existing literature on protection schemes is focused on shared protection design.

1.1 Shared-risk link group constraints

The conventional protection schemes [1–4] assume that links will independently and that the primary and the backup paths will not fail simultaneously for any connection request, provided that the primary and the backup paths do not traverse the same fiber link. But some links in actual networks have correlated failures, as follows:

The fiber cable topology considered is shown in Fig. 1(a), and the corresponding fiber link topology is shown in Fig. 1(b). Although the fiber links 1–2 and 1–3 are shown in Fig. 1(b) to be independent, they traverse common fiber cable 1–4 in Fig. 1(a). The breakdown of fiber cable 1–4 can possibly lead to the simultaneous failure of fiber links 1–2 and 1–3.

 

Fig. 1. (a) Fiber cable (1–4) topology, (b) fiber link topology, (c) fiber cable (1–2 and 4–3) topology, (d) conduit topology.

Download Full Size | PDF

Even though the fiber links traverse independent fiber cables, it is also possible for these links to fail simultaneously. Another fiber cable topology is shown in Fig. 1(c), and the corresponding conduit topology is shown in Fig. 1(d). Though fiber cables 1–2 and 4–3 are shown in Fig. 1(c) to be independent, they traverse the common conduit in Fig. 1(d). The breakdown of the conduit can possibly lead to simultaneous failure of fiber cables 1–2 and 4–3. Then the fiber links that traverse fiber cables 1–2 and 4–3 will also have correlated failures.

In Ref. 5 the term “shared-risk link group” (SRLG) denotes a correlated failure, for which the link group shares common physical resources (that is, shares common components that can fail), such as fiber cables and conduits. The SRLG can be determined from routing information on physical links and also can be distributed by network managers. Each SRLG has a unique identifier. In computing paths, we distributed different SRLG identifiers for the links before we computed that paths so that the different degrees of disjunction between the primary and the backup paths could be satisfied. If each connection request has a primary path and a corresponding SRLG-disjoint backup path, then single SRLG breakdown would be completely tolerated.

1.2 Previous work

In computing primary or backup paths, one should design the routing-selection algorithm carefully. A sound algorithm should optimize resource utilization and protection-switching time. A higher resource utilization ratio means a lower blocking ratio, and a smaller protection switching time means faster recovery from failure.

The scheme described in Refs. 6 and 7 first computes a shortest primary path for each connection request and then deletes all links that are traversed by the primary path and computes the shortest backup path on the spare network topology. It is obvious that the primary and the corresponding backup paths are not SRLG disjointed but only link disjointed. Because adjusting the link cost dynamically according to the current state of the network is not considered, the paths are not the least costly but only the shortest. Thus the resource utilization is not optimal.

An algorithm given in Ref. 2 adjusts the link cost dynamically according to the current state of the network before computing primary or backup paths, so that the paths are least costly. But it does not consider the SRLG constraints, and the primary paths and the corresponding backup paths are only link disjointed. Though the primary and backup paths are the least costly, the pair of primary and backup paths may not be. In Section 4 below, we shall see that joint routing (JR) has better performance than separated routing (SR) [2].

Extending the concept that was described in Refs. 8 and 9, we propose an algorithm with SRLG constraints that we call the loopless K shortest path (LPSP). The LPSP algorithm first computes K pairs of primary and SRLG-disjoint backup paths and then selects the minimal-cost pair of paths from among the K pairs. But LPSP is only a path-selection algorithm because it does not consider resource assignment, and the link cost is always the basic cost of the link, which is a constant determined by many factors, such as physical length of the fiber link and installation cost of the fiber link. In fact, the link cost will change with the state of the network [2], including availability of spare resources. Thus the link cost cited in Ref. 9 is not reasonable.

The primary and corresponding backup paths described in Refs. 1 and 9 are completely link disjoint or SRLG disjoint, and this concept is equivalent to 100% reliable protection but does not include differentiated reliability (DiR) [10–12]. Integrating SRLG constraints and DiR [13], we propose a partial SRLG-disjoint shared-path protection (PSD-SPP) algorithm, which can efficiently satisfy the specific differentiated requirements of users. But the partial SRLG-disjoint shared-path protection algorithm uses SR, and therefore the performance, including the resource utilization ratio, is not optimal.

1.3 Our proposal

Previous research has not resolved optimal routing selection with DiR under SRLG constraints, and it considered not the integrative performances of the resource utilization ratio (or blocking ratio) and the protection-switching time but only the resource utilization ratio. The protection-switching time is an important performance target and cannot be ignored. Assuming only single SRLG breakdown in the network, a novel algorithm, called the joint routing-selection algorithm with DiR (JRSA-DiR), is proposed. The JRSA-DiR considers the joint performance of the resource utilization ratio and the protection-switching time. We can see in the simulation results of Section 4 below that the JRSA-DiR not only produces nearly optimal performance but also can make the appropriate trade-offs between the resource utilization ratio (or blocking ratio) and the protection-switching time.

The rest of this paper is organized as follows: In Section 2 we elaborate on our network model, shared-path protection with DiR, protection-switching time, and link-cost assignment. Based on SRLG constraints with DiR, we describe the JRSA-DiR algorithm in detail in Section 3. Simulation results and analysis are presented in Section 4. In Section 5 we describe our conclusions.

2. System model and problem statement

2.1 Network model

We define a network topology G(N,L,W) for a given WDM mesh network, where N is the set of nodes, L is the set of bidirectional links, and W is the set of available wavelengths per fiber link. |N|, |L|, and |W| denote the node number, the link number, and the wavelength number, respectively. Each link l∈L has been assigned a SRLG identifier. A connection request arrives at the network dynamically, and only one connection request arrives at a time, defined by a triple r(s, d, b), where s, d∈N denote the source node and the destination node, respectively, and b specifies the bandwidth requirement of the request. One uses a minimum-cost path algorithm, which is called the Dijkstra algorithm, to compute a route. Before describing this algorithm, we introduce the following notation:

▪ L, a bidirectional fiber link in G. The link’s capacity is C.

▪ c_l, the basic cost of link l. It is determined by many factors, such as physical length of the fiber link and the cost of installation of the fiber link.

▪ c_l,, the cost of link l. It is determined by the current state of the network.

▪ s_l, the SRLG identifier for link l.

▪ a_l, the total bandwidths already consumed on link l.

▪ r_l, the total residual bandwidths on link l; a_l+r_l=C should be satisfied.

▪ w_l, the total bandwidths already consumed by primary paths of connections on link l.

▪ p_l, the reserved bandwidths on link l; p_l+w_l=a_l should be satisfied.

▪ t_pl, the reserved bandwidths of temporary record on link l.

▪ w_pn, the primary path for connection request n, where n is the connection request identifier that can be distributed by arriving orders for a connection request.

▪ B_p, the backup path for wp_n.

▪ C_b, the total cost of all links on the backup path.

▪ List (l), the set of connection request identifiers that affect p_l.

▪ P(l), the reliability of link l.

▪ CP(_sl)=P(f_failure|l_failure), the correlated probability of failure for SRLG s_l. This means that the probability that link f(_sf=_sl) will fail under these conditions fails.

▪ RD, the required reliability of users.

▪ |S|, the number of elements in set S.

2.2 Shared-path protection with DiR

Other kinds of DiR were suggested in Refs. 10–12. In what follows, we present the novel idea of considering only a single SRLG breakdown [13].

For each connection request n, the reliability of wp_n is

The probability that wp_n will fail is

The probability that wp_n and bp_n will fail simultaneously is

where P(bp_nfailure | wp_nfailure) is the probability that backup path bp_n will fail on the condition that primary path wp_n fails. These common SRLG identifiers, which are included by the primary and backup paths, compose the set CS; then

Then the reliability of wp_n and bp_n is

For each connection request n, if the following inequality has been satisfied, then the backup path bpn does not need to be assigned:

Otherwise, backup path bpn needs to be assigned. For each s_l(l ∈ wp_n), if inequality (7) below has been satisfied then sl does not need to be protected; that is, the corresponding backup path that can traverse these links has the common SRLG sl. Otherwise, sl needs to be protected; that is, the corresponding backup path that cannot traverse these links has the common SRLG sl. These SRLG identifiers that need to be protected compose set U:

For shared-path protection with DiR, the common resources, which are in the links that have been shared by some backup paths, cannot be shared if their corresponding primary paths traverse the same links or include the common SRLG identifiers in U; then new resources should be assigned.

2.3 Protection-switching time

The protection-switching time is defined as the time between the failure of the primary path and the time that the corresponding backup path begins to work [1]. The following notation is introduced:

▪ D, the message processing time at a node is 10 µs, corresponding to 1-GHz CPU time.

▪ P, the propagation delay on the link, is 400 µs, corresponding to a link length of 80 km.

▪ X, the time to configure, test, and set up an OXC (Optical Cross-Connect) is 10 µs.

▪ F, the time to detect the links failures, is 10 µs.

▪

If the primary path of connection request k traverses failed link l, the number of hops from source l to the source node is n, and the number of hops of the backup path is m. Now we illustrate the steps in the protection-switching procedure for shared-path protection.

 

Fig. 2. Protection-switching time illustrated for shared-path protection.

Download Full Size | PDF

When link l fails, the end nodes of l that are the link source and the link destination send failure messages to the source node and the destination node, respectively. Then the source node sends a setup message to the destination node along backup path and configures the OXCs at each intermediate node along backup path because, in shared protection, at the time of the connection setup, wavelengths are reserved for the backup path but OXCs are not configured. After receiving the setup message, the destination node sends a confirmation message back to the source node along the backup path, thus completing the switching procedure. Then the protection-switching time t_k is calculated as

It is obvious that shorter lengths of primary and backup paths mean smaller n and m, and this leads to smaller t_k and faster recovery after failures.

2.4 Link-cost assignment

Assume that connection request n arrives at a given time. First we compute the shortest primary path because a short primary path means that fewer new resources need to be assigned. If the backup path needs to be assigned, then we find all the SRLG identifiers that need to be protected and compose set U according to inequality (7). For each link l(l∈L), if s_k(k∈wp_n) in U has been included by the arbitrary wp_m[m∈List (l)] or wp_n has traversed the same links with the arbitrary wp_m, then we let tp_l=p_l+b. Otherwise, we let tp_l=p_l. Link-cost function c’l is calculated as follows, where ε is a constant (in simulations, we take ε sufficiently small):

We can see from Eq. (9) that these links, which have no less reserved capacity than tp_l, have less link cost. If the backup paths traverse these links, then we need not reserve new resources. Thus the resource utilization ratio will be improved.

3. Proposed algorithm

3.1 Policy of routing selection

Our proposed method for enumerating paths in K loopless paths is to explore the search space of primary and backup paths as much as possible to compute primary and backup paths near optimal path cost [7,8]. Extending this concept, we should consider the resource utilization ratio and the protection-switching time when we select routings and should let the joint cost of the resource utilization ratio and the protection-switching time be near optimal.

First, we compute the shortest primary path wp_n for connection request n, and those links that have been traversed by primary path wp_n should be SRLG disjoint. If backup path bp_n needs to be assigned, then according to inequality (7) we find all the SRLG identifiers that need to be protected and adjust the link cost according to Eq. (9). Then we compute a partial SRLG-disjoint backup path bp_n. A_n should be calculated by Eq. (10) below, where α is a proportion constant and should be selected in [0, +∞) and H_n is the total number of hops of primary and backup paths. Thus, we find a pair of paths that is Pair_m(wp_n,bp_n,A_n)(1≤m≤K).

After finishing K distinct candidate pairs of paths (if we cannot find K candidate pairs of paths, we should find all potential pairs of paths), we select a pair of paths that has the minimal A_n:

It is shown in Eq. (10) that A_n is the joint cost of resource utilization and the total length of primary and backup paths. The bigger α is, the bigger the proportion of H_n in A_n is, and the value of An depends mostly on Hn. Thus a minimal value of An means a minimal total length of primary and backup paths. According to Eq. (8), a smaller total length of primary and backup paths means a shorter protection-switching time, and then a minimal H_n will mean an optimal protection-switching time. As α becomes smaller, the proportion of ${\displaystyle \sum _{l\in L}{a}_l}$ in A_n becomes greater, and the value of A_n depends mostly on ${\displaystyle \sum _{l\in L}{a}_l}$. Then, the minimal ${\displaystyle \sum _{l\in L}{a}_l}$ will mean a minimal assignment of resources, namely, an optimal resource utilization.

According to the above analysis, different values of α can achieve different resource utilization and protection-switching times. In Section 4 below, we illustrate these results by means of simulations.

3.2 JRSA-DiR process and complexity

▪ Step 1: Wait for arrival of a connection request. If a connection request arrives, then record the network state as S at this time and go to step 2. Otherwise, check all the connections that are holding on the network and update the primary and backup paths, reserved resources, and List (l) for all links. Go back to step 1.

▪ Step 2: If there are K distinct pairs of paths, go to step 4. Otherwise, restore network state S, delete link l(r_l<b), and compute a shortest primary path wp_n on the spare network topology. If successful, go to step 3. Otherwise go to step 4.

▪ Step 3: If the backup path does not need to be assigned, go back to step 2. Otherwise, restore all links that were deleted in step 2. Delete the links that have been traversed by the primary path and adjust the link cost according to Eq. (9). Then compute partial SRLG-disjoint minimum-cost backup path bp_n; then 0<C_b<+∞ should be satisfied. If this value is not found, then go to step 2. Otherwise, compute A_n according to Eq. (10) and compose a pair of paths Pair_m(wp_n, bp_n, A_n)(1≤m≤K). Go back to step 2.

▪ Step 4: If Pair_m(wp_n,bp_n,A_n)(1≤m≤K) is not empty, select a pair of paths that has the minimal An. Update List (l) for each link l of bpn; if tp1>pl, then add the connection request identifier n into List (l). Memorize the primary and backup paths found here and reserve the resources while updating the temporary records. Go back to step 1. If Pair_m(wp_n, bp_n, A_n)(1≤m≤K) is empty, then go to step 5.

▪ Step 5: Abandon the connection request, check all the connections that are holding on the network, and update the primary and backup paths, reserved resources, and List (l) for each link l. Go back to step 1.

▪

The complexity of the JRSA-DiR depends mostly on the running times of Dijkstra algorithm. The complexity of the Dijkstra algorithm is O(|N|²). Analyzing the process yields a complexity of the JRSA-DiR of approximately O(2K|N|²) for a connection request. It is obvious that a larger value of K means a higher complexity of the JRSA-DiR.

3.3 Performance of the algorithm

The resource utilization per connection (RUPC) is calculated in Eq. (11) below, where E is the set of connections that are holding on the network. It is obviously that a smaller value of RUPC means that we need to assign fewer resources and also means a smaller backup bandwidth reserve on all the backup paths and a higher degree of spare capacity sharing, that is, a higher resource utilization ratio. Higher resource utilization leads to lower traffic blocking because more spare resources can be used in the following traffic routing.

The blocking ratio (BR) is the ratio of |R| to |V|, where R is the set of connection requests that are being abandoned by the network and V is the set of all connection requests that have arrived at the network. In the case of dynamic traffic, the BR can approximately reflect the effectiveness of resource utilization, and a smaller BR means a higher resource utilization ratio.

The protection-switching time (PST) is calculated in Eq. (12) below, where M is the set of connection requests and their primary paths traverse the failed links. A smaller PST means faster recovery after failures:

4. Simulation results and analysis

4.1 Simulation model

We simulate a dynamic network environment with the assumptions that connection requests arrive according to an independent Poisson process with arrival rate β and that the connections’ holding times are negatively exponentially distributed, 1/µ. We assume that µ=1 and that each request bandwidth is always a wavelength. If the connection fails to be established, the network abandons it immediately; i.e., there are no waiting queues. The test network is shown in Fig. 3, where nodes, which have wavelength conversion capacities (we assume Optical-Electric-Optical conversion), are interconnected by bidirectional fiber links that are all assumed to be 80 km long; the basic link cost is 30. The number of wavelengths per fiber is assumed to be three. Each link has a SRLG identifier that is a random number that was distributed and is shown underlined in Fig. 3.

In the simulations we take a sufficiently large K (K >100) and a sufficiently small ε(ε<1). According to Ref. 13, the reliable probability that each link is randomly distributed is 0.95-1, and the correlated probability of failure of each SRLG is randomly selected (10%, 20%, or 30%). All simulation results are averaged by simulation of 10⁶ connection requests.

 

Fig. 3. USA (the United States of America) network topology.

Download Full Size | PDF

4.2 Performance with different values of α

Assuming that RD=100%, we investigate the performances of a resource utilization ratio, a blocking ratio, and a protection-switching time with different values of α.

 

Fig. 4. (a) RUPC versus α, (b) BR versus α, (c) PST [ms] versus α.

Download Full Size | PDF

It is shown in Fig. 4(a) that the RUPC increases and gradually becomes invariable as α increases, and this means that the resource utilization ratio is reduced and gradually reaches its worst performance. When α=0, the resource utilization ratio is optimal.

We can see from Fig. 4(b) that the BR increases and gradually becomes invariable as α increases, and this means that the blocking ratio is gradually enhanced and gradually reaches its worst performance. When α=0, the blocking ratio is optimal. The reason for this is that when α is bigger, the resource utilization ratio is lower, and then fewer spare resources can be used by the following connection requests; and this causes more connection requests to be blocked.

From Fig. 4(c) it is obvious that the PST is reduced and gradually becomes invariable as α increases, and this means that the protection-switching time is reduced and gradually reaches its optimal performance. When α=0, the protection switching time is the worst.

According to Eq. (10), it is obvious that ${\displaystyle \underset{\alpha \to \infty }{lim}}{A}_n=\alpha H_n$; the JRSA-DiR selects the pair of paths with the minimal total length of primary and backup paths. Then n and m are smaller in Eq. (8), and this yields a protection-switching time that is optimal. And we can find that ${\displaystyle \underset{\alpha \to \infty }{lim}}{A}_n={\displaystyle \sum _{l\in L}}{a}_l$; the JRSA-DiR selects the pair of paths with the minimal resource assignment, and this leads to a resource utilization ratio that is optimal; that is, the blocking ratio is optimal in dynamic traffic. If α is a finite constant in (0, +∞), then the JRSA-DiR selects the pair of paths with the minimal joint cost. Thus it can make the trade-offs between the resource utilization ratio (or blocking ratio) and the protection-switching time.

It is shown from the above analysis that the performances of resource utilization ratio (or blocking ratio) and the protection-switching time restrict each other. Because the resource utilization ratio is higher, the backup paths do their best to traverse those links that have had enough reserve capacity and need not assign new resources, and this causes the backup paths that have fewer links to be used and the lengths of backup paths to increase. Then m will increase in Eq. (8) and the PST will become large. A smaller PST, however, will lead to a lower resource utilization ratio.

 

Fig. 5. (a) RUPC versus network load, (b) BR versus network load, (c) PST [ms] versus network load.

Download Full Size | PDF

In Fig. 5, A is a sufficiently large constant. It is shown that, when α=0, the performances of the RUPC and the BR are optimal, whereas that of the PST is the worst. When α=A, the performance of the PST is optimal and those of the RUPC and the BR are the worst. When α=1, the performances of the RUPC, the BR, and the PST are trade-offs between optimal and worst.

4.3 Comparison of joint routing with separated routing

In Section 1 we pointed out that JR performs better than SR. In what follows, we simulate and analyze their comparison.

When K=1, the JRSA-DiR computes the pair of paths for which the primary and corresponding backup paths are optimal. Under these conditions, this algorithm is equivalent to SR [2,13]. From Fig. 5 we can see that the performance of the RUPC, the BR, and the PST for JR (when K>100) is better than for SR (when K=1). Analyzing SR and JR, we introduce two problems, as follows:

(1) Though wp_m and wp_n have the same minimal cost, the corresponding bp_m and bp_n maybe have different costs. Assume that A_m>A_n. If the SR first selects minimal-cost primary path wp_m, then the corresponding backup path is bp_m, but then A_m is not the minimal cost. If we use JR, minimal cost A_n can be found. Then JR can be closer to optimal than can SR.

(2) Though wp_m has a smaller cost than wp_n, the corresponding bp_m maybe have a bigger cost than bp_n. Assume that A_m>A_n. If SR first selects minimal-cost primary path wp_m, then the corresponding backup path is b_p, but A_m is not the minimal cost. If we use JR, minimal cost A_n can be found.

From the above analysis, one can see that JR can always find the optimal pair of primary and backup paths, whereas SR cannot. Thus JR can have closer to optimal performance than can SR. But JR has higher complexity than SR because JR needs a large value of K.

4.4 Performance with differentiated reliable RD

According to Ref. 13, we assume three different levels of reliability, i.e., P1–P3. P1 has the highest level of reliability; that is, it provides 100% protection. P2 has a lower level; that is, it provides 98% protection. P3 provides only 96% protection. To obtain nearly optimal RUPC, BR, and PST, we assume that α=0 in Figs. 6(a) and 6(b) and that α=A in Fig. 6(c). For simulation, K should be sufficiently large (K>100).

It is shown in Fig. 6 that, with a different network load, if the reliability is higher then RUPC, the BR, and the PST will all be larger, and this means a lower resource utilization ratio, a higher blocking ratio, and a longer protection-switching time. If the reliability is higher, according to inequality (7) more SRLGs will need to be protected, and then backup paths will have fewer links to be selected and have lower probability of sharing reserved resources with other backup paths, and this will lead to a lower degree of capacity sharing. A lower resource utilization ratio means that connection requests can use fewer spare resources, and then more connection requests will be blocked, resulting in a higher blocking ratio. If more SRLGs need to be protected, then the lengths of the backup paths will increase, namely, m in Eq. (8) would increase, and then the PST will become large.

 

Fig. 6. (a) RUPC versus network load, (b) BR versus network load, (c) PST [ms] versus network load.

Download Full Size | PDF

For Figs. 7(a) and 7(b) we assume two levels of reliability, 96% and 98%, respectively. In simulating connection requests1000 times, we found that all actual amounts of requests for reliability that were demanded by these connection requests were satisfied.

 

Fig. 7. Actual reliability versus number of connection requests when (a) RD=96% and (b) RD=98%.

Download Full Size | PDF

5. Conclusions

In wavelength-division-multiplexing survivable networks, routing-selection algorithms should be studied because an effective algorithm can improve the resource utilization ratio, reduce the blocking ratio, and shorten the protection-switching time. Our proposal extends the K-shortest-paths idea and suggests a novel joint routing-selection algorithm with differentiated reliability (JRSA-DiR) under shared-risk link group constraints. The JRSA-DiR algorithm considers the joint performance of the resource utilization ratio (or blocking ratio) and the protection-switching time. It not only can efficiently satisfy the specific requirements of users but also can make the necessary trade-offs between the resource utilization ratio (or blocking ratio) and the protection-switching time.