SFB 376 - Teilprojekt A2 Forschungsschwerpunkt: Peer to Peer Netzwerke

Ein Peer-to-Peer Netzwerk ist ein virtuelles Netzwerk zwischen einer Teilmenge der Knoten (der Menge der ``Peers'') eines verteilten Systems. Hierbei stellt jeder der Peers einen Teil seiner Ressourcen, wie z.B. Rechenzeit oder Speicherplatz, für allgemeine Netzwerkdienste zur Verfügung. Dieses ist ein Hauptmerkmal von Peer-to-Peer Netzwerken im Vergleich zu z.B. Client-/Server-Systemen. Prinzipiell agieren Peers sowohl als Server, in dem sie Ressourcen zu Verfügung stellen, als auch als Client, in dem sie Netzwerkdienste in Anspruch nehmen.

Ein sehr wichtiger Netzwerkdienst in Peer-to-Peer Netzwerken ist ein File-Sharing System das es den Peers ermöglicht mit Hilfe eines Schlüssels oder Namens schnell eine Kopie einer Datei innerhalb des Netzwerks zu lokalisieren. Tatsächlich besteht die Hauptaufgabe bei dem Design von Peer-to-Peer Systemen in der effizienten Implementierung dieser Suchfunktionalität.

Eine Hauptschwierigkeit besteht dabei darin, dass sich die Menge der Peers normalerweise dynamisch verändert, d.h. es kommen ständig neue Knoten zu dem virtuellen Netzwerk hinzu, während andere Knoten das Netzwerk wieder verlassen. Aus diesem Grund müssen alle Datenstrukturen so angelegt sein, dass sie ein effizientes Hinzufügen und Löschen von Peers unterstützen. Da es auch häufig vorkommt, dass ein Peer ohne vorherige Abmeldung das Netzwerk verläßt muß ein Peer-to-Peer System darüber hinaus auch über eine gewisse Fehlertoleranz verfügen.

Zusammenfassend kann man sagen dass ein Peer-to-Peer System Antworten auf die folgenden Fragen geben muß:

• Welche Peers werden über einen virtuellen Netzwerklink (Pfad im zugrundeligenden Basisnetzwerk) verbunden?
• Wie werden SEARCH- und PUBLISH-Operationen im virtuellen Netzwerk durchgeführt, um ein File-Sharing zu ermöglichen?
• Wie werden INSERT- und DELETE-Operationen implementiert, damit sich Knoten dem Netzwerk anschließen, und es auch wieder verlassen können?

• Robustheit. Das Netzwerk sollte den Ausfall einer begrenzten Anzahl an Knoten (üblicherweise ein konstanter Bruchteil der Peerknoten) verkraften können.
• Lastbalancierung. Netzwerkoperationen wie z.B. Suchen, sollten alle Peers ungefähr mit der gleichen Wahrscheinlichkeit besuchen, um Engpässe bei der nebenläufigen Ausführung vieler Operationen zu vermeiden. Zusätzlich sollten die Daten gleichmäßig über die Peers verteilt sein.
• Knotengrad. Der Grad eines Knotens innerhalb des virtuellen Netzwerks darf nicht zu groß sein, da es sonst nicht möglich wäre INSERT- und DELETE-Operationen effizient zu implementieren, da z.B. bei einer DELETE-Operation jeder Nachbar kontaktiert werden muß. Allerdings darf der Knotengrad auch nicht zu klein sein, da es sonst nicht möglich ist die Robustheit des Gesamtsystems zu gewährleisten. (Falls ein Knoten nur sehr wenige Nachbarn hat kann es leicht passieren, dass alle seine Nachbarn ausfallen. Dann wäre das virtuelle Netzwerk nicht mehr zusammenhängend.)
• Sucheffizienz. Eine Suche nach einer Datei sollte nur wenig Schritte (Hops) im virtuellen Netzwerk benötigen. Üblicherweise beträgt die Anzahl der Schritte O(log n) oder O(log²n).
• Lokalität. (wird bei den aktuellen Systemen zumeist nicht berücksichtigt) Falls es mehrere Kopien einer Datei im System gibt, sollte die Suchoperation eines Peers eine möglichst nah gelegene zurückliefern. Zusätzlich sollte die Suchoperation selbst auch keine unnötigen Wege zurücklegen; d.h. die insgesamt zurückgelegte Weglänge sollte ungefähr der Entfernung zu nächstgelegenen Kopie entsprechen.

