Survey of Research towards Robust Peer-to-Peer Networks: Search Methods
RFC 4981
|
Document |
Type |
|
RFC - Informational
(September 2007; No errata)
|
|
Last updated |
|
2018-12-20
|
|
Stream |
|
ISE
|
|
Formats |
|
plain text
pdf
html
bibtex
|
Stream |
ISE state
|
|
(None)
|
|
Consensus Boilerplate |
|
Unknown
|
|
Document shepherd |
|
No shepherd assigned
|
IESG |
IESG state |
|
RFC 4981 (Informational)
|
|
Telechat date |
|
|
|
Responsible AD |
|
Russ Housley
|
|
Send notices to |
|
(None)
|
Network Working Group J. Risson
Request for Comments: 4981 T. Moors
Category: Informational University of New South Wales
September 2007
Survey of Research towards Robust Peer-to-Peer Networks:
Search Methods
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
IESG Note
This RFC is not a candidate for any level of Internet Standard. The
IETF disclaims any knowledge of the fitness of this RFC for any
purpose and notes that the decision to publish is not based on IETF
review apart from IESG review for conflict with IETF work. The RFC
Editor has chosen to publish this document at its discretion. See
RFC 3932 for more information.
Abstract
The pace of research on peer-to-peer (P2P) networking in the last
five years warrants a critical survey. P2P has the makings of a
disruptive technology -- it can aggregate enormous storage and
processing resources while minimizing entry and scaling costs.
Failures are common amongst massive numbers of distributed peers,
though the impact of individual failures may be less than in
conventional architectures. Thus, the key to realizing P2P's
potential in applications other than casual file sharing is
robustness.
P2P search methods are first couched within an overall P2P taxonomy.
P2P indexes for simple key lookup are assessed, including those based
on Plaxton trees, rings, tori, butterflies, de Bruijn graphs, and
skip graphs. Similarly, P2P indexes for keyword lookup, information
retrieval and data management are explored. Finally, early efforts
to optimize range, multi-attribute, join, and aggregation queries
over P2P indexes are reviewed. Insofar as they are available in the
primary literature, robustness mechanisms and metrics are highlighted
throughout. However, the low-level mechanisms that most affect
robustness are not well isolated in the literature. Recommendations
are given for future research.
Risson & Moors Informational [Page 1]
RFC 4981 Survey of Research on P2P Search September 2007
Table of Contents
1. Introduction ....................................................3
1.1. Related Disciplines ........................................6
1.2. Structured and Unstructured Routing ........................7
1.3. Indexes and Queries ........................................9
2. Index Types ....................................................10
2.1. Local Index (Gnutella) ....................................10
2.2. Central Index (Napster) ...................................12
2.3. Distributed Index (Freenet) ...............................13
3. Semantic Free Index ............................................15
3.1. Origins ...................................................15
3.1.1. Plaxton, Rajaraman, and Richa (PRR) ................15
3.1.2. Consistent Hashing .................................16
3.1.3. Scalable Distributed Data Structures (LH*) .........16
3.2. Dependability .............................................17
3.2.1. Static Dependability ...............................17
3.2.2. Dynamic Dependability ..............................18
3.2.3. Ephemeral or Stable Nodes -- O(log n) or
O(1) Hops ..........................................19
3.2.4. Simulation and Proof ...............................20
3.3. Latency ...................................................21
3.3.1. Hop Count and the O(1)-Hop DHTs ....................21
3.3.2. Proximity and the O(log n)-Hop DHTs ................22
3.4. Multicasting ..............................................23
3.4.1. Multicasting vs. Broadcasting ......................23
3.4.2. Motivation for DHT-based Multicasting ..............23
3.4.3. Design Issues ......................................24
3.5. Routing Geometries ........................................25
3.5.1. Plaxton Trees (Pastry, Tapestry) ...................25
3.5.2. Rings (Chord, DKS) .................................27
3.5.3. Tori (CAN) .........................................28
3.5.4. Butterflies (Viceroy) ..............................29
3.5.5. de Bruijn (D2B, Koorde, Distance Halving, ODRI) ....30
3.5.6. Skip Graphs ........................................32
4. Semantic Index .................................................33
4.1. Keyword Lookup ............................................34
Show full document text