Random P2P network with O(d) routing distance

Most existing P2P networks route requests in O(kN1/k), O(logN), O(logN/log logN ), or O(logN/log k) hops, where N is the number of participating nodes and k is an adjustable parameter. Using the simple uniformly-random neighbor selection strategy, this paper proposes a random peer-to-peer network that is the first of its kind to resolve requests in d hops and O(d) messages with a probability of 1-c, where c is a chosen constant that can be arbitrarily small. The system combines arbitrary neighbor selection, typically used only in unstructured P2P networks, with a DHT (distributed hash table) ring. It is practically attractive due to small routing delay, which does not grow with the size of the network. The number of neighbors per node is O((-ln c)frac12dN1/d), which is within a constant factor (-ln c)frac12d from the optimal complexity O(N1/d) for any network whose routing paths are bounded by d hops.