Bei den wichtigsten, derzeitigen Peer to Peer Systemen verläuft der Netzwerkaufbau und die Zuordnung von Daten zu Knoten nach demselben, allgemeinen Prinzip. Jedes Datum und jeder Peer werden mittels einer Hashfunktion in eine Bildmenge abgebildet. Beispiele für solch eine Bildmenge sind ein Ring, ein d-dimensionaler Torus oder die Menge aller b-ren Zahlen einer bestimmten Länge. Ob zwischen zwei Peers ein virtueller Link aufgebaut wird hängt von der Entfernung bzw. Lage der Peers innerhalb der Bildmenge ab. Ein Datum wird üblicherweise dem nächstgelegenen Peer innerhalb der Bildmenge zugeordnet.

Im folgenden geben wir eine kurze Zusammenstellung der wichigsten Peer to Peer Systeme.

• CAN (siehe [RFH+01])
  Bei diesem System ist die Bildmenge ein d-dimensionaler Torus. Ein Peer ist jeweils für die Daten eines Rechtecks auf diesem Torus verantwortlich. Die Knoten haben einen Grad von d und eine Suchoperation benötigt O(d n ^1/d ) Schritte.
• Chord (siehe [SML+01])
  Die Bildmenge ist ein Ring. Ein Peer wird mit O(log n) nachfolgenden/vorhergehenden Knoten und mit O(log n) vielen weit entfernten Knoten verbunden. Ein Peer ist für alle Daten verantwortlich die in das Intervall zwischen ihm und dem nachfolgenden Peer fallen. Dies ergibt einen logarithmischen Grad und eine logarithmische Anzahl von Schritten für eine Suchoperation.
• Pastry/Tapestry (siehe [RD01] und [HKRZ02,ZKJ01])
  Bei diesen Projekten ist die Bildmenge die Menge aller b-ären Zahlen einer gewissen Länge. Das besondere ist, dass durch den Aufbau der virtuellen Links eine gewisse Lokalität gewährleistet wird. Insgesamt bekommt ein Knoten O(log n) Schritte für eine Suchoperation benötigt.
• Naor / Wieder (siehe [NW03b,NW03a])
  Diese beiden Autoren haben kürzlich einen neuen Ansatz vorgestellt, der einen optimalen Tradeoff zwischen Knotengrad und maximaler Schrittzahl einer Suchoperation erreicht. Sie erreichen für Knotengrad O(log_dn)

Unsere Ziele

Wir möchten versuchen die Erfahrung, die wir in den bisherigen Förderphasen im Bereich der Congestionminimierung gemacht haben auf den Bereich der Peer to Peer Netzwerke zu übertragen. Ziel ist die Entwicklung eines Peer to Peer Systems, dass die durch Suchoperationen und Datenzugriffe erzeugte Congestion minimiert. Die derzeitigen Verfahren, wie z.B. Tapestry, versuchen nur die Gesamtkommunikationslast innerhalb des Netzwerks gering zu halten. Der Schwerpunkt in diesem Bereich wird auf der theoretischen Analyse der entwickelten Strategien liegen.

Ein weiterer Schwerpunkt in der kommenden Antragsphase wird die Anpassung unserer Routing- und Datenmanagementstrategien an sogenannte Overlay- bzw. Peer to Peer Netzwerke bilden. In einem Overlay-Netzwerk kann man nur eine Teilmenge der physikalischen Knoten kontrollieren. Alle anderen Knoten fungieren im Prinzip als passive Router wobei sie ein vorgegebenes Protokoll (z.B. TCP/IP) benutzen.

