A Concentric Multi-ring Overlay for Highly Reliable P2P Networks


The paper presents a concentric multiring overlay networking topology for fast and shortest path resource discovery in dynamic distributed systems like P2P networks. First, we define a highly reliable P2P system called HiPeer, which is deployed on top of the logical overlay with a number of lowest bounds in terms of network performance. Then, we demonstrate that for any De Bruijn digraph of degree d > 2 and diameter D_{DB}, HiPeer constructs a highly reliable network, where each node maintains a routing table with a size of at most 2d + 3 entries independently of the number N of nodes in the system. Further, we show that for any network with at most d nodes, any existing resource in the network can be found within at most D_{HiPeer} = log_d_(N(d - 1) + d) - 1 hops. This result is as close to the Moore bound as the query path length in the other best P2P proposals based on the De Bruijn digraphs. Thus, HiPeer defines a highly connected network with connectivity d and the lowest yet known lookup bound D_{HiPeer}. Moreover, we show that any node’s ”join or leave” operation in HiPeer implies a constant expected reorganization cost of the magnitude order of O(d) control messages.

Giscard Wepiwe, Plamen L. Simeonov
Proceedings of the 4th IEEE International Symposium on Network Computing and Applications (NCA'05). Cambridge - MA - USA, 83-90.