DE69127198T2

DE69127198T2 - Nachrichtenlenkung in einem Nezt, das aus über Brücken verbundenen Lokalnetzsegmenten besteht

Info

Publication number: DE69127198T2
Application number: DE69127198T
Authority: DE
Inventors: Rainer Dr Oechsle
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-10-14
Filing date: 1991-10-14
Publication date: 1998-02-12
Anticipated expiration: 2011-10-15
Also published as: EP0537408B1; EP0537408A1; DE69127198D1; JPH05219064A; JPH0752888B2; US5570466A

Description

BESCHREIBUNG

Nachrichtenlenkung

Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf die Nachrichtenlenkung von Datenpakten oder Rahmen in einem lokalen Kommunikationsnetz, das aus einer Vielzahl von LAN-Segmenten besteht, die über Brücken miteinander verbunden sind.

Hintergrund der Erfindung

In einem LAN-Kommunikationsnetz aus mehreren Segmenten, die über Brücken miteinander verbunden sind, ist ein bestimmtes Maß an Nachrichtenlenkung erforderlich, um eine korrekte Übertragung der adressierten Dateneinheiten, wie beispielsweise Rahmen, über die Brücken zwischen den Segmenten zu gewährleisten. Mangelhafte Nachrichtenlenkungsprozesse führen zu erhöhten Übertragungszeiten und Verschwendung von Übertragungskapazität.
Eine allgemeine Übersicht über Verfahren der Nachrichtenlenkung enthält ein Artikel von M. Schwartz et. al. mit dem Titel "Routing Protocols", veröffentlicht in dem Band "Computer Networks and Protocols" (Hrg. C. A. Sunshine), Plenum Press, New York 1989, S. 239 - 271. Neben verschiedenen anderen Verfahren wird darin die Verwendung von Baunstrukturen der kürzesten Pfade für die Nachrichtenlenkung beschrieben. Dieses Verfahren wird auf Netzebene eingerichtet. Es beruht auf Netzadressen mit einer bestimmten Struktur, aus denen Netznummern (Segmentnummern) abgeleitet werden können. Die Nachrichtenlenkung erfolgt anhand dieser Netznummern. Dieses Verfahren läßt sich nicht direkt auf die Überbrückung anwenden, da MAC-Adressen aus einem einfachen Adreßraum ohne jegliche Struktur abgeleitet werden.
Die Rundsende-Nachrichtenlenkung, bei der ebenfalls die Baumstrukturen der kürzesten Pfade verwendet werden, wird in einem Artikel von Y. K. Dalal et. al. mit dem Titel "Reverse Path Forwarding of Broadcast Packets", Communications of the ACM, Bd. 21, Nr. 12, S. 1040 - 1048 (Dezember 1978) beschrieben.
Für LAN-Kommunikationssysteme, die mehrere gebrückte Segmente umfassen, sind heutzutage zwei Überbrückungsverfahren weit verbreitet. Sie sind unter der Bezeichnung "Lernbrücke" (Transparent Spanning Tree Bridge) bzw. "Ursprungslenkungsbrücke" (Source Routing Bridge) bekannt.
Das Lernbrückenverfahren wird z. B. von F. Backes in "Transparent Bridges for Interconnection of IEEE 802 LANs", IEEE Network, Bd. 2, Nr. 1, S. 5 - 9 (Januar 1988) beschrieben. Der Grundgedanke des Lernbrückenverfahrens besteht in der Konfiguration der Brücken, so daß die Brücken und die LAN-Segmente einen Überbrückungsbaum (Spanning Tree) bilden. Alle Brücken horchen den gesamten Datenverkehr auf den LAN-Segmenten ab, mit denen sie verbunden sind, und erkennen aus den Quelladressen, in welcher Richtung sich eine Datenstation befindet. Ausgehend von diesem Wissen leiten die Brücken die Rahmen über den Überbrückungsbaum weiter. Wenn eine Zieladresse unbekannt ist, wird der Rahmen über den Überbrückungsbaum an alle LAN-Segmente rundgesendet.
Dieses Überbrückungsverfahren hat mehrere Nachteile: (1) Da die LANs und Brücken einen einzigen Überbrückungsbaum bilden, kann in allgemeinen nur eine Teilmenge der verfügbaren Brücken zu einem bestimmten Zeitpunkt aktiv sein. Die restlichen Brücken werden lediglich als Reservebrücken zu Sicherungszwecken verwendet. (2) Aufgrund des Überbrückungsbaums kann ein Leitweg zwischen zwei LAN-Segmenten alles andere als optimal sein. So kann ein Rahmen von einem LAN-Segment zu einem anderen LAN- Segment möglicherweise über eine Vielzahl von Brücken und LAN- Segmenten übertragen werden, obwohl die Quell- und Ziel-LAN- Segmente direkt über eine Brücke miteinander verbunden sind, diese Brücke jedoch nicht Teil des jeweiligen Überbrückungsbaums ist. (3) Lernbrücken müssen jeden Rahmen einzeln kopieren und verarbeiten, um die MAC-Adressen zu erfahren. Daher kann eine Brücke stark ausgelastet sein, auch ohne daß sie einen Rahmen weiterleitet. (4) Da die kontinuierlich aktualisierte Tabelle mit den Zieladressen relativ groß werden kann, kann eine erhebliche Zeitspanne für das Nachschlagen in der Adressentabelle erforderlich sein, so daß die Weiterleitung längere Zeit in Anspruch nehmen kann.
Das Verfahren der Ursprungslenkungsbrücke beschreiben R. C. Dixon et. al. in "Addressing, Bridging, and Source Routing", IEEE Network, Bd. 2, Nr. 1, S. 25 - 32 (Januar 1988). Der Grundgedanke beim Verfahren der Ursprungslenkungsbrücke besteht darin, daß jeder Rahmen von den Quelldatenstationen mit Nachrichtenlenkungsdaten versehen wird. Diese Daten beschreiben den gesamten Pfad, den der Rahmen von der Quelldatenstation über alle dazwischenliegenden Brücken und LAN-Segmente bis zum Ziel- LAN-Segment nehmen muß. Die Brücken leiten die Rahmen einfach ausgehend von diesen Nachrichtenlenkungsdaten weiter. Vor der Verwendung der Nachrichtenlenkungsdaten werden Erkennungsrahmen von der Quell- an die Zieldatenstaton über das Netz gesendet, wobei die Brücken die Leitwege in den Erkennungsrahmen aufzeichnen und "kreisende" Rahmen verwerfen. Die Zieldatenstation antwortet auf diese Erkennungsrahmen, so daß auch die Quelldatenstation den Leitweg erfährt. Die Quell- oder Zieldatenstation kann einen von mehreren Leitwegen auswählen.
Auch das Verfahren der Ursprungslenkungsbrücke hat eine Reihe von Nachteilen: (1) Es gibt eine Obergrenze für die Nachrichtenlenkungsdaten, die in MAC-Rahmen übertragen werden können. Wenn der Wert für diese Obergrenze niedrig ist, beschränkt sich die Nachrichtenlenkung auf eine kleine Anzahl von Sprüngen. Wenn dieser Wert hoch ist, kommt es zu einem erheblichen Rahmen-Überhang in der Länge. (2) Die Nachrichtenlenkung in einem gebrückten LAN kann nicht so geändert werden, daß dies für die Datenstationen transparent ist, da ein Quelleitweg den Pfad durch das Netz, dem der Rahmen folgen nuß, exakt vorschreibt. Daher kann das Netz nicht an unterschiedliche Datenverkehrslasten angepaßt werden, ohne daß die Datenstationen davon betrof-. fen sind.
DE 40 00 673 A1 beschreibt ein Verfahren und eine Vorrichtung für die Übertragung von Datentelegrammen in einem System, das aus Bussegmenten besteht, die über Brücken miteinander verbunden sind. Jede Brücke enthält Speichermittel, in denen - getrennt für die beiden Übertragungsrichtungen - einen Bezeichner für jedes Bussegment gespeichert ist, das von dieser Brücke aus in der betreffenden Richtung erreicht werden kann. Jedes Datentelegramm enthält einen Bussegmentbezeichner für die Zieldatenstation. Eine Brücke leitet ein Datentelegramm weiter, wenn das betreffende Datentelegramm den Bezeichner für ein Bussegment enthält, das in der Brücke als erreichbares Buselement gekennzeichnet ist.
Das System darf jedoch keine Schleifen enthalten, da andernfalls einige Datentelegramme vervielfältigt werden und das Ziel als mehrere Kopien (auf verschiedenen Leitwegen) erreichen können. Daher ist dieses Verfahren nur dann möglich, wenn das System an sich über eine Baumstruktur verfügt. In einem willkürlichen oder nicht vorhersagbaren System kann es vorkommen, daß einige der Segmente Schleifen bilden, so daß ein Verfahren erforderlich ist, mit den jeder Datenrahmen als eine einzige Kopie weitergeleitet und so die unnötige Vervielfältigung von Rahmen und damit die Verstopfung des Systems vermieden wird.

