DE3842762C2 - - Google Patents

Description

Die Erfindung betrifft ein Hochgeschwindigkeits-Datenpaket­ vermittlungssystem nach dem Oberbegriff von Anspruch 1.

Datenpaketvermittlungsnetzwerke werden bei der Datenkommu­ nikation vielfältig verwendet, da sie Kommunikationskanal- Betriebsmittel wirtschaftlich verwenden. Bei ihnen ist eine Verbindung der Sende- und Empfangsstationen nur dann erfor­ derlich, wenn Daten tatsächlich übertragen werden, und nicht während der Leerlaufzeiten zwischen den Übertragungen. Dabei werden Daten in Datenpakete übertragen, die jeweils die Adresse der Empfangsstation enthalten. Die Daten­ paketvermittlung im Netzwerk muß in der Lage sein, die Adresse in jedem Datenpaket lesen und das Datenpaket schnell an den richtigen Bestimmungsort weiterleiten zu können.

Die Druckschrift DE 37 28 805 A1 beschreibt eine Daten­ paketvermittlung mit einer Vielzahl von Eingangsleitungen und Ausgangsleitungen, die jeweils mit einer Eingangsschaltung und einer Ausgangsschaltung verbunden sind, welche mit Durchlaufspeichern versehen sind. Die Daten werden im Time- Sharing-Betrieb (Multiplexer) von den Eingangsschaltungen in einen Datenspeicher geschrieben, der als Pufferspeicher ausgelegt ist. Von dort werden die Daten über einen Demulti­ plexer an die Ausgangsschaltungen weitergegeben. In einer speziellen Ausführungsform können mehrere dieser Daten­ paketvermittlungseinheiten stufenweise in einer Kaskade ange­ ordnet sein, um ein größeres Vermittlungsnetzwerk zu bil­ den. Zwischen zwei hintereinanderfolgenden Datenpaketver­ mittlungseinheiten kann dann ein Steuerkanal vorhanden sein, über den Signale laufen, die von einer Quittierungs­ steuerung verarbeitet werden, um die Datenübertragung von einer Vermittlungseinheit zur nächsten zu steuern.

Bei einem bekannten Aufbau für eine Hochgeschwindigkeits- Datenpaketvermittlung wird ein Selbstleit-Vermittlungsnetz­ werk verwendet, das eine Vielzahl 2×2-Koppelpunkt-Ver­ mittlungselementen aufweist, die entsprechend den einzelnen Bits in der Datenpaketadresse betrieben werden. Die Ver­ mittlungs- bzw. Koppelelemente sind so miteinander verbun­ den, daß gewährleistet ist, daß ein Datenpaket automatisch an die richtige Adresse weitergeleitet wird, vorausgesetzt, daß keine Kollisionen mit anderen Datenpaketen auf dem Weg auftreten.

Ein Problem bei einem derartigen Datenpaketvermittlungsauf­ bau besteht darin, daß dann, wenn Kollisionen auftreten, eines der zwei miteinander kollidierenden Datenpakete an die falsche Adresse weitergeleitet wird. Eine bekannte Lösung dieses Problems besteht darin, ein Sortier- oder Unterbrechungsnetzwerk vorzusehen, das die Datenpakete sor­ tiert oder in anderer Weise vorverarbeitet, bevor sie in das Selbstleit-Vermittlungsnetzwerk eintreten. Auf diese Weise ist es möglich zu gewährleisten, daß die für verschie­ dene Adressen bestimmten Datenpakete richtig weitergeleitet werden, ohne daß sie miteinander kollidieren. Dieses Schema löst jedoch nicht das Problem von Mehrfach-Datenpaketen, die die gleiche Bestimmungsadresse haben. Derartige Daten­ pakete kollidieren immer noch, was zur Folge hat, daß einige von ihnen zur falschen Adresse weitergeleitet werden.

Die Aufgabe der Erfindung besteht darin, ein Datenpaketvermittlungssystem zu schaffen, das das Problem der Kollisionen wirkungsvoll löst und eine Datenpaketver­ mittlung hoher Qualität ermöglicht, wobei sichergestellt wird, daß jedes Datenpaket die richtige Adresse erreicht.

Diese Aufgabe wird durch das Datenpaketvermittlungssystem nach Anspruch 1 gelöst.

