RT info:eu-repo/semantics/article
T1 The disjoint multipath challenge: multiple disjoint paths guaranteeing scalability
A1 López Pajares, Diego
A1 Rojas Sánchez, Elisa
A1 Carral Pelayo, Juan Antonio
A1 Martinez Yelmo, Isaias
A1 Álvarez Horcajo, Joaquín
K1 Algorithms
K1 Disjoint
K1 Multipath
K1 Graph theory
K1 Dijkstra's algorithm
K1 Routing
K1 Informática
K1 Computer science
AB 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.
PB IEEE
SN 2169-3536
YR 2021
FD 2021-05-17
LK http://hdl.handle.net/10017/48258
UL http://hdl.handle.net/10017/48258
LA eng
NO Comunidad de Madrid
DS MINDS@UW
RD 24-abr-2024