A self-stabilizing algorithm for virtual ring construction

Abstract

Diese Arbeit präsentiert SelfVRC, einen selbststabilisierenden, verteilten Algorithmus zum bestimmen von virtuellen Ringen in verbundenen ungewichteten Graphen.

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.