Diese Erfindung bezieht sich allgemein auf Netzwerke. Insbesondere bezieht sich die Erfindung auf ein Teilen von Arbeitslasten von Knoten in einem Netzwerk.

Große Netzwerke, wie beispielsweise das Internet, die eventuell die Infrastruktur für viele Partner-zu-Partner-Systeme (Peer-to-Peer-Systeme) bereitstellen, werden nun verwendet, um eine Vielfalt von Diensten für Benutzer zu liefern. Beispielsweise können Mediendienste, wie beispielsweise Streaming und eine Umcodierung (Transcoding), Web-Dienste für elektronischen Handel, wie beispielsweise Flug- und Hotelreservierungen, oder Gitterrechendienste für eine Berechnung und für Daten über große Netzwerke verfügbar sein.

Eine grundlegende Herausforderung bei einem wirksamen Nutzen dieser Netzwerkdienste besteht darin, erwünschte Dienste in großen Netzwerken, wie beispielsweise dem Internet, effizient und schnell zu lokalisieren. Die Herausforderung eines Entdeckens von Diensten ist durch mehrere Faktoren verkompliziert. Falls beispielsweise ein zentralisierter Informationsdienst zum Erleichtern einer derartigen Entdeckung verwendet würde, wie beispielsweise ein zentralisierter Informationsdienst, der für Partner-zu-Partner-Dateiteilhabungssysteme (Peer-to-Peer-File-Sharing-Systeme) verwendet wird, ließe sich derselbe nicht ohne weiteres skalieren, wenn sich die Anzahl von verfügbaren Diensten und die Anzahl von Benutzern erhöhen. Zusätzlich weist jeder Dienst mehrere dynamische Attribute auf, z. B. Last und Latenz, die sich stets verändern und in dem Informationsdienst aktualisiert werden müssen. Die erwünschte Aktualisierungsrate kann durch einen zentralisierten Informationsdienst eventuell nicht aufrechterhalten werden. Ferner kann ein Bereitstellen eines Informationsdienstes mit einer minimalen Ausfallzeit mehrere Systemadministratoren für eine Wartung erfordern und wäre kostspielig. Schließlich sollte der Informationsdienst für schnellere Ansprechzeiten ortsbewusst sein. Beispielsweise sollte eine Abfrage, die eine Anforderung nach einem erwünschten Dienst umfasst, an einen Knoten in der Netzwerknähe des Knotens gerichtet sein, der die Abfrage anfänglich sendet, und die Dienste, die als eine Antwort auf die Abfrage zurückgegeben werden, sollten sich ebenfalls in der Netzwerknähe des abfragenden Knotens befinden.

Falls ein Informationsdienst verfügbar gemacht würde, sollte der Informationsdienst zusätzlich Selbstverwaltungseigenschaften umfassen, wie beispielsweise Arbeitslastausgleichs- und andere Verwaltungsaufgaben zum Minimieren einer kostspieligen, manuellen fehleranfälligen Verwaltung.

Gemäß einem Ausführungsbeispiel wird aus einem Satz von Knoten in einem Partner-zu-Partner-Netzwerk ein Knoten identifiziert, der die höchsten Arbeitslasten in dem Partner-zu-Partner-Netzwerk aufweist. Die Arbeitslast des Knotens wird mit einem anderen Knoten unter Verwendung eines Teilungsalgorithmus geteilt.

Verschiedene Merkmale der Ausführungsbeispiele können vollständiger erkannt werden, wenn dieselben mit Bezug auf die folgende detaillierte Beschreibung der Ausführungsbeispiele in Verbindung mit den zugehörigen Figuren besser verständlich werden, in denen:

1 ein Partner-zu-Partner-Netzwerk gemäß einem Ausführungsbeispiel darstellt;

2 ein Überlagerungsnetzwerk in einem Partner-zu-Partner-Netzwerk gemäß einem Ausführungsbeispiel darstellt;

3 einen Attributraum und Attributteilräume gemäß einem Ausführungsbeispiel darstellt;

4 in einem Informationsdienstknoten gespeicherte Informationen gemäß einem Ausführungsbeispiel darstellt;

5 ein Routen einer Abfrage gemäß einem Ausführungsbeispiel darstellt;

6 ein Routen einer Anzeige gemäß einem Ausführungsbeispiel darstellt;

7 eine Austauschphase und eine Verbreitungsphase gemäß einem Ausführungsbeispiel darstellt;

8A-D Routingtabellen für Informationsdienstknoten gemäß einem Ausführungsbeispiel darstellen;

9A-C Beispiele von Routingtabellen und Attributteilräumen darstellen, die aus einer Arbeitslastaufteilung resultieren, gemäß einem Ausführungsbeispiel;

10 Informationsdienstknoten in der Anfangsphase des globalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel darstellt;

11A-B Beispiele eines Anwendens eines globalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel darstellen;

12 ein Flussdiagramm eines Verfahrens zum Anwenden eines lokalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel darstellt;

13 ein Flussdiagramm eines Verfahrens zum Anwenden eines globalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel darstellt;

14 ein Beispiel eines Verwendens von Latenzberichten darstellt, um einen Informationsdienstknoten für eine Nachbildung auszuwählen;

15 ein Flussdiagramm eines Verfahrens zum Reproduzieren eines Informationsdienstknotens gemäß einem Ausführungsbeispiel darstellt; und

16 ein Computersystem gemäß einem Ausführungsbeispiel darstellt.

Zu Einfachheits- und Darstellungszwecken sind die Prinzipien der Ausführungsbeispiele beschrieben. Ein Durchschnittsfachmann auf dem Gebiet würde jedoch ohne weiteres erkennen, dass die gleichen Prinzipien gleichermaßen auf alle Typen von Netzwerksystemen anwendbar sind und in denselben implementiert sein können, und dass jegliche derartigen Variationen nicht von der wahren Wesensart und dem Schutzbereich der Ausführungsbeispiele abweichen. In der folgenden detaillierten Beschreibung wird zudem Bezug auf die zugehörigen Zeichnungen genommen, die spezifische Ausführungsbeispiele darstellen. Elektrische, mechanische, logische und strukturelle Veränderungen können an den Ausführungsbeispielen vorgenommen werden, ohne von der Wesensart und dem Schutzbereich der Ausführungsbeispiele abzuweichen.

Gemäß einem Ausführungsbeispiel ist ein verteilter Informationsdienst zum Entdecken von Diensten in einem Netzwerk vorgesehen. Der Informationsdienst versieht Benutzer mit Informationen über Dienste, die über das Netzwerk verfügbar sind. Ein Benutzer fragt den Informationsdienst nach Informationen über erwünschte Dienste ab, die über das Netzwerk verfügbar sind. Der Informationsdienst kann mit einer Liste von Dienstknoten in dem Netzwerk antworten, die wirksam sind, um den erwünschten Dienst zu liefern.

Der Informationsdienst ist ein verteilter Informationsdienst, der eine Mehrzahl von Informationsdienstknoten in einem Partner-zu-Partner-Netzwerk umfasst, die Informationen über die verfügbaren Dienste speichern. Ungleich herkömmlichen Partner-zu-Partner-Netzwerken, bei denen die Knoten dazu neigen, vorübergehend zu sein, sind die Informationsdienstknoten stabile Knoten in einer Partner-zu-Partner-Architektur, bei denen es wahrscheinlicher ist, dass dieselben für eine erweiterte Zeitdauer in dem Partner-zu-Partner-Netzwerk bleiben, anstatt für eine kurze Zeitdauer dem Partner-zu-Partner-Netzwerk beizutreten. Einem Durchschnittfachmann auf dem Gebiet ist ersichtlich, dass das Partner-zu-Partner-Netzwerk ein Beispiel eines Organisierens der Informationsdienstknoten in einer verteilten Architektur ist und irgendein Typ einer verteilten Architektur verwendet werden kann.

Die verteilte Beschaffenheit des Informationsdiensts minimiert die Engstelle, die einem Verwenden eines herkömmlichen, zentralen Informationsdepots zugeordnet ist, das alle Abfragen nach Informationen handhabt, und verbessert somit Abfrageantwortzeiten. Ein Überlagerungsnetzwerk für das Partner-zu-Partner-Netzwerk wird verwendet, um Abfragen und Informationen über Dienste in dem verteilten Informationsdienst zum Erleichtern der Entdeckung verfügbarer Dienste in einem Netzwerk effizient zu routen.

Wie hierin verwendet, bezieht sich ein Dienst auf irgendeine Funktion, die an einer Eingabe wirksam ist und eine Ausgabe erzeugt. Beispiele von Diensten umfassen eine Umcodierung, eine Sprachübersetzung, eine Verschlüsselung, eine Bildreparatur und -analyse, eine Fehlerkorrektur, ein Umwandeln eines Inhalts in unterschiedliche Sprachen, etc. Ein Dienst kann ferner aus mehreren Diensten gebildet sein. Beispielsweise kann eine Ausgabe eines Dienstes für so viele Zwischendienste, wie verwendet werden, um den Dienst zusammenzusetzen, die Eingabe eines anderen Dienstes sein, usw. Ein Beispiel eines zusammengesetzten Dienstes kann einen Mediendienst umfassen, der eine Video-Streaming-Dienst-Eingabe in einem Umcodierungsdienst umfasst, derart, dass ein Benutzer Streaming-Video in einem Format empfangen kann, das an einem speziellen Endbenutzergerät betrachtet werden kann.

Andere Typen von Diensten umfassen Berechnungsdienste, Datenspeicherungsdienste und Gitterrechendienste, die ein gemeinschaftliches Verwenden von Computerressourcen einschließen können. Ein Gitterrechendienst beispielsweise ermöglicht Benutzern einen Zugriff auf Rechendienste basierend auf Spezifikationen, wie beispielsweise Anwendungserfordernissen.

1 stellt ein Netzwerk 100 dar, das Benutzerknoten 110, Dienstknoten 120 und Informationsdienstknoten 130 umfasst. Ein Beispiel des Netzwerks 100 umfasst ein Netzwerk auf großer Skala, wie beispielsweise das Internet, bei dem Dienste Benutzern verfügbar gemacht werden. Die Ausführungsbeispiele können jedoch in kleineren Netzwerken implementiert sein, die Dienste liefern. Benutzerknoten können irgendeinen Knoten umfassen, der wirksam ist, um einen Dienst zu empfangen. Typischerweise legt ein Benutzerknoten eine Abfrage einem Informationsdienst zum Bestimmen vor, ob ein Dienst, der durch einen Benutzer gewünscht wird, in dem Netzwerk 100 verfügbar ist, und falls der Dienst verfügbar ist, welcher Dienstknoten zum Empfangen des Dienstes zu kontaktieren ist. Die Dienstknoten 120 umfassen Knoten, die wirksam sind, um Dienste zu liefern. Nachdem ein Benutzerknoten einen Dienstknoten identifiziert, der wirksam ist, um durch ein Abfragen des Informationsdienstes einen erwünschten Dienst zu liefern, empfängt der Benutzerknoten den Dienst von dem Dienstknoten, der den erwünschten Dienst liefert. Ein Knoten ist irgendeine Vorrichtung, die Nachrichten über das Netzwerk senden und/oder empfangen kann und die typischerweise wirksam ist, um eine gewisse Art einer Datenverarbeitung durchzuführen. Beispiele von Knoten umfassen Router, Server und Endbenutzergeräte, wie beispielsweise PDAs, Personalcomputer, Laptops und Mobiltelefone.

Gemäß einem Ausführungsbeispiel wird der Informationsdienst durch die Informationsdienstknoten 130 geliefert. Die Informationsdienstknoten 130 ermöglichen die Entdeckung von Diensten in dem Netzwerk 100. Zusätzlich zu einer Dienstentdeckung gleichen die Informationsdienstknoten 130 Arbeitslasten unter denselben unter Verwendung mehrerer Techniken aus, die in der ebenfalls anhängigen US-Patentanmeldung (Anwaltsaktenzeichen Nr. 200500031-1) mit dem Titel „Splitting Workload Of A Node" von Sujoy Basu et al. und der ebenfalls anhängigen US-Patentanmeldung (Anwaltsaktenzeichen Nr. 200500030-1) mit dem Titel „Determining Highest Workloads For Nodes In A Network" von Sujoy Basu et al. beschrieben sind, die beide durch Bezugnahme in ihrer Gesamtheit aufgenommen sind.

Wie es oben beschrieben ist, führt der Informationsdienst, einschließlich der Informationsdienstknoten 130, Funktionen durch, die der Entdeckung von Diensten in dem Netzwerk 100 zugeordnet sind. Zwei wichtige Funktionen umfassen das Speichern von Informationen über verfügbare Dienste und das Ansprechen auf Abfragen über verfügbare Dienste. Die Informationsdienstknoten 130 sind in einem Partner-zu-Partner-Netzwerk, in 2 gezeigt, in dem Netzwerk 100 vorgesehen. Das Partner-zu-Partner-Netzwerk 200 und ein Überlagerungsnetzwerk 210 für das Partner-zu-Partner-Netzwerk 200 werden unter anderem zum Speichern von Informationen über Dienste in den Informationsdienstknoten 130, zum Routen unter den Informationsdienstknoten 130 und zum Ansprechen auf Abfragen verwendet.

Wie es in 2 gezeigt ist, überlagert das Überlagerungsnetzwerk 210 das darunter liegende Partner-zu-Partner-Netzwerk 200. Das Überlagerungsnetzwerk 210 ist eine logische Darstellung des Partner-zu-Partner-Netzwerks 200 und ist wirksam, um Abfragen und Dienstinformationen basierend auf Attributen und Attributbereichen effizient zu routen, die verwendet werden, um Dienste zu definieren, wie es unten detailliert beschrieben ist. 2 stellt die Informationsdienstknoten 130, die in dem Netzwerk 100 zentral positioniert sind, und die Benutzerknoten 110 sowie die Dienstknoten 120, die in dem Überlagerungsnetzwerk 210 vorgesehen sind, zu Zwecken eines Darstellens dar, dass das Partner-zu-Partner-Netzwerk 200 die Informationsdienstknoten 130 umfasst und dass die Benutzerknoten 110 und die Dienstknoten 120 mit den Informationsdienstknoten 130 in dem Partner-zu-Partner-Netzwerk 200 kommunizieren, wenn es erforderlich ist. Die Informationsdienstknoten 130 können in mehreren unterschiedlichen Bereichen des Netzwerks 100 vorgesehen sein, um eine Latenz zu minimieren, z. B. die Länge von Zeit, die ein Benutzerknoten benötigt, um eine Antwort auf eine Abfrageantwort zu bekommen.

Ein Dienst ist durch ein Spezifizieren von Werten für verschiedene Dienstattribute gekennzeichnet. Zum Beispiel kann ein Computerdienst durch die Werte von Attributen gekennzeichnet sein, wie beispielsweise einem Betriebssystem und Anwendungen, einer Menge an physischem Speicher, einem Plattenraum und einer Netzwerkbandbreite.

Der Informationsdienst verfolgt diese Attribute und Attributwerte. Jeder Informationsdienstknoten weist die Verantwortung zum Verfolgen eines bestimmten Satzes von Werten für eines oder mehrere der Attribute auf. Die Kombination der Sätze von Attributwerten für alle verfolgten Attribute bildet den Attributteilraum, der durch diesen Informationsdienstknoten verfolgt wird.

Der Informationsdienst, der aus den Informationsdienstknoten 130 gebildet ist, umfasst einen Attributraum 300, der in 3 gezeigt ist. Der Attributraum 300 umfasst alle Informationen über verfügbare Dienste in dem Partner-zu-Partner-Netzwerk 100. Der Attributraum 300 ist eine logische Darstellung der Informationen, die in dem Informationsdienst gespeichert sind.

Der Attributraum 300 ist unter den Informationsdienstknoten 130 verteilt. Lediglich drei Informationsdienstknoten 130a-c sind in 3 zu Darstellungszwecken gezeigt. Jedem der Informationsdienstknoten 130 ist eine Verantwortung für einen Attributteilraum in dem Attributraum 300 zugewiesen. Jeder Attributteilraum ist speziellen Attributen und Attributwerten zugeordnet. Bei dem Informationsdienst ist ein Dienst durch vorbestimmte Attribute und Attributwerte definiert, die je nach Dienst variieren. Attribute und Attributwerte sind jedem der Informationsdienstknoten 130 zugewiesen. Ein Dienst ist bestimmt, um in einen Attributteilraum eines Informationsdienstknotens zu fallen, und somit sind Informationen über diesen Dienst letztendlich in diesem Informationsdienstknoten gespeichert, falls die Attribute und Attributwerte für den Dienst mit den Attributen und Attributwerten übereinstimmen, die dem Attributteilraum für den Informationsdienstknoten zugewiesen sind. Beispielsweise kann ein Attributteilraum Attributwerte für ein spezielles Attribut umfassen. Falls ein Dienst unter Verwendung eines oder mehrerer Attributwerte definiert ist, die die Attributwerte eines Attributteilraums schneiden, kann der Dienst in den Attributteilraum fallen. Ein Beispiel, das die Attributteilräume weiter beschreibt, lautet wie folgt. Eine Liste von vorbestimmten Attributen zum Definieren aller Dienste in dem Netzwerk 100 kann einen Speicher, einen Plattenraum, eine Durchschnittslast, ein Betriebssystem, Anwendungen, eine Dienstbetriebszeit und eine Ansprechzeit umfassen. Ein Gitterrechendienst kann das gemeinschaftliche Verwenden von Computerressourcen umfassen. Ein Gitterrechendienst, z. B. ein Gitterrechendienst 1, kann basierend auf den Computerressourcen definiert sein, die gemeinschaftlich verwendet werden können. Der Gitterrechendienst 1 ist unter Verwendung der folgenden Attributwerte definiert:

• Speicher: 1 GB
• Plattenraum: 2,5-5 GB
• Betriebssystem: Linux 2.4
• Durchschnittslast: 0
• Anwendungen: Maya, Renderman
• Dienstbetriebszeit: 99,5 %
• Ansprechzeit: <= 20 ms

Wie es in 3 gezeigt ist, ist dem Informationsdienstknoten 130a der Attributteilraum zugewiesen, der durch die Attributwerte von Speicher <= 1 GB definiert ist. Eine Anzeige 310 für den Gitterrechendienst 1, der die Attributwerte in Tabelle 1 umfasst, ist an dem Informationsdienstknoten 130a gespeichert, weil der Informationsdienstknoten 130a alle Anzeigen speichert, die einen Speicherattributwert <= 1 GB aufweisen.

Eine Anzeige umfasst die Attribute und Attributwerte, die verwendet werden, um einen speziellen Dienst zu definieren. Ein vorbestimmter Satz von Attributen kann verwendet werden, um alle Dienste in dem Netzwerk 100 zu definieren. Jeder der Dienstknoten 120 misst oder bestimmt anderweitig die Attributwerte für jedes der Attribute in dem vorbestimmten Satz von Attributen. Jeder der Dienstknoten 120 sendet ferner regelmäßig die Anzeigen desselben zu dem Informationsdienst. Das Überlagerungsnetzwerk 210 routet die Anzeigen automatisch zu dem geeigneten Informationsdienstknoten, der den Attributteilraum besitzt, in den die Anzeige fällt. Die Attribute und Attributwerte, die oben für den Gitterrechendienst 1 gezeigt sind, sind ein Beispiel der Informationen in der Anzeige 130 für den Gitterrechendienst 1. Ein Dienstknoten, der den Gitterrechendienst 1 liefert, misst oder bestimmt anderweitig beispielsweise regelmäßig die Attributwerte für den Gitterrechendienst 1, die in Tabelle 1 gezeigt sind, und überträgt die Anzeige 310, die die Attributwerte umfasst, zu dem Überlagerungsnetzwerk 210 für eine Speicherung in dem Informationsdienstknoten, der den Attributteilraum besitzt, in den die Anzeige fällt. Bei dem in 3 gezeigten Beispiel routeten die Informationsdienstknoten 130 eine Anzeige 310 für den Gitterrechendienst 1 zu dem Informationsdienstknoten 130a, weil der Informationsdienstknoten 130a alle Informationen über Dienste speichert, die zu dem Überlagerungsnetzwerk 210 übertragen wurden und einen Attributwert innerhalb Speicher <= 1 GB aufweisen. Das heißt, der Gitterrechendienst 1 ist unter Verwendung eines Attributwerts von 1 GB für das Speicherattribut definiert und der Attributwert 1 GB schneidet den Attributbereich von Speicher <= 1 GB für den Attributteilraum des Informationsdienstknotens 130a, d. h. ist in demselben enthalten. Somit fällt der Gitterrechendienst 1 in den Attributteilraum des Informationsdienstknotens 130a.

Die Attribute, die oben für den Gitterrechendienst 1 gezeigt sind, sind Beispiele des vorbestimmten Satzes von Attributen, der verwendet wird, um Dienste in dem Netzwerk 100 zu definieren. Einem Durchschnittfachmann auf dem Gebiet ist ersichtlich, dass andere Attribute verwendet werden können, um die verfügbaren Dienste zu definieren. Ferner kann ein vorbestimmter Satz von Attributen verwendet werden, um die Dienste zu definieren. Es kann jedoch jeder Dienst unterschiedliche Attributwerte aufweisen, die regelmäßig gemessen und in dem Informationsdienstknoten gespeichert werden, der den entsprechenden Attributteilraum aufweist.

Abfragen werden auf ähnliche Weise in dem Partner-zu-Partner-Netzwerk 200 gespeichert. Beispielsweise kann das Überlagerungsnetzwerk 210, das in 2 gezeigt ist, eine Abfrage 320 empfangen, die in 3 gezeigt ist, und eine Anforderung nach einem Dienst mit einem Attribut von Speicher > 1 GB und Plattenraum = 2 GB umfassen. Die Abfrage 320 fällt in den Attributteilraum, den der Informationsdienstknoten 130b besitzt. Somit wird die Abfrage 320 durch das Überlagerungsnetzwerk 210 hindurch zu dem Informationsdienstknoten 130b geroutet. Die Abrage 320 wird automatisch zu dem Informationsdienstknoten 130b geroutet und in demselben gespeichert und der Informationsdienstknoten 130b spricht auf die Abfrage durch ein Durchsuchen der Anzeigen, die in dem Informationsdienstknoten 130b gespeichert sind, und ein Senden jeglicher Übereinstimmungen zu dem Knoten an, der den Dienst anfordert.

Das Überlagerungsnetzwerk 210, das den Attributraum 300 umfasst, unterstützt Bereichsabfragen. Bereichsabfragen umfassen einen oder mehrere Attributbereiche, die einen erwünschten Dienst identifizieren. Die Informationsdienstknoten 130 sind unter Verwendung des Überlagerungsnetzwerks 210 wirksam, um Bereichsabfragen zu einem Attributteilraum zu routen, der den Bereich von Attributwerten oder einen Attributteilraum umfasst, der den Bereich von Attributwerten in der Abfrage schneidet. Zusätzlich kann die Abfrage mehrere Attributbereiche umfassen und kann die Abfrage zu mehr als einem Informationsdienstknoten geroutet werden, der einen Attributteilraum aufweist, der einen Attributbereich umfasst oder schneidet.

4 stellt ein Beispiel von einigen der Informationen dar, die in einem Informationsdienstknoten, wie beispielsweise dem Informationsdienstknoten 130b, gespeichert sind. Der Informationsdienstknoten 130b umfasst einen Speichercache 410, eine Überlagerungsroutingtabelle 420 und einen Nachbildungspositionscache 440. Der Speichercache 410 speichert lokale Abfragen 401 und globale Abfragen 402. Der Speichercache 410 speichert ferner lokale Anzeigen 405 und globale Anzeigen 406. Die globalen Abfragen 402 umfassen Abfragen, die durch das Überlagerungsnetzwerk 210 hindurch zu dem Informationsdienstknoten 130b geroutet werden, weil die Abfragen in den Attributteilraum fallen, den der Informationsspeicherknoten 130b besitzt. Die Abfrage 320, die in 3 gezeigt ist, ist ein Beispiel einer globalen Abfrage.

Die lokalen Abfragen 401 umfassen irgendeine Abfrage, die durch den Informationsdienstknoten 130b empfangen wird. Zum Beispiel kann der Informationsdienstknoten 130a eine Abfrage empfangen und die Abfrage zu dem Bestimmungsort derselben in dem Überlagerungsnetzwerk 210 weiterleiten, der den Informationsdienstknoten umfassen kann, der den Attributteilraum besitzt, in den die Abfrage fällt. Vor einem Weiterleiten der Abfrage zu dem Bestimmungsort derselben hin wird die Abfrage in dem Speichercache 410 lokal Cache-gespeichert. Ferner durchsucht der Informationsdienstknoten 130b vor einem Weiterleiten der Abfrage zu dem Bestimmungsort derselben hin die lokalen Anzeigen 405, die in dem Speichercache 410 gespeichert sind, um zu bestimmen, ob irgendwelche Übereinstimmungen mit der Abfrage gefunden werden. Falls eine Übereinstimmung gefunden wird, spricht der Informationsdienstknoten 130b auf die Abfrage beispielsweise durch ein Senden der übereinstimmenden Anzeige zu dem Knoten an, der den Dienst und den zugeordneten Dienstknoten anfordert. Der Informationsdienstknoten 130b kann fortfahren, die Abfrage zu dem Bestimmungsort derselben zu routen, weil der Bestimmungsort Anzeigen für Dienste umfassen kann, die mit der Abfrage übereinstimmen und die durch Dienstknoten näher an dem Knoten geliefert werden, der den Dienst anfordert. Alternativ leitet der Informationsdienstknoten 130b die Abfrage eventuell nicht weiter, falls eine Übereinstimmung lokal Cache-gespeichert ist.

Die globalen Anzeigen 406 umfassen Anzeigen, die durch das Überlagerungsnetzwerk 210 hindurch zu dem Informationsdienstknoten 130b geroutet werden, weil die Anzeigen in den Attributteilraum fallen, den der Informationsspeicherknoten 130b besitzt. Die Anzeige 310, die in 3 gezeigt ist, ist ein Beispiel einer globalen Anzeige für den Informationsdienstknoten 130a.

Die lokalen Anzeigen 405 umfassen irgendeine Anzeige, die durch den Informationsdienstknoten 130a empfangen wird. Beispielsweise kann der Informationsdienstknoten 130a eine Anzeige empfangen und die Anzeige zu dem Bestimmungsort derselben hin weiterleiten. Diese Anzeigen sind lokal in dem Speichercache 410 Cache-gespeichert und können durchsucht werden, um schnellere Ansprechzeiten für Abfragen zu liefern, falls in dem lokalen Cache Übereinstimmungen gefunden werden.

Der Informationsdienstknoten 130b umfasst ferner die Überlagerungsroutingtabelle 420. Die Überlagerungsroutingtabelle 420 umfasst die folgenden Felder: Ebene 421, IP-Adresse 422, Wahrscheinlichkeit 423 und Attributbereich 424. Die Ebene 421 ist im Allgemeinen der Anzahl von Malen zugeordnet, die der Informationsdienstknoten 130b die Arbeitslast desselben mit einem anderen Informationsdienstknoten geteilt hat. Wenn der Informationsdienstknoten 130b die Arbeitslast desselben mit einem anderen Informationsdienstknoten teilt, wird ein neuer Eintrag in der Routingtabelle in dem Informationsdienstknoten 130b auf einer größeren Ebene erzeugt als der bestehenden höchsten Ebene in der Routingtabelle. Beispielsweise wurden die Einträge 431 und 432 auf einer Ebene 1 erzeugt, als der Informationsdienstknoten 130b die Arbeitslast desselben mit den Informationsdienstknoten 130c teilte. Der Eintrag 433 wurde auf einer Ebene 2 erzeugt, als der Informationsdienstknoten 130b nachfolgend die Arbeitslast desselben mit dem Informationsdienstknoten 130d teilte. Eine Arbeitslastteilung kann durchgeführt werden, wenn eine Bestimmung vorgenommen wird, dass ein Informationsdienstknoten im Vergleich zu anderen Informationsdienstknoten in dem Überlagerungsnetzwerk 210 eine hohe Arbeitslast aufweist. Die Wahrscheinlichkeiten 423 geben die Wahrscheinlichkeit an, dass ein Informationsdienstknoten die erwünschten Daten aufweisen wird. Zum Beispiel gibt der Eintrag 430 an, dass der Informationsdienstknoten 130a immer anzeigen mit Speicher <= 1 GB speichert, und gibt der Eintrag 431 an, dass der Informationsdienstknoten 130c immer Anzeigen mit Plattenraum <= 2 GB speichert. Der Informationsdienstknoten 130c weist jedoch eine Wahrscheinlichkeit von 50 % eines Speicherns von Anzeigen mit Plattenraum <= 5 GB auf. Ein Erzeugen der Einträge in den Routingtabellen und die Wahrscheinlichkeiten sind detaillierter in den US-Patentanmeldungen beschrieben, die oben durch Bezugnahme aufgenommen wurden.

Das IP-Adressfeld 422 in der Routingtabelle 420 ist zu einem Identifizieren des Bestimmungsorts eines Informationsdienstknotens in einem speziellen Eintrag vorgesehen. Falls beispielsweise der Informationsdienstknoten 130b eine Anzeige empfängt und bestimmt, dass die Anzeige ein Speicherattribut < 1 GB aufweist, verwendet der Informationsdienstknoten 130b den Eintrag 430, um die Anzeige zu dem nächsten Bestimmungsort derselben zu routen, z. B. dem Informationsdienstknoten 130a. Die IP-Adresse des Informationsdienstknotens 130a kann in dem IP-Adressfeld des Eintrags 430 vorgesehen sein und der Informationsdienstknoten 130b verwendet ein IP-Routing, um die Nachricht zu dem Informationsdienstknoten 130a in dem Netzwerk 200 zu übertragen.

Der Nachbildungspositionscache 440 speichert Informationen, die der Anzahl von Malen zugeordnet sind, die jeder Dienstknoten kontaktiert wird, und Latenzen für die Dienstknoten, die kontaktiert wurden. Eine Nachbildung ist eine Kopie eines Informationsdienstknotens. Zum Beispiel kann ein Informationsdienstknoten bei einer neuen Position in dem Netzwerk 100 dupliziert sein, falls bestimmt wird, dass der ursprüngliche Informationsdienstknoten häufig durch Benutzerknoten in einem Bereich des Netzwerks 100 kontaktiert wurde und/oder Benutzerknoten, die Nachrichten, wie beispielsweise Antworten auf Abfragen, von dem ursprünglichen Informationsdienstknoten empfangen, hohe Latenzen zu dem Informationsdienstknoten erfahren haben. Der Informationsdienstknoten 130b kann die Informationen in dem Nachbildungspositionscache 440 verwenden, um zu bestimmen, ob eine Nachbildung in einem anderen Bereich des Netzwerks 100 hinzuzufügen ist, um eine Latenz zu reduzieren.

5 stellt ein Beispiel eines Routens einer Abfrage 501 in dem Überlagerungsnetzwerk 210 dar. Ein Benutzerknoten 110a überträgt die Abfrage 501 zu einem Informationsdienstknoten, z. B. dem Informationsdienstknoten 130a, in dem Überlagerungsnetzwerk 210. Bei einem Beispiel kann der Informationsdienstknoten, mit dem der Benutzerknoten 110aeinen anfänglichen Kontakt in dem Überlagerungsnetzwerk 210 herstellt, basierend auf einer Netzwerknähe ausgewählt sein. Während eines Initialisierungsschritts, wenn der Benutzerknoten 110a dem Partner-zu-Partner-Netzwerk 100 beitritt, empfängt beispielsweise der Benutzerknoten 110a eine Nachricht von einem Informationsdienstknoten, die die IP-Adresse des Informationsdienstknotens in enger Netzwerknähe zu dem Benutzerknoten 110a angibt. Ein Beispiel eines Bestimmens von Positionsinformationen für Knoten unter Verwendung von Abständen, die basierend auf einer Netzwerkmetrik gemessen sind, wie beispielsweise einer Latenz, einer Anzahl von Sprüngen, etc., ist in der US-Patentanmeldung Seriennummer 10/767,285, eingereicht am 30. Januar 2004 und mit dem Titel „Selecting Nodes Close To Another Node In A Network Using Location Information For The Nodes" von Zhichen Xu et al. beschrieben, die an die Anmelderin der vorliegenden Erfindung übertragen ist. Die Positionsinformationen werden verwendet, um eine Netzwerknähe zu anderen Knoten in dem Netzwerk zu bestimmen, und können verwendet werden, um einen nächstgelegenen Informationsdienstknoten auszuwählen. Andere Techniken zum Bestimmen von Abständen und Positionsinformationen in einem Netzwerk können ebenfalls verwendet werden.

Nachdem der Benutzerknoten 110a einen Informationsdienstknoten in enger Nähe identifiziert, z. B. den Informationsdienstknoten 130a, überträgt der Benutzerknoten 110b die Abfrage 501 zu dem Informationsdienstknoten 130a. Die Abfrage 501 umfasst Attributwerte, die einen Dienst definieren, der durch den Benutzerknoten 110a gewünscht wird. Die Attributwerte können ein Bereich oder ein einziger Wert sein. Bei diesem Beispiel umfasst die Abfrage 501 die folgenden Attributwerte:

• Speicher: 2 GB
• Plattenraum: 10 GB
• Betriebssystem: Linux 2.4
• Ansprechzeit: 50-100 ms

Der Informationsdienstknoten 130a empfängt die Abfrage 501. Der Attributteilraum für den Informationsdienstknoten 130a umfasst Speicher <= 1 GB. Die Abfrage 501 umfasst einen Attributwert von 2 GB für einen Speicher. Der Attributwert von 2 GB ist nicht in dem Attributbereich von Speicher <= 1 GB für den Attributteilraum des Informationsdienstknotens 130a enthalten und somit fällt die Abfrage 501 nicht in den Attributteilraum des Informationsdienstknotens 130a.

Der Informationsdienstknoten 130a identifiziert einen Informationsdienstknoten aus der Routingtabelle desselben, der die Attributwerte der Abfrage 501 umfasst. Zum Beispiel beginnt der Informationsdienstknoten 130a mit dem Eintrag auf niedrigster Ebene, z. B. Ebene 0, und durchsucht die Routingtabelle desselben nach einem Eintrag, der Attributwerte umfasst, die die Attributwerte in der Abfrage 501 schneiden. Ein Eintrag 510 ist gezeigt, der Folgendes umfasst: Ebene 0, IP-Adresse für den Informationsdienstknoten 130b, Wahrscheinlichkeit von 1 und Speicher > 1 GB. Basierend auf dem Eintrag 510 überträgt der Informationsdienstknoten 130a die Abfrage 501 zu dem Informationsdienstknoten 130b. Der Attributteilraum für den Informationsdienstknoten 130b umfasst Ansprechzeit < 20 ms, was in dem Ansprechzeitbereich von 50-100 ms nicht enthalten ist, der in der Abfrage 501 spezifiziert ist. Somit durchsucht der Informationsdienstknoten 130d die Routingtabelle desselben und findet beispielsweise den Eintrag 511. Der Eintrag 511 identifiziert den Informationsdienstknoten 130d und die Abfrage 501 wird an den Informationsdienstknoten 130d übertragen. Der Informationsdienstknoten 130d weist einen Attributteilraum auf, der die Attributwerte der Abfrage 501 umfasst, und somit fällt die Abfrage 501 in diesen Attributteilraum. Der Informationsdienstknoten 130a bestimmt, ob irgendwelche Anzeigen, die in dem globalen Cache desselben gespeichert sind, die Abfrage erfüllen. Ein Dienst muss eventuell beispielsweise alle Attributwerte aufweisen, die in der Abfrage 501 spezifiziert sind, damit derselbe als eine Übereinstimmung betrachtet wird. Falls eine Übereinstimmung gefunden wird, spricht der Informationsdienstknoten 130a auf die Abfrage 501 durch ein Senden der Anzeigen, einschließlich beispielsweise der IP-Adresse des Dienstknotens, der den Dienst liefert, an den Benutzerknoten 110a an. Der Informationsdienstknoten 130a kann ferner eine Nachricht an den Dienstknoten für die Anzeige, zusammen mit der IP-Adresse des Benutzerknotens 110, senden, die angibt, dass der Benutzerknoten 110a den Dienst anfordert, der in der Anzeige beschrieben ist. Die Abfrage 501 ist ferner in dem globalen Cache des Informationsdienstknotens 130c gespeichert.

Die Informationsdienstknoten 130a und 130b können eine Kopie der Abfrage 501 in dem lokalen Cache derselben vor einem Weiterleiten der Abfrage 501 speichern. Ferner können die Informationsdienstknoten 130a und 130b bestimmen, ob irgendwelche Anzeigen, die in dem lokalen Cache derselben gespeichert sind, die Abfrage 501 erfüllen, bevor die Abfrage weitergeleitet wird. Falls eine Übereinstimmung gefunden wird, kann der Informationsdienstknoten 130a durch ein Senden der Anzeige, einschließlich beispielsweise der IP-Adresse des Dienstknotens, der den Dienst liefert, an den Benutzerknoten 110a auf die Abfrage 501 ansprechen. Der Informationsdienst 130a kann ferner eine Nachricht zusammen mit der IP-Adresse des Benutzerknotens 110a, die angibt, dass der Benutzerknoten 110a den Dienst in der Anzeige anfordert, an den Dienstknoten senden, der den Dienst liefert, der in der Anzeige beschrieben ist.

Bei dem oben mit Bezug auf 5 beschriebenen Beispiel wird die Abfrage 501 zu dem Informationsdienstknoten 130d geroutet, weil die Abfrage 501 in den Attributteilraum des Informationsdienstknotens 130d fällt. Die Abfrage 501 kann weiterhin zu anderen Informationsdienstknoten geroutet werden, die eventuell Anzeigen umfassen, die mit der Abfrage 501 übereinstimmen. Zum Beispiel kann ein weiterer Informationsdienstknoten den folgenden Attributteilraum umfassen: Speicher > 1 GB, Plattenraum > 5 GB, Ansprechzeit >= 20 ms und Betriebssystem einschließlich Linux 1.0-2.5. Der Informationsdienstknoten 130d kann die Abfrage 501 zu dem Informationsdienstknoten routen, der den oben beschriebenen Attributteilraum umfasst, weil die Abfrage 501 auch in diesen Attributteilraum fällt. Somit kann der Benutzerknoten 110a Suchergebnisse von mehreren Informationsdienstknoten empfangen, einschließlich Informationsdienstknoten, die Übereinstimmungen in den lokalen Caches derselben finden, und der Benutzerknoten 110a kann einen Dienstknoten zum Empfangen des erwünschten Dienstes auswählen.

Zusätzlich ist zu beachten, dass das Überlagerungsnetzwerk 210 Bereichsabfragen unterstützt. Die Abfrage 501 umfasst einen Bereich von Attributwerten, 50-100 ms, für das Attribut Ansprechzeit. Die Abfrage 501 kann einen oder mehrere Bereiche umfassen und wird zu Informationsdienstknoten geroutet, die den Bereich schneiden. Zum Beispiel kann die Abfrage 501 zu einem Attributteilraum geroutet werden, der irgendeinen der Attributwerte 50-100 ms umfasst.

6 stellt ein Routing einer Anzeige 601 in dem Überlagerungsnetzwerk 210 dar. Anzeigen werden auf ähnliche Weise zu Abfragen in dem Überlagerungsnetzwerk 210 geroutet. Die Dienstknoten 120 messen die Attribute derselben regelmäßig und übertragen die Anzeigen derselben einschließlich der gemessenen Attribute an das Überlagerungsnetzwerk 210. Jede Anzeige kann einen Attributwert und einen Bereich von Attributwerten für jedes Attribut in einem vorbestimmten Satz von Attributen umfassen. Ein Beispiel eines vorbestimmten Satzes von Attributen umfasst Speicher, Plattenraum, Betriebssystem, Durchschnittslast eines Dienstknotens, der einen Dienst liefert, Anwendungen, Dienstbetriebszeit und Ansprechzeit eines Informationsdienstknotens, der einen Dienst liefert.

6 stellt eine Anzeige 601 dar, die durch den Dienstknoten 120b erzeugt wird. Die Anzeige 601 umfasst das Folgende:

• Speicher: 1 GB
• Plattenraum: 2.5-5 GB
• Betriebssystem: Linux 2.4
• Durchschnittslast: 0
• Anwendungen: Maya, Renderman
• Dienstbetriebszeit: 99,5 %
• Ansprechzeit: <= 20 ms

Der Dienstknoten 120b kann die Anzeige 601 an den Informationsdienstknoten 130a übertragen, weil beispielsweise der Informationsdienstknoten 130a sich in enger Nähe zu dem Dienstknoten 120b befindet. Die Anzeige 601 fällt nicht in den Attributteilraum, den der Informationsdienstknoten 130a besitzt, weil die Anzeige 601 einen Speicher > 1 GB aufweist und der Attributteilraum für den Informationsdienstknoten 130a einen Speicher <= 1 GB umfasst. Somit identifiziert der Informationsdienstknoten 130a den Informationsdienstknoten 130b aus einem Eintrag 610 in der Routingtabelle desselben. Der Informationsdienstknoten 130b beginnt beispielsweise mit dem Eintrag auf niedrigster Ebene und durchsucht die Routingtabelle desselben nach einem Eintrag, der Attributwerte umfasst, die Attributwerte in der Anzeige 601 schneiden. Der Eintrag 610 identifiziert den Informationsdienstknoten 130b und die Anzeige 601 wird an den Informationsdienstknoten 130b übertragen. Die Anzeige 601 fällt nicht in den Attributteilraum, den der Informationsdienstknoten 130b besitzt, weil der Plattenraum in der Anzeige 601 kleiner oder gleich 5 GB ist. Der Informationsdienstknoten 130b identifiziert den Informationsdienstknoten 130c aus einem Eintrag 611 in der Routingtabelle desselben, der den Attributwert Plattenraum <= 5 GB umfasst. Die Anzeige 601 fällt in den Attributteilraum des Informationsdienstknotens 130c und ist bei dem Informationsdienstknoten 130c gespeichert. Vor einem Weiterleiten der Anzeige 601 speichern die Informationsdienstknoten 130a und 130b die Anzeige 601 in dem lokalen Cache derselben. Zusätzlich kann der Informationsdienstknoten 130c die Anzeige 601 für eine Speicherung in dem globalen Cache desselben kopieren und die Anzeige 601 zu anderen Informationsdienstknoten weiterleiten, die Attributteilräume umfassen, in die die Anzeige 601 fällt.

Eine Arbeitslast wird regelmäßig durch jeden der Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 gemessen, das in 2 gezeigt ist. Eine Arbeitslast kann aus einer oder mehreren Metriken berechnet werden, einschließlich der Anzahl von gespeicherten Anzeigen, der Anzahl von verarbeiteten Abfragen, der durchschnittlichen Latenz eines Verarbeitens einer Abfrage, eines Durchsatzes, z. B. pro Sekunde verarbeitete Abfragen, etc., aber nicht darauf begrenzt.

Am Anfang jeder Epoche nehmen die Informationsdienstknoten 130 an einer Austauschphase teil. Jede Epoche kann eine Zeitperiode umfassen, zu der eine Austauschphase und/oder eine Verbreitungsphase durchgeführt werden. Ein Epochenzähler oder die Zeit des Anfangs der nächsten Epoche kann in der Obere-K-Liste enthalten sein. Der Epochenzähler oder die Anfangszeit der nächsten Epoche können durch einen Informationsdienstknoten verwendet werden, um zu bestimmen, ob eine Liste, die durch den Informationsdienstknoten empfangen wird, für die aktuelle Epoche vorgesehen ist. Während der Austauschphase wird eine Liste von oberen K Knoten einen Dienstbaum hinaufgeroutet, der aus den Informationsdienstknoten 130 gebildet ist. An dem oberen Ende des Dienstbaums befindet sich ein Führungsknoten, der ein vorausgewählter Informationsdienstknoten sein kann.

Eine Obere-K-Liste, die die höchsten Arbeitslasten umfasst, die durch die Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 gemessen werden, wird durch jeden der Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 hindurch zu einem Führungsknoten 701 geroutet, der in 7 gezeigt ist. Wenn die Obere-K-Liste durch jeden der Informationsdienstknoten 130 geroutet wird, vergleicht jeder Informationsdienstknoten die gemessene Arbeitslast desselben mit anderen Arbeitslasten in der Obere-K-Liste. Falls eine Arbeitslast eines Informationsdienstknotens, der die Obere-K-Liste empfängt, größer als eine andere Arbeitslast in der Obere-K-Liste ist, schließt der Informationsdienstknoten die Arbeitslast desselben in die Obere-K-Liste ein, wobei möglicherweise die kleinere Arbeitslast ersetzt wird. Die Obere-K-Liste kann eine vorbestimmte Anzahl von Arbeitslasten, K, umfassen. Falls somit die Obere-K-Liste weniger als K Arbeitslasten umfasst, schließt der Informationsdienstknoten die Arbeitslast desselben in die Obere-K-Liste ein. Ferner kann die Obere-K-Liste anfänglich aus mehreren Obere-K-Listen gebildet sein. Beispielsweise kann jedes Blatt eines Dienstbaums, der die Informationsdienstknoten 130 umfasst, eine Obere-K-Liste hervorbringen. Die Obere-K-Listen können an Informationsdienstknoten kombiniert werden, die mehrere Obere-K-Listen empfangen. Schließlich kompiliert der Führungsknoten 701 eine einzige Obere-K-Liste.

Zusätzlich zu der Obere-K-Liste werden ein L-min-Ebene-Vektor und ein höchster Routingtabellenwert in dem Überlagerungsnetzwerk durch das Überlagerungsnetzwerk 210 hindurch ausgebreitet. Der min-Ebene-Vektor umfasst eine Anzahl L von minimalen Routingtabellenebenen in dem Überlagerungsnetzwerk 210. Wenn der min-Ebene-Vektor durch jeden der Informationsdienstknoten 130 hindurch geroutet wird, vergleicht jeder Informationsdienstknoten die höchste Ebene der Routingtabelle desselben mit anderen Werten in dem min-Ebene-Vektor. Falls die höchste Ebene in der Routingtabelle eines Informationsdienstknotens, der den min-Ebene-Vektor empfängt, kleiner als ein anderer Wert in dem min-Ebene-Vektor ist, schließt der Informationsdienstknoten die höchste Ebene desselben in den min-Ebene-Vektor ein, wobei möglicherweise der größere Wert ersetzt wird. Der min-Ebene-Vektor kann eine vorbestimmte Anzahl von Werten, L, umfassen. Falls somit der min-Ebene-Vektor weniger als L Werte umfasst, schließt der Informationsdienstknoten die höchste Ebenen desselben in den min-Ebene-Vektor ein. Ferner kann der min-Ebene-Vektor anfänglich aus mehreren min-Ebene-Vektoren gebildet sein. Beispielsweise kann jedes Blatt eines Dienstbaums, der die Informationsdienstknoten 130 umfasst, einen min-Ebene-Vektor hervorbringen. Die min-Ebene-Vektoren können bei Informationsdienstknoten, die mehrere min-Ebene-Vektoren empfangen, kombiniert werden. Schließlich kompiliert der Führungsknoten 701 einen einzigen min-Ebene-Vektor, der eine Anzahl L von Werten umfasst.

Die höchste Ebene der Routingtabelle in den Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 wird ebenfalls durch jeden der Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 hindurch zu dem gleichen Führungsknoten 701 geroutet, der in 7 gezeigt ist. Wenn die höchste Ebene durch jeden der Informationsdienstknoten 130 geroutet wird, vergleicht jeder Informationsdienstknoten die höchste Ebene der Routingtabelle desselben mit dem empfangenen Wert. Falls die höchste Ebene in der Routingtabelle des Informationsdienstknotens größer als der empfangene Wert ist, ersetzt der Informationsdienstknoten den empfangenden Wert mit seinem eigenen. Jedes Blatt eines Dienstbaums, der die Informationsdienstknoten 130 umfasst, bringt eine eigene höchste Ebene desselben hervor. Diese Werte können an Informationsdienstknoten, die mehrere höchste Ebenenwerte empfangen, kombiniert werden. Schließlich kompiliert der Führungsknoten 701 eine einzige höchste Ebene. Die höchste Routingtabellenebene kann zu einer Zweckmäßigkeit in dem L-min-Ebene-Vektor enthalten sein und durch das Überlagerungsnetzwerk hindurch mit dem L-min-Ebene-Vektor übertragen werden.

Während der Austauschphase umfasst jeder der Informationsdienstknoten 130 einen Identifizierer in der Obere-K-Liste, wie beispielsweise eine IP-Adresse, wenn die Obere-K-Liste zu dem Führungsknoten 701 geroutet wird. Der Identifizierer ist enthalten, selbst falls der Informationsdienstknoten, der die Obere-K-Liste empfängt, die Arbeitslast desselben nicht in die Obere-K-Liste einschließt. In einer Verbreitungsphase wird die Obere-K-Liste unter Verwendung der Identifizierer den Dienstbaum herunter durch jeden der Informationsdienstknoten 130 hindurch übertragen. Zum Beispiel wird die Obere-K-Liste an jeden der Informationsdienstknoten 130 in der umgekehrten Reihenfolge dazu übertragen, wie jeder Informationsdienstknoten die Obere-K-Liste empfangen hat. Wenn ferner ein neuer Informationsdienstknoten dem Informationsdienst beitritt, empfängt der neue Informationsdienstknoten die Obere-K-Liste einschließlich Arbeitslasten, die in der letzten Epoche gemessen wurden, zusätzlich zu einem Erzeugen einer neuen Routingtabelle und einem Speichern von Anzeigen und Abfragen in den globalen Caches für den neuen Informationsdienstknoten.

Die Austausch- und die Verbreitungsphase sind ferner mit Bezug auf 7 dargestellt. 7 stellt einen Abschnitt eines Dienstbaums dar, der die Informationsdienstknoten 130a-d in dem Überlagerungsnetzwerk 210 umfasst. Der Führungsknoten 701 ist der Informationsdienstknoten 130a.

Während der Austauschphase messen die Informationsdienstknoten 130a-d die Arbeitslasten derselben. Die Obere-K-Liste von Arbeitslasten wird den Dienstbaum hinauf von den Blättern aus, z. B. den Informationsdienstknoten 130d und 130e, zu dem Führungsknoten 701 übertragen.

Die Informationsdienstknoten 130 erzeugen Arbeitslastvektoren für die Obere-K-Liste und min-Ebene-Vektoren zum Schätzen, wie versetzt der Dienstbaum ist oder wie ausgeglichen der Dienstbaum ist. Die min-Ebene-Vektoren können verwendet werden, um einen Informationsdienstknoten für eine Arbeitslastteilung auszuwählen, während versucht wird, einen ausgeglichenen Dienstbaum beizubehalten. Zum Beispiel wird die Differenz zwischen der höchsten (maximalen) Routingtabellenebene in dem Überlagerungsnetzwerk 210 und einem minimalen Wert in dem min-Ebene-Vektor mit einer Schwelle verglichen. Falls die Differenz größer als eine Schwelle ist, dann kann ein Informationsdienstknoten, der den minimalen Wert aufweist, für eine Arbeitslastteilung bei einem Versuch ausgewählt werden, einen ausgeglichenen Dienstbaum beizubehalten. Somit ist der Vergleich der Differenz zwischen der höchsten (maximalen) Routingtabellenebene in dem Überlagerungsnetzwerk 210 und dem minimalen Wert in dem min-Ebene-Vektor mit einer Schwelle ein Beispiel eines Schätzens, wie versetzt der Dienstbaum ist oder wie ausgeglichen der Dienstbaum ist. Basierend auf dieser Schätzung kann ein Informationsdienstknoten für eine Arbeitslastteilung ausgewählt werden, um den Dienstbaum auszugleichen.

Wie es in 7 gezeigt ist, messen die Informationsdienstknoten 130d und 130e die Arbeitslasten derselben und erzeugen die Arbeitslastvektoren 710 bzw. 711. Die Arbeitslastvektoren in dem Überlagerungsnetzwerk 210, die die K höchsten Arbeitslasten umfassen, werden kombiniert, um die Obere-K-Liste zu bilden. Jeder Arbeitslastvektor umfasst zumindest die Identifikation des Informationsdienstknotens und die gemessene Arbeitslast.

Die Informationsdienstknoten 130d und 130e erzeugen ferner min-Ebene-Vektoren 720 bzw. 721. Die min-Ebene-Vektoren umfassen die höchste Ebene in der Routingtabelle für den Informationsdienstknoten. Beispiele von höchsten Ebenen für die Informationsdienstknoten 130a-d sind in 8A-D gezeigt und umfassen 0, 2, 1 bzw. 2. Die min-Ebene-Vektoren werden verwendet, um eine L-min-Ebene-Liste zu bilden, die die L niedrigsten Ebenen in dem Überlagerungsnetzwerk 210 umfasst. Die L-min-Ebene-Liste umfasst ferner eine Informationsdienstknoten-ID und eine Routingtabellenebene für den Informationsdienstknoten, der die höchste Ebene in dem Überlagerungsnetzwerk 210 aufweist.

Es können mehrere Obere-K-Listen während der Austauschphase ausgetauscht und bei Zwischenknoten, wie beispielsweise dem Informationsdienstknoten 130b, kombiniert werden. Beispielsweise sind die Arbeitslastvektoren 710 und 711 Obere-K-Listen, die zu dem Informationsdienstknoten 130b übertragen werden. Unter der Annahme, dass K Drei beträgt, kombiniert der Informationsdienstknoten 130b die Arbeitslastvektoren 710 und 711 und den eigenen Arbeitslastvektor desselben zu der Obere-K-Liste 712. Die Obere-K-Liste 712 wird zu dem Führungsknoten 701 hin übertragen und kann die Arbeitslasten der Informationsdienstknoten 130c und/oder 130a umfassen, falls die Arbeitslasten derselben höher als die Arbeitslasten in der Obere-K-Liste 712 sind, die durch jeden Informationsdienstknoten empfangen wird.

Während der Austauschphase werden ferner die min-Ebene-Vektoren 720 und 721 zu dem Informationsdienstknoten 130b übertragen. Der Informationsdienstknoten 130b kombiniert die min-Ebene-Vektoren 720 und 721 und den eigenen min-Ebene-Vektor desselben zu der L-min-Ebene-Liste 722 (auch als der L-min-Ebene-Vektor bezeichnet). Die L-min-Ebene-Liste wird zu dem Führungsknoten 701 hin übertragen und kann die höchsten Routingtabellenebenen für die Informationsdienstknoten 130c und/oder 130a umfassen, falls die Ebenen derselben niedriger als die Ebenen in der L-min-Ebene-Liste sind. Zusätzlich umfasst die L-min-Ebene-Liste den Dienstknoten, der die höchste Ebene in dem Überlagerungsnetzwerk 210 aufweist. Der Unterschied zwischen der höchsten Routingtabellenebene und der minimalen Ebene eines Informationsdienstknotens, der anfänglich für eine Arbeitslastteilung ausgewählt wird, kann mit einer Schwelle vergleichen werden, um zu bestimmen, ob der anfänglich ausgewählte Informationsdienstknoten die Auswahl für eine Arbeitslastteilung bleibt. Dieser Vergleich ist eine Technik zum Beibehalten eines ausgeglichenen Dienstbaums.

Während der Austauschphase wird ferner die Reihenfolge der Informationsdienstknoten, die die Obere-K-Liste empfangen, an dem Informationsdienstknoten 130 gespeichert, derart, dass die Obere-K-Liste zu allen Informationsdienstknoten während der Ausbreitungsphase ausgebreitet werden kann. Reihenfolgeinformationen 730 umfassen beispielsweise Identifikationen, wie beispielsweise IP-Adressen, die Informationsdienstknoten 130e und 130d, derart, dass der Informationsdienstknoten 130b die Obere-K-Liste 712 während der Ausbreitungsphase zu den Informationsdienstknoten 130e und 130d überträgt. Andere Beispiele von Reihenfolgeinformationen umfassen Reihenfolgeinformationen 731 an dem Informationsdienstknoten 130c, wie beispielsweise die IP-Adresse des Informationsdienstknotens 130b, und Reihenfolgeinformationen 732 an dem Informationsdienstknoten 130a, wie beispielsweise die IP-Adresse des Informationsdienstknotens 130c. Während der Ausbreitungsphase wird somit die Obere-K-Liste 712 den Dienstbaum herunter zu allen Informationsdienstknoten 130 übertragen. Die K-min-Ebene-Liste wird ebenfalls während der Ausbreitungsphase den Dienstbaum herunter übertragen.

Ein Obere-K-Routing-Algorithmus wird zum Bestimmen verwendet, zu welchem Informationsdienstknoten die Obere-K-Liste übertragen werden soll, basierend auf der Routingtabelle in dem Informationsdienstknoten, der die Obere-K-Liste überträgt. 8A-D stellen beispielsweise die Routingtabellen für die Informationsdienstknoten 130a-d dar. Um die Obere-K-Liste zu dem Führungsknoten zu routen, überträgt der Informationsdienstknoten, der die Obere-K-Liste empfängt, die Obere-K-Liste zu der maximalen Ebene in der Routingtabelle desselben, die für den Bereich unterhalb eines entsprechenden Teilungswerts verantwortlich ist. Die Informationen in der Obere-K-Liste identifizieren die oberen K Knoten und die Arbeitslasten derselben, die bis dahin bekannt sind, wenn die Obere-K-Liste zu dem Führungsknoten geroutet wird. Unter Bezugnahme auf die Routingtabelle für den Informationsdienstknoten 130d in der 8D beispielsweise ist die höchste oder maximale Ebene in dem Eintrag 840 mit einer Ebene von 2. Der Eintrag 840 umfasst einen Attributteilungswert von 20 ms für das Ansprechzeitattribut. Der Bereich für eine Ansprechzeit umfasst: Ansprechzeit <= 20 ms. Weil der Bereich unter dem entsprechenden Teilungswert liegt, d. h. geringer als der Teilungswert von 20 ms, wird der Knoten 130b als der nächste Knoten zum Empfangen der Obere-K-Liste identifiziert. Der Knoten 130d überträgt die Obere-K-Liste an den Knoten 130b.

Der Informationsdienstknoten 130b empfängt die Obere-K-Liste und verwendet basierend auf dem Obere-K-Routing-Algorithmus den Eintrag 820 der Routingtabelle für den Informationsdienstknoten 130b, der in 8b gezeigt ist, um den Informationsdienstknoten 130c als den nächsten Informationsdienstknoten zu identifizieren, der die Obere-K-Liste empfangen soll. Der Informationsdienstknoten 130b schließt die Arbeitslast desselben in die Obere-K-Liste ein und überträgt die Obere-K-Liste an den Informationsdienstknoten 130c.

Bei diesem Beispiel ist der Wert von K = 3. Der Informationsdienstknoten 130c empfängt ferner die Arbeitslasten der Informationsdienstknoten 130b, 130d und 130e, wie es in 7 gezeigt ist. Falls die Arbeitslast des Informationsdienstknotens 130c geringer als die Arbeitslasten der Informationsdienstknoten 130b, 130d und 130e ist, dann schließt der Informationsdienstknoten 130c die Arbeitslast desselben nicht in die Obere-K-Liste ein. Der Eintrag 830 der Routingtabelle für den Informationsdienstknoten 130c identifiziert den Informationsdienstknoten 130a als den nächsten Knoten zum Empfangen der Obere-K-Liste basierend auf dem Obere-K-Routing-Algorithmus. Der Informationsdienstknoten 130a bestimmt, ob die Arbeitslast desselben größer als die drei Arbeitslasten in der Obere-K-Liste ist. Falls dem so ist, schließt der Informationsdienstknoten 103a die Arbeitslast desselben in die Obere-K-Liste ein. Ferner ist der Informationsdienstknoten 130a der Führungsknoten. Der Führungsknoten ist der Informationsdienstknoten mit lediglich Attributbereichen, die größer als ein entsprechender Teilungswert in der Routingtabelle desselben sind. Die Routingtabelle für den Informationsdienstknoten 130a, die in 8A gezeigt ist, umfasst einen Eintrag 810. Der Eintrag 810 umfasst einen Attributbereich, der größer als der entsprechende Teilungswert von 1 GB ist. Somit umfasst die Routingtabelle des Informationsdienstknotens 130a lediglich Attributbereiche, die größer als ein entsprechender Teilungswert sind, und der Informationsdienstknoten 130a ist der Führungsknoten. Im Gegensatz dazu umfassen die Routingtabellen der Informationsdienstknoten 130b-d zumindest einen Attributbereich, der geringer als entsprechender Teilungswert ist, wie beispielsweise die Einträge 820, 830 und 840.

Nachdem der Führungsknoten die Obere-K-Liste empfängt, beginnt die Ausbreitungsphase. Wie es in 7 gezeigt ist, überträgt der Führungsknoten, z. B. der Informationsdienstknoten 130a, die Obere-K-Liste an den Informationsdienstknoten 130c. Die Obere-K-Liste wird schließlich zu allen Informationsdienstknoten ausgebreitet, beispielsweise in der umgekehrten Reihenfolge dazu, wie die Informationsdienstknoten die Obere-K-Liste vorhergehend empfingen, als dieselbe den Dienstbaum hinauf zu dem Führungsknoten hin geroutet wurde.

Die Obere-K-Liste umfasst eine Liste von K höchsten Arbeitslasten in dem Überlagerungsnetzwerk 210. Eine wie hierin verwendete Liste umfasst eine Datendarstellung von einem oder mehreren Werten, die zwischen Knoten übertragen werden können. Beispielsweise umfasst die Obere-K-Liste Werte für die größten Arbeitslasten in dem Überlagerungsnetzwerk 210. Diese Werte werden zwischen den Informationsdienstknoten 130 übertragen. Zusätzlich zu einem Umfassen von Arbeitslasten umfasst die Obere-K-Liste einen Identifizierer des Informationsdienstknotens, der die Arbeitslast in der Obere-K-Liste aufweist. Ein Beispiel eines Identifizierers ist eine IP-Adresse, aber es können andere Identifizierer verwendet werden.

Die in 8B-D gezeigten Routingtabellen können basierend auf Teilungsalgorithmen erzeugt werden, die verwendet werden, um Arbeitslasten für die Informationsdienstknoten auszugleichen. Ein Typ eines Teilungsalgorithmus ist ein lokaler Teilungsalgorithmus, der verwendet wird, um die Arbeitslast eines Informationsdienstknotens zu teilen, wie beispielsweise eines Informationsdienstknotens in der Obere-K-Liste, der eine hohe Arbeitslast aufweist. Die Arbeitslast des Informationsdienstknotens kann mit einem anderen Informationsdienstknoten geteilt werden, wie beispielsweise einem neuen Informationsdienstknoten, der dem Überlagerungsnetzwerk 210 beitritt, oder einem existierenden Informationsdienstknoten.

Der lokale Teilungsalgorithmus wird verwendet, um ein Attribut und zumindest einen Attributteilwert zum Teilen der Arbeitslast eines Informationsdienstknotens zu identifizieren. Jede Anzeige kann einen vorbestimmten Satz von Attributen und möglicherweise Attributwerte für jedes Attribut in dem Satz von Attributen umfassen. Ein Beispiel einer Anzeige, die den Satz von Attributen und entsprechende Attributwerte umfasst, ist oben in Tabelle 3 gezeigt. Der lokale Teilungsalgorithmus wird verwendet, um ein Attribut aus dem Satz von Attributen und zumindest einen Attributteilwert für das ausgewählte Attribut auszuwählen, um die Arbeitslast eines Informationsdienstknotens aufzuteilen.

9A-C helfen den Prozess zu zeigen, durch den Informationsdienstknoten die Arbeitslast unter denselben verteilen, wenn neue Knoten dem Überlagerungsnetzwerk 210 beitreten. Es kann. eine Zutrittsstrategie verwendet werden, um einen Zutritt zu dem Überlagerungsnetzwerk 210 zu steuern. Beispielsweise kann einem Knoten gestattet werden, dem Überlagerungsnetzwerk 210 beizutreten, falls der Knoten eine Betriebszeit aufweist, die größer als eine Schwelle ist, falls der Knoten nicht vorübergehend ist und falls der Knoten vorbestimmte Hardwareattribute umfasst, wie beispielsweise eine Verarbeitungsgeschwindigkeit, einen Plattenraum und einen Speicher größer vorbestimmten Schwellen.

Bei diesem Beispiel war anfänglich der Informationsdienstknoten 130a der einzige Knoten, der den Informationsdienst liefert, wie beispielsweise der einzige Knoten, der Anzeigen speichert und auf Abfragen anspricht. Dann tritt der Informationsdienstknoten 130b dem Informationsdienst bei. Durch ein Anwenden eines lokalen Teilungsalgorithmus bestimmt der Informationsdienstknoten 130a, dass eine gleichmäßige Verteilung der Arbeitslast desselben erreicht werden kann, falls der Informationsdienstknoten 130a Anzeigen speichert und auf Abfragen mit Speicher <= 1 GB anspricht, d. h. einen Attributteilraum von Speicher <= 1 GB aufweist, und der Informationsdienstknoten 130b Anzeigen speichert und auf Abfragen mit Speicher > 1 GB anspricht, d. h. einen Attributteilraum von Speicher > 1 GB aufweist. Diese Arbeitslastteilung ist in 9A dargestellt, die die Attributteilräume und die Routingtabellen der Informationsdienstknoten 130a und 130b nach der Teilung zeigt.

