DE69228423T2

DE69228423T2 - Mehrfachsende-Leitweglenkung zwischen Bereichen

Info

Publication number: DE69228423T2
Application number: DE69228423T
Authority: DE
Inventors: Willibald Doeringer; Douglas Dykeman; Allan Kendrick Edwards; Diane Pozefsky; Soumitra Sarkar; Roger O. Turner
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-11-27
Filing date: 1992-11-27
Publication date: 1999-09-30
Anticipated expiration: 2012-11-28
Also published as: EP0598969A1; ES2129038T3; CA2105040C; CA2105040A1; JP2539167B2; TW265497B; BR9304798A; JPH06224912A; KR960014987B1; CN1091570A; US5361256A; KR940012961A; DE69228423D1; ATE176744T1; CN1052358C; EP0598969B1

Description

Mehrfachsende-Leitweglenkung zwischen Bereichen

Gebiet der Erfindung

In Rechnernetzwerken werden, um Information zu verteilen, Leitwegprotokolle benutzt, die es gestatten zu bestimmen, wie ein Datenpaket oder eine Nachricht von einem beliebigen Punkt in diesem Netzwerk an seinen beabsichtigten Bestimmungsort geschickt wird. In vielen Fällen wird ein Datenpaket oder eine Nachricht von einer einzigen Quelle, dem Absender, an einen einzigen Empfänger abgesendet; dies wird üblicherweise als Einfachsenden bezeichnet. Heutige Rechnernetzwerke haben durchdachte Leitwegprotokolle, um sichere, schnelle und zuverlässige Ausführung solcher Einfachsende-Übertragungen zu unterstützen oder abzusichern. Falls ein Datenpaket oder eine Nachricht jedoch von einer einzigen Sendequelle an eine Gruppe von Empfangsstationen innerhalb eines Netzwerkes gesendet werden muß - üblicherweise als Mehrfachsenden bezeichnet - ist es sehr ineffizient, falls überhaupt möglich, sich zu diesem Zwecke auf traditionelle Einfachsende-Leitwegprotokolle zu verlassen. Dafür bietet die vorliegende Erfindung eine Lösung; sie bezieht sich auf Mehrfachsenden, insbesondere auf ein Verfahren des Mehrfachsendens von Nachrichten in einem komplexen Netzwerk, das ursprünglich nur für Einfachsende-Übertragung ausgerüstet ist.

Grundlagen und Aufgaben der Erfindung

Leitwegprotokolle nach Stand der Technik, wie etwa das Leitwegprotokoll zwischen Bereichen (IDRP) werden beispielsweise in ISO "Informationsverarbeitungssysteme - Telekommunikation und Informationsaustausch zwischen Systemen - Protokoll für den Austausch von Leitweginformation zwischen Bereichen zwischen Vermittlungssystemen zum Unterstützen des Sendens von PDUs nach ISO 8473" beschrieben. ISO/DIS CD 10747, 1997., das von der International Standards Organization, ISO, herausgegeben wurdet bietet einen Rahmen zum Weiterleiten von Einfachsende-Datenpaketen, d. h. Datenpakete werden an einen einzelnen Bestimmungsort geschickt.
Oftmals besteht eine Hauptforderung von Rechnernetzwerken im allgemeinen und von Mehrfachprotokoll-Transportnetzwerken von Anwendern (im folgenden mit MPTN abgekürzt) im besonderen darin, das Mehrfachsenden von Datenpaketen zuzulassen, die von einer bestimmten Quelle an eine Gruppe von Bestimmungsorten gesendet werden. Allgemein gesagt, bietet diese Erfindung eine Lösung für diese Forderung, indem sie ein Verfahren des und ein System zum Mehrfachsenden unter Verwendung einer Gruppe von neuen Protokollen in Kombination mit vorhandenen Leitwegprotokollen (z. B. IDRP) lehrt, um Mehrfachsenden in einem Rechnernetzwerk von beliebiger Größe und Topologie zu unterstützen. Sie hat Merkmale, die sie für eine solche Umgebung geeignet sein lassen, die in keinerlei vorhandenen Mehrfachsendeprotokollen vorhanden ist.
Im folgenden werden Grundlagen und Aufgaben der Erfindung ausführlicher beschrieben. Es sollte sich jedoch verstehen, daß die Erfindung in keiner Weise darauf beschränkt ist, innerhalb der Art von Netzwerk benutzt zu werden, wie sie hier nachstehend beschrieben ist. Weitere Beispiele sind in anderen Teilen der Beschreibung zu finden.
Eine weit verbreitete Protokollgruppe, wie etwa Mehrfachprotokoll-Transportnetzwerk von IBM, bietet ungeachtet des Netzwerkes, dem sie angeschlossen sind, Verknüpfungsmöglichkeiten für Rechneranwendungen. Damit können, wie in Figur. 1 veranschaulicht, zwei an unterschiedliche Teilnetzwerke im gleichen MPTN 11 angeschlossene Anwendungen kommunizieren. Wie in Fig. 1 dargestellt, kann eine Mandantenanwendung 12, die an einem ersten Teilnetzwerk 13 angeschlossen ist, z. B. einem NetBIOS-Teilnetzwerk (ein Handelsname des Einreichers), mit einer kompatiblen Serveranwendung 14 kommunizieren, die an einem zweiten Teilnetzwerk 15 angeschlossen ist, z. B. einer Systemnetzwerkarchitektur-Teilnetzwerk (SNA, was gleichfalls ein Handelsname des Einreichers ist). MPTN-Gateways 16 und 17 sind erforderlich, um die drei verschiedenen Teilnetzwerke 13, 15 und 18 zu einem einzigen logischen Netzwerk (dem MPTN) zu verbinden; die Gateways sind über das dritte Teilnetzwerk 18 verbunden, z. B. ein. Übertragungssteuerprogramm-/Internetprotokoll-Netzwerk (TCP/IP).
Eine Schlüsselfunktion der MPTN-Gateways 16 und 17 besteht darin, Nachrichten von ihrer Quelle (z. B. der Mandantenanwendung 12) zu einem Bestimmungsort (z. B. der Serveranwendung 14) weiterzuleiten. Dieses Problem ist aus folgenden Gründen schwierig.
- Es muß ein Weg zwischen der Quelle und dem Bestimmungsort gefunden werden, der den Anforderungen der Anwendung genügt (z. B. Sicherheit, Geschwindigkeit, Zuverlässigkeit).
- Das MPTN kann sehr groß sein, viele Teilnetzwerke und Gateways haben. Dies kann zu einer sehr komplizierten Netzwerktopologie führen, und damit müssen an den Gateways komplizierte Leitwegentscheidungen vorgenommen werden.
- Aufgrund von Verbindungs- und Knotenfehlern oder durch die Installation neuer Ausrüstung verändern sich die Topologie und damit die richtigen Leitwegentscheidungen in Echtzeit.
Um diese Probleme zu lösen, benutzen MPTN-Gateways das vorstehend erwähnte Leitwegprotokoll, das von der International Standards Organization genormt wurde und als Leitwegprotokoll zwischen Bereichen (IDRP) bezeichnet wird. IDRP definiert die Formate und Verfahrensweisen eines Protokolls zur Leitweglenkung von einer einzelnen Quelle an einen einzelnen Bestimmungsort in einem Netzwerk beliebiger Topologie und Größe. IDRP unterstützt jedoch Mehrfachlenden nicht, das heißt, die Übermittlung einer Nachricht von einer einzelnen Quelle an mehrere Bestimmungsorte. Andererseits ist aus einer Reihe von Gründen Mehrfachsenden in MPTN wichtig. Zum ersten unterstützten einige Netzwerke das Mehrfachsenden und daher ziehen Anwendungen, die in solchen Teilnetzwerken laufen, aus diesem Merkmal Nutzen. Um Verknüpfungsmöglichkeit mit solchen Anwendungen zu bieten, muß Mehrfachsenden in der zwischen den Netzwerken vorhandenen Umgebung unterstützt werden. Zum zweiten beruhen einige MPTN-Steuerprotokolle auf Mehrfachsenden. Beispielsweise erfordern es Protokolle zum Lokalisieren eines Betriebsmittels, daß eine Suche nach diesem Betriebsmittel an alle Gateways verteilt wird, die an Teilnetzwerke angeschlossen sind, in denen es sich befinden könnte.
Einige Beispiele dieser Probleme, die mit dem Mehrfachsenden in einer Umgebung zwischen Netzwerken verbunden sind, werden nun unter Bezugnahme auf das in Fig. 2 erläuterte einfache MPTN beschrieben. In diesem Beispiel wird ein Mehrfachsenden durch eine Anwendung in Teilnetzwerk W (21) ausgelöst, das an Bestimmungsorte in Teilnetzwerken X (22) und Z (24) übermittelt werden soll. In Teilnetzwerk Y (23) gibt es keine Bestimmungsorte. Die mit einem derartigen Vorgang verbundenen Probleme enthalten:
- Es ist nicht annehmbar, getrennte (Einfachsende-) Nachrichten an alle Bestimmungsorte zu erzeugen, da dies für die Betriebsmittel des MPTN eine unnötige Belastung schaffen würde. Beispielsweise würde es in Fig. 2 eine derartige Einfachsendestrategie erfordern, daß für jeden Bestimmungsort eine Nachricht auf der Verbindung zwischen Gateway A (25) und Gateway B (26) anstatt eben einer Mehrfachsende-Nachricht zu senden ist.
- Es ist nicht annehmbar, die Nachricht an jedes Teilnetzwerk im MPTN mehrfach zu senden. Im Beispiel dürfte Teilnetzwerk Y (23) keine Mehrfachsendung empfangen, die nur für Knoten in den Teilnetzwerken X (22) und Z (24) bestimmt ist. Obgleich dies durch das Beispiel nicht erläutert wird, ist klar, daß in einem großen MPTN mit vielen Teilnetzwerken und vielen unterschiedlichen Mehrfachsendegruppen eine derartige Überflutungsstrategie nicht akzeptabel sein würde.
- Ein gegebenes Datenpaket sollte nur einmal an ein gegebenes Teilnetzwerk mehrfach gesendet werden. Im Beispielnetzwerk gibt es zwei Pfade von Gateway B (26) zu Teilnetzwerk X (22), und zwar über Gateway D (28) und direkt über Gateway C (29). Teilnetzwerk X (22) sollte jedoch nur eine einzige Kopie der Mehrfachsendung aus der Quelle in Teilnetzwerk W (21) erhalten. Diese Regel muß ungeachtet der Anzahl der an Teilnetzwerk X (22) angeschlossenen Gateways oder der Anzahl der Pfade zwischen einer Quelle und einem bestimmten Bestimmungs-Teilnetzwerk eingehalten werden. Dies ist wichtig, um die Belastung zu minimieren, die aufgrund von Mehrfachsendeverkehr auf den Teilnetzwerken liegt, und das Duplizieren von Datenpaketlieferung zu vermeiden, was für einige Anwendungen Fehlerbeseitigungsprotokolle notwendig machen würde.

