DE69310946T2

DE69310946T2 - Verfahren und Mittel zum Detektieren einer Leitweglenkungsschleife in einem Fernmeldenetz

Info

Publication number: DE69310946T2
Application number: DE69310946T
Authority: DE
Inventors: Franciscus Wilhelmus A Brocken; Cyrillus Godefridus Joa Houben
Original assignee: Koninklijke PTT Nederland NV
Current assignee: Koninklijke KPN NV
Priority date: 1992-02-14
Filing date: 1993-02-10
Publication date: 1997-11-06
Anticipated expiration: 2013-02-11
Also published as: AU3297393A; ES2102590T3; GR3024554T3; JPH0646131A; US5371732A; ATE153817T1; NL9200279A; DE69310946D1; CA2089467A1; CA2089467C; EP0555926B1; JP2860854B2; AU662592B2; EP0555926A1

Description

A. Erfindungshintergrund

Die Erfindung bezieht sich auf ein Verfahren zum Detektieren einer Leitweglenkungsschleife in einem Fernmeldenetz, das mit Knoten ausgerüstet ist, von denen ein jeder knotenspezifische Wegleitinformation enthält, in dem ein Leitweg von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation erstellt wird.
Ein derartiges Verfahren ist in der US 5,014,262 offenbart. In dieser Druckschrift sind zwei Unterverfahren beschrieben: ein erstes Unterverfahren zum Detektieren einer Leitweglenkungsschleife ("Looping" genannt), und ein zweites Unterverfahren zum Detektieren uneffizienter Wegleitung ("Kreisrouting" genannt) Das erste Unterverfahren, das für jeden Zielknoten ausgeführt wird, umfasst vier Schritte; Im ersten Schritt werden alle Knoten, die keinen Verkehr für den Zielknoten empfangen, entfernt, und im zweiten Schritt werden alle Knoten, die keinen Verkehr zum Zielknoten übermitteln, entfernt. Diese zu entfernenden Knoten können daher nicht zu einer Leitweglenkungsschleife gehören. Im dritten Schritt werden alle Knoten, die zu sogenannten Minischleifen gehören, behandelt. Zwei Knoten gehören zu einer Minischleife, wenn einer der Knoten Verkehr für den Zielknoten vom anderen Knoten empfängt und der erste Knoten ebenfalls Verkehr zum anderen Knoten übermittelt. Aus technischen Gründen kann eine Minischleife nie als eine Leitweglenkungsschleife auftreten, da an einer Knotenlage deren Vorgängerknoten, von dem der weiterzuleitende Verkehr herstammt, bekannt ist, und da dieser Verkehr somit sicherlich niemals zum genanten Vorgängerknoten zurückzusenden ist. Im vierten Schritt werden die Knoten, die nicht zu einer Leitweglenkungsschleife gehören, identifiziert. Ein solcher Knoten muss z.B. das Kriterium erfüllen, dass wenn der Knoten Verkehr zu einem anderen Knoten übermittelt, dieser andere Knoten keinen Verkehr zum betreffenden Knoten zurücksenden darf. Wie dieses Kriterium, das tatsächlich bloss mit anderen Worten besagt, dass keine Leitweglenkungsschleife möglich sein darf, erfüllt werden soll, bleibt unklar. Eine Lösung könnte darin bestehen, nach den ersten drei Schritten für alle übrigbleibenden Knoten zu untersuchen, ob der Knoten der am meisten eingehenden und ausgehenden Verkehr aufweist und Verkehr zu einem bestimmten Knoten übermittelt, auch Verkehr von jenem bestimmten Knoten über einen längeren Weg zurückempfängt. Der genannte Knoten wäre dann zu entfernen, und die übrigbleibenden Knoten wären erneut zu untersuchen, usw. Solche Untersuchungen sind, wie das erwähnte Kriterium, jedoch bloss eine andere Formulierung des Problems der Detektierung von Leitweglenkungsschleifen. Dieses bekannte Verfahren, das auf jeden Fall mühsam und daher in Folge zeitraubend ist, hat noch den zusätzlichen Nachteil dass es unsicher ist, ob bestehende Leitweglenkungsschleifen damit auch gefunden werden.

B. Zusammenfassung der Erfindung

