DE68921312T2

DE68921312T2 - Aufbau für selbstleitweglenkendes Paketvermittlungsnetz.

Info

Publication number: DE68921312T2
Application number: DE68921312T
Authority: DE
Inventors: James Moscoe Johnson; Ronald Anthony Spanke
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1988-12-21
Filing date: 1989-12-12
Publication date: 1995-09-28
Anticipated expiration: 2009-12-13
Also published as: ES2068254T3; EP0375249B1; CA1319410C; US4899335A; DE68921312D1; JPH02185140A; EP0375249A3; EP0375249A2

Description

Die Erfindung betrifft Paketwegführungsanordnungen.
Paketwegführungsanordnungen haben sich als bevorzugte Vermittlungsnetzwerke für viele Arten digitaler Kommunikationen erwiesen. Datenpakete, die je einen Datenteil und eine numerische Bezeichnung eines Netzwerkausgangsports umfassen, werden an den Eingang eines solchen Netzwerks angelegt und das Netzwerk überträgt jedes Paket zu dem angegebenen Ausgangsport.
Ein übliches Paketnetzwerk wird als Expansionsnetzwerk bezeichnet und umfaßt eine Vielzahl von miteinander verbundenen Koppeielenienten, die zwei Eingänge und zwei Ausgänge besitzen. Koppel- oder Schaltelemente empfangen Pakete an beiden Eingängen, interpretieren die Ausgangsport- Bezeichnungen und führen die Eingangspakete zu den Ausgängen des Koppelelements. Wenn zwei Pakete, die für den gleichen Koppelelementausgang bestimmt sind, in ein Koppelelement eintreten, wird ein Paket blockiert, da nur ein Paket zu einem bestimmten Zeitpunkt zu einem einzigen Ausgang übertragen werden kann. Die Paketblockierung verringert die Paketübertragungsrate von Expansionsnetzwerken und erfordert Einrichtungen für die Wiedergewinnung der blockierten Pakete. Ein Expansionsnetzwerk, das als Omega-Netzwerk bezeichnet wird, ist beschrieben in einem Aufsatz "Access and Alignment of Data in an Array Processor", Transaction Computers, Band C- 24, Nr. 12, Dezember 1975, Seiten 1145-1155.
Ein Paketvermittlungsnetzwerk, das von Huang und Knauer in einem Aufsatz "STARLITE: A Wideband Digital Switch", Globecom 1984, Seiten 121-125 beschrieben ist, vermeidet das Blockierproblem von Expansionsnetzwerken, indem ankommende Pakete in aufsteigender (oder absteigender) Reihenfolge auf der Grundlage ihrer Bestimmung sortiert werden bevor sie an die Eingänge des Expansionsnetzwerkes angelegt werden. Die Vorsortierung von Paketen beseitigt Kombinationen von Eingangspaketen, die zu einer Blockierung führen würden. Da die Blockierung vermieden worden ist, wird der Durchsatz des Netzwerks verbessert und zusätzliche komplizierte Einrichtungen zur Wiedergewinnung blockierter Pakete sind unnötig. Die Blockierverringerung, die durch das von Huang et al. beschriebene Netzwerk mit Sortierung und anschließender Expandierung erreicht wird, ist ein großer Vorteil bei der Paketvermittlung. Es ergeben sich jedoch Schwierigkeiten bei der Herstellung solcher Netze, die eine große Anzahl von Eingangs- und Ausgangsports besitzen.
Zur Vermittlung von Paketgruppen in einem Netzwerk mit Sortierung und anschließender Expandierung müssen die Koppelelemente sowohl der Sortier- als auch der Expandierstufen voll miteinander verbunden sein, so daß ein Paket an jeder Eingangsposition innerhalb der Gruppe mit jeder Ausgangsposition der Gruppe verbunden werden kann. Bekannte Netzwerke mit Sortierung und anschließender Expandierung, beispielsweise das Netzwerk nach Huang et al., sortieren alle empfangenen Pakete als eine einzelne Gruppe und expandieren die sortierte Folge dann als einzelne Gruppe. Solche Netzwerke müssen eine vollständige Verbindungsmöglichkeit besitzen, die durch Bereitstellung mehrerer Lagen von Koppelelementen und komplexen Verbindungen zwischen den Lagen erreicht wird. Wenn die Anzahl der Pakete in der Gruppe die für ein kommerzielles Produkt erforderliche Größe besitzt, beispielsweise 128 oder mehr, sind viele Lagen von Koppelelementen erforderlich, die zu einer großen Anzahl von Vermittlungsschaltungen mit komplizierten Verbindungen führen.
Die Zahl der Schaltungsgruppen, die zur Herstellung einer Konstruktion erforderlich sind, wird zum Teil durch die Menge der Schaltungen auf einer Schaltungsgruppe bestimmt, die durch die erforderliche Leistung, Wärmeabfuhr und verfügbare Oberflächengröße sowie auch durch die Anzahl von Eingangs- und Ausgangsverbindungen begrenzt wird, die für die Schaltungen auf der Schaltungsgruppe erforderlich sind. Wenn standardmäßige Layout-Verfahren auf bekannte Netzwerke kommerzieller Größe mit Sortierung und anschließender Expandierung angewendet werden, ist die Anzahl der erforderlichen Schaltungsgruppen groß, weil a) eine große Anzahl von Vermittlungsschaltungen (viele Lagen) erforderlich ist und b) die volle Verbindungsmöglichkeit der Schaltung die Anzahl der Schaltungen verringert, die wegen der Eingangs-/ Ausgangs-Verbindungsbegrenzungen auf jeder Schaltungsgruppe untergebracht werden können. Dies große Anzahl von Schaltungsgruppen führt zu Produkten, die groß, kompliziert und teuer sind.
Im Hinblick auf die vorstehenden Erläuterungen besteht ein Bedarf nach einem Paketvermittlungsnetzwerk kommerzieller Größe, das die vorteilhaften Eigenschaften eines Netzwerks mit Sortierung und anschließender Expandierung ohne die Größe, Kompliziertheit und finanziellen Aufwand bekannter Systeme zu besitzen.
Entsprechend einem Merkmal der Erfindung wird eine Paketwegführungsanordnung gemäß Anspruch 1 geschaffen.
Nach einem weiteren Merkmal der Erfindung wird eine Paketwegführungsanordnung gemäß Anspruch 13 bereitgestellt.
Die Größe, Kompliziertheit und die Kosten bekannter Netzwerke mit Sortierung und anschließender Expandierung werden bei einem Ausführungsbeispiel der Erfindung dadurch herabgesetzt, daß empfangene Pakete auf der Grundlage der Paketbestimmungsorte in Gruppen aufgetrennt werden, je Gruppe ohne Rücksicht auf andere Gruppen sortiert wird und Teile der sortierten Gruppen in einer Vielzahl von Expansionsausgangskopplern rekombiniert werden, bevor die Pakete Ausgangsports des Netzwerks zugeführt werden. Im einzelnen umfassen die Ausgangsports des Netzwerks eine Vielzahl von Ausgangskopplern, und wenn Pakete durch eine Eingangsanordnung empfangen werden, so werden sie etwa gleichmäßig entsprechend ihrer Ausgangskopplerbestimmung auf eine Vielzahl von Zwischensortiereinheiten verteilt, die für einen gemeinsamen Ausgangskoppler bestimmte Paketgruppen identifizieren und die identifizierten Gruppen den Bestimmungsausgangskopplern zuführen. Die Ausgangskoppler führen die empfangenen Gruppen von Paketen zusammen und verteilen die einzelnen Pakete auf die Bestimmungsausgangsports.
Eine beispielhafte Eingangsanordnung für Netze mit Zwischensortiereinheiten umfaßt ein Eingangssortiernetzwerk zur Sortierung empfangener Pakete in eine Folge auf der Grundlage der Ausgangskopplerbestimmungen der Pakete. Eine gleichmäßige Verteilung der Pakete auf der Grundlage der Ausgangsbestimmung wird dadurch erreicht, daß jedes nte Paket der Folge von Paketen vom Eingangssortiernetzwerk auf die gleiche Zwischenkoppeleinheit gegeben wird.
Weitere Vorteile lassen sich durch eine Eingangsanordnung erreichen, die eine Vielzahl von Eingangssortiereinheiten zur Verteilung von Paketen auf Zwischensortiereinheiten aufweist. Jede Eingangssortiereinheit ordnet eine vorbestimmte Anzahl der empfangenen Pakete auf der Grundlage der Ausgangsbestimmungen der vorbestimmten Anzahl von Paketen in eine Folge ein. Ein annähernd gleichmäßige Verteilung von Paketen auf die Zwischensortiereinheiten wird erreicht, indem jeden nte Paket der Folge von Paketen von jeder Eingangssortiereinheit auf die gleiche Zwischensortiereinheit gegeben wird. Die Bereitstellung einer Vielzahl von Eingangssortiereinheiten verbessert die physikalische Realisierbarkeit des Netzwerks, indem die Anzahl von gegenseitigen Verbindungen verringert wird, die für eine Paketverteilung durch Verringerung der Paketgruppengröße erforderlich ist.
Zwischensortiereinheiten nehmen die annähernd gleichmäßig verteilten Pakete von der Eingangsanordnung auf und identifizieren Paketgruppen anhand des Ausgangskopplers, für den sie bestimmt sind. Bei einem speziellen Ausführungsbeispiel sortieren die Zwischensortiereinheiten Pakete auf der Grundlage der Paketbestimmungen in eine Vielzahl von Gruppen, deren Zahl gleich der Zahl der Ausgangskoppler ist, und führen jede Gruppe einem unterschiedlichen Ausgangskoppler zu.
Die physikalische Realisierbarkeit des Netzwerks kann weiter verbessert werden, indem eine vorbestimmte Anzahl von Verbindungen zwischen den Zwischensortiereinheiten und den Ausgangskopplern bereitgestellt wird. Wenn eine solche vorbestimmte Anzahl von Verbindungen vorhanden ist, umfassen die Zwischensortiereinheiten Schaltungen als Teil einer Einfanganordnung, die die Anzahl von Paketen in einer Gruppe auf eine vorbestimmte Anzahl begrenzen, bevor sie den Ausgangskopplern zugeführt werden. Wenn jedes Paket Prioritätsinformationen enthält, die die relative Wichtigkeit des Pakets definieren, sprechen die Schaltungen zweckmäßig auf die Prioritätsinformationen an, so daß die Pakete mit niedrigster Priorität gesperrt werden.
Bei einem speziellen Ausführungsbeispiel der Erfindung werden die Pakete durch Zwischensortiereinheiten sowohl entsprechend der Bestimmung als auch der Prioritätsinformation sortiert, derart, daß die Pakete in Gruppe sortiert sind und im einzelnen entsprechend ihrer Priorität in jeder Gruppe angeordnet sind. Sperrschaltungen unterteilen jede Paketgruppe in eine ersten und eine zweite Untergruppe, derart, daß die Anzahl von Paketen in der zweiten Untergruppe null ist, so lange die Anzahl von Paketen in der ersten Untergruppe kleiner oder gleich der vorbestimmten Anzahl ist und die Priorität von Paketen in der ersten Untergruppe höher als die Priorität von Paketen in der zweiten Untergruppe ist. Die Pakete in der ersten Untergruppe werden dann den Ausgangskopplern zugeführt. Ein weiterer Vorteil läßt sich erreichen, wenn die zweite Paketuntergruppe in einer Verzögerungsschaltung verzögert und dann den Ausgangskopplern zu einem späteren Zeitpunkt zugeführt werden. Die Verzögerung bei der Weiterübertragung von Paketen wird bei einem Ausführungsbeispiel dadurch bereitgestellt, daß die verzögerten Pakete mit später empfangenen Paketgruppen zusammengeführt werden, die entsprechend der obigen Erläuterung an Ausgangsports vermittelt werden.
Eine beispielhafte Ausgangskoppeleinheit umfaßt ein Netzwerk zur Zusammenführung der von den Zwischensortiereinheiten empf angenen Paketgruppen in eine Folge auf der Grundlage der Ausgangsport-Bestimmungen, um die Verteilung der Pakete auf die Ausgangsports zu erleichtern. Aufgrund der Verteilung ankommender Pakete besteht die Möglichkeit, daß eine Ausgangskoppeleinheit mehr als 1 Paket für einen einzelnen Bestimmungs-Ausgangsport empfängt. Die Ausgangskoppeleinheit enthält eine Sperranordnung zur Sperrung aller Pakete außer einem Paket für einen einzigen Bestimmungs-Ausgangsport. Mit Vorteil werden die gesperrten Pakete für eine spätere Übertragung zu den Ausgangsports verzögert, und spezielle, zu sperrende Pakete werden auf der Grundlage der Paketpriorität ausgewählt.