Das erfindungsgemäße Datenpaketvermittlungssystem weist auf: eine Vielzahl von externen Ausgangsanschlüssen, eine Vielzahl von externen Eingangsanschlüssen zum Empfang von Eingangsdatenpaketen, wobei jedes Datenpaket die Adresse eines externen Ausgangsanschlusses enthält, ein Selbstleit- Vermittlungsnetzwerk, eine Vielzahl von Warteschlangenein­ richtungen, von denen eine jeweils mit dem externen Ein­ gangsanschluß zum Empfang der Eingangsdatenpakete von den externen Eingangsanschlüssen, zum vorübergehenden Speichern derselben in FIFO (first-in-first-out)-Warteschlangen, zum Senden der vorderen Datenpakete in diesen Warteschlangen zum Selbstleit-Vermittlungsnetzwerk und zum Löschen der vorderen Datenpakete von diesen Warteschlangen in Abhängig­ keit von den Quittungssignalen, sowie eine Vielzahl von Adressenprüfeinrichtungen, von denen jeweils eine mit jedem externen Ausgangsanschluß verbunden ist, zum Empfang der Datenpakete von dem Selbstleit-Vermittlungsnetzwerk, zum Prüfen der Adressen und, wenn ein Paket zur richtigen Adresse weitergeleitet wurde, zum Senden desselben zu dem entsprechenden externen Ausgangsanschluß und zur Rückgabe eines Quittungssignals über das Selbstleit-Vermittlungs­ netzwerk an die Warteschlangeneinrichtungen.

Eine Ausführungsform der Erfindung wird anhand der Zeich­ nungen näher beschrieben. Es zeigt

Fig. 1 eine schematische Darstellung einer Aus­ führungsform der Erfindung;

Fig. 2A bis 2D schematische Darstellungen zur Erläute­ rung der Betriebsweise der Koppelelemente in Fig. 1.

Eine Ausführungsform der Erfindung wird anhand der schema­ tischen Darstellung in Fig. 1 beschrieben. Fig. 1 zeigt ein neues Datenpaketevermittlungssystem, das ein Selbstleit- Vermittlungsnetzwerk 1 mit einer Vielzahl von Eingangsan­ schlüssen 1-10 bis 1-17 und einer Vielzahl von Ausgangsan­ schlüssen 1-20 bis 1-27, eine Vielzahl von externen Ein­ gangsanschlüssen 10-0 bis 10-7, eine Vielzahl von externen Ausgangsanschlüssen 20-0 bis 20-7, eine Vielzahl von FIFO (first-in-first-out)-Warteschlangeneinrichtungen 30-0 bis 30-7, die zwischen den externen Eingangsanschlüssen 10-0 bis 10-7 und den Eingangsanschlüssen 1-10 bis 1-17 des Selbstleit-Vermittlungsnetzwerks 1 angeordnet sind, und eine Vielzahl von Adressenprüfeinrichtungen 40-0 bis 40-7 aufweist, die zwischen den Ausgangsanschlüssen 1-20 bis 1-27 des Selbstleit-Vermittlungsnetzwerks 1 und den exter­ nen Ausgangsanschlüssen 20-0 bis 20-7 angeordnet sind. Das Selbstleit-Vermittlungsnetzwerk 1 weist 2×2-Koppelpunkt- Vermittlungselemente 1-1 bis 3-4 auf, die entsprechend den individuellen Bits in der Datenpaketadresseninformation autonom arbeiten. Die Vermittlungs- bzw. Koppelelemente 1-1 bis 1-4 arbeiten entsprechend dem niederwertigsten Bit der Datenpaketadresse, die Koppelelemente 2-1 bis 2-4 ent­ sprechend dem nächstwertigen Bit und die Koppelelemente 3-1 bis 3-4 entsprechend dem höchstwertigen Bit. In anderen Worten, die Koppelelemente sind in einer Vielzahl von Stu­ fen angeordnet und sie nehmen in den entsprechenden Stufen einen der Vermittlungszustände an, der dem entsprechenden Bit der Adresseninformation des ihm eingegebenen Daten­ pakets entspricht.

