Diese Erfindung bezieht sich auf eine verteilte Datenstruktur und eine Technik zur Verwendung der Datenstruktur, um mit einem Peer-To-Peer-System zu interagieren, wie auch die Verwendung der Technik bei Multicasting auf Applikationsebene.

Peer-To-Peer-Systeme (Peer-To-Peer = P2P) verwenden ein Netzwerk, das teilnehmende Maschinen verbindet, die gleiche oder ähnliche Fähigkeiten und Verantwortlichkeiten haben. Diese Systeme führen Aufgaben ohne die Koordination eines herkömmlichen Servers (oder mit einer minimalen Einrichtungs-Koordination durch einen Server) aus. 1 zeigt beispielsweise die Darstellung eines P2P-Systems 100 auf hoher Ebene. Das System 100 enthält eine Sammlung von Peer-Einheiten (102–112) mit gleichen oder ähnlichen Fähigkeiten und Verantwortlichkeiten. Bei einem Beispiel können die Peer-Einheiten (102–112) unabhängigen PC-Geräten entsprechen, die über das Internet oder ein Intranet miteinander verbunden sind. Die Peer-Einheiten (102–112) können Dateien oder andere Informationen untereinander (wie es mit dem beispielhaften Kommunikationsweg 114 gezeigt ist) ohne die Hilfe eines Servers direkt austauschen. Eine allgemeine Einführung in P2P-Systeme findet sich in D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins und Z. Xu., "Peer-To-Peer Computing" Technical Report HPL-2002-57, HP Lap, 2002.

P2P-Systeme verwenden im allgemeinen eine verteilte Hash-Tabelle (DHT), um die Speicherung und das Abrufen von Objekten in Peer-Einheiten zu erleichtern, die in den Systemen teilnehmen. Wie der Name vermuten lässt, bezieht sich eine verteilte Hash-Tabelle (DHT) auf eine Hash-Tabelle, die über mehrere Orte verteilt ist, wie etwa über mehrere Speicher, die unterschiedlichen Computergeräten zugeordnet sind. Eine verteilte Hash-Tabelle legt eine Vielzahl von DHT-Knoten fest, die entsprechende zugewiesene IDs haben. Die DHT-Knoten definieren zusammen einen abstrakten logischen DHT-Raum. Ein Objekt kann in diesen logischen DHT-Raum eingefügt oder aus diesem abgerufen werden, indem dieses Objekt einer Hash-Funktion unterzogen wird, um einen Schlüssel zu erzeugen. Dieser Schlüssel wird anschließend verwendet, um eine spezielle Zielknoten-ID im logischen DHT-Raum zu lokalisieren, die das Objekt empfangen wird, oder bei der das Objekt wiederaufgefunden werden kann. Das heißt jeder DHT-Knoten ist einem Bereich von Schlüsseln zugeordnet; ein Objekt wird einem speziellen DHT-Knoten hinzugefügt oder dort abgerufen, abhängig davon, ob der Schlüssel des Objektes in den Bereich von Schlüsseln fällt, die diesem speziellen DHT-Knoten zugeordnet sind. Im Gegensatz zu Anwendungen einer nicht verteilten Hash-Tabelle, können DHT-Knoten frei zum logischen DHT-Raum hinzukommen oder diesen verlassen (z.B. entsprechend Computergeräten, die zum P2P-System hinzukommen bzw. dieses verlassen), weshalb eine Funktionalität bereitgestellt sein muss, die sich diesen Ereignissen zuwendet.

Es wurde eine Vielfalt von DHT-Strategien entwickelt, um die Speicherung und das Abrufen von Objekten in einem P2P-System zu verwalten. 2 zeigt eine CAN-Strategie (CAN – Content Adressable Network), wie sie beispielsweise in S. Ratnasamy, P. Francis, M. Handley, R. Karp und S-Shenker, "A Scalable Content-Adressable Network", ACM SigComm 2001, San Diego, CA, USA, August 2001 beschrieben ist. Diese Strategie modelliert den logischen DHT-Raum zu einem D-dimensionalen kartesischen Raum 200. Die CAN-Strategie unterteilt den Raum 200, wenn Knoten zum DHT-Raum 200 hinzukommen. Wenn beispielsweise Knoten n1 hinzukommt, weist die CAN-Strategie den gesamten Raum 200 diesem Knoten zu. Wenn der Knoten n2 hinzukommt teilt die CAN-Strategie den Raum in zwei Hälften und ordnet jede Hälfte dem Knoten n1 bzw. n2 zu. Kommt der Knoten n3 hinzu, teilt die CAN-Strategie die rechte Hälfte in eine oberes und ein unteres Viertel, wobei das obere Viertel dem Knoten n2 und das untere Viertel dem Knoten n3 zugeordnet wird. Und wenn der Knoten n4 hinzukommt, teilt die CAN-Strategie das untere rechte Viertel in ein linkes Achtel (das dem Knoten n3 zugeordnet wird) und ein rechtes Achtel (das dem Knoten n4 zugeordnet wird). Dieser Vorgang wird sooft wiederholt, wie es notwendig ist, um den Knoten die hinzukommen oder entfernt werden, Rechnung zu tragen. Die resultierenden Unterteilungen definieren logische Räume, die verwendet werden, um Objekte in die verteilte Hash-Tabelle einzufügen und aus dieser abzurufen. Es kann gesagt werden, dass ein Knoten die Objekte "besitzt", die zu seinem Raum passen.

3 zeigt eine weitere Strategie, die CHORD genannt wird (z.B. wie es in I. Stoica, R. Morris, D. Karger, M. F. Kaashoek and H. Balakrishnan, "Chord: a Scalable Peer-To-Peer Lookup Service for Internet Applications", ACM SigComm 2001, San Diego, CA, USA, August 2001 beschrieben ist). Bei dieser Strategie wird der logische DHT-Raum als kreisförmiger Raum 300 aufgebaut. DHT-Knoten werden IDs zugeordnet und dem kreisförmigen logischen DHT-Raum 300 auf der Basis ihrer zugeordneten IDs hinzugefügt. Beispielsweise haben die beispielhaften DHT-Knoten n1, n2, n3, n4 und n5, die in 3 gezeigt sind, zugeordnete IDs, die deren "Anordnung" im kreisförmigen logischen DHT-Raum 300 regeln. Wie bei 2 teilen die DHT-Knoten den logischen DHT-Raum, wenn sie hinzugefügt werden, wodurch mehrere Teilräume oder Zonen definiert werden. Diese Zonen definieren die Objekte, die jeder Knoten "besitzt". Um beispielsweise ein Objekt in eine verteilte Hash-Tabelle einzufügen, die mit der DHT-Strategie festgelegt wird, die in 3 gezeigt ist, wird das Objekt einer Hash-Funktion unterzogen, um einen Schlüssel zu erzeugen. Das Objekt wird anschließend an dem DHT-Knoten gespeichert, der eine Zone hat, die diesem Schlüssel zugewiesen ist (z.B. an dem DHT-Knoten, der einen Bereich von Schlüsseln umfasst, die den Schlüssel des Objektes beinhalten). In beiden Fällen von 2 und 3 kann eine Vielfalt von Suchstrategien verwendet werden, um einen speziellen Knoten im P2P-System schnell zu finden. Im allgemeinen beinhalten die Suchstrategien das Ausführen zahlreicher "Sprünge" im logischen DHT-Raum, um sich dem gewünschten DHT-Zielknoten zu nähern. Normalerweise sind unterschiedliche Mechanismen vorgesehen, um diese Suche zu beschleunigen. Beispielsweise speichert jeder DHT-Knoten bei der CHORD-Strategie die IDs eines Satzes anderer DHT-Knoten. Diese andern IDs können auf exponentielle Art und Weise zunehmen, wodurch sogenannte "Finger" eingerichtet werden, die den logischen Raum sondieren. Dadurch kann der Suchvorgang einen gewünschten DHT-Knoten mit einer geringen Anzahl von Sprüngen schnell lokalisieren.

2 und 3 geben lediglich eine Übersicht zweier beispielhafter bekannter DHT-Routing-Strategien einer höheren Ebene an. Es gibt zahlreiche andere Strategien. Beispielsweise ist eine weitere hinlänglich bekannte Routing-Strategie die PASTRY-Routing-Strategie, wie sie in A. Rowstron and P. Druchel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-To-Peer Systems" 18. FIFP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Deutschland, November 2001 beschrieben ist.

Die Druckschrift "SOMO: Self-Organized Metadata Overlay for Ressource Management in P2P DHT", Z. Zhang et. al, Springer Verlag 2003 beschreibt den Aufbau eines selbstorganisierten Metadaten-Overlay auf einem strukturierten P2P-DHT in Top-Down-Manier.

P2P-Systeme bieten gegenüber herkömmlichen Client-Server-Strategien zahlreiche Vorteile. Beispielsweise verfügen P2P-Systeme über die Fähigkeit, sich ohne zentrale Koordination automatisch und frei zu erweitern und zu verkleinern. Dieser Mangel einer überwachenden Koordination stellt jedoch auch zahlreiche Herausforderungen. Beispielsweise kann es erwünscht sein, dass sich das P2P-System konzertiert verhält, um eine bestimmte umfassende Funktion auszuführen. Unter Umständen kann es erwünscht sein, Daten von den Teilnehmern des P2P-Systems zu sammeln. Oder es kann erwünscht sein, Informationen unter den Teilnehmern im P2P-System zu verteilen. Beim Client-Server-Ansatz kann ein Server einfach seine Clients pollen, um Informationen von seinen Clients zu sammeln, oder Informationen zu seinen Clients rundzusenden, um Informationen zu seinen Clients zu verteilen. Die Datensammlung und -verteilung wird in einem P2P-System jedoch zunehmend problematisch, da es aus einem losen Zusammenschluss miteinander verbundener Peers besteht, die frei kommen und gehen können. Das Hinzufügen einer zentralisierten herkömmlichen Berichtsfunktionalität kann die Wirkung haben, dass das P2P-System verkompliziert wird und somit seine Flexibilität und Brauchbarkeit verringert wird.

Somit gibt nach dem Stand der Technik beispielsweise den Bedarf an einer wirkungsvollen Strategie zur Interaktion mit einer P2P-DHT, die beispielsweise das Sammeln von Daten von ihren Teilnehmern und das Verteilen von Informationen auf ihre Teilnehmer gestattet. Darüber hinaus ist es gewünscht, die P2P-DHT wirkungsvoll zu organisieren und mit ihr bei Vorgängen zu interagieren, die von ihrer Effizienz profitieren, wie etwa bei einer Multicasting-Session auf Applikationsebene.

Gemäß einer beispielhaften Anwendung ist ein Verfahren zum Aufbauen eines Daten-Overlay beschrieben. Das Verfahren enthält das Bereitstellen einer verteilten Hash-Tabelle (DHT), die das Einfügen und Abrufen von Objekten in und aus dem Peer-To-Peer-System regelt, wobei die verteilte Hash-Tabelle einen logischen Raum enthält, der eine Vielzahl von DHT-Knoten beinhaltet, die eine dazugehörige Vielzahl von DHT-Zonen haben. Das Verfahren umfasst zudem das Aufbauen des Daten-Overlays als Datenstruktur auf dem logischen Raum der verteilten Hash-Tabelle durch Zuordnen von Objekten in der Datenstruktur auf DHT-Knoten und durch Einrichten von Verknüpfungen zwischen den Objekten in der Datenstruktur. Der Daten-Overlay hat die Topologie eines Baums, wobei der Baum über Baumknoten verfügt, die entsprechenden DHT-Knoten zugeordnet sind. Jeder Baumknoten hat eine ihm zugeordnete entsprechende Baumknotenzone, die einem Teil des logischen Raums der verteilten Hash-Tabelle entspricht.

Maschinen werden auf den logischen Raum der DHT abgebildet. Jede Maschine entspricht einer oder mehreren der Baumknotenzonen. Jede Maschine wählt als ihren repräsentativen Knoten aus der einen oder den mehreren Baumknotenzonen, die ihr entspricht/entsprechen, den Baumknoten, der der größten Baumknotenzone entspricht. Jeder repräsentative Knoten wählt als seinen Elternknoten einen weiteren repräsentativen Knoten, der der repräsentative Knoten für eine angrenzende der Baumknotenzone ist, die größer ist.