Kurze Beschreibung der Zeichnungen

Es zeigen
Fig. 1 das Blockschaltbild eines Paketvermittlungsnetzwerkes nach der Erfindung;
Fig. 2 das bei dem Ausführungsbeispiel benutzte Format von Paketen;
Fig. 3 das Blockschaltbild einer Verteilung gemäß Fig. 1;
Fig. 4 das Blockschaltbild einer in Fig. 1 dargestellten Sortiereinheit;
Fig. 5 das Blockschaltbild eines in Fig. 1 gezeigten Ausgangskopplers;
Fig. 6 ein Einfangnetzwerk gemäß Fig. 4.

Ins einzelne gehende Beschreibung

Fig. 1 stellt ein Blockschaltbild für ein Paketvermittlungsnetzwerk nach der vorliegenden Erfindung dar. Ein Verteiler 101 nimmt Pakete auf 128 ankommenden Paketwegen 102 auf und verteilt jedes empfangene Paket auf eine von vier Sortiereinheiten 104-107 über Verteilerausgangswege 103. Der Verteiler 101 sortiert empfangene Pakete in aufsteigender Reihenfolge von der linken Seite aus auf der Grundlage eines bestimmten Kopplers von acht Ausgangskopplern 108-115, welcher der Bestimmungsausgangskoppler für das Paket ist. Nachdem die Pakete durch den Verteiler 101 sortiert worden sind, werden sie an Verteilerausgangswege 103 derart angelegt, daß die für den niedrigst numerierten Ausgangskoppler 108 bestimmten Pakete an den am weitesten links liegenden Ausgängen 103 erscheinen, und Pakete, die für den höchst numerierten Ausgangskoppler 115 bestimmt sind, am rechten Ende der sortierten Paketfolge auftreten. Inaktive Pakete entsprechend der nachfolgenden Beschreibung werden vom Verteiler 101 an den am weitesten rechts liegenden Ausgang 103 angelegt.
Mit Vorteil sind die Ausgangswege 103 des Verteilers 101 an Eingänge der Sortiereinheiten 104-107 in einem vorbestimmten Muster angeschlossen, das die vom Verteiler 101 empfangenen Pakete gleichmäßig auf die Sortiereinheiten verteilt und jeder Sortiereinheit einen repräsentativen Abtastwert auf der Grundlage der Ausgangskopplerbestimmungen der ankommenden Pakete bereitstellt. Das vorbestimmte Muster des vorliegenden Ausführungsbeispiels besteht darin, daß der am weitesten links liegende Ausgang 103 und jeder folgende, vierte Ausgang (0, 4, 8...) mit der Sortiereinheit 104 verbunden sind, der zweite Ausgang von links und jeder vierte Ausgang danach (1, 5, 9...) mit der Sortiereinheit 105, der dritte Ausgang 103 von links und jeder vierte Ausgang danach (2, 6, 10...) mit der Sortiereinheit 106 und der vierte Ausgang 103 von links und jeder vierte Ausgang danach (3, 7, 11...) mit der Sortiereinheit 107. Die gleichmäßige Verteilung von Paketen auf jede Vermittlungseinheit 104-107 auf der Grundlage der Ausgangskoppler-Bestimmung der Pakete liefert jeder Sortiereinheit, beispielsweise 104 etwa die gleiche Anzahl von Paketen, die für einen Ausgangskoppler, beispielsweise 115 bestimmt sind. Dies gilt für alle anderen Koppeleinheiten 105- 107.
Jede Zwischensortiereinheit 104-107 nimmt 32 Pakete (128:4) vom Verteiler 101 auf und sortiert die Pakete in acht Gruppen auf der Grundlage des jeweiligen Ausgangskopplers von acht Ausgangskopplern 108-115, für den jedes Paket bestimmt ist. Wenn eine Gruppe mehr als vier, für einen Ausgangskoppler bestimmte Pakete enthält, werden vier Pakete für die Übertragung zu dem durch die Pakete der Gruppe bezeichneten Ausgangskoppler ausgewählt. (Die Behandlung nicht gewählter Pakete wird später in Verbindung mit einer genaueren Beschreibung der Sortiereinheiten 104-107 erläutert.) Die in jeder Gruppe nach der Auswahl verbleibenden Pakete werden über Übertragungswege 116 zu dem durch die Pakete der Gruppe bezeichneten Ausgangskoppler übertragen. Jeder Ausgangskoppler 108-115 führt die Gruppe der von ihm empfangenen Pakete zusammen und vermittelt sie über einen Expansionskoppler zu angegebenen Ausgangsports 118.
Der Verteiler 101 liefert jeder Sortiereinheit 104-107 einen annähernd repräsentativen Beispielswert des Eingangsverkehrs und jede Sortiereinheit trennt diesen Beispielswert auf der Grundlage der Ausgangskoppler 108-115, die die Bestimmung jedes Pakets sind, in Gruppen auf. Da die von jeder Sortiereinheit 104-107 empfangenen Pakete den gesamten ankommenden Verkehr darstellen, kann die Sortierung durch die Sortiereinheiten unabhängig von mehreren Einheiten statt von einer einzigen Sortiereinheit durchgeführt werden und die durch jede einzelne Sortiereinheit gebildeten Gruppen stellen weiterhin den ankommenden Verkehr dar. Das Zusammenführen der Gruppen von Sortiereinheiten durch die Ausgangskoppler 108-115 rekombiniert diese Paketgruppen für eine am Ende erfolgende Zuführung zu Ausgangsports. Zweckmäßig sind die Stufen dieses Aufbaus in mehrere Einheiten aufgetrennt, die keine Verbindung innerhalb der Stufe benötigen und demgemäß die komplizierten Zwischenstufenverbindungen nach dem Stand der Technik vermeiden.
Die folgende, genauere Beschreibung der Arbeitsweise des Paketvermittlungsnetzwerks beginnt mit einer Beschreibung eines beispielhaften, in Fig. 2 dargestellten Pakets. Das Paket gemäß Fig. 2 umfaßt einen Kopfteil 130 und einen Datenteil 131. Der Kopfteil 130 umfaßt ein Aktivitätsbit 132, wobei eine "0" ein aktives Paket und eine "1" ein inaktives Paket angeben, ferner einen Teil 133 mit einer 3-Bit- Ausgangskopplerbezeichnung, eine 4-Bit-Ausgangsportbezeichnung 134 und eine Prioritätsbezeichnung 135. Der Teil 133 mit einer Ausgangskopplerbezeichnung definiert einen Bestimmungsausgangskoppler, beispielsweise 108 für das Paket und die Ausgangsportbezeichnung 134 definiert den speziellen Ausgangsport 180 des angegebenen Ausgangskopplers, der das Paket aufnehmen soll. Das Prioritätsfeld 135 wird auf bekannte Weise zur Identifizierung der relativen Übertragungswichtigkeit des zugeordneten Pakets benutzt. Ein Prioritätsfeld 31 gleich "0" bezeichnet höchste Priorität und die zunehmende numerische Bedeutung des Prioritätsfeldes läßt die Priorität abnehmen.
Fig. 3 zeigt ein Ausführungsbeispiel für den Verteiler 101, der die Verteilung unter Verwendung von acht Eingangssortiereinheiten 120-127 statt nur einer einzelnen Sortiereinheit gemäß Fig. 1 durchführt. Obwohl diese Verteilung die repräsentative Natur der den Sortiereinheiten 104-107 gelieferten Pakete verringert, bietet die Aufteilung der Verteilerfunktion auf mehrere Einheiten den Vorteil, die Zwischenstufenverbindungen innerhalb des Verteilers 101 zu verringern, wodurch die Herstellung vereinfacht wird. Jede Sortiereinheit 120-127 nimmt Pakete von 16 Eingangsübertragungswegen 102 auf, sortiert die empfangenen Pakete in aufsteigender Reihenfolge, beginnend von links und zwar aufgrund des Aktivitätsbit 132 (Fig. 2) gefolgt von der Ausgangskopplerbezeichnung 133. (Ein weiterer Verteilungsvorteil kann durch zunehmende Kompliziertheit der Eingangssortiereinheit erreicht werden, und zwar durch Aufnahme der Priorität in den Sortierschlüssel, derart, daß benachbarte Pakete, die für den gleichen Ausgangskoppler bestimmt sind, anhand abnehmender Priorität angeordnet werden.) Der Einschluß des Aktivitätsbit 132 in die Sortierung führt dazu, daß alle inaktiven Pakete zusammen auf die rechte Seite der Ausgangsfolge gebracht werden. Die sortierte Folge von Paketen von jeder Eingangssortiereinheit, beispielsweise 120, wird an 16 Übertragungswege 103 angelegt. Die 16 Ausgänge 103 der Eingangssortiereinheit 120 sind auf die Eingänge von Sortiereinheiten 104-107 verteilt, um die empfangenen Pakete gleichmäßig zu verteilen. Im einzelnen sind die ersten vier Ausgänge von links der Eingangssortiereinheit 120 in einer Folge mit den Sortiereinheiten 104-107 verbunden, und die nächsten vier Ausgänge jeder Gruppe von vier Ausgängen ist in einer Folge an die Vermittlungseinheiten 104-107 angeschlossen. Dieses Verbindungsmuster gilt auch für die Eingangssortiereinheiten 121, 122 und 123 mit der Ausnahme, daß die Ausgänge der Eingangssortiereinheit 121 mit Sortiereinheiten 105, 106, 107 und 104 nacheinander verbunden sind, die Ausgänge der Eingangssortiereinheit 122 nacheinander mit Sortiereinheiten 106, 107, 104 und 105 und die Ausgänge der Eingangssortiereinheit 123 mit Sortiereinheiten 107, 104, 105 und 106 verbunden sind. Das Verbindungsmuster zwischen den Eingangssortiereinheiten 124-127 und den Sortiereinheiten 104- 107 ist das gleiche wie die Verbindungsmuster für die Eingangssortiereinheiten 120-123.
Eine Aufteilung der Verteilungsfunktion des Verteilers 101 auf acht Eingangssortiereinheiten behält den Vorteil weniger Zwischenstufenverbindungen gemessen an größeren Paketgruppen bei und das Verbindungsmuster zwischen den Eingangssortiereinheiten 120-127 und den Sortiereinheiten 104- 107 ermöglicht die annähernd gleichmäßige Verteilung der empfangenen Pakete auf die Sortiereinheiten. Die Verwendung mehrerer Eingangssortiereinheiten 120-127 beeinflußt die Gleichmäßigkeit der Paketverteilung auf die Sortiereinheiten 104-107. Bei acht Eingangssortiereinheiten 120-127, die mit vier Sortiereinheiten 104-107 auf der Grundlage des beschriebenen Verbindungsmusters verbunden sind, besteht die (unwahrscheinliche) Möglichkeit, daß die Sortiereinheit, beispielsweise 104, die die größte Anzahl von Paketen für einen gegebenen Ausgangskoppler empfängt bis zu acht Pakete mehr für den gegebenen Ausgangskoppler als die Koppeleinheit, beispielsweise 121, die die geringste Anzahl von Paketen für den gegebenen Ausgangskoppler erhält. Diese Größe einer ungleichen Verteilung hat sich als angemessen für funktionelle Vermittlungsanordnungen erwiesen.
Der Aufbau der Sortiereinheiten 104-107 wird mit Bezug auf Fig. 4 beschrieben, die die Struktur der Sortiereinheit 104 darstellt. Die Sortiereinheit 104 nimmt vier Eingangspakete von jeder der acht Eingangssortiereinheiten 120-127 auf, also insgesamt 32 Eingangspakete, und überträgt vier Pakete zu jedem von acht Ausgangskopplern 108-115, also insgesamt 32 Ausgangspakete. Die Sortiereinheit 104 enthält ein Sortiernetzwerk 140, das die 32 empfangenen Pakete in eine Folge von Paketen auf der Grundlage des Aktivitätsbit 132 (Fig. 2) der Ausgangskopplerbezeichnung 133 und des Prioritätsfeldes 135 sortiert.
Das Sortiernetzwerk 140 kann entsprechend einer Beschreibung beispielsweise durch Batcher im US-Patent 3 428 946 ausgegeben am 18. Februar 1969 oder durch Huang et al. im US-Patent 4 516 238, ausgegeben am 7. Mai 1985 aufgebaut sein. Das Sortiernetzwerk 140 sortiert 32 empfangene Pakete entsprechend der numerischen Bedeutung eines "Sortierschlüssels" und erzeugt am Ausgang 32 parallele Pakete, wobei diejenigen Pakete mit dem Sortierschlüssel niedrigster Bedeutung an einem Ende (links) und diejenigen Pakete mit dem Sortierschlüssel höchster Bedeutung am anderen Ende (rechts) erscheinen. Zweckmäßig ist der Sortierschlüssel so gewählt, daß er nacheinander das Aktivitätsbit 132, die Ausgangskoppler- Bestimmung 133 und das Prioritätsfeld 135 (Fig. 2) umfaßt (es sei daran erinnert, daß ein Prioritätsfeld gleich 0 die höchste Priorität bedeutet). Die Verwendung dieses Sortierschlüssels erzeugt ein Ausgangsergebnis, bei dem aktive Pakete auf der linken und inaktive Pakete auf der rechten Seite angeordnet und die aktiven Pakete entsprechend ihrem Ausgangsbestimmungskoppler gruppiert und innerhalb jeder Gruppe entsprechend ihrer Priorität angeordnet sind (höchste Priorität links).
Die Ausgangspakete des Sortiernetzwerks 140 werden an ein Zusammenführnetzwerk 141 angelegt, das sie mit einer Vielzahl von Paketen von der Verzögerungseinheit 142 zusammenführt. Die Pakete von der Verzögerungseinheit 142 umfassen eine sortierte Folge von früher empfangenen Paketen, die nicht zu den Ausgängen der Sortiereinheit 104 übertragen worden sind und deren Ursprung weiter unten erläutert wird. Das Zusammenführnetzwerk 141 ist ein Sortiernetzwerk, das zwar größer ist aber auf die gleiche Weise wie das Sortiernetzwerk 140 aufgebaut ist und den gleichen Sortierschlüssel wie das Netzwerk 140 benutzt. Demgemäß erzeugt das Zusammenführnetzwerk 141 an seinen Ausgängen 143 eine Folge von Paketen, in der aktive, für den gleichen Ausgangskoppler bestimmte Pakete in Gruppen zusammengefaßt sind und innerhalb jeder Gruppe entsprechend ihrer Priorität geordnet sind, und aktive Pakete auf der rechten Seite gruppiert sind. Die Pakete an den Ausgängen 143 des Zusammenführnetzwerks 141 werden als Eingänge an ein Einfangnetzwerk 144 angelegt.
Das Einfangnetzwerk 144 nimmt Pakete, die für den gleichen Ausgangskoppler auf benachbarten Leitern 143 bestimmt sind, auf und gibt die vier Pakete höchster Priorität, die für jeden Ausgangskoppler bestimmt sind, an einen Ausgangskopplerwähler 145. Im einzelnen werden, wenn vier oder weniger Pakete für einen gegebenen Ausgangskoppler, beispielsweise 108 bestimmt sind, alle diese Pakete zum Ausgangskopplerwähler 145 übertragen und wenn mehr als vier Pakete für einen gegebenen Ausgangskoppler bestimmt sind, werden diejenigen vier Pakete, welche die höchste Priorität haben, zum Ausgangskopplerwähler ausgesendet. Die nicht zum Ausgangskopplerwähler 145 gegebenen Pakete stehen für eine Rückführung zu den Eingängen des Zusammenführnetzwerks 141 über die Verzögerungseinheit 142 zur Verfügung.
Das Einfangnetzwerk 144 wählt die Pakete für eine Übertragung zum Ausgangskopplerwähler 145 und sieht diejenigen Pakete oberhalb der gewählten Anzahl, falls sie vorhanden sind, für eine Rückführung aus. Dies kann durch die in Fig. 6 gezeigte Anordnung erreicht werden. Jeder Ausgangsport des Zusammenführnetzwerks 141 (außer dem letzten) ist mit einem ersten, ihm zugeordneten Eingang eines Komparators 160 sowie mit einem zweiten Eingang eines Komparators 160 verbunden, der dem benachbarten Ausgang des Zusammenführnetzwerks 141 in Richtung zunehmenden Wertes des Sortierschlüssels (nach rechts) zugeordnet ist. Der letzte Ausgang des Zusammenführnetzwerks 141 ist nur mit dem ihm zugeordneten Komparator 160 verbunden. Der dem ersten (am weitesten links liegenden) Ausgang des Zusammenführnetzwerks 141 zugeordnete Komparator besitzt ebenfalls nur einen Eingang. Der andere Eingang ist auf nur "1"-Werte festgelegt, um ein Ausgangssignal "0" sicherzustellen (natürlich kann ein Ausgangssignal "0" auch ohne Verwendung eines Komparators durch Verdrahtung erzielt werden). Entsprechend dieser Verbindungslösung ist beispielsweise der zweite Ausgang des Zusammenführnetzwerks 141, nämlich die Leitung 161, mit dem Komparator 160, markiert B und dem Komparator 160, markiert C, verbunden. Der dritte Ausgangsport des Zusammenführnetzwerks 141, die Leitung 162, ist mit dem Komparator 160, markiert C, sowie dem Komparator 160, markiert D, verbunden.
Das Ausgangssignal jedes Komparators 160 ist entweder eine "1" oder eine "0". Es ist eine "1", wenn das Ausgangskopplerfeld 133 des an den Komparator angelegten Pakets ebenfalls eine "1" ist und im anderen Fall immer eine "0". Der Komparator 160 kann mit Exklusiv-ODER-Gattern und einem Flipflop aufgebaut werden. Unter Ansprechen auf einen Satz von Ausgangskopplerbezeichnungen
0, 0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6...
liefern die Komparatoren den Ausgangssignalsatz
0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1...
Die zweite Schicht im Einfangnetzwerk gemäß Fig. 6 ist ein Satz von UND-Gattern 166 und Puffern 164. Wiederum ist ein Puffer 164 jedem Ausgang des Zusammenführnetzwerks 141 sowie einem entsprechenden UND-Gatter 166 zugeordnet. Der Puffer 164 verzögert das Ausgangssignal des Zusammenführnetzwerks 141 und liefert das verzögerte Paket an eine Logikschaltung 167. Jedes Gatter 166 ist mit ihrem zugeordneten Komparator und einer festen Anzahl von vorher benachbarten Komparatoren verbunden. Die Gesamtzahl von Eingängen jedes UND-Gatters 166 ist gleich der Anzahl von Paketen, die durch jede Sortiereinheit, beispielsweise 104, gleichzeitig an einen Ausgangskoppler, beispielsweise 108, angelegt werden können. In Fig. 4 ist diese Anzahl gleich "4", und entsprechend ist jedes UND-Gatter 166 mit seinem zugeordneten Komparator und drei vorhergehenden Komparatoren (wenn diese vorhanden sind) verbunden. Beispielsweise ist das UND-Gatter 166, markiert D, mit Ausgängen der Komparatoren A, B, C und D verbunden. Die Größe des Puffers 164 ist so gewählt, daß sie mit dem Vergleichsergebnis der Komparatoren 160 zusammenfällt. Zu diesem Zeitpunkt ist das Ausgangssignal des UND-Gatters 166 eine "1" nur dann, wenn die beiden den jeweiligen Komparatoren zugeführten Adressen gleich sind. Dieses Signal wird zusammen mit dem Paketsignal am Ausgang des Puffers 164 an die Logikschaltung 167 gegeben.
Für den oben benutzten Satz von Signalen bilden die Ausgänge der UND-Gatter 166 den Signalsatz
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0.
Die einzige "1" in dem obigen Satz ist dem fünften Paket zugeordnet, das mit dem Ausgangskoppler 4 verbunden werden will. Das fünfte Paket ist nicht für eine Übertragung zum Ausgangswähler 145 ausgewählt und für eine Rückführung verfügbar gemacht. Die Logikschaltung 167 spricht auf eine "0" vom UND-Gatter 166 durch Weiterführen des Pakets vom Puffer 164 zu einem Sortierer 168 und auf eine "1" vom UND-Gatter 166 durch Weiterführen des Pakets zur Verzögerungsschaltung 142 über einen Leiter 169 an. Die Logikschaltungen 167 nehmen Pakete in der gleichen Reihenfolge an, wie sie das Zusammenführnetzwerk 141 verlassen, d.h. sie sind in einer Folge auf der Grundlage der Ausgangskopplerbezeichnung gruppiert und anhand der Priorität in jeder Gruppe angeordnet (von links nach rechts). Demgemäß werden die am weitesten links stehenden vier Pakete (höchster Priorität) jeder Gruppe zum Sortierer 168 übertragen, während die am weitesten rechts stehenden Pakete jeder Gruppe (niedrigste Priorität), dann wenn sie vorhanden sind, zurückgeführt werden. Der Sortierer 168 sortiert die Pakete von den Logikschaltungen 167 in eine Folge auf der Grundlage der Ausgangskopplerbezeichnung, um aufeinander folgende Pakete auf benachbarte Ausgangswege zu bringen, und überträgt sie zum Ausgangswähler 145.
Die Anzahl der tatsächlich zurückgeführten Pakete ist Auslegungssache, wodurch die Kosten und die Güte der Sortiereinheit 104 beeinflußt werden. Eine Rückführung weniger Pakete hält die Verzögerungs-, Zusammenführ- und Einfangnetzwerke klein, was bedeutet, daß eine wesentliche Anzahl von Paketen durch das Einfangnetzwerk 144 fallengelassen wird. Alternativ verringert die Rückführung einer großen Zahl von Paketen die Anzahl der fallengelassenen Pakete, erhöht aber die Kosten und Kompliziertheit der Verzögerung-, Zusammenführ- und Einfangnetzwerke, da jedes dieser Netzwerke eine größere Zahl von Paketen erfassen muß. Die Verzögerungseinheit 142 kann so aufgebaut sein, daß sie diese Konstruktionsauswahl durch Auswahl von Paketen für die Rückführung verwirklicht.
Der Ausgangskopplerwähler 145 spricht auf Ausgangskopplerbezeichnungen an und führt empfangene Pakete zu ihren Ausgangsports. Die Ausgänge des Ausgangskopplerwählers 145 sind mit jedem Ausgangsstufenkoppler in Gruppen von vier verbunden. Jede Gruppe ist entsprechend der Darstellung in Fig. 4 mit einem Ausgangsstufenkoppler verbunden. Die am weitesten links liegenden vier Ausgänge des Kopplerwählers 145 sind mit dem Ausgangskoppler 108 und die am weitesten rechts liegenden vier Ausgänge des Ausgangskopplerwählers sind mit dem Ausgangskoppler 115 verbunden. Der Ausgangskopplerwähler 145 spricht auf die Ausgangskopplerbezeichnung 133 jedes empf angenen Pakets an und führt das Paket zu einem der Ausgänge in einer mit dem bezeichneten Ausgangskoppler, beispielsweise 108, verbundenen Gruppe.
Das Vermittlungsnetzwerk gemäß Fig. 1 enthält acht Ausgangskoppler 108-115, die im wesentlichen identisch sind. Fig. 5 zeigt das Blockschaltbild des Ausgangskopplers 108 und stellt den Aufbau aller acht Ausgangskoppler 108-115 dar.
Der Ausgangskoppler 108 enthält ein Sortiernetzwerk 150, das vier Pakete von jeder der vier Sortiereinheiten 104-107 mittels der oben beschriebenen Arbeitsweise der Sortiereinheiten 104-107 und der Verbindungswege 116 auf. Die zum Ausgangskoppler 108 ausgesendeten Pakete enthalten alle eine Ausgangskopplerbezeichnung 133 (Fig. 2), die den Ausgangskoppler 108 definieren. Das Sortiernetzwerk 150 sortiert die empfangenen Pakete in aufsteigender Reihenfolge aufgrund des Ausgangsports, der in dem Ausgangsport fällt 134 (Fig. 2) des Pakets angegeben ist, sowie aufgrund der Paketpriorität.
Die sortierten Pakete werden an ein Zusammenführnetzwerk 151 gegeben, wo sie mit Paketen von einer Verzögerungseinheit 152 zusammengeführt werden. Die Ausgänge 153 des Zusammenführnetzwerks 151 enthalten die Pakete vom Sortiernetzwerk 150 und einer Verzögerungseinheit 152, wobei die Pakete in einer Folge entsprechend ihrem Bestimmungsausgangsport mit Paketen für die gleiche Bestimmung anhand ihrer Priorität angeordnet sind. Die Pakete sind über Nachrichtenwege 153 mit einem Einfangnetzwerk 154 verbunden. Dieses Netzwerk wählt die Pakete höchster Priorität, die für jeden der 16 Ausgangsport des Ausgangskopplers 108 bestimmt sind. Die gewählten Pakete werden an einen Ausgangsportwähler 155 angelegt, der als Expansionsnetzwerk arbeitet, um jedes Paket seinem Bestimmungsausgangsport zuzuführen. Die Pakete, die nicht zum Ausgangsportwähler 155 übertragen werden, werden zu den Eingängen der Verzögerungseinheit 152 für eine spätere Zusammenführung mit der neuen Folge von Paketen vom Sortiernetzwerk 150 zurückgeführt.

