1. Introduction

In wavelength-division-multiplexing (WDM) optical networks, a wavelength channel has a transmission rate greater than gigabits per second[1]. If the fiber links were to fail, many traffic streams would be dropped. Therefore, design protection must be considered for WDM optical networks.

1.1 Previous algorithms

Authors of several previous papers have proposed algorithms to protect single-link failure [1–3]. A protection algorithm, called the dedicated-path protection (DPP), is illustrated in Fig. 1(a). The DPP computes a working path wp_n and a link-disjoint backup path bp_n for each connection request n, and the reserved backup wavelengths along bp_n cannot be shared with other backup paths. Then the DPP has a lower resource utilization ratio (the definition of resource utilization ratio can be found in Subsection 3.2) than other protection algorithms [1].

Another protection algorithm, called shared-path protection (SPP), is illustrated in Fig. 1(b). The SPP computes a working path wp_n and a link-disjoint backup path bp_n for each connection request n, and the reserved backup wavelengths along bp_n can be shared with other backup paths if their corresponding working paths are link-disjoint paths with wp_n . Then the SPP has a higher resource utilization ratio than other protection algorithms [1–7].

 

Fig.1. Illustration of (a) DPP and (b) SPP.

Download Full Size | PDF

Since the number of users has significantly increased, the size of networks continues to increase. Many heterogeneous networks that interconnect lead to a more and more complicated structure of networks. The risk probability increases, and multilink failures must be considered for WDM optical networks [8, 9]. The previous algorithms of DPP and SPP provide complete protection from single-link failure. As multilink failures occur, Fig. 2 illustrates the survivable situations of DPP and SPP:

 

Fig. 2. Survivable situations in multilink failures for (a) SPP and (b) DPP.

Download Full Size | PDF

Unprotected situations: In Fig. 2, if fiber links n and t fail simultaneously, all the working paths, wp ₀, wp ₁, and wp ₂, cannot be protected.

Protected situations: Figure 2(a) shows that, if fiber links m and n fail simultaneously, working paths wp ₀, wp ₁, and wp ₂ can be protected, but wp ₃, wp ₄, and wp ₅ cannot be protected because λ₀, λ₁, and λ₃ have been used by the backup paths of wp ₀, wp ₁ and wp ₂. Figure 2(b) shows that all the working paths can be protected because there are enough reserved wavelengths on link t.

Obviously, the DPP has a higher protection ability (the definition of protection ability can be found in Subsection 3.2) and a lower resource utilization ratio than the SPP. To provide a greater degree of protection, we need to reserve more wavelengths. Then we can consider adjusting the reserved wavelengths to provide different protection for multilink failures.

1.2 Proposed algorithm

Here we present a new path protection algorithm, called resource sharing degree constraints (RSDCs), which can be used to adjust the reserved backup wavelengths. When computing the reserved wavelengths, if the RSD is larger than an upper bound value of k, we can increase the reserved wavelengths until the RSD is not larger than the value of k. From simulations it becomes obvious that the RSDCs has a higher degree of protection than the SPP and has a higher resource utilization ratio than the DPP. By configuring different k, we can determine the RSDCs as well as the appropriate trade-offs between the resource utilization ratio and the protection ability.

If we extend the link disjoint to a shared-risk link group (SRLG) disjoint [10], the RSDCs for protection from multilink failures can be extended to protect the multi-SRLG failures [11].

2. System model and problem statement

2.1 Network model

Define a network topology G(N, L, W) for a given WDM optical 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. The connection request arrives at the network dynamically, and there is only one connection request arrival at a time defined by r(s, d), where s, d∊N denote the source node and destination node. The requested bandwidth is a wavelength. Here we allow wavelength conversion. The least-expensive path algorithm, which is Dijkstra’s, applies to compute the routes. Before describing this algorithm, the following notations are introduced:

l, a bidirectional fiber link in G;

c_l , the basic cost of link l, is determined by many factors, such as physical length of the fiber link, installation cost of the fiber link;

c’ _l , the cost of link l, is determined by the current network’s state;

F_l , the number of free wavelengths on link l, and a_l +F_l =|W| should be satisfied;

W_l , the number of wavelengths already consumed by working paths on link l;

