Cargando…
Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection
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 protec...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8465832/ https://www.ncbi.nlm.nih.gov/pubmed/34573741 http://dx.doi.org/10.3390/e23091116 |
_version_ | 1784572976939663360 |
---|---|
author | Szcześniak, Ireneusz Olszewski, Ireneusz Woźna-Szcześniak, Bożena |
author_facet | Szcześniak, Ireneusz Olszewski, Ireneusz Woźna-Szcześniak, Bożena |
author_sort | Szcześniak, Ireneusz |
collection | PubMed |
description | 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 “on-the-fly” 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. |
format | Online Article Text |
id | pubmed-8465832 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-84658322021-09-27 Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection Szcześniak, Ireneusz Olszewski, Ireneusz Woźna-Szcześniak, Bożena Entropy (Basel) Article 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 “on-the-fly” 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. MDPI 2021-08-27 /pmc/articles/PMC8465832/ /pubmed/34573741 http://dx.doi.org/10.3390/e23091116 Text en © 2021 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Szcześniak, Ireneusz Olszewski, Ireneusz Woźna-Szcześniak, Bożena Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title | Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title_full | Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title_fullStr | Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title_full_unstemmed | Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title_short | Towards an Efficient and Exact Algorithm for Dynamic Dedicated Path Protection |
title_sort | towards an efficient and exact algorithm for dynamic dedicated path protection |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8465832/ https://www.ncbi.nlm.nih.gov/pubmed/34573741 http://dx.doi.org/10.3390/e23091116 |
work_keys_str_mv | AT szczesniakireneusz towardsanefficientandexactalgorithmfordynamicdedicatedpathprotection AT olszewskiireneusz towardsanefficientandexactalgorithmfordynamicdedicatedpathprotection AT woznaszczesniakbozena towardsanefficientandexactalgorithmfordynamicdedicatedpathprotection |