DE19611008A1 - Konfiguration einer digitalen Koppeleinrichtung - Google Patents

Description

Die Erfindung betrifft ein Verfahren nach dem Oberbegriff des Anspruchs 1 zur Konfiguration einer Koppeleinrichtung für digitale Übertragungsleitungen in Situationen, die eine Ände­ rung des Vermittlungszustands erfordern.

Die synchrone digitale Hierarchie (SDH) umfaßt eine große Einheit zur Übertragung von Zeitmultiplexsignalen in einem Telekommunikationsnetz, dessen Fernnetz sich in ein fernge­ steuertes Koppelnetz ausdehnt. Die erste Ebene der SDH-Signale ist das synchrone Transportmodul (STM-1), dessen Übertragungs­ rate 155 520 Mbit/s beträgt. Der STM-1-Basisrahmen besteht aus Bytes (8 Bit), von denen es einschließlich Steuerblöcken 2430 gibt. Somit überträgt der STM-1-Rahmen 63 TU 12 (Untereinheit, englisch "tributary unit")-Signale von 2 Mbit/s, die ein 2- Mbit/s-Signal eines gewöhnlichen PCM-Systems mit 30 Kanälen enthalten können. Jedes Byte in dem Rahmen bildet einen 64- kbit/s-Kanal. Die SDH-Signale oder Transportmodule werden aus den Subsystem-Signalen durch Byte-Verschachtelung gebildet.

Eine digitale Koppeleinrichtung (DXC) in der SDH kann den Verkehr zwischen den verschiedenen SDH-Ebenen und zwischen verschiedenen Signalen vermitteln. Sie muß zusätzlich in der Lage sein, eine flexible Neukonfigurierung des Netzes vorzu­ nehmen, d. h. die Verbindungen umzuleiten, und bei Störungs- oder Fehlersituationen des Netzes ein schnelles Umschalten auf Reserve- oder Ausweichverbindungen gewährleisten.

Es wurden intensive Studien über die digitale Vermittlung gemacht, um eine optimale Architektur zu finden. Eine blockie­ rungsfreie Struktur, die die Kriterien betreffend Kapazität und Brauchbarkeit erfüllt, ist die TST-Struktur oder Zeit- Raum-Zeit-Vermittlung (englisch "time-space-time switching"), wie sie in unserem Patent PCT/FI/00174 (korrespondierend zu FI-921834) offenbart ist. Dieses Patent offenbart die allge­ meinen Prinzipien eines TST-Vielfach in beträchtlicher Aus­ führlichkeit. Obwohl das in dem Patent PCT/FI/00174 offenbarte Verfahren recht gut funktioniert, benötigt man insbesondere für größere Koppeleinrichtungen oder Vielfache ein effiziente­ res Verfahren zur Steuerung der Koppeleinrichtung.

Aufgabe der Erfindung ist es, ein Verfahren zum Vermitteln von digitalen Signalen zwischen zwei gegebenen Punkten anzugeben und dabei eine blockierungsfreie Verbindung zu realisieren und die bekannten Unzulänglichkeiten und Nachteile zu vermeiden.

Diese Aufgabe wird mit einem in Zeitperioden implementierten Verfahren zur Konfigurationsberechnung nach Anspruch 1 gelöst. Die Unteransprüche beschreiben vorteilhafte Ausbildungen der Erfindung.

Die durchzuschaltenden Signale sind vorteilhafterweise Multi­ plex-Subsignale von hochkanaligen Signalen, was bei dem SDH- System bedeutet, daß die Subsignale vorrangig virtuelle VC-12- Container von 2 Mbit/s sind, wobei die Hauptsignale dann STM- 1-Signale von 155 Mbit/s sind. Der erfindungsgemäße Game-Algo­ rithmus besitzt bessere Eigenschaften als andere bekannte Punkt-zu-Punkt-Durchschaltalgorithmen. Seine Vorteile sind, daß er weniger Datenspeicher benötigt und schneller auszufüh­ ren ist. Ein mäßiger Verbrauch der Speicherkapazität und eine schnelle Ausführung sind sehr wichtig, wenn die Koppeleinrich­ tung groß wird, insbesondere wenn sie die momentane Größe 16 × 16 übersteigt. Der Algorithmus beinhaltet darüber hinaus eine einfache und geradewegs zum Ziel führende Um- oder Neuord­ nungs-Routine, die den Hauptteil des Algorithmus bildet. Die Neuordnungs-Routine kann so leicht implementiert werden und ist für eine schnelle Ausführung optimiert.

Die Stärke des Algorithmus liegt in der Tatsache, daß er le­ diglich Verbindungen umordnet, welche eine Umordnung benöti­ gen. Dies wird zum Teil dadurch verwirklicht, daß das Vermitt­ lungs- oder Durchschaltproblem auf eine neuartige Weise aufge­ stellt wird. Das Vermittlungsproblem wird als imaginäre Matrix dargestellt. Der Algorithmus verzeichnet oder protokolliert alle an den Verbindungen vorgenommenen Umordnungen, um die Vermittlung zu realisieren. Wenn alle Umordnungen vorgenommen worden sind, stellen die Verzeichnisse alle notwendigen Infor­ mationen bereit, die zur Realisierung der Vermittlung entspre­ chend den Steuerinformationen für die Koppeleinrichtung benö­ tigt werden.

Bei dem erfindungsgemäßen Verfahren werden schwierige Vermitt­ lungssituationen in einer Rekursionsstufe gelöst, bei der die stelle einer Verbindung in der imaginären Matrix zufällig an eine neue Stelle verdrängt wird, woraufhin der Ablauf nach dem Basisverfahren fortgesetzt wird.

Der erfindungsgemäße Algorithmus kann außerdem dazu verwendet werden, Punkt-zu-Punkt-Signale durch ein dreistufiges Benes- Koppelnetz zu leiten.

Die Erfindung wird nun unter Bezugnahme auf die beigefügten Zeichnungen beispielhaft beschrieben.

Fig. 1 ist ein vereinfachtes Beispiel einer Vermittlungs­ situation mit nur 5 Zeitschlitzen anstatt der übli­ chen 64.

