Open Access
Add to BibSonomyAbstract
In this study we propose a new heuristic approach called the hybrid survivable configuration (HSC) to provide differentiated service for optical wavelength-division-multiplexing (WDM) networks subject to double-link failures. Compared with previous approaches, HSC not only can obtain higher survivability but also can save significant resources. The simulation results are shown to be promising.
©2007 Optical Society of America
Corrections
Lei Guo, "Hybrid survivable configuration for optical wavelength-division-multiplexing mesh networks: erratum," Opt. Express 17, 803-803 (2009)https://opg.optica.org/oe/abstract.cfm?uri=oe-17-2-803
1. Introduction
Survivability in optical WDM mesh networks is an important issue that has been studied over the past decade, since network failures lead to a great deal of blocked traffic [1]. Most previous research involved studying the single-link failure [1–4] that is dominant in optical WDM networks. As the size and complexity of optical networks continue to grow, the probability of multiple failures becomes high; therefore, the survivability of double-link failures has been considered and studied in recent work [5–8].
To survive double-link failures, several studies [6–8] propose some efficient approaches, i.e., shared-path protection (SPP), shared-segment protection (SSP), and shared-link protection (SLP). Of these, SPP has the best resource utilization. In SPP, each connection request is assigned to one primary path and two link-disjoint backup paths so that SPP can provide complete protection for double-link failures. However, backup resources in SPP are about three times that of primary resources, which is not acceptable to many general users.
Because of the expense involved, these general users may not require the service of complete protection for double-link failures.
Therefore, we propose a new two-level survivability model: Level 1, in which the connection requests need complete protection for double-link failures; and Level 2, in which the connection requests need complete protection for single-link failures but do not need complete protection for double-link failures. Based on this concept, we propose a new heuristic approach called HSC to provide differentiated service for Level 1 and Level 2. For connection requests for Level 1, HSC will assign one primary path and two link-disjoint backup paths. For connection requests for Level 2, HSC will assign one primary path and one link-disjoint backup path. If connection requests with Level 2 cannot be protected for current double-link failures, HSC will compute a new segment-primary path to reroute the primary traffic. It is obvious that in comparing HSC with the SPP approach, HSC can reduce the backup path assignment, save backup resources, and obtain more efficient resource utilization than SPP.
2. Survivability for double-link failures
2.1 Network model
Assume that the given optical network has V nodes and L fiber links and that each fiber link contains W wavelengths. Assume that each connection request arrives at the network in an orderly fashion and that there is only one connection request arriving at a time. Assume that the required bandwidth of each connection request is one wavelength channel. The shortest path algorithm, i.e., Dijkstra’s algorithm, is applied to compute the routes. The following notations are introduced.
2.2 Survivability in SPP and HSC
In SPP, each connection request is assigned to one primary and two link-disjoint backup paths. In Fig. 1(b), for connection request from source node A to destination node E, the primary path and backup paths are A-B-C-D-E, A-F-G-H-E, and A-I-J-K-E, respectively. In the worst case, if links C-D and G-H both fail, the primary traffic can be switched to the second backup path A-I-J-K-E. It is obvious that SPP can provide complete protection for the double-link failures.
In HSC, if the connection request from shared node A to destination node E is Level 1, the routing assignment is the same as with SPP. If the connection request is Level 2, it will be assigned to one primary path A-B-C-D-E and one link-disjoint backup path A-F-G-H-E. In the worst case, if links C-D and G-H fail, both the primary path and the backup path are unavailable. Then, HSC will recompute a new segment-primary path from node C to destination node E. If the segment-primary path C-K-E can be found, the primary traffic can be rerouted to the new primary path A-B-C-K-E. It is obvious that the connection request cannot be protected if the segment-primary path C-K-E is unavailable due to some constraints (e.g., lack of wavelength resources).
Compared with SPP, although HSC cannot provide complete protection for Level 2, it can save more backup resources since the backup paths in Level 2 can be reduced and the primary traffic can be dynamically rerouted to the new segment-primary paths according to the current network state. In Section 4 we can see that the survivability of HSC is very close to that of SPP, while it can save significantly more resources than SPP.
Fig. 1. Illustrations for survivability in SPP and HSC: (a) network topology; (b) routing in SPP; (c) rerouting in HSC.
3. Heuristic process
The process of HSC can be presented as follows:
Input: a new connection request crn with Level 1 or Level 2.
Output: a solution of (pn,b 1 n,b 2 n) with Level 1 or (pn,bn) with Level 2; or NULL if no solution is available.
Step 1: Adjust the costs of all links according to (1) and compute the least-cost primary path pn. If pn can be found, go to step 2; otherwise, block this connection request and return NULL.
Step 2: Adjust the costs of all links according to (2) and compute the least-cost backup path. If the backup path can be found, go to step 3; otherwise, block this connection request and return NULL.
Step 3: If Level=1, record the backup path obtained in step 2 as b n 1 and go to step 4; otherwise, record the backup path obtained in step 2 as bn, let pwj ← pwj + 1(∀j∈pn)bWj ← max{v * j,bwj}(∀j∈bn), fwj ← W - pwj - bWj(∀j∈L) and return (pn,bn).
Step 4: Adjust the costs of all links according to (3) and compute the least-cost backup path b 2 n. If b 2 n can be found, let pWj ← pWj + 1(∀j∈pn), bWj ← max{v * j, bwj}(∀j∈b 1 n,b 2 n), fwj ← W - pWj - bWj(∀j∈L) and return (pn,b 1 n,b 2 n); otherwise, block this connection request and return NULL.
In (1), the links that have more free resources (i.e.,fwj) will have a smaller link-cost, and then the primary paths will be favorable for traversing these links and the consumed resources can be more uniformly distributed to all links. Therefore, the load may be more balanced.
In (2) and (3), v * j is the backup resource reserved on link j for computing the backup paths, and it can be written as
We can see that the links that already have assigned more backup resources (i.e., bwj) have a smaller link-cost. The backup paths will be favorable for traversing these links, and fewer new backup resources need to be assigned. Therefore, the resource utilization ratio can be improved.
The time complexity of HSC mainly depends on the time of running Dijkstra’s algorithm. It is obvious that in the worst case, HSC will run three iterations of Dijkstra’s algorithm so that the time complexity of HSC is approximately 0(3V2).
4. Simulations and analysis
In simulations, we assume that the required bandwidth of each connection is one wavelength channel. The survivable level of each connection request is randomly selected from {Level 1, Level 2}. If the connection request fails to be established, the network abandons it immediately. We tested three networks: US, ARPNET, and ITALY, which are shown in Fig. 2. The number of wavelengths per fiber link is assumed to be 128. Each node is assumed to have wavelength conversion capacity. We compare HSC with SPP in two performances: (1) resource consumed (RC), that is, the ratio of total backup resources over total primary resources; (2) survivability (SA), that is, the ratio of the total number of protected connections over the total number of connections affected by the failures. A smaller RC means a better resource utilization ratio, and a bigger SA means higher survivable ability.
In Fig. 3(a), we can see that compared with SPP, HSC can save significant resources, and the improvement ratio is up to 70%. The reason for this is that SPP always assigns two backup paths to each connection for providing complete protection for the double-link failures, while HSC can provide differentiated service based on the survivable level. In Level 1, HSC assigns two backup paths to each connection to completely protect against double-link failures. In Level 2, HSC only assigns one backup path to each connection to protect against a single-link failure, while it can use the rerouting technique to survive the double-link failure. Therefore, HSC has a better resource utilization ratio than SPP.
In Fig. 3(b), we simulate the double-link failures randomly. It is obvious that SPP can provide 100% survivability since each connection request has been assigned to two backup paths. We can also see that the survivability of HSC is up to 93%, which is very close to that of SPP. The reason for this is that, although HSC cannot provide 100% protection for the connection requests with Level 2 in the double-link failures, it can use the rerouting technique to improve survivability. Therefore, HSC also can achieve high survivability in double-link failures. Since the improvement of resource utilization for HSC to SPP is up to 70%, the bit difference of about 7% for survivability between HSC and SPP is noteworthy.
5. Conclusion
This study has proposed a new heuristic approach called HSC to provide differentiated service for the double-link failures in optical WDM networks. Theoretical analysis and simulation results show that, compared with SPP, HSC not only has very close survivability to that of SPP but also can save significant resources.
Acknowledgments
The authors thank the reviewers for their valuable comments.
References and links
1. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol. 21,870–883 (2003). [CrossRef]
2. R. He, H. Wen, L. Li, and G. Wang, “Shared sub-path protection algorithm in traffic-grooming WDM mesh networks,” Photon. Network Commun. 8,239–249 (2004). [CrossRef]
3. C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee , “New and improved approaches for shared-path protection in WDM mesh networks,” J. Lightwave Technol. 22,1223–1232 (2004). [CrossRef]
4. H. Wen, L. Li, R. He, H. Yu, S. Wang, and N. Song, “Dynamic grooming algorithms for survivable WDM mesh networks,” Photonic Network Commun. 7,253–263 (2003). [CrossRef]
5. D. Schupke and R. Prinz, “Capacity efficiency and restorability of path protection and rerouting in WDM networks subject to dual failures,” Photon. Network Commun. 8,191–207 (2004). [CrossRef]
6. W. He, M. Sridharan, and A. Somani, “Capacity optimization for surviving double-link failures in mesh-restorable optical networks,” Photon. Network Commun. 9,99–111 (2005). [CrossRef]
7. L. Guo, H. Yu, and L. Li. “Dynamic survivable algorithm for meshed WDM optical networks,” J. Network Comput. Appl. 30,328–338 (2007). [CrossRef]
8. H. Choi, S. Subramaniam, and H. A. Choi, “Loopback methods for double-link failure recovery in optical networks,” IEEE/ACM Trans. Network 12,1119–1130 (2004). [CrossRef]
