OSA's Digital Library

Optics Express

Optics Express

  • Editor: Andrew M. Weiner
  • Vol. 22, Iss. 3 — Feb. 10, 2014
  • pp: 2386–2402
« Show journal navigation

Pre-configured polyhedron based protection against multi-link failures in optical mesh networks

Shanguo Huang, Bingli Guo, Xin Li, Jie Zhang, Yongli Zhao, and Wanyi Gu  »View Author Affiliations


Optics Express, Vol. 22, Issue 3, pp. 2386-2402 (2014)
http://dx.doi.org/10.1364/OE.22.002386


View Full Text Article

Acrobat PDF (1198 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

This paper focuses on random multi-link failures protection in optical mesh networks, instead of single, the dual or sequential failures of previous studies. Spare resource efficiency and failure robustness are major concerns in link protection strategy designing and a k-regular and k-edge connected structure is proved to be one of the optimal solutions for link protection network. Based on this, a novel pre-configured polyhedron based protection structure is proposed, and it could provide protection for both simultaneous and sequential random link failures with improved spare resource efficiency. Its performance is evaluated in terms of spare resource consumption, recovery rate and average recovery path length, as well as compared with ring based and subgraph protection under probabilistic link failure scenarios. Results show the proposed novel link protection approach has better performance than previous works.

© 2014 Optical Society of America

1. Introduction

In light of the above, there is a pressing need to develop improved multi-failure recovery solutions which also incorporate resource provision efficiency. This paper addresses this critical area and is organized as follows. First, Section II presents an overview of some existing work in dual and multi-failure recovery. Next, a novel pre-configured polyhedron (PCP) protection structure based on k-regular and k-edge connected graph is proposed in Section III and heuristic algorithm to construct such structure in Section IV. Section V then presents detailed simulation results and compares the performance of the proposed scheme with various existing solutions. Finally, conclusions and directions for future work are presented.

2. Related work

3. k-regular and k-connected structures and pre-configured polyhedron

3.1 k-regular and k-edge connected graph and PCP schemes

Definition 1: k-regular and k-edge connected graph: k-regular represents the degree of each node in a graph is k and k-edge connected graph means there does not exist a set of fewer than k edges whose removal disconnects the graph. The proposed k-regular and k-edge connected structure is based on the Menger's theorem which is one of the cornerstones of graph theory.

Theorem 3.1. (Menger Theorem) [18

18. F. T. Boesch and J. F. Wang, “Super line connectivity properties of circulant graphs,” SIAM J. Alg. Disc. Math. 7(1), 89–98 (1986). [CrossRef]

,19

19. A. Frank, Connectivity and Network Flows. Chapter 2 of Handbook of Combinatorics. R.L. Graham, M. Grotschel, and L. Lovasz editors. Elsevier and MIT Press (1995).

]

  • (1) Let G = (V, E) be a graph and {A, B}V. Then the minimum number of edges separating A from B in G is equal to the maximum number of edge-disjoint AB paths in G.
  • (2) A graph is k-edge-connected if and only if it contains k edge-disjoint paths between any two vertices.

  • Definition 2: Failure Recovery Probability (FRP) FRP is the ratio of failure scenarios that could be recovered by the protection structure and all possible failure scenarios.

  • Definition 2: Pre-Configured Polyhedron Protection For a given physical topology, if a k-regular and k-edge connected subgraph could be constructed on it and all the links are marked as on-structure links or span links, this k-regular and k-edge connected subgraph is referred as a Pre-Configured Polyhedron protection.

3.2 Analysis of spare resources required for link-restorable optical mesh network and k-regular and k-edge connected protection structure

(a) Lower bound of spare resource required by link-restorable optical mesh networks

(b) Upper bound of SCE of k-regular and k-edge connected protection structures

limSCENN*=f×k×N/2Ε¯=fd¯f
(7)

3.3 Some designing concerns of PCP

In this section, some PCP designing concerns are analyzed, and it is shown that the size of PCP structure and the selection of k would have impact on its SCE and recovery capability, which is important to survivable network design. Following are some notions will be used and two observations to be discussed in details.

  • Definition 3: Link Spare Ratio (LSR, α) LSR is the ratio of spare capacity allocated for each link of protection structure and the working capacity protected in each link.
  • Observation 1: FRP performance is closely related with the value of SCE, as well as the failure scenario considered and the link failure probability.
  • Observation 2: For PCP protection structures with same connectivity (i.e., k), generally larger size protection structure could protect link failures more efficiently. On the other hand, for PCP structures with same size, proper k would lead to higher SCE.

  • pl is the failure probability of a link;
  • P(f) is the probability of random f link failures happening;
  • C|E|f is all possible f link failures scenarios among |E| links;
  • R¯f is the amount of failure scenarios that could not be recovered among C|E|f;
  • Pn(f)is normalizedP(f) among all possible failures;
  • Pr(f)is the recovery probability of random f link failures.

4. Heuristics algorithm

4.1 Polyhedron structure construction

Regarding to the PCP structure construction, one method is to extend a cycle to a k-edge-connected graph which has been studied by Mader in 1972 on the connectivity of circulant graphs:

  • Theorem 4.1 (Mader in 1972) [19

    19. A. Frank, Connectivity and Network Flows. Chapter 2 of Handbook of Combinatorics. R.L. Graham, M. Grotschel, and L. Lovasz editors. Elsevier and MIT Press (1995).

    ,21

    21. W. Mader, “Eine Eigenschaft der Atome endlicher Graphen,” Arch. Math. 22(1), 257–262 (1971). [CrossRef]

    ]:
    • (1) The circulant graph Cn(l1, l2, ..., lk) with n nodes, degree k, and links from vertex i to vertices i + lj (lj is positive integer) for j in [1…k] is connected if and only if gcd(n, l1, l2, ..., lk) = 1. Circulant graph is a graph the n vertices of which can be numbered from 0 to n–1 in such a way that, if some two vertices numbered x and y are adjacent, then every two vertices numbered z and (zx + y) mod n are adjacent.
    • (2) Every connected point-symmetric (vertex transitive) graph of degree k has edge-connectivity k.

Accordingly, the PCP could be designed as following. After finding a cycle in the physical topology, selecting specified links/paths in the physical topology and adding it to the cycle to form a circulant graph, which leaves each node pair in cycle separated by lj nodes (where lj|V|/21 [16

16. X. Li, S. Huang, J. Zhang, Y. Zhao, and W. Gu, “k-regular and k-(edge)-connected Protection Structures in Optical Transport Networks,” OFC JW2A.03 (2013).

]). If the amount of links/paths added for each node pair is k-2, this circulant graph is a k-regular and k-edge connected structure.

However, it is generally impracticable to construct one huge PCP protection structure for a given physical topology, because it needs higher graph connectivity and would lead to longer recovery path, no matter to say its computation complexity (e.g., Hamilton cycle searching has high computation and time complexity even for a large planar graph). So, two compromise approaches are introduced, graph abstraction based graph decomposing approach and a remediation approach to form a holistic polyhedron.

Algorithm 1 Polyhedron Structure Construction
Input: Adjacency matrix of physical topology {aij}; βis a parameter defined to limit the size of PCP structure; λ is weight coefficient of cci; w¯; γis a coefficient related with k;
Output: Polyhedron protection structure;
1: Sorting the nodes according their cci* = λcci + sumcc(ni); E* = Ø; N* = Ø;
2: while E* 1 E do
3: for node ni with max cci* do
4: N* = N*ni
for each nj with aij or aji = 1 do //cover the adjacent nodes of ni and their adjacent nodes
N* = N*nj
for nk with ajk or akj = 1 do
N* = N*nk
for |N*|<β|N| do // to control the amount of involving nodes
for each nxN¯* do //N¯*=NN*
for each nyN*do
wx=axy
end for
if wx>w then n=nx,w=wx // initialization w = 0;
end for
if wx<w¯ then continue
else N*=N*nx
end for
end for
end for
end for
find the longest Hamilton cycle G (N, E) in subgraph G* with nÎN* and edges between them;
construct the polyhedron structure by adding links separated by γ|N|/21 nodes with the remediation approach;
E* = E∪{eij and eji|aij or aji = 1, where i, jÎN}
5: run graph abstraction;
6: go to step 2;
7: end while.

4.2 Spare capacity allocation

4.3 Recovery approach in PCP after link failures

An alternative approach is dynamic path selection in the end node based on a locally maintained PCP structure connectivity and spare capacity utilization information. This approach is resource efficient and could provide sufficient recovery capability if there are enough spare resources. Also, its recovery path computation is extremely simple than the dynamic restoration approach since it is implemented within the PCP structure. Specifically, in this paper, this approach is employed to achieve better failure recovery efficiency.

5. Performance evaluation and discussion

5.1 Spare capacity consuming

5.2. Recovery capability

5.3 Average recovery path length (ARPL)

Figure 9
Fig. 9 ARPL vs. global cluster coefficient.
shows that the ARPL of all these schemes are reduced with the increase of GCC (the size of topology is 80), which is the result of fact that the increase of GCC improves the topology connectivity. However, the ARPL of PCP is more susceptible to the variation of GCC, while that of other two schemes could not be reduced further especially when GCC>0.5. For PCP itself, GCC contributes more to the reduction of ARPL when GCC<0.4, but SCE plays an important role afterwards.

6. Concluding remarks

Acknowledgments

The authors would like to thank the anonymous reviewers and the editors for their valuable comments and suggestions which are helpful to improve the paper. Part of this work has been published in OFC 2013. This work is supported partly by the National Basic Research Program of China (973 Program) (Nos. 2010CB328204 and 2010CB328202), the National Natural Science Foundation of China (Nos. 61205058 and 61331008), the Hi-Tech Research and Development Program of China (863 Program) (No.2012AA011302), the Program for New Century Excellent Talents in University (NCET-12-0793), the Beijing Nova Program (No. 2011065), the Beijing Youth Elite Project for Universities (No. YETP0479), and the Fundamental Research Funds for the Central Universities.

References and links

1.

L. Guo, J. Cao, H. Yu, and L. Li, “Path-based routing provisioning with mixed shared protection in WDM mesh networks,” J. Lightwave Technol. 24(3), 1129–1141 (2006). [CrossRef]

2.

C. Ou, H. Zang, N. K. Singhal, K. Zhu, L. H. Sahasrabuddhe, R. A. MacDonald, and B. Mukherjee, “Subpath Protection for Scalability and Fast Recovery in Optical WDM Mesh Networks,” IEEE J.. Sel. Areas Commun. 22(9), 1859–1875 (2004). [CrossRef]

3.

H.-W. Lee, E. Modiano, and K. Lee, “Diverse routing in networks with probabilistic failures,” IEEE/ACM Trans. Networking 18(6), 1895–1907 (2010). [CrossRef]

4.

P. Agarwal, A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, and G. Zussman, “The resilience of WDM networks to probabilistic geographical failures,” Proc. IEEE INFOCOM1521–1529 (2011).

5.

Y. Zhao, X. Li, H. Li, X. Wang, J. Zhang, and S. Huang, “Multi-link faults localization and restoration based on fuzzy fault set for dynamic optical networks,” Opt. Express 21(2), 1496–1511 (2013). [CrossRef] [PubMed]

6.

R. Asthana, Y. N. Singh, and W. D. Grover, “p-Cycles: An overview,” IEEE Commun. Surveys Tutorials 12(1), 97–111 (2010). [CrossRef]

7.

G. Ellinas, A. G. Hailemariam, and T. E. Stern, “Protection cycles in mesh WDM networks,” IEEE J. Sel. Areas Commun. 18(10), 1924–1937 (2000). [CrossRef]

8.

S. Huang, B. Li, B. Guo, J. Zhang, P. Luo, D. Tan, and W. Gu, “Distributed Protocol for Removal of Loop Backs with Asymmetric Digraph Using GMPLS in P-Cycle Based Optical Networks,” IEEE Trans. Commun. 59(2), 541–551 (2011). [CrossRef]

9.

J.-S. Li, C.-F. Yang, and J.-H. Chen, “Star-Block Design in Two-Level Survivable Optical Networks,” IEEE/ACM Trans. Networking 19(2), 526–539 (2011). [CrossRef]

10.

M. T. Frederick, P. Datta, and A. K. Somani, “Sub-Graph Routing: A generalized fault-tolerant strategy for link failures in WDM Optical Networks,” Comput. Netw. 50(2), 181–199 (2006). [CrossRef]

11.

S. Ramasubramanian and A. Chandak, “Dual-Link Failure Resiliency through Backup Link Mutual Exclusion,” IEEE/ACM Trans. Netw. 16(1), 157–169 (2008). [CrossRef]

12.

L. Ruan and T. Feng, “A hybrid protection/restoration scheme for two-link failure in WDM mesh networks,” in Proc. IEEE GLOBECOM 1–5 (2010).

13.

L. Guo, “Hybrid survivable configuration for optical wavelength-division-multiplexing mesh networks,” Opt. Express 15(3), 834–838 (2007). [CrossRef] [PubMed]

14.

D. Oscar, X. Feng, N. Min-Allah, K. Mahmoud, P. Min, K. Samee, and N. Ghani, “Network Survivability for Multiple Probabilistic Failures,” IEEE Commun. Lett. 16(8), 1320–1323 (2012).

15.

X. Cheng, X. Shao, and Y. Wang, “Multiple link failure recovery in survivable optical networks,” Photonic Netw. Commun. 14(2), 159–164 (2007). [CrossRef]

16.

X. Li, S. Huang, J. Zhang, Y. Zhao, and W. Gu, “k-regular and k-(edge)-connected Protection Structures in Optical Transport Networks,” OFC JW2A.03 (2013).

17.

S. Huang, J. Zhang, X. Li, Y. Zhao, and W. Gu, “Pre-configured polyhedron (p-poly) based protection structure against multi-link failures in optical networks,” in CHINACOM 277–283 (2012).

18.

F. T. Boesch and J. F. Wang, “Super line connectivity properties of circulant graphs,” SIAM J. Alg. Disc. Math. 7(1), 89–98 (1986). [CrossRef]

19.

A. Frank, Connectivity and Network Flows. Chapter 2 of Handbook of Combinatorics. R.L. Graham, M. Grotschel, and L. Lovasz editors. Elsevier and MIT Press (1995).

20.

D. A. Schupke, “Analysis of p-Cycle Capacity in WDM Networks,” Photonic Netw. Commun. 9(8), 756–758 (2006).

21.

W. Mader, “Eine Eigenschaft der Atome endlicher Graphen,” Arch. Math. 22(1), 257–262 (1971). [CrossRef]

22.

B. Guo, S. Huang, P. Luo, H. Huang, J. Zhang, and W. Gu, “Dynamic Survivable Mapping in IP Over WDM Network,” J. Lightwave Technol. 29(9), 1274–1284 (2011). [CrossRef]

OCIS Codes
(060.0060) Fiber optics and optical communications : Fiber optics and optical communications
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4257) Fiber optics and optical communications : Networks, network survivability
(060.4261) Fiber optics and optical communications : Networks, protection and restoration

