DE69028798T2

DE69028798T2 - Netzwerksteueranordnung zur Verarbeitung von mehreren Verbindungsanfragen

Info

Publication number: DE69028798T2
Application number: DE69028798T
Authority: DE
Inventors: Gaylord W Richards
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1989-05-08
Filing date: 1990-05-01
Publication date: 1997-04-17
Anticipated expiration: 2010-05-02
Also published as: JPH0349335A; US4993016A; JPH07101875B2; EP0397370A3; EP0397370A2; EP0397370B1; DE69028798D1

Description

Die Erfindung betrifft ein Kommunikationsnetzwerk-Steuersystem, das sowohl in leitungsvermittelten als auch in paketvermittelten Netzwerken Anwendung finden kann, um verfügbare Netzwerkwege schnell zu ermitteln und eine Kommunikation über solche Wege zu ermöglichen.
Die Zeit, die erforderlich ist, eine Wegsuche durch ein Vermittlungsnetzwerk durchzuführen, begrenzt effektiv die Geschwindigkeit, mit der leitungs- oder paketvermittelte Kommunikationen über das Netzwerk aufgebaut werden können. Der Wegsuchprozeß beruht auf drei Grundbestimmungen:
1) Identifizieren eines oder mehrerer Wege zwischen einem bestimmten Netzwerkeingang und einem bestimmten Netzwerkausgang,
2) Feststellen, ob einer der identifizierten Wege frei ist, und
3) wenn mehr als einer der identifizierten Wege frei ist, Auswählen eines Weges zur Verwendung für eine bestimmte Kommunikation.
Ist ein freier Weg erst einmal ausgewählt worden, müssen weitere Steuertätigkeiten ausgeführt werden, um die Kommunikation über diesen Weg zu ermöglichen. Wie in einem Aufsatz von A. Feiner et al., Bell System Technical Journal, September 1964, Seiten 2208-2214, offenbart ist, bestand eine Grundentscheidung beim Entwurf des 1 ESS -Schalters darin, die Wegesuchfunktion vom Vermittlungsnetzwerk selbst zu isolieren. Ein zentraler Prozessor führt alle Wegsuchfunktionen durch und legt eine ständige Aufzeichnung aller relevanten Vermittlungsinformationen in einem Speicher ab. Da lediglich ein einzelner Prozessor verwendet wird, wird lediglich eine Wegesuchoperation zu einem Zeitpunkt durchgeführt. Demzufolge gibt es keine Möglichkeit, einen Fehler aufgrund eines Speichers zu begehen, auf den für eine zweite Wegesuchoperation zugegriffen wird, bevor ein Weg, der als Ergebnis einer ersten Wegesuche ausgewählt wird, als besetzt gekennzeichnet wird. Da allerdings Netzwerkentwicklungen auf die Übertragung einer großen Vielfalt von Sprach-, Bild- und Dateninformationen und insbesondere auf Netzwerke gerichtet sind, die für die Verwirklichung im Fotobereich entwickelt wurden, und wo leitungsvermittelte oder paketvermittelte Verbindungen eine hohe Rate erfordern, kann die Begrenzung auf eine Wegesuchoperations- Charakteristik bekannter Netzwerksteueranordnungen auf der Basis "Eine Wegsuche zu einem Zeitpunkt" zu langen Verbindungsanforderungs- Warteschlangen und Verbindungsaufbau-Verzögerungen führen.
In der EP-A-0 141 233 ist ein einstufiger Koppelpunktschalter (Crosspoint-Schalter) offenbart, der Zeilen aufweist, die mit Eingängen und auch Ausgängen verbunden sind. Die Spalten sind im wesentlichen "Knoten", die jede Zeile mit irgendeiner anderen Zeile verbinden können, indem Koppelpunktschalter zwischen den Zeilen und einer Spalte in den "Ein"- Zustand gesteuert werden. Da jede Spalte jede Zeile (Eingang) mit irgendeiner anderen Zeile (Ausgang) verbinden kann, existiert das Problem eines Konfliktes (Kollision) in den Knoten oder Verbindungen des Schalters nicht.
Gemäß einem Gesichtspunkt der Erfindung wird ein in Anspruch 1 umschriebenes Verfahren zur Verfügung gestellt.
Gemäß einem weiteren Gesichtspunkt der Erfindung wird eine Anordnung nach Anspruch 13 geschaffen.
In einer beispielhaften Netzwerksteueranordnung, die unter Verwendung einer Hardware anstelle eines einzelnen, Software-gesteuerten Prozessors verwirklicht ist, werden zwei oder mehrere Wegesuchoperationen unter Verwendung einer der beiden Techniken parallel durchgeführt:
1) Lesen eines Speichers für eine zweite Wegesucheoperation während der Zeit, während der Informationen, die aus dem Speicher für eine erste Wegesucheoperation ausgelesen werden, zum Auswählen eines Weges verarbeitet werden, und
2) Aufrechterhalten von Doppelspeichern und deren Auslesen, um zwei Wegesuchoperationen vor der Aktualisierung beider Speicher durchzuführen. Für die beispielhaften, hier beschriebenen Netzwerke ist es ziemlich wahrscheinlich, daß kein Netzwerkweg von einem ersten Eingang mit einem ersten Ausgang in Konflikt mit irgendeinem der Netzwerkwege von einem zweiten Eingang zu einem zweiten Ausgang steht. Außerdem kann eine einfache logische Schaltung schnell feststellen, ob zwei Verbindungsanforderungen kollidieren. Mehrere Wegesuchoperationen werden nur dann durchgeführt, wenn keine Kollision gegeben ist.
Ein Verfahren gemäß der Erfindung wird in einer Anordnung mit einem Netzwerk zur Verbindung eines beliebigen Eingangs von einer Vielzahl von Eingängen mit einem beliebigen Ausgang einer Vielzahl von Ausgängen und mit einer Einrichtung zur Speicherung von Besetzt-/Frei-Informationen für Wegekomponenten verwendet. Die Speichereinrichtung wird ausgelesen, um einen freien Weg von einem ersten Netzwerkeingang zu einem ersten Netzwerkausgang zu identifizieren. Nach der Identifizierung eines freien Weges werden Wegekomponenten des Weges in der Speichereinrichtung als besetzt markiert. Bevor jedoch der Weg als besetzt markiert wird, wird auf die Speichereinrichtung zugegriffen, um einen freien Weg von einem zweiten Netzwerkeingang zu einem zweiten Netzwerkausgang zu finden.
Eine beispielhafte Netzwerksteuereinrichtung (Fig. 1) wird zur Steuerung eines 512x512-Mehrstufen-Überkreuzungs-Netzwerks (Fig. 38), auch Mehrstufen-Crossover-Netzwerk genannt, verwendet. Die Steuereinrichtung weist mehrere Speicher auf, von denen jeder Besetzt-/Frei- Stufeninformationen für eine der Netzwerkstufen speichert. Eine Wegetrennungs-Prüfeinheit (Fig. 46) stellt fest, ob ein beliebiger Netzwerkweg von einem ersten Netzwerkeingang zu einem ersten Netzwerkausgang mit einem beliebigen Netzwerkweg von einem zweiten Netzwerkeingang zu einem zweiten Netzwerkausgang kollidiert. Auf die Stufenspeicher wird zugegriffen, um einen freien Weg vom zweiten Eingang zum zweiten Ausgang vor der Aktualisierung der Stufenspeicher zu finden, und zwar nur dann, wenn festgestellt wird, daß keine Kollision möglich ist. Die Wegetrennungs- Überprüfung erfolgt dadurch, daß entsprechende Bits der binären Eingangsnummern, die dem ersten und zweiten Eingang zugeordnet sind, und entsprechende Bits der binären Ausgangsnummern, die dem ersten und zweiten Ausgang zugeordnet sind, logisch kombiniert werden.
Gemäß einer ersten Mehrfach-Verarbeitungstechnik wird eine Besetzt-/Frei-Information aus den Stufenspeichern ausgelesen und nachfolgend zur Identifizierung eines freien Weges verarbeitet. Gleichzeitig mit der Identifikationsverarbeitung wird wieder auf die Stufenspeicher zugegriffen, um eine weitere, nicht kollidierende Wegesuche auszuführen.
Eine alternative Netzwerksteuereinrichtung (Fig. 45) weist für jede Stufe vielfältige erste und zweite Speicher auf. In einer zweiten Mehrfach- Verarbeitungstechnik werden die ersten Stufenspeicher und die zweiten Stufenspeicher gleichzeitig ausgelesen, um zwei Wegesuchoperationen auszuführen. Identifizierte Wege werden nachfolgend sowohl in den ersten als auch in den zweiten Stufenspeicher markiert. Die alternative Netzwerksteuereinrichtung wendet ebenso die erste Mehrfach- Verarbeitungstechnik an, um ferner die Verbindungsanforderungs- Verarbeitungszeiten zu verringern.
Eine bestimmte, beispielhafte Ausführungsform der Erfindung ist in einer Netzwerksteuereinrichtung 1300 (Fig. 1) verwendet, die ein 512x512- Mehrstufen-Überkreuzungs-Netzwerk 1200 (Fig. 38) steuert. Um ein besseres Verständnis für die Größe des Netzwerkes 1200 und der möglichen Komplexität einer Durchführung von Wegesuchoperationen in einem Netzwerk dieser Größe zu bekommen, betrachten wir zunächst das 16x16- Überkreuzungs-Netzwerk 1170 (in Fig. 34 bis 36) und beachten das Muster von Überkreuzungs-Verbindungen von Stufe zu Stufe. Fig. 37 ist eine Darstellung der relativen Größe des 16x16-Netzwerks 1170 und des 512x512-Netzwerkes 1200. Es ist auch ein 128x128-Netzwerk mittlerer Größe dargestellt. Das Überkreuzungs-Netzwerk 1200 (Fig. 38) enthält 15 Stufen; allerdings führen die Stufen 1, 2, 3, 13, 14 und 15 keine Vermittlungsfunktion durch, sondern werden lediglich zum Verwirklichen des Ausgangsfächers/Eingangsfächers F=8 benutzt. Die Netzwerksteuereinrichtung 1300 wird zur Durchführung von Wegesuch-, Verbindungs- und Trennfunktionen für das Netzwerk 1200 über mehrere Stufensteuereinrichtungen 1201 bis 1209 benutzt, und zwar individuell für die Stufen 4 bis 12. Für das vorliegende Beispiel handelt es sich bei den Knoten der Vermittlungsstufen 4 bis 12 um Vermittlungsknoten voller Kapazität, wie beispielsweise der Knoten nach Fig. 6.
Die Netzwerksteuereinrichtung 1300 (Fig. 1) weist mehrere Speicher 1312 auf, die jeweils Besetzt-/Frei-Stufeninformationen für eine der Verbindungsstufen des Netzwerks 1200 speichern. Die Besetzt-/Frei- Stufeninformation wird gleichzeitig von allen Speichern 1312 kombiniert, um einen freien Weg von einem bestimmten Eingang des Netzwerkes 1200 zu einem bestimmten Ausgang des Netzwerkes 1200 zu finden. Das Netzwerk 1200 besitzt acht Wege von einem bestimmten Eingang zu einem bestimmten Ausgang. Jeder Stufenspeicher 1312 speichert die Besetzt-/Frei-Stufenbits für alle acht Wege unter einer adressierbaren Speicherstelle auf der Grundlage des bestimmten Ein- und Ausgangs. Die Besetzt-/Frei-Stufenbits werden für alle Wege und alle Stufen gleichzeitig ausgelesen. Acht Besetzt-/Frei- Prüfeinrichtungen 1314 ermitteln gleichzeitig den gesamten Besetzt-/Frei- Gesamtzustand aller acht Wege. Eine Freier-Weg-Auswahleinheit 1316 wählt einen der freien Wege zur Verwendung für eine bestimmte Kommunikation aus. Alle Stufenspeicher 1312 werden gleichzeitig aktualisiert, um die ausgewählten Wege wieder als besetzt festzulegen. Signale werden zu den Knoten-Stufensteuereinrichtungen 1201 bis 1209 übertragen, um den ausgewählten Weg für eine Kommunikation und Informationen freizugeben, die festlegen, daß der Weg in den Wegspeicher 1318 geschrieben wird. Wenn eine Trennanforderung empfangen wird, wird die Besetzt-/Frei- Stufeninformation in allen Stufenspeichern 1312 gleichzeitig geändert, um wieder einen freien Zustand widerzuspiegeln. Signale werden zu den Knoten- Stufensteuereinrichtungen 1201 bis 1209 (Fig. 38) übertragen, um eine Kommunikation über den Weg zu sperren, wobei die Weginformation aus dem Wegspeicher 1318 (Fig. 1) gelöscht wird.
Bei dem Netzwerk 1200 ist es sehr wahrscheinlich, daß zwei Verbindungsanforderungen nicht kollidieren, d. h. keiner der acht Wege des Netzwerkes 1200 von einem ersten Eingang zu einem ersten Ausgang kollidiert mit irgendeinem der acht Wege des Netzwerks 1200 von einem zweiten Eingang zu einem zweiten Ausgang. Eine Wegetrenn-Prüfeinheit 1306 (Fig. 46) stellt fest, ob irgendein Netzwerkweg für die beiden Verbindungsanforderungen kollidiert. Auf die Stufenspeicher 1312 wird zugegriffen, um einen freien Weg vom zweiten Eingang zum zweiten Ausgang vor deren Aktualisierung zu finden, und zwar nur dann, wenn festgestellt wird, daß keine Kollision möglich ist. Die Wegetrenn-Prüfung erfolgt durch logisches Kombinieren entsprechender Bits der binären Eingangsnummern, die dem ersten und zweiten Eingang zugeordnet sind, und durch logisches Kombinieren entsprechender Bits der binären Ausgangsnummern, die dem ersten und zweiten Ausgang zugeordnet sind.
Bei einer ersten Mehrfach-Verarbeitungstechnik wird die Besetzt/Frei-Information aus den Stufenspeichern 1312 ausgelesen und nachfolgend von den Besetzt-/Frei-Prüfeinheiten 1314 und der Einheit 1316 zum Auswählen eines freien Weges nachfolgend verarbeitet, um einen freien Weg zu identifizieren. Gleichzeitig mit der Wegeidentifikations-verarbeitung wird wiederum auf die Stufenspeicher 1312 zugegriffen, um eine weitere, nicht kollidierende Wegesuche durchzuführen.
Eine alternative Netzwerksteuereinrichtung 1301 (Fig. 45) besitzt vervielfältigte erste und zweite Doppelspeicher 1312 für jede Stufe. In einer zweiten Mehrfach-Verarbeitungstechnik werden die ersten und zweiten Speicher 1312 gleichzeitig ausgelesen, um zwei Wegesuchfunktionen durchzuführen. Identifizierte Wege werden nachfolgend sowohl im ersten als auch im zweiten Speicher 1312 als besetzt markiert. Die Steuereinrichtung 1301 wendet auch die erste Mehrfach-Verarbeitungstechnik an, um Verbindungsanforderungs-Verarbeitungszeiten weiter zu verringern.