Claims

1. Paketwegführungsanordnung zur Wegführung von Paketen einschließlich von Bestimmungsinformationen mit einer Vielzahl von Ausgangskopplern (108, 115), die je eine Vielzahl von Ausgangsports (118) enthalten, um empfangene Pakete zu den Ausgangsports zu führen und einer Eingangseinrichtung (101), die die Pakete aufnimmt und unter Ansprechen auf deren Bestimmungsinformationen an die Vielzahl von Ausgangskopplern verteilt, dadurch gekennzeichnet, daß die Anordnung eine Vielzahl von Zwischeneinrichtungen (104- 107) aufweist, die so verbunden sind, daß jede Zwischeneinrichtung von der Eingangseinrichtung etwa die gleiche Anzahl von für jeden Ausgangskoppler bestimmten Paketen wie andere Zwischeneinrichtungen empfängt, und daß jede Zwischeneinrichtung eine Einrichtung (140, 141, 143, 144, 145) aufweist, die unter Ansprechen auf die Bestimmungsinformationen Paketgruppen mit einem gemeinsamen Ausgangskoppler identifiziert und diese Paketgruppen zu den Ausgangskopplern überträgt.

2. Anordnung nach Anspruch 1, bei der die Vielzahl von Zwischeneinrichtungen (104-107) n Zwischeneinrichtungen umfaßt und die Eingangseinrichtung eine Einrichtung (120-127) enthält, die die von der Eingangseinrichtung empfangenen Pakete in eine Folge entsprechend den durch die Bestimmungsinformationen definierten Bestimmungen der Pakete ordnet, sowie eine Einrichtung zu Verbindung jedes n-ten Pakets der Folge mit der gleichen Zwischeneinrichtung der n Zwischeneinrichtungen.