Fig. 2 zeigt eine imaginäre Matrix und Verbindungen zwi­ schen den Eingangstoren und den Ausgangstoren. Bei diesem vereinfachten Beispiel stellt die horizontale Achse die Eingangstore mit den Eingangszeitschlitzen und die vertikale Achse die Ausgangstore mit den Ausgangszeitschlitzen dar.

Fig. 3 ist ein vereinfachtes Flußdiagramm des erfindungs­ gemäßen Game-Algorithmus.

Fig. 4 stellt die Rekursionsstufe gemäß der Erfindung dar.

Fig. 5 zeigt eine Situation, nachdem eine erste Reihenver­ tauschung entsprechend dem erfindungsgemäßen Verfah­ ren durchgeführt worden ist.

Fig. 6 zeigt eine Situation in der Vermittlungsmatrix, nachdem eine erste Untermatrix unter Verwendung des erfindungsgemäßen Game-Algorithmus neu geordnet wor­ den ist.

Die effektive Implementierung der erfindungsgemäßen Konfigura­ tionsberechnung in einer Koppeleinrichtung basiert auf der Tatsache, daß in einem TST-Vielfach (d. h. einer TST-Koppel­ einrichtung) das Problem einer neuen Konfiguration mit einem Zeitschlitz pro Zeit gelöst werden kann. Mit anderen Worten, wenn eine blockierungsfreie Stelle für einen beliebigen Zeit­ schlitz n in k Zeitstufen oder Zeitvielfachen (engl.: "time switch") und k × k Raumstufen oder Raumvielfachen (engl.: "space switch") der Eingangsseite gefunden wird, kann man sicher sein, daß die anderen Zeitschlitze n+1, n+2, . . . , m mit Hilfe des gleichen Prinzips problemmäßig gelöst werden können. Daher kann eine Konfiguration für die Koppeleinrichtung mit einem Zeitschlitz pro Zeit berechnet werden, so daß eine blockierungsfreie Vermittlungskonfiguration stets in der ein­ gangsseitigen Zeitstufe der verbleibenden Zeitschlitze n, n+1, n+2, . . . , m und in der Raumstufe gesucht wird.

Die Raumverbindung eines bestimmten Zeitschlitzes ist blockie­ rungsfrei, wenn alle Ausgänge der Raumstufe in Gebrauch sind. Mit anderen Worten muß die eingangsseitige Zeitstufe alle Zeitschlitze oder Kanäle in solcher Weise verbinden, daß alle zeitgekoppelten Zeitschlitze der Eingänge der Raumstufe auf unterschiedliche Ausgänge gerichtet sind. Wenn ein Eingang keinen Zeitschlitz aufweist, der zu einem bestimmten Ausgang geleitet werden soll, braucht dieser Ausgang selbstverständ­ lich nicht benutzt zu werden. Daher ist die Funktion der ein­ gangsseitigen Zeitstufe vor der Raumstufe, die Kanäle in den Zeitschlitzen gleichmäßig aufzuteilen, so daß die Raumstufe sie mit geeigneten, gewünschten Ausgängen verbinden kann. Genauer gesagt sollte in der Raumstufe keine Stockung oder Stauung auftreten, bei der ein Zeitschlitz mehr als einen zu einem bestimmten Ausgangszeitschlitz geleiteten Kanal enthält. Unter Verwendung des erfindungsgemäßen Verfahrens wird die Koppelmatrix so aufgebaut, daß die Vermittlung blockierungs­ frei erfolgt.

Bei dem Vermittlungsverfahren wird die Konfiguration einer Koppeleinrichtung mit einem Zeitschlitz pro Zeit berechnet. Zunächst werden die Eingangskanäle oder die Bytes in dem Rah­ men in so viele Gruppen aufgeteilt, wie es vermittelte Signale oder Zeitperioden im Transportmodul der Verbindung gibt. Bei­ spielsweise gibt es bei einer mit der eingangsseitigen Zeit­ stufe verbundenen SDH STM-1-Leitung 63 Zeitperioden eines 2- Mbit/s-Signals mit der Übertragungsrate von 155 Mbit/s, die Subsystem-Container genannt werden (z. B. Untereinheit TU 1, die das 2-Mbit/s-Signal eines gewöhnlichen PCM-Systems mit 30 Kanälen enthält). Der entsprechend der Erfindung gewählte Ort jedes Zeitschlitzes in dem Rahmen wird direkt oder durch Be­ rechnung mittels eines Zeigers standardgemäß erhalten. Ent­ sprechend gibt es bei einer Leitung nach der plesiochronen digitalen Hierarchie (PDH) 64 Zeitperioden des 2-Mbit/s- Signals, wenn die Rate 140 Mbit/s beträgt. Das Problem der Vermittlungsrouten wird für jede auf diese Weise definierte Gruppe gelöst, so daß eine realisierte Vermittlungskonfigura­ tion auch bedeutet, daß die bis jetzt zu berechnenden Zeit­ schlitze auch verbunden werden können. Somit wird unter Ver­ wendung eines zeitperiodischen Verfahrens gemäß Fig. 3 eine Lösung für das gesamte Koppelnetz erhalten.

Die Erfindung kann auf Koppeleinrichtungen mit unidirektiona­ ler oder bidirektionaler Verkehrsvermittlung angewendet wer­ den. Bei einer bidirektionalen Koppeleinrichtung kann die Vermittlungskonfiguration für eine Richtung analog erzeugt werden, z. B. als Spiegelbild.

Das Vermittlungsproblem wird als imaginäre Matrix (gezeigt in Fig. 2) dargestellt. Es sei daran erinnert, daß Fig. 2 verein­ facht ist, um eine (4 × 5)²-Matrix darzustellen, wogegen die Größe einer einem realen Koppelnetz entsprechenden Matrix (16 × 63)² entsprechen würde. Das geringe Speichererfordernis des Algorithmus basiert darauf, daß die einzig notwendigen Daten­ felder diejenigen Daten sind, die den Punkten auf den Matrix­ achsen entsprechen.

Der Algorithmus protokolliert alle Umordnungen, die an den Verbindungen vorgenommen werden, um die Vermittlung zu reali­ sieren. Wenn alle Umordnungen vorgenommen worden sind, stellen die Aufzeichnungen alle notwendigen Informationen bereit, die zur Realisierung der Vermittlung entsprechend den Steuerinfor­ mationen für die Koppeleinrichtung benötigt werden.