Beschreibung der Zeichnungen

Es zeigen:
Fig. 1 ein Diagramm einer beispielhaften Netzwerksteuereinrichtung zur Steuerung eines 512x512-Mehrstufen-Überkreuzungsnetzwerks nach Fig. 39,
Fig. 2 das Schaltbild eines Ausführungsbeispiels einer Netzwerktopologie für ein System mit Expansion, einem Netzwerk mit perfekter Umordnung und Konzentration;
Fig. 3, 4 und 5 Schaltbilder der Netzwerktopologie gemäß Fig. 2 mit unterschiedlicher Verwirklichung der Expansion und Konzentration;
Fig. 6, 7 und 8 Schaltbilder eines Knotens mit voller Kapazität, eines Knotens der Kapazität eins mit Auswahlmöglichkeit und eines Knotens der Kapazität eins ohne Auswahlmöglichkeit zur Verwendung bei dem System nach Fig. 2;
Fig. 9 das Schaltbild einer Netzwerktopologie ähnlich der gemäß Fig. 2, aber ohne Konzentration;
Fig. 10 das Schaltbild einer Netzwerktopologie ähnlich der gemäß Fig. 2, aber ohne Expansion;
Fig. 11 das Schaltbild eines einstufigen, streng nicht blockierenden Netzwerkes;
Fig. 12 das Schaltbild eines dreistufigen, streng nicht blockierenden Clos- Netzwerks;
Fig. 13 das Schaltbild eines allgemeinen, dreistufigen, streng nicht blockierenden Clos-Netzwerks;
Fig. 14 das Schaltbild eines fünfstufigen, streng nicht blockierenden Clos- Netzwerks;
Fig. 15 das Schaltbild eines vielstufigen Verbindungsnetzwerks (MIN);
Fig. 16 das Schaltbild eines speziellen Typs eines MIN, das hier als erweitertes, verallgemeinertes Umordnungsnetzwerk (EGS) bezeichnet wird;
Fig. 17 und 18 Schaltbilder eines Beispiels für ein EGS-Netzwerk;
Fig. 19 das Schaltbild eines Kanalgraphen L(xy)vom Eingang x zum Ausgang y des Netzwerks gemäß Fig. 17 und 18;
Fig. 20 das Schaltbild eines einzelnen, kreuzenden Anrufs zusätzlich zum Kanalgraphen L(xy) gemäß Fig. 19;
Fig. 21 und 23 Schaltbilder des Netzwerks gemäß Fig. 16, die zur Ableitung von Nichtblockierungskriterien für das Netzwerk benutzt werden;
Fig. 22 ein Schaltbild des Netzwerks gemäß Fig. 18 zur Beschreibung einer Netzwerkeigenschaft, die hier als Vorwärts-Rückwärts-Invarianzeigenschaft (FBIP) bezeichnet wird;
Fig. 24 das Schaltbild eines Beispiels für ein nicht blockierendes EGS-Netzwerk;
Fig. 25 das Schaltbild eines speziellen Netzwerks mit perfekter Umordnung, nämlich des Überkreuzungs- (oder Halb-Überkreuzungs-) Netzwerks;
Fig. 26 das Schaltbild eines EGS-Netzwerks, das einen wichtigen Sonderfall eines Netzwerks mit perfekter Umordnung darstellt;
Fig. 27 ein Wegfreiwahl-Verarbeitungsflußdiagramm zur Durchführung der Wegfreiwahlfunktion in einem EGS-Netzwerk gemäß Fig. 16 mit Knoten voller Kapazität;
Fig. 28 ein Wegfreiwahl-Verarbeitungsflußdiagramm zur Ausführung der Wegfreiwahlfunktion in einem EGS-Netzwerk gemäß Fig. 16 mit Knoten der Kapazität eins;
Fig. 29 das Schaltbild eines Netzwerks mit perfekter Umordnung zur Erläuterung der Beziehung zwischen den kopplern und Linkleitungen eines Umordnungsnetzwerks zu den Eingangs-, ein Weg- und Ausgangsnummern;
Fig. 30 ein Schaltbild, das die Verwürfelung der Binärdarstellung von Eingangs-, Weg- und Ausgangsnummern für das Netzwerk gemäß Fig. 29 zur Bildung einer einzigen Binärzahl darstellt;
Fig. 31 ein Schaltbild, das die Bestimmung von Kopplern, Linkleitungen, Eingängen und Ausgängen für das Netzwerk gemäß Fig. 29 aus einer einzigen Binärzahl erläutert;
Fig. 32 eine schematische Darstellung der Transformationen zwischen verschiedenen Stufen von zwei isomorphen Netzwerktypen - Überkreuzungsnetzwerken und Netzwerken mit Umordnung-, wobei die Transformationen in Tabellen 1-3 angegeben sind;
Fig. 34 - 36 in der Anordnung gemäß Fig. 33 ein Diagramm eines zweidimensionalen 16 x 16 -Überkreuzungsnetzwerks unter Verwendung eindimensionaler Knotenanordnungen;
Fig. 37 ein Diagramm zur Erläuterung der relativen Größe des 16 x 16- Überkreuzungsnetzwerks gemäß Fig. 34-36, eines 128 x 128-Überkreuzungsnetzwerks und eines 512 x 512-Überkreuzungsnetzwerks gemäß Fig. 38;
Fig. 38 das Schaltbild eines 512 x 512-Überkreuzungsnetzwerks und eines entsprechenden Überkreuzungsnetzwerks-Steuergeräts;
Fig. 39 ein Flußdiagramm zur Verarbeitung einer Verbindungsanforderung für das Überkreuzungsnetzwerk-Steuergerät gemäß Fig. 38;
Fig. 40 ein Flußdiagramm zur Verarbeitung einer Trennanforderung für das Überkreuzungsnetzwerk-Steuergerät gemäß Fig. 38;
Fig. 42 - 44 in der Anordnung gemäß Fig. 41 ein Schaltbild für die Verwirklichung des Überkreuzungsnetzwerk-Steuergeräts gemäß Fig. 38 mit Hardware- Logikschaltungen;
Fig. 45 das Schaltbild eines alternativen Ausführungsbeispiels für das Netzwerk- Steuergerät mit verdoppelten Kopien der Netzwerksteuergerätspeicher;
Fig. 46 das Schaltbild einer Trennweg-Prüfeinheit für das Steuergerät gemäß Fig. 42 - 44;
Fig. 47 ein Zeitdiagramm zur Erläuterung der überlappenden Wegfreiwahl- Verarbeitung durch das Steuergerät gemäß Fig. 42 - 44;
Fig. 48 ein Zeitdiagramm zur Erläuterung der überlappenden Wegfreiwahl- Verarbeitung durch das alternative Steuergerät gemäß Fig. 45;
Fig. 49 das Schaltbild eines Netzwerks mit einer ersten Stufe von 1x2" Elementen, einer letzten Stufe mit 2"x1 Elementen, für das die Trennweg-Prüfeinheit gemäß Fig. 46 verwendbar ist;
Fig. 50 das Schaltbild einer Übersetzungseinheit von Überkreuzung auf Umordnung für das Steuergerät gemäß Fig. 42 - 44;
Fig. 51 das Schaltbild einer Freiweg-Auswahleinheit für das Steuergerät nach Fig. 42 - 44.

Detaillierte Beschreibung

Die folgende Beschreibung wird in zwei Abschnitte untergliedert. Zunächst wird eine reduziert blockierende Netzwerktopologie beschrieben. Vorteilhafterweise kann die Topologie im optischen Bereich verwirklicht werden. Die Netzwerk-Steueranordnungen werden anschließend beschrieben, mit denen Wege schnell aufgefunden und Kommunikationen über solche Netzwerke mit verringerter Blockierung hergestellt werden.

Netzwerk-Topologie

