DE69331672T2

DE69331672T2 - Adressenerkennungsvorrichtung

Info

Publication number: DE69331672T2
Application number: DE69331672T
Authority: DE
Inventors: Stuart F. Bryant; Fearghal Morgan; Joseph O'callaghan; Una M. Quinlan; John Rigby; Michael J. Seaman; Andrew Walton
Original assignee: Cabletron Systems Inc
Current assignee: Enterasys Networks Inc
Priority date: 1992-01-10
Filing date: 1993-01-08
Publication date: 2002-11-21
Anticipated expiration: 2013-01-09
Also published as: US5519858A; EP0551243A3; JPH05274347A; EP0551243B1; DE69331672D1; EP0551243A2

Description

Gebiet der Erfindung

Die Erfindung bezieht sich auf Computernetzwerke und insbesondere auf eine Adressen-Erkennungsvorrichtung, die zum Speichern und Nachschlagen von Netzwerkadressen-Information verwendet wird.

Hintergrund der Erfindung

Die Fähigkeit von Computern, miteinander zu kommunizieren, wurde zu einer grundlegenden Eigenschaft der modernen Informationsverarbeitung. Nutzer-Anwendungen, die von der Fähigkeit eines der Nutzer-Anwendung ausführenden Computers abhängen, eine Daten an weitere Computer zu senden und von diesen zu empfangen, nehmen ständig zu. Die Kommunikationsfähigkeit ist für die Nutzeranwendungapplikation notwendig, um die Aufgabe für die die Anwendung entwickelt wurde, ausführen zu könen, oder Information an weitere Benutzer innerhalb einer Gruppe oder Organisation vermitteln zu können. Eine besondere Anwendung kann beispielsweise ausgestaltet sein, Unterprogramme aufzurufen, die für bestimmte Datenverarbeitungsfunktionen auf einem weiteren Computer laufen, oder auf eine entfernte Datenbank zuzugreifen, um Eingabedaten zu erhalten oder Ergebnisse zu speichern.
Eine wichtige Aufgabe beim Bereitstellen von Kommunikationsfähigkeit zwischen Computern besteht darin, sämtliche Datenbank- und Verarbeitungsresourcen der Gruppe oder Organisation für jeden anderen Benutzer in der Gruppe oder Organisation verfügbar zu machen. Als Antwort auf den wachsenden Bedarf für ausgeklügelte Kommunikationsfähigkeiten zwischen Computern wurden Netzwerk-, Routing- and Brückenprotokolle, wie beispielsweise IP, DECnet, OSI, etc., entwickelt, um Datenübertragungen zwischen in einem Netzwerk miteinander verknüpften Computern zu steuern. Die verschiedenen Protokolle werden bei Übertragungsdiensten implementiert, die verwendet werden, um Computer miteinander zu koppeln.
Jedes Protokoll ist typischerweise hinsichtlich einer Anzahl von Schichten definiert, wobei sich jede Schicht auf einen bestimmten Aspekt der für die Datenübertragungen überall in einem Netzwerk erforderlichen Funktionalität bezieht. Beispielsweise werden die ersten drei Schichten als eine physikalische Schicht, eine Datenverknüpfungsschicht und eine Netzwerkschicht definiert. Die physikalische Schicht ist auf die physikalischen und elektrischen Spezifikationen einer physikalischen Verbindung, beispielsweise eines Busses, gerichtet, der die Computer eines Netzwerks miteinander koppelt. Die physikalische Schicht steuert Bit-Übertragungen durch die Verbindung so, dass eine Reihe von Bits eines Datenpakets von einem Rechner auf dem Netzwerk zu einem weiteren Rechner auf dem Netzwerk übermittelt werden können. Die physikalische Schicht setzt die Spannungspegel für logische Einsen und Nullen, das Timing der stabilen Bit- Information auf dem Bus, usw., wie es notwendig ist, um die Bits eines Datenpakets über einen Bus zu übertragen.
Die Datenverknüpfungsschicht ist auf das Packen oder Blockbilden (framing)von bei einer Datenübertragung empfangenen Bits in ein definiertes Paket gerichtet, das frei von Übertragungsfehlern ist. Die Datenverknüpfungsschicht erzeugt und erkennt Grenzen zwischen Bits, um Bit-Felder zu definieren. Die Bits zwischen Grenzen verleihen den Bits eines Datenpakets Struktur und Bedeutung. Beispielsweise kann das Datenpaket einen Header mit den ersten n Bits einer Übertragung für Computer-Ursprungs- und -Zieladressen- Information, die Länge des Datenpakets in Bytes, das verwendete Netzwerkprotokoll usw. umfassen. Dem Header können zu einem Block zusammengefasste Daten-Bytes folgen, welche die tatsächliche, zwischen zwei oder mehr Computern auf dem Netzwerk übertragene Nachricht enthalten.
Die Netzwerkschicht ist auf die Steuerung der Weiterleitung von Information gerichtet, die erforderlich ist, um eine Nachricht von einem Ursprungs-Computer an einen Ziel-Computer des Netzwerks zu senden. Jedes Protokoll definiert die Länge und den Inhalt für eine Netzwerkadresse, um jeden Ursprung oder jedes Ziel von Datenpaketen und das Verarbeitungsschema zur Weiterleitung eines Datenpakets durch ein Netzwerk eindeutig zu identifizieren. Die Netzwerkadressen-Information befindet sich in einem der Bit- Felder eines Datenpakets, wie es durch das von dem Protokoll definierte Datenverknüpfungsschicht-Verarbeitungsschema umrahmt ist.
Netzwerke werden allgemein in Lokalbereichsnetzwerke (LANs) und Weitbereichsnetzwerke (WANs) angeordnet. Ein LAN koppelt Computer, die physisch relativ nahe zueinander, beispielsweise in dem gleichen Gebäude, positioniert sind. Ein WAN koppelt Computer, die in unterschiedlichen Städten oder sogar auf unterschiedlichen Kontinenten gelegen sein können. Ein WAN umfasst gewöhnlich Komponenten wie beispielsweise Router. Jeder Router ist angepasst, um ein Datenpaket von einem Ursprungscomputer auf einem LAN zu empfangen und das Datenpaket an einen Zielcomputer auf einem weiteren LAN weiterzuleiten.
Der Router verarbeitet eine Netzwerkadresse eines Datenpakets gemäß einem in dem Netzwerk verwendeten Übertragungsdienst implementierten Protokoll, um zu bestimmen, wie das Datenpaket weiterzuleiten ist, z. B. an einen weiteren Router, der direkt mit dem Empfangs-LAN oder einem Zwischen-Router gekoppelt ist, etc. Jeder Router speichert Information über die Topologie des Netzwerks zur Verwendung beim Weiterleiten jedes Datenpakets.
Eine Brücke bzw. Koppelelement ist eine weitere Komponente, die verwendet werden kann, um Datenpakete von Computern eines LANs an Computer eines anderen LAN zu übertragen. Eine Brücke koppelt unterschiedliche LANs und überwacht Kommunikationen innerhalb und zwischen den LANs, um Ausgangs- und Zieladressen-Information zu "lernen". Die Brücke lernt und "altert" Adressen-Information kontinuierlich, um die Übertragung eines Datenpakets zwischen LANs zu bewältigen.
Typischerweise hat jede der Brücken- und Router- Komponenten Zugriff auf eine Nachschlagedatenbank, die Brücken- bzw. Routing-Information enthält, die sich auf die Netzwerkadressen der Ursprünge und Ziele der Daten in dem bestimmten Netzwerk beziehen, das von dem jeweiligen Router oder der jeweiligen Brücke bedient wird. Eine Adressen- Erkennungsmaschine kann als eine Resource für einen Router oder eine Brücke zum Zugriff auf die Nachschlagedatenbank implementiert sein.
Der Router oder die Brücke arbeiten, um die Netzwerkadresse aus dem Header einer an dem Router oder der Brücke empfangenen Datenübertragung zu extrahieren, und gibt die Adresse in die Adressen-Erkennungsmaschine ein. Die Adressen-Erkennungsmaschine verwendet die eingegebene Netzwerkadresse als Index für den Durchlauf der Nachschlagedatenbank, um einen Eintrag zu lokalisieren, der der Netzwerkadresse entspricht. Der Eintrag enthält von dem Router oder der Brücke aufgeforderte Protokoll-Information zum Leiten der Datenübertragung an das gekennzeichnete Ziel.
Es ist anzumerken, dass die Art und der Inhalt der Information, die in einem Datenbank-Eintrag gespeichert wird, davon abhängt, ob ein Router oder eine Brücke in dem Netzwerk aufgrund der unterschiedlichen Betriebsmerkmale von Routing- und Brückenbildungs-Vorgängen implementiert wurden. Außerdem werden die Größe und das Format der Netzwerkadresse und die Art und der Inhalt der auf die Netzwerkadresse bei einem bestimmten Netzwerk bezogenen Netzwerk-Information von dem in dem Netzwerk implementierten Netzwerkprotokoll definiert. Dem gemäß muss die Struktur einer Nachschlagedatenbank ausgestaltet sein, um entweder eine Brückenbildung oder ein Routing sowie auch die Anforderungen der Adressenlänge und des Informations-Inhaltsdes Protokolls zu vewältigen, das bei dem Netzwerk verwendet wird, in dem die Brücke oder der Route r arbeitet. Somit würde eine Nachschlagedatenbank, die ausgestaltet ist, um einen Router in einem Netzwerk zu unterstützen, das beispielsweise ein DECnet-Protokoll implementiert, nicht zur Verwendung durch eine Brücke geeignet sein, usw..
Die EP 0 408 188 beschreibt eine Adressen- Erkennungsmaschine, in der eine Netzwerk-Zieladresse verwendet wird, um auf eine Weiterleitungs-Datenbank zuzugreifen. Eine TRIE-Datenbank wird zur Übereinstimmung aufeinander folgender Fragmente der Netzwerk-Zieladresse verwandet, wenn die Knoten des TRIE durchlaufen werden, um schließlich einen Index an die Weiterleitungs-Datenbank zurückzugeben.

Zusammenfassung der Erfindung

