Self-stabilizing ring networks on connected graphs

Large networks require scalable routing. Traditionally, protocol
overhead is
reduced by introducing a hierarchy. This requires aggregation of
nearby nodes
under a common address prefix. In fixed networks, this is achieved
administratively, whereas in wireless ad-hoc networks, dynamic
assignments of
nodes to aggregation units are required.

As a result of the nodes commonly being assigned a random
network address, the
majority of proposed ad-hoc routing protocols discovers routes
between end
nodes by flooding, thus limiting the network size. Peer-to-peer
(P2P) overlay
networks offer scalable routing solutions by employing
virtualized address spaces,
yet assume an underlying routing protocol for end-to-end
connectivity.

We investigate a cross-layer approach to P2P routing, where the
virtual address
space is implemented with a network-layer routing protocol by
itself. The Iterative
Successor Pointer Rewiring Protocol (ISPRP) efficiently
initializes a ring-structured
network among nodes having but link-layer connectivity. It is
fully self-organizing
and issues only a small per-node amount of messages by keeping
interactions
between nodes as local as possible.
... mehr
The main contribution of this paper is a proof that ISPRP is
self-stabilizing, that is,
starting from an arbitrary initial state, the protocol lets the
network converge into
a correct state within a bounded amount of time.