R_l , the number of reserved wavelengths on link l;

TR_l , the number of reserved wavelengths of temporary record on link l;

wp_n , the working path for connection request n;

bp_n , the backup path for wp_n ;

|S|, the number of elements in set S;

${\mathit{\text{WV}}}_l^n$ , a boolean variable that is defined as Eq. (1).

If a connection request n is protected by fiber link l, then ${\mathit{\text{WV}}}_l^n$ =1; otherwise, ${\mathit{\text{WV}}}_l^n$ =0.

where WV_l , the total number of connections protected by link l, is defined as follows:

2.2 Reserved backup wavelengths

For arbitrary link l we assume v_l =max ($v_l^e$ ) (∀e∊L, e≠l), where $v_l^e$ represents the number of working paths that traverse link e and are protected by link l (that is, the corresponding backup paths traverse link l). Let TP_l =v_l , and the RSD of link l is defined as follows:

We assume a parameter k [k∊[1, ∞)] if RSD(l)>k and then increase the value of TP_l until RSD(l)≤k. The illustration follows in Fig. 3, where we assume that links m, n, and f fail simultaneously. In Fig. 3(a), connections 0, 1, 2, and 3 can be protected as RSD(t)=k=1.5. In Fig. 3(b), all the connections can be protected as RSD(t)=k=1. In Fig. 3(c), connections 0 and 1 can be protected as RSD(t)=k=3. It is obvious that a bigger k means more reserved wavelengths and more connections will be protected; that is, higher protection capability.

 

Fig. 3. Illustration of reserved backup wavelengths with RSDCs when (a) RSD(t)=k=1.5, (b) RSD(t)=k=1, (c) RSD(t)=k=3.

Download Full Size | PDF

Contrasting Fig. 1 with Fig. 3, we can determine the RSDCs (k=1) is equivalent to the DPP and the RSDCs (k=3) is equivalent to the SPP. When k=1.5, the resource utilization ratio and the protection ability of the RSDCs are trade-offs between the DPP and the SPP.

2.3. Link-cost assignment

Assume that connection request n arrives at a given time. First, we adjust the link cost according to Eq. (4) and compute the least-expensive working path:

If a working path is found, we can adjust the link cost according to Eq. (5) and compute the link-disjoint and least-expensive backup path, where ε is a sufficiently small constant (the value of the ε should be 10^-2 or smaller) and U={k; k∊wp_n}. It is obvious from Eq. (5) that these links have enough reserved wavelengths, that is, have no less reserved backup capacity than Tp_l , and have less link cost. If the backup paths traverse these links, we need not reserve new wavelengths. Thus, the resource utilization ratio will be improved:

3. Proposed algorithm

3.1 Process and complexity of the resource sharing degree constraint

The process of the RSDCs is presented as follows:

Step 1: Wait for the arrival of a connection request. If a connection request arrives, go to Step 2; otherwise update the network’s state and return to Step 1.

Step 2: Adjust the link cost according to Eq. (4) and compute the working path. If a working path is found, go to Step 3. Otherwise, block the connection request, update the network’s state, and return to Step 1.

Step 3: According to the value of k and Eq. (3), compute the TP_l for each link l. Adjust the link cost according to Eq. (5) and compute the backup path. If a backup path is found, accept the connection request, update the network’s state, and return to Step 1. Otherwise, block the connection request, update the network’s state, and return to Step 1.

The complexity of RSDCs depends mostly on the running time of Dijkstra’s algorithm. The complexity of Dijkstra’s algorithm is O(|N|²). By analyzing the process, one can determine that the complexity of RSDCs is approximately O(2|N|²) for a connection request.

3.2 Performance of the algorithm

The resource utilization ratio (RUR) is calculated in Eq. (6). It is obvious that a smaller RUR means that we need to assign fewer wavelengths. It also means that there are fewer backup wavelengths in reserve on all the backup paths and a higher degree of reserved capacity sharing, that is, a higher RUR. A higher RUR leads to lower traffic blocking because more free wavelengths can be used in the following traffic routing:

The requests blocking ratio is the ratio of |R| to |V|, where R is the set of connection requests that is 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 blocking ratio can approximately reflect the effectiveness of the resource utilization, and a smaller blocking ratio means a higher resource utilization ratio.