ToC Category:
Optical Communications

History
Original Manuscript: November 4, 2013
Revised Manuscript: December 15, 2013
Manuscript Accepted: January 7, 2014
Published: January 28, 2014

Citation
Shanguo Huang, Bingli Guo, Xin Li, Jie Zhang, Yongli Zhao, and Wanyi Gu, "Pre-configured polyhedron based protection against multi-link failures in optical mesh networks," Opt. Express 22, 2386-2402 (2014)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-22-3-2386


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. L. Guo, J. Cao, H. Yu, L. Li, “Path-based routing provisioning with mixed shared protection in WDM mesh networks,” J. Lightwave Technol. 24(3), 1129–1141 (2006). [CrossRef]
  2. C. Ou, H. Zang, N. K. Singhal, K. Zhu, L. H. Sahasrabuddhe, R. A. MacDonald, B. Mukherjee, “Subpath Protection for Scalability and Fast Recovery in Optical WDM Mesh Networks,” IEEE J.. Sel. Areas Commun. 22(9), 1859–1875 (2004). [CrossRef]
  3. H.-W. Lee, E. Modiano, K. Lee, “Diverse routing in networks with probabilistic failures,” IEEE/ACM Trans. Networking 18(6), 1895–1907 (2010). [CrossRef]
  4. P. Agarwal, A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, “The resilience of WDM networks to probabilistic geographical failures,” Proc. IEEE INFOCOM1521–1529 (2011).
  5. Y. Zhao, X. Li, H. Li, X. Wang, J. Zhang, S. Huang, “Multi-link faults localization and restoration based on fuzzy fault set for dynamic optical networks,” Opt. Express 21(2), 1496–1511 (2013). [CrossRef] [PubMed]
  6. R. Asthana, Y. N. Singh, W. D. Grover, “p-Cycles: An overview,” IEEE Commun. Surveys Tutorials 12(1), 97–111 (2010). [CrossRef]
  7. G. Ellinas, A. G. Hailemariam, T. E. Stern, “Protection cycles in mesh WDM networks,” IEEE J. Sel. Areas Commun. 18(10), 1924–1937 (2000). [CrossRef]
  8. S. Huang, B. Li, B. Guo, J. Zhang, P. Luo, D. Tan, W. Gu, “Distributed Protocol for Removal of Loop Backs with Asymmetric Digraph Using GMPLS in P-Cycle Based Optical Networks,” IEEE Trans. Commun. 59(2), 541–551 (2011). [CrossRef]
  9. J.-S. Li, C.-F. Yang, J.-H. Chen, “Star-Block Design in Two-Level Survivable Optical Networks,” IEEE/ACM Trans. Networking 19(2), 526–539 (2011). [CrossRef]
  10. M. T. Frederick, P. Datta, A. K. Somani, “Sub-Graph Routing: A generalized fault-tolerant strategy for link failures in WDM Optical Networks,” Comput. Netw. 50(2), 181–199 (2006). [CrossRef]
  11. S. Ramasubramanian, A. Chandak, “Dual-Link Failure Resiliency through Backup Link Mutual Exclusion,” IEEE/ACM Trans. Netw. 16(1), 157–169 (2008). [CrossRef]
  12. L. Ruan, T. Feng, “A hybrid protection/restoration scheme for two-link failure in WDM mesh networks,” in Proc. IEEE GLOBECOM 1–5 (2010).
  13. L. Guo, “Hybrid survivable configuration for optical wavelength-division-multiplexing mesh networks,” Opt. Express 15(3), 834–838 (2007). [CrossRef] [PubMed]
  14. D. Oscar, X. Feng, N. Min-Allah, K. Mahmoud, P. Min, K. Samee, N. Ghani, “Network Survivability for Multiple Probabilistic Failures,” IEEE Commun. Lett. 16(8), 1320–1323 (2012).
  15. X. Cheng, X. Shao, Y. Wang, “Multiple link failure recovery in survivable optical networks,” Photonic Netw. Commun. 14(2), 159–164 (2007). [CrossRef]
  16. X. Li, S. Huang, J. Zhang, Y. Zhao, and W. Gu, “k-regular and k-(edge)-connected Protection Structures in Optical Transport Networks,” OFC JW2A.03 (2013).
  17. S. Huang, J. Zhang, X. Li, Y. Zhao, and W. Gu, “Pre-configured polyhedron (p-poly) based protection structure against multi-link failures in optical networks,” in CHINACOM 277–283 (2012).
  18. F. T. Boesch, J. F. Wang, “Super line connectivity properties of circulant graphs,” SIAM J. Alg. Disc. Math. 7(1), 89–98 (1986). [CrossRef]
  19. A. Frank, Connectivity and Network Flows. Chapter 2 of Handbook of Combinatorics. R.L. Graham, M. Grotschel, and L. Lovasz editors. Elsevier and MIT Press (1995).
  20. D. A. Schupke, “Analysis of p-Cycle Capacity in WDM Networks,” Photonic Netw. Commun. 9(8), 756–758 (2006).
  21. W. Mader, “Eine Eigenschaft der Atome endlicher Graphen,” Arch. Math. 22(1), 257–262 (1971). [CrossRef]
  22. B. Guo, S. Huang, P. Luo, H. Huang, J. Zhang, W. Gu, “Dynamic Survivable Mapping in IP Over WDM Network,” J. Lightwave Technol. 29(9), 1274–1284 (2011). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited