DE3687400T2

DE3687400T2 - Digitale nachrichtenuebertragungsnetzwerke und aufbau von uebertragungswegen in diesen netzwerken.

Info

Publication number: DE3687400T2
Application number: DE8686113668T
Authority: DE
Inventors: Brice, Jr; Robert Allen Weingarten
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1985-11-04
Filing date: 1986-10-03
Publication date: 1993-07-15
Anticipated expiration: 2006-10-04
Also published as: JPH0450780B2; EP0221360A2; US4825206A; JPS62109451A; EP0221360A3; DE3687400D1; EP0221360B1

Description

Die vorliegende Erfindung bezieht sich auf digitale Nachrichtenübertragungsnetzwerke und den Aufbau von Übertragungswegen in diesen Netzwerken, in denen der Übertragungsweg oder der Leitweg,den eine Nachricht durch das Netzwerk nimmt, dynamisch berechnet wird, d. h. der Weg wird jedesmal neu bestimmt, wenn eine Übertragungssitzung zwischen zwei Benutzern des Netzwerkes aufzubauen versucht wird.
Übertragungsnetzwerke sind Anordnungen von Computern, Leitzentralen und zugehörigen peripheren Geräten und Verbindungsstrecken, die es "Endbenutzern", die an entfernten Stellen in dem Netzwerk sich befinden, erlauben, die Übertragung von Information aufzubauen und aufrechtzuerhalten. Ein Endbenutzer kann in diesem Zusammenhang ein menschlicher Benutzer an irgendeiner Art von Datenstation sein, oder ein Anwendungsprogramm, das auf einem Leitrechner oder auf irgendeiner Art einer intelligenten Gerätesteuereinheit läuft (d. h. Arbeitsstation, Personal Computer, Anzeigesteuereinheit, usw.). Fig. 1 stellt ein kleines Übertragungsnetzwerk dar. Darin sind zwei IBM System 370 Leitrechner 12, 14 und drei IBM 3725 miteinander verbunden, die fünf Datenstationen 22, 24, 26, 28, 30 unterstützen, die wie gezeigt angeschlossen sind. Übertragungsverbindungstrecken 32, 34, 46, 38, 40, 44 verbinden die Computer 12, 14 und die Steuereinheiten 16, 18, 20 wie dargestellt.
Eine Nachrichtenübertragung zwischen sagen wir der Datenstation 30 und dem Leitrechner 12 in Fig. 1 ist auf mehreren verschiedenen Wegen möglich. Um sich eine Vorstellung von der Übertragung in einem Netzwerk zu machen, ist eine Übereinkunft getroffen worden, nach der die Computer und die Übertragungssteuereinheiten in einem Netzwerk kollektiv als Knoten und die Verbindungen zwischen den Knoten als Verbindungsstrecken bezeichnet werden. Fig. 2 veranschaulicht ein Diagramm der Knoten und Verbindungsstrecken des Netzwerkes 10, das in Fig. 1 dargestellt ist, wobei gleiche Elemente in Fig. 2 die gleichen Bezugszahlen wie in Fig. 1 aufweisen, jedoch mit einem Strich versehen. Datenstationen sind in dem Diagramm nicht dargestellt, da sie nicht direkt mit dem Aufbau einer Nachrichtenverbindung und dem Steuerprozeß verbunden sind, auf den sich die vorliegende Erfindung bezieht.
Ein Dialog, der als eine Sitzung bezeichnet wird zwischen einem Endbenutzer an der Datenstation 30 und einem Anwendungsprogramm in dem Leitrechner 12 in Fig. 1, würde mit einer Nachrichtenverbindung zwischen den Knoten 12 und 18, oder 121 und 181 nach Fig. 2 verbunden sein. Verschiedene Wege sind für solch eine Sitzung möglich. Beispielsweise könnte die Nachrichtenverbindung einfach über die Verbindungsstrecke 341 erfolgen oder der Weg könnte die Verbindungsstrecken 32' und 40' und den Knoten 16' einschließen. Alternativ könnte der Weg die Verbindungsstrecken 32', 36' und 38' und die Knoten 16' und 14' einschließen. Die Wahlmöglichkeiten nehmen mit der Größe und Kompliziertheit des Netzwerkes zu.
Außer in sehr begrenzten Fällen, in denen das Netzwerk voll verbunden ist, durchläuft die Information,die an einem Ursprungsknoten eingegeben wird, (der einen Endbenutzer unterstützt), einen oder mehrere Zwischenknoten, bevor sie den Bestimmungsknoten erreicht, (der den anderen Endbenutzer unterstützt). Information, die von einem Knoten übertragen und zu einem anderen Knoten geleitet wird, muß über die Verbindungsstrecken laufen, die die Knoten miteinander verbinden. In einigen Netzwerken durchläuft die gesamte Information, die zwischen zwei Endbenutzern während einer bestimmten Übertragungssitzung übertragen wird, den gleichen Weg, der in diesem Fall ein Leitweg genannt wird. Der Mechanismus, der benutzt wird, um den Leitweg zu schaffen, der später als Leitwegmechanismus bezeichnet wird, ist abhängig von einer bestimmten Netzwerkarchitektur.
Die meisten Leitwegmechanismen für ein Netzwerk benutzen Leitwegtabellen in jedem Knoten (Ursprungs-, Zwischen- und Bestimmungsknoten), um Nachrichten zu dem nächsten Knoten abzusenden. Leitwegmechanismen können variieren, aber verschiedene benutzen einen Index in eine Leitwegtabelle, (wobei der Index entweder eine Identifizierung eines Leitweges oder eine Kombination von Identifizierungen der Quelle und/oder des Bestimmungsknotens ist), um anzugeben, welcher Ausgangsverbindungsstrecke und damit zu welchem nächsten benachbarten Netzwerkknoten die Nachricht zu schicken ist. Wenn die Nachricht den Bestimmungsknoten erreicht, wird sie natürlich statt dessen durch den Endbenutzer verarbeitet.
Die Leitwegtabellen in jedem Netzwerkknoten können entweder statisch oder dynamisch aufgebaut werden. In dem statischen Fall werden die Leitwegdefinitionen festgelegt, wenn der Netzwerkbetrieb gestartet wird. Der statische Mechanismus ist für die Erfindung nicht relevant und wird daher nicht diskutiert.
Bei der dynamischen Leitwegwahl wird ein Verfahren zum Schaffen eines Leitweges verwendet, das dynamisch einen Leitweg von Endpunkt zu Endpunkt, von dem Quellenknoten zu einem Bestimmungsknoten schafft, der während einer bestimmten Übertragungssitzung benutzt werden kann. Dieser Leitweg von Endpunkt zu Endpunkt bleibt definiert und aktiv, bis alle Sitzungen, die den Leitweg benutzen, enden. Dann kann der Leitweg eliminiert werden, um Betriebsmittel des Netzwerkes freizugeben, wie z. B. Einträge in die Leitwegtabelle, die für andere dynamisch geschaffene Leitwege zu benutzen sind.
Verschiedene Verfahren können benutzt werden, um dynamische Leitwege in Netzwerken zu schaffen. Ein solches Verfahren, das in den Proceedings of the Seventh International Conference on Computer Communication, Sydney, 30.10.-2.11. 1984 Elsevier Pub., Amsterdam, NL; J.M. Jaffe et al.; "Applying dymamic routing for a general network architecture", Seiten 716-721 veröffentlicht wurde, verwendet eine Topologie-Datenbank, die die Identifizierungen aller physikalischen Knoten und Verbindungsstrecken in dem Netzwerk enthält, einschließlich ihrer Verbindbarkeit, Statusarten und physikalischen Eigenschaften, um einen Leitweg dynamisch zu bilden. Dieses Verfahren wählt geeignete Knoten und Verbindungsstrecken aufgrund ihres aufgezeichneten Status aus und erzeugt eine Nachricht, die ab jetzt als Nachricht LEITWEG AUFBAUEN bezeichnet wird, und eine Liste der Knoten und Verbindungsstrecken enthält, die bei dem Leitweg zu benutzen sind. Die Nachricht LEITWEG AUFBAUEN durchläuft jeden Knoten in der Liste und erlaubt es jedem Knoten, einen Eintrag in seine Leitwegtabelle vorzunehmen, so daß nachfolgende Nachrichten für eine Sitzung, die dem Leitweg zugeordnet ist, die gleichen physikalischen Knoten durchlaufen kann, die durch die Nachricht LEITWEG AUFBAUEN identifiziert wurden. Sowohl Vorwärts- als auch Rückwärtszeiger werden in der Leitwegtabelle des Knotens plaziert.
Leitwegwahl in Nachrichtenübertragungsnetzwerken wird diskutiert durch Jaffe et al in "SNA Routing: Past, Present and Possible Future", erschienen in dem IBM System Journal, Vol. 22, No 4 (1983), Tymes in "Routing and Flow Control in TYMNET" erschienen in den IEEE Transactions on Communications, Vol. COM-29, No 4, (1981), und durch McQuillan et al in "The New Routing Algorithm for ARPANET", erschienen in den IEEE Transactions on Communications, Vol. COM-28, No 5, (1980).
Zweifellos ist es wichtig für die Topologie-Datenbank, laufende Information darüber zu haben, welche Knoten und Verbindungsstrecken für eine Übertragung verfügbar sind. Andernfalls könnten Versuche gemacht werden, Leitwege zu schaffen, die nicht verfügbare Knoten oder Verbindungsstrecken aufweisen, und mehrere Versuche zum Schaffen des Leitwegs können erforderlich werden, bevor ein verfügbarer Leitweg tatsächlich gefunden wird. Dies stellt einen unnötigen Verbrauch an Betriebsmitteln des Netzwerkes dar. Anders als durch manuelle Eingabe durch den Operator erfolgte das Berichten des Anfangszustandes, der Fehler und der Reaktivierungen der Netzwerkknoten und Verbindungsstrecken, die im folgenden als Netzwerkelemente bezeichnet werden, durch Rundspruch der Statusaktualisierungen durch benachbarte Knoten. Die Artikel von Tymes und McQuillan et al, die oben genannt wurden, beschreiben solche Aktualisierungsverfahren mittels Rundspruch. Diese Statusaktualisierungen durch Rundspruch haben den Vorteil, daß sie nicht das Eingreifen des Operators erfordern. Sie haben jedoch das Problem, besonders in großen und komplizierten Netzwerken, daß sie den Gesamtverkehr des Netzwerkes beträchtlich erhöhen. In einigen Fällen ist es vorzuziehen, weniger als eine vollständige Kenntnis des Status des Netzwerkes zu akzeptieren, um diesen Gesamtverkehr zu verringern. In der Tat ist es in solchen Netzwerken notwendig,einen Mechanismus zu haben,um die durch Rundspruch übertragene Nachricht zu "töten", die das System durchläuft, da sonst die Nachricht immer wieder das Netzwerk durchläuft. Typische Mechanismen schließen die Eingliederung einer Abschaltzeit ein, nach der die Nachricht von dem Netzwerk verworfen wird. Selbst mit solchen Begrenzungsmechanismen beanspruchen Nachrichten zur Aktualisierung des Status einen großen Teil der Gesamtleistungsfähigkeit des Netzwerkes zur Nachrichtenverarbeitung, so daß wenig Kapazität für Benutzernachrichten verfügbar ist.
Es ist daher offensichtlich, daß eine Notwendigkeit für eine Einrichtung zum Aktualisieren einer Topologie-Datenbank in einer Umgebung für dynamische Leitwegwahl besteht, so daß deutlich verringerte Anforderungen an die Leistungsfähigkeit des Netzwerkes zur Nachrichtenverarbeitung gestellt werden im Vergleich zu Systemen nach dem Stand der Technik zur Aktualisierung von Technologie-Datenbanken.
Die vorliegende Erfindung wird weiter als Beispiel beschrieben mit Bezugnahme auf bevorzugte Ausführungsbeispiele der Erfindung wie sie in den zugehörigen Zeichnungen dargestellt sind, von denen ist:
Fig. 1 ein Blockdiagramm eines einfachen Übertragungsnetzwerkes vom Maschentyp
Fig. 2 eine schematische Darstellung des in Fig. 1 gezeigten Netzwerkes
Fig. 3 eine schematische Darstellung einer Leitwegtabelle einer Topologie-Datenbank, die durch das Netzwerk nach Fig. 1 verwendet wird,
Fig. 4 eine schematische Darstellung einer Leitweganweisung,
Fig. 5 eine schematische Darstellung einer Nachricht LEITWEGANFORDERUNG,
Fig. 7 eine schematische Darstellung einer Nachricht LEITWEG AUFBAUEN
Fig. 8 eine schematische Darstellung einer Tabelle zur Leitwegwahl,
Fig. 9 eine schematische Darstellung einer Nachricht LEITWEGFEHLER und
Fig. 10 eine schematische Darstellung eines Netzwerkes mit einer Topologie-Datenbank.
In den Zeichnungen sind gleichartige Elemente mit gleichartigen Bezugszahlen bezeichnet und gleiche Elemente in verschiedenen speziellen Ausführungsbeispielen sind durch gleiche Bezugszahlen bezeichnet.
Die vorliegende Erfindung verkörpert ein Verfahren und eine Vorrichtung, die dazu benutzt werden können, um den Status der Netzwerkknoten und Verbindungsstrecken dynamisch an Topologie- Datenbänke zu berichten, so daß die Nachrichten LEITWEG AUFBAUEN wirksam geschaffen werden können mit der Kenntnis des physikalischen Zustandes der Leitwegelemente. Die folgende Beschreibung ist anwendbar auf ein IBM SNA Netzwerk, das z. B. Computer des IBM Systems 370 und Datenfernverarbeitungssteuereinheiten IBM 3725 als Knoten umfaßt und geeignete Übertragungsstrecken zur Netzwerkverbindung. Jedoch werden die Prinzipien und Protokolle mit genügender Allgemeinheit dargestellt, um die Anwendung auf irgendein Übertragungsnetzwerk zu ermöglichen, das dynamische Leitwegwahl aufweist, die auf einer oder mehreren Topologie-Datenbanken zur Leitwegschaffung beruht und auf lokalen Leitwegtabellen in jedem Knoten für den Aufbau und das Aufrechterhalten der Übertragungssitzungen.
Bei dem bevorzugten Ausführungsbeispiel wird jede Topologie- Datenbank anfangs mit Information bezüglich all der Knoten und Verbindungsstrecken und ihrer möglichen Verbindbarkeit mit benachbarten Knoten versorgt. Diese Information wird über übliche Eingabeanweisungen eingegeben, entweder interaktiv oder über Definitionen zur Stapelverarbeitung. Die Anweisungen für Verbindungsstrecken und Knoten geben ferner bestimmte Eigenschaften an, wie z. B. Übertragungsgeschwindigkeit der Leitung (Verbindungsstrecke), Größe des Knotenpuffers und Übertragungssicherheit der Datenelemente, die von den Endbenutzern benutzt werden, um einen Leitweg anzufordern. Diese Kenndaten werden unten dargelegt unter BEDIENUNGSREGELN, DEFINITIONEN & ZUSTÄNDE, Teil a) Datenarten. Zusätzlich wird jedes Netzwerkelement in der Topologie-Datenbank anfänglich als "betriebsfähig angenommen" oder verfügbar markiert. Dieser Anfangszustand hat nichts zu tun mit dem tatsächlichen Zustand des entsprechenden Elementes, erlaubt es aber dem Verfahren zur Leitwegauswahl das Element für einen Versuch, einen Leitweg aufzubauen, auszuwählen und dynamisch seinen tatsächlichen Betriebsfähigkeits- oder Nichtbetriebsfähigkeitsstatus über den Rückmeldungsmechanismus festzustellen. Die Information wird in üblicher Weise in der Art gespeichert, daß sie für eine Abfrage und einen Vergleich verfügbar ist, wenn eine Anforderung nach einem Leitweg empfangen wird.
Diese Information wird eingegeben für 1) Leitwege, 2) Verbindungsstrecken und 3) Knoten. Daher wird unter der Annahme, daß ein interaktives Eingabeverfahren (im Gegensatz zur Stapelverarbeitung) verwendet wird, eine Leitweganweisung benutzt, um Information einzugeben, die einen Leitweg zwischen zwei Knoten definiert, zwischen denen eine Nachrichtenübertragung zugelassen werden soll. Diese Anweisung gibt die Verbindungsstrecken und Knoten in diesem Leitweg der Reihe nach an und eine Identifizierung (ID) für diesen Leitweg.
Für jedes Knotenpaar, das miteinander in Verbindung treten kann, können so viele Leitweganweisungen eingegeben werden wie es verschiedene Leitwege zwischen den Knoten gibt. Fig. 3 zeigt die Topologie-Datenbankanweisungen für die möglichen Leitwege zwischen den Knoten 16' und 14' in Fig. 2. In diesem Fall gibt es drei solche Leitwege: 50, 52 und 54. Fig. 4 zeigt die Form einer Leitweganweisung 58. Die Namen 60 von Verbindungsstrecken und Knoten werden in der Reihenfolge, in der eine Nachricht den Leitweg durchläuft, angeordnet, beginnend mit dem Ursprungsknoten und endend mit dem Bestimmungsknoten. Die Art der Anweisung 62 identifiziert die Anweisung als eine Leitweganweisung.
Fig. 5 stellt eine Anweisung 64 für eine Verbindungsstrecke dar und eine Anweisung 66 für einen Knoten, und zeigt die verschiedenen Felder 68, 70, die das Element identifizieren, und die Daten für die vorher erwähnten Kenndaten enthalten. Die Anweisungsart 72, 74, identifiziert die Anweisungen als Anweisungen einer Verbindungsstrecke oder eines Knotens. Die über die Anweisungen für den Leitweg, die Verbindungsstrecke und die Knoten eingegebene Information wird in üblicher Weise in der Art gespeichert, daß sie für das Abfragen und Vergleichen verfügbar ist, wenn eine Leitweganforderung empfangen wird, um zuerst alle Leitwege, die zwischen den angegebenen Endknoten identifiziert sind, abzurufen und zweitens die beste Übereinstimmung der Kenndaten für die Elemente in den ausgewählten Leitwegen mit den angegebenen Kenndaten zu finden und dadurch den besten Leitweg auszuwählen.
Wenn ein Endbenutzer mit einem anderen Endbenutzer in eine Nachrichtenverbindung einzutreten wünscht, wird eine Sitzung des Steuerprogramms angefordert, das in dem Ursprungsknoten resident ist. Die Sitzungsanforderung schließt die Namen des Quellen- und des Bestimmungsknotens ein, die die Endbenutzer unterstützen, und eine Service-Klasse. Die Service-Klasse ist eine vereinbarte Kurzschrift für einen Satz der vorher erwähnten Kenndaten des auszuwählenden Leitwegs. Bei dem bevorzugten Ausführungsbeispiel wird die Information in der Sitzungsanforderung als eine Nachricht, künftig als Nachricht LEITWEGANFORDERUNG bezeichnet, zu der nächsten verfügbaren Topologie-Datenbank zur Auswahl eines Leitweges abgeschickt Fig. 6 stellt eine Nachricht 76 LEITWEGANFORDERUNG dar. Sie besteht aus einem Anforderungscode 78, der die Nachricht als eine LEITWEGANFORDERUNG identifiziert, dem Namen 79 des Ursprungsknotens, dem Namen 80 des Bestimmungsknotens und dem Namen 82 der Service-Klasse.
Beim Empfang der Nachricht LEITWEGANFORDERUNG wählt die Topologie-Datenbank einen möglichen Leitweg aus, dessen Elemente den Kenndaten entsprechen, die in der angegebenen Service-Klasse identifiziert sind. Wenn ein Leitweg mit genau dem gleichen Satz von Elementen mit den gleichen Kenndaten bereits benutzt wird, dann wird die Sitzung dem bereits geschaffenen Leitweg zugeordnet. Wenn ein Leitweg noch nicht geschaffen wurde, wird die Topologie-Datenbank abgefragt, um den besten Leitweg zwischen dem Quellen- und dem Bestimmungsknoten aufgrund der Übereinstimmung der aktuellen Elementkenndaten mit den geforderten Kenndaten auszuwählen. In diesem Prozeß können nur Knoten und Verbindungsstrecken ausgewählt werden, die als funktionsfähig angenommen werden oder bekannt sind. Der ausgewählte Leitweg wird dann in einer Nachricht beschrieben, die eine Liste der Knoten und Verbindungsstrecken enthält, die den Leitweg bilden, zusammen mit einer eindeutigen Leitwegidentifizierung (Leitweg ID) für den Leitweg, die künftig als Nachricht LEITWEG AUFBAUEN bezeichnet wird. Fig. 7 stellt eine Nachricht 84 LEITWEG AUFBAUEN dar. Der Anforderungscode 86 identifiziert die Nachricht als eine Nachricht LEITWEG AUFBAUEN. Die Leitweg ID 87 identifiziert den Leitweg. Die Namen 88 der Knoten und Verbindungsstrecken erscheinen in der Reihenfolge, in der eine Nachricht den Leitweg durchläuft, wie bei der Leitweganweisung 58 (Fig. 4 oben).
Leitwegelemente werden anfangs als funktionsfähig angenommen, da der Zustand jedes Netzwerkelementes unbekannt ist, wenn die Topologie-Datenbank aktiviert wird. Anstatt sich anfänglich den Status jedes Elementes zu verschaffen, der in der Topologie- Datenbank durch eine Eingabe durch den Operator, durch Austausch mit anderen Datenbanken oder durch Abfrage jedes Netzwerkelementes definiert ist, kann der Zustand durch Benutzen des bevorzugten Ausführungsbeispieles der vorliegenden hierin beschriebenen Erfindung erfahren werden, wenn Sitzungen angefordert werden.
Wenn die Nachricht LEITWEG AUFBAUEN das Netzwerk durchläuft, schafft jeder aktive Knoten Einträge in die Leitwegtabelle in üblicher Weise für beide Verbindungsrichtungen. D.h., wenn die Nachricht LEITWEG AUFBAUEN verarbeitet wird, wird ein Eintrag in die Leitwegtabelle gemacht, der die Leitweg ID (einschließlich der Namen oder Adressen des Ursprungs- und Bestimmungsknotens) enthält und die Adresse der Ausgangsverbindungsstrecke. Wie bekannt erlaubt dies danach eine schnelle Leitwegwahl für Nachrichten über die Leitweg ID, die die Nachricht begleitet. Wenn eine Nachricht mit dieser Information eintrifft, ergibt eine einfache Tabellenabfrage die Adresse der Ausgangsverbindungsstrecke, was ausreicht, um die Nachricht auf ihren Weg zu schicken.
Bei einem alternativen Ausführungsbeispiel wird die Leitweg ID auf eine einzige Identifizierung des lokalen Weges (LWID) in jedem Knoten reduziert, die eine nacheinander ausgewählte, mit Null beginnende Zahl sein kann, die einem Leitweg zugeordnet wird, wenn die Nachricht LEITWEG AUFBAUEN für diesen Leitweg eintrifft. Die LWID wird in die Tabelle eingetragen und zum vorhergehenden Knoten zurückgeschickt zum Eintragen in die Leitwegtabelle dieses Knotens. Jede Leitwegtabelle besitzt bei diesem Ausführungsbeispiel die LWID, die sie überträgt, die Ausgangsverbindungsstrecke zum nächsten Knoten und die LWID, die durch den nächsten Knoten im Leitweg zugeordnet wird. Wenn bei diesem Ausführungsbeispiel eine Nachricht an einem Knoten ankommt, wird die LWID für diesen Knoten von dem Kennsatz getrennt und dazu benutzt, den Tabelleneintrag für diese Sitzung zu lokalisieren. Die LWID für den nächsten Knoten, die in der Tabelle angeordnet ist, wird dann gegen die eintreffende LWID ausgetauscht. Die Nachricht wird dann über die zugeordnete Ausgangsverbindungsstrecke zu dem nächsten Knoten geschickt und so weiter. Fig. 8 zeigt eine Leitwegtabelle 90, die einen einseitig gerichteten Eintrag 88 für einen hypothetischen Leitweg einschließt, bei Benutzung des LWID-Verfahrens. Wie gezeigt, gibt es drei Elemente für einen Eintrag, eine LWID 94, die ID 96 für die Ausgangsverbindungsstrecke und die LWID für den nächsten Knoten 98.
Nachdem die für den Eintrag der Leitwegtabelle notwendige Information von der Nachricht LEITWEG AUFBAUEN getrennt ist, wird sie zu dem nächsten Element geschickt usw., um alle die für den Leitweg notwendigen Tabelleneinträge zu schaffen. Wenn alle Knoten und Verbindungsstrecken für einen Leitweg von Punkt zu Punkt aktiv sind, ist die Nachricht LEITWEG AUFBAUEN erfolgreich und ein Leitweg von Punkt zu Punkt wird geschaffen.
Jeder Eintrag in eine Leitwegtabelle in jedem durchlaufenen Knoten wird als funktionsfähig markiert. Wenn ein Knoten die Nachricht LEITWEG AUFBAUEN nicht zu dem nächsten Knoten weiterleiten kann, weil entweder die Verbindungsstrecke zu dem Knoten oder der Knoten selbst
funktionsunfähig ist, dann wird eine Nachricht LEITWEGFEHLER erzeugt, die die funktionsunfähige Verbindungsstrecke oder den Ursprung des Leitweges zurückgeschickt wird zur Übermittlung an die Topologie-Datenbank. Der funktionsunfähige Status wird in der Topologie-Datenbank markiert und das Netzwerkelement wird in nachfolgenden Nachrichten LEITWEG AUFBAUEN nicht benutzt, bis sein Status sich ändert.
Wenn die Nachricht LEITWEGFEHLER durch jeden Knoten, der in der Nachricht LEITWEG AUFBAUEN identifiziert ist, zurückkehrt, bleibt der Eintrag in die Leitwegtabelle jedes Knotens intakt, wobei der Status des Leitweges als funktionsunfähig markiert wird. Diese Tabelleneinträge werden benutzt für den Rückmeldungsmechanismus zu dem Endknoten (und seiner Topologie- Datenbank), wenn das fehlerhafte Element reaktiviert wird. Die Nachricht LEITWEG FEHLERHAFT wird übertragen durch Befolgen der Einträge in der Leitwegtabelle des Knotens, die von der fehlerhaften Nachricht LEITWEG AUFBAUEN veranlaßt wurden. Fig. 9 zeigt eine Nachricht 100 LEITWEGFEHLER für ein auf einer LWID basierendes Netzwerk. Sie schließt einen Anforderungscode 102 ein, der die Nachricht als eine Nachricht LEITWEG FEHLERHAFT identifiziert, die Knoten ID 104 des Knotens, der den Fehler feststellte, die ID 106 des fehlerhaften Elementes und die nächste LWID 108.
Wenn der Knoten, der einen LEITWEGFEHLER (der "benachbarte" Knoten) meldete, feststellt, daß das funktionsunfähige Element anschließend wieder funktionsfähig wurde, wird eine Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG geschaffen und zu dem Ursprungsknoten zur Übermittlung an seine Topologie-Datenbank gesandt. Die Topologie-Datenbank stellt dann den Statuseintrag des Elementes auf funktionsfähig zurück. Das Element ist dann für nachfolgende Versuche LEITWEG AUFBAUEN verfügbar. Die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG ist mit der Nachricht LEITWEGFEHLER identisch (100, Fig. 9) mit der Ausnahme, daß der Anforderungscode sie als eine Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG identifiziert.
Wenn mehr als ein Leitweg versucht hätte, das funktionsunfähige Element zu benutzen, wäre mehr als ein Satz von Einträgen in die Leitwegtabelle in dem benachbarten Knoten geschaffen worden und für so viele dieser Sätze von Einträgen wie geschaffen wurden, wären Nachrichten LEITWEGELEMENT FUNKTIONSFÄHIG geschaffen und zu den entsprechenden Ursprungsknoten zurückgeschickt worden, um ihre Einträge in der Topologie-Datenbank für das Element auf funktionsfähig zurückzustellen.
Dieser Hinweis läuft zu dem Ursprungsknoten des Leitweges indem er den Einträgen in der Leitwegtabelle des Knotens folgt, die von der fehlerhaften Nachricht LEITWEG AUFBAUEN aufgestellt wurden, in der gleichen Weise wie die Nachricht LEITWEGFEHLER.
Das gleiche Verfahren wird benutzt, nachdem ein Leitweg von Punkt zu Punkt erfolgreich aufgebaut wurde und ein Fehler auf einer Verbindungsstrecke oder einem Knoten in dem Leitweg auftritt. Die gleiche Nachricht LEITWEG FEHLERHAFT wird zurückgeschickt, in diesem Fall zu beiden Endknoten, dem Ursprungs- und dem Bestimmungsknoten, zur Übermittlung an die Topologie-Datenbank jedes Endknotens. Die Nachricht LEITWEGFEHLER identifiziert das fehlerhafte Element und wie in dem anfänglichen Fall des Fehlers beim Aufbau des Leitweges, bleiben die Einträge in der Leitwegtabelle in den Leitwegsegmenten zu den Endknoten intakt, wenn die Nachricht zum Endknoten zurückläuft. Wie in dem vorigen Fall, bei dem das fehlerhafte Element funktionstüchtig wurde, werden die Einträge in der Leitwegtabelle des Knoten durch Nachrichten LEITWEGELEMENT FUNKTIONSFÄHIG benutzt, (eine in jeder Richtung rings um den Punkt des Fehlers), um den Leitweg zurückzuverfolgen bis zu dem Endknoten zur Übermittlung an die Topologie-Datenbank(en), um den funktionsfähigen Zustand des Netzwerkelementes anzuzeigen.
In jedem Fall werden, wenn die Nachrichten LEITWEGELEMENT FUNKTIONSFÄHIG zu der (den) Topologie-Datenbankdo(en) läuft, die Einträge in der Leitwegtabelle der Knoten längs des Leitweges entfernt, um Platz in der Leitwegtabelle zurückzugewinnen, so als wenn der Leitweg von Punkt zu Punkt nach dem Ende aller Sitzungen, die den Leitweg benutzten, normal gelöscht worden wäre.
Der Rückmeldungsmechanismus funktioniert sowohl angesichts eines einzelnen Fehlerpunktes als auch mehrerer Fehlerpunkte längs des Leitweges, wie das im einzelnen unten beschrieben wird.
Die Grundelemente des Rückmeldungsmechanismus des bevorzugten Ausführungsbeispieles können durch einen Satz von Regeln, Definitionen, Zuständen und Protokollen beschrieben werden, die auf irgendein Übertragungsnetzwerk angewandt werden können, das die dynamische Leitwegwahl der hier beschriebenen Art aufweist. Die Protokolle werden für vier Betriebsfälle beschrieben.