Stand der Technik

Zum besseren Verständnis der Erfindung werden Lösungen zum Mehrfachsenden von. Nachrichten in anderen Umgebungen und vorhandene Lösungen in Umgebungen zwischen Netzwerken betrachtet.

Lokale Datennetze (LANs)

LANs sind eine sehr spezielle Art von Teilnetzwerken, da sie natürlicherweise eine Rundsendefunktion unterstützen, so daß eine einzelne Nachricht leicht an alle Knoten geschickt wird. Die am meisten übliche Mehrfachsendestrategie für LAN besteht daher darin, Nachrichten rundzusenden und jeden angeschlossenen Rechner diejenigen Nachrichten ausfiltern zu lassen, die für lokale Benutzer nicht erforderlich sind. Ein Beispiel wird von S. E. Deering und D. R. Cheriton in "Multicast Routing in Datagram Internetworks and Extended LANs" in ACM Transactions on Computer Systems, Bd. 8, Nr. 2, S. 85 bis 110, ACM, Mai 1990r gegeben. Eine derartige Strategie erscheint jedoch, wie vorstehend erklärt, für ein großes Internetzwerk ungeeignet. Es sollte auch erwähnt werden, daß im wesentlichen die gleichen Beobachtungen für Datennetze im städtischen Bereich (MANs) gelten.
Wenn LAN-Segmente durch Brücken miteinander verbunden sind, können diese selektiv LAN-Nachrichten ausfiltern, so daß sie nur auf Segmenten rundgesendet werden, in denen mindestens ein Knoten ein Bestimmungsort für eine Mehrfachsendung ist. Diese Protokolle arbeiten wie folgt (siehe vorstehend zitierte Deering und Cheriton hinsichtlich Veränderungen an diesem grundlegenden Algorithmus):
1. Gruppenmitglieder senden ihr Vorhandensein auf dem LAN rund, an dem sie angeschlossen sind. Diese Rundsendungen werden durch Brücken auf alle LAN-Segmente geschickt, so daß alle Brücken den Standort der Gruppenmitglieder lernen können.
2. Wenn ein Mehrfachsende-Datenpaket für eine Gruppe empfangen wird, übermitteln nur Brücken auf dem Pfad zu einem oder mehreren Mitgliedern dieser Gruppe das Paket. Damit wird das Überfluten aller LAN-Segmente bei jeder Mehrfachsendung vermieden.
Eine Einschränkung derartigen Mehrfachsendens auf LAN-Basis besteht darin, daß in der Topologie keine Schleifen zulässig sind, d. h. es kann nicht mehrere Pfade über Brücken zwischen zwei beliebigen LAN-Stationen geben. Dies ist erforderlich, weil andernfalls das einfache Übermittlungsschema, wie es von den LAN-Brücken benutzt wird, dazu führte, daß innerhalb einer derartigen Schleife Pakete ewig rundgesendet würden. Ein derartiges Schema ist zum Mehrfachsenden in einem großen Internetzwerk ungeeignet, da der gesamte Verkehr dazu gezwungen würde, durch das Internetzwerk den gleichen Weg zu nehmen, wodurch auf den betroffenen Verbindungen eine unannehmbare Belastung entstehen würde. Es gibt Algorithmen, die Schleifen in der LAN- Topologie zulassen, aber es wird eine einzelne Gruppe von Brücken ausgewählt, die einen schleifenfreien Schlüsselbaum zum Verschicken von Mehrfachsendungen bildet. Damit wird der gesamte Mehrfachsendeverkehr wiederum gezwungen, einem einzigen Pfad entlang der Verzweigungen des Schlüsselbaumes zu folgen.

Mehrfachsenden im Internetzwerk

Es gibt Mehrfachsende-Algorithmen, die mit Leitwegprotokollen arbeiten, die in Internetprotokoll-(IP-)Netzwerken verwendet werden. IP-Netzwerke bieten Leitweglenkung und Vermittlungssteuerung von Datenpaketen (als Datagramme bezeichnet) über ein Netzwerk mit allgemeiner Topologie, das aus LANs, Punkt-zu- Punkt-Verbindungen und sogar Teilnetzwerken besteht, wie etwa X.25. Ein IP-Internetzwerk besteht aus einer Ansammlung von derartigen Teilnetzwerken, die durch IP-Nachrichtenführer verbunden sind.
Die folgenden Leitwegprotokolle, die in IP-Netzwerken benutze werden, beruhen alle auf einem Entfernungsvektor-Leitwegschema (manchmal auch als Pfadvektor bezeichnet), das dem gleicht, das in IDRP benutzt wird:
- Leitweginformationsprotokoll (RIP), wie von C. L. Hedrik in "Routing Information Protocol", RFC 1058 (Request for Comments), NIC (Network Information Center), Juni 1988 beschrieben.
- Hello-Leitwegprotokoll, beschrieben von D. L. Mills in "Experimetal Multiple Path Routing Algorithm", RFC 981, NIC, März 1986.
- Grenz-Gateway-Protokoll (BGP), beschrieben von K. Lougheed und Y. Rekhter in "Border Gateway Protocol (BGP), RFC 1163, NIC, Juni 1990.
Protokoll zwischen Gateways (GGP), wie von R. M. Hinden und A. Sheltzer in "DARPA Internet Gateway", RFC 823, NIC, September 1982, beschrieben.
Wie später offensichtlich wird, bietet die vorliegende Erfindung eine Lösung, die für alle Netzwerke anwendbar ist, die auf den vorstehenden (oder gleichwertigen) Leitwegprotokollen beruhen.
IP-Mehrfachsendealgorithmen sind in erster Linie für die Anwendung mit dem Leitweginformationsprotokoll entwickelt worden, wie es von dem vorstehend zitierten C. L. Hedrik beschrieben wurde, sind aber ebenso mit den anderer: Entfernungsvektor- Leitwegalgorithmen verwendbar. IP-Mehrfachsendealgorithmen (siehe z. B. vorstehend zitierte S. E. Deering und D. R. Cheriton; S. E. Deering "Host Extensions for IP Multicasting", RFC 1112, NIC, August 1988; L. Hughes und P. Thomlinson "A Multicast Internetwork Routing Algorithm", Proceedings of the IFIP WG 6.4 Conference an High Speed Networking, 18. bis 22. März 1991, Berlin, S. 183 bis 200; D. Waitzman, C. Partridge und S. E. Deering "Distance Vector Multicast Protocol", RFC 1075, NIC November 1988) sind alle Varianten des von Y. K. Dalal und R. M. Metcalfe in "Reverse Path Forwarding von Broadcast Packets", Communication of the ACM, Bd. 21, Nr. 12, S. 1040 bis 1048, ACM, Dezember 1978, beschriebenen Rückwärtspfad-Rundsendealgorithmus. Dieser Algorithmus gleicht dem LAN-Mehrfachsendealgorithmus darin, daß ein Schlüsselbaum benutzt wird, um die Mehrfachsende-Datenpakete zu verteilen, er enthält jedoch zusätzliche Merkmale, um einige der Probleme zu lösen, die mit LAN- Mehrfachsendung verbunden sind. Kurz gesagt, der Algorithmus arbeitet wie folgt (für eine ausführlichere Beschreibung siehe die vorstehend zitierten S. E. Deering und D. R. Cheriton):
1. Mehrfachsende-Datenpakete werden am Anfang an alle Teilnetzwerke in dem Internetzwerk rundgesendet. Datenpakete werden auf einem kostenminimierten Schlüsselbaum rundgesendet. Wenn ein Nachrichtenführer ein Mehrfachsende-Datenpaket aus irgendeiner Quelle "S" erhält, weiß er, daß er sich am Schlüsselbaum für Mehrfachsendungen mit Ursprung bei S befindet, falls seine Leitwegtabellen anzeigen, daß er Knoten 5 mit niedrigeren Kosten als alle anderen an ein gegebenes Teilnetzwerk angeschlossenen Nachrichtenführer (diese Information ist in allen normalen IP- Leitwegtabellen verfügbar) erreichen kann. Wenn dies der Fall ist, schickt dieser Nachrichtenführer die Mehrfachsende-Datenpakete an das in Frage kommende Teilnetzwerk. Es wurde von den vorstehend zitierten ST. Deering und D. R. Cheriton gezeigt, daß dieser Algorithmus dazu führt, daß das Mehrfachsende-Datenpaket mit minimalen Kosten an jedes Teilnetzwerk in dem Internetzwerk verteilt wird.
Eine offensichtliche Verbesserung dieses Schemas im Vergleich mit den LAN-Mehrfachsendeschemata besteht darin, daß hier, obwohl für eine gegebene Quelle der Mehrfachsende-Schlüsselbaum festliegt, er nicht für alle Quellen der gleiche ist. Damit wird der Mehrfachsendeverkehr im Netzwerk auf viele verschiedene Pfade verteilt.
2. Um das Rundsenden vom Mehrfachsende-Datenpaketen an Teilnetzwerke zu vermeiden, die keine Mitglieder in der vorgegebenen Gruppe haben, wird ein Schema benutzt, in dem Nachrichtenführer, die eine Mehrfachsendung für eine bestimmte Gruppe empfangen, die nicht auf einem Zweig des Mehrfachsendebaumes liegt, der zu beliebigen Mitgliedern dieser Gruppe führt, die Mehrfachsendung ablegen (es gibt offensichtlich keinen Bedarf, sie zu übermitteln) und an den Vorgänger im Mehrfachsendebaum berichten, daß dieser Zweig des Baumes abgeschnitten werden kann. Dieser Vorgang beginnt mit Nachrichtenführern, die an "Laub-Teilnetzwerke" angeschlossen sind (Teilnetzwerke, die das Ende ihres jeweiligen Zweiges am Baum darstellen), und geht seinen Weg nach oben so weit wie möglich den Zweig entlang, um die Verteilung von Mehrfachsendeverkehr darauf zu beschränken, wo er erforderlich ist.
Die IP-Mehrfachsendeschemata haben die folgenden Nachteile:
- Anfänglich müssen Mehrfachsendungen von einer gegebenen Quelle an eine gegebene Gruppe im gesamten Internetzwerk rundgesendet werden, bis der Mehrfachsendebaum für dieses Paar von Quelle und Bestimmungsort beschnitten worden ist.
- Das Schema erfordert es, daß Information, die zum Beschneiden der Mehrfachsendebäume benutzt worden ist, nach einiger Zeit abgelegt wird, so daß neue Mitglieder, die mit dem Netzwerk auf einem vorher abgeschnittenen Baum zweig verbunden werden, schließlich mit dem Empfangen von Mehrfachsendungen beginnen. Daher werden Mehrfachsendebäume kontinuierlich neu aufgebaut und neu beschnitten, was an den Netzwerkverbindungen und Verarbeitungsknoten beträchtliche Kosten verursacht.
- Mehrfachsendebäume sind für jedes Paar Quelle-Mehrfachsendegruppe vorhanden. Das heißt, für jede unterschiedliche Quelle, die an eine gegebene Gruppe mehrfach sendet, ist ein getrennter logischer Mehrfachsendebaum vorhanden. Damit müßten Leitwegknoten eine extrem große Datenbank für beschnittene Mehrfachsendebäume verwalten.
Aus diesen Gründen erscheinen derartige Protokolle und Algorithmen zur Benutzung im MPTN und ähnlichen Architekturen ungeeignet. Ein brauchbarer Algorithmus sollte in der Lage sein, die Leitwegfähigkeiten von Gateways zu benutzen, die keine Mehrfachsende-Intelligenz haben.
Ausführlicher werden die folgenden Ziele oder Aufgaben der Erfindung als Anforderungen zur Bereitstellung von Mehrfachsendedienst gekennzeichnet:
1. Mehrfachsende-Datenpakete dürfen nicht an alle Teilnetzwerke rundgesendet werden, und tatsächlich sollten sie darauf beschränkt werden, daß sie nur an Teilnetzwerke geschickt werden, die ein Mitglied der Mehrfachsendegruppe enthalten.
2. Jedes Mehrfachsende-Datenpaket muß genau einmal an jedes Bestimmungs-Teilnetzwerk geliefert werden (d. h. es dürfen keine duplizierten Mehrfachsende-Datenpakete erzeugt werden).
3. Die Protokolle sollten keinerlei zentralisierte Elemente erfordern. Sie sollten vollständig verteilt sein.
4. Die Protokolle sollten keine Berechnung eines Schlüsselbaumes aus einer zentralisierten Datenbank erfordern.
5. Leitwegentscheidungen für Mehrfachsende-Datenpakete müssen flexibel sein. Verteilung von allen Mehrfachsendungen über zum Beispiel einen festen Schlüsselbaum ist nicht annehmbar.
6. Die Anzahl von verteilten Datenpaketen muß minimiert werden. Insbesondere ist es nicht annehmbar, für jeden Bestimmungsort ein getrenntes Einfachsende-Datenpaket zu erzeugen.
7. Die Kosten der Verteilung von Mehrfachsende-Datenpaketen müssen minimiert werden. Damit muß von der Mehrfachsendequelle zu jedem Bestimmungsort ein guter Pfad genommen werden.

