DE69429983T2

DE69429983T2 - Datenübertragungsnetz und Verfahren zum Betreiben des Netzes

Info

Publication number: DE69429983T2
Application number: DE69429983T
Authority: DE
Inventors: Olivier Bertin; Jean-Paul Chobert; Alain Pruvost
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-05-25
Filing date: 1994-05-25
Publication date: 2002-10-17
Anticipated expiration: 2014-05-26
Also published as: EP0684716A1; JP3149332B2; JPH07327042A; US5606669A; DE69429983D1; EP0684716B1

Description

Der Erfindung zugrundeliegender allgemeiner Stand der Technik

Die vorliegende Erfindung betrifft im allgemeinen Datenübertragungsnetze, und im einzelnen eine sogenannte baumüberbrückungsorganisierte Architektur (Spanning Tree - STB), die einen Netzwerkbetrieb in einer Anzahl Situationen, einschließlich einer Schnellpfadbestimmung und einer Schnell-STB-Wiederherstellung in optimaler Weise ermöglicht, sowie ein Verfahren zur Ausführung derselben. Th weiteren Einzelheiten behandelt die Erfindung ein Verfahren und Mittel zum dynamischen organisieren jeder STB-Knotenarchitekur, so, daß sie die Baum-Topologie voll wiedergibt, sowie ein Verfahren und Mittel zum Verwenden der organisierten Knotenarchitektur zum Implementieren von Netzwerk-Operationen wie z. B. Schnellpfadbestimmung oder Schnell-STB- Wiederherstellung. Aber die spezifische Knotenorganisation ist auch in einer Anzahl anderer Situationen, die bei herkömmlichem Betrieb der Datenübertragungsnetze auftreten können und auch wirklich auftreten, sehr nützlich.
Das Europäische Patent 0 404 423 beschreibt ein vermaschtes örtliches Netzwerk (LAN), das ein automatisches Paketschalten und Wegbestimmen zwischen Host-Computern vorsieht, die an das Netzwerk gekoppelt sind. Das Netzwerk weist eine Vielzahl nichtblockierender Durchdrückschalter auf, die jeweils in der Lage sind, gleichzeitig eine Vielzahl von Datenpaketen einen Bestimmungsweg zu führen. Wenn immer ein neuer Schalter oder ein neues Link zum Netzwerk hinzugefügt wird, und wenn immer ein Schalter oder ein Link gestört ist, konfigurieren die Schalter im Netzwerk automatisch das Netzwerk um durch Neuberechnen des Satzes der zulässigen Pfade durch das Netzwerk.
Fig. 1 illustriert ein Datennetz, enthaltend eine Anzahl Knoten A bis Z.
Wie in der Figur dargestellt, sind die Netzwerkknoten miteinander durch Links verschaltet zum Ermöglichen der Übertragung von Datenpaketen und sonstigen Signalen, wie z. B. Steuerdaten, zwischen den Knoten. Jedes Netzwerk-Link verbindet zwei benachbarte Knoten. Vorzugsweise enthält jedes Link des Netzwerks in Wirklichkeit ein Paar unidirektionale Links oder Link-Segmente; und jedes solches Link-Paar kann durch ein einziges Übertragungsmedium, wie z. B. eine Optikfaser, oder durch zwei getrennte Übertragungsmedien, wie z. B. ein Paar Koaxialkabel oder Optikfasern, realisiert werden.
Offensichtlich ermöglicht eine so organisierte Netzwerkstruktur das Übermitteln von Daten zwischen jedem beliebigen Knotenpaar, bestehend aus einem sogenannten Quellknoten und einem sogenannten Bestimmungsknoten. Diese Quellen- und Bestimmungsbezeichnungen sind natürlich je nach Verkehrsrichtung dynamisch veränderbar, was die bereits komplexe Netzwerkarchitektur, wie sie in der Figur dargestellt ist, noch komplexer macht, um die Komplexität des Netzwerkbetriebs als Daten- und Steuerverkehr ausdrücken zu können. Zum Beispiel können Daten- oder Verkehrssteuerpakete auf Zufallsrouten in einem schleifenverbundenen Knotensatz geschickt werden, was offensichtlich den Durchsatz des Netzes vermindern würde, oder allgemein gesagt, den Verkehr stören würde.
Eine optimierte Netzwerk-Neuorganistion, die in bestimmten Fällen auf den Steuerverkehr konzentriert sein kann, ist auf dem Stand der Technik bereits geoffenbart, wobei diese Neuorganisation zu einer sogenannten Baumüberbrückungs- Architektur (STB architecture) führt.
In Fig. 2 dargestellt ist ein STB-Baum, das ist eine optimale Struktur, die eine wirksame Übertragung einer Meldung ermöglicht (z. B. Daten- oder Steuermeldung) von und zu einem beliebigen Knoten des Übertragungsnetzes. Der STB-Baum enthält die Mindestanzahl Links, so daß das Netzwerk noch immer verbunden ist und dOch keine Zyklen oder Schleifen aufweist. Damit ist es ein gutes Medium zum Senden Von Daten- und/oder Steuerpaketen. Die Links können betrachtet werden als sich von einem Knoten aus nach außen erstreckend (d. i. Knoten A in Fig. 2), der als Stammknoten bezeichnet wird. Die Außenknoten des STB-Baums (z. B. Knoten F, Knoten G, Knoten K, Knoten L, Knoten N, Knoten Z, Knoten T, Knoten W und Knoten Y) werden als Astknoten bezeichnet. Die Knoten zwischen den Astknoten und dem Stammknoten werden als Zwischenknoten bezeichnet. Hier muß darauf hingewiesen werden, daß in der Struktur des Netzwerks laut Fig. 2 jeder beliebige Knoten A bis Z leicht als Stammknoten des STB-Baums in einer spezifischen Baumdarstellung je nach Fall betrachtet werden kann.
In einer solchen Baumstruktur wird der Stammknoten, der als solcher bekannt ist, von den anderen Netzknoten, d. i. Kind- Knoten, durch ein sogenanntes Stammknoteneigenschaftsverfahren (Rootship procedure) bezeichnet, das sowohl im Netzwerk verteilte Hardware- als auch Softwaremittel benutzt. Die Links, die Knotenpaare des STB-Baums verbinden, werden manchmal auch "Verbindungslinien" (edges) genannt.
Der Stammknoten wird auch als Eltern-Knoten der Knoten bezeichnet, die direkt mit ihm verbunden sind, und alle Knoten, die mit dem Stammknoten direkt verbunden sind, werden als Kinderknoten des Stammknoten bezeichnet. Ebenso wird der Baumstruktur entlang in Richtung nach außen jeder Knoten, der mit einem anderen Knoten direkt verbunden ist, als Kind- Knoten des letzteren bezeichnet, und der letztere Knoten wird als Eltern-Knoten des vorherigen bezeichnet. So ist z. B. in der STB-Baumstruktur gemäß Fig. 2 der Knoten A der Elter der Knoten B, H und M; Knoten B ist der Elter des Knotens C; Knoten C ist der Elter der Knoten D und G. Umgekehrt sind die Knoten D und G Kinder-Knoten des Knoten C. Mit anderen Worten, in einer STB-Baumstruktur ist der Stammknoten der einzige Knoten, der keinen Eltern-Knoten hat. Abgesehen von diesem Kennzeichnen braucht der Stammknoten kaum ein anderes Hardware- oder Softwaremittel, das einem anderen Knoten des STB-Baums nicht zur Verfügung stünde. Folglich kann jeder der Knoten A bis Z zu einem gegebenen Moment als Stammknoten arbeiten.
Offensichtlich können unter normalen Betriebsbedingungen verschiedene Situationen eintreten, die eine Umorganisation des STB-Baums erforderlich machen. Z. B. kann ein neues Link zum Optimieren des Verkehrs eingesetzt werden müssen, wie z. B. der Austausch eines langsamen oder geringleistungsfähigen Link durch ein schnelleres Link oder eines höherer Kapazität, oder nur zum Setzen einer neuen Verbindung zwischen Knoten. Ein solcher Link-Austausch müßte natürlich möglichst schnell wieder betriebsbereit sein, um Verkehrsverstopfungen oder eine noch schlimmere Situation zu vermeiden.
Nehmen wir an, daß ein an einen Knoten angeschlossenes Terminal Zugriff auf eine CPU (Central Processing Unit) fordert, die mit einem anderen Knoten verbunden ist, so sollte auch in diesem Fall das System ein einfaches und schnelles Pfadwahlverfahren zwischen diesen beiden Knoten des Beförderungsnetzes unter Verwendung des STB-Baums vorsehen. Wieder gilt, je schneller der Pfad gesetzt wird, desto besser ist es im Hinblick auf den Netzbetrieb.
Zusätzlich könnte angesichts der Bedeutung des Verkehrs in modernen Datennetzwerken jede Störung (z. B. Link-Störung) einen Teil des STB-Baums isolieren und den gesamten Verkehr darin lahmlegen, wenn nicht, noch schlimmer, der gesamte Datennetzbetrieb lahmgelegt würde. Solche Situationen wurden auf dem Stand der Technik bereits in Betracht gezogen, aber die vorgeschlagenen Lösungen werden nicht als voll zufriedenstellend angesehen im Hinblick auf die Zeit, die zum Umorganisieren des BST-Baums erforderlich ist. Man versteht offensichtlich, wie dramatisch die Folgen einer Link-Störung sein können, nur durch Annahme, daß eine neue Link-Störung eintreten könnte, bevor die erste behoben ist. Dann würde der Verkehr vollständig zusammenbrechen, was sich bei den Verlusten (z. B. Geldverlusten) verheerend auswirken könnte.
Man stelle sich nur diese Situation in einer Multimedia- Umgebung vor.
Dementsprechend würde eine gute Lösung dieser Probleme und noch weiterer, insbesondere wenn sie keine teueren Mittel zur Implementierung erfordern, bei der Datenverkehrsindustrie und auch bei den Anwendern sehr willkommen sein. Das ist genau das, worauf die vorliegende Erfindung abzielt.

