Abstract

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.