DE60318971T2

DE60318971T2 - Routinggerät mit paralleler Verarbeitung

Info

Publication number: DE60318971T2
Application number: DE60318971T
Authority: DE
Inventors: Albert Lespagnol
Original assignee: Alcatel Lucent SAS
Current assignee: Alcatel Lucent SAS
Priority date: 2002-04-19
Filing date: 2003-04-18
Publication date: 2009-02-05
Anticipated expiration: 2023-04-19
Also published as: US20040090961A1; DE60318971D1; CN100373888C; FR2838899B1; CN1455345A; EP1355454A1; FR2838899A1; EP1355454B1; ATE385640T1

Description

Die vorliegende Erfindung bezieht sich auf den Bereich der Weiterleitung von Datenpaketen in einem Netzwerk, und insbesondere auf Geräte, die zumindest die Routingfunktion gewährleisten (siehe beispielsweise im Dokument US-A-5905 725 ).
Unter „Routing" versteht man in diesem Zusammenhang die Funktion der Vermittlung von Datenpaketen in einem Netzwerk (Ebene 3 des OSI-Modells). Die Bezeichnung entspricht dem englischen Begriff „Routing".
Das Routing ist eine wesentliche Funktion für die Übertragung von Daten in einem Netzwerk. Sie besteht darin, an jedem Knoten eines Netzwerks mit Hilfe einer Routingtabelle den folgenden Knoten zu ermitteln, der die Möglichkeit zur Optimierung der Übertragung eines Datenpakets zwischen seiner Quelle und seinem Ziel bietet. Die Umsetzung erfolgt entweder mit Hilfe von Routern vom Typ L3F (für „Level 3 Forwarding") oder mit Hilfe von „gemischten" Vermittlungsgeräten („Switch-Router"), die sowohl die Vermittlung als auch das Routing gewährleisten.
Aufgrund der permanenten Weiterentwicklung insbesondere öffentlicher Netzwerke ist es unbedingt erforderlich, die Routingtabelle häufig zu aktualisieren, in der Regel alle fünf Sekunden. Diese Aktualisierungen erfordern ein erhebliches Datenaustausch-Volumen, typischerweise mehrere Megabit, was die Leistungen des Routing- oder Vermittlungsgeräts erheblich beeinträchtigt. Außerdem erweist sich die verteilte Architektur von Routing- oder Vermittlungsgeräten als immer weniger für den Verkehr geeignet, der in den Netzwerken stetig zunimmt.
Die Erfindung hat daher das Ziel, die vorgenannten Nachteile ganz oder teilweise zu beseitigen.
Zu diesem Zweck schlägt sie ein Gerät zum Datenrouting vor, das einerseits ein Verwaltungsmodul, das die primären Routingdaten und die Speicheradresse der weiterzuleitenden Sekundärdaten empfangen kann, und andererseits ein Übertragungsmodul umfasst, um ausgehend von diesen empfangenen Daten und den in mindestens einer Routingtabelle gespeicherten Daten tertiäre Daten zu ermitteln, die mindestens einen der Ausgangsanschlüsse einer Datenübertragungsstufe und neue primäre Routingdaten bezeichnen, und um die ermittelten Primär- und Tertiärdaten an die Datenübertragungsstufe zu übermitteln, so dass zumindest bestimmte neue Primärdaten mit den weiterzuleitenden Sekundärdaten kombiniert werden, die unter der Speicheradresse abgelegt sind, und anschließend an jeden Ausgangsanschluss übermittelt werden, der von den Tertiärdaten bezeichnet wird.
Unter Datenübertragungsstufe versteht man in der vorliegenden Beschreibung eine Stufe, die insbesondere aus einer Eingangsstufe (oder „Ingress Stage"), die mit Eingangsanschlüssen zum Empfang von Datenpaketen ausgerüstet ist, einem Pufferspeicher zur temporären Speicherung von Routingdaten unter einer Speicheradresse und mit einer Ausgangsstufe (oder „Egress Stage"), die mit Ausgangsanschlüssen zur Weiterleitung der Routingdaten ausgerüstet ist, besteht.
Diese Vorrichtung ist durch die Tatsache gekennzeichnet, dass:

• ihr Verwaltungsmodul einen Pufferspeicher umfasst, der in n Unterspeicher unterteilt ist, die in der Lage sind, die Anteile von empfangenen Datenpaketsegmenten jeweils unter gewählten Adressen zu speichern und auf einen entsprechenden Befehl hin gleichzeitig über n erste parallele Ausgänge einen der gespeicherten Anteile zu übermitteln, und
• ihr Übertragungsmodul entsprechend ausgeführt ist, um erstens vom Verwaltungsmodul die gewählten Speicheradressen der ersten, nacheinander empfangenen Segmente zu empfangen, und zweitens dem Verwaltungsmodul die Speicheradressen einiger dieser ersten Segmente in Abhängigkeit von einem ausgewählten Kriterium zu übermitteln, um im Gegenzug am Ausgang der ersten parallelen Ausgänge die Anteile des Segments zu empfangen, die in den Unterspeichern unter den Speicheradressen gespeichert sind, und drittens, um die Anteile, die zu verschiedenen Segmenten gehören, an eine oder mehrere Routingtabellen (je nach Bedarf) weiterzuleiten, um auf parallele Weise, ausgehend von den in diesen Routingtabellen gespeicherten Daten und einer abschnittsweisen Analyse der verschiedenen Segmente, die Primär- und Tertiärdaten zu ermitteln, die den verschiedenen Sekundärdaten zugeordnet sind.

Dank dieser neuartigen Architektur kann die Anzahl der Routingtabellen nun in Abhängigkeit vom Volumen der zu übertragenden Daten gewählt werden. Außerdem bietet die neuartige Konzeption des Geräts gemäß der Erfindung die Möglichkeit, es in neue Typen von Vermittlungsstellen-Routern mit zentraler Architektur zu integrieren, in denen insbesondere Verkehrssteuerung und Pufferspeicherung gemeinsam ausgeführt werden können.
Vorzugsweise stammen die Daten in Form von Segmenten mit gleicher Länge, die nicht mehr in Anteile unterteilt werden müssen, direkt aus dem Verwaltungsmodul. Diese Segmentierung wird dann beispielsweise in der Datenübertragungsstufe einer Weiterleitungsvorrichtung durchgeführt.
Vorteilhafterweise stellen die Verwaltungs- und Übertragungsmodule eine Routingstufe vom Typ L3F dar, die man mit einer Datenübertragungsstufe koppeln kann.
In einer bevorzugten Ausführungsvariante umfasst das Übertragungsmodul eine Eingangsstufe, die erstens mit n Registern, in denen die Speicheradressen der n ersten empfangenen Segmente gespeichert sind, zweitens mit einem Eingangspufferspeicher, der die gewählten Adressen der ersten Segmente vom Verwaltungsmodul empfängt, um diese an die Register weiterzuleiten, und drittens mit einer Vermittlungseinheit (oder „Shifter") ausgerüstet ist, die n Eingänge umfasst, die von den n ersten parallelen Ausgängen jeweils n Segmentanteile erhalten, sowie 1 bis n zweite Ausgänge, die in der Lage sind, die weitergeleiteten Anteile, die zu verschiedenen Segmenten gehören, zu übermitteln. Vorzugsweise umfasst jede Vermittlungseinheit ebenso viele Eingänge wie zweite Ausgänge.
Ebenfalls in einer bevorzugten Ausführungsvariante umfasst das Übertragungsmodul 1 bis n (die Anzahl hängt von der Anzahl an Datenpaketen ab, die pro Sekunde vermittelt werden müssen) Routingeinheiten, die unterschiedliche Segmentanteile von den zweiten Ausgängen erhalten, wobei sie jeweils einen wiederbeschreibbaren Speicher umfassen, in dem eine der Routingtabellen gespeichert ist, und die in der Lage sind, parallel die Primär- und Tertiärdaten zu ermitteln, die den verschiedenen Sekundärdaten zugeordnet sind. Vorzugsweise umfasst das Übertragungsmodul so viele parallele Routingeinheiten wie zweite Ausgänge.
Gemäß einem weiteren Merkmal der Erfindung stellt jede Routingtabelle das dar, was der Fachmann auf Englisch als „Trie Table" bezeichnet. Darin sind daher Zeilen mit Primärdaten gespeichert, die die Wörter definierten, die für die Routing-Präfixe repräsentativ sind, wobei jeder empfangene Segmentanteil dann verwendet wird, um eines der Wörter einer Zeile zu adressieren. Vorzugsweise sind in jeder Routingtabelle (oder Trie Table) Primärdaten gespeichert, die für die Worte ersten und zweiten Typs repräsentativ sind, wobei der erste und zweite Typ jeweils so genannte „Zwischen-„ bzw. „Endwörter" definieren, wobei nur die Endwörter neue primäre Routingdaten darstellen.
Es ist im Übrigen vorteilhaft, wenn das Übertragungsmodul eine Ausgangsstufe umfasst, die mit Ausgangspufferspeichern ausgerüstet ist, deren Anzahl der Anzahl an Ausgangsanschlüssen der Übertragungsstufe entspricht und die in der Lage sind, die Tertiärdaten, die neuen Primärdaten und die Speicheradresse der Routingeinheiten zu empfangen. In einer Variante kann man eine Gruppe von Ausgangspufferspeichern für jeden Ausgangsanschluss vorsehen, um z. B. mehrere unterschiedliche Dienstguten zu gewährleisten. In diesem Fall ist es vorteilhaft, wenn die Ausgangsstufe zudem einen Multiplexer umfasst, der Daten von den verschiedenen Routingeinheiten erhält und Daten an die verschiedenen Ausgangspufferspeicher übermittelt.
Ebenfalls vorzugsweise können die Routingeinheiten, wenn sie Routingtabellen vom Typ „Trie Table" beinhalten, einerseits jeweils ein Zwischenmodul umfassen, das über einen Ausgang verfügt, der mit dem wiederbeschreibbaren Speicher (in dem die Trie Table gespeichert ist) und dem ersten und zweiten Ausgang verbunden ist, die jeweils Daten von einem der zweiten Ausgänge der Eingangsstufe und dem Ausgang des wiederbeschreibbaren Speichers Daten erhalten, und andererseits entsprechend ausgeführt sind, um aus der Routingtabelle das Wort auszulesen, das unter der im empfangenen Anteil angegebenen Adresse gespeichert ist, und dieses Wort anschließend an den Ausgang des wiederbeschreibbaren Speichers zu übertragen, so dass dieser es an den zweiten Eingang des Zwischenmoduls oder an die Ausgangsstufe weiterleitet, je nachdem, ob das ausgelesene Wort ersten oder zweiten Typs ist. In diesem Fall ist das Zwischenmodul entsprechend ausgeführt, um beim Empfang von Daten, die für ein Wort ersten Typs repräsentativ sind, aus der Routingtabelle das Wort auszulesen, das unter der von diesem Wort ersten Typs bezeichneten Adresse gespeichert ist, das ausgelesene Wort anschließend an den Ausgang des wiederbeschreibbaren Speichers zu übertragen, so dass dieser es an den zweiten Eingang des Zwischenmoduls oder die Ausgangsstufe übermittelt, je nachdem, ob das ausgelesene Wort ersten oder zweiten Typs ist. Dieser Vorgang wird so lange wiederholt, bis aus der betreffenden Routingtabelle ein Endwort (zweiter Typ) ausgelesen wird.
In einer bevorzugten Ausführungsvariante sind die Eingangs- und Ausgangspufferspeicher vom Typ „FIFO" (für „First In First Out").
Die Erfindung schlägt zudem einen Router oder eine Vermittlungsvorrichtung (vom Typ „Switch Router") vor, die mit einer Datenübertragungsstufe und einem Gerät gemäß der Erfindung ausgerüstet ist. In diesem Fall besteht das Gerät gemäß der Erfindung aus der Routingstufe des Routers oder Switch-Routers, die mit der Datenübertragungsstufe gekoppelt ist.
Die Erfindung schlägt zudem ein Verfahren zum Routing von Sekundärdaten vor, die primären Routingdaten und einer Speicheradresse zugeordnet sind, bei dem man ausgehend von den Primärdaten und den in mindestens einer Routingtabelle gespeicherten Daten Tertiärdaten ermittelt, die mindestens einen Ausgangsanschluss und neue primäre Routingdaten bezeichnen, anschließend werden die ermittelten Primär- und Tertiärdaten übertragen, so dass zumindest bestimmte der neuen Primärdaten mit den zu vermittelnden Sekundärdaten kombiniert, unter der Speicheradresse abgelegt und anschließend an jeden Ausgangsanschluss übertragen werden, der von den Tertiärdaten bezeichnet wird.
Dieses Verfahren ist durch die Tatsache gekennzeichnet, dass die Ermittlung darin besteht, erstens in n Unterspeichern unter gewählten Adressen die Anteile jedes Segments zu speichern, das aus einer Zerlegung der empfangenen, zu vermittelnden Datenpakete, d. h. den ersten Segmenten, resultiert, zweitens an gewählten Stellen die gewählten Speicheradressen der empfangenen ersten Segmente nacheinander zu speichern und anschließend, in Abhängigkeit von einem gewählten Kriterium, aus den Unterspeichern parallel die unter den Speicheradressen der ersten Segmente gespeicherten Anteile auszulesen, die an bestimmten, gewählten Stellen vorhanden sind, um diese Segmentanteile gleichzeitig und parallel zu übertragen, und drittens die Anteile, die zu verschiedenen Segmenten gehören, (je nach Bedarf) an eine oder mehrere Routingtabellen zu übermitteln, um ausgehend von den in diesen Routingtabellen gespeicherten Daten und der abschnittsweisen Analyse der verschiedenen Segmente parallel die Primär- und Tertiärdaten zu ermitteln, die verschiedenen zu vermittelnden Sekundärdaten zugeordnet werden sollen.
Vorzugsweise empfängt man die Routingdaten in Form von Segmenten mit gleicher Länge.
Ebenfalls vorzugsweise erfolgt das Routing nach Typ L3F.
Ebenfalls vorzugsweise speichert man die Speicheradressen der Abschnitte des gleichen Segments in n praktisch identischen Registern.
Weiterhin vorzugsweise sieht man ebenso viele Routingtabellen wie Unterspeicher vor.
Entsprechend einem Merkmal des Verfahrens gemäß der Erfindung sind in jeder Routingtabelle (oder „Trie Table") die Primärdaten, die die Worte definieren, die für die Routingpräfixe repräsentativ sind, in Form von Zeilen gespeichert, wobei jeder empfangene Segmentanteil die Möglichkeit bietet, eines der Worte einer Reihe zu adressieren. Vorzugsweise sind die Primärdaten repräsentativ für Worte ersten und zweiten Typs. In diesem Fall liest man aus der Routingtabelle während der Ermittlungsphase das unter der Adresse, die in dem empfangenen Segmentanteil bezeichnet ist, gespeicherte Wort aus, leitet das Wort anschließend weiter, so dass es an die neue Routingtabelle oder die Ausgangsanschlüsse übertragen wird, je nachdem ob das ausgelesene Wort ersten oder zweiten Typs ist, und jedes Mal, wenn ein Wort ersten Typs übermittelt wird, liest man aus der Tabelle ein weiteres Wort aus, das unter der Adresse gespeichert ist, die von dem übertragenen Wort bezeichnet wird, bis man ein Wort zweiten Typs erhält.
Die Geräte und das Verfahren gemäß der Erfindung, die oben beschrieben wurden, sind insbesondere, wenn auch nicht ausschließlich, gut für Routingstandards wie z. B. IP (für „Internet Protocol") geeignet, und zwar unabhängig vom Medium, sowie für Protokolle ohne Verbindung.
Weitere Merkmale und Vorteile der Erfindung werden anhand der nachstehenden detaillierten Beschreibung und den beiliegenden Zeichnungen deutlich, wobei:
1 ein Blockdiagramm ist, in dem ein Routinggerät gemäß der Erfindung, das einen Router bildet, schematisch dargestellt ist,
2 ein Blockdiagramm ist, in dem die Routingstufe des Geräts aus 1 schematisch dargestellt ist.
3 auf schematische Weise ein Beispiel für den Aufbau des Pufferspeichers des Verwaltungsmoduls der Routingstufe aus 2 darstellt,
4 auf schematische Weise ein Beispiel für die Ausführung des Pufferspeichers des Verwaltungsmoduls der Routingstufe aus 2 darstellt,
5 auf schematische Weise einen Speichermodus (Schreiben) für Daten im Pufferspeicher des Verwaltungsmoduls der Routingstufe aus 2 darstellt,
6 auf schematische Weise ein Beispiel für einen Routingmechanismus darstellt,
7A und 7B auf schematische Weise die Signale, die vom Haupttaktgeber des Geräts erzeugt werden, sowie die Verbindung zwischen diesem Haupttaktgeber und den Zählern des Geräts darstellen,
8 eine Tabelle ist, die den Auslesemodus für Daten am Eingang des Vermittlungsmoduls und des Übertragungsmoduls der Routingstufe darstellt,
9 eine Tabelle ist, in der ein Auslesemodus für Daten am Ausgang des Vermittlungsmoduls des Übertragungsmoduls der Routingstufe darhrstellt ist,
10 ein Beispiel für eine Routingtabelle vom Typ „Trie Table" ist.
Die beiliegenden Zeichnungen haben im Wesentlichen eindeutigen Charakter, sie dienen daher nicht nur der Ergänzung der Erfindung, sonder können gegebenenfalls auch zu ihrer Definition verwendet werden.
Im Folgenden wird zunächst Bezug auf 1 genommen, um ein Ausführungsbeispiel für ein Routinggerät gemäß der Erfindung zu beschreiben, das einen Router darstellt.
Natürlich kann die Erfindung auch in einer Vermittlungseinrichtung vom Typ Switch-Router eingesetzt werden, insbesondere mit zentralen Vermittlungs- und Routingfunktionen. Sie könnte auch nur die Routingstufe eines Routers darstellen.
Das Gerät 1 umfasst zunächst eine Datenübertragungsstufe 2, die eine Eingangsstufe (oder „Ingress Stage") 3 umfasst, die mit Eingangsanschlüssen ausgerüstet ist, um Datenpakete zu empfangen, mit einem Pufferspeicher 5, um die zu vermittelnden Daten, die von der Eingangsstufe 3 übertragen werden, temporär zu speichern, und mit einer Ausgangsstufe (oder „Egress Stage") 6, die mit Ausgangsanschlüssen 7 ausgerüstet ist, um die resultierenden zu vermittelnden Daten insbesondere an den Pufferspeicher 5 weiterzuleiten.
Dieses Gerät 1 umfasst außerdem eine Routingstufe 8, die Daten von der Eingangsstufe 3 erhält und die Ausgangsstufe 6 mit neuen Routingdaten speist.
Die Komponenten des Geräts 1 werden von einem Haupttaktgeber MCL synchronisiert, dessen Taktperiode als Inkrementierungsbasis für einen Hauptzähler MCP und einen Zusatzzähler (MCP16, MCPi) dient, wie in 7A und 7B dargestellt. MCPx ist ein Zähler mit Modulo x, der im Takt von MCL weiter zählt.
Die Datenübertragungsstufe 2 wird auf detaillierte Weise in den Patentbeschreibungen US 5.237.564 und EP 00 440 281 beschrieben. Daher werden im Folgenden nur die wesentlichen Funktionen dieser Übertragungsstufe 2 beschrieben, nicht jedoch die Zusatzfunktionen.
Die Eingangsstufe 3 ist zunächst so ausgeführt, um an ihren I Eingangsanschlüssen 4 Datenpakete mit variabler Länge zu empfangen, und um aus diesen Daten einerseits die Primärdaten, die für die Routinginformationen repräsentativ sind, die von der Routingstufe 8 verarbeitet werden müssen, und andererseits die Sekundärdaten auszulesen, die weitervermittelt werden müssen.
Diese Sekundärdaten werden an den Pufferspeicher 5 übertragen, um dort unter einer Speicheradresse FSA(s) gespeichert zu werden. Wenn der Pufferspeicher 5 beispielsweise s Segmente speichern kann, gibt ein Zähler MCPs zu jedem Zeitpunkt die Speicheradresse FSA(s) für das in diesem Pufferspeicher 5 eintreffende Segment an. Die Primärdaten werden an die Routingstufe übermittelt, und zwar zusammen mit der Speicheradresse FSA(s), bei der es sich tatsächlich um den laufenden Wert von MCPs handelt, wobei die zugeordneten Sekundärdaten temporär im Pufferspeicher 5 gespeichert wurden.
Vorzugsweise sind die empfangenen Datenpakete, wie in den vorgenannten Patentdokumenten beschrieben, zunächst Gegenstand einer Segmentierung in der Eingangsstufe 3, ehe ihre Daten an den Pufferspeicher 5 und die Routingstufe 8 übertragen werden. Diese Segmentierung besteht darin, jedes Paket in Segmente mit gleicher Länge zu unterteilen, wobei die Verbindung aufrecht erhalten bleibt, die diese im Bereich des Pufferspeichers 5 und der Routingstufe 8 verbindet. Sobald die neuen Routinginformationen von der Routingstufe 8 ermittelt wurden, werden die Sekundärdaten des ursprünglichen Pakets wiederhergestellt, um an den Pufferspeicher 5 übertragen zu werden, wobei ihnen neue Routinginformationen (Primärdaten) angehängt werden, ehe sie an die Ausgangsanschlüsse 7 weitergeleitet werden.
Die Anzahl an Segmenten eines empfangenen Pakets (PL(i)) wird von der Routingstufe 8 bei der Ankunft der Segmente gezählt.
Die Primärdaten sind üblicherweise im ersten Segment des empfangenen Pakets enthalten. Sie umfassen im Allgemeinen den Anschluss und die Adresse der Paketquelle sowie den Anschluss und die Adresse des Paketziels.
Im Fall des Routings handelt es sich bei den Primärdaten im Allgemeinen um Routinginformationen, wie beispielsweise die Zieladresse, die als Index für die Routingtabelle dienen. Die Routinginformation ist im Allgemeinen eine globale Kennung (d. h. dass vor der Übertragung des Pakets keine Verbindung hergestellt werden muss). Zahlreiche Routingprotokolle funktionieren nach diesem Prinzip. Darunter ist insbesondere das Internet Protocol (IP) zu nennen, das medienunabhängig arbeitet. Im Fall des IP-Protokolls dient die globale Kennung, IP-Adresse genannt, dazu, das Paket lokal weiterzuleiten und die neuen, von der Routingtabelle übermittelten Primärdaten bilden ein neues Label, das für das Routing zum nächsten Gerät verwendet wird.
Wenn das Gerät 1 I Eingangsanschlüsse 4 umfasst, ist jedes Segment in I Anteile (oder Worte) unterteilt. Die Verarbeitungszeit eines Worts (oder Anteils) entspricht der Taktperiode des Haupttaktgebers MCL. Die Eingangsanschlüsse 4 sind so ausgeführt, dass ein in Anschluss i eintreffendes Paket ein Wort vor einem eintreffenden Segment in Anschluss i – 1 gesetzt wird, Modulo I. Des gleichen sind die Ausgangsanschlüsse 7 so ausgeführt, dass ein an Anschluss i übertragenes Segment ein Wort vor das an Anschluss i – 1 übertragene Segment gesetzt wird, Modulo I.
Im Folgenden wird auf 2 bis 10 Bezug genommen, um ein Ausführungsbeispiel für eine Routingstufe gemäß der Erfindung zu beschreiben.
Die Routingstufe 8, die in 2 darstellt ist, ist vom Typ L3F. Sie umfasst zunächst ein Verwaltungsmodul 9, das einen Verwaltungs-Pufferspeicher 10 umfasst, in dem unter einer gewählten Adresse i die primären Routingdaten, die im ersten von der Eingangsstufe 3 übertragenen Segment enthalten sind, die Speicheradresse FSA(s) im Pufferspeicher 5 des erste Segments für die Sekundärdaten, die den Primärdaten zugeordnet sind, sowie vorzugsweise die Gesamtanzahl an Segmenten PL(i) des zugeordneten Paktes gespeichert sind.
Wie in 3 dargestellt, sind die ersten Segmente und die Zusatzdaten (MFSA(i) und MPL(i)) vorzugsweise vertikal im Verwaltungs-Pufferspeicher 10 gespeichert, der vorzugsweise mittels binärer Verschiebung funktioniert. Wenn daher der Pufferspeicher 10 m Eingänge (oder Spalten) umfasst, wird ein erstes Segment durch ein neues erstes Segment ersetzt, wenn m zu vermittelnde Pakete empfangen wurden.
Die Größe m des Pufferspeichers 10 kann einfach in Abhängigkeit von der Übertragungsgeschwindigkeit der eingehenden Pakete im Gerät 1 und von der Betriebsgeschwindigkeit des Geräts 1 (bzw. der Übertragungsgeschwindigkeit, mit der die Pakete weitergeleitet werden) gesteuert werden. Die Betriebsgeschwindigkeit ist vorzugsweise höher als die Eingangsgeschwindigkeit, so dass selbst bei einer geringen Größe m des Pufferspeichers 10 gewährleistet werden kann, dass kein Segment verloren geht (bzw. überschrieben wird, was den Verlust des entsprechenden Pakets zur Folge hätte).
Die Segmente, die das Verwaltungsmodul 9 erreichen, werden in Segmentanteile zerlegt, die jeweils ein Wort darstellen. Wie bereits schematisch in 4 dargestellt, ist der Verwaltungs-Pufferspeicher 10 daher in n identische und unabhängige Unterspeicher BM(0) bis BM(n – 1) unterteilt, wobei jeder Unterspeicher BM(r) zur Speicherung eines Anteils (oder Worts) M(r) bestimmt ist, der (das) in allen Segmenten die Zeile r einnimmt. Jedes Wort (bzw. jeder Anteil) wird mit Hilfe eines Busses BMI(r) in den Unterspeichern BM(r) gespeichert und mit Hilfe eines Busses BMO(r) aus diesem Unterspeicher ausgelesen.
Der Haupttaktgeber MCL synchronisiert die Auslesung (oder Wiedergewinnung) und die Ablage (oder Speicherung) des Pufferspeichers 10. Wie in 7A dargestellt, ist die halbe Taktperiode H1 zum Schreiben bestimmt, während die halbe Taktperiode H0 zur Auslesung bestimmt ist. Wie in 3 dargestellt wird die Adressierung der Unterspeicher BM(r) im Übrigen zur Auslesung ebenso wie zur Speicherung von einem Multiplexer gewährleistet.
Genauer gesagt werden, wie in 5 dargestellt, zur Speicherung jedem Unterspeicher BM(R) zwei Zähler zugeordnet. Der Zähler CWA(r) enthält die Adresse des Pufferspeichers 10, in dem ein eingehendes Wort (oder ein Anteil) in Zeile r eines Segments gespeichert werden soll. Der Zähler CFSA(r) enthält die Adresse des Pufferspeichers 10, in dem das erste Segment eines Pakets gespeichert ist. Da der Pufferspeicher 10 n Unterspeicher BM(r) enthält, existieren also n Sätze mit zwei Zählern (CWA, CFSA).
Diese Zähler sind vorzugsweise in Form eines Puffers mit binärer Verschiebung ausgeführt, die die gespeicherten Daten bei jeder Taktperiode MCL nach einem Schreibvorgang um eine Zeile verschieben. Die Zeile „0" nimmt beispielsweise den Zeilenwert „n – 1" ein, die Zeile „1" nimmt den Zeilenwert „0" ein, ..., die Zeile „n – 1" nimmt den Zeilenwert „n – 2" ein.
Ehe die Verschiebung durchgeführt wird, können zwei Fälle auftreten. Wenn das erste Segment eines neuen Pakets ankommt, ergibt sich unter Berücksichtigung der Tatsache, dass i den Wert für CFSA(0) repräsentiert:

– MFSA(i): Adresse dieses ersten Segments im Pufferspeicher 5, die durch den Wert des Hauptzähler MCP(s) gegeben ist, wobei s die Größe des Pufferspeichers 5 ist;
– MPL(i) = 1;
– CFSA(0) = CWA(0); und
– CWA(n – 1) = CWA(0) + 1 (Modulo m). Dieser letzte Vorgang inkrementiert die Adresse, unter der das folgende empfangene Segment gespeichert wird, wodurch gewährleistet wird, dass das zuvor eingetroffene Segment nicht gelöscht wird. Dieser Vorgang wird nicht ausgeführt, wenn es sich bei dem laufenden Segment nicht um das erste Segment eines Pakets handelt. Infolgedessen wird dieses Segment von den folgenden Segmenten gelöscht, bis ein neues erstes Segment eintrifft.

Wenn es sich bei dem empfangenen Segment nicht um das erste Segment eines neuen Pakets handelt, ergibt sich unter Berücksichtigung der Tatsache, dass i den Wert für CFSA(0) repräsentiert:

– MPL(i) = MPL(i) + 1(Modulo m).

Wenn das letzte Segment eines Pakets empfangen wird, wird die Adresse des ersten Segments dieses Pakets im Pufferspeicher 10 (CFSA(0)) in die Warteschlange eines Eingangs-Pufferspeichers 11 eingestellt, vorzugsweise vom Typ FIFO, so dass die empfangenen Primärdaten in Abhängigkeit von ihrer Eingangsreihenfolge in der Routingstufe 8 verarbeitet werden. Es wird nur die Adresse des ersten Segments im FIFO-Eingangsspeicher 11 gespeichert, da die verschiedenen Anteile dieses ersten Segments in der gleichen Spalte des Pufferspeichers 10 gespeichert sind (die gespeicherte Adresse entspricht also der Adresse der Spalte). Wenn dieser FIFO-Eingangsspeicher 11 Daten im Header seiner Warteschlange enthält, werden diese ebenso verarbeitet, wie die Sekundärdaten des zugeordneten Pakets. Vorzugsweise wird die Größe des FIFO-Eingangsspeichers 11 gleich der Größe des Verwaltungs-Pufferspeichers 10 gewählt.
Dieser FIFO-Eingangsspeicher 11 gehört zu einem Übertragungsmodul 12 der Routingstufe 8, das mit dem Verwaltungsmodul 9 gekoppelt ist, auf das im Folgenden noch näher eingegangen wird.
Vorzugsweise weisen alle Anschlüsse der Eingangs- 3 und Ausgangsstufen 6 die gleiche Übertragungsgeschwindigkeit auf wie die Leitungs-Schnittstellenkarten, die mit dem Gerät 1 verbunden sind. Wie jedoch im Patent EP 00 440 281 beschrieben, kann man Leitungs-Schnittstellenkarten einsetzen, die eine Übertragungsgeschwindigkeit gleich einem ganzen Vielfachen der Geschwindigkeit der Eingangs- 4 und Ausgangsanschlüsse 7 aufweisen. Wenn die Übertragungsgeschwindigkeit der Anschlüsse beispielsweise gleich 2,4 Gbps beträgt, kann man einer Leitungsschnittstelle mit dem Format OC192c vier Anschlüsse zuordnen.
Zu diesem Zweck kann man jede Leitungsschnittstelle mit k aufeinander folgenden Anschlüssen [j, j + 1, ..., j + k – 1] verbinden. Der Fall k = 1 entspricht einer Leitungsschnittstelle, die mit nur einem Anschluss verbunden ist. Bei dieser Variante werden die beiden vorgenannten Fälle wie folgt geändert, wenn man davon ausgeht, dass das erste Wort eines Segments am Anschluss j + x empfangen wird (unter der Bedingung 0 ≤ x < k).
Wenn das erste Segment eines neuen Pakets eintrifft, ergibt sich unter Berücksichtigung der Tatsache, dass i den Wert für CFSA(0 + x) darstellt:

– MFSA(i): Adresse dieses ersten Segments im Pufferspeicher 5, die durch den Wert des Hauptzählers MCP(s) gegeben ist, wobei s die Größe des Pufferspeichers 5 ist.
– MPL(i) = 1;
– CFSA(0 + x) = CWA(0 + x); und
– CWA(n – 1) = CWA(0 + x) + 1(Modulo m).

Wenn es sich bei dem empfangenen Segment nicht um das erste Segment eines neuen Pakets handelt, ergibt sich unter Berücksichtigung der Tatsache, dass I den Wert für CFSA(0 + x) darstellt:

– MPL(i) = MPL(i) + 1(Modulo m).

In diesem Fall wird von den k Zählerpaaren (CWA, DVSA), die der Leitungsschnittstelle zugeordnet sind, nur das erste Paar verwendet.
Wie bereits erläutert, erfolgt die Auslesung des Pufferspeichers 10 des Verwaltungsmoduls 9 während der ersten halben Taktperiode MCL, die dafür vorgesehen ist. Wie in 6 dargestellt, wird die Adresse CFSA(0), in der die verschiedenen Anteile (oder Worte) ihres ersten Segments im Pufferspeicher 10 des Verwaltungsmoduls 9 gespeichert sind, jedes Mal, wenn ein Paket von der Routingstufe, und genauer gesagt von dem Verwaltungsmodul 9 vollständig empfangen wurde, in die Warteschlange des FIFO-Eingangspufferspeichers 11 eingestellt. Während der für das Schreiben in den FIFO-Speicher 11 dedizierten halben Taktperiode werden die folgenden Vorgänge ausgeführt:

– RR(i) = RR(i – 1);
– wenn der FIFO 11 nicht leer ist, wird der erste Wert an RR0 übertragen; vor der Übertragung nimmt jedes RR(i + 1) den Wert RR(i) an.

Diese Adresswerte werden zu einem späteren Zeitpunkt an das Verwaltungsmodul 9 weitergeleitet, damit dieses das eindeutige Wort (bzw. den Anteil), das in jedem Unterspeicher BM(r) seines Pufferspeichers 10 gespeichert ist, unter der von dem Wert des zugeordneten Registers RR(r) bezeichneten Adresse ausliest.
Natürlich kann sich die Adresse von einem Unterspeicher zum anderen verändern. Im Prinzip wird in jeder Taktperiode eine andere Spalte in jedem Unterspeicher BM(i) des Pufferspeichers 10 ausgelesen.
Die Anzahl an Registern RR ist gleich der maximalen Anzahl an zu analysierenden Anteilen, die in einem bestimmten Segment enthalten sind.
Diese Informationen (Primärdaten, Speicheradresse FSA(n) und Gesamtanzahl an zugeordneten Segmenten PL) werden dann praktisch gleichzeitig über n erste parallele Ausgänge vom Verwaltungsmodul 9 an das Übertragungsmodul 12 weitergeleitet.
Der Pufferspeicher 11 und die Register RR(r) gehören vorzugsweise zu einer Eingangsstufe 13 des Übertragungsmoduls 12, das außerdem ein Vermittlungsmodul 14 (oder „Barrel Shifter") umfasst, das mit n Eingängen ausgerüstet ist, an die jeweils Daten von den n ersten Ausgängen des Verwaltungsmoduls 9 übertragen werden.
Dieses Vermittlungsmodul 14 hat die Aufgabe, von den ersten Ausgängen des Verwaltungsmoduls 9 die Primärdaten, die in Form von Anteilen (oder Worten w(r)) angeordnet sind, und die zugeordneten Zusatzdaten (FSA(n) und PL(i)) zu empfangen, um diese über einen oder mehrere zweite Ausgänge 16 in dem vom Haupttaktgeber MCL festgelegten Takt an eine oder mehrere Routingeinheiten 15 weiterzuleiten. Genauer gesagt empfängt das Vermittlungsmodul 14 parallel die aufeinander folgenden Anteile der verschiedenen Segmente und leitet diese über seine verschiedenen zweiten Ausgänge 16 weiter, wobei darauf geachtet wird, sämtliche Anteile des gleichen Segments an den gleichen Ausgang 16 zu übertragen, damit die verschiedenen Segmente abschnittsweise parallel analysiert werden. Das Vermittlungsmodul 14 verfügt daher über n verschiedene und geordnete Zustände, und geht entsprechend der Taktperiode des Haupttaktgebers MCL von einem Zustand zum nächsten über.
Während der halben Taktperiode, die für das Schreiben in den Verwaltungs-Pufferspeicher 10 bestimmt ist, werden die folgenden Vorgänge ausgeführt:

– RR(i) = RR(i – 1);
– Wenn das nächste erste Wort w0 eines Segments, das im Unterspeicher BM(0) gespeichert ist, zur Verarbeitung an das Übertragungsmodul 12 übermittelt werden soll, wird die erste Adresse des Anteils, die im Header der Warteschlange des FIFO-Eingangsspeichers 11 gespeichert ist, an das erste Register RR(0) übertragen. Wenn der Warteschlangen-Header leer ist, wird ein Wert an das erste Register RR(0) übertragen, der angibt, dass kein entsprechendes Paket vorhanden ist.

Während der halben Taktperiode, die zum Auslesen des Verwaltungs-Pufferspeichers 10 bestimmt ist, werden die folgenden Vorgänge ausgeführt:

– Jede in einem Register RR(i) gespeicherte Adresse ermöglicht das Auslesen (oder Abrufen) des Worts w(i) (oder Anteils) aus dem zugeordneten Unterspeicher BM(i), das er enthält;
– Die ausgelesenen Anteile w(i) werden dann an die n ersten Ausgänge des Vermittlungsmoduls 14 übertragen, das sie in Abhängigkeit vom Zustand, in den es gesetzt wurde (von n verschiedenen Zuständen) an einen seiner zweiten Eingänge 16 weiterleitet;
– Parallel zu dieser Übertragung von Worten w(i) werden die Zusatzdaten (FSA(n) und PL(i)) an das Vermittlungsmodul 14 und anschließend an die gewählte Routingeinheit 15 weitergeleitet.

Beispiele für die Art und Weise der Auslesung und Weiterleitung von Anteilen (oder Worten) w(r) eines Segments sind in 8 und 9 dargestellt. In diesem Beispiel verwendet die Vermittlungseinheit 3 Ausgänge, sämtliche Anteile des gleichen Segments werden an den richtigen zweiten Ausgang weitergeleitet, jeweils ein Anteil pro Taktperiode. Zum Zeitpunkt t + 0 wird w0i ausgelesen und an den zweiten Ausgang i weitergeleitet. Zum Zeitpunkt t + 1 wird w1i ausgelesen und an den zweiten Ausgang i weitergeleitet; w0j wird ausgelesen und an den zweiten Ausgang j weitergeleitet. Zum Zeitpunkt t + 2 wird w2i ausgelesen und an den zweiten Ausgang i weitergeleitet; w1j wird ausgelesen und an den zweiten Ausgang j weitergeleitet; w0k wird ausgelesen und an den zweiten Ausgang k weitergeleitet. w2i wird ausgelesen und an den Unterspeicher BM(2) weitergeleitet, die Vermittlungseinheit 14 leitet es an i weiter, während w1j im Unterspeicher BM(1) ausgelesen und von der Vermittlungseinheit 14 an j weitergeleitet wird etc.
Vorzugsweise umfasst das Vermittlungsmodul 14 ebenso viele Eingänge wie zweite Ausgänge 16.
Die Anzahl an Routingeinheiten 15 wird in Abhängigkeit von der Übertragungsgeschwindigkeit der weiterzuleitenden Daten gewählt. Sie kann daher gleich der Anzahl an zweiten Ausgängen 16 des Vermittlungsmoduls 14 sein.
Wenn die Anzahl an Routingeinheiten 15 unter der Anzahl an n zweiten Ausgänge liegt, muss man gewährleisten, dass das abschnittsweise zu analysierende Segment nicht über einen zweiten Ausgang 16 übertragen wird, der zu diesem Zeitpunkt nicht der gewählten Routingeinheit zugeordnet ist. Diese Bedingung wird durch die Tatsache erfüllt, dass eine Adresse des ersten Segments von dem FIFO-Eingangsspeicher 11 nur unter der Bedingung an das erste Register RR(0) übertragen wird, dass das Vermittlungsmodul 14 in einem Zustand ist, der die Übertragung des Worts w(0), das von RR(0) im BM(0) bezeichnet wird, an eine verfügbare Routingeinheit 15 ermöglicht. Auf die gleiche Weise übermittelt man dem Vermittlungsmodul 14 das Wort w0, das vom RR(0) im BM(0) bezeichnet wird, wenn der Header der Warteschlange des FIFO-Eingangsspeichers 11 leer ist (d. h. wenn kein Paket vermittelt werden muss), begleitet von einem Bit, das angibt, dass das Segment leer ist.
Somit können höchstens n Segmente parallel im Verwaltungs-Pufferspeicher 10 des Verwaltungsmoduls 9 ausgelesen und parallel übertragen werden, um ebenfalls auf parallele Weise von den Routingeinheiten 15 über die zweiten Ausgänge 16 des Vermittlungsmoduls 14 analysiert zu werden.
Um die Analyse der geordneten Anteile des Segments durchzuführen, das von einem der zweiten Ausgänge 16 des Vermittlungsmoduls 14 übertragen wurde, umfasst jede Routingeinheit 15 einen wiederbeschreibbaren Speicher 17, in dem eine Routingtabelle gespeichert ist.
Vorzugsweise ist jede Routingtabelle vom Typ „Trie Table". Dieser Tabellentyp wird insbesondere im Dokument von V. Srinivasan und G. Varghese, 1999, „Fast address lookups using controlled prefix expansion", Transactions an Computer Systems 17, 1 (Feb.), 1–40, beschrieben.
Im Gegensatz zu einer Standard-Routingtabelle enthält eine Trie Table nicht alle Adressen und möglichen Adresskombinationen. Die Primärdaten sind daher in Zeilen in Form von Worten ersten und zweiten Typs gespeichert, die für die zum Routing der Sekundärdaten erforderlichen Präfixe repräsentativ sind. Ein Wort ersten Typs wird als „Zwischenwort" bezeichnet, da es dazu dient, ein anderes Wort der Routingtabelle zu kennzeichnen. Ein Wort zweiten Typs wird als „Endwort" bezeichnet, da es tatsächlich die primären Routingdaten (Tertiärdaten wie z. B. die Liste der Ausgänge 7, an die die Sekundärdaten übertragen werden sollen, neue primäre Routingdaten (oder Label), die den entsprechenden, an jeden bezeichneten Ausgangsanschluss 7 weiterzuleitenden Sekundärdaten zugeordnet werden sollen, gegebenenfalls begleitet von Zusatzinformationen, wie beispielsweise Dienstgüte) beinhaltet.
Wenn das Gerät gemäß der Erfindung Trie Tables einsetzt, ist in jeder Routingeinheit 15 ein Zwischenmodul 18 vorgesehen, das einen mit dem wiederbeschreibbaren Speicher 17 (in dem die Trie Table gespeichert ist) gekoppelten Ausgang und erste und zweite Eingänge umfasst, die jeweils Daten von einem der zweiten Ausgänge des Vermittlungsmoduls 14 und vom Ausgang des wiederbeschreibbaren Speichers 17 empfangen.
Die Analyse der vom Vermittlungsmodul 14 empfangenen Anteile (oder Worte) beginnt vorzugsweise immer mit der ersten Zeile R(0) der Routingtabelle. In jeder Taktperiode des Haupttaktgebers MCL bezeichnet der zu analysierende Anteil eine Adresse in der aktuellen Zeile R(j) der Routingtabelle (beim ersten Anteil eines Segments handelt es sich zunächst um die erste Zeile R(0)). Wenn das unter der bezeichneten Adresse ausgelesene (oder abgerufene) Wort ersten Typs ist (Zwischenwort), wird es an das Zwischenmodul 18 weitergeleitet. Der Wert dieses Worts bezeichnet die Adresse, unter der das nächste Wort in der nächsten Taktperiode ausgelesen werden muss. Solange es sich bei dem ausgelesenen Wort um ein Wort ersten Typs handelt, wird die Suchschleife wiederholt. Handelt es sich bei dem ausgelesenen Wort jedoch um ein Wort zweiten Typs (Endwort), wird es mit den Zusatzdaten FSA(n) und PL(i) sowie eventuell der Dienstgüte, wie aus 6 ersichtlich, an eine Ausgangsstufe 19 des Übertragungsmoduls 12 übertragen.
Auf diese Weise kann man Adressen mit variabler Länge analysieren.
Ein Beispiel für eine Trie Table ist in 10 dargestellt. In diesem Beispiel wird die Tabelle unter den folgenden Adressen initialisiert: A: 21.35.1C.43/32, B: C1.35/16, C: C1.35.BA/24, D: 18.2D/16. Jeder Anteil weist eine Länge von 4 Bit auf.
Wenn man entsprechend diesem Beispiel ein Paket mit der Zieladresse 18.2D.29.13 (Hexadezimalbezeichnung) empfängt, bezeichnen die ersten 4 Bit dieser Adresse (1) ein Wort in Zeile 0 (L0). Somit erhält man L0(1) = 9. Man nutzt dann den zweiten Anteil (hier gleich 8), um Zeile 9 zu adressieren (die durch den erhaltenen Wert gleich 9 bezeichnet wird). Somit erhält man L9(8) = 10. Anschließend verwendet man den dritten Anteil (hier gleich 2), um Zeile 10 zu adressieren (die durch den erhaltenen Wert gleich 10 bezeichnet wird). Somit erhält man L10(2) = 11. Anschließend verwendet man den vierten Anteil (hier gleich D), um Zeile 11 zu adressieren (die durch den erhaltenen Wert gleich 11 bezeichnet wird). Somit erhält man L11(D) = Endwort, wodurch diese Analyse beendet ist.
Die Ausgangsstufe 19 des Übertragungsmoduls 12 umfasst Ausgangs-Pufferspeicher 20, deren Anzahl gleich der Anzahl an Ausgangsanschlüssen 7 der Ausgangsstufe 6 der Datenübertragungsstufe 2 ist. Diese Ausgangsspeicher 20 sind vorzugsweise vom Typ FIFO. Vorzugsweise umfasst die Ausgangsstufe 20 außerdem einen Multiplexer 21, der Daten von den Ausgängen der Routingeinheiten 15(j) empfängt und die neuen Primärdaten, die für die jeweils zugeordneten Ausgangsanschlüsse 7 bestimmten Tertiärdaten, die Speicheradresse FSA(s) im Pufferspeicher 5 für die zu vermittelnden Sekundärdaten und die entsprechende Gesamtanzahl an Segmenten PL an die verschiedenen FIFO-Ausgangsspeicher 20 überträgt.
In einer Variante kann man jedem Ausgangsanschluss 7 eine Gruppe von FIFO-Ausgangsspeichern 20 zuordnen, wenn die Routingtabellen auch Zusatzinformationen beinhalten, wie z. B. die Dienstgüte (QoS). Jede Gruppe umfasst dann einen FIFO-Ausgangsspeicher, der der entsprechenden Dienstgüte zugeordnet ist.
Der Multiplexer 21 ist entsprechend ausgeführt, um an die FIFO-Ausgangsspeicher, die den Ausgangsanschlüssen 7 zugeordnet sind, in jeder Taktperiode des Haupttaktgebers MCL die Daten zu übertragen, die von einer der Routingeinheiten 15(j) stammen. Auf diese Weise werden die verschiedenen Routingeinheiten 15(j) vom Multiplexer 21 nacheinander berücksichtigt.
Die I FIFO-Ausgangsspeicher 20 werden auf zyklische Weise abgefragt. Ein FIFO-Speicher 20 wird in jeder Taktperiode des Haupttaktgebers MCL ausgelesen, wobei ein Zyklus I Taktperioden umfasst. Während der Taktzeit i (Modulo I), wenn kein Paket am Ausgangsanschluss i(7) übertragen werden soll, wird der zugeordnete FIFO-Ausgangsspeicher (20) ausgelesen und übermittelt seinen Inhalt (Adresse FSA(s), Anzahl an zugeordneten Segmenten PL und Label), so dass die zugeordneten Sekundärdaten in der nächsten Taktperiode an den Ausgangsanschluss i(7) übertragen werden können, nachdem neue Primär- und Tertiärdaten hinzugefügt wurden.
Die vorstehend beschriebenen Datenübertragungs- 2 und Routingstufen 8 haben lediglich Beispielcharakter und können Gegenstand zahlreicher Varianten und Anpassungen sein. Sie können insbesondere als separate, jedoch miteinander verbundene Schaltungen oder als einzelne Schaltung ausgeführt werden, die gegebenenfalls auf der gleichen Leiterplatte integriert sind. Im Übrigen bestehen diese Stufen im Wesentlichen aus elektronischen Komponenten, sie können jedoch auch Softwaremodule umfassen, die insbesondere dazu dienen, ihre jeweiligen und/oder gemeinsamen Funktionen zu steuern.
Die Erfindung bietet außerdem ein Verfahren zum Routing von Sekundärdaten, die primären Routingdaten und einer Speicheradresse FSA(s) zugeordnet sind, in der man ausgehend von den Primärdaten und den in mindestens einer Routingtabelle gespeicherten Daten Tertiärdaten ermittelt, die mindestens einen Ausgangsanschluss 7 und neue primäre Routingdaten bezeichnen, anschließend überträgt man die ermittelten Primär- und Tertiärdaten, so dass zumindest bestimmte der neuen Primärdaten mit den weiterzuleitenden Sekundärdaten, die unter der Speicheradresse FSA(s) gespeichert sind, kombiniert und anschließend an jeden von den Tertiärdaten bezeichneten Ausgangsanschluss 7 übertragen werden.
Dieses Verfahren kann mit Hilfe der oben beschriebenen Geräte umgesetzt werden. Die hauptsächlichen und optionalen Funktionen und Unterfunktionen, die von den Schritten dieses Verfahrens gewährleistet werden, sind praktisch identisch mit den Funktionen, die von den verschiedenen Einrichtungen, aus denen die Geräte bestehen, gewährleistet werden, daher werden im Folgenden nur die Schritte aufgeführt, in denen die Hauptfunktionen des Verfahrens gemäß der Erfindung umgesetzt werden.
Das Verfahren ist durch die Tatsache gekennzeichnet, dass seine Ermittlungsphase darin besteht, erstens in n Unterspeichern BM(r) unter gewählten Adressen die Anteile jedes Segments zu speichern, die sich aus der Zerlegung der empfangenen, weiterzuleitenden Datenpakete ergeben, und zweitens die gewählten Speicheradressen der ersten, nacheinander empfangenen Segmente an gewählten Stellen zu speichern und anschließend in Abhängigkeit von einem gewählten Kriterium aus den Unterspeichern BM(r) die unter den Speicheradressen für die ersten Segmente gespeicherten Anteile, die an bestimmten gewählten Stellen abgelegt sind, gleichzeitig und parallel diese Segmentanteile auszulesen, und drittens die Anteile, die zu verschiedenen Segmenten gehören, an eine oder mehrere Routingtabellen (je nach Bedarf) weiterzuleiten, um ausgehend von den in diesen Routingtabellen gespeicherten Daten und einer Analyse der verschiedenen Segmente abschnittsweise, parallel die Primär- und Tertiärdaten zu ermitteln, die den verschiedenen weiterzuleitenden Sekundärdaten zuzuordnen sind.
Vorzugsweise werden die Routingdaten verarbeitet, nachdem sie in Segmente mit gleicher Länge zerlegt wurde, z. B. in einer Vorstufe.
Im Übrigen ist es vorteilhaft, die Speicheradressen der n ersten, nacheinander empfangenen Segmente in n parallelen, praktisch identischen Registern zu speichern. Ebenso kann man bis zu n Segmente parallel verarbeiten, sobald man ebenso viele Routingtabellen wie Unterspeicher BM(r) vorsieht.
Gemäß einem anderen Merkmal des Verfahrens ist jede Routingtabelle vom Typ „Trie Table". In diesem Fall liest man aus der Routingtabelle während der Ermittlungsphase das unter der Adresse gespeicherte Wort aus, das von dem Anteil des empfangenen Segments bezeichnet wird, leitet dieses Wort anschließend an die neue Routingtabelle oder die Ausgangsanschlüsse (die mit dem Multiplexer 21 verbunden sind) weiter, je nachdem, ob das ausgelesene Wort ersten oder zweiten Typs ist, und jedes Mal, wenn ein Wort ersten Typs übermittelt wird, liest man aus der Tabelle ein weiteres, unter der von dem übermittelten Wort bezeichneten Adresse gespeichertes Wort aus, bis man ein Wort zweiten Typs erhält.
Dank der Erfindung ist das Routinggerät für den verwendeten Routingprotokolltyp transparent. Es ist daher ausreichend, die Routingtabellen für die Funktion entsprechend dem gewählten Protokoll (z. B. IPV4 oder IPV6) zu konfigurieren.
Im Übrigen ermöglicht die Erfindung durch Auswahl der entsprechenden Anzahl an parallelen Routingeinheiten die Anpassung an jede Art von Übertragungsgeschwindigkeit, und sie behält den sequenziellen Charakter der Datenpakete, die zum gleichen Datenfluss gehören, bei.
Einerseits kann das Gerät gemäß der Erfindung in Vermittlungsstellen/Router mit verteilter oder zentraler Architektur integriert werden. Unter „zentraler Architektur" versteht man in der vorliegenden Beschreibung eine Architektur, in der die Hauptfunktionen eines Routers oder einer Vermittlungsstelle, die üblicherweise nicht mit einer Leitungsschnittstelle verbunden sind, zentral (bzw. gemeinsam) genutzt werden, wie beispielsweise Schreiben in einem Pufferspeicher, Vermittlung, Routing, Verkehrssteuerung und Dienstgüte.
Die Erfindung bietet außerdem die Möglichkeit, ein Routing im Rundsende-Modus („Broadcast") oder im Punkt-zu-Mehrpunkt-Modus („Multicast") auszuführen, allerdings unter dem Vorbehalt, dass die maximale Anzahl an Zweigen im Mehrpunkt-Sendebaum der Anzahl an Anschlüssen des Geräts entspricht.
Außerdem bietet die Erfindung die Möglichkeit, für die Leitungsschnittstellen einen beliebigen Protokolltyp sowie eine beliebige Anzahl an Leitungsschnittstellen einzusetzen, einschließlich Übertragungsgeschwindigkeiten vom Typ OC192c oder darüber.
Die Erfindung ist nicht auf die vorstehend beschriebenen Ausführungsvarianten für die Geräte und das Verfahren beschränkt, die lediglich Beispielcharakter haben, sondern sie umfasst sämtliche Varianten, der der Fachmann im Rahmen der folgenden Ansprüche umsetzen kann.

Claims

Datenroutinggerät, bestehend aus i) einem Verwaltungsmodul (9), das entsprechend ausgeführt ist, um primäre Routingdaten und eine Speicheradresse (FSA(s)) für die den genannten Primärdaten zugeordneten Sekundärdaten zu empfangen, und ii) einem Übertragungsmodul (12), das entsprechend ausgeführt ist, um ausgehend von diesen Daten und von den in mindestens einer Routingtabelle gespeicherten Daten die Tertiärdaten (und neue Routing-Primärdaten) zu ermitteln, wobei die Tertiärdaten mindestens einen Ausgangsanschluss (7) einer Stufe (2) für die Datenübertragung bezeichnen, und um die ermittelten Primär- und Tertiärdaten an die genannte Übertragungsstufe (2) zu übermitteln, so dass zumindest bestimmte der genannten neuen Primärdaten mit den genannten Sekundärdaten, die unter der genannten Speicheradresse (FSA(s)) gespeichert sind, kombiniert und anschließend an jeden Ausgangsanschluss (7) übertragen werden, der von den genannten Tertiärdaten bezeichnet wird, dadurch gekennzeichnet, dass das genannte Verwaltungsmodul (9) einen Pufferspeicher (10) umfasst, der in n Unterspeicher unterteilt ist, die jeweils in der Lage sind, einen Anteil jedes Segments, der aus der Zerlegung von empfangenen, zu vermittelnden Datenpaketen resultiert, d. h. das erste Segment unter einer gewählten Adresse zu speichern, und gleichzeitig auf einen Befehl hin über n erste parallele Ausgänge einen der gespeicherten Anteile zu übertragen, sowie dadurch, dass das Übertragungsmodul (12) entsprechend ausgeführt ist, um i) vom Verwaltungsmodul (9) die gewählten Speicheradressen der ersten Segmente der zu vermittelnde Pakete zu empfangen und ii) bestimmte dieser Speicheradressen in Abhängigkeit von einem ausgewählten Kriterium an das Verwaltungsmodul zu übertragen, um im Gegenzug an den ersten parallelen Ausgängen die unter den genannten Speicheradressen gespeicherten Segmentanteile zu empfangen, und iii) die Anteile, die zu verschiedenen Segmenten gehören, an mindestens eine Routingtabelle (15-1, ... 15-j) weiterzuleiten, um ausgehend von den in diesen Routingtabellen gespeicherten Daten und einer abschnittsweisen Analyse der verschiedenen Segmente die genannten Primär- und Tertiärdaten zu ermitteln, die den verschiedenen zu vermittelnden Sekundärdaten zugeordnet sind.
Gerät gemäß Anspruch 1, dadurch gekennzeichnet, dass das genannte Übertragungsmodul (12) mindestens zwei Routingtabellen (15) umfasst, um die parallele Analyse der verschiedenen Segmente zu gewährleisten.
Gerät gemäß einem der Ansprüche 1 und 2, dadurch gekennzeichnet, dass das genannte Verwaltungsmodul (9) entsprechend ausgeführt ist, um die Daten in Form von Segmenten mit gleicher Länge zu empfangen.
Gerät gemäß einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass das genannte Verwaltungsmodul (9) und das genannte Übertragungsmodul (12) eine Routingstufe (8) vom Typ L3F darstellen.
Gerät gemäß einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass das Übertragungsmodul (12) eine Eingangsstufe (13) umfasst, die i) mit n Registern (RR), die in der Lage sind, die Speicheradressen von n ersten Segmenten zu speichern, ii) mit einem Eingangspufferspeicher (11), der in der Lage ist, die genannten gewählten Adressen der genannten ersten Segmente vom Verwaltungsmodul (9) zu empfangen, um diese an die genannten Register (RR) zu übertragen, und iii) mit einem Vermittlungsmodul (14) ausgerüstet ist, das i) n Eingänge, die jeweils n Segmentanteile von den n ersten parallelen Ausgängen empfangen, und ii) mindestens einen zweiten Ausgang (16) umfasst, der in der Lage ist, die genannten, übermittelten Anteile, die zu verschiedenen Segmenten gehören, weiterzuleiten.
Gerät gemäß Anspruch 5, dadurch gekennzeichnet, dass das Vermittlungsmodul (14) n Eingänge und n zweite Ausgänge umfasst.
Gerät gemäß einem der Ansprüche 2 bis 5 in Kombination mit Anspruch 6, dadurch gekennzeichnet, dass das genannte Übertragungsmodul (12) eine Anzahl an Routingeinheiten (15) umfasst, die zwischen 1 und n beträgt, wobei die genannten Routingeinheiten verschiedene Segmentanteile von den genannten zweiten Ausgängen (16) empfangen, jeweils einen wiederbeschreibbaren Speicher (17) umfassen, in dem eine der Routingtabellen gespeichert ist, und in der Lage sind, die genannten, den verschiedenen zu vermittelnden Sekundärdaten zugeordneten Primär- und Tertiärdaten parallel zu ermitteln.
Gerät gemäß einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, dass die Primärdaten, die die Worte definieren, die für die Routingpräfixe repräsentativ sind, in jeder Routingtabelle in Form von Zeilen gespeichert sind, wobei jeder empfangene Segmentanteil die Möglichkeit bietet, eines der genannten Worte einer Zeile zu adressieren.
Gerät gemäß Anspruch 8, dadurch gekennzeichnet, dass in jeder Routingtabelle Primärdaten gespeichert sind, die für die Worte ersten und zweiten Typs repräsentativ sind.
Gerät gemäß einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass das genannte Übertragungsmodul (12) eine Ausgangsstufe (19) umfasst, die mit Ausgangspufferspeichern (20) ausgerüstet ist, deren Anzahl der Anzahl an Ausgangsanschlüssen (7) der Übertragungsstufe (2) entspricht und die in der Lage sind, die genannten Tertiärdaten, die genannten neuen Primärdaten und die genannte Speicheradresse (FSA(s)) der Routingeinheiten (15) zu empfangen.
Gerät gemäß einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass das genannte Übertragungsmodul (12) eine Ausgangsstufe (19) umfasst, die mit Gruppen von Pufferspeichern (20) ausgerüstet ist, deren Anzahl der Anzahl an Ausgangsanschlüssen (7) der Übertragungsstufe (2) entspricht, wobei jede Gruppe in der Lage ist, die genannten Tertiärdaten, die genannten neuen Primärdaten und die genannte Speicheradresse (FSA(s)) der Routingeinheiten (15) zu empfangen.
Gerät gemäß Anspruch 11, dadurch gekennzeichnet, dass die Ausgangspufferspeicher (20) einer Gruppe unterschiedlichen Dienstguten zugeordnet sind.
Gerät gemäß einem der Ansprüche 10 bis 12, dadurch gekennzeichnet, dass die genannte Ausgangsstufe (19) einen Multiplexer (21) umfasst, der Daten von den Routingeinheiten (15) empfängt und diese an die genannten Ausgangspufferspeicher (20) überträgt.
Gerät gemäß Anspruch 9 in Kombination mit einem der Ansprüche 10 bis 13, dadurch gekennzeichnet, dass jede Routingeinheit (15) i) ein Zwischenmodul (18), das einen mit dem wiederbeschreibbaren Speicher (17) verbundenen Ausgang und erste und zweite Eingänge umfasst, die jeweils Daten von einem der zweiten Ausgänge der Eingangsstufe (13) und von dem Ausgang des genannten wiederbeschreibbaren Speichers (17) empfangen, umfasst und ii) entsprechend ausgeführt ist, um das unter der von dem empfangenen Anteil bezeichneten Adresse gespeicherte Wort aus der Routingtabelle auszulesen und das genannte Wort anschließend an den Ausgang des genannten wiederbeschreibbaren Speichers zu übertragen, so dass die Daten an den zweiten Eingang des Zwischenmoduls (18) oder die genannte Ausgangsstufe (19) übertragen werden, je nachdem, ob das genannte ausgelesene Wort ersten oder zweiten Typs ist, sowie dadurch, dass das genannte Zwischenmodul (18) entsprechend ausgeführt ist, um beim Empfang von Daten, die für ein Wort ersten Typs repräsentativ sind, das unter der durch das genannte Wort ersten Typs bezeichneten Adresse gespeicherte Wort aus der Routingtabelle auszulesen, das genannte Wort anschließend an den genannten Ausgang des genannten wiederbeschreibbaren Speichers (17) zu übertragen, so dass es an den zweiten Eingang des Zwischenmoduls (18) oder an die genannte Ausgangsstufe (19) weitergeleitet wird, je nachdem, ob das genannte ausgelesene Wort ersten oder zweiten Typs ist.
Gerät gemäß einem der Ansprüche 1 bis 14, dadurch gekennzeichnet, dass zumindest bestimmte der genannten Pufferspeicher (11, 20) vom Typ „FIFO" sind.
Gerät gemäß einem der Ansprüche 1 bis 15, dadurch gekennzeichnet, dass es die genannte Datenübertragungsstufe (2) umfasst.
Gerät zur Vermittlung von Datenpaketen, dadurch gekennzeichnet, dass es ein Datenroutinggerät gemäß einem der vorgenannten Ansprüche umfasst.
Verfahren zum Routing von Sekundärdaten, die primären Routingdaten und einer Speicheradresse (FSA(s)) zugeordnet sind, in dem man i) ausgehend von diesen Primärdaten und von Daten, die in mindestens einer Routingtabelle gespeichert sind, Tertiärdaten, die mindestens einen Ausgangsanschluss (7) bezeichnen, sowie neue primäre Routingdaten ermittelt, anschließend ii) die genannten ermittelten Primär- und Tertiärdaten weiterleitet, so dass zumindest bestimmte der genannten neuen Primärdaten mit den genannten Sekundärdaten, die unter der genannten Speicheradresse (FSA(s)) gespeichert sind, kombiniert und anschließend an jeden Ausgangsanschluss (7), der von den genannten Tertiärdaten bezeichnet wird, übertragen werden, dadurch gekennzeichnet, dass die genannte Ermittlung darin besteht, i) in n Unterspeichern unter gewählten Adressen n Anteile jedes Segments, das sich aus einer Zerlegung von empfangenen, zu vermittelnden Daten ergibt, d. h. die ersten Segmente zu speichern, ii) an gewählten Stellen die gewählten Speicheradressen der ersten Segmente zu speichern und anschließend in Abhängigkeit von einem gewählten Kriterium aus den genannten Unterspeichern die Anteile parallel auszulesen, die unter den genannten Speicheradressen gespeichert sind, die an bestimmten der genannten gewählten Stellen gespeichert sind, um die genannten Segmentanteile gleichzeitig und parallel zu übertragen, und iii) um die Anteile, die zu verschiedenen Segmenten gehören, an mindestens eine Routingtabelle zu übertragen, um ausgehend von den in diesen Routingtabellen gespeicherten Daten und einer abschnittsweisen Analyse der verschiedenen Segmente die genannten Primär- und Tertiärdaten zu ermitteln, die den verschiedenen zu vermittelnden Sekundärdaten zugeordnet werden sollen.
Verfahren gemäß Anspruch 18, dadurch gekennzeichnet, dass die Daten in Form von Segmenten mit gleicher Länge empfangen werden.
Verfahren gemäß einem der Ansprüche 18 und 19, dadurch gekennzeichnet, dass das Routing vom Typ L3F ist.
Verfahren gemäß einem der Ansprüche 18 bis 20, dadurch gekennzeichnet, dass die genannten Speicheradressen der ersten Segmente in n Registern gespeichert werden.
Verfahren gemäß einem der Ansprüche 18 bis 21, dadurch gekennzeichnet, dass ebenso viele Routingtabellen wie Unterspeicher vorgesehen werden.
Verfahren gemäß einem der Ansprüche 18 bis 22, dadurch gekennzeichnet, dass die Primärdaten, die die Worte definieren, die für die Routingpräfixe repräsentativ sind, in jeder Routingtabelle in Form von Zeilen gespeichert sind, wobei jeder empfangene Segmentanteil die Möglichkeit bietet, eines der genannten Worte einer Zeile zu adressieren.
Verfahren gemäß Anspruch 23, dadurch gekennzeichnet, dass in jeder Routingtabelle Primärdaten gespeichert sind, die für Worte ersten und zweiten Typs repräsentativ sind.
Verfahren gemäß Anspruch 24, dadurch gekennzeichnet, dass während der genannten Ermittlung das unter der von dem empfangenen Segmentanteil bezeichneten Adresse gespeicherte Wort aus der Routingtabelle ausgelesen wird, das genannte Wort anschließend übertragen wird, so dass es an die genannte neue Routingtabelle oder an die genannten Ausgangsanschlüsse (7) weitergeleitet wird, je nachdem, ob das genannte ausgelesene Wort ersten oder zweiten Typs ist, und jedes Mal, wenn ein Wort ersten Typs übertragen wird, wird aus der genannten Tabelle ein weiteres, unter der von dem genannten übertragenen Wort bezeichneten Adresse gespeichertes Wort ausgelesen, bis ein Wort zweiten Typs ermittelt wird.
Einsatz des Geräts und des Verfahrens gemäß einem der vorgenannten Ansprüche mit IP-Routingstandards oder verbindungslosen Protokollen.