The protection ability (PA) is the ratio of |D| to |H|, where D is the set of connections protected as failures occur and H is the set of connections that hold onto the network. It is obvious that a greater PA means that more connections are protected from failure, that is, a greater degree of PA.

4. Simulation results and analysis

We simulate a dynamic network environment with the assumption that the arrival of connection requests, according to an independent Poisson process with arrival rate β, and the connections that hold time are negative exponentially distributed 1/µ, so the network load is β/µ erlang (an erlang is 1 h of telephone traffice in 1 h of time). We assume that µ=1 and each requested bandwidth is a wavelength. If the connection fails, the network abandons it immediately, i.e., there are no queues. The test network is shown in Fig. 4, where nodes with wavelength conversion capacities (we assume an optical-electronic-optical conversion) are interconnected by bidirectional fiber links with a basic link cost of a constant (assume to be 10). The number of wavelengths per fiber is assumed to be five. The value of k is selected from [1, ∞). We compare the performances of the RSDCs with the DPP and the SPP [1–3]. All the simulation results are averaged by simulation of 10⁶ connection requests.

 

Fig. 4. National network topology of America.

Download Full Size | PDF

In Figs. 5 and 6, A→∞. Figure 5(a) shows that the RUR decreases and gradually becomes invariable as k increases under different network loads (i.e., 10–35 erlang). This means that the resource utilization ratio improves and gradually reaches its best performance. When k→∞, the resource utilization ratio is at its highest. Figure 5(b) shows that the blocking ratio decreases and gradually becomes invariable as k increases under different network loads. This means that the blocking ratio is gradually reduced and gradually reaches its best performance. When k→∞, the blocking ratio is at its lowest. The reason for this is that, when k is large, the resource utilization ratio is higher, and more free wavelengths can be used by new connection requests.

In Fig. 3 it is obvious that, when k=1, the reserved wavelengths cannot be shared, and the RSDCs is equivalent to the DPP with a higher RUR and blocking ratio; when k→∞, the reserved wavelengths can be shared by those backup paths whose working paths are link disjointed with each other, and the RSDCs is equivalent to the SPP that has a lower RUR and blocking ratio; when k is equal to a finite constant from [1, ∞), the reserved wavelengths can be partially shared, and the performance of the RSDCs can be trade-offs between the DPP and the SPP.

In Figs. 5(c) and 5(d) it is shown that, when k=1, the performances of the RUR and the blocking ratio are at their worst; when k→∞, the performances of the RUR and the blocking ratio are at their best; when k=1.5, 2, and 3, the RUR and the blocking ratio are trade-offs between the best and the worst.

 

Fig. 5. As different network loads (a) the RUR versus k and (b) the blocking ratio versus k. As different k, (c) the RUR versus network load and (d) the blocking ratio versus network load.

Download Full Size | PDF

From Fig. 6 we can see that, as the multilink failures occur, the performance of the PA is the best when k=1, it is the worst when k→∞, and it is a trade-off between the worst and the best when k=1.5, 2, and 3. The reason for this is that there are more reserved wavelengths when k=1, and more connections can switch the traffic to backup paths as failures occur, resulting in higher degree of PA. When k→∞, there are fewer reserved wavelengths that can be used by failed connections, and the PA is lower. When k is equal to a finite constant from [1, ∞), the reserved wavelengths are trade-offs between k=1 and k→∞, and then the PA is also a trade-off between the best and the worst.

 

Fig. 6. PA versus network load when (a) two random links fail, (b) three random links fail, (c) four random links fail.

Download Full Size | PDF

We can thus conclude that, by configuration of different k, the RSDCs has a lower RUR and blocking ratio than the DPP and has a higher PA than the SPP; that is, the RSDCs determines the appropriate trade-offs between the DPP and the SPP.

5. Conclusion

We have investigated the protection design for survivable WDM mesh networks and have proposed a new path protection algorithm, called resource sharing degree constraints (BSDCs). With respect to previous work, RSDCs, adds a valuable elasticity in resource assignment and is able to determine the appropriate trade-offs between the resource utilization ratio and the protection ability.