Fig. 2 zeigt das Blockschaltbild eines Systems 1600 mit einem Expansions- (Ausgangsverzweigungs)-Abschnitt 1610, einem Netzwerk 1620 mit perfekter Umordnung und einem Konzentrations- (Eingangsverzweigungs)-Abschnitt 1630. Das System 1600 besitzt N=4 Eingänge und M=4 Ausgänge. Das Netzwerk 1620 mit perfekter Umordnung weist vier Knotenstufen 1621-0, 1621-1, 1621-2 und 1621-3 mit 2x2-Knoten und drei Linkleitungsstufen 1622-0, 1622-1 und 1622-2 auf, die je Verbindungen mit perfekter Umordnung aufeinanderfolgender Knotenstufen durchführen. Der Expansionsabschnitt 1610 expandiert die N=4 Eingänge auf 16 (mehr als N) Eingänge der ersten Knotenstufe 1621-0. Der Konzentrationsabschnitt 11630 konzentriert 16 (mehr als M) Ausgänge der letzten Knotenstufe 1621-3 auf M=4 Ausgänge. Das System 1600 besitzt mehr als zwei Wege zwischen jedem der N Eingänge und jedem der M Ausgänge. Die einzelnen Knoten der Knotenstufen 1621-0, 1621-1, 1621-2 und 1621-3 werden durch entsprechende Stufensteuergeräte 1640, 1641, 1642, 1643 abhängig von Befehlen von einem Netzwerk- Steuergerät 1650 gesteuert.
Drei alternative Verwirklichungen des Expansionsabschnitts 1610 und des Konzentrationsabschnitts 1613 sind in den Fig. 3, 4 und 5 dargestellt. Im Expansionsabschnitt 1710 (Fig. 3) ist jeder der N=4 Eingänge direkt mit vier Eingängen der Knotenstufe 1621-0 verbunden, Im Konzentrationsabschnitt 1730 sind vier Ausgänge der Knotenstufe 1621-3 direkt mit jedem der M=$ Ausgänge verbunden. Der Expansionsabschnitt 1810 (Fig. 4) besitzt eine einzige Stufe 1811 mit 1x4 Knoten und der Konzentrationsabschnitt 1830 eine einzige Stufe 1831 mit 4x1 Knoten. Der Expansionsabschnitt 1910 (Fig. 5) hat zwei Stufen 1911 und 1912 mit 1x2 Knoten und der Konzentrationsabschnitt 1930 zwei Stufen 1931 und 1932 mit 2x1 Knoten. Jeder Expansionsabschnitt 1710, 1810, 1910 verbindet jeden der N Eingänge mit mehreren Eingängen der Knotenstufe 1621-0 nach einem hier definierten Muster unter Aufrechterhaltung einer perfekten Umordnung. Jeder Konzentrationsabschnitt 1730, 1830, 1930 verbindet mehrere Ausgänge der Knotenstufe 1621-3 mit jedem der M Ausgänge nach einem hier definierten Muster unter Aufrechterhaltung einer perfekten Umordnung.
Drei alternative 2x2-Vermittlungsknoten 1510, 1520 und 1530 zur Verwendung im System 1600 sind in den Fig. 6, 7 und 8 dargestellt. Jeder Knoten mit n Eingängen und m Ausgängen wird als Knoten voller Kapazität bezeichnet, wenn er min{nm) Signale gleichzeitig führen kann. Ein Knoten wird als Knoten mit der Kapazität eins bezeichnet, wenn er gleichzeitig nur ein Signal führen kann. Ein Knoten der Kapazität eins kann eine Wahlmöglichkeit bezüglich der Eingänge oder der Ausgänge oder auch keine Wahlmöglichkeit besitzen.
Der Knoten 1510 ((Fig. 6), ein Knoten voller Kapazität, umfaßt zwei Wähler 1511 und 1512. Der Wähler 1511 verbindet einen der Knoteneingänge I1 und I2 mit dem Knotenausgang O1 unter Ansprechen auf ein Auswahlsignal S1. Der Wähler 1512 verbindet einen der Knoteneingänge I1 und I2 mit dem Knotenausgang O2 unter Ansprechen auf ein Auswahlsignal S2
Der Knoten 1520 (Fig. 7), ein Knoten mit der kapazität eins mit einer Eingangswahlmöglichkeit, umfaßt zwei UND-Gatter 1521, 1522 und ein ODER-Gatter 1523. Das UND-Gatter 1521 überträgt ein Signal vom Eingang I1 über das ODER-Gatter 1523 zu beiden Ausgängen O1 und O2 unter Ansprechen auf ein Auswahlsignal S1. Das UND- Gatter 1522 überträgt ein Signal vom Eingang I2 über das ODER-Gatter 1523 zu beiden Ausgängen O1 und O2 unter Ansprechen auf ein Auswahlsignal S2. Nur eines der Auswahlsignale S1 und S2 ist jeweils logisch eins.
Der Knoten 1530 (Fig. 8), ein Knoten der Kapazität eins ohne Auswahlmöglichkeit, umfaßt ein ODER-Gatter 1531 und ein UND-Gatter 1532. Wenn ein Steuersignal C logisch eins ist, überträgt das UND-Gatter 1532 die logische Kombination der Signale an den Eingängen I1 und I2 zu beiden Ausgängen O1 und O2. Wenn das Steuersignal C logisch null ist, überträgt das UND-Gatter 1532 logisch null an beide Ausgänge O1 und O2. Nur einer der Eingänge I1 und I2 empfängt jeweils ein aktives Signal.
Der Knoten 1530 stellt einen Sonderfall eines allgemeineren Vermittlungsknotens dar, der hier als nxm-Modul bezeichnet wird. Ein nxm-Modul, das n Eingänge und m Ausgänge besitzt, führt entweder die logische Kombination der Signale an den n Eingängen zu allen m Ausgängen oder führt eines der Signale an den n Eingängen zu einem der m Ausgänge. Wenn ein Netzwerk mit nxm-Modulen so gesteuert wird, daß höchsten ein Eingang eines nxm-Moduls ein aktives Signal hat, so führt das nxm-Modul entweder das Signal zu allen m Ausgängen oder läßt die m Ausgänge frei. Der Knoten 1530 ist ein 2x2-Modul, das hier auch als 2-Modul bezeichnet wird.
Wenn das System 1600 (Fig. 5) unter Verwendung von 2-Modulen verwirklicht wird, beispielsweise der Knoten 1530, als Vermittlungsknoten des Netzwerks 20 mit perfekter Umordnung sowie im Expansionsabschnitt 1910 und im Konzentrationsabschnitt 1930, so werden die 2-Module des Netzwerks 1620 mit perfekter Umordnung individuell je nach Notwendigkeit abgeschaltet oder betätigt, derart, daß keines der 2-Module mehr als ein aktives Eingangssignal besitzt. Die 2-Module der letzten Expansionsknotenstufe 1912 werden ebenfalls individuell abgeschaltet oder betätigt (in Fig. 5 nicht gezeigt), derart, daß ein Signal, das an einem gegebenen Eingang der N Eingänge empfangen wird, zu nur zwei 2-Modulen der Knotenstufe 1621-0 übertragen wird. Zur Verbesserung der Toleranz des Systems 1600 gegen Fehler, beispielsweise wenn ein bestimmter 2-Modul-Ausgang auf einem logischen Wert festgehalten wird, können alle Expansions- und Konzentrations-2- Module steuerbar sein.
Fig. 9 zeigt das Blockschaltbild eines Systems 1601 mit N=4 Eingängen und M=16 Ausgängen. Das System 1601 ist identisch mit dem System 1600 (Fig. 2) mit der Ausnahme, daß der Konzentrationsabschnitt 1630 nicht erforderlich ist.
Fig. 10 zeigt das Blockschaltbild eines Systems 1602 mit N=16 Eingängen und M=4 Ausgängen. Das System 1602 ist identisch mit dem System 1600 (Fig. 2) mit der Ausnahme, daß der Expansionsabschnitt 1610 nicht erforderlich ist.
Vor einer Beschreibung der Blockiereigenschaften von Systemen, beispielsweise des Systems 1600, werden die Grundprinzipien von streng nicht blockierenden Netzwerken erläutert. Die Bedingung dafür, daß ein Netzwerk streng nicht blockierend ist besteht darin, daß die Minimalzahl von Wegen zwischen jedem Eingangs- Ausgangspaar die Maximalzahl von Wegen übersteigen muß, die zwischen diesem Paar blockiert sein können. Eine ausreichende (aber nicht notwendige) Bedingung dafür, daß ein Netzwerk streng nicht blockierend ist, besteht darin, daß die Minimalzahl von Wegen zwischen jedem Eingangs-Ausgangspaar die Maximalzahl von Wegen übersteigt, die zwischen jedem Eingangs-Ausgangspaar blockiert sein können. Als Gleichung wird diese ausreichende Bedingung wie folgt ausgedrückt:
WEGE ≥ BLOCKIERTE WEGE + 1.
Ein hilfreiches Netzwerkattribut ist, daß sich die Anzahl von Wegen und blockierten Wegen nur wenig (oder überhaupt nicht) für jede Eingangs-Ausgangs-Paar-Auswahl ändert.
Ein einstufiges, streng nicht blockierendes Netzwerk 1002 ist in Fig. 11 dargestellt. Im Netzwerk 1002 ist die Minimalzahl von Wegen zwischen jedem Eingangs- Ausgangs-Paar gleich eins. Es sind keine blockierten Wege vorhanden, da jede horizontale Schiene einem Eingang und jede vertikale Schiene einem Ausgang besonders zugeordnet ist. Daher gilt
WEGE = 1 ≥ BLOCKIERTE WEGE + 1 = 0 + 1.
Demgemäß ist das Netzwerk 1002 ein streng nicht blockierendes Netzwerk. Im Netzwerk 1002 sind NxM Kreuzpunkte vorhanden, aber es werden min{N,M] Kreuzpunkte jeweils gleichzeitig benutzt. Zur Herstellung eines Netzwerks mit besserem Wirkungsgrad werden mehrere Stufen benutzt, um mehr Wege als möglicherweise blockierte Wege zu erzeugen, während gleichzeitig die Zahl der Kreuzpunkte abnimmt.
Ein streng nicht blockierendes, dreistufiges 24x24-Clos-Netzwerk 1004 ist in Fig. 12 gezeigt. Es sind fünf Wege zwischen jedem Eingang und Ausgang vorhanden, und zwar einer über jeden Mittelstufenkoppler. Jeder Eingang (Ausgang) kann zwei Wege durch die anderen beiden Eingänge (Ausgänge) seines Kopplers blockiert haben. Wenn diese beiden Paare blockierter Wege getrennt sind, so sind insgesamt vier Wege blockiert. Unter Anwendung der Bedingung für strenges Nichtblockieren ergibt sich dann 5≥(2+2)+1. Die Zahl der Kreuzpunkte im Netzwerk 1004 beträgt 3x5x8+8x8x5+5x3x8=560. Zum Vergleich, ein 24x24-Koordinatennetzwerk besitzt 576 Kreuzpunkte.
Ein streng nicht blockierendes, dreistufiges Clos-Netzwerk 1006 ist in Fig. 13 gezeigt. (Die Zwischenstufenverbindungen sind in Fig. 13 weggelassen.) Wendet man die Bedingung für strenges Nichtblockieren auf das Netzwerk 1006 an, so beträgt die Minimalzahl von Wegen zwischen jedem Eingangs-Ausgangspaar gleich r. Die Maximalzahl blockierter Wege ist gleich (n-1) + (m-1) und daher ist, wenn gilt r≥n+m-1, das Netzwerk 1006 streng nicht blockierend. Man beachte, daß jedes S+2-stufiges Clos-Netzwerk rekursiv aus einem S-stufigen Clos-Netzwerk erzeugt werden kann, indem einfach jeder Koppler in einer gegebenen Stufe durch ein dreistufiges Clos-Netzwerk ersetzt wird. Ein streng nicht blockierendes, fünfstufiges Clos-Netzwerk 1008 ist in Fig. 14 gezeigt, wobei die Zahl der Linkleitungen zwischen den Stufen dort angegeben ist. Zwei Probleme bei der Verwirklichung von Clos Netzwerken auf photonischem Gebiet sind die folgenden: 1) nicht quadratische, nicht kleine Vermittlungselemente und 2) unterschiedliche Anzahl von Verbindungen zwischen den Stufen (geometrisch ansteigend in Richtung zur Mitte).
Ein vielstufiges Verbindungsnetzwerk (MIN) 1010 ist in Fig. 15 gezeigt und wird durch die folgenden fünf Bedingungen definiert:
(1) ein MIN besitzt eine willkürliche Zahl S Stufen von Knoten,
(2) es sind ri Knoten in jeder Stufe i vorhanden, die je ni Eingänge und mi Ausgänge haben,
(3) Knoten in unterschiedlichen Stufen können unterschiedliche Werte von ni und mi besitzen,
(4) für 1 ≥ i ≥ S-1 sind die Ausgänge der Knoten in der Stufe i (über Linkleitungen) mit den Eingängen der Knoten in der Stufe i+1 verbunden und
(5) rimi=ri+1ni+1 für 1 ≥ i ≥ S-1.
Ein erweitertes, verallgemeinertes Umordnungsnetzwerk (EGS) 1012 ist in Fig. 16 gezeigt. Ein EGS-Netzwerk ist ein MIN mit einem speziell angegebenen Linkleitungs- Verbindungsmuster. In jeder Stufe i sind die Knoten nacheinander von 0 bis ri-1 und die Ausgänge eines bestimmten Knotens nacheinander von 0 bis mi-1 numeriert. Die Ausgänge der Knoten in der Stufe i sind dann nacheinander von 0 bis rimi-1 numeriert und der Ausgang oi des Knotens xi ist mit ximi+oi numeriert. Das EGS-Verbindungsmuster ist das folgende: Der Ausgang ximi+oi der Stufe i ist mit dem Knoten (ximi+oi)modri+1 in der Stufe i+1 verbunden. Dieses Verbindungsmuster ordnet Linkleitungen nacheinander Knoten in der nächsten Stufe zu (die sogenannte perfekte Umordnung). Ein wichtiges Merkmal des EGS-Verbindungsmusters besteht darin, daß die Zahl von Wegen zwischen jeweils zwei Knoten in einer gegebenen Stufe sich nie um mehr als eins unterscheidet. Für i< j beträgt die Zahl von Wegen zwischen einem Knoten der Stufe i und einem Knoten der Stufe j entweder oder
wobei [x] die kleinste ganze Zahl ≥ x und [x] die größte ganze Zahl ≤ x angibt. Es sei ein EGS-Netzwerk mit N=n&sub1;r&sub1; Eingängen und m=msrs Ausgängen betrachtet. Die Minimalzahl von Wegen zwischen jedem Eingangs-Ausgangspaar ist gegeben durch
Ein beispielhaftes EGS-Netzwerk 1014 ist in den Figuren 17 und 18 gezeigt. Zur Bestimmung der Anzahl von Wegen zwischen dem Eingang x und dem Ausgang y wird berechnet: Wege
Der Kanalgraph L(x,y) des Eingangs x und Ausgangs y ist die Vereinigung aller Wege zwischen x und y. Zur Feststellung einer oberen Grenze für die Anzahl blockierter Wege muß die Anzahl von Gesprächsverbindungen festgestellt werden, die jeden Kanalgraphen kreuzen können, und außerdem die Anzahl von Wegen, die jede Gesprächsverbindung blockieren kann. Der Kanalgraph L(x,y) ist durch ausgezogene Linien in Fig. 19 dargestellt.
In Fig. 20 ist der Kanalgraph L(x,y) durch gestrichelte Linien gezeigt. Eine einzige kreuzende Gesprächsverbindung (dargestellt durch ausgezogene Linien in Fig. 20) blockiert einen der Wege von L(x,y). Es sei eine Gesprächsverbindung betrachtet, die L(x,y) auf j-i Linkleitungen von der Knotenstufe i zur Knotenstufe j (j> i) kreuzt. Eine Linkleitung von der Knotenstufe k zur Knotenstufe k+1 sei als Linkleitung der Stufe k bezeichnet. Die Anzahl von Wegen zwischen dem Eingang x und dem Ausgang y, die durch die Linkleitung i der kreuzenden Gesprächsverbindung C(ij) blockiert wird, ist durch das Produkt aus der Anzahl von Wegen von x zum Knoten der Stufe i für C(ij) und der Anzahl von Wegen von dem Knoten der Stufe i+a für C(ij) zu y gegeben. Die Maximalzahl von Wegen von jedem Eingang (oder Knoten der Stufe 1) zu jedem Knoten der Stufe i ist gegeben durch
und die Maximalzahl von Wegen von jedem Knoten der Stufe i+1 zu jedem Ausgang (oder Knoten der Stufe S) ist gegeben durch
Demgemäß beträgt die Maximalzahl von Wegen zwischen x und y, die durch die Linkleitung i von C(ij) blockiert werden
Die zusätzliche Zahl von Wegen, die durch die Linkleitung i+1 blockiert werden, ist gegeben durch
Die Subtraktion des zweiten Terms korrigiert den Umstand, daß der erste Term Wege enthält, die durch die Linkleitung i blockiert werden, nämlich alle diejenigen Wege, welche die Linkleitung i+1 über die Linkleitung i erreichen. Unter Verwendung einer ähnlichen Korrektur für jede verbleibende Linkleitung von C(ij) ergibt sich, daß die Anzahl der durch C(ij) blockierten Wege gegeben ist durch BLOCKIERTE WEGE (i,j)
Unter Bezugnahme auf das Netzwerk 1012 (Fig. 21) sei das Folgende betrachtet. Da n&sub1; ≤ N und nicht abnehmend in k ist, muß eine Stufe t vorhanden sein, derart, daß für
In ähnlicher Weise muß eine Stufe u vorhanden sein, derart, daß für
Die Beziehung > 1 beinhaltet, daß alle Eingänge wenigstens einen Weg zu jedem Knoten der Stufe t+1 besitzen und daher, daß die kreuzende Gesprächsverbindung C(ij) i≤t+1 besitzt, und entsprechend, weil > 1 ist, j ≥ u - 1 besitzen muß. Unter Verwendung aller dieser Informationen kann festgestellt werden, daß der Ausdruck für blockierte Wege lautet: BLOCKIERTE WEGE (i,j) ≤
wobei konventionell verstanden wird, daß der Summenterm gleich null ist, wenn t+1> u - 2 und der Produktterm gleich eins ist, wenn gilt t + 2 > S. Man beachte, daß eine Funktion des Eintrittspunktes i und
eine Funktion des Austrittspunktes j sind. Außerdem ist
eine Konstante für alle kreuzenden Gesprächsverbindungen. Daher ist die obere Grenze für alle Wege, die durch eine einzige kreuzende Gesprächsverbindung blockiert werden, eine getrennte Funktion des Eintrittspunktes und des Austrittspunktes zuzüglich einer Konstanten.
Es muß jetzt noch die Maximalzahl von Gesprächsverbindungen bestimmt werden, die einen Kanalgraphen kreuzen können. Da die Anzahl von Wegen, die durch eine einzelne kreuzende Gesprächsverbindung blockiert werden können, eine getrennte Funktion des Eintrittspunktes und des Austrittspunktes zuzüglich einer Konstanten ist, muß nur die Maximalzahl von Gesprächsverbindungen bestimmt werden, die in jede Stufe eintreten und aus ihr heraustreten können. Es müssen nicht die Eintritts- und Austrittspunkte einer gegebenen Gesprächsverbindung zugeordnet werden. Es kann jetzt eine wichtige Eigenschaft von EGS-Netzwerken (genannt die Vorwärts-Rückwärts- Invarianzeigenschaft) betrachtet werden, die für jeden Satz von aufeinanderfolgenden Stufen des Netzwerks gilt, die einer bestimmten Bedingung genügen. Wenn die Vorwärts- Rückwärts-Invarianzeigenschaft für bestimmte Teile des Netzwerks gilt, kann die Maximalzahl von in jede Stufe eintretenden und aus ihr austretenden Gesprächsverbindungen drastisch verringert werden.
Die Vorwärts-Rückwärts-Invarianzeigenschaft (FBIP) kann wie folgt angegeben werden: jeder Knoten der Stufe j, der durch einen gegebenen Knoten der Stufe i erreicht werden kann, erreicht genau den gleichen Satz von Knoten der Stufe i. FBIP gilt für die Stufen i und j in einem EGS-Netzwerk, wenn mk rj teilt. Die Wege zwischen bestimmten Knoten der Stufe 3 und 5 für das Netzwerk 1014 sind durch ausgezogene Linien in Fig. 22 dargestellt. Man beachte, daß jeder Knoten der Stufe 5, der durch einen gegebenen Knoten der Stufe 3 erreicht werden kann, genau den gleichen Satz von Knoten der Stufe 3 erreicht. FBIP ist wichtig, da diese Eigenschaft die Zahl der kreuzenden Gesprächsverbindungen drastisch verringert und eine Mehrstufen-Modulausbildung ergibt.
Unter Bezugnahme auf das Netzwerk 1012 in Fig. 23 sei angenommen, daß FBIP für die Stufen 1 bis i gilt, d.h. mp geteilt durch ri. Das heißt, jeder Knoten der Stufe i, der durch einen Eingang x erreicht werden kann, erreicht genau den gleichen Satz von Knoten oder Eingängen der ersten Stufe. Da jeder Knoten der Stufe i höchstens np Eingänge erreichen kann (das Produkt der np Ausgangsverzweigungen von der Stufe i bis zur Stufe 1), können höchstens np -1 Gesprächsverbindungen in den Kanalgraphen L(x,y) von der Stufe 1 bis zur Stufe i (Punkt A in Fig. 23) eintreten. Wenn FBIP für die Stufen i+2 bis S gilt, dann können in ähnlicher Weise höchstens mp -1 Gesprächsverbindungen aus der Stufe i+2 bis Stufe S austreten (Punkt B in Fig. 23). Für den schlechtesten Fall sei angenommen, daß alle Gesprächsverbindungen, die in oder vor der Stufe i eintreten, aus der oder vor der Stufe i+1 austreten und daß alle Gesprächsverbindungen, die aus der oder nach der Stufe i+2 austreten, in die oder nach der Stufe i+1 eintreten. Für ein gegebenes i mit 1 ≤ i ≤ S - 2 ist also die obere Grenze für die Zahl von Gesprächsverbindungen, die einen Kanalgraphen kreuzen, gegeben durch np - 1 + mp -1. Durch Minimieren für i und Beachten, daß höchstens min {N-1, M- 1} Gesprächsverbindungen einen Kanalgraphen kreuzen können, ergibt sich, daß die Maximalzahl ω von Gesprächsverbindungen, die einen Kanalgraphen kreuzen können, gegeben ist durch:
Die Argumente zur Gewinnung dieses Ergebnisses sind gültig, wenn FBIP für alle Stufen 1 bis i gilt, in denen np ≤ ω ist und für alle Stufen j bis S, für die gilt mp ≤ ω.
Bis hierher wurde festgestellt, daß:
(1) wenigstens Wege zwischen jedem Eingangs-Ausgangspaar vorhanden sind,
(2) höchstens
Wege durch eine Gesprächsverbindung blockiert sind, die in einen Kanalgraphen in der Stufe i eintritt und diesen in der Stufe j verläßt,
(3) höchstens ω = np + mp -2, N-1,M-1}
Gesprächsverbindungen einen Kanalgraphen kreuzenu wenn np N teilt für np ≤ ω und mp M teilt für mp ≤ ω. Es verbleibt dann nur noch, die Maximalzahl von Gesprächsverbindungen zu bestimmen, die in jede Stufe des Kanalgraphen eintreten und aus ihr austreten können.
Es sei daran erinnert, daß höchstens np - 1 Gesprächsverbindungen in L(x,y) im Netzwerk 1012 (Fig. 23) am Punkt A von der Stufe 1 über die Stufe i eintreten können. Außerdem können höchstens ω Gesprächsverbindungen von der Stufe 1 über die Stufe i eintreten. Außerdem sei daran erinnert, daß höchstens mp - 1 Gesprächsverbindungen aus L(x,y) vom Punkt B des Netzwerks 1012 von der Stufe i+2 über die Stufe S austreten können. Ebenso können höchstens ω Gesprächsverbindungen aus der Stufe i+2 über die Stufe S austreten. Demgemäß können min { np - 1, ω} Gesprächsverbindungen von der Stufe 1 über die Stufe i und
min { np - 1, ω} Gesprächsverbindungen von der Stufe 1 über die Stufe i-1 eintreten. Nimmt man eine Maximalzahl von Gesprächsverbindungen an, die über die Stufe i-1 eintreten, so ergeben sich höchstens
min { np - 1, ω} - min np - 1, ω) Gesprächsverbindungenu die in der Stufe i eintreten.
Entsprechend sind höchstens
min { mp -1, ω}-min{ mp -1, ω} Gesprächsverbindungen vorhanden, die in der Stufe i austreten. Jetzt kann die Grundbedingung für streng nicht blockierende EGS-Netzwerke definiert werden:
wobei die Minimalzahl von Wegen zwischen jedem Eingangs- Ausgangspaar ist,
min { np - 1, ω} - { np - 1, ω} die Maximalzahl von eintretenden Gesprächsverbindungen bei der Stufe i ist,
die Anzahl von Wegen ist, die durch eintretende Gesprächsverbindungen bei der Stufe i blockiert werden,
min { mp - 1, ω} - min { mp - 1, ω} die Maximalzahl von austretenden Gesprächsverbindungen bei der Stufe i ist,
die Zahl der Wege ist, die durch die bei der Stufe i austretende Gesprächsverbindung blockiert werden,
ω die Maximalzahl von kreuzenden Gesprächsverbindungen ist und eine konstante
Komponente blockierter Wege für alle kreuzenden Gesprächsverbindungen ist.
Dies kann dann als grundlegendes Theorem für streng nicht blockierende EGS- Netzwerke festgestellt werden: Jedes EGS-Netzwerk, das N=n&sub1;r&sub1; Eingänge und M=msrs Ausgänge besitzt, bei dem
np N teilt für np ≤ ω und mp M teilt für mp ≤ ω und bei dem
gilt, wobei t der größte Wert für i ist, derart, daß np≤N gilt, u der kleinste Wert für i ist, derart, daß mp≤M gilt, und
ist streng nicht blockierend für Punkt-zu-Punkt-Verbindungen.
Die vorstehende Ableitung hat Knoten voller Kapazität (Kapazität = min {nimi}) angenommen. Ähnliche Ableitungen lassen sich für Knoten der Kapazität eins mit Auswahlmöglichkeit und für Knoten der Kapazität 1 ohne Auswahlmöglichkeit durchhführen. Getrennte Ergebnisse werden zusammengeführt durch die Einführung einer Variablen α, wobei α=1 für Knoten voller Kapazität ist, α=0 für Knoten der Kapazität eins mit Auswahlmöglichkeit und α=-1 für Knoten der Kapazität eins ohne Auswahlmöglichkeit. Das grundlegende Theorem für streng nicht blockierendes EGS-Netzwerke läßt sich dann wie folgt angeben:
Jedes EGS-Netzwerk (bei dem α=1 für Knoten voller Kapazität ist, α=0 für Knoten der Kapazität eins mit Auswahlmöglichkeit und α=-1 für Knoten der Kapazität eins ohne Auswahlmöglichkeit}, das N=n&sub1;r&sub1; Eingänge und M=msrs Ausgänge besitzt, bei dem np N teilt für np ≤ ω und mp M teilt für mp ≤ ω
und bei dem
wobei t der größte Wert von i ist, derart, daß np ≤N gilt, u der kleinste Wert für i ist, derart, daß mp≤M gilt, und
ist streng nicht blockierend für Punkt-zu-Punkt-Verbindungen.
Die große Konstruktionsflexibilität von EGS-Netzwerken beruht in erster Linie auf der Tatsache, daß die Bedingungen für einen nicht blockierenden Betrieb global sind und allein auf N, M, α und verschiedene ni- und mi-produkten beruhen. Im allgemeinen hängen die Nichtblockierungsbedingungen nicht von der Beziehung zwischen einem bestimmten ni und mi ab.
Ein Beispiel für ein nicht blockierendes EGS-Netzwerk 1016 ist in Fig. 24 gezeigt. Wenn die Ausgangs-Linkleitungen in jeder Stufe dieses Netzwerks nacheinander den Knoten in der nächsten Stufe zugeordnet sind (perfekte Umordnung), dann kann jeder freie Eingang mit einem freien Ausgang unabhängig vom augenblicklichen Verbindungszustand des Netzwerks verbunden werden, d.h., das Netzwerk ist streng nicht blockierend.
Ein vielstufiges Verbindungsnetzwerk (MIN)G wird als Netzwerk mit perfekter Umordnung bezeichnet, wenn eine der folgenden zwei Bedingungen gilt:

Bedingung 1:

Für jede Stufe i von G existiert eine 1:1-Abbildung φi von den ri Knoten der Stufe i von G auf den Satz von ganzen Zahlen {0, 1,...,ri-1}, derart, daß der Knoten α in der Stufe i von G mit dem Knoten β in der Stufe i+1 von G verbunden ist, wenn, und nur wenn gilt

Bedingung 2:

Für jede Stufe i von G existiert eine 1:1-Abbildung ψi von den ri Knoten der Stufe i von G auf den Satz von ganzen Zahlen {0,1,...,ri-1), derart, daß der Knoten β in der Stufe i+1 von G mit dem Knoten α in der Stufe i von G verbunden ist, wenn, und nur wenn gilt
Man beachte, daß ein EGS-Netzwerk ein Netzwerk mit perfekter Umordnung ist, weil die Bedingung 1 gilt, wenn jedes φi einfach die Identitätsabbildung ist.
Es möge Ci = {φi:i&epsi; (1,2,...,S)} einen Satz von S Abbildungen φi darstellen, die der Bedingung 1 genügen, und C&sub2; = {ψi:i&epsi; (1,2,...,S)} einen Satz von S Abbildungen, die der Bedingung 2 genügen.
Man sagt, daß eine Expandiereinrichtung jeden der N Eingänge von G mit mehreren Eingängen der Knoten der ersten Stufe von G mit einem Muster unter Aufrechterhaltung einer perfekten Umordnung verbindet, wenn eine der folgenden zwei Bedingungen gilt.

Bedingung 1e:

C&sub1; ist vorhanden, n&sub1;r&sub1;/N = F, eine ganze Zahl, und es existiert eine 1:1-Abbildung φ&sub1; von N Eingängen von G auf den Satz von ganzen Zahlen {0,1,...,N-1}, derart, daß der Eingang α mit dem Knoten β in der Stufe 1 von G verbunden ist, wenn, und nur wenn gilt

Bedingung 2e:

C&sub2; ist vorhanden, n&sub1;r&sub1;/N = F, eine ganze Zahl, und es existiert eine 1:1-Abbildung ψ&sub1; von N Eingängen von G auf den Satz von ganzen Zahlen {0,1,...,N-1}, derart, daß der Knoten β in der Stufe 1 von G mit dem Eingang α von G verbunden ist, wenn, und nur wenn gilt
Man sagt, daß eine Konzentriereinrichtung mehrere Ausgänge der letzten Stufe S von Knoten von G mit jedem der M Ausgänge von G in einem Muster unter Aufrechterhalter perfekter Umordnung verbindet, wenn eine der beiden Bedingungen gilt.

Bedingungen 1c:

C&sub1; ist vorhanden, nSrS/M = F', eine ganze Zahl, und es existiert eine 1:1- Abbildung φ&sub0; von den M Ausgängen von G auf den Satz von ganzen Zahlen {0,1,...,M-1}, derart, daß der Knoten in der Stufe S von G mit dem Ausgang β verbunden ist, wenn, und nur wenn gilt