Die Erfindung in ihrer breitgefassten Form beruht in einer Adressen-Erkennungsvorrichtung, wie es in Anspruch 1 dargelegt ist. Hier ist spezifisch eine Adressen- Erkennungsverrichtung beschrieben, die in der Ausgestaltung flexibel und bei Weiterleitungs- und Brückenbildungsvorgängen im Zusammenhang mit verschiedenen, unterschiedlichen Netzwerkprotokollen brauchbar ist. Auf diese Art und Weise kann eine einzige Adressen-Erkennungsvorrichtung gemäß der Erfindung einen Router, eine Brücke oder beide gleichzeitig bedienen, und zur gleichen Zeit Nachschlagevorgänge für verschiedene, unterschiedliche Protokolle unterstützen. Die Adressen-Erkennungsvorrichtung ist auch so strukturiert, dass sie eine große Menge von Netzwerk-Informationsdaten in einem wirtschaftlichen und effizienten Nachschlagschema bewältigt, so dass die Adressen-Erkennungsmaschine mehrere Routing- und Brückenbildungskomponenten als eine gemeinsam genutzte Ressource bedienen kann.
Im allgemeinen umfasst die Adressen- Erkennungsvorrichtung gemäß einer weiteren Ausführungsform der Erfindung eine Adressen-Erkennungsmaschine, die mit einer Nachschlagedatenbank gekoppelt ist. Die Nachschlagedatenbank umfasst eine primäre Datenbank und eine sekundäre Datenbank. Die Adressen-Erkennungsmaschine nimmt als eine Eingabe die aus einer Datenübertragung extrahierte Netzwerkadresse an. Die Adressen-Erkennungsmaschine verwendet die Netzwerkadresse als Index in der primären Datenbank. Die primäre Datenbank umfasst eine Mehrweg-Baumknotenstruktur (TRIE), die zum Durchlaufen der Knoten als eine Funktion vorausgewählter Segmente der Netzwerkadresse und einer festgelegten Sequenz der Segmente angeordnet ist, um einen Zeiger auf einem Eintrag in der sekundären Datenbank zu lokalisieren.
Die TRIE-Struktur weist eine vorhersagbare Suchzeit auf, erfordert keinen umfangreichen Speicher für Vergleiche von Zahlzeichenwerten, um einen Knotenzeiger auszuwählen, und kann mit einem wirtschaftlichen Umfang an Speicherplatz, insbesondere bei einem spärlich mit Einträgen versehenen Adressenraum, wie es häufig bei Netzwerken der Fall ist, implementiert werden. Somit stellt die TRIE-Struktur der primären Datenbank einen schnellen Zugriff auf eine große Datenmenge bereit, wie es der Fall sein würde, wenn die Adressen-Erkennungsmaschine als eine gemeinsam genutzte Ressource zu verwenden ist.
Jedes Segment der als Index von der Adressen- Erkennungsmaschine verwendeten Netzwerkadresse lokalisiert einen Knoten, der Zeiger auf nachfolgende Knoten enthält, wobei jeder Zeiger eines bestimmten Knotens durch einen der möglichen Werte eines nachfolgenden Segments der Adresse definiert wird. Das Durchlaufen der Knoten beginnt bei einem Stammknoten und setzt sich durch eine Sequenz von Übergangsknoten gemäß der Sequenz von Segmenten der Netzwerkadresse fort, bis ein Abschluß- oder Endknoten erreicht ist. Jeder Abschlußknoten speichert den Zeiger auf dem sekundären Datenbankeintrag, der der Netzwerkadresse entspricht, die verwendet wurde, um den Abschlußknoten zu erreichen. Der Eintrag in der sekundären Datenbank, auf den von dem primären Datenbankzeiger gezeigt wird, enthält Information, die für den Router oder die Brücke gegebenenfalls notwendig ist, um die Datenübertragung zu ihrem beabsichtigten Ziel hin zu lenken.
Gemäß einem Merkmal einer weiteren Ausführungsform der Erfindung umfasst die Adressen-Erkennungsmaschine eine Tabelle zum Speichern mehrerer Datenbank-Spezifikatoren.
Jeder der Datenbank-Spezifikatoren enthält Steuer-Information für den Durchlauf der primären und sekundären Datenbanken. Die Adressen-Erkennungsmaschine empfängt zusammen mit einer Netzwerkadresse einen Index als eine Eingabe, um einen der in der Tabelle gespeicherten Datenbank-Spezifikatoren zu identifizieren. Die Adressen-Erkennungsmaschine durchläuft die primären und sekundären Datenbanken gemäß der in den Datenbank-Spezifikatoren enthaltenen Steuer-Information, die durch den die Netzwerkadresse begleitenden Index indiziert ist.
Beispielsweise definieren unterschiedliche Protokolle, Adressengrößen, Formate sowie weitere Informationselemente, die in den Einträgen der sekundären Datenbank gespeichert sein können. Um unterschiedliche Größen von Netzwerkadressen gemäß den Formaten unterschiedlicher Protokolle unterzubringen, ist der TRIE der primären Datenbank so angeordnet, dass es mehrere Stammknoten aufweist, um verschiedene Durchlaufpfade bereitzustellen, die jeweils eine unterschiedliche Größe und Adressenformat aus den möglichen Netzwerkadressen, die in die Adressen-Erkennungsmaschine eingegeben werden können, bewältigen können. Jeder Datenbank- Spezifikator umfasst Information über die Stammknoten, die für eine bestimmte Netzwerkadresse zu verwenden ist.
Außerdem liefern die Datenbank-Spezifikatoren einen Mechanismus zum Steuern, welche Information von einem Eintrag in der sekundären Datenbank an einen Router oder eine Brücke in Verbindung mit einer bestimmten Netzwerkadresse zurückgegeben wird. Jeder Eintrag kann angeordnet sein, um einen breiten Bereich von Information zu speichern. Die Steuer-Information der Datenbank-Spezifikatoren sind programmierbar, um anzugeben, welche spezifische Information während eines spezifischen Nachschlagevorgangs unter der Steuerung eines bestimmten Datenbank-Spezifikators zurückzugeben ist. Auf diese Art und Weise kann eine ausreichende Information für eine beliebige Anzahl von Aspekten eines bestimmten Protokolls in den sekundären Datenbankeinträgen gespeichert werden, wobei nur diejenige Information, die für einen bestimmten Adressen- Nachschlagevorgang passend ist, von dem Eintrag gelesen wird, wie es in dem jeweiligen Datenbank-Spezifikator spezifiziert ist.
Die Datenbank-Spezifikatoren liefern ebenfalls spezifische Steuer-Information zum Implementieren verschiedener Adressen-Abgleichtechniken, die von spezifischen Protokollen verlangt werden, und Lern- und Alterungsfunktionen, die für Brückenbildungsvorgänge erforderlich sind, so dass ein bestimmter Nachschlagevorgang entweder für einen Brückenbildungs- oder Weiterleitungsvorgang gesteuert werden kann und gleichzeitig Adressen-Abgleichfunktionen unterstützen kann, die bei einem bestimmten Protokoll erforderlich sein können.
Gemäß einem weiteren Merkmal der Adressen- Erkennungsvorrichtung einer weiteren Ausführungsform der Erfindung wird jeder der Knoten in der primären Datenbank und jeder der Einträge in der sekundären Datenbank mit Steuerdaten-Strukturen versehen, die programmierbar sind, um das Durchlaufen der Datenbank zu steuern. Die Steuerdaten- Strukturen an den Knoten und Einträgen vermehren die in den Datenbank-Spezifikatoren enthaltene Steuer-Information, um die Flexibilität der Datenbankausgestaltung für wirksame Nachschlagevorgänge in einer Umgebung weiter zu erhöhen, die Brückenbildungs- und/oder Weiterleitungsvorgänge in Bezug auf verschiedene unterschiedliche Protokolle ausführt.
Somit ist die Adressen-Erkennungsvorrichtung der Erfindung ausreichend flexibel, um als eine zentralisierte, gemeinsam genutzte Ressource für mehrere Leitungskarten zu arbeiten, wobei jede jeweils als Router oder Brücke arbeitet und jeweils mehrere Netzwerkprotokolle verarbeitet.

Kurzbeschreibung der Zeichnungen

Ein ausführlicheres Verständnis der Erfindung kann aus der folgenden Beschreibung einer bevorzugten Ausführungsform erhalten werden, die nur als Beispiel gegeben wird und in Verbindung mit den beigefügten Zeichnungen zu lesen ist, in denen
Fig. 1 ein Blockdiagramm einer High-Level-Darstellung der Architektur für eine Adressen-Erkennungsmaschine ist, die mit einer Leitungskarte gekoppelt ist, die entweder als Router oder als Brücke innerhalb eines Computernetzwerks arbeitet;
Fig. 2 eine Speicherabbildung des Speichers der Adressen-Erkennungsmaschine von Fig. 1 ist;
Fig. 3 ein Beispiel einer Netzwerkadresse und eines in die Adressen-Erkennungsmaschine von Fig. 1 eingegebenen Datenbank-Spezifikators veranschaulicht;
Fig. 4 eine schematische Darstellung der primären Datenbank von Fig. 2 ist;
Fig. 5 eine beispielhafte Struktur für einen Präfix- String für einen Knoten der primären Datenbank von Fig. 4 veranschaulicht;
Fig. 6 ein Blockdiagramm für einen Knotenzeiger einer der Knoten der primären Datenbank von Fig. 4 ist;
Fig. 7 ein beispielhaftes Format für einen Eintrag in die sekundäre Datenbank von Fig. 2 veranschaulicht; und
Fig. 8 ein beispielhaftes Format für einen Nachschlagedatenbank-Spezifikator der Adressen- Erkennungsmaschine von Fig. 1 veranschaulicht.

Ausführliche Beschreibung

