TY - JOUR
T1 - A tree-based peer-to-peer network with quality guarantees
AU - Hsiao, Hung Chang
AU - He, Chih Peng
N1 - Funding Information:
The authors thank the anonymous reviewers for their valuable feedback and Dr. Yingwu Zhu for his helpful comments on this paper. This work was partially supported by the National Science Council, Taiwan, under Grant 95-2221-E-006-095.
PY - 2008/8
Y1 - 2008/8
N2 - Peer-to-peer (P2P) networks often demand scalability, low communication latency among nodes, and low system-wide overhead. For scalability, a node maintains partial states of a P2P network and connects to a few nodes. For fast communication, a P2P network intends to reduce the communication latency between any two nodes as much as possible. With regard to a low system-wide overhead, a P2P network minimizes its traffic in maintaining its performance efficiency and functional correctness. In this paper, we present a novel tree-based P2P network with low communication delay and low system-wide overhead. The merits of our tree-based network include: $(i)$ a tree-shaped P2P network which guarantees that the degree of a node is constant in probability regardless of the system size. The network diameter in our tree-based network increases logarithmically with an increase of the system size. Specially, given a physical network with a power-law latency expansion property, we show that the diameter of our tree network is constant. $(ii)$ Our proposal has the provable performance guarantees. We evaluate our proposal by rigorous performance analysis, and validate by extensive simulations.
AB - Peer-to-peer (P2P) networks often demand scalability, low communication latency among nodes, and low system-wide overhead. For scalability, a node maintains partial states of a P2P network and connects to a few nodes. For fast communication, a P2P network intends to reduce the communication latency between any two nodes as much as possible. With regard to a low system-wide overhead, a P2P network minimizes its traffic in maintaining its performance efficiency and functional correctness. In this paper, we present a novel tree-based P2P network with low communication delay and low system-wide overhead. The merits of our tree-based network include: $(i)$ a tree-shaped P2P network which guarantees that the degree of a node is constant in probability regardless of the system size. The network diameter in our tree-based network increases logarithmically with an increase of the system size. Specially, given a physical network with a power-law latency expansion property, we show that the diameter of our tree network is constant. $(ii)$ Our proposal has the provable performance guarantees. We evaluate our proposal by rigorous performance analysis, and validate by extensive simulations.
UR - http://www.scopus.com/inward/record.url?scp=47249129857&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=47249129857&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2007.70798
DO - 10.1109/TPDS.2007.70798
M3 - Article
AN - SCOPUS:47249129857
VL - 19
SP - 1099
EP - 1110
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
SN - 1045-9219
IS - 8
ER -