Aufgaben der Erfindung

Eine Aufgabe der Erfindung besteht daher in der Bereitstellung eines Überbrückungsverfahrens für gebrückte LAN-Systeme, das die Nachteile der bekannten Überbrückungsverfahren vermeidet. Insbesondere besteht eine Aufgabe der Erfindung in der Bereitstellung eines Überbrückungsverfahrens, das lediglich mittelgroße Nachrichtenlenkungstabellen in Brücken benötigt, das nur minimale Nachrichtenlenkungsdaten in den übertragenen Rahmen erfordert, das die schnelle Weiterleitung von Rahmen über die Brücken ermöglicht und das die wirksame Verarbeitung der Erkennungsrahmen gestattet, um die Nachrichtenlenkungsdaten zu ermitteln, die eine Datenstation für die Weiterleitung von Rahmen an eine andere Datenstation benötigt, deren Standort unbekannt ist.

Zusammenfassung der Erfindung

Diese Aufgaben werden mit einem Verfahren für die Nachrichtenlenkung von Rahmen über ein Netz gelöst, das aus Netzsegmenten besteht, die über Brücken nach den Ansprüchen 1 und 2, mit einer Vorrichtung nach den Ansprüchen 3 bis 6 sowie mit einem Netz nach Anspruch 7 miteinander verbunden sind.
Die Erfindung zeichnet sich durch die folgenden Vorteile aus:
- Die Topologie ist nicht auf einen einzigen Überbrückungsbaum beschränkt.
- Die Größe der Nachrichtenlenkungstabellen liegt im Größenbereich der Anzahl von LAN-Segmenten, die wiederum eine angemessene Anzahl nicht überschreiten sollten. Daher ist die Verwendung einer Nachrichtenlenkungstabelle sehr viel wirksamer als dies in einem System der Fall ist, in dem Einträge für alle Adressen erforderlich sind.
- Aufgrund der geringen Größe der Nachrichtenlenkungstabellen und der festen Position der relevanten Nachrichtenlenkungsdaten in den einzelnen Rahmen kann die Entscheidung, ob ein Rahmen kopiert werden soll oder nicht, von der Adapter- Hardware getroffen werden. Rahmen, die nicht weitergeleitet werden müssen, müssen auch nicht verarbeitet werden.
- Das gebrückte LAN wird während der Erkennungsphase nicht mit Daten überschwemmt. Ein Erkennungsrahmen wird genau einmal an jedes einzelne LAN-Segment übertragen.
- Es gibt keine Beschränkung für die Länge der Pfade, über die die Rahmen übertragen werden; die Länge der Nachrichtenlenkungsdaten in den Rahmen ist jedoch festgelegt und kurz.
- Die dynamische Anpassung der Weiterleitung über die Brücken läßt sich erzielen, indem die Baumstrukturen der kürzesten Pfade geändert werden.
Diese und andere Vorteile werden deutlicher aus einer bevorzugten Ausführungsform der Erfindung, die im folgenden mit Bezug auf die Zeichnungen beschrieben wird.

Liste der Zeichnungen

Fig. 1 zeigt die Konfiguration eines typischen lokalen Kommunikationsnetzes aus LAN-Segmenten, die über Brücken miteinander verbunden sind, in dem die Erfindung verwendet werden kann, sowie ein Beispiel für eine Baumstruktur der kürzesten Pfade.
Fig. 2 zeigt das Format der im System aus Fig. 1 übertragenen MAC-Rahmen und insbesondere das Format des Steuerfeldes für die Nachrichtenlenkung, das für die Realisierung der Erfindung an gepaßt wurde.
Fig. 3 zeigt das Format der Nachrichtenlenkungstabellen für Brücken, die für die Realisierung der Erfindung bereitgestellt werden.
Die Fig. 4A, 4B und 4C zeigen eine schematische Darstellung eines gebrückten LAN-Segmentnetzes und der Baumstrukturen der kürzesten Pfade in einem solchen Netz.
Fig. 5 zeigt ein Blockdiagramm einiger Funktionseinheiten, die in einer Brücke für die Realisierung der Erfindung bereitgestellt werden.
Fig. 6 zeigt ein Blockdiagramm einiger Funktionseinheiten, die in einer Brücke für die Realisierung der Erfindung bereitgestellt werden, insbesondere für das Testen und Modifizieren des Felds mit den Nachrichtenlenkungsdaten des Erkennungsrahmens.

Ausführliche Beschreibung

1) LAN-Netzkonfiguration

Fig. 1 zeigt einen Netztyp, in dem die Erfindung realisiert wird. Dabei handelt es sich um ein lokales Netz (LAN), das aus verschiedenen separaten LAN-Segmenten LS-1 ... LS-7 besteht, die über Brücken BR-1 ... BR-5 miteinander verbunden sind. Die Benutzerdatenstationen UT sind mit den einzelnen LAN-Segmenten verbunden.
Die LAN-Segmente können zu einem beliebigen bekannten LAN-Typ gehören, z. B. Token-Ring-Netze, Doppelbusnetze usw. Dabei wird davon ausgegangen, daß alle LAN-Segmente des Netzes denselben Typ aufweisen; abhängig von den verwendeten Brücken können jedoch auch unterschiedliche Typen von LAN-Segmenten in einem Netz verwendet werden.
Die Benutzerdatenstationen UT können innerhalb des Systems verschoben werden, d. h. sie sind nicht fest mit einem LAN-Segment eines bestimmten Anschlusses verbunden. Jede Benutzerdatenstation verfügt jedoch über eine eindeutige Adresse, mit der sie innerhalb des Systems identifiziert werden kann.

2) Übertragungsformat (Rahmenformat)