Mit Bezug auf die Zeichnungen und zuerst auf Fig. 1 ist dort eine Adressen-Erkennungsvorrichtung gemäß der Erfindung dargestellt, die als eine Adressen-Erkennungskarte 10 implementiert ist, die mit einer Leitungskarte 12 durch einen Rückwandbus (backplanebus) 14 gekoppelt ist. Die Adressen- Erkennungskarte 10 umfasst eine Adressen-Erkennungsmaschine 100, die mit einem Anforderungs-/Antwort-RAM 101, einer Nachschlagedatenbank 300 und einer Tabelle 102 gekoppelt ist. Die Adressen-Erkennungsmaschine 100 ist ebenfalls mit einer Busschnittstelle 103 zum Koppeln mit dem Rückwandbus 14 gekoppelt. Wie in Fig. 1 gezeigt ist, koppelt die Busschnittstelle 103 ebenfalls den RAM 101 mit dem Bus 14.
Die Leitungskarte 12 umfasst eine Leitungsschnittstelle 200, die jeweils mit einem RAM 203 und mehreren Datenübertragungsleitungen 202 gekoppelt ist, und einen Prozessor 201, der mit dem RAM 203 gekoppelt ist, eine Tabelle 205 und eine Busschnittstelle 204. Die Busschnittstelle 204 wird verwendet, um den Prozessor 201 mit dem Rückwandbus 14 zu koppeln. Die Datenübertragungsleitungen 202 sind jeweils zum Koppeln mit einem Datenübertragungsdienst angepasst, der verwendet wird, um Datenpakete in einem Computernetzwerk (nicht dargestellt) zu übertragen. Die Leitungsschnittstelle 202 empfängt und überträgt Datenpakete zu und von den Datenübertragungsleitungen, wie aus ein Folgenden hervorgeht.
Der Rückwandbus 14 umfasst einen asynchronen Hochleistungsbus, der mit den Busschnittstellen 103, 204 gemäß der Futurebus IEEE Backplane Bus Specification (ANSE/IEEE Std 896.1) arbeitet, um Kommunikationsdienste zwischen der Leitungskarte 12 und der Adressen- Erkennungskarte 10 bereitzustellen.
Die Leitungsschnittstelle 200 stellt die physische und elektrische Anschlußmöglichkeit bzw. Verbindbarkeit zu den Datenübertragungsleitungen 202 zur Bit-Übertragung bereit. Beispielsweise ist die Leitungsschnittstelle 200 über ein Verteilungs-Panel oder Adapterkabel mit RS232-, RS422/449-, V.35- oder X.21-Miettelefonleitungen gekoppelt und ist angepasst, serielle Bits eines Datenpakets gemäß den elektrischen und physischen Spezifikationen der Mietleitung zu übertragen und zu empfangen. Außerdem formatiert die Leitungsschnittstelle 200 die seriell übertragenen Bits in Datenpakete gemäß dem Datenverbindungsprotokoll, das bei dem jeweiligen Übertragungsdienst benutzt wird, wie beispielsweise eine der HDLC-, LAPB- oder PPP-Standard- Datenverbindungen.
Der Prozessor 201 führt Datenverbindungs- und Netzwerkschichten-Routing oder -Brückenverarbeitungen durch, die beim Empfangen oder zum Übertragen jedes Datenpakets von der Leitungsschnittstelle 200 über die Übertragungsleitungen 202 erforderlich sind. Der RAM 203 wird als ein Pufferspeicher zwischen der Leitungsschnittstelle 200 und dem Prozessor 201 verwendet, um Datenpakete zu speichern. Der RAM 203 kann in Pufferabschnitte aufgeteilt werden, wobei jeder Abschnitt zur Verwendung als Puffer in Verbindung mit Datenpaketen, die von einer der Übertragungsleitungen 202 empfangen oder auf diesen übertragen werden, vorgesehen ist.
Die Netzwerkschichtverarbeitung wird von dem Prozessor 202 gemäß den in dem Computernetzwerk oder -netzwerken, die mit den Übertragungsleitungen gekoppelt sind, verwendeten Netzwerkschichtprotokollen durchgeführt, wie beispielsweise einem der OSI-, IP- und DECnet-Netzwerkprotokolle, das IS-IS- Mehrfachprotokoll-Routingschema und/oder einem Überbrückungsprotokoll. Der Prozessor 201 analysiert das Format jedes Datenpakets, um das Netzwerkschichtprotokoll zu bestimmen, das für dieses Datenpaket zu verwenden ist. Beispielsweise umfasst, wie es oben beschrieben ist, der Header, eines zu einem Block zusammengefassten Datenpakets eine Identifikation des Protokolls, das bei dem Netzwerk verwendet wird, das mit der Übertragungsleitung 202 gekoppelt ist, bei dem das Datenpaket empfangen wurde. Der Prozessor 201 verwendet die Protokoll-Information als Index in der Tabelle 205, um einen Index zu einem Datenbank-Spezifikator zu lokalisieren. Der Datenbank-Spezifikator liefert Steuer- Information für die Adressen-Erkennungsmaschine 100, wie es nachstehend beschrieben wird.
Die Adressen-Erkennungsmaschine 100 liefert einen Netzwerk-Informations-Nachschlagdienst für die Leitungskarte 12. Für jedes von der Leitungskarte 12 empfangene Datenpaket extrahiert der Prozessor 201 die Netzwerk-Zieladresse und leitet die Adresse zusammen mit dem Datenbank- Spezifikatorindex als eine "Anforderung" an den Anforderungs- /Antwort-RAM 101 weiter. Die Adressen-Erkennungsmaschine 100 liest jede Anforderung in dem Anforderungs-/Antwort-RAN 101 und verwendet den Datenbank-Spezifikatorindex und die Adresse, die in der Anforderung enthalten sind, als Index in der Tabelle 102 bzw. der Datenbank 300 zum Nachschlagen eines entsprechenden Eintrags. Ein Teil des entsprechenden Eintrags wird in das Anforderungs-/Antwort-RAN 101 als eine "Antwort" angeordnet, die dann von dem Prozessor 201 gelesen wird. Die Antwort umfasst Netzwerk-Information, die angibt, welche Übertragungsleitung 202 das Datenpaket zu bekommen hat, das der Anforderung/Antwort für Übertragungen aus der Leitungskarte 12 entspricht.
Die Anforderungen und Antworten werden zwischen der Leitungskarte 12 und dem RAM 101 über den Bus 14 mit einem Vorrichtungs-Sperrschema übermittelt, das in dem Anforderungs-/Antwort-RAM implementiert ist. Beispielsweise wird ein "Besitz"-Sperrschema ("ownerschip" interlock scheme) in dem RAN 101 implementiert, so dass der Prozessor 201 eine Anforderung in eine adressierte Stelle des RAMs 101 nur schreiben wird, wenn der Prozessor 201 "Besitzer" dieser Stelle ist. Der Prozessor 201 gibt den Besitz auf, sobald er eine Anforderung in eine bestimmte Stelle schreibt. Die Adressen-Erkennungsmaschine 100 gibt den Besitz an den Prozessor 201 zurück, nachdem sie die Information an der bestimmten Stelle gelesen hat und fortfährt, die Anforderung zu verarbeiten. Der Prozessor 201 kann keine zusätzlichen Anforderungen schreiben, sobald er den Besitz aller seiner zugewiesenen Stellen aufgegeben hat, bis die Adressen- Erkennungsmaschine 100 den Besitz für mindestens eine Stelle in dem Anforderungs-/Antwort-RAN 101 zurückgibt.
Mit Bezug auf Fig. 2 ist dort eine Speicherbildung für die Nachschlagedatenbank 300 der Adressen-Erkennungsmaschine 100 dargestellt. Wie oben beschrieben ist, verwendet die Adressen-Erkennungsmaschine 100 eine Netzwerkadresse, die in dem Anforderungsteil eines Eintrags in dem Anforderungs- /Antwort-RAM 101 als Index zu der Datenbank 300 gespeichert ist, um einen Eintrag in der Datenbank 300 zu lokalisieren. Der Eintrag in der Datenbank 300 enthält die Netzwerk- Information, die sich auf die Netzwerkadresse bezieht, die von der Adressen-Erkennungsmaschine 100 an das Anforderungs- /Antwort-RAN 101 als Antwort zurückgegeben wird. Der Prozessor 201 in der Leitungskarte 12 verwendet die Antwort, um die Netzwerk-Information zur Übertragung des Datenpakets an sein vorgesehenes Ziel zu verarbeiten.
Die Datenbank 300 ist in eine primäre Datenbank 301 und eine sekundäre Datenbank 302 aufgeteilt. Die primäre Datenbank 301 umfasst eine Mehrweg-Baumdatenstruktur (TRIE), wie es nachstehend beschrieben ist, wobei die Netzwerkadresse verwendet wird, um einen Zeiger auf einen Eintrag in der sekundären Datenbank 302 zu lokalisieren. Der Eintrag in die sekundäre Datenbank 302 umfasst die Netzwerk-Information für die Antwort.
Ein Beispiel einer Anforderung 303 ist in Fig. 3 gezeigt. Die Anforderung 303 umfasst eine 16-Bit- Netzwerkadresse 303A und ein Datenbank-Spezifikator-Indexfeld 303B.
Die Adressen-Erkennungsmaschine 100 unterhält die Tabelle 102 als eine Nachschlagetabelle für Datenbank- Spezifikatoren, die in der Steuerung eines Nachschlagevorgangs in der Nachschlagedatenbank 300 verwendet werden, wie es nachstehend beschrieben ist. Das Indexfeld 303 in der in die Adressen-Erkennungsmaschine 100 eingegebenen Anforderung liefert einen Index zu der Tabelle 102, um einen Nachschlagedatenbank-Spezifikator zu lokalisieren, der bei einem aktuellen Antwort-Nachschlagevorgang zu verwenden ist.
Die Adressen-Erkennungsmaschine 100 liest die Adresse 303A aus dem Anforderungs-/Antwort-RAN 101 und verarbeitet die Adresse 303A in Gruppen von vier Bits. Jede Gruppe von vier Bits wird als Zahlzeichen oder Codeelement 304 bezeichnet. Die primäre Datenbank 301 umfasst eine Mehrzahl von Knoten 305, die miteinander durch Knotenzeiger 306 verbunden sind, wobei jeder Knoten 305 einem bestimmten Wert einem Zeichen oder einer Folge von Zeichen einer Netzwerkadresse zugeordnet sind. Im allgemeinen umfasst jeder Knoten 16 Knotenzeigereinträge 306, einen für jeden eindeutigen Bitkombinationswert eines Vier-Bit-Zeichens 304, das in Folge dem Zeichen oder der Sequenz von Zeichen folgt, das/die dem jeweiligen Knoten 205 zugeordnet ist/sind (2&sup4; gleich 16, 0000 bis 1111), wie es in Fig. 4 gezeigt ist.
Die Adressen-Erkennungsmaschine 100 greift zuerst auf die primäre Datenbank 301 mit einer Stammzeigeradresse 308 zu, die auf den Stammknoten 305A der primären Datenbank 301 zeigt. Die Stammzeigeradresse ist in dem Datenbank- Spezifikator gekennzeichnet, der von der Adressen- Erkennungsmaschine 100 verwendet wird, wie aus dem Folgenden hervorgeht. Der Stammknoten 305A umfasst 16 Knotenzeiger 307, die jeweils beispielsweise der Adresse einer der den Zahlzeichen zugeordneten Bits 0-3 gleich 0000 bis 1111 jeweils zugeordnet sind. Die Adressen-Erkennungsmaschine 100 wird den dem Wert der Bits 0-3 des ersten Zeichens 300 zugeordneten Knotenzeiger verwenden, der mit dem Wert des ersten Zeichens der verarbeiteten Netzwerkadresse übereinstimmt, beispielsweise Bits 0-3 gleich 0000, um auf den nächsten Knoten zuzugreifen.
Bei dem Beispiel von Fig. 4 umfasst der dem Zeichen 304 zugeordnete Knoten 305, der Bits 0-3 gleich 0000 aufweist, 16 Knotenzeiger 307 einschließlich eines Knotenzeigers 307, der eine Adresse auf einem weiteren Knoten 305 ist, der einem der Werte der Bitkombination für das nächste Zeichen 304 der Netzwerkadresse (Bits 4-7) zugeordnet ist, wobei die Bits 4-7 gleich 0000 sind, usw.
Die primäre Datenbank 301 ist auf diese Art und Weise aufgebaut, so dass jeder mögliche Wert für ein Zeichen 304 (z. B. das Zeichen mit den Bits 0-3) mit jedem möglichen Zeichenwert in der Sequenz von Zeichen 304 verknüpft ist, die eine Netzwerkadresse (z. B. die Zeichen mit den Bits 4-7, 8-11 und 12-15), durch die 16 Knotenzeiger 307 in jedem Knoten 305 umfassen kann. Die Adressen-Erkennungsmaschine 100 durchläuft die primäre Datenbank 301 von Knoten zu Knoten über die Knotenzeiger 307 für die Zeichenwerte, die mit den entsprechenden Zeichenwerten der Netzwerkadresse übereinstimmen, die verarbeitet werden, bis alle Zeichen abgeglichen wurden.
Jeder Knoten 305, der auf einen nächsten Knoten 305 in der Folge von Zeichen der Netzwerkadresse (d. h. die den die Bits 0-3, 4-7 und 8-11 umfassenden Zeichen zugeordneten Knoten bei diesem Beispiel) zeigt, wird als Übergangsknoten (transition node) (d. h. ein Knoten, der auf einen weiteren Knoten zeigt) bezeichnet. Die die Bits 12-17 umfassenden Zeichen entsprechenden Knoten werden Abschlussknoten 305B genannt, da eine Übereinstimmung mit den Bits 12-15 das Abgleichverfahren für die 16-Bit-Netzwerkadresse dieses Beispiels abschließt. Jeder Abschlussknoten 305 umfasst 16 Nachschlag-Abgleichzeiger 309, einen für jeden der 16 möglichen Werte für das Zeichen 304, das die Bits 12-15 umfasst. Jeder Nachschlag-Abgleichzeiger 309 umfasst eine Adresse zu einem Eintrag in der sekundären Datenbank 302.
In Anbetracht der spärlich mit Einträgen versehenen Adressenräume, die häufig bei Netzwerken angetroffen werden, werden die Knoten 305 mit Präfix-Strings 310 versehen, um den Umfang an Speicherplatz zu verringern, der für die primäre Datenbank 301 erforderlich ist, und um die Suchzeit zu vermindern. Eine spärlich mit Einträgen versehene Stelle bedeutet, dass nur relativ wenige der Gesamtzahl von Bitwerten, die durch eine n-Bit-Netzwerkadresse dargestellt werden können, tatsächlich eine Adressenkomponente in dem Netzwerk bilden. Ein Präfix-String ist ein String von Zeichen, der vielen Adressen gemeinsam ist. Es ist anzumerken, dass es eine große Anzahl gemeinsamer Zeichen in einem spärlich mit Einträgen versehenen Adressenraum gibt.
Beispielsweise kann eine 16-Bit-Netzwerkadresse über 65 000 Netzwerkkomponenten eindeutig identifizieren. Das Netzwerk, das die 16-Bit-Adresse verwendet, kann jedoch nur 16 Komponenten aufweisen, wobei hiervon jede eindeutig durch einen der 16 möglichen Werte der niedrigstwertigen Zeichen der Adresse identifiziert werden kann. Dies ist ein Beispiel eines spärlich mit Einträgen versehenen Adressenraums, und die Werte der drei höherwertigen Zeichen für alle 16 Komponenten können die gleichen sein.
Somit kann bei diesem Beispiel ein Präfix-String einen String der drei höherwertigen Zeichen umfassen, die für einen Vergleich mit den drei höherwertigen Zeichen einer Netzwerkadresse verwendet werden, die in einem einzigen Knoten 305 verarbeitet werden. Die Verwendung von Präfix- Strings minimiert den gesamten Speicherplatz, der erforderlich ist, um die primäre Datenbank 301 zu implementieren, da weniger als die Gesamtzahl 305 von Knoten erforderlich ist, um nach einer bestimmten Netzwerkadresse zu suchen. Die Adressen-Erkennungsmaschine 100 vergleicht drei Zeichen einer Adresse in dem Knoten 305, die dem Präfix- String zugeordnet sind. Eine OSI-Netzwerkprotokolladresse ist für eine Gesamtzahl von 40 Zeichen 20 Byte lang. Bestimmte höherwertige Zeichen, beispielsweise die 16 höchstwertigen Zeichen vieler Adressen in dem Netzwerk können für viele Komponenten in einem bestimmten OSI-Netzwerk die gleichen sein, und diese Zeichenwerte können als Präfix-Strings in zugeordneten Knoten der primären Datenbank für einen einzigen Knotenvergleich durch die Adressen-Erkennungsmaschine 100 gespeichert werden.
Fig. 5 veranschaulicht eine exemplarische Datenstruktur, die als Präfix-String 310 in einem Knoten 305 verwendet werden kann. Der Präfix-String 310 ist in vier Wörter 311 aufgeteilt. Die ersten drei Wörter 311 umfassen jeweils fünf Zahlzeichen 304 und drei Steuer-Bits, die als DIG STR CNT 312 in den Bits 0-2 des Worts gekennzeichnet sind. Die Steuerbits geben an, welche Zeichen des Worts für Vergleichszwecke gültig sind, wie aus dem Folgenden hervorgeht. Das vierte Wort umfasst zwei Zeichen und einen Zwischenübereinstimmungszeiger 313.
Die Steuerbits DIG_STR_CNT 312 werden verwendet, um den Präfix-String 310 flexibel zu machen, so dass der Präfix- String 310 ein String von ein bis 17 Zeichen gemäß der Adressenraumbelegung des Protokolls darstellen kann, das bei einem bestimmten Netzwerk verwendet wird. Die DIG_STR_CNT- Bits 312 für ein Wort 311 werden von der Adressen- Erkennungsmaschine 100 wie folgt interpretiert:
DIG STR_CNT_Bits 312 gleich 000: Alle fünf Zeichen sind gültig, und weitere Zeichen in dem nächsten Wort 311 sind ebenfalls gültig (die Steuerung für gültige Zeichen in dem nächsten Wort sind in den DIG_STR_CNT-Bits 312 für das nächste Wort enthalten);
DIG STR_CNT_Bits 312 gleich 001-101: Dies ist das letzte Wort des String und der Wert der DIG_STR_CNT-Bits gibt die Anzahl von gültigen Zeichen in diesem Wort an;
DIG STR_CNT_Bits 312 gleich 110: Alle fünf Zeichen sind gültig, und das erste Zeichen des nächsten Worts ist gültig, und das erste Zeichen des nächsten Worts ist das letzte Zeichen des String;
1 DIG STR_CNT_Bits 312 gleich 111: Alle fünf Zeichen sind gültig, und die nächsten zwei Zeichen des nächsten Worts sind gültig, und die ersten zwei Zeichen des nächsten Worts sind die letzten Zeichen des String.
Die DIG STR_CNT_Bits 312 werden gesetzt und die Zeichen eines String werden in die Präfix-Stringstruktur 310 eines Knotens 305 geladen, um einen String von Zeichen zu bilden, die die Adressen-Erkennungsmaschine 100 mit den entsprechenden Zeichen der verarbeiteten Netzwerkadresse vergleichen kann. Das Zeichen in der Adresse nach dem String wird als Index in Knotenzeigern zum Fortsetzen des Durchlaufens der primären Datenbank 301 verwendet. Für eine maximale Flexibilität wird jeder Knoten 305 der primären Datenbank 310 mit einer Präfix-Stringdatenstruktur 310 versehen, die je nach dem in einem Netzwerk verwendeten Adressenschema entweder verwendet wird oder nicht. Der Zwischenübereinstimmungszeiger 313 wird verwendet, um einen Eintrag in der sekundären Datenbank 302 für eine beste Übereinstimmungsposition zu lokalisieren, wenn eine genaue Übereinstimmung nicht gefunden werden kann, wie es nachstehend beschrieben ist.
Jeder Knotenzeiger 307 umfasst eine nächste Knotenadresse und Steuerfelder, um das Durchlaufen der primären Datenbank 301 durch die Adressen-Erkennungsmaschine 100 zu steuern. Ein Beispiel eines Knotenzeigers 307 ist in Fig. 6 gezeigt. Ein IDI_CNT-Feld 314 umfasst fünf Bits, ein LOAD_IDI-Feld 315 umfasst ein Bit, ein SAVE_RESULT-Feld 316 umfasst ein Bit, ein NEXT_NODE-Feld 317 umfasst 15 Bits und ein PTR_CTRL-Feld 318 umfasst zwei Bits.
Das NEXT_NCDE-Feld 317 enthält die Adresse für den nächsten Knoten 305 in dem Zeichenübereinstimmungsdurchlauf der primären Datenbank 301.
Das SAVE_RESULT-Feld 316 wird bei einem besten Übereinstimmungs-Routing verwendet. Bei bestimmten Routing- Protokollen ist es notwendig, die beste Übereinstimmung für eine Netzwerkadresse zu finden, wenn eine genaue Übereinstimmung nicht über die Knoten 305 der primären Datenbank 310 gefunden werden kann. Das SAVE_RESULT-Bit 316 wird in einem Knotenzeiger 307 gesetzt, wenn eine beste Übereinstimmung für eine Adresse an dem Zeichen der dem Knoten 305 zugeordneten Adresse gültig ist, auf den von dem Knotenzeiger 307 gezeigt wird. Wenn das SAVE_RESULT-Bit 316 gesetzt ist, speichert die Adressen-Erkennungsmaschine 100 den Wert des NEXT_NODE-Felds 317 in einem internen Register. Der gespeicherte NEXT_NODE-Wert ist eine Adresse an einem nächsten Knoten 305, dessen Zwischenübereinstimmungszeiger 313 als Zeiger auf die sekundäre Datenbank 302 verwendet wird, sollte eine beste Übereinstimmung notwendig sein (d. h. bei Fortsetzung des Durchlaufs der primären Datenbank 301, wenn keine genaue Übereinstimmung für die verarbeitete Adresse gefunden wird, verwendet die Adressen- Erkennungsmaschine 100 den gespeicherten NEXT_NODE-Wert, um auf den Zwischenübereinstimmungszeiger zum Zugriff auf die sekundäre Datenbank 302 zuzugreifen).
Außerdem werden bestimmte Netzwerkadressen in Segmente, beispielsweise gemäß dem IS-IS-Routing-Protokoll aufgeteilt. Die International Organization for Standardization (ISO) definiert beispielsweise eine hierarchische Adressenstruktur mit einem anfänglichen Domänenteil (IDP) und einem spezifischen Domänenteil (DSP). Der Übergang von dem IDP-Teil zu dem DSP-Teil einer ISO-formatierten Adresse folgt nicht der Baumstruktur der primären Datenbank 301.
Dem gemäß werden das IDI_CNT-Feld 314 und das LOAD_IDI- Feld 315 verwendet, um einen Durchlauf der primären Datenbank auf das Zeichen einer ISO-Adresse umzuleiten, an der der IDP- Abschnitt endet. Wenn das Bit des LOAD_IDI-Felds 315 in einem Knoten 305 gesetzt ist, wird das IDI_CNT-Feld 314 die Anzahl von Zeichen von dem aktuellen Zeichen bis zu dem Zeichen an dem Ende des IDP-Teils der Adresse enthalten. Die Adressen- Erkennungsmaschine 100 speichert den Wert in dem IDI_CNT-Feld 314 (IDI-Zählwert) und dekrementiert den IDI-Zählwert für jeden nachfolgenden Knoten 305, bis der Wert gleich Null ist. An dem Knoten, bei dem der IDI-Wert gleich Null ist, bewegt sich die Adressen-Erkennungsmaschine 100 zu einem nächsten Knoten 305 unter Verwendung einer in einem an dem Knoten 305 vorgesehenen DSP-Zeiger 307A gespeicherten Adresse (siehe 7 Fig. 4). Der DSP-Zeiger 307A zeigt auf einen Knoten, der den Durchlauf für eine ISO-Adresse fortsetzt.
Wenn das Bit des LOAD_IDI-Felds 315 nicht gesetzt ist, und ein vorausgewähltes Bit in dem IDI_CNT-Feld 314 gesetzt ist, wird dies als ein gesetztes Bereichsübereinstimmungs-Bit (AM-Bit) interpretiert. Bestimmte Protokolle, z. B. die DECnea/OSI- und DECnet/Phase- IV-Protokolle definieren eine Bereichsadresse. Wenn das AM-Bit auf einen Knoten 305 gesetzt ist, gibt dies an, dass das Ende einer Bereichsadresse bei diesem Zeichen gültig ist. Die Fortsetzung des Durchlaufens der primären Datenbank 301 nach Antreffen eines Knotens 305, der ein gesetztes AM-Bit aufweist, wird nachstehend beschrieben.
Die Bits des PTR_CTRL-Felds 318 beliefern die Adressen- Erkennungsmaschine 100 mit Information über den von dem NEXT_NODE-Feld 317 gezeigten nächsten Knoten 305. Die Bits des PTR_CTRL-Felds 318 werden wie folgt interpretiert:
PTR_CTRL-Bits gleich 00: der nächste Knoten enthält keinen Präfix-String; wie oben beschrieben ist, ist jeder Knoten mit einer Präfix-Stringstruktur versehen, wenn die PTR_CTRL-Bits 00 sind, wird die Präfix-Stringstruktur des nächsten Knotens nicht verwendet, und die 00 Bits teilen der Adressen-Erkennungsmaschine 100 mit, die Struktur in dem nächsten Knoten zu ignorieren;
PTR_CTRL-Bits gleich 01: der nächste Knoten enthält einen Präfix-String, dem gemäß vergleicht die Adressen- Erkennungsmaschine 100 die entsprechenden Zeichen der verarbeiteten Adresse mit den gültigen Zeichen des String, wie es durch die DIG_STR_CNT-Bits 312 des Präfix-String 310 angegeben ist;
PTR_CTRL-Bits gleich 10: der nächste Knoten ist ein "Padding"-Eintrag, der der Erkennungsmaschine 100 mitteilt, den aktuellen Knoten 305 erneut zu verwenden, da Padding- Zeichen in der Adresse existieren, wobei die Padding-Zeichen von der Adresse entfernt werden und der Durchlauf fortgesetzt wird [Das IDI-Feld des IDP-Teils einer OSI-Standard-Adresse ist rechtsbündig und aufgefüllt, um die festgelegte Länge des Felds zu füllen. Die Padding-Zeichen werden zu dem aktuellen Knoten 305 unter Verwendung der Padding-Zeiger in einer Schleife zurückgeführt.], wobei das NEXT_NODE-Feld 317 ignoriert wird;
PTR_CTRL-Bits gleich 11: Der Zeiger gibt ein Nachschlage-Fehler an, wobei der Zeiger angibt, dass der von dem Knoten, wo das SAVE_RESULT-Bit gesetzt ist, gespeicherte Zwischenübereinstimmungszeiger nun verwendet werden soll, um auf die sekundäre Datenbank zuzugreifen, wobei das NEXT_NODE- Feld 317 ignoriert wird.
Wenn ein Abschlussknoten 305B erreicht ist, greift die Adressen-Erkennungsmaschine 100 auf die sekundäre Datenbank 302 mit dem geeigneten Nachschlage-Übereinstimmungszeiger 309 zu. Die Adressen-Erkennungsmaschine 100 stellt Information aus einem entsprechenden sekundären Datenbank-Eintrag gemäß den Steuerbits der Nachschlagedatenbank-Spezifikatoren wieder her, der durch das Nachschlage Feld 303B der jeweiligen Anforderung angegeben wird, wie aus dem Folgenden hervorgeht. Die PTR_CTRL-Bits des Knotenzeigers 307 an dem Abschlussknoten 305 geben an, dass der Abschlussknoten einen String enthält, dann muss die Adressen-Erkennungsmaschine 100 die restlichen Zeichen einer mit dem String verarbeiteten Adresse vergleichen. Wenn eine Übereinstimmung auftritt, wird der entsprechende Nachschlage-Übereinstimmungszeiger 309 des Abschlussknotens 305 verwendet, um auf die sekundären Datenbank 302 zuzugreifen. Wenn es keine Übereinstimmung gibt oder wenn weniger Zeichen in der Adresse als in dem String übrig bleiben, dann wird der von dem Knoten 305, wo das SAVE_RESULT-Bit gesetzt war, gespeicherte Zwischenübereinstimmungszeiger verwendet, um auf die sekundäre Datenbank 302 zuzugreifen.
In Fig. 7 ist ein beispielhaftes Format für einen sekundären Datenbank-Eintrag 400 dargestellt. Es gibt drei Arten von sekundären Datenbank-Einträgen 400: Einen gemeinsamen Block (common block) 401, einen sog. Path-Split- Block 402 und einen Nachbarschaftsblock (adjacency block) 403. Jeder gemeinsame Block 401 ist mit einem Path-Split- Block 402 verbunden. Es gibt eine gleiche Anzahl von gemeinsamen, Path-Split- und Nachbarschafts-Blöcken 401, 402, 403 in der sekundären Datenbank 302. Es gibt keine direkte Beziehung zwischen jedem verbundenen gemeinsamen Block/Path- Split-Block und den Nachbarschaftsblöcken. Jeder der gemeinsamen Blöcke und Nachbarschaftsblöcke 401, 402 enthält Information, die von der Adressen-Erkennungsmaschine 100 als eine Antwort an das Anforderungs-/Antwort-RAM 101 zurückzugeben ist.
Jeder gemeinsame Block 401 ist acht Wörter lang. Die ersten drei Wörter 401A werden verwendet, um das Altern (ageing) und Lernen von Information beizubehalten, das erforderlich ist, wenn das Ziel eines Datenpakets unter Verwendung einer Brücke erreicht wird, wie es nachstehend beschrieben ist. Die verbleibenden fünf Wörter 401B sind frei und werden verwendet, um eine beliebige Information zu speichern, die für eine Rückkehr bei einer Antwort erforderlich sein kann, wie beispielsweise Routing- Information für OSI- oder DECnet-Netzwerkprotokolle, etc. Jeder der Nachschlage-Übereinstimmungszeiger 309 und Nachschlage-Zwischenzeiger 314 der primären Datenbank 310 indizieren einen entsprechenden gemeinsamen Block 401.
Jeder Path-Split-Block 402 ist mit einem jeweiligen gemeinsamen Block 401 verbunden und umfasst eine Gruppe von vier Zeigern, die verwendet werden, um einen Nachbarschaftsblock zur Verwendung bei einer aktuellen Antwort auszuwählen.
Jeder Nachbarschaftsblock 403 ist vier Wörter lang. Die Wörter jedes Nachbarschaftsblocks 403 enthalten ebenfalls Information, die bei einer Antwort erforderlich sein kann. Aufeinanderfolgende Nachschlage-Vorgänge bei dem gleichen gemeinsamen Block 401 der sekundären Datenbank 302 können jeweils Information von einem unterschiedlichen Nachbarschaftsblock 403 abhängig von dem Path-Splitting- Vorgang zurückgeben.
Jeder Path-Split-Block 402 umfasst ein NUM_PATHS-Feld 404 mit zwei Bits, ein LAST_PATH-Feld 405 mit zwei Bits und vier Nachbarschaftsblockzeiger 406, die jeweils 15 Bits umfassen, die jeweils mit ADJ_PTR_O bis ADJ_PTR_3 gekennzeichnet sind. Jeder Nachbarschaftsblockzeiger 406 zeigt auf einen betreffenden Nachbarschaftsblock 403. Die Bits des NUM_PATHS-Felds 404 werden von der Adressen- Erkennungsmaschine 100 wie folgt interpretiert:
NUM_PATHS-Bits gleich 00: auf einen Nachbarschaftsblock wird nur durch den Path-Split-Block 402 zugegriffen, wie es durch ADJ_PTR_0 angegeben ist;
NUM_PATHS-Bits gleich 01: Auf einen der beiden unterschiedlichen Nachbarschaftsblöcke wird durch den Path- Split-Block 402 zugegriffen, wie es entweder durch ADJ_PTR_0 oder ADJ_PTR_1 angegeben ist;
NUN PATHS-Bits gleich 10: Auf einen der drei unterschiedlichen Nachbarschaftsblöcke wird durch den Path- Split-Block 402 zugegriffen, wie es durch einen von ADJ_PTR_0 bis ADJ_PTR_2 angegeben ist;
NUM_PATHS-Bits gleich 11: Auf einen der vier unterschiedlichen Nachbarschaftsblöcke wird durch den Path- Split-Block 402 zugegriffen, wie es durch einen von ADJ_PTR_0 bis ADJ_PTR_3 angegeben ist.
Das LAST_PATH-Feld 405 gibt die Anzahl der Nachbarschaftsblockzeiger 406 an, die während eines aktuellen Abrufs von Information aus der sekundären Datenbank 302 für eine Antwort zu verwenden ist. Die Bits des LAST_PATH-Felds 405 werden von der Adressen-Erkennungsmaschine 100 wie folgt interpretiert:
LAST_PATH-Bits gleich 00: Verwende ADJ_PTR_0 für die aktuelle Antwort;
LAST_PATH-Bits gleich 01: Verwende ADJ_PTR_1 für die aktuelle Antwort;
LAST_PATH-Bits gleich 10: Verwende ADJ_PTR_2 für die aktuelle Antwort;
LAST_PATH-Bits gleich 11: Verwende ADJ_PTR_3 für die aktuelle Antwort.
Jedes Mal, wenn die Adressen-Erkennungsmaschine 100 in einen Path-Split-Block 402 eintritt, inkrementiert sie das LAST_PATH-Feld 405. Wenn der Wert der Bits in dem LAST_PATH- Feld 405 den Wert der Bits in den NUM_PATHS-Feld 404 des Path-Split-Blocks 402 überschreitet, wird das LAST_PATH-Feld 405 auf Null gesetzt. Somit läuft der Wert der Bits in dem LAST_PATH-Feld 405 von 0 zu dem Wert der Bits in dem NUN_PATHS-Feld 404 des Path-Split-Blocks 402 periodisch durch.
Der Path-Splitting-Vorgang, der von dem Path-Splitting- Block 402 bereitgestellt wird, liefert eine automatische Steuerung von Routing-Informationsänderungen, die bei einem bestimmten Routing-Protokoll bei aufeinanderfolgenden Übertragungen von Datenpakten an eine bestimmte Netzwerkadresse gewünscht sein können. Die NUM_PATHS- und LAST_PATH-Felder 404, 405 können verwendet werden, um eine Anzahl verschiedener Nachbarschaftsblöcken einzustellen, auf die bei aufeinanderfolgenden Lesevorgängen eines bestimmten gemeinsamen Blocks 401 zugegriffen werden können, und um zu steuern, welcher Nachbarschaftsblock während eines aktuellen gemeinsamen Blocklesevorgangs gelesen wird.
In Fig. 8 ist ein beispielhaftes Format für einen Nachschlagedatenbank-Spezifikator 500 gezeigt. Wie es oben erläutert ist, unterhält die Adressen-Erkennungsmaschine 100 eine Tabelle 102 von Nachschlagedatenbank-Spezifikatoren 500, z. B. 24 Nachschlagedatenbank-Spezifikatoren 500. Beim Verarbeiten einer spezifischen Anforderung geht die Adressen- Erkennungsmaschine 100 dazu über die primäre Datenbank 301 zu durchlaufen und Information aus der sekundären Datenbank 302 gemäß den in einem bestimmten Nachschlagedatenbank- Spezifikator 500 gesetzten Steuerbits abzurufen, wie es durch den Prozessor 201 in dem Nachschlage-Feld 303B der Anforderung 300 angegeben ist (siehe Fig. 3).
Unterschiedliche Protokolle erfordern unterschiedliche Adressenformate und weitere Elemente, wie beispielsweise die Protokollklasse, die in dem gemeinsamen Block 401 gespeichert werden kann, sowie verwandte Nachbarschaftsblöcke 403 des sekundären Datenbank-Eintrags 400, auf die bei der Verarbeitung einer bestimmten Anforderung gezeigt wird. Die Nachschlagedatenbank-Spezifikatoren liefern einen Mechanismus zum Steuern, welche Information bei einer Antwort zurückgegeben wird.
Jeder Nachschlagedatenbank-Spezifikator 500 umfasst sechs Felder: Ein Argument-Längenfeld (ARG_LENGTH) 501 mit sechs Bits, ein Stammdatenbank-TRIE-Feld (ROOT_TRIE) 502 mit fünf Bits, ein Bereichsübereinstimmungs-Zählfeld (AM_CNT) 503 mit sechs Bits, ein Bereichsübereinstimmungs-Stammdatenbank- TRIE-Feld 504 (AM_TRIE) mit fünf Bits, ein Nachschlag- Steuerbitfeld 505 mit einer vorausgewählten Anzahl von Nachschlag-Steuerbits, und eine sekundäre Datenbankmaske (SDB_MASK) 506 mit 31 Bits.
Das Argument-Längenfeld 501 gibt die Anzahl von Zeichen in dem Adressenteil 303A einer bestimmten Anforderung 303 an (siehe Fig. 3). Wie es oben erläutert ist, können die als Anforderungen in das Anforderungs-/Antwort-RAM 101 geschriebenen Netzwerkadressen je nach dem jeder bestimmten Adresse zugeordneten Netzwerkprotokoll von fester Länge oder in der Länge veränderlich sein.
Das Stammdatenbank-TRIE-Feld 502 spezifiziert, welcher Stammübergangsknoten in der primären Datenbank 301 zu verwenden ist. Die primäre Datenbank 301 kann mit mehreren Stämmen verwendet werden, die jeweils benutzt werden, um eine Suche nach einem sekundären Datenbank-Nachschlage- Übereinstimmungszeiger 309 zu beginnen. Somit wird die in dem ROOT_TRIE-Feld 502 gesetzte Anzahl von der Adressen- Erkennungsmaschine 100 verwendet, um zu bestimmen, bei welchem Stamm die Suche beginnen soll.
Das Bereichsübereinstimmungs-Zählfeld 503 gibt die Anzahl verbleibender Zeichen über das Zeichen hinaus an, das durch ein eingestelltes AM-Bit angegeben ist, um einen Bereich, wie es oben beschrieben ist, für einen Bereichsübergang innerhalb der primären Datenbank 301 abzuschließen. Das Bereichsübereinstimmungs-Stamm-TRIE-Feld 504 gibt den Stammknoten 305 der primären Datenbank 301 an, der für die verbleibenden Bereichsübereinstimmungs- Zählzeichen der Adresse zu verwenden ist.
Wenn das AM-Bit bei einem Knotenzeiger 307 gesetzt ist und die Anzahl der bei einer verarbeiteten Adresse verbleibender Zeichen gleich dem Wert in dem Bereichsübereinstimmungs-Zählfeld 503 des Nachschlagedatenbank-Spezifikators 500 ist, die in der Anforderung 303 angegeben ist, dann wird ein Übergang zu dem durch das Bereichsübereinstimmungs-Stamm-TRIE-Feld 504 dieses Nachschlagedatenbank-Spezifikators 500 spezifizierten Stammknoten durchgeführt. Das nächste Zeichen der gerade bearbeiteten Adresse wird zur Übereinstimmung mit dem spezifizierten Stammknoten verwendet. Wenn die Anzahl von verbleibenden Zeichen nicht gleich dem Bereichsübereinstimmungs-Zählwert ist, oder wenn das AM-Bit in einem Knotenzeiger 307 nicht gesetzt ist, dann wird das nächste Zeichen in dem Knoten nachgeschlagen, auf das von dem NEXT_NODE-Feld 317 des Knotenszeigers 307 gezeigt wird.
Das Nachschlage-Steuerbitfeld 505 kann verschiedene Bits umfassen, die verwendet werden, um den Betrieb der Adressen- Erkennungsmaschine 100 während eines Nachschlagvorgangs zu steuern. Beispielsweise kann ein Nachschlag-Sperrbit bereitgestellt werden, um einen durch den zugeordneten Nachschlagedatenbank-Spezifikator 500 spezifizierten Nachschlagetyp zu sperren. Wenn es gesetzt ist, wird ein Fehler zurückgegeben, falls bei dem zugeordneten Nachschlagedatenbank-Spezifikator 500 in dem Nachschlag-Feld 303 eine Anforderung angegeben ist.
Die Adressen-Erkennungsmaschine der Erfindung ist so ausgelegt, dass sie sowohl Routing- als auch Brücken- Protokolle unterstützt. Wie oben beschrieben ist, umfasst jeder gemeinsame Block 401 drei Wörter 401A, die zum "Altern" und Lernen von Information reserviert sind, die für die Implementierung eines Brückenprotokolls notwendig ist. Ein Port-Lern- und -Alterungs-Bit ist in dem Nachschlag- Steuerbitfeld 505 enthalten, um der Adressen- Erkennungsmaschine 100 anzugeben, dass eine bestimmte Netzwerk-Zieladresse einen Brückenbildungsvorgang erfordert, um das jeweilige Datenpaket zu übertragen. Wenn das Port- Lern- und -Alterungs-Bit in einem Nachschlagedatenbank- Spezifikator 500 gesetzt ist, werden die folgenden Lern- und -Alterungsfunktionen von der Adressen-Erkennungsmaschine 100 durchgeführt.
Die Adressen-Erkennungsmaschine 100 liest das erste Wort 401A des gemeinsamen Blocks 401 für eine Aktualisierungsmaske 408, die 16 Bits umfasst. Jedes Bit der Aktualisierungsmaske 408 entspricht beispielsweise einem der Ports in der Leitungskarte 12, der ein Ursprungs-Port in einer Brücke sein kann. Für jeden Port, dessen entsprechendes Bit in der Maske 408 gesetzt ist, wird ein Lernvorgang durchgeführt. Der Prozessor 201 weist eine Bitanzahl bei jeder Anforderung auf, um ein bestimmtes Bit in der Maske 408 zu spezifizieren, das sich auf eine Brückenadresse bezieht. Die Adressen- Erkennungsmaschine 100 bestimmt, ob das Bit für die von dem Prozessor 201 in der Anforderung spezifizierte Portnummer in der Maske 408 gesetzt ist. Wenn das spezifizierte Bit nicht gesetzt ist, wird das Lernen von der Adressen- Erkennungsmaschine 100 für diesen Port nicht durchgeführt. Es wird jedoch ein Timer-Übergehungsbit 408 in dem ersten Wort 401A bereitgestellt. Wenn alle Timer-Übergehungs- und Port- Lern- und -Alterungsbits gesetzt sind, führt die Adressen- Erkennungsmaschine 100 die Alterungsfunktion mit Bezug auf den gemeinsamen Block 401 durch.
Beim Eintreten in den gemeinsamen Block 401 für eine Brückenadresse stellt die Adressen-Erkennungsmaschine 100 einen Brückenzugriffs-Timer 401 in dem zweiten Wort 401A auf Null und stellt ein Timer-an-Bit 411 auch in dem zweiten Wort 401A ein. Das Timer-Feld umfasst 20 Bits. Als Hintergrundfunktion fragt die Adressen-Erkennungsmaschine 100 jeden gemeinsamen Block 401 (zylindrisch) ab, der ein Timeran-Bit 411 gesetzt hat, zum Beispiel ein Mal pro Sekunde, und inkrementiert den Wert in dem Timer-Feld 410.
Die Adressen-Erkennungsmaschine 100 unterhält einen Alterungs-Zeitüberwachungswert, der mit dem inkrementierten Wert in dem Timer-Feld 410 verglichen wird. Wenn der inkrementierte Wert in dem Timer-Feld 410 größer als der Alterungs-Zeitüberwachungswert ist, dann wird das Timer-an- Bit 411 gelöscht, um anzugeben, dass die Brückeninformation in dem entsprechenden gemeinsamen Block 401 gealtert ist, wie aus dem Brückenprotokoll ersichtlich ist.
Das zweite Wort 401A umfasst ebenfalls ein Timer- Sperrbit 412. Wenn das Timer-Sperrbit 412 gesetzt ist, wird das Timer-Feld 410 nicht inkrementiert. Das Timer-Sperrbit 412 wird in jedem gemeinsamen Block 401 gesetzt, für das die Alterung nicht durchzuführen ist. Wenn sowohl das Timer- Sperrbit 412 als auch das Timer-an-Bit 411 gesetzt sind, hält dies den gemeinsamen Block 401 als "dauerhaft an" aufrecht.
Das dritte Wort 401A des gemeinsamen Blocks 401 umfasst ein Port-Nummernfeld 413 und ein Zuletzt-Gesehen-Feld 414, das für das Ursprungs-Port-Lernen verwendet wird. Wenn das Port-Lern- und -Alterungs-Bit gesetzt ist und der Lernvorgang durchgeführt wird (wie es durch das passende Bit in der Aktualisierungsmaske 408 angegeben ist), schreibt die Adressen-Erkennungsmaschine 100 die Ursprungs-Port-Nummer für ein Datenpaket in das Port-Nummernfeld 413. Die Ursprungs- Portnummer wird ebenfalls in das Zuletzt-Gesehen-Feld 414 geschrieben, ob der Lernvorgang durchgeführt wird oder nicht.
Das Nachschlage-Steuerbitfeld 505 kann ebenfalls ein enable adjacency set-on-access-Bit umfassen, um der Adressen- Erkennungsmaschine 100 anzugeben, dass ein set-on-access (A_SCA)-Bit 415 (in jedem Nachbarschaftsblock 403 vorgesehen, siehe Fig. 7) zu setzen ist, wenn die Adressen- Erkennungsmaschine 100 einen Nachbarschaftsblock 403 liest. Das set-on-access-Bit 415 unterstützt die Adressenauflösungsprotokoll-Cache-Anforderungen des IP- Netzwerkprotokolls. Die Cache-Anforderung des IP-Protokolls können in dem Prozessor 201 der Leitungskarte 12 implementiert sein. Ein gesetztes A_SOA-Bit 415 gibt dem Prozessor 201 an, dass der betreffende Nachbarschaftsblock 403 bei einem Routing-Vorgang verwendet wurde.
Die sekundäre Datenbankmaske (SDB_MASK) 506 jedes Nachschlagedatenbank-Spezifikators 500 wird verwendet, um auszuwählen, welche Bytes der in den fünf Langwörtern 401B eines gemeinsamen Blocks und den vier Langwörtern eines verwandten Nachbarschaftsblocks 403 gespeicherten Daten an den Prozessor 201 bei einer bestimmten Antwort zurückzugeben sind.
Die ersten 19 Bits der Maske 506 bestimmen, welche Bytes des gemeinsamen Blocks 401 zurückgegeben werden. Jedes Byte der gemeinsamen Blöcke 401 entspricht einem der 19 Bits. Wenn das entsprechende Bit der Maske 506 gesetzt ist, wird das Byte in der Antwort zurückgegeben. Ebenso werden die nächsten 12 Bits verwendet, um zu bestimmen, welche Bytes des Nachbarschaftsblocks 403 in der Antwort zurückgegeben werden, wobei als eine Funktion hiervon die 12 Bits gesetzt werden. Wenn alle Nachbarschaftsbits der Maske 506 Null sind und das enable adjacency set-on-access-Bit des Nachschlag- Steuerbitfelds 505 nicht gesetzt ist, dann werden die Path- Split-Nachbarschaftsblockzeiger 406 nicht verwendet und das LAST_PATH-Feld 405 wird nicht inkrementiert.
Die verschiedenen Steuerbits der Präfix-String- Datenstrukturen 310, der Knotenzeiger 307, der Path-Split- Blöcke 402 und der Nachschlagedatenbank-Spezifikatoren 500 liefern eine maximale Flexibilität bei der Steuerung des Durchlaufens der primären Datenbank 301 und der Wiederherstellung der Routing- oder Brückenbildungs- Information aus der sekundären Datenbank 302. Die Steuerbitanordnung der Adressen-Erkennungsmaschine 100 baut eine Vorrichtungskompatibilität auf, um die verschiedenen Anforderungen unterschiedlicher Routing- und Brückenprotokolle in einer einzigen Speicherstruktur zu bewältigen, die für verschiedene Komponenten, die Brückenbildungs- oder Routing-Vorgänge in einem Computernetzwerk durchführen, eine zentralisierte Resource bereitstellen kann.