Die Art und Weise, in der die Koppelelemente 1-1 bis 3-4 arbeiten, ist in den Fig. 2A bis 2D dargestellt. Jedes Koppelelement weist zwei Eingabeklemmen und zwei Ausgabe­ klemmen auf, die als obere und untere Eingabe- und Ausgabe­ klemmen bezeichnet werden. Wenn ein Datenpaket an einer der beiden Eingabeklemmen eines Koppelelements empfangen wird, liest das Koppelelement das relevante Datenpaketadres­ senbit und nimmt einen Zustand an, bei dem diese Eingabe­ klemme mit der oberen Ausgangsklemme verbunden ist, um das Datenpaket zur oberen Ausgangsklemme weiterzuleiten, wenn das Bit eine "0" ist, oder nimmt einen Zustand an, bei dem diese Eingabeklemme mit der unteren Ausgabeklemme verbunden ist, um das Datenpaket zur unteren Ausgabeklemme weiterzu­ leiten, wenn das Bit eine "1" ist. Wenn das Koppelelement nur ein Datenpaket empfängt, kann es das Datenpaket immer auf diese Weise weiterleiten. Wenn das Koppelelement am Eingang zwei Datenpakete gleichzeitig empfängt und wenn diese Datenpakete im relevanten Adressenbit sich unterschei­ den, so arbeitet das Koppelelement wie in Fig. 2A und Fig. 2B, so daß beide Datenpakete zur richtigen Ausgangsklemme weitergeleitet werden. Wenn die beiden Datenpakete identi­ sche Werte in dem relevanten Adressenbit haben, tritt eine Bedingung auf, die als Kollision bezeichnet wird. Dabei ist eine der beiden Eingangsklemmen mit der richtigen Aus­ gangsklemme verbunden, so daß eine der Eingangsklemmen mit der richtigen Ausgangsklemme verbunden ist, während die andere Eingangsklemme mit der falschen Ausgangsklemme ver­ bunden ist, so daß eines der eingegebenen Datenpakete zur falschen Ausgangsklemme weitergeleitet wird, wie es in Fig. 2C und Fig. 2D dargestellt ist. In Fig. 2C und Fig. 2D wird das untere Datenpaket zur richtigen Ausgangsklemme und das obere Datenpaket zur falschen Ausgangsklemme weiter­ geleitet.

Jedes Koppelelement behält den Zustand, in den es durch ein Adressenbit eines Datenpakets gebracht wurde, solange bei, bis ein weiteres Datenpaket empfangen wird. Die Koppel­ elemente sind zu einer Zweirichtungs-Übertragung der Si­ gnale in der Lage. So ermöglicht das Koppelelement insbe­ sondere nicht nur die Weiterleitung der Datenpakete in eine Richtung von den Eingabe- zu den Ausgabeklemmen, sondern auch den Durchgang von Quittungssignalen in die andere Richtung von den Ausgangs- zu den Eingangsklemmen, was spä­ ter beschrieben wird.

Die Koppelelemente 1-1 bis 3-4 sind entsprechend dem in Fig. 1 dargestellten wohl bekannten Selbstleit-System mit­ einander verbunden. Daraus ist leicht ersichtlich, daß die­ ses Verbindungssystem - mit Ausnahme von Kollisionen - ein Datenpaket immer zum richtigen Ausgangsanschluß weiterlei­ tet.

Die Warteschlangeneinrichtungen 30-0 bis 30-7 arbeiten wie folgt. Jede Warteschlangeneinrichtung 30-0 bis 30-7 weist eine Speichereinrichtung zum vorübergehenden Speichern von Datenpaketen in einer FIFO-Warteschlange auf. Wenn ein Datenpaket von einer externen Eingangsklemme empfangen wird, wird es mit dem hinteren Ende der Warteschlange ver­ bunden. Bei einem Taktsignal TS, das wiederholt, z. B. periodisch von einer Steuereinrichtung 50 erzeugt wird, wird das Datenpaket vorne in der Warteschlange, wenn diese nicht leer ist, zum Selbstleit-Vermittlungsnetzwerk 1 gesen­ det, das es zu einem der Ausgangsanschlüsse 1-20 bis 1-27 und damit zu den Adressenprüfeinrichtungen 40-0 bis 40-7 weiterleitet. Das gleiche Taktsignal TS wird allen Warte­ schlangeneinrichtungen 30-0 bis 30-7 zugeführt, so daß sie alle ihre Datenpakete gleichzeitig aussenden. Nach dem Aus­ senden eines Datenpakets kann eine Warteschlangeneinrich­ tung ein Quittungssignal AS über das Selbstleit-Vermitt­ lungsnetzwerk 1 von einer der Adressenprüfeinrichtungen 40-0 bis 40-7 empfangen. Wenn eine Warteschlangeneinrich­ tung ein solches Quittungssignal AS empfängt, löscht sie das vordere Datenpaket in seiner Warteschlange. Wenn eine Warteschlangeneinrichtung kein solches Quittungssignal empfängt, löscht sie ihr vorderes Datenpaket nicht, so daß das gleiche Datenpaket wieder mit dem nächsten Taktsignal TS ausgesendet wird.