Zusammenfassung der Erfindung

Kurz gesagt, die vorliegende erreichte Erfindung die vorstehenden Aufgaben durch ein Verfahren und ein System zum Mehrfachsenden einer Nachricht von einer Sendestation an eine Vielzahl von Empfangsstationen innerhalb eines konventionellen Einfachsende-Nachrichtenübertragungsnetzwerkes unter Verwendung vorhandener Protokolle dadurch, daß zumindest in bestimmten Knoten innerhalb des Netzwerkes Tabellen von Teilnetzwerken mit Mehrfachsende-Empfangsstationen oder Tabellen von Mehrfachsende- Empfangsstationen verwaltet werden und daß geeignete Leitweginformation im Kennsatz von Mehrfachsende-Nachrichten enthalten ist, wie es in den Ansprüchen weiter definiert wird.
Bei dieser Erfindung wird eine Lösung vorgestellt die, wenn sie in Kombination mit Leitwegprotokollen mit Entfernungsvektor benutzt wird, wie etwa dem Standard-Leitwegprotokoll OSI IDRP, beschrieben in ISO "Information Technology - Telecommunications and Information Exchange between Systems - Intermediate System to Intermediate System Intra-Domain Routing Protocol for Use in Conjunction with the Protocol for Providing the Connection", ISO/DIS 10589, 1990, oder beliebigem anderen ähnlichen Protokoll, wie etwa solche, die in IP-Netzwerken verwendet werden, auf die vorstehend Bezug genommen wurde, Mehrfachsenden in großen Internetzwerken unterstützt. Diese Lösung ist ebenfalls einsetzbar mit Leitwegprotokollen mit Verbindungsstatus, wie etwa OSPF, das für IP-Netzwerke entwickelt wurde (beschrieben von J. Moy in "OSPF Version 2", RFC 1247, NIC, Juli 1991) und dem OSI IS-IS Protokoll (beschrieben in ISO/DIS 10589, vorstehend zitiert), und ist damit auf einen großen Bereich von Internetzwerkumgebungen anwendbar. Innerhalb der Erfindung werden drei neue Arten Von Protokollen vorgestellt:
1. zur Verteilung von Netzwerkinformation auf der Basis von Netzwerktopologie und dem Standort der Mitglieder der Mehrfachsendegruppe und zur Erzeugung von Leitwegtabellen, die diese Information benutzen;
2. zum effizienten Senden von Mehrfachsende-Datenpaketen an alle Mitglieder einer Mehrfachsendegruppe, denen die Leitweginformation vom ersten Schritt übermittelt wurde; und
3. um die Mehrfachsendeprotokolle mit der Fähigkeit auszustatten, in einer MPTN-Umgebung benutzt zu werden.
Einzelheiten und Beispiele der Erfindung werden im folgenden in Verbindung mit den Zeichnungen beschrieben.

Die Zeichnungen

Fig. 1 ist ein Mehrfachprotokoll-Transportnetzwerk (MPTN), das aus drei Teilnetzwerken besteht (was schon vorstehend beim Stand der Technik erläutert wurde);
Fig. 2 ist ein Beispiel für ein weiteres MPTN (ebenso schon vorstehend erläutert);
Fig. 3 ist ein Beispiel für die Information, die von Gateways aus angeschlossenen Teilnetzwerken gelernt worden ist;
Fig. 4 ist eine Einzelheit in einem Teilnetzwerk, nämlich alle Knoten mit einen gemeinsamen Adreßvorsatzcode in einem derartigen Teilnetzwerk;
Fig. 2 und 3 zeigen im wesentlichen die gleiche Anordnung, die Bezugszahlen sind so gewählt, daß die letzte Ziffer jeder Zahl in jeder Figur das gleiche Teil kennzeichnet, d. h. "21" in Fig. 2 ist das gleiche Teil wie "31" in Fig. 3;
Fig. 5 zeigt verschiedene Knoten mit einem gegebenen Adreßvorsatzcode in unterschiedlichen Teilnetzwerken;
Fig. 6 ist die sogenannte Unterstützung der Teilnetz-ID des MPTN.

Ausführliche Beschreibung

Der folgende Abschnitt ist in vier Teile aufgeteilt. Der erste Teil, mit "Leitweginformation" betitelt, beschreibt die Leitweginformation, die verteilt wird, und die Tabellen, die für die Leitweglenkung von Mehrfachsende-Datenpaketen erzeugt werden. Der zweite Teil, mit "Übermitteln von Mehrfachsende-Datenpaketen " betitelt, beschreibt die Verfahrensweise beim Benutzen der erzeugten Tabellen zur Leitweglenkung von Mehrfachsende- Datenpaketen. Dann wird im dritten Teil, der mit "Mehrfachsenden mit verminderter Leitweginformation" betitelt ist, eine Beschreibung gegeben, wie die Menge an Leitweginformation vermindert werden kann, die für die Mehrfachsendeprotokolle erforderlich ist. Schließlich wird in Teil vier, mit "MPTN-Benutzung des Mehrfachsendens" betitelt, ein Beispiel gegeben, wie MPTN die in dieser Erfindung beschriebenen Protokolle benutzt.

Leitweginformation