Aufgaben der Erfindung

Eine Aufgabe der vorliegenden Erfindung ist das Vorsehen einer Datenübertragungs-Architektur und insbesondere einer BST-Baum-Architektur, die einen schnellen BST-Baum, einen Knotenbetrieb oder eine Baumumorganisation unter den meisteN Betriebsbedingungen ermöglicht.
Eine weitere Aufgabe der vorliegenden Erfindung ist das Vorsehen einer Knotenorganisation und entsprechender Mittel zum Ermöglichen der Selbsteinstellung der Knoten nach einer Baum-Umänderung.
Noch eine weitere Aufgabe der vorliegenden Erfindung ist das Vorsehen eines Verfahrens und Mittels zum Schnellfestlegen eines angeforderteN Pfades zwischen zwei Knoten eines BST- Baums.
Noch eine Aufgabe der vorliegenden Erfindung ist das Vorsehen eines Verfahrens und Mittels zum Umorganisieren des BST-Baums unter einer Reihe herkömmlicher Betriebsbedingungen, einschließlich des Falles einer Link-Störung, und das angemessen schnell.
Noch eine weitere Aufgabe der vorliegenden Erfindung ist das Vorsehen eines Verfahrens und entsprechender Mittel zum Ermöglichen einer schnellen BST-Baum-Wiederherstellung, auch im Falle von Mehrfach-Link-Störungen.

Zusammenfassung der Erfindung

Diese Aufgaben werden gelöst durch ein Datenübertragungsnetz mit mehreren Knoten, die über bidirektionale Links verschaltet sind zum Ermöglichen der Übertragung von Datenpaketen und Steuerdaten zwischen den Knoten, wobei die Knoten in jedem gegebenen Augenblick zu einer STB-Baum- Anordnung einschließlich eines Stammknoten und von Kinder- Knoten verschaltet sind, nach auswärts in eine Eltern-Kind- Beziehung organisiert sind, wobei jeder Knoten (außer detn Stammknoten) einen einzigen Eltern-Knoten aufweist, wobei der STB-Baum dadurch gekennzeichnet ist, daß jeder Knoten mit Speichermitteln zum Abspeichern in eine sogenannte Topologie- Datenbank einschließlich einer Eltern-Tabelle vefsehen ist, alle diese Knoten des Baums mit jedem Knoten (außer dem Stammknoten) auf ihren Eltern-Knoten und auf eine Link- Tabelle über Aus-Link-Zeiger zeigen, die Link-Tabelle Dual- Link-Zeiger zum Zeigen auf entsprechende Dual-Links innerhalb der Link-Tabelle und Mittel zum Zuweisen jedes Link-Bezugs auf eine Bit-Position enthält, die anzeigt, ob dieses Link augenblicklich am STB-Baum beteiligt ist oder nicht; Mittel zum Anwenden der Elter-Tabellen- und Link-Tabellen-Inhalte zum Organisieren der Baumanordnung nach-freiem Willen enthält; sowie Mittel zum dynamischen Aktualisieren der Knoten-Topologie-Datenbank einschließlich der Eltern-Tabelle und der Link-Tabelle bei jeder sTB-Baum (Um)-Organisierung vorgesehen sind.
Diese und noch weitere Aufgaben, Kennzeichen und Vorteile der Erfindung werden offensichtlich aus einer Betrachtung der folgenden detaillierten Beschreibung deutlich anhand der begleitenden Zeichnungen, die bevorzugte Ausführungsformen der Erfindung spezifizieren und zeigen.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist eine schematische Darstellung eines herkömmlichen Datennetzes, in dem die vorliegende Erfindung implementiert würde.
Fig. 2 ist eine schematische Darstellung eines sogenannten STB-Baums, abgeleitet vom Datennetz der Fig. 1, und der mit Mitteln zum Implementieren der Erfindung versehen werden soll.
Fig. 3 ist eine schematische Darstellung eines Netzwerk-Baums zum Sammelsendebetrieb.
Fig. 4 ist eine schematische Darstellung der Hardware für den Betrieb eines der Knoten des Netzwerkbaums der Fig. 3.
Fig. 5 ist eine schematische Darstellung einer Knoten- Organisation, die gemacht wurde zum Unterstützen der Erfindung.
Fig. 6 und 7 (einschließlich Fig. 7.1 bis Fig. 7.3) sind Flußdiagramme, die zum Implementieren der Erfindung gemacht wurden.

