Survey of Research towards Robust Peer-to-Peer Networks: Search Methods
RFC 4981

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 01

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