Building a scalable P2P network with small routing delay

• 摘要：

  Most existing P2P networks route requests in O( kN ^1/k ), O(log N), O(log N/log k) 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.

• 作者：

  Shiping Chen;Yuan Li;Kaihua Rao;Lei Zhao;Tao Li;式刚 陈

• 刊名：

• 在线出版时间：

  2008