3. Anordnung nach Anspruch 1, bei der die Vielzahl von Zwischeneinrichtungen (104-107) n Zwischeneinrichtungen aufweist und die Eingangseinrichtung umfaßt:

eine Vielzahl von Sortiereinheiten (120-127), die je eine vorbestimmte Vielzahl der von der Eingangseinrichtung empfangenen Pakete in eine durch die Bestimmungsinformationen definierte Folge entsprechend der Bestimmung der empfangenen Pakete ordnet, und

eine Einrichtung zur Verbindung jedes n-ten Pakets der Folge von Paketen mit der gleichen Zwischeneinrichtung der n- Zwischeneinrichtungen (104-107).

4. Anordnung nach Anspruch 1, bei der jede Zwischeneinrichtung (104) aufweist:

eine Zwischensortiereinheit (140-144), die unter Ansprechen auf die Bestimmungsinformationen, die an sie sortierten Pakete in eine Vielzahl von Gruppen von Paketen sortiert, deren Zahl gleich der Zahl der Ausgangskoppler ist, und

eine Verbindungseinrichtung (145), die mit jedem Ausgangskoppler (108, 115) eine andere Gruppe von Paketen verbindet.

5. Anordnung nach Anspruch 4, bei der jede Verbindungseinrichtung (145) eine vorbestimmte Anzahl von Paketen mit jedem Ausgangskoppler (108, 115) verbindet und jede Zwischensortiereinheit (140-144) eine Einrichtung (144) zur Begrenzung der Anzahl von Paketen in jeder Gruppe auf die vorbestimmte Anzahl umfaßt.