Es wird eine kurze Beschreibung des Leitwegprotokolls zwischen Bereichen (IDRP) bereitgestellt, so daß die Erfindung besser zu verstehen ist. Weitere Einzelheiten sind in ISO/DIS 10589 zu finden, auf das vorstehend Bezug genommen wurde.
IDRP verteilt Leitweginformation zwischen Gateways in sogenannten Aktualisierungs-PDUs, d. h. Aktualisierungs-Protokolldateneinheiten. Aktualisierungs-PDUs enthalten die folgenden Felder, die für die Erfindung von Bedeutung sind.
1. Erreichbarkeitsinformation: Dieses Feld gibt die Betriebsmittel vor, die entlang des in dieser Aktualisierungs-PDU vorgegebenen Pfades erreicht werden können. Dies kann die Adresse eines speziellen Endsystems sein, oder es kann der Vorsatzcode sein, der den durch eine Gruppe von Endsystemen benutzten Adressen gemeinsam ist. Alle Systeme, deren Adresse einen gegebenen Vorsatzcode enthält, befinden sich im gleichen Teilnetzwerk, und daher kennzeichnet dieser Vorsatzcode dieses Teilnetzwerk eindeutig. In der Erreichbarkeitsinformation ist ein Typfeld definiert, das anzeigt, daß die Erreichbatkeitsinformation ein Adreßvorsatzcode (Typ = 0) ist. Damit könnten in Aktualisierungs- PDUs unterschiedliche Arten von Erreichbarkeitsinformation verteilt werden, indem ein neuer Typcode definiert wird.
2. Dienstqualität: Dies gibt Eigenschaften vor wie Kosten, Verzögerung und Sicherheitsfolgen für die Benutzung der Leitweginformation in dieser Aktualisierungs-PDU.
3. Pfad: Die Leitweginformation, die vorgibt, wie die durch den/die Vorsatzcode/Vorsatzcodes in der Erreichbarkeitsinformation gekennzeichneten Endsysteme zu erreichen sind.
Auf empfangenen Aktualisierungs-PDUs beruhend, bauen Gateways Leitwegtabellen auf, die in IDRP als Sendeinformationsbanken (FIBs) bezeichnet werden. Für jeden Bestimmungsort (ein Bestimmungsort wird durch einen in einer Aktualisierungs-PDU empfangenen Vorsatzcode gekennzeichnet und kann damit ein einzelner Knoten oder eine Gruppe von Knoten sein), wird das nächste Gateway auf dem Pfad zu diesem Bestimmungsort gespeichert (dies wird aus dem Pfadfeld der Aktualisierungs-PDU ermittelt). Genau ein Pfad für jedem Vorsatzcode wird für jede eindeutige Gruppe von Eigenschaften von Dienstparametern gespeichert. Dieser Pfad ist derjenige, der die vorgegebene Diensteigenschaft am besten bereitstellen kann.
In der Erfindung wird eine neue Art von. Erreichbarkeitsinformation definiert, die als Gruppenkennzeichner (groupid) bezeichnet wird. Ein Gruppenkennzeichner wird benutzt, um eine Gruppe von Endsystemen zu adressieren, die eine bestimmte Menge von Mehrfachsendungen empfangen soll. Der Gruppen kennzeichner, der aus dem normalen Adreßraum des Teilnetzwerkes ausgewählt wird, ist daher als Adresse des Bestimmungsortes eines Mehrfachsende- Datenpaketes so enthalten, daß die richtige Gruppe von Endsystemen gekennzeichnet wird. Die von einem bestimmten Gruppenkennzeichner adressierten Endsysteme befinden sich nicht notwendigerweise in einem gemeinsamen Teilnetzwerk. Das Auswählen von Gruppenkennzeichnern aus dem Standard-Adreßraum garantiert, daß sie sogar für Gateways gültige Erreichbarkeitsinformation darstellen, welche die nachstehend beschriebenen Mehrfachsende- Erweiterungen nicht realisieren.
Um Einfachsenden zwischen Domänen zu unterstützen, melden Teilnetzwerke den/die Adreßvorsatzcode/Adreßvorsatzcodes, die von ihren Knoten gemeinsam genutzt werden, an Gateways. Diese Vorsatzcodes werden dazu benutzt, die Aktualisierungs-PDUs zu erzeugen, wie vorstehend beschrieben. In der Erfindung melden Teilnetzwerke auch alle Gruppenkennzeichner, die in diesem Teilnetzwerk erreichbar sind.
Ein Beispiel ist in Fig. 3 veranschaulicht. In dieser Figur haben die Teilnetzwerke mit den Vorsatzcodes X (32) und Z (34) auch Endsysteme in Gruppe G. Sie melden daher sowohl den Vorsatzcode als auch den Gruppenkennzeichner an die lokalen Gateways C (39) und E (37). Teilnetzwerke W (31) und Y (33) haben keinerlei Gruppenkennzeichner zu melden, so melden sie nur ihre Vorsatzcodes. Es ist anzumerken, daß ein gegebenes Teilnetzwerk mehrere Gruppenkennzeichner und Vorsatzcodes (nicht dargestellt) melden kann.
IDRP-Aktualisierungs-PDUs sind wie folgt aufgebaut. Aktualisierungs-PDUs, die keine Gruppenkennzeichner enthalten, sind so aufgebaut, wie es im vorstehend erwähnten ISO/DIS CD 10747 vorgegeben ist. Aktualisierungs-PDUs, die dafür benutzt werden, Gruppenkennzeichnern Erreichbarkeit anzukündigen, müssen die folgende Information enthalten:
- einen Adreßvorsatzcode des Teilnetzwerkes und
- ein oder mehrere Gruppenkennzeichner für dieses Teilnetzwerk.
Die Erreichbarkeitsinformation in einer Aktualisierungs-PDU, die Gruppenkennzeichner enthält, besteht nur aus den Gruppenkennzeichnern und einem (eines der) Adreßvorsatzcode/Adreßvorsatzcodes, die für die Endsysteme in dem Teilnetzwerk eindeutig sind, das die Gruppenkennzeichner meldet, so daß alle Gateways in der Lage sein werden, eine Verknüpfung zwischen dem Teilnetzwerkvorsatzcode und den in diesem Teilnetzwerk erreichbaren Gruppenkennzeichnern aufzubauen.
Die auf diese Weise aufgebaute Aktualisierungs-PDU wird mit dem unveränderten Erreichbarkeitsinformationsfeld entsprechend den vorhandenen IDRP-Protokollen allen Gateways übermittelt. Es ist anzumerken, daß dieser Aufbau der Aktualisierungs-PDU durch den IDRP-Standard erlaubt ist und daß keine weiteren Veränderungen am Aufbau oder der Verteilung der Aktualisierungs-PDU erforderlich sind.
Im in Fig. 3 gezeigten Beispiel würde Gateway C (39) eine Aktualisierungs-PDU mit der folgenden Erreichbarkeitsinformation erzeugen: Vorsatzcode = X, Gruppenkennzeichner = G. Gleicherweise würde Gateway E (37) eine Aktualisierungs-PDU mit Vorsatzcode = Z und Gruppenkennzeichner = G erzeugen. Diese beiden Aktualisierungs-PDUs würden entsprechend dem IDRP-Protokoll an alle anderen Gateways verteilt, damit sie alle die Verknüpfung zwischen Gruppe G und Teilnetzwerken X und Z lernen können.
Wenn sich Erreichbarkeitsinformation verändert (d. h. sich der Vorsatzcode ändert oder Gruppenkennzeichner hinzugefügt oder gelöscht werden), werden die Veränderungen den lokalen Gateways gemeldet, welche die normalen IDRP-Leitwegprotokolle dafür benutzen, alle MPTN-Gateways mit der neuen Information zu aktualisieren.
Der Aufbau von Aktualisierungs-PDUs, wie er vorstehend angegeben wurde, versetzt Gateways in die Lage, eine zusätzliche Leitwegtabelle aufzubauen, die als Mehrfachsende-Leitwegtabelle oder MURT bezeichnet wird. Die MURT enthält für jeden Gruppenkennzeichner die Liste von Vorsatzcodes für Teilnetzwerke, die Mitglieder dieser Gruppe enthalten, wie es aus Aktualisierungs- PDUs gelernt wurde, die Gruppenkennzeichner enthalten. Wie die MURT zur Leitweglenkung benutzt wird, ist im nächsten Abschnitt erklärt.
Im System von Fig. 3 würde nachfolgend auf die Verteilung der Aktualisierungs-PDUs, wie es vorstehend beschrieben ist, jedes Gateway für Gruppenkennzeichner G einen MURT-Eintrag haben, der X und Z als die Vorsatzcodes von Teilnetzwerken kennzeichnet, in denen sich Gruppenmitglieder befinden.
Die restlichen IDRP-Leitwegtabellen (z. B. die vorstehend beschriebene FIB) werden entsprechend den vorhandenen IDRP- Spezifikationen aufgebaut. Insbesondere die mit der gesamten Erreichbarkeitsinformation (einschließlich Gruppenkennzeichner) verbundene Pfadinformation wird in der FIB gespeichert.
Bis hierher ist in diesem Abschnitt die Verfahrensweise zum Aufbau einer MURT unter Verwendung des OSI IDRP-Leitwegprotokolls beschrieben worden. Diese gleiche Verfahrensweise kann mit jedem beliebigen Entfernungsvektor-Leitwegprotokoll benutzt werden, wie sie z. B. in den folgenden Quellen beschrieben sind: C. L. Hedrick, "Routing Information Protocol", RFC 1058, NIC, Juni 1988; die vorstehend zitierten R. M. Hinden und A. Sheltzer; die vorstehend zitierten K. Lougheed und Y Rekhter, der vorstehend zitierte D. L. Mills. In allen derartigen Protokollen werden Aktualisierungs-PDUs verteilt, um einer gegebenen Adresse oder einem gegebenen Adreßvorsatzcode Erreichbarkeit anzukündigen. Durch Verknüpfen von Gruppenkennzeichnern mit jedem Adreßvorsatzcode kann, wie vorstehend beschrieben, eine WIRT aufgebaut werden.
Eine MURT kann auch unter Verwendung von Leitwegprotokollen mit Verbindungsstatus aufgebaut werden, wie sie etwa in ISO/DIS 10589 von 1990 oder bei vorstehend zitiertem J. Moy beschrieben werden. In solchen Protokollen verteilt jedes Gateway Erreichbarkeitsinformation in PDUs mit Verbindungsstatus, die Information über den Status jeder mit diesem Gateway benachbarten Verbindung ebenso wie alle Adreßvorsatzcodes bereitstellt, die von diesem Gateway aus direkt erreichbar sind. Diese PDUs mit Verbindungsstatus werden ohne Modifizierung an alle anderen Gateways im System geschickt. Daher kann, indem auch eine Liste von Gruppenkennzeichnern in den PDUs mit Verbindungsstatus einbezogen wird, eine MURT aufgebaut werden, welche die Gruppe mit einer Liste von Adreßvorsatzcodes von Teilnetzwerken verknüpft, in denen sich Gruppenmitglieder befinden. Sowohl Entfernungsvektor- wie Verbindungsstatus-Leitwegprotokolle erzeugen eine FIB, die im wesentlichen der gleicht, die vom IDRP erzeugt wird. Aufgrund dessen ist der Mehrfachsende-Übermittlungsalgorithmus, der im nächsten Abschnitt beschrieben wird, auch auf diese Umgebungen anwendbar.

Mehrfachsende-Datenpaketübermittlung