Die Daten werden innerhalb des Systems in Form von Rahmen übertragen. Ein mögliches Format für derartige Rahmen ist in Fig. 2 abgebildet. Es entspricht dem Format, das für Token-Ring-LANs in IEEE 802.5 definiert ist. Der Rahmen verfügt über einen Kopfbereich, ein Datenfeld (optional) und einen Endbereich. Der Kopfbereich beginnt mit dem Anfangsbegrenzer (SD) und enthält weiter ein Zugangssteuerfeld AC, ein Rahmensteuerfeld FC, zwei Felder für eine Zieladresse bzw. eine Quelladresse und ein Feld für Nachrichtenlenkungsdaten RI. Das Datenfeld umfaßt die zu übertragenden Daten. Der Endbereich enthält Felder für eine Blockprüfzeichenfolge FCS, für den Endebegrenzer des Rahmens (ED) und für ein Rahmenstatusbyte (FS). Die Erfindung kann jedoch auch mit anderen Rahmenformaten realisiert werden, sofern die Felder für Zieladresse, Quelladresse und Nachrichtenlenkungsdaten vorhanden sind.
Die Quell- und Zieladressen geben die Datenstationen an, zwischen denen der betreffende Rahmen übertragen werden soll (die Zieladresse kann auch eine Sammel- oder Rundsendeadresse sein) Das Nachrichtenlenkungsfeld enthält Daten, mit denen die Brükken den Rahmen an das LAN-Segment weiterleiten, mit dem die Ziel-Benutzerdatenstation verbunden ist. Die Erfindung bezieht sich vorwiegend auf die Nachrichtenlenkung von Rahmen in einem Netz des Typs aus Fig. 1.
Die Übertragung der einzelnen Rahmen geschieht folgendermaßen: Jedes LAN-Segment, das einen Rahmen von einer verbundenen Benutzerdatenstation oder Brücke empfangen hat, gibt den Rahmen an alle anderen Einheiten weiter, die mit ihm verbunden sind. Jede Benutzerdatenstation prüft die Zieladresse und empfängt den Rahmen, wenn ihre eigene Adresse mit dem Ziel übereinstimmt. Jede Brücke prüft das Nachrichtenlenkungsfeld eines jeden Rahmens, die es auf einem der verbunden LAN-Segmente empfängt, und leitet abhängig von den Nachrichtenlenkungsdaten entweder eine Kopie (oder mehrere Kopien) des Rahmens an ein anderes LAN-Segment (oder an mehrere andere LAN-Segmente) weiter, oder sie verwirft den Rahmen. Der Inhalt der einzelnen Felder kann von einer Brücke geändert werden, bevor der betreffende Rahmen weitergeleitet wird.
Brücken für die Verbindung der LAN-Segmente sind in der Regel Einrichtungen mit zwei Anschlüssen, d. h. sie verbinden zwei LAN-Segmente miteinander und können Rahmen in beide Richtungen übertragen. Wie aus dem System aus Fig. 1 hervorgeht, können sie jedoch auch Mehranschlußeinrichtungen sein. In diesem Fall können sie Rahmen von jedem der n LAN-Segmente, mit denen die Brücke verbunden ist, an jedes einzelne oder an eine Vielzahl der (n-1) anderen LAN-Segmente übertragen. Die Nachrichtenlenkungsdaten RI bestimmen in jedem Fall die Übertragung der Rahmen zwischen den LAN-Segmenten.
Wie bereits in der Einleitung kurz erwähnt wurde, gibt es verschiedene Verfahren für die Ermittlung der Nachrichtenlenkung und für die Bereitstellung der Nachrichtenlenkungsdaten. Die vorliegende Erfindung schlägt ein besonders leistungsfähiges, neuartiges Verfahren für die Nachrichtenlenkung von Rahmen in einem System aus mehreren LAN-Segmenten vor, die über Brücken miteinander verbunden sind.

3) Funktionsprinzipien der Erfindung

Eine Voraussetzung für die Erfindung besteht darin, daß innerhalb des Netzes ein einziger (kürzester) Pfad von jedem LAN- Segment zu jedem anderen LAN-Segment ermittelt wird, und daß für jedes der LAN-Segmente in ihrer Funktion als Zielsegmente die vorgegebenen Pfade von allen anderen LAN-Segmenten eine Baunstruktur bilden. Dies wird auch als Überbrückung mit der Baumstruktur der kürzesten Pfade bezeichnet. Eine ausführlichere Erläuterung wird mit Blick auf Fig. 4 und 5 gegeben.
Es wird vorausgesetzt, daß allen LAN-Segmenten des Systems eine eindeutige Kennzeichnungsnummer (bzw. ein Code) zugewiesen wird. Der Ausdruck "kürzester Pfad" bezeichnet dabei den optimalen Pfad, wobei dies nicht unbedingt hinsichtlich der Länge, sondern hinsichtlich von Merkmalen wie Zeitverzögerung, Übertragungskosten, Verfügbarkeit usw. zu verstehen ist. Auf diese Weise kann Brücken eine bestimmte Gewichtung zugewiesen werden, die ihre Kapazität und Leistungsfähigkeit beschreibt.
Verfahren für die Ermittlung der kürzesten Pfade, die eine Baumstruktur bilden, sind z. B aus der Veröffentlichung von M. Schwartz et. al. mit dem Titel "Routing Protocols" bekannt, die in der Einleitung bereits erwähnt wurde. Die Ermittlung der Baumstrukturen der kürzesten Pfade kann entweder zentral oder verteilt erfolgen. Sie kann außerdem vor dem eigentlichen Betrieb während der Netzkonfigurierung oder dynamisch (adaptiv) während des Betriebs durchgeführt werden.
Die Erfindung verwendet die Baumstrukturen der kürzesten Pfade auf die folgende Art und Weise:

a) Nachrichtenlenkungstabellen in Brücken

In jeder Brücke wird eine Tabelle gespeichert, die die zuvor ermittelten Baumstrukturen der kürzesten Pfade enthält. Fig. 3 zeigt das Format einer derartigen Tabelle. Sie enthält einen Eintrag für jede Pfadbaumstruktur, die die betreffende Brücke kreuzt. Dieser Eintrag umfaßt: die LAN-Segmentnummer des Ziel- LAN-Segments der jeweiligen Pfadbaumstruktur; die LAN-Segmentnummer des nächsten LAN-Segments (Nachbarsegment), an die die Brücke einen Rahmen mit dem entsprechenden Ziel weiterleiten muß (nächster Sprung); und eine oder mehrere LAN-Segmentnummern der vorherigen LAN-Segmente, von denen die Rahmen für das betreffende Ziel empfangen werden köhnen (vorherige Sprünge). Daher enthalten die Tabellen nicht nur Nachrichtenlenkungsdaten für die Weiterleitung von Rahmen an ihr Ziel, sondern für jedes Ziel auch die Baumstruktur einschließlich der vorherigen LAN- Segmente.

b) Weiterleitungsrahmen (normale Ubertragung)

Für die Übertragung von Rahmen von einer Quelle zu einem Ziel in einem bekannten LAN-Segment enthalten die Nachrichtenlenkungsdaten RI lediglich die Nummer des Quell-LAN-Segments sowie die Nummer des Ziel-LAN-Segments (neben den Adressen der Quell- Benutzerdatenstation und der Ziel-Benutzerdatenstation). Die Rahmen müssen ein Feld mit den Nachrichtenlenkungsdaten in einem entsprechenden Format enthalten, wie dies im unteren Teil von Fig. 2 gezeigt ist: Er enthält drei Felder; eines mit Steuerdaten für die Nachrichtenlenkung und zwei andere Felder für eine Quell- bzw. Ziel-LAN-Segmentnummer. Das Steuerfeld für die Nachrichtenlenkung enthält neben mehreren Bits, die für die vorliegende Erfindung nicht von Bedeutung sind, ein einzelnes Bit (F/D) für die Unterscheidung zwischen Weiterleitungsrahmen (wie sie in diesem Abschnitt beschrieben werden) und Erkennungsrahmen (im nächsten Abschnitt beschrieben). Mit einem der Bits im Steuerfeld für die Nachrichtenlenkung kann die Übertragungsrichtung (DIR) angezeigt werden, wie in Abschnitt 9 näher erläutert wird.
Wenn eine Brücke einen Weiterleitungsrahmen erkennt, muß sie lediglich die Ziel-LAN-Segmentnummer überprüfen und ermitteln, ob ihre Nachrichtenlenkungstabelle diese Nummer enthält. Wenn sie sie enthält, wird der Rahmen an das nächste LAN-Segment weitergeleitet, das in dem betreffenden Tabelleneintrag angegeben ist (sofern der Eintrag als vorheriges LAN-Segment dasjenige Segment auflistet, von dem der Rahmen empfangen wurde); andernfalls wird der Rahmen von der Brücke verworfen. Auf diese Weise können Rahmen mit einem Mindestmaß an Nachrichtenlenkungsoperationen über Brücken übertragen werden.

c) Erkennungsrahmen (zur Ermittlung des Ziel-LAN-Segments)

