The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability
The multipath challenge is a research line in continuous development because of its multiple benefits, however, these benefits are overshadowed by scalability, which goes down considerably when the paths are multiple and disjoint. The disjointness aggregates an extra value to the multiple paths, but...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9432811/ |
| _version_ | 1829491021155663872 |
|---|---|
| author | Diego Lopez-Pajares Elisa Rojas Juan A. Carral Isaias Martinez-Yelmo Joaquin Alvarez-Horcajo |
| author_facet | Diego Lopez-Pajares Elisa Rojas Juan A. Carral Isaias Martinez-Yelmo Joaquin Alvarez-Horcajo |
| author_sort | Diego Lopez-Pajares |
| collection | DOAJ |
| description | The multipath challenge is a research line in continuous development because of its multiple benefits, however, these benefits are overshadowed by scalability, which goes down considerably when the paths are multiple and disjoint. The disjointness aggregates an extra value to the multiple paths, but it also implies more complex mathematical operations that increase the computational cost. In fact, diverse proposals exist that try to increase scalability by limiting the number of paths obtained to the minimum possible (two-disjoint paths), which is enough for backup applications but not for other purposes. This paper presents an algorithm that solves these drawbacks by discovering multiple disjoint paths among multiple nodes in an efficient way, while keeping bounded the computational cost and ensuring scalability. The proposed algorithm has been validated thoroughly by performing a theoretical analysis, bolstered afterwards by an exhaustive experimental evaluation. The collected results are promising, our algorithm reduces the time spent to obtain the disjoint paths regarding its competitors between one and three orders of magnitude, at the cost of a slight decrease in the number of paths discovered. |
| first_indexed | 2024-12-15T00:30:30Z |
| format | Article |
| id | doaj.art-7d6a14e459b147698c94a6b420bd7b06 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-15T00:30:30Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-7d6a14e459b147698c94a6b420bd7b062022-12-21T22:42:01ZengIEEEIEEE Access2169-35362021-01-019744227443610.1109/ACCESS.2021.30809319432811The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing ScalabilityDiego Lopez-Pajares0https://orcid.org/0000-0002-8959-4321Elisa Rojas1https://orcid.org/0000-0002-6385-2628Juan A. Carral2https://orcid.org/0000-0002-5545-9463Isaias Martinez-Yelmo3https://orcid.org/0000-0001-9648-8669Joaquin Alvarez-Horcajo4https://orcid.org/0000-0002-8522-9933Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, SpainDepartamento de Automática, Universidad de Alcalá, Alcalá de Henares, SpainDepartamento de Automática, Universidad de Alcalá, Alcalá de Henares, SpainDepartamento de Automática, Universidad de Alcalá, Alcalá de Henares, SpainDepartamento de Automática, Universidad de Alcalá, Alcalá de Henares, SpainThe multipath challenge is a research line in continuous development because of its multiple benefits, however, these benefits are overshadowed by scalability, which goes down considerably when the paths are multiple and disjoint. The disjointness aggregates an extra value to the multiple paths, but it also implies more complex mathematical operations that increase the computational cost. In fact, diverse proposals exist that try to increase scalability by limiting the number of paths obtained to the minimum possible (two-disjoint paths), which is enough for backup applications but not for other purposes. This paper presents an algorithm that solves these drawbacks by discovering multiple disjoint paths among multiple nodes in an efficient way, while keeping bounded the computational cost and ensuring scalability. The proposed algorithm has been validated thoroughly by performing a theoretical analysis, bolstered afterwards by an exhaustive experimental evaluation. The collected results are promising, our algorithm reduces the time spent to obtain the disjoint paths regarding its competitors between one and three orders of magnitude, at the cost of a slight decrease in the number of paths discovered.https://ieeexplore.ieee.org/document/9432811/Algorithmsdisjointmultipathgraph theoryDijkstra’s algorithmrouting |
| spellingShingle | Diego Lopez-Pajares Elisa Rojas Juan A. Carral Isaias Martinez-Yelmo Joaquin Alvarez-Horcajo The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability IEEE Access Algorithms disjoint multipath graph theory Dijkstra’s algorithm routing |
| title | The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability |
| title_full | The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability |
| title_fullStr | The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability |
| title_full_unstemmed | The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability |
| title_short | The Disjoint Multipath Challenge: Multiple Disjoint Paths Guaranteeing Scalability |
| title_sort | disjoint multipath challenge multiple disjoint paths guaranteeing scalability |
| topic | Algorithms disjoint multipath graph theory Dijkstra’s algorithm routing |
| url | https://ieeexplore.ieee.org/document/9432811/ |
| work_keys_str_mv | AT diegolopezpajares thedisjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT elisarojas thedisjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT juanacarral thedisjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT isaiasmartinezyelmo thedisjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT joaquinalvarezhorcajo thedisjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT diegolopezpajares disjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT elisarojas disjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT juanacarral disjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT isaiasmartinezyelmo disjointmultipathchallengemultipledisjointpathsguaranteeingscalability AT joaquinalvarezhorcajo disjointmultipathchallengemultipledisjointpathsguaranteeingscalability |