Vom Grundsatz her ist, sobald die MURT entsprechend der Beschreibung im vorhergehenden Abschnitt aufgebaut worden ist, die Leitweglenkung von Mehrfachsende-Datenpaketen sehr einfach. Die MURT gestattet es, daß Teilnetzwerke, in denen sich Mitglieder der Mehrfachsendegruppe befinden, gekennzeichnet werden. Weiterhin kann die FIB des IDRP dafür benutzt werden, Datenpakete an jedes dieser Teilnetzwerke zu lenken. Eine Kopie jedes Mehrfachsende-Datenpaketes könnte einfach an jedes dieser Teilnetzwerke gelenkt werden. Aufgrund der in dem vorstehenden Abschnitt mit dem Titel Zusammenfassung der Erfindung vorgegebenen Anforderungen des MPTN hinsichtlich Einschränkungen bei der Anzahl der verteilten Datenpakete sind jedoch die in diesem Abschnitt angegebenen Verfahren und Algorithmen ein wesentlicher Bestandteil dieser Erfindung.
Die Erfindung definiert auch einen Algorithmus des Mehrfachsende-Schlüsselbaum-Algorithmus (MSTA) zur Leitweglenkung von Mehrfachsende-Datenpaketen in einem MPTN. Der MSTA ist auch in anderen Netzwerken verwendbar, die Leitweginformation bereit stellen, die ähnlich der ist, die im vorstehenden Abschnitt angegeben ist.
Um dem Leser beim Verständnis zu helfen, werden MSTA in einem Beispiel dargestellt, ehe die ausführlichen Algorithmen angegeben werden.
Die Topologie des in diesem Beispiel benutzten Netzwerkes ist in Fig. 3 veranschaulicht. Unter Verwendung der Protokolle des vorhergehenden Abschnittes werden an den jeweiligen MPTN-Gateways die folgenden Leitwegtabellen aufgebaut:

Bei Gateway A (35)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode W: Adressen mit diesem Vorsatzcode befinden sich in dem lokalen Teilnetzwerk (31)
X: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
Y: Gateway B
Z: Gateway B
G: Gateway B
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes) Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.

Bei Gateway B (36)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway A.
X: Gateway C
Y: Gateway D
Z: Gateway E
G: Gateway E
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes)
Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.

Bei Gateway C (39)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode X: Adressen mit diesem Vorsatzcode befinden sich im lokalen Teilnetzwerk (32)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
Y: Gateway D
Z: Gateway B
G: lokales Teilnetzwerk (32)
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes)
Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.

Bei Gateway D (38)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode Y: Adressen mit diesem Vorsatzcode befinden sich im lokalen Teilnetzwerk (33)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
X: Gateway C
Z: Gateway B
G: Gateway C
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes)
Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.

Bei Gateway E (37)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode Z: Adressen mit diesem Vorsatzcode befinden sich im lokalen Teilnetzwerk (34)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
X: Gateway B
Y: Gateway B
G: lokales Teilnetzwerk (34)
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes)
Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.
Der grundlegende Aufbau ist in Fig. 3 gezeigt. In diesem Beispiel ist G der Gruppenkennzeichner einer Mehrfachsendegruppe, die Mitglieder in Teilnetzwerken X (32) und Z (34) hat. Ein Quellenknoten in Teilnetzwerk W (31) schickt eine Mehrfachsendung an Gruppenkennzeichner G.
MPTN-Gateway A (35) empfängt von Teilnetzwerk W (31) ein mehrfach gesendetes Datenpaket, das an Gruppenkennzeichner G adres siert ist. Sein MURT-Eintrag zeigt an, daß die Mehrfachsendung an die Teilnetzwerke mit Vorsatzcodes X (32) und Z (34) erfolgen soll. Aus seiner FIB bestimmt Gateway A (35), daß die nächste Etappe sowohl für X als auch für Z Gateway B (36) ist. Es sendet daher ein MPTN-Mehrfachsende-Datenpaket mit den folgenden Feldern an Gateway B (36):
Bestimmungsort = G
Zielteilnetzwerke = X, Z
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket
Es ist anzumerken, daß das Zielteilnetzwerk-Feld alle eindeutigen Bestimmungs-Teilnetzwerke für diese Mehrfachsendung auf einem gegebenen Pfad vorgibt. Da beide Teilnetzwerke X (32) und Z (34) über Gateway B (36) erreicht werden, wird nur ein einziges Datenpaket von Gateway A (35) zu Gateway B (36) geschickt, um die Mehrfachsendung zu bewerkstelligen.
Gateway B (36) empfängt das vorstehend angegebene Mehrfachsende-Datenpaket. Da die Zielteilnetzwerke angegeben sind, muß es keinen Gebrauch von der MURT machen. Es ist anzumerken, daß dies bewirkt, daß nur Gateways eine WIRT verwalten müssen, die an mögliche Quellen von Mehrfachsendeverkehr angeschlossen sind. Alle anderen Gateways brauchen diese Tabelle nicht zu erzeugen. Gateway B benutzt seine FIB, um festzustellen, daß die nächste Etappe für Teilnetzwerk X Gateway C (39) und für Teilnetzwerk Z (34) Gateway E (37) ist. Es sendet daher ein MPTN- Mehrfachsende-Datenpaket mit den folgenden Feldern an Gateway C:
Bestimmungsort = G
Zielteilnetzwerke = X
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket.
Es ist anzumerken, daß das Feld des Zielteilnetzwerkes nur nie Teilnetzwerke auf diesem Pfad enthält. Teilnetzwerk Z (34) wird auf einem unterschiedlichen Pfad erreicht und ist daher in der Mehrfachsendung an Gateway C (39) nicht enthalten.
Gleichermaßen sendet Gateway B (36) ein MPTN-Mehrfachsende- Datenpaket mit den folgenden Feldern an Gateway E (37):
Bestimmungsort = G
Zielteilnetzwerke = Z
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket.
Gateway C (39) empfängt eine Mehrfachsendung, die für Teilnetzwerk X (32) bestimmt ist, an dem es angeschlossen ist. Es übernimmt daher die Mehrfachsendung des Datenpaketes an Gruppenkennzeichner G in Teilnetzwerk X. Gleichermaßen übernimmt. Gateway E (37) die Mehrfachsendung der Datenpakete an Teilnetzwerk Z (34) an alle Mitglieder des Gruppenkennzeichners G. Damit wird die Mehrfachsendung allen Mitgliedern des Gruppenkennzeichners G übermittelt. Die vorstehenden Algorithmen genügen allen MPTN-Anforderungen für eine effiziente Mehrfachsendung:
1. Das Datenpaket wurde nur in Teilnetzwerken mehrfach gesendet, die ein Mitglied einer Mehrfachsendegruppe enthalten (z. B. X und Z, aber nicht Y). Die MURT kennzeichnet die Bestimmungs-Teilnetzwerke.
2. Jedes Mehrfachsende-Datenpaket wurde genau einmal an jedes Teilnetzwerk übermittelt. Die Zielteilnetzwerk-Felder der MPTN-Mehrfachsendung werden benutzt, um sicherzustellen, daß jedes Teilnetzwerk genau eine Kopie der Mehrfachsendung empfängt.
3. Es gibt keine zentralisierten Elemente. Die Erzeugung der MURT und die Leitweglenkung der Mehrfachsende-Datenpakete ist vollständig verteilt.
4. Die Algorithmen erfordern keine Berechnung eines Schlüsselbaumes aus einer Topologiedatenbank.
5. Die Mehrfachsende-Leitweglenkung hat die gesamte Flexibilität der normalen MPTN-Leitweglenkung. Wie im Beispiel gezeigt, werden die normalen FIBs des IDRP benutzt, um Mehrfachsende-Datenpakete zu lenken. Dies schließt ein, daß für unterschiedliche Mehrfachsende-Datenpakete aufgrund von unterschiedlicher Qualität der Dienstanforderungen und/oder veränderlicher Netzwerkbedingungen (Topologie oder Belastung) unterschiedliche Leitwege benutzt werden können.
6. Die Anzahl der verteilten Datenpakete ist minimiert. Ein Mehrfachsende-Datenpaket für verschiedene Bestimmungsorte (z. B. X und Z) wird nur als getrenntes Datenpaket gesendet, wenn die besten Leitwege zu den unterschiedlichen Bestimmungsorten nicht die gleichen sind. Im Beispiel wurde nur ein einziges Datenpaket von Gateway A zu Gateway B geschickt, aber Gateway B sandte einzelne Datenpakete an Gateways C und E.
7. Die Mehrfachsende-Datenpakete werden entsprechend der FIB des IDRP auf dem besten Leitweg an jeden Bestimmungsort gesendet. Ein Einfachsende-Datenpaket an einen der gegebenen Bestimmungsorte würde dem gleich Pfad wie das Mehrfachsende-Datenpaket zu diesem Bestimmungsort folgen.
Es ist ebenfalls wichtig, daß nur ein einziger MURT-Eintrag pro Mehrfachsende-Gruppe erzeugt wird. Die Mehrfachsende-Algorithmen für das Internetz-Protokoll, die im Abschnitt Stand der Technik dieser Beschreibung beschrieben sind, erfordern Knoten, um Mehrfachsende-Tabellen mit Einträgen für jedes Quellengruppenpaar zu erzeugen (damit wird die Anzahl der Einträge mit der Gesamtanzahl der Quellen multipliziert, verglichen mit dem MPTN-Schema).
Nachdem die vorstehende informative Beschreibung des Sendealgorithmus für MPTN-Mehrfachsende-Datenpakete vorgelegt worden ist, werden nun die Verfahrensweisen zum Mehrfachsenden ausführlich beschrieben. Es wird eine Verfahrensweise für das MPTN-Gateway, das am Anfang das Mehrfachsende-Datenpaket von einem Teilnetzwerk (Liste A) empfängt, und eine für dazwischenliegende MPTN-Gateways beschrieben, die Mehrfachsendungen übermitteln, die sie von anderen Gateways (Liste B) erhalten haben.
Verfahrensweise Liste A: Initiate_MPTN_Multicast
Diese Verfahrensweise wird von einem MPTN-Gateway benutzt, das aus einem Teilnetzwerk ein Mehrfachsende-Datenpaket empfängt.
Eingabe: Das Mehrfachsende-Datenpaket des Teilnetzwerkes, das ein Bestimmungs-Gruppenkennzeichner, die Dienstqualität und die Daten vorgibt, die mehrfach gesendet werden sollen.
Ausgabe: MPTN-Mehrfachsende-Datenpakete an die nächsten Gateways auf dem Pfad zum Zielort oder eine Mehrfachsendung direkt zu Zielteilnetzwerken, die direkt an das Gateway angeschlossen sind.
Unter Verwendung des angegebenen Gruppenkennzeichners als Schlüssel in die MURT ergibt sich die Liste der Vorsatzcodes für Teilnetzwerke, die Mitglieder der Gruppe enthalten.
Für jeden Vorsatzcode in der Liste
wird der Vorsatzcode und die vorgegebene Dienstqualität als Schlüssel in die FIB des IDRP benutzt, um das nächste Etappen-Gateway auf dem Pfad zu diesem Teilnetzwerk zu bestimmen.
wird dieser Vorsatzcode einer Liste für die bestimmte nächste Etappe hinzugefügt.
Für jede vorstehend erzeugte Liste der nächsten Etappen target_subnetworks auf die Liste der Vorsatzcodes einstellen, die mit dieser nächsten Etappe verbunden ist.
die MPTN-Mehrfachsendung einschließlich des Gruppenkennzeichners, target_subnetworks, Dienstqualität und Daten an diese nächste Etappe senden.
Es ist anzumerken, daß in einigen Fällen das Zielteilnetzwerk direkt an diesem Gateway angeschlossen ist und daß die Mehrfachsendung in diesen Fällen direkt an dieses Teilnetzwerk geschickt wird.

