In der Veröffentlichung Weighted Arbitration Algorithms with Priorities for Input-Queued Switches with 100% Throughput"von R. Schoenen, G. Post, G. Sander, Broadband Switching Symposium'99, werden verschiedene, gewichtete Vermittlungsalgo- rithmen einer Paketvermittlungsvorrichtung verglichen. Die Vermittlungsalgorithmen versuchen mit unterschiedlichen Vermittlungsschritten eine Kollision mehrerer für den selben Ausgangsport der Paketvermittlungsvorrichtung bestimmter Pakete zu verhindern und daraus resultierenden Datenverlust oder Verzögerung zu reduzieren.

Die Veröffentlichung befaßt sich mit einer anhand einer Gewichtung arbeitender Berechnungsvorschrift zur Verknüpfung von Eingangs-und Ausgangsports der Vermittlungsvorrichtung. Dabei werden die Gewichtungen der Verknüpfungen für eine Vermittlung eines Eingangsports mit einem Ausgangsport in einer Zustandsmatrix repräsentiert. Die Zeilen und Spalten der Zustandsmatrix entsprechen den Eingangs-und Ausgangsport der Vermittlungseinrichtung für Datenpakete. In jeder Spalte der Matrix wird eine maximal große Gewichtung ausgewählt und als akzeptierte Verknüpfung zwischen einem Eingangs-und Ausgangsport markiert. Im weiterem Verlauf der Berechnung wird der ausgewählte Eingangsport bzw. die dem Eingangsport entsprechende Zeile der Zustandsmatrix nicht weiter berücksichtigt. Die markierten Verknüpfungen werden in einer Entscheidungsmatrix festgehalten, anhand der die Verknüpfungen zwischen den Eingangs- und Ausgangsport erstellt werden.

Der Erfindung liegt die Aufgabe zugrunde, eine schnell berechnete Vermittlung von Datenpaketen innerhalb einer Paketvermittlungsvorrichtung zu ermöglichen.

Die Aufgabe wird durch eine Paketvermittlungsvorrichtung mit mehreren Ein- und Ausgangsports und wenigstens einer Vermittlungseinheit bestehend aus einer Koppelmatrix und einer Zuteileinheit zur Steuerung der Koppelmatrix, wobei in der Zuteileinheit eine Zustandsmatrix mit Elementen vorgesehen ist, die jeweils eine Gewichtung einer Verknüpfung zwischen einem Eingangsport und einem Ausgangsport der Paketvermittlungsvorrichtung repräsentieren und deren Zeilen jeweils einem Eingangsport und Spalten jeweils einem Ausgangsport der Paketvermittlungsvorrichtung entsprechen, und die Zuteileinheit mittels eines Vektors zur Anordnung der Spalten in Abhängigkeit von einem jeder Spalte zugeordneten Element des Vektors vorgesehen ist, gelöst.

Eine Paketvermittlungsvorrichtung besteht aus mehreren Leitungseinheiten (Line Card) und mehreren Vermittlungseinheiten (Switch Card). Zu Komponenten einer Leitungseinheit zählt als wesentliche Komponente eine Portsteuerung. Jede Portsteuerung ist mit mehreren parallel arbeitenden Vermittlungseinheiten verbunden und hat die Aufgabe an der Paketvermittlungsvorrichtung ankommende, zu vermittelnde Pakete nach Priorität und gewünschten Ausgangsport der Paketvermittlungsvorrichtung in Warteschlangen anzu- ordnen.

Jede Vermittlungseinheit der Paketvermittlungsvorrichtung besteht aus einer Koppelmatrix (Crosspoint Matrix) und einer Zuteileinheit (Arbiter). Die Konfiguration der Koppelmatrix werden in regelmäßigen Zeitabständen durch die Zuteileinheit mittels einer Berechnungsvorschrift neu bestimmt und somit neu Verknüpfungen zwischen Ein-und Aus- gangsport der Paketvermittlungsvorrichtung für die Vermittlung der Pakete erstellt.

Eine Zustandsmatrix der Paketvermittlungsvorrichtung enthält mehrere Elemente, die eine Gewichtung jeder Verknüpfung eines Eingangsports mit einem Ausgangsport repräsentieren. Die Gewichtung werden durch die Portsteuerung generiert, somit kann die Portsteuerung die Zuteileinheit informieren ob und wie dringend die sich im Eingangport befindender Pakete vermittelt werden sollten. Eine Gewichtung kann Angaben über die Priorität und Klasse der Pakete bzw. die Wartzeit oder Größe einer Warteschlange beinhalten.