Detaillierte Beschreibung einer bevorzugten Ausführungsform der Erfindung

Die nachstehende Beschreibung gründet sich auf ein allgemeines Datennetz, wie es in Fig. 1 dargestellt ist, in dem zu einem gegebenen Augenblick bestimmte Links in Betrieb sind, während es andere nicht sind. Der entsprechende STB- Baum ist der in Fig. 2 mit diesen Verbindungslinien dargestellt, die zu einem gegebenen Augenblick die Knoten A bis Z verbinden.
Es müßte bereits darauf hingewiesen sein, und das ist offensichtlich für jeden Fachmann für Datenübertragungsnetze daß die Netzwerk-Darstellungen sowohl der Fig. 1 als auch der Fig. 2 nur zur Illustration der Erfindung gegeben sind und auf keinen Fall als Einschränkung des Umfangs der Erfindung angesehen werden dürfen. Die Netzwerke können in der Praxis komplexer, aber auch einfacher sein.
Auch die Abstände zwischen den Knoten können variieren von verhältnismäßig kleinen Abständen bis zu relativ größen Abständen (z. B. Tausende von Kilometern).
Es muß auch verstanden werden, daß Terminals (nicht dargestellt) einschließlich sowohl herkömmlicher Datenterminals als auch Großrechner oder CPUs an gegebene Knoten angeschlossen sind und den Datenverkehr mittels herkömmlicher Logon-Verfahren steuern. Diese Verfahren werden hier nicht beschrieben, weil sie nicht direkt mit der Erfindung in Beziehung stehen.
Schließlich sind die Knoten und links nicht unbedingt miteinander äquivalent soweit Leistung, Schnellverkehrskapazität usw. betroffen sind, aber das stört oder beeinflußt die Erfindung nicht.
Auch sind Eltern-, Kind- und Wurzelbeziehungen wie oben beschrieben definiert, und die STB-Baum-Darstellung kann und wird sich wahrscheinlich auch zeitlich verändern, je nachdem, welcher Knoten der STB-Baum-Stammknoten wird.
Wie bereits erwähnt, müssen Daten- und Steuerinformationen durch das Netzwerk geführt werden. Diese Informationen, die im allgemeinen als Daten bezeichnet werden und sowohl reine Daten als auch Steuerdaten umfassen, werden individuell in eine herkömmliche Paketstruktur organisiert, wobei jedes Paket einen sogenannten Kopfabschnitt einschließlich Streckenführungsinformationen (Adresse) zur Anwendung durch das Netzwerk enthält, um das betrachtete Paket von einem Ausgangspunkt über Netzwerk-Links und -Knoten zu einem zugewiesenen Zielpunkt durch das Netzwerk zu führen.
Einige Pakete können zu verschiedenen Knoten gesendet d. h. sammelgesendet werden. Mit anderen Worten, der Sammelsende- Führungsknoten ermöglicht das Senden eines Pakets von einem Sendeknoten gleichzeitig zu mehreren Empfängerknoten. Der Sendeknoten und die entsprechenden Empfängerknoten handeln wie ein Sammelsendebaum. Man kann dabei überlegen, daß eine Baumadresse einem Sammelsendebaum zugeordnet wird sobald dieser Baum definiert ist. Die verschiedenen Netzwerkknoten spezifizieren durch Setzen der richtigen Baumadresse in die Link-Hardware, welches ihrer zugeordneten Links (definiert als Link-Eigentum) auf dem Sammelsendebaum liegt.
Durch das Netzwerk übertragene Pakete enthalten eine Baumadresse in ihrem Leitwegführungs-Kopfteil. Diese Pakete werden durch das Netzwerk nur auf dem Link-Teil des Sammelsendebaums übertragen, und wenn sie die richtige Baumadresse in ihrer Hardware gesetzt haben.
Ein Beispiel für eine Sammelsendebaum-Organisation und das Sammelsendeleitwegführenwird in Fig. 3 und 4 illustriert.
In Fig. 3 ist ein Netzwerk mit vier Knoten dargestellt, die entsprechend als Knoten 1, 2, 3 und 4 gekennzeichnet sind. Diese Knoten sind mit physikalischen Verbindungslinks verschaltet, wobei jedes Link aus zwei Einweglinks besteht. Jedes Einweglink ist definiert durch (man könnte auch sagen "gehört zu") seinen Ursprungsknoten. Umgekehrt wird auch gesagt, daß der Knoten Links "besitzt".
Knoten 1 besitzt zwei Links: Link 1a und 1b
Knoten 2 besitzt drei Links: Link 2a, 2b und 2c
Knoten 3 besitzt zwei Links: Link 3a und 3b
Knoten 4 besitzt drei Links: Link 4a, 4b und 4c.
Wie in Fig. 3 dargestellt, heißt das Link 4a das duale Link von Link 1b, wobei beide Links ein komplettes physikalisches Link zwischen Knoten 1 und Knoten 4 bilden.
Mit den oben betrachteten vier Knoten, verschaltet mit den gestrichelten Links, wird ein Sammelsendebaum organisiert (das ist jedoch nur eine mögliche Darstellung). Dieser Sammelsendebaum wird definiert durch eine vorher zugeteilte Baumadresse "TA" (Tree Address). Wenn der Knoten 1 ein Paket, mit der Adresse TA in seinem Leitwegführungs-Kopfabschnitt, sendet, wird das Paket automatisch über das Link 1a und Link 1b, dann vom Knoten 4 über das Link 4c zum Knoten 3 geführt. Nur diejenigen Links, die Teil des Sammelsendebaums sind, befördern das betrachtete Paket. Schließlich wurde das Paket von Knoten über den Sammelsendebaum 1 wirklich zu den Knoten 2, 3 und 4 gesendet, wie gewünscht.
Fig. 4 zeigt eine schematische Darstellung einer Schalt- Hardware, die den Sammelsendebaum "TA" im Knoten 4 unterstützt. Der Knoten 4 weist eine Anzahl Ports auf, die jedem am Knoten 4 angeschlossenen Link entsprechen, d. h. Port 4a, Port 4b und Port 4c. Jeder Port ist mit seinen Puffer auf, der die Sammelsendebaumadresse speichert, und ein Paket wird nur durch solche das betrachtete Paket unterstützenden Ports sammelgesendet, wenn deren Kopfteil eine entsprechende Baumadresse aufweist, abgesehen von dem Port, das als Eingangsport tätig ist.
Mit anderen Worten, wenn ein Paket mit der Adresse "TA" in seinem Leitwegführungskopf beim Knoten 4 ankommt, gibt die knoteninterne Schalterhardware eine Kopie dieses Pakets an alle Links, die als Teil des "TA"-Sammelsendebaums markiert sind, abgesehen von dem Link, von dem aus das Paket zum Knoten gelangt ist. Im vorliegenden Fall wird das Paket an Link 4c weitergeschickt.
Ein Überbrückungsbaum (ST) kann unter bestimmten Betriebsbedingungen als ein Beispiel für einen Sammelsendebaum handeln, der alle Knoten eines Netzwerks verbindet (siehe Fig. 1 und 2). Jedes Paket, das von einem Knoten gesendet wird und die STB-Adresse in seinem Leitweg- Kopfteil enthält, wird automatisch an alle anderen Knoten des Netzwerks gesendet durch Verwenden des oben beschriebenen Sammelsendeprozesses und der Hardware.
Dieser Mechanismus ist besonders nützlich zum Verbreiten von Netzwerksteuermeldungen, die schnell alle Netzwerkknoten erreichen müssen, ohne über jedes einzelne Link des ursprünglichen Datenübertragungsnetzwerks laufen zu müssen, in welchem Fall sie von jedem Knoten mehr als einmal empfangen würden. Der SBT-Baum stellt somit sicher, daß eine Meldung, die von einem Senderknotenteil des STB-Baums gesendet wird, nur einmal von jedem Empfängerknoten empfangen wird, der zu dem STB-Baum gehört.
Angesichts dieser obigen Überlegungen würde die STB-Operation mehr oder weniger schnell, und allgemeiner gesagt, in einer mehr oder weniger optimierten Weise in Abhängigkeit von der vorgesehenen Knotenarchitektur arbeiten.
In der vorliegenden Erfindung wurde jeder Knoten mit Mitteln zum Einstellen einer vollen STB-Baum-Darstellung oder Topologie-Datenbank und Mitteln zum dynamischen Neueinstellen dieser voll topologischen Darstellung auf sehr schnelle Weise versehen. Zu diesem Zweck wird jeder Knoten mit Softwaremitteln ausgestattet, die unter Verwendung herkömmlicher und bereits existierender Prozessormittel und Direktzugriffsspeichermittel, sowie der Hardware und der Logik der Fig. 3 und 4, wie bereits beschrieben, den Knoten mit der vollen Darstellung des STB-Baums organisieren und pflegen, um die optimale Operation des Netzwerks zu ermöglichen.
Genauer gesagt ist jeder Knoten mit einer Bezugspunkt- Adapterlogik einschließlich Steuereinheit und Direktzugriffsspeichermitteln versehen, in denen eine topologische Datenbank abgespeichert wird. Die Topologie- Datenbank listet die Netzwerkknoten auf, wobei jeder Knoten einen Eltern-Knoten für die augenblickliche STB- Baumdarstellung und einen Zeiger nach außerhalb des Links umfaßt, der auf eine Außenlink-Tabelle zeigt. Diese Außenlink-Tabelle wird ihrerseits duale Linkzeiger beinhalten, die auf eine Dual-Link-Tabelle zeigen sowie eine Bit-Position (ST-Bit), die anzeigt, ob das betrachtete Link tatsächlich zum STB-Baum (ST) gehört oder nicht.
Nehmen wir z. B. an, wir betrachten den Knoten C. Dieser Knoten beinhaltet, wie jeder andere Knoten, eine sogenannten Elterntabelle (NODE Table oder List), die darin gespeichert ist. Diese Tabelle listet in NODE LIST Form Knoten A, Knoten B, Knoten C, Knoten D, ... Knoten Z (d. h. alle Netzwerkknoten) auf. Jeder Knoten zeigt auf einen Eltern- Knoten. Jeder Knoten zeigt auch auf eine erste oder Außen- Link-Tabelle. Zum Beispiel zeigt Knoten C auf eine Liste, die CB, CD, CG und CI beinhaltet (diese gleichen Links sind verbunden mit CB, der auf CD zeigt, wobei CD auf CG zeigt, und CG auf CI zeigt.
Ebenso genannt sind in dieser ersten Tabelle Hinweise darauf, ob das betrachtete Link zum augenblicklichen STB-Baum gehört oder nicht. Wie bereits gesagt, besorgt das ein einziges Bit (ST). Wenn dieses ST-Bit auf den Binärwert "1" gesetzt ist, zeigt das an, daß dieses Link zum STB-Baum gehört. Ansonsten, wenn ST auf "0" gesetzt ist, gehört das Link nicht zum Baum.
Wenn wir jetzt die Darstellung in Fig. 2 ansehen, ist ST = 1 für die Links CB, CD und CG, und ST = 0 für CI.
Nun zeigt jedes Link der ersten Tabelle auf eine zweite Liste oder Dual-Link-Tabelle. Zum Beispiel zeigt CB auf eine Liste enthaltend BC, BI, BA und BD. Offensichtlich aufgrund des Dualitätszusammenhangs enthält BC in der zweiten Tabelle einen Zeiger, der auf CB in der ersten Liste zurückzeigt. Diese zweite Liste erwähnt auch, ob jedes Link im STB-Baum ist oder nicht. Bit ST ist dementsprechend vor BC und BA auf "1" gesetzt, während es vor BI und BD auf dem Binärwert Null steht.
Dann zeigt jedes Link in dieser zweiten Liste auf eine dritte Dualliste. Zum Beispiel zeigt BA auf eine dritte Liste enthaltend AD, AB, AI, AH, AM, AO und AQ. Die folgenden Links in der dritten Liste zeigen ein ST-Bit, das auf den Binärwert 1 gesetzt ist, d. i. AB, AH und AM, während für die restlichen Links ST = 0 ist.
Und so weiter, bis das gesamte Netzwerk vollständig beschrieben ist. (Alle diese Link-Tabellen oder -Listen können in der Praxis zu einer einzigen LINK TABLE kombiniert sein). In der Tat, diese Darstellung ist knotenabhängig, weil sie so aufgebaut ist, als ob sie von dem betrachteten Knoten aus gesehen würde, aber auch jeder Knoten enthält eine volle Baumdarstellung, einschließlich jeder einzelnen Knoten- Elternbeziehung. Diese Tabellen können in der Tat zu einer Topologie-Datenbank kombiniert werden, die schematisch in Fig. 5 dargestellt ist.
In den Fig. 6 und 7 sind Flußdiagramme zum Aufbauen einer örtlichen STB-Baum-Darstellung dargestellt. Fig. 6 beschreibt, wie der Stammknoten des örtlichen Bilds des STB- Baums bestimmt wird. Der örtliche Stammknoten ist der erste Endknoten (Knoten ohne Kind-Knoten), auf den man trifft, wenn man die Eltern der Reihe nach anwählt.
Nehmen wir an, man sitzt in einem gegebenen Knoten X'. Der Prozeß läuft an mit Schritt 50, womit der gegebene Knoten X' selbst in die NODE LIST eingetragen wird. Dann, in Schritt 51, wird der entsprechende Elternknoten Y' in die NODE LIST eingetragen. Das System holt dann das erste Link des Knoten Y' (Schritt 52) und führt einen Test mit dem genannten Link durch (Schritt 53), um zu prüfen, ob es auf dem STB-Baum, online ist und nicht von X' kommt. Sollte das Ergebnis des Tests des Schritts 53 positiv sein, wird der Bestimmungsknoten als Elter von Y' gesetzt und in der NODE LIST registriert. X' wird auf Y' gesetzt und das neue Y' wird zum Elter von Y' gemacht (Schritt 54). Dann springt der Prozeß zurück zu Schritt 52.
Sollte im Gegenteil dazu der Test in Schritt 53 negativ sein, wird ein zweiter Test durchgeführt (Schritt 55), um festzustellen, ob das betrachtete Link das letzte Link für den genannten Knoten war. Sollte die Anwort auf den Test in Schritt 55 negativ sein, betrachtet das System das nächste Link des Knotens Y' (Schritt 56). Ansonsten geht der Prozeß zu Schritt 57 über und der genannte Knoten Y' wird als der örtliche Stammknoten registriert.
Dann geht der Prozeß über zu Fig. 7, die den Algorithmus zum Scannen der Knotentabelle und Datenbank zum Aktualisieren der entsprechenden Elterninformation darstellt. Die Wurzel wird zunächst aus der NODE LIST gelöscht (Schritt 61), und ein Test wird durchgeführt zur Überprüfung, ob die NODE LIST leer ist (Schritt 62). Sollte das der Fall sein, ist der örtliche STB-Baum voll beschrieben, wobei alle Knoten außer dem örtlichen Stammknoten einen Elternknoten definiert und registriert haben. Ansonsten liest der Prozeß den ersten Knoten der NODE TABLE (z. B. Knoten X') (Schritt 63) und ein Test wird durchgeführt, ob der NODE X' einen Elternknoten hat (Schritt 64). Sollte dieser Test negativ sein, holt der Prozeß ein erstes Link (Schritt 65) und prüft, ob dieses Link auf dem STB-Baum (ST = 1) und online ist (Schritt 66). Wenn der Test in Schritt 66 negativ ist, wird ein Test durchgeführt (Schritt 67), ob das betrachtete Link das letzte einschlägige Link war. Wenn nicht, wird das nächste Link aufgerufen und der Prozeß springt zurück zu Schritt 66. Wenn der Test in Schritt 66 positiv ist, prüft das System, ob der Bestimmungsknoten einen Elter hat (Schritt 68), und wenn nicht, geht das System zu Test 67 über. Ansonsten wird der Bestimmungsknoten (sagen wir Y') als Elternknoten des Knoten X' gesetzt und Y' wird in der NODE LIST registriert (Schritt 69). Sollte das Ergebnis von Test 64 oder Test 67 positiv sein, und ebenso nach Abschluß der Operation in Schritt 69, wird ein weiterer Test durchgeführt (Schritt 70), ob der betrachtete Knoten der letzte in der NODE TABLE zu scannende Knoten war.
Wenn dieser letzten Test negativ ist, geht das System zum Scannen der NODE TABLE über, um deren nächsten registrierten Knoten zu erfassen (Schritt 71) und springt in Schleife zurück zu Schritt 64. Anderenfalls prüft das System, ob alle Knoten einen Elter aufweisen (Schritt 72), und wenn nicht, springt es zurück zu Schritt 62, ansonsten löscht es die NODE LIST und springt dann ebenfalls zum gleichen Schritt 62 zurück.
Offensichtlich kann aufgrund der Flußdiagramme der Fig. 6 und 7 jeder Programmierfachmann auf der Basis der Systemmerkmale (z. B. Prozessoren) sofort ein Programm in einer geeigneten Programmiersprache ableiten, ohne dazu einer erfinderischen Tätigkeit zu bedürfen.
Wie bereits gesagt, verbessert die erfinderische volle örtliche Baumdarstellung den Netzwerk- und STB-Baum-Betrieb in einer Anzahl kritischer Situationen durch weitgehende Vereinfachung und Beschleunigung der Lösung jedes einschlägigen Problems.
Betrachten wir zum Beispiel, vereinfacht ausgedrückt, den Fall, in dem ein Pfad zwischen einem sogenannten Quellknoten und einem, sogenannten Bestimmungsknoten schnell bestimmt werden muß unter Verwendung ausschließlich der STB- Verbindungen (Links). Eine Fast Path Determination (Pfad- Schnellbestimmung) wird vom System eingeleitet. Diese Operation soll hier durch Durchsuchen der Quellknoten- Topologie-Datenbank bis zum Quellknoten sowohl für den Quellknoten als auch für den Bestimmungsknoten, Auflisten aller Elternknoten des Bestimmungsknotens bis zum Stammknoten, Auflisten aller Elternknoten des Quellknotens bis zum Stammknoten ausgeführt werden. Der erste gemeinsame Knoten in den beiden Listen wird dann zum Definieren des Pfades benutzt.
Nehmen wir z. B. an, der Quellknoten Z will den STB-Pfad zum Bestimmungsknoten X aufbauen.
Die im Knoten Z eingesetzte Logik tastet die örtliche Tabelle ab und erstellt die folgenden Listen (siehe Fig. 2).
Quellknoteneltern-Liste = Z, R, Q, P, 0, M, A
Bestimmungsknoten-Elternliste = X, U, R, Q, P, 0, M, A
Dann geht das System dazu über, eine umgekehrte Abtastung der beiden obigen Listen durchzuführen, und löscht alle gemeinsamen Knoten abgesehen vom letzten. Also wird in den beiden Listen als erster A gelöscht, anschließend M, O, P und Q. Da der letzte gemeinsame Knoten R ist, setzt der Knoten Z den gesuchten Pfad und definiert ihn in einer Steuermeldung als Z, R, U, X durch örtliches Scannen der verbleibenden Quellknotenliste nach vorwärts, und der Bestimmungsknotenliste nach rückwärts.
Aber die vorliegende Erfindung ist sogar noch bedeutsamer in Situationen, in denen ein Link bricht und der STB-Baum sehr schnell wieder aufgebaut (d. i. neu definiert) werden muß. Zum Verständnis, wie dramatisch diese Situation sein kann, betrachte man gleichzeitige Verbindungszusammenbrüche innerhalb des Baumes, oder auch aufeinanderfolgende Zusammenbrüche, die so schnell aufeinander folgen, daß der Baum nach einem der obigen Zusammenbrüche noch nicht wieder neu definiert werden kann. Man braucht nicht betonen, welches Durcheinander sich aus einer solchen Situation ergeben würde, das das gesamte Netzwerk zum Absturz bringen und völlig arbeitsunfähig machen würde.
Mit der vollen Baumdarstellung, die von der vorliegenden Erfindung bereitgestellt wird, und durch die Topologie- Datenbanken in jedem Knoten wird das System schneller wiederinstandgesetzt als mit den meisten herkömmlichen Systemen.
Nachstehend wird das System im Betrieb zur schnellen Wiederherstellung eines 5TB-Baums gezeigt. Um das Problem voll zu verstehen, muß man sich vorstellen, daß der oben geoffenbarte verteilte Bauminstandsetzungsalgorithmus einen unverwechselbaren Modusknoten definiert, der der Stammknoten heißt. Der Stammknoten zentralisiert und koordiniert den größten Teil der Instandsetzung des STB-Baums.
Wenn ein Verbindungszusammenbruch vorkommt, wird dadurch der ursprüngliche STB-Baum in zwei Bäume zerteilt. Ein Knoten, der vor dem Zusammenbruch ein Kind war, wird jetzt ein Stammknoten (Knoten ohne Elter) einer neu entstandenen Baumpartition. Mit den bereits in jedem Knoten vorgesehenen Mitteln, d. i. die volle Baumbeschreibung, kann jede Partition versuchen, eine STB-Baum-Partition wiederherzustellen, insbesondere, wenn sie zusätzlich die zusammengebrochene Verbindung kennt. Aber letztlich sollen die zwei Partitionen wieder zu einem einzigen Baum zusammengesetzt werden, um die Störung zu beseitigen. Aber damit die zwei zerteilten Bäume zusammenwachsen können, müssen sich ihre Stammknoten auf die gleiche Verbindung einigen, die zum Verschalten der beiden angewählt werden kann.
Ein Verfahren zum Aufstandbringen eines STB-Baums nach Netzwerktopologie-Veränderungen (Link- und Knotenstörungen und Wiederherstellungen) wurde von Israel Cidon, Inder S. Gopeel, Shay Kutten und Marcia Peters im IBM Technical Disclosure Bulletin, Bd. 35, Nr. 1A, Juni 1992, 55 93-398, unter dem Titel "Distributed Tree Maintenance" beschrieben. In dieser Offenbarung stellt der Topologieinstandsetzungsalgorithmus sicher, daß Knoten in einem Baum schließlich die Topologie ihrer benachbarten Verbindungen kennen. Die Übereinstimmung zwischen den Stammknoten zum Verschalten ist sichergestellt durch eine Eigenschaft, genannt "weight" (Gewicht), die allen Netzwerkverbindungen auf unverwechselbare Art und Weise zugeordnet ist, so daß sie in eine strikte Reihenfolge gebracht werden können. Zum Zusammenschließen zweier Bäume müssen sich die Stammknoten der beiden Bäume auf eine nicht im Baum liegende Verbindung zwischen ihnen mit dem geringsten Gewicht einigen. Dann bewegt sich der Stammknoten von einem Knoten zum anderen über eine zuverlässige Punkt-zu-Punkt- Meldung, genannt Move-Root. Der einzige Khoten, der eine Move-Root senden kann, ist der augenblickliche Stammknoten. Mit dem Senden der Move-Root-Meldung ist der augenblickliche Stammknoten nicht länger Stammknoten. Der Empfänger der Move- Root wird der nächste Stammknoten. Der Topologie- Aktualisierungs- und Baum-Instandsetzungs-Algorithmus sind voneinander abhängig, indem der augenblickliche Stammknoten alle Verbindungen im Netzwerk in Betracht zieht, um festzustellen, wohin er den Stammknoten schieben soll.
Die volle Kenntnis der Baum-Topologie, und insbesondere die Kenntnis von Knoten-Verwandtschaften in jedem Knoten, wie von der vorliegenden Erfindung vorgesehen, kombiniert mit der davon abgeleiteten Pfad-Schnellbestimmung, wie oben beschrieben, ermöglicht eine schnellere Baumwiederherstellung. Dieser Prozeß, genannt Fast Spanning Tree Recovery (schnelle STB-Baumwiederherstellung), die vom System eingeleitet wird, wird nachstehend anhand eines Beispiels näher beschrieben.
Nehmen wir an, die Verbindung BC wird gestört. Der ursprüngliche Baum (siehe Fig. 2) ist jetzt in zwei Bäume zerlegt, den ursprünglichen Baum (Baum (A)) ohne die Knoten C, G, D, E und F, und einen neuen Baum mit nur den Knoten C, G, D, E und F. Nehmen wir laut Definition an, daß der Kindknoten der gestörten Verbindung, d. i. Knoten C, zum Stammknoten (Selbststammknotensetzen) für den Baum mit den Knoten C, D, E, F, G gesetzt wird; dieser zweite Baum kann als Baum (C) bezeichnet werden.
Der Prozeß zum Vereinigen der beiden Teile, d. i. Baum (A) und Baum (C), läuft damit an, daß Knoten C seine Topologie- Datenbank durchsucht.
Diese Datenbank wird hier nachstehend schematisch dargestellt und zeigt die Eltern-Tabelle und die Link-Tabellen, die in der Tat leicht zu einer einzige Link-Tabelle zusammengefaßt werden können.
Die Eltern-Tabelle in Knoten C listet alle Netzwerkknoten mit jeweils vor dem Knoten den entsprechenden Elternknoten. Somit ist vor der Verbindungsstörung Knoten A als Stammknoten elternlos, der Elter des Knoten B ist Knoten A, der Elter des Knoten C ist Knoten B, usw., durch bis zum Knoten Z. Die Elterntabelle sieht daher vor der Linkstörung aus wie folgt: ELTERNTABELLE
Wie angegeben beinhaltet die Eltern-Tabelle auch einen Aus- Link-Zeiger für jeden Knoten, wobei der Zeiger auf die Links zeigt, die aus dem betrachteten Knoten hinausführen (erste Liste), wobei jede Link-Liste ihrerseits auf eine Dual-Link- Liste zeigt (zweite Liste, dritte Liste, usw....)
Betrachten wir hierunter ein Beispiel mit einer ersten Liste, die die Aus-Links von Knoten C zeigt, eine zweite Liste, die die Dual-Liste zeigt, auf die vom CB Dual PTR gezeigt wird, und eine dritte Liste, auf die von BA Dual PTR gezeigt wird. LINK-TABELLE
Wie oben gezeigt, zeigt der Aus-Link-Zeiger Vor dem Knoten C auf die erste Link-Liste, die CB, CD, CG und CI beinhaltet, die jeweils auf das nächste Link zeigen (in den obigen Tabellen nicht dargestellt). Mit anderen Worten, CB zeigt auf CD, das seinerseits auf CG zeigt usw. bis zu CI. Zusätzlich, und wie erwähnt, beinhaltet die erste Link-Liste Dual-Link- Zeiger, die auf die zweite Link-Liste zeigen. Zum Beispiel, der CB in der ersten Link-Liste zugeordnete Dualzeiger zeigt auf die Dual-Liste (d. i. zweite Link-Liste), die die folgenden Links auflistet: BC, BI, BA und BD. Jede Link in der zweiten Link-Liste zeigt seinerseits auf die dritte Link- Liste usw., wie im Falle des BA-Link-Dualzeigers angegeben ist.
In der Praxis werden alle diese Link-Listen zu einer einzigen komplexen Link-Tabelle zusammengefaßt.
Zusätzlich, und das sollte bei der Link-Störungsbeseitigung, wie angegeben, helfen, ist jedes Link mit einem Ein-Bit- Hinweis (d. i. ST) definiert, der angibt, ob das entsprechende Link augenblicklich im STB-Baum (ST = 1) oder nicht im STB- Baum (ST = 0) ist. Zum Beispiel, für den ursprünglichen Baum, der in Fig. 2 dargestellt ist, und für Knoten C zeigt die Link-Liste ST = 1 CB, CD, CG, und ST = 0 für CI.
Wenn das Link BC/CB gestört wird, wie oben gesagt, wird Knoten C, d. i. der Kindknoten auf der gestörten Verbindung, ein Stammknoten für den Baum mit C, G, D, E, F. Nur diese Links im Baum(C), d. i. CG, CD, DE, EF, behalten ein ST-Bit gleich binär 1. Die anderen werden zurückgesetzt: Die obige erste Tabelle sieht dann so aus:
Auch die Eltern-Tabelle wird rückgestellt um die Link-Störung und die Baum-Teilung wiederzugeben.
Aufgrund der obigen Information bestimmt Knoten C nur durch Durchsuchen seiner Topologie-Datenbank, und insbesondere durch Durchsuchen der Link-Tabelle, die Liste der Links XKn, wobei Kn ein Knoten ist, der zum Baum (A) gehört. Im obigen Beispiel enthält die Liste der Links CKn nur CB und CI als Links, die nicht zum Baum (C) gehören, und daher potentiell brauchbar zum Verbinden von Baum (A) mit Baum (B) ist.
Da CB gestört ist, umfaßt der Liste der verbleibenden Links nur CI, und CI wird zur Auswahl bezeichnet. Allgemeiner gesprochen könnte die Liste der CKn mehrere Links enthalten. In diesem Fall würde ein zusätzlicher Parameter vordefiniert werden (z. B. Höchstgeschwindigkeits-Link), um die Zweideutigkeit zu beheben und das Link zu wählen.
Daher ist das vom Knoten C geWählte Link CI. Der Knoten C beginnt einen Dialog mit Knoten I durch Senden einer sogenannten "Combine Request"-Meldung (Verbindungsanforderung). Knoten I antwortet jedoch erst, nachdem ihm die "Rootship" (Stammknoteneigenschaft) für Baum (A) zugesichert wurde, der Baum (I) werden soll. Der Knoten (I) gewährt die Verbindungsanforderung erst, nachdem er die Stammknoteneigenschaft hat, was noch nicht der Fall ist. Damit eine unbegrenzte Wartezeit vermieden wird, falls ein Problem auftritt, setzt Knoten C einen Zeitgeber und, wartet nur bis zum Ablauf der gesetzten Zeit.
Die Anwendung eines ähnlichen Prozesses (Tabellenrückstellung usw ...) in Baum (A) ermöglicht, daß ein Link zwischen den zwei Teilbäumen gesetzt wird. Mit anderen Worten, sobald eine Meldung eingeht, daß Link BC gestört ist, durchsucht die ursprüngliche Wurzel (A) ihre Topologie-Datenbank, um die Liste der Kandidaten-Links KnC zu finden, wobei Kn ein Knoten aus Baum (A) ist, nachdem die Baumtrennung eingetreten ist, d. h. der Baum, der alle Netzwerkknoten enthält außer C, G, D, E, F.
Das gleiche Link IC in Satz CKn wird vom Stammknoten A gewählt.
Dann kann vom Knoten A zum Knoten I eine unmittelbare "Move Root" (Stammknotenbewegung) implementiert werden durch Anwenden des Schnellpfadbestimmungsverfahrens der vorliegenden Erfindung wie oben beschrieben (nur durch Durchsuchen der Elternlisten). Knoten A gibt eine Move-Root- Meldung an den Knoten I durch Verwenden des ausgewählten Pfads auf dem STB-Baum zwischen Knoten A und Knoten I. Dann gewährt Knoten I die "Combine Request"-Meldung, die er vom Knoten C erhalten hat, über CI und vervollständigt den Verbindungsprozeß mit C. Dann wird der vereinigte STB-Baum gemäß dem oben beschriebenen Prozeß neu definiert mit Knoten I als neuer Stammknoten.
Wie bereits erwähnt, ist die vorliegende Erfindung auch für eine Reihe anderer Situationen von besonderem Interesse. Zum Beispiel, um einen gegebenen STB-Baumdurchmesser zu reduzieren, oder um ein gegebenes minderwertiges Link (oder sogenanntes niedriggewichtetes Link) durch ein höhergewichtetes Link zu ersetzen. In diesen Fällen erscheinen die vollen topologischen Datenbanken, die in jedem Knoten zur Verfügung stehen, hinreichend brauchbar.

Claims

1. Ein Datenübertragungsnetz mit mehreren Knoten, die über bi-direktinale Links verschaltet sind zum Ermöglichen der Übertragung von Datenpaketen und Steuerdaten zwischen den Knoten, wobei die Knoten in jedem gegebenen Augenblick zu einer STB-Baum-Anordnung einschließlich eines Stammknotens und Kinder-Knoten verschaltet sind, die nach auswärts in eine Elter-Kind-Beziehung organisiert sind, wobei jeder Knoten, abgesehen von dem Stammknoten, einen einzigen Eltern-Knoten aufweist, wobei der STB-Baum dadurch gekennzeichnet ist, daß jeder Knoten versehen ist:

mit Speichermitteln zum Abspeichern in eine sogenannte Topologie-Datenbank, die eine Eltern-Tabelle umfaßt, wobei alle Knoten des Baums, abgesehen vom Stammknoten, auf seinen Eltern-Knoten und über ein Aus-Link-Zeigermittel auf eine Link-Tabelle zeigt, die Link-Tabelle ein Dual- Link-Zeigermittel umfaßt zum Zeigen auf entsprechende Dual-Links innerhalb der Link-Tabelle, und mit Mitteln zum Zuweisen jedes Link-Bezugs auf eine Bit-Position, das sogenannten ST-Bit, das anzeigt, ob dieses Link augenblicklich am STB-Baum beteiligt ist oder nicht;

mit Mitteln zum Anwenden der Elter-Tabellen- und Link- Tabellen-Inhalte zum Organisieren der Baumanordnung nach freiem Willen;

mit Mittel zum dynamischen Aktualisieren der Knoten- Topologie-Datenbank einschließlich der Elter-Tabelle und der Link-Tabelle bei jeder STB-Baum (Um)-Organisierung;

diese Mittel bei normalen Betriebsbedingungen operativ sind.

2. Ein Datenübertragungsnetz gemäß Anspruch 1, in dem die Mittel zum aktualisieren der Elterntabelle und der Link- Tabelle bei jeder STB-Baum-Umorganisierung in jedem Knoten enthalten:

a) Mittel im betrachteten Knoten zum Scannen der örtlichen gespeicherten Elterntabelle und Link-Tabelle zum Erfassen des ersten Knotens ohne Kind d. i. des sogenannten Anschlußknotens, unter Zuweisung der Stammknoteneigenschaft an den Knoten und entsprechendem Ergänzen der Tabellen;

b) Mittel zum Durchforschen der örtlichen Knoten-Topologie- Datenbank einschließlich örtlicher Elterntabelle und Link- Tabelle zum Finden der STB-Baum-Links, für die der Bestimmungsknoten der Elter ist, Markieren der Quellknoten mit den entsprechenden Bestimmungsknoten als Elternknoten, und zum entsprechenden Berichtigen der Tabellen;

c) Mittel zum Iterieren des Prozesses mit dem Quellknoten als Bestimmung, bis alle Knoten einen Elter haben, und entsprechendem Berichtigen der Tabellen, wobei volle Elter-Kind-Beziehungen für jeden Knoten in der betrachteten Knotendatenbank geladen werden, um die Baumstruktur zu definieren.