Zur Ermittlung der Nummer des LAN-Segments, mit der eine gewünschte Ziel-Benutzerdatenstation verbunden ist, werden gemäß der Erfindung Erkennungsrahmen und eine entsprechende Verarbeitungsprozedur bereitgestellt. Wenn eine Quell-Benutzerdatenstation A einen Erkennungsrahmen sendet, gibt sie ihre Quelladresse und die Zieladresse des jeweiligen Kommunikationspartners B ein, setzt das F/D-Bit im Steuerfeld für die Nachrichtenlenkung auf "Erkennung" und gibt als Quell- und Ziel-LAN- Segmentnummern Nullen ein, um anzuzeigen, daß diese Felder leer sind. Anstelle von Nullen kann auch ein bestimmter Code (bzw. eine Nummer) oder der Wert eines bestimmten Bits verwendet werden, um anzuzeigen, daß ein Feld für die LAN-Segmentnummer leer ist.
Danach wird der Erkennungsrahmen vom Quell-LAN-Segment an jedes der anderen LAN-Segmente des Netzes unter Verwendung der Baumstruktur der kürzesten Pfade weitergeleitet, wobei das Quell- LAN-Segment die Wurzel der Baumstruktur ist (entspricht den "reverse path forwarding" [Weiterleitung in umgekehrter Pfadrichtung] aus dem in der Einleitung erwähnten Artikel von Dalal et. al.). Die Weiterleitung erfolgt mit den gespeicherten Nachrichtenlenkungstabellen der einzelnen Brücken, wie weiter unten ausführlicher beschrieben wird. Grundsätzlich geschieht folgendes: Alle Brücken, die mit dem Quell-LAN-Segment verbunden sind, schreiben die Quell-LAN-Segmentnummer sowie die Nummer des LAN-Segments, an das der Rahmen weitergeleitet wird. Alle anderen Brücken überschreiben einfach die Ziel-LAN- Segmentnummer mit der Nummer des Segments, an das sie den betreffenden Rahmen weiterleiten.
Im einzelnen werden in den Brücken die folgenden Operationen ausgeführt: In jeder ersten Brücke auf den Pfaden des Erkennungsrahmens (und seiner Kopien) wird die Quell-LAN-Segmentnummer in das betreffende Feld eingetragen: Die erste Brücke erkennt, daß das Feld leer ist (d. h. Nullen oder einen bestimmten Code enthält) und weiß, von welchem LAN-Segment sie diesen Rahmen empfangen hat. Die erste Brücke leitet eine Kopie des Erkennungsrahmens an alle LAN-Segmente weiter, die auf einem kürzesten Pfad ZUM Quell-LAN-Segment liegen, und trägt dabei die Segmentnummer des betreffenden vorherigen LAN-Segments in das Feld für das Ziel-LAN-Segment ein. Jede weitere Brücke, die den Rahmen erkennt, leitet eine Kopie davon an jedes vorhergehende LAN-Segment weiter, sofern es sich auf einen Pfad zur Quelle über die Brücke befindet, und ändert dabei die Ziel- LAN-Segmentnummer entsprechend (indem sie die Nummer des vorherigen LAN-Segments einträgt).
Auf diese Weise wird eine Kopie des Erkennungsrahmens genau einmal von jedem der (n-1) LAN-Segmente empfangen, wobei sich die jeweilige Segmentnummer in Feld für das Ziel-LAN-Segment befindet. Die Ziel-Benutzerdatenstation B empfängt den Rahmen, erkennt ihn als Erkennungsrahmen, vertauscht die Quell- und Zieladressen sowie die Quell- und Ziel-LAN-Segmentnummern, setzt das F/D-Steuerbit für die Nachrichtenlenkung auf "Weiterleiten" und sendet den Rahmen anschließend zurück an die Quell-Benutzerdatenstation A, von der er ursprünglich losgeschickt wurde. Die Benutzerdatenstation A speichert eine der empfangenen LAN-Segmentnummern, d. h. die Nummer, die bei ihrem Partner B als Ziel-LAN-Segmentnuminer eingegangen ist (und die die Quell-Benutzerdatenstation A nun als Quell-LAN-Segmentnummer zurückerhalten hat), als Ziel-LAN-Segmentnummer für die weitere Verwendung in Weiterleitungsrahmen (normale Übertragung) mit der betreffenden Adresse der Ziel-Benutzerdatenstation B und speichert außerdem die andere empfangene LAN- Segmentnummer als eiqene Quell-LAN-Segmentnummer (falls sie sie zuvor noch nicht kannte).
Diese Prozedur hat den Vorteil, daß der Erkennungsrahmen nur einmal an jedes LAN-Segment übertragen wird, während er bei ei- ner allgemeinen Rundsende-Prozedur mehrmals an seinem Ziel empfangen werden kann, wodurch spezielle Beseitigungs- und Auswahlschritte erforderlich werden und Übertragungskapazität des Netzes mit unnötigen Rahmenkopien belegt wird. Außerdem muß der Erkennungsrahmen nur zwei LAN-Segmentnummern enthalten (anstelle einer ganzen Folge wie bei der Ursprungslenkung).
Anstelle des Austauschs der Ziel- und Quellfelder kann der Empfänger eines Erkennungsrahmens auch ein Richtungsbit senden, wie in Abschnitt 9 kurz erläutert wird.

4) Prinzip der Baumstruktur der kürzesten Pfade

Das Prinzip der Baumstrukturen der kürzesten Pfade gemäß der Erfindung in den Fig. 4A, 4B und 4C für ein etwas weniger komplexes Netz als dasjenige aus Fig. 1 dargestellt. Wie Fig. 4A zeigt, enthält das Netz vier LAN-Segmente S1 ... S4, die über vier Brücken B1 ... B4 miteinander verbunden sind.
Die ausgewählten kürzesten Pfade zwischen allen LAN-Segmenten, die vier Baumstrukturen bilden, von denen jede ein LAN-Segment als Ziel (Wurzel der Baumstruktur) hat, sind in Fig. 4B abgebildet, die für jede Brücke alle kürzesten Pfade zeigt, die uber diese Brücke führen. Aus diesen Daten wird die Nachrichtenlenkungstabelle für jede einzelne Brücke abgeleitet. Die Brücke B2 soll hier als Beispiel dienen. Die folgenden Tabelleneinträge werden für B2 erstellt (wobei ein Pfad zum Segment "i" als P-Si gekennzeichnet wird):
Zur besseren Verdeutlichung der Baumstruktur wurden die kürzesten Pfade zum LAN-Segment S3 aus Fig. 4B noch einmal separat in Fig. 4C dargestellt. Ein Erkennungsrahmen von einer Benutzerdatenstation, die mit S3 verbunden ist, wird in umgekehrter Richtung über die Pfade dieser Baumstruktur weitergeleitet. Die Brücke B3, über die kein kürzester Pfad zu 53 führt, leitet keinen Erkennungsrahmen weiter, der S3 als Quelle hat (obwohl sie diese Erkennungsrahmen auf den LAN-Segmenten S2 und S4 erkennt). Eine ähnliche Baumstruktur der kürzesten Pfade kann für jedes andere LAN-Segment erzeugt werden.
In diesem Zusammenhang sind die folgenden Anmerkungen erforderlich: (1) Der Pfad zwischen zwei LAN-Segmenten muß nicht unbedingt für beide Richtungen gleich sein, d. h. der kürzeste Pfad von A nach B kann anders verlaufen als der kürzeste Pfad von B nach A. Ein Beispiel hierfür ist im nächsten Abschnitt enthalten. (2) Obwohl alle kürzesten Pfad ZU einem LAN-Segment (von allen anderen LAN-Segmenten) eine Baumstruktur bilden nüssen, müssen die Pfade VON einen LAN-Segment zu allen anderen LAN- Segmenten nicht unbedingt eine Baumstruktur aufweisen. Auf diese Weise lassen sich die kürzesten Pfade sehr viel leichter aufbauen. Für die einfachen Beispiele in dieser Beschreibung bilden die kürzesten Pfade jedoch in beide Richtungen Baumstrukturen.

5) Baumstruktur der kürzesten Pfade für das Beispielnetz