Verfahrensweise Liste B: Forward_MPTN_Multicast

Diese Verfahrensweise wird von einem MPTN-Gateway benutzt, um ein von einem anderen MPTN-Gateway erhaltenes Mehrfachsende-Datenpaket zu übermitteln.
Eingabe: Die MPTN-Mehrfachsendung einschließlich des Gruppenkennzeichners, target_subnetworks, Dienstqualität und Daten, wie sie in der Verfahrensweise Initiate_MPTN_Mulitcast erzeugt wurden.
Ausgabe: MPTN-Mehrfachsende-Datenpakete an die nächsten Gateways auf dem Pfad zum Zielort oder eine Mehrfachsendung direkt zu Zielteilnetzwerken, die direkt an das Gateway angeschlossen sind.
Für jeden Vorsatzcode in der empfangenen Liste target_subnetworks wird der Vorsatzcode und die vorgegebene Dienstqualität als Schlüssel in die FIB des IDRP benutzt, um das nächste Etappen-Gateway auf dem Pfad zu diesem Teilnetzwerk zu ermitteln; wird der Vorsatzcode zu einer Liste für die bestimmte nächste Etappe hinzugefügt.
Für jede vorstehend erzeugte Liste der nächsten Etappen target_subnetworks auf die Liste einstellen, die mit dieser nächsten Etappe verbunden ist;
die MPTN-Mehrfachsendung einschließlich Gruppenkennzeichner, target_subnetworks, Dienstqualität und Daten an diese nächste Etappe übermitteln.
Es ist anzumerken, daß in einigen Fällen das Zielteilnetzwerk direkt an dieses Gateway angeschlossen ist und daß in solchen Fällen die Mehrfachsendung direkt an dieses Teilnetzwerk geschickt wird.

Mehrfachsenden mit verminderter Leitweginformation

In dem in den vorstehenden Abschnitten beschriebenen Mehrfachsendeschema ist an jedem Gateway, das mit einer potentiellen Quelle von Mehrfachsendeverkehr an diese Gruppe verbunden ist, ein MURT-Eintrag für eine Gruppe erforderlich. In großen MPNs mit vielen Gruppen kann dies unerwünscht sein. Daher wird in diesem Abschnitt ein alternatives Schema beschrieben, in dem MURT-Einträge für eine bestimmte Mehrfachsendegruppe nur an Ga teways verwaltet werden müssen, die an Teilnetzwerke mit Mitgliedern in dieser Gruppe angeschlossen sind (andere Gateways könnten diese MURT-Einträge wahlweise verwalten). Dieses Schema kann möglicherweise die Speichermenge vermindern, die erforderlich ist, um Mehrfachsenden zu Lasten optimaler Leitweglenkung zu unterstützen, wie zu zeigen ist. Das in diesem Abschnitt beschriebene Schema ist unmittelbarer Bestandteil dieser Erfindung und kann in Verbindung mit dem oder anstelle des vorhergehenden Schemas benutzt werden.
Bei diesem Schema melden Teilnetzwerke Gruppenkennzeichner und Adreßvorsatzcodes benachbarten Gateways, wie es in dem Abschnitt mit dem Titel Leitweginformation beschrieben wurde. Diese Gateways müssen MURT-Einträge für die festgelegten Gruppenkennzeichner erzeugen. Sie müssen auch IDRP-Aktualisierungs- PDUs erzeugen, wie es im angesprochenen Abschnitt beschrieben ist. Gateways, die nicht an ein Teilnetzwerk angeschlossen sind, das Mitglieder eines bestimmten Gruppenkennzeichners enthält, sind jedoch nicht gezwungen, für diesen Gruppenkennzeichner MURT-Einträge zu verwalten.
Das Übermitteln von Datenpaketen, die an einen Gruppenkennzeichner adressiert sind, geht wie folgt vor sich:
- wenn ein Datenpaket, das übermittelt werden soll, ein von einem vorhergehenden MPTN-Gateway eingestelltes Zielteilnetzwerk-Feld hat, wird es entsprechend dem Algorithmus in Liste B übermittelt. Dies kann durch alle Gateways erfolgen, weil für diesen Algorithmus keine MURT erforderlich ist (die Zielvorsatzcodes werden im Zielteilnetzwerk vorgegeben).
- Wenn ein Datenpaket, das übermittelt werden soll, kein Zielteilnetzwerkfeld eingestellt hat und die Bestimmungsadresse ein Gruppenkennzeichner ist, für das an diesem Ga teway ein MURT-Eintrag verwaltet wird, wird die Verfahrensweise zum Auslösen einer MPTN-Mehrfachsendung in Liste A befolgt.
- Wenn ein Datenpaket, das übermittelt werden soll, kein Zielteilnetzwerkfeld eingestellt hat und für die Bestimmungsadresse kein MURT-Eintrag vorhanden ist, wird das Datenpaket punktweise auf der Basis des FIB-Eintrags des IDRP für diese Adresse übermittelt.
Wenn nur die Gateways, die an die Teilnetzwerke mit Mitgliedern einer Gruppe angeschlossen sind, einen MURT-Eintrag für diesen Gruppenkennzeichner haben, wird das Datenpaket punktweise zu einem derjenigen Gateways gelenkt, die dann veranlassen, daß es an die übrigen Gateways mehrfach gesendet wird.
Der vorstehende Algorithmus zur Leitweglenkung mit verminderter Information wird mit einem Beispiel erläutert, das sich wieder auf das in Fig. 3 dargestellte Netzwerk bezieht. Unter Verwendung der in diesem. Abschnitt beschriebenen Protokolle werden die folgenden Leitwegtabellen an den jeweiligen MPTN-Gateways aufgebaut:

Bei Gateway A (35)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode W: Adressen mit diesem Vorsatzcode befinden sich in dem lokalen Teilnetzwerk (31)
X: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
Y: Gateway B
Z: Gateway B
G: Gateway B

Bei Gateway B (36)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway A.
X: Gateway C
Y: Gateway D
Z: Gateway E
G: Gateway E

Bei Gateway C (39)

Bei Gateway D (38).

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode Y: Adressen mit diesem Vorsatzcode befinden sich im lokalen Teilnetzwerk (33)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
X: Gateway C
Z: Gateway B
G: Gateway C

Bei Gateway E (37)

FIB (Vorsatzcode: nächste Etappe auf kürzestem Pfad)
Adreßvorsatzcode Z: Adressen mit diesem Vorsatzcode befinden sich im lokalen Teilnetzwerk (34)
W: das nächste Gateway auf dem Pfad zu dem Teilnetzwerk, das Adressen mit diesem Vorsatzcode enthält, ist Gateway B.
X: Gateway B
Y: Gateway B
G: lokales Teilnetzwerk (34)
MURT (Gruppenkennzeichner: verknüpfte Vorsatzcodes)
Gruppenkennzeichner G: die mit diesem Gruppenkennzeichner verknüpften Vorsatzcodes sind X, Z.
In diesem Beispiel ist "G" der Gruppenkennzeichner einer Mehrfachsendegruppe, die Mitglieder in Teilnetzwerken X (32) und Z (34) hat, und es wird angenommen, daß nur Gateways C (39) und E (37) MURT-Einträge für Gruppenkennzeichner G verwalten. Damit behandeln alle anderen Gateways G wie eine Einfachsendeadresse (d. h. entsprechend den vorhandenen IDRP-Verfahrensweisen), und verwalten daher einen Einfacheintrag für G in ihren FIBs. Die Tatsache, daß mehrere Gateways bei G einen Pfad ankündigen (im Beispiel Gateways C und E), ist kein Problem, da IDRP dies zuläßt. Gateways speichern jedoch nur für den besten Pfad für einen gegebenen Vorsatzcode Leitweginformation (in der FIB). Beispielsweise hat Gateway B (36) statt von Gateway C (39) einen FIB-Eintrag von Gateway E (37), das mit G verbunden ist. Dies könnte umgedreht werden, aber in jedem Falle wird in der FIB nur einer der Pfade gespeichert.
MPTN-Gateway A (35) empfängt von Teilnetzwerk W (31) ein Mehrfachsende-Datenpaket, das an G adressiert ist. Es hat für G keinen MURT-Eintrag, daher lenkt es das Datenpaket auf der Grundlage des FIB-Eintrags für G (an Gateway B) mit den folgenden Feldern:
Bestimmungsort = G
Zielteilnetzwerke = nicht eingestellt
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket
Es ist anzumerken, daß das Feld für das Zielteilnetzwerk nicht eingestellt ist, da der MURT-Eintrag für G nicht verfügbar ist.
Gateway B (36) empfängt das Datenpaket, und da es auch keinen MURT-Eintrag für G hat, lenkt es das Datenpaket auf der Basis seiner FIB an Gateway E (37) mit den folgenden Feldern:
Bestimmungsort = G
Zielteilnetzwerke = nicht eingestellt
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket
Gateway E (37) ist an Teilnetzwerk Z angeschlossen, das Mitglieder in Gruppe G hat, und daher hat es für G einen MURT- Eintrag. Die MURT zeigt an, daß das Datenpaket in Teilnetzwerken mit Vorsatzcodes X und Z mehrfach gesendet werden soll. Da Teilnetzwerk Z (34) angeschlossen ist, sendet es das Datenpaket mehrfach in dieses Teilnetzwerk. Da der FIB-Eintrag für Teilnetzwerk X (32) Gateway B (36) ist, wird an Gateway B ein MPTN- Mehrfachsende-Datenpaket mit den folgenden Feldern geschickt:
Bestimmungsort = G
Zielteilnetzwerke = X
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket
Da das Feld für Zielteilnetzwerke nun eingestellt ist, verschickt Gateway B (36) das Datenpaket auf der Basis dieses Feldes (die hier vorgenommene Leitwegentscheidung im Gegensatz zu der vorstehend bei Gateway B getroffenen). Damit schickt es, da der FIB-Eintrag für Teilnetzwerk X (32) Gateway C (39) ist, das MPTN-Mehrfachsende-Datenpaket mit den folgenden Feldern an Gateway C:
Bestimmungsort = G
Zielteilnetzwerke = X
Daten wie vorgegeben im ursprünglichen Mehrfachsende-Datenpaket
Schließlich sendet Gateway C (39) das Datenpaket mehrfach an Gruppenkennzeichner G in Teilnetzwerk X (32), an dem es angeschlossen ist.
Es ist anzumerken, daß in diesem Beispiel das Datenpaket zweimal durch Gateway B (36) gelenkt wurde; einmal mit nicht eingestellten Zielteilnetzwerkfeld und einmal mit eingestelltem. Damit gehen die Einsparungen beim Speichern, bei denen die MURT- Einträge an Gateways A, B und D (35, 36 und 38) nicht verwaltet werden, zu Lasten von nicht optimalem Leitwegverhalten für Mehrfachsende-Datenpakete.