Bedingung 2c:

C&sub2; ist vorhanden, nSrS/M = F', eine ganze Zahl, und es existiert eine 1:1--
Abbildung ψ&sub0; von den M Ausgängen von G auf den Satz von ganzen Zahlen {0,1,...,M-1}, derart, daß der Ausgang β mit dem Knoten α in der Stufe S von G verbunden ist, wenn, und nur wenn gilt
Das Netzwerk G mit einer solchen Expansions- und Konzentrationseinrichtung kann äquivalent dargestellt werden, als ein S+2-stufiges Netzwerk mit perfekter Umordnung, das eine Expansionsstufe mit N 1xF Knoten umfaßt, gefolgt von den S Stufen von G, gefolgt von einer Konzentrationsstufe mit M F'x1 Knoten. Wenn die Bedingung 1 (2) gilt, wird φ&sub1; (ψ&sub1;) auf die N Eingangsknoten angewendet, und der Eingangsknoten α ist mit dem Knoten β in der Stufe 1 von G gemäß Bedingung 1e (2e) verbunden, und φ&sub0; (ψ&sub0;) wird auf die M Ausgangsknoten angewendet und der Knoten α in der Stufe S von G ist mit dem Ausgangsknoten β gemäß Bedingung 1c (2c) verbunden.
Das Überkreuzungsnetzwerk 1020 in Fig. 25 ist ein Netzwerk mit perfekter Umordnung. Dies läßt sich leicht bestätigen, indem man die Bezeichnung der Knoten in jeder Stufe und die Verbindung zwischen den Stufen prüft. Das Vorhandensein solcher regelmäßigen, physikalischen Verbindungsmuster von Netzwerken mit perfekter Umordnung ist wichtig für Konstruktionsüberlegungen.
In einem Überkreuzungsnetzwerk mit 2k,2x2 Knoten je Stufe wird jede Verbindungsleitungsstufe i aus einem Überkreuzungs-Verbindungsmuster mit 2ri Unterteilungen gebildet, wobei gilt r&sub1; &epsi; I(k) = {0,1,...,k-1). Die gewählten Werte für die verschiedenen r&sub1; beeinflussen in hohem Maß die Güte und die Verbindungsmöglichkeiten des Netzwerks.
Ein sehr brauchbares Muster für die ri-Auswahl (das zu einem Netzwerk mit perfekter Umordnung führt) besteht darin, daß r&sub1;,r&sub2; ... rk durch eine Permutation von 1(k) für i≥k, ri = rj gegeben ist, wobei j = 1 + (i-1)modk, d.h., rk+1 = r&sub1;,rk+2 = r&sub2; ... r2k = rk usw. Viele weitere brauchbare Muster sind vorhanden, die Netzwerken entsprechen, welche nicht zu der Familie von Netzwerken mit perfekter Umordnung gehören.
Das EGS-Netzwerk 1022 in Fig. 26 stellt einen wichtigen Sonderfall eines Netzwerks mit perfekter Umordnung dar. Für das Netzwerk 1022 gilt
S≥3, n&sub1; = 1, m&sub1; = F, r'1 = N, ns = F, Ms = 1, rs = N und für
2≤i≤S-1, ni = mi = n, und ri = FN/n.
ES SEI:
P(B) = Wahrscheinlichkeit, daß ein gegebener freier Eingang und Ausgang nicht verbunden werden können (blockiert);
P(F) = Wahrscheinlichkeitu daß ein gegebener nxn-Knoten in den Stufen 2 bis 2-1 aufgrund eines Fehlers nicht benutzbar ist;
OCC = Wahrscheinlichkeit, daß ein gegebener Eingang oder Ausgang besetzt ist;
α = 0 für nxn-Knoten der Kapazität eins (mit Auswahlmöglichkeit);
α = 1 für nxn-Knoten voller Kapazität.
DANN GILT:
N,F,N,S,P(B),OCC und α stehen annähernd in Beziehung durch
Für3 ≤ S ≤ 2 logα N+1-α
ES SEI:
Ps(B) = P(B) für ein Netzwerk mit S Stufen
DANN GILT:
Ps+1(B) und P&sub3; (B) stehen annähernd in Beziehung durch dann ist der Exponent größer als eins und Ps(B) nimmt doppelt exponentiell ins ab, d.h.,
aufgetragen über S ist eine gerade Linie. Um diese starke Auswirkung zu demonstrieren sei angenommen Ps(B) = 10&supmin;¹ und Ps+1(B) = [PS(B)]².
Dann gilt PS+1 = (10&supmin;¹)² = 10&supmin;², PS+2(B) = [10&supmin;²]² = 10&supmin;&sup4;, PS+3(B) = [10&supmin;&sup4;]² = 10&supmin;&sup8;, PS+4(B) = [10&supmin;&sup8;]² = 10&supmin;¹&sup6;, usw. In einem solchen Netzwerk ist also die Blockierwahrscheinlichkeit von 10&supmin;¹ auf 10&supmin;¹&sup6; durch einfaches Hinzufügen von vier stufen verringert worden.
Der obige angenäherte Ausdruck für die Blockierwahrscheinlichkeit kann für jedes Netzwerk G mit perfekter Umordnung und 5 Knotenstufen verallgemeinert werden, wobei die Stufe i nixmi Knoten aufweist mit N=n&sub1;r&sub1; Eingängen und M=rsms. Ausgängen. Setzt man P(F)=0, OCC=1 und α=1, so erhält man die Blockierwahrscheinlichkeit in G, P(G) annähernd zu
P(G) ≤ 0,5 ist ein konservativer Schwellenwert für das Netzwerk G, der für Anwendungsfälle brauchbar ist, bei denen die Blockierwahrscheinlichkeit überhaupt von Bedeutung ist.

Netzwerk-Steuerung