REGELN FÜR DEN BETRIEB, DEFINITIONEN & ZUSTÄNDE

Topologie-Datenbank

Es existiert eine oder mehrere Topologie-Datenbanken, die den Netzwerkknoten, die Verbindbarkeit und Statusdaten enthalten, die benutzt werden können, um einen Leitweg von Punkt zu Punkt durch ein Übertragungsnetzwerk auszuwählen.
Für jedes Leitwegelement (d. h. für jeden Netzwerkknoten, der entweder ein Quellen- ein Bestimmungs- oder ein Zwischenknoten sein kann, ein Leitrechner oder ein Nachrichtenübertragungsrechner und für jede Verbindungsstrecke, die entweder eine Datenfernverarbeitungsverbindung, eine Kanalverbindung, eine lokale Datenfernverarbeitungsschleife, ein Netzwerk für einen lokalen Bereich, eine Glasfaserleitung oder irgendein anderes Medium sein kann, das zwei Leitrechner- oder Übertragungsprozessorknoten verbinden kann), gibt es einen Satz von Parametern wie folgt: Element Identifizierungen Verbindbarkeit Kenndaten Status Knoten Knotenname Knotenadresse benachbarte Knoten Kapazität des Nachrichtenspeichers Verarbeitungsleistung Sicherheit funktionsfähig funktionsunfähig unbekannt/(als funktionsfähig angenommen) Verbindungsstrecke Verbindungsstreckenname Verbindungsstreckenadresse benachbarte Knoten Bandbreite Zuverlässigkeit Sicherheit funktionsfähig funktionsunfähig unbekannt/(als funktionsfähig angenommen)
Verschiedene Verfahren können benutzt werden, um die Einträge und die Kenntnis über die Elemente in der Topologie-Datenbank zu schaffen. Sie schließen ein die Eingabe durch den Operator, einen Systemerzeugungsprozeß, die automatische Identifizierung eines Elementes bei der Aktivierung des Elementes usw.

