Shared Risk Link Group disjointness and geodiverse routing: A trade-off between benefit and practical effort
Corresponding Author
Rita Girão-Silva
Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal
Institute for Systems Engineering and Computers at Coimbra (INESC Coimbra), Coimbra, Portugal
Correspondence
Rita Girão-Silva, Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal.
Email: [email protected]
Search for more papers by this authorBoro Nedic
Department of Mathematics and Natural Sciences, Darmstadt University of Applied Sciences, Darmstadt, Germany
Search for more papers by this authorMatthias Gunkel
Deutsche Telekom Technik GmbH - Optical Transport Core, Darmstadt, Germany
Search for more papers by this authorTeresa Gomes
Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal
Institute for Systems Engineering and Computers at Coimbra (INESC Coimbra), Coimbra, Portugal
Search for more papers by this authorCorresponding Author
Rita Girão-Silva
Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal
Institute for Systems Engineering and Computers at Coimbra (INESC Coimbra), Coimbra, Portugal
Correspondence
Rita Girão-Silva, Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal.
Email: [email protected]
Search for more papers by this authorBoro Nedic
Department of Mathematics and Natural Sciences, Darmstadt University of Applied Sciences, Darmstadt, Germany
Search for more papers by this authorMatthias Gunkel
Deutsche Telekom Technik GmbH - Optical Transport Core, Darmstadt, Germany
Search for more papers by this authorTeresa Gomes
Department of Electrical and Computer Engineering, University of Coimbra, Coimbra, Portugal
Institute for Systems Engineering and Computers at Coimbra (INESC Coimbra), Coimbra, Portugal
Search for more papers by this authorAbstract
The resilience to disasters is a very relevant problem in telecommunication networks. This work addresses the problem of 1 + 1 optical lightpath protection considering maximally shared risk link group (SRLG)-disjoint geodiverse paths, applied in the context of an optical network. The resilience to geographically correlated disasters is accomplished by guaranteeing geodiversity of the paths. This work focuses on estimating the increase of the path lengths and the increase in cost of the required transponders, compared to simple link-disjointness (i.e., when no constraints on SRLG-disjointness or geodiversity are considered). Results in different networks allow to evaluate the effect of SRLG-disjointness to ensure some geodiversity.
REFERENCES
- 1M.W. Ashraf, S.M. Idrus, F. Iqbal, and R.A. Butt, On spatially disjoint lightpaths in optical networks, Photonic Netw. Commun. 36 (2018), 11–25.
- 2A. Beshir, F. Kuipers, A. Orda, and P. Van Mieghem, Survivable routing and regenerator placement in optical networks, IV International Congress on Ultra Modern Telecommunications and Control Systems (ICUMT 2012), St. Petersburg, Russia, 2012, pp. 684–690.
- 3R. Bhandari, Survivable Networks, Algorithms for Diverse Routing, Kluwer Academic Publishers, Norwell, MA, 1999.
- 4 H. Bottomley, Between the sinusoidal projection and the Werner: An alternative to the Bonne, Cybergeo 241 (2003). http://journals.openedition.org/cybergeo/3977
- 5Y. Cheng, M.T. Gardner, J. Li, R. May, D. Medhi, and J.P.G. Sterbenz. Optimised heuristics for a geodiverse routing protocol, 2014 10th International Conference on the Design of Reliable Communication Networks (DRCN), 2014, pp. 1–9.
- 6Y. Cheng, M.T. Gardner, J. Li, R. May, D. Medhi, and J.P.G. Sterbenz, Analysing GeoPath diversity and improving routing performance in optical networks, Comput. Netw. 82 (2015), 50–67.
- 7Y. Cheng, J. Li, and J.P.G. Sterbenz, Path geo-diversification: Design and analysis, 2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2013, pp. 46–53.
- 8Y. Cheng, D. Medhi, and J.P.G. Sterbenz, Geodiverse routing with path delay and skew requirement under area-based challenges, Networks 66 (2015), 335–346.
- 9Y. Cheng and J.P.G. Sterbenz, Critical region identification and geodiverse routing protocol under massive challenges, 2015 7th International Workshop on Reliable Networks Design and Modeling (RNDM), 2015, pp. 14–20.
- 10J.C.N. Clímaco, M.E. Captivo, and M.M.B. Pascoal, On the bicriterion – minimal cost/minimal label – spanning tree problem, Eur. J. Oper. Res. 204 (2010), 199–205.
- 11J.M.F. Craveirinha, J.C.N. Clímaco, L.M.R.A. Martins, and M.M.B. Pascoal, An exact method for constructing minimal cost/minimal SRLG spanning trees over optical networks, Telecommun. Syst. 62 (2016), 327–346.
- 12A. Eira, M. Quagliotti, and J. Pedro, Impact of client- and line-side flexibility in the lifecycle of next-generation transport networks [Invited], IEEE/OSA J. Opt. Commun. Netw. 8 (2016), A101–A115.
- 13T. Gomes and J. Craveirinha, An algorithm for enumerating SRLG diverse path pairs, J. Telecommun. Inf. Technol. 3 (2010), 5–12.
- 14T. Gomes, L. Jorge, P. Melo, and R. Girão-Silva, Maximally node and SRLG-disjoint path pair of min-sum cost in GMPLS networks: A lexicographic approach, Photonic Netw. Commun. 31 (2016), 11–22.
- 15T. Gomes, C. Simões, and L. Fernandes, Resilient routing in optical networks using SRLG-disjoint path pairs of min-sum cost, Telecommun. Syst. 52 (2013), 737–749.
- 16T. Gomes, J. Tapolcai, C. Esposito, D. Hutchison, F. Kuipers, J. Rak, A. de Sousa, A. Iossifides, R. Travanca, J. André, L. Jorge, L. Martins, P.O. Ugalde, A. Pašić, D. Pezaros, S. Jouet, S. Secci, and M. Tornatore, A survey of strategies for communication networks to protect against large-scale natural disasters, 8th International Workshop on Resilient Networks Design and Modeling (RNDM), 2016, pp. 11–22.
- 17J.Q. Hu, Diverse routing in optical mesh networks, IEEE Trans. Commun. 51 (2003), 489–494.
- 18 IBM ILOG CPLEX Optimization Studio V12.8.0. IBM, 2017.
- 19A. Mauthe, D. Hutchison, E.K. Çetinkaya, I. Ganchev, J. Rak, J.P.G. Sterbenz, M. Gunkel, P. Smith, and T. Gomes, Disaster-resilient communication networks: Principles and best practices, 2016 8th International Workshop on Resilient Networks Design and Modeling (RNDM), 2016, pp. 1–10.
- 20V. Miletić, T. Šubić, and B. Mikac. Optimizing maximum shared risk link group disjoint path algorithm using NVIDIA CUDA heterogeneous parallel programming platform, 2014 X International Symposium on Telecommunications (BIHTEL), 2014, pp. 1–6.
- 21B. Nedic, M. Gunkel, T. Gomes, and R. Girão-Silva, SRLG-disjointness and geodiverse routing – A practical network study and operational conclusions, 10th International Workshop on Resilient Networks Design and Modeling (RNDM 2018), Longyearbyen, Svalbard (Spitsbergen), Norway, 2018, pp. 1–8.
- 22R. Noldus and P. Van Mieghem, Assortativity in complex networks, J. Complex Netw. 3 (2015), 507–542.
- 23S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski, SNDlib 1.0 – Survivable network design library, Networks 55 (2010), 276–286 http://sndlib.zib.de.
- 24P. Poggiolini, A. Carena, V. Curri, G. Bosco, and F. Forghieri, Analytical modeling of nonlinear propagation in uncompensated optical transmission links, IEEE Photonics Technol. Lett. 23 (2011), 742–744.
- 25J. Rak, D. Hutchison, E. Calle, T. Gomes, M. Gunkel, P. Smith, J. Tapolcai, S. Verbrugge, and L. Wosinska, RECODIS: Resilient communication services protecting end-user applications from disaster-based failures, 18th International Conference on Transparent Optical Networks (ICTON), 2016. pp. 1–4. Invited paper.
- 26J.P. Rohrer, A. Jabbar, and J.P.G. Sterbenz, Path diversification for future internet end-to-end resilience and survivability, Telecommun. Syst. 56 (2014), 49–67.
- 27M.J. Rostami, S. Khorsandi, and A.A. Khodaparast, CoSE: A SRLG-disjoint routing algorithm, Proceedings of the Fourth European Conference on Universal Multiservice Networks (ECUMN'07), Toulouse, France, 2007, pp. 86–92.
- 28M.J. Rostami, A.A.E. Zarandi, and S.M. Hoseininasab, MSDP with ACO: A maximal SRLG disjoint routing algorithm based on ant colony optimization, J. Netw. Comput. Appl. 35 (2012), 394–402.
- 29A. de Sousa, D. Santos, and P. Monteiro, Determination of the minimum cost pair of D-geodiverse paths, 13th International Conference on the Design of Reliable Communication Networks (DRCN 2017), Munich, 2017, pp. 1–8.
- 30J.W. Suurballe and R.E. Tarjan, A quick method for finding shortest pairs of disjoint paths, Networks 14 (1984), 325–336.
- 31J. Tapolcai, L. Rónyai, B. Vass, and L. Gyimóthi, List of shared risk link groups representing regional failures with limited size, IEEE INFOCOM 2017 – IEEE Conference on Computer Communications, 2017, pp. 1–9.
- 32A. Todimala and B. Ramamurthy, IMSH: An iterative heuristic for SRLG diverse routing in WDM mesh networks, 13th International Conference on Computer Communications and Networks, ICCCN'2004, 2004, pp. 199–204.
- 33
P. Van Mieghem, Performance Analysis of Complex Networks and Systems, Cambridge University Press, Cambridge, 2014.
10.1017/CBO9781107415874 Google Scholar
- 34B. Vass, E. Berczi-Kovacs, and J. Tapolcai, Enumerating shared risk link groups of circular disk failures hitting k nodes, 13th International Conference on the Design of Reliable Communication Networks (DRCN 2017) Munich, 2017, pp. 1–9.
- 35K. Xie, H. Tao, X. Wang, G. Xie, J. Wen, J. Cao, and Z. Qin, Divide and conquer for fast SRLG disjoint routing, 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2018, pp. 622–633.
- 36D. Xu, Y. Chen, Y. Xiong, C. Qiao, and X. He, On finding disjoint paths in single and dual link cost networks, IEEE INFOCOM 2004 Hong Kong, 2004.
- 37S. Yin, S. Huang, B. Guo, X. Li, Y. Zhao, J. Zhang, and W. Gu, Survivable multipath routing and resource assignment with SRLG in virtual optical networks, 2016 Optical Fiber Communications Conference and Exhibition (OFC), 2016, pp. 1–3.
- 38Y. Zhu and J.P. Jue, Reliable collective communications with weighted SRLGs in optical Networks, IEEE/ACM Trans. Netw. 20 (2012), 851–863.
