Diese Erfindung bezieht sich allgemein auf Netzwerke. Insbesondere bezieht sich die Erfindung auf Arbeitslasten für 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.

Gemäß einem Ausführungsbeispiel sind Knoten in einem Netzwerk wirksam, um einen Informationsdienst zu liefern. Ein Satz der Knoten, die eine höchste Arbeitslast aufweisen, werden durch ein Routen (Leiten) einer Liste von Arbeitslasten für die Knoten durch die Knoten in dem Überlagerungsnetzwerk hindurch zu einem endgültigen Bestimmungsort in dem Netzwerk identifiziert. Jeder Knoten, der die Liste empfängt, bestimmt, ob eine Arbeitslast in die Liste einzuschließen ist.

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 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;

9 ein Flussdiagramm eines Verfahrens, das Schritte in einer Austauschphase umfasst, gemäß einem Ausführungsbeispiel darstellt;

10 ein Flussdiagramm eines Verfahrens für einen Obere-K-Routing-Algorithmus (Top-K-Routing-Algorithmus) gemäß einem Ausführungsbeispiel darstellt; und

11 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. beschrieben sind, und führen ein Routen durch, wie es in der ebenfalls anhängigen US-Patentanmeldung (Anwaltsaktenzeichen Nr. 200406058-1) mit dem Titel „Routing A Service Query In An Overlay Network" von Sujoy Basu et al. beschrieben ist, 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: Tabelle 1 von Attributen und Attributwerten für Gitterrechendienst 1 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 11 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 110a einen 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: Tabelle 2 der Attribute und Attributwerte für die Abfrage 501 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: Tabelle 3 von Attributwerten für die Anzeige 601 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.

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ählte 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.

9 stellt ein Verfahren 900, das Schritte in der Austauschphase umfasst, gemäß einem Ausführungsbeispiel dar. Das Verfahren 900 ist mit Bezug auf 1-8 durch ein Beispiel und ohne Einschränkung beschrieben. Bei einem Schritt 901 wird die Obere-K-Liste durch die Informationsdienstknoten 130 in dem Überlagerungsnetzwerk 210 hindurch zu einem endgültigen Bestimmungsort in dem Überlagerungsnetzwerk 210 geroutet. Bei einem Beispiel umfasst der endgültige Bestimmungsort den Führungsknoten 130a, der in 7 gezeigt ist. Während der Austauschphase empfängt der Führungsknoten 130a, der in 7 gezeigt ist, die Obere-K-Liste einschließlich einer Identifikation der Informationsdienstknoten, die die oberen K höchsten Arbeitslasten in dem Überlagerungsnetzwerk 210 aufweisen, das in 2 gezeigt ist. Der Führungsknoten ist der Informationsdienstknoten mit einer Routingtabelle, die lediglich einen Attributbereich oder Attributbereiche aufweist, die größer als ein entsprechender Teilungswert in der Routingtabelle desselben sind. Der Führungsknoten kann anfänglich durch einen Administrator ausgewählt werden. Es kann ein stabiler Informationsdienstknoten als der Führungsknoten ausgewählt werden.

Bei einem Schritt 902, der durch die Informationsdienstknoten 130 durchgeführt werden kann, wenn die Obere-K-Liste zu dem endgültigen Bestimmungsort geroutet wird, bestimmt jeder Informationsdienstknoten, der die Obere-K-Liste empfängt, ob eine Arbeitslast eines jeweiligen Knotens, der die Liste empfängt, eingeschlossen werden soll. Wie es in

7 gezeigt ist, empfängt beispielsweise der Informationsdienstknoten 130c die Obere-K-Liste von dem Informationsdienstknoten 130b während der Austauschphase. Falls die Arbeitslast des Informationsdienstknotens 130c geringer als die Arbeitslasten der Informationsdienstknoten 130b und 130d ist, dann schließt der Informationsdienstknoten 130c die Arbeitslast desselben für K = 2 nicht in die Obere-K-Liste ein. Falls der Informationsdienstknoten 130c bestimmt, dass die Arbeitslast desselben größer als die zwei Arbeitslasten in der Obere-K-Liste ist, wird die Arbeitslast des Informationsdienstknotens 130c in die Obere-K-Liste eingeschlossen und wird die Obere-K-Liste zu dem endgültigen Bestimmungsort hin geroutet, wie beispielsweise dem Führungsknoten 130a.

10 stellt ein Flussdiagramm für ein Verfahren 1000 für den Obere-K-Routing-Algorithmus, der an einem Knoten durchgeführt wird, wie beispielsweise einem Informationsdienstknoten, gemäß einem Ausführungsbeispiel dar. Das Verfahren 100 ist mit Bezug auf 1-8 lediglich durch ein Beispiel und ohne Einschränkung beschrieben.

Bei einem Schritt 1001 empfängt der Informationsdienstknoten 130b, der in 7 gezeigt ist, die Obere-K-Liste. Bei einem Schritt 1002 bestimmt der Informationsdienstknoten 130b, ob die Arbeitslast desselben in die Obere-K-Liste einzuschließen ist. Der Informationsdienstknoten 130b schließt beispielsweise die Arbeitslast desselben in die Obere-K-Liste ein, falls die Arbeitslast desselben größer als eine andere Arbeitslast in der Obere-K-Liste ist oder falls die Obere-K-Liste noch keine Anzahl K von Arbeitslasten umfasst. Mit Bezug auf das Beispiel von 7 schließt beispielsweise der Informationsdienstknoten 130b, falls K = 2, die Arbeitslast desselben in die Obere-K-Liste, weil die Obere-K-Liste eine Arbeitslast für den Informationsdienstknoten 130d umfasst. Bei einem Schritt 1003 routet der Informationsdienstknoten 130b die Liste zu einem Führungsknoten in dem Partner-zu-Partner-Überlagerungsnetzwerk 210hin weiter. Zum Beispiel identifiziert der Informationsdienstknoten 130b aus der Routingtabelle desselben einen Eintrag auf höchster Ebene, der einen Attributbereich umfasst, der kleiner oder gleich einem Attributteilungswert ist. Wie es in 8b der Routingtabelle für den Informationsdienstknoten 130b gezeigt ist, ist der Eintrag auf höchster Ebene, der einen Attributbereich umfasst, der kleiner oder gleich einem Attributteilungsbereich ist, der Eintrag 820. Der Informationsdienstknoten 130c wird aus dem Eintrag 820 identifiziert und die Obere-K-Liste wird an den Informationsdienstknoten 130c übertragen.