2. Leitwegauswahlalgorithmus

Der (die) Algorithmus (Algorithmen), der (die) benutzt wird (werden), um einen Leitweg auszuwählen (d. h. sicher, geringste Verzögerung, größte Bandbreite usw.), sollte(n) die Anwendbarkeit der Erfindung in einem Netzwerk nicht berühren, vorausgesetzt, daß der Auswählalgorithmus an den Regeln zur Schaffung einer Liste des ausgewählten Leitweges und des oben beschriebenen Elementstatus festhält.

3. Leitweganforderungsmechanismus

Ein Mechanismus wird bereitgestellt, um es einem Benutzer zu erlauben, einen Leitweg von Punkt zu Punkt von einem Quellenknoten durch das Netzwerk hindurch zu einem Bestimmungsknoten anzufordern. Diese Anforderung wird zu einer Topologie- Datenbank geschickt mit einer Anzeige der gewünschten Kenndaten (sicher, geringste Verzögerung usw.). Die Anforderung leitet den Prozeß zur Leitwegauswahl in der Topologie-Datenbank ein und schafft eine Nachricht LEITWEG AUFBAUEN.

4. Nachricht LEITWEG AUFBAUEN

Dies ist eine Nachricht, die die Liste der ausgewählten Knoten und Verbindungsstrecken enthält, um einen Leitweg von Punkt zu Punkt von einem Quellen- zu einem Bestimmungsknoten zu schaffen. Die Nachricht LEITWEG AUFBAUEN durchläuft das Netzwerk von der Quelle zur Bestimmung, vom Knoten zur Verbindungsstrecke, zum Knoten,zur Verbindungsstrecke usw. in der in der Nachricht LEITWEG AUFBAUEN angegebenen Reihenfolge. Während sie den vorgeschlagenen Leitweg durchläuft, werden Leitwegtabellen in jedem durchlaufenen Knoten geschaffen, wobei die Verbindungen zum benachbarten Knoten in Vorwärts- und Rückwärtsrichtung durch Einträge in der Leitwegtabelle angezeigt werden. Die Nachricht LEITWEG AUFBAUEN kann eine von zwei Antworten erhalten:
Die Nachricht LEITWEG AUFBAUEN-ANTWORT oder die Nachricht LEITWEGFEHLER.