Wie oben erwähnt, sind die zu verbindenden Signale hauptsäch­ lich virtuelle VC-12-Container von 2 Mbit/s. Die Verbindung des Hauptsignals (STM-1) als Ganzes zwischen den Eingangs- und Ausgangstoren muß nicht betrachtet werden, da derartige Ver­ bindungen unmittelbar ohne Berechnung hergestellt werden kön­ nen. Somit ist das Problem die Verbindung der VC-12-Signale von ankommenden Hautsignalen zu anderen weggehenden Hauptsi­ gnalen.

Das allgemeine Problemfeld und Startpunkt für den Algorithmus ist eine Tabelle, welche alle in der Koppeleinrichtung herzu­ stellenden Verbindungen enthält. Die Größe der Tabelle beträgt 16 × 63, was die Zahl der Tore bzw. Zeitschlitze darstellt. Die Positionen der Tabellenelemente in Reihen und Spalten und die Elementwerte stellen die Verbindungen dar. Der Veranschau­ lichung halber zeigt Fig. 1 eine vereinfachte Tabelle der Größenordnung 4 × 5, d. h. 4 Eingangstore und 5 Zeitschlitze. Die Werte der Tabellenelemente stellen die gewünschten Aus­ gangstore und Ausgangszeitschlitze für Signale an den Ein­ gangstoren dar. Beispielsweise ist von Eingangstor 1, Zeit­ schlitz 2 über die Koppeleinrichtung eine Verbindung zu Aus­ gangstor 4, Zeitschlitz 3 herzustellen. Somit umfassen in den Tabellenelementen die Eingangstore eine Reihe und die Zeit­ schlitze eine Spalte, wobei das Ausgangstor und der Ausgangs­ zeitschlitz in dem Element oder dem Kreuzungspunkt in der Tabelle in folgender Form angegeben sind: (Tor, Zeitschlitz). Bei dem Beispiel der Fig. 1 ist der Vermittlungszustand von der Eingangsseite her gesehen. In analoger Weise enthält die Tabelle eine Verbindung von Eingangstor 2, Zeitschlitz 3 zu Ausgangstor 1, Zeitschlitz 2, die auch als 2,3 → 1,2 ausge­ drückt werden kann.

Eine erfolgreiche Konfiguration bei der TST-Architektur erfor­ dert, daß die Verbindungen stets so angeordnet werden, daß in jedem Zeitschlitz die Eingangssignale auf verschiedene einzel­ ne Ausgänge der Raumstufe gerichtet sind, d. h. zwei oder mehr Signale können in einem bestimmten Zeitschlitz nicht auf ein Ausgangstor gerichtet sein. Dieses Erfordernis ist an sich einfach. Allerdings unterscheidet sich die Leistung von Algo­ rithmen, die bei größeren Koppeleinrichtungen verwendet wer­ den, stark hinsichtlich der Weise, wie sie das Konfigurations­ problem lösen und wieviel Zeit die Berechnung erfordert.

Als nächstes wird der mathematische Hintergrund des erfin­ dungsgemäßen Algorithmus betrachtet.

Auf die Kriterien der TST-Architektur kann die kombinatorische Mathematik angewendet werden. Die Theorie beinhaltet die Defi­ nition eines Systems eindeutiger Darstellung (SDR, englisch: "system of distinct representation"). Das SDR-System be­ schreibt N Mengen (s1, s2, . . . sN) mit einer solchen Verteilung der Elemente, daß es möglich ist, eine Lösung für die Elemente zu finden, bei der jedes der Elemente verschieden ist. Die Mengen sX können den folgenden Inhalt haben:

s1: (1,3,5)
s2: (2,4)
s3: (1,2)
s4: (3,4)
s5: (5).

Eine mit Hilfe der sXs gemachte SDR-Darstellung kann die fol­ genden Elemente enthalten: 1, 4, 2, 3, 5 (mit anderen Worten, Element 1 aus der Menge s1, Element 4 aus der Menge s2, usw.). Das Kriterium zur Bereitstellung eines SDR-Systems wird durch den Satz von Hall angegeben: "Eine eindeutige Darstellung ist in den Mengen sX vorhanden, wenn für alle k in jeder Vereini­ gung von k Mengen s k verschiedene Repräsentanten gefunden werden."

Anhand der obigen Mengendefinitionen kann man erkennen, daß der Satz für diese Mengen sX (x = 1 bis 5) gültig ist. Wenn die Vereinigung der Mengen s1 und s2 näher bestimmt wird, erhält man 5 Repräsentanten (die Elemente 1, 2, 3, 4, 5), was mehr als die Zahl der die Vereinigung bildenden Mengen ist. Wenn die Menge s4 nur das Element 5 enthalten würde, würde dies das SDR-System unmöglich machen, was ebenfalls durch den Satz von Hall erkannt wird. Die Vereinigung der Mengen s4 und s5 würde dann nämlich nur einen Repräsentanten enthalten, was weniger als die Zahl der Mengen in der Vereinigung ist.

Diese mathematische Situation ist auf die TST-Architektur an­ wendbar, da die Mengen sX Eingangsleitungen darstellen können. Die Mengenelemente können dann Signale darstellen, welche auf gewünschte Ausgangsleitungen gerichtet werden müssen. Man be­ achte, daß zu diesem Zeitpunkt die Reihenfolge der Zeitschlit­ ze mathematisch unbeachtlich ist, da der wesentliche Gedanke bei der TST-Struktur ist, die Verbindungen so anzuordnen, daß sie verschiedene Tore im Raumvielfach benutzen. Die Zeitstufen oder -vielfache werden für die geeignete Reihenfolge außerhalb des Umfangs dieser Definition sorgen.

Es kann gezeigt werden, daß der Satz von Hall für die TST- Architektur gültig ist, da die Eingangs- und Ausgangsseiten von der gleichen Größe sind. Das Problem ist nicht die Blockie­ rungsfreiheit der bedingt blockierungsfreien TST-Architek­ tur, sondern wie ein Algorithmus zu beschreiben ist, der die korrekte Durchschaltkonfiguration findet, d. h. wie man am besten eine Lösung findet, bei der die Signale für alle 63 Zeitschlitze verschiedene Tore über das Raumvielfach benutzen.