3. Ein Datenübertragungsnetz gemäß Anspruch 1 oder 2, das ferner Mittel beinhaltet zum Durchführen, auf Anforderung, einer Schnellpfadbestimmung zwischen einem sogenannten Quellknoten und einem sogenannten Bestimmungsknoten, die beide zum STB-Baum gehören, und jeder beliebige Knoten auf dem STB-Baum in der Lage ist, entweder als Quellknoten oder als Bestimmungsknoten zu handeln, wobei diese Mittel beinhalten:

Mittel zum Anlaufenlassen des Quellknotens zum Scannen seiner gespeicherten Elterntabelle nach oben, und Abspeichern einer sogenannten Quell-Elternliste, die die aufeinanderfolgenden Elternknoten nach oben auflistet;

Mittel zum Anlaufenlassen des Quellenknotens zum Scannen ihrer gespeicherten Elterntabelle und Speichern einer Bestimmungs-Elternliste, die nach oben mit dem Zielknoten anläuft;

Mittel zum umgekehrten Scannen beider Listen und Löschen aller gemeinsamen Knoten abgesehen von dem letzen;

wobei der Pfad zwischen dem Quellknoten und dem Bestimmungsknoten generiert wird durch einfaches Verketten der restlichen Quell-Eltern-Liste nach vorwärts und der restlichen Bestimmungs-Eltern-Liste nach rückwärts.