Der Informationsdienstknoten 130c ist der nächste Knoten, der dem Informationsdienst und dem Überlagerungsnetzwerk 210 beitritt, das den Informationsdienst liefert, und die Arbeitslasten von einem oder mehreren der Informationsdienstknoten 130a und 130b sollten umverteilt werden. Eine Option besteht darin, die Arbeitslasten aller Informationsdienstknoten, die aktuell den Informationsdienst liefern, z. B. die Informationsdienstknoten 130a und 130b, global auszuwerten. Dies wird durch Anwenden eines globalen Teilungsalgorithmus erreicht, der alle Informationsdienstknoten beeinflusst und möglicherweise die Arbeitslast aller Informationsdienstknoten umverteilt. Eine andere Option besteht darin, einen lokalen Teilungsalgorithmus anzuwenden, der die Arbeitslast eines einzigen Informationsdienstknotens jedes Mal dann teilt, wenn ein neuer Knoten dem Informationsdienst beitritt, und dann regelmäßig eine globale Umverteilung durchführt.

9B stellt eine lokale Umverteilung der Arbeitslast des Informationsdienstknotens 130b dar. Unterschiedliche Typen von lokalen Teilungsalgorithmen können verwendet werden, um zu bestimmen, wie der Attributteilraum des Informationsdienstknotens 130b mit dem Informationsdienstknoten 130c zu teilen ist. Bei einem Beispiel wird ein iterativer Cluster-Algorithmus, wie beispielsweise ein k-Mittel-Clustern, verwendet, um ein Attribut und einen Attributteilwert basierend auf zwei Clustern auszuwählen, die durch den Cluster-Algorithmus gefunden werden. Bei einem anderen Beispiel wird ein Cluster-Algorithmus, wie beispielsweise der gleiche k-Mittel-Cluster-Algorithmus, verwendet, um drei Cluster zu bestimmen, und die drei Cluster werden verwendet, um ein Attribut und Attributteilwerte zum Teilen der Arbeitslast des Informationsdienstknotens 130b auszuwählen.

9B stellt die Attributteilräume und die Routingtabellen für die Informationsdienstknoten 130b und 130c dar, nachdem ein Cluster-Algorithmus verwendet wird, um drei Cluster zum Teilen der Arbeitslast des Informationsdienstknotens 130b mit dem Informationsdienstknoten 130c zu bestimmen.

Man nehme an, dass ein Plattenraum das Attribut ist, das zum Teilen ausgewählt ist. Tabelle 4 unten stellt die Verteilung von Anzeigen und Abfragen dar, die in den Attributteilraum des Informationsdienstknotens 130b fallen, vor der Teilung mit dem Informationsdienstknoten 130c dar. Diese Verteilung kann unter Verwendung des Cluster-Algorithmus bestimmt werden. Tabelle 4 einer Arbeitslastverteilung für den Informationsdienstknoten 130b Plattenraum <= 2 GB 40 % 2 < Plattenraum <= 5 GB 20 % Plattenraum > 5 GB 40 %

Wie es in Tabelle 4 gezeigt ist, bestimmt der Cluster-Algorithmus, dass einem Cluster von Attributwerten für Plattenraum <= 2 GB, z. B. 40 %, und einen anderen Cluster von Attributwerten für Plattenraum > 5 GB, z. B. 40 %, 80 % der Arbeitslast für den Informationsdienstknoten 130b zugeordnet sind. Zusammen decken diese zwei Cluster 80 % der Anzeigen und Abfragen ab, die in den Informationsdienstknoten 130b vor der Teilung gespeichert sind. Zwei Attributteilwerte werden basierend auf diesen Clustern ausgewählt. Ein Teilungswert ist 2 GB.

Es besteht eine 100%-ige Wahrscheinlichkeit, dass der Informationsdienstknoten 130c nach der Teilung Anzeigen speichert, die einen Plattenraum-Attributwert <= 2 GB aufweisen. Dies spiegelt sich in dem Eintrag 910 für die Routingtabelle für den Informationsdienstknoten 130b und dem Attributteilraum für den Informationsdienstknoten 130cwieder. Ein anderer Teilungswert ist 5 GB. Es gibt eine 100%-ige Wahrscheinlichkeit, dass der Informationsdienstknoten 130b nach der Teilung Anzeigen speichert, die einen Plattenraum-Attributwert > 5 GB aufweisen. Dies ist in dem Eintrag 920 des Informationsdienstknotens 130c und dem Attributteilraum für den Informationsdienstknoten 130b wiedergespiegelt.

Ein dritter Cluster, der durch den Cluster-Algorithmus identifiziert ist, umfasst den folgenden Bereich: 2GB > Plattenraum <= 5 GB. Der Cluster-Algorithmus bestimmt, dass 20 % der Arbeitslast für den Informationsdienstknoten 130b dem dritten Cluster zugeordnet sind. Einem der Informationsdienstknoten 130b oder 130c kann eine gewisse Wahrscheinlichkeit zugewiesen sein, um Anzeigen und Abfragen zu speichern, die in den dritten Cluster fallen. Wahrscheinlichkeiten können zugewiesen sein, um die Rate, mit der Anzeigen empfangen und in den Informationsdienstknoten 130b und 130c gespeichert werden, wesentlich abzugleichen. Die Einträge 912 und 922 für die Routingtabellen für die Informationsdienstknoten 130b bzw. 130c stellen die Wahrscheinlichkeiten dar, dass eine Anzeige bei dem Informationsdienstknoten gefunden wird, der in dem Eintrag aufgelistet ist. Zum Beispiel kann eine Abfrage mit einem Plattenraum-Attributwert größer 2 GB basierend auf dem Attributteilraum desselben zu dem Informationsdienstknoten 130c geleitet werden. Falls keine Übereinstimmungen gefunden werden, wird die Abfrage basierend auf dem Eintrag 922 zu dem Informationsdienstknoten 130b geleitet, weil es eine 50%-ige Wahrscheinlichkeit gibt, dass Anzeigen mit einem Plattenraum-Attributwert größer 2 GB in dem Informationsdienstknoten 130b gespeichert werden.

Nachdem der Attributteilraum des Informationsdienstknotens 130b mit dem Attributteilraum des Informationsdienstknotens 130c geteilt ist, sendet der Informationsdienstknoten 130b alle gespeicherten Anzeigen und Abfragen, die in den Attributteilraum des Informationsdienstknotens 130c fallen, an den Informationsdienstknoten 130c. Somit ist der Informationsdienstknoten 130c bereit, um auf Abfragen anzusprechen, die in den Attributteilraum desselben fallen.

9C stellt Beispiele von Routingtabellen und Attributteilräumen für die Informationsdienstknoten 130b und 130d dar, nachdem ein Teilungsalgorithmus auf den Informationsdienstknoten 130b zum Teilen der Arbeitslast des Informationsdienstknotens 130b mit dem Informationsdienstknoten 130d angewandt wird. Bei diesem Beispiel wird ein iterativer Cluster-Algorithmus, wie beispielsweise ein k-Mittel-Clustern, verwendet, um ein Attribut und einen Attributteilungswert basierend auf zwei Clustern auszuwählen, die durch den Cluster-Algorithmus gefunden werden. Das ausgewählte Attribut ist eine Ansprechzeit und der Teilungswert, der aus den zwei Clustern bestimmt ist, beträgt 20 ms. Der Cluster-Algorithmus bestimmt beispielsweise, dass für das Ansprechzeitattribut die Anzeigen und Abfragen, die durch den Informationsdienstknoten 130b gespeichert sind, in zwei Cluster eingeteilt werden können. Ein Cluster umfasst Attributwerte < 20 ms und der andere Cluster umfasst Attributwerte >= 20ms. Somit wird der Attributteilungswert von 20 ms ausgewählt und wird die Arbeitslast des Informationsdienstknotens 130b mit dem Informationsdienstknoten 130d basierend auf dem Teilungswert von 20 ms geteilt.

Wie es oben beschrieben ist, kann ein Teilungsalgorithmus verwendet werden, um ein Attribut und einen Teilungswert zum Teilen der Arbeitslast eines Informationsdienstknotens auszuwählen. Ein Beispiel eines Teilungsalgorithmus ist der k-Mittel-Cluster-Algorithmus, der zwei Cluster zum Bestimmen des Attributs und des Teilungswerts identifiziert. Der k-Mittel-Cluster-Algorithmus ist ein bekannter Algorithmus, der verwendet wird, um eine Population von Daten zu einer vorbestimmten Anzahl von Clustern zu gruppieren. Falls beispielsweise zwei Cluster ausgewählt sind, dann wird jeder Datenpunkt in der Population zufällig einem der zwei Cluster zugewiesen, derart, dass näherungsweise die gleiche Anzahl von Datenpunkten sich in jedem Cluster befindet. Dann wird jeder Datenpunkt in jedem Cluster ausgewertet, um basierend auf einem minimalen Abstand zu einem Cluster zu bestimmen, zu welchem Cluster derselbe gehört. Ein Clustern wird beispielsweise für das Speicherattribut bei dem Informationsdienstknoten 130b durchgeführt. Der Informationsdienstknoten 130b bestimmt die Speicherattributwerte für alle Anzeigen, die in demselben gespeichert sind. Es werden zwei Cluster ausgewählt mit Mitten bei 1 GB bzw. 5 GB.

Jeder Attributwert wird ausgewertet, um basierend auf einem minimalen Abstand zu einem Cluster zu bestimmen, zu welchem Cluster derselbe gehört. Beispielsweise liegt ein Attributwert von 0,25 GB näher an 1 GB als an 5 GB und somit wird der Attributwert von 0,25 GB dem Cluster von 1 GB zugewiesen. Ein Attributwert von 4 GB liegt näher an 5 GB und wird dem Cluster von 5 GB zugewiesen. Diese Auswertung wird durchgeführt, bis eine Bestimmung vorgenommen ist, dass keiner der Datenpunkte einem unterschiedlichen Cluster neu zugewiesen werden muss.

Ein Bestimmen von zwei Clustern wird für jedes Attribut in dem vorbestimmten Satz von Attributen mit einem numerischen Wert durchgeführt. Zum Beispiel zeigt Tabelle 3 ein Beispiel einer Anzeige, die Attributwerte für jedes der Attribute in dem Satz umfasst. Ein Clustern wird für jedes der Attribute außer für das Anwendungsattribut durchgeführt, weil die Anwendungsattributwerte nicht numerisch sind.

Nach einem Anwenden des k-Mittel-Cluster-Algorithmus, um zwei Cluster für jedes Attribut zu bestimmen, wird zumindest ein Optimierungskriterium verwendet, um eines der Attribute für eine Teilung auszuwählen. Dann wird ein Teilungswert für das ausgewählte Attribut basierend auf den Clustern bestimmt. Ein Bespiel des Optimierungskriteriums kann das Attribut umfassen, für das ein Clustern zu einer minimalen Differenz einer Größe zwischen den zwei Clustern führt. Ein anderes Beispiel kann ein Normieren jedes Satzes von Attributwerten in dem Cluster auf einen Wert in dem Bereich von 0 bis 1 und ein anschließendes Auswählen eines Attributs mit dem minimalen quadrierten Fehler umfassen, wo ein k-Mittel-Clustern konvergiert. Es können andere Optimierungsmetriken verwendet werden, um die Cluster für jedes Attribut auszuwerten, derart, dass ein Attribut ausgewählt wird, das Cluster aufweist, die ein optimales Teilen einer Arbeitslast eines Informationsdienstknotens ermöglichen.

Nachdem das Attribut ausgewählt ist, wird der Teilungswert basierend auf den Clustern für das ausgewählte Attribut bestimmt. Zum Beispiel sind M1 und M2 die Mittel der Attributwerte in jedem der Cluster C1 bzw. C2, derart, dass M1 < M2. Es sei angenommen, dass Max(C1) der maximale Attributwert für C1 ist, während Min(C2) der minimale Attributwert für C2 ist. Der Teilungswert ist gleich (Max(C1) + Min(C2))/2.

Der k-Mittel-Cluster-Algorithmus kann ferner verwendet werden, um drei Cluster zum Identifizieren eines Attributs und von Teilungswerten zum Teilen der Arbeitslast eines Informationsdienstknotens zu bestimmen. Der k-Mittel-Cluster-Algorithmus wird verwendet, um drei Cluster für jedes Attribut in dem vorbestimmten Satz von Attributen mit einem numerischen Wert zu bestimmen. Nach einem Anwenden des k-Mittel-Cluster-Algorithmus, um drei Cluster für jedes Attribut zu bestimmen, wird zumindest ein Optimierungskriterium verwendet, um eines der Attribute für ein Teilen auszuwählen. Dann wird für das ausgewählte Attribut basierend auf den Clustern ein Teilungswert bestimmt. Es kann das oben beschriebene Optimierungskriterium verwendet werden.

Nachdem das Attribut ausgewählt ist, werden Teilungswerte basierend auf den Clustern für das ausgewählte Attribut bestimmt. Beispielsweise sind M1, M2 und M3 die Mittel der Attributwerte in jedem der Cluster C1, C2 bzw. C3, derart, dass M1 < M2 < M3. Die Anzeigen für den Cluster C1 werden einem der Informationsdienstknoten zugewiesen, wie beispielsweise dem Informationsdienstknoten 130c, und die Anzeigen für den Cluster C3 werden dem anderen Informationsdienstknoten zugewiesen, wie beispielsweise dem Informationsdienstknoten 130b. Die Anzeigen für den dritten Cluster C2 werden einem der Informationsdienstknoten 130c oder 130b basierend auf einer Wahrscheinlichkeit zugewiesen. Um eine einheitliche Verteilung einer Arbeitslast zwischen den zwei Informationsdienstknoten sicherzustellen, werden die Wahrscheinlichkeiten P und (1 – P) bestimmt, welche Anzeige von dem Cluster C2 einem der Informationsdienstknoten 130b oder 130c zugewiesen wird. Der Wert von P ist gegeben durch: Size(C1) + P* Size(C2) = (1 – P)* Size(C2) + Size(C3). Die zwei Teilungswerte, wie beispielsweise 2 GB und 5 GB, die in 9B gezeigt sind, sind Max(C1) und Min(C3).