Die Tabellen 1 und 2 enthalten repräsentative Baumstrukturen der kürzesten Pfade und die sich daraus ergebenden Nachrichtenlenkungstabellen für das Beispielnetz aus Fig. 1. Jeder kürzeste Pfad wird als eine Folge von Nummern a-(b)-c-(d)-e dargestellt, wobei die Nummer ganz links das Quell- und die Nummer ganz rechts das Ziel-LAN-Segment ist; die in Klammern gesetzten Nummern sind die Brücken, die zu diesem Pfad gehören. Dabei ist zu beachten, daß zwischen LS-3 und LS-6 sowie zwischen LS-5 und LS-6 für jede Richtung ein anderer kürzester Pfad genannt ist (gekennzeichnet mit "#" und "%" in Tabelle 1).

a) Baumstruktur der kürzesten Pfade für ein LAN-Segment

Im Netz aus Fig. 1 ist eine der Baumstrukturen der kürzesten Pfade, diejenige für das LAN-Segment 2, durch gestrichelte Linien mit Pfeilen dargestellt (d. h. die Baumstruktur mit den kürzesten Pfaden von jedem LAN-Segment zu LS-2).

b) Verarbeitung von Erkennungsrahmen im Beispielnetz

Fig. 1 zeigt außerdem eine Quell-Benutzerdatenstation UT-A in LAN-Segment 2 sowie eine Ziel-Benutzerdatenstation UT-B im LAN- Segment 7, anhand derer die Verarbeitung des Erkennungsrahmens erläutert wird, der von der Datenstation A an die Datenstation B gesendet wird. Wie oben erwähnt, enthält der Erkennungsrahmen anfänglich die Adressen der Datenstationen A und B sowie zwei leere Felder für die LAN-Segmentnummer im Feld mit den Nachrichtenlenkungsdaten. Der Inhalt dieser Felder wird im folgenden für das Quell-LAN-Segment mit SRC/LS = x, für das Ziel-LAN- Segment mit DST/LS = y gekennzeichnet, wobei x und y, wie erforderlich, in den Brücken ausgetauscht werden.
Der Erkennungsrahmen wird von der Datenstation A auf LS-2 gegeben und von BR-1 empfangen, die anschließend SRC/LS = 2 einfügt, da es sich um einen Erkennungsrahmen mit einem leeren, vom LAN-Segment 2 empfangenen Quell-LAN-Feld handelt. (SRC/LS wird danach nicht mehr geändert.) BR-1 fügt danach DST/LS = 1 und DST/LS = 5 in zwei Kopien des Erkennungsrahmens ein und leitet sie an LS-1 und LS-5 weiter, da in ihrer Nachrichtenlenkungstabelle diese beiden LAN-Segmente als vorherige LAN- Segmente für das Ziel-LAN LS-2 aufgelistet sind.
Über LS-1 wird der Erkennungsrahmen in BR-2 empfangen, die DST/LS = 6 in eine Kopie des Rahmens einfügt und diesen Rahmen an LS-6 weiterleitet, da dieses LAN-Segment in ihrer Nachrichtenlenkungstabelle als vorheriges LAN-Segment für das Ziel-LAN LS-2 aufgelistet ist. Der Rahmen wird außerdem über LS-6 von BR-3 empfangen. Diese Brücke findet LS-2 nicht als Ziel in ihrer Nachrichtenlenkungstabelle und ignoriert daher den Erken- nungsrahmen. Auf diese Weise hat eine Kopie des Rahmens die LAN-Segmente LS-1 und LS-6 erreicht, wird jedoch von beiden verworfen, da keine Benutzerdatenstation den Rahmen empfängt.
Über LS-5 wird der Erkennungsrahmen mit DST/LS = 5 in den beiden Brücken BR-4 und BR-5 empfangen. BR-5 findet in ihrer Nachrichtenlenkungstabelle für das Ziel-LAN LS-2 einen Eintrag für LS-3 als vorheriges LAN-Segment. Daher schreibt sie in eine Kopie des Erkennungsrahmens DST/LS = 3 (und überschreibt den vorherigen Eintrag DST/LS = 5) und leitet den Rahmen weiter an LS- 3. Dort wird der Rahmen verworfen, da er von keiner Benutzerdatenstation empfangen wird und keine weitere Brücke mit LS-3 verbunden ist.
Die Nachrichtenlenkungstabelle der Brücke BR-4 listet die beiden LAN-Segmente LS-4 und LS-7 als vorherige LAN-Segmente für das Ziel-LAN LS-2 auf. Daher gibt BR-4 die Einträge DST/LS = 4 und DST/LS = 7 in die beiden Kopien des Erkennungsrahmens ein, den sie an die betreffenden LAN-Segmente weiterleitet In LS-4 wird der Rahmen aus denselben Gründen verworfen wie in LS-3. Die mit LS-7 verbundene Benutzerdatenstation B empfängt jedoch den Erkennungsrahmen, der zu diesem Zeitpunkt LS-2 als Quell- LAN-Segmentnummer und LS-7 als Ziel-LAN-Segmentnummer enthält. Die Datenstation B tauscht anschließend die beiden Adressen der Benutzerdatenstationen und die beiden LAN-Segmentnummern aus, wandelt den Rahmen in einen Weiterleitungsrahmen um und sendet ihn zurück an die Benutzerdatenstation A. Wenn er dort empfangen wird, wird LS-7 aus dem Rahmen ausgelesen und als Ziel-LAN- Segmentnummer in Verbindung mit der Datenstationsadresse B gespeichert. Wenn die Datenstation A bisher noch nicht wußte, mit welchem LAN-Segment sie verbunden war, speichert sie LS-2 (empfangen im zurückgesendeten Rahmen) als ihre eigene Quell- LAN-Segmentnummer für zukünftige Weiterleitungsrahmen.
Es muß darauf hingewiesen werden, daß der Erkennungsrahmen bei der Weiterleitung an LS-7 erneut von der Brücke BR-3 empfangen wird. Da LS-2 jedoch nicht in deren Nachrichtenlenkungstabelle als Ziel aufgelistet ist, wird die zweite Kopie des Erkennungsrahmens, die BR-3 erreicht, ebenfalls ignoriert.

c) Übertragung von Weiterleitungsrahmen

Wenn die Datenstation A danach einen Rahmen an die Datenstation B senden möchte, fügt sie LS-7 im Feld für das Ziel-LAN-Segment des Rahmens ein. BR-1 nimmt den an LS-2 weitergeleiteten Rahmen auf und leitet ihn weiter an LS-5, da dieses Segment in ihrer Nachrichtenlenkungstabelle als nächstes LAN-Segment für das Ziel-LAN LS-7 und LS-2 als vorheriges LAN-Segment aufgelistet ist. Anschließend erkennen die Brücken BR-4 und BR-5 den an LS- 5 weitergeleiteten Rahmen. BR--5 ignoriert den Rahmen, da für das Ziel LS-7 in ihrer Nachrichtenlenkungstabelle die Rahmen nur dann an LS-5 weitergeleitet werden, wenn sie von LS-3 kommen, was hier jedoch nicht der Fall ist. BR-4 leitet den Rahmen an LS-7 weiter, da dieses Segment als nächstes LAN-Segment für Rahmen aufgelistet ist, die von den vorherigen LAN-Segmenten LS-4 und LS-5 kommen (wobei in diesem Fall letzteres zutrifft). In LS-7 wird der Rahmen danach von seiner tatsächlichen Zieldatenstation B empfangen. Auch die Brücke BR-3 erkennt den Rahmen, der an LS-7 weitergeleitet wird. Aus ihrer Nachrichtenlenkungstabelle geht jedoch hervor, daß Rahmen für LS-7 nur dann (an LS-7) weitergeleitet werden sollen, wenn sie von einen vorherigen LAN-Segment LS-6 kommen. Dies ist hier nicht der Fall, weshalb der Rahmen von BR-3 ignoriert wird.

7) Regeln für die Verarbeitung von Rahmen in Brücken