Indem man die Gültigkeit des Satzes von Hall testet, findet man einen möglichen Algorithmus. Ein solcher Algorithmus nimmt sich einfach ein Element aus einer Menge sX heraus, solange dieses Element nicht bereits in der Lösung enthalten ist. Der Algorithmus probiert Elemente in der Menge aus, bis er eine neue Lösung findet. Dies wird für alle Mengen fortgesetzt, bis alle Mengen durch eindeutige Elemente dargestellt sind.

Wenn unter all den Elementen einer bestimmten Menge keine Lösung gefunden wird, muß eine rekursive Funktion durchgerührt werden. Die Rekursion startet durch Auswählen eines Elements aus der ungelösten Menge. Das sich überschneidende Element in einer anderen Menge muß aus der Lösung entfernt werden und eine neue Lösung für diese sich überschneidende Menge getunden werden. Wenn die sich überschneidende Menge ein Element um­ faßt, welches die Zahl der Lösungen erhöht, ist dies die neue Lösung. Wenn andererseits keine neue Lösung gefunden wird, fährt die Rekursion fort, nun jedoch mit der neuen ungelösten Menge als Startpunkt. Die rekursive Funktion ist ähnlich der obigen, mit der Ausnahme, daß die Wahl des nächsten Elements nicht auf ein vorhergehendes, sich überschneidendes Element gerichtet werden kann. Die rekursive Berechnung wird fortge­ führt, bis die Zahl der Lösungen mit einer neuen Lösung erhöht wird.

Als nächstes wird ein Beispiel herangezogen, um den Prüfalgo­ rithmus zu veranschaulichen. Es können die oben beschriebenen Mengen verwendet werden, d. h.:

s1: (1,3,5); s2: (2,4); s3: (1,2); s4: (3,4); s5: (5).

Das Element 1 aus der Menge s1 wird für die Lösung ausgewählt. Als nächstes wird das Element 2 aus der Menge s2 ausgewählt. Dann muß ein Element aus der Menge s3 ausgewählt werden. Die Menge s3 enthält die Elemente 1 und 2, welche in der bisheri­ gen Lösung bereits enthalten sind, was darauf hinzeigt, daß die rekursive Funktion aufgerufen wird. Es sei das Element 1 der Menge s3 die neue Lösung, was bedeutet, daß das Element 1 der Menge s1 aus der Lösung zu entfernen ist. Dann muß man eine neue Lösung für die Menge s1 haben; hierfür ist das Ele­ ment 3 geeignet, weil mit diesem die Zahl der Lösungen größer wird, d. h. die vorhergehende Lösung (s2(2), s3(1)) wird zu (s1(3), s2(2), s3(1)). Die Rekursion stoppt dann. Im nächsten Schritt wird das Element 4 der Menge s4 und schließlich das Element 5 der Menge s5 gewählt. Somit ist die endgültige Lö­ sung: (s1(3), s2(2), s3(1), s4(4), s5(5)).

Wenn eine Überschneidung oder eine Kollision zwischen den Lö­ sungen auftritt, ist der Lösungsansatz des Algorithmus, von der Menge aus zu beginnen, die noch keine Lösung hat. Dieser Startpunkt kann nicht immer als empfehlenswert angesehen wer­ den, da der Algorithmus in einer Schleife zwischen den glei­ chen Mengen bleiben kann, bis er ein Element der früheren Mengen findet, welches die Lösung vergrößert. Ein besserer Startpunkt ist dann, ein Element einer früheren Menge sX zu wählen, mit dem eine neue Lösung gefunden werden kann. Der Rest der Lösungen wird gefunden, indem der Algorithmus in entgegengesetzter Richtung durchlaufen wird.

Als nächstes wird betrachtet, wie eine geeignete rekursive Funktion realisiert wird. Im Fall einer Kollision wird eine Menge sX ausgewählt, die ein Element besitzt, welches eine zusätzliche Lösung hervorbringt. Die vorhergehende Auswahl in dieser Menge sX ist zu entfernen. Es wird nun eine freie Lö­ sung in einer anderen Menge gewählt und das zuvor für diese gewählte Element aus der Lösung entfernt. Diese Wählen/Entfer­ nen-Funktion in einer Menge setzt sich durch die Mengen der Gesamtlösung fort, bis ein beseitigtes Element in einer Menge gefunden wird, von der aus die Rekursion gestartet wurde, d. h. in der Menge, die zuvor nur solche Elemente hatte, die bereits in anderen Mengen enthalten waren.

Anhand eines Beispiels wird nun die oben beschriebene Rekur­ sionssituation betrachtet und ein glatteres Verfahren angewen­ det. Die Menge s3 hat dann zwei Elemente, von denen jedoch keines ausgewählt werden kann. Sowohl s1 als auch s2 können die Lösung vergrößern. Die Menge s1 umfaßt ferner die Elemente 3 und 5 und die Menge s2 ferner das Element 4. Man nehme nun das Element 3 der Menge s1. Dann wird das zuvor gewählte Ele­ ment 1 der Menge s1 entfernt, wodurch in einer anderen Menge das Element 1 gewählt werden kann. Untersucht man die Menge s3, erkennt man, daß auch diese Menge das Element 1 enthält, welches dann als Lösung für die Menge s3 gewählt wird. Somit ist die Gesamtlösung (s1(3), s2(2), s3(1)).

Der Nachteil dieses Verfahrens oder Algorithmus ist seine Ineffizienz. Die Zeit, die zur Vergrößerung der Lösung erfor­ derlich ist, d. h. um eine weitere Verbindung über die Raum­ stufe einzufügen, ist in der Praxis viel zu lang. Im schlimmsten Fall kann man k neue Auswahlen benötigen, um die Lösung von k-1 auf k zu vergrößern. Theoretisch kann die Lö­ sung für den gesamten Zeitschlitz dann Σk Schritte erfordern. Im schlimmsten Fall ist die theoretische Effizienz des Aus­ wahlprozesses (100% × 16)/Σk = 11,76%, wenn k_max = 16 oder wenn die Größe der Koppeleinrichtung 16 × 16 beträgt.