Claims

1. Adressen-Erkennungsvorrichtung mit:

einer Adressen-Erkennungsmaschine (100), die angepaßt ist, um eine Netzwerkadresse als einen Eingabe zu empfangen;

einer Netzwerkinformations-Nachschlagedatenbank (300), die mit der Adressen-Erkennungsmaschine gekoppelt ist;

wobei die Netzwerkinformations-Nachschlagedatenbank (300) eine Mehrzahl von Einträgen (400) umfaßt, wobei jeder der Mehrzahl von Einträgen Netzwerkinformation bezüglich einer entsprechenden Netzwerkadresse enthält;

wobei die Adressen-Erkennungsmaschine arbeitet, um eine darin eingegebene Netzwerkadresse als einen Nachschlageindex für die Nachschlagedatenbank zum Zugriff auf und Wiederherstellen von einem entsprechenden der Einträge zu verwenden;

wobei die Netzwerkinformations-Nachschlagedatenbank eine primäre Datenbank (301) und eine sekundäre Datenbank (302) umfaßt, wobei die Mehrzahl der Einträge (400) in der sekundären Datenbank angeordnet sind, die primäre Datenbank eine Mehrzahl verknüpfter Knoten (305) zum Anpassen an vorausgewählte Abschnitte einer Netzwerkadresse umfaßt, die als ein Nachschlage-Index verwendet werden, so daß der der primären Datenbank eingegebene Index die verknüpften Knoten gemäß den Übereinstimmungen (309) zwischen den verknüpften Knoten als eine Funktion einer Sequenz der vorausgewählten Abschnitte der Netzwerkadresse durchläuft, um einen sekundären Datenbankzeiger auf einem der Einträge der sekundären Datenbank zu lokalisieren;

wobei die Adressen-Erkennungsmaschine den lokalisierten sekundären Datenbankzeiger verwendet, um auf den entsprechenden der Einträge der sekundären Datenbank (302) zuzugreifen und diesen wieder herzustellen;

und dadurch gekennzeichnet, daß:

ausgewählte Einträge der Mehrzahl der Einträge (400) einen gemeinsamen Block (401), der Netzwerkinformation enthält, und einen Satz von Path-Split-Blöcken (402) enthält, wobei jeder des Satzes von Path-Split-Blöcken mit einem der gemeinsamen Blöcke verknüpft ist, wobei jeder des Satzes der Path-Split-Blöcke ein Satz von Nachbarschaftsblockzeigern (406) umfaßt, die jeweils angeordnet sind, um auf einen vorausgewählten des Satzes der Nachbarschaftsblöcken zum steuerbaren Verknüpfen des jeweiligen gemeinsamen Blocks mit einem vorausgewählten Satz von Nachbarschaftsblöcken zu zeigen.

2. Vorrichtung gemäß Anspruch 1, bei der die primäre Datenbank (301) eine Datenbank mit einer Mehrweg- Baumknotenstruktur (TRIE) umfaßt,

wobei die Netzwerkadresse (303) ein n-Bit-Adressenfeld umfaßt; und

wobei die Adressen-Erkennungsmaschine (100) das n-Bit- Adressenfeld in eine Mehrzahl von m-Bit-Zeichen (304) zur Durchquerung durch die primäre Datenbank segmentiert, wobei jedes m-Bit-Zeichen einen von 2 m verschiedenen Werten aufweist.

3. Vorrichtung gemäß Anspruch 2, bei der die Mehrzahl der verknüpften Knoten (305) mindestens einen Satz von Übergangsknoten und einen Satz von Abschlußknoten (305B) umfaßt, die mit jedem des mindestens einen Satzes von Übergangsknoten verknüpft sind, wobei jeder des mindestens einen Satzes von Übergangsknoten mit einem Stammknoten (305A) verknüpft ist, und jeder des mindestens einen Stammknotens und jeder Knoten des mindestens einen Satzes von Übergangsknoten 2 m Knotenzeiger (307) zum Verknüpfen mit nachfolgenden Knoten aufweist, wobei jeder der Knotenzeiger der Stamm- oder Übergangsknoten einem der 2 m verschiedenen Werten entspricht und auf einen nachfolgenden eines des mindestens einen Satzes von Übergangsknoten und dem verknüpften Satz von Abschlußknoten zeigt, wobei jeder der Abschlußknoten (305B) 2m sekundäre Datenbankzeiger (309) umfaßt, wobei jeder der sekundären Datenbankzeiger einer der Abschlußknoten einem der 2m verschiedenen Werten entspricht und auf einen der Einträge der sekundären Datenbank (302) zeigt, wobei die Zeichen der Netzwerkadresse in einer vorausgewählten Sequenz von Zeichen (304) auf eine entssprechende Sequenz verknüpfter Knotenzeiger eines Stammknotens und nachfolgenden Übergangsknoten einzeln angepaßt werden, um die primäre Datenbank (301) zu einem der Abschlußknoten (305B) zu durchqueren,

wobei jeder der Knotenzeiger (307) ferner Steuerinformation zur Verwendung durch die Adressen- Erkennungsmaschine umfaßt, um die Durchquerung der primären Datenbank zu einem vorausgewählten Zeichen der Zeichen umzuleiten,

wobei jeder der Übergangsknoten einen 2m + 1 Knotenzeiger enthält, und wobei die Steuerinformation ein IDI_CNT-Feld (314) sowie ein LOAD_IDI-Feld (315) umfaßt, wobei das LOAD_IDI-Feld einen eingestellten Zustand oder einen gelöschten Zustand darstellt, wobei der eingestellte Zustand der Adressen-Erkennungsmaschine angibt, daß die Durchquerung der primären Datenbank bei einem ausgewählten Zeichen der Zeichen umzuleiten ist, und der gelöschte Zustand der Adressen-Erkennungsmaschine angibt, daß die Durchquerung der primären Datenbank ohne Umleitung fortzusetzen ist, wobei das IDI_CNT-Feld eine ganze Zahl enthält, die der Adressen- Erkennungsmaschine das vorausgewählte Zeichen der Zeichen angibt, zu der die Durchquerung umzuleiten ist;

der 2m + 1 Knotenzeiger auf einen weiteren des Satzes von Übergangsknoten zum Umleiten der Durchquerung durch die Adressen-Erkennungsmaschine zeigt, wenn eine an den jeweiligen Übergangsknoten anzupassende Zeichen ein vorausgewähltes Zeichen der Zeichen ist, wie es in einem IDI_CNT-Feld eines vorherigen Übergangsknoten angegeben ist.

