DE60320104T2

DE60320104T2 - Verfahren und Vorrichtung zur Berechnung von Mehrfachsendungsleitwegen

Info

Publication number: DE60320104T2
Application number: DE60320104T
Authority: DE
Inventors: Seisho Yasukawa; Koji Sugisono; Masanori Uga
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 2002-12-11
Filing date: 2003-12-10
Publication date: 2009-05-14
Anticipated expiration: 2023-12-11
Also published as: CN100442750C; US7652998B2; DE60320104D1; EP1515495A2; DE60303763D1; EP1515495B1; DE60303763T2; US20040218536A1; EP1429500B1; US20080013465A1; EP1515495A3; US7693074B2; CN1514603A; EP1429500A1

Description

HINTERGRUND DER ERFINDUNG
1. Gebiet der Erfindung
Die vorliegende Erfindung betrifft eine Technologie zum Berechnen von Mehrfachsendungsleitwegen (auch Multicast-Leitwege bzw. Multicast-Pfade genannt) in einem Multicast-Kommunikationsnetz. Insbesondere betrifft die vorliegende Erfindung eine Technologie zum Berechnen effizienter Multicast-Pfade von einem Quellenknoten zu jedem der Zielknoten zum Übertragen von Multicast-Verkehr.
2. Beschreibung des Standes der Technik
Multicast-Kommunikation wird zum Liefern von Bewegtbildern und Sprache zu einer Vielzahl spezifischer Benutzer in einem Computernetz Beachtung geschenkt. In dem Multicast-Kommunikationsnetz ist ein Quellenknoten mit Zielknoten über einen Rendezvouspunkt-Knoten verbunden, bei welchem ein Pfad in eine Vielzahl von Pfaden zu den Zielknoten aufgeteilt wird. An dem Rendezvouspunkt-Knoten werden Mehrfachsende-Daten kopiert und über die mehreren Pfade zu den Zielknoten übertragen.
Bezüglich der Einzelverbindungskommunikation bzw. Unicast-Kommunikation, bei welcher ein Quellenknoten mit jedem Zielknoten in einem Eins-zu-eins-Zusammenhang verbunden ist, muss der Quellenknoten Kopien von Informationen vorbereiten, deren Anzahl dieselbe ist wie die der Zielknoten. Demnach kann durch die Verwendung von Multicast-Kommunikation ggf. der Umfang an über das Netz übertragener Information erhöht werden.
Bei Multicast-Kommunikation wird ein Satz von Zielknoten eine Multicast-Gruppe genannt und ein Satz von Multicast-Pfaden wird von dem Quellenknoten zu jedem Knoten der Multicast- Gruppe eingerichtet. Die Multicast-Pfade werden derart eingerichtet, dass der Quellenknoten mit allen Zielknoten, die zur Multicast-Gruppe gehören, verbunden wird. Ein Benutzer, der Information zu erhalten wünscht, die zu einer Multicast-Gruppe übertragen wird, tritt der Multicast-Gruppe bei. Demnach ändern sich die Multicast-Pfade in Übereinstimmung mit dem Beitrittszustand von Benutzern.
Es gibt mehrere Anwendungen, die Multicast-Kommunikation verwenden wie z. B. Videokonferenzen, Online-Spiele und Anwendungen zum Liefern von Bewegtbildern wie z. B. Film- und Fernsehprogrammen. Bezüglich der Videokonferenzen und Online-Spiele entsprechen Zielknoten einer Vielzahl von Benutzern und zusätzlich kann jeder der Vielzahl von Benutzer ein Quellenknoten werden, wenn er auf empfangene Daten antwortet. Bezüglich solcher Anwendungen ist eine Technologie zu beachten zum Ausgleichen von Zeiten, zu welchen jeder Benutzer auf Daten, die über das Multicast-Netz übertragen werden, antwortet, so dass die Gelegenheit des Antwortens für jeden Benutzer gleich wird. Zum Ausgleichen bzw. Gleichmachen der Antwortzeiten gibt es eine Technologie, bei der Multicast-Pfade von dem Quellenknoten zu jedem Zielknoten derart entworfen werden, dass ähnliche Verzögerungen in jedem Multicast-Pfad auftreten.
Differenzen zwischen Verzögerungen entlang der Pfade zwischen dem Quellenknoten und jedem Zielknoten werden Verzögerungsschwankung unter Benutzern genannt. Jedoch werden derzeit hauptsächlich Algorithmen zum Berechnen von Minimalverzögerungs-Pfaden verwendet und es gibt kein Kommunikationsverfahren, das einen Algorithmus zum Berechnen von Pfaden unter Berücksichtigung der Verzögerungsschwankung zwischen Benutzern einsetzt. Es gibt folgende konventionelle Beispiele von Algorithmen zum Verringern von Verzögerungsschwankungen zwischen Benutzern:

Dokument 1: G, Rouskas et al., "Multicast Routing With End-to-End Delay and Delay Variation Constraints", IEEE Journal an Selected Areas in Communication, Band 15, Nr. 3, April 1997.
Dokument 2: Pi-Rong Sheu et al., "A Fast and Efficient Heuristic Algorithm for the Delay and Delay Variation Bound Multicast Tree Problem", IEEEICC, 2001.