6. Anordnung nach Anspruch 5, bei der jedes Paket eine die relative Wichtigkeit des Pakets definierende Prioritätsinformation umfaßt und die Einrichtung (144) zur Begrenzung der Anzahl von Paketen unter Ansprechen auf die Prioritätsinformation Pakete zur Einbeziehung in jede der Gruppen auswählt.

7. Anordnung nach Anspruch 1, bei der jedes Paket eine Prioritätsinformation enthält und jede Zwischeneinrichtung (104) umfaßt:

eine Zwischensortiereinrichtung (140), die unter Ansprechen auf die Bestimmungsinformationen und die Prioritätsinformation die an sie verteilten Pakete in eine Vielzahl von Gruppen von Paketen sortiert, deren Zahl gleich der Anzahl von Ausgangskopplern ist und die innerhalb jeder Gruppe entsprechend der Priorität angeordnet sind,

eine Sperreinrichtung (144) zur Trennung jeder Gruppe von Paketen in eine erste und eine zweite Untergruppe, derart, daß die Anzahl von Paketen in der zweiten Untergruppe null ist, solange die Anzahl von Paketen in der ersten Untergruppe kleiner oder gleich einer vorbestimmten Zahl ist und die Priorität von Paketen in der ersten Untergruppe nicht niedriger als die höchste Priorität von Paketen in der zweiten Untergruppe ist, und