Nachdem die Maschinen auf den logischen Raum der DHT abgebildet worden sind, können Metadaten Metadaten an jeder Maschine erfassen. Die erfassten Metadaten können von jeder Maschine zu ihrem repräsentativen Knoten gesendet werden, wobei diese repräsentativen Knoten die auf diese Weise empfangenen Metadaten zu ihrem jeweiligen Elternknoten senden können. Die Metadaten, die am höchsten Knoten in einem Baum (z.B. dem Wurzelknoten) empfangen werden, können verarbeitet und zu jeder Maschine über die entsprechenden Elternknoten und repräsentativen Knoten gesendet werden. Die Metadaten können beispielsweise Informationen sein, die den Betrieb jeder Maschine betreffen, und die verarbeiteten Metadaten können Anweisungen sein, die den Betrieb jeder Maschine steuern.

Ein umfangreicheres Verständnis der Anwendungen kann unter Bezugnahme auf die folgenden detaillierte Beschreibung in Verbindung mit den beiliegenden Zeichnungen gewonnen werden.

1 zeigt ein herkömmliches Peer-To-Peer-System (P2P-System).

2 zeigt eine herkömmliche CAN-Routing-Strategie.

3 zeigt eine herkömmliche CHORD-Routing-Strategie.

4 zeigt einer herkömmliche Technik zum Verknüpfen von zwei Objekten einer Datenstruktur im Zusammenhang einer lokalen Maschinenumgebung.

5 zeigt eine beispielhafte Technik zum Verknüpfen von zwei Objekten einer Datenstruktur in einer P2P-Umgebung einer verteilten Hash-Tabelle (DHT), bei der zwei Objekte zwei unterschiedlichen Knoten in der P2P-DHT-Umgebung zugeordnet werden und bei der die Verknüpfungstechnik die Basis eines Daten-Overlays bildet, der sich "auf" der DHT befindet.

6 zeigt eine einfache P2P-DHT, die einen Ring, eine Zone und eine Basis-Routingtabelle enthält, die r Nachbarn auf jeder Seite aufzeichnet, wobei ein Hashvorgang den DHT-Knoten Zonen zuordnet.

7 zeigt eine beispielhafte Baumstruktur, die mit Hilfe des Konzeptes eines Daten-Overlays aus 5 aufgebaut ist, wobei die Baumstruktur als Selbstorganisierender Metadaten-Overlay (SOMO) bezeichnet wird.

8a–8c zeigen progressive schematische Ansichten eines Vorgangs zum Aufbauen eines SOMO von unten nach oben, wobei 8a das Aufbauen eines logischen Baums als einen Bezugsrahmen zeigt, 8b das Finden repräsentativer virtueller Knoten und 8c ein Abbilden des logischen Baumes auf physikalische Maschinen zeigt.

9a–9c zeigen fortschreitende schematische Ansichten eines Eigenskaliervorgangs zum Wiederherstellen des von unten nach oben aufgebauten SOMO, der in 8c gezeigt ist, wobei 9a den von unten nach oben aufgebauten SOMO zeigt, der in 8c dargestellt ist, 9b das Hinzufügen einer physikalischen Maschine zeigt, für die ein entsprechender virtueller Knoten im logischen Baum gefunden wird, und 9c ein Abbilden des korrigierten logischen Baums auf sämtliche physikalischen Maschinen zeigt.

10a zeigt die Kombination von Fähigkeiten einer DHT für die Pool-Bildung von Ressourcen und einen von unten nach oben aufgebauten SOMO, um gemeinsam einen Ressourcen-Pool herzustellen.

10b zeigt eine beispielhafte Anwendung der SOMO-Baumstruktur von 7 auf die Sammlung von Informationen von und die Verteilung von Informationen auf die Teilnehmer des P2P-Systems.

11a zeigt eine schematische Anordnung für Multicasting auf Applikationsebene, und 11b zeigt eine Verbesserung an der Anordnung aus 11a durch Verwendung eines Helferknotens in einem Ressourcen-Pool, wobei Kreise ursprüngliche Mitglieder einer Multicast-Session auf Applikationsebene repräsentieren und ein Quadrat einen verfügbaren Peer zeigt, der eine hohe Ordnung hat.

12 zeigt eine SOMO-Berichtsstruktur zur Zeitplanung einer einzelnen Multicast-Session auf Applikationsebene, wobei jeder Knoten seine Netzwerkkoordinaten wie auch seine Bandbreitenbegrenzungen in seinem Bericht für den SOMO veröffentlicht.

13 zeigt einen beispielhaften Computer, der verwendet wird, um einen Teilnehmer eines P2P-Systems zu implementieren, wobei das P2P-System einen Daten-Overlay enthält, der auf dessen DHT aufgebaut ist.

Es werden dieselben Ziffern im Verlauf der Beschreibung und in den Zeichnungen verwendet, um ähnliche Bestandteile und Merkmale zu kennzeichnen. Ziffern der Folge 100 beziehen sich auf Merkmale, die ursprünglich in 1 zu finden sind, Ziffern der Folge 200 beziehen sich auf Merkmale, die ursprünglich in 2 zu finden sind, Ziffern der Folge 300 beziehen sich auf Merkmale, die ursprünglich in 3 zu finden sind, usw..

Die hier beschriebenen Strategien betreffen eine Datenstruktur, die "auf" einer verteilten Hash-Tabelle (DHT) aufgebaut ist, die in einem Peer-To-Peer-(P2P-)System verwendet wird. Der Begriff Peer-To-Peer-(P2P-)System kann eine beliebige Zwischenverbindung von Teilnehmern beschreiben, bei der die Teilnehmer direkt mit Anderen interagieren können, wie etwa ein Zwischenverbindungsnetzwerk 100, das in 1 dargestellt ist. Bei einer Anwendung verlangt das P2P-System nicht die Unterstützung von serverartigen Einheiten. Die Teilnehmer können eine beliebige Art von Einheit beinhalten, wie etwa PCs, Laptop-Computer, PDAs, applikationsspezifische Rechenvorrichtungen und dergleichen. Die Teilnehmer können miteinander über eine beliebige Kombination einer Routing-Infrastruktur kommunizieren, wie etwa über drahtgebundene und/oder drahtlose Kommunikations-Routing-Machanismen, unterschiedliche Router, Gateways, etc.. Zudem können die Teilnehmer miteinander durch eine beliebige Kombination von Netzwerkprotokollen, wie etwa TCP/IP (wie es beispielsweise durch das Internet oder ein Intranet bereitgestellt wird), kommunizieren.

Allgemeiner gesagt kann eine beliebige der Funktionen, die hier beschrieben sind, unter Verwendung von Software, Firmware (z.B. unveränderte logische Schaltkreise), manueller Verarbeitung oder einer Kombination aus diesen Anwendungen eingesetzt werden. Der Begriff "Logik" oder "Modul", wie er hier verwendet wird, steht allgemein für Software, Firmware oder eine Kombination aus Software und Firmware. Für den Fall einer Softwareanwendung repräsentiert der Begriff "Logik" oder "Modul" beispielsweise Programmcode, der festgelegte Aufgaben durchführt, wenn er auf einer Verarbeitungsvorrichtung oder Verarbeitungsvorrichtungen (z.B. einer CPU oder CPUs) ausgeführt wird. Der Programmcode kann in einer oder mehreren von einem Computer lesbaren Speichervorrichtung(en) gespeichert sein.

Diese Beschreibung enthält folgendes: Abschnitt A beschreibt eine allgemeine Daten-Overlay-Struktur, die "auf" einer P2P-DHT aufgebaut werden kann; Abschnitt B beschreibt einen Selbstorganisierenden Metadaten-Overlay oder "SOMO"; Abschnitt C beschreibt die Verwendung des SOMO zum Erfassen und Verteilen von Informationen in einem P2P-System; Abschnitt D beschreibt ALM (Application Level Multicasting – Multicasting auf Applikationsebene) mit Hilfe der P2P-DHT; Abschnitt E beschreibt die Verwendung eines beispielhaften P2P-Teilnehmers, der bei dem Typ des P2P-DHT-Systems mit ALM verwendet werden kann, wie es in den Abschnitten A–D beschrieben ist.

Ein Daten-Overlay ist eine Datenstruktur, die aus Objekten besteht. Die Datenstruktur wird "auf" einer verteilten Hash-Tabelle implementiert. Als Hintergrund stellt die DHT eine Technik zum Einfügen von Objekten in und zum Abrufen von Objekten aus einem verteilten Speicher bereit, der durch ein P2P-System bereitgestellt ist. Sie führt diese Aufgabe durch Definieren einer Sammlung von DHT-Knoten innerhalb eines logischen DHT-Raumes aus. Das heißt, die DHT-Technik ordnet jeden DHT-Knoten einem vorbestimmten Abschnitt des logischen DHT-Raumes zu, der als die "Zone" des DHT-Knotens bezeichnet wird. Bei der CHORD-Technik kann die Zone eines speziellen DHT-Knotens als die Spanne interpretiert werden, die zwischen diesem speziellen DHT-Knoten und seinem benachbarten Knoten in einem kreisförmigen logischen DHT-Raum (wie etwa in 3 gezeigt) definiert ist. Ein Objekt wird gespeichert, indem es einem Hashvorgang unterzogen wird, um einen Schlüssel zu erzeugen, und anschließend dieser Schlüssel verwendet wird, um das Objekt einer speziellen Knoten-ID im logischen DHT-Raum zuzuordnen. Das Objekt wird aus dem logischen DHT-Raum in einer entsprechenden Art und Weise abgerufen. Diese zugeordneten Zonen führen schließlich eine Abbildung auf reale Maschinen aus (z.B. Computergeräte und zugeordnete Dateispeichersysteme), wenngleich es keine Eins-zu-Eins-Beziehung zwischen Knoten und Maschinen geben muss.

Der Daten-Overlay wird "auf" der DHT in dem Sinne implementiert, dass dessen Objekte Knoten im logischen DHT-Raum zugeordnet sind. Zudem geht eine Applikation von einem Objekt zu einem weiteren Objekt in der Datenstruktur des Overlays über (führt ein Routing aus), indem sie die zugrundeliegenden Protokolle und Dienste der P2P-DHT verwendet. Insbesondere sei für einen Bezugsrahmen der herkömmliche Fall von 4 betrachtet, die die Umgebung 402 einer einzelnen Maschine zeigt. In dieser Umgebung 402 enthält eine Datenstruktur zwei Objekte a 404 und b 406, die im Speicher eingesetzt sind, der von einer einzelnen Maschine bereitgestellt ist. Ein Objekt repräsentiert im weiten Sinn eine beliebige Einheit eines beliebigen Typs von Informationen; in einem herkömmlichen Fall kann ein Objekt beispielsweise einem Datenbankeintrag, z.B. einem Dokument, entsprechen. Im Beispiel von 4 enthält das Objekt a 404 einen Verweis 408, der auf Objekt b Bezug nimmt.

Im Gegensatz dazu zeigt 5 den Einsatz eines Daten-Overlays im Zusammenhang einer P2P-DHT-Umgebung 502. Da in dieser Umgebung 502 die Objekte "auf" dem DHT-Knoten-Gerüst aufgebaut sind, das durch die DHT bereitgestellt wird, bilden einzelne Knoten im logischen DHT-Raum den "Host" für die Objekte im Daten-Overlay. Beispielsweise ist der DHT-Knoten x 504 der Host für das Objekt a 506 und der DHT-Knoten y 508 der Host für das Objekt b 510. Bei diesem Beispiel bezieht sich das Objekt a 506 auf das Objekt b 510. Im allgemeinen kann das Objekt a 506 mit dem Objekt b 510 verknüpft werden, indem der Schlüssel gespeichert wird, der verwendet wird, um auf das Objekt b 510 zuzugreifen. Dieser Schlüssel wird eingerichtet, wenn das Objekt b 510 erzeugt wird. Für den Fall von 5 enthält das Bezugsschema jedoch zwei Felder. Ein erstes Feld 510 enthält eine feste Adresse, die von Objekt a 506 auf Objekt b 510 verweist. Dieses Feld wird als a.foo.key bezeichnet. Ein zweites Feld 510 enthält einen Soft-State-Bezug, der den letzten bekannten Knoten (z.B. Knoten y 508) identifiziert, der der Host für Objekt b 510 ist. Dieses Feld wird als a.foo.host bezeichnet. Das zweite Feld 514 dient somit als Routing-Abkürzung für einen Zugriff auf Objekt b 510.