Der erfindungsgemäße Game-Algorithmus benutzt eine Verbin­ dungsanforderungstabelle wie diejenige in Fig. 1. Man beachte, daß die auf Basis der Ausgangstore aufgestellte Tabelle einen Vermittlungszustand zeigen muß, bei dem die Elemente der Ta­ belle die Eingänge der Koppeleinrichtung anzeigen. So ent­ spricht in der Tabelle eine Reihe dem Ausgangstor, eine Spalte dem Zeitschlitz, und die Elementinhalte entsprechen dem Ein­ gangstor und dem Zeitschlitz. Von der Verbindungsanforderungs­ tabelle werden die Verbindungen in zwei Hilfstabellen abgebil­ det, welche die Verbindungen von den Eingängen zu den Ausgän­ gen festlegen.

Die primäre Funktion des erfindungsgemäßen Algorithmus ist, alle Verbindungen in einem Versuch problemmäßig zu lösen, ohne die Verbindungsanforderungstabelle in kleinere Teile zu zerle­ gen. Die beiden Hilfstabellen, d. h. die Eingangstabelle und die Ausgangstabelle, sind in zwei Feldern aufgebaut, welche nach Zeitschlitzen geordnet sind. Diese zwei Felder umfassen die zwei Achsen der imaginären Matrix. Fig. 2 zeigt ein Bei­ spiel dieser Felder, die zu einer imaginären Matrix auf Grund­ lage der in Fig. 1 vorgelegten Daten angeordnet sind. Die x- Achse der Matrix entspricht dem Eingangstor-Anforderungsfeld und die y-Achse dem Ausgangstor-Anforderungsfeld.

In Fig. 2 befinden sich die Eingänge auf der x-Achse. Die erste oder obere Reihe gibt das Eingangstor an, die zweite Reihe den Zeitschlitz der Eingangsverbindung. Die dritte Reihe der x-Achse gibt das Ziel-Ausgangstor und den Ziel-Zeitschlitz (Tor, Zeit) für das Signal am Eingangstor/Zeitschlitz an. Die erste oder außen links liegende Spalte gibt das Ausgangstor und die zweite Spalte den Zeitschlitz der Ausgangsverbindung an, was in der Ausgangsverbindungsanforderung dargestellt ist. Die dritte Spalte gibt den gewünschten Inhalt der Ausgangsver­ bindung an, d. h. die Verbindungsquelle in der Form: Eingangs­ tor, Eingangszeitschlitz. Die Struktur dieses Ausgangsfeldes ist somit die gleiche wie diejenige des Eingangsfeldes. Dar­ über hinaus stellt der Inhalt des Ausgangsfeldes die gleichen Verbindungen wie das Eingangsfeld dar; nur der Blickwinkel ist ein anderer. Im Rest der Tabelle, d. h. in der imaginären Ma­ trix, sind Verbindungen durch eine "1" angegeben. Somit ist an jedem mit "1" markierten Kreuzungspunkt einer Reihe und einer Spalte ein Eingang mit einem Ausgang verbunden.

Wenn die Größe der Matrix N × N ist (wobei N = 4 in Fig. 2), kann die Matrix in Untermatrizen der Hauptmatrix realisiert werden. Dann wird für jeden Zeitschlitz sowohl des Eingangs­ als auch des Ausgangsverbindungsfeldes eine Untermatrix gebil­ det. In der Hauptmatrix bilden die Untermatrizen eine Diago­ nale von der links oberen Ecke zur rechts unteren Ecke. Zwei dieser Untermatrizen sind in Fig. 2 durch dickere Linien ein­ gerahmt. Diese Matrizen geben die Verbindungen über die Raum­ stufe in jedem der Zeitschlitze an. Die Matrizen sind außerdem der vollständigen Lösung des SDR-Systems äquivalent.

Fig. 3 zeigt die Hauptschleife des Algorithmus. In der Haupt­ schleife werden alle Verbindungen in Untermatrizen gesammelt. Die Lösung ist vollständig, wenn alle Verbindungen in Unter­ matrizen bewegt worden sind. Die Bewegungen werden durchge­ führt, indem Reihen oder Spalten in Paaren getauscht werden. Die Bewegungen werden in den Eingangs- und Ausgangsfeldern durchgeführt, aber auch in zwei Extrafeldern, welche in fig. 2 nicht gezeigt sind. Diese Extrafelder haben die gleiche Größe wie die Eingangs- und Ausgangsfelder, enthalten aber nur ein Element. Die Funktion eines solchen Statusfelds ist, die in der ersten und zweiten Zeitstufe der TST-Koppeleinrichtung benötigten Bewegungen anzuzeigen. Daher werden diese zwei Statusfelder erstes Statusfeld und zweites Statusfeld genannt; sie entsprechen der eingangsseitigen Zeitstufe bzw. der aus­ gangsseitigen Zeitstufe.

Die Bewegungen werden in solcher Weise gesteuert, daß das Ziel jeder Bewegung stets eine Untermatrix ist. Verbindungen außer­ halb der Untermatrizen, d. h. als "1" markierte Elemente in der imaginären Matrix, besitzen stets zwei alternative Ziel-Unter­ matrizen, nämlich eine in Richtung der Reihe und die andere in Richtung der Spalte. Eine Bewegung in eine Untermatrix wird zugelassen, wenn die Verbindung die einzige ist, die das frag­ liche Eingangstor und das fragliche Ausgangstor benutzt, d. h. wenn eine eindeutige Verbindung in diesem Zeitschlitz erhalten wird. Eine Bewegung in Richtung der Reihe ersetzt wegen der Startreihenfolge in der Hauptschleife eine Bewegung in Rich­ tung der Spalte. Da eine Bewegung eigentlich ein Tausch ist, wird die ausgewählte Verbindung in eine Untermatrix bewegt und außerdem gleichzeitig die ursprüngliche oder bestehende Ver­ bindung außerhalb der Untermatrix, die sich in der Zielreihe oder -spalte befand, in die Ursprungsposition der ausgewählten Verbindung bewegt. Auf diese Weise wird eine Bewegung in Rich­ tung der Reihe durchgeführt, indem zwei Spalten untereinander vertauscht werden. In analoger Weise kann eine Bewegung in Richtung der Spalte als Tausch zwischen den fraglichen Reihen beschrieben werden. Die Bewegungen werden für alle Verbindun­ gen durchgeführt, startend von der ersten Verbindung und en­ dend bei der letzten Verbindung in dem Ausgangsfeld.