eine Einrichtung (145) zur Verbindung der ersten Untergruppe mit den Ausgangskopplern.

8. Anordnung nach Anspruch 7 mit einer Einrichtung (142) zur Verzögerung der Pakete der zweiten Untergruppe und zur späteren Weiterführung eines Pakets der zweiten Untergruppe zu einem der Ausgangskoppler.

9. Anordnung nach Anspruch 1, bei der die Ausgangskoppler aufweisen:

eine Einrichtung (150), die unter Ansprechen auf die Bestimmungsinformationen die Paketgruppen auf der Grundlage der Ausgangsport-Bestimmungen in eine Folge von Paketen einordnen, und

eine Einrichtung (154, 155) zur Weiterleitung der Pakete der Folge an die Ausgangsports.

10. Anordnung nach Anspruch 9, bei der die Einrichtung zur Weiterleitung der Pakete einer Einrichtung (154) umfaßt, die die Weiterleitung eines gewählten Pakets zu einem der Ausgangsports sperrt, der die Bestimmung von mehr als einem Paket in der Folge von Paketen ist.

11. Anordnung nach Anspruch 10 mit einer Rückübertragungseinrichtung (152, 151) zur Verzögerung des gewählten Pakets und zu dessen späterer Weiterleitung an einen der Ausgangsports.