Gegenstand der Erfindung ist es, unter anderem, ein Verfahren der eingangs genannten Art zu liefern, das weniger mühsan einzusetzen ist und das das Vorhandensein von Leitweglenkungsschleifen mit an Sicherheit grenzender Wahrscheinlichkeit aufspürt.
Zu diesem Zweck ist das erfindungsgemässe Verfahren dadurch gekennzeichnet, dass während der Erstellung eines Leitweges ein Parameter des genannten Leitweges an jedem folgenden, sich auf dem Leitweg befindenden Knoten um eine Einheit erhöht wird, und dass der in einer Anzahl Einheiten ausgedrückte Parameter eines teilweise erstellten Leitweges dabei mit einem vorbestimmten Wert verglichen wird, und dass ein teilweise erstellter Leitweg, dessen Parameter den genannten Wert überschreitet, als ein eine Leitweglenkungsschleife enthaltender Leitweg detektiert wird.
Der in einer Anzahl Einheiten ausgedrückte Wert des Parameters des teilweise erstellten Leitweges ist zu jedem Zeitpunkt gleich der Anzahl Verbindungsglieder, die zusammen zu diesem Zeitpunkt den genannten, teilweise erstellten Leitweg bilden. Das Erhöhen des Parameters um eine Einheit an jedem folgenden, sich auf dem Leitweg befindenden Knoten ist in diesem Fall äquivalent zum Abzählen der Anzahl Verbindungsglieder, wobei ein Verbindungsglied ein sich zwischen zwei aufeinanderfolgenden Knoten befindendes Wegstück ist. Der genannte Parameter, der daher zu jedem beliebigen Zeitpunkt die Länge des zu diesem Zeitpunkt erstellten Leitweges angibt, ist ein Hinweis auf das Vorhandensein einer Leitweglenkungsschleife. Wenn die Lange eines teilweise erstellten Leitweges, ausgedrückt durch die Anzahl der Verbindungsglieder, die zusammen den teilweise erstellten Leitweg bilden, den vorbestimmten Wert überschreitet, so kann daraus mit an Sicherheit grenzender Wahrscheinlichkeit geschlossen werden, dass eine Leitweglenkungsschleife vorhanden ist. Der genannte vorbestimmte Wert könnte, zum Beispiel, gleich der gesamten Anzahl der am Fernmeldenetz teilnehmenden Knoten gewählt werden, oder als ein kleinerer Wert festgesetzt werden, falls das genannte Fernmeldenetz eine stark vernetzte Struktur aufweist.
Die Erfindung beruht auf der Einsicht, dass es in jedem Fernmeldenetz einen oder mehrere Leitwege gibt, welche die grösstmögliche Länge aufweisen, und dass, sobald die für einen (teilweise erstellten) Leitweg ermittelte Länge jene grösstmögliche Länge überschreitet, dies eine Folge der Gegenwart einer Leitweglenkungsschleife im genannten (teilweise erstellten) Leitweg sein muss.
Obgleich die US 5,014,262 die Detektion ineffizienter Wegleitung ("Kreisrouting") (mit Hilfe des oben erwähnten zweiten Unterverfahrens) offenbart, und zwar durch das Bestimmen der Länge eines erstellten Leitweges und das anschliessende Untersuchen, ob die genannte Länge grösser als nötig ist, was durch Vergleichen der Länge mit einem mit dem Leitweg assoziierten Nominalwert geschieht, so legt das US-Patent keine Detektion einer Leitweglenkungsschleife durch Bestimmen der Länge eines (teilweise erstellten) Leitweges und deren Verglichen mit einem vorbestimmten Wert offen, der grösser oder gleich der grösstmöglichen Weglänge im Fernmeldenetz ist. Das erfindungsgemässe Verfahren löst in der Folge ein Problem, das über eine lange Zeit hinweg existiert hat und das von grosser Bedeutung hinsichtlich der in den letzten Jahren regelmässigen Zusammenbrüche grosser Fernmeldenetze ist, die als Resultat des Vorhandenseins von Leitweglenkungsschleifen auftreten.
Gemäss einem ersten Ausführungsbeispiel ist das erfindungsgemässe Verfahren dadurch gekennzeichnet, dass von zwei Knoten, die sich auf dem zu erstellenden Leitweg befinden und die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, nicht mehr als eine der beiden wegleitmöglichkeiten zum Erstellen des Leitweges verwendet wird.
Zwei Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, bilden eine sogenannte Minischleife, die aus den früher erwähnten technischen Gründen niemals als Wegleitschleife auftreten kann. Das erste Ausführungsbeispiel des erfindungsgemässen Verfahren berücksichtigt dies dadurch, dass nie mehr als eine der beiden Wegleitmöglichkeiten verwendet wird.
Gemäss einem zweiten Ausführungsbeispiel ist das erfindungsgemässe Verfahren dadurch gekennzeichnet, dass alle Knoten aufeinanderfolgend als Zielknoten, und alle übrigbleibenden Knoten aufeinanderfolgend als Quellenknoten für jeden Zielknoten fungieren.
Bei diesem Verfahren werden alle Leitwege zwischen einerseits allen möglichen Quellenknoten, und andererseits allen möglichen Zielknoten auf das Vorhandensein von Leitweglenkungsschleifen untersucht. Dies kann durch das Erstellen aller möglichen Leitwege von einem Quellenknoten zum Zielknoten geschehen, wobei diese Operation für alle verbleibenden Quellenknoten wiederholt wird. Es ist ebenfalls möglich, zuerst zu versuchen, den Zielknoten vom Quellenknoten aus mit einem Leitweg der Länge 1 zu erreichen, und dann diese Operation für alle Quellenknoten mit einer jedesmal zunehmenden Länge zu wiederholen.
Die Erfindung bezieht sich ferner auf ein Fernmeldenetz zum Gebrauch des. erfindungsgemässen Verfahrens, das ausgestattet ist
- mit Knoten, die jeweils knotenspezifische Wegleitinformation enthalten, und
- mit Detektionsmitteln, die Leitwegerstellungsmittel zur Erstellung eines Leitweges von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation umfassen.
Es ist weiterhin ein Ziel der Erfindung, ein Fernmeldenetz des oben beschriebenen Typs zu schaffen, welches das Vorhandensein von Leitweglenkungsschleifen in einer nicht aufwendigen Weise und mit an Sicherheit grenzender Wahrscheinlichkeit detektiert.
Zu diesem Zweck ist das erfindungsgemässe Fernmeldenetz dadurch gekennzeichnet, dass die Detektionsmittel weiter ausgestaltet sind
- mit Zählmitteln zum Erhöhen einer Zählerstellung um eine Zähleinheit an jedem folgenden, sich auf dem Leitweg befindenden Knoten während des Erstellens des genannten Leitweges, und
- mit Vergleichsmitteln zum Vergleichen der mit einem teilweise erstellten Leitweg assoziierten Zählerstellung mit einem vorbestimmten Zählerwert, und zum Erzeugen eines Alarmsignales falls dieser letztere überschritten wird.
In diesem Zusammenhang ist die Zählerstellung der Zählmittel, ausgedrückt als Anzahl von Zähleinheiten, gleichwertig zur Anzahl der Verbindungsglieder, die zusammen den (teilweise erstellten) Leitweg bilden, und es drückt daher die Länge des genannten Leitweges aus. Die Vergleichsmittel werden benutzt, um die Zählerstellung, und folglich die Länge des teilweise erstellten Leitweges, mit dem vorbestimmten Zählerwert zu vergleichen, der grösser oder gleich der grösstmöglichen Weglänge im Fernmeldenetz ist, und der zum Beispiel gleich der totalen Anzahl Knoten gewählt werden kann, die am Fernmeldenetz teilnehmen. Falls dieser Wert überschritten wird, so zeigt das zu erzeugende Alarmsignal, mit an Sicherheit grenzender Wahrscheinlichkeit, das Vorhandensein einer Leitweglenkungsschleife an.
Bei einem ersten Ausführungsbeispiel ist das erfindungsgemässe Fernmeldenetz dadurch gekennzeichnet, dass die Detektionsmittel mit Vernachlässigungsmitteln ausgestattet sind, zum Vernachlässigen von mindestens einer von zwei Wegleitmöglichkeiten in der Erstellung eines Leitweges, im Falle von zwei sich auf dem zu erstellenden Leitweg befindenden Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben.
Zwei solche Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, bilden eine sogenannte Minischleife, welche, wie oben beschrieben, nie als Leitweg auftreten kann. Die erste Ausführung des erfindungsgemässen Fernmeldesystems umfasst Vernachlässigungsmittel, zum Vernachlässigen von mindestens einer der beiden Wegleitmöglichkeiten
Bei einem zweiten Ausführungsbeispiel ist das erfindungsgemässe Fernmeldenetz dadurch gekennzeichnet, dass die Detektionsmittel mit Auswahlmitteln ausgestattet sind, um aufeinanderfolgend alle Knoten als Zielknoten und um aufeinanderfolgend alle übrigbleibenden Knoten als Quellenknoten für jeden ausgewählten Zielknoten auszuwählen.
Durch den Gebrauch der Auswahlmittel werden alle Leitwege im Fernmeldenetz, zwischen einerseits allen möglichen Quellenknoten, und andererseits allen möglichen Zielknoten, auf das Vorhandensein von Leitweglenkungsschleifen untersucht.
Die Erfindung bezieht sich weiterhin auf ein Detektionssystem für den Gebrauch im erfindungsgemässen Fernmeldesystem, welches Leitwegerstellungsmittel zum Erstellen eines Leitweges von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation umfasst.
Die erfindungsgemässen Detektionsmittel sind dadurch gekennzeichnet, dass die Detektionsmittel weiter ausgestaltet sind
- mit Zählmitteln zum Erhöhen einer Zählerstellung um eine Zähleinheit bei jedem folgenden, sich auf dem Leitweg befindenden Knoten während des Erstellens des genannten Leitweges, und
- mit Vergleichsmitteln zum Vergleichen der mit dem teilweise erstellten Leitweg assoziierten Zählerstellung mit einem vorbestimmten Zählerwert und zum Erzeugen eines Alarmsignales in dem Falle, dass dieser letztere überschritten wird.
Bei einem ersten Ausführungsbeispiel sind die erfindungsgemässen Detektionsmittel dadurch gekennzeichnet, dass sie mit Vernachlässigungsmitteln ausgestaltet sind, um mindestens eine von zwei Wegleitmöglichkeiten in der Erstellung eines Leitweges im Falle von zwei sich auf dem zu erstellenden Leitweg befinden Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, zu vernachlässigen.
Bei einem zweiten Ausführungsbeispiel sind die erfindungsgemässen Detektionsmittel dadurch gekennzeichnet, dass die Detektionsmittel mit Auswahlmitteln ausgestattet sind, um aufeinanderfolgend alle Knoten als Zielknoten und um aufeinanderfolgend alle übrigbleibenden Knoten als Quellenknoten für jeden ausgewählten Zielknoten auszuwählen.
Die Detektion einer Leitweglenkungsschleife im Fernmeldenetz durch das Erstellen von Leitwegen und anschliessendes Untersuchen, ob die Länge der genannten Leitwege einen bestimmten Wert überschreitet, kann entweder durch tatsächliches Erstellen von Leitwegen erfolgen, oder aber durch Erstellen von Leitwegen in simulierter Weise. Im ersten Fall erfolgt das Erstellen tatsächlich aufgrund der mit den Knoten assoziierten, knotenspezifischen Wegleitinformation, wohingegen im zweiten Fall ebenfalls zentrale Speichermittel zum Einsatz kommen können, in denen die knotenspezifische Wegleitinformation aller Knoten gespeichert ist.