Einsatz des Mehrfachsendens in MPTN

Wie vorstehend angemerkt, ist MPTN auf der Mehrfachsenden angewiesen, um Mehrfachsendungen durch Anwendungen unter Benutzung von MPTN zu unterstützen und MPTN-Steueralgorithmen zu unterstützen. Diese Probleme und die Art, in der sie gelöst werden, sind in diesem Abschnitt beschrieben.
Vorhandene Leitweglenkprotokolle erfordern es, daß alle Knoten, deren Adressen einen gemeinsamen Vorsatzcode haben, sich in einem einzigen Teilnetzwerk befinden. Auf diese Weise kennzeichnet der Vorsatzcode das Teilnetzwerk eindeutig, und Operationen, die Knoten mit dem gegebenen Vorsatzcode betreffen, können vollständig innerhalb dieses Teilnetzwerkes ablaufen. Dies ist in Fig. 4 veranschaulicht.
MPTN gestattet es Knoten in verschiedenen Teilnetzwerken, den gleichen Adreßvorsatzcode zu besitzen. Damit kennzeichnet ein derartiger Vorsatzcode nicht eindeutig ein bestimmtes Teilnetzwerk, und Operationen, die Knoten mit diesem Vorsatzcode betreffen, müßten über mehrfache Teilnetzwerke verteilt werden. Dies ist in Fig. 5 veranschaulicht. Dies wird als "aufgeteilter Netzkennzeichner" bezeichnet, weil "Netzkennzeichner" ein Synonym für Adreßvorsatzcode und "aufgeteilt" bedeutet, daß die Knoten mit dem vorgegebenen Netzkennzeichner unter verschiedenen Teilnetzwerken aufgeteilt sein können. Die Teilnetzwerke, die Knoten in dem aufgeteilten Netzkennzeichner enthalten, werden als "Inseln" dieses aufgeteilten Netzkennzeichners bezeichnet. Damit veranschaulicht Fig. 5 einen aufgeteilten Netzkennzeichnern mit 3 Inseln. Das Unterstützen derartiger aufgeteilter Netzkennzeichner hat auf die folgenden MPTN-Operationen Auswirkungen:
1. Von MPTN-Benutzern mehrfach gesendete Datenpakete an Knoten in einem aufgeteilten Netzkennzeichner müssen an alle Teilnetzwerke übermittelt werden, die derartige Knoten enthalten.
2. Um an einen Knoten in einem aufgeteilten. Netzkennzeichner Verbindungen und Einfachsende-Datagramme zu lenken, müssen MPTN-Gateways zuerst ermitteln, in welcher Insel des aufgeteilten Netzkennzeichners sich der Bestimmungsort befindet.
3. Teilnetzwerkprotokolle, die sicherstellen, daß alle in diesem Teilnetzwerk in Gebrauch befindlichen Adressen eindeutig sind, müssen auf alle Inseln eines aufgeteilten Netzkennzeichners ausgeweitet werden, da aufgrund der Benutzung des gleichen Adreßvorsatzcodes dort Knoten mit der gleichen Adresse vorhanden sein könnten.
Um aufgeteilte Netzkennzeichner zu unterstützen, werden die in dieser Erfindung beschriebenen Mehrfachsendeprotokolle benutzt. Insbesondere wird der den Knoten im aufgeteilten Netzkennzeichner gemeinsame Adreßvorsatzcode wie ein Gruppenkennzeichner behandelt, und dieser Gruppenkennzeichner wird bei allen MPTN- Gateways registriert, die allen Inseln des aufgeteilten Netzkennzeichners benachbart sind. Damit kennzeichnet der Gruppenkennzeichner die Gruppe aller Inseln des aufgeteilten Netzkennzeichners. Es werden Benutzerdatagramme und Verbindungsanforderungen empfangen werden, die eine Bestimmungsadresse vorschreiben, die mit dem Vorsatzcode des aufgeteilten Netzkennzeichners (d. h. des Gruppenkennzeichners) beginnen, da Benutzer mit Betriebsmitteln in diesem aufgeteilten Netzkennzeichner kommunizieren möchten. MPTN-Steuerdatenpakete werden an den Gruppenkennzeichner adressiert, um mit einem Gateway in Verbindung zu treten, das an jede Insel des aufgeteilten Netzkennzeichners angeschlossen ist, wie nachstehend erklärt. Wie bei anderen Gruppen erfordert jedes Gruppenmitglied (d. h. jede Insel) auch einen eindeutigen Vorsatzcode, der mit dem Gruppenkennzeichner in der MURT verbunden ist. Dies ergibt sich wie folgt.
Jedes mit einem aufgeteilten Netzkennzeichner verbundene Gateway hat in diesem Teilnetzwerk eine Adresse, die global eindeutig ist (diese globale Eindeutigkeit wird von den Teilnetzwerkprotokollen garantiert). Wenn dieses Gateway das einzige Gateway ist, das mit einer bestimmten Insel des aufgeteilten Netzkennzeichners verbunden ist, kann es in diesem Teilnetzwerk seine eigene Adresse als eindeutigen Vorsatzcode für die Insel benutzen. Da alle Leitwegprotokolle in der Klasse, die für diese Erfindung von Bedeutung ist (z. B. IDRP, IP, OSPF, OSI IS- IS), es erforderlich machen, daß Gateways miteinander kommunizieren, um Leitweginformation auszutauschen, haben Gateways automatisch mit allen anderen Gateways Kontakt, die an die gleiche Insel des aufgeteilten Netzkennzeichners angeschlossen sind (d. h. alle diejenigen Gateways, mit denen es über dieses Teilnetzwerk Leitweginformation austauscht). Damit erkennen Gateways, wenn Mehrfach-Gateways an der gleichen Insel eines aufgeteilten Netzkennzeichners angeschlossen sind, und erkennen auch, wenn Gateways zu der Gruppe, die mit einer Insel mit aufgeteiltem Netzkennzeichner verbunden ist, hinzugefügt oder aus ihr entfernt werden.
Das Verfahren zum Auswählen eines eindeutigen Vorsatzcodes zum Verknüpfen mit einer Insel eines aufgeteilten Netzkennzeichners ist wie folgt:
1. Wenn ein Gateway am Anfang aktiviert wird, nimmt es an, daß seine eigene Adresse als eindeutiger Vorsatzcode für die Insel des aufgeteilten Netzkennzeichners benutzt wird, mit dem es verbunden ist.
2. Immer dann, wenn ein Gateway das Vorhandensein anderer Gateways feststellt, die mit der gleichen Insel verbunden sind (was es tun muß, um die vorhandenen Leitwegprotokolle einzurichten), prüft es die Adressen aller derartiger Ga teways und benutzt die kleinste derartige Adresse (was seine eigene sein könnte) als den eindeutigen Vorsatzcode für den aufgeteilten Netzkennzeichner. Da alle Gateways diesen Algorithmus ausführen werden, werden sie zusammenkommen, um die gleiche Adresse als Vorsatzcode zur eindeutigen Kennzeichnung dieser Insel zu benutzen.
Dieser Schritt muß immer dann wiederholt werden, wenn ein Gateway zu der Gruppe von Gateways hinzugefügt wird oder aus ihr herausfällt, die an die lokale Insel mit aufgeteiltem Netzkennzeichner angeschlossen ist.
Dieses Verfahren stellt gültige eindeutige Vorsatzcodes für Inseln von aufgeteilten Netzkennzeichnern für den Falle bereit, daß zwei oder mehr getrennte Inseln zu einer Insel vereinigt werden, oder wenn eine einzelne Insel dynamisch in mehrere Inseln aufgeteilt wird. Der Algorithmus ist vollständig verteilt und garantiert, daß er zu einer korrekten Zuordnung von eindeutigen Vorsatzcodes zu Gateways führt, die an Inseln mit aufgeteiltem Netzkennzeichner angeschlossen sind.
Die eindeutigen Adreßvorsatzcodes, die mit einem aufgeteilten Netzkennzeichner verbunden sind, werden als "abgeleiteter Netzkennzeichner" bezeichnet. Dies ist in Fig. 6 veranschaulicht.
In dieser Fig. 6 sehen wir, daß sich Knoten mit Adreßvorsatzcode X in zwei unterschiedlichen Teilnetzwerken befinden. Daher wird X, ein aufgeteilter Netzkennzeichner, als Gruppenkennzeichner mit den an diesen Teilnetzwerken angeschlossenen MPTN- Gateways registriert. Gateway G (62) ist das einzige an der oberen Insel des aufgeteilten Netzkennzeichners X angeschlossene Gateway. Es benutzt daher seine lokale Adresse X.7 als eindeutigen Vorsatzcode, um mit Gruppenkennzeichner X verbunden zu werden. Gateways H (63) und I (64) sind mit der unteren Insel des aufgeteilten Netzkennzeichners verbunden. Da die Adresse von Gateway H niedriger als die von Gateway 1 ist (X.8 ist weniger als X.9), benutzen sie beide X.8 als den eindeutigen Vorsatzcode, um mit Gruppenkennzeichner X verbunden zu werden. Unter Verwendung der Protokolle dieser Erfindung baut Gateway F (61) die erläuterten FIB und MURT-Tabelleneinträge auf, die mit dem Adreßvorsatzcode X verbunden sind.
Unter Verwendung der Mehrfachsendeprotokolle aus den vorhergehenden Abschnitten und der Verfahrensweise zur Abbildung aufgeteilter Netzkennzeichner auf Gruppenkennzeichner und abgeleitete Netzkennzeichner in diesem Abschnitt ist es möglich, in MPTN aufgeteilte Netzkennzeichner zu unterstützen.
Wenn ein Datenpaket eines MPTN-Benutzers an alle Knoten mit Vorsatzcode X mehrfach gesendet werden soll, kann das Datenpaket an alle Inseln des aufgeteilten Netzkennzeichners unter Verwendung der Verfahrensweise der vorhergehenden Abschnitte verteilt werden, da X ein Eintrag in der MURT ist. Auf die gleiche Weise können Flüsse, die Teil von Namenverwaltungsprotokollen von Teilnetzwerken sind, an alle Teile eines aufgeteilten Netzkennzeichners mehrfach gesendet werden.
Wenn eine Verbindung oder ein Einfachsende-Datagramm an einen Knoten mit Vorsatzcode X (etwa X.3 im Beispiel in Fig. 6) geschickt werden soll, ist ein zusätzliches Protokoll erforderlich, das einen weiteren Teil dieser Erfindung bildet. Ein MPTN-Gateway, das ein Einfachsende-Datenpaket oder eine Einfachsende-Verbindung lenken soll, die auf einem Adreßvorsatz beruht, der in der MURT erscheint, benutzt diese Verfahrensweise.
1. Unter Verwendung des in dieser Erfindung beschriebenen Mehrfachsendeverfahrens wird eine LOCATE-Anforderung an ein MPTN-Gateway verteilt, das an jede Insel des aufgeteilten Netzkennzeichners angeschlossen ist. Ein Parameter des LOCATE besteht aus der speziellen Adresse, die Ziel des ursprünglichen Einfachsende-Datenpaketes ist (d. h. das Betriebsmittel, das aufgefunden werden soll). Damit sendet im Beispiel Gateway F (61) mehrfach ein LOCATE an Gateways G (62) und H (63), um den Standort von Betriebsmittel X.3 festzustellen.
2. Jedes Gateway, das eine derartige LOCATE-Anforderung erhält, durchsucht das angeschlossene Teilnetzwerk (unter Verwendung der eigenen Protokolle dieses Teilnetzwerkes oder der MPTN-Protokolle), um zu ermitteln, ob das Zielbetriebsmittel tatsächlich in dieser Insel des aufgeteilten Netzkennzeichners angeordnet ist. Im Beispiel entdeckt Gateway G (62), daß X.3 sich in dem angeschlossenen Teilnetzwerk befindet, während Gateway H (63) nicht in der Lage ist, X.3 zu finden.
3. Alle Gateways, die LOCATE empfangen haben, schicken eine Antwort an das MPTN-Gateway zurück, das die Suche ausgelöst hat, welche den eindeutigen Vorsatzcode der Antwortenden und eine Markierung enthält, die angibt, ob das. Betriebsmittel gefunden wurde oder nicht. Im Beispiel schickt Gateway G (62) eine Antwort an Gateway F (61) zurück, die seinen eindeutigen Adreßvorsatzcode X.7 und eine Markierung enthält, mit der angezeigt wird, daß das Betriebsmittel gefunden wurde. Gateway H (63) schickt ein Ergebnis zurück, das anzeigt, daß das Betriebsmittel nicht gefunden wurde.
4. Sobald eine positive Antwort auf die Suche eingetroffen ist, ist Gateway F (61) in der Lage, die Einfachsendenachricht oder -Verbindung an den richtigen Bestimmungsort zu lenken. Der Kennsatz dieser Anforderung muß angeben, an welches Gateway die Anforderung geschickt werden soll (im Beispiel X.7), so daß alle Gateways die Anforderung über mitteln können. Der Kennsatz muß weiterhin die Adresse enthalten, für welche die Anforderung bestimmt ist (X.3), so daß das letzte Gateway in der Lage ist, sie durch das Teilnetzwerk zu lenken, das den Bestimmungsort enthält.
Es ist für Gateways, die ein bestimmtes Betriebsmittel nicht finden können, wichtig, eine negative Antwort auf eine LOCATE- Anforderung zu schicken. Andernfalls würde das Gateway, das die Anforderung lenken muß, in dem Falle, daß ein Betriebsmittel nicht vorhanden ist (z. B. ein Benutzer versucht, an X.5 eine Nachricht zu senden, das gar nicht vorhanden ist), ewig auf eine Antwort warten. Statt dessen weiß es, wenn eine negative Nachricht von jedem Gateway empfangen worden ist, daß das in Frage stehende Betriebsmittel nicht erreichbar ist, es kann daher die ursprüngliche Anforderung zurückweisen.
Damit endet die Beschreibung der bevorzugten Ausführungsformen. Natürlich sind zahlreiche Variationen der gegebenen Beispiele möglich, und zwar innerhalb des Rahmens der Erfindung, wie sie beansprucht wird.