5. Nachricht LEITWEGAUFBAUEN-ANTWORT

Diese Nachricht wird von der Bestimmung zurück zur Quelle bei erfolgreichem Schaffen eines Leitweges ausgegeben.

6. Die Nachricht LEITWEGFEHLER

wird bei einem fehlerhaften Versuch LEITWEG AUFBAUEN zurückgeschickt und beim Fehler eines Elementes in einem erfolgreich geschaffenen Leitweg. Wenn im Falle eines fehlerhaften Versuchs LEITWEG AUFBAUEN ein Netzwerkknoten die Nachricht LEITWEG AUFBAUEN nicht an seinen Nachbarn weiterleiten kann, schafft er eine Nachricht LEITWEGFEHLER. Diese Nachricht, die in Fig. 9 dargestellt ist, wird zur Quelle zurückgeschickt, um zur Topologie-Datenbank weitergeleitet zu werden. Diese Nachricht LEITWEGFEHLER zeigt an, welcher Knoten das funktionsunfähige Netzwerkbetriebsmittel feststellte. Die Topologie-Datenbank speichert den Status des funktionsunfähigen Elementes (d. h. L3) und benutzt dieses Element für andere Versuche LEITWEG AUFBAUEN nicht wieder, bis daß sie anschließend durch die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG davon informiert wird, daß das Element funktionsfähig ist. Im Falle des Fehlers eines Elementes in einem aufgebauten Leitweg, wird die gleiche Nachricht LEITWEGFEHLER erstellt und für den gleichen Zweck, aber in diesem Fall wird sie zu den beiden beteiligten Endknoten geschickt.