Der Algorithmus in Fig. 3 startet mit Schritt 10. In dem Ent­ scheidungsblock 11 wird untersucht, ob die Verbindung bereits in einer Untermatrix enthalten ist. Wenn dies der Fall ist, geht die Ausführung weiter zu Block 18; andernfalls wird in Block 13 untersucht, ob es in der fraglichen Untermatrix eine freie Reihe gibt. Falls nicht, wird in Block 14 untersucht, ob es in der fraglichen Untermatrix eine freie Spalte gibt. Wenn keine freie Spalte gefunden wird, springt die Ausführung zu einer Rekursions-Subroutine, die im Zusammenhang mit Fig. 4 erläutert wird. Wenn in Block 14 eine freie Spalte gefunden wird, findet in Block 15 ein Reihentausch statt, und die Aus­ führung kehrt zurück zu Block 11. Wenn in Block 13 eine freie Reihe gefunden wird, findet. In Block 17 ein Spaltentausch statt, und die Ausführung geht weiter zu Block 18. In dem Entscheidungsblock 18 wird untersucht, ob dies die letzte Verbindung war. Falls nicht, wird in Block 19 die nächste Verbindung ausgewählt, und die Ausführung fährt von Block 11 aus fort. Andernfalls endet der Algorithmus bei Schritt 20.

Die Ausführung des erfindungsgemäßen Algorithmus kann mit Hilfe des Falls der in Fig. 2 gezeigten imaginären Matrix veranschaulicht werden. Der Algorithmus startet mit der ersten Verbindung im Ausgangsfeld, d. h. der in Fig. 2 vom Eingang 3,5 zum Ausgang 1,1 angeforderten Verbindung. Diese Verbindung ist nicht in einer Untermatrix, da die Eingangs- und Ausgangszeit­ schlitze unterschiedliche Zeitschlitze haben, was in Block 11 in Fig. 3 untersucht wird. In Block 13 wird herausgefunden, daß die Untermatrix in der gleichen Reihe bereits eine Ver­ bindung aufweist, die das gleiche Eingangstor verwendet. Daher wird kein Spaltentausch durchgeführt. In Block 14 der Fig. 3 wird jedoch angezeigt, daß die Untermatrix in Richtung der Spalte frei ist, und es wird in Block 15 ein Reihentausch durchgeführt. Die Matrix der Fig. 2 wird aktualisiert; das Resultat ist eine Tabelle gemäß Fig. 5. Die geänderten Werte sind in Fettdruck und Kursivschrift gesetzt.

Als nächstes wird die Stelle 1,1 im Ausgangsfeld betrachtet. Das Element dieser Reihe verbindet nun den Eingang 4,4 mit dem Ausgang 1,1, was bedeutet, daß es sich nicht in einer Unter­ matrix befindet. Die Untermatrix in Richtung der Reihe hat eine freie Position. Daher findet ein Spaltentausch statt. Die erste Verbindung im Ausgangsfeld ist somit fertiggestellt. Die in Fig. 3 gezeigte Hauptschleife geht dann weiter zur nächsten Reihe der imaginären Matrix, welche das Ausgangstor 2 Zeit­ schlitz 1, enthält. Diese Verbindung befindet sich bereits in der Untermatrix, so daß keine Vertauschungen notwendig sind. Dann wird der nächste Ausgang, d. h. 3,1, untersucht. Die Ver­ bindung vom Eingang 1,3 zum Ausgang 3,1 befindet sich nicht in der Untermatrix. In Richtung der Reihe gibt es keine freie Position. Es wird dann ein Reihentausch durchgeführt, weil in der Spalte 3,3 (Ausgangstor 3, Zeitschlitz 3) der Untermatrix ein freies Element ist. Gleichzeitig wird die Zielreihe - oder die Verbindung 2,1→3,3 - an den Ort der untersuchten Reihe bewegt, wodurch das Verbindungselement direkt in die Unter­ matrix gelangt. Die Untermatrix in der oberen linken Ecke ist dann vollständig. Der Status der imaginären Gesamtmatrix ist nun in Fig. 6 innerhalb des Rahmens mit den dickeren Randli­ nien gezeigt.

Das Ausfüllen der Untermatrizen geht dann mit dem oben be­ schriebenen Verfahren weiter.

Wenn Reihen- und Spaltenvertauschungen wie oben beschrieben durchgeführt werden, werden auch die entsprechenden Statusfel­ der aktualisiert. Ein Spaltentausch wird in dem (der Ein­ gangsseite zugeordneten) ersten Statusfeld und ein Reihen­ tausch in dem (der Ausgangsseite zugeordneten) zweiten Status­ feld registriert.

Als nächstes wird eine Rekursionssituation mit Bezug auf Fig. 4 betrachtet. Eine Rekursion wird verwendet, wenn keine der möglichen Untermatrizen für eine Bewegung frei ist. Dies be­ deutet, daß beide Untermatrizen reserviert sind, und zwar entweder am fraglichen Eingangstor oder am fraglichen Aus­ gangstor. Wenn dies geschieht, dauert die Reihen- und Spalten­ vertauschung fort, bis eine freie Stelle gefunden wird. Das Blockdiagramm in Fig. 3 sollte mit diesen erzwungenen Reihen- und Spaltenvertauschungen ergänzt werden. Die Rekursion star­ tet beim Entscheidungsblock 14, wenn keine freie Spalte gefun­ den wird, wodurch die Ausführung zu der rekursiven Berechnung weitergeht, wie durch den Pfeil 16 angedeutet.

