Search and replication in unstructured peer-to-peer networks

Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker

Research output: Contribution to journalConference article

38 Citations (Scopus)

Abstract

Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the flooding-based query algorithm used in Gnutella does not scale; each individual query generates a large amount of traffic and large systems quickly become overwhelmed by the query-induced load. This paper explores various alternatives to Gnutella's query algorithm and data replication strategy. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's flooding method while reducing the network traffic by two orders of magnitude in many cases. We also present a distributed replication strategy that yields close-to-optimal performance.

Original languageEnglish (US)
Pages (from-to)258-259
Number of pages2
JournalPerformance Evaluation Review
Volume30
Issue number1
DOIs
StatePublished - Jan 1 2002
EventACM SIGMETRICS 2002 International Conference on Measurement and Modeling of Computer Systems - Marina Del Rey, CA, United States
Duration: Jun 15 2002Jun 19 2002

Fingerprint

Peer to peer networks
Topology

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Lv, Qin ; Cao, Pei ; Cohen, Edith ; Li, Kai ; Shenker, Scott. / Search and replication in unstructured peer-to-peer networks. In: Performance Evaluation Review. 2002 ; Vol. 30, No. 1. pp. 258-259.
@article{174e03a633024daca13cb630036d573e,
title = "Search and replication in unstructured peer-to-peer networks",
abstract = "Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the flooding-based query algorithm used in Gnutella does not scale; each individual query generates a large amount of traffic and large systems quickly become overwhelmed by the query-induced load. This paper explores various alternatives to Gnutella's query algorithm and data replication strategy. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's flooding method while reducing the network traffic by two orders of magnitude in many cases. We also present a distributed replication strategy that yields close-to-optimal performance.",
author = "Qin Lv and Pei Cao and Edith Cohen and Kai Li and Scott Shenker",
year = "2002",
month = "1",
day = "1",
doi = "https://doi.org/10.1145/511399.511369",
language = "English (US)",
volume = "30",
pages = "258--259",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

Search and replication in unstructured peer-to-peer networks. / Lv, Qin; Cao, Pei; Cohen, Edith; Li, Kai; Shenker, Scott.

In: Performance Evaluation Review, Vol. 30, No. 1, 01.01.2002, p. 258-259.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Search and replication in unstructured peer-to-peer networks

AU - Lv, Qin

AU - Cao, Pei

AU - Cohen, Edith

AU - Li, Kai

AU - Shenker, Scott

PY - 2002/1/1

Y1 - 2002/1/1

N2 - Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the flooding-based query algorithm used in Gnutella does not scale; each individual query generates a large amount of traffic and large systems quickly become overwhelmed by the query-induced load. This paper explores various alternatives to Gnutella's query algorithm and data replication strategy. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's flooding method while reducing the network traffic by two orders of magnitude in many cases. We also present a distributed replication strategy that yields close-to-optimal performance.

AB - Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network topology or data placement. However, the flooding-based query algorithm used in Gnutella does not scale; each individual query generates a large amount of traffic and large systems quickly become overwhelmed by the query-induced load. This paper explores various alternatives to Gnutella's query algorithm and data replication strategy. We propose a query algorithm based on multiple random walks that resolves queries almost as quickly as Gnutella's flooding method while reducing the network traffic by two orders of magnitude in many cases. We also present a distributed replication strategy that yields close-to-optimal performance.

UR - http://www.scopus.com/inward/record.url?scp=0036037084&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036037084&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/511399.511369

DO - https://doi.org/10.1145/511399.511369

M3 - Conference article

VL - 30

SP - 258

EP - 259

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 1

ER -