Das Dokument 1 ist das erste Dokument, das versucht, das oben erwähnte Problem zu lösen. Das Folgende ist das Verfahren zum Berechnen von Pfaden in Übereinstimmung mit Dokument 1.
Erstens, jeder minimal verzögerte Pfad zwischen einem Quellenknoten und jedem Zielknoten wird berechnet und eine Verzögerung w eines Pfades, die die maximale Verzögerung zwischen den minimal verzögerten Pfaden ist, wird geprüft. Annehmend, dass Δ eine von einer Anwendung akzeptierbare Verzögerungsschwankung ist (dieser Parameter bedeutet, dass die Differenz der maximalen Ende-zu-Ende-Verzögerung und der minimalen Ende-zu-Ende-Verzögerung über die Pfade von dem Quellenknoten zu allen Zielknoten innerhalb Δ gehalten worden ist), werden Pfade, die die Bedingung di ≤ w – Δ erfüllen, akzeptiert. Bezüglich eines Pfades, der nicht akzeptiert worden ist, wird nach einem Pfad gesucht, der die Bedingung erfüllt unter Verwendung eines Algorithmus zum Suchen nach einem k–t kürzesten Pfad. Dann wird der gesuchte Pfad akzeptiert. In der Annahme, dass die Anzahl der Zielknoten m ist und die Anzahl der Knoten im Netz n ist, ist dann die Rechenzeitkomplexität dieses Verfahrens O (kmn³).
In dem Dokument 2 wird ein Verfahren vorgeschlagen, bei welchem die Zeitkomplexität kleiner ist als die des Dokumentes 1, so dass Rechenzeit zum Erhalten von Pfaden gekürzt wird. Das Rechenverfahren ist folgendermaßen.
Die Multicast-Pfade schließen einen Eins-zu-eins-Unicast-Pfad zwischen dem Quellenknoten und einem Rendezvouspunkt-Knoten ein (der auch Zentralknoten genannt werden kann) und Einer-zu-mehreren-Pfade zwischen dem Rendezvouspunkt-Knoten und jedem Zielknoten. In dem Verfahren des Dokumentes 2 wird die minimale Verzögerung zwischen jedem Zielknoten und jedem anderen Knoten im Netz zuerst berechnet. Als nächstes wird für jeden Knoten im Netz eine zugeordnete Multicast-Verzögerungsschwankung zwischen dem Knoten und jedem Zielknoten berechnet. Dann wird ein Knoten mit der minimalen Mulitcastverzögerungsschwankung als Rendezvouspunkt-Knoten ausgewählt. Letztendlich wird jeder Zielknoten mit diesem Rendezvouspunkt-Knoten über den Minimalverzögerungspfad verbunden, der Quellenknoten wird ebenfalls mit dem Rendezvouspunkt-Knoten über den Minimalverzögerungspfad verbunden. Die Zeitkomplexität dieses Verfahrens ist O (n³) und eine schnellere Berechnung als bei Dokument 1 kann realisiert werden.
Es gibt die folgenden Probleme bei den oben erwähnten konventionellen Technologien.
Gemäß den oben erwähnten zwei Berechnungsverfahren wird die Zeitkomplexität groß. Da Anwendungen, die eine Verringerung der Verzögerungsschwankung erfordern, im Allgemeinen Echtzeitverarbeitung benötigen, ist es wünschenswert, die Zeitkomplexität zu verringern. Zudem wird gefordert, die Übertragungsverzögerung für die Echtzeitanwendungen zu verringern. Bezüglich des Verfahrens des Dokumentes 2, bei welchem ein Rendezvouspunkt bereitgestellt wird, wird betont, dass ein Realisieren eines Minimalverzögerungspfades allgemein schwierig ist. Daher gibt es ein Problem, dass die Übertragungsverzögerung zu jedem Zielknoten im Allgemeinen gemäß dem Verfahren des Dokumentes 2 groß wird.
Beim Einrichten des Multicast-Kommunikationsnetzes vom Gesichtspunkt des effizienten Einrichtens von Multicast-Pfaden zwischen einem Quellenknoten und jedem Zielknoten ist ein Minimalbaumproblem bekannt, bei dem die Gesamtkosten der Multicast-Pfade minimiert werden. Dieses Problem wird Steiner-Baumproblem genannt. Das Steiner-Baumproblem ist als NP-Problem bekannt, bei welchem es in unmöglich wird, Pfade, die einen optimalen Minimal-Baum von dem Quellenknoten zu jedem Zielknoten bilden in einer endlichen Rechenzeit zu berechnen, wenn die Größe des Netzes groß ist.
Trotzdem zum Erhalten der Ideallösung des Steinerproblems NP hart ist, wird ein Rechenverfahren zum heuristischen Herleiten einer Näherungslösung als KMB-Kommunikationsverfahren vorgeschlagen (siehe Dokument 3: L. Kou, G. Markowsky und L. Berman, "A Fast Algorithm for Steiner Tree", Acta Informatica 15, 1981, Seiten 141 bis 145).
In diesem Verfahren werden der Quellenknoten und die Zielknotengruppe extrahiert und ein Graph, der durch Ränder gebildet wird, die jeweils einem kürzesten Pfad zwischen extrahierten Knoten entsprechen, wird zuerst konstruiert. Von dem konstruierten Graphen wird ein Minimalbereichsbaum konstruiert. Dann wird jeder Rand des Bereichsbaums ersetzt durch den kürzesten Pfad des Eingangsgraphen, um einen Sub-Graphen zu konstruieren. Dann wird ein Minimalbereichsbaum aus dem Sub-Graphen gefunden. Letztendlich werden Multicast-Pfade (Steinerbaum) konstruiert durch Löschen unnötiger Ränder aus dem Bereichsbaum.
Jedoch berücksichtigt gemäß dem Multicast-Pfadberechenverfahren des Dokumentes 3 obwohl die Übertragungskosten der gesamten Multicast-Pfade minimiert werden können, das Verfahren nicht die Kostenschwankung (Verzögerungsschwankung) von dem Quellenknoten zu jedem Zielknoten. Demnach wird die Kostenschwankung sehr groß. Daher gibt es beim Anwenden dieses Rechenverfahrens auf die Echtzeitanwendung, die keine große Verzögerungsschwankung zulässt, ein großes Problem dahingehend, dass große Verzögerungsschwankung auftritt zwischen Multicastempfängern.
RESÜMEE DER ERFINDUNG
Die Erfindung stellt ein Multicast-Kommunikationspfad-Rechenverfahren bereit, wie es in Anspruch 1 definiert ist, ein Multicast-Kommunikationspfad-Rechenverfahren bereit, wie es in Anspruch 4 definiert ist, und ein entsprechendes Computerprogramm und eine Computer-lesbares Medium, wie in Anspruch 8 bzw. 9 definiert.
Die vorliegende Erfindung kann die Rechenzeitkomplexität zum Berechnen von Multicast-Pfaden und die Verringerung der Verzögerungsschwankung zwischen Benutzern verbessern. Sie kann die Verzögerungsschwankung zwischen Benutzern verringern während der Reduzierung der Gesamtkosten von Multicast-Pfaden.
Gemäß der vorliegenden Erfindung schließt das Verfahren einen Rechenprozess zum Minimieren der Gesamtbaumkosten ein und einen Rechenprozess zum derartigen Formen des Baums, dass eine Verzögerungsschwankung vom Quellenknoten zu jedem Zielknoten klein ist. Demnach können Multicast-Pfade erhalten werden, bei denen die Verzögerungsschwankung verringert werden kann während die Gesamtkosten der Multicast-Pfade minimiert werden.
Zudem kann bei dem berechneten minimalen Baum der Rendezvouspunktknoten zum Optimieren der Verzögerungsschwankung dynamisch festgelegt werden, was sich von der konventionellen Technik unterscheidet.
KURZBESCHREIBUNG DER ZEICHNUNGEN
Andere Ziele, Merkmale und Vorteile der vorliegenden Erfindung werden ersichtlicher aus der folgenden detaillierten Beschreibung wenn gelesen im Zusammenhang mit den beiliegenden Zeichnungen, in welchen zeigt:
1 eine Figur zum Erläutern des Entwurfs eines Beispiels;
2 ein Blockdiagramm einer Multicast-Kommunikationspfad-Berechnungseinrichtung gemäß dem ersten Beispiel;
3 ein Konfigurationsbeispiel eines Pfadberechnungsmoduls 121 gemäß dem ersten Beispiel;
4 eine Konfiguration einer Multicast-Kommunikationspfad-Einstelleinrichtung gemäß dem ersten Beispiel;
5 ein Ablaufdiagramm zum Zeigen von Prozessen für das Berechnen von Pfaden bzw. Leitwegen in der Multicast-Kommunikationspfad-Recheneinrichtung gemäß dem ersten Beispiel;
6 ein Beispiel eines Multicast-Netzes gemäß dem ersten Beispiel;
7 Minimalverzögerungspfade von einem Quellenknoten zu jedem Zielknoten;
8 Pfade, die Multicast-Kommunikationspfad-Einstelleinrichtung 20, Knoten A, C, E, G, I und einen Zielknoten 3 verbinden;
9 einen Minimalverzögerungspfad von der Multicast-Kommunikationspfad-Einstelleinrichtung 20 zu dem Knoten E und Minimalverzögerungspfade von dem Knoten E zu jedem Zielknoten 1–5;
10 einen Entwurf der Prozedur zur Multicast-Kommunikationspfad-Berechnung gemäß einer ersten Ausführungsform;
11 eine Konfiguration eines Pfadberechnungsmoduls der Multicasts-Kommunikationspfad-Berechnungsvorrichtung der Ausführungsform;
12 ein Ablaufdiagramm des Multicast-Kommunikationspfad-Berechnungsverfahrens gemäß der Ausführungsform;
13 ein Beispiel eines Netzgraphen, auf den die Prozedur der Ausführungsform angewendet wird;
14 einen Netzgraphen, in dem der Quellenknoten ausgeschlossen ist;
15 einen Graphen eines kürzesten Pfades unter dem Zielknoten;
16 einen minimalen Spanning-Trees (aufgespannten Baum), der erhalten wird von dem Graphen des kürzesten Pfades unter dem Zielknoten;
17 ein Zwischenergebnis für die Konstruktion eines minimalen Spanning-Tree unter Berücksichtigung von Zwischenknoten;
18 einen Sub-Graphen, der einen minimalen Spanning-Tree unter Berücksichtigung von Zwischenknoten bildet;
19 einen minimalen Spanning-Tree des Sub-Graphen;
20 einen Zielknoten einschließenden Minimalbaum;
21 Multicast-Pfade von dem Quellenknoten zu jedem Zielknoten, in dem ein Rendezvouspunktknoten vorgesehen ist;
22 ein Konfigurationsbeispiel eines Multicast-Kommunikationspfad-Berechnungssystems gemäß der Ausführungsform;
23 ein Netz zum Evaluieren des Multicast-Kommunikationspfad-Berechnungssystems gemäß der Ausführungsform;
24 einen Performance-Evaluierungsgraphen von Multicast-Kommunikationspfadkosten; und
25 einen Performance-Evaluierungsgraphen einer Übertragungsverzögerungsschwankung.
DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORM
Im Folgenden wird eine Ausführungsform der vorliegenden Erfindung unter Bezugnahme auf 10 bis 25 beschrieben.
Als erstes wird ein Beispiel eines Multicast-Kommunikationspfadeinrichtverfahrens gemäß der Ausführungsform unter Bezugnahme auf die Figuren beschrieben. Diese liegt außerhalb des Schutzbereichs der Erfindung und ist dazu vorgesehen, das Verständnis der Erfindung zu unterstützen.
1 ist eine Figur zum Erläutern des Entwurfs des Beispiels. Ein Mulicastnetz zeigt eine Vielzahl von Knoten, von denen jeder eine Multicastübertragungseinrichtung einschließt. Eine Multicast-Kommunikationspfad-Recheneinrichtung wird in einem Knoten bereitgestellt und eine Multicast-Kommunikationspfad-Einstelleinrichtung wird in einem Knoten bereitgestellt. Die Multicast-Kommunikationspfad-Recheneinrichtung kann getrennt sein von den Knoten, die das Multicastnetz bilden. Zudem können die Multicast-Kommunikationspfad-Recheneinrichtung und die Multicast-Kommunikationspfad-Einstelleinrichtung in einem Knoten enthalten sein.
(1) Eine Multicastübertragungseinrichtung (Knoten) in dem Netz sammelt Netzmessinformation wie z. B. die Verzögerung von einer Datenübertragung auf jeder Verbindung. (2) Dann sendet jede Multicastübertragungseinrichtung die Netzmessinformation an die Multicast-Kommunikationspfad-Recheneinrichtung und die Multicast-Kommunikationspfad-Einstelleinrichtung. (3) Wenn Bedarf für das Einstellen von Multicast-Pfaden für das Übertragen von Multicastdaten aufkommt, führen die Multicast-Kommunikationspfad-Einstelleinrichtung und die Multicast-Kommunikationspfad-Recheneinrichtung das Einstellen der Multicast-Pfade durch Ausführen später erwähnter Prozesse aus. In der ersten Ausführungsform hat die Multicast-Übertragungseinrichtung die Fähigkeit des Sammelns von Netzmessinformation. Die Multicast-Kommunikationspfad-Recheneinrichtung hat eine Fähigkeit des Berechnens der Pfade bzw. der Leitwege. Die Multicast-Kommunikationspfad-Einstelleinrichtung hat eine Fähigkeit des Einstellens von Multicast-Pfaden im Netz.
Wenn die Multicast-Kommunikationspfad-Einstelleinrichtung und die Multicast-Kommunikationspfad-Recheneinrichtung getrennte Einrichtungen sind, fordert die Multicast-Kommunikationspfad-Einstelleinrichtung von der Multicast-Kommunikationspfad-Recheneinrichtung das Berechnen der Multicast-Pfade an. (4) Wenn die Multicast-Kommunikationspfad-Einstelleinrichtung und die Multicast-Kommunikationspfad-Recheneinrichtung die selbe Einrichtung sind, weist die Multicast-Kommunikationspfad-Einstelleinrichtung ihr Pfad-Rechenmodul an, die Pfade zu berechnen. (5) Dann berechnet das Pfad-Rechenmodul der Multicast-Kommunikationspfad-Einstelleinrichtung oder der Multicast-Kommunikationspfad-Recheneinrichtung die Multicast-Pfade in Übereinstimmung mit der gesammelten Information. (6) Das Rechenergebnis wird an ein Pfadeinstellmodul der Multicast-Kommunikationspfad-Einstelleinrichtung gesendet. (7) Dann stellt die Multicast-Kommunikationspfad-Einstelleinrichtung, die das Rechenergebnis empfängt, die Multicast-Pfade ein.
Mit der Fähigkeit des Sammelns der Netzmessinformation wird die Netzmessinformation unter Verwendung eines Protokolls mit Funktionen zum Austausch von Netzmessinformation zwischen benachbarten Knoten gesammelt, wie z. B. OSPF-TE (Open Shortest Path First-Traffic Engineering) und IS-IS-TE (Intermediate system-Intermediate system-Traffic Engineering) und ähnlichem.
Die Multicast-Kommunikationspfad-Recheneinrichtung schließt eine Funktion zum Empfangen von Netzmessinformation von einer Multicastübertragungseinrichtung ein, eine Paketübertragungsfunktion zum Senden des Rechenergebnisses, ein Programm zum Realisieren eines Algorithmus, der zur Pfadberechnung verwendet wird, ein Aufzeichnungsmedium zum Speichern der Netzmessinformation, des Pfad-Rechenprogramms und des Pfad-Rechenergebnisses, und eine Pfadberechnungsfunktion zum Umsetzen der Pfadberechnung. Die Multicast-Kommunikationspfad-Recheneinrichtung kann gegebenenfalls die Netzmessinformation von der Multicast-Kommunikationspfad-Recheneinrichtung empfangen, statt die Netzmessinformation selbst zu sammeln.
Das Pfad-Rechenprogramm, das in dieser Ausführungsform verwendet wird, hat eine Funktion zum Berechnen von Minimalverzögerungspfaden von einem Quellenknoten zu jedem Zielknoten, eine Funktion zum Berechnen von Verzögerungen von einem Kandidatenknoten zu jedem Zielknoten, in welchem der Kandidatenknoten auf einem Pfad existiert mit der maximalen Verzögerung unter den Minimalverzögerungspfaden und eine Funktion zum Auswählen eines Rendezvouspunkt-Knotens aus den Kandidatenknoten.
Gemäß den oben beschriebenen Funktionen kann die Zeitkomplexität zum Auswählen eines Kandidatenknotens als Rendezvouspunkt-Knoten verringert werden verglichen mit dem Verfahren nach Dokument 2 in Übereinstimmung mit dieser Ausführungsform. Zudem kann in Übereinstimmung mit der vorliegenden Ausführungsform durch Auswählen des Rendezvouspunkt-Knotens in Übereinstimmung mit einem Auswahlkriterium, das wirksam ist für das Verringern von Verzögerungsschwankung, die Verzögerungsschwankung verringert werden verglichen mit einem konventionellen Multicast-Pfad- Rechenverfahren, bei dem Minimalverzögerungspfade als Multicast-Pfade ausgewählt werden.
Zudem können gemäß der vorliegenden Erfindung, da die vorliegende Fähigkeit des Sammelns noch Netzmessinformation verwendet werden kann, die Multicast-Pfade leicht berechnet werden. Es ist leicht für die Multicast-Kommunikationspfad-Recheneinrichtung, die Netzmessinformation zu erhalten und es gibt einen Vorteil dahingehend, dass es nicht erforderlich ist, ein neues Protokoll zu entwickeln zum Sammeln der Netzmessinformation.
Im Folgenden werden die Multicast-Kommunikationspfad-Recheneinrichtung und die Multicast-Kommunikationspfad-Einstelleinrichtung beschrieben.
2 ist ein Blockdiagramm der Multicast-Kommunikationspfad-Recheneinrichtung. In 2 zeigt das Symbol 10 die Multicast-Kommunikationspfad-Recheneinrichtung. Die Multicast-Kommunikationspfad-Recheneinrichtung 10 schließt einen Informationsmanagementteil 11 ein, einen Pfad-Rechenteil 12 und einen Paketverarbeitungsteil 13. Der Informationsmanagementteil 11 dient dem Managen von Netzmessinformation in Bezug auf Verzögerung oder Kosten, die in jedem Knoten und jeder Verbindung zwischen Knoten im Netz auftreten. Der Pfad-Rechenteil 12 dient dem Berechnen von Multicast-Pfaden bzw. Mehrfachrufleitwegen. Der Paketprozessteil 13 dient dem Verarbeiten von zu sendenden oder zu empfangenden Pakten. Zudem empfängt der Paketverarbeitungsteil 13 die Netzmessinformation und eine Pfadberechnungsanfrage und sendet ein Rechenergebnis an die Multicast-Kommunikationspfad-Einstelleinrichtung.
Der Informationsmanagementteil 11 schließt ein Routing-Protokollmodul bzw. Leitwegprotokollmodul 111 ein und einen Messinformationsspeicherteil 112. Das Routing-Protokollmodul 111 verarbeitet ein Informationsaustauschprotokoll, das verwendet wird in einem Routing-Protokoll wie z. B. OSPF und IS-IS, die verwendet werden zum Sammeln von Information in Bezug auf den Verkehrszustand und ähnliches. Der Messinformationsspeicherteil 112 organisiert Netzmessinformation, die durch das Protokoll erhalten wird wie z. B. Topologie und Verzögerung und Kosten. Zudem schließt der Pfad-Rechenteil 12 ein Pfad-Rechenmodul 121 ein zum Berechnen von Multicast-Pfaden und einen Rechenergebnisspeicherteil 122 zum Speichern von Rechenergebnissen.
Der Paketverarbeitungsteil 13 schließt ein Paketverarbeitungsmodul 131 ein, einen Paketübertragungstabellenspeicherteil 132 und eine Netzschnittstelle 133. Das Paketverarbeitungsmodul 131 bestimmt den Typ eines ankommenden Paketes, sendet das Paket zu einem anderen Knoten oder sendet das Paket zu dem Informationsmanagementteil 11. Der Paketübertragungstabellenspeicherteil 132 speichert Übertragungsziele.
3 zeigt ein Beispiel einer Konfiguration des Pfadberechnungsmoduls 121 dieser Ausführungsform. Funktionen jedes Teils des Pfadberechnungsmoduls 121 können durch Hardware wie z. B. eine CPU und einen Speicher, und durch Software realisiert werden.
Wie in 3 gezeigt schließt das Pfadberechnungsmodul 121 einen Eingabeteil 141 ein, einen Minimalverzögerungspfadberechnungsteil 142, einen Kandidatenknotenauswahlteil 143, einen Differenzberechnungsteil 144, einen Rendezvouspunkt-Knotenauswahlteil 145 und einen Ausgabeteil 146. Der Eingabeteil 141 empfängt Topologieinformation und Verzögerungsinformation von dem Netz. Der Minimalverzögerungspfadberechnungsteil 142 berechnet Minimalverzögerungspfade von einem Quellenknoten zu jedem Zielknoten unter Verwendung der Topologieinformation und der Verzögerungsinformation. Der Kandidatenknotenauswahlteil 143 wählt Knoten als Kandidatenknoten der Rendezvouspunkt-Knotens aus, die sich auf einem Minimalverzögerungspfad unter den vielen Minimalverzögerungspfaden von dem Quellenknoten zu jedem Zielknoten befindet. Der Differenzberechnungsteil 144 berechnet für jeden der Kandidatenknoten Minimalverzögerungspfade von dem Kandidatenknoten zu jedem Zielknoten und berechnet für jeden der Kandidatenknoten eine Differenz zwischen dem Maximalwert und dem Minimalwert zwischen den Verzögerungen der berechneten Minimalverzögerungspfade. Der Rendezvouspunkt-Knotenauswahlteil 145 wählt einen Kandidatenknoten als Rendezvouspunkt-Knoten aus, von welchem die berechnete Differenz die geringste ist. Der Ausgabeteil 146 gibt als Multicast-Pfade einen Minimalverzögerungspfad von dem Quellenknoten zu dem Rendezvouspunkt-Knoten aus und jeden Minimalverzögerungspfad von dem Rendezvouspunkt-Knoten zu jedem Zielknoten.
Die Multicast-Kommunikationspfad-Recheneinrichtung 10 kann gegebenenfalls als ein Hauptcomputer konfiguriert sein, der getrennt von dem Multicastnetz vorgesehen ist, und eine CPU einschließt, einen Speicher, ein Festplattenlaufwerk und ähnliches. In diesem Fall wird eine Information, die erforderlich ist für die Pfadberechnung, von außen bereitgestellt und die Pfadberechnung wird durch das Verwenden eines Programms für Multicast-Kommunikationspfad-Berechnung ausgeführt.
4 zeigt ein Konfiguration der Multicast-Kommunikationspfad-Einstelleinrichtung. In dieser Figur zeigt das Bezugszeichen 20 die Multicast-Kommunikationspfad-Einstelleinrichtung. Die Multicast-Kommunikationspfad-Einstelleinrichtung 20 schließt einen Informationsmanagementteil 21 ein, einen Messteil 22, einen Pfad-Einstellprotokoll-Verarbeitungsteil 23 und einen Paketverarbeitungsteil 24. Der Informationsmanagementteil 21 organisiert Information in Bezug auf Verzögerung oder Kosten, die in Knoten aufkommen oder in Verbindungen im Netz. Der Mess-Teil 22 misst Verzögerungszeiten oder Kosten, die in ihm aufkommen. Der Pfadeinstellprotokoll-Verarbeitungsteil 23 führt Pfadeinstellung aus, wenn beispielsweise neue Datenströme aufkommen. Der Paketverarbeitungsteil 24 verarbeitet ankommende Pakete.
Die Grundstruktur des Informationsmanagementteils ist die selbe wie die des Informationsmanagementteils 11 in der Multicast-Kommunikationsrecheneinrichtung 10 und schließt ein Routing-Protokollmodul 211 ein und einen Messinformationsspeicherteil 212. Der Messteil 22 schließt ein Messmodul zum Messen von Zuständen der Netzschnittstelle 243 und Information wie z. B. Verzögerung jedes Knotens im Netz ein. Der Paketverarbeitungsteil 24 schließt ein Paketverarbeitungsmodul 241 ein, einen Paketübertragungstabellenspeicherteil 242 zum Speichern eines Übertragungsziels von Paketen und Netzschnittstellen 243. Das Paketverarbeitungsmodul 241 bestimmt Typen ankommender Pakete, leitet die Pakete weiter und bestimmt, ob ein neuer Pfad einzurichten ist. Zudem schließt die Multicast-Kommunikationspfad-Einstelleinrichtung 20 einen Pfad-Rechenteil 25 ein. Der Pfad-Rechenteil 25 schließt ein Rechenprozessmodul 251 zum Berechnen von Multicast-Pfaden ein und einen Rechenergebnisspeicherteil 252 zum Speichern des Rechenergebnisses. In dem Fall, indem die Multicast-Kommunikationspfad-Einstelleinrichtung 20 eine Berechnung von Multicast-Pfaden ausführt, führt der Pfadberechnungsteil 25 Prozesse aus, die die selben sind wie jene der Multicast-Kommunikationspfad-Recheneinrichtung 10. Wenn die Multicast-Kommunikationspfad-Einstelleinrichtung 20 keine Berechnung der Multicast-Pfade ausführt, kann die Multicast-Kommunikationspfad-Einstelleinrichtung 20 nicht den Pfad-Rechenteil 25 einschließen.
Der Pfadeinstellprotokoll-Verarbeitungsteil 23 empfängt Pfadeinstellanfragen von dem Paketverarbeitungsteil 24 und sendet die Anfragen an die Multicast-Kommunikationspfad-Recheneinrichtung 10. Zudem hat der Pfadeinstellprotokoll- Verarbeitungsteil 23 eine Funktion des Einstellens von Multicast-Pfaden im Netz in Übereinstimmung mit dem von der Multicast-Kommunikationspfad-Recheneinrichtung 10 erhaltenen Rechenergebnis.
Wenn die Multicast-Kommunikationspfad-Recheneinrichtung 10 und die Multicast-Kommunikationspfad-Einstelleinrichtung 20 im selben Knoten eingeschlossen sind, schließt der Knoten jeden Prozessteil der Multicast-Kommunikationspfad-Recheneinrichtung 10 und der Multicast-Kommunikationspfad-Einstelleinrichtung 20 ein.
Als nächstes wird der Betrieb der Multicast-Kommunikationspfad-Recheneinrichtung 10, der Multicast-Kommunikationspfad-Einstelleinrichtung 20 und der Multicast-Übertragungseinrichtung beschrieben.
Die Knoten im Netz tauschen mit Nachbarnknoten Netzmessinformation einschließlich Topologie und Verzögerung des Netzes aus. Jeder Knoten speichert die durch die Austauschoperation erhaltene Netzmessinformation.
Die Netzmessinformation schließt nicht nur Information ein, die durch den eigenen Knoten gemessen worden ist, sondern schließt auch Information ein, die von anderen Knoten gemessen worden ist. In Übereinstimmung mit der Austauschoperation kann jeder Knoten Netzmessinformation von allen Knoten des Netzes erhalten.
Ein Knoten mit der Fähigkeit der Multicast-Kommunikationspfad-Einstelleinrichtung 20 sendet eine Pfadberechnungsanfrage an einen Knoten mit der Fähigkeit der Multicast-Kommunikationspfad-Recheneinrichtung 10. Der Knoten mit der Fähigkeit der Multicast-Kommunikationspfad-Recheneinrichtung 10 berechnet die Multicast-Pfade unter Verwendung der durch den Informationsmanagementteil 11 gemanagten Netzmessinformation und von Information von Zielknoten, die von dem Knoten, der die Pfadberechnungsanfrage sendet, gesendet worden sind.
5 ist ein Ablaufdiagramm zum Zeigen von Prozessen zum Berechnen von Multicast-Pfaden in der Multicast-Kommunikationspfad-Recheneinrichtung 10.
Zuerst empfängt die Multicast-Kommunikationspfad-Recheneinrichtung 10 die Pfadberechnungsanfrage von der Multicast-Kommunikationspfad-Einstelleinrichtung 20. Zu diesem Zeitpunkt empfängt die Multicast-Kommunikationspfad-Recheneinrichtung 10 auch Information des Quellenknotens und der Zielknoten von der Multicast-Kommunikationspfad-Einstelleinrichtung 20. Dann liest der Pfad-Rechenteil 20 in der Multicast-Kommunikationspfad-Recheneinrichtung 10 von dem Messinformationsspeicherteil 112 in dem Informationsmanagementteil 11 die Netzmessinformation, die ein Topologie- und Verkehrsstatus des Netzes angibt im Schritt S1. Dann berechnet das Pfadberechnungsmodul 121 Minimalverzögerungspfade zwischen dem Quellenknoten zu jedem Zielknoten unter Verwendung der Netzmessinformation im Schritt S2. Insbesondere berechnet das Pfadberechnungsmodul 121 jeden Minimalverzögerungspfad zwischen dem Quellenknoten, der die Pfadberechnungsanfrage sendet, und jedem Zielknoten. Zum Berechnen des Minimalverzögerungspfades wird beispielsweise ein Dijkstra-Algorithmus verwendet.
Als nächstes wählt im Schritt S3 das Pfadberechnungsmodul der Multicast-Kommunikationspfad-Recheneinrichtung 10 einen Minimalverzögerungspfad aus, der die maximale Verzögerung unter den Minimalverzögerungspfaden hat, die im Schritt S2 berechnet worden sind. Dann berechnet das Pfadberechnungsmodul 121 für jeden Knoten (der als Kandidatenknoten bezeichnet wird) auf dem ausgewählten Minimalverzögerungspfad Datenübertragungsverzögerungen von dem Knoten zu jedem Zielknoten im Schritt S4. Dann berechnet das Pfadberechnungsmodul 121 für jeden Kandidatenknoten eine Differenz zwischen der maximalen Verzögerung und der minimalen Verzögerung zwischen den im Schritt S4 berechneten Verzögerungen und wählt einen Kandidatenknoten, durch welchen die geringste Differenz berechnet worden ist, als den Rendezvouspunkt-Knoten im Schritt S5 aus. Insbesondere werden im Schritt S5 die Differenz δ zwischen der maximalen Verzögerung und der minimalen Verzögerung zum Übertragen von Daten von einem Kandidatenknoten zu jedem Zielknoten für jeden Kandidatenknoten berechnet und der Rendezvouspunkt-Knoten wird als ein Kandidatenknoten bestimmt, der die Minimaldifferenz δ hat. Dann führt das Pfadberechnungsmodul 121 das Rechenergebnis zu dem Knoten zurück, der die Pfadberechnungsanfrage gesendet hat, über den Paketverarbeitungsteil 12 im Schritt S6, wobei das Rechenergebnis einen Pfad von dem Quellenknoten zu dem Rendezvouspunkt-Knoten und Pfade von dem Rendezvouspunkt-Knoten zu jedem Zielknoten angibt.
In dieser Ausführungsform wird zum Sammeln der Netzmessinformation wie z. B. Verzögerung durch die Multicast-Übertragungseinrichtung ein Kommunikationsprotokoll OSPF-TE verwendet. In dem OSPF-TE ist Verkehrsinformation wie Verzögerung in Topologieinformationsaustauschinformation des OSPF enthalten, welches ein Unicast- bzw. ein Einzelverbindungsrouting- bzw. Leitwegfindeprotokoll ist.
Zudem wird gemäß dieser Ausführungsform ein Multicast-MPLS-Protokoll (MPLS = Multi Protocol Label Switching) verwendet als ein Protokoll zum Einstellen von Multicast-Pfaden. Das Multicast-MPLS-Protokoll ist eine Erweiterung von RSVP-TE (Resource Reservation Protocol-Traffic Engineering) zum Realisieren expliziter Pfadfestlegung. Das Multicast-MPLS ist eine Technologie, bei welcher ein Informationselement zu RSVP-TE hinzugefügt wird, welches bei normalem MPLS verwendet wird, zu einer Meldung zum Erzeugen von LSP (Label Switched Path) zum Speichern von Baumtopologie, so dass Punkt-zu-Mehrpunkt-LSP kann in Übereinstimmung mit der Topologieinformation eingerichtet werden.
Im Folgenden wird ein Prozessbeispiel zum Berechnen von Multicast-Pfaden in Übereinstimmung mit dieser Ausführungsform beschrieben.
6 zeigt ein Multicastnetz. In dieser Figur zeigen Symbole 1–5 Zielknoten. A–I geben Knoten an, die zwischen dem Quellenknoten und den Zielknoten existieren und jeder Knoten schließt die Fähigkeit des Multicast-Übertragungseinrichtens ein. Ein Multicastnetz wird durch die Multicast-Kommunikationspfad-Einstelleinrichtung 20 (Quellenknoten), die Knoten A–I und die Zielknoten 1–5 gebildet, die durch Kommunikationsleitungen verbunden sind. Jede an jeder Verbindung gezeigte Nummer gibt eine Verzögerung (Kosten) der Verbindung an.
Die Multicast-Kommunikationspfad-Einstelleinrichtung 20, die ein Quellenknoten ist, überträgt Daten zu den Zielknoten 1–5 in Übereinstimmung mit dem von der Multicast-Kommunikationspfad-Recheneinrichtung 10 berechneten Ergebnis. Die Netzmessinformation wie z. B. Verzögerung, die in jeder Verbindung auftritt, wird durch jeden Knoten unter Verwendung des oben erwähnten OSPF-TE gesammelt. Die Netzmessinformation wird im Voraus zu der Multicast-Kommunikationspfad-Recheneinrichtung gesendet.
7 zeigt Minimalverzögerungspfade von dem Quellenknoten zu jedem Zielknoten.
Wenn die Multicast-Kommunikationspfad-Recheneinrichtung 10 eine Pfadberechnungsaufforderung von der Multicast-Kommunikationspfad-Einstelleinrichtung 20 empfängt, berechnet die Multicast-Kommunikationspfad-Recheneinrichtung 10 die Minimalverzögerungspfade von dem Quellenknoten (Multicast-Kommunikationspfad-Einstelleinrichtung 20) zu jedem Zielknoten als erstes. Zum Berechnen der Minimalverzögerungspfade verwendet die Multicast-Kommunikationspfad-Recheneinrichtung 10 einen Dijkstra-Algorithmus. Ein Dijkstra-Algorithmus wird im Allgemeinen zum Berechnen eines Minimalverzögerungspfades verwendet. Die Minimalverzögerungspfade, die durch die Multicast-Kommunikationspfad-Recheneinrichtung 10 berechnet worden sind, sind die Multicast-Kommunikationspfad-Recheneinrichtung 20 → der Knoten A → der Knoten C → der Zielknoten 1, die Multicast-Kommunikationspfad-Einstelleinrichtung 20 → der Knoten A → der Knoten C → der Knoten E → der Knoten G → der Zielknoten 2, die Multicast-Kommunikationspfad-Einstelleinrichtung 20 → der Knoten A → der Knoten C → der Knoten E → der Knoten G → der Knoten I → der Zielknoten 3, die Multicast-Kommunikationspfad-Einstelleinrichtung 20 → der Knoten A → der Knoten C → der Knoten D → der Knoten F → der Zielknoten 4, und die Multicast-Kommunikationspfad-Einstelleinrichtung 20 → der Knoten A → der Knoten C → der Knoten D → der Zielknoten 5.
Die Verzögerung für die Verbindung Quellenknoten → Zielknoten 1 ist 4, die Verzögerung für Quellenknoten → Zielknoten 2 ist 7, die Verzögerung für Quellenknoten → Zielknoten 3 ist 9, die Verbindung für Quellenknoten → Zielknoten 4 ist 6 und die Verzögerung für die Quellenknoten → Zielknoten 5 ist 5. Daher ist der Minimalverzögerungspfad mit der maximalen Verzögerung der Minimalverzögerungspfad von dem Quellenknoten zu dem Zielknoten 3.
Als nächstes wählt die Multicast-Kommunikationspfad-Recheneinrichtung 10 einen Rendezvouspunkt-Knoten unter den Knoten A, C, E, G und I auf dem Minimalverzögerungspfad von dem Quellenknoten zu dem Zielknoten 3 mit der maximalen Verzögerung unter den Minimalverzögerungspfaden.
8 zeigt den Quellenknoten und die Knoten A, C, E, G, I und den Zielknoten 3 verbindenden Minimalverzögerungspfad. Im Folgenden wird der Minimalverzögerungspfad als Rendezvouspunkt-Kandidatenpfad bezeichnet. Zudem werden die Knoten A, C, E, G und I Kandidatenknoten genannt.
Als nächstes berechnet die Multicast-Kommunikationspfad-Recheneinrichtung 10 für jeden Kandidatenknoten Minimalverzögerungspfade von dem Kandidatenknoten zu jedem Zielknoten 1–5. Für jeden Kandidatenknoten n (n: n gibt eine Zahl eines Kandidatenknotens an) unter der Annahme, dass die maximale Verzögerung zwischen den Verzögerungen der berechneten Minimalverzögerungspfade durch Dmax (n) dargestellt wird und die Minimalverzögerung dargestellt wird durch Dn (n), berechnet die Multicast-Kommunikationspfad-Recheneinrichtung 10 Dmax (A) und Dmin (A), Dmax (C) und Dmin (C), Dmax (E) und Dmin (E), Dmax (G) und Dmin (G), und Dmax (I) und Dmin (I).
Zum Verringern der Verzögerungsschwankung zwischen Benutzern ist es erforderlich, dass eine Differenz zwischen Dmax und Dmin gering ist. Daher wählt die Multicast-Kommunikationspfad-Recheneinrichtung 10 einen Kandidatenknoten als Rendezvouspunkt-Knoten aus, durch welchen die Differenz zwischen Dmax (n) und Dmin (n) am geringsten ist. Spezieller, die Multicast-Kommunikationspfad-Recheneinrichtung 10 berechnet jede Differenz zwischen Dmax (A) und Dmin (A), zwischen Dmax (C) und Dmin (C), zwischen Dmax (E) und Dmin (E), zwischen Dmax (G) und Dmin (G) und zwischen Dmax (I) und Dmin (I). Dann wählt die Multicast-Kommunikationspfad-Recheneinrichtung 10 einen Kandidatenknoten, durch den die Differenz am geringsten ist, als Rendezvouspunkt-Knoten aus. Da der Kandidatenknoten, durch welchen die Differenz zwischen Dmax (n) und Dmin (n) minimal ist, der Knoten E ist, wählt als ein Ergebnis die Multicast-Kommunikationspfad-Recheneinrichtung 10 den Knoten E als Rendezvouspunkt-Knoten aus. Die Verzögerung vom Knoten E zum Zielknoten 1 ist 3, die Verzögerung vom Knoten E zum Zielknoten 2 ist 2, die Verzögerung vom Knoten E zum Zielknoten 3 ist 4 und die Verzögerung vom Knoten E zum Zielknoten 4 ist 3 und die Verzögerung vom Knoten E zum Zielknoten 5 ist 4. Daher liegt die Schwankung der Verzögerung vom Rendezvouspunkt-Knoten zu jedem Zielknoten innerhalb eines Bereichs von 2–4.
Die Multicast-Kommunikationspfad-Recheneinrichtung 10 bereitet als Multicast-Kommunikationspfade einen Minimalverzögerungspfad von der Multicast-Kommunikationspfad-Einstelleinrichtung 20 zum Knoten E vor und Minimalverzögerungspfade von dem Knoten E zu jedem Zielknoten 1–5. Dann sendet die Multicast-Kommunikationspfad-Recheneinrichtung 10 das Rechenergebnis an die Multicast-Kommunikationspfad-Einstelleinrichtung 20. 9 zeigt den Minimalverzögerungspfad von der Multicast-Kommunikationspfad-Einstelleinrichtung 20 zu dem Knoten E und die Minimalverzögerungspfade von dem Knoten E zu jedem Zielknoten 1–5. Daten werden von der Multicast-Kommunikationspfad-Einstelleinrichtung 20 zu jedem Zielknoten über den Knoten E übertragen, der der Rendezvouspunkt-Knoten ist. Als nächstes schließt die Multicast-Kommunikationspfad-Einstelleinrichtung 20, die Information in Bezug auf die Multicast-Kommunikationspfade empfängt, die Information der Multicast-Kommunikationspfade in einer Übertragungspfad-Einstellsteuermeldung ein und richtet die Multicast-Pfade unter Verwendung von Multicast-MPLS ein, was ein Protokoll ist zum Einstellen von Pfaden und ein erweitertes Protokoll von RSVP-TE. Dann überträgt die Multicast-Kommunikationspfad-Einstelleinrichtung 20 Daten über die Multicast-Pfade nach dem Einrichten der Multicast-Pfade.
Die Zeitkomplexität O des Dijkstra-Algorithmus ist im Allgemeinen n², wenn die Anzahl der Knoten n ist. Da die Multicast-Pfade durch Anwenden von Dijkstra-Algorithmen zu jedem der n Knoten in Übereinstimmung mit konventioneller Technologie berechnet werden, ist die Zeitkomplexität O = n³ in Übereinstimmung mit der konventionellen Technologie. Jedoch, gemäß der vorliegenden Erfindung, da Dijkstra-Algorithmen angewendet werden auf p Knoten (P < n) eines Minimalverzögerungspfades zwischen dem Quellenknoten und einem Zielknoten, ist die Zeitkomplexität O = pn². Daher, verglichen mit der konventionellen Technologie, kann die Zeitkomplexität verringert werden.
Jede der Multicast-Kommunikationspfad-Recheneinrichtungen und der Multicast-Kommunikationspfad-Einstelleinrichtungen schließt ein Computersystem in sich ein. Die oben erwähnten Prozesse dieser Ausführungsform können durch Lesen eines Programms von einem computerlesbaren Medium und Ausführen des Programms realisiert werden. Das computerlesbare Medium kann eine Magnetscheibe sein, eine optisch-magnetische Scheibe, eine CD-ROM, eine DVD-ROM, eine Halbleiterspeicher und ähnliches. Das Computerprogramm kann zu einem Computer über eine Kommunikationsleitung geliefert werden, und der Computer kann als Multicast-Kommunikationspfad-Recheneinrichtung oder Multicast-Kommunikationspfad-Einstelleinrichtung funktionieren.
Wie oben erwähnt können durch Annehmen eines Systems, das einen Knoten zum Berechnen von Pfaden einschließt, der den Pfad-Rechenalgorithmus unter Berücksichtigung der Verzögerungsschwankung zwischen Benutzern ausführt, Verzögerungen zwischen Benutzern ausgeglichen bzw. angepasst oder entzerrt werden. Demgemäß kann ein Dienst bereitgestellt werden zum Zufriedenstellen der Fairness zwischen Benutzern in Bezug auf Verzögerung, was gemäß der konventionellen Technologie schwierig war. Zudem kann eine schnellere Berechnung verglichen mit einem konventionellen Gerät erhalten werden, das einen Dienst zum Zufriedenstellen der Fairness zwischen Benutzern in Bezug auf Verzögerung bereitstellt. Entsprechend kann die Pfadeinrichtungszeit verringert werden.
(Erste Ausführungsform)
Im Folgenden wird eine Ausführungsform der vorliegenden Erfindung unter Bezugnahme auf die Figuren beschrieben.
In der ersten Ausführungsform unterscheidet sich der Rechenalgorithmus zum Berechnen der Multicast-Pfade von dem des ersten Beispiels. Die anderen Konfiguration en können dieselben sein wie jene des ersten Beispiels.
10 zeigt einen Entwurf der Prozedur des Multicast-Kommunikationspfadrechenverfahrens gemäß der Ausführungsform.
Zuerst wird ein Distanzgraph in die Multicast-Kommunikationspfadrechenvorrichtung im Schritt S11 eingegeben, wobei der Distanzgraph Multicast-Netztopologie und Netzübertragungskosten unter Verwendung von zwischen Knoten verbindender Verbindungsinformation und Übertragungskosteninformation, die für die Übertragung von Daten auf der Verbindung erforderlich ist, repräsentiert. Statt des Eingebens des Distanzgraphen von außerhalb kann der Distanzgraph in der Vorrichtung im Voraus gesammelt werden und kann von einem Aufzeichnungsmedium in der Vorrichtung ausgelesen werden.
Als Nächstes werden Quellenknoteninformation und Zielknoteninformation im Schritt S12 eingegeben. Von der eingegebenen Information wird ein erster Distanz-Sub-Graph eingerichtet, in welchem der Quellenknoten im Schritt S13 gelöscht wird.
Danach wird die Zielknotengruppe von dem ersten Distanz-Sub-Graphen ausgewählt und ein zweiter Distanz-Sub-Graph wird konstruiert, der durch Ränder in Entsprechung zu den kürzesten Pfaden zwischen den Zielknoten im Schritt S14 gebildet wird. Dann wird im Schritt S15 ein Minimal-Spanning-Tree von dem zweiten Distanz-Sub-Graphen konstruiert. Zu diesem Zeitpunkt nehme man, wenn mehrere Minimal-Spanning-Trees existieren, einen beliebige von diesen.
Dann wird jeder Rand, der einem kürzesten Pfad in dem Minimal-Spanning-Tree entspricht, in einem durch Knoten des Eingangsdistanzgraphen gebildeten Pfad rekonstruiert, so dass im Schritt S16 ein Sub-Graph konstruiert wird. Dann wird im Schritt S17 ein Minimal-Spanning-Tree von dem rekonstruierten Sub-Graphen konstruiert. Wenn es mehrere Spanning-Trees gibt, nehme man einen beliebigen. Von dem konstruierten Spanning-Tree werden unnötige Ränder derart gelöscht, dass alle Zielknoten einen Teil des Spanning-Trees bilden, so dass im Schritt S18 Multicast-Pfade, die alle Zielknoten einschließen, eingerichtet werden.
Knoten in den konstruierten Multicast-Pfaden werden Kandidatenknoten eines Referenzpunktknotens. Dann werden für jeden Kandidatenknoten Distanzen von einem Kandidatenknoten zu dem jeweiligen Zielknoten berechnet, und eine Differenz zwischen der Maximaldistanz und der Minimaldistanz in den Distanzen wird berechnet. Dann wird ein Kandidatenknoten als Rendezvouspunktknoten ausgewählt, in welchem die unterschiedlichen die Differenz zwischen den Kandidatenknoten im Schritt S19 minimal ist. Dann wird der Multicast-Pfad, der durch die Zielknoten gebildet wird, mit den Sourceknoten am Rendezvouspunktknoten verbunden und Multicast-Pfade, die den Quellenknoten und alle Zielknoten einschließen, werden im Schritt S20 konstruiert.
11 zeigt eine Konfiguration eines Pfadberechnungsmoduls der Multicast-Kommunikationspfad-Berechnungsvorrichtung gemäß der Ausführungsform der vorliegenden Erfindung.
Das in 11 gezeigte Pfadberechnungsmodul schließt einen Informationseingabeteil 300 ein, einen ersten Distanz-Sub-Graph-Konstruierteil 311, einen zweiten Distanz-Sub-Graph-Konstruierteil 312, einen ersten Minimal-Spanning-Tree-Konstruierteil 313, einen Pfadrekonstruktionsteil 314, einen zweiten Minimal-Spanning-Tree-Konstruktionsteil 315, einen ersten Multicast-Pfad-Konstruktionsteil 316, einen Rendezvouspunktauswahlteil 317 und einen zweiten Multicast-Kommunikationspfad-Konstruktionsteil 318.
Der Informationseingabeteil 300 empfängt den Distanzgraphen, wobei der Distanzgraph Multicast-Netztopologie und Netzübertragungskosten unter Verwendung von Verbindungsinformation des Verbindens zwischen Knoten zeigt und Übertragungskosteninformation, die erforderlich ist zum Übermitteln von Daten auf der Verbindung. Zudem empfängt der Informationseingabeteil 300 Quellenknoteninformation und Zielknotengruppenformation. Die Netzübertragungskosten in der zweiten Ausführungsform entsprechen einer "Verzögerung" in der ersten Ausführungsform.
Der erste Distanz-Sub-Graph-Konstruktionsteil 311 konstruiert einen ersten Distanz-Sub-Graphen, wobei der Quellenknoten in dem eingegebenen Distanzgraphen gelöscht ist.
Der zweite Distanz-Sub-Graph-Konstruktionsteil 312 wählt die Zielknotengruppe von dem ersten Distanz-Sub-Graphen aus und konstruiert einen zweiten Distanz-Sub-Graphen, der durch die kürzesten Pfade zwischen jeweils zwei Knoten in der Zielknotengruppe gebildet wird.
Der erste Minimal-Spanning-Tree-Konstruktionsteil 313 konstruiert einen Minimal-Spanning-Tree von dem zweiten Distanz-Sub-Graphen; wenn zu dieser Zeit eine Vielzahl von Minimal-Spanning-Trees existieren, wählt er einen beliebigen aus.
Der Übertragungspfad-Konstruktionsteil 314 konstruiert den jeweiligen Rand, der einem kürzesten Pfad in dem Minimal-Spanning-Tree entspricht, in einen Pfad, der durch Knoten des eingegebenen Distanzgraphen gebildet wird, so dass ein Sub-Graph eingerichtet wird.
Der zweite Minimal-Spanning-Tree-Konstruktionsteil 315 wählt wieder einen Minimal-Spanning-Tree von dem durch den Übertragungspfad-Konstruktionsteil 314 konstruierten Sub-Graphen. Wenn es mehrere Spanning-Trees gibt, wird ein beliebiger ausgewählt.
Der erste Multicast-Kommunikationspfad-Konstruktionsteil 316 löscht unnötige Ränder von dem konstruierten Spanning-Tree derart, dass alle Zielknoten zu einem Teil des Spanning-Trees werden, so dass Multicast-Pfade, die alle Zielknoten einschließen, eingerichtet werden.
Knoten in den Multicast-Pfaden sind Kandidatenknoten eines Rendezvouspunktknotens. Der Rendezvouspunktauswahlteil 317 berechnet für jeden Kandidatenknoten Übertragungsdistanzen von einem Kandidatenknoten zu jedem Zielknoten, und berechnet eine Differenz zwischen der maximalen Distanz und der minimalen Distanz in den Übertragungsdistanzen. Dann wählt der Rendezvouspunktauswahlteil 317 einen Kandidatenknoten als den Rendezvouspunktknoten aus, in welchem die Differenz zwischen den Kandidatenknoten minimal ist.
Der zweite Multicast-Kommunikationspfad-Konstruktionsteil 318 verbindet die durch die Zielknoten gebildeten Multicast-Pfade zu dem Quellenknoten bei dem Rendezvouspunktknoten, um Multicast-Pfade einzurichten, die den Quellenknoten und alle Zielknoten einschließen.
Im Folgenden wird die Prozedur zum Berechnen der Multicast-Pfade in Übereinstimmung mit dieser Ausführungsform detailliert beschrieben. In dieser Ausführungsform wird die folgende Information beispielsweise von dem Messergebnisspeicherteil eingegeben. Die folgende Information kann als Netzmessinformation unter Verwendung des in dem ersten Beispiel beschriebenen existierenden Protokolls gesammelt werden.