7. Die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG

wird von einem Knoten erstellt, wenn er die Wiederaktivierung eines funktionsunfähigen Elementes feststellt. Die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG wird erstellt und abgeschickt, vorausgesetzt, daß eine Nachricht LEITWEG AUFBAUEN vorher zu dem Element floß, das sich von funktionsunfähig in funktionsfähig änderte. Die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG durchläuft das Netzwerk zurück zum Ursprungsknoten unter Benutzung der von der früheren Nachricht LEITWEG AUFBAUEN stammenden Einträge in die Leitwegtabelle.

8. Nachricht LEITWEG LÖSCHEN

Diese Nachricht wird auf den Leitweg geschickt, um zu signalisieren, daß der Leitweg nicht länger benötigt wird. Sie wird durch die Endpunkte des Leitweges (entweder Quellen- oder Bestimmungsknoten) erstellt, wenn alle Sitzungen, die einem speziellen Leitweg von Punkt zu Punkt zugeordnet wurden, beendet sind. Wenn die Nachricht LEITWEG LÖSCHEN durchläuft, gibt jeder Knoten auf ihrem Weg die Einträge der Leitwegtabelle, die diesem speziellen Leitweg zugeordnet waren, frei und leitet die Nachricht auf dem Leitweg weiter, der gelöscht wird. Die Nachricht LEITWEG LÖSCHEN hat keine Wirkung auf den Elementstatus in der Topologie-Datenbank, da diese Nachricht nur auf aktiven Leitwegen ausgegeben wird und der Element status nicht von ihren augenblicklichen Zustand FUNKTIONSFÄHIG geändert wird.

9. Betriebsmittelzustand

Jedes Element (Knoten, Verbindungsstrecke) kann drei Zustände einnehmen: UNBEKANNT- ALS FUNKTIONSFÄHIG ANGENOMMEN (UNB) FUNKTIONSFÄHIG (FU) oder FUNKTIONSUNFÄHIG (FUU). Wenn ein Element sich in dem Zustand FU oder UNB befindet, kann es für Zwecke der Leitwegauswahl benutzt werden. In dem Zustand FUU kann das Element nicht für die Leitwegauswahl benutzt werden, bis es als UNB oder FU markiert wurde.

a) EINSTELLEN DES ZUSTANDES UNBEKANNT-ALS FUNKTIONSFÄHIG ANGENOMMEN

1) Alle Elemente werden als UNB angesehen, wenn die Topologie- Datenbank aktiviert wird, ebenso wie ein neues Element, wenn es zu einer bereits vorhandenen Topologie-Datenbank hinzugefügt wird.
2) Ein Element in dem Zustand FUU wird in UNB geändert, wenn ein anderes Element auf dem gleichen FUU Leitweg, aber näher an der Topologie-Datenbank, ebenfalls fehlerhaft ist. Dies geschieht, um sicherzustellen, daß ein Element nicht unbegrenzt in dem Zustand FUU bleibt, weil eine Meldung LEITWEGELEMENT FUNKTIONSFÄHIG die Topologie-Datenbank aufgrund eines zweiten Aus falls nicht erreichen kann.

b) EINSTELLEN DES ZUSTANDES FUNKTIONSFÄHIG

1) Elemente wechseln von UNB zu FU, wenn eine Nachricht LEITWEG AUFBAUEN-ANTWORT empfangen wird.
2) Elemente wechseln von FUU zu FU, wenn ein Element, das den Erfolg einer Anforderung LEITWEG AUFBAUEN verhindert, funktionsfähig wird, und das Erzeugen einer Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG veranlaßt.

c) EINSTELLEN DES ZUSTANDES FUNKTIONSUNFÄHIG

1) EIN LEITWEGFEHLER, der aus einem Versuch LEITWEG AUFBAUEN resultiert, verursacht eine Zustandsänderung nach FUU für das als funktionsunfähig identifizierte Element, über das die Nachricht LEITWEG AUFBAUEN nicht weitergegeben werden konnte.
2) Ein Hinweis LEITWEGFEHLER auf einem aktiven Leitweg verursacht eine Zustandsänderung nach FUU für das als fehlerhaft identifizierte Element.

10. Knoten-Leitwegtabellen

Jeder Netzwerkknoten enthält eine Knoten-Leitwegtabelle, die benutzt wird, um Nachrichten durch das Netzwerk zu leiten. Die Knoten-Leitwegtabelle wird unter Benutzung des Mechanismus LEITWEG AUFBAUEN dynamisch angelegt, wie das durch die Leitwege gefordert wird. Jeder Eintrag besteht aus Vorwärts- und Rückwärtszeigern auf die Ausgangswarteschlangen, die mit dem "nächsten Teil" der Nachrichtenreise in jeder Richtung verbunden sind, als auch aus dem Status oder Zustand des Eintrags. Wenn der Knoten der Quellen- oder Bestimmungsknoten für den Leitweg ist, wird dies auch in dem Tabelleneintrag angezeigt.
Es gibt zwei weitere Zustände, die jeder Eintrag einer Knoten- Leitwegtabelle aufweisen kann: FU oder FUU. Der Zustand FU wird gesetzt, wenn der Leitweg erstellt wird. Der Zustand FUU wird durch die folgenden Bedingungen gesetzt:
a) Ein Hinweis: LEITWEGFEHLER wird zurückgemeldet von einem Versuch LEITWEG AUFBAUEN.
b) Ein Hinweis LEITWEGFEHLER wird von einem aktiven Leitweg empfangen.
Der Zustandseintrag in der Leitwegtabelle kann durch einen Operator für Informationszwecke (z. B. Operatornachfragen) benutzt werden und durch einen Knoten, um weitere Nachrichten auf einem aufgebauten Leitweg abzuschneiden, der eine Nachricht LEITWEGFEHLER aufweist, die zu ihm zurückläuft, wodurch wertvolle Verbindungszeit freigegeben wird.