4. Vorrichtung gemäß Anspruch 3, bei der die Steuerinformation ein Bereichs-Übereinstimmungs- Informationsfeld (314, 315) umfaßt, wobei das Bereichs- Übereinstimmungs-Informationsfeld einen eingestellten Zustand und einen gelöschten Zustand darstellt, wobei der eingestellte Zustand der Adressen-Erkennungsmaschine (100) angibt, daß die Durchquerung der primären Datenbank zu einem ausgewählten Zeichen der Zeichen umzuleiten ist, und der gelöschte Zustand der Adressen-Erkennungsmaschine angibt, daß die Durchquerung der primären Datenbank (301) ohne Umleitung fortzusetzen ist; und

wobei die Adressen-Erkennungsmaschine einen Satz von Datenbankspezifikatoren (500) umfaßt, wobei jeder der Datenbankspezifikatoren Steuerinformation (503, 504) zum Umleiten der Durchquerung der primären Datenbank umfaßt, wenn die Bereichs-Übereinstimmungs-Information in einem der Knotenzeiger mit einem Zeichen der Netzwerkadresse, der in dem eingestellten Zustand ist, übereinstimmt;

wobei die Adressen-Erkennungsmaschine gesteuert wird, um einen der Datenbankspezifikatoren vor der Eingabe eines Index in die primäre Datenbank auszuwählen, wobei die Steuerinformation jeder der Datenbankspezifikatoren ein Bereichs-Übereinstimmungs-Zählfeld (503) und ein Bereichs- Übereinstimmungs-Stammfeld (504) umfaßt, wobei jedes Bereichs-Übereinstimmungs-Zählfeld der Adressen- Erkennungsmaschine das vorausgewählte Zeichen der Zeichen angibt, bei dem eine Umleitung der Durchquerung der primären Datenbank stattzufinden hat, wenn die Bereichs- Übereinstimmungs-Information an irgendeinem Zeichen des Index im eingestellten Zustand ist, und jedes Bereichs- Übereinstimmungs-Stammfeld der Adressen-Erkennungsmaschine einen vorausgewählten Knoten der primären Datenbank angibt, wo die Durchquerung der primären Datenbank für verbleibende, nachfolgende Zeichen des Index fortzusetzen ist.

5. Vorrichtung gemäß Anspruch 3, bei der jeder der Übergangsknoten einen sekundären Zwischendatenbankzeiger (313) zur Verwendung durch die Adressen-Erkennungsmaschine für ein bestes Übereinstimmungs-Ergebnis umfaßt; und wobei jeder der Knotenzeiger (305) ferner ein SAVE_RESULT-Feld (316) umfaßt, das einen eingestellten Zustand und einen gelöschten Zustand darstellt, wobei der eingestellte Zustand der Adressen-Erkennungsmaschine angibt, daß ein sekundärer Zwischendatenbankzeiger eines ausgewählten Übergangsknotens als ein bestes Übereinstimmungs-Ergebnis zu verwenden ist, wobei der vorausgewählte Übergangsknoten ein Übergangsknoten ist, auf den von einem Knotenzeiger gezeigt wird, der ein SAVE_RESULT-Feld in dem eingestellten Zustand aufweist, wobei jeder Knotenzeiger (307) ferner ein PTR_CTRL-Feld (318) umfaßt, um anzugeben, wenn es ein "100k-up-fail-use-best- match-result" an der Adressen-Erkennungsmaschine gibt, so daß die Adressen-Erkennungsmaschine dann den sekundären Zwischendatenbankzeiger (313) des vorausgewählten Übergangsknotens, der von dem SAVE_RESULT-Feld in dem eingestellten Zustand angegeben wird, zum Zugriff auf und Wiederherstellen von einen/einem Eintrag der sekundären Datenbank verwendet.

6. Vorrichtung gemäß Anspruch 3, bei der jeder der vorausgewählten Knoten der Mehrzahl verknüpfter Knoten (305) eine steuerbar veränderliche String-Struktur (310) zum steuerbaren Anpassen einer vorausgewählten Anzahl von Zeichen der Netzwerkadresse auf eine Anforderung (303) an dem einen Knoten der primären Datenbank umfaßt,

wobei jede String-Struktur (310) mindestens ein Wort (311) und ein Steuerfeld (312) umfaßt, wobei jedes des mindestens einen Wortes in x m-Bit-Zeichen segmentiert wird, und das Steuerfeld der Adressen-Erkennungsmaschine einen Satz der x m-Bit-Zeichen angibt, die zur Verwendung als ein Zeichen-String zum Anpassen an die entsprechenden Zeichen eines Index gültig sind,

wobei jeder Knotenzeiger ferner ein PTR_CTRL-Feld (318) umfaßt, um der Adressen-Erkennungsmaschine anzugeben, ob die steuerbar veränderliche String-Struktur eines Knotens, auf den durch den jeweiligen Knotenzeiger gezeigt wird, bei einer Anpassung an Zeichen eines Index zu verwenden ist,

wobei das mindestens eine Wort eine Mehrzahl von Wörtern umfaßt, wobei jedes der Mehrzahl von Wörtern ein Steuerfeld aufweist.

7. Vorrichtung gemäß Anspruch 1, bei der die Mehrzahl der Einträge in der Netzwerkinformations-Nachschlagedatenbank einen ersten Satz von Einträgen und einen zweiten Satz von Einträgen umfaßt,

die Adressen-Erkennungsmaschine (100) arbeitet, um eine ihr eingegebene Netzwerkadresse als einen Nachschlageindex für die Nachschlagedatenbank zum Zugriff auf und Wiederherstellen von einen/einem entsprechenden Satz/Satzes des ersten Satzes von Einträgen zu verwenden;

jeder des ersten Satzes von Einträgen (400) den gemeinsamen Block (401) aufweist, der Netzwerkinformation bezüglich der Netzwerkadresse enthält, die verwendet wird, um den entsprechenden des ersten Satzes von Einträgen zu lokalisieren;

jeder des zweiten Satzes von Einträgen (400) einen Nachbarschaftsblock (403) aufweist, der zusätzliche Netzwerkinformation bezüglich der in den gemeinsamen Blöcken enthaltenen Netzwerkinformation enthält.

8. Vorrichtung gemäß Anspruch 1, bei der jeder der Einträge (400) einen gemeinsamen Block (401) umfaßt, der Netzwerkinformation bezüglich der Netzwerkadressen enthält, die verwendet wird, um den entsprechenden der Einträge zu lokalisieren;

jeder der gemeinsamen Blöcke (401) ein Brückeninformationsfeld (410) aufweist; und wobei die Adressen-Erkennungsmaschine gesteuert wird, um einen Brückenvorgang durchzuführen, um Brückeninformation von dem Brückeninformationsfeld zu lesen und auf dieses zu schreiben.

9. Vorrichtung gemäß Anspruch 1, bei der jeder der Einträge (400) einen gemeinsamen Block (401) umfaßt, der Netzwerkinformation bezüglich der Netzwerkadresse enthält, die verwendet wird, um den entsprechenden der Einträge zu lokalisieren;

die Vorrichtung ferner einen Satz von Datenbankspezifikatoren (500) aufweist, wobei jeder der Datenbankspezifikatoren eine Informationsmaske (506) aufweist, um an die Adressen-Erkennungsmaschine vorausgewählte Abschnitte der Netzwerkinformation anzugeben, die in dem jeweiligen der Einträge enthalten ist und bei einem Nachschlagevorgang mit dem Index zurückzusenden sind; und

die Adressen-Erkennungsmaschine gesteuert wird, um einen der Datenbankspezifikatoren vor der Eingabe eines Index in die Nachschlagedatenbank auszuwählen.