Da die Knoten des Daten-Overlays über mehrere DHT-Knoten verteilt sein können, kann der Daten-Overlay an sich als verteilte Datenstruktur betrachtet werden. Obwohl die Datenstruktur verteilt ist, kann es gewünscht sein, sie derart zu speichern, dass ihre Objekte geografisch nicht unnötig weit zerstreut sind. Dies kann dadurch erreicht werden, dass die Schlüssel von a 506 und b 510 so erzeugt werden, dass sie dicht beieinander liegen. Dadurch erhöht sich die Wahrscheinlichkeit, dass das P2P-DHT-System diese Schlüssel mit demselben Knoten im P2P-System oder in eng aufeinander bezogene Knoten im P2P-DHT-System zuordnet.

Der Daten-Overlay stellt zudem eine Sammlung von Primitiven bereit, die verwendet werden, um Verweise und Objekte in seiner Datenstruktur zu verändern. Insbesondere beinhalten diese Primitive eine Prozedur (setref) zum Einrichten eines Bezuges von Objekt a zu einem weiteren Objekt b, eine Prozedur (dref) zum Zurückführen eines Objekt, auf das durch Objekt a verwiesen wurde, und eine Prozedur zum Löschen (delete) eines Objektes, auf das durch Objekt a verwiesen wurde.

Da der Daten-Overlay auf dem DHT-System aufgebaut ist, nutzen dessen Primitive die Dienste der DHT. Beispielsweise können die Primitive einen DHT_insert-Dienst zum Einfügen eines Objektes in den logischen DHT-Raum nutzen. Die Primitive können einen DHT_lookup-Dienst verwenden, um eine vorbestimmte DHT-Routing-Prozedur zu nutzen und so ein Objekt auf Basis seines Schlüssels im logischen DHT-Raum zu finden (wie etwa die exponentiale Finger-Suchstruktur, die von CHORD verwendet wird). Und die Primitive können zudem eine DHT_direct-Prozedur verwenden, um direkt auf ein Objekt zuzugreifen, wenn der DHT-Knoten, der das Objekt speichert, im voraus bekannt ist. Mit anderen Worten umgeht DHT_direct die normale DHT_lookup-Routing-Prozedur und sucht direkt den Knoten, der der Host für das Objekt ist, dessen Schlüssel gegeben ist. Sowohl DHT_lookup als auch DHT_insert führen als Nebeneffekt den DHT-Knoten in der DHT zurück, die momentan der Host für das Zielobjekt ist.

Der Daten-Overlay kann unter Verwendung seines zugrundeliegenden DHT-Dienstes implementiert werden, indem abgeändert wird, welche Bibliotheksroutinen auch immer verwendet werden, um Objekte zu erzeugen, so dass diese Routinen ebenfalls die Verweise, die oben beschrieben wurden, als Attribute der Objekte einrichten. Die Bibliotheksroutinen sollten zudem abgeändert werden, um sich den oben beschriebenen Primitiven zum Einstellen eines Bezuges anzupassen, ein Objekt zurückzuführen, auf das durch einen Bezug verwiesen wurde, und ein Objekt zu löschen, auf das durch einen Bezug verwiesen wurde.

Es gibt eine Reihe von Vorteilen dafür, den Daten-Overlay auf einer DHT aufzubauen. Beispielsweise ist die DHT darauf ausgelegt, sich selbst zu organisieren, wenn DHT-Knoten dem logischen DHT-Raum hinzugefügt und aus diesem gelöscht werden (was sich auf reale Maschinen bezieht, die zu einem P2P-System hinzukommen oder dieses verlassen). Die DHT ist zudem derart beschaffen, dass sie sich selbst in Erwiderung darauf "heilt" (wiederherstellt), dass DHT-Knoten dem logischen DHT-Raum hinzugefügt und aus diesem gelöscht werden (wie etwa durch Wiedereinrichtung von Verknüpfungen zwischen Knoten, Übertagen von Objekten zwischen Knoten, etc.). Dadurch, dass er auf der DHT implementiert ist, kann der Daten-Overlay zudem die Merkmale der Selbstorganisation und der Selbstwiederherstellung annehmen. Insbesondere kann der Daten-Overlay so beschaffen sein, dass er im selben Umfang selbstorganisierend und selbstwiederherstellend ist wie die zugrundeliegende DHT.

Weiterhin können unterschiedliche Applikationen portiert werden, um auf einer P2P-DHT zu laufen, wodurch diesen Applikationen die Illusion eines unbegrenzten Speicherplatzes gegeben ist (wie etwa, dass der Eindruck eines einzigen Ressourcen-Pools gegeben ist, der eine große Größe hat, die die Knoten des logischen DHT-Raumes umfasst). Dieser Speicherplatz kann umfangreich Speicher-Heaps von Maschinen enthalten, die am P2P-DHT-System beteiligt sind. Die Host-Routing-Abkürzung (z.B. a.foo.host) bestimmt das Verhalten von Applikationen, die den Daten-Overlay unabhängig vom zugrundeliegenden DHT-System nutzen.

In einer DHT wird von einem sehr großen logischen Raum (z.B. 160 Bits) ausgegangen. Knoten kommen zu diesem Raum mit zufälligen IDs hinzu und teilen somit den Raum gleichmäßig. Die ID kann beispielsweise ein MD5-Hash über einer IP-Adresse eines Knotens sein. Ein geordneter Satz von Knoten gestattet es, dass eine für einen Knoten verantwortliche Zone strikt definiert ist. Es seien p und q der Vorgänger bzw. der Nachfolger eines Knotens x. Eine Definition einer Zone des Knotens ist einfach der Zwischenraum zwischen der ID seiner unmittelbaren Vorgänger-ID (nicht inklusiv) und einer eigenen ID. Mit anderen Worten: zone(x) ≡ (ID(p), ID(x)].

6 zeigt eine Art, eine DHT als logischen Raum zu betrachten, wobei jeder Knoten eine logische Position im logischen Raum belegt und der logische Raum unterteilt ist. Somit muss jeder Knoten einige wenige seiner angrenzenden Nachbarn im Gedächtnis behalten, um den logischen Raum kohärent zu gestalten. Eine neue Maschine nimmt eine beliebige ID und kommt zur DHT hinzu. Die neue Maschine kontaktiert beliebige der Knoten, sucht nach einer Position und teilt anschließend den logischen Raum für sich selbst, so dass sich der Baum, selbst organisiert und selbst wiederherstellt. Der sich selbst wiederherstellende Aspekt kommt zum Tragen, wenn eine Maschine ausscheidet, da ihr Ausscheiden von ihren angrenzenden Nachbarmaschinen beobachtet wird, wobei dieses Ausscheiden erfasst wird, wenn die ausscheidende Maschine nicht länger einen "Heartbeat" sendet, um ihre Gegenwart zu kennzeichnen. Anschleißend kann eine benachbarte Maschine aufgenommen werden.

6 zeigt zudem im wesentlichen, wie konsistent der Hashvorgang Zonen den DHT-Knoten zuweist, wobei ein Ring, eine Zone und eine Basis-Routingtabelle verwendet werden. Um den Ring gegen die dynamische Kraft des Systems unempfindlich zu machen, zeichnet jeder Knoten r Nachbarn auf jeder Seite in der rudimentären Routing-Tabelle auf, die allgemein als Blattsatz bekannt ist. Nachbarn kommunizieren periodisch miteinander, um ihre Gegenwart zu kennzeichnen (z.B. "Heartbeats") wie auch ihre Routing-Tabellen zu aktualisieren, wenn ein Knoten hinzukommt/ausscheidet oder wenn Ereignisse auftreten. Dieser Basisring, gezeigt in 6, ist eine einfache P2P-DHT. Wenn man sich vorstellt, dass die Zone ein Hash-Bucket in einer herkömmlichen Hash-Tabelle ist, dann ist der Ring eine DHT. Mit einem gegebenen Schlüssel im Raum kann man immer herausfinden, welcher Knoten verantwortlich ist. Die Suchleistung ist O(N) bei diesem einfachen Ringaufbau, wobei N die Zahl der Knoten im System ist.

Ein Algorithmus, der auf dem oben beschriebenen Konzept aufgebaut ist, erzielt ein O(logN)-Verhalten entweder mit O(logN)-Zuständen oder sogar konstanten Zuständen (d.h. die Routing-Tabelleneinträge). Repräsentative Systeme beinhalten das CAN-Unterteilungsschema, das CHORD-Unterteilungsschema und dergleichen. Das gesamte System einer DHT ist selbstorganisierend mit einem Overhead in einer Größenordnung von O(logN). Zudem ist die DHT die Virtualisierung eines Raumes, bei dem sowohl Ressourcen als auch andere Einheiten (wie etwa Dokumente, die in der DHT gespeichert sind) nebeneinander existieren.

Der oben beschriebene Daten-Overlay stellt ein Gerüst zum Aufbauen einer willkürlichen Datenstruktur auf einer DHT bereit. Die Datenstruktur enthält eine Vielzahl von Objekten, die Knoten in der Datenstruktur bilden. Diese Datenstruktur kann eine beliebige Art einer Topologie durch Verknüpfen der Knoten miteinander auf unterschiedliche Weise annehmen. Zudem kann die Datenstruktur unterschiedliche Funktionen in Abhängigkeit der Operationen einsetzen, die ihren einzelnen Knoten zugeordnet sind. Der folgende Abschnitt beschreibt ein Beispiel des Daten-Overlays, der als selbstorganisierender Metadaten-Overlay oder kurz "SOMO" bezeichnet wird.

Die SOMO-Datenstruktur ist derart aufgebaut, dass sie die Topologie einer Baumstruktur annimmt. Die SOMO-Baumstruktur hat einen Wurzel-Knoten. Der Wurzel-Knoten kann einen oder mehrere Nachfolger haben, die ihrerseits ihre eigenen jeweiligen Nachfolger haben. Die Endknoten der SOMO-Baumstruktur werden als Blattknoten bezeichnet. Die Blattknoten sind entsprechenden DHT-Knoten im logischen DHT-Raum des P2P-Systems zugeordnet.

Wie es später im folgenden detaillierter beschrieben wird, besteht eine Funktion der SOMO-Baumstruktur darin, Metadaten aus den DHT-Knoten zu extrahieren (was letztendlich das Extrahieren von Daten aus den Maschinen beinhaltet, die das P2P-System implementieren) und diese Metadaten nach oben durch den SOMO-Baum zum Wurzel-Knoten der SOMO-Baumstruktur weiterzuleiten. Eine Applikation kann anschließend diese Metadaten lesen und eine bestimmte Aktion auf der Basis dieser Metadaten ausführen. (Metadaten bezeichnen im allgemeinen eine beliebige Art von Informationen, die den Operationen zugeordnet sind, die vom P2P-System ausgeführt werden, wie etwa Informationen die das Verhalten von Maschinen betreffen, die das P2P-System beinhalten). Die SOMO-Baumstruktur kann zudem dazu verwendet werden, Informationen vom Wurzel-Knoten der SOMO-Baumstruktur abwärts zu den DHT-Knoten und zugehörigen Maschinen innerhalb des P2P-Systems zu verteilen. Somit kann die SOMO-Baumstruktur, allgemein gesagt, die Rolle der Datenerfassung (z.B. Anhäufung) und der Datenrundsendung übernehmen.

7 zeigt eine beispielhafte SOMO-Baumstruktur 702, die auf einem zugrundeliegenden logischen DHT-Raum 704 aufgebaut ist. Der logische DHT-Raum 704 ist in eine Zahl von Zonen unterteilt, wie etwa die beispielhafte Zone 706 und die beispielhafte Zone 708. Jede Zone enthält einen ihr zugeordneten DHT-Knoten, wie etwa den beispielhaften DHT-Knoten 710. Die DHT kann den logischen DHT-Raum 704 in Zonen gemäß einer beliebigen Technik unterteilen, wie etwa den Techniken, die durch das CAN-Unterteilungsschema, das CHORD-Unterteilungsschema, das PASTRY-Unterteilungsschema oder eine beliebige andere Art eines DHT-Unterteilungsschemas bereitgestellt sind. Bei Verwendung des CHORD-Unterteilungsschemas kann der logische DHT-Raum 704 beispielsweise als ein Ring definiert werden, der über Knoten verfügt, die an unterschiedlichen Orten um diesen herum verteilt sind, wobei die Zonen den Spannen entsprechen können, die benachbarte, angrenzende DHT-Knoten auf dem Ring trennen.