(1) Ein gerichteter Distanzgraph, der eine Topologie des gesamten Netzes beschreibt: G = (V, E, d), wobei V: Knoten, E: Verbindungen (Ränder) zwischen Knoten, d: Kosten von Verbindungen (entsprechend der Verzögerung der ersten Ausführungsform)
(2) Multicast-Verkehrsquellenknoten: s (⊆V)
(3) Multicast-Verkehrszielknoten (Zielknotengruppe): S (⊆V) Durch Eingeben der obigen Information der Multicast-Pfade: T durch Durchführen der folgenden Berechnung ausgegeben.

12 ist ein Ablaufdiagramm des Multicast-Kommunikationspfad-Berechnungsverfahrens nach der Ausführungsform.
Schritt 101) Ein Sub-Graph G' = (V-s, E-Es, d-ds) wird durch Löschen des Quellenknotens von dem eingegebenen Graphen G = (V, E, d) konstruiert.
Schritt 102) Die Zielknotengruppe S wird von dem Sub-Graphen D ausgewählt und es wird ein Distanz-Sub-Graph G1 = (V1, E1, d1) konstruiert, wobei der Distanz-Sub-Graph G1 = (V1, E1, d1) jeweils durch die Zielknotengruppe S und die kürzesten Pfade zwischen zwei Knoten in der Zielknotengruppe S gebildet wird.
Schritt 103) Ein Minimal-Spanning-Tree T1 wird von dem Distanz-Sub-Graphen G1 konstruiert. Wenn es mehrere Spanning-Trees gibt, wird ein beliebiger Spanning-Tree ausgewählt.
Schritt 104) Durch Ersetzen jedes Randes des Spanning-Trees T1 durch entsprechende kürzeste Pfade in dem Graphen G wird ein Sub-Graph Ga konstruiert. Wenn es eine Vielzahl kürzester Pfade gibt, wird ein beliebiger ausgewählt.
Schritt 105) Ein Minimal-Spanning-Tree Ts wird aus dem Sub-Graphen Ga konstruiert. Wenn es eine Vielzahl von Minimal-Spanning-Trees gibt, wird ein beliebiger ausgewählt.
Schritt 106) Multicast-Pfade, die die Zielknotengruppe S einschließen, werden durch Löschen unnötiger Ränder von dem Minimal-Spanning-Tree Ts derart gebildet, dass alle Zielknoten eingeschlossen sind.
Schritt 107) Knoten, die die im Schritt 106 konstruierten Multicast-Pfade bilden, werden als Kandidaten eines Rendezvouspunktknotens (RP)-Knoten ausgewählt. Dann werden Distanzen d(RPx, NODEy) zwischen RPx und jedem Zielknoten berechnet und eine Differenz zwischen dmax und dmin wird berechnet, bei der dmin eine kürzeste Distanz von RPx zu dem Zielknoten ist und dmin dmax eine längste Distanz von RPx zu dem Zielknoten ist. Die Distanz d (RPx, NODEy) kann die kürzeste Distanz zwischen RPx und NODEy sein. Dann wird ein Kandidat, von dem die Differenz die kleinste ist, als Rendezvouspunktknoten (RP-Knoten) ausgewählt. Das heißt, ein Kandidat, der [min(dmax (RPx, NODEy) – dmin (RPx, NODEz))] erfüllt, wird als der Rendezvouspunktknoten ausgewählt.
Schritt 108) Die im Schritt 106 konstruierten Multicast-Kommunikationspfade werden zu dem Quellenknoten s über den Rendezvouspunktknoten verbunden, so dass die den Quellenknoten n die Zielknotengruppe S einschließenden Multicast-Pfade konstruiert werden.
Im Folgenden wird ein Beispiel zum Berechnen von Multicast-Pfaden unter Verwendung der oben erwähnten Prozedur beschrieben. 13 zeigt einen Netzwerkgraphen eines Multicast-Netzes (das die Prozedur in diesem Beispiel angewendet wird).
13 zeigt ein durch 10 Knoten von V0 bis V9 gebildetes Netz. Jeder Knoten wird durch eine Verbindung verbunden und die Anzahl der jeweiligen Verbindungen zeigt Übertragungskosten. Beispielsweise 1 der Verbindung zwischen dem Knoten V0 und dem Knoten V1 zugewiesen ist, sind die Übertragungskosten für das Übertragen von Daten von dem Knoten V0 zu dem Knoten V1 gleich 1.
Für das Konstruieren der Multicast-Kommunikationspfade von dem Quellenknoten V0 zu der Zielknotengruppe V1, V2, V3 und V4 wird in Übereinstimmung mit der Ausführungsform die folgende Rechenprozedur durchgeführt.
Wenn das Pfadberechnungsmodul Netzgraphinformation von 13 und Quellenknoteninformation V0 und Zielknotengruppen-Information V1, V2, V3 und V4 empfängt, werden der Knoten V0 und die mit V0 verbunden Verbindungen V0V1, V0V9 und V0V4 von dem eingegebenen Graphen gelöscht. 14 zeigt den Netzgraphen, in dem der Quellenknoten und die Verbindungen gelöscht sind. Das heißt, 14 zeigt einen Netzgraphen nach dem Durchführen des Prozesses des Schrittes 101.
Dann wird Zielknoten durch den Schritt 102 ein Kürzestpfadgraph zwischen konstruiert. 15 zeigt das Ergebnis des Schrittes 102.
Danach wird durch den Schritt 103 der durch Ränder, die die kürzesten Pfade unter den Zielknoten bilden, gebildete Minimal-Spanning-Tree konstruiert. 16 zeigt das Ergebnis. Danach wird jeder Rand, der den Spanning-Tree bildet, ersetzt durch den Ursprungspfad des eingegebenen Graphen. 17 zeigt ein Zwischenergebnis dieses Prozesses. 18 zeigt das Ergebnis. Wie in der Figur gezeigt, werden, da der kürzeste Pfad zwischen dem Knoten V1 und dem Knoten V4 durch Knoten V1V9V5V4 gebildet wird, die Knoten V9 und V9 zwischen V1 und V4 eingefügt. Auf dieselbe Weise werden Knoten, die die kürzesten Pfade bilden zwischen den Knoten V1 und V2 und zwischen den Knoten V2 und V3 eingefügt. In diesem Beispiel wird, da die Knoten V9, V6 und V5 für mehrere Pfade überlappen, der in 18 gezeigte Sub-Graph durch Formen des Graphen unter Berücksichtigung der tatsächlichen physikalischen Verbindungen erhalten.
Danach wird durch den Schritt 105 ein Minimal-Spanning-Tree (Ts) von dem in 18 gezeigten Graphen gebildet. 19 zeigt das Ergebnis.
Dann werden durch den Schritt 106 Multicast-Pfade (ein Minimalbaum), die die Zielknoten einschließen, durch Löschen unnötiger Ränder derart, dass die Zielknoten in den Multicast-Pfaden enthalten sind, eingerichtet. Das Ergebnis ist in 20 gezeigt. Wie in 20 gezeigt, wird ein Minimalbaum VIV9V5V6V2V3V4 gebildet, der die Zielknoten V1, V2, V3 und V4 einschließt.
Danach wird durch den Schritt 107 ein Rendezvouspunktknoten unter den Knoten in dem Minimalbaum derart ausgewählt, dass eine Schwankung der Übertragungsdistanzen zu dem jeweiligen Knoten minimal wird. Zum Auswählen des Rendezvouspunktknotens wird jeder Knoten, der den Minimalbaum bildet, ein Kandidat des Rendezvouspunktknotens. Für jeden Kandidaten werden die Übertragungsdistanzen von dem Kandidaten zu jedem Zielknoten berechnet und eine Differenz der Maximaldistanz und der Minimaldistanz in den Übertragungsdistanzen werden erhalten. In dem Beispiel der 20 ist die Differenz zwischen der Maximaldistanz (dmax) und der Minimaldistanz (dmin), wenn der Knoten V9 ein Kandidat des Rendezvouspunktknotens ist, da die Distanzen die folgenden sind:
RP·V1 = 1
RP·V2 = 3,
RP·V3 = 3,
RP·V4 = 2,
gleich 2. In dem Beispiel der 21 ist beim Bestimmen, dass der Knoten V5 gleich RP ist, jede Übertragungsdistanz RP zu den Zielknoten V1, V2, V3 und V4 gleich 2. Dies bedeutet, dass der Knoten V5, bei dem die Differenz 0 ist, der optimale Rendezvouspunkt ist.
Zudem wird durch den Schritt 108 der Quellenknoten V0 mit dem Rendezvouspunktknoten verbunden, so dass die optimalen Multicast-Pfade von dem Quellenknoten zu den Zielknoten konstruiert werden.
22 zeigt ein Konfigurationsbeispiel eines Multicast-Kommunikationspfadrechensystem gemäß der Ausführungsform. Das heißt, das System kann nicht nur wie in 1 gezeigt konfiguriert werden, sondern auch wie in 22 gezeigt. Das System, das in 22 gezeigt wird, führt die oben erwähnte Multicast-Berechnungsprozedur aus.
Die Netzverkehrs-Informationsdatenbank 120 sammelt Netzverkehrsinformationen unter Verwendung eines Routing-Protokolls. Die Multicast-Rechenmaschine 310 empfängt Knoteninformation, Zielknotengruppeninformation, Erfordernisse und Einschränkungen. Dann berechnet die Multicast-Rechenmaschine 310 die optimalen Multicast-Pfade und gibt sie aus unter Verwendung der Netzverkehrs-Informationsdatenbank 120 in Übereinstimmung mit dem in 11 gezeigten Rechenverfahren.
Im Folgenden wird ein Beispiel, das die Performance des Rechenverfahrens dieser Ausführungsform zeigt, beschrieben.
23 zeigt ein Netz zum Evaluieren des Multicast-Kommunikationspfadrechensystems. Wie in der Figur gezeigt, wird durch Festlegen eines beliebigen Graphen, der 400 Knoten und eine Bandbreite für jede Verbindung einschließt, ein Multicast-Baum konstruiert, der 40 Zielknoten einschließt. 24 zeigt einen Performance-Evaluierungsgraphen der Multicast-Pfade und 25 zeigt einen Performance-Evaluierungsgraphen der Verzögerungsschwankung. Wie in dem Evaluierungsergebnis gezeigt, kann die Verzögerungsschwankung des gesamten Baums, obwohl die Übertragungskosten geringfügig in Übereinstimmung mit dem Verfahren der vorliegenden Erfindung verglichen mit dem KMB-Kommunikationsverfahren ansteigen, in Übereinstimmung mit dem Verfahren der vorliegenden Erfindung unterdrückt werden.
Wie oben erwähnt, wird durch Verwenden des Rechenverfahrens der vorliegenden Erfindung in Übereinstimmung mit den Dienstequalitäts- bzw. QoS-Anforderungen für jeden Multicast-Verkehr ein optimaler Multicast-Kommunikationspfad einrichtbar und die Bandbreite wird im gesamten Netz effizient verwendbar, so dass ein Multicast-Kommunikationsnetz mit hoher Performance einrichtbar wird.
Auf dieselbe Weise wie bei dem ersten Beispiel kann durch Installieren eines Programms der vorliegenden Erfindung in einem Computer, der als Multicast-Kommunikationspfad-Rechenvorrichtung arbeitet, der in 11 gezeigte Betriebsablauf realisiert werden. Zudem kann das Programm über ein Netz gesendet und empfangen werden.
Das Programm kann in einer Festplatte eines Computers oder in einem bewegbaren Aufzeichnungsmedium wie einer flexiblen Diskette und einer CD-ROM und Ähnlichem gespeichert werden. Das gespeicherte Programm kann in dem Computer installiert werden.
Zudem können die Multicast-Pfade in dem Netz auf dieselbe Weise eingerichtet werden wie bei dem ersten Beispiel.
Wie oben erwähnt, können in Übereinstimmung mit dem Rechenverfahren dieser Ausführungsform Multicast-Pfade eingerichtet werden, bei denen Verzögerungsvariation unterdrückt werden kann, während des Verringerns der Kosten des Gesamtnetzes. Demnach kann ein effizientes Multicast-Kommunikationsnetz mit hoher Performance konstruiert werden.
Die vorliegende Erfindung ist nicht auf die speziell offenbarte Ausführungsform beschränkt und Variationen und Modifikationen können vorgenommen werden, ohne vom Schutzbereich der vorliegenden Erfindung, wie sie beansprucht ist, abzuweichen.

