Building a Scalable P2P Network with Small Routing Delay.

Most existing P2P networks route requests in O( kN^1/k), O(logN), O(logN/logk) hops, where N is the number of participating nodes and k is an adjustable parameter. Although some can achieve O(d)-hop routing for a constant d by tuning the parameter k, the neighbor locations however become a function of N, causing considerable maintenance overhead if the user base is highly dynamic as witnessed by the deployed systems. This paper explores the design space using the simple uniformly-random neighbor selection strategy, and proposes a random peer-to-peer network that is the first of its kind to resolve requests in d hops with a chosen probability of 1 - c, where c is a constant. The number of neighbors per node is within a constant factor from the optimal complexity O(N^1/d) for any network whose routing paths are bounded by d hops. [ABSTRACT FROM AUTHOR]