P2P Suche

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

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))
zum Vergleich: Gnutella
n = Anzahl der Knoten, Speicher pro Node O(1), Lookup O(n), Insert O(1), Background Messages O(1), Background Latency O(1)