Eine Zeile der Zustandsmatrix entspricht einem Eingangsport und jede Spalte entspricht einem Ausgangsport der Paketvermittlungsvorrichtung. Anhand eines Vektors ordnet die Zuteileinheit die Spalten innerhalb der Zustandsmatrix neu an. Der Vektor besteht aus Vektorelemente, die jeweils einer Spalte der Zustandsmatrix zugeordnet sind. Bei der Neuordnung der Spalten ist die Größe der Vektorelemente entscheidend. Eine neue

Reihenfolge der Spalten in der Zustandsmatrix ist abhängig von dem der Spalte zugeordneten Vektorelement.

Durch die Neuordnung der Spalten entsteht aus der ersten Zustandsmatrix eine zweite Zustandsmatrix, die sich von der ersten Zustandsmatrix in der Reihenfolge der Spalten unterscheidet. Nach der Neuordnung der Spalten führt die Zuteileinheit anhand der zweiten Zustandsmatrix eine Berechnungsvorschrift zur Auswahl der vorläufigen Verknüpfungen zwischen Eingangsports und Ausgangsport aus.

Die Verknüpfungen werden in einer ersten Entscheidungsmatrix festgehalten.

Die Spalten der ersten Entscheidungsmatrix werden in die ursprüngliche Reihenfolge der ersten Zustandmatrix durch die Zuteileinheit umgeordnet, so dass eine zweite Entscheidungs- matrix entsteht.

Die in der Entscheidungsmatrix markierten Verknüpfungen werden als akzeptierte Verknüpfungen an die Koppelmatrix zur Konfiguration verschickt und die Eingangsports mit den Ausgangsports zur Vermittlung von Datenpaketen verknüpft.

Die Berechnungsvorschrift nach der die Zuteileinheit arbeitet, kann ein Successive Incremental Matching over Multiple Ports (SIMP) Algorithmus sein, der in der Veröffentlichung Weighted Arbitration Algorithms with Priorities for Input-Queued Switches with 100% Throughput"von R. Schoenen, G. Post, G. Sander, Broadband Switching Symposium'99 beschrieben wird. Dabei wird die Reihenfolge mit der SIMP auf die Spalten der Zustandsmatrix arbeitet, bestimmt durch die zuvor beschriebene Neuordnung der Spalten, welche mit Hilfe eines Vektors erzielt wird. Durch die Neuordnung der Zustandsmatrix und somit eine geänderte erste Spalte, mit der die Berechnungsvorschrift SIMP beginnt, kann die Ausführung von SIMP vereinfacht werden.

Durch die Neuordnung der Spalte bzw. eine neu Reihenfolge, nach der die Spalten durch die Zuteileinheit zur Ausführung der Berechnungsvorschrift herangezogen werden, kann die Berechnungsvorschrift schnell günstige Verknüpfungen der Eingangsports mit den Ausgangsports bestimmen und somit zur einer hervorragenden Leistung der Paketvermittlungsvorrichtung führen.

Die Portsteuerung erzeugt und versendet in regelmäßigen Zeitabständen die Gewichtungen zur Bestimmung der Konfiguration der Koppelmatrix an die Zuteileinheit.

Eine vorzugsweise Ausführungsform der Zustandsmatrix enthält Elemente, die jeweils einen Unterschied zwischen einer aktuellen durch die Portsteuerung erzeugten Gewichtung einer Verknüpfung und einer im vorher liegenden Zeitabstand erzeugten Gewichtung repräsentieren.

Am Ausgang jeder Portsteuerung werden die Datenpakete in Warteschlangen zwischengespeichert, bevor sie die Portsteuerung und die Paketvermittlungsvorrichtung verlassen. Falls eine Betriebsgeschwindigkeit der Ausgangsports langsamer ist als die Betriebsgeschwindigkeit der Paketvermittlungsvorrichtung, können die Datenpakete die Ausgangsports nicht ausreichend schnell verlassen und die Warteschlangen werden durch die Datenpakete überfüllt. Eine Warteschlange der Datenpakete gibt einen Speicherinhalt eines Ausgangsports wieder. Die zur Neuordnung der Zustandsmatrix notwendigen Vektorelementen, repräsentieren jeweils einen Speicherinhalt eines Ausgangsports.

Die Neuordnung der Spalten richtet sich nach der Größe der Vektorelemente.

Dabei wird eine Spalte, die einem mit Datenpakten angefüllten Speicherinhalt repräsentierenden Vektorelement zugeordnet ist, als letzte Spalte der zweiten Zustandsmatrix angeordnet. Eine einem leeren Speicherinhalt repräsentierendem Vektorelement zugeordnete Spalte wird als erste Spalte der zweiten Zustandsmatrix angeordnet und somit als erste durch die Zuteileinheit zur Abarbeitung der Berechnungsvorschrift herangezogen.

