TY - JOUR
T1 - A near-optimal algorithm attacking the topology mismatch problem in unstructured peer-to-peer networks
AU - Hsiao, Hung Chang
AU - Liao, Hao
AU - Yeh, Po Shen
N1 - Funding Information:
The authors are grateful to the anonymous reviewers who have provided them with valuable comments to improve their study. This work was partially supported by the National Science Council, Taiwan, under Grant 97-2221-E-006-132 and 98-2221-E-006-096.
PY - 2010
Y1 - 2010
N2 - In an unstructured peer-to-peer (P2P) network (e.g., Gnutella), participating peers choose their neighbors randomly such that the resultant P2P network mismatches its underlying physical network, resulting in the lengthy communication between the peers and redundant network traffics generated in the underlying network. Previous solutions to the topology mismatch problem in the literature either have no performance guarantees or are far from the optimum. In this paper, we propose a novel topology matching algorithm based on the Metropolis-Hastings method. Our proposal is guided by our insight analytical model and is close to the optimal design. Specifically, we show that our proposal constructs an unstructured P2P network in which a broadcast message, originated by any node v, reaches any other node u by taking approximately the only physical end-to-end delay between v and u. In addition, our design guarantees the exponential broadcast scope. We verify our solution through extensive simulations and show that our proposal considerably outperforms state-of-the-art solutions.
AB - In an unstructured peer-to-peer (P2P) network (e.g., Gnutella), participating peers choose their neighbors randomly such that the resultant P2P network mismatches its underlying physical network, resulting in the lengthy communication between the peers and redundant network traffics generated in the underlying network. Previous solutions to the topology mismatch problem in the literature either have no performance guarantees or are far from the optimum. In this paper, we propose a novel topology matching algorithm based on the Metropolis-Hastings method. Our proposal is guided by our insight analytical model and is close to the optimal design. Specifically, we show that our proposal constructs an unstructured P2P network in which a broadcast message, originated by any node v, reaches any other node u by taking approximately the only physical end-to-end delay between v and u. In addition, our design guarantees the exponential broadcast scope. We verify our solution through extensive simulations and show that our proposal considerably outperforms state-of-the-art solutions.
UR - http://www.scopus.com/inward/record.url?scp=77953103964&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953103964&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2009.160
DO - 10.1109/TPDS.2009.160
M3 - Article
AN - SCOPUS:77953103964
VL - 21
SP - 983
EP - 997
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
SN - 1045-9219
IS - 7
M1 - 5313805
ER -