Die SOMO-Baumstruktur 702 enthält einen oder mehrere Knoten, die hier als "SOMO-Knoten" bezeichnet werden, um sie von DHT-Knoten zu unterscheiden. Jeder SOMO-Knoten ist durch das Symbol s repräsentiert. Die beispielhafte SOMO-Baumstruktur 702, die in 7 gezeigt ist, enthält SOMO-Knoten s 712–726. Die Knoten s 712–726 bilden eine umgekehrte Baumstruktur. Das heißt ein Wurzel-Knoten 712 verzweigt in einen Nachkommens-Knoten 714 und einen Nachkommens-Knoten 716. Diese Nachkommens-Knoten haben ihre eigenen jeweiligen Nachkommens-Knoten; beispielsweise enthält der Nachkommens-Knoten 714 den Nachkommens-Knoten 718 und den Nachkommens-Knoten 720. Wenngleich die gesamte Struktur der beispielhaften SOMO-Baumstruktur 702 in 7 verkürzt ist, um die Darstellung und Erläuterung zu vereinfachen, endet die SOMO-Baumstruktur 702 schließlich in Blattknoten (z.B. den Blattknoten 722, 724, 726), die in entsprechende DHT-Knoten im logischen DHT-Raum 704 gepflanzt sind. Im allgemeinen sind die Verknüpfungen zwischen den SOMO-Knoten in der SOMO-Baumstruktur 702 in 7 mit Punktlinien dargestellt, die die SOMO-Knoten miteinander verbinden; diese Verknüpfungen können unter Verwendung eines Bezugsschemas eingesetzt werden, das im Abschnitt "Daten-Overlay" oben beschrieben ist.

Jeder SOMO-Knoten s hat eine ihm zugeordnete Zone. Beispielsweise enthält der Wurzel-SOMO-Knoten 712 eine Zone 728, die den gesamten logischen DHT-Raum 704 überspannt. Der Nachkommens-Knoten 716 enthält eine Zone 730, die die Hälfte der Zone 728 des Wurzel-Knotens 712 überspannt. Ein weiterer Nachkommens-Knoten 720, der in der SOMO-Baumstruktur 702 tiefer angeordnet ist, hat eine Zone 732, die ein Viertel der Zone 728 des Wurzel-Knotens 712 ist. Demzufolge führen nachfolgende Knoten s, die zur Hierarchie der SOMO-Baumstruktur 702 hinzugefügt werden, zu einer allmählich feineren Unterteilung der Zone 728 des Wurzel-Knotens 712. Zudem wächst die Hierarchie der SOMO-Baumstruktur 702 "höher" für jene Bereiche des logischen DHT-Raumes 704, die eine feinere (das heißt, dichtere) Unterteilung des Raumes 704 aufweisen. Im allgemeinen repräsentiert 7 die Zonen, die einzelnen SOMO-Knoten zugeordnet sind, durch horizontale Pfeile, die die Länge der jeweiligen Zonen der SOMO-Knoten überspannen. Ein DHT-Knoten, der der Host eines speziellen SOMO-Knotens s ist, ist als DHT_host(s) ausgedrückt.

Wie es oben erläutert wurde, sollte eine DHT zur Vervollständigung eines P2P-Ressourcen-Pools um eine systemeigene Überwachungs-Infrastruktur erweitert werden, da es bei einem großen System nicht praktikabel ist, sich auf einen externen Überwachungsdienst zu verlassen. Eine derartige Infrastruktur muss ein paar Schlüsseleigenschaften erfüllen: (1) sie muss im selben Umfang selbstorganisierend sein wie die Host-DHT; (2) sie muss vollständig verteilt und selbstwiederherstellend sein; und muss (3) im Bezug auf die Metadaten die erfasst und verteilt werden, so präzise wie möglich sein. Der SOMO, der hier vorgeschlagen ist, ist von unten nach oben aufgebaut, wie es im folgenden beschrieben wird.

Die Überwachungsinfrastruktur kann eine Reihe von Topologien annehmen. Was den Ressourcen-Pool angeht, ist eine der wichtigsten Funktionalitäten die Anhäufung. Somit ist der SOMO ein Baum des Ordnung k, dessen Blätter in jedem DHT-Knoten gepflanzt sind. Informationen werden von unten erfasst und breiten sich zur Wurzel aus. Somit kann man den SOMO so bezeichnen, dass er eine "zusammenlaufende Sendung" von den Blättern zur Wurzel und anschließend (wahlweise) eine Rundsendung wieder zurück abwärts zu den Blättern ausführt. Sowohl die Erfassungs- als auch die Verteilungsphase sind O(log_kN)-gebunden, wobei N die Gesamtzahl von Objekten ist. Jede Operation im SOMO beinhaltet nicht mehr als k – 1 Interaktionen, wodurch er vollständig verteilt ist. Durch Verwendung des Prinzips des Soft-State können Daten in O(log_kN)-Zeit wiedergewonnen werden. Der SOMO-Baum organisiert und stellt sich selbst innerhalb dieser Zeitgrenze wieder her. In gewisser Weise kann der SOMO als reagierender "Nachrichtensender" bezeichnet werden, dessen Aufbau und Verarbeitung von sämtlichen Knoten gemeinsam genutzt wird. Es ist die zeitgerechte, globale "Nachricht", die die Illusion des Ressourcen-Pools erzeugt.

Die Grundidee des SOMO besteht darin, dass, anstelle mit jeder einer Vielzahl von einzelnen Maschinen zu arbeiten und diese zu einer Hierarchie zu konfigurieren, zunächst ein Baum in einem logischen Raum "gezeichnet" wird und anschließend eine Abbildung vom logischen Baum zu tatsächlichen Maschinen ausgeführt wird.

Wie es oben erläutert wurde, kann der Daten-Overlay als eine Funktion dynamischer und unbeaufsichtigter Abänderungen, die in der zugrundeliegenden DHT vorgenommen werden, wachsen und schrumpfen. Da die SOMO-Baumstruktur 702 ein Beispiel eines Daten-Overlay ist, bedeutet dies, dass die SOMO-Baumstruktur 702 ebenfalls die Fähigkeit hat, in Erwiderung auf Abänderungen zu wachsen und zu schrumpfen, die an der zugrundeliegenden DHT vorgenommen werden. Zudem hat die SOMO-Baumstruktur wie ihre zugrundeliegende DHT die Fähigkeit, sich selbst wiederherzustellen und Abänderungen in der zugrundeliegenden DHT entgegenzuwirken. Der folgende Teilabschnitt erläutert die Art und Weise, in der die sich SOMO-Baumstruktur 702 in Erwiderung auf Änderungen in ihrer zugrundeliegenden DHT entwickelt.

Der logische Baum verhält sich wie ein Bezugsgerüst, das sämtlichen Maschinen im P2P-Pool hilft, sich zu einer Hierarchie in einer vollständig verteilten und automatischen Art und Weise zu organisieren. Er besteht aus einem Satz virtueller Knoten, von denen jeder über einen Schlüssel verfügt, wie es in 8a gezeigt ist, der zudem seine Position im eindimensionalen logischen DHT-Raum bestimmt.

Die erste Invariante beim Aufbauen des Baumes besteht darin, dass jeder virtuelle Knoten einen Abschnitt des Raumes besitzt und der Schlüssel des virtuellen Knotens das Zentrum des Teilraumes ist, den er besitzt. Angenommen, der logische Raum ist [0, 1], dann ist der Schlüssel des virtuellen Wurzel-Knotens 0,5. Anschließend wird der Raum des virtuellen Wurzel-Knotens (der gesamte logische Raum an diesem Punkt) gleichmäßig in k Teilräume unterteilt und jeder Teilraum durch einen virtuellen Knoten auf Ebene-1 abgedeckt. Durch umgekehrtes Anwenden dieses Teilungsvorgangs wird ein logischer Baum aufgebaut. Somit enthält Ebene-i insgesamt kⁱ virtuelle Knoten, wobei jeder virtuelle Knoten einen Teilraum der Größe 1/kⁱ besitzt. Insbesondere besitzt der j-te (0 <= J < 2ⁱ) virtuelle Knoten auf Ebene-i einen Raum von [j/kⁱ, (j + 1)/kⁱ) und ist bei (2j + 1)/2kⁱ positioniert/verschlüsselt, wobei 'k' die Ordnung und 'i' die Ebene ist. Dementsprechend ist eine beispielhafte Prozedur zum Aufbauen einer SOMO-Baumstruktur von unten nach oben in 8a–8c gezeigt.

Der physikalische Baum wird aufgebaut, wenn jede Maschine in der P2P-Umgebung ihre Elternmaschine gefunden hat. Dies kann in einer vollständig verteilten Art und Weise dadurch erreicht werden, dass der oben aufgebaute logische Baum zur Wirkung kommt. Da sämtliche Maschinen die gesamte Kenntnis des logischen Baumes haben, wählt jede Maschine unter Verwendung eines Ebenengrößen-Baumtraversal-Algorithmus' den höchsten virtuellen Knoten, der in ihre Zone fällt. Dieser virtuelle Knoten repräsentiert diese Maschine im fertigen physikalischen Baum und kann als solches der repräsentative Knoten oder repre(x) für Maschine x bezeichnet werden. Das deterministische Wesen des logischen Baums bedeutet, dass x den Schlüssel des virtuellen Eltern-Knotens von repre(x) berechnen kann. Mit Hilfe einer DHT-Lookup findet x die Maschine y, die der Host für diesen Schlüssel ist, und richtet eine Verbindung zu y ein, wie es in 8b gezeigt ist. Jede Maschine führt dieselbe Prozedur mit rein lokalem Wissen aus (die Zone und die deterministische logische Baumtopologie). Sämtliche Nachkommens-Eltern-Verbindungen werden durch ein Paar logischer Schlüssel identifiziert: den repräsentativen virtuellen Knoten, der auf die Nachkommens-Maschine fällt und den entsprechenden virtuellen Eltern-Knoten, der auf die Eltern-Maschine fällt. Die Verbindung wird mit Hilfe von Heartbeats aufrechterhalten, wobei die oben beschriebene Invariante immer gleich bleibt. Wenn sich beispielsweise die Zone von x teilt, weil ein neuer Nachbar hinzukommt, unterbricht x sämtliche Verbindungen, deren Punkte am Elternende nicht länger zu seiner Zone gehören. Zu diesem Zeitpunkt richten Maschinen am anderen Ende der Verbindungen ihre Eltern-Maschinen neu ein, indem sie eine Prozedur ausführen, wie sie zuvor beschrieben wurde, wodurch sich die Topologie selbst wiederherstellt – ein Beispiel hierfür ist die Prozedur, die in 9a–9c gezeigt ist.

Die vorangehende Prozedur kann als das Abbilden von Maschinen auf den logischen Raum der DHT verstanden werden. Jede Maschine entspricht einer oder mehreren Baumknotenzonen. Jede Maschine wählt als ihren repräsentativen Knoten aus einer oder mehreren der Baumknotenzonen, die ihr entsprechen, den Baumknoten entsprechend der größten Baumknotenzone. Jeder repräsentative Knoten wählt als seinen Eltern-Knoten einen weiteren repräsentativen Knoten, der der repräsentative Knoten für eine benachbarte Baumknotenzone ist, die eine größere Größe hat. Eine beispielhafte Prozedur für die Auswahl der repräsentativen Knoten und der Elternknoten, einschließlich dem Wurzel-Knoten, ist in 8a–8c zu sehen. Wie es in 7 gezeigt ist, nimmt die Größe der Baumknotenzone mit der zunehmenden Ebene des Baumes ab, wobei die erste Ebene die des Wurzel-Knotens ist, der eine Baumknotenzone entsprechend der gesamten Spanne des logischen Raumes der DHT hat.

Die vorangegangene Prozedur organisiert die physikalischen Maschinen zu einem Baum in einer vollständig verteilten Art und Weise. Weiterhin ist der Baum mit hoher Wahrscheinlichkeit von Ordnung k und ausgeglichen. Die Definition des repräsentativen virtuellen Knotens besteht darin, dass es der höchste virtuelle Knoten ist, der in die Zone einer Maschine fällt. Jede Maschine ist angeschlossen, da sich der virtuelle Eltern-Knoten auf einer anderen Maschine befindet. Der resultierende Graph hat keine Schleife, da dies die Definition des repräsentativen virtuellen Knotens verletzen würde. Somit muss es ein Baum sein. Die logische Baumstruktur ist deterministisch, und die einzige zusätzliche Eingabe, die eine Maschine benötigt, ist ihre eigene Zone im DHT-Raum. Somit ist das Aufbauen des Baumes vollständig verteilt. Der logische Baum ist ausgeglichen und von der Ordnung k. Ob der physikalische Baum ebenfalls von Ordnung k und ausgeglichen ist, wird hauptsächlich durch die Zonenverteilung bestimmt. Da die ID einer Maschine im DHT zufallsartig erzeugt wird, ist der resultierende Baum mit hoher Wahrscheinlichkeit von Ordnung k und ausgeglichen.

