Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks
verfasst von : Rachid Hadid, Vincent Villain
Erschienen in: Distributed Applications and Interoperable Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The purpose of the paper is to present the first self-stabilizing algorithm for finding \(n-1\) one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm works on n-dimensional star networks \(S_n\). Given a source node s and a set of \(D = \{d_1, d_2, ...,d_{n-1} \}\) of \(n-1\) destination nodes in the n-dimensional star network, our algorithm constructs \(n-1\) node-disjoints paths \(P_1, P_2,...,P_{n-1}\), where \(P_i\) is a path from s to \(d_i\), \(1 \le i \le n-1\). Since the proposed solution is self-stabilizing [7], it does not require initialization and withstands transient faults. The stabilization time of our algorithm is \(O(n^2)\) rounds.