C. Referenz

US 5,014,262

D. Ausführungsbeispiel

Die Erfindung wird nun genauer erläutert unter Bezugnahme auf ein in den Figuren dargestelltes Ausführungsbeispiel. Es zeigen:
Figur 1 ein Flussdiagramm eines Ausführungsbeispiels des erfindungsgemässen Verfahrens,
Figur 2 & 3 ein Fernmeldenetz gemäss der Erfindung, das mit Knoten und Detektionsmitteln ausgestattet ist, die eine Leitweglenkungsschleife detektieren, und
Figur 4 eine detailliertere Wiedergabe der Detektionsmittel.
Im Flussdiagramm von Figur 1 haben die Blöcke die folgende Bedeutung:
Block 1 definiere neuen Zielknoten
Block 2 definiere neuen Quellenknoten
Block 3 t:=0
Block 4 bestimme den nächsten, sich auf dem Leitweg befindenden Knoten für jeden möglichen Weg zwischen Quellenknoten und Zielknoten unter Vermeidung von Minischleifen, speichere die derart gefundenen Folgeknoten zusammen mit einem assoziierten Wert von t ab, und behandle sie gemäss einer Prioritätsordnung
Block 5 t:=t+1
Block 6 ist der gegenwärtige Knoten der Zielknoten?
ja: gehe nach Block 7
nein: gehe nach Block 8
Block 7 speichere den Leitweg zusammen mit der assoziierten Länge t ab
Block 8 ist t≥x?
ja: gehe nach Block 9
nein: gehe zurück nach Block 4
Block 9 erzeuge Alarmsignal, eine Leitweglenkungsschleife wurde detektiert
Block 10 gibt es noch verbleibende Knoten (Block 4) die zu behandeln sind?
ja: gehe zurück nach Block 5
nein: gehe nach Block 11
Block 11 wurden alle möglichen Knoten als Quellenknoten definiert für den Fall des definierten Zielknotens?
ja: gehe nach Block 12
nein: gehe zurück nach Block 2
Block 12 wurden alle möglichen Knoten als Zielknoten definiert?
ja: gehe nach Block 13
nein: gehe zurück nach Block 1
Block 13 erstelle eine Liste der gefundenen Leitwege, jeder mit seiner assoziierten Länge t, sowie aller detektierten Leitweglenkungsschleifen, jede mit ihren assoziierten Quellen- und Zielknoten.
Das erfindungsgemässe Verfahren, wie im Flussdiagramm in Figur 1 gezeigt, arbeitet folgendermassen. Ein Zielknoten wird aus allen mit dem Fernmeldenetz assoziierten Knoten (Block 1) ausgewählt. Für den genannten Zielknoten wird daraufhin ein Quellenknoten aus den übrigbleibenden Knoten (Block 2) ausgewählt und ein Parameter t nimmt den Wert 0 an (Block 3) Auf der Basis der knotenspezifischen Wegleitinformation des Quellenknotens wird nun, für jeden möglichen Leitweg zwischen Quellen- und Zielknoten, der nächstfolgende, sich auf dem genannten Leitweg befindende Knoten unter Vermeidung von Minischleifen bestimmt (d.h. von zwei Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen haben, wird bloss eine der genannten Wegleitmöglichkeiten zur Erstellung des Leitweges verwendet) Alle derart gefundenen Knoten werden zusammen mit dem assoziierten Wert von t abgespeichert und gemäss ihrer Prioritätsordnung behandelt (Block 4) Der Parameter t wird um eine Einheit erhöht (Block 5), und es wird für den gefundenen Knoten höchster Priorität untersucht, ob er mit dem Zielknoten übereinstimmt (Block 6). Im Falle einer Übereinstimmung wurde ein Leitweg gefunden, der zusammen mit dem assoziierten Wert von t abgespeichert wird, welcher die Länge des genannten Leitweges wiedergibt und dabei als Anzahl der Verbindungsglieder aus gedrückt wird, die zusammen den Leitweg bilden (Block 7). Im Falle einer Nichtübereinstimmung wird untersucht, ob der Parameter t grösser oder gleich einem vorbestimmten Wert x ist (Block 8). Falls ja, so wurde eine Leitweglenkungsschleife detektiert, und ein Alarmsignal wird erzeugt (Block 9); falls nein, so wird für jeden möglichen Leitweg zwischen dem genannten Knoten und dem Zielknoten der nächstfolgende, sich auf dem genannten Leitweg befindende Knoten auf der Basis der knotenspezifischen Wegleitinformation des gefundenen Knotens höchster Priorität bestimmt, bis alle möglichen Leitwege zwischen dem Knoten höchster Priorität und dem Zielknoten erstellt und eventuelle Leitweglenkungsschleifen detektiert worden sind.
Es wird dann untersucht, ob es noch übrigbleibende Knoten tieferer Priorität (siehe Block 4) gibt, die zu behandeln sind (Block 10). Falls es solche gibt, so werden sie wiederum gemäss der Prioritätsordnung behandelt, d.h., für den Knoten höchster Priorität unter den verbleibenden Knoten wird der Parameter t um eine Einheit erhöht, und es wird untersucht, ob er mit dem Zielknoten übereinstimmt, etc., und wenn es dann keine verbleibenden Knoten mehr gibt, wird untersucht, ob alle Knoten ausser dem definierten Knoten bereits als Quellenknoten definiert wurden (Block 11). Falls nicht, so wird ein anderer Knoten, der noch nicht zur Diskussion stand, für den Fall des vorgegebenen Zielknotens als Quellenknoten definiert, etc. (Block 2); falls dem so ist, wird untersucht, ob alle Knoten bereits als Zielknoten definiert wurden (Block 12). Falls nicht, so wird ein anderer Knoten, der noch nicht zur Diskussion stand, als Zielknoten definiert, etc. (Block 1); falls dem so ist, wird eine Liste aller gefundenen Leitwege angezeigt, jeder mit seiner assoziierten Länge t, sowie aller detektierten Leitweglenkungsschleifen, jede mit ihren assoziierten Quellen- und Zielknoten (Block 13).
Es wird darauf hingewiesen, dass die Erhöhung des Parameters t bei jedem folgenden, sich auf dem Leitweg befindenden Knoten in einem weiten Sinn zu interpretieren ist. Es ist daher auch möglich, den Parameter t beim Durchlaufen jedes folgenden, sich zwischen zwei Knoten befindenden Bindegliedes zu erhöhen, und es darf weiter nicht ausgeschlossen werden, dass jeder neue Leitweg mit einem Festwert des Parameters t begonnen werden kann, der dann bei jedem nächstfolgenden Knoten oder Bindeglied vermindert wird, und dass zum Beispiel eine Leitweglenkungsschleife bei einem Wert 0 detektiert wird (ein Nachteil in diesem Zusammenhang ist es natürlich, dass in diesem Falle die Länge des erstellten Leitweges nicht direkt verfügbar ist).
Das oben, auf der Basis von Figur 1, beschriebene Ausführungsbeispiel bezieht sich auf ein Verfahren, das zum Beispiel für die simulierte Erstellung von Leitwegen zum Einsatz kommen könnte. In der tatsächlichen Erstellung von Leitwegen auf der Basis der mit den Knoten assoziierten, knotenspezifischen Wegleitinformation könnte ebenfalls eine Variante dieses Ausführungsbeispieles zur Anwendung kommen, in der für einen vorgegebenen Zielknoten zuerst untersucht wird, ob der Zielknoten von einem bestimmten Quellenknoten aus mit Leitwegen der Länge 1 erreicht werden kann, und dann, ob der Zielknoten vom Quellenknoten aus auf der Basis der oben bestimmten Daten mit Leitwegen grösserer Länge erreicht werden kann, wobei diese letztere Operation ständig mit stetig zunehmender Länge wiederholt wird, bis es schliesslich nicht mehr möglich ist, Leitwege noch grösserer Länge zu erstellen, oder bis die Länge des zuletzt erstellten Leitweges den vorbestimmten Wert x überschreitet; man hätte es dann mit der Detektion einer Leitweglenkungsschleife zu tun. In diesem Falle ist der Wert x grösser als die grösstmögliche Weglänge im Fernmeldenetz und ist z.B. gleich der Anzahl der darin vorhandenen Knoten.
Das in Figuren 2 und 3 dargestellte Fernmeldenetz 20 enthält Detektionsmittel 21 und Knoten 30 bis 41 inklusive. In Figur 2 sind die Wegleitmöglichkeiten vom Quellenknoten 39 zum Zielknoten 32 aufgezeigt. Die Knoten 39 und 36 haben eine direkte, unidirektionelle Wegleitmöglichkeit vom erstgenannten Knoten 39 zum letztgenannten Knoten 36. Dasselbe gilt für die Knoten 36 und 37, 37 und 35, und 35 und 32. In Figur 3 sind die Wegleitmöglichkeiten vom Quellenknoten 32 zum Zielknoten 39 gezeigt. Die Knoten 32 und 35 haben eine direkte unidirektionelle Wegleitmöglichkeit vom erstgenannten Knoten 32 zum letztgenannten Knoten 35. Dasselbe gilt für die Knoten 35 und 31, 31 und 30, 30 und 34, 33 und 36, 34 und 37, 37 und 36, und 36 und 39. Die Knoten 30 und 33 haben beide eine gegenseitige, direkte bidirektionelle Wegleitmöglichkeit zum anderen und bilden eine sogenannte Minischleife. Dasselbe gilt für die Knoten 33 und 34.
Die Erstellung eines Leitweges vom Quellenknoten 39 zum Zielknoten 32, wie in Figur 2 gezeigt, erfolgt folgendermassen. In der knotenspezifischen Wegleitinformation vom Quellenknoten 39 wird Knoten 36 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 32 gefunden. Der Parameter t nimmt den Wert 1 an. Knoten 36 stimmt nicht mit dem Zielknoten 32 überein, und der Wert vom Parameter t ist kleiner als der vorbestimmte Wert, der für dieses Fernmeldenetz 20 auf den Wert 12 (die Anzahl Knoten) oder auf den Wert 9 (der längstmögliche Weg plus 1) gesetzt werden könnte. In der knotenspezifischen Wegleitinformation von Knoten 36 wird Knoten 37 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 32 gefunden. Der Parameter t nimmt den Wert 2 an. Knoten 37 stimmt nicht mit dem Zielknoten 32 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 37 wird Knoten 35 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 32 gefunden. Der Parameter t nimmt den Wert 3 an. Knoten 35 stimmt nicht mit dem Zielknoten 32 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 35 wird Knoten 32 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 32 gefunden. Der Parameter t nimmt den Wert 4 an. Knoten 32 ist der Zielknoten 32, und der Weg von Quellenknoten 39 zu Zielknoten 32, via Knoten 36, 37 und 35, und mit einer Länge 4, wurde folglich gefunden. Es gibt keine Leitweglenkungsschleife auf diesem Weg.
Das Erstellen eines Leitweges vom Quellenknoten 32 zum Zielknoten 39, wie in Figur 3 gezeigt, in dem eine Leitweglenkungsschleife detektiert wird, erfolgt folgendermassen. In der knotenspezifischen Wegleitinformation vom Quellenknoten 32 wird Knoten 35 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 1 an. Knoten 35 stimmt nicht mit dem Zielknoten 39 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 35 wird Knoten 31 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 2 an. Knoten 31 stimmt nicht mit dem Zielknoten 39 überein, und der Wert vom Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 31 wird Knoten 30 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 3 an. Knoten 30 stimmt nicht mit dem Zielknoten 39 überein, und der Wert vom Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 30 werden zwei auf verschiedenen Leitwegen liegende Knoten, nämlich Knoten 33 und 44, als Folgeknoten zum vorgegebenen Zielknoten 39 gefunden, da es vier verschiedene mögliche Wege von Knoten 30 zum Zielknoten 39 gibt: einen ersten Weg via Knoten 33 und 36; einen zweiten Weg via Knoten 33, 34, 37 und 36, beide Wege ergeben daher Knoten 33 als Folgeknoten; einen dritten Weg via Knoten 34, 37 und 36; und einen vierten Weg via 34, 33 und 36, beide Wege ergeben daher Knoten 34 als Folgeknoten Für beide Knoten nimmt der Parameter t den Wert 4 an.
Unter der Annahme dass von den Knoten 33 und 34 der Knoten 33 die höchste Priorität hat, werden die Leitwege via diesen Knoten zuerst erstellt In der knotenspezifischen Wegleitinformation von Knoten 33 werden zwei auf verschiedenen Leitwegen liegende Knoten, nämlich Knoten 36 auf dem ersten Weg und Knoten 34 auf dem zweiten Weg, als Folgeknoten zum vorgegebenen Zielknoten 39 gefunden, und abhängig von der Priorität der genannten Knoten 36 und 34, die nicht mit dem Zielknoten übereinstimmen, werden beide Leitwege weiter in einer bestimmten Reihenfolge erstellt. Für beide Knoten 36 und 34 nimmt der Parameter t den Wert 5 an. In der knotenspezifischen Wegleitinformation von Knoten 36 wird Knoten 39 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 6 an. Knoten 39 ist der Zielknoten 39, und der Leitweg vom Quellenknoten 32 zum Zielknoten 39 via die Knoten 35, 31, 30, 33 und 36 wurde dabei und zwar mit einer Länge von 6 aufgefunden. Es gibt keine Leitweglenkungsschleife auf diesem ersten Weg. In der knotenspezifischen Wegleitinformation von Knoten 34 wird Knoten 37 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 6 an. Knoten 37 stimmt nicht mit Zielknoten 39 überein, und der Wert vom Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 37 wird Knoten 36 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden Der Parameter t nimmt den Wert 7 an Knoten 36 stimmt nicht mit Zielknoten 39 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9 In der knotenspezifischen Wegleitinformation von Knoten 36 wird Knoten 39 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 8 an. Knoten 39 ist der Zielknoten 39, und der Leitweg vom Quellenknoten 32 zum Zielknoten 39 via die Knoten 35, 31, 30, 33, 34, 37, 36 und 39 wurde daher und zwar mit einer Länge von 8 aufgefunden. Es gibt keine Leitweglenkungsschleife auf diesem zweiten Weg.
Nach der Erstellung der Leitwege via Knoten 33 werden die Leitwege via Knoten 34 erstellt. In der knotenspezifischen Wegleitinformation von Knoten 34 werden zwei auf verschiedenen Leitwegen liegende Knoten, nämlich Knoten 37 auf dem dritten Weg und Knoten 33 auf dem vierten Weg, als Folgeknoten zum vorgegebenen Zielknoten 39 gefunden, und abhängig von der Priorität der genannten Knoten 37 und 33, die nicht mit dem Zielknoten 39 übereinstimmen, werden beide Leitwege weiter in einer bestimmten Reihenfolge erstellt. Für beide Knoten 37 und 33 nimmt der Parameter t den Wert 5 an. In der knotenspezifischen Wegleitinformation von Knoten 37 wird Knoten 36 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 6 an. Knoten 36 stimmt nicht mit Zielknoten 39 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 36 wird Knoten 39 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 7 an. Knoten 39 ist der Zielknoten 39, und der Leitweg vom Quellenknoten 32 zum Zielknoten 39 via die Knoten 35, 31, 30, 34, 37, und 36 wurde daher und zwar mit einer Länge von 7 aufgefunden. Es gibt keine Leitweglenkungsschleife auf diesem dritten Weg. In der knotenspezifischen Wegleitinformation von Knoten 33 werden zwei auf verschiedenen Leitwegen liegende Knoten, nämlich Knoten 36 und 30, als Folgeknoten zum vorgegebenen Zielknoten 39 gefunden, und abhängig von der Priorität der genannten Knoten 36 und 30, die nicht mit dem Zielknoten 39 übereinstimmen, werden beide Leitwege weiter in einer bestimmten Reihenfolge erstellt Für beide Knoten 36 und 30 nimmt der Parameter t den Wert 6 an. Der vierte Weg scheint daher verschiedene Wege zu enthalten, die aufgespalten wurden. In der knotenspezifischen Wegleitinformation von Knoten 36 wird Knoten 39 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 7 an. Knoten 39 ist der Zielknoten 39, und der Leitweg vom Quellenknoten 32 zum Zielknoten 39 via die Knoten 35, 31, 30, 34, 33, und 36 wurde daher und zwar mit einer Länge von 7 aufgefunden Es gibt keine Leitweglenkungsschleife auf dieser Aufspaltung des vierten Weges. In der knotenspezifischen Wegleitinformation von Knoten 30 wird Knoten 34 als Folgeknoten auf dem Weg zum vorgegebenen Zielknoten 39 gefunden. Der Parameter t nimmt den Wert 7 an. Knoten 34 stimmt nicht mit Zielknoten 39 überein, und der Wert von Parameter t ist kleiner als der vorbestimmte Wert 9. In der knotenspezifischen Wegleitinformation von Knoten 34 werden, wie zuvor, zwei auf verschiedenen Leitwegen liegende Knoten, nämlich Knoten 37 und 33, als Folgeknoten zum vorgegebenen Zielknoten 39 gefunden, und abhängig von der Priorität der genannten Knoten 37 und 33, die nicht mit dem Zielknoten 39 übereinstimmen, werden beide Leitwege weiter in einer bestimmten Reihenfolge erstellt. Für beide Knoten 37 und 33 nimmt der Parameter t den Wert 8 an. Es ist irrelevant, von welchem der Knoten 37 und 33 aus nun der Weg weiter erstellt wird (und wie ein Weg, wenn überhaupt, von Knoten 33 aus erstellt wird): bevor der Zielknoten 39 erreicht wird, nimmt der Parameter t den Wert 9 an, was auf das Vorhandensein einer Leitweglenkungsschleife im teilweise erstellten Leitweg hinweist. Diese Schleife umfasst die Knoten 30, 34, 33, 30, 34 etc. und könnte in einfacher Weise beseitigt werden, entweder durch Beseitigung der unidirektionellen Wegleitmöglichkeit von Knoten 30 nach 34, und als Folge davon, der unidirektionellen Wegleitmöglichkeit von Krioten 33 nach 34 und von Knoten 34 nach Knoten 33, wobei die Wegleitmöglichkeiten in der Gegenrichtung zwischen den vier letztgenannten Knoten bestehen bleiben sollten; oder durch die alleinige Beseitigung der unidirektionellen Wegleitmöglichkeit von Knoten 33 nach 30, wobei die Wegleitmöglichkeit in der Gegenrichtung zwischen den letztgenannten Knoten bestehen bleiben soll.
Die in der Figur 4 dargestellten Detektionsmittel 21 umfassen Leitwegerstellungsmittel 22 zur Erstellung eines Leitweges von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation. Die Leitwegerstellungsmittel 22 sind an Speichermittel 23 gekoppelt, in denen die knotenspezifische Wegleitinformation gespeichert ist, und sie sind an Zählmittel 24 gekoppelt, um eine Zählerstellung um eine Zähleinheit an jedem nachfolgenden, sich auf einem Leitweg befindenden Knoten wahrend des Erstellens des genannten Leitweges zu erhöhen. Zu diesem Zweck erhalten die Zählmittel 24 von den Leitwegerstellungsmitteln 22 einen Zählimpuls an einen ersten Eingang, und eine zu ladende und mit einem bestimmten Knoten zu assozuerende Zählerstellung an einem zweiten Eingang. Ein Ausgang der Zählmittel 24 ist an einen ersten Eingang von Vergleichsmitteln 25 gekoppelt, um die mit einem teilweise erstellten Leitweg assoziierte Zählerstellung mit einem vorbestimmten Zählerwert zu vergleichen und um dann ein Alarmsignal zu erzeugen, falls dieser zuletzt genannte Zählerwert überschritten wird, wobei der vorbestimmte Zählerwert x in Speichermitteln 26 gespeichert ist, die an einen zweiten Eingang der Vergleichsmittel 25 gekoppelt sind. Ein Ausgang der Vergleichsmittel 25 ist zum Anliefern des Alarmsignales an die Leitwegerstellungsmittel 22 gekoppelt Die Leitwegerstellungsmittel 22 sind ferner an Auswahlmittel 27 zum aufeinanderfolgenden Auswählen aller Knoten als Zielknoten und zum aufeinanderfolgenden Auswählen aller übrigbleibenden Knoten als Quellenknoten für jeden ausgewählten Zielknoten sowie an Vernachlässigungsmittel 28 zum Vernachlässigen von mindestens einer von zwei Wegleitmöglichkeiten in der Erstellung eines Leitweges im Falle von zwei sich auf dem zu erstellenden Leitweg befindenden Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, gekoppelt.
In diesem Zusammenhang geben die Speichermittel 23 symbolisch die Speicher aller Knoten wieder, falls eine Leitweglenkungsschleife über ein tatsächliches Erstellen des Leitweges detektiert werden soll. Falls eine Leitweglenkungsschleife über das Erstellen von Leitwegen in simulierter Weise detektiert werden soll, könnten die Speichermittel 23 ebenfalls durch einen zentralen Speicher gebildet werden, in welchem die knotenspezifische Wegleitinformation aller Knoten gespeichert ist.