12. Anordnung nach Anspruch 10, bei der jedes Paket eine Prioritätsinformation enthält und die Sperreinrichtung (154) eine Einrichtung umfaßt, die die Weiterleitung eines Pakets mit der niedrigeren Priorität von zwei für den gleichen Ausgangsport bestimmten Paketen besitzt, sperrt.

13. Paketwegführungsanordnung zur Wegführung von Paketen, die Bestimmungsinformationen enthalten, mit einer Verteilungseinrichtung (101) zur Aufnahme einer Vielzahl von Paketen, die eine Vielzahl von Eingangssortiereinrichtungen (120-127) enthält, welche je auf die Bestimmungsinformationen einer vorbestimmten Anzahl der Pakete ansprechen und die vorbestimmte Anzahl von Paketen in einer Eingangsfolge sortieren, und

einer Vielzahl von Ausgangskopplern (108-115), wobei jeder Ausgangskoppler eine Vielzahl von Ausgangsports (118), eine Einrichtung (150), die unter Ansprechen auf die Bestimmungsinformationen die empfangenen Paketgruppen auf der Grundlage der Ausgangsport-Bestimmungen der Pakete in einer Ausgangsfolge bringt, und eine Einrichtung (155) aufweist, die die Pakete der Ausgangsfolge an die Ausgangsport (118) weiterleitet,

dadurch gekennzeichnet, daß

die Anordnung eine Vielzahl von Zwischensortiereinrichtungen (104-107) und eine Verbindungseinrichtung (103) aufweist, die die Pakete aus jeder Eingangsfolge von Paketen an die Zwischensortiereinrichtungen anschaltet, derart, daß jede Zwischensortiereinrichtung etwa die gleiche Anzahl der für jeden Ausgangskoppler bestimmten Pakete wie andere Zwischensortiereinrichtungen empfängt, und

daß jede Zwischensortiereinrichtung eine Einrichtung (140, 143, 144, 145) enthält, die unter Ansprechen auf die Bestimmungsinformationen Paketgruppen mit einer gemeinsamen Ausgangskoppler-Bestimmung identifiziert, und einer Einrichtung zur Übertragung jeder Paketgruppe an einen der Ausgangskoppler der gemeinsamen Ausgangskoppler-Bestimmung.