P2P Suche

Einleitung

• Napster: (verteilte) zentrale Verzeichnisse

• Gnutella: Anfrage an möglichst viele Knoten ( #nachbarn^TTL )

• JXTA: Anfrage an möglichst viele Knoten

• Linda, Jini: Tuple-Spaces

• Chord: verteite Hashtabellen (DHT)

Verfahren

• Flooding mit Queries
  wie Gnutella und JXTA, Queries an alle Nachbarn mit bestimmter TTL

• Expanding Ring
  Queries an alle Nachbarn mit wachsender TTL

• Random Walk
  Queries nehmen zufällige Routen (Wege), evtl. werden mehrere zufällige Routen gleichzeitig begangen
  Optimierung durch periodische Rückfragen beim Absender

• distributed Hashtables
  in P2P Systemen bei denen die Knoten Informationen über die Nachbarschaftsbezeihungen pflegen

verteilte Hashtabellen (distributed hash tables DHT)

• Hashwert zu einem Suchbegriff: s

• Hashwert zu Knoten-Id: k

• Entfernung zwischen Knoten und Suchbegriff: d(s,k)

• z.B. Anzahl der Bits, die verschieden sind

• der Knoten mit der geringsten Entfernung zum Suchbegriff wird ausgezeichnet als Anker

• der Knoten, der ein Objekt zu dem Suchbegriff speichert, ist ein Target

• auf allen Knoten zwischen einem Target und einem Anker werden Verweise auf das Target gespeichert

• eine Suchanfrage wird in Richtung auf einen Anker geroutet

• wird ein Verweis angetroffen, ist das Objekt zum Suchbegriff gefunden und der Verweis wird zum Suchenden geroutet

• über den Verweis kann das Objekt vom Target geladen werden

• hat der Anker keinen Verweis, ist das Objekt nicht erreichbar / vorhanden

• in den Routingtabellen müssen Informationen über 'Entfernungen' zu Suchbegriffen vorhanden sein

• Systeme: Chord, Pastry, Tapestry
  n = Anzahl der Knoten, Speicher pro Node O(log(n)), Lookup O(log(n)), Insert O(log(n)), Background Messages O(1), Background Latency O(1)

• Andere Systeme: Kelips
  n = Anzahl der Knoten, Speicher pro Node O(sqrt(n)), Lookup O(1), Insert O(1), Background Messages O(log(n)), Background Latency O(log(n))