Unstructured peer-to-peer networks: Topological properties and search performance

G.H.L. Fletcher, H.A. Sheth, K. Börner

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    33 Citations (Scopus)


    Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.
    Original languageEnglish
    Title of host publicationProceedings of the 3rd International Workshop on Agents and Peer-to-Peer Computing (AP2PC 2004), 19 July 2004, New York NY, USA
    EditorsG. Moro, S. Bergamaschi, K. Aberer
    Place of PublicationBerlin
    ISBN (Print)3-540-29755-3
    Publication statusPublished - 2004

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Unstructured peer-to-peer networks: Topological properties and search performance'. Together they form a unique fingerprint.

    Cite this