Bei weiteren Ausführungsformen des Vektors, geben die Vektorelemente jeweils die Summe aller in einer Spalte angeordneten Elemente an oder bestehen aus dem größten Element jeweils einer Spalte der ersten Zustandsmatrix. Die Anordnung der Spalten der zweiten Zustandsmatrix richtet sich auch in diesen Fällen nach der Größe des Vektor- elements.

Die Zuteileinheit ist nicht nur in der Lage auf der zweiten Zustandsmatrix zu arbeiten, sie kann auch direkt auf die ursprüngliche Zustandsmatrix zugreifen, wobei die Reihenfolge, mit der die Spalten der Zustandsmatrix abgearbeitet werden, bestimmt wird durch den Vektor.

Die Erfindung betrifft auch eine Vermittlungseinheit bestehend aus einer Koppelmatrix und einer Zuteileinheit zur Steuerung der Koppelmatrix für eine Paketvermittlungsvorrichtung mit mehreren Ein-und Ausgangsports. Die Zuteileinheit arbeitet anhand einer Zustandsmatrix mit Elementen, die jeweils eine Gewichtung einer Verknüpfung zwischen einem Eingangsport und einem Ausgangsport der Paketvermittlungsvorrichtung repräsentieren und deren Zeilen jeweils einem Eingangsport und Spalten jeweils einem Ausgangsport der Paketvermittlungsvorrichtung entsprechen. Die Zuteileinheit ordnet die Spalten in Abhängigkeit eines Vektors, dessen Vektorelemente jeweils einer Spalte zugeordneten sind.

Weiterhin betrifft die Erfindung eine Zuteileinheit zur Steuerung der Koppelmatrix einer Vermittlungseinheit für eine Paketvermittlungsvorrichtung mit mehreren

Ein-und Ausgangsports. Die Zuteileinheit arbeitet anhand einer Zustandsmatrix mit Elementen, die jeweils eine Gewichtung einer Verknüpfung zwischen einem Eingangsport und einem Ausgangsport der Paketvermittlungsvorrichtung repräsentieren und deren Zeilen jeweils einem Eingangsport und Spalten jeweils einem Ausgangsport der Paketvermittlungsvorrichtung entsprechen. Die Zuteileinheit ordnet mittels eines Vektors die Spalten in Abhängigkeit von einem jeder Spalte zugeordneten Vektorelement an.

Die Erfindung betrifft weiterhin ein Vermittlungsverfahren für eine Paketvermittlungsvorrichtung mit mehreren Ein-und Ausgangsports und wenigstens einer Vermittlungseinheit bestehend aus einer Koppelmatrix und einer Zuteileinheit zur Steuerung der Koppelmatrix. Die Zuteileinheit arbeitet anhand einer Zustandsmatrix mit Elementen, die jeweils eine Gewichtung einer Verknüpfung zwischen einem Eingangsport und einem Ausgangsport der Paketvermittlungsvorrichtung repräsentieren und deren Zeilen jeweils einem Eingangsport und Spalten jeweils einem Ausgangsport der Paketvermittlungsvor- richtung entsprechen. Die Spalten der Zustandsmatrix werden mittels eines Vektors in Abhängigkeit von einem jeder Spalte zugeordneten Vektorelement angeordnet.

Anhand einiger Ausführungsbeispiele soll die Erfindung in Verbindung mit den Figuren näher erläutert werden.

Es zeigen : Fig. 1 Paketvermittlungsvorrichtung, Fig. 2 Ermittlung der endgültigen Verknüpfungen anhand eines Vektors, dessen Vektorelemente jeweils einen Speicherinhalt eines Ausgangsports repräsentieren, Fig. 3 Ermittlung der endgültigen Verknüpfungen anhand eines Vektors, dessen Vektorelemente jeweils eine Summe einer Spalte einer Zustandsmatrix repräsentieren, Fig. 4 Ermittlung der endgültigen Verknüpfungen anhand eines Vektors, dessen Vektorelemente jeweils ein größtes Element einer Spalte der Zustandsmatrix repräsentieren, Eine in Fig. 1 dargestellte Paketvermittlungsvorrichtung besteht aus zwei Leitungseinheiten 1 und 2 und mehreren Vermittlungseinheiten 3 bis 5. Die Anzahl der Leitungseinheiten 1 und 2 ist häufig viel Größer als zwei z. B. 64, im Ausführungsbeispiel wurde sie aufgrund einer übersichtlichen Darstellung auf zwei beschränkt. Die

