Title | ||
---|---|---|
A Near-Optimal Algorithm Attacking the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/TPDS.2009.160 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | DocType | Volume |
node u,novel topology,underlying network,p2p network,unstructured peer-to-peer networks,redundant network,near-optimal algorithm,underlying physical network,optimal design,topology mismatch problem,exponential broadcast scope,broadcast message,node v,broadcasting,graph theory,end to end delay,network topology,broadcast,metropolis hastings,routing,mobile computing | Journal | 21 |
Issue | ISSN | Citations |
7 | 1045-9219 | 5 |
PageRank | References | Authors |
0.38 | 29 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hung-Chang Hsiao | 1 | 256 | 32.34 |
Hao Liao | 2 | 51 | 5.37 |
Po-Shen Yeh | 3 | 5 | 0.72 |