11. Protokolle

Der Rückmeldungsmechanismus des bevorzugten Ausführungsbeispiels der vorliegenden Erfindung schließt bestimmte Protokolle ein, um den richtigen Hinweis der Topologie-Datenbank(en) über den Status der Betriebsmittel auf einem dynamisch erstellten Leitweg innerhalb eines Netzwerkes sicherzustellen.
Diese Protokolle werden beschrieben unter Benutzung von vier Fällen, die kritische Netzwerkereignisse erfassen. Sie sind:
1) Der Hinweis der Topologie-Datenbank, wenn ein fehlerhaftes Element (eines in einem vorher benutzten Leitweg) reaktiviert wird.
2) Der Doppelfehlerfall, bei dem zwei Elemente auf einem aktiven oder noch nicht aktiven Leitweg ausfallen.
3) Die Entdeckung eines funktionsunfähigen Elementes während eines Versuchs LEITWEG AUFBAUEN.
4) Der Ausfall eines Elementes in einem noch nicht aktiven Leitweg, nachdem die Nachricht LEITWEG AUFBAUEN die fehlerhafte Verbindungsstrecke passiert hat, aber bevor die Nachricht LEITWEGAUFBAU-ANTWORT über die ausgefallene Verbindungsstrecke zurückgeschickt wurde.

Fall 1: Leitwegausfall und nachfolgender Hinweis nach der Fehlerbehebung

Es werde angenommen, daß ein dynamischer Leitweg A-L1-B-L2-C-L3-D-L4-E in dem in Fig. 10 dargestellten Netzwerk 110 für eine Sitzung zwischen den Knoten A und E erstellt wurde. In den Knoten A, B, C, D und E sind die Zustandseinträge der Leitwegtabelle FU. Es werde angenommen, daß am Knoten A eine Topologie-Datenbank 112 benutzt wurde, um die Leitwegelemente, die diesen Leitweg umfassen, auszuwählen, und daß die Zustände all der Netzwerkelemente der Datenbank FU sind. Die Betriebsregeln sind wie folgt, wobei ein Ausfall der Verbindungsstrecke L2 angenommen wird und die Verarbeitung an den Knoten B und A betrachtet wird. Die Verarbeitung an den Knoten C und E wäre ähnlich.
a) Der Ausfall von L2 wird durch beide Knoten B und C festgestellt.
b) In diesem Beispiel erstellt der Knoten B eine Nachricht LEITWEGFEHLER und schickt sie zu dem Knoten A zur Weiterleitung an dessen Topologie-Datenbank.
c) Wenn der Hinweis LEITWEGFEHLER das Netzwerk zum Knoten A durchläuft, wird der Eintrag in die Leitwegtabelle für diesen Leitweg in jedem Knoten in der Richtung weg von dem ausgefallenen Element (d. h. von B nach A) als FUU markiert, aber verbleibt in der Leitwegtabelle des Knotens.
d) Der Hinweis LEITWEGFEHLER veranlaßt die Topologie-Datenbank bei A, die Verbindungsstrecke L2 als FUU zu markieren, so daß sie nachfolgend nicht benutzt wird, um einen anderen Versuch LEITWEG AUFBAUEN durch L2 einzuleiten.
e) Wenn die Verbindungsstrecke L2 funktionsfähig wird, durchsucht der Knoten B seine Knoten-Leitwegtabelle, um die Eintragungen zu finden, die als FUU markiert sind und die vorher die Verbindungsstrecke L2 in ihrem Ausgangsweg benutzten. Dann erstellt der Knoten B Nachrichten LEITWEGELEMENT FUNKTIONSFÄHIG für die Leitwege, die jedem solchen Eintrag entsprechen. In diesem Beispiel zeigt die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG, daß L2 jetzt FU ist und wird längs des Leitweges zurück zum Knoten A übertragen. Jeder Knoten in dem Weg löscht beim Weiterleiten dieser Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG den vorhanden Eintrag FUU aus seiner Knotenleitwegtabelle.
f) Wenn die Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG den Knoten A erreicht, wird sie zu der Topologie-Datenbank, die den Knoten A unterstützt, weitergeleitet. Die Topologie-Datenbank aktualisiert dann ihren Elementstatus für L2 in FU, so daß L2 für einen neuen Versuch LEITWEG AUFBAUEN benutzt werden kann.
Eine ähnliche Verarbeitung erfolgt in der entgegengesetzten Richtung vom Knoten C zum Knoten E einschließlich des Knotens D und zu der Topologie-Datenbank, die den Knoten E unterstützt, wenn die von der des Knotens A verschieden ist.

FALL 2: DOPPELFEHLERFALL

Es werde das gleiche in Fig. 10 dargestellte Netzwerk betrachtet. Es werde wieder angenommen, daß ein Leitweg von A nach E durch jeden Knoten erstellt wurde unter Benutzung von L1, L2, L3 und L4. Es werden die folgenden Ereignisse betrachtet: Zuerst fällt die Verbindungsstrecke L3 aus, dann die Verbindungsstrecke L2. Das folgende tritt ein.
a) Der Knoten C stellt den Fehler L3 fest. Der Knoten C fragt seine Knoten-Leitwegtabelle ab, und wenn er einen Eintrag mit einer Ausgangsverbindungsstrecke L3 findet, schickt er einen Hinweis LEITWEGFEHLER in die entgegengesetzte Richtung, (d. h. zum Knoten B). Die Einträge in den Leitwegtabellen der Knoten C, B und A werden in den Leitwegtabellen belassen, aber als FUU markiert. Am Knoten A wird die Nachricht LEITWEGFEHLER der Topologie-Datenbank übergeben, in der der Elementeintrag für L3 als FUU markiert wird. Eine ähnliche Verarbeitung wird in der Richtung zum Knoten E durchgeführt und der Knoten D stellt den Fehler L3 fest.
b) Wenn anschließend der Knoten B den Fehler L2 feststellt, fragt er seine Knoten-Leitwegtabelle ab, schickt eine Nachricht LEITWEGFEHLER, die L2 als fehlerhaft identifiziert, zu A unter Benutzung des funktionsfähigen Teiles dessen, was als ein bereits funktionsunfähiger Leitweg bekannt ist. Knoten A leitet diesen Hinweis zu der Topologie-Datenbank weiter. Beide Knoten A und B belassen ihre Einträge in der Leitwegtabelle in dem Zustand FUU.
c) Wenn die Topologie-Datenbank diesen zweiten Hinweis LEITWEGFEHLER für denselben Leitweg empfängt, obgleich für ein verschiedenes fehlerhaftes Element, fragt sie ihre Topologie- Datenbank ab und markiert das ursprünglich fehlerhafte Element (L3) als UNB, wenn nicht L3 wegen ihres Vorkommens in einem anderen Leitweg als FUU bekannt ist, und markiert das neuerlich fehlerhafte Element (L2) als FUU. An diesem Punkt können verschiedene Bedingungen eintreten, die sich mit der Zeit befassen, zu der L2 oder L3 funktionsfähig wird. Jede Bedingung wird unten beschrieben.
1) Es werde angenommen, daß L2 funktionsfähig wird, während L3 funktionsunfähig bleibt. Wenn L2 funktionsfähig wird, benutzt der Knoten B das im Fall 1 beschriebene Verfahren, um der Topologie-Datenbank zu melden, daß L2 jetzt verfügbar ist. Ebenso werden die Eintragungen in der Knotentabelle in B und A gelöscht. Die Topologie-Datenbank markiert dann L2 als FU. Eine Anforderung LEITWEG AUFBAUEN kann abgeschickt werden, um den Leitweg (unter der Annahme, daß eine Sitzung den Leitweg zu benutzen wünscht) aufzubauen und scheitert an der Verbindungsstrecke L3.
Das teilweise aufgebaute Leitwegsegment bleibt bestehen, und erwartet, daß L3 wieder funktionsfähig wird.
2) Es werde angenommen, daß L3 funktionsfähig wird, aber L2 nicht. In diesem Fall erhält die Topologie-Datenbank keinen Hinweis, da L2 nicht funktionsfähig ist und den Weg zum Ursprungsknoten A blockiert. Dies verursacht jedoch keine Probleme, da die Topologie-Datenbank angenommen hatte, daß L3 funktionsfähig war (d. h. UNB), nachdem L2 ohnehin ausfiel.
3) Es werde angenommen, daß L3 funktionsfähig wird, wonach L2 funktionsfähig wird. Dies wird wie in den Punkten (2) und (1) oben behandelt, mit der Ausnahme, daß jetzt die Nachricht LEITWEG AUFBAUEN erfolgreich ist, da L3 funktionsfähig ist. Das Verarbeiten dieses Doppelfehlers vom Standpunkt der Knoten D und E ist ähnlich dem von B und A, außer in der entgegengesetzten Richtung. Einträge in der Knoten-Leitwegtabelle in den Knoten D und E werden als FUU markiert für den Verkehr, der in der Richtung auf den Fehler fließt.
Beachte: Wenn ein Eintrag in eine Leitwegtabelle in beiden Richtungen FUU wird, wird der Eintrag in der Tabelle gelöscht. In diesem Fall wird der Knoten isoliert durch den Fehler auf jeder Seite irgendwo längs des Leitweges, und die Eintragungen in der Leitwegtabelle werden nicht für einen späteren Hinweis LEITWEGELEMENT FUNKTIONSFÄHIG benötigt. In diesem Fall löscht der Knoten C den Eintrag in seiner Leitwegtabelle und nur die Knoten B und D übertragen eine Nachricht LEITWEGELEMENT FU zu dem Endpunkt des Leitweges.