Ein Peer to Peer Netzwerk ist ein Overlaynetzwerk bei dem die Knoten über die man Kontrolle besitzt (die sog. ``Peers'') über das Internet verteilt sind. Eine weitere Schwierigket bei derartigen Netzwerken besteht darin dass sich die Menge der Peers mit der Zeit verändert, d.h. es kommen ständig neue Knoten hinzu während andere Knoten das Netzwerk verlassen. Deshalb ist es von enormer Bedeutung, dass das gesamte Netzwerk dezentral organisiert wird, da es keinen ausgezeichneten, zentralen Knoten gibt, der fortwährend Bestandteil des Netzwerks wäre.

In der Praxis haben sich peer-to-peer file sharing Systeme (wie z.B. Gnutella oder Kazaa) innerhalb weniger Jahre zu einer der beliebtesten Internetapplikationen entwickelt. Eine Hauptaufgabe hierbei ist es eine möglichst effiziente Suche von Dateien zu unterstützen. Dafür hält in den aktuellen Systemen jeder Peer eine Routingtabelle aufrecht, die eine kleine Teilmenge von Peers, die sogenannten Nachbarn, enthält. Falls ein Peer nun eine Anfrage für eine Datei erhält, für die er nicht zuständig ist, leitet er die Anfrage an einen Nachbarn weiter, der diese Anfrage ``besser'' beantworten kann. Hierbei ist das Maß dafür wie gut ein Knoten eine Anfrage beantworten kann, die Distanz zwischen einem Hashwert des jeweiligen Knotens und einem Hashwert des Dateinamens. Durch eine geeignete Wahl der Nachbarschaftsbeziehungen und einer geeigneten Wahl der Datenverteilung kann auf diese Art und Weise ein korrekter Suchalgorithmus implementiert werden.

Ziel bei der Entwicklung von Peer to Peer Systemen ist es zum Einen die Anzahl der Nachbarn eines Knotens möglichst klein zu halten, um das Löschen und Einfügen von Peers effizient gestalten zu können. Zum Anderen ist es wichtig zu gewährleisten dass die Arbeit für das Beantworten und Weiterleiten von Suchanfragen gleichmäÂßig zwischen allen Peers verteilt wird.

Bei den bestehenden Protokollen existieren einige Hindernisse die einer guten Skalierbarkeit im Weg stehen.

• Das Hashingkonzept führt dazu dass Datenlokalität zerstört wird. Dies kann zu einer deutlichen Erhöhung der Netzwerklast durch ``unnötige'' Nachrichten führen.
• Die Routingstrategien verwenden nur einen Pfad zwischen ein Quelle/Zielpaar. Dies kann wegen der unteren Schranke von Borodin-Hopcroft zu einer sehr hohen Congestion führen.

Wir möchten die Routing- und Datenverwaltungsstrategien, die in den vergangenen Antragsphasen in diesem Teilprojekt entwickelt worden sind, auf Peer to Peer Netzwerke übertragen, um Lösungen zu erhalten deren Kommunikationsbelastung nah an die Kommunikationsbelastung einer optimalen Strategie herankommen. Um dieses zu erreichen muß eventuell vorhandene Lokalität zwischen Suchanfragen und Datenplatzierungen ausgenutzt werden. Die Peer to Peer Plattform Tapestry benutzt schon ein Verfahren das Lokalität ausnutzen kann. Dies wird allerdings dazu genutzt um die Gesamtkommunikationslast im System zu optimieren. Wir möchten, aufbauend auf unseren bisherigen Arbeiten, versuchen ein Peer to Peer System zu entwickeln, dass in der Lage ist die Congestion innerhalb des Netzwerkes zu minimieren.

Ein weiterer wichtiger Punkt im Zusammenhang mit Peer to Peer Netzwerken ist die Fehlertoleranz. Da Knoten fortwährend das Netzwerk verlassen muß gewährleistet werden, dass ein ausreichende Redundanz der Daten vorhanden ist, damit zu jederzeit auf globale Datenobjekte zugegriffen werden kann. Hierfür möchten wir Datenverteilungsstrategien entwickeln, die unter statistischen Annahmen über das Systemverhalten die Wahrscheinlichkeit eines Datenverlustes minimieren.

Kooperationen mit anderen Teilprojekten

Teilprojekt C6

Navigationshilfe: