HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks

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.
Complete list of metadata

https://hal.inria.fr/hal-03223260
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, May 10, 2021 - 5:41:36 PM
Last modification on : Wednesday, November 3, 2021 - 7:07:16 AM
Long-term archiving on: : Wednesday, August 11, 2021 - 8:08:34 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Rachid Hadid, Vincent Villain. A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks. 20th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2020, Valletta, Malta. pp.186-203, ⟨10.1007/978-3-030-50323-9_12⟩. ⟨hal-03223260⟩

Share

Metrics

Record views

58