Resolving the topology mismatch problem in unstructured peer-to-peer networks

Hung Chang Hsiao, Hao Liao, Cheng Chyun Huang

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


Prior studies show that more than 70 percent of communication paths in a popular unstructured peer-to-peer (P2P) system (i.e., Gnutella) do not exploit the physical network topology, leading to the topology mismatch problem, and thus, lengthen communication between participating peers. While previous efforts in solving overlay topology matching problems do not guarantee the bounds of performance metrics (e.g., the communication delay between any two overlay peers and the broadcasting scope of any participating peer), in this paper, we present a novel topology matching algorithm that has provable performance qualities. In our proposal, each participating node creates and manages a constant number of overlay connections to other peers in a distributed manner. In rigorous performance analysis, we show that 1) the expected overlay communication delay between any two nodes in our P2P network is a constant; 2) in addition, any joining node has the exponential broadcasting scope in expectation; 3) furthermore, a participating node takes a polylogarithmic overhead to exploit the physical network locality and maintain its flooding scope. Together with extensive simulations, we present our proposal that significantly outperforms two recent solutions, i.e., THANCS and mOverlay, in terms of overlay communication latency and/or broadcasting scope.

Original languageEnglish
Pages (from-to)1668-1681
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
Publication statusPublished - 2009

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Resolving the topology mismatch problem in unstructured peer-to-peer networks'. Together they form a unique fingerprint.

Cite this