Research Article
Random P2P Network with O(d) Routing Distance
@INPROCEEDINGS{10.1109/CHINACOM.2008.4685001, author={Shiping Chen and Kaihua Rao and Yuan Li and Lei Zhao and Tao Li and Shigang Chen}, title={Random P2P Network with O(d) Routing Distance}, proceedings={ChinaCom2008-Advances in Internet Symposium}, publisher={IEEE}, proceedings_a={CHINACOM2008-AIS}, year={2008}, month={11}, keywords={P2P Computing}, doi={10.1109/CHINACOM.2008.4685001} }- Shiping Chen
Kaihua Rao
Yuan Li
Lei Zhao
Tao Li
Shigang Chen
Year: 2008
Random P2P Network with O(d) Routing Distance
CHINACOM2008-AIS
IEEE
DOI: 10.1109/CHINACOM.2008.4685001
Abstract
Most existing P2P networks route requests in O(kN^(1/k)),O(logN),O(logN/logK),or O(logN/log(logN)) 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((-lnc)^(1/2)dN^(1/d)),which is within a constant factor(-lnc)^(1/2)d from the optimal complexity O(N^(1/d)) for any network whose routing paths are bounded by d hops.