Jede der Adressenprüfeinrichtungen 40-0 bis 40-7 prüft die Adresse des von dem Selbstleit-Vermittlungsnetzwerk 1 empfangenen Datenpakets. Wenn ein Datenpaket an die rich­ tige Adresse weitergeleitet wurde, d. h. an die Adressen­ prüfeinrichtung, die mit dem externen Ausgangsanschluß der Adresse des Datenpakets verbunden ist, so sendet die Adres­ senprüfeinrichtung es an den externen Ausgangsanschluß und gibt ein Quittungssignal AS über das Selbstleit-Vermitt­ lungsnetzwerk 1 zurück, wodurch angezeigt wird, daß das Datenpaket richtig empfangen wurde. Da zu diesem Zeitpunkt die Koppelelemente des Selbstleit-Vermittlungsnetzwerks 1 sich immer noch im gleichen Zustand befinden, verfolgt das Quittungssignal den Weg des Datenpakets rückwärts zu­ rück und erreicht die Warteschlangeneinrichtung (eine von 30-0 bis 30-7), von der das Datenpaket stammt. Wenn ein Datenpaket an eine falsche Adresse weitergeleitet wurde, gibt die Adressenprüfeinrichtung es nicht an den externen Ausgangsanschluß weiter und gibt auch kein Quittungssignal zurück. Das vordere Datenpaket in der Warteschlangeneinrich­ tung wird daher nicht gelöscht und es wird erneut übertra­ gen, wenn das nächste Taktsignal der Warteschlangeneinrich­ tung zugeführt wird.

Die Arbeitsweise dieses neuen Datenpaketvermittlungssystems wird für den Fall dargestellt, bei dem drei Datenpakete gleichzeitig eingegeben werden, wie es in Fig. 1 darge­ stellt ist. Ein erstes Datenpaket, das an den externen Aus­ gangsanschluß 20-7 (Binäradresse 111) adressiert ist, wird an dem externen Eingangsanschluß 10-5 empfangen. Ein zwei­ tes Datenpaket, das an den externen Ausgangsanschluß 20-5 (Binäradresse 101) adressiert ist, wird an dem externen Eingangsanschluß 10-7 empfangen. Ein drittes Paket, das auch an den externen Ausgangsanschluß 20-5 adressiert ist, wird am externen Eingangsanschluß 10-1 empfangen. Nun soll angenommen werden, daß sich keine weiteren Datenpakete im System befinden, so daß diese drei Pakete sofort nach vorne in den Warteschlangen in den Warteschlangeneinrichtungen 30-1, 30-5 und 30-7 sich bewegen und gleichzeitig an das Selbstleit-Vermittlungsnetzwerk 1 ausgesendet werden.

Das erste Datenpaket wird entlang des Wegs 2 über die Koppelelemente 1-3, 2-4 und 3-4 an die Adressenprüfeinrich­ tung 40-7 weitergeleitet, die ihre Adresse prüft und heraus­ findet, daß es den richtigen Bestimmungsort erreicht hat. Die Adressenprüfeinrichtung 40-7 sendet daher dieses Paket an den externen Ausgangsanschluß 20-7 und gibt ein Quit­ tungssignal - dargestellt durch die gestrichelte Linie in der Zeichnung - entlang des Wegs 2 zurück, um der Warte­ schlangeneinrichtung 30-5 anzuzeigen, daß das Datenpaket richtig empfangen wurde. Die Warteschlangeneinrichtung 30-5 löscht dann dieses Datenpaket von seiner Warteschlange und wird frei zum Aussenden eines weiteren Datenpakets zum nächsten Zeitpunkt.