Claims

1. Verfahren zum Detektieren von Leitweglenkungsschleifen in einem Fernmeldenetz, das mit Knoten ausgerüstet ist, von denen ein jeder knotenspezifische Wegleitinformation enthält, in dem ein Leitweg von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation erstellt wird, dadurch gekennzeichnet, dass während des Erstellens eines Leitweges ein Parameter des genannten Leitweges an jedem folgenden, sich auf dem Leitweg befindenden Knoten um eine Einheit erhöht wird, und dass der in einer Anzahl Einheiten ausgedrückte Parameter eines teilweise erstellten Leitweges dabei mit einem vorbestimmten Wert verglichen wird, und dass ein teilweise erstellter Leitweg, dessen Parameter den genannten Wert überschreitet, als ein eine Leitweglenkungsschleife enthaltender Leitweg detektiert wird.

2. Verfahren gemäss Anspruch 1, dadurch gekennzeichnet, dass bei zwei sich auf dem zu erstellenden Leitweg befindenden Knoten, von denen beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, nicht mehr als eine der beiden Wegleitmöglichkeiten zum Erstellen des Leitweges verwendet wird.

3. Verfahren gemäss Anspruch 2, dadurch gekennzeichnet, dass alle Knoten aufeinanderfolgend als Zielknoten, und alle übrigbleibenden Knoten aufeinanderfolgend als Quellenknoten für jeden der Zielknoten fungieren.