a) Erkenne Ankunft des Rahmens und gewinne Nachrichtenlenkungsdaten.
b) Ermittle, ob es sich um einen ERKENNUNGS-Rahmen oder einen WEITERLEITUNGS-Rahmen handelt (überprüfe entsprechendes Anzeigebit F/D in Steuerfeld für die Nachrichtemlenkung).
c1) Bei ERKENNUNGS-Rahmen:
c1a) Erkenne, ob das Feld für das Quell-LAN-Segment leer ist.
- Wenn es leer ist: Füge LAN-Segmentnummer des Eingangs-LAN-Segments ein, von dem der Erkennungsrahmen empfangen wurde.
- Wenn es nicht leer ist: Andere Inhalt des Felds für das Quell-LAN-Segment nicht.
c1b) Prüfe, ob die LAN-Segmentnummer im Feld für das Quell-LAN-Segment als Ziel-LAN-Segmentnummer in einem Eintrag der lokalen Nachrichtenlenkungstabelle enthalten ist und ob dieser Eintrag eine nächste LAN- Segmentnummer enthält, die mit dem Eingangs-LAN- Segment übereinstimmt, von dem der Erkennungsrahmen empfangen wurde.
- Wenn nicht: Verwirf Erkennungsrahmen.
- Wenn ja: Kopiere Erkennungsrahmen für jede vorherige LAN-Segmentnummer in dem betreffenden Eintrag; füge die entsprechende vorherige LAN-Segmentnummer als Ziel-LAN-Segmentnummer in die Kopie ein und übertrage den Erkennungsrahmen zum entsprechenden LAN-Segment als Ausgabe.
c2) Bei WEITERLEITUNGS-Rahmen:
Prüfe, ob die Ziel-LAN-Segmentnummer im Weiterleitungsrahmen als Ziel-LAN-Segmentnummer in einem Eintrag der lokalen Nachrichtenlenkungstabelle enthalten ist und ob der Weiterleitungsrahmen von einem Eingangs-LAN-Segment, das in demselben Eintrag als vorheriges LAN-Segment aufgelistet ist, empfangen wurde.
Wenn nein: Verwirf Weiterleitungsrahmen.
- Wenn ja: Übertrage Weiterleitungsrahmen an das LAN- Segment, das in dem betreffenden Eintrag als nächstes LAN-Segment aufgelistet ist.

8) Beispiel einer Brücke unter Verwendung der Nachrichtenlenkungsprinzipien der Erfindung

Fig. 5 ist ein Blockdiagramm einer möglichen Brückenrealisierung und zeigt die Funktionseinheiten für die Ausführung der Erfindung. Die Beispielbrücke ist eine Brücke mit drei Anschlüssen, d. h. sie verbindet drei angeschlossene LAN-Segmente LS-A, LS-B und LS-C (11, 13, 15) direkt miteinander. Für jedes verbundene LAN-Segment LS-i verfügt die Brücke über einen Eingangspuffer 17-i und einen Ausgangspuffer 19-i. Jeder Eingangspuffer ist über ein Gatter 21-i mit einem gemeinsamen Eingangsbus 23 verbunden, und jeder Ausgangspuffer ist über ein Gatter 25-i mit einem gemeinsamen Ausgangsbus 27 verbunden. Das Prozessormittel 29 für die Nachrichtenlenkungsfelder wird bereitgestellt, um (a) die Nachrichtenlenkungsdaten der ankommenden Rahmen zu überprüfen, die gemäß den vorgegebenen Regeln (die in Abschnitt 7 erläutert wurden und in das Prozessormittel integriert sind) über den Eingangsbus an das Prozessormittel übertragen werden, und um (b) entweder den betreffenden Rahmen von einem LAN-Segment über die Ein-/Ausgangsbusse und die entsprechenden Gatter an ein oder beide andere LAN-Segmente weiterzuleiten, den Inhalt des Nachrichtenlenkungsfelds des Rahmens ggf. zu ändern oder den betreffenden, in einem Eingangspuffer gespeicherten Rahmen zu verwerfen.
Das Speichermittel 31 wird für die Nachrichtenlenkungstabelle bereitgestellt und ist mit dem Prozessormittel 29 für die Nachrichtenlenkungsfelder verbunden. Die Nachrichtenlenkungstabelle wird über einen Eingang 33 vom Netzmanagement im die Brücke geladen, wenn die Baumstrukturen der kürzesten Pfade ermittelt wurden und wenn eine geeignete Teilmenge als Nachrichtenlenkungstabelle für die betreffende Brücke vorbereitet wurde (siehe oben). Das Steuernittel 35, das ebenfalls mit dem Prozessormittel 29 für die Nachrichtenlenkungsfelder verbunden ist, sendet und empfängt Steuersignale an bzw. von den Gattern 19-i/25-i und den Eingangspuffern 17-i. Die entsprechenden Steuersignale sind i-ACT, das die Verfügbarkeit eines empfangenen Rahmens in einem Eingangspuffer anzeigt, und i(IN) sowie i(OUT) zum Durchschalten des jeweiligen Pufferinhalts an/von den Ein-/Ausgangsbussen.
Fig. 6 zeigt Mittel, mit denen Erkennungsrahmen in einer Brücke getestet und modifiziert werden. Das Feld mit den Nachrichtenlenkungsdaten eines angekommenen Rahmens wird in den Registermitteln 37 gespeichert. Die jeweilige Nummer des Eingangs-LAN- Segments, von dem der Rahmen empfangen wurde, wird in den Registermitteln 39 gespeichert. Testmittel 41 erkennen, ob es sich um einen Erkennungsrahmen (F/D = 1) handelt und ob das Quell- LS-Feld nur Nullen enthält. Wenn dies der Fall ist, wird die Eingangs-LS-Nummer in das Quell-LS-Feld des Rahmens geladen.
Wenn der Rahmen ein Erkennungsrahmen (F/D = 1) ist, wird danach eine Folgesteuerung 43 gestartet, die Einträge aus der Nachrichtenlenkungstabelle der Brücke sequentiell ausliest und vergleicht. In den Vergleichsmitteln 46 wird für jeden Eintrag der Nachrichtenlenkungstabelle getestet, ob die Ziel-LS-Nummer in der Tabelle mit der Quell-LS-Nummer des Rahmens übereinstimmt und ob die Nummer für das nächste LAN-Segment in dem Tabelleneintrag mit der Eingangs-LS-Nummer des betreffenden Rahmens übereinstimmt. Wenn dies der Fall ist, werden die einzelnen Nummern für das vorherige LAN-Segment in dem Tabelleneintrag sequentiell in die Registermittel 47 eingetragen und in das Ziel-LS-Feld des Erkennungsrahmens geladen. Anschließend wird der Erkennungsrahmen an ein Ausgangs-LAN-Segment weitergeleitet, wobei der Inhalt des Nachrichtenlenkungsfelds den Daten in den Registermitteln 37 entspricht, das durch den Inhalt der Registermittel 47 angegeben wird, und dessen Nummer nun als Ziel- LS-Nummer im Nachrichtenlenkungsfeld des Rahmens enthalten ist.

9) Alternativen / Weitere Merkmale

a) Kompatibilität mit bestehenden Nachrichtenlenkungsprotokollen