FALL 3: ENTDECKUNG EINES FUNKTIONSUNFÄHIGEN ELEMENTES WÄHREND EINES VERSUCHS, EINEN LEITWEG AUFZUBAUEN

Dieser Fall ist ähnlich dem Verarbeiten im Fall 1, mit der Ausnahme, daß anstelle eines Hinweises LEITWEGFEHLER, der auf den vorhanden Leitweg ausgegeben wird, der Fehlerhinweis Teil des Hinweises auf einen Fehler beim LEITWEGAUFBAU wird. Wie im Fall 1 wird das Element in der Topologie-Datenbank, das den Versuch LEITWEG AUFBAUEN stoppte, als FUU markiert. Wenn das funktionsunfähige Element funktionsfähig wird, dann erfolgt die gleiche Verarbeitung wie sie im Fall 1 unter den Punkten (e) und (f) beschrieben wurde

FALL 4: AUSFALL EINES BETRIEBSMITTELS, NACHDEM EINE NACHRICHT LEITWEGAUFBAUEN GERADE DAS FEHLERHAFTE ELEMENT PASSIERT HAT

Dieser Fall ist ähnlich dem Fall 1, mit der Ausnahme, daß der Fehlerhinweis für den Eintrag in die Leitwegtabelle eines noch nicht aktiven Knotens bestimmt ist, (da die LEITWEGAUFBAU- ANTWORT noch nicht empfangen wurde), anstelle eines Eintrags für einen voll aktivierten Knoten. Die Verarbeitung ist die gleiche für den benachbarten Knoten, der den Fehler feststellte. Der Hinweis, daß das fehlerhafte Element wieder funktionsfähig wurde, erfolgt wie im Fall 1 unter den Punkten (e) und (f).
Die oben beschriebenen Protokolle können, wie das vorher erwähnt wurde, in eigentlich jedem Netzwerk mit dynamischer Leitwegwahl implementiert werden, um die Grundsätze des bevorzugten Ausführungsbeispiels der Erfindung durchzuführen. Außerdem können übliche Hilfsmittel, falls erwünscht, zugefügt werden, z. B. die Implementierung von Nachrichtencodes, Befehle des Operators zur Statusabfrage von Eintragungswerten in der Leitwegtabelle und dergleichen.

BEHANDLUNG VOLLER LEITWEGTABELLEN IN NETZWERKKNOTEN

Während des Netzwerkbetriebs können eine oder mehrere Netzwerkknoten ihre Leitwegtabellen bis zu deren Kapazität gefüllt haben, so daß keine weiteren Leitwegeinträge in diesen Knoten vorgenommen werden, bis der Zustand gemildert wird. Die normale Art für das Eintreten solch einer Milderung besteht für Sitzungen darin, zu enden und für Leitwege, die nicht länger benutzt werden, darin, aus dem Netzwerk gelöscht zu werden. Es kann auch wünschenswert sein, daß eine Topologie-Datenbank automatisch eingreift, um Leitwegelemente zu löschen, die auf die Reaktivierung oder Fehlerbehebung irgendeines Hilfsmittels warten, oder einen Netzwerkoperator zu veranlassen, eine Topologie-Datenbank aufzufordern, solch ein Eingreifen vorzunehmen.
Demgemäß ist es möglich, einen Hinweis für eine Topologie- Datenbank auf das Auftreten einer "Voll-" Bedingung einer Leitwegtabelle in einem Netzwerkknoten einzubauen. Der Netzwerkknoten schickt eine Nachricht, die den Besetztzustand der Leitwegtabelle anzeigt, zu seinem Steuerknoten, der seinerseits die Nachricht zu der Topologie-Datenbank in jenem Steuerknoten weiterleitet. Die Topologie-Datenbank annulliert entweder unerledigte Leitweganforderungen, die den betreffenden Knoten berühren, oder fordert ein manuelles Eingreifen durch den Netzwerkoperator beim Treffen der Entscheidung, abhängig von den Anfangseinstellungen in der Topologie-Datenbank. In dem ersten Fall kann dem Netzwerkoperator ein Hinweis gegeben werden, obgleich eine Entscheidung des Operators nicht erforderlich ist.
Wenn die Topologie-Datenbank selbst oder der Netzwerkoperator entscheidet, anstehende Leitweganforderungen von dem Netzwerk zu entfernen, schickt die Topologie-Datenbank die geeignete(n) Anforderung(en) LEITWEG LÖSCHEN längs des (der) aufgebauten Leitwegsegmente(s), um diese Einträge aus den Leitwegtabellen der Knoten in dem Leitwegsegment zu löschen.

ENTFERNEN VON KNOTEN AUS DEM NETZWERK

Ein Netzwerkoperator kann entscheiden, vorübergehend oder dauernd eine Verbindungsstrecke oder einen Knoten aus dem Netzwerk zu entfernen. Solch ein Verbindungsstrecken- oder Knoten- Betriebsmittel kann augenblicklich aktiv sein oder die Reaktivierung erwarten oder die Fehlerbehebung nach einem früheren Fehler. Demgemäß kann ein Befehl des Operators an die Topologie-Datenbank eingeschlossen sein, um die Darstellung eines Betriebsmittels von dem Netzwerk zu entfernen.
Wenn das Betriebsmittel aktiv ist, können Benutzersitzungen, abhängig von dem Betriebsmittel, beendet werden oder es kann ihnen erlaubt werden, normal zu enden, worauf die Leitwege, die das Betriebsmittel einschließen, in normaler Weise durch von einer Topologie-Datenbank stammende Aufforderungen LEITWEG LÖSCHEN gelöscht werden nach dem Empfangen eines Befehls, das Betriebsmittel bei neuen Anforderungen LEITWEG AUFBAUEN zu entfernen.
Wenn ein Verbindungsstrecken- oder ein Knoten- Betriebsmittel die Reaktivierung oder Fehlerbehebung erwartet, wenn sie von dem Netzwerk entfernt wird, werden anhängige Leitweganfoderungen, die von dem Betriebsmittel abhängen, annulliert. Nach dem Empfangen eines Befehls, ein Betriebsmittel aus dem Netzwerk zu entfernen, gibt die Topologie-Datenbank Anforderungen LEITWEG LÖSCHEN heraus für alle anhängigen Leitweganforderungen, die das das entfernte Betriebsmittel einschließen, und versucht nicht, irgendwelche neuen Leitwege, die dieses Betriebsmittel benutzen, aufzubauen.
Die vorliegende Erfindung stellt, wie durch die obige Beschreibung der Ausführungsbeispiele illustriert wird, ein System bereit zum Benachrichtigen einer Topologie-Datenbank eines Netzwerkes von der Verfügbarkeit möglicher Nachrichtenverbindungen unter den verschiedenen Elementen eines Nachrichtenübertragungsnetzwerkes mit stark verringertem Netzwerkverkehr im Vergleich zu Lösungen nach dem Stand der Technik. Die beträchtliche Zunahme der Statusnachrichten in dem Netzwerk wird stark durch die Anwendung der vorliegenden Erfindung verringert und einer minimalen, aber ausreichenden Klasse von Knoten wird die notwendige Verfügbarkeitsinformation gegeben, um Sitzungsleitwege wirksam zu schaffen und mit einem Minimum von unnötiger Benutzung von Netzwerkbetriebsmitteln.