Die in 8B–D gezeigten Routingtabellen können basierend auf Teilungsalgorithmen (Splitting-Algorithmen) erzeugt werden, die verwendet werden, um Arbeitslasten für die Informationsdienstknoten auszugleichen, die die höchsten Arbeitslasten aufweisen, wie es beispielsweise in der Obere-K-Liste identifiziert ist. Ein lokaler Teilungsalgorithmus kann eine Teilung einer Arbeitslast eines zweiten Knotens in dem Überlagerungsnetzwerk mit einem ersten Knoten basierend auf zumindest einem Attributteilungswert für den zweiten Knoten umfassen. Der erste Knoten kann einen neuen Knoten umfassen, der dem Überlagerungsnetzwerk 210 beitritt. Dem neuen Knoten wird basierend auf dem Teilungswert ein Attributteilraum zugewiesen. Im Wesentlichen werden alle Einträge in der Routingtabelle des zweiten Knotens zu der Routingtabelle des ersten Knotens kopiert und wird zumindest ein neuer Eintrag auf höchster Ebene in der Routingtabelle des ersten Knotens für die Routingtabelle des ersten Knotens basierend auf dem zumindest einen Attributteilungswert erzeugt.

11 stellt ein exemplarisches Blockdiagramm eines Computersystems 1100 dar, das als ein Informationsdienstknoten in dem Überlagerungsnetzwerk 210 verwendet werden kann. Das Computersystem 1100 umfasst einen oder mehrere Prozessoren, wie beispielsweise einen Prozessor 1102, der eine Ausführungsplattform zum Ausführen einer Software bereitstellt.

Befehle und Daten von dem Prozessor 1102 werden über einen Kommunikationsbus 1104 kommuniziert. Das Computersystem 1100 umfasst ferner einen Hauptspeicher 1106, wie beispielsweise einen Direktzugriffsspeicher (RAM = Random Access Memory), in dem während einer Laufzeit eine Software resident sein kann, und einen sekundären Speicher 1108. Der sekundäre Speicher 1108 umfasst beispielsweise ein Festplattenlaufwerk 1110 und/oder ein entfernbares Speicherlaufwerk 1112, das ein Diskettenlaufwerk, ein Magnetbandlaufwert, ein Compact-Disk-Laufwerk etc. darstellen kann, oder einen nichtflüchtigen Speicher, in dem eine Kopie der Software gespeichert sein kann. Der sekundäre Speicher 1108 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, Routingtabellen, der globalen Informationstabelle und gemessenen QoS-Charakteristika, kann eine gemessene verfügbare Bandbreite und eine Bandbreite, die für Dienste erforderlich ist, in dem Hauptspeicher 1106 und/oder dem sekundären Speicher 1108 gespeichert sein. Das entfernbare Speicherlaufwerk 1112 liest auf gut bekannte Weise aus einer entfernbaren Speichereinheit 1119 und/oder schreibt zu derselben.

Ein Benutzer stellt mit dem Computersystem 1100 mit einem oder mehreren Eingabegeräten 1128 eine Schnittstelle her, wie beispielsweise einer Tastatur, einer Maus, einem Schreibstift und dergleichen. Der Anzeigeadapter 1122 bildet eine Schnittstelle mit dem Kommunikationsbus 1109 und der Anzeige 1120 und empfängt Anzeigedaten von dem Prozessor 1102 und wandelt die Anzeigedaten in Anzeigebefehle für die Anzeige 1120 um. Eine Netzwerkschnittstelle 1130 ist zum Kommunizieren mit anderen Knoten über das Netzwerk 200 vorgesehen, das in 1 gezeigt ist.

Einer oder mehrere der Schritte der Verfahren 700, 800 und 900 können als eine Software implementiert sein, die auf einem computerlesbaren Medium eingebettet ist, wie beispielsweise dem Speicher 1106 und/oder 1108, und auf dem Computersystem 1100 beispielsweise durch den Prozessor 1102 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 Computerprogramm (Computerprogramme) existieren, das (die) aus Programmanweisungen in einem Quellcode, Objektcode, ausführbaren Code oder anderen Formaten zum Durchführen einiger der Schritte gebildet ist (sind). Irgendeines der Obigen kann auf einem computerlesbaren Medium ausgeführt sein, das Speichervorrichtungen 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.

Knoten (130) in einem Netzwerk (210) sind wirksam, um einen Informationsdienst zu liefern. Ein Satz der Knoten, die eine höchste Arbeitslast aufweisen, wird durch ein Routen einer Liste von Arbeitslasten (712) für die Knoten durch das Netzwerk (210) hindurch zu einem endgültigen Bestimmungsort (701) identifiziert. Jeder Knoten, der die Liste (712) empfängt, bestimmt, ob eine Arbeitslast eines jeweiligen Knotens in die Liste (712) einzuschließen ist.