Random P2P Network with O(d) Routing Distance

Shiping Chen; Kaihua Rao; Yuan Li; Lei Zhao; Tao Li; Shigang Chen

ChinaCom2008-Advances in Internet Symposium

Research Article

Random P2P Network with O(d) Routing Distance

Cite: BibTeX Plain Text

@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

Shiping Chen¹^,*, Kaihua Rao², Yuan Li², Lei Zhao², Tao Li², Shigang Chen³

1: Network Center, University of Shanghai for Science and Technology, China , School of Computer and Electrical Engineering, U. of Shanghai for Science and Technology, China
2: School of Computer and Electrical Engineering, U. of Shanghai for Science and Technology, China
3: Department of Computer and Information Science and Engineering, University of Florida, USA

*Contact email: spchen@citiz.net

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.

Keywords: P2P Computing

Published: 2008-11-21
Publisher: IEEE
Modified: 2010-05-16

: http://dx.doi.org/10.1109/CHINACOM.2008.4685001