Leitungseinheiten 1 und 2 bestehen jeweils aus unterschiedlichen für die Beschreibung des Ausführungsbeispiels nicht relevanten und deshalb nicht dargestellten Komponenten wie einer optische Übertragungseinheit, Rahmengenerator, Netzwerkprozessor etc., sowie einer für das Ausführungsbeispiel wesentlichen Portsteuerung 6 und 7. Jede Vermittlungseinheit 3 bis 5 besteht aus einer Koppelmatrix 8 und einer Zuteileinheit 9. Sowohl die Zuteileinheit 9 sowie die Koppelmatrix 8 jeder parallel arbeitenden Vermittlungseinheit 3 bis 5 sind jeweils mit der Portsteuerung 6 und 7 verbunden.

Datenpakete konstanter Länge werden als Zellen bezeichnet. Da Zellen konstanter Länge bei der Vermittlung leichter zu handhaben sind als Pakete wechselnder Größe, werden die ankommenden Pakete innerhalb der Leitungseinheiten 1 und 2 in Zellen konstanter Länge zerteilt und in Warteschlangen zwischengespeichert. Nach einer erfolgreichen Vermittlung, d. h. akzeptierte Zuordnung jeweils eines Eingangsports mit einem Ausgangsport, werden die Zellen aus der Warteschlange entfernt.

Anhand einer Gewichtung kann die Portsteuerung die Zuteileinheit informieren ob und wie dringend die sich im Eingangport befindenden Zelle vermittelt werden sollten. Die Gewichtung kann Angaben über die Priorität und Klasse der Pakete bzw. die Wartzeit oder Größe einer Warteschlange im Eingangport beinhalten.

Die Portsteuerung 6 und 7 sendet die zur Bestimmung der Konfiguration der Koppelmatrix notwendigen Informationen, u. a. die Gewichtung an die Zuteileinheit 9.

Nachdem die Zuteileinheit die Konfiguration der Koppelmatrix 8 ermittelt hat und die Konfiguration sowohl an die Portsteuerung als auch an die Koppelmatrix verschickt hat, wird die Koppelmatrix 8 jeder Vermittlungseinheit 3 bis 5 entsprechend konfiguriert. Die Portsteuerung 6 und 7 versendet in regelmäßigen Zeitabständen den sog. Zellperioden die Zellen zur Vermittlung an die Koppelmatrix 8.

In Fig. 2 wird eine durch die Zuteileinheit 9 ausgeführte und auf eine Zustandsmatrix 10 angewandte Berechnungsvorschrift zur Konfiguration der Koppelmatrix 8 dargestellt. Die Berechnungsvorschrift wird in der Veröffentlichung"Weighted Arbitration Algorithms with Priorities for Input-Queued Switches with 100% Throughput"von R.

Schoenen, G. Post, G. Sander, Broadband Switching Symposium'99 vorgestellte. Fig. 2 besteht aus einer ersten Zustandsmatrix 10, einem Vektor 11, einer zweiten Zustandsmatrix 12, der Berechnungsvorschrift 13, einer vorläufigen Entscheidungsmatrix 14, und einer endgültigen Entscheidungsmatrix 15.

Die Zustandsmatrix 10 entspricht einer Paketvermittlungsvorrichtung mit vier Eingangsports (Input) 10 bis I3 und vier Ausgangsports (Output) 00 bis 03. Sie enthält

sechzehn Elemente, welche die Gewichtung jeder Verknüpfung eines Eingangsports 10 bis I3 mit einem Ausgangsport 00 bis 03 repräsentieren.

Im Ausführungsbeispiel der Fig. 2 wurde die Anzahl der Spalten und Zeilen bzw. der Eingangs-und Ausgangsport auf vier beschränkt, um eine übersichtliche Darstellungsform zu erzielen.

Der Vektor 11 besteht aus Vektorelementen, die jeweils einer Spalte der Zustandsmatrix bzw. einem Ausgangsport zugeordnet sind und einen Speicherinhalt des Ausgangsports repräsentieren. Dabei bedeute ein mit Null besetztes Vektorelement, dass der Speicherinhalt des Ausgangsports fast leer ist und eine große Speicherkapazität des Ausgangsports zur Verfügung steht, so dass Datenpakete an den Ausgangsport vermittelt werden sollten.