Die rekursive Berechnung ähnelt der oben beschriebenen rekur­ siven Funktion im Prüfalgorithmus. Bei dem erfindungsgemäßen Game-Algorithmus wird eine frühere Auswahl aus der Untermatrix befreit und gleichzeitig aus der Untermatrix entfernt. Dies entspricht der Wirkung des Prüfalgorithmus, bei dem eine neue Lösung anstatt der alten gewählt wird. Nun jedoch wird der Game-Algorithmus benutzt, um die Untermatrix zu füllen, so daß eine neue Arbeitslösung erhalten wird. Das Problem ist aller­ dings, daß man sicherstellen muß, daß der Game-Algorithmus nicht in einer Schleife steckenbleibt, wenn eine freie Unter­ matrix für eine aus einer Untermatrix herausgetauschte Ver­ bindung geholt wird. Der Prüfalgorithmus ist erfolgreich, weil er auf dem Prinzip funktioniert, daß in jedem Entfernen/Wäh­ len-Schritt nur die neue Lösung zur Abarbeitung ausgewählt wird. Der erfindungsgemäße Game-Algorithmus benutzt den glei­ chen Wählprozeß, wenn er neue Verbindungen zur Abarbeitung übernimmt.

Es wird nun ein Blick auf die Rekursionssituation geworfen. Der Grundaufbau einer großen Koppelmatrix basiert auf der Tatsache, daß zu einem gegebenen Zeitpunkt auf einer Reihe oder einer Spalte nur eine Verbindung vorhanden ist. Wenn die Rekursion beginnt, stehen für das fragliche Signal bei ent­ sprechend reserviertem oder belegtem Tor zwei Untermatrixkan­ didaten zur Verfügung: eine Untermatrix auf der Eingangsseite, d. h. eine Untermatrix in Reihenrichtung, und eine weitere Untermatrix auf der Ausgangsseite, d. h. eine Untermatrix in Spaltenrichtung. Den ganzen Rekursionsprozeß hindurch sind nur diese beiden Untermatrizen beteiligt, da die Rekursion unmit­ telbar dann endet, wenn in einer der Untermatrizen eine freie Stelle gefunden wird. Dies bedeutet, daß bei der Rekursion Verbindungen zwischen diesen Untermatrizen bewegt werden, bis eine freie Stelle gefunden wird. Wenn die Rekursion dann in eine Schleife eintritt, müssen Vertauschungen zwischen diesen zwei Untermatrizen stattfinden. Dies bedeutet auch, daß an dem Rekursionsprozeß keine Verbindungen außerhalb dieser zwei Untermatrizen beteiligt sind. Fig. 4 stellt eine Situation mit zwei benachbarten Untermatrizen dar.

In Fig. 4 beginnt der Rekursionsprozeß damit, daß die Stelle einer gültigen Verbindung geändert wird, so daß die Verbindung von dem in der rechten oberen Ecke der Figur gezeigten Raum s1 wegbewegt wird. Die Bewegung betrifft zunächst die Verbindung b1 die vom Raum s1 in die Untermatrix s3 bewegt wird. Der Tausch bedeutet, daß die an dem Tausch beteiligten Verbindun­ gen b1 und b2 die einzigen Verbindungen sind, die ein gemein­ sames Tor benutzen, was den Tausch notwendig macht. In der Figur ist dieses Tor im Zeitschlitz t+1, bezüglich dessen sich die Signale b1 und b2 überschneiden, das Ausgangstor O1. Wenn die Rekursion fortgesetzt wird, ist es erforderlich, daß der nächste erzwungene Tausch Signale betrifft, die ein gemeinsa­ mes Tor aufweisen, welches nicht das gleiche Tor wie das ge­ meinsame Tor beim vorangehenden, das Signal b1 betreffenden Tausch sein kann. In diesem Fall erfolgt der Tausch links in der Untermatrix s2 und betrifft die Signale b2 und b3. Das diesen Signalen gemeinsame Tor ist in diesem Fall das Ein­ gangstor I1, was bedeutet, daß das Signal b3 wegzubewegen ist. Es wird dann b3 aus der Untermatrix s2 in den Raum s1 und von dort in die Untermatrix s3 bewegt. Das als nächstes bewegte Signal b4 muß wiederum ein gemeinsames Tor (O2) mit dem Signal b3 haben. Daher wird b4 in den Raum s1 bewegt. Die nächste Verbindung ist b5; sie wird aus der Untermatrix s2 bewegt, weil sie das gleiche Eingangstor wie die Verbindung b4 be­ sitzt.

Der "Domino"-Effekt der Rekursion kann über alle verfügbaren Tore fortgesetzt werden. Um die Rekursion in eine Schleife gehen zu lassen, muß eine Verbindung vorliegen, welche in die fette der zwangsweisen Vertauschungen hineingetauscht wird. Die einzig verfügbare Möglichkeit für einen Tausch ist beim Beginn der Kette, weil das einzige nicht getroffene Tor das der Verbindung b1 ist, d. h. deren Eingangstor Ix. In Fig. 4 ist Ix = I4. Da Ix ein Tor ist, das auch in einer anderen Untermatrix für die Verbindung b1 reserviert befunden wurde, bedeutet dies, daß die Verbindung bz und das Tor Ix, welche die Überschneidung verursachen, bereits in einer anderen Un­ termatrix sind. Der einzige Weg, um die Verbindung bz mit b1 zu vertauschen, ist, eine andere Verbindung für das Tor Ix zu finden. Da b1 und bz das Tor Ix verwenden, kommt eine dritte Verbindung, die das gleiche Tor Ix verwendet, in dem durch die Untermatrizen überdeckten Bereich nicht in Frage. Daher kann keine Rekursion eintreten, die eine Schleife am Beginn der Vertauschungskette verursachen würde. Die Kettenreaktion er­ fordert daher höchstens 2x(k-1) Vertauschungen, um die Ver­ bindung und ihre Anordnung in einer Untermatrix durch Rekur­ sion problemmäßig zu lösen. k entspricht dann der Größe der Koppeleinrichtung, d. h. k_max = 16. Der Kettenvertauschungsprozeß ähnelt dem Prüfalgorithmus im Hinblick auf die Umordnung der Lösungen innerhalb der Untermatrix; die hier offenbarte Re­ kursion löst aber auch gleichzeitig zwei Untermatrizen.

