Options
A self-stabilizing algorithm for virtual ring construction
Citation Link: https://doi.org/10.15480/882.1314
Publikationstyp
Conference Paper
Date Issued
2016-04-14
Sprache
English
Author(s)
Institut
TORE-DOI
TORE-URI
This paper presents a self-stabilizing, distributed
algorithm for finding a virtual ring in a connected unweighted
graph, named SelfVRC. A virtual ring allows routing without
knowing the topology of the underlying network. All network
nodes know their own positions on the ring as well as those of
their neighbors. While self-stabilizing algorithms that construct
a virtual ring exist, little work has been done in minimizing its
length. SelfVRC was evaluated with different fair and unfair
schedulers. It stabilizes in O(n) rounds. The resulting ring is
not longer than 2(n − 1) and is on average significantly shorter.
Cycles in the underlying graph are utilized to reduce the length
of the virtual ring. SelfVRC depends on unique node identifiers
and a root node.
algorithm for finding a virtual ring in a connected unweighted
graph, named SelfVRC. A virtual ring allows routing without
knowing the topology of the underlying network. All network
nodes know their own positions on the ring as well as those of
their neighbors. While self-stabilizing algorithms that construct
a virtual ring exist, little work has been done in minimizing its
length. SelfVRC was evaluated with different fair and unfair
schedulers. It stabilizes in O(n) rounds. The resulting ring is
not longer than 2(n − 1) and is on average significantly shorter.
Cycles in the underlying graph are utilized to reduce the length
of the virtual ring. SelfVRC depends on unique node identifiers
and a root node.
Subjects
self-stabilization
virtual ring
distributed algorithm
DDC Class
620: Ingenieurwissenschaften
Loading...
Name
SelfVRC.pdf
Size
780.58 KB
Format
Adobe PDF