In der obigen Beschreibung wurde davon ausgegangen, daß das Feld mit den Nachrichtenlenkungsdaten eines jeden Rahmens neben den Steuerdaten für die Nachrichtenlenkung lediglich zwei weitere Felder für LAN-Segmentnummern (Quelle und Ziel) enthält. Um die Kompatibilität mit Protokollen zu gewährleisten, die Felder mit Nachrichtenlenkungsdaten variabler Länge vorsehen, wie dies z. B. bei Systemen mit Ursprungslenkung der Fall ist, ist die folgende Variante möglich: Die Längenanzeige im Steuerfeld für die Nachrichtenlenkung, die die tatsächliche Länge (die Anzahl der Bytes für die LAN-Segmentnummern) der Nachrichtenlenkungsdaten angeben, wird auf einen konstanten Wert gesetzt, der zwei Feldern mit der LAN-Segmentnummer (vier Bytes) entspricht.
Auf diese Weise kann die vorliegende Erfindung für die Brücken eines Netzes verwendet werden, ohne daß die Benutzerdatenstationen geändert werden müssen (diese können weiterhin das Protokoll mit Feldern einer variablen Länge verwenden, wobei dennoch die Nachrichtenlenkungsdaten auf zwei LAN-Segmentnummern beschränkt würden).
Wie in den Abschnitten 5a und 5b beschrieben wurde und aus Fig. 2 hervorgeht, kann das Steuerfeld für die Nachrichtenlenkung ein Richtungsbit (DIR) enthalten (wie dies z. B. bei Systemen mit Ursprungslenkung der Fall ist). Wenn dieses Bit auf "1" gesetzt ist, veranlaßt es, daß alle Brücken und Datenstationen die Quell- und Zielfelder in umgekehrter Reihenfolge verwenden, so daß in einer Datenstation, die einen empfangenen Rahmen (z. B. einen Erkennungsrahmen) an seinen Sender zurücküberträgt, kein Vertauschen oder Austauschen von Quell und Ziel erforderlich ist. Auch läßt sich so vermeiden, daß bei Verwendung der Erfindung die Datenstationen geändert werden müssen.

b) Erzeugen von Brücken-Nachrichtenlenkungstabellen in Netzen mit Baumstruktur

Wenn das Netz an sich eine Baumstruktur aufweist, müssen die Nachrichtenlenkungstabellen nicht im voraus aufgebaut werden, sondern können in einer Lernprozedur erzeugt werden. (So wird z. B. das Netz aus Fig. 1 zu einem reinen Baumstrukturnetz, wenn die Brücke BR-3 weggelassen wird.) Um die Nachrichtenlenkungstabellen in einem solchen System durch eine Lernprozedur aufzubauen, müssen die Brücken alle empfangenen Weiterleitungs- und Erkennungsrahmen überprüfen, um Daten darüber zu erhalten, welche LAN-Segmente, die mit der Brücke verbunden sind, von welchen Quell-LAN-Segmenten Rahmen erhalten.
Diese Lernprozedur hat Annlichkeit mit derjenigen, die im Artikel von F. Backes über Lernbrücken beschrieben wird, mit der wichtigen Ausnahme, daß bei Lernbrücken eine große Anzahl von Datenstationsadressen erforderlich ist, während bei einem System gemäß der vorliegenden Erfindung lediglich LAN- Segmentbezeichner erfaßt werden müssen, deren Anzahl nur einen Bruchteil der Anzahl der Datenstationsadressen beträgt.

c) Server für die Erkennungsprozedur

Alternativ dazu, daß jede Benutzerdatenstation ihre eigenen Erkennungsrahmen an die betreffenden Zieldatenstationen sendet, kann dies auch durch einen oder mehrere Server des Systems erfolgen, z. B. durch einen Server pro LAN-Segment. In diesem Fall sendet eine Datenstation ihre Anforderung der LAN- Segmentnummer einer Zieldatenstation an den Server ihres eigenen LAN-Segments. Der Server (der wie in Abschnitt 3c beschneben als Quelldatenstation dient) sendet einen Erkennungsrahmen und überträgt später die Ziel-LAN-Segmentnummer (und ggf. die Quell-LAN-Segmentnummer) an den Anforderer. Wenn der Server über eine Tabelle mit Adressen von Benutzerdatenstationen und den betreffenden LAN-Segmentnummern verfügt, die er in einer früheren Erkennungsoperation erhalten hat, kann er auf eine Vielzahl von Erkennungsanforderungen reagieren, indem er einfach in seiner Tabelle nachsieht, dort eine zuvor erhaltene Ziel-LAN-Segmentnummer findet und so kreisende Erkennungsrahmen unnötig macht. Nur wenn die Tabelle nicht die Zielsegmentnummer für eine Datenstationsadresse enthält, muß der Server tatsächlich einen Erkennungsrahmen senden. Tabelle 1 Baumstrukturen der kürzesten Pfade für das Netz aus Fig. 1 Tabelle 2 (A) Nachrichtenlenkungstabellen für Brücken im Netz aus Fig. 1 Tabelle 2 (B) Nachrichtenlenkungstabellen für Brücken im Netz aus Fig. 1

Claims

1. Verfahren für die Nachrichtenlenkung von Rahmen von einer Quell- zu einer Zieldatenstation (UT, UT-A, UT-B) über ein Netz, das aus Netzsegmenten (LS-1 ... LS-7) besteht, die über Brücken (BR-1 ... BR-5) miteinander verbunden sind, wobei jedes Netzsegment über einen eindeutigen Bezeichner verfügt und jeder Rahmen einen Bezeichner für ein Zielnetzsegment enthält, wobei das Verfahren durch die folgenden Schritte gekennzeichnet ist:

- Festlegung eines eindeutigen Pfads (Fig. 1, Tabelle 1) von jedem Netzsegment zu jedem anderen Netzsegment,

- Bestimmung einer Pfadbaumstruktur (Fig. 1, Tabelle 1) für jedes Netzsegment als Zielnetzsegment, die jeden der vorgegebenen eindeutigen Pfade zu dem Zielnetzsegment umfaßt,

- In jeder Brücke Speicherung einer Nachrichtenlenkungstabelle (Fig. 3, Tabelle 2) mit einem Eintrag für jede Pfadbaumstruktur, deren Bestandteil die Brücke bildet, wobei jeder Eintrag für die betreffende Pfadbaumstruktur Bezeichner für das Zielnetzsegment, für das nächste Netzsegment und für alle vorherigen Netzsegmente der Pfadbaumstruktur enthält,

- in jeder Brücke Testen eines jeden Eintrags in der lokalen Nachrichtenlenkungstabelle daraufhin, ob der Bezeichner für das Zielnetzsegment in einem empfangenen Rahmen mit dem Bezeichner für das Zielnetzsegment in dem Eintrag übereinstimmt und ob einer der Bezeichner für vorherige Netzsegmente in dem Eintrag mit dem Eingangsnetzsegment übereinstimmt, von dem der Übertragungsrahmen empfangen wurde, und

- bei positiven Testergebnis Weiterleitung des betreffenden Übertragungsrahmen an das Netzsegment, das mit dem Bezeichner für das nächste Netzsegment in dem Eintrag übereinstimmt, oder

- bei negativem Testergebnis Verwerfen des Übertragungsrahmens.

2. Verfahren nach Anspruch 1, das die folgenden Schritte für die Ableitung der Nachrichtenlenkungsdaten umfaßt, die für die Rahmenübertragung zwischen der Quell- und der Zieldatenstation erforderlich sind, wobei jede der Datenstationen über eine eindeutige Adresse verfügt:

- Übertragung eines Erkennungsrahmens (Fig. 2) von der Quelldatenstation (UT-A), der die Adresse der Quelldatenstation, die Adresse der Zieldatenstation sowie zwei leere Felder für einen Bezeichner eines Quellnetzsegments bzw. einen Bezeichner eines Zielnetzsegments enthält,

- in jeder Brücke (BR-1 ... BR-5) Empfangen eines Erkennungsrahmens mit einen leeren Feld für den Bezeichner des Quellnetzsegments, wobei zuerst der Bezeichner des Netzsegments in das Feld eingefügt wird, von dem der Erkennungsrahmen empfangen wurde;

- in jeder Brücke Testen eines jeden Eintrags der lokalen Nachrichtenlenkungstabelle (Fig. 3, Tabelle 2) daraufhin, ob der Bezeichner für das Quellnetzsegment in dem Erkennungsrahmen mit dem Bezeichner für das Zielnetzsegment in dem Eintrag übereinstimmt und ob der Bezeichner für das nächste Segment in dem Eintrag mit den Eingangsnetzsegment übereinstimmt, von dem der Erkennungsrahmen empfangen wurde, und