4. Fernmeldenetz zum Gebrauch des Verfahrens gemäss Anspruch 1,

- mit Knoten die jeweils knotenspezifische Wegleitinformation enthalten, und

- mit Detektionsmitteln, die Leitwegerstellungsmittel zur Erstellung eines Leitweges von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation umfassen,

dadurch gekennzeichnet, dass die Detektionsmittel weiter ausgestaltet sind

- mit Zählmitteln zum Erhöhen einer Zählerstellung um eine Zähleinheit an jedem folgenden, sich auf dem Leitweg befindenden Knoten während des Erstellens des genannten Leitweges, und

- mit Vergleichsmitteln zum Vergleichen der mit einem teilweise erstellten Leitweg assoziierten Zählerstellung mit einem vorbestimmten Zählerwert, und zum Erzeugen eines Alarmsignales falls dieser letztere überschritten wird.

5. Fernmeldenetz gemäss Anspruch 4, dadurch gekennzeichnet, dass die Detektionsmittel mit Vernachlässigungsmitteln ausgestattet sind zum Vernachlässigen von mindestens einer von zwei Wegleitmöglichkeiten in der Erstellung eines Leitweges, im Falle von zwei sich auf dem zu erstellenden Leitweg befindenden Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben.

6. Fernmeldenetz gemäss Anspruch 5, dadurch gekennzeichnet, dass die Detektionsmittel mit Auswahlmitteln ausgestattet sind, um aufeinanderfolgend alle Knoten als Zielknoten und um aufeinanderfolgend alle übrigbleibenden Knoten als Quellenknoten für jeden ausgewählten Zielknoten auszuwählen.

7. Detektionsmittel zur Verwendung im Fernmeldenetz gemäss Anspruch 4, das Leitwegerstellungsmittel zum Erstellen eines Leitweges von einem Quellenknoten einerseits zu einem Zielknoten andererseits auf der Basis der mit dem Quellenknoten assoziierten, knotenspezifischen Wegleitinformation und der mit den sich auf dem Leitweg befindenden Knoten assoziierten, knotenspezifischen Wegleitinformation umfasst,

dadurch gekennzeichnet, dass die Detektionsmittel weiter ausgestaltet sind

- mit Vergleichsmitteln zum Vergleichen der mit einem teilweise erstellten Leitweg assoziierten Zählerstellung mit einem vorbestimmten Zählerwert, und zum Erzeugen eines Alarmsignales, falls dieser letztere überschritten wird.

8. Detektionsmittel nach Anspruch 7, dadurch gekennzeichnet, dass die Detektionsmittel mit Vernachlässigungsmitteln ausgestaltet sind, um mindestens eine von zwei Wegleitmöglichkeiten in der Erstellung eines Leitweges im Falle von zwei sich auf dem zu erstellenden Leitweg befindenden Knoten, die beide eine direkte Wegleitmöglichkeit zum anderen in ihrer Wegleitinformation haben, zu vernachlässigen.

9. Detektionsmittel nach Anspruch 8, dadurch gekennzeichnet, dass die Detektionsmittel mit Auswahlmitteln ausgestaltet sind, um aufeinanderfolgend alle Knoten als Zielknoten und um aufeinanderfolgend alle übrigbleibenden Knoten als Quellenknoten für jeden ausgewählten Zielknoten auszuwählen.