Anhand des Vektors 11 werden die Spalten der Zustandsmatrix durch die Zuteileinheit neu angeordnet. Durch die Neuordnung der Spalten entsteht eine zweite Zustandsmatrix 12, deren Spalten nach der Größe der Vektorelemente sortiert sind. Eine Spalte deren Vektorelement einen fast freien Speicherinhalt repräsentiert, wird als eine der ersten Spalten sortiert. Eine Spalte mit einem fast vollständig angefüllten Speicherinhalt des Ausgangsports wird als eine der letzten Spalten der zweiten Zustandsmatrix angeordnet.

Da der Vektor 11 zwei mit Null besetzte Vektorelemente besitzt, muß durch ein sogenanntes Round-Robin-Verfahren als Bedienstrategie (Scheduling) entschieden werden, welche der diesem Vektorelementen zugeordnete Spalte als erste Spalte der zweiten Zustandsmatrix 12 angeordnet wird.

Die Spalte des Ausgangsports 01 wurde als erste Spalte der Zustandsmatrix 12 ausgewählt. Die folgenden Spalten sortiert die Zuteileinheit 9 nach der Größe des Vektorelements entsprechend ein beginnend mit dem kleinsten Vektorelement. Daraus resultiert als zweite Spalte die Spalte des Ausgangsports 03, danach die Spalte des Ausgangsports 02 und die Spalte des Ausgangsports 00 mit dem größten Vektorelement.

Die Spalten der zweite Zustandsmatrix 12 entsprechen der Reihenfolge, in der sie durch die Zuteileinheit 9 zur Ausführung der Berechnungsvorschrift 13 herangezogen werden. In der vorläufigen Entscheidungsmatrix 14 werden die Verknüpfungen markiert, die anhand der Berechnungsvorschrift 13 ausgewählt wurden. Die Spalte der vorläufigen Entscheidungsmatrix 14 werden in der ursprünglichen Reihenfolge der Ausgangsports in die endgültige Entscheidungsmatrix 15 eingeordnet.

Die Fig. 3 besteht aus der gleich Anordnung wie Fig. 2 mit dem Unterschied, dass die Vektorelemente jeweils aus einer Summe aus Elementen einer Spalte der Zustandsmatrix 10 bestehen. In Folge dessen ergibt sich eine andere Neuordnung der Spalten.

Die Spalten werden der Größe des Vektorelementes entsprechen sortiert. Da das größte Vektorelement der Spalte des Ausgangsports 00 entspricht, wird die Berechnungsvorschrift mit der Spalte des Ausgangsports beginnen bzw. diese Spalte als erste in der zweiten Zustandsmatrix 12 angeordnet. Das zweit größte Vektorelement ist der Spalte des Ausgangsport 02 zugeordnet, so dass sich die in der Fig. 3 dargestellte Reihenfolge der Spalte der zweiten Zustandsmatrix 12 ergibt.

Analog zur Fig. 2 wird die Berechnungsvorschrift 13 auf die Zustandsmatrix 12 angewendet. In der vorläufigen Entscheidungsmatrix 14 werden die Verknüpfungen markiert, die anhand der Berechnungsvorschrift 13 ausgewählt wurden. Die Spalte der vorläufigen Entscheidungsmatrix 14 werden in der ursprünglichen Reihenfolge der den Spalten entsprechenden Ausgangsports in die endgültige Entscheidungsmatrix 15 eingeordnet.

Fig. 4 besteht ebenfalls aus der gleichen Anordnung wie Fig. 2 mit dem Unterschied, dass die Vektorelemente des Vektors 11 ein größtes Element der dem Vektorelement zugeordneten Spalte entsprechen.

Da die Spalte des Ausgangsports 02 den größten Vektorelement zugeordnet ist, wird diese Spalte als erste Spalte in der zweiten Zustandsmatrix 12 angeordnet bzw. als erste zur Ausführung der Berechnungsvorschrift herangezogen. Die weitere Reihenfolge der Spalten richtet sich nach Größe der Vektorelemente, so dass die Spalte des Ausgangsports 00 als nächste Spalte der Zustandsmatrix 13 bestimmt wird. Die übrigen Spalten der Zustands- matrix 12 sind die Spalte des Ausgangsports O1 und Ausgangsport 03.

Analog zur Fig. 2 wird die Berechnungsvorschrift 13 auf die Zustandsmatrix 12 angewendet. In der vorläufigen Entscheidungsmatrix 14 werden die Verknüpfungen markiert, die anhand der Berechnungsvorschrift 13 ausgewählt wurden. Die Spalte der vorläufige Entscheidungsmatrix 14 werden in der ursprünglichen Reihenfolge der den Spalten entsprechenden Ausgangsports in die endgültige Zustandsmatrix 15 eingeordnet.