- bei positivem Testergebnis für jeden Bezeichner eines vorherigen Netzsegments, der in dem Eintrag enthalten ist, Einfügen dieses Bezeichners für das vorherige Netzsegment in das Feld für das Zielnetzsegment des Erkennungsrahmens und Weiterleitung einer Kopie des Erkennungsrahmens an das Netzsegment, das dem eingefügten Netzsegmentbezeichner entspricht, oder

- bei negativem Testergebnis Verwerfen des Erkennungsrahmens,

- Empfangen des Erkennungsrahmens in der Zieldatenstation (UT-B), der den Bezeichner des Quellnetzsegments für die Quelldatenstation sowie den Bezeichner des Zielnetzsegments für die Zieldatenstation enthält, und

- Rückübertragung des Bezeichners für das Quellnetzsegment und des Bezeichners für das Zielnetzsegment von der Zieldatenstation an die Quelldatenstation.

3. Brückenvorrichtung in einem Netz, das aus Netzsegmenten besteht, die über Brücken miteinander verbunden sind, wobei jedes Netzsegment über einen eindeutigen Bezeichner verfügt und Datenstationen umfaßt, die mit den Netzsegmenten verbunden sind, wobei in dem besagten Netz für jedes Netzsegnent eine Pfadbaumstruktur als Ziel bestimmt wird, wobei die Pfadbaumstruktur einen einzigen Pfad von jedem anderen Netzsegment zu dem betreffenden Zielnetzsegment enthält und wobei die Brückenvorrichtung folgendes umfaßt:

- Mittel (31) für die Speicherung einer Nachrichtenlenkungstabelle (Fig. 3) mit einem Eintrag für jede Pfadbaumstruktur, deren Bestandteil die Brücke bildet, wobei jeder Eintrag für die betreffende Pfadbaumstruktur Bezeichner für das Zielnetzsegment, für das nächste Netzsegment und für alle vorherigen Netzsegmente der Pfadbaumstruktur auflistet,

- Mittel (29, 35) für die Verarbeitung der Nachrichtenlenkungsdaten, die in dem empfangenen Rahmen enthalten sind, und für die Erzeugung von Steuersignalen als Reaktion auf die Nachrichtenlenkungsdaten und auf den Inhalt eines jeden Eintrags der Nachrichtenlenkungstabelle, einschließlich Mitteln für das Testen eines jeden Tabelleneintrags daraufhin, ob der Zielnetzbezeichner in einem empfangenen Rahmen mit dem Zielnetzbezeichner in dem Eintrag übereinstimmt und ob ein Bezeichner für ein vorheriges Netzsegment in dem Eintrag mit den Eingangsnetzsegment übereinstimmt, von dem der Rahmen empfangen wurde, und

- Mittel (21, 23, 25, 27) für die Weiterleitung, sofern der Test positiv ausfällt, des betreffenden Rahmens als Reaktion auf die Steuersignale an das Netzsegment (13, 15), das dem Bezeichner für das nächste Netzsegment in dem Eintrag entspricht, einschließlich Mitteln für das Verwerfen des Rahmens, falls das Testergebnis negativ ausfällt.

4. Brückenvorrichtung nach Anspruch 3, die umfaßt:

- Mittel (37, 39, 45) für den Vergleich der Segmentbezeichner eines Eintrags der Tabelle mit einem Segmentbezeichner, der in dem Rahmen empfangen wurde, sowie mit einem Segmentbezeichner, der dem Eingangsnetzsegment entspricht, von dem der Rahmen empfangen wurde, sowie für die Erzeugung eines Weiterleitungssteuersignals, und

- Mittel (47), die auf das Weiterleitungssteuersignal ansprechen, für die Weiterleitung eines Segmentbezeichners von dem Tabelleneintrag zu den Mitteln (35) für die Steuersignalerzeugung, um so das Ausgangsnetzsegment zu ermitteln, an das der Rahmen weitergeleitet werden soll.

5. Brückenvorrichtung nach Anspruch 3, die umfaßt:

-Registermittel (37) für das Speichern des Inhalts der beiden Felder für die Netzsegmentbezeichner, der als Nachrichtenlenkungsdaten in einem empfangenen Rahmen enthalten ist,

- Mittel (29, 35) für das Erzeugen von Steuersignalen für die Nachrichtenlenkung als Reaktion auf Nachrichtenlenkungsdaten in einen empfangenen Rahmen und auf den Inhalt der Nachrichtenlenkungstabelle,

- Mittel (37, 39, 43, 45) für das Vergleichen von Segmentbezeichnern aus jedem Eintrag der Nachrichtenlenkungstabelle mit einem Netzsegmentbezeichner, der in dem Rahmen empfangen wurde, und mit einem Bezeichner, der den Eingangsnetzsegment entspricht, von dem der Rahmen empfangen wurde, sowie für die Erzeugung eines Weiterleitungssteuersignals,

- Mittel (47), die auf das Weiterleitungssteuersignal ansprechen, für die Weiterleitung eines Segmentbezeichners von dem Eintrag der Nachrichtenlenkungstabelle zu den Mitteln (29, 35) für die Erzeugung eines Weiterleitungssteuersignals, um so das Ausgangsnetzsegment zu ermitteln, an das der Rahmen weitergeleitet werden soll, und

- Mittel (21, 23, 25, 27) für die Übertragung eines Rahmens als Reaktion auf die Nachrichtenlenkungssteuersignale von einem beliebigen der Netzsegmente (11), die mit der Brücke verbunden sind, zu einem beliebigen anderen (13, 15) der verbundenen Netzsegmente.

6. Brückenvorrichtung nach Anspruch 3, die umfaßt:

- Mittel (41) für die Erkennung des Vorhandenseins eines Erkennungsrahmens,

- Mittel (39, 41) für die Erkennung, ob der Erkennungsrahmen ein leeres Feld für den Zielnetzsegmentbezeichner enthält, und für die Einfügung des Bezeichners für das Eingangsnetzsegment, von dem der Erkennungsrahmen empfangen wurde, in das Feld,

- Mittel (43, 45) für das sequentiell für jeden Eintrag der Nachrichtenlenkungstabelle durchgeführte Vergleichen des Zielsegmentbezeichners des Eintrags mit dem Quellnetzsegmentbezeichner, der in einem Erkennungsrahmen enthalten ist, des Bezeichners für das nächste Segment des Eintrags mit dem Segmentbezeichner des Eingangsnetzes, von dem der Erkennungsrahmen empfangen wurde, sowie für die Erzeugung eines Weiterleitungssteuersignals, und

- Mittel (43, 47) für das sequentielle Einfügen - als Reaktion auf das Weiterleitungssteuersignal - eines jeden Bezeichners für ein vorheriges Segment eines Eintrags der Nachrichtenlenkungstabelle in das Feld für den Zielnetzsegmentbezeichner des Erkennungsrahmens und für die Bereitstellung des Segmentbezeichners an die Mittel (29, 35) für die Erzeugung des Nachrichtenlenkungssteuersignals, um so eine Kopie des Erkennungsrahmens an das Ausgangsnetzsegment weiterzuleiten, das dem eingefügten Bezeichner für das vorherige Segment entspricht.

7. Netz für die Weiterleitung von Rahmen von einer Quell- zu einer Zieldatenstation (UT, UT-A, UT-B) gemäß dem Verfahren aus Anspruch 1 oder 2, wobei das Netz aus Netzsegmenten (LS-1 ... LS-7) besteht, die über Brücken (BR-1 ... BR-5) nach einem beliebigen der Ansprüche 3 bis 6 miteinander verbunden sind, wobei jedes Netzsegment über einen eindeutigen Bezeichner verfügt und Datenstationen (UT, UT- A, UT-B) umfaßt, die mit dem Netzsegment verbunden sind, worin für jedes Netzsegment als Ziel eine Pfadbaumstruktur (Fig. 1, Tabelle 1) bestimmt wird, wobei die Pfadbaumstruktur einen einzigen Pfad von jeden Quellnetzsegment zu dem betreffenden Zielnetzsegment umfaßt.