In ähnlicher Weise wird das zweite Datenpaket auf den Weg 3 über die Koppelelemente 1-4, 2-4 und 3-2 zur Adressenprüf­ einrichtung 40-5 weitergeleitet. Da es die richtige Adresse erreicht, wird es an den externen Ausgangsanschluß 20-5 weitergeleitet und ein Quittungssignal wird an die Warte­ schlangeneinrichtung 30-7 zurückgegeben, die wiederum die­ ses Datenpaket von seiner Warteschlange löscht.

Das dritte Datenpaket wird entlang des Wegs 4 über die Koppelelemente 1-1 und 2-3 zum Koppelelement 3-2 weiterge­ leitet, wo es mit dem zweiten Datenpaket kollidiert. Das Ergebnis ist, daß das dritte Datenpaket zur falschen Adres­ se weitergeleitet wird. So wird es zu der Adressenprüfein­ richtung 40-1 weitergeleitet. Diese stellt die falsche Adresse fest und sendet dieses Datenpaket nicht zum exter­ nen Ausgangsanschluß 20-1 weiter und gibt auch kein Quit­ tungssignal zurück. Damit bleibt dieses Datenpaket in der Warteschlangeneinrichtung 30-1 und wird zum nächsten Zeit­ punkt ausgesendet.

Da ein Datenpaket so lange nicht gelöscht wird, bis es die richtige Adresse erreicht hat, wird jedes Datenpaket fort­ während ausgesendet, bis es den beabsichtigten Bestimmungs­ ort erreicht hat. Fehlgeleitete Datenpakete bleiben im Ver­ mittlungssystem, ohne daß sie entweder falsch weitergegeben werden oder verlorengehen. Das erfindungsgemäße Datenpaket­ vermittlungssystem vermeidet damit die Ineffektivität der bekannten Datenpaketvermittlungssysteme, bei denen fehlge­ leitete Datenpakete an den falschen externen Ausgangsan­ schluß abgegeben werden, wo sie aufgegeben werden und dem externen Eingangsanschluß erneut übertragen werden müssen. Das erfindungsgemäße Paketvermittlungssystem verbindet da­ mit hohe Vermittlungsgeschwindigkeit mit hoher Vermittlungs­ güte.

Der Schutzumfang der Erfindung ist nicht auf die oben be­ schriebene Ausführungsform beschränkt, sondern umfaßt auch Änderungen und Ausgestaltungen, die für den Fachmann ohne weiteres ersichtlich sind. So kann insbesondere das Selbst­ leit-Vermittlungsnetzwerk eine Konfiguration aufweisen, die von der in Fig. 1 dargestellten verschieden ist, und die Zahl der Eingangs- und externen Ausgangsanschlüsse kann variiert werden, wie es je nach der Größe des Paket­ vermittlungssystems erforderlich ist.

Claims (6)