Claims

1. Verfahren zum Mehrfachsenden einer Nachricht von einer Sendestation an eine Vielzahl von Empfangsstationen innerhalb eines konventionellen Einfachsende-Nachrichtenübertragungsnetzwerkes unter Verwendung vorhandener Protokolle, wobei das Netzwerk aus einer Vielzahl von Teilnetzwerken besteht, die Knoten (Netzkoppler, Gateways A ... E) enthalten, welche die Teilnetzwerke verbinden und als Eingabeanschlüsse dazu fungieren,

wobei einer oder mehrere der Gateways (35 ... 39), welche die Teilnetzwerke (31 ... 34) verbinden, eine Leitwegtabelle (MURT) verwalten, um an Empfangsstationen mehrfach zu senden,

und ein Kennsatz, der in jeder übertragenen Mehrfachsendenachricht enthalten ist, Information (Gruppen-ID) enthält, die eine Gruppe der die Mehrfachsendung empfangenden Stationen definiert.

2. Verfahren von Anspruch 1, wobei die Leitwegtabelle (MURT) eines Gateways insbesondere zusätzlich zur konventionellen Leitweginformation einen oder mehrere Gruppenkennzeichner (Gruppen-ID), die mindestens eine die Mehrfachsendung empfangende Station, vorzugsweise eine Gruppe von die Mehrfachsendung empfangenden Stationen definieren, und einen Vorsatzcode enthält, der das/die Teilnetzwerk(e) kennzeichnet, in denen die die Mehrfachsendung empfangende(n) Station(en) angeordnet ist/sind.

3. Verfahren von Anspruch 2, wobei die Empfangsstation(en), die durch den Gruppenkennzeichner (Gruppen-ID) definiert werden, in unterschiedlichen Teilnetzwerken angeordnet ist/sind.

4. Verfahren nach einem oder mehreren der vorhergehenden Ansprüche, wobei die Leitwegtabellen (MURT), die in einem bestimmten Gateway verwaltet werden, Information nur von denjenigen die Mehrfachsendung empfangenden Stationen enthalten, die über den Gateway erreicht werden können.

5. Verfähren nach einem oder mehreren der vorhergehenden Ansprüche, wobei nur diejenigen Gateways, die mit möglichen Quellen von Mehrfachsende-Nachrichten verbunden sind, eine Tabelle (MURT) der adressierbaren die Mehrfachsendung empfangenden Stationen verwalten.

6. Verfahren nach einem oder mehreren der vorhergehenden Ansprüche, wobei die Gruppenkennzeichnung (Gruppen-ID) und/oder die Adreßvorsatzcodes zusammen mit der konventionellen Leitweginformation an die Gateways übertragen werden.

7. System zum Mehrfachsenden einer Nachricht von einer Sendestation an eine Vielzahl von Empfangsstationen innerhalb eines konventionellen Einfachsende-Nachrichtenübertragungsnetzwerkes unter Verwendung vorhandener Protokolle, wobei das Netzwerk aus einer Vielzahl von Teilnetzwerken besteht, die durch Knoten (Netzkoppler, Gateways A ... E) verbunden sind, wobei

ein oder mehrere Gateways (37 ... 39), welche die Teilnetzwerke (31 ... 34) verbinden, eine Leitwegtabelle für Mehrfachsendung empfangende Stationen enthalten, jede Mehrfachsende-Nachricht, die übertragen werden soll, einen Kennsatz trägt, der Information enthält, die eine Gruppe der die Mehrfachsendung empfangenden Stationen definiert,

in jedem Gateway Mittel zum Übersetzen, Vergleichen und Modifizieren des Kennsatzes der Mehrfachsendenachricht bereitgestellt werden.

8. System von Anspruch 7, wobei die Teilnetzwerke von unterschiedlicher Art sind und/oder unterschiedliche Nachrichtenübertragungsprotokolle benutzen.

9. System von Anspruch 8, wobei nur eine Teilmenge der Teilnetzwerke so ausgerüstet ist, daß sie Mehrfachsendung unterstützen.