Der k-Mittel-Cluster-Algorithmus ist ein Typ eines Cluster-Algorithmus, der verwendet wird, um ein Attribut auszuwählen und einen oder mehrere Attributteilungswerte zu bestimmen. Andere Typen von Cluster-Algorithmen, wie beispielsweise ein Entität-Mittel-Clustern, oder andere Typen einer statistischen Analyse können verwendet werden, um die Ähnlichkeit zwischen Daten zu bestimmen, wie beispielsweise Attributwerte für ein Attribut für jede Anzeige, und ähnliche Daten zu gruppieren, um eine Arbeitslast zu teilen.

Die oben beschriebenen lokalen Teilungsalgorithmen werden verwendet, um die Arbeitslast eines Informationsdienstknotens, der einer der Informationsdienstknoten sein kann, die die höchste oder eine der höchsten Arbeitslasten in der Obere-K-Liste aufweisen, mit einem anderen Informationsdienstknoten zu teilen, wie beispielsweise einem neuen Informationsdienstknoten, der dem Überlagerungsnetzwerk 210 beitritt. Eine andere Option besteht darin, die Arbeitslasten aller Informationsdienstknoten in dem Überlagerungsnetzwerk global auszuwerten und zum Ausgleichen der Arbeitslasten der Informationsdienstknoten 130 die Arbeitslasten für alle der Informationsdienstknoten möglicherweise neu zuzuweisen. Dies wird durch ein Anwenden eines globalen Teilungsalgorithmus erreicht, der alle Informationsdienstknoten beeinflusst und möglicherweise die Arbeitslast aller Informationsdienstknoten umverteilt.

Es kann ein globaler Teilungsalgorithmus verwendet werden, um Arbeitslasten einer großen Anzahl von Informationsdienstknoten oder aller Informationsdienstknoten anstelle eines einzelnen Informationsdienstknotens auszugleichen und ferner eine Latenz in dem Überlagerungsnetzwerk 210 zu verbessern. Falls beispielsweise ein lokaler Teilungsalgorithmus auf viele Informationsdienstknoten in einem Bereich des Überlagerungsnetzwerks 210 angewandt wird, können die Arbeitslasten der Informationsdienstknoten in diesem Bereich besser ausgeglichen werden. Die Latenz in dem Überlagerungsnetzwerk 210 kann jedoch erhöht sein, weil mehr Sprünge benötigt werden können, um einen endgültigen Bestimmungsort in dem Überlagerungsnetzwerk 210 zu erreichen, wie beispielsweise einen Informationsdienstknoten, dem der Attributteilraum gehört, in den eine Anzeige fällt. Der globale Teilungsalgorithmus kann verwendet werden, um die Arbeitslasten aller Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 auszugleichen und eine Latenz zu minimieren. Der globale Teilungsalgorithmus kann regelmäßig angewandt werden und kann zu Zeiten angewandt werden, wenn eine Verarbeitung bei dem Informationsdienst historisch niedrig ist, um eine Unterbrechung des Informationsdienstes zu minimieren.

Die globale Auswertung aller Informationsdienstknoten beginnt damit, dass jede Informationsdienstknoten alle Anzeigen zusammenfasst, die durch einen jeweiligen Informationsdienstknoten während einer Zeitperiode empfangen werden. Ein Beispiel einer Zusammenfassung kann ein Histogramm umfassen, wie beispielsweise 20 % der Anzeigen, die während der letzten 24 Sunden empfangen wurden, weisen einen Speicher zwischen 4 und 5 GB, 20 % weisen einen Speicher zwischen 0,5 und 1 GB auf, etc. Es kann ein Histogramm für jedes Attribut vorgesehen sein. Zusammenfassungen können in anderen Formen als einem Histogramm geliefert werden.

10 stellt die Informationsdienstknoten 130 in der Anfangsphase des globalen Teilungsalgorithmus dar. 10 stellt die Informationsdienstknoten 130 dar, die Zusammenfassungen 1020 an einen zentralen Knoten 1010 übertragen. Der zentrale Knoten 1010 kann einer der Informationsdienstknoten 130 sein. Bei einem anderen Beispiel kann der zentrale Knoten 1010 eine Mehrzahl von Informationsdienstknoten umfassen, die jeweils zugewiesen sind, um Zusammenfassungen von Informationsdienstknoten beispielsweise in enger Nähe zu empfangen. Bei diesem Beispiel kommuniziert die Mehrzahl von zentralen Knoten miteinander, um den globalen Teilungsalgorithmus anzuwenden.

Der zentrale Knoten 1010 wendet einen Teilungsalgorithmus an der gesamten Eingabe von Zusammenfassungen von jedem Informationsdienstknoten an. Der Teilungsalgorithmus kann einen der oben beschriebenen lokalen Teilungsalgorithmen umfassen. Es kann beispielsweise ein Cluster-Algorithmus, wie beispielsweise der k-Mittel-Cluster-Algorithmus, verwendet werden, um zwei Cluster für jedes Attribut aus den Zusammenfassungen von den Informationsdienstknoten zu identifizieren. Es werden ein Attribut und ein Teilungswert basierend auf den berechneten Clustern ausgewählt. Wie es in 11A gezeigt ist, kann beispielsweise das Speicherattribut ausgewählt sein und kann der Teilungswert 2 GB betragen. Dann werden zwei Informationsdienstknoten 130d und 130a aus dem Satz von Informationsdienstknoten 1100 ausgewählt, die Zusammenfassungen liefern. Den Informationsdienstknoten 130d und 130a wird basierend auf dem Teilungswert ein Attributteilraum zugewiesen. Beispielsweise wird dem Informationsdienstknoten 130d ein Attributteilraum von Speicher <= 2 GB zugewiesen und wird dem Informationsdienstknoten 130a ein Attributteilraum von Speicher > 2 GB zugewiesen und werden Routingtabellen für jeden der zwei Informationsdienstknoten erzeugt. Dann wird der Informationsdienstknoten mit dem größten Cluster geteilt. Falls beispielsweise mehr Anzeigen einen Speicher > 2 GB als einen Speicher <= 2 GB aufweisen, wie es aus den Zusammenfassungen 1020 bestimmt wird, die in 10 gezeigt sind, dann wird der Cluster von Anzeigen, die einen Speicher > 2 GB aufweisen, für den Informationsdienstknoten 130a mit einem anderen Informationsdienstknoten geteilt. 11B zeigt den Informationsdienstknoten 130f, der ausgewählt ist, um die Arbeitslast des Informationsdienstknotens 130a zu teilen. Dieser Prozess wird wiederholt, bis allen Informationsdienstknoten ein Attributteilraum in dem Überlagerungsnetzwerk 210 zugewiesen ist. Bei einem Beispiel können die Informationsdienstknoten jedes Mal beliebig aus dem Satz 1100 ausgewählt werden, wenn ein Cluster geteilt wird.

Nachdem allen Knoten in dem Satz 100 ein neuer Attributteilraum zugewiesen wurde und eine neue Routingtabelle erzeugt wurde, werden die Anzeigen an den Informationsdienstknoten übertragen, der den Attributteilraum aufweist, in den jede Anzeige fällt. Beispielsweise überträgt jeder Informationsdienstknoten die Anzeigen, die in dem globalen Cache desselben gespeichert sind, an den Informationsdienstknoten, dem der entsprechende Attributteilraum neu zugewiesen wurde. Alternativ können alle Informationsdienstknoten 130 die globalen Caches derselben leeren und auf das nächste Berichten von Anzeigen von dem Dienstknoten 120 an das Überlagerungsnetzwerk 210 warten. Zum Beispiel können die Dienstknoten 120, die in 1 und 2 gezeigt sind, regelmäßig Anzeigen an das Überlagerungsnetzwerk 210 übertragen und somit können die Informationsdienstknoten 130 auf das nächste Berichten warten, um Anzeigen zu speichern, die jeweiligen Attributteilräumen zugeordnet sind.

Anstelle eines Verwendens des oben beschriebenen lokalen Teilungsalgorithmus mit zwei Clustern kann der globale Teilungsalgorithmus den lokalen Teilungsalgorithmus mit drei Clustern anwenden, bei dem eine Wahrscheinlichkeit für den dritten Cluster bestimmt wird. Der lokale Teilungsalgorithmus mit drei Clustern wird angewandt, bis der Satz von Informationsdienstknoten, die Zusammenfassungen liefern, erschöpft ist. Dann werden die globalen Caches basierend auf den neu zugewiesenen Attributteilräumen wieder bestückt.

12 stellt ein Flussdiagramm eines Verfahrens 1200 zum Anwenden eines lokalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel dar. Bei einem Schritt 1201 empfängt ein Informationsdienstknoten in dem Überlagerungsnetzwerk 210, wie beispielsweise der Informationsdienstknoten 130b, eine Anforderung. Die Anforderung kann eine Teilnahmeanforderung oder irgendeine Nachricht sein, die das Teilen der Arbeitslast des Informationsdienstknotens 130b aufruft. Zum Beispiel kann der Informationsdienstknoten 130b der Informationsdienstknoten sein, der die höchste Arbeitslast in der Obere-K-Liste oder eine der höchsten Arbeitslasten in der Obere-K-Liste aufweist. Die maximale Routingtabellenebene in dem Überlagerungsnetzwerk 210, die in der oben mit Bezug auf 7 beschriebenen K-min-Ebene-Liste vorgesehen sein kann, und die höchste Routingtabellenebene eines ausgewählten Informationsdienstknotens, die ebenfalls in der K-min-Ebene-Liste vorgesehen sein kann, können ebenfalls bei einem Auswählen eines Informationsdienstknotens für ein Teilen betrachtet werden. Zum Beispiel überträgt der Informationsdienstknoten 130c eine Beitrittsanforderung an das Überlagerungsnetzwerk 210. Die Beitrittsanforderung kann an einen Informationsdienstknoten übertragen werden, wie beispielsweise den Informationsdienstknoten 130e, der sich, wie es bestimmt wurde, in enger Netzwerknähe zu dem Informationsdienstknoten 130c befindet. Der Informationsdienstknoten 130e wählt den Informationsdienstknoten 130b in der Obere-K-Liste aus, der die höchste Arbeitslast aufweist. Der Informationsdienstknoten 130e vergleicht ferner die höchste Routingtabellenebene des Informationsdienstknotens 130b mit der maximalen Routingtabellenebene des Überlagerungsnetzwerks 210. Falls die Differenz der Routingtabellenebenen größer als eine Schwelle ist, dann kann ein anderer Informationsdienstknoten für ein Teilen ausgewählt werden. Der andere Informationsdienstknoten kann ein anderer Informationsdienstknoten aus der Obere-K-Liste sein. Durch ein Nutzen dieses Routingtabellenebenenvergleichs wird ein unausgeglichener Dienstbaum minimiert, der durch ein übermäßiges Teilen in einem Bereich des Dienstbaums bewirkt wird.

Bei 1202 wendet der Informationsdienstknoten 130b einen lokalen Teilungsalgorithmus an, um die Arbeitslast des Informationsdienstknotens 130b zu teilen, falls der Informationsdienstknoten 130b bei dem Schritt 1201 ausgewählt wird. Zum Beispiel wendet der Informationsdienstknoten 130b einen der lokalen Teilungsalgorithmen, die oben beschrieben sind, an, um ein Attribut und zumindest einen Attributteilungswert zum Teilen der Arbeitslast des Informationsdienstknotens 130b mit dem Informationsdienstknoten 130c auszuwählen.

13 stellt ein Flussdiagramm eines Verfahrens 1300 zum Anwenden eines globalen Teilungsalgorithmus gemäß einem Ausführungsbeispiel dar. Das Verfahren 1300 ist mit Bezug auf die 10 und 11A-B durch ein Beispiel und ohne Einschränkung beschrieben. Bei einem Schritt 1301 empfängt der zentrale Knoten 1010 die Zusammenfassungen 1030 von den Informationsdienstknoten 130.

Bei einem Schritt 1302 wählt der zentrale Knoten 1010 ein Attribut und zumindest einen Attributteilungswert basierend auf einer statistischen Analyse der Zusammenfassungen aus. Die statistische Analyse kann die Anwendung von einem der lokalen Teilungsalgorithmen, die oben beschrieben sind, auf die Zusammenfassungen 1030 umfassen.

Bei einem Schritt 1303 weist der zentrale Knoten 1010 Arbeitslasten zwei Knoten, z. B. den Informationsdienstknoten 130d und 130a, aus dem Satz von Informationsdienstknoten 1100 zu, der in 11 gezeigt ist, als ob die zwei Knoten die einzigen Informationsdienstknoten in dem Überlagerungsnetzwerk 210 sind. Die zugewiesenen Arbeitslasten basieren auf dem zumindest einen Teilungswert.