1. Datenpaketvermittlungssystem, das aufweist
ein Vermittlungsnetzwerk (1) mit Eingangsklemmen (1-10 bis 1-17) und Ausgangsklemmen (1-20 bis 1-27), wobei das Ver­ mittlungsnetzwerk (1) autonom Datenpakete, die an irgendeinem der Eingangsklemmen (1-10 bis 1-17) empfangen werden, an die Ausgangsklemme (1-20 bis 1-27) gemäß einer Adres­ seninformatioin des Datenpakets weiterleiten kann,
eine Vielzahl von externen Ausgangsanschlüssen (20-0 bis 20-7),
eine Vielzahl von externen Eingangsanschlüssen (10-0 bis 10-7) zum Empfang von Datenpaketen, wobei jedes Datenpaket eine einen externen Ausgangsanschluß bezeichnende Adreß­ information aufweist,
eine Vielzahl von Speichereinrichtungen (30-0 bis 30-7), von denen jeweils eine mit jeweils einem externen Eingangs­ anschluß (10-0 bis 10-7) verbunden ist, wobei jeweils eine der Eingangsklemmen (1-10 bis 1-17) des Vermittlungsnetz­ werkes (1) mit jeweils einer der Speichereinrichtungen (30-0 bis 30-7) verbunden ist und über die jeweilige Speicher­ einrichtung mit dem jeweiligen äußeren Eingangsanschluß verbunden ist,
wobei jede der Speichereinrichtungen Datenpakete vom je­ weils zugeordneten externen Eingangsanschluß erhält, die Datenpakete kurzzeitig speichert und die gespeicherten Datenpakete der jeweils zugeordneten Eingangsklemme des Ver­ mittlungsnetzwerks (1) zuführt,
gekennzeichnet durch
eine Vielzahl von Adreßprüfeinrichtungen (40-0 bis 40-7), von denen jeweils eine mit jeweils einem der externen Aus­ gangsanschlüsse verbunden ist,
wobei jeweils eine der Ausgangsklemmen des Vermittlungs­ netzwerks mit jeweils einer der Adreßprüfeinrichtungen verbunden ist und über die jeweilige Adreßprüfeinrichtung mit dem jeweils zugeordneten äußeren Ausgangsanschluß ge­ koppelt ist, und
wobei jede der Adreßprüfeinrichtungen (40-0 bis 40-7) Datenpakete von dem Vermittlungsnetzwerk (1) erhält, die Adressen der Datenpakete überprüft und, wenn ein erhal­ tenes Datenpaket eine Adresseninformation hat, die den je­ weils verbundenen externen Ausgangsanschluß bezeichnet, das Datenpaket an den jeweils verbundenen Ausgangsanschluß wei­ tergibt und ein Quittungssignal (AS) über das Vermittlungs­ netzwerk zu der Speichereinrichtung zurückgibt, von der das Datenpaket über das Vermittlungsnetzwerk der Adreßprüfein­ richtung zugeführt worden ist, und
die Speichereinrichtung die gespeicherten Datenpakete in Antwort auf das zugeführte Quittungssignal (AS) löscht.

2. System nach Anspruch 1, dadurch gekennzeichnet, daß es zusätzlich eine Steuereinrichtung (50) aufweist, die wiederholt ein Taktsignal (TS) an alle Speichereinrichtungen (30-0 bis 30-7) abgibt, wobei die Speichereinrichtungen entsprechend dem Taktsignal die gespeicherten Datenpakete zum Vermittlungs­ netzwerk (1) übertragen.

3. System nach Anspruch 2, dadurch gekennzeichnet, daß jede Speichereinrichtung (30-0 bis 30-7) eine Warteschlangeneinrichtung aufweist, die die Datenpakete von den externen Eingangsanschlüssen (10-0 bis 10-7) in FIFO-Warteschlangen speichert, die vorderen Datenpakete in der Warteschlange entsprechend dem Taktsignal (TS) an das Vermittlungsnetzwerk (1) sendet und das vordere Datenpaket von den Warteschlangen in Abhängigkeit vom Quit­ tungssignal (AS) löscht.

4. System nach Anspruch 1, dadurch gekennzeichnet, daß das Vermittlungsnetzwerk (1) eine Vielzahl von Vermittlungs­ elementen (1-1 bis 3-4) aufweist, die jeweils autonom einen ihrer Vermittlungszustände entsprechend der Adresseninformation des eingegebenen Datenpakets annehmen, diesen Zustand so lange aufrechterhalten, bis ein weiteres Datenpaket eintrifft und in der Lage sind, einen Durchgang der Datenpakete in die eine Richtung und den Durchgang der Quittungssignale (AS) in die entgegengesetzte Richtung zu ermöglichen.

5. System nach Anspruch 4, dadurch gekennzeichnet, daß die Vermittlungselemente (1-1 bis 3-4) im Vermittlungsnetzwerk (1) in einer Vielzahl von Stufen angeordnet sind und jedes Vermittlungselement in den entsprechenden Stufen in den Ver­ mittlungszustand übernimmt, der dem entsprechenden Bit der Adresseninformation der eingegebenen Datenpakete entspricht.

6. System nach Anspruch 1, dadurch gekennzeichnet, daß das Vermittlungsnetzwerk (1) eine Übertragung des Quittungs­ signals (AS) von der jeweiligen Adreßprüfeinrichtung (40-0 bis 40-7) über einen Weg bewerkstelligt, über den das Daten­ paket, das von der Adreßprüfeinrichtung entgegengenommen worden ist, zugeführt worden ist.