Claims

1. Übertragungsnetzwerk für digitale Datennachrichten, umfassend Knoten (12, 14, 16, 18, 20), die durch Verbindungsstrecken (32,34,36,40,44,) gekoppelt sind, bei dem eine Nachricht zwischen einem Quellenknoten und einem Zielknoten längs eines Leitweges läuft, der eine Folge von Knoten und gekoppelten Verbindungsstrecken umfaßt, und das Netzwerk Mittel zur Wartung einer Topologie-Datenbank (112) einschließt, die die möglichen verfügbaren Nachrichtenverbindungs-Leitwege durch das Netzwerk und den Status der Netzwerkknoten und Verbindungsstrecken aufzeichnet, wobei jeder Knoten eingerichtet ist, um eine Leitwegtabelle zu warten und:

wenn er als Quellenknoten dient, einen Leitweg von der Topologie-Datenbank zu erhalten und eine Nachricht LEITWEG AUFBAUEN längs des Leitweges zu schicken, um dadurch den Leitweg festzulegen,

auf eine Nachricht LEITWEG AUFBAUEN durch Aufzeichnen eines Eintrags in seine Leitwegtabelle mit der Identifizierung des Leitweges und der Verbindungsstrecken und/oder Knoten darin, die dem betreffenden Knoten unmittelbar benachbart sind, zu antworten,

wobei das Netzwerk dadurch gekennzeichnet ist, daß jeder Knoten außerdem eingerichtet ist, um:

jeden Fehler eines unmittelbar benachbarten Knotens oder einer Verbindungsstrecke in dem Leitweg estzustellen,

entweder während des Versuchs, einen Leitweg festzulegen, oder nachdem der Leitweg festgelegt wurde, und als Antwort darauf (i) den Status des Leitweges als funktionsunfähig in dem entsprechenden Eintrag in der Leitwegtabelle des Knotens aufzuzeichnen, wobei der Eintrag im wesentlichen unversehrt bleibt, und (ii) eine Nachricht LEITWEGFEHLER, die den fehlerhaften Knoten oder die fehlerhafte Verbindungsstrecke identifiziert, längs des Leitweges in der zu dem fehlerhaften Knoten oder der fehlerhaften Verbindungsstrecke entgegengesetzten Richtung zu übertragen, auf eine Nachricht LEITWEGFEHLER durch Übermitteln der Nachricht LEITWEGFEHLER längs des Leitweges in entgegengesetzter Richtung und durch (ii) weiteres Aufzeichnen des Status des Leitwegs als funktionsunfähig in dem entsprechenden Eintrag in der Leitwegtabelle des Knotens zu antworten, wobei der Eintrag im wesentlichen unversehrt bleibt, und, wenn er als Quellen- oder Zielknoten arbeitet, zusätzlich die Nachricht LEITWEGFEHLER zu der Topologie-Datenbank zu übertragen, um den aufgezeichneten Status der Knoten und Verbindungsstrecken des Netzwerkes auf den neuesten Stand zu bringen.

2. Netzwerk nach Anspruch 1, bei dem jeder Knoten dafür eingerichtet ist, wenn er die Rückkehr zur Verfügbarkeit eines unmittelbar benachbarten Knotens oder einer Verbindungsstrecke feststellt, eine Nachricht LEITWEGELEMENT FUNKTIONSFÄHIG zu erzeugen, die das anzeigt, welche in der gleichen Weise behandelt wird wie die Nachricht LEITWEGFEHLER.

3. Netzwerk nach Anspruch 2, bei dem es drei gültige Statusarten für jeden Netzwerkknoten oder jede Verbindungsstrecke in der Topologie-Datenbank gibt, FUNKTIONSFÄHIG, FUNKTIONSUNFÄHIG und UNBEKANNT/(ALS FUNKTIONSFÄHIG ANGENOMMEN), wobei der Vorgabezustand UNBEKANNT ist, welcher Status zu dem geeigneten anderen Status als Antwort auf die Nachrichten LEITWEGFEHLER und LEITWEGELEMENT FUNKTIONSTÜCHTIG umgeschaltet wird.

4. Netzwerk nach irgendeinem vorhergehenden Anspruch, bei dem die Topologie-Datenbank Informationen bezüglich der Eigenschaften der Netzwerkknoten und Verbindungsstrecken speichert, und ein Quellenknoten eine Nachricht LEITWEGANFORDERUNG, die die Identifizierung des Quellenknotens, die Identifizierung des Zielknotens und die gewünschten Leitwegeigenschaften angibt,an die Topologie- Datenbank abschickt, welche als Antwort auf solch eine Nachricht einen "am besten geeigneten" funktionstüchtigen Leitweg bestimmt und eine entsprechende Nachricht LEITWEG AUFBAUEN erzeugt, die die ausgewählte Leitwegidentifizierung und die Leitwegelemente der Reihe nach bestimmt.

5. Verfahren zum Steuern eines Übertragungsnetzwerkes für digitale Datennachrichten, umfassend Knoten (12, 14, 16, 18, 20), die durch Verbindungsstrecken (32, 34, 36, 40, 44) gekoppelt sind, in dem eine Nachricht zwischen einem Quellenknoten und einem Zielknoten längs eines Leitwegs läuft, der eine Folge von Knoten und koppelnden Verbindungsstrecken aufweist, wobei das Netzwerk Mittel zur Wartung einer Topologie-Datenbank (112) zum Aufzeichnen der möglichen verfügbaren Nachrichtenverbindungs-Leitwege durch das Netzwerk und des Status der Netzwerkknoten und Verbindungsstrecken einschließt, und jeder Knoten eingerichtet ist, um eine Leitwegtabelle zu warten,

wobei das Verfahren die Schritte umfaßt:

daß ein Quellenknoten einen Leitweg von der Technologie-Datenbank erhält und eine Nachricht LEITWEG AUFBAUEN längs eines Leitwegs sendet, um dadurch den Leitweg aufzubauen, daß jeder Knoten auf eine Nachricht LEITWEG AUFBAUEN durch Aufzeichnen eines Eintrags in seine Leitwegtabelle mit dem Identifizieren des Leitweges und der Verbindungsstrecken und/oder Knoten darin, die unmittelbar zu dem betreffenden Knoten benachbart sind, antwortet,

wobei das Verfahren dadurch gekennzeichnet ist, daß es weiter die Schritte umfaßt, daß:

jeder Knoten jeden Fehler eines unmittelbar benachbarten Knotens oder einer Verbindungsstrecke in dem Leitweg feststellt, entweder beim Versuch, den Leitweg festzulegen, oder nachdem der Leitweg festgelegt wurde, und als Antwort darauf (i) den Status des Leitweges als funktionsunfähig in dem betreffenden Eintrag in der Leitwegtabelle des Knotens aufzeichnet, wobei der Eintrag im wesentlichen unversehrt bleibt, und (ii) eine Nachricht LEITWEGFEHLER, die den fehlerhaften Knoten oder die fehlerhafte Verbindungsstrecke identifiziert, längs des Leitweges in der zum fehlerhaften Knoten oder zur fehlerhaften Verbindungsstrecke entgegengesetzten Richtung überträgt,

wobei jeder Knoten auf eine Nachricht LEITWEGFEHLER durch Abs enden der Nachricht LEITWEGFEHLER längs des Leitweges in der entgegengesetzten Richtung und ferner durch (ii) Aufzeichnen des Status des Leitweges als funktionsunfähig in den entsprechenden Eintrag in der Leitwegtabelle des Knotens antwortet, wobei der Eintrag im wesentlichen unversehrt bleibt und der Quellenknoten und/oder der Zielknoten zusätzlich die Nachricht LEITWEGFEHLER an die Topologie-Datenbank abschickt, um den aufgezeichneten Zustand der Netzwerkknoten und Verbindungsstrecken auf den neuesten Stand zu bringen.