Es sei daran erinnert, daß das in Fig. 16 gezeigte Netzwerk 1012 ein EGS- Netzwerk mit einem Verbindungsmuster ist, das Linkleitungen nacheinander mit Kopplern in der nächsten Stufe verbindet - eine Verbindung perfekter Umordnung. Die Anzahl P von Wegen zwischen jedem Eingang x und jedem Ausgang y im Netzwerk 1012 ist gegeben durch
l(k) bezeichne den Satz von ganzen Zahlen (0,1, ... k-1}. Ein gegebener Weg vom Eingang x zum Ausgang y sei durch das Triple (x,P*,y) bezeichnet, wobei P* ein Element von I(P) ist. Der Weg (x,P*,y) verläuft über den Koppler
der Stufe i für 1 ≤ i ≤ S. Eine Linkleitung zwischen den Stufen i und i+1 sei als Linkleitung der Stufe i bezeichnet. Der Weg (x,P*,y) benutzt si Stufe i-Linkleitung
Fig. 27 zeigt ein Wegfreiwahl-Verarbeitungsflußdiagramm zur Durchführung der Wegfreiwahlfunktion im Netzwerk 1012, bei dem die Koppler volle Kapazität haben, d.h., cap(Si) = min{nimi}. Die Verarbeitung beginnt mit dem Block 1102, bei dem ein vorher nicht geprüfter Weg P* gewählt wird. Gemäß Block 1104 wird der Besetztifreizustand von Li(x,P*,y) für alle i geprüft mit 1 ≤ i ≤ S-1. Gemäß Entscheidungsblock 1106 wird festgestellt, ob alle Li(x,P*,y) frei sind. Wenn dies der Fall ist, geht die Verarbeitung weiter vom Block 1106 zum Block 1108, bei dem davon ausgegangen wird, daß der Weg P* zur Verbindung des Eingangs x mit dem Ausgang y benutzt werden kann. Wenn beim Block 1106 festgestellt wird, daß alle Li(x,P*,y) nicht frei sind, geht die Verarbeitung weiter zum Entscheidungsblock 1110. Dort wird festgestellt, ob andere, ungeprüfte Wege vorhanden sind. Wenn dies der Fall ist, kehrt die Verarbeitung zum Block 1102 zurück und das Flußdiagramm wird für einen neuen ungeprüften Weg wiederholt. Wenn jedoch beim Entscheidungsblock 1110 festgestellt wird, daß keine weiteren ungeprüften Wege vorhanden sind, zweigt die Verarbeitung zum Block 1112 ab, bei dem davon ausgegangen wird, daß alle Wege zwischen dem Eingang x und dem Ausgang y blockiert sind. Die Linkleitungen Li werden beim Flußdiagramm gemäß Fig. C1 geprüft, da angenommen worden ist, daß die Koppler des Netzwerks 1012 volle Kapazität haben.
Fig. 28 zeigt ein Wegfreiwahl-Verarbeitungsflußdiagramm zur Ausführung der Wegfreiwahlfunktion im Netzwerk 1012, bei dem die Koppler die Kapazität eins haben, d.h., cap(Si) = 1. Die Verarbeitung beginnt beim Block 1122, bei dem ein vorher ungeprüfter Weg P* gewählt wird. Beim Block 1124 wird der Besetzt/Freizustand von Si(x,P*,y) für alle geprüft mit 1 ≤ i ≤ S. Beim Entscheidungsblock 1126 wird festgestellt, ob alle Si(x,P*,y) frei sind. Wenn dies der Fall ist, geht die Verarbeitung weiter vom Block 1126 zum Block 1128. Dort wird davon ausgegangen, daß der Weg P* zur Verbindung des Eingangs x mit dem Ausgang y benutzt werden kann. Wenn beim Block 1126 festgestellt wird, daß alle Si(x,p*,y) nicht frei sind, geht die Verarbeitung weiter zum Entscheidungsblock 1130. Dort wird festgestellt, ob weitere, ungeprüfte Wege vorhanden sind. Wenn dies der Fall ist, kehrt die Verarbeitung zurück zum Block 1122 und das Flußdiagramm wird für einen neuen, ungeprüften Weg wiederholt. Wenn jedoch beim Entscheidungsblock 1130 festgestellt wird, daß keine weiteren ungeprüften Wege vorhanden sind, läuft die Verarbeitung zum Block 1132. Dort wird davon alisgegangen, daß alle Wege zwischen dem Eingang x und dem Ausgang y blockiert sind. Die Koppler Si werden beim Flußdiagramm gemäß Fig. 28 geprüft, da für die Koppler des Netzwerks 1012 angenommen worden ist, daß sie die Kapazität eins haben.
Es ist wichtig zu beachten, daß bei der Durchführung der Wegfreiwahl für das Netzwerk 1012 parallele Operationen möglich sind. Alle Si(x,P*,y)- oder Li(x,P*,y)- Besetzt/Frei-Zustände für alle i und P* können gleichzeitig gelesen werden und dann können alle P Wege gleichzeitig als besetzt oder frei festgestellt werden. Aus diesen, als frei festgestellten Wegen wird, wenn ein solcher vorhanden ist, ein bestimmter Weg ausgewählt.
Wenn das betrachtete Netzwerk kein EGS-Netzwerk sondern eine isomorphe Abwandlung eines EGS-Netzwerkes ist, müssen der Eingang x und der Ausgang y auf ihre EGS-äquivalente Voranwendung der Wegführungsalgorithmen abgebildet werden. Eine umgekehrte Abbildung ist für den Betrieb der Koppler erforderlich.
Eine überlappende Operation kann für eine Vielzahl von herzustellenden Verbindungen durchgeführt werden, wenn alle Wege für jedes Eingangslausgangspaar unabhängig von allen Wegen für jedes andere Eingangslausgangspaar sind.
Zur Vereinfachung wird gesetzt
Wenn M M&sub1; teilt, so werden die oben für P, Si(x,P*,y) und Li(x,P*,y) gegebenen Gleichungen zu
Es sei ein Netzwerk G betrachtet, bei dem gilt
N = M 2n, n&sub1; = ms = 1, m&sub1; = ns = 2k = F und, für 2 ≤ i ≤ (S-1, n&sub1; = m&sub1; = 2, wobei n und k ganze Zahlen sind. Dann werden
Außerdem gilt
Außerdem ist Mi = 2S-i für 2 ≤ i ≤ S.
Der Ausdruck xM&sub1; + P*M + y wird demgemäß x2S+k-1 + P*2n + y, die Werte x und y erstrecken sich über die ganzzahligen Werte 0, 1 ... 2n-1 und P* erstreckt sich über die ganzzahligen Werte 0, 1 ... 2S+k-n-2-1. Demgemäß besitzt P*2n Werte 0, 2n, 2 2n, 3 2n ... 2S+k-2-2n und P*2n + y erstreckt sich über alle ganzzahligen Werte von 0 bis 2²S+k-2-1. Außerdem besitzt x 2S+k-2 Werte 0, 2S+k-2 ... 12S 2S+k+n-2-22S+k-2, so daß x2S+k-2 + p*2n + y erstreckt sich über alle ganzzahligen Werte von 0 bis 2S+k+n-2-1.
Man kann demgemäß xM&sub1; + P*M + y = x2S+k-2 + P*2n + y wie folgt als Binärzahl mit S + k + n -2 Bits
Es sei der Ausdruck betrachtet
Das Dividieren einer Binärzahl durch 2S-i und Aufnehmen der Grundfunktion entspricht einer Verschiebung der Binärzahl um S-1 Plätze nach rechts.
Demgemäß ist
äquivalent der Binärzahl, die in dem folgenden Rechteck angegeben ist:
Eine Binärzahl modulo 2n+k-1 wird durch die am weitesten rechts stehenden n+k-1 Bits der Binärzahl angegeben.
Demgemäß ist
äquivalent der Binärzahl, die in dem nachfolgenden Rechteck angegeben ist:
Si(x,P*,y) ist demgemäß gegeben durch ein Fenster von log&sub2; ri Bits, die um log&sub2; Mi Bits von rechts bei der Binärdarstellung von xM&sub1; + P*M + y verschoben sind. Entsprechend wird Li(x,P*,y) dargestellt durch ein Fenster von log&sub2;(rimi) Bits, die um log&sub2; Mi+1 Bits von rechts für die Binärdarstellung von xM&sub1; + P*M + y verschoben sind.
Die Beziehungen der Koppler und Linkleitungen eines Umordnungsnetzwerkes zu den Eingangs/Ausgangs- und Wegnummern wird hier für das beispielhafte Netzwerk 1140 gemäß Fig. 29 beschrieben. Fig. 30 zeigt die Verknüpfung der Binärdarstellungen für den Eingang 137, den Weg 417 und den Ausgang 291 unter Bildung einer einzigen Binärzahl Fig. 31 zeigt, daß die Festlegung eines bestimmten Kopplers in einer gegebenen Stufe einfach dadurch erfolgen kann, daß eine bestimmte Anzahl aufeinanderfolgender Bits in der Binärzahl gewählt wird. Die speziellen 11-Bit-Folgen, die zur Identifizierung der Koppler der Stufe 2 und der Koppler der Stufe 16 benutzt werden, sind in Fig. 31 dargestellt. In ähnlicher Weise sind die 12-Bit-Folgen zur Identifizierung der speziellen Linkleitungen in der Stufe 2 und 16 gezeigt. Die 11-Bit-Folgen identifizieren einen Koppler von 2048 Kopplern. Die 12-Bit-Folgen identifizieren eine Linkleitung von 4096 Linkleitungen. In Fig. 31 ist außerdem das Verfahren zur Identifizierung der speziellen Eingänge und Ausgänge der verschiedenen Stufen dargestellt, und zwar auf der Grundlage des oder der Bits, die den Biffolgen benachbart sind, welche zur Identifizierung der Koppler und Linkleitungen benutzt werden. Beispielsweise sind die Eingänge der Stufen 2 und 16 und die Ausgänge der Stufen 1, 2 und 16 identifiziert. Man beachte, daß für das Netzwerk 1140 die Ausgangswegführung "selbstwegführend" ist, und zwar unabhängig vom Eingang.
Es sei daran erinnert, daß das Überkreuzungsnetzwerk und das Umordnungsnetzwerk isomorph sind. Die Transformationen zwischen verschiedenen Stufen der beiden Netzwerktypen sind schematisch in Fig. 32 dargestellt. Die speziellen, in Fig. 32 angegebenen Transformationen sind in den Tabellen 1-3 aufgelistet. In Fig. 32 stehen der im Block 1150 angegebene Koppler und Ausgang der Stufe i eines Überkreuzungsnetzwerks zu dem im Block 1154 angegebenen Koppler und Ausgang der Stufe i eines Umordnungsnetzwerks durch die Transformationen 1, 2, 3 und 4 gemäß Block 1152 in Beziehung. Entsprechend stehen der im Block 1160 angegebene Koppler und Eingang für die Stufe i+1 eines Überkreuzungsnetzwerks und der im Block 1164 angegebene Koppler und Eingang für die Stufe i+1 eines Umordnungsnetzwerks durch die Transformationen 9, 10, 11 und 12 gemäß Block 1162 in Beziehung. Die Transformationen zwischen der Koppler- und Ausgangsnummer der Stufe i für ein Überkreuzungsnetzwerk und der Koppler- und Eingangsnummer der Stufe i+1 für ein Überkreuzungsnetzwerk sind durch die Transformationen 13, 14, 15 und 16 gemäß Block 1156 dargestellt. Die entsprechenden Beziehungen zwischen den aufeinanderfolgenden Stufen eines Umordnungsnetzwerks sind durch die Transformationen 5, 6, 7 und 8 gemäß Block 1158 angegeben. Die Transformationen 1 bis 16 sind in den Tabellen 1 bis 3 aufgelistet. Für jede Transformation ist die zu transformierende Zahl eine n-Bit-Binärzahl, die dargestellt wird durch Bn-1 ... B&sub1;B&sub0;. Tabelle 1 Tabelle 2 Tabelle 3
Es werden jetzt Anordnungen zur Steuerung eines 512x512- Überkreuzungsnetzwerks 1200 (Fig. 38) beschrieben. Um ein besseres Verständnis für die Größe eines solchen Netzwerks zu erlangen, wird zunächst auf das 16x16- Überkreuzungsnetzwerk 1170 (Fig. 34-36) Bezug genommen und auf das Muster der Überkreuzungsverbindungen von Stufe zu Stufe verwiesen. Fig. 37 enthält eine Darstellung für die relative Größe des 16x16-Netzwerks 1170 und des 512x512-Netzwerks 1200. Außerdem ist als mittlere Größe ein 128x128-Netzwerk dargestellt. Das Überkreuzungsnetzwerk 1200 (Fig. 38) enthält 15 Stufen. Die Stufen 1, 2, 3, 13, 14 und 15 führen jedoch keine Vermittlungsfunktion aus. Sie werden lediglich zur Verwirklichung der Ausgang/Eingangsverzweigung F=8 benutzt. Ein Überkreuzungsnetzwerk-Steuergerät 1300 führt die Wegfreiwahl und die Verbindungs- und Trennfunktionen für das Netzwerk 1200 über eine Vielzahl von Stufensteuergeräten 1201 bis 1209 durch, die den Stufen 4 bis 12 individuell zugeordnet sind. Für das vorliegende Beispiel sind die Knoten der Vermittlungsstufen 4 bis 12 Vermittlungsknoten voller Kapazität wie der Knoten gemäß Fig. 5. Die Knoten der Ausgangsverzweigungsstufen 1, 2 und 3 sowie die Knoten der Eingangsverzweigungsstufen 13, 14 und 15 sind einfache Ausgangsverzweigungs- bzw. Eingangsverzweigungselemente. Das Überkreuzungsnetzwerk-Steuergerät 1300, das als einzelner, unter Programmsteuerung betriebener Prozessor oder als Hardware- Logikschaltungsanordnung verwirklicht werden kann, führt die beispielsweise in den Fig. 39 und 40 dargestellte Steuerverarbeitung aus, um Verbindungen bzw. Trennungen auszuführen.
Die Verbindungsverarbeitung (Fig. 39) beginnt, wenn ein Eingangs/Ausgangspaar des Netzwerks 1200 für eine gegebene Verbindungsanforderung in einer Warteschlange im Block 1402 gespeichert wird. Wenn das gespeicherte Eingangs/Ausgangspaar verarbeitet werden soll, erfolgt eine Umwandlung der Eingangsund Ausgangsnummern im Block 1404 in die entsprechenden Eingangs- und Ausgangsnummern des Umordnungsnetzwerks, das topologisch dem Netzwerk 1200 äquivalent ist. Im Block 1406 erfolgt dann eine Unabhängigkeitswegprüfung unter Verwendung von später hier beschriebenen Prozeduren, um Testzustellen, ob einer der möglichen Wege für diese Verbindungsanforderung einen der möglichen Wege für weitere, gleichzeitig verarbeitete Verbindungsanforderungen kreuzt. Wenn kein Konflikt mit anderen, im Aufbau befindlichen Verbindungen vorhanden ist, geht die Ausführung weiter zum Block 1408, bei dem die Koppler oder Linkleitungen, die allen Wegen vom Eingang zum Ausgang des äquivalenten Umordnungsnetzwerks zugeordnet sind, bestimmt werden. Da im Netzwerk 1200 die Koppler (oder Knoten) Koppler voller Kapazität sind, reicht es aus, die Linkleitungen eines gegebenen Weges über das Netzwerk zu bestimmen. Wenn die Netzwerkkoppler Koppler der Kapazität eins sind, reicht es aus, die Koppler eines gegebenen Weges über das Netzwerk zu bestimmen. Nachdem die Wegkomponenten aller Wege bestimmt sind, wird gemäß Block 1410 ein freier Weg identifiziert, falls ein solcher freier Weg vorhanden ist. Wenn ein freier Weg gefunden ist, wird gemäß Block 1412 ein Wegspeicher aktualisiert, um den freien Weg unter Verwendung der Eingangs-, Ausgangs- und Wegnummern für das äquivalente Umordnungsnetzwerk zu definieren. Gemäß Block 1414 werden Verbindungsbefehle zu den Netzwerk-Stufensteuergeräten 1201 bis 1209 übertragen. Außerdem werden die Wegkomponenten (Koppler oder Linkleitungen) für den identifizierten Weg gemäß Block 1416 für alle Stufen als besetzt markiert.
Es sei zum Block 1406 zurückgekehrt. Wenn festgestellt wird, daß die gegebene Verbindungsanforderung sich in Konflikt mit anderenu gerade verarbeiteten Verbindungsanforderungen befindet, so werden Informationen betreffend die gegebene Verbindungsanforderung in einer Warteschlange im Block 1420 gespeichert. Nachdem gemäß Block 1410 ein freier Weg für eine der anderen Verbindungsanforderungen gefunden ist, wird ein Bericht zur Warteschlange des Blocks 1420 gegeben. Die Wegunabhängigkeitsprüfung gemäß Block 1406 wird dann wiederholt. Wenn gemäß Block 1410 kein freier Weg für eine Verbindungsanforderung gefunden wird, werden die Blöcke 1422 und 1424 ausgeführt. Gemäß Block 1422 wird ein Bericht an die Warteschlange des Blocks 1420 gegeben, daß die Verbindungsverarbeitung beendet ist. Gemäß Block 1424 wird ein Blockierfehlerbericht an die Warteschlange im Block 1402 gegeben, derart, daß die nicht erfolgreiche Verbindungsanforderung später wieder verarbeitet werden kann.
Die Trennverarbeitung (Fig. 40) beginnt, wenn ein Eingang des Netzwerks 1200 für eine gegebene Trennanforderung in einer Warteschlange im Block 1440 gespeichert wird. Wenn der gespeicherte Eingang verarbeitet werden SOIIV erfolgt eine Umwandlung der Eingangsnummer gemäß Block 1422 in die entsprechende Eingangsnummer des Umordnungsnetzwerks, das dem Netzwerk 1200 topologisch äquivalent ist. Gemäß Block Wegspeichers benutzt, um die Ausgangs- und Wegnummer des Umordnungsnetzwerks für die Verbindung zu bestimmen. Gemäß Block 1448 werden Trennbefehle zu den Netzwerkstufen-Steuergeräten 1201 bis 1209 übertragen. Weiterhin werden die Wegkomponenten (Koppler oder Linkleitungen) für den aufgetrennten Weg wiederum für alle Stufen als frei markiert.
Ein Hardware-Ausführungsbeispiel für das Netzwerk-Steuergerät 1300 ist in den Fig. 42-44 dargestellt. Verbindungsanforderungenu die ein bestimmtes Eingangslausgangspaar des Netzwerks 1200 angeben, werden in einer Verbindungsanforderungs-Warteschlange 1302 gespeichert. Die 9-Bit- Überkreuzungseingangsnummer und die 9-Bit-Überkreuzungsausgangsnummer werden zu einer Überkreuzungs-auf-Umordnungs-Abbildungseinheit 1304 (Fig. 50) zur Umwandlung in die entsprechende 9-Bit-Umordnungseingangsnummer und die entsprechende 9-Bit- Umordnungsausgangsnummer übertragen. Die Umordnungseingangs- und -ausgangsnummern werden in einer Verbindungs/Trenn-Anforderungswarteschlange 1305 gespeichert und dann zu einer Wegunabhängigkeits-Prüfeinheit 1306 (Fig. 46) übertragen. Die Einheit 1306 stellt fest, ob das augenblickliche Eingangslausgangsnummernpaar Wege über das Netzwerk 1200 definiert, die bezüglich der Linkleitungen unabhängig von den Wegen sind, die einem anderen Eingangs/Ausgangsnummernpaar zugeordnet sind. Wenn zwei oder mehr Verbindungsanforderungen unabhängige Wege über das Netzwerk 1200 definieren, können mehrere Verbindungsanforderungen und Wegfreiwahlvorgänge gleichzeitig in einer Betriebsweise verarbeitet werden, die hier als Überlappungsbetriebsweise bezeichnet wird. Die Umordnungs- Eingangs/Ausgangsnummern werden dann in einer Verbindungs/Trennanforderungs- Warteschlange 1308 gespeichert. Wenn eine Wegfreiwahl auszuführen ist, überträgt die Verbindungsanforderungs-Warteschlange 1308 ein Leseanforderungssignal an eine Vielzahl von Speichern 1312, die die Linkleitungs-Besetzt/Freibits für eine entsprechende Stufe der Linkleitungsstufen 4 bis 11 des Netzwerks 1200 speichern. (Die Linkleitungsstufe ist die Stufe von Linkleitungen zwischen der Knotenstufe i und der Knotenstufe i+1.) Die 9- Bit-Umordnungs-Eingangs- und Ausgangssignale werden außerdem parallel von der Verbindungsanforderungs-Warteschlange 1308 übertragen, und vorbestimmte Eingangs- und Ausgangssignale werden zur Adressierung von Stellen der Speicher 1312 benutzt.
Man beachte, daß im Netzwerk 1200 jedem angegebenen Eingangs/Ausgangspaar acht Wege zugeordnet sind. Jeder Speicher 1312 besitzt 512 Speicherstellen mit je 8 Bits. Jede der 512 Speicherstellen eines gegebenen Speichers 1312 entspricht einem unterschiedlichen Wert der vorbestimmten 9 Bits, die aus der Binärzahl entnommen worden sind, welche durch Verknüpfen der Eingangsnummer, der Wegnummer und der Ausgangsnummer gemäß Fig. 30 gebildet worden ist. Es wird jedoch keines der Wegnummernbits für irgendeine Stufe entnommen. Als Ergebnis definiert ein Speicher 1312 den Besetztifreizustand einer Linkleitungsstufe für jeden der acht Wege, die einem gegebenen Eingangslausgangsnummernpaar zugeordnet sind. Alle 8 Bits der adressierten Stellen des Speichers 1312 werden gelesen und gleichzeitig durch eine Vielzahl von Weg-Besetzt/Frei-Prüfeinheiten 1314 kombiniert, die beispielsweise in Form von ODER-Gattern mit mehreren Eingängen verwirklicht sind. Eine der Wegprüfeinheiten 1314 überträgt ein Freisignal, wenn alle ihre Eingangssignale einen Freizustand für Linkleitungen angeben. Eine Freiweg-Auswahleinheit 1316 (Fig. 51) nimmt die Besetzt/Freisignale von jeder Einheit 1314 auf und wählt auf vorbestimmte Weise einen der definierten freien Wege. Die Freiweg-Auswahleinheit 1316 überträgt dann die Binärzahl, die dem einen der acht gewählten Wege entspricht. Die Einheit 1316 überträgt außerdem eine Wegblockieranzeige, wenn kein Weg gefunden wird. Die Wegblockieranzeige wird zur Verbindungsanforderungs-Warteschlange 1302 zurück übertragen, so daß die Verbindungsanforderung später wiederholt werden kann. Der Kehrwert der Wegblockieranzeige wird als Schreibanforderungssignal benutzt, um ein Besetztbit in jeden der Speicher 1312 einzuschreiben. Die Freiwegnummer wird zu den speichern 1312 gegeben, um zusätzlich den speziellen Weg und damit das spezielle Bit derjenigen Speicherstelle zu identifizieren, die durch die Eingangs- und Ausgangsnummer adressiert wird. Außerdem wird ein Wegspeicher 1318 unter Ansprechen auf die Schreibanforderung aktualisiert und speichert an einer durch die Umordnungs-Eingangsnummer definierten Adresse sowohl die Umordnungs-Ausgangsnummer als auch die Wegnummer des gewählten freien Weges.
Eine Trennanforderungs-Warteschlange 1320 führt Trennungen aus, indem sie den zu trennenden Überkreuzungseingang zur Überkreuzungs-auf-Umordnungs- Abbildungseinheit 1304 für eine Umwandlung in den entsprechenden Umordnungseingang überträgt. Der Umordnungseingang wird dann zur Adressierung des Wegspeichers 1318 benutzt. Die Trennanforderungs-Warteschlange 1320 überträgt ein Leseanforderungssignal zum Wegspeicher 1318 und liest den Umordnungsausgangu der an derjenigen Stelle des Wegspeichers 1318 abgelegt ist, welcher durch die Umordnungseingangsadresse definiert wird. Der gelesene Umordnungsausgang wird dann zusammen mit dem Umordnungseingang über die Warteschlange 1305V die Wegunabhängigkeits-Prüfeinheit 1306 und die Warteschlange 1308 zu den Adressenspeichern 1312 übertragen. Die adressierte Speicherstelle des Wegspeichers 1318 enthält außerdem die Wegnummer des zu trennenden Weges. Die gelesene Wegnummer wird parallel zu jedem Speicher 1312 übertragen, um zusätzlich das spezielle Bit anzugeben, das in den Freizustand zurückzusetzen ist. Danach überträgt die Trennanforderungs-Warteschlange 1320 eine Schreibanforderung, die die Änderung in den Freizustand bei den Speichern 1312 bewirkt und außerdem die Informationen bezüglich dieser Verbindung aus dem Wegspeicher 1318 entfernt. Jedes Knotenstufen-Steuergerät 1201 bis 1209 enthält einen Umsetzeru der eine vorbestimmte Kombination der Umordnungseingangs-, -ausgangs- und -wegsignale durchführt, um sowohl den Knoten als auch die Knoteneingangs-, Knotenausgangsverbindung zu bestimmen, die als Teil eines neuen Weges zu betätigen oder für eine Trennung abzuschalten sind. Die Auslegung dieser Umsetzer beruht auf der folgenden Logik. Aufgrund von Überlegungen ähnlich denen zur Bestimmung von Si(x,P*,y) und Li(x,P*,y) aus einer binären Darstellung von xM&sub1; + P*M + y lassen sich Ii(x,P*,y) (der für Si(x,P*,y) benutzte Eingang) und Oi(x,P*,y) (der für Si(x,P*,y) benutzte Ausgang) bestimmen.
Für 2 ≤ i ≤ S-1, ri = 2n+k+1, Mi = 2S-i und ni = 2¹ ist Ii(x,P*,y) gegeben durch ein Fenster von einem Bit, das um n+k-1+S-i Bits von der rechten Seite der Binärdarstellung von xM&sub1; + P*M + y verschoben ist.
Oi(x,P*,y) ist gegeben durch ein Fenster von einem Bit, das um S-i-1 Bits von der rechten Seite der Binärdarstellung von xM&sub1; + P*M + y verschoben ist.
Um Si(x,P*,y) und Oi(x,P*,y) aus der Umordnungsebene in die Überkreuzungsebene abzubilden, werden die Ausdrücke (3) und (4) in der Tabelle 1 bzw. der Ausdruck (12a) in der Tabelle 3 benutzt. Die erforderlichen Exklusiv-ODER-Funktionen lassen sich leicht als Hardware verwirklichen und die Eingangssignale für diese Funktionen werden direkt aus der Binärdarstellung von xM&sub1; + P*M + y gewonnen.
Die Überkreuzungs-auf-Umordnungs-Abbildungseinheit 1304 (Fig. 50 umfaßt eine Gruppe von Exklusiv-ODER-Gattemu die die jeweiligen Eingangs- und Ausgangssignale kombinieren. Da das Netzwerk eine Ausgangs- und Eingangsverzweigung von acht besitzt, kann das gesamte Netzwerk so angesehen werden, daß es insgesamt fünfzehn Stufen umfaßt, nämlich drei Stufen für eine 1:8- Ausgangsverzweigung, neun Vermittlungsstufen und drei Stufen für eine 1:8- Eingangsverzweigung. Die Ausgangs/Eingangsverzweigung wird dadurch bewirkt, daß selektiv nur einer der acht Eingänge/Ausgänge (ein Eingang/Ausgang von einem von vier Kopplern) ausgerüstet wird. Die gewählten 512 Eingangs- und Ausgangskoppler werden dann unter Verwendung des Ausdrucks (1) in Tabelle 1 auf die Umordnungsebene abgebildet. Die sich ergebende Logik ist in Fig. 50 gezeigt.
Die Speicher 1312 sind je 512x8-Speicher mit willkürlichem Zugriff, die die Linkleitungs-Besetzt/Freibits speichern. Die Weg-Besetzt/Frei-Prüfeinheiten 1314 sind als ODER-Gatter verwirklicht. Die Auswahleinheit 1316 (Fig. 51) ist unter Verwendung einer Anordnung von UND-, NAND-, ODER- und NOR-Gattern ausgeführt, um unter Verwendung von drei Wegsignalen den gewählten freien Weg zu definieren und ein einzelnes Signal zu erzeugen, das als Wegblockieranzeige und als Schreibanforderungssignal benutzt wird.
Die Wegunabhängigkeits-Prüfeinheit 1306 beruht auf der in Fig. 46 dargestellten Logikanordnung. Die beiden geprüften Eingangs/Ausgangspaare sind bezeichnet mit (X9, X8, X7, X6, X5, X4, X3, X2, X1) - (Y9, Y8, Y7, Y6, Y5, Y4, Y3, Y2, Y1) und (x9, x8, x7, x6, x5, x4, x3, x2, x1) - (y9, y8, y7, y6, y5, y4, y3, y2, y1). Die Logikanordnung der Einheit 1306 läßt sich zur Prüfung von unabhängigen Wegen in dem in Fig. 49 gezeigten Netzwerk 1330 unabhängig von der Ausgangsverzweigung verwendenu wie durch die erste Stufe von Elementen angegebenu die 1x2n Elemente enthält, und unabhängig von der Eingangsverzweigung, wie durch die 2n x1 -Elemente der letzten Stufe angezeigt. Die Logikanordnung der Einheit 1306 erzeugt ein Signal logisch null, wenn alle Wege für das Eingangs/Ausgangspaar nicht linkleitungsunabhängig sind, und erzeugt ein Signal logisch eins, wenn alle Paare linkleitungsunabhängig sind. Die Erklärung für diese Logikfunktion lautet wie folgt. Es sei die Binärdarstellung von xM&sub1; + P*M + y für die beiden geprüften Eingangslausgangspaare betrachtet.
Li(x,P*,y) wird durch ein Fenster von log&sub2; (rimi) = n+k = 9+3 = 12 Bits angegeben, das um log&sub2; Mi+1 = 12-i Bits von der rechten Seite dieser Binärwerte für 4 ≤ i ≤ 11 verschoben ist. Da jede Linkleitung der Stufe 1, 2 oder 3 durch nur einen Eingang zugänglich ist (die drei Stufen der Ausgangsverzweigung) und jede Linkleitung der Stufe 12, 13 oder 14 durch nur einen Ausgang zugänglich ist (die drei Stufen der Eingangsverzweigung) handelt es sich nur um Li für 4 ≤ i ≤ 11.
Man betrachte folgende Ausdrücke:
L&sub4;(x,P*,y) and L&sub4;(x',P*,y').
L&sub4;(x,P*,Y) = X&sub8;X&sub7;X&sub6;X&sub5;X&sub4;X&sub3;X&sub2;X&sub1;pppY&sub9;
L&sub4;(x',P*,y') = x&sub8;x&sub7;x&sub6;x&sub5;x&sub4;x&sub3;x&sub2;x&sub1;pppy&sub9;
Da das Feld ppp nur alle möglichen acht Werte annehmen kann, sind diese beiden Sätze von Linkleitungen nur dann unabhängig, wenn die restlichen Bits sich in wenigstens einer Position unterscheiden. Demgemäß sind die beiden Linkleitungssätze unabhängig, wenn
D&sub4; = (X&sub8; x&sub8;) + (X&sub7; x&sub7;) + ... + (X&sub1; x&sub1;) + (Y&sub9; y&sub9;) = 1. Entsprechend ist L&sub5;(x,P*,y) unabhängig von L&sub5;(x,p*,y), wenn
D&sub5; = (X&sub7; x&sub1;) + ... + (X&sub1; x&sub1;) + (Y&sub9; y&sub9;) + (Y&sub8; y&sub8;) = 1 usw., bis man erreicht D&sub1;&sub1; = (X&sub1; x&sub1;) + (Y&sub9; y&sub9;) + ... + (Y&sub2; y&sub2;) = 1. Der gesamte Satz von Linkleitungen ist nur dann unabhängig, wenn jedes Di = 1 oder DT = D&sub4; xD&sub5; x ... xD&sub1;&sub1; = 1. Die in Fig. 46 dargestellte Logik ist eine Boolsche Reduktion von DT.
Wenn festgestellt wird, daß zwei Eingangslausgangspaare bezüglich der Linkleitungen unabhängig sind, dann kann die Wegfreiwahl zur Herstellung von Verbindungen in einer überlappenden Betriebsweise ausgeführt werden, wie im Zeitsteuerungsdiagramm gemäß Fig. 47 gezeigt. Die zur Ausführung eines Lesevorgangs für die Speicher 1312, die nachfolgende Funktion der Logikschaltungen mit den ODER- Gattern 1314 und der Freiweg-Auswahleinheit 1316 erforderliche Zeit und dann die nachfolgende zeit zum Einschreiben in den Wegspeicher 1318 sowie zum Einschreiben von Besetztbits in die Speicher 1312 sind in Fig. 47 durch die Zeiten R&sub1;, L&sub1;, W&sub1; dargestellt. Die entsprechenden Zeitintervalle für eine zweite Verbindungsanforderung sind mit R&sub2;, L&sub2; W&sub2; bezeichnet. Wie dargestellt findet der zweite Lesevorgang während der Zeit stattu zu der die Ergebnisse des ersten Lesevorgangs über die verschiedenen Stufen von Logikgattern laufen. Wie in Fig. 48 gezeigt, können, wenn doppelte Kopien der Netzwerksteuergerät- Speicher usw. entsprechend Fig. 45 benutzt werden, vier Lesevorgänge ausgeführt werden, bevor die entsprechenden vier Schreibvorgänge stattfinden.
Alternativ kann man, statt zu prüfen, ob Konflikte zwischen den Wegen eines ersten Eingangs und eines ersten Ausgangs sowie eines zweiten Eingangs und eines zweiten Ausgangs auftreten, einfach so vorgehen, als ob für die gewählten Wege keine Konflikte vorhanden sind und dann im Fall eines Konflikts einen alternativen Weg zwischen dem zweiten Eingang und Ausgang wählen. Das Auftreten eines Konflikts wird festgestellt, wenn einer der Besetzt/Freianzeiger für den zweiten gewählten Weg besetzt markiert ist. In diesem Fall müssen die Besetzt/Freianzeiger für den zweiten Weg als frei angenommen werden mit Ausnahme derjenigen, die bereits als besetzt festgestellt sind, und es erfolgt eine Freiwahl nach einem alternativen Weg zwischen dem zweiten Eingang und Ausgang.
In vielen EGS-Netzwerken ist die Wahrscheinlichkeit, daß zwei Verbindungsanforderungen unabhängig sind, hoch. Es sei ein EGS-Netzwerk mit N Eingängen und M Ausgängen, S Stufen sowie mit n&sub1; Eingängen jedes Kopplers in der Stufe i und mi Ausgängen für jeden Koppler der Stufe i betrachtet, wobei
Man definiere L(a,b) als den Satz aller Linkleitungen auf allen Wegen zwischen dem Eingang a und dem Ausgang b, S(a,b) als den Satz aller Koppler auf allen Wegen zwischen dem Eingang a und dem Ausgang b und φ als den leeren oder Null-Satz. Mit diesen Definitionen lassen sich die folgenden Theoreme angeben.
Theorem für Linkleitungs-unabhängigen Weg:
L(x,y) L(X',y') = φ wenn und nur wenn t ≥ u,
Theorem für Koppler-unabhängigen Weg:
S(x,y) S(x',y') = φ wenn und nur wenn t > u,
wobei
t der kleinste Wert von i ist, für den gilt
und
u der größte Wert von i ist, für den gilt
und wobei
W die größte ganze Zahl ≤ W
und
W die kleinste ganze Zahl ≥ W angibt.
Für willkürlich gewählte x, y und x', y' werden zwei Fälle betrachtet:
Fall 0:
x und x' werden mit Ersatz aus dem Satz von N Eingängen gewählt, d.h., es wird zugelassen, daß x und x' der gleiche Eingang ist. Entsprechend werden y und y' mit Ersatz aus dem Satz von M Ausgängen gewählt. Für diesen Fall wird eine Variable β = 0 gesetzt.
Fall 1:
x und x' sowie auch y und y' werden ohne Ersatz aus den Sätzen von N Eingängen bzw. M Ausgängen gewählt. Demgemäß gilt x ≠ x, und y ≠ y. Für diesen Fall wird gesetzt β = 1.
Wahrscheinlichkeit für die Linkleitungsunabhängigkeit des Weges: Die Wahrscheinlichkeit, daß L(x,y) L(x',y') = φ ist gegeben durch
Wahrscheinlichkeit für die Kopplerunabhängigkeit des Weges
Die Wahrscheinlichkeit, daß gilt S(x,y) S(x',y') = φ ist gegeben durch
Für log&sub2; N ≤ S ≤2 log&sub2; N:P (unabhängig) = P (alle Wege zwischen einem gegebenen Eingangs/Ausgangspaar sind bezüglich der Koppler und Verbindungsleitungen unabhängig von allen Wegen zwischen einem anderen Eingangslausgangspaar) =
Es gibt
Möglichkeiten zur Auswahl von zwei Eingangs/Ausgangspaaren, die gemeinsame Koppler für bestimmte Wege besitzen. Es sind
Möglichkeiten vorhanden, zwei Eingangs/Ausgangspaare zu wählen. Beispielsweise gibt es für N=512 und S=9
Möglichkeiten zurauswahl von zwei Eingangs/Ausgangspaaren, die sich kreuzende Wege besitzen, und
Möglichkeiten, zwei Eingangs/Ausgangspaare zu wählen. P (unabhängig)
Weiterhin gilt P (wenigstens zwei von drei Paaren sind unabhängig) 0,99999613, P (jedes Paar von vier Paaren ist unabhängig von den anderen drei) 0,9094 und P (vier von fünf Paaren sind alle unabhängig) 0,996.

Claims

1. Verfahren zur Verwendung in einer Anordnung mit einem Netzwerk (1200) zur Verbindung mit jedem von einer Vielzahl von Eingängen mit jedem von einer Vielzahl von Ausgängen und mit einer Einrichtung (1312) zur Speicherung von Besetzt/Frei-Informationen für Wegkomponenten des Netzwerks, mit den Verfahrensschritten:

Lesen (über 1314) der Speichereinrichtung (1312) zur Identifizierung (über 1316) eines freien Weges von einem ersten Eingang über das Netzwerk (1200) zu einem ersten Ausgang,

nach Identifizieren eines freien Weges vom ersten Eingang zum ersten Ausgang werden Wegkomponenten des identifizierten Weges in der Speichereinrichtung (1312) als besetzt markiert (über 1318), und vor der Markierung wird auf die Speichereinrichtung (1312) zum Auffinden eines freien Weges von einem zweiten Eingang über das Netzwerk (1200) zu einem zweiten Ausgang zugegriffen, gekennzeichnet durch den Schritt:

Feststellen (über 1306), ob Wege des Netzwerks vom ersten Eingang zum ersten Ausgang in Konflikt mit Wegen des Netzwerks vom zweiten Eingang zum zweiten Ausgang sind,

wobei das Zugreifen unter Ansprechen auf die Feststellung (über 1306) erfolgt, daß keine Wege des Netzwerks vom ersten Eingang zum ersten Ausgang in Konflikt mit Wegen des Netzwerks vom zweiten Eingang zum zweiten Ausgang sind.

2. Verfahren nach Anspruch 1,

bei dem das Neztwerk eine Vielzahl von Knoten der Kapazität Eins aufweist und bei dem der Feststellschritt die Feststellung umfaßt, ob Wege des Netzwerks vom ersten Eingang zum ersten Ausgang den gleichen Knoten wie Wege des Netzwerks vom zweiten Eingang zum zweiten Ausgang enthalten.

3. Verfahren nach Anspruch 1,

bei dem das Netzwerk eine Vielzahl von Knoten voller Kapazität enthält, die untereinander durch Links verbunden sind, und bei dem der Feststellschritt die Feststellung umfaßt, ob Wege des Netzwerks vom ersten Eingang zum ersten Ausgang die gleichen Links wie Wege des Netzwerks vom zweiten Eingang zum zweiten Ausgang enthalten.

4. Verfahren nach Anspruch 1,

bei dem jedem Eingang eine binäre Eingangsnummer mit einer Vielzahl von Bits und jedem Ausgang eine binäre Ausgangsnummer mit einer Vielzahl von Bits zugeordnet sind, und

bei dem der Feststellschritt den Schritt umfaßt:

logische Verarbeitung der Bits der dem ersten und zweiten Eingang zugeordneten binären Eingangsnummern und der Bits der dem ersten und zweiten Ausgang zugeordneten binären Ausgangsnummern.

5. Verfahren nach Anspruch 4,

bei dem der Verarbeitungsschritt umfaßt:

logische Kombination entsprechender Bits der dem ersten und dem zweiten Eingang zugeordneten binären Eingangsnummern und logische Kombination entsprechender Bits der dem ersten und zweiten Ausgang zugeordneten binären Ausgangsnummern.

6. Verfahren nach Anspruch 1,

bei dem die Speichereinrichtung erste und zweite Speichereinrichtungen umfaßt, die je zur Speicherung von Besetzt/Frei-Informationen für alle Wegkomponenten aller Wege des Netzwerks vorgesehen sind,

wobei der Leseschritt das Lesen der ersten Speichereinrichtung umfaßt,

wobei der Markierschritt das Markieren aller Wegkomponenten des identifizierten Weges als besetzt sowohl in der ersten als auch in der zweiten Speichereinrichtung umfaßt, und

wobei der Zugriffsschritt das Zugreifen auf die zweite Speichereinrichtung umfaßt.

7. Verfahren nach Anspruch 1,

bei dem die Speichereinrichtung eine erste und eine zweite Speichereinrichtung umfaßt, die je zur Speicherung von Besetzt/Frei- Informationen für alle Wegkomponenten aller Wege des Netzwerks vorgesehen sind,

wobei der Leseschritt das Lesen der ersten Speichereinrichtung umfaßt,

wobei der Zugriffsschritt das Zugreifen auf die zweite Speichereinrichtung gleichzeitig mit dem Lesen der ersten Speichereinrichtung umfaßt.

8. Verfahren nach Anspruch 1,

bei dem der Leseschritt das Lesen der Besetzt/Frei-lnformationen aus der Speichereinrichtung und die Verarbeitung der gelesenen Information zur Identifizierung eines freien Weges vom ersten Eingang zum ersten Ausgang umfaßt.

9. Verfahren nach Anspruch 1,

bei dem der Leseschritt das Lesen der Besetzt/Frei-Information aus der Speichereinrichtung und die Verarbeitung der gelesenen Information gleichzeitig mit dem Zugreifen zur Identifizierung eines freien Weges vom ersten Eingang zum ersten Ausgang umfaßt.

10. Verfahren nach Anspruch 1 mit ferner dem Schritt:

nach Auffinden eines freien Weges vom zweiten Eingang zum zweiten Ausgang werden alle Wegkomponenten des gefundenen Weges in der Speichereinrichtung als besetzt markiert.

11. Verfahren nach Anspruch 1,

bei dem der erste und der zweite Eingang der gleiche Eingang und der erste und der zweite Ausgang der gleiche Ausgang sein können.

12. Verfahren nach Anspruch 1,

bei dem der erste und der zweite Eingang unterschiedliche Eingänge und der erste und der zweite Ausgang unterschiedliche Ausgänge sein müssen.

13. Anordnung mit einem Netzwerk (1200) zur Verbindung jedes Eingangs einer Vielzahl von Eingängen mit jedem Ausgang einer Vielzahl von Ausgängen, einer Einrichtung (1 31 2) zur Speicherung von Besetzt/Frei-Informationen für Wegkomponenten des Netzwerks,

einer Einrichtung (1314), die unter Ansprechen auf eine Anforderung nach einer ersten Verbindung von einem ersten Eingang über das Netzwerk zu einem ersten Ausgang Besetzt/Frei-Informationen aus der Speichereinrichtung liest,

einer Einrichtung (1316), die unter Ansprechen auf die gelesenen Besetzt/Frei-lnformationen einen freien Weg über das Netzwerk für die erste Verbindung identifiziert,

eine Einrichtung (1318), die unter Ansprechen auf die Identifizierung des ersten Verbindungsweges durch die Identifizierungseinrichtung Wegkomponenten des ersten Verbindungsweges in der Speichereinrichtung als besetzt markiert, und

einer Einrichtung (1300), die unter Ansprechen auf eine Anforderung nach einer zweiten Verbindung von einem zweiten Eingang über das Netzwerk zu einem zweiten Ausgang die Leseeinrichtung so steuert, daß sie vor der Besetzt-Markierung der Komponenten des ersten Verbindungsweges durch die Markiereinrichtung Besetzt/Frei- Informationen auslesen, um einen Weg über das Netzwerk für die zweite Verbindung zu identifizieren,

dadurch gekennzeichnet,

daß die Steuereinrichtung eine Einrichtung (1306) aufweist, die feststellt, ob ein Weg des Netzwerks vom ersten Eingang zum ersten Ausgang mit Wegen des Netzwerks vom zweiten Eingang zum zweiten Ausgang in Konflikt steht, und

daß die Steuereinrichtung (1300) das Auslesen der Speichereinrichtung zur Identifizierung des zweiten Verbindungsweges nur unter Ansprechen auf eine Feststellung der Feststelleinrichtung (1306) steuert, daß keine Wege des Netzwerks vom ersten Eingang zum ersten Ausgang vorhanden sind, die mit Wegen des Netzwerks vom zweiten Eingang zum zweiten Ausgang in Konflikt stehen.

14. Anordnung nach Anspruch 13,

bei der die Speichereinrichtung eine erste und eine zweite Speichereinrichtung aufweist, die je Besetzt/Frei-lnformationen für alle Wegkomponenten aller Wege des Netzwerks speichern,

bei der die Leseeinrichtung unter Ansprechen auf die Anforderung der ersten Verbindung Besetzt/Frei-Informationen aus der ersten Speichereinrichtung zur Identifizierung des ersten Verbindungsweges liest,

bei der die Markiereinrichtung unter Ansprechen auf die Identifizierung des ersten Verbindungsweges alle Wegkomponenten des ersten Verbindungsweges in der ersten und der zweiten Speichereinrichtung als besetzt markiert, und

bei der die Steuereinrichtung unter Ansprechen auf die Anforderungen nach der zweiten Verbindung die Leseeinrichtung so steuert, daß sie vor der Besetzt-Markierung der Komponenten des ersten Verbindungsweges in der ersten und der zweiten Speichereinrichtung durch die Markiereinrichtung Besetzt/Frei-Informationen aus der zweiten Speichereinrichtung zur Identifizierung des zweiten Verbindungsweges ausliest.

15. Anordnung nach Anspruch 13,

bei der die Speichereinrichtung eine erste und eine zweite Speichereinrichtung aufweist, die je Besetzt/Frei-Informationen für alle Wegkomponenten aller Wege des Netzwerks speichern,

bei der die Leseeinrichtung unter Ansprechen auf die Anforderungen nach der ersten Verbindung Besetzt/Frei-Informationen aus der ersten Speichereinrichtung zur Identifizierung des ersten Verbindungsweges ausliest,

bei der die Markiereinrichtung unter Ansprechen auf die Identifizierung des ersten Verbindungsweges alle Wegkomponenten des ersten Verbindungsweges in der ersten und in der zweiten Speichereinrichtung als besetzt markiert, und

bei der die Steuereinrichtung unter Ansprechen auf die Anforderung nach der zweiten Verbindung die Leseeinrichtung so steuert, daß sie Besetzt/Frei-Informationen aus der ersten und der zweiten Speichereinrichtung zur Identifizierung des zweiten Verbindungsweges gleichzeitig mit dem Auslesen von Besetzt/Frei-Informationen aus der ersten Speichereinrichtung zur Identifizierung des ersten Verbindungsweges ausliest.

16. Anordnung nach Anspruch 13,

bei der die Identifizierungseinrichtung aufweist:

eine Einrichtung zur Verarbeitung von gelesenen Besetzt/Frei- Informationen für die Identifizierung des ersten Verbindungsweges, und bei der die Steuereinrichtung das Auslesen aus der zweiten Speichereinrichtung zur Identifizierung des zweiten Verbindungsweges gleichzeitig mit der Verarbeitung zur Identifizierung des ersten Verbindungsweges durch die Verarbeitungseinrichtung steuert.