Claims

Ein Multicast-Kommunikationspfad-Berechnungsverfahren zum Erhalten von Multicast-Pfaden von einem gegebenen Quellenknoten (V0) zu mehreren Zielknoten (V1–V4) in einem mehrere Knoten einschließenden Netz, wobei das Verfahren die Schritte umfasst: Empfangen (S1) oder Lesen (S11) eines Topologie und Verzögerung eines Netzes einschließenden Distanzgraphen, wobei eine Distanz einer Verzögerung entspricht; Einrichten (S13) eines ersten Distanz-Sub-Graphen, in dem der gegebene Quellenknoten in dem empfangenen Distanzgraphen gelöscht wird; Auswählen der mehreren Zielknoten aus dem ersten Distanz-Sub-Graphen, Erhalten (S14) eines zweiten Distanz-Sub-Graphen, in dem jeder Rand ein kürzester Pfad zwischen zwei der mehreren Zielknoten ist, und Einrichten (S15) eines ersten minimalen Spanning-Tree des zweiten Distanz-Sub-Graphen; Einrichten eines Sub-Graphen des ersten minimalen Spanning-Tree durch Einschließen von Zwischenknoten in jeden der Ränder des ersten minimalen Spanning-Tree, und Einrichten (315 eines zweiten minimalen Spanning-Tree des Sub-Graphen; Löschen unnötiger Ränder von dem zweiten minimalen Spanning-Tree, so dass ein den Zielknoten einschließender Baum eingerichtet ist; Annehmen, dass Knoten, die den Baum bilden, Kandidatenknoten eines Rendezvouspunktknotens sind, Erhalten für jeden der Kandidatenknoten eine Differenz zwischen der maximalen Distanz und der minimalen Distanz unter Distanzen zwischen dem Kandidatenknoten und je mehreren Zielknoten, und Auswählen des Kandidatenknotens, für den die Differenz am geringsten ist, als Rendezvouspunktknoten; und Erhalten (S20) des Multicast-Pfads durch Verbinden des Baums und des gegebenen Quellenknotens bei dem Rendezvouspunktknoten, und Ausgeben des Multicast-Pfades.
Multicast-Kommunikationspfadeinrichtverfahren, wobei eine Multicast-Kommunikationspfad-Berechnungsvorrichtung die Multicast-Pfade in Übereinstimmung mit Anspruch 1 berechnet, und eine Multicast-Kommunikationspfad-Einstellvorrichtung die berechneten Multicast-Pfade in dem Netz einrichtet, wobei die Multicast-Kommunikationspfad-Einstellvorrichtung eine Anfrage zum Berechnen der Multicast-Pfade zu der Multicast-Kommunikationspfad-Berechnungsvorrichtung sendet, und die Multicast-Kommunikationspfad-Berechnungsvorrichtung die Multicast-Pfade in Übereinstimmung mit der Anfrage berechnet, und wobei die Multicast-Kommunikationspfad-Berechnungsvorrichtung die Ausgangsergebnisse zu der Multicast-Kommunikationspfad-Einstellvorrichtung sendet, und die Multicast-Kommunikationspfad-Einstellvorrichtung die Multicast-Pfade in Übereinstimmung mit den Ausgangsergebnissen einrichtet.
Multicast-Kommunikationspfadeinstellverfahren nach Anspruch 2, wobei jeder der mehreren Knoten in dem Netz den Verkehrszustand des Netzes misst und die Messergebnisse zu der Multicast-Kommunikationspfad-Berechnungsvorrichtung sendet, und die Multicast-Kommunikationspfad-Berechnungsvorrichtung die Multicast-Pfade in Übereinstimmung mit den Messergebnissen berechnet.
Multicast-Kommunikationspfad-Berechnungsvorrichtung zum Erhalten von Multicast-Pfaden von einem gegebenen Quellenknoten (V0) zu mehreren Zielknoten (V1–V4) in einem mehrere Knoten einschließenden Netz, wobei die Vorrichtung umfasst: ein Teil (1) zum Empfangen oder Lesen eines Topologie- und Verzögerung des Netzes einschließenden Distanzgraphen, wobei eine Distanz einer Verzögerung entspricht; ein Teil zum Einrichten eines ersten Distanz-Sub-Graphen, in dem der gegebene Quellenknoten aus dem empfangenen Distanzgraphen gelöscht ist; ein Teil zum Auswählen der mehreren Zielknoten von dem ersten Distanz-Sub-Graphen, Erhalten eines zweiten Distanz-Sub-Graphen, in dem jeder Rand ein kürzester Pfad zwischen zwei der mehreren Zielknoten ist, und Einrichten eines ersten minimalen Spanning-Tree des zweiten Distanz-Sub-Graphen; ein Teil zum Einrichten eines Sub-Graphen des ersten minimalen Spanning-Tree durch Einschließen von Zwischenknoten in jeden der Ränder des ersten minimalen Spanning-Tree, und Einrichten eines zweiten minimalen Spanning-Tree des Sub-Graphen; ein Teil zum Löschen unnötiger Ränder von dem zweiten minimalen Spanning-Tree, so dass ein den Zielknoten einschließender Baum eingerichtet wird; ein Teil, um unter der Annahme, dass Knoten, die den Baum bilden, Kandidatenknoten eines Rendezvouspunktknotens sind, für jeden der Kandidatenknoten eine Differenz zwischen der Maximaldistanz und der Minimaldistanz oder den Distanzen zwischen dem Kandidatenknoten und jedem der mehreren Zielknoten zu erhalten und um den Kandidatenknoten, für den die Differenz am kleinsten ist, als den Rendezvouspunktknoten auszuwählen; und ein Teil, um die Multicast-Pfade durch Verbinden des Baums und des gegebenen Quellenknotens bei dem Rendezvouspunktknoten zu erhalten und die Multicast-Pfade umfassende Ergebnisse auszugeben.
Multicast-Kommunikationspfad-Berechnungsvorrichtung nach Anspruch 4, ferner umfassend: ein Teil, um die Topologieinformation und die Verzögerungsinformation des Netzes zu empfangen; und ein Teil, um die empfangene Information in einem Aufzeichnungsmedium zu speichern, wobei die Multicast-Kommunikationspfad-Berechnungsvorrichtung die Multicast-Pfade durch Lesen der empfangenen Information von dem Aufzeichnungsmedium berechnet.
Multicast-Kommunikationspfad-Berechnungsvorrichtung nach Anspruch 4, ferner ein Teil umfassend, um die Ausgangsergebnisse in einer Multicast-Pfadeinstellsteuernachricht einzuschließen und die Multicast-Pfadeinstellsteuernachricht über die Multicast-Pfade zu senden, die durch die Ausgangsergebnisse angegeben werden.
Multicast-Kommunikationspfad-Berechnungsvorrichtung nach Anspruch 4, ferner umfassend: ein Teil zum Empfangen einer Anfrage zum Berechnen der Multicast-Pfade von einer Multicast-Kommunikationspfad-Einstellvorrichtung; und ein Teil zum Senden der Ausgangsergebnisse zu der Multicast-Kommunikationspfad-Einstellvorrichtung.
Computerprogramm, um eine Multicast-Kommunikationspfad-Berechnungsvorrichtung zu veranlassen, die Multicast-Pfade von einem gegebenen Quellenknoten (V0) zu mehreren Zielknoten (V1–V4) in einem mehrere Knoten einschließenden Netz zu berechnen, wobei das Computerprogramm umfasst: Programmcode zum Empfangen oder Lesen des Distanzgraphen, der Topologie und Verzögerung des Netzes einschließt, wobei Distanz einer Verzögerung entspricht; Programmcode, um einen ersten Distanz-Sub-Graphen einzurichten, in dem der gegebene Quellenknoten von dem empfangenen Distanzgraphen gelöscht ist; Programmcode, um die mehreren Zielknoten von dem ersten Distanz-Sub-Graphen auszuwählen, einen zweiten Distanz-Sub-Graphen erhaltend, in dem jeder Rand ein kürzester Pfad zwischen zwei der mehreren Zielknoten ist, und Einrichten eines ersten minimalen Spanning-Tree des zweiten Distanz-Sub-Graphen; Programmcode, um einen Sub-Graphen des ersten minimalen Spanning-Tree einzurichten durch Einschließen von Zwischenknoten in jeden der Ränder des ersten minimalen Spanning-Tree, und Einrichten eines zweiten minimalen Spanning-Tree des Sub-Graphen; Programmcode, um unnötige Ränder von dem zweiten minimalen Spanning-Tree zu löschen, so dass ein Baum eingerichtet wird, der die Zielknoten einschließt; Programmcode, um unter der Annahme, dass Knoten, die den Baum bilden, Kandidatenknoten eines Rendezvouspunktknotens sind, eine Differenz zwischen der Maximaldistanz und der Minimaldistanz unter Distanzen zwischen dem Kandidatenknoten und jedem der mehreren Zielknoten für jeden der Kandidatenknoten zu erhalten, und den Kandidatenknoten, für den die Differenz am kleinsten ist, als dem Rendezvouspunktknoten auszuwählen; und Programmcode, um die Multicast-Pfade durch Verbinden des Baums und des gegebenen Quellenknotens bei dem Rendezvouspunktknoten zu erhalten, und die Multicast-Pfade auszugeben.
Computerlesbares Medium, das Programmcode speichert, um eine Multicast-Kommunikationspfad-Berechnungsvorrichtung zu veranlassen, Multicast-Pfade von einem gegebenen Quellenknoten (V0) zu mehreren Zielknoten (V1–V2) in einem mehrere Knoten einschließendem Netz zu berechnen, wobei das computerlesbare Medium ein Computerprogramm nach Anspruch 8 umfasst.