{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T09:43:19Z","timestamp":1762508599426,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T00:00:00Z","timestamp":1630022400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["020\/RID\/2018\/19"],"award-info":[{"award-number":["020\/RID\/2018\/19"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We present a novel algorithm for dynamic routing with dedicated path protection which, as the presented simulation results suggest, can be efficient and exact. We present the algorithm in the setting of optical networks, but it should be applicable to other networks, where services have to be protected, and where the network resources are finite and discrete, e.g., wireless radio or networks capable of advance resource reservation. To the best of our knowledge, we are the first to propose an algorithm for this long-standing fundamental problem, which can be efficient and exact, as suggested by simulation results. The algorithm can be efficient because it can solve large problems, and it can be exact because its results are optimal, as demonstrated and corroborated by simulations. We offer a worst-case analysis to argue that the search space is polynomially upper bounded. Network operations, management, and control require efficient and exact algorithms, especially now, when greater emphasis is placed on network performance, reliability, softwarization, agility, and return on investment. The proposed algorithm uses our generic Dijkstra algorithm on a search graph generated \u201con-the-fly\u201d based on the input graph. We corroborated the optimality of the results of the proposed algorithm with brute-force enumeration for networks up to 15 nodes large. We present the extensive simulation results of dedicated-path protection with signal modulation constraints for elastic optical networks of 25, 50, and 100 nodes, and with 160, 320, and 640 spectrum units. We also compare the bandwidth blocking probability with the commonly-used edge-exclusion algorithm. We had 48,600 simulation runs with about 41 million searches.<\/jats:p>","DOI":"10.3390\/e23091116","type":"journal-article","created":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T09:53:23Z","timestamp":1630058003000},"page":"1116","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection"],"prefix":"10.3390","volume":"23","author":[{"given":"Ireneusz","family":"Szcze\u015bniak","sequence":"first","affiliation":[{"name":"Department of Computer Science, Cz\u0119stochowa University of Technology, 42-200 Cz\u0119stochowa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ireneusz","family":"Olszewski","sequence":"additional","affiliation":[{"name":"Institute of Telecommunications, UTP University of Sciences and Technology, 85-796 Bydgoszcz, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1486-6572","authenticated-orcid":false,"given":"Bo\u017cena","family":"Wo\u017ana-Szcze\u015bniak","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Jan D\u0142ugosz University, 42-200 Cz\u0119stochowa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s11107-015-0532-0","article-title":"Survivable elastic optical networks: Survey and perspective","volume":"31","author":"Shen","year":"2016","journal-title":"Photonic Netw. Commun."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/MNET.2015.7340430","article-title":"Protection in elastic optical networks","volume":"29","author":"Walkowiak","year":"2015","journal-title":"IEEE Netw."},{"doi-asserted-by":"crossref","unstructured":"Simmons, J.M. (2014). Optical Network Design and Planning, Springer. Optical Networks.","key":"ref_3","DOI":"10.1007\/978-3-319-05227-4"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"s12","DOI":"10.1109\/MCOM.2012.6146481","article-title":"Elastic optical networking: A new dawn for the optical layer?","volume":"50","author":"Gerstel","year":"2012","journal-title":"IEEE Commun. Mag."},{"doi-asserted-by":"crossref","unstructured":"Szcze\u015bniak, I. (2021, August 26). The Implementation of the Efficient and Optimal Algorithm for the Dynamic Dedicated Path Protection. Available online: http:\/\/www.irkos.org\/ddpp.","key":"ref_5","DOI":"10.3390\/e23091116"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1364\/JOCN.11.000568","article-title":"Generic Dijkstra for optical networks","volume":"11","author":"Jajszczyk","year":"2019","journal-title":"IEEE\/OSA J. Opt. Commun. Netw."},{"unstructured":"Andersen, R., Chung, F., Sen, A., and Xue, G. (2004, January 7\u201311). On disjoint path pairs with wavelength continuity constraint in WDM networks. Proceedings of the IEEE INFOCOM 2004, Hong Kong, China.","key":"ref_7"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"25422","DOI":"10.1109\/ACCESS.2019.2901018","article-title":"Modulation-Adaptive Link-Disjoint Path Selection Model for 1 + 1 Protected Elastic Optical Networks","volume":"7","author":"Kishi","year":"2019","journal-title":"IEEE Access"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1759","DOI":"10.1109\/TNET.2011.2138717","article-title":"Indirect and direct multicost algorithms for online impairment-aware RWA","volume":"19","author":"Christodoulopoulos","year":"2011","journal-title":"Trans. Netw."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1364\/JOCN.6.001115","article-title":"Dynamic routing and spectrum allocation in elastic optical networks with mixed line rates","volume":"6","author":"Wang","year":"2014","journal-title":"J. Opt. Commun. Netw."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1109\/CC.2013.6506930","article-title":"Polynomial-time adaptive routing algorithm based on spectrum scan in dynamic flexible optical networks","volume":"10","author":"Yang","year":"2013","journal-title":"China Commun."},{"doi-asserted-by":"crossref","unstructured":"Liu, Y., Hua, N., Wan, X., Zheng, X., and Liu, Z. (2011, January 13\u201316). A spectrum-scan routing scheme in flexible optical networks. Proceedings of the 2011 Asia Communications and Photonics Conference and Exhibition, Shanghai, China.","key":"ref_12","DOI":"10.1364\/ACP.2011.83100B"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/S0140-3664(00)00236-X","article-title":"Efficient heuristic algorithms for light-path routing and wavelength assignment in WDM networks under dynamically varying loads","volume":"24","author":"Shen","year":"2001","journal-title":"Comput. Commun."},{"key":"ref_14","first-page":"2955","article-title":"Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection","volume":"33","author":"Wang","year":"2015","journal-title":"J. Light. Technol."},{"unstructured":"Chen, C., and Banerjee, S. (1995, January 14\u201316). A new model for optimal routing in all-optical networks with scalable number of wavelength converters. Proceedings of the GLOBECOM \u201995, Singapore.","key":"ref_15"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1364\/JOCN.8.000507","article-title":"Graph-model-based dynamic routing and spectrum assignment in elastic optical networks","volume":"8","author":"Hsu","year":"2016","journal-title":"J. Opt. Commun. Netw."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s002910000046","article-title":"A survey and annotated bibliography of multiobjective combinatorial optimization","volume":"22","author":"Ehrgott","year":"2000","journal-title":"OR Spektrum"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2988","DOI":"10.1016\/j.comnet.2008.06.016","article-title":"Routing and scheduling connections in networks that support advance reservations","volume":"52","author":"Varvarigos","year":"2008","journal-title":"Comput. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1109\/TNET.2004.836112","article-title":"Concepts of exact QoS routing algorithms","volume":"12","author":"Mieghem","year":"2004","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1109\/49.536364","article-title":"Quality-of-service routing for supporting multimedia applications","volume":"14","author":"Wang","year":"1996","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-642-48782-8_9","article-title":"Bicriterion path problems","volume":"Volume 177","author":"Hansen","year":"1980","journal-title":"Multiple Criteria Decision Making Theory and Application"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","article-title":"On a multicriteria shortest path problem","volume":"16","author":"Martins","year":"1984","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2478\/v10006-007-0023-2","article-title":"Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms","volume":"17","author":"Tarapata","year":"2007","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/net.3230040204","article-title":"Disjoint paths in a network","volume":"4","author":"Suurballe","year":"1974","journal-title":"Networks"},{"unstructured":"Bhandari, R. (1999). Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers.","key":"ref_25"},{"unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice Hall.","key":"ref_26"},{"doi-asserted-by":"crossref","unstructured":"Szcze\u015bniak, I., and Wo\u017ana-Szcze\u015bniak, B. (2016, January 9\u201312). Adapted and constrained Dijkstra for elastic optical networks. Proceedings of the 2016 International Conference on Optical Network Design and Modeling (ONDM), Cartagena, Spain.","key":"ref_27","DOI":"10.1109\/ONDM.2016.7494087"},{"doi-asserted-by":"crossref","unstructured":"Cetinkaya, E., Alenazi, M., Cheng, Y., Peck, A., and Sterbenz, J. (2013, January 10\u201313). On the fitness of geographic graph generators for modelling physical level topologies. Proceedings of the 2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Almaty, Kazakhstan.","key":"ref_28","DOI":"10.1109\/ICUMT.2013.6798402"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1364\/JOCN.4.000603","article-title":"Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks","volume":"4","author":"Wan","year":"2012","journal-title":"J. Opt. Commun. Netw."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/9\/1116\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:53:46Z","timestamp":1760165626000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/9\/1116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,27]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["e23091116"],"URL":"https:\/\/doi.org\/10.3390\/e23091116","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,8,27]]}}}