Bei einem Schritt 1304 bestimmt der zentrale Knoten 1010, ob allen Informationsdienstknoten in dem Satz 1100 Arbeitslasten zugewiesen wurden. Falls nicht, werden die Schritte 1302 und 1303 wiederholt.

Gemäß einem Ausführungsbeispiel wird, wenn ein neuer Knoten verfügbar ist, um dem Überlagerungsnetzwerk 210 beizutreten, eine Beitrittsanforderung an den Informationsdienstknoten in der Obere-K-Liste weitergeleitet, der die höchste Arbeitslast aufweist. Dann teilt dieser Informationsdienstknoten die Arbeitslast desselben mit dem neuen Knoten basierend auf der Anwendung eines lokalen Teilungsalgorithmus. In bestimmten Situationen kann es, anstatt die Arbeitslast eines Informationsdienstknotens zu teilen, günstiger sein, einen existierende Informationsdienstknoten in einem anderen Bereich des Netzwerks 100, das in 1 und 2 gezeigt ist, zu reproduzieren, um eine Latenz zwischen den Benutzerknoten, die Informationen für bestimmte Dienste anfordern, und den Informationsdienstknoten zu reduzieren, die die Anzeigen speichern, die für die Anforderungen relevant sind. Beispielsweise kann ein Informationsdienstknoten bei einer neuen Position in dem Netzwerk 100 dupliziert werden, falls bestimmt wird, dass Benutzerknoten hohe Latenzen von dem Informationsdienstknoten erfahren, der Abfragen verarbeitet und Ergebnisse zu den Benutzerknoten sendet.

Bei einem Beispiel kann ein Informationsdienstknoten reproduziert werden, anstatt die Arbeitslast eines Informationsdienstknotens zu teilen, falls die Arbeitslasten in der Obere-K-Liste unterhalb einer Schwelle liegen. Dann kann angenommen werden, dass es günstiger ist, einen Informationsdienstknoten zu reproduzieren, um eine Latenz zu reduzieren, anstatt die Arbeitslast eines Informationsdienstknotens zu reduzieren.

Ein spezieller Informationsdienstknoten kann reproduziert werden, falls eine Latenz zwischen dem Informationsdienst und einem Benutzerknoten größer als eine Schwelle ist. Latenzen können in einem Nachbildungsinformationscache für jeden Informationsdienstknoten gespeichert sein. Der Nachbildungspositionscache 440, der in 4 gezeigt ist, für den Informationsdienstknoten 130b speichert Informationen, die den Latenzen bestimmter Informationsdienstknoten zugeordnet sind. Der Informationsdienstknoten 130b kann die Informationen in dem Nachbildungspositionscache 440 verwenden, um zu bestimmen, ob eine Nachbildung in einem anderen Bereich des Netzwerks 100 hinzuzufügen ist, um eine Latenz zu reduzieren. 14 stellt beispielsweise den Informationsdienstknoten 130b dar, der Latenzberichte 1410a-c von Benutzerknoten 110a-c in enger Nähe zu dem Informationsdienstknoten 130b empfängt. Der Informationsdienst 130b kann der Informationsdienstknoten sein, den die Benutzerknoten 110a-c anfänglich kontaktieren, wenn dieselben Abfragen an das Überlagerungsnetzwerk 210 senden. Die Berichte 1410a-c umfassen Latenzen von Informationsdienstknoten, die Abfragen verarbeiten und Abfrageergebnisse an die Benutzerknoten 110a-c senden. Die Berichte 1410a-c umfassen ferner die Identifikation eines entsprechenden Informationsdienstknotens mit jeder Latenz. Latenzen und Informationsdienstknotenidentifikationen sind in dem Nachbildungspositionscache 440 gespeichert. Der Informationsdienstknoten 130b empfängt eine Beitrittsanforderung von dem Knoten 1420. Der Informationsdienstknoten 130b bestimmt, ob die Arbeitslasten in der Obere-K-Liste unter einer Schwelle liegen. Falls die Arbeitslasten unter einer Schwelle liegen, dann wählt der Informationsdienstknoten 130b einen Informationsdienstknoten aus dem Nachbildungspositionscache aus, der eine hohe Latenz aufweist. Bei einem Beispiel wird ein Informationsdienstknoten, der aus dem Nachbildungspositionscache 440 identifiziert wird und eine Latenz größer einer Schwelle aufweist, für eine Reproduzierung ausgewählt, wie beispielsweise der Informationsdienstknoten 130f. Der Informationsdienstknoten 130f wird reproduziert, was ein Kopieren von globalen Caches und ein Speichern der Anzeigen in dem neuen Informationsdienstknoten 1420 umfassen kann, der eine Nachbildung ist. Netzwerknäheinformationen, wie beispielsweise Abstände zwischen Knoten, können auf einer Netzwerkmetrik basieren, wie beispielsweise einer Umlaufzeit, einer Anzahl von Sprüngen, etc.

15 stellt ein Flussdiagramm eines Verfahrens 1400 zum Reproduzieren eines Informationsdienstknotens gemäß einem Ausführungsbeispiel dar. Das Verfahren 1400 wird mit Bezug auf das in 14 gezeigte Beispiel durch ein Beispiel und ohne Einschränkung beschrieben. Bei einem Schritt 1501 empfängt der Informationsdienstknoten 130b eine Anforderung, wie beispielsweise eine Beitrittsanforderung, von dem Knoten 1420, was eine Arbeitslastteilung oder eine Reproduzierung veranlasst.

Bei einem Schritt 1502 bestimmt der Informationsdienstknoten 130b, ob ein Informationsdienstknoten zu reproduzieren oder die Arbeitslast eines Informationsdienstknotens zu teilen ist. Bei einem Beispiel kann ein Informationsdienstknoten anstelle eines Teilens der Arbeitslast eines Informationsdienstknotens reproduziert werden, falls die Arbeitslasten in der Obere-K-Liste unterhalb einer Schwelle liegen.

Bei einem Schritt 1503 wählt, falls der Informationsdienstknoten 130b bestimmt, einen Informationsdienstknoten zu reproduzieren, der Informationsdienstknoten 130b einen Informationsdienstknoten aus, der reproduziert werden soll.

Faktoren, die bei einem Auswählen eines Informationsdienstknotens für eine Reproduzierung betrachtet werden, umfassen eine Latenz eines Informationsdienstknotens und einen Abstand zwischen dem Knoten 1420 und dem Benutzerknoten. Hinsichtlich eines Abstands beispielsweise wird ein neuer Knoten ausgewählt, um eine Nachbildung zu sein, der sich in der gleichen Netzwerknähe zu dem Benutzerknoten, der die hohe Latenz aufweist, und dem Informationsdienstknoten 130b befindet, falls der Informationsdienstknoten 130b der Knoten ist, der Berichte von dem Benutzerknoten empfängt.

Bei einem Schritt 1504 wird der ausgewählte Informationsdienstknoten reproduziert. Zum Beispiel werden die globalen Caches und die Routingtabelle des Informationsdienstknotens 130f zu dem Knoten 1420 kopiert.

16 stellt ein exemplarisches Blockdiagramm eines Computersystems 1600 dar, das als ein Informationsdienstknoten in dem Überlagerungsnetzwerk 210 verwendet werden kann. Das Computersystem 1600 umfasst einen oder mehrere Prozessoren, wie beispielsweise einen Prozessor 1602, die eine Ausführungsplattform zum Ausführen einer Software liefern.

Befehle und Daten von dem Prozessor 1602 werden über einen Kommunikationsbus 1604 kommuniziert. Das Computersystem 1600 umfasst ferner einen Hauptspeicher 1606, wie beispielsweise einen Direktzugriffsspeicher (RAM = Random Access Memory), in dem eine Software während einer Laufzeit resident sein kann, und einen sekundären Speicher 1608. Der sekundäre Speicher 1608 umfasst beispielsweise ein Festplattenlaufwerk 1610 und/oder ein entfernbares Speicherungslaufwerk 1612, das ein Diskettenlaufwerk, ein Magnetbandlaufwert, ein CD-Laufwerk (CD = Compact Disk) etc. darstellt, oder einen nicht flüchtigen Speicher, in dem eine Kopie der Software gespeichert sein kann. Der sekundäre Speicher 1608 kann ferner einen ROM (Read-Only Memory = Nur-Lese-Speicher), einen EPROM (Erasable, Programmable ROM = löschbarer, programmierbarer ROM), einen EEPROM (Electrically Erasable, Programmable ROM = elektrisch löschbarer, programmierbarer ROM) umfassen. Zusätzlich zu einer Software, können Routingtabellen, die globale Informationstabelle und gemessene QoS-Charakteristika, eine gemessene verfügbare Bandbreite und eine Bandbreite, die für Dienste erforderlich ist, in dem Hauptspeicher 1606 und/oder dem sekundären Speicher 1608 gespeichert sein. Das entfernbare Speicherungslaufwerk 1612 liest von und/oder schreibt zu einer entfernbaren Speicherungseinheit 1614 auf eine gut bekannte Weise.

Ein Benutzer stellt mit einem oder mehreren Eingabegeräten 1628, wie beispielsweise einer Tastatur, einer Maus, einem Schreibstift und dergleichen, eine Schnittstelle mit dem Computersystem 1600 her. Der Anzeigeadapter 1622 stellt eine Schnittstelle mit dem Kommunikationsbus 1604 und der Anzeige 1620 her und empfängt Anzeigedaten von dem Prozessor 1602 und wandelt die Anzeigedaten in Anzeigebefehle für die Anzeige 1620 um. Eine Netzwerkschnittstelle 1630 ist für ein Kommunizieren mit anderen Knoten vorgesehen.

Einer oder mehrere der Schritte der Verfahren 1200, 1300 und 1500 können als eine Software implementiert sein, die auf einem computerlesbaren Medium eingebettet ist, wie beispielsweise dem Speicher 1606 und/oder 1608, und beispielsweise durch den Prozessor 1602 an dem Computersystem 1600 ausgeführt wird. Die Schritte können durch ein Computerprogramm ausgeführt sein, das in einer Vielfalt von Formen existieren kann, sowohl aktiv als auch inaktiv. Zum Beispiel können dieselben als ein Softwareprogramm (Softwareprogramme) existieren, das (die) aus Programmanweisungen in einem Quellcode, einem Objektcode, einem ausführbaren Code oder anderen Formaten zum Durchführen einiger der Schritte gebildet ist (sind). Irgendwelche der Obigen können auf einem computerlesbaren Medium verkörpert sein, das Speicherungsvorrichtungen und Signale umfasst, in komprimierter oder unkomprimierter Form. Beispiele von geeigneten computerlesbaren Speichervorrichtungen umfassen einen herkömmlichen Computersystem-RAM (Direktzugriffsspeicher), ROM (Nur-Lese-Speicher), EPROM (löschbarer, programmierbarer ROM), EERPOM (elektrisch löschbarer, programmierbarer ROM) und magnetische oder optische Platten oder Bänder. Beispiele von computerlesbaren Signalen, ob dieselben unter Verwendung eines Trägers moduliert sind oder nicht, sind Signale, auf die zuzugreifen ein Computersystem, das das Computerprogramm hostet oder ausführt, konfiguriert sein kann, einschließlich Signalen, die durch das Internet oder andere Netzwerke heruntergeladen werden. Konkrete Beispiele des Vorhergehenden umfassen eine Verteilung der Programme auf eine CD-ROM oder über eine Internet-Herunterladung. In einer Hinsicht ist das Internet selbst als eine abstrakte Entität ein computerlesbares Medium. Das gleiche gilt für Computernetzwerke im Allgemeinen. Es ist deshalb klar, dass diese Funktionen, die unten aufgezählt sind, durch irgendeine elektronische Vorrichtung durchgeführt werden können, die zum Ausführen der oben beschriebenen Funktionen in der Lage ist.

Während Ausführungsbeispiele mit Bezug auf Beispiele beschrieben wurden, sind Fachleute auf dem Gebiet in der Lage, verschiedene Modifikationen an den beschriebenen Ausführungsbeispielen vorzunehmen, ohne von der wahren Wesensart und dem Schutzbereich abzuweichen. Die Begriffe und Beschreibungen, die hierin verwendet werden, sind lediglich durch eine Darstellung dargelegt und sind nicht als Einschränkungen gemeint. Obwohl die Verfahren durch Beispiele beschrieben wurden, können insbesondere Schritte der Verfahren in unterschiedlichen Reihenfolgen als dargestellt oder simultan durchgeführt werden. Fachleute auf dem Gebiet erkennen, dass diese und andere Variationen innerhalb der Wesensart und des Schutzbereichs möglich sind, wie es in den folgenden Ansprüchen und den Äquivalenten derselben definiert ist.

Um mit der zunehmenden Arbeitslast bei expandierenden Netzwerken umzugehen, wird eine dezentralisierte Arbeitslastausgleichstechnik benötigt, die ebenfalls die Ansprechzeit während Verkehrsspitzen reduziert, und wird ein Knoten aus einem Satz von Knoten in einem Partner-zu-Partner-Netzwerk identifiziert, der die höchsten Arbeitslasten in dem Partner-zu-Partner-Netzwerk (210) aufweist. Die Arbeitslast des Knotens (130b) wird mit einem anderen Knoten (130c) unter Verwendung eines Teilungsalgorithmus geteilt.