4. Ein Datenübertragungsnetz gemäß einem beliebigen der Ansprüche 1 bis 3, in dem die Eltern-Tabelle und die Link- Tabelle zu einer einzigen Link-Tabelle kombiniert sind.

5. Ein Datenübertragungsnetz gemäß einem beliebigen der Ansprüche 1 bis 4, das ferner Mittel enthält zum Durchführen, bei einer STB-Baum-Störung, die den ursprünglichen STB-Baum auseinanderreißt und teilt in einen ersten Baum einschließlich des Kindknotens des gestörten Links und aller darin noch angehängten Knoten, und einen zweiten Baum, einschließlich des ursprünglichen Stammknotens und aller noch vorhandener angehängter Knoten, einer schnelle Beseitigungsoperation zum Neukombinieren des partitionierten Baums zu einem einzigen Baum, und Neudefinieren des entsprechenden STB-Baums, wobei das Schnellbehebungsmittel aufweist:

a) Mittel zum Definieren des Kindknotens des gestörten Links als Stammknoten des ersten STB-Baums;

b) Mittel, sowohl im ursprünglichen Stammknoten als auch im Stammknoten ersten Baums zum Rücksetzen des ST-Bits innerhalb der entsprechenden Datenbanken, um die augenblickliche Baum-Partition wiederzuspiegeln;

c) Mittel zum Durchsuchen der zurückgesetzten Topologie- Datenbanken innerhalb des Stammknotens des ersten Baums, zum Auflisten der Links zwischen dem Stammknoten des ersten Baums und den Knoten, die zum zweiten Baum gehören, zum Auswählen eines der genannten Links auf der Grundlage vorgegebener Verbindungsmerkmale zum Zusammenhängen des ersten und des zweiten Baums, und zum entsprechenden Unterrichten des Zielknotens auf dem gewählten Link;

d) Mittel zum Durchsuchen der aktualisierten Topologie- Datenbank innerhalb des Stammknotens des zweiten Baums, um ein Link zwischen dem Bestimmungsknoten und dem Stammknoten des ersten Baums auszuwählen;

e) Mittel zum Senden von Move-Root-Steuerdaten von vom Stammknoten des zweiten Baums an den Bestimmungsknoten und zum Vervollständigen des Baumverbindungsprozesses; und

f) Mittel zum entsprechenden Aktualisieren jeder Knoten- Topologie-Datenbasis.

6. Ein Verfahren zum Durchführen, in einem Netzwerk gemäß einem beliebigen der Ansprüche 1 bis 5, von Schnell-STE- Baum-Störungsbehebungsoperationen nach einer Störung eines Baum-Links IJ, wobei I der Kind-Knoten und J der Elternknoten des gestörten Links ist, und R der Stammknoten des ursprünglichen STB-Baums ist, wobei der ursprüngliche Baum in zwei Partitionen geteilt ist, die definiert sind als Teil R mit R als dem entsprechenden Stammknoten, und der andere als Teil I mit I als Stammknoten definiert ist, und das Verfahren beinhaltet:

Im Knoten I:

- Durchsuchen der Knoten-Topologie-Datenbasis zum Finden und Speichern einer Liste Links IKn, wobei Kn ein Knoten ist, der zum Teil R gehört;

- Auswählen eines gespeicherten Links K in der Liste auf der Grundlage eines vordefinierten Link-Kriteriums;

- Starten eines Verschmelzungsprozesses durch Veranlassen, daß der Knoten I eine sogenannte "Combine Request"-Meldung an den Knoten K schickt;

Im Knoten R:

- Durchsuchen der Topologie-Datenbank zum Finden und Speichern einer Liste von Links KnI, wobei Kn ein Knoten ist, der zum Teil R gehört;

- Auswählen des Knotens KI unter dem Satz Knoten Kn auf der Grundlage der vordefinierten Link-Kriterien;

- Einleiten und Senden einer "Move-Root"-Meldung an den Knoten K;

Benutzen des Knotens K zum Komplettieren des Vereinigungsprozesses, um die Stammknoteneigenschaft für den vereinigten Baum zu erhalten, und Neuinitiieren der Topologie-Datenbanken-Installation durch Anwenden der Mittel gemäß Definition in Anspruch 2.

7. Ein Verfahren gemäß Anspruch 6, in dem die Vereinigungsprozeß-Startoperationen das Anlaufenlassen eines Zeitgeber zum Setzen einer Grenze für die Gültigkeit der an den Knoten K gesendeten "Combine Request"-Meldung beinhalten.

8. Ein Verfahren gemäß Anspruch 6 oder 7, in dem die "Move Root"-Meldung vom Knoten R an den Knoten K unter Verwendung gemäß Anspruch 3 gemachter schneller Pfadbestimmungsmittel gesendet wird.

9. Ein Verfahren zum Durchführen von Schnell-STB-Baum- Wiederherstellingsoperationen gemäß Anspruch 6 bis 8 unter Verwendung von Mitteln zum Synchronisieren der Operationen gemäß der Chronologie der Link-Störungen im Falle von auftretenden Mehrfach-Link-Störungen.