Der SOMO kann mit Änderungen der Mitgliedschaft automatisch und mit minimalem Overhead umgehen, da über jede Verbindung durch zwei logische Punkte entschieden wird: der erste Punkt davon ist der repräsentative virtuelle Knoten und ist durch seine DHT-Zone bestimmt, und der zweite Punkt davon ist ebenfalls deterministisch, sofern der erste gegeben ist. Somit kann, solange diese Invariante beibehalten wird, die Topologie neu eingerichtet werden, wenn immer es Veränderungen der Mitgliedschaft gibt. Infolgedessen wächst der SOMO-Baum, wenn neue Mitglieder zum Pool hinzukommen, und schrumpft, wenn sich Peers entfernen, wie es in 9a–9c gezeigt ist. Demzufolge ist eine beispielhafte Prozedur zum Wiederherstellen der von unten nach oben aufgebauten SOMO-Baumstruktur in 9a–9c zu sehen.

Ist es gewünscht, eine Maschine, die über die meisten Fähigkeiten verfügt, oben auf dem logischen Baum zu plazieren, kann die Knoten-ID zu einer anderen als der zufallsartig erzeugten geändert werden. Ein aufwärtsgerichteter Merge-Sort wird dann vom SOMO ausgeführt, um den am besten befähigten Knoten zu finden. Dieser Knoten tauscht anschließend seine ID mit dem Knoten aus, der momentan den logischen Wurzelpunkt des SOMO besitzt (d.h. 0,5 des gesamten Raumes [0, 1], wobei dies wirkungsvoll die Maschine ändert, die als Wurzel arbeitet, ohne dass andere Peers zerstört werden. Diese selbstoptimierende Eigenschaft wird dadurch möglich gemacht, das zunächst im logischen Raum operiert wird.

Der SOMO als Infrastruktur bestimmt weder, welche Daten erfasst werden sollen, noch die Operation, die aufgerufen wird, um die erfassten Daten zu verarbeiten. Um einen Ressourcen-Pool aufzubauen, sammelt jede Maschine einfach ihre Ressourcen-Metrik, kombiniert ihre Ressourcen-Metrik mit dem, was von ihren Nachkommens-Knoten empfangen wird, und verschmilzt diese mit ihrem Elternknoten. Die Daten, die weitergeleitet werden, sollten Soft-State sein. Zudem können Berichte als Optimierung die Gestalt von 'Delta' aufeinander folgender Berichte haben.

Das Verhalten des SOMO ist durch die Höhe des physikalischen Baums bestimmt, die ihrerseits durch die Parameter (d.h. k) des logischen Baums und die Verteilung von DHT-Knoten im logischen Raum festgelegt ist. Da die Knoten-ID zufällig ist, ist die Höhe des physikalischen Baums O(log_kN). Daher werden bei einem Datenberichtsintervall T Informationen von den SOMO-Blättern erfasst, wobei diese zu ihrer Wurzel mit einer maximalen Verzögerung von log_kN·T fließen. Diese Begrenzung wird abgeleitet, wenn der Fluss zwischen Hierarchien des SOMO vollständig unsynchronisiert ist. Wenn der Aufruf der oberen Knoten des SOMO nach Berichten unverzüglich die ähnlichen Aktionen ihrer Nachkommen auslösen, kann die Latenz auf T + t_hop·log_kN verringert werden, wobei t_hop eine durchschnittliche Latenz einer Auslösung im DHT ist, der als Host dient. Dieser unsynchronisierte Fluss hat eine Latenzgrenze von log_kN·T, wohingegen die synchronisierte Version in der Praxis mit T (z.B. 5 Minuten) begrenzt sein wird. Es wird darauf hingewiesen, dass O(t_hop·log_kN) die absolute Untergrenze ist. Für M2-Knoten mit k = 8 und einer typischen Latenz von 200 ms pro DHT-Sprung hat die SOMO-Wurzel eine globale Übersicht mit einer Verzögerung von 1,6 s.

Wie es oben beschrieben wurde, besteht eine beispielhafte Verwendung der SOMO-Baumstruktur 702 darin, Informationen von den physikalischen Maschinen im P2P-System zu erfassen, die durch den logischen DHT-Raum 704 repräsentiert sind. Eine weitere beispielhafte Verwendung der SOMO-Baumstruktur 702 besteht darin, Informationen auf diese physikalischen Maschinen zu verteilen. Die gesammelten Informationen können Metadaten sein. Metadaten beschreiben Informationen, die den Betrieb des P2P-Systems betreffen, wie etwa Informationen, die das Verhalten der physikalischen Maschinen widerspiegeln. Die Informationen, die auf die physikalischen Maschinen verteilt werden, können Anweisungen repräsentieren, die den Betrieb der physikalischen Maschinen steuern können. Somit kann man den SOMO-Mechanismus so interpretieren, dass er eine konvergierende Sendung von den SOMO-Blattknoten zum SOMO-Wurzelknoten ausführt, um die Datenerfassung zu ermöglichen, und anschließend einen Multicast zurück nach unten zu den SOMO-Blattknoten ausführt, um die Datenverteilung zu ermöglichen.

10a zeigt, dass die Kombination der DHT-Fähigkeit, einen Pool für Ressourcen zu bilden, mit einem SOMO zusammen zu einem P2P-Ressourcen-Pool führt, der aus einer DHT und einem SOMO besteht. Als Rekapitulation wird die DHT nicht im Sinne der gemeinsamen Nutzung von Inhalten verwendet, sondern vielmehr als effiziente Möglichkeit, mit geringem oder ohne Verwaltungsaufwand und ohne Skalierbarkeits-Engpass eine große Menge von Ressourcen zu einem Pool zusammenzustellen. Der SOMO ist eine selbstorganisierende "Nachrichten-Rundsende"-Hierarchie, die über eine DHT geschichtet ist. Das Anhäufen des Ressourcenstatus' in O(logN)-Zeit erzeugt dann die Illusion eines einzigen Ressourcen-Pools. Die Prozedur, die in 10a zu sehen ist, zeigt die paarweise Registrierung der Ressourcen, das Erfassen von Statistiken, eine Ansammlung der erfassten Statistiken zu einem Schnappschuss und das anschließend Sicherstellen, das die resultierende dynamische Datenbank von Applikationen abgefragt werden kann. Der Maßstab und die Zusammensetzung der P2P-Ressourcen erfordern es, dass jede Ebene vollständig selbstorganisierend, selbstskalierend, und selbstwiederherstellend ist, so dass es einen geringen Verwaltungsaufwand gibt.

10b zeigt beispielsweise ein Szenario 1002, bei dem eine SOMO-Baumstruktur 1004 verwendet wird, um Informationen von physikalischen Maschinen 1006 im P2P-System über den logischen DHT-Raum 1008 zu sammeln. Insbesondere rufen die SOMO-Blattknoten die erforderlichen Informationen von ihren DHT-Knoten ab, die als Host dienen. (Als Nebeneffekt kann diese Prozedur auch einen SOMO-Nachkommens-Knoten neustarten, für den Fall, dass dieser verschwunden ist, da der DHT-Knoten der als Host dient, abgestürzt ist). Eine oder mehrere Applikationen 1010 können diesen Erfassungsvorgang für einen beliebigen definierten Zweck aufrufen (wie etwa zum Zweck der Leistungsüberwachung, d.h. Sammeln unterschiedlicher Informationen, die unterschiedliche Belastungen und Kapazitäten der physikalischen Infrastruktur betreffen, die das P2P-System enthält).

Insbesondere zeigt 10b die Konfiguration der SOMO-Baumstruktur 1004, um Informationen zu sammeln, indem Linien dargestellt sind, die Pfeile aufweisen, die nach oben von jedem SOMO-Knoten zu seinem entsprechenden SOMO-Elternknoten zeigen. Auf diese Weise verlaufen die Informationen trichterförmig nach oben in der SOMO-Baumstruktur 1004 von deren SOMO-Blattknoten zu deren SOMO-Wurzelknoten. Die Applikation(en) 1010 kann (können) einen vollständigen Bericht aus dem SOMO-Wurzelknoten extrahieren, der Informationen aus dem gesamten P2P-System entnimmt. Alternativ kann dieser Bericht verschmolzene und sortierte Daten enthalten, vorausgesetzt, dass die SOMO-Knoten so konfiguriert wurden, dass sie diese Funktion ausführen, bevor sie die Informationen, die sie sammeln, zu ihren entsprechenden SOMO-Elternknoten weiterleiten. Die SOMO-Knoten können dazu eingerichtet sein, diese Aufgabe auszuführen, indem ein 'op'-Element so konfiguriert wird, das es Verschmelzen und Sortieren ausführt. Beispielsweise kann das Element op eine Operation definieren, die der betreffende SOMO-Knoten an Informationen ausführen kann, die er weiterleitet (entweder in einem Datenerfassungs- oder Datenverteilungsmodus). Beispielsweise kann unter Bezugnahme auf 7 das op festlegen, dass eine Verschmelzungsoperation im Verlauf des Sammelns von Informationen mit Hilfe der SOMO-Baumstruktur 702 ausgeführt werden soll. Durch Einschließend des op-Elementes kann die SOMO-Baumstruktur 702 eine beliebige Funktionalität in verteilter oder paralleler Art und Weise ausführen. Somit kann die SOMO-Baumstruktur 702 auch als Mechanismus betrachtet werden, der ein verteiltes, paralleles Verarbeitungsgerüst bereitstellt, um eine beliebige Art von Funktionalität zu implementieren. Dies ist lediglich ein veranschaulichendes Beispiel. Die SOMO-Knoten können andere Operationen an den Informationen ausführen, während diese die SOMO-Knoten auf ihrem Weg zum SOMO-Wurzelknoten durchlaufen, wie etwa unterschiedliche arithmetische Operationen.

Der folgende Pseudo-Code stellt eine Technik zum Erfassen von Informationen unter Verwendung der SOMO-Baumstruktur 1004 bereit: Pseudo-Code: SOMO-Erfassungsprozedur:

Um System-Metadaten zu erfassen, können die SOMO-Knoten periodisch die oben beschriebene Prozedur ausführen, indem sie Berichte von ihren jeweiligen Nachkommen anfordern. Die Erfassungsprozedur kann abgestimmt werden, um bestimmte Informationen aus der SOMO-Baumstruktur 1004 zu extrahieren. Insbesondere erleichtert die hierarchische Beschaffenheit der SOMO-Baumstruktur 1004 die Verwendung von Abfragen komplexer Bereiche, um Informationen zu entdecken, die für einen gegebenen logischen DHT-Raumbereich relevant sind. Ist k beispielsweise 2 und ist es gewünscht, einen Zustandsbericht über das erste Viertel des logischen DHT-Raums abzurufen, muss eine Applikation 1010 lediglich einen Bericht vom linken SOMO-Nachkommens-Knoten 1012 der SOMO-Baumstruktur 1004 der zweiten Ebene beziehen. Eine weitere nützliche Implementierung beinhaltet Registrierungsabfragen an SOMO-Knoten, die den SOMO-Mechanismus im wesentlichen in eine Veröffentlichungs-Teilnahme-("pub-sub"-)Infrastruktur umwandelt.

10b zeigt zudem das Szenario 1002, bei dem die SOMO-Baumstruktur 1004 verwendet wird, um Informationen auf die physikalischen Maschinen 1006 im P2P-System über den logischen DHT-Raum 1008 zu verteilen. Eine oder mehrere Applikationen 1010 kann/können diese Verteilungsoperation für einen beliebigen definierten Zweck aufrufen (wie etwa für die Verteilung von Anweisungen auf die physikalischen Maschinen 1006). Die Konfiguration der SOMO-Baumstruktur 1004 für die Verteilung von Informationen ist in 10b gezeigt, indem Linien dargestellt sind, die über Pfeile verfügen, die nach unten von den SOMO-Elternknoten zur ihren jeweiligen SOMO-Nachkommens-Knoten zeigen. Auf diese Weise breiten sich Informationen die SOMO-Baumstruktur 1004 nach unten von ihrem SOMO-Wurzelknoten zu ihren SOMO-Blattknoten aus. Die Informationen können sich durch die Verzweigungen der SOMO-Baumstruktur 1004 ohne Abänderung durch die SOMO-Knoten ausbreiten. Alternativ können die SOMO-Knoten mit Hilfe ihres op-Elementes eine beliebige Art von Operation an den Informationen ausführen, bevor diese zu ihren zugehörigen SOMO-Nachkommens-Knoten weitergeleitet werden. Wie es für den Fall der Datenerfassung beschrieben ist, ist es ebenfalls möglich, Informationen lediglich auf Teile des logischen DHT-Raumes 1008 zu verteilen, indem lediglich gewählte Verzweigungen des SOMO-Baumstruktur 1004 herangezogen werden.

Es können zusätzliche Applikationen und Abänderungen des Daten-Overlays und der SOMO-Baumstruktur implementiert werden. Bei einer beispielhaften Implementierung kann der SOMO-Mechanismus mit Multicasting auf Applikationsebene (ALM) verwendet werden, indem Algorithmen bereitgestellt werden, die auf die Metadaten wirken, die aus der SOMO-Baumstruktur erfasst werden, oder die die Informationen erzeugen, die sich durch die SOMO-Baumstruktur nach unten ausbreiten. ALM-Techniken können implementiert werden, indem eine geeignete Funktionalität in der Applikation (den Applikationen) 1010 bereitgestellt wird, die in 10b gezeigt ist/sind. 11a–11b zeigen schematische Anordnungen für das ALM.

Die Verfügbarkeit eines P2P-Ressourcen-Protokolls bietet Optimierungsmöglichkeiten. Wie es in 11a–11b gezeigt ist, kann eine Optimierung vorgenommen werden, wenn ein anderweitiger, sich im Leerlauf befindender, jedoch geeigneter Peer identifiziert ist. Sobald der geeignete Peer identifiziert ist, kann er in eine Topologie mit einer besseren Leitungsfähigkeit integriert werden. Somit zeigt 11b eine Verbesserung an der Anordnung, die in 11a gezeigt ist. Die Verbesserung wird durch Verwendung eines Helfer-Knotens in einem Ressourcen-Pool vorgenommen. In 11a–11b kennzeichnen Kreise ursprüngliche Elemente einer Multicast-Session auf Applikationsebene und kennzeichnet ein Quadrat einen verfügbaren Peer der eine hohe Ordnung hat. Die Optimierung kann marktbedarfsorientiert sein, so dass die ressourcenhungrigsten Aufgaben von den Maschinen in einem Peer-To-Peer-System ausgeführt werden, die über die meisten Ressourcen verfügen.

Bei zahlreichen P2P-Applikationen beinhaltet die Ressourcen-Statistik nicht nur die CPU-Auslastungen und die Netzwerkaktivitäten, sondern auch eine komplexere Ressourcen-Statistik, die nicht lokal von der Maschine abgeleitet werden kann. Ein betreffender Fall ist ALM. Angenommen, es ist gewünscht, die Zeitplanung einer Session auszuführen, und eine lange Liste von potentiellen Helfer-Peers wurde durch Abfragen des SOMO zusammengestellt, dann muss ein Peer gewählt werden, der sich in der Nähe befindet und die geeignete Bandbreite hat. Sind lediglich die IP-Adressen des Peers gegeben, ist das Senden eine Pings über diese, um deren Nachbarschaft zu finden, sowohl zeitaufwendig als auch fehlerbehaftet. Die folgende Beschreibung konzentriert sich auf die Metrik der IP-Adresse und der Bandbreite als Minderung dieses Problems. Es wird erläutert, wie diese Attribute erzeugt werden können, indem die Interaktionen zwischen den DHT-Knoten zum tragen kommen, die die Integrität des logischen Raumes beibehalten.

Um eine koordinatenbasierte Latenzschätzung, Latenz(x, y), zu finden, ist es ausreichend, Distanz (coord(x), coord(y)) zu berechnen, wobei coord eine Netzwerkkoordinate in einem d-dimensionalen euklidischen Raum ist. Jeder Knoten muss seine Heartbeats mit seinen Blattsatz-Knoten bereitstellen, um den DHT-Raum kollektiv beizubehalten. Wenn jeder Knoten zufallsartig wählt, die Heartbeat-Nachricht von Knoten in seinem Blattsatz zu bestätigen, so wird er im Laufe der Zeit einen gemessenen Verzögerungsvektor d_m zu seinen Blattsatz-Nachbarn haben. In der Heartbeat-Nachricht teilt jeder Knoten zudem seine momentanen Koordinaten mit. Somit ist zudem ein vorhergesagter Verzögerungsvektor d_p lokal verfügbar. Der Knoten x aktualisiert seine eigenen Koordinaten durch Ausführen eines Downhill-Simplex-Algorithmus' und Minimieren der Funktion:

Die Optimierung erfolgt lokal und aktualisiert lediglich die eigenen Koordinaten von x, die auf die Blattsatz-Nachbarn von x bei anschließenden Heartbeats verteilt werden. Diese Prozedur wird von allen Knoten periodisch ausgeführt, wobei die Knotenkoordinaten sowie die gemessenen und vorhergesagten Verzögerungsvektoren fortwährend aktualisiert werden.

Die Netzwerkbandbreite eines Peers ist dahingehend eine weitere wichtige Metrik für zahlreiche Applikationen, die auf einem P2P-Ressourcen-Pool laufen, dass es eine Korrelation zwischen der Engpassbandbreite und dem Durchsatz gibt. Daher kann die Engpassbandbreite als Prädiktor für den Durchsatz dienen. Es kann davon ausgegangen werden, dass ein Engpass im letzten Sprung liegt. Für jeden Knoten wird dessen Upstream-Engpassbandbreite als Maximum der gemessenen Engpassbandbreiten von dem Knoten zu seinen Blattsatz-Elementen geschätzt, die sowohl durch die Uplink-Bandbreite des Knotens und die Downklink-Bandbreiten der Blattsatz-Knoten beschränkt sind. De grundlegende Idee besteht darin, dass, wenn es einen Nachbarn mit einer Downlink-Bandbreite gibt, die größer ist als die Uplink-Bandbreite des Knotens, die Schätzung genau ist. Somit wäre bei einer größeren Zahl von Blattsatz-Knoten die Möglichkeit größer, eine präzise Schätzung zu bekommen. Aus demselben Grund wird die Downstream-Engpassbandbreite als das Maximum der gemessenen Engpassbandbreiten von seinen Blattsatz-Knoten zu sich selbst geschätzt.

Die Messung der Engpassbandbreite ist hinlänglich bekannt. Bei einer Paket-Paar-Technik werden beispielsweise zwei Pakete der Größe S direkt hintereinander von einem Quell-Knoten gesendet. Der Empfänger misst die Zeitstreuung T dazwischen und schätzt die Engpassbandbreite aus der Quelle als S/T.

Die Kooperation von Blattsatz-Knoten über Heartbeats ermöglicht es, dass die Paket-Paar-Technik natürlich entwickelt wird. Ein Knoten x wählt periodisch, einem Nachbarn y zwei aufeinander folgende Heartbeat-Nachrichten direkt hintereinander zu senden, wobei jede derart gefüllt ist, dass ihre Größe ausreichend groß ist (wie etwa 1,5 kB). 'y' verfügt nun über die Schätzung der Engpassbandbreite auf dem Weg von x zu sich selbst. Dieser Wert wird beim nächsten Heartbeat zu x Huckepack genommen. In ähnlicher Weise führt y dieselbe Prüfung durch wie x. Nachdem x genügend gemessene Bandbreiten von seinen Blattsatz-Elementen gesammelt hat, kann es nun seine eigene Engpassbandbreite, wie oben beschrieben, schätzen.

Es wird nun gezeigt, wie ein P2P-Ressourcen-Pool optimal für mehrere gleichzeitige ALM-Sessions verwendet wird. Das Endziel besteht darin, für aktive Sessions die optimale Leistung mit allen verfügbaren und geeigneten Peers im Ressourcen-Pool zu erreichen. Die Leistungs-Metrik einer Session ist durch bestimmte Dienstgüten-Definitionen bestimmt. Darüber hinaus sollten Sessions höherer Priorität proportional einen höheren Anteil der Ressourcen im Pool beziehen. Hier liegt die Konzentration auf einer kleinen bis mittleren Session-Größe, bei der davon ausgegangen wird, dass eine Dienstgüte in vielen Fällen eine Bedingung ist (z.B. Videokonferenz). Es wird zudem von einer statischen Mitgliedschaft ausgegangen, bei der die ursprüngliche Gruppe von Telnehmern mit M(s) für einen bestimmte Session 's' gekennzeichnet ist, obwohl der Algorithmus erweitert werden kann, um sich auch auf eine dynamische Mitgliedschaft anzupassen.

Ein Aufgaben-Manager einer Session ist dafür verantwortlich, einen modifizierten heuristischen Algorithmus ablaufen zu lassen, um die Topologie der ALM zu planen. Um wenig Ressourcen im Pool zu verwenden, fordert der Aufgaben-Manager den SOMO auf, eine Liste von Kandidaten zu beziehen. Die Gegenstände auf der Liste beinhalten nicht nur die Ressourcen-Verfügbarkeit, sondern auch deren Netzwerkkoordinaten und deren Bandbreite. Wenn der Plan gezeichnet ist, beginnt der Aufgaben-Manager die helfenden Peers zu kontaktieren, damit diese ihre Verwendung bereitstellen. Konkurrierende Aufgaben lösen ihre Behauptung lediglich durch ihre jeweiligen Prioritäten.

Für das ALM gibt es unterschiedliche Kriterien für die Optimierung; wie etwa den Bandbreiten-Engpass, die maximale Latenz, oder die Varianz von Latenzen. Die maximale Latenz sämtlicher Elemente wird hier als das Hauptziel des Baumaufbau-Algorithmus' verwendet, da sie in großem Maße die Wahrnehmung der Endbenutzer beeinflussen kann. Jeder Knoten hat eine Begrenzung der Zahl von Kommunikations-Sessions, die er handhaben kann, die hier "Ordnung" genannt wird. Dies kann auf die begrenzte Zugriffsbandbreite oder die Arbeitslast von Endsystemen zurückzuführen sein. Die Optimierung wird so ausgeführt, dass der ressourcenhungrigsten Aufgabe durch die Maschinen mit den meisten Ressourcen im Peer-To-Peer-System gedient wird.

Eine Definition für eine Dienstgüte für eine bestimmte Session kann formal wie folgt formuliert sein:

Definition 1. Problem der ordnungsbegrenzten, minimalen Höhe eines Baumes (DB-MHT). Gegeben sei ein ungerichteter, vollständiger Graph G(V, E), eine Ordnungsbegrenzung d_bound(v) für jedes v ∊ V, eine Latenzfunktion l(e) für jede Flanke e ∊ E. Finde einen überspannenden Baum T von G, so dass für jedes v ∊ T die Ordnung von v erfüllt: d(v) ≤ d_bound(v) und die Höhe von T (gemessen als gesamte Latenz von der Wurzel) minimiert wird.

Mit Hilfe des Ressourcen-Pools kann die Definition für die Dienstgüte erweitert werden. Eine erweiterte Gruppe von Helfer-Knoten H wird dem Graphen hinzugefügt, wobei das Ziel darin besteht, die beste Lösung im Bezug auf einen optimalen Plan, der ohne Verwendung von H abgeleitet wird, zu erreichen, indem die geringste Anzahl von Helfer-Knoten hinzugefügt wird.

Es werden das Verfahren zur Zeitplanung einer einzelnen ALM-Session wie auch ein Algorithmus zum Optimieren einer einzelnen ALM-Session erläutert, wenn ein Ressourcen-Pool verwendet wird. Der Algorithmus weist eine O(N³)-Leistungsgrenze auf und kann eine Lösung für Hunderte von Knoten in weniger als einer Sekunde erzeugen. Siehe beispielsweise unten die TABELLE A, ohne den Code im gestrichelten Kasten. Dieser Algorithmus, der hier als "AMCast" bezeichnet wird, beginnt zunächst mit der Wurzel und fügt diese einem Satz der momentanen Lösung zu. Als nächstes werden die minimalen Höhen der restlichen Knoten berechnet, indem ihre nächstgelegenen potentiellen Eltern im Lösungssatz gefunden werden, die Gegenstand der Ordnungsbeschränkungen sind. Dies kehrt wieder durch Aufnehmen des Knotens mit der geringsten Höhe in die Lösung. Der Vorgang fährt fort, bis sämtliche Knoten schließlich im resultierenden Baum enthalten sind. Um sicherzustellen, dass der bestmögliche Baum für einen Beginn ermittelt wurde, kann der Algorithmus mit einem Satz weiterer Abstimmungs- oder Justiermaßnahmen versehen werden. Beispielsweise können Abstimm- und Justiermaßnahmen zur Annäherung an einen global optimalen Algorithmus das Justieren eines Baumes mit einem Satz heuristischer Schritte beinhalten. Diese Schritte umfassen: (a) das Auffinden neuer Eltern für den höchsten Knoten; (b) das Austauschen des höchsten Knotens mit einem weiteren Blattknoten; und (c) das Austauschen. des Teilbaums, dessen Wurzel die Eltern des höchsten Knoten ist, mit einem weiteren Teilbaum.

Bei der Suche nach dienlichen Helfer-Knoten enthält der Algorithmus zwei Berücksichtigungen: (1) die Zeit zur Auslösung der Suche; und (2) die Kriterien, um eine Addition zu bewerten. Der allgemeine Mechanismus ist durch den Pseudo-Code in dem durch einen Kasten gekennzeichneten "Section A" in der Tabelle A beschrieben:

Es seien u der Knoten, den der AMCast-Algorithmus der Lösung hinzufügen möchte, und parent(u) dessen Eltern. Wenn die freie Ordnung von parent(u) auf Eins verringert wird, wird die Suche nach einem zusätzlichen Knoten h ausgelöst. Ist ein derartiges h im Ressourcen-Pool vorhanden, dann wird h anstelle dessen zu den Eltern von u und ersetzt u als Nachkommen des ursprünglichen parent(u). Unterschiedliche Versionen variieren lediglich hinsichtlich das Auswahlkriteriums h, wobei jedoch diese Klasse der Optimierung als Algorithmus eines kritischen Knotens bezeichnet werden kann. "Kritisch" bedeutet hier, dass dies die letzte Möglichkeit ist, für einen speziellen Knoten den ursprünglichen Algorithmus zu verbessern.

Es können unterschiedliche Algorithmen zur Suche nach h verwendet werden. Eine erste Variation des Algorithmus' besteht darin, einen zusätzlichen Knoten, nächstgelegen zum Elternknoten, mit einer geeigneten Ordnung (z.B. kann '4' verwendet werden) zu finden. Es sei l(a, b) die Latenz zwischen zwei beliebigen Knoten a und b. Die folgende Heuristik liefert sogar bessere Ergebnisse, wie es in Tabelle B gezeigt ist:

Hier kann v eines der Geschwister von u sein. Die Idee besteht hierbei darin, dass, da sämtliche v potentiell die zukünftigen Geschwister von h sein werden, l(h, parent(u)) + max(l(h, v) höchst wahrscheinlich die potentielle Baumhöhe nach dem Hinzukommen von h beeinflusst (Bedingung 1). Ein derartiger Helfer-Knoten sollte eine geeignete Ordnung haben (Bedingung 2). Um schließlich "unbrauchbare" Knoten zu vermeiden, die weit entfernt sind, wenngleich ihre Ordnungen hoch sind, legen wir einen Radius R fest: h muss innerhalb R von parent(u) entfernt liegen (Bedingung 3). Die Eingangsparameter, die notwendig sind, um diese Prozedur auszuführen, beinhalten die Netzwerkkoordinaten, so dass wir die Latenz zwischen einem willkürlichen Paar wie auch die Ordnungen jedes Knoten berechnen können. Dies wird möglich, indem jeder Knoten veranlasst wird, seine Netzwerkkoordinaten wie auch seine Bandbreitenbeschränkungen in seinem Bericht an den SOMO zu veröffentlichen, wie es in 12 gezeigt ist, die eine Visualisierung des SOMO-Berichtes ist, den ein Zeitplaner verwendet. Somit hat jeder Knoten eine Auslastung (verfügbare CPU-Zyklen), ein spezielles Speichervermögen (RAM, Platz auf der Platte, Cache) und verfügt zudem über bestimmte Netzwerkinformationen, wie etwa wo sich der Knoten befindet (IP-Adresse) und wie viel verfügbare Bandbreite der Knoten hat. 10a zeigt die Sammlung von Daten für die Verwendung in einem SOMO-Bericht, wie er etwa in 12 dargestellt ist.

Während der vorhergehende Abschnitt den eigenständigen Zeitplanalgorithmus für eine ALM-Session beschreibt, erläutert dieser Abschnitt, wie mit mehreren aktiven Sessions verfahren wird, bei denen Sessions mit einer höheren Priorität proportional mehr Ressourcen zugeordnet wird und die Verwendung des Ressourcen-Pools insgesamt maximiert wird.

Sämtliche Sessions können zu beliebigen Zeiten beginnen und enden. Jede Session hat eine mit einer ganzen Zahl bewertete Priorität zwischen 1 und 3. Eine Priorität-1-Session ist die höchste Klasse. Die Zahl der maximalen gleichzeitigen Sessions schwankt zwischen 10 und 60, wobei jede Session einen nicht überlappenden Elementensatz von 20 hat. Wenn es 60 aktive Sessions gibt, gehören somit sämtliche Knoten zu wenigstens eines Session. Das heißt, der Anteil ursprünglicher Elemente aktiver Sessions schwankt zwischen 17% und 100%. Zählt man die Helfer-Knoten, verwendet eine Sessions normalerweise mehr als die ursprünglichen Elemente. Es können zudem Knoten mit einer höheren Ordnung an mehr als einer Session beteiligt sein.

Das Prinzip, das diesem Ansatz zur Optimierung mehrerer ALM-Sessions zugrunde liegt, ist in gewisser Weise analog zu einer gut organisierten Gesellschaft: solange globales, rechtzeitiges und vertrauenswürdiges Wissen verfügbar ist, mag es das Beste sein, jede Aufgabe so zu belassen, dass sie um Ressourcen mit ihren eigenen Empfehlungen (d.h. mit ihren jeweiligen Prioritäten) in Wettstreit tritt. Dieses rein marktorientierte Modell gestattet das Erreichen des Ziels ohne den Bedarf eines globalen Zeitplaners gleich welcher Art.

Das Einstellen der geeigneten Prioritäten bei Knoten, die an einer Session beteiligt sind, erfordert zusätzliche Überlegung. Wenn in einer gemeinschaftlichen P2P-Umgebung ein Knoten eine Aufgabe ausführen muss, die ihn selbst als Element enthält, ist es angemessen, dass dies Aufgabe in diesem Knoten die höchste Priorität hat. Daher hat sie für eine Session s mit Priorität L die höchste Priorität (d.h. die erste Priorität) für Knoten in M(s) und L an anderer Stelle (d.h. für beliebige Helfer-Knoten, die außerhalb M(s) liegen). Damit ist sichergestellt, dass jede Session ausgeführt werden kann, wobei eine untere Grenze dem AMCast-adju-Algorithmus entspricht. Die obere Grenze erhält man unter der Voraussetzung, dass s die einzige Session im System ist (d.h. Blattsatz + adju).

Wie zuvor ist die Wurzel einer ALM-Session der Aufgaben-Manager, der die Planung und die Zeitplanung der Baumtopologie ausführt. Jede Session verwendet den Blattsatz-Justier-Algorithmus, um die Zeitplanung vollständig selbständig auf der Basis von Systemressourcen-Informationen auszuführen, die vom SOMO bereitgestellt werden. Für eine Session mit der Priorität L werden beliebige Ressourcen, die mit Aufgaben belegt sind, die eine geringere Priorität als L haben, als für deren Verwendung verfügbar angesehen. Wenn eine aktive Session eine Ressource in ihrem momentanen Plan verliert, muss sie in ähnlicher Weise die Zeitplanung erneut ausführen. Jede Session wird zudem eine Zeitplanung periodisch wiederholen, um zu prüfen, ob ein besserer Plan, der kürzlich frei gewordene Ressourcen verwendet, besser ist als der momentane Plan, und zu diesem umschalten, wenn dies der Fall ist.

Um es dem SOMO zu erleichtern, Ressourcen-Informationen zu erfassen und zu verteilen und so die Planung jedes Aufgaben-Managers zu unterstützen, veröffentlicht, wie zuvor, jeder Knoten seine Informationen, wie etwa Netzwerkkoordinaten, in seinem Bericht an den SOMO. Dessen Ordnung ist jedoch zu Prioritäten heruntergebrochen, die von aktiven Sessions belegt sind. Dies ist in den folgenden beiden Beispielen in der Ordnungs-Tabelle C zusammengefasst:

In der Ordnungs-Tabelle C sind die Ordnungs-Tabellen von zwei Knoten dargestellt. Die Gesamtordnung von x ist 4 und wird von der Session s4 mit 2 Ordnungen verwendet und von s12 mit einer weiteren Ordnung, so dass x mit einer freien Ordnung verbleibt. y verfügt andererseits lediglich über zwei Ordnungen, die beide von Session s5 verwendet werden. Die Ordnungs-Tabellen werden immer dann aktualisiert, wenn eine Zeitplanung stattfindet, die die Ordnungsteilung eines Knotens beeinflusst. Ordnungs-Tabellen werden, wie es zuvor erläutert wurde, vom SOMO erfasst und für jede beliebige laufende Aufgabe zur Abfrage verfügbar gemacht. Die Ordnungs-Tabelle C zeigt, dass es für eine Maschine möglich ist, sich unter unterschiedlichen Strömen von ALM-Sessions aufzuteilen, so dass einige Dinge simultan durch Aufteilen der Bandbreite erledigt werden können. Somit zeigt die Ordnungs-Tabelle C, wie viele Gesamt-Ordnungen verfügbar sein können und wie viele Fähigkeiten verfügbar sein können, indem die Fähigkeiten auf verschiedene Aufgaben aufgeteilt werden, so dass sie als Sessions unterschiedlicher Priorität zeitlich geplant werden können.

Wenn es mehr Sessions beim Multicasting auf Applikationsebene gibt und die gesamten Ressourcen knapp werden, nimmt die Leistungsfähigkeit ab. Aufgaben höherer Priorität sind jedoch in der Lage, eine weitaus bessere Leistungsfähigkeit beizubehalten, als jene geringerer Priorität. Zudem verlieren Aufgaben geringerer Priorität mehr Helfer-Knoten, wenn die Ressourcen in intensivem Wettstreit stehen.

Um einen Ressourcen-Pool zu erzeugen, ist es unvermeidlich, dass eine hierarchische Struktur eingerichtet wird, um eine zeitliche Anhäufung sicherzustellen. Bei einer Zwei-Ebenen-Architektur, bei der das IP-Ebenen-Multicasting angewendet wird, um Statistiken an einem Ort zu erfassen, kann beispielsweise das Ergebnis dann an einer zentralen Stelle angehäuft werden. Die Bestandteile sind hier erläutert, um einen Weitbereichs-Ressourcen-Pool plausibel zu machen, d.h. (1) die Kombination der selbstorganisierenden Fähigkeit einer P2P-DHT und (2) eine systemeigene, selbstskalierende Überwachungsstruktur.

ALM ist eine zu bevorzugende Applikation für P2P-DHTs. Um ein ALM zu optimieren, sollte jedoch ein Ressourcen-Pool verwendet werden. Mit einem Ressourcen-Pool können eine Optimierung einer einzelnen ALM-Session wie auch eine Optimierung mehrerer gleichzeitiger ALM-Sessions in einem vollautomatischen, marktorientierten Ansatz ausgeführt werden. Es wird jedoch darauf hingewiesen, dass das ALM lediglich eine Applikation für den P2P-Ressourcen-Pool ist. Trotzdem wird für eine Methodik, die ein eher verteilter als ein zentralisierter Abstimmungsmechanismus ist, ein Ansatz in zwei Schritten befürwortet: (1) applikationsspezifische Zeitplanung je Aufgabe; und (2) kombiniert mit marktorientiertem fairem Wettstreit durch Koordination innerhalb der Aufgaben.

Der Daten-Overlay, der oben in Abschnitt A beschrieben ist, ist eine Datenstruktur, die auf mehrere Maschinen und möglicherweise über eine andere Infrastruktur in einem P2P-System verteilt werden kann. Somit kann jeder der Teilnehmer im P2P-System so angesehen werden, dass er einen Teil des Daten-Overlays implementiert. Um diesen Effekt zu erzielen, kann jeder Teilnehmer den erforderlichen Code und die Daten speichern, um einen Daten-Overlay zu erzeugen und mit diesem zu interagieren. Der Code und die Daten können im flüchtigen und/oder nicht flüchtigen Speicher jedes Teilnehmers gespeichert werden (was im folgenden erläutert wird).

Beispielsweise zeigt 13 eine Ansicht höherer Ebene eines beispielhaften P2P-Teilnehmers als einen Computer 1342. Dieser Computer 1342 entspricht einem Computer für allgemeine Zwecke oder einem Server-Computer sowie einer angeschlossenen Anzeigevorrichtung 1374. Der Computer 1342 kann jedoch auch unter Verwendung anderer Arten eines Computergerätes implementiert sein. Beispielsweise kann der Computer 1342, wenngleich dies nicht gezeigt ist, ein Hand- oder Laptopgerät, Set-Top-Boxen oder Großrechner und dergleichen umfassen.

Der beispielhafte Computer 1342 kann verwendet werden, um die Prozesse auszuführen, die hier beschrieben sind. Der Computer 1342 enthält einen oder mehrere Prozessoren oder Prozessoreinheiten 1344, einen Systemspeicher 1346 und einen Bus 1348, der unterschiedliche Systemkomponenten, die den Systemspeicher 1346 enthalten, mit den Prozessoren 1344 verbindet. Es können ein oder mehrere Speicher im Computer 1342 verwendet werden, um den Code und die Daten zu speichern, die verwendet werden, um einen Teil des Daten-Overlays, wie etwa einen Teil der SOMO-Baumstruktur, zu implementieren.

Der Bus 1348 repräsentiert eine oder mehrere unterschiedlicher Arten von Busstrukturen, enthaltend einen Speicherbus oder Speicher-Controller, einen Peripheriebus, einen beschleunigten Graphikanschluss und einen Prozessorbus oder lokalen Bus, bei denen eine Vielfalt von Busarchitekturen Verwendung findet. Der Systemspeicher 1346 enthält einen ROM (Festspeicher) 1350 und einen RAM (Direktzugriffsspeicher) 1352. Ein BIOS (Basic Input/Output System) 1354, das die Basisroutinen enthält, die dabei hilfreich sind, Informationen zwischen Elementen innerhalb des Computers 1342, wie etwa während des Startens, zu übertragen, ist im ROM 1350 gespeichert.

Der Computer 1342 enthält zudem ein Festplattenlaufwerk 1356 um von einer Festplatte (nicht gezeigt) zu lesen und auf diese zu Schreiben, ein Magnetplattenlaufwerk 1358, um von einer entnehmbaren Magnetplatte 1360 zu lesen und auf diese zu schreiben, und ein optisches Plattenlaufwerk 1362, um von einer entnehmbaren optischen Platte 1364, wie etwa einer CD-ROM oder einem anderen optischen Medium zu lesen und auf dieses zu schreiben. Das Festplattenlaufwerk 1356, das Magnetplattenlaufwerk 1358 und das optische Plattenlaufwerk 1362 sind mit dem Bus 1348 über eine SCSI-Schnittstelle 1366 oder eine andere geeignete Schnittstelle verbunden. Die Laufwerke und ihre zugehörigen computerlesbaren Medien stellen einen nicht flüchtigen Speicher für computerlesbare Anweisungen, Datenstrukturen, Programmmodule und andere Daten für den Computer 1342 bereit. Wenngleich die beispielhafte Ausführungsform, die hier beschrieben ist, eine Festplatte, eine entnehmbare Magnetplatte 1360 und eine entnehmbare optische Platte 1364 verwendet, wird der Fachmann verstehen, das andere Typen computerlesbarer Medien, die Daten speichern können und auf die von einem Computer zugegriffen werden kann, wie etwa Magnetkassetten, Flash-Speicherkarten, digitale Videoplatten, RAMs und ROMs und dergleichen, ebenfalls in der beispielhaften Betriebsumgebung verwendet werden können.

Es kann eine Anzahl von Programmmodulen auf der Festplatte 1356, der Magnetplatte 1360, der optischen Platte 1364, im ROM 1350 oder im RAM 1352 gespeichert sein, die ein Betriebssystem 1370, eines oder mehrere Applikationsprogramme 1372 (wie etwa die Web-Anfrage-Verfolgungs-Applikation) 140, einen Cache/andere Module 1374 und Programmdaten 1376 beinhalten. Das Betriebssystem 1370 kann ein Web-Anfrage-Ereignisverfolgungswerkzeug beinhalten, wie es hier beschrieben ist (wie etwa die Verfolgungs-Infrastruktur 144). Ein Benutzer kann Befehle und Informationen in den Computer 1342 über Eingabevorrichtungen, wie etwa eine Tastatur 1378 und eine Zeigevorrichtung 1380, eingeben. Andere Eingabevorrichtungen (die nicht gezeigt sind) können ein Mikrofon, einen Joystick, ein Gamepad, eine Satellitenschüssel, einen Scanner und dergleichen beinhalten. Diese und andere Eingabevorrichtungen sind mit der Verarbeitungseinheit 1344 durch eine Schnittstelle 1382 verbunden, die mit dem Bus 1348 gekoppelt ist. Ein Monitor 1384 oder ein anderer Typ einer Anzeigevorrichtung ist ebenfalls mit dem Bus 1348 über eine Schnittstelle, wie etwa einen Videoadapter 1386, verbunden. Zusätzlich zum Monitor enthalten PCs normalerweise andere Peripherie-Ausgabevorrichtungen (nicht gezeigt), wie etwa Lautsprecher und Drucker.

Der Computer 1342 arbeitet im allgemeinen in einer Netzwerkumgebung mit Hilfe logischer Verbindungen zu einem oder mehreren entfernten Computern, wie etwa einem entfernten Computer 1388. Der entfernte Computer 1388 kann ein PC, ein weiterer Server, eine Router, ein Netzwerk-PC, eine Peer-Vorrichtung oder anderer gewöhnlicher Netzwerkknoten sein und enthält viele oder sämtliche Elemente, die oben im Bezug auf den Computer 1342 beschrieben wurden. Die logischen Verbindungen, die in 13 gezeigt sind, beinhalten ein lokales Netzwerk (LAN) 1390 und ein Weitbereichsnetzwerk (WAN) 1392. Derartige Netzwerke sind in Büros, weltweiten Computernetzwerken, Intranets und dem Internet allgemein üblich.

Bei der Verwendung in einer LAN-Netzwerkumgebung ist der Computer 1342 mit dem lokalen Netzwerk durch eine Netzwerkschnittstelle oder einen Adapter 1394 verbunden. Bei Verwendung in einer WAN-Netzwerkumgebung enthält der Computer 1342 normalerweise ein Modem 1396 oder eine andere Einrichtung zum Einrichten von Kommunikationen über das Weitbereichsnetzwerk 1392, wie etwa das Internet. Das Modem 1396, das intern oder extern sein kann, ist mit dem Bus 1348 über eine Seriellanschluss-Schnittstelle 1368 verbunden. In einer Netzwerkumgebung können Programmmodule, die im Bezug auf den PC 1342 dargestellt sind, oder Teile derselben in der entfernten Speichervorrichtung gespeichert sein. Es wird darauf hingewiesen, dass die dargestellten Netzwerkverbindungen beispielhaft sind und andere Einrichtungen zum Herstellen einer Kommunikationsverbindung zwischen Computern verwendet werden können.

Im allgemeinen werden die Datenprozessoren des Computers 1342 mit Hilfe von Anweisungen programmiert, die zu unterschiedlichen Zeiten auf den unterschiedlichen computerlesbaren Speichermedien des Computers gespeichert werden. Programme und das Betriebssystem werden normalerweise beispielsweise auf Floppy-Disketten oder CD-ROMs verteilt. Von dort werden sie in den Sekundärspeicher eines Computers installiert oder geladen. Bei der Ausführung werden sie wenigstens teilweise in den elektronischen Primärspeicher des Computers geladen. Die Erfindung, die hier beschrieben ist, enthält diese und andere unterschiedliche Typen von computerlesbaren Speichermedien, wenn derartige Medien Anweisungen oder Programme zum Implementieren der Blöcke beinhalten, die im folgenden in Verbindung mit einem Mikroprozessor oder einem anderen Datenprozessor beschrieben sind. Die Erfindung umfasst zudem den Computer an sich, wenn er gemäß den Verfahren und den Techniken programmiert wird, die hier beschrieben sind.

Zu Darstellungszwecken sind Programme und andere ausführbare Programmkomponenten, wie etwa das Betriebssystem, hier als diskrete Blöcke dargestellt, wenngleich es sich versteht, dass sich derartige Programme und Komponenten zu unterschiedlichen Zeiten in unterschiedlichen Speicherkomponenten des Computers befinden und durch den (die) Datenprozessor(en) des Computers ausgeführt werden.

Beliebige der hier beschriebenen Funktionen können unter Verwendung von Software, Firmware (z.B. einer unveränderlichen Logikschaltung), manueller Verarbeitung oder einer Kombination aus diesen Anwendungen implementiert werden. Der Begriff "Logik" oder "Modul", wie er hier verwendet wird, repräsentiert Software, Firmware oder eine Kombination aus Software und Firmware. Für den Fall einer Softwareimplementierung repräsentiert der Begriff "Logik" oder "Modul" Programmcode, der spezielle Aufgaben durchführt, wenn er in einer Verarbeitungsvorrichtung oder Verarbeitungsvorrichtungen (z.B. einer CPU oder CPUs) ausgeführt wird. Der Programmcode kann auf einer oder mehreren computerlesbaren Speichervorrichtungen gespeichert sein. Die dargestellte Trennung von Logik und Modulen in eigene Einheiten kann eine tatsächliche physikalische Gruppierung und Zuordnung derartiger Software und/oder Hardware widerspiegeln, oder kann einer konzeptionellen Zuordnung unterschiedlicher Aufgaben entsprechen, die von einem einzelnen Softwareprogramm und/oder einer Hardwareeinheit ausgeführt werden. Die dargestellte Logik und die Module können sich an einer einzigen Stelle (z.B. ausgeführt durch eine einzige Verarbeitungsvorrichtung) befinden oder über mehrere Orte verteilt sein.

Um einen P2P-Ressourcen-Pool zu erzeugen, wird die Fähigkeit der Selbstorganisation einer P2P-DHT mit einer sich selbst skalierenden, hierarchischen, systemeigenen Überwachungs-Infrastruktur kombiniert. Um die Selbstskalierung und eine Stabilität zu erreichen, muss diese Infrastruktur eine logische Hierarchie sein, die im virtuellen Raum eingerichtet wird, der durch die DHT erzeugt wird, und anschließend auf die Teilnehmer abgebildet wird. Es wurde hier erläutert, wie ein SOMO, der mit einer DHT kombiniert ist, wirkungsvoll einen Ressourcen-Pool erzeugt.

Die Leistung des Ressourcen-Pools kann verwendet werden, um die zeitgerechte und präzise Nachrichtensendung über den SOMO zu nutzen, einen applikationsspezifischen Zeitplaner für jede Aufgabe zu installieren und anschließend einen vollautomatischen, marktorientierten Ansatz auszuführen, um Aufgaben in fairem Wettstreit zu koordinieren.

Es wurden Implementierungen zum Aufbauen einer Datenstruktur auf einer DHT in einem P2P-System beschrieben. Es wurde eine spezifische hierarchische Struktur speziell zum Verteilen von Informationen im P2P-System und zum Sammeln von Informationen aus dem P2P-System erläutert.

Bestimmte Vorgänge wurde so erläutert, das sie eindeutige Schritte bilden, die in einer bestimmten Reihenfolge ausgeführt werden. Derartige Implementierungen sind beispielhaft und nicht einschränkend. Bestimmte Schritte, die hier beschrieben wurden, können gruppiert und in einem einzigen Vorgang ausgeführt werden, und bestimmte Schritte können in einer Reihenfolge ausgeführt werden, die sich von der Reihenfolge unterscheidet, die bei den Beispielen zur Anwendung kommt, die in dieser Beschreibung erläutert sind.

Zudem sind zahlreiche Beispiele in dieser Beschreibung als Alternative dargestellt (z.B. Fall A oder Fall B). Darüber hinaus schließt diese Beschreibung jene Fälle ein, die Alternativen in einer einzigen Anwendung kombinieren (z.B. Fall A und Fall B), wenngleich diese Beschreibung nicht ausdrücklich diese verbindenden Fälle bei jedem Beispiel erwähnt.

Die vorliegende Erfindung kann in anderer spezieller Form ausgeführt werden, ohne von ihren speziellen Eigenschaften abzuweichen. Die beschriebenen Ausführungsformen sind in allen Aspekten lediglich als beispielhaft und nicht einschränkend zu betrachten. Der Geltungsbereich der Erfindung ist somit durch die beigefügten Ansprüche anstelle durch die vorangehende Beschreibung definiert. Sämtliche Änderungen, die der Bedeutung und dem Bereich der Äquivalenz der Ansprüche entsprechen, sind in deren Geltungsbereich eingeschlossen.