Die Stärke des Game-Algorithmus ist, daß keine echten Berech­ nungsprozesse notwendig sind. Es werden lediglich die Verbin­ dungen in vakante Stellen in verschiedenen Untermatrizen be­ wegt. Ein weiterer Vorteil des Game-Algorithmus ist, daß nur Verbindungen außerhalb der Untermatrizen vertauscht werden, was bereits erfolgreiche Verbindungen unberührt läßt. Der Vertauschungsprozeß hat außerdem eine sehr nützliche Eigen­ schaft: Eine in eine Untermatrix bewegte Verbindung kann eine andere Verbindung in nur einem Ausführungsschritt unmittelbar in eine andere Untermatrix verdrängen. Der in dem Algorithmus enthaltene Rekursionsprozeß zeigt darüber hinaus bessere Ei­ genschaften im Vergleich zu dem Prüfalgorithmus. Bei dem Re­ kursionsprozeß werden aus einer Untermatrix bewegte Verbindun­ gen dazu benutzt, eine andere Untermatrix zu ergänzen, und zwar sogar in solcher Weise, daß zwei Matrizen gleichzeitig bearbeitet werden können. Der größte Vorteil des Game-Algo­ rithmus ist, daß er mit einer Sammlung eindeutiger Verbindun­ gen beginnt, welche dann neu geordnet werden, wodurch man beim Game-Algorithmus nicht alles von vorne bzw. ohne Vorgabe be­ ginnen muß, wie dies beim Prüfalgorithmus und einigen anderen Algorithmen der Fall ist.

Da vor der Wahl einer Bewegung einer Verbindung beim Game- Algorithmus keine spezielle Berechnung notwendig ist, kann eine Verbindung in zwei möglichen Richtungen bewegt werden. Die Entscheidung über die Vertauschung einer Verbindung wird auf Zufallsbasis getroffen, abhängig lediglich von der Ver­ teilung der Verbindungen in der Ausgangsmatrix. Insbesondere zwangsweise Vertauschungen können zur Lösung schwieriger Zu­ fallssituationen verwendet werden.

Es wird eine digitale Koppeleinrichtung vorgeschlagen, die erfindungsgemäß mit Hilfe eines Game-Algorithmus konfiguriert wird, wenn das Verbindungsproblem durch eine imaginäre Ver­ bindungsmatrix definiert wird. Die Signale werden in der Ver­ bindungsmatrix nach Zeitschlitzen angeordnet, so daß längs der Diagonalen der Matrix Untermatrizen gebildet werden. Zunächst wird untersucht, ob in einer Untermatrix bereits eine Verbin­ dung vorhanden ist. Wenn nicht, wird untersucht, ob in der Reihe der abgearbeiteten Verbindung in der fraglichen Unter­ matrix ein freier Platz vorhanden ist. Wenn ein freier Platz vorhanden ist, wird zwischen der Spalte der Verbindung und der freien Spalte in der Untermatrix eine Vertauschung durchge­ führt. Andernfalls wird untersucht, ob in der Spalte der abge­ arbeiteten Verbindung in der fraglichen Untermatrix ein freier Platz vorhanden ist, und eine Vertauschung zwischen der Reihe der abgearbeiteten Verbindung und der freien Reihe in der Un­ termatrix durchgeführt. Andernfalls wird in einer Rekursions­ stufe eine zwangsweise Reihen- und/oder Spaltenvertauschung durchgeführt und zum Beginn des Prozesses zurückgekehrt. Schließlich wird untersucht, ob alle Verbindungen in der Ma­ trix abgearbeitet worden sind, und der Prozeß beendet.

Claims (5)

1. Verfahren zum Vermitteln digitaler Signale zwischen gege­ benen Eingangs- und Ausgangspunkten in einer digitalen Koppeleinrichtung in solcher Weise, daß in einem Zeit­ schlitz nicht mehr als ein Signal auf ein und dasselbe Ausgangstor gerichtet wird, dadurch gekennzeichnet, daß es Schritte umfaßt, bei denen

• a) eine (k × k)-Verbindungsanforderungstabelle mit n Zeitschlitzen für k Eingangstore in einer Reihe und n Zeitschlitzen für k Ausgangstore in einer Spalte erzeugt wird, wobei der Inhalt eines Elements dem Eingangstor und dem Eingangszeitschlitz entspricht, und die Verbindungen aus der Verbindungsanforde­ rungstabelle in zwei Hilfstabellen niedergeschrieben werden, welche die Verbindungen von Eingängen zu Ausgängen beschreiben und deren erste den Eingängen und deren zweite den Ausgängen entspricht, wobei die Hilfstabellen zwei Achsen einer durch die Verbin­ dungsanforderungstabelle gebildeten, imaginären Ma­ trix bilden,
• b) n × n-Untermatrizen auf der Diagonalen der Matrix erzeugt werden,
• c) eine erste abzuarbeitende Verbindung ausgewählt wird,
• d) untersucht wird, ob die Verbindung in einer Unter­ matrix liegt, und - falls dem so ist - zu Schritt g) gegangen wird, andernfalls
• e) untersucht wird, ob in der Reihe der abgearbeiteten Verbindung in der fraglichen Untermatrix ein freier Platz vorhanden ist, und - falls dem so ist - ein Tausch zwischen der Spalte der abgearbeiteten Ver­ bindung und der freien Spalte in der Untermatrix durchgeführt wird, andernfalls
• f) untersucht wird, ob in der Spalte der abgearbeiteten Verbindung in der fraglichen Untermatrix ein freier Platz vorhanden ist, und - falls dem so ist - ein Tausch zwischen der Reihe der abgearbeiteten Verbin­ dung und der freien Reihe in der Untermatrix durch­ geführt wird und zu Schritt d) zurückgegangen wird, andernfalls ein zwangsweiser Reihen- und/oder Spal­ tentausch in einer Rekursionsstufe durchgeführt wird und zu Schritt d) zurückgegangen wird,
• g) untersucht wird, ob alle Verbindungen in der Matrix abgearbeitet worden sind, und - wenn dies der Fall ist - der Prozeß beendet wird, andernfalls die näch­ ste abzuarbeitende Verbindung aus der Verbindungs­ matrix ausgewählt und zu Schritt d) zurückgegangen wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß eine Untermatrix einem Zeit­ schlitz entspricht.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Auswahl in Schritt c) ausschließlich auf eine Verbindung gerichtet wird, die zuvor noch nicht abgearbeitet worden ist.

4. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß k = 16 und n = 63.

5. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß in der Rekursionsstufe Ver­ bindungen zwischen den zwei fraglichen Untermatrizen ver­ tauscht werden, bis wenigstens eine der Untermatrizen eine freie Stelle enthält.