Conference Papers Year : 2020

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 n1

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 Sn
. Given a source node s and a set of D={d1,d2,...,dn1}
of n1
destination nodes in the n-dimensional star network, our algorithm constructs n1
node-disjoints paths P1,P2,...,Pn1
, where Pi
is a path from s to di
, 1in1
. 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(n2)
rounds.

Fichier principal
Vignette du fichier
495624_1_En_12_Chapter.pdf (268) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03223260 , version 1 (10-05-2021)

Licence

Identifiers

Cite

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⟩
113 View
48 Download

Altmetric

Share

  • More