DE69033517T2

DE69033517T2 - Suchvorgang innerhalb einer Datenbasis durch komprimierte Präfixassoziation

Info

Publication number: DE69033517T2
Application number: DE69033517T
Authority: DE
Inventors: Nigel T. Poole; George Varghese; Hugh M. Wilkinson Iii
Original assignee: Cabletron Systems Inc
Current assignee: Enterasys Networks Inc
Priority date: 1989-07-12
Filing date: 1990-06-08
Publication date: 2000-12-21
Anticipated expiration: 2010-06-09
Also published as: DE69033517D1; EP0408188A2; US5781772A; ATE192248T1; JPH03135668A; EP0408188B1; AU1125792A; CA2019730A1; US6014659A; AU620994B2; EP0408188A3; AU5686390A; AU644721B2

Description

Hintergrund der Erfindung

Diese Erfindung bezieht sich auf ein Präfix-Übereinstimmungsprüfen bei Datenbanksuchen.
Eine Datenbank ordnet Sätzen von Ketten bzw. Strings oder Kennbegriffen gespeicherter Information zu. Datenbanken werden oft verwendet, um nach einer bestimmten, einem gegebenen Eingabe-String oder einem Kennbegriff zugeordneten Information zu suchen.
Einige Anwendungen erfordern ferner, daß die wiederhergestellte Information dem am besten übereinstimmenden Präfix, falls vorhanden, des Eingabe-String zuzuordnen ist. Wenn beispielsweise der String "CART" der Eingabe-String in eine Datenbank ist, und die Datenbank die den Strings "C", "CA" und "CARL" zugeordnete Information hält, ist der String "CA" der mit "CART" am besten übereinstimmende Präfix, und die "CA" zugeordnete Information sollte zurückgegeben werden. Es sei bemerkt, daß "C" ebenfalls ein Präfix von "CART" ist, wobei jedoch " CA" ein besserer (d. h. längerer) Präfix als "C" ist.
Ein Suchvorgang des am besten übereinstimmenden Präfixes wird typischerweise von einer Datenbank mit einer hierarchischen, baumähnlichen Struktur durchgeführt. Diese Art von Datenbank wird oft als ein Trie bezeichnet. Eine Trie-Datenbank ermöglicht sowohl ein genaues Übereinstimmungsprüfen (d. h. Suchen nach einem String, der genau gleich dem Eingabe-String ist), sowie auch eine Übereinstimmung des besten Präfixes.
Mit Bezug auf Fig. 1 besteht ein Trie aus einer Anzahl von Knoten 32, von denen jeder Zeiger auf andere Knoten enthält. Jeder Knoten weist ein Array von n Zeigern auf, wobei ein Zeiger jedem der n möglichen Zeichen entspricht, die in einem Zeichen des Eingabe-Strings auftreten können. Der Trie umfaßt ferner einen als Wurzel bezeichneten einzigen Knoten 33, an dem die Suche oder der Suchvorgang beginnt.
Um einen String nachzuschlagen, z. B. "CAD", beginnt eine Suche an dem Wurzelknoten des Tries und verwendet das erste Zeichen "C", um einen Index in dem Array von Zeigern an dem Wurzelknoten zu setzen. Der "C"-Zeiger 34 wird auf einen Abschnitt des Tries zeigen, der Information für alle Strings enthält, die mit "C" beginnen. Die Suche wandert zu diesem neuen Knoten und verwendet das nächste Zeichen in dem Eingabe-String, "A", um in den Array von gespeicherten Zeigern zu indizieren. Der "A"-Zeiger 35 liefert die Wurzel eines weiteren Abschnitts des Tries, der Information für alle Strings aus der Gesamtheit der Strings enthält, die mit "CA" beginnen. Schließlich verwendet die Suche das letzte Zeichen "D", um in den Array zu indizieren, um den "CAD" entsprechenden, tatsächlichen Eintrag zu erhalten.
Die Speicheranforderung eines Tries kann berechnet werden und ist etwa proportional dem Produkt von: (1) der Anzahl von Einträgen in der Datenbank, (2) der Anzahl von unterschiedlichen Zeichen, (3) der durchschnittlichen Anzahl von Zeichen in einem Wort und (4) der Speichergröße eines Zeigers. Somit beträgt für eine Datenbank mit einem Verzeichnis von 50.000 Einträgen, die (2) 26 mögliche Zeichen, (3) bis zu 20 Zeichen pro Eintrag und (4) 4 Bytezeiger aufweisen, die Menge an erforderlichen Speicher etwa 2K Byte pro Eintrag oder 100 MByte.
Trotz dieser Speicheranforderung ist der Trie für ein schnelles Nachschlagen und eine Präfix-Übereinstimmungsprüfung attraktiv. Einige nützliche Anwendungen umfassen Verzeichnisnachschläge in einem Telefonkontext, Online- Wörterbücher, Rechtschreibprüfungen und Nachschlagen von Sozialversicherungsnummern.
Ein Computernetzwerk besteht aus einer Anzahl von Rechnern, die durch Router genannte Vorrichtungen miteinander verbunden sind, so daß jeder Computer als Pakete bezeichnete Nachrichten an jeden anderen Computer senden kann. Bei Analogie sind die Router Postämter, und die Pakete entsprechen Briefen. Jedes Paket trägt eine Zieladresse, und jeder Router berechnet den besten Weg zu der Zieladresse. Jeder Router entlang dieses Wegs ist für ein "Weiterleiten" des Pakets an den nächsten Router auf dem Weg verantwortlich. Dieser Weiterleitungsprozeß wird fortgesetzt, bis das Paket sein Ziel erreicht. Wenn ein Paket an einem Router ankommt, sucht der Router nach der Zieladresse in einer Weiterleitungs-Datenbank. Die Weiterleitungs-Datenbank besteht aus einer Liste von Zieladressen und dem nächsten Router in dem Weg zu jeder solchen Adresse.
Da das Postsystem zu groß ist, ist es für jedes Postamt unmöglich, eine Datenbank zu speichern, die Einträge für jede Adresse in der Welt enthält. Um einen Brief an WHITE- HALL-LONDON-ENGLAND zu leiten, wird er anstatt dessen zu erst an das Zielland (ENGLAND) und dann an die Stadt (LONDON) und schließlich an die Straßenadresse (WHITEHALL) in der Zielstadt gesendet. Somit könnten wir die Postsystemadressen aus drei Ebenen bzw. Levels einer Hierarchie bestehend beschreiben: Level 0 ist die Straßenadresse, Level I ist die Stadt und Level 2 das Land. Aus dem gleichen Grund werden Zieladressen in sehr großen Computernetzwerken ebenfalls hierarchisch aufgeteilt und weisen verschiedene Levels einer Hierarchie auf.
Ein Verfahren zum Aufbauen sehr großer Netzwerke wird durch die Routing-Norm der International Standards Organization (ISO) beschrieben. Dies wird bald eine weltweite Norm sein, die verwendet werden wird, um große globale Netzwerke zu bauen. Gemäß der ISO-Norm speichert jeder Router keine Routing-Information für jede mögliche Adresse in dem Netzwerk. Anstelle dessen speichert er Routing-Information für Teiladressen.
Beispielsweise könnte ein Router die besten Wege, um ein Paket an die Teiladressen DEC-READING-ENGLAND, ENGLAND, und LONDON-ENGLAND speichern. Es sei angenommen, daß der Router nun ein Paket, das an WHITEHALL-LONDON-ENGLAND adressiert ist, erhält. Die ISO-Norm gibt an, daß der Router das Paket i an die am besten übereinstimmende Teiladresse, die er in seiner Datenbank aufweist, senden sollte. Da der Router bei dem obigen Beispiel weiß, wie Pakete an LONDON-ENGLAND wieterzuleiten sind, sollte das Paket dahin gesendet werden. Bei diesem Schema kommt ein Paket jedes Mal, wenn es weitergeleitet wird, näher an sein Ziel.
Der ISO-Routing-Standard für weltweite Netzwerke spezifiziert, daß jeder Router in dem Netzwerk eine Datenbank von Teiladressen unterhält. Wenn ein Paket an dem Router ankommt, muß der Router die Datenbank durchsuchen und den Eintrag wiederherstellen, der der Zieladresse in dem Paket entspricht, oder, falls das fehlschlägt, den Eintrag entsprechend dem am besten übereinstimmenden Präfix der Zieladresse wiederherstellen.
Eine ISO-Routing-Norm von besonderem Interesse sind die Open Systems Interconnection (OSI) Normen, wie beispielsweise ISO 8348 Anhang 2 (ISO 8348/AD2), wie sie von der Internationalen Organisation für Normung veröffentlicht ist. Gemäß dieser Norm wurde die Verwaltung von Unterräumen einer ISO-Adresse an verschiedene international anerkannte Organisationen delegiert. Jeder dieser Organisationen wurde ein eindeutiges Anfangsadressenoktett (typischerweise acht Bit) zugeordnet, die die delegierte Verwaltung angibt. Die einzelnen Organisationen sind für ein Zuordnen weiterer Abschnitte der Adresse verantwortlich, wie durch eindeutige anfängliche Teile einer der Organisation spezifischen Länge zur Verwaltung und Zuordnung durch andere Organisation gekennzeichnet wird. Dieser Prozeß kann sich viele Male wiederholen, wobei jedoch garantiert wird, daß spezifisch zugeordnete Knotenadressen global eindeutig sind.
Ein OSI-Netzwerk Adressen-Format (NSAP-Format) ist in Fig. 2A dargestellt. Es umfaßt einen Anfangsdomänenteil IDP (initial domain part) 60 und einen Domänen-spezifischen Teil DSP (domain specific part) 70. Das Format und die Länge des IDP 60 ist genormt. Es besteht aus zwei Teilen, dem AFI 62 (authority and format identifier) und dem IDI 64 (initial domain identifier). Jedes dieser Elemente erfordert eine spezifizierte Anzahl von Bits, die in Oktetten (acht Bits) oder Halboktetten (vier Bits) gezählt werden. Die Ziffern in dem AFI und dem IDI sind binärcodierte Dezimalziffern. Jede Dezimalziffer wird durch einen Halboktett-Wert in dem Bereich von 0000 (dezimal 0) bis 1001 (dezimal 9) dargestellt.
Der AFI 62 ist auf eine Länge von zwei Halboktetten genormt (d. h. zwei binärcodierte Dezimalziffern) und wird verwendet, um die zum Zuordnen von IDI-Werten verantwortliche Behörde und das Format des IDI zu spezifizieren. Der IDI 64 kennzeichnet die Subdomäne, aus der DSP-Werte zugeordnet werden, und die für das Zuordnen der Werte verantwortliche Behörde. Abhängig von dem IDI-Format kann die tatsächliche Anzahl von Ziffern in dem IDI-Feld geringer als die Anzahl von Halboktetten sein, die dem IDI-Feld zugeordnet sind. Das durch ISO 8348/AD2 spezifizierte Preferred Binary Encoding spezifiziert, daß der IDI falls notwendig mit führenden Ziffern aufgefüllt wird, um die durch den AFI spezifizierte maximale IDP-Länge zu erhalten. Somit kann das IDI-Feld einige Ziffern 66, die Adresseninformation mitteilen, und weitere Füllziffern 65 enthalten, die keine Information mitteilen. Die nützlichen IDI-Ziffern 66 sind in dem IDI-Feld rechtsbündig, und der Rest des IDI-Felds enthält die Füllziffern 65. Der Wert des AFI kann verwendet werden, um die IDP-Länge zu bestimmen und die nützlichen IDI-Ziffern 66 zu lokalisieren, wie nachstehend vollständig erläutert wird.
In der ISO 8348/AD2-Norm spezifizierte IDI-Formate umfassen diejenigen, die durch eine Anzahl unterschiedlicher Behörden veröffentlicht wurden, einschließlich der folgenden:
X,121 (Numerierung des öffentlichen Datennetzwerks) ISO DCC (geographische Adressenzuordnung unter ISO-Steuerung)
F.69 (Telex-Numerierung)
E.163 (Telefon-Numerierung)
E.164 (ISDN-Numerierung)
ISO ICD (nicht-geographischer Adressenzuordnung unter ISO- Steuerung)
Lokal (IDI ist Null; Adresse ist nicht notwendigerweise eindeutig).
Der IDI 64 kennzeichnet die Behörde, die den DSP verwaltet. Das spezifische Format des DSP 70, mit Ausnahme seiner maximale Länge, wird gegenwärtig nicht von der ISO vorgeschrieben, sondern wird der angegebenen Behörde überlassen. Der DSP kann eine binärcodierte dezimale Syntax ähnlich dem IDP oder eine rein binäre Syntax verwenden. Wo der DSP eine binäre Syntax verwendet, wird der DSP-Wert direkt als binäre Oktette dargestellt. Wo der DSP eine dezimale Syntax verwendet, wird jede Dezimalziffer durch ein Halboktett in dem Bereich von 0000 bis 1001 (wie bei dem IDP) dargestellt. Im letzteren Fall wird wo notwendig der Halboktett-Wert von 1111 als eine Auffüllung nach dem letzten Halboktett des DSP verwendet, um die gesamte Adressenlänge auf eine ganzzahlige Anzahl von Oktetten zu runden.
Fig. 2B und 2C sind Tabellen, die die AFI-Werte und die für IDP, DSP erforderlichen maximalen Längen, und die gesamte NSAP-Adresse, die jedem IDI-Format entspricht, angeben. (Es sei bemerkt, daß bei NSAP-Adressen im ISO 8348/AD2-Format, der IDI auf die maximale Länge aufgefüllt ist). Dort wo zwei Werte für den AFI gegeben werden, identifiziert der erste einen IDI, der auf die maximale Länge mit führenden Null(0000)-Ziffern aufgefüllt ist, während der zweite einen IDI kennzeichnet, der mit führenden Nicht-Null-Ziffern aufgefüllt ist (die Nicht-Null-Auffüllziffern müssen den Wert 0001 aufweisen). Führende Nicht-Null-Ziffern werden verwendet, um die Konfusion zu mildern, wenn die erste Ziffer des tatsächlichen IDI-Werts gleich 0000 ist. Wenn Nicht-Null- Auffüllziffern in dem IDI verwendet werden, muß daher die erste Nullziffer in dem IDI die erste Nicht-Füll-Ziffer sein.
Fig. 2B findet auf Fälle Anwendung, bei denen die DSP-Syntax binär ist, wohingegen Fig. 2C auf Fälle Anwendung findet, bei denen sie dezimal ist.
Beispielsweise gibt ein Zwei-Halboktett-BCD-AFI-Wert von sechsunddreißig an: (1) das Zielsystem verwendet eine X.121 öffentliche Netzwerkadresse, (2) der IDI 64 besteht aus bis zu vierzehn signifikanten Dezimalziffern, die eine Subdomänenbehörde kennzeichnen, und (3) die DSP 70 Halboktette, falls vorhanden, werden eine Zielvorrichtung in einer binärcodierten dezimalen Syntax darstellen.
Bei der aktuellen Version der DECnet-Phase-5-Adressen für die Digital Network Architecture (DNA), wie sie von der Digital Equipment Corporation, Manard, Massachusetts, veröffentlicht ist, weist der DSP 70 eine binäre Syntax auf, und die letzten neun Oktetten des NSAP (wobei die letzten sieben desselben in dem DSP sein müssen) werden in verschiedene Felder aufgeteilt, wie es in Fig. 2A gezeigt ist. (Solche Felder in Fig. 2A, die DNA-spezifisch sind, werden mit einem Stern (*) markiert).
Die LOC-AREA 72 ist ein Feld, daß für eine Rückwärts-Kompatibilität mit früheren Versionen der DNA und für mögliche zukünftige Verbesserungen definiert ist. Die LOC-AREA 72 ist als die ersten zwei Oktette der letzten neun Oktette der NSAP definiert.
Die Level-1-ID 74 ist ein sechs Oktettfeld, daß das Zielsystem innerhalb eines DECnet-Bereichs eindeutig identifiziert. Ein korrekter Betrieb des DNA-Network-Routing-Layer erfordert nur, daß das ID 74 Feld innerhalb eines DECnet- Bereichs eindeutig ist (ausgenommen für Level-2-Router, wobei die Level-1-ID des Level-2-Routers typischerweise innerhalb des gesamten privaten Netzwerks eindeutig ist). Das ID-Feld wird jedoch gewöhnlich aus dem IEEE 802 Adressenraum ausgewählt, wobei in diesem Fall garantiert ist, daß es global eindeutig ist. Wenn eine 802 Adresse verwendet wird, kann sie der tatsächlichen Data-Link-Adresse des Knotens auf einem 802 LAN entsprechen, wobei jedoch diese Korrespondenz durch die Routing-Algorithmen nicht angenommen oder gefordert werden.
Das SEL 76 ist ein Oktettfeld an dem Ende einer DECNET-Phase- V-Adresse. Das SEL wirkt als ein Selektor für das Modul, das das Paket zu empfangen hat, wenn es einmal sein Ziel erreicht. Die Verkettung des IDP 60 und des führenden Teils des DSP (d. h., wenn es existiert, des Teils des DSP, das den letzten neun Oktetten vorangeht) wird als die PRE-LOC-AREA 80 bezeichnet. Die Verkettung des PRE-LOC-AREA und des LOC-AREA ist als die Bereichsadresse 90 bekannt. (Somit besteht die Bereichsadresse aus allen ausgenommen der letzten sieben Byte der NSAP). Wenn ein Paket eine Bereichsadresse 90 aufweist, die genau mit der des lokalen Bereichs übereinstimmt, dann ist das Ziel des Pakets lokal in diesem Bereich und wird durch Level-1-Routing unter Verwendung des Level-1-ID-Felds 74 weitergeleitet. Andernfalls wird es durch Level-2-Routing weitergeleitet. Das Level-2-Routing wirkt auf Präfix-Teile der Bereichsadresse, wobei das Paket zu dem Bereich dirigiert wird, dessen Bereichsadresse die maximale genaue Übereinstimmung mit der Paketadresse aufweist.
Weitere Nicht-DNA-Knoten müssen den DNA-Adressierungskonventionen oder den DAN-Anforderungen nicht folgen. Routers, die für einen DNA-Adressensyntax entwickelt wurden, werden jedoch mit Nicht-DNA-Knoten und Nicht-DNA-Netzwerken zusammenwirken, wenn bestimmte Anforderungen erfüllt werden. Es gibt verschiedene mögliche Modi einer Zusammenwirkung:
Bei einem Modus arbeitet ein Nicht-DNA-Endsystem in dem Level-2-DNA-Netzwerk, und ein benachbarter Level-2-Router wird manuell konfiguriert, um Pakete an das Endsystem über einen "erreichbaren Adresseneintrag" der DNA weiterzuleiten. Die einzige Anforderung der Adresse des Nicht-DNA-Endsystems besteht darin, daß jedes Präfix der Adresse des Endsystems, das durch Entfernen von höchstens 14 hinteren Halboktetten gebildet wird, von allen Bereichsadressen in dem Level-2- Netzwerk unterschiedlich sein muß.
Als ein Endsystem in einem bestimmten DNA-Bereich wird die Adresse des Nicht-DNA-Knotens der Einschränkung unterworfen, daß die führende Oktette vor den letzten sieben Oktetten gleich der Bereichsadresse des Bereichs sein müssen, in dem der Knoten residiert. Außerdem müssen die führenden sechs Oktette der letzten 7 Oktette eine eindeutige Level-1-ID innerhalb des Bereichs bilden. Eine Konfiguration des benachbarten Routers findet manuell oder automatisch über das Es/IS (ISO 9542)-Protokoll statt.
Schließlich wird ein DNA-Netzwerk mit autonomen Netzwerken von Nicht-DNA-Knoten via erreichbaren Adressen unter Verwendung von Adressen-Präfixen zusammenwirken.
Ein Routing in einem Netzwerk basiert auf einer weiterleitenden Datenbank. In einer weiterleitenden Datenbank wird jede aufgelistete Zieladresse mit dem nächsten Link und der Adresse auf dem Link des Routing-Wegs, den ein Paket nehmen sollte, um sein Ziel zu erreichen, quer verbunden.
Die Datenbank kann in zwei Teile aufgeteilt werden: (i) einen Teil, der Netzwerkadressen auf interne Indizes abbildet, und (ii) einen Teil, der die internen Indizes auf Sätze von Links und Link-Adressenelemente abbildet.
Ein Netzwerk-Router erhält die Zieladresseninformation von dem Header eines empfangenen Pakets, greift auf die Datenbank zu, um den besten nächsten Link, durch den das Paket weiterzuleiten ist, und die Datenlinkadresse auf diesem Link zu bestimmen, und leitet das Paket demgemäß weiter.
Bekannte Datenbankformate beeinflussen die Rate, mit der Pakete weitergeleitet werden, und die Speicheranforderungen der Datenbank können groß sein.
ACM Transactions on Database System 14 (1989), Seiten 41 - 74; R Ramesh et al. "Variable Depth Trie Index Optimization: Theory and Experimental Results" beschreibt eine Technik zum Verringern Speicheranforderung einer Trie-Datenbank durch ) Entfernen von Sub-Tries von der Datenbank und Verwenden einer Nicht-Trie-Suchtechnik, um innerhalb des den entfernten Sub- Tries entsprechenden Teilen der Datenbank zu suchen.

Zusammenfassung der Erfindung

Gemäß der Erfindung erfordert eine Routing-Datenbank weniger Platz als vorbekannte Datenbanken für eine identische Funktion. Außerdem wird Routing-Information unter Verwendung weniger aufwendiger Hardware schneller gefunden.
Die vorliegende Erfindung liefert ein Verfahren und eine Vorrichtung zum Durchführen von Suchen entlang einer Weglänge einer verringerten Länge gemäß den beigefügten unabhängigen Ansprüchen.
Bei einem Aspekt wird ein Knoten, der sonst zwischen einem vorhergehenden und einem folgenden Knoten in dem Suchweg auftreten würde, eliminiert, und Informationen wird so gespeichert, wie die Suche nach den folgenden Knoten vorangeschritten wäre, wenn dieser eliminierte Knoten anwesend gewesen wäre. Während der Suche wird ein Suchargument mit der gespeicherten Information verglichen, und die Suche schreitet wirksam von den vorhergehenden Knoten direkt zu dem folgenden Knoten voran, wenn der Vergleich positiv ist.
Bevorzugte Ausführungsformen umfassen die folgenden Merkmale. Einige Knoten liefern Ergebniswerte für die Suche. Ein Knoten wird nur eliminiert, wenn seine Anwesenheit den Ergebniswert für die Suche nicht beeinflussen würde. Die zu vergleichende Information wird in dem folgenden Knoten gespeichert. Die Suche weist erste und zweite Modi auf, wobei der erste Modus Verarbeitungsknoten entlang des Suchweges umfaßt. Der eliminierte Knoten ist einer, der, wenn er vorhanden wäre, entweder veranlassen würde, daß die Suche zu dem folgenden Knoten weiterschreiten würde, oder veranlassen würde, daß die Suche in den zweiten Modus eintreten würde. Das Suchargument umfaßt eine Reihe von Suchsegmenten, wobei einige Werte der Segmente des Arguments Knoten entlang des Suchwegs entsprechen, wobei einige andere Werte der Segmente sich auf den zweiten Modus der Suche beziehen. Die gespeicherte Information ist eine Sequenz der Suchsegmente. Indikatoren sind den Knoten zugeordnet, wobei jeder Indikator die Segmente angibt, die dem zweiten Modus entsprechen. Der Suchweg wird durch Verarbeiten aufeinanderfolgender Suchsegmenten, wobei die Verarbeitung ein Prüfen des jedem Knoten zugeordneten Indikators umfaßt, und durch Voranschreiten zu dem zweiten Suchmodus, wenn der Indikator angibt, daß das Segment sich auf den zweiten Modus bezieht, abgesucht. Der zweite Modus der Suche umfaßt ein Terminieren der Suche. Das Suchargument umfaßt eine Systemadresse in einem Netzwerk.
Weitere Vorteile und Merkmale werden aus der folgenden Beschreibung der bevorzugten Ausführungsform und aus den Ansprüchen offensichtlich.

Beschreibung der bevorzugten Ausführungsform

Wir beschreiben zuerst kurz die Zeichnungen.
Fig. 1 ist ein Diagramm einer Trie-Datenbank.
Fig. 2A ist ein Diagramm eines OSI-Netzwerkadressenformats.
Fig. 2B und 2C sind Tabellen von IDI-Formaten.
Fig. 3 ist ein Blockdiagramm eines Routers mit einer Erkennungsmaschine.
Fig. 4 ist ein Diagramm einer nicht-komprimierten Routing- Datenbank-Struktur.
Fig. 5 ist ein Diagramm einer Zeiger-komprimierten Routing- Datenbank-Struktur.
Fig. 5A ist ein Diagramm einer Zeiger-komprimierten Knotenstruktur.
Fig. 6 ist ein Diagramm einer Weg-komprimierten Routing- Datenbank-Struktur.
Fig. 7 ist ein Diagramm einer Teil-Datenbank-Struktur, die die Vorkehrungen für IDI-, DSP- und Level-1-Verarbeitung veranschaulichen.
Fig. 8 ist ein Diagramm der Datenwege einer Erkennungsmaschine.
Fig. 9 ist eine Tabelle, die die Stellen von Knotendaten in den Speichern von Fig. 8 veranschaulicht.

Struktur und Betrieb

Tries sind ein geeigneter Kandidat zum Aufrechterhalten einer Teiladressen-Datenbank in ISO-Routern. Tries unterstützen ohne weiteres eine Präfix-Suche einer besten Übereinstimmung mit einer Zieladresse. Außerdem sind Tries zum Suchen nach Strings großer und veränderlicher Länge, wie beispielsweise ISO-Teiladressen, geeignet. Die Speicheranforderungen von Ines können jedoch die Verwendung von Tries in praktischen Routern ungeeignet machen. Um ein Trie auf ISO-Adressen anzuwenden, muß das Trie-Suchverfahren ferner auf die besonderen Charakteristiken von ISO-Adressen, wie beispielsweise die oben erläuterten Felder variabler Länge und Füllziffern, angepaßt werden.
Die Erfindung verringert die Speicheranforderungen einer Trie-Datenbank und paßt ferner eine Trie-Suche an ISO-Adressen an. Die durch die Erfindung erreichten Speicherreduzierungen werden in Anhang C ausführlich dargestellt.
Die Verfahren zum Verringern von Trie-Speicheranforderungen sind auf Tries in einer weiten Vielfalt von Zusammenhängen außerhalb der bevorzugten Ausführungsform anwendbar; die Verfahren zum Anpassen von Trie-Suchen an ISO-Adressen können ebenfalls in anderen Zusammenhängen nützlich sein.
Mit Bezug auf Fig. 3 wird beim ersten Betrieb eines Routers 10 ein Paket 11 an einer Empfangseinheit 12 empfangen. Die Empfangseinheit 12 liefert das Paket an eine Weiterleitungs- Maschine 14. Die Weiterleitungs-Maschine 14 verarbeitet den Paket-Header, wobei die Zielnetzwerkadresse extrahiert und an eine Erkennungsmaschine 20 transferiert wird. Eine logische Einheit 22 liefert die von der Weiterleitungs-Maschine 14 verwendeten logischen Signale, um sie mit der Erkennungsmaschine 20 schnittstellenmäßig zu verbinden. Die Erkennungsmaschine 20 verwendet die Zieladresse, um einen Index aus einer im Speicher 50 gespeicherten Datenbank wiederherzustellen. Dieser Index wird an die Weiterleitungs-Maschine 14 zurückgegeben, die den Wert verwendet, um auf eine Weiterleitungs-Datenbank (nicht gezeigt) zuzugreifen. Die Weiterleitungs-Datenbank besteht aus Sätzen von Link-Bezügen und Link-Adressen. Die Weiterleitungs-Maschine 14 verwendet dann den Link-Bezug, um das Paket 11 an eine von mehreren Übertragungseinheiten (X-Mit) 26A bis 26D zu dirigieren (vier werden für darstellende Zwecke gezeigt). Die Übertragungseinheiten 26A bis 26D sind für Warteschlangenpakete und zum Senden derselben über die Netzwerk-Kommunikations-Links 16 an weitere Router oder Zielsystemen verantwortlich.
In der Adressen-Erkennungsmaschine 20 empfängt eine Holeinheit 30 (Fetch Unit) die Paketzieladresse von der Weiterleitungs-Maschine 14 und liefert die Adresse, oder spezifische Fragmente der Adresse, an eine Sucheinheit 40. Die Sucheinheit 40 verwendet die Adressen oder die von der Holeinheit 30 präsentierten Adressenfragmente, um direkt auf den Speicher 50 zuzugreifen. Aus dem Speicher 50 geholte Zwischenergebnisse werden von der Sucheinheit 40 verarbeitet und in Verbindung mit der durch die Holeinheit 30 präsentierten Adresse verwendet, um auf weitere Zwischenergebnisse und schließlich auf das Endergebnis zuzugreifen. Das Endergebnis wird von der Sucheinheit 40 an die Weiterleitungs- Maschine 14 zurückgegeben, die das Ergebnis als einen Index in der Weiterleitungs-Datenbank (nicht gezeigt) verwendet.
Bei anderen Betriebsmodi kann die Datenbank von einer Management-Maschine 18 verwendet werden (siehe Anhang B). Die Management-Maschine 18 ist zum Erzeugen und Unterhalten der im Speicher 50 gespeicherten Datenbank verantwortlich. Die Management-Maschine 18 empfängt Information über die aktuelle Netzwerk-Verschaltung auf einer kontinuierlichen Basis durch Wege, die nicht gezeigt sind. Die Management-Maschine 18 präsentiert Adressenfragmente, die von der Netzwerk- Verschaltungs-Information erzeugt wurden, an die Sucheinheit 40. Das Ergebnis dieser Suche wird an die Management-Maschine 18 zurückgegeben, die das Ergebnis verwendet, um etwas über die aktuelle Information in der Datenbank zu lernen. Wenn es notwendig ist, die Datenbank zu aktualisieren, so daß sie die aktuelle Netzwerk-Konnektivität richtig darstellt, greift die Management-Maschine 18 direkt auf den Speicher 50 zu, um die Änderungen zu bewirken.
Wie in dem Hintergrund der Erfindung erwähnt wurde, muß der Router 10 imstande sein, ein Level-1- und ein Level-2-Routing durchzuführen. Das Level-1-Routing erfordert, daß eine genaue Übereinstimmung der von der Holeinheit 30 präsentierten Netzwerkzieladresse in der Datenbank vorhanden ist. Es gibt viele bekannte Datenbankstrukturen, die es ermöglichen, daß eine genaue Übereinstimmung verwirklicht wird. Ein Level-2-Routing erfordert jedoch, daß, wenn eine genaue Übereinstimmung nicht gefunden werden kann, der Eintrag in der Datenbank, der das längste Präfix der Netzwerkzieladresse aufweist, dann lokalisiert werden sollte. Diese Anforderung begrenzt die Anzahl unterschiedlicher Datenbankstrukturen, die verwendet werden können.
Bei der Erfindung ist die im Speicher 50 gespeicherte Datenbank eine besondere Art einer Baumstruktur, die als ein TRIE bekannt ist. Fig. 4 ist ein Beispiel eines Teils einer solchen TRIE-stukturierten Datenbank. Jeder Knoten 110 des TRIES kann ein Array von 16 Zeigern 105 auf andere Knoten 110 enthalten. Ein Übergang von der Wurzel des Tries zu anderen Knoten 110 wird durch Fragmentieren des Sucharguments (z. B. einer Netzwerkzieladresse) in eine Sequenz von Segmenten (z. B. Halboktette) durchgeführt; wobei an jedem Knoten in dem Ine das nächste Halboktette in der Sequenz, das einen Wert von null bis fünfzehn aufweist, verwendet wird, um einen der sechzehn Zeiger auszuwählen.
Mit Bezug auf Fig. 3 zeigt das aktuelle Knotenregister 41 seinerseits auf die Knoten des TUE, die während einer Suche durchlaufen werden. Wenn eine Suche initiiert wird, wird das aktuelle Knotenregister 41 auf einen Punkt an der Wurzel des TRTE gesetzt. Bei der Fragmentierung des Sucharguments in Halboktette entsprechen die gebildeten Halboktette den vorher erläuterten bildenden Ziffern der NSAP.
Mit Bezug auf Fig. 4 werden Knoten 110 mit Zeigern Elternknoten (parent nodes) genannt; die Ziele der Zeiger sind Kinderknoten (child nodes). Knoten in dem Trie, die keine Zeiger auf andere Knoten enthalten (z. B. Knoten 110-8, 110-9 und 110-11) werden als "Terminal-Knoten" bezeichnet. Wenn die Suche einen Terminal-Knoten erreicht, wird die Suche beendet. 1 Die Suche wird ferner beendet, wenn der durch das nächste Halboktett ausgewählte Zeiger 105 auf einem NIL-Knoten 115 zeigt (obgleich mehrere Knoten von Fig. 3 Null-Ergebniswert enthalten können, wurden zwecks Klarheit viele weitere Nil- Knoten weggelassen).
Wenn ein Terminal-Knoten durch Verwenden aller der Halboktette in dem Suchargument erreicht wird, dann wurde eine genaue Übereinstimmung in der Datenbank gefunden, und der Terminal-Knoten hält einen Ergebniswert 120, der dem Suchargument entspricht. Wenn jedoch ein NIL-Knoten 115 oder ein Terminal-Knoten (z. B. 110-8) erreicht wird, bevor alle Sequenzen von Halboktetten verwendet wurden, dann ist keine genaue Übereinstimmung des Suchobjekts in der Datenbank enthalten.
Es ist möglich, daß ein Präfix des Suchobjekts in der Datenbank enthalten ist; wenn dies der Fall ist, dann wird mindestens einer der während der Suche durchlaufenden Knoten einen Ergebniswert 120 enthalten. Wenn kein durchlaufender Knoten einen Ergebniswert enthält (z. B. ein Suchvorgang, der am Knoten 110&supmin;¹³ endet) dann existiert kein solcher Präfix in der Datenbank. Wenn viele Knoten, die einen Ergebniswert halten, durchlaufen werden, dann sind viele Präfixe des Suchobjekts in der Datenbank enthalten: der erste solcher durchlaufender Knoten hält ein Ergebnis, das dem kürzesten Präfix entspricht, während der letzte derart durchlaufender Knoten ein Ergebnis hält, das dem längsten Präfix entspricht. Das dem längsten Präfix entsprechende Ergebnis wird als das Ergebnis der Suche zurückgegeben.
In vielen Fällen würde der Ergebniswert 120 für einen Kinderknoten und seinen Elternknoten identisch sein. In diesen Fällen (z. B. Knoten 110-5 und 110-7) hält der Kinderknoten keinen Ergebniswert 120. Wenn die Suche an einem Kinderknoten beendet wird, der keinen Ergebniswert 120 enthält, wird der Ergebniswert 120 des zuletzt durchlaufenden vorhergehenden Knotens, der einen Ergebniswert aufweist, zurückgegeben. Auf diese Art wird der entsprechende Ergebniswert eines in der Datenbank gespeicherten Präfixes nur bei einem Knoten eingegeben, was die Wartung vereinfacht.
Die vorhergehenden Abrisse einer Trie-strukturierte Datenbank können verwendet werden, um es einem Suchprozeß zu ermöglichen, eine genaue Übereinstimmung oder eine Übereinstimmung des besten Präfixes eines gegebenen Sucharguments zu lokalisieren. Zwei Formen einer Datenbankkomprimierung werden bei bevorzugten Ausführungsformen der Erfindung verwendet, um die Speichermenge zu verringern, die erforderlich ist, um die TRIE-Struktur zu unterstützen. Diese sind als Zeiger-Komprimierung und Weg-Komprimierung bekannt.
Mit Bezug auf Fig. 5 wird eine Zeigerkomprimierung durch Eliminieren aller Nil-Knoten und aller Zeiger auf Nil-Knoten von dem Trie erreicht. Dies wird durch Zuordnen einer Zeiger- Bit-Mask 115 zu jedem Elternknoten in dem TRIE durchgeführt. Die Bit-Mask gibt an, welche der Kinderknoten Nil sind, d. h. welche der Zeiger 105 auf Nil-Knoten zeigen. Jedes Bit in der Maske entspricht einem der Zeiger des Elternknotens, und wird gesetzt, wenn der Zielknoten des Zeigers Nicht-Null ist; andernfalls wird er gelöscht.
Beispielsweise ist der Wurzelknoten 100 der Bit-Mask 115-0 zugeordnet. Zwei Nicht-Nil-Kinderknoten 110-1, 110-2 existieren unterhalb des Wurzelknotens 100. Somit enthält die Wurzelknoten-Bit-Mask 115-0 zwei "1" Bits, einen für jede der Nicht-Nil-Kinderknoten. Alle weiteren Bits der Maske sind "0", was angibt, daß alle anderen Kinderknoten des Wurzelknotens Nil-Knoten sind.
Durch Vergleichen von Fig. 5 mit Fig. 4 ist ersichtlich, daß die Stelle dieser beiden "1" Bit genau der Stelle der beiden Zeiger entspricht. Bevor zu einem Kinderknoten weitergegangen wird, prüft die Sucheinheit 40 die Eltern-Bit- Maske 115 im Betrieb, um zu bestimmen, daß der neue Knoten Nicht-Nil ist. Wenn der neue Knoten Nil ist, wird die Suche sofort beendet, ohne daß man sich zu dem neuen Knoten bewegt.
Somit werden mit Bezug auf Fig. 5A alle Nil-Knoten (und die Zeiger, die Nil-Knoten angeben) von dem Trie eliminiert, wobei Speicherplatz gespart wird. Da es notwendig sein würde, nur einen Nil-Knoten für den gesamten TRIE zu speichern, sind die Speicherersparnisse ein Ergebnis der Eliminierung der Zeiger auf den Nil-Knoten oder die Knoten. Mit einer Zeiger- Komprimierung können die Speicheranforderungen für eine TRIEstrukturierte Datenbank verringert werden, wobei jedoch die Berechnung der aktuellen Knotenadresse komplizierter ist. Um die Adresse der neuen Knoten zu bestimmen, muß die Sucheinheit 40 auf die Bit-Maske 115 der Eltern Bezug nehmen, um die Anzahl und die Verteilung der Zeiger 105 zu bestimmen. Wenn die Bit-Maske angibt, daß der dem nächsten Halboktett in der Sequenz entsprechende Zeiger vorhanden ist, wird die Bit- Maske verwendet, um die Stelle des erforderlichen Zeigers 115 in der in dem Eltern-Knoten gespeicherten Zeigerliste zu bestimmen.
Um eine Wegkomprimierung einzuführen, sei zuerst bemerkt, daß eine Zeigerkomprimierung alle Nil-Knoten und Zeiger auf Nil-Knoten eliminiert hat, wobei jedoch die Weglänge (d. h. die Anzahl von Knoten) von dem Wurzelknoten zu irgendeinem gegebenen Ergebnisknoten nicht verringert wurde. Eine Wegkomprimierung wird verwendet, um derartige Verringerungen zu erreichen.
Eine Wegkomprimierung eliminiert jeden Knoten in der Datenbank, der (1) nur einen Kinderknoten und (2) keinen Ergebniswert oder den gleichen Ergebniswert wie sein Elternknoten aufweist. Der Knoten 110-7 von Fig. 5 erfüllt diese Anforderungen. Mit Bezug auf Fig. 6 wurde nach einer Wegkomprimierung der Knoten 110-7 eliminiert, und der Knoten 110-11 ist direkt unter dem Knoten 110-2.
Bei der bevorzugten Ausführungsform der Erfindung werden die Halboktette, die dem (einen oder mehreren) eliminierten Knoten entsprechen, als ein Wegkomprimierungs-Ziffern-String 125 gespeichert. (In Fig. 6 weist der String eine Länge von gerade einer Ziffer auf.) Im Betrieb vergleicht die Sucheinheit 40 jede Stelle der Wegkomprimierungs-Ziffern-String 125 mit aufeinanderfolgende Halboktette des Suchobjekts. Alle Vergleiche müssen eine Übereinstimmung angeben, um zu dem nächsten Knoten voranzuschreiten. Wenn irgendeiner der Vergleiche fehlschlägt, wird die Suche an dem gerade vor der Wegkomprimierungs-Ziffern-String 125 durchlaufenden Knoten beendet. Indem eine Wegkomprimierung auf diese Art und Weise implementiert wird, kann die TRIE-Datenbank verwendet werden, um das beste Präfix für ein Suchobjekt zu lokalisieren. Dies wäre nicht möglich, wenn die übersprungenen Halboktette nicht verarbeitet würden.
Bei bevorzugten Ausführungsformen wird der Wegziffern-String am Kinderknoten gespeichert. Wenn ein String an einem Kinderknoten vorhanden ist, muß der String mit nachfolgenden Halboktetten des Suchobjekts erfolgreich übereinstimmen, um am Kinderknoten anzukommen. Wenn die String-Übereinstimmung fehlschlägt, wird der Mißerfolg behandelt, als ob ein Nil- Zeiger am Elternknoten ausgewählt wurde.
Dieser Prozeß wird in Fig. 6 durch die Zwischenschaltung des Wegziffern-Strings 125 zwischen dem Knoten 110-2 und 110-11 diagrammartig angegeben. Die Existenz eines Wegziffern- Strings in einem Knoten wird durch ein Flag-Bit an diesem Knoten angegeben. Wenn dieses Flag gesetzt ist, weist der Knoten einen zugeordnete Wegstellen-String auf; wenn dieses Flag nicht gesetzt ist, enthält der Knoten keinen derartigen String. Wie in Fig. 6 ersichtlich ist, wurden Flag-Bits bei jedem der Knoten 110 aufgenommen.
Somit führt die Zeigerkomprimierung und die Wegkomprimierung zu verringerten Speicheranforderungen für eine TRIE-strukturierte Datenbank, wobei genau die gleiche Funktionalität wie für eine nicht-komprimierte Datenbank möglich wird.
Die oben beschriebene optimierte TRIE-Struktur erfordert einige Verbesserungen, damit sie eine OSI-Netzwerk-Zieladresse (NSAP = network destination address) in dem Kontext eines DECNET-Phase-V-Routing richtig verarbeiten kann. Die bisher beschriebenen Mechanismen ermöglichen Suchvorgänge, die imstande sind, genaue Übereinstimmungen und maximale Längen von Präfix-Übereinstimmungen der Eingangsadresse zu finden. Diese Mechanismen müssen verbessert werden, um: (i) gespeicherte Adressen-Präfixe zu erlauben, die kürzer als der IDP sind, um Adressen auf Gleichheit zu prüfen, deren führende signifikante IDI-Ziffern mit den signifikanten IDI-Ziffern des gespeicherten Präfix identisch sind; und (ii) ein Erkennen von Bereichsadressen zu erlauben, die einen Übergang auf eine Level-1-Datenbank veranlassen (da Netzwerkadressen von veränderlicher Länge sind, ist es für eine gespeicherte Bereichsadresse möglich, mit den führenden Halboktetten einer Eingangsadresse übereinzustimmen, ohne daß die Eingangsadresse die Anforderung erfüllt, daß genau 14 Halboktette nach der übereinstimmenden Bereichsadresse übrig bleiben.
Als Beispiel sei ein in der Datenbank gespeicherter Präfix 37-123 betrachtet, um die Anforderung für die erste Verbesserung zu veranschaulichen. Bei diesem Beispiel gibt der AFI "37" an, daß die IDP-Länge 16 Ziffern beträgt (d. h. die IDI- Länge beträgt 14 Ziffern). Die Ziffern, die dem Bindestrich folgen, d. h. "123", sind die führenden signifikanten Ziffern des IDI. Jede beispielsweise durch die Holeinheit 30 präsentierte Adresse, deren AFI gleich "37" ist und deren führenden signifikanten IDI-Ziffern gleich "123" sind, sollten einen Knoten in dem TRIE durchlaufen, der eine Erkennung des Präfix 37-123 angibt. Es seien die folgenden drei Adressen betrachtet, wie sie durch die Holeinheit 30 präsentiert werden:
(i) 37000000000123456789abcdef
(ii) 3700000000000123456789ab
(iii) 37000000000000123456789abcdef
Die erste Adresse weist signifikante IDI-Ziffern auf, die gleich "12345" sind. Die zweite Adresse weist signifikante IDI-Ziffern auf, die gleich "123" sind. Die dritte Adresse weist signifikante IDI-Ziffern auf, die gleich "12" sind. Somit enthalten die erste und die zweite Adressen das Präfix 37-123, jedoch die dritte Adresse nicht. Da es eine beliebige Anzahl von Füllziffern in dem IDI (zwischen 0 und 11) in einer Adresse geben kann, die das obige Präfix 37-123 enthält, würde ein nicht-modifizierter Adressenerkennungs- Trie zwölf unterschiedliche Zweige für das Präfix 37-123 aufweisen, wobei jeder eine unterschiedliche Anzahl von Füllziffern (in dem Bereich von 0 bis 11) darstellt, und jeder zu einem unterschiedlichen Knoten führt, der mit dem dem Präfix 37-123 entsprechenden Ergebnis gekennzeichnet wird. Diese Struktur ist jedoch nicht elegant und speicherintensiv.
Eine bevorzugte Art und Weise, um das Präfix 37-123 zu speichern, besteht darin, alle IDI-Füllziffern als nicht beachtenswert zu behandeln. Dann wird der Knoten, der das dem Präfix 37-123 entsprechende Ergebnis speichert, nach der Halboktetten-Sequenz 3,7,1, 2,3 erreicht. Bei bevorzugten Ausführungsformen werden Füllziffern einfach als nicht beachtenswert betrachtet, ohne daß der Grundbetrieb des TRIEs geändert wird. Füllziffern werden als nicht beachtenswert betrachtet, indem der TRIE derart angeordnet wird, daß IDI- Füllziffern Zeiger 105 auswählen, die auf den Elternknoten und nicht auf einen unterschiedlichen Kinderknoten zurückzeigen. (Als eine Konsequenz dieser Selbstbezugnahme kann ein Knoten, der der ersten Ziffer des IDI entspricht, keinen zugeordneten Wegkomprimierungs-Ziffern-String aufweisen.)
Ohne eine weitere Modifikation wird, wenn die IDI-Füllziffern einmal als nicht beachtenswert betrachtet worden sind, die dritte Adresse in der obigen Beispielliste ebenfalls entlang des Wegs 3,7,1, 2,3 laufen und fälschlich angeben, daß sie das Präfix 37-123 enthält. Um dies zu überwinden, werden dem Grund-TRIE zwei Mechanismen hinzugefügt: (i) einen Zähler, der verbleibende IDI-Längenzähler 43 (Fig. 3), der einen Zählwert der verbleibenden IDI-Ziffern der Eingangssuchadresse unterhält; und (ii) einen 17ten Zeiger, DSP-Zeiger genannt, der von einem eine Ziffer des IDI darstellenden Elternknoten auf einen die erste Ziffer des DSP darstellenden Kinderknoten zeigt. Auf den 17ten Zeiger wird zugegriffen, wenn der IDI-Längenzähler auf Null dekrementiert ist.
Im Betrieb speichern während einer Suche einer Netzwerkzieladressen die Knoten in dem TRIE, die nach einem Verarbeiten des zweiten Halboktetts der Adresse erreicht werden, die entsprechenden IDI-Längen. Daß eine IDI-Länge gespeichert ist, wird durch ein zusätzliches Flag-Bit angegeben. Die Sucheinheit 40 erkennt, daß das Flag gesetzt ist, liest die an dem Knoten gespeicherte IDI-Länge und transferiert sie zu dem IDI-Längenzähler 43. Jedesmal, wenn ein Halboktett von der Sucheinheit 40 verarbeitet wird (einschließlich der Füllziffern des IDI), wird der IDI-Längenzähler 42 um Eins dekrementiert. Wenn die IDI-Länge auf Null dekrementiert ist, wurde der gesamte IDI verarbeitet. An diesem Punkt wird der 17te (d. h. DSP)-Zeiger an dem aktuellen Knoten ausgewählt. Es sei bemerkt, daß es dann, wenn der AFI-Wert 48 oder 49 ist, keinen IDI gibt; somit müssen Knoten in der Datenbank, die diesen AFI-Werten entsprechen, eine Angabe, daß die IDI-Länge Null ist, und ferner einen 17ten Zeiger für einen sofortigen Übergang in die DSP-Domäne der Datenbank vorsehen.
Ein weiteres Beispiel veranschaulicht den Bedarf für eine zweite Verbesserung des Grund-TRIEs, die sich auf ein Erkennen von Bereichsadressen bezieht. Es sei betrachtet, daß ein Router in einem durch die Bereichsadresse 47123400000000abcd definierten DECNET-Bereich wirksam ist. Unter Bezug auf die Fig. 2A und 2B können unterschiedliche Felder dieser Bereichsadresse erkannt werden, wie es gezeigt ist:
Als nächstes sei betrachtet, daß die folgenden drei Netzwerkzieladressen der Sucheinheit 40 durch die Holeinheit 30 präsentiert werden (die aus den durch das Netzwerk laufenden Pakete extrahiert wurden):
(i) 47123400000000abcd0123456789ab00
(ii) 47123400000000abcd0123456ff
(iii) 47123400000000abcd01234567ff89ab00
Die führenden Ziffern der ersten Adresse stimmen genau mit der Bereichsadresse des Bereichs überein, in dem der Router residiert. Die verbleibenden Ziffern können als zwei Felder interpretiert werden: (a) ein Feld mit 12 Halboktetten 0123456789ab, das der DECNET-Level-1-ID-Teil der Adresse ist, und (b) ein zweites Halboktett-Feld 00, das das DECNET SEL- Feld ist. Somit sollte das Paket, von dem die erste Adresse extrahiert wurde, als für ein Endsystem innerhalb des Bereichs bestimmt betrachtet werden, und sollte durch DECNET Level-1-Routing weitergeleitet werden. Für den Level-1-ID- Teil muß in der Datenbank eine genaue Übereinstimmung gefunden werden, so daß das Paket an das richtige Endsystem weitergeleitet werden kann.
Die führenden Ziffern der zweiten Adresse stimmen ebenfalls genau mit der Bereichsadresse des Bereichs überein, in dem der Router residiert. Wenn die verbleibenden Ziffern geprüft werden, gibt es Neun. Somit können die verbleibenden Ziffern nicht als ein Level-1-ID-Teil plus ein SEL-Teil interpretiert werden; demgemäß ist das Paket, das die spezifizierte Zieladresse enthält, nicht für ein Endsystem innerhalb des Bereichs, bestimmt, in dem der Router residiert. Die zufällige Übereinstimmung zwischen den führenden Ziffern der Zieladresse und der Bereichsadresse muß unberücksichtigt bleiben; das längste Präfix der gesamten Adresse sollte in der Level- 2-Datenbank gesucht werden, und das Paket über Level-2- Routing weitergeleitet werden.
Ebenso stimmen die führenden Ziffern der dritten Beispieladresse genau mit der Bereichsadresse überein. Hier muß ebenfalls die Übereinstimmung unberücksichtigt bleiben, da der verbleibende Ziffern-String zu lang sein würde, um als ein Level-1-ID-Teil plus ein SEL-Teil interpretiert zu werden. Das längste Präfix der gesamten Adresse sollte ebenfalls in der Level-2-Datenbank gesucht werden, und das Paket über Level-2-Routing weitergeleitet werden.
Wenn eine Suche der obigen drei Adressen in einer TRIE-Datenbank durchgeführt wird, ist es offensichtlich, daß sie alle den gleichen Weg folgen werden bis zu dem und über den Knoten in der Datenbank hinaus, der eine Übereinstimmung mit der Bereichsadresse entspricht. Wie oben erläutert wurde, ist es für die erste Adresse notwendig, einem unterschiedlichen Weg zu folgen, sobald eine Übereinstimmung mit der Bereichsadresse aufgetreten ist - an diesem Punkt sollte eine Abzweigung zu einem Subtrie gemacht werden, der eine logisch getrennte Datenbank ist, der alle Level-1-Adressen hält.
Um Abzweigungen von der Level-2-Datenbank in die Level-1- Datenbank zu ermöglichen, wird ein weiteren, 18ter Zeiger jedem TRIE-Knoten hinzugefügt. Um den 18ten oder "Level-1"- Zeiger zu verwenden, werden dem Grund-TRIE zwei zusätzliche Mechanismen hinzugefügt: (i) ein Zähler und ein Vergleicher in dem aktuell verbleibenden Längenregister (CRL 42 in Fig. 3), die angeben, daß es genau 14 verbleibende Halboktette des Suchobjekts gibt; und (ii) ein an jedem Knoten gespeichertes zusätzliches Flag-Bit, das nur an dem Knoten oder den Knoten in dem TRIE gesetzt wird, der/die nach einer genauen Übereinstimmung mit der Bereichsadresse erreicht wird/werden (d. h. die Bereichsadresse des Bereichs, in dem der Router residiert). Auf dieses Flag-Bit wird als das "Ebene-1-Übergang möglich"-Bit Bezug genommen.
Das CRL-Register 42 wird mit der Länge des gesamten Suchobjekts geladen (d. h. der Anzahl enthaltener Halboktetten), wenn es zuerst durch die Weiterleitungs-Maschine 14 der Holeinheit 30 präsentiert wird.
Obgleich kein Teil der Adresse per se, wird die Länge der Adresse in dem Paket-Header aufgenommen, wie in ISO 8348/AD2 spezifiziert ist. Das CRL-Register 42 wird jedesmal um Eins dekrementiert, wenn ein Halboktett von der Sucheinheit 40 verarbeitet wird.
Nur wenn das "Level-1-Übergang möglich"-Bit gesetzt ist und das CRL-Register angibt, daß es genau 14 verbleibende Halb- oktette gibt, wird der 18te Zeiger ausgewählt. Der Kinderknoten des 18ten Zeigers wird der Wurzelknoten der Level-1- Datenbank sein. Es sei bemerkt, daß das nächste Halboktett von dem Suchobjekt nicht bis nach dem Übergang in die Level- 1-Datenbank verbraucht (consumed) werden wird.
Wenn ein Übergang in die Level-1-Datenbank während einer Suche nach einer Netzwerkzieladresse beim Betrieb statt findet, dann ist das die Adresse enthaltende Paket für ein Endsystem innerhalb des Bereichs bestimmt, in dem der Router residiert. Wie oben erläutert wurde, muß eine genaue Übereinstimmung in der Level-1-Datenbank für den Level-1-ID- Teil der Zieladresse gefunden werden. Das bedeutet, daß irgendwelche vorhergehenden "beste Präfix"-Ergebnisse, die während des anfänglichen Durchlaufs der Level-2-Datenbank erfaßt wurden, irrelevant sind, sobald ein Übergang in die Level-1-Datenbank stattgefunden hat. Wenn keine genaue Übereinstimmung in der Level-1-Datenbank gefunden werden kann, muß das Paket als verworfen betrachtet werden, da seine Zieladresse nicht existiert. Von einer Suche in der Level-1- Datenbank zurückgegebene Ergebnisse müssen daher genauen Übereinstimmungen entsprechen; andernfalls sollte ein Null- Ergebnis zurückgegeben werden.
Mit Bezug auf Fig. 7 werden vier Knoten einer Teildatenbank dargestellt und als ein Beispiel des Voranschreitens einer Suche durch eine Datenbank gemäß der Erfindung verwendet. In dem Beispiel wurde eine Wegkomprimierung aber keine Zeigerkomprimierung verwendet.
Die Suche schreitet wie folgt voran. Eine Adressensuche kommt an dem Knoten 110-A an. Das Weg-String- und das IDI-Flag-Bit werden bei Ankunft geprüft. Da beide Flags nicht im Knoten 110-A gesetzt sind ("0"), erfordert der Knoten 110-A keine besondere Verarbeitung. Daher verwendet die Suche das nächste Halboktett, um das Zeiger-Array von Zeigern zu induzieren und schreitet zu einem Kinderknoten voran. In dem Beispiel weist das geholte Halboktett einen Wert von 7 auf, so daß die Sucheinheit 40 den Zeiger 7 verwendet, um sich zum Knoten 110-B zu bewegen.
Bei Ankunft am Knoten 110-B sieht die Sucheinheit 40, daß das Weg-String-Flag "0" ist, und somit weist der Knoten 110-B keine zugeordneten Wegziffern-Strings auf. Das "IDI"-Flag ist jedoch "1". Dies gibt an, daß der Knoten 110-B IDI- Information 130 enthält, die die Länge des IDI-Felds enthält. (Es kann daher angenommen werden, daß mit aller Wahrscheinlichkeit das Halboktett "7", das gerade verarbeitet wurde, die zweite AFI-Ziffer war.) Die Sucheinheit 40 stellt diese Information wieder her und lädt den Wert in das IDI-Längenregister. Dieses Register wird dann jedesmal um Eins dekrementiert, wenn ein Halboktett verarbeitet wird. Das nächste Halboktett (die erste Ziffer des IDI-Felds) wird geholt, und die Suche schreitet voran.
Bei der Beispielsuche spezifiziert der AFI für den Suchweg, daß die IDI-Füllziffern gleich dem Dezimalwert 0 sind. Um Füll-Bits zu ignorieren, zeigt der Zeiger im Knoten 110-B, der einem Halboktett-Wert von 0000 entspricht, auf den Knoten 110-B. Daher verläßt die Suche nicht den Knoten 110-B, solange wie IDI-Füllziffern verarbeitet werden und das IDI- Längenregister nicht auf Null dekrementiert ist. Die Suche verläßt den Knoten gewöhnlicherweise nur dann, nachdem eine Nicht-Füllziffer (Nicht-0000-Ziffer) analysiert (parsed) ist.
The Art of Computer Programming, Bd. 3, Seiten 490-498: "Sorting and Searching" beschreibt ein Verfahren eines Aufbauens eines binären Tries, das eine Einweg-Verzweigung vermeidet, indem in jedem Knoten eine Anzahl von zu überspringenden Bits aufgenommen wird, bevor der nächste Test durchgeführt wird.
Bei einem Weg, dem die Suche nachfolgend folgen könnte, würde sie am Knoten 110-D ankommen, dessen Weg-String-Flag gesetzt ist. Dies gibt an, daß der Knoten 110-D einen Wegziffern- String 125 enthält. Vor einer weiteren Verarbeitung am Knoten 110-D stellt die Sucheinheit den Wegziffern-String 125 wieder her und vergleicht die Elemente des Strings mit den der Sucheinheit nachfolgend präsentierten Halboktetten. Nur nachdem der gesamte Ziffern-String erfolgreich verglichen wurde, bearbeitet die Sucheinheit den Knoten 110-D weiter.
Während einer weiteren Verarbeitung entdeckt die Sucheinheit, daß das Ergebnisfeld den Wert xyz enthält, der angibt, daß die bis jetzt verarbeiteten Halboktette ein Präfix sind, das zugeordnete Routing-Information aufweist (das Präfix ist dem Ergebniswert xyz zugeordnet). Der Ergebniswert xyz wird von der Sucheinheit gespeichert. Wenn kein weiteres Ergebnis während der Suche angetroffen wird, dann wird der Wert xyz als das Suchergebnis zurückgegeben, der angibt, daß das zugeordnete Präfix das beste Präfix ist, das in der Datenbank für dieses besondere Suchargument gespeichert ist.
Nachfolgend entdeckt die Sucheinheit, daß das DSP-Flag gesetzt ist. Dieses gibt an, daß der Knoten 110-D einen 17ten Nicht-Null-Zeiger aufweist, der in die DSP-Domäne der Daten- bank zeigt. (Bei einer tatsächlichen Implementierung kann das DSP-Flag-Bit durch die Verwendung von Null- und Nicht-Null- DSP-Zeigern und nicht mit einem expliziten Bit implementiert werden). Wenn und nur wenn das IDI-Längenregister auf genau Null dekrementiert wurde, kann auf diesen siebzehnten Zeiger zugegriffen werden. Wenn dies der Fall ist, wird die Suche in der DSP-Domäne der Datenbank fortgesetzt. Wenn die IDI-Länge nicht auf Null dekrementiert wurde, wird das nächste Halboktett des Suchobjekts verwendet, um einen der ersten sechzehn Zeiger am Knoten 110-D auszuwählen.
Bei einem anderen Weg, dem die Suche folgen könnte, würde sie am Knoten 110-C ankommen. Am Knoten 110-C ist das Level-1- Flag gesetzt. Dies gibt an, daß die Halboktette des Sucharguments, die bis jetzt verarbeitet wurden, genau mit der Bereichsadresse des Bereichs in dem der Router residiert, übereinstimmen (d. h. der Router, in dem diese Datenbank enthalten ist). Wenn an diesem Punkt genau vierzehn Halboktette des Sucharguments verbleiben, dann wird das Suchargument als eine Adresse eines Endsystems innerhalb dieses DECnet-Bereichs betrachtet; demgemäß wird der achtzehnte Zeiger am Knoten 110-C ausgewählt und die Suche wird in dem Level-1-Subtrie wieder aufgenommen.
Somit enthält jeder Knoten mehrere Flags und mögliche Teile einer Information. Jeder Knoten kann (wo eine Zeigerkomprimierung verwendet wird) eine achtzehn-Bit-Zeiger-Bitmaske, 16 Zeiger auf nachfolgende Knoten (oder auf sich selbst), einen DSP-Zeiger, einen Level-1-Zeiger, eine Wegkomprimierungs- String sowie eine Angabe seiner Länge, Ergebnisinformation und IDI-Längeninformation enthalten.

Ausführliche Beschreibung

Eine spezifische Implementierung einer Sucheinheit wird hier beschrieben. Die Ausgestaltung wird durch den Wunsch vorangetrieben, eine minimale Anzahl von ohne weiteres verfügbaren Komponenten zu verwenden und die verbrauchte Leistung zu minimieren.
Der Wunsch, eine minimale Anzahl von ohne weiteres verfügbaren (handelsüblichen) Komponenten zu verwenden, muß hervorgehoben werden. Wir haben oben ein Minimieren der Verwendung eines Speichers durch die Techniken einer Wegkomprimierung und einer Zeigerkomprimierung beschrieben. Wenn diese Techniken von einem Implementierungsstandpunkt betrachtet werden, kann entschieden werden, daß eine Wegkomprimierung aber keine Zeigerkomprimierung implementiert werden sollte. Obgleich eine Zeigerkomprimierung eine Verringerung der Menge des erforderlichen Speichers ermöglicht, verlangt sie ferner, daß der Speicher in kleine Teile segmentiert wird, die durch einen Speicherverwaltungsprozeß verwaltet werden. Ein zusätzlicher Mehraufwand umfaßt eine Extra-Logik, um die Bit-Maske zu lesen und zu decodieren, mehrstufige Hardware-Addierer, um die signifikanten Bits der Maske zu akkumulieren und zusätzliche Addierer, um diese Akkumulierung dann auf die Adresse des Blocks des komprimierten Vektors zu addieren.
Dieser Mehraufwand erfordert nicht nur die Verwendung einer Extra-Steuerlogik, sondern verringert ebenfalls die potentielle Zykluszeit der Maschine, da sich die Extra-Logik im kritischen Weg jedes Zyklus befindet. Indem auf eine Zeigerkomprimierung verzichtet wird, wird die Steuerlogik sehr vereinfacht und die Zykluszeit verbessert. Die Hinzufügung von mehr Speicher erhöht nicht die Komponentenanzahl (component count), gegenüber dem, was sie sein würde, wenn die Zeigerkomprimierung wirksam wäre. Unterschiedliche Implementierungsanforderungen, insbesondere solche mit größeren Datenbanken, können dazu führen, daß eine Speicherverwendung eine höhere Berücksichtigung erfordert. Unter diesen unterschiedlichen Anforderungen kann eine Zeigerkomprimierung wirksam verwendet werden.
Die Erkennungsmaschine ist hier ausgestaltet, um in ein "Widget-2"-System hineinzupassen. Dieses System weist eine kleine Hauptplatine mit 3-Steckplätzen auf, wobei einer ihrer Steckplätze für eine Art einer Adressen-Erkennungsmaschine (ARE = address recognition engine) bestimmt ist. Der Hauptplatinenbus ist im wesentlichen derjenige eines Host- 68020-Motorola-Mikroprozessors, jedoch mit nur 24 und nicht 32 Adressenbits. Das Timing des Bus wurde bezüglich der CPU verlangsamt, um die Bus-Schnittstellenlogik zu vereinfachen. Es ist immer noch möglich, nicht mehr als zwei Wartezyklen (200 ns Zyklen) zu gewährleisten, wenn die CPU auf das ARE zugreift, wenn Performance-Anforderungen dies vorschreiben.
Um eine maximale Flexibilität zu erlauben, unterstützt die Implementierung acht unterschiedliche Wurzelknoten für anfängliche Suchen. Der eigentliche Wurzelknoten kann zum Suchen unterschiedlicher Adressenformaten oder zum Durchführen verschiedener Arten allgemeiner Suchvorgänge ausgewählt werden.

Zentrale Komponenten

Mit Bezug auf Fig. 3 gibt es vier Grundkomponenten, die den Speicher 50 der Erkennungsmaschine 20 implementieren, und eine Anzahl von Registern und elementaren Zustandsmaschinen, die gleichzeitig wirksam sind (zusammen als die Suchmaschine 40 bekannt). Die vier zentralen Speicherkomponenten werden nachstehend beschrieben.

DRAM-Zeigerspeicher

Der Kern der Erkennungsmaschine 20 besteht aus dem Knoten- Zeigerspeichern und der "aktueller Knoten + aktueller Zifferzeiger -> nächster Knoten"-Sucheinheit 40. Mit Bezug auf Fig. 8 werden die Zeigerspeicher durch ein Array von DRAM- Speichern 200 implementiert, die durch eine kleine Menge von Steuerlogik unterstützt werden. Ein 16-Bit-Zustandsvektor (d. h. die durch die Leitungen 202 beförderte Knotenadresse) und eine 4-Bit-Ziffer (durch Leitungen 204 befördert) erfordert einen DRAM-Speicher 200, der als 1M · 16 (20 Bit · 16 Bit) organisiert ist, und erlaubt, daß 64K Zustände (oder Knoten) implementiert werden können. Dies ermöglicht, daß mindestens 32 K-Adressen erkannt werden können; wobei tatsächlich festgestellt wird, daß es 32K Null-Knoten (mit keinen "nächsten Zustand" Kinderknoten) und 32K Nicht-Terminal- Knoten mit nächsten Zuständen gibt, wobei dann nur halb soviel physischer Speicher erforderlich ist, d. h. nur ein Megabyte (als 512K · 16 organisiert). Ein DRAM-Array 200 dieser Größe erfordert nur acht (256K · 4) Chips, oder bei einer Vorausschau in der Speichertechnologie) nur vier (1M x 4) Chips.
Das Grund-Maschinenzyklen-DRAM-Array 200 weist die höchstmögliche Geschwindigkeit auf, und diese Geschwindigkeit diktiert weitgehend die Suchzeit für irgendeine gegebene Adresse (wenn angenommen wird, daß es genug Zeit gibt, um die DRAM-Adresse für den nächsten Zyklus zu erzeugen, nachdem die Daten für den aktuellen Zyklus gültig wurden; dies kann ohne weiteres verwaltet werden, da die nächste DRAM-Adresse im wesentlichen eine Verkettung der 16-Bit-Zeiger-Daten mit der 4-Bit-Ziffer ist).
Ein Knoten wird so durch eine 16-Bit-Adresse definierter, die auf Leitungen 202 befördert wird. Wenn das höchstwertige Bit der Adresse gleich Null ist, ist der Knoten (bei dieser Implementierung) als abschließend definiert (mit keinen Nächste-Knoten-Zeigern), sonst ist er nicht abschließend (d. h. weist Nächste-Knoten-Zeiger auf).

Schneller statischer RAM

Alle 64K-Knoten müssen die Extra-Information (zusätzlich zu den Zeigern auf nächste Knoten bereitstellen), auf die früher hingewiesen wurde. Um diese Information zu liefern, wird auf einen schnellen 64K · 16 statischen RAM 210 gleichzeitig mit dem DRAM-Zeiger-Array 200 zugegriffen. Das statische RAM liefert die folgende Information über den aktuellen Knoten:
- NIL-Flag: gesetzt, wenn der Knoten NIL ist (und die Verarbeitung anhalten sollte);
- Weg-String: wenn ein Weg-String an dem Knoten gespeichert ist, ist eine Nicht-Null-Länge im SRAM gespeichert;
- Ergebnis-Flag: gesetzt, wenn der Knoten einen neuen Ergebniswert enthält;
- IDI-Flag: gesetzt, wenn AFI durchgeführt ist (und der Knoten die IDI-Länge enthält);
- Level-1-Flag: Level-1-Übergang möglich (DECnet-Bereich wird an diesem Knoten erkannt).
Die Abbildung dieser Information wird später unter der Überschrift "Speicherabbildung" ausführlicher beschrieben.

Wegziffern-String-Speicher

Auf den Wegziffern-String-Speicher 220 wird gleichzeitig mit dem DRAM-Zeiger-Array 200 zugegriffen. String-Speicherplatz wird jedem der 64K Knoten zugeordnet. Die Anzahl an jedem Knoten gespeicherter Ziffern wird durch das String-Längen- Feld angegeben, das in dem schnellen statischen RAM 210 gespeichert ist. Die maximale Anzahl von Ziffern, die an einem Knoten gespeichert werden können, wird durch die Adresse des Knotens bestimmt. Es gibt drei unterschiedlich Maxima: 48 Ziffern, 16 Ziffern oder null Ziffern. Die Knotenadresse auf Leitungen 202 bestimmt, welches Maximum wirksam ist; die Zuordnung ist teilweise fest verdrahtet und teilweise logisch programmierbar und ausgestaltet, um die Menge von physischem Speicher zu minimieren.
Die Implementierung unterstützt 48 Ziffern von Speicher bei 4K Knoten und 16 Ziffern von Speicher bei 52K Knoten. 8K Knoten weisen keinen String-Speicherplatz auf. Der gesamte erforderliche Speicher beträgt 1M Ziffern, der aus 512K Oktetten oder vier (1M · 1) Chips besteht. Bei der nächsten Generation von 4MBit DRAMs ist wieder nur ein Chip erforderlich.
Gemäß der Erfindung werden Techniken verwendet, um die Knotenadresse (16 Bit) und den Wert des String-Ziffern- Zählers (6 Bit) auf die 1M*4 DRAM-Adressenleitung (20 Bit) abzubilden. Tatsächlich ändert sich die Abbildung als eine Funktion der Knotenadressenleitungen. Dies wird ebenfalls weiter ausführlicher in dem nachstehenden Abschnitt mit dem Titel "Speicherabbildung" beschrieben.

DSP-Zeigerspeicher

Auf dem DSP-Zeigerspeicher 230 wird ebenfalls gleichzeitig mit dem DRAM-Zeiger-Array 200 zugegriffen. Nur 32K der Knoten, bekannt als "Übergangsknoten" (wobei die Knotenadresse MSB gleich eins ist) können auf diesen Speicher zugreifen. Folglich ist die DSP-Speicheranforderung 32K · 16, was nur zwei Chips entspricht. Der DSP-Zeiger, auf den an einem Knoten zugegriffen wird, wird nur verwendet, wenn das Ende des IDP erkannt wird; d. h. nach einer IDI-Suche, wenn der CRL-Zähler auf Null dekrementiert ist.

Steuerlogik

Zentraler Komponente der Steuerlogik für die ARE werden nachstehend beschrieben:
Der Timing-Generator (nicht gezeigt) ist für das richtige Sequenzieren der Speicher-Arrays verantwortlich; z. B. RAS- und CAS-Steuerung, Refresh-Timing, Zyklus-zu-Zyklus- Steuerung, etc.
Die Holeinheit 280, 290 ist für das Liefern von Halboktetten der Adresse an die Sucheinheit auf einer Nachfragebasis verantwortlich. Die Halboktette werden in der Reihenfolge von der Suchadresse extrahiert, wie sie (in diesem Fall) durch die Host-CPU an eine Registerdatei 270 geliefert werden. Die Halboktette werden der Suchmaschine präsentiert und mit deren Timing-Generator synchronisiert. Eine Verriegelung ist vorgesehen, daß, wenn die Suchmaschine ein Halboktett erfordert, den die Host-CPU noch nicht geliefert hat, dann die Suchmaschine angehalten wird, bis das Halboktett verfügbar ist.
Es gibt drei Ziffern-Zähler, die in der Lage sind, gleichzeitig betrieben zu werden:
Der aktuell verbleibende Längenzähler (CRL) 240 wird mit der Halboktettlänge des gesamten Sucharguments geladen, wenn sie zuerst durch die CPU der Erkennungsmaschine präsentiert wird. Der Zähler wird um eins dekrementiert, jedesmal wenn eine Ziffer durch die Suchmaschine verbraucht (verarbeitet) wird.
Wenn der Zählwert Null erreicht, ist er eine Angabe, daß die Suche enden muß.
Der CRL-Zähler 240 liefert ferner ein Signal auf Leitung 310 an den Zykluscontroller (nicht gezeigt, siehe nachstehende Beschreibung unter Zykluscontroller), daß genau vierzehn Ziffern des Sucharguments für den Zweck eines Durchführens eines Level-1-Übergangs übrig bleiben.
Der Verbleibende-IDI-Längenzähler (IDIL-Zähler) 250 wird mit der Länge des IDI geladen, die durch den AFI-Wert diktiert wird (wie in der DECNET-Phase-V-Routing-Spezifikation). Das Laden findet unter dem Befehl eines an einem Knoten gesetzten Steuerbits statt (dem der zweiten AFI-Ziffer direkt folgenden Knoten). Dieser Zähler wird ebenfalls um eins dekrementiert, jedesmal wenn eine Ziffer von der Suchmaschine verbraucht (consumed) wird; wenn der Zählwert Null erreicht, dann muß der nächste Maschinenzyklus ein DSP-Übergangszyklus sein. Der Wert des IDIL-Zählers wird jedesmal auf -64 zurückgesetzt, wenn eine neue Suche beginnt. Der Wert -64 gibt "Länge nicht geladen" an.
Es sei bemerkt, daß die ARE verwendet werden kann, um beliebige Wörter in einer beliebigen Datenbank zu suchen; es ist nicht notwendig, den IDIL-Zähler zu laden (wenn er nicht geladen ist, dann kann und wird ein DSP-Übergang nicht durchgeführt werden).
Der String-Ziffern-Zähler 260 wird jedesmal beim Eintreten in irgendeinen Knoten zurückgesetzt. Der Zähler wird am Ende jedes Maschinenzyklus, der ein String-Ziffern-Vergleichszyklus ist, inkrementiert; somit wird dieser Zähler auf Null zurückgesetzt verbleiben, bis ein Knoten erreicht wird, bei dem ein konstanter String gespeichert ist. Wenn ein String einer Länge von N Ziffern an einem Knoten gespeichert ist, dann wird der String-Ziffern-Zähler von dem Wert 0 bis N -1 inkrementieren, wenn N String-Ziffern-Vergleichszyklen stattfinden (unter der Annahme, daß die Vergleiche erfolgreich sind). Wenn der String-Ziffern-Zähler den Wert N erreicht, finden keine weiteren Vergleiche statt; der Zähler wird im nächsten Maschinenzyklus auf Null zurückgesetzt.
Der Zykluscontroller (nicht gezeigt) kann als die zentrale Intelligenz der Suchmaschine angesehen werden. Er sieht Statusinformation über den aktuelle Maschinenzyklus und Steuerinformation von dem Knotensteuerwort am Bus 330. Der Zykluscontroller entscheidet, wie der gegenwärtige Zyklus fortzusetzen ist (d. h. ob eine String-Ziffer zu vergleichen, ein Zeiger für einen weiteren Zyklus auszuwählen, oder anzuhalten ist); ob ein weiterer Maschinenzyklus zu starten ist, und falls ja, ob eine neue Ziffern- und/oder eine neue Knotenadresse zu verwenden ist. Der Zykluscontroller erzeugt ebenfalls Signale an verschiedene Register und Zähler.
Die Statusregister 245, 148 werden verwendet, um die Knotenadresse des zuletzt durchlaufenden Präfix zu speichern (d. h. das beste Präfix bis jetzt), und um nützliche vergangene Historie zu speichern; insbesondere, ob DSP- und/oder Level- 1-Übergänge stattgefunden haben, ob das "beste Präfix bis jetzt" jemals geladen wurde, ob das Verbleibende-IDI-Längenregister 250 geladen wurde.
Host-CPU-Zugriffs-Transceiver 252, 254, 256, 258, 262 erlauben es der Host-CPU, auf die internen Speicher der ARE für Wartungszwecke zuzugreifen. Der von der Suchmaschine verwendete gleichzeitige Betrieb wird für diese Zwecke gesperrt; die Speicher erscheinen zusammen an der Host-CPU als eine einzige Datenbank mit einer "programmierfreundlichen"-Struktur und Adressenabbildung. Bei dieser Struktur erscheinen alle einem bestimmten Trie-Knoten zugeordneten Daten innerhalb einer gleichförmig organisierten Datenstruktur.

Funktionelle Schnittstellen zu der ARE

Es gibt drei grundlegende funktionelle Schnittstellen zu der ARE. Diese sind:
1. Suchschnittstelle - Paketweiterleitung;
2. Suchschnittstelle - Wartung;
3. Wartungsschnittstelle.
Die erste dieser ist unkompliziert, sie kann als den primären Grund zum Aufbauen einer ARE betrachtet werden. In diesem Modus werden Weiterleitungs-Adressen (und/oder andere Adressen, z. B. Datalink-Adressen), die aus den das Netzwerk durchlaufenden Paketen extrahiert wurden, an die ARE geliefert. Die ARE führt ein Nachschlagen der Adressen durch und gibt Weiterleitungs-Information an eine Weiterleitungs-Maschine zurück (in diesem Fall ist die Weiterleitungs-Maschine die Host-CPU).
Die zweiten und dritten Funktionen betreffen beide die Wartung. Die Suchschnittstelle für Wartung ist der Suchschnittstelle zum Paketweiterleiten sehr ähnlich. In diesem Fall sind jedoch die der ARE präsentierten Adressen nicht notwendigerweise vollständige Adressen. Typischerweise werden Adressenfragmente geliefert, um zu bestimmen, welche Strukturänderungen an der Datenbank erforderlich sind, um Einträge hinzuzufügen, zu löschen oder zu modifizieren. Eine geringfügige Modifikation des Betriebsverhaltens der ARE wird für Wartungssuchen verwendet, um mit den subtilen Unterschieden der Adressensemantik fertig zu werden.
Die Wartungsschnittstelle beinhaltet kein Suchen; tatsächlich wird die Suchmaschine in diesem Modus am Betrieb gehindert. Die Adressen-, Daten- und Steuerwege innerhalb der ARE werden vollständig neu strukturiert, so daß die internen Speicher der ARE der Host-CPU sichtbar gemacht werden. Auf jede Speicherkomponente der ARE wird dann durch Decodieren der CPU- Adressenleitungen und nicht durch eine Suchmaschine zugegriffen.
Die CPU-Schnittstelle an die ARE zwecks Durchführen einer Suche ist funktional die gleiche, ob die Suche zwecks Weiterleiten eines Pakets oder eines Prüfens der Datenbank ist. Die Schnittstelle wird durch eine direkte Speicherabgebildete Steuer-, Status- und Datenregister unterstützt. Die Steuerregister ermöglichen, den Betriebsmodus der ARE zu steuern, wohingegen die Statusregister ermöglichen, den Betrieb der ARE zu überwachen. Die Datenregister liefern ein Mittel zum Präsentieren einer Adresse an die ARE und zum Lesen eines Suchergebnisses.
Die Steuerregister sehen Steuerung des folgenden vor:
1. Suchmodus oder Wartungsmodus auswählen;
2. Adressenformatmodus auswählen (Einflüsse der Interpretation von Ergebnissen);
3. Sperren von Level-1-Übergängen (für Wartungssuchen);
4. Sperren von IDP- zu DSP-Übergängen (Wartungssuchen);
5. Zyklisches Abfragen oder Verzögern Auswählen, bis das Suchergebnis vollständig ist;
6. Paritätsschutz der ARE-Speicher steuern.
Die Statusregister erlauben, das folgende zu überwachen:
1. Zustand der Suchmaschine (rückgesetzt, suchend, angehalten);
2. Zustand der Adresseneingabe an die Suchmaschine.
Die Datenregister sind in acht Blöcke unterteilt. Jeder Block entspricht einer Suchinitiierung an einem der acht Wurzelknoten, wobei jedoch die Blöcke sonst funktional identisch sind. (Einige der acht Wurzelknoten können mit Datenbanken beginnen, die für unterschiedliche Arten von Suchen verwendet werden, andere können beispielsweise dem Anfang von Level-1-Zweigen einer Adressensuch-Datenbank entsprechen.) Ein Registerblock weist eine Größe von 64 Bytes auf; wobei die zweiten 32 Bytes ein Alias der ersten 32 Bytes sind (d. h. Verwenden des gleichen physischen Speichers). Von den 32 physischen Bytes in einem Block können bis zu 24 Bytes verwendet werden, um eine zu suchende Adresse an die ARE zu schreiben. Das erste Byte muß eine Längenangabe der Gesamtlänge der zu liefernden Adresse sein. (Es sei bemerkt, daß dieses Format eine direkte Extrahierung aus ISO8338/AD2-Paketen erlaubt, die das Netzwerk durchlaufen.) Die Wahl, in welchen Alias die Adresse einzuschreiben ist, bestimmt, ob das Längenbyte als die Länge der Adresse, die in Oktetten oder in Halboktetten gemessen wird, interpretiert wird. Eine Oktettlänge ermöglicht eine direkte Extrahierung aus einem ISO 8348/AD2; eine Halboktettlänge erlaubt, nach willkürlichen Längen-Präfixen zu suchen, was besonders bei Wartungssuchen nützlich ist. Die maximale Längenadresse, nach der gesucht werden kann (bei der aktuellen Implementierung), beträgt 22 Oktette oder 46 Halboktette.
Der Suchvorgang wird beginnen, sobald die ersten vier Oktette der Suchadresse geschrieben sind. Ein Sperrmechanismus hindert die Suchmaschine daran, die Oktetten 5 bis 8 zu verwenden, bis diese ebenfalls durch die CPU geschrieben wurden. Ebenso wird die Sperre für die verbleibenden Oktette in Gruppen von vier vorgesehen. Es sei bemerkt, daß vier Oktette bei einem Schreibvorgang geschrieben werden können, da die ARE eine 32-Bit-Datenschnittstelle aufweist. Es sei ebenfalls bemerkt, daß die Suchadresse, einschließlich des Längenbytes, notfalls mit willkürlichen Daten aufgefüllt werden muß, um ein Vielfaches von vier Oktetten der Gesamtlänge zu sein.
Das Suchergebnis wird durch die Suchmaschine in den gleichen Block geschrieben, in den die Suchadresse durch die CPU geschrieben wurde. Der Status der Suchmaschine kann durch die CPU (unter Verwendung der Statusregister 248) überwacht werden, um zu bestimmen, wenn das Suchergebnis gültig ist; oder eine Sperre kann alternativ freigegeben werden, so daß die CPU angehalten wird, wenn das Ergebnis gelesen wird, bis das Ergebnis gültig ist.
Das Suchergebnis ist eine Gruppe von 8 Bytes. Die Gruppe wird in die folgenden Felder unterteilt:
1. Zusammenfassung (1 Byte);
2. Ergebnis-bis jetzt (2 Bytes);
3. Soweit-gekommen (2 Bytes);
4. Interne Zählwerte (3 Bytes)
Das Zusammenfassungs-Byte liefert eine schnelle Erfassung eines Erfolgs oder eines Mißerfolgs einer Suche. Im Fall eines Sucherfolgs liefert im Paket-Weiterleitungs-Modus das Ergebnis-bis jetzt einen Index an eine entfernte Tabelle (d. h. extern zu der Erfassungsmaschine), die alle notwendige Information zur Weiterleitung liefert. Im Fall eines Mißerfolgs bei der Suche, insbesondere bei Wartungssuchen, gibt die Zusammenfassung den Grund für den Mißerfolg an. Die anderen Felder liefern eine hinreichende Information, um es der ARE-Datenbank zu erlauben, ohne weiteres und schnell durch die CPU aktualisiert zu werden, falls dies gewünscht ist. Weitere Einzelheiten dieser Register und ihre Interpretation wird im Anhang B geliefert.
Die CPU kann die Suchmaschine in einen "Wartungs"-Modus (und nicht in einen "Such"-Modus) setzen, indem ein Bit in das Steuerregister geschrieben wird.
Im Wartungsmodus arbeitet die Suchmaschine nicht, und jeder vorher erfaßte Status (mit Ausnahme der Datenbank) ist verloren. In diesem Modus wird der gesamte interne Speicher der ARE in einen Teil des CPU-Adressenraums abgebildet. Auf diesen Teil des Adressenraums ist kein Zugriff möglich, es sei denn, daß die Suchmaschine im Wartungsmodus ist. (Dies vereinfacht eine Arbitrierung für die internen Speicher und Busse sehr und ist konsistent mit dem Ziel einer minimalen Komponentenanzahl (parts count).)

Speicherabbildung (Memory Map)

Die Abbildung ist in 64K aufeinanderfolgenden Knoten organisiert; jeder Knoten weist eine Größe von 256 Oktette auf. Somit beträgt der gesamte virtuelle Raum, der durch die Speicher aufgespannt wird, 16 MByte. Die Speicherabbildung jedes Knotens ist in Fig. 9 dargestellt; die physischen Speicherteile, die verschiedene Fragmente bilden, sind in Klammern dargestellt.
Bei diesem Speicherabbildungsschema wird eine Ressource innerhalb eines Knotens N, die ein Offset (wie in Fig. 9 gezeigt ist) von m aufweist, mit der von der CPU gelieferten Adresse adressiert:
N*2^8+m; d. h. die Verkettung von N gefolgt von m.
Einige harte Regeln werden bei dem Abbildungsschema von Fig. 9 durchgesetzt. Die Regeln sind:
1. Alle Knoten mit einer Adresse geringer als 8000 hex sind Terminal-Knoten. Eine Wegziffern-String kann an einigen Terminal-Knoten gespeichert werden, wobei jedoch ein Übergang zu einem anderen Knoten an irgendeinem Terminal-Knoten strengstens verboten ist.
2. Es gibt 4K Knoten mit einer Vorkehrung mit bis zu 28 Halboktetten einer Wegziffern-Stringspeicherung. Die Hälfte dieser Knoten sind Terminal-Knoten (Knoten 7800 - 7fffhex) und die andere Hälfte sind Übergangsknoten (Knoten f800 - ffff hex). Diese Knoten sind primär zum Speichern von Level- 2-Einträgen in der Datenbank vorgesehen.
3. Es gibt 52K Knoten mit einer Vorkehrung mit bis zu 16 Halboktetten einer Wegziffern-Stringspeicherung. Die Hälfte dieser Knoten sind Terminal-Knoten (Knoten 1000 - 77ff hex) und die andere Hälfte sind Übergangsknoten (Knoten 9000 - f7ff hex). Diese Knoten sind zum Speichern von Level-1- Einträgen, Datalink-Adressen und weiteren Entitäten einer Gesamtlänge, die in der Datenbank 16 Halboktette nicht überschreitet.
4. Es gibt 8K Knoten mit keiner Vorkehrung für eine Wegziffern-Stringspeicherung; dies ist eine Konsequenz eines Aufgebens einer Speicherung für 16 Halboktetten und Zuordnen des Speichers zu den 4K Knoten mit einer 48 Halboktetten- Speicherung. Diese Knoten können jedoch beispielsweise für diejenigen Knoten verwendet werden, bei denen ein IDP- Zählwert innerhalb eines Knotens lokalisiert ist (und eine String-Speicherung somit nicht erlaubt ist) oder für irgendeinen Knoten, bei denen ein konstanter String nicht vorhanden ist.
5. Es gibt nur einen Level-1-Zeiger. Auf ihn kann auf allen Übergangsknoten zugegriffen werden. Der Zeiger sollte gesetzt sein, um auf die Wurzel des Level-1-Zweigs der Datenbank zu zeigen.

Theorie einer ARE-Betriebsweise

Die grundlegende Theorie eines Betriebs für eine Suche gemäß der Erfindung wird hier beschrieben. Es sei angenommen, daß die CPU eine gültige Datenbank-Trie-Struktur aufgebaut hat, bevor der Suchvorgang beginnt.
Mit Bezug auf Fig. 8 wird eine Registerdatei 270 verwendet, um den notwendigen Speicher zum Halten der Suchadresse, die die CPU an die ARE liefert, und zum Halten des Ergebnisses, das an die CPU zurückzugeben ist, vorzusehen. Die Registerdatei 270 weist duale Ports auf, wobei ein gleichzeitiger Zugriff von der ARE und der CPU ermöglicht wird. Dies verbessert die Performanz und macht den Bedarf an einer Arbitrierungssteuerlogik überflüssig.
Ein Suchvorgang wird initiiert, wenn die CPU das Suchargument in die Registerdatei 270 schreibt. Wenn die CPU insbesondere auf das dritte Oktett eines Langwort-Eintrags schreibt (dies wird gewöhnlich gleichzeitig mit dem Schreiben des ganzen Langworts sein), wird eine Hardware-Flag gesetzt, das angibt, daß das zugeordnete Langwort gültige Daten enthält. Zur gleichen Zeit erinnert man sich, daß der gewählte Block zwecks Beginnen der Suche an dem richtigen Wurzelknoten ausgewählt wurde; und man erinnert sich an den innerhalb des Blocks verwendeten Alias, so daß das erste Oktett als ein Oktett- oder eine Halboktettlänge richtig interpretiert werden kann.
Es gibt sechs "Bereit"-Flags, eine für jedes der ersten sechs Langwörter in einem Block. Die Flags werden auf eine von zwei Wegen gelöscht: Entweder werden sie von der CPU explizit gelöscht, indem ein Wartungsmodusbefehl ausgegeben wird (und durch nachfolgendes Rückgeben des Modus an den Suchmodus); oder die CPU überschreibt das Suchargument mit einem neuen Suchargument. Ein Überschreiben des ersten Langworts wird ein ARE-Systemrücksetzen erzeugen, wobei jedoch das erste Langwort "Bereit"-Flag gesetzt bleibt. Das letztere Verfahren ermöglicht es, mehrere Suchen mit geringem oder keinem Steuermehraufwand durchzuführen.
Die Steuerlogik 290 um die Registerdatei 270 prüft die Flags und leitet die Langwörter (wenn sie bereit sind, d. h. gültig sind) an einen Multiplexer 280 weiter, der in ein Paar von programmierbaren Logikarrays eingebaut ist. Die Ausgabe des Multiplexers 280 speist Halboktette von Daten an die Suchmaschine auf dem Bus 204 und erzeugt eine "Daten bereit"- Anzeige. Wenn "Daten bereit" verzögert wird (da die CPU die Datei nicht so schnell füllen kann, wie die Suchmaschine diese leeren kann), wird dann die Suchmaschine ebenfalls verzögert. Die Registerdatei-Steuerlogik 290 sucht nach einem "nächste Ziffer"-Signal auf der Leitung 282 von der Suchmaschine, woraufhin sie das nächste Halboktett auf den Ausgabebus des Multiplexers 280 treiben wird. Eine Synchronisierung der "Bereit"-Flags tritt parallel mit der Serialisierung jedes Langworts in acht Halboktette auf; diese Pipelining-Technik ermöglicht es, daß der Mehraufwand eine Synchronisierung wieder vollständig wettgemacht werden kann.
Das erste Oktett in einem Registerdateiblock (d. h. das Oktett mit der niedrigsten Adresse) wird an das CRL-Register 240 weitergeleitet. Wenn die Länge als eine Oktettlänge zu interpretieren ist (und nicht als eine Halboktettlänge), dann wird ihr Wert verdoppelt, so daß das CRL-Register 240 immer einen Halboktett-Zählwert hält. Das zweite und alle nachfolgende Oktett(e) werden an den Halboktetten-Multiplexer 280 weitergeleitet. Für jedes das in den Multiplexer 280 eintretende Oktett werden die höchstwertigen vier Bits zuerst ausgegeben, gefolgt von den niederstwertigen vier Bits. Wenn jedes Halboktett auf dem Halboktett-Bus 204 gültig ist, signalisiert die Steuerlogik 290 "bereit" auf der Leitung 292. Falls und wenn das Nächste-Ziffer-Signal auf der Leitung 282 anliegt, wird das CRL-Register 240 um eins dekrementiert und ein Halboktett verbraucht (consumed). Nachdem alle Halboktette auf den Halboktett-Datenbus (Leitungen 204) ausgegeben wurden, wird die Halboktett-Generatorlogik immer noch "bereit" auf der Leitung 292 an die Suchmaschine ausgeben, obgleich es keine Halboktette mehr gibt. Wenn "nächste Ziffer" auf der Leitung 282 an die Steuerlogik 290 angelegt wird, werden nicht definierte Daten auf die Halboktett-Datenleitungen 204 getrieben. Auf der Leitung 284 werden die Daten jedoch mit einer Angabe, daß die "verbleibende Länge Null ist" (RLEQ0) qualifiziert.
Sobald "Daten bereit" für das erste Halboktett auf dem Halboktett-Datenbus 204 angegeben wird, startet der erste Maschinenzyklus. Der Zyklus startet, indem eine gültige Ziffer auf den Halboktett-Datenbus 204 und eine gültige Knotenadresse auf den Knotenadressenbus 204 getrieben wird. Die für den ersten Maschinenzyklus verwendete Knotenadresse (d. h. die Wurzelknotenadresse) wird einer der ersten acht Werte 8000 bis 8007 (hexadezimal) sein, der dadurch bestimmt wird, welcher der Blöcke 0 bis 7 mit der Suchadresse geladen wurde.
Ein Maschinenzyklus ist (in der Zeit) gleich einem DRAM- Zyklus. Die Master-Kristall-Oszillatorfrequenz wird ausgewählt, um die Zykluszeit zu minimieren, aber auch um einen richtigen DRAM-Betrieb unter Bedingungen des schlimmsten Falls zu garantieren. Diese Zeit beträgt etwa 208 Nanosekunden pro Maschinenzyklus.
Ein Maschinenzyklus eines allgemeinen Falls wird betrachtet. Dieser allgemeine Fall umfaßt den allerersten Maschinenzyklus. Maschinenzyklen werden aufeinanderfolgend ohne Verzögerung ausgeführt, es sei denn, daß es eine Verzögerung beim Erhalten der nächsten Ziffer gibt (dadurch gegeben, daß "Daten bereit" negiert wird), die durch ein unverhältnismäßig langsames Laden der Registerdatei verursacht wird. Etwa alle 15 Mikrosekunden wird ein Maschinenzyklus der Aufgabe eines Auffrischens der DRAM-Arrays gewidmet; während dieser Auffrischzyklen wird kein Suchfortschritt erreicht.
Am Anfang des Maschinenzyklus wird die aktuelle Knotenadresse auf den Knotenadressenbus und die aktuelle Suchadressenziffer auf den Zifferdatenbus getrieben. Ein gleichzeitiger Zugriff wird auf die folgenden Speicher durchgeführt:
1. Ein Nächster-Knoten-Zeiger wird von dem Zeiger-DRAM-Array 200 geholt;
2. Ein DSP-Zeiger wird von den statischen DSP-Zeiger-RAMs 230 geholt.
3. Eine Nächste-Stringziffer wird von dem Wegziffern-String- DRAM-Array 220 geholt.
4. String-/IDI-Längen- und Steuerbits werden von den schnellen statischen RAMs 210 geholt.
Der Nächste-Knoten-Zeiger und der DSP-Zeiger konkurrieren um den Knotendatenbus 206, so wie es auch das Level-1-Zeiger- 3 datenregister 340 tut. Die Steuerlogik wird entscheiden, welcher Konkurrent auf dem Bus freigegeben wird (siehe nachstehend).
Die nächste Stringziffer wird auf dem Bus 208 freigegeben und mit der aktuellen Suchziffer auf dem Bus 204 verglichen (sogar dann, wenn es keine Stringziffer gibt). Der Vergleich wird durch den Komparator 300 durchgeführt. Der auf der Leitung 302 durch das "Zifferübereinstimmungs"-Signal angegebene Vergleichsstatus wird der Steuerlogik verfügbar gemacht.
Die aus den schnellen statischen RAMs geholte Steuerinformation ist relativ früh, nach etwa 60 Nanosekunden im Maschinenzyklus verfügbar. Zu dieser Zeit ist zusätzliche Statusinformation aus den Register- und Steuerschaltungen innerhalb der Suchmaschine verfügbar. Dieser zusätzliche Status umfaßt:
1. CRL = 14 (Leitung 310): 14 Halboktette verbleiben, Level-1-Übergang möglich.
2. CRL = 0 (Leitung 284): letzte Ziffer wurde verwendet.
3. IDIL = 0 (Leitung 312): IIDIL wurde dekrementiert auf oder wird mit Null geladen.
4. "IDI geladen" (Leitung 314): verhindert ein IDI-Neuladen an einem Füllziffer-Schleifenknoten.
5. "String erschöpft" (Leitung 316): gibt an, daß der Wert in dem Stringziffernzähler 260 gleich dem "String-Längen"-Feld aus dem schnellen statischen RAM ist (auf dem Bus 320 befördert) - beide Werte sind Null, wenn kein String gespeichert ist.
Das Setzen der obigen Statusbits zusammen mit der auf dem Bus 330 beförderten Knotensteuerinformation von den schnellen statischen RAMs bestimmt, was sich in der zweiten Hälfte dieses Maschinenzyklus ereignen wird. Grundlegend wird der Maschinenzyklus einer der folgenden vier Arten sein:
1. Stringziffer-Vergleichszyklus (String-Zyklus);
2. Level-1-Übergangszyklus (Level-1-Zyklus);
3. IDP auf DSP Übergangszyklus (DSP-Zyklus);
4. Normaler Nächster-Knoten-Zeigerzyklus (Zeigerzyklus). Die Arten 2, 3 und 4 können zusammen als ein "normaler Zyklus" bezeichnet werden; es gibt nichts Anormales im Verlauf eines "String-Zyklus", ausgenommen, daß die Suchmaschine nicht auf einen neuen Knoten voranschreitet.
In der folgenden Beschreibung wird in sequentieller Form angegeben, wie die Zyklusart entschieden wird; die Suchmaschine führt jedoch alle diese Entscheidungen gleichzeitig aus:
Wenn eine "Lade IDI-Länge" (ein Knotensteuerbit auf dem Bus 330) anliegt und "IDI geladen" (auf Leitung 314) falsch ist, dann wird die IDI-Länge in dieses Register geladen und "IDI geladen" angelegt. "IDI-Länge = 0" (auf Leitung 312) wird immer dann angelegt, wenn die Inhalte der Register Null sind und "IDI geladen" angelegt ist.
Wenn "Lade IDI-Länge" negiert wird, kann ein Stringvergleich verlangt werden. Wenn "String erschöpft" (auf Leitung 316) anliegt, ist dies ein "normaler Zyklus"; ansonsten wird dieser Maschinenzyklus ein Wegstringziffern-Vergleichszyklus sein. Im letzteren Fall werden die Nächste-Ziffer- und DSP- Zeiger ignoriert. Die Maschine wartet, bis die "Ziffernübereinstimmung"-Flag (auf Leitung 302) gültig ist (nach etwa 180 Nanosekunden) und dann, wenn sie negiert ist, wird eine String-Fehlübereinstimmung erklärt und die Maschine hält an. Wenn "Ziffernübereinstimmung" angelegt ist, dann wird "nächste Ziffer" (auf Leitung 282) von dem Halboktett- Generator angefordert; das String-Zählregister 260 wird inkrementiert; das IDI-Längenregister 250 und das CRL- Register 240 werden dekrementiert. Die Maschine beendet den aktuellen Zyklus und startet den nächsten Zyklus, ohne den Wert am Knotenadressenbus 202 zu ändern.
String-Vergleichszyklen werden kontinuierlich stattfinden, bis es eine Ziffernfehlübereinstimmung gibt oder bis "String erschöpft" auf Leitung 316 anliegt, was angibt, daß alle Ziffern erfolgreich auf Übereinstimmung überprüft wurden, oder bis "CRL = 0" auf Leitung 284 durch den CRL-Zähler 240 angelegt wird (was ebenfalls als eine Fehlübereinstimmung betrachtet wird). Wann immer "String erschöpft" auf Leitung 316 anliegt, wird das String-Zählregister 260 in dem nächsten Maschinenzyklus auf Null zurückgesetzt (sogar dann, wenn er bereits Null ist).
Ein "String-Zyklus" wird nicht stattfinden, wenn "String erschöpft" während des Maschinenzyklus anliegt, da "String erschöpft" nur anliegt, wenn es (1) keinen Wegziffern-String an dem Knoten gibt; oder (2) der String an dem aktuellen Knoten bereits erfolgreich auf Übereinstimmung geprüft wurde. Ein "String-Zyklus" wird nicht stattfinden, wenn "Lade IDI- Längenregister" anliegt, da es keinen String geben kann, wenn eine IDI-Länge an dem Knoten gespeichert ist (da nur ein Feld in dem Speicher zum Speichern von Längeninformation vorgesehen ist - wenn sich ein IDI-Übergang ereignet, speichert dieses Feld die IDI-Länge und kann somit keine String-Längen speichern).
Ein "normaler Zyklus" wird eine von drei potentiellen nachster Knotenadressen aus drei Quellen auswählen: den Nächste- Knoten-Zeiger, den DSP-Zeiger und den Level-1-Zeiger. Diese Auswahl wird gemäß der folgenden Regeln durchgeführt:
(a) Wenn "IDI-Länge = 0" auf Leitung 312 und "IDI geladen" auf Leitung 314 anliegt, und DSP-Übergänge global freigegeben sind, dann wird ein "DSP-Zyklus" ausgewählt. Der Wert des vom Speicher 230 zugegriffenen DSP-Zählers wird die Adresse des nächsten Knotens. Nur ein "DSP-Zyklus" ist während des Suchvorgangs erlaubt, was die Suchmaschine daran hindert, in unendlichen Schleifen hängen zu bleiben.
(b) Wenn (a) nicht anwendbar ist, wenn "CRL = 14" von dem Zähler 214 auf Leitung 310 anliegt und die "Level-1-Übergangs"-Flag an dem aktuellen Knoten gesetzt ist, dann werden Level-1-Übergänge global freigegeben, und der Level- 1-Zeiger, auf den von dem Register 340 zugegriffen wird, wird die Quelle der nächsten Knotenadresse sein. In diesem Fall ist der Zyklus ein "Level-1-Zyklus". Nur ein "Level-1- Zyklus" ist wieder pro Suchvorgang erlaubt.
Wenn entweder (a) oder (b) anwendbar sind, dann wird der nächste Maschinenzyklus ohne ein Holen einer "nächsten Ziffer" von dem Halboktett-Generator ablaufen. Das heißt, daß die gleiche Ziffer neu geprüft wird, wenn der Level-1- oder der DSP-Übergang durchgeführt wurde. Wenn weder (a) noch (b) anwendbar sind, dann wird der "Nächste-Knoten-Zeiger", auf den vom Zeiger-DRAM-Array 200 zugegriffen wird, die Quelle der nächsten Knotenadresse sein - d. h. dieser Maschinenzyklus wird ein "Zeigerzyklus" sein. In diesem Fall wird "nächste Ziffer" auf Leitung 282 an dem Halboktett-Generator 290 angelegt, so daß die nächste Ziffer am Anfang des nächsten Maschinenzyklus verfügbar ist. Das CRL-Register 240 und das IDIL-Register 250 werden beide dekrementiert.
Für jeden "normalen Zyklus" sind die folgenden Regeln anwendbar. Wenn das höchstwertige Knotenadressen-Bit gleich Null oder wenn das "NIL-Knoten"-Flag gesetzt ist, dann wird dieser Maschinenzyklus der letzte für das aktuelle Suchargument sein (d. h. die aktuelle Netzwerkadresse, die gesucht wird). Wenn das "speicher aktuelle Knotenadresse"-Flag gesetzt ist, dann wird die Knotenadresse des aktuellen Zyklus in dem "Ergebnisbis-jetzt"-Register 295 gespeichert (nur wenn dies kein Nil- Knoten ist), wobei jeder vorherige Wert überschrieben wird.
Für einen "String-Zyklus" oder für einen "Zeigerzyklus" (d. h. jeden Maschinenzyklus, der eine Suchziffer absorbiert), wird der aktuelle Maschinenzyklus der letzte sein, wenn "CRL = 0" auf Leitung 284 anliegt. Im Fall eines "String-Zyklus" wird eine String-Fehlübereinstimmung deklariert. Im Fall eines "Zeigerzyklus" wird der aktuelle Knoten deklariert, um den größten Fortschritt darzustellen, der an der Suchadresse durchgeführt werden kann. Wenn das Signal "CRL = 0" während eines "DSP-Zyklus" oder eines "Level-1-Zyklus" anliegt, dann kann der geeignete Übergang immer noch durchgeführt werden, da er nicht verlangt, daß ein gültiges Halboktett am Halboktett-Datenbus 204 vorhanden ist.
Fehler in der Datenbank können durch die Maschine erkannt werden, was zu einer verfrühten Fehlerbeendigung führt. Die folgenden Fehler werden erkannt:
1. Ein Paritätsfehler zwischen dem aktuellen Halboktett und dem aktuellen Wegziffern-String, wie er durch das Paritätsprüfelement 300 erfaßt wird;
2. Ein Paritätsfehler im Zeiger-DRAM-Array 200, wie er durch das Paritätsprüfelement 302 erfaßt wird, wenn der Fehler während eines "Zeigerzyklus" auftritt (d. h. wenn Daten aus diesem Speicher als die nächste Knotenadresse zu verwenden sind;
3. Wenn der String-Längenzähler 260 über den legalen Bereich während eines "String-Zyklus" inkrementiert wurde.
Sobald die Maschine das periodisches Durchlaufen angehalten hat, wird das "belegt"-Status-Bit gelöscht und das Ergebnis der Suche kann von der CPU gelesen werden. Anhang B beschreibt ausführlich das Format und die Interpretation des Suchergebnisses.

Performanz-Vorhersage für die ARE

Suchzeit

Die Leistung oder Performanz der ARE ist relativ leicht vorherzusagen. Die Suchzeit wird grob gleich der Anzahl von Ziffern in dem Suchargument multipliziert mit der Maschinenzykluszeit sein. Zusätzlicher Aufwand muß diesem Schritt hinzugefügt werden.
Einmal alle 15 Mikrosekunden wird ein Maschinenzyklus ablaufen, um die DRAMs 200, 220 aufzufrischen. Nur ein solcher "extra"-Zyklus kann pro Suche erwartet werden. Außerdem kann es zwei weitere Maschinenzyklen geben, bei denen eine Ziffer nicht absorbiert wird: ein "DSP-Zyklus" und ein "Level-1- Zyklus". Erfindungsgemäß verhindern, wie es oben erläutert wurde, intrinsische Hardwaresperren mehr als einen von jedem Übergangszyklus pro Suchargument, sogar mit verfälschten Datenbanken.
Wenn die maximale Länge eines Sucharguments vierzig Ziffern beträgt, dann werden höchstens 44 Maschinenzyklen benötigt, um das Argument zu verarbeiten. (Dies umfaßt einen letzten "Dummy"-Maschinenzyklus, der mit keinem gültigen Halboktett auf diesem Halboktett-Datenbus 204 läuft.) Dazu muß der Mehraufwand des Ladens der Eingabe und des Lesens der Ausgaberegister hinzugefügt werden. Diese Berechnung ist schwierig, insbesondere wenn bei den Daten-Schreib- und Daten-Lese- Zyklen auf die Anweisungen Bezug genommen wird, die sie verursachen.
Die CPU-Registerladezyklen können alle mit höchstens zwei Wartezuständen ablaufen. Der erste Maschinenzyklus kann starten, sobald der erste Registerdatei-Ladezyklus erfaßt wird. Diese Zeit ist von der Größenordnung von 300 Nanosekunden, die von dem Start von S0 des CPU-Schreibzyklus bis zu dem Start des ersten Maschinenzyklus gemessen wird. Zum Lesen des Ergebnisses können gleichzeitig CPU-DSACK-Signale mit dem Ende des letzten Maschinenzyklus angelegt werden (oder besser, deren Blockieren kann freigegeben werden). Das Ende des S5 des CPU-Lesezyklus wird dann innerhalb von 150 Nanosekunden auftreten.
Die CPU wird typischerweise sechs Langwörter (bis zu 46 Ziffern, wobei nur die ersten 40 Ziffern signifikant sind) an die Registerdatei transferieren. Die von dem Start des ersten Transfers bis zum Ende des das Ergebnis lesende Lesezyklus gemessene Zeit wird für eine 208 Nanosekunden-Maschinenzyklus betragen:
300 ns + 44 · 208 ns + 150 ns = 9,6 us.
Um eine genauere Zahl für die verfügbare CPU-Reservezeit zu geben, sollte die Transferzeit von sechs Langwörtern von dieser Zahl subtrahiert werden (6 · 200 ns = 1,2 us). Dies gibt ein Ergebnis von 8,4 us.
Die Nachschlagzeit einer Level-1-Adresse oder einer IEEE 802.3-Datenlinkadresse ist viel geringer. Wenn die CPU die Adresse mit einem Oktett vom Wert "12" voranhängt und dann das Ergebnis an die Registerdatei 270 transferiert, werden zwei Langwort-Schreibvorgänge erforderlich sein (wobei das letzte Oktett derselben ignoriert wird). Wenn von der Tatsache Gebrauch gemacht wird, daß Daten in der Registerdatei 270 nicht überschrieben werden, kann einem der acht Eingabeblöcke (und dementsprechend einer der acht Wurzelknoten) Level-1-Nachschlagvorgängen zugewiesen werden - sobald das erste Oktett mit dem Wert "12" geschrieben ist, wird es dort bleiben. Auf diese Art kann die Level-1-Adresse direkt in die Datei geschrieben werden. Dies wird immer noch zwei Schreibvorgänge erfordern, wobei jedoch aufgrund der Fehlausrichtung mindestens drei CPU-Buszyklen durch die Schnittstellen- Hardware ablaufen.
Der Wurzelknoten für den Level-1-Nachschlagevorgang wird (vermutlich) der gleiche sein, wie der Anfangsknoten in dem Level-1-Zweig der Datenbank; wobei keine Domänen-Übergänge erwartet werden können. Wenn sich ein Auffrischzyklus während eines Nachschlagens ereignet, wird die Nachschlagzeit 12 Ziffern + Auffrischen + Dummy sein:
300 ns + 14 · 208 ns + 150 ns = 3,4 us.
Ein Subtrahieren der Zeit für (wahrscheinlich 3) Schreibzyklen gibt eine wirksame Nachschlagzeit von 2,8 us.

Datenbankkapazität

Die Datenbankkapazität der hier präsentierten erfindungsgemäßen ARE ist relativ leicht zu berechnen. Es werden zwei Arten von Datenbanken betrachtet, die zusammen in der ARE existieren: solche, die es ermöglichen, daß Adressen mit bis zu einer Gesamtlänge von 16 Halboktetten erkannt werden können; und zweitens solche, die es ermöglichen, daß Adressen mit bis zu 40 (potentiell 46) Halboktetten erkannt werden können. Eine Gesamtzahl von bis zu acht unterschiedlichen Datenbanken kann, begrenzt durch die Anzahl von Wurzelknoten, zusammen existieren.
Die früheren Datenbanken werden unter anderen zum Erkennen von Level-1-Adressen, Datalink-Adressen und Router-Ids verwendet. Unter der Voraussetzung, daß es 52K Knoten mit einer bis zu 16 Halboktetten konstanter String-Speicherung an jedem Knoten gibt, wovon 26K Terminal-Knoten sind, folgt, daß eine kombinierte Gesamtsumme von bis zu 26K Einträgen für diese Datenbanken garantiert werden kann. (Im schlimmsten Fall wird jeder Übergangsknoten höchstens zwei Nächste-Knoten-Zeiger aufweisen; somit wird der TRIE ein binärer TRIE mit so vielen Übergangsknoten wie Endknoten.)
Da es 4K Knoten gibt, die konstante Strings mit einer Länge bis zu 48 Halboktetten haben (von denen 2K Terminal-Knoten sind), erscheint es zuerst vernünftig anzunehmen, daß bis zu 2K Einträge zum Suchen dieser längeren Adressen garantiert werden können. Im schlimmsten Fall können jedoch extra Übergangsknoten erforderlich sein - diese extra Knoten weisen nur einen Ausgang auf, nämlich den DSP-Zeigerausgang. (Der DSP- Übergang kann nicht als Teil des konstanten Strings gespeichert werden.) Unter diesen Bedingungen können nur 1K Einträge garantiert werden. Es sei bemerkt, daß es möglich ist, die ARE neu zu definieren, so daß DSP-Übergänge von Terminal- Knoten erlaubt sind - dann erhöht sich die Garantie auf 1,3K Einträge im schlimmsten Fall. Es sei ferner bemerkt, daß es möglich ist, Knoten von den anderen Datenbanken zu stehlen und die Knoten mit kleineren konstanten String-Kapazitäten zusammen zu "ketten". Tatsächlich ist die aktuelle definierte maximale IDP-Länge nur 18 Ziffern lang - daher können sogar die Knoten mit einer Kapazität von 16-Ziffern zum Halten von IDP-Ziffern verwendet werden, ohne zu befürchten, daß die konstante String-Speicherlänge die Knotenkapazität überschreitet. (Wenn die maximale IDP-Länge 18 Ziffern ist, dann wird die maximale IDI-Länge zwei weniger sein - AFI-Ziffern werden gewöhnlich nicht als Teil eines konstanten Strings gespeichert.)
Für Paket-Weiterleitungszwecke sei bemerkt, daß die Level-2- Datenbank auf die Level-1-Datenbank durch den Level-1-Zeiger abgezweigt wird. Daher kann angegeben werden, daß eine Datenbank aufgebaut werden kann, die die Erkennung von bis zu 26K Adressen garantiert, die im Bereich (in-area) sind (und durch Level-1-Routing weitergeleitet werden) und bis zu 1K Adressen, die in einem äußeren Bereich (out-of-area) sind (und gemäß dem längsten Präfix weitergeleitet werden).
Weitere Ausführungsformen liegen innerhalb des Schutzumfangs der Ansprüche, die den Anhängen folgen.
Beispielsweise kann die Erfindung für Suchvorgänge jeder großen Datenbank verwendet werden, die Strings von (möglicherweise stark) veränderlicher Länge aufweisen. Solche Datenbanken sind üblich: Beispiele umfassen Nachschlagverzeichnisse in einem Telefonkontext, Online-Wörterbücher, Rechtschreibprüfer, Nachschlagen von Sozialversicherungsnummern, etc. Die Erfindung würde in jedem derartigen Kontext, bei dem ein Nachschlagen im Verzeichnis unter Verwendung eines Such-Tries durchgeführt wird, anwendbar sein. Obgleich das Wort "Knoten" hier verwendet wurde, um ein Element in einer hierarchischen Baumstruktur zu beschreiben, ist die Erfindung auf jede Baumstruktursuche anwendbar, ob oder ob nicht das Wort "Knoten" verwendet wird, um die Baumstruktur zu beschreiben.

Anhang A: ARE-Speicherabbildung

Die ARE wird in einem 16 MB-Raum in der Widget-Speicherabbildung zwischen Adressen 0800 0000 und 08ff ffff abgebildet.
Der 16 MB-ARE-Raum ist in 64K "Knoten" aufgeteilt, wobei jeder Knoten eine Größe von 256 Oktetten aufweist. Somit kann eine ARE-Adresse (die aus acht hexadezimalen Ziffern besteht), wie gezeigt in drei Felder unterteilt werden:
08 nnnn aa
wobei die ersten zwei Ziffern, "08", die ARE auswählen; die nächsten vier Ziffern, "nnnn", einen der 64K Knoten aus wählen; und die zwei Ziffern am Ende, "aa", einen Unterraum innerhalb eines Knotens auswählen.
Die erlaubten Unterräume, auf die an jedem Knoten zugegriffen werden kann, werden in Fig. 9 definiert.

Beschreibung von Ressourcen Knotensteuerwort

Das Knotensteuerwort ist ein Byte-adressierbares 16-Bit-Wort, das an jedem Knoten unterstützt wird. Es werden nicht alle Bits von der Suchmaschine interpretiert, wobei jedoch alle Bits implementiert werden, um die ARE-Wartung zu erleichtern (z. B. durch Verkettung freier Knoten). Das Format und die Erläuterung dieses Worts wird nachstehend gegeben:
NIL SR IC L1 d11 d10 d9 d8 d7 d6 < -LÄNGE ->
NIL (Nil-Knoten): Wenn dieses Bit gesetzt ist, dann wird dieser Knoten von der Suchmaschine als ein Nil-Knoten interpretiert. An einem Nil-Knoten ist die Einstellung jedes anderen Steuerbits irrelevant. Sofort nach Eintreten in einen Nil-Knoten wird die Suchmaschine anhalten, wobei ein "Nil- Knoten" als der Grund des Anhaltens angegeben wird. Jeder an einem Nil-Knoten gespeicherter String wird ignoriert. Die Adresse des Nil-Knotens wird nicht in irgendeinem durch die Suchmaschine zurückgegebenen Ergebnis gemeldet.
ANMERKUNG: Alle Knoten, deren MSB-Adresse gleich Null ist (d. h. Knoten 000 bis 7fff), sind Terminal-Knoten. Während eines Suchvorgangs wird, wenn ein Terminal-Knoten angetroffen wird, die Suchmaschine anhalten und keinen Übergang von dem Knoten durchführen,
SR (Speicher Ergebnis): Während eines Suchvorgangs werden alle angetroffenen Knoten, die dieses Bit gesetzt haben, im "bis jetzt-Ergebnis"-Register 245 gespeichert. Dieses einzelne Wortregister 245 wird immer die Adresse des Knotens enthalten, der zuletzt mit dem SR-Bit gesetzt angetroffen wurde. Das SR-Bit wird nicht durch die Suchmaschine geprüft, bis irgendein vorhandener konstanter String erfolgreich mit dem Suchschlüssel übereinstimmt; eine String-Fehlübereinstimmung (die eine frühzeitige Erschöpfung der Suchschlüsselziffern umfaßt) wird dazu führen, daß der Knoten trotz der Bedingung des SR-Bits NICHT gespeichert wird. Die Knotenadresse wird nicht gespeichert, wenn der Knoten NIL ist.
IC (IDP-Zählwert vorhanden): Wenn dieses Bit gesetzt ist, dann wird der Wert des "Länge"-Felds von der Suchmaschine als die Länge eines IDP interpretiert. Dieses Bit sollte an dem ersten Knoten gesetzt werden, der der zweiten Ziffer des AFI folgt. Das Längenfeld sollte auf die geeignete IDP-Länge, die durch den relevanten AFI angegeben wird, gesetzt werden. Nur ein solcher Wert wird während eines Suchvorgangs geladen. Das IC-Bit wird ignoriert, wenn der Knoten NIL ist.
ANMERKUNG: Ein konstanter String kann an keinem Knoten, bei dem das IC-Bit gesetzt ist, gespeichert werden (und wird ignoriert).
L1 (Level-1-Übergang möglich): Dieses Bit wird nur durch die Suchmaschine geprüft, wenn es genau vierzehn verbleibende Ziffern des Suchschlüssels aufweist und jeden vorhandenen konstanten String mit Suchadresse erfolgreich auf Überein- Stimmung geprüft hat. Wenn dies der Fall ist und das L1-Bit gesetzt ist, dann wird die Suchmaschine den Wert des Level-1- Zeigers als die Adresse des nächsten Knotens verwenden.
d11,d10, ...,d6: Diese Bits werden nicht von der Suchmaschine verwendet.
LÄNGE (5 Bits): Dieses Feld wird auf eine von zwei Arten interpretiert:
1. Wenn IC gesetzt ist und NIL nicht gesetzt ist, dann wird dieses Feld als die Länge eines IDP interpretiert (wie oben erläutert wird).
2. Wenn IC nicht gesetzt ist und NTL nicht gesetzt ist, dann wird dieses Feld als die Länge eines an dem Knoten gespeicherten konstanten Strings interpretiert. Der konstante String wird mit den Ziffern des Suchschlüssels auf Übereinstimmung geprüft, bis es eine Fehlübereinstimmung gibt oder bis eine der beiden Quellen erschöpft ist.

String-Speicherplätze

String-Speicherplatz wird vorgesehen, um konstante Strings mit veränderlicher Länge an einem Knoten zu speichern. Der String wird als eine Folge von Ziffern, eine Ziffer pro Byte, gespeichert. (Die vier höchstwertigen Bits jedes Bytes werden bei einem Schreibvorgang ignoriert und immer als Null gelesen.) Die Länge des Strings (Anzahl gespeicherter Ziffern) wird in dem Knotensteuerwort angegeben. Die maximale Anzahl von Ziffern, die gespeichert werden können, ist eine Funktion der Knotenadresse, wie nachstehend gezeigt ist:

Übergangsknoten:

f800 < = Knotenadresse < = ffff - maximal 48 Ziffern
9000 < = Knotenadresse < = f7ff - maximal 16 Ziffern
8000 < = Knotenadresse < = Bfff - keine Speicherung erlaubt.

Terminal-Knoten:

7800 < = Knotenadresse < = 7fff - maximal 48 Ziffern
1000 < = Knotenadresse < = 77ff - maximal 16 Ziffern
0000 < = Knotenadresse < = Offf - keine Speicherung erlaubt.
("x < = y" bedeutet x ist kleiner oder gleich y)
Wenn die Suchmaschine eine Knoten antrifft, bei dem ein Wegziffern-String gespeichert ist, wird der String mit den verbleibenden Suchadressenziffern verglichen, bis eine der beiden Quellen von Ziffern erschöpft ist oder bis es eine Fehlübereinstimmung gibt.

Nächste-Knoten-Zeiger

Achtzehn "nächste Knoten"-Zeiger werden für alle 32K Übergangsknoten vorgesehen. (Eine Zeigerkomprimierung wurde nicht implementiert.) Die ersten 32K Knoten sind "Terminal- Knoten" und sie können keine Übergänge durchführen.
Ein Nächster-Knoten-Zeiger wird von der Suchmaschine ausgewählt, wenn eine String-Übereinstimmung erfolgreich beendet wurde (wo relevant), wenn der Knoten kein Terminal- oder NIL- Knoten ist, und wenn es verbleibende Suchadressenziffern gibt. Die Auswahl wird gemäß der folgenden Regeln durchgeführt (siehe oben "Theorie der Betriebsweise"):
1. Wenn eine IDI-Länge in das IDIL-Register 250 geladen und diese Länge auf genau Null dekrementiert wurde (oder wenn nicht, der aktuelle Knoten eine Gesamt-IDP-Länge von 2 in IDIL lädt) - d. h. wenn die Suchmaschine glaubt, daß die nächste zu verarbeitende Suchschlüsselziffer die erste Ziffer des DSP ist - dann wird der DSP-Zeiger ausgewählt. Der DSP-Zeiger kann höchstens einmal während eines Suchvorgangs ausgewählt werden. Die Auswahl des DSP-Zeigers verbraucht die aktuelle Suchschlüsselziffer nicht - sie wird im nächsten Maschinenzyklus verwendet.
2. Wenn es andernfalls genau vierzehn verbleibende Suchschlüsselziffern gibt und das L1-Bit in dem Knotensteuerwort an diesem Knoten gesetzt ist, dann wird der Level-1-Zeiger ausgewählt. Der Level-1-Zeiger kann höchstens einmal während eines Suchvorgangs ausgewählt werden. Die Auswahl des Level- 1-Übergangszeigers verbraucht die aktuelle Suchschlüsselziffer nicht - sie wird im nächsten Maschinenzyklus verwendet.
ANMERKUNG: Wenn sowohl (1) als auch (2) anwendbar sind, werden die Bedingungen für (2) neu geprüft, nachdem (1) ausgeführt wurde.
3. Andernfalls wird die nächste Ziffer des Suchschlüssels verwendet, um einen der ersten sechzehn Nächste-Knoten-Zeiger auszuwählen. Wenn die Ziffer beispielsweise Null ist, dann wird der Zeiger an der Adresse 40 verwendet. (Zeigeradressen- Offset ist 40, siehe Fig. 9.)
Suchadressen-Speicherbereich
32 Byte Speicherplatz sind an jedem der Knoten 8000 bis 8007 vorgesehen. Von diesen 32 Byte werden die ersten 24 Byte zum Laden einer neuen Suchadresse verwendet; das Ergebnis der Suche wird von der Suchmaschine in die letzten acht Byte geschrieben. Bis zu acht Suchzusammenhänge werden unterstützt es sei jedoch bemerkt, daß eine neue Suche nicht initiiert werden sollte, bis die aktuelle beendet ist (da dies die aktuelle Suche abbrechen wird). Wenn eine Suche initiiert ist, wird der verwendete Knoten, um die Suchadresse zu laden, der von der Suchmaschine verwendete Wurzelknoten sein. Das Format der Suchadresse muß wie folgt sein:
Erstes Byte (Adresse 80/a0): Länge der Suchadresse. Nachfolgende Bytes: Suchadresse, Länge wie im ersten Byte definiert.
Die in das erste Byte geschriebene Längeninformation wird auf eine von zwei Arten interpretiert: Wenn das Byte in die Adresse 80 geschrieben ist, wird sie als eine Oktettlänge interpretiert, d. h. die Anzahl vorgesehener Ziffern ist doppelt so groß wie der Wert des Längenbytes; wenn das Längenbyte in die Adresse a0 geschrieben ist, wird es als eine Halboktettenlänge interpretiert, wobei explizit die Anzahl von Ziffern in dem Suchschlüssel angegeben wird. Der Adressenraum a0-bf ist sonst ein Alias des Adressenraum +80-9f. (ANMERKUNG: Die aktuelle ARE-Implementierung betrachtet eine Halboktettenlänge größer als 40 (dezimal) oder gleich Null als einen Fehler).
Es können mehr Ziffern in den Suchschlüsselbereich geschrieben werden, als durch das Längenoktett impliziert werden; insgesamt sollten mindestens 32 Oktette geschrieben werden, ansonsten wird das 33ste Oktett die Suche entweder neu initialisieren oder einen Busfehler verursachen. Wenn mehr als 24 Oktette geliefert werden, werden die überschüssigen Oktette mit dem Suchergebnis zum Zeitpunkt, wenn es verfügbar wird, überschrieben. Wenn weniger Oktette geliefert werden als das Längenfeld angibt, dann wird die Suchmaschine unbegrenzt darauf warten, daß sie geliefert werden, es sei denn, daß die Suche vorzeitig beendet wird.

Suchergebnis-Information

Das Ergebnis einer Suche ist bei Adressen 98-9f (ebenso bei b8-bf) an dem Knoten verfügbar, bei dem der Suchschlüssel geladen wurde (d. h. einer der Knoten 8000 bis 8007). Das Format des Ergebnisses ist wie folgt:

Offset Interpretation

98 oder b8 Summenstatus-Byte.
99 oder b9 verbleibende Halboktettenlänge der Suchadresse bei Beendigung der Suche. (Byte)
9a-9b oder ba-bb der zuletzt angetroffene Knoten, bei dem das SR-Bit gesetzt ist (vorzeichenloses Wort).
9c oder bc verbleibende Halboktettenlänge eines IDI bei Beendigung der Suche (Byte mit Vorzeichen).
9d oder bd Wert des Stringziffernzählers bei der Beendigung der Suche. (Byte)
9e-9f oder be-bf zuletzt während einer Suche angetroffener 5 Knoten (ausgenommen, wenn dies ein NIL- Knoten ist). (vorzeichenloses Wort)
Für ausführliche Information hinsichtlich des Interpretierens der Ergebnisinformation siehe Anhang B.

Steuer- und Statusregister Paritätssteuerungs- und Statusregister 0 - Adresse 080000c0

Format: PES PEP EPS EPP 0 0 0 0 0
Rücksetzstatus: 0 0 0 0 0 0 0 0 0 0
Das Statusregister 0 sieht eine Paritätssteuerung und einen Status für CPU-Zugriffe auf Datenbankspeicher vor, die mit DRAMs implementiert sind.
PES: Gesetzt, wann immer ein Paritätsfehler beim CPU-Lesen eines String-Speicherungs-Speichers erfaßt wird. Rückgesetzt durch ein Überschreiben durch die CPU mit einer Eins.
PEP: Gesetzt, wann immer ein Paritätsfehler beim CPU-Lesen von Nächste-Knoten-Zeigern erfaßt wird. Rückgesetzt durch ein Überschreiben durch die CPU mit einer Eins.
EPS: Lesen /Schreiben durch die CPU. Wenn Null, verwende ungerade Parität (Erzeugen und Prüfen) an dem String- Speicherungs-Speicher; wenn auf Eins gesetzt, verwende gerade Parität.
EPP: Lesen/Schreiben durch die CPU. Wenn Null, verwende ungerade Parität (Erzeugen und Prüfen) an dem Nächste-Knoten- Zeiger-Speicher; wenn auf Eins gesetzt, verwende gerade Parität.

Steuerregister 1 - Adresse 080000c1

Format: 1 SM NSAP IL1 IDSP SDK d2 d1 d0
Rücksetzstatus: 0 0 0 0 0 0 0 0
Es gibt ein Steuerregister für die gesamte ARE. Die Bits werden nachstehend definiert:
SM (Suchmodus): Wenn SM = 0 ( = "Wartungsmodus") ist, wird der Suchmodus gesperrt und die Suchergebnis-Information ist ungültig; die Suchmaschine wird rückgesetzt. Dieser Modus muß ausgewählt werden, bevor die CPU auf irgendeine Ressource unterhalb der Adresse 7f zugreifen kann. Wenn SM = 1 ist, ist der Suchmodus freigegeben. Dieser Modus muß ausgewählt werden, bevor ein Suchschlüssel geladen ist, und muß beibehalten werden, bis das Ergebnis gelesen wurde. In diesem Modus sind alle Ressourcen unterhalb der Adresse 7f unzugänglich.
NSAP (NSAP-Modus): Dieses Bit beeinflußt nur die Einstellung des Erfolg/Fehler-Bits in dem Ergebnis-Summenoktett am Ende einer Suche. (siehe Anhang B).
IL1 (Sperren von Level-1-Übergängen): Wenn dieses Bit gesetzt ist, dann wird während jeglicher Suche ein Level-1-Übergang nicht durchgeführt.
IDSP (Sperren eines DSP-Übergangs): Wenn dieses Bit gesetzt ist, dann wird ein DSP-Übergang während jeglicher Suche nicht durchgeführt.
SDK (Verzögere DSACK): Wenn dieses Bit gesetzt ist, dann wird ein Lesen der Suchergebnis-Information (oben unter Suchergebnis-Information definiert) zu einem möglicherweise erweiterten Buszyklus führen, der verzögert wird, bis das Ergebnis verfügbar ist; dies eliminiert den Bedarf zu prüfen, ob das Ergebnis verfügbar ist. Dies ist in jedem Kontext, jedoch nur im Suchmodus, anwendbar.
D2,d1,d0 0 - nicht durch die ARE verwendet.

Suchstatusregister 2 - Adresse 08000c2 (schreibgeschützt)

Format: BCNT RT2 RT1 RT0 0 0 0 0
Rücksetzstatus: u u u u 0 0 0 0
Die vier aus diesem Register verfügbaren Status-Bits sind primär für diagnostische Zwecke vorgesehen. Die Bits sind nur gültig, wenn die Suchmaschine entweder angeHALTEN oder BELEGT ist (wie im Statusregister 3 definiert ist).
BCNT: Dieses Bit ist gesetzt, wenn die Suchmaschine annimmt, daß das erste Byte der Suchadresse ein Oktett-weiser Längenzählwert ist; wenn BCNT gelöscht ist, dann wird ein Halboktett (Ziffer)-Zählwert angenommen.
RT2..0: Diese drei Bits sind gleich den drei letzten niederstwertigen Bits der Wurzeladresse, die die Suchmaschine für den Zweck eines Lesens des Sucharguments verwendet.

Suchstatusregister 3 - Adresse 080000c3 (schreibgeschützt)

Format: BELEGT HALT f5 f4 f3 f2 f1 f0
Rücksetzstatus: 0 0 0 0 0 0 0 0
Dieses Statusregister liefert den Suchmaschinenstatus zur Anwendung und diagnostischen Verwendung.
BELEGT: Dieses Bit ist gesetzt, wenn die Suchmaschine Knoten verarbeitet oder das Ergebnis lädt.
HALT: Dieses Bit ist gesetzt, wenn die Suchmaschine ein Verarbeiten von Knoten angehalten hat.
Die obigen zwei Bits sollten als ein Paar decodiert werden.
f5..f0: Diese Bits werden durch Schreiben von Komponenten des Suchschlüssels in die Registerdatei gesetzt und werden von der Suchmaschine als eine Angabe verwendet, daß gültige Daten vorhanden sind.
Alle Bits des Registers 3 werden rückgesetzt, wann immer die Maschine im Wartungsmodus ist (Bit 7 des Steuerregisters 1 ist Null). Die Bits f5 bis f1 werden rückgesetzt, wann immer die CPU in das letzte Byte des ersten Langworts des Suchschlüssels schreibt; zur gleichen Zeit wird das Bit f0 gesetzt (wenn der Suchmodus freigegeben ist). Das Bit f1 ist im Suchmodus gesetzt, wenn die CPU in das letzte Byte des zweiten Langworts des Suchschlüssels schreibt; und die Bits f2 bis f5 werden ebenso beim Schreiben des letzten Bytes des dritten bis sechsten Langworts gesetzt.
ARE Statusregister 4 - Adresse 080000c4 (schreibgeschützt)
Format: s7 s6 s5 s4 s3 s2 s1 s0
Rücksetzstatus: - - - - - - - -
Das Statusregister ermöglicht es der CPU, die Position von acht Schaltern in dem eingebauten (on-board) Schaltungspaket zu lesen.

Anhang B: Decodieren des Suchergebnisses von der ARE

Das Ergebnis einer Suche ist bei den Adressen 98-9f verfügbar (gleichfalls b8-bf) an dem gleichen Knoten, in dem der Suchschlüssel geladen wurde; d. h. einer der Knoten 8000 bis 8007. Wenn das Steuerbit "SDK" gesetzt ist (Bit 3 im Steuerregister 1), dann kann das Ergebnis zu irgendeiner Zeit nach dem Laden des Suchschlüssels gelesen werden - die CPU wird durch Hardware verzögert, bis gültige Daten zurückgegeben werden können. Wenn das "SDK"-Bit nicht gesetzt ist, dann muß die CPU das Statusregister 3 abfragen, um zu bestimmen, wann der Status des Suchergebnisses gültig ist.
Das Format des Ergebnisses ist wie folgt; eine minimale Verzögerung wird auftreten, wenn das Ergebnis als zwei Langwörter gelesen wird.
Zusammenfassungs-Status-Byte
Das Zusammenfassungs-Status-Byte ist vorgesehen, damit die Host-CPU schnell bestimmen kann, ob eine Suche erfolgreich war oder nicht; und falls nicht, den Grund für das Scheitern der Suche.
Die Codierung hängt davon ab, ob die Datenbank von der Suchmaschine als verfälscht (corrupted) oder nicht angesehen wird; und wird ferner durch das "NSAP-Modus"-Bit im Steuerregister 1 beeinflußt.
Die beiden Fälle werden nachstehend getrennt behandelt:

Fall 1: Datenbank verfälscht

Für eine verfälschte Datenbank wird die Codierung der Ausgabe wie folgt sein:
1 1 0 ISC PEP PES L1ND LIDE
wobei
ISC = erreichter verbotener String-Zählwert ist (die CPU gab an, daß mehr Stringziffern als das an einem Knoten erlaubte Maximum vorhanden waren)
PEP = Paritätsfehler am Zählerspeicher
PES = Paritätsfehler am String-Speicher
LIND = Level-1-Übergang durchgeführt, aber kein DSP-Übergang durchgeführt (nur NSAP-Modus)
LIDE = Level-1-Übergang durchgeführt und Quellenziffern erschöpft (nur NSAP-Modus)
Das Setzen der Bits ISC, PEP und PES schließt sich gegenseitig aus.
Wenn ISC gesetzt ist, dann versuchte die Suchmaschine einen String-Vergleichszyklus mit einem Ziffernzeiger durchzuführen, der die maximal an einem Knoten erlaubte String-Länge überschritten hat. Das "soweit-gekommen"-Feld enthält den Knoten, bei dem der String gespeichert ist; das "String- Zähl"-Feld enthält den Stringziffernzeiger, der zu groß ist.
Wenn PEP gesetzt ist, dann wurde ein Übergang von einem Knoten durch einen der sechzehn "nächster Knoten"-Zeiger durchgeführt. Die für den nächsten Knoten angegebene Adresse enthielt einen Paritätsfehler. Das "soweit-gekommen"-Feld enthält den Knoten, bei dem der verfälschte "nächster Knoten"-Zeiger gespeichert ist. Das "verbleibende Länge"-Feld gibt an, wieviele Ziffern des Suchschlüssels verbleiben, um von der Suchmaschine verarbeitet zu werden; die erste von diesen verbleibenden Ziffern ist diejenige, die direkt der Ziffer folgt, die verwendet wurde, um den verfälschten "nächster Knoten"-Zeiger auszuwählen.
Wenn PES gesetzt ist, dann wurde ein String-Vergleichszyklus durchgeführt, wobei jedoch die gespeicherte Stringziffer einen Paritätsfehler enthielt. Das "soweit-gekommen"-Feld enthält den Knoten, bei dem der verfälschte String gespeichert ist. Das "Stringzähl"-Feld zeigt auf die Ziffer nach derjenigen, bei der ein Paritätsfehler erfaßt wurde.
Die Einstellung der LiND- und LIDE-Bits ist unabhängig von den ISC-, PEP- und PES-Bits. Bei der Beendigung der Suche, aus welchem Grund auch immer, wird das LIND-Bit gesetzt, wenn der NSAP-Modus ausgewählt ist, und ein Level-1-Übergang, jedoch kein DSP-Übergang, werden durchgeführt. Das LIDE-Bit wird ebenso gesetzt, wenn ein Level-1-Übergang durchgeführt wurde und es keine verbleibenden Suchschlüsselziffern gibt die Suchmaschine erwartet, daß es normalerweise mindestens zwei verbleibende Ziffern bei der Beendigung einer NSAP-Suche geben wird, wenn ein Level-1-Übergang durchgeführt wurde (diese beiden Ziffern sind das SEL-Feld).

Fall 2: Datenbank nicht verfälscht

Wenn die Datenbank als nicht verfälscht angesehen wird, dann wird das Codieren der Bits in dem Zusammenfassungs-Status- Byte wie folgt sein:
F 0 RL NIL SM DE L1 DSP
wobei
F = Suchmißerfolg (0 = Erfolg). Dieses Bit wird durch das NSAP-Modus-Bit beeinflußt.
RL = "Ergebnis-bis jetzt"-Feld ist gültig.
NIL = NIL-Knoten erreicht
SM = String-Fehlübereinstimmung aufgetreten
DE = Quellenziffern erschöpft
L1 = Level-1-Übergang durchgeführt
DSP = DSP-Übergang durchgeführt
Das F-Bit ist 0, wenn die Suche erfolgreich ist. Eine erfolgreiche Suche wird definiert als eine, bei der die Datenbank nicht verfälscht ist, die gelieferte Länge in dem Bereich von 1 bis 40 Halboktette ist, und außerdem im NSAP- Modus entweder a) ein Level-1-Übergang nicht durchgeführt wurde und das Ergebnis-bis jetzt-Register mindestens einmal geladen wurde; dann wird die Codierung des Zusammenfassungs- Status-Byte sein: 001XXX0X - oder b) ein Level-1-Übergang durchgeführt wurde, es gab keine String-Fehlübereinstimmung, ein Terminal-Knoten erreicht wurde, bei dem das SR-Bit gesetzt ist, und (implizit) ein DSP-Übergang durchgeführt wurde und nicht alle Suchschlüsselziffern verwendet wurden. Die Codierung des Zusammenfassungs-Status-Byte wird in diesem Fall sein: 0010 0011.
In einem Nicht-NSAP-Modus ist eine erfolgreiche Suche eine, bei der die Datenbank nicht verfälscht ist, die Suchadressenlänge in der vorgeschriebenen Länge ist, alle Suchadressenziffern verwendet wurden, eine String-Fehlübereinstimmung nicht aufgetreten ist (und die Suchadressenziffern während einer String-Übereinstimmung nicht erschöpft wurden) und der erreichte Endknoten (der kein NIL-Knoten ist) das SR-Bit gesetzt hat. Der Endknoten kann oder kann nicht ein Terminal- Knoten sein - wenn er ein Terminal-Knoten ist, dann wird das "DE"-Bit Null sein (obgleich die Ziffern erschöpft sind). Die Codierung des Zusammenfassungs-Status-Byte wird sein: 0010 0XXX.
Das RL-Bit wird gesetzt, nachdem das "Ergebnis-bis jetzt"- Feld mit einer Knotenadresse während einer Suche geladen ist. Dieses Bit gibt an, daß das "Ergebnis-bis jetzt"-Feld gültige Daten enthält; wenn RL gleich Null ist, dann ist der Wert des "Ergebnis-bis jetzt"-Felds nicht definiert (bei bevorzugten Ausführungsformen wird es den Wurzelknoten enthalten).
Die Einstellung des L1-Bit hängt davon ab, ob das Steuerbit "IL1" im Steuerregister 1 gesetzt ist oder nicht. Wenn es nicht gesetzt ist, dann werden Level-1-Übergänge freigegeben und das L1-Status-Bit wird nur gesetzt, wenn ein Level-1- Übergang während der Suche durchgeführt wurde. Andernfalls werden, wenn das "IL1"-Bit gesetzt ist, Level-1-Übergänge gesperrt; in diesem Fall wird der L1-Status gesetzt, wenn zu irgendeinem Zeitpunkt während der Suche ein Übergang von einem Knoten (kein DSP-Übergang) durchgeführt wurde, bei dem das Knotensteuerbit "Level-1-Übergang freigeben" gesetzt war.
Das DSP-Bit wird gesetzt und nur dann gesetzt, wenn ein DSP- Übergang während der Suche durchgeführt wurde. Wenn das Steuerbit "IDSP" im Steuerregister 1 gesetzt ist, dann werden DSP-Übergänge gesperrt und das DSP (Übergang durchgeführt)- Statusbit wird immer Null sein.
Die NIL-, SM-, DE-Bits codieren den Grund, warum die Suchmaschine in dem Fall angehalten hat, bei dem die Datenbank nicht verfälscht ist. Jeder Fall wird nachstehend ausführlich behandelt; es sei bemerkt, daß wie oben erläutert ist, das "Ergebnis-bis jetzt"-Feld nur gültig ist, wenn das RL-Bit gesetzt ist.
a) NIL, SM, DE = 000: Diese Codierung bedeutet, daß ein Terminal-Knoten von der Suchmaschine erreicht wurde. Das "soweit-gekommen"-Feld enthält den Terminal-Knoten. Das "Ergebnis-bis jetzt"-Feld enthält den zuletzt durchlaufenen Knoten, der das "SRSF"-Knoten-Steuerbit gesetzt hatte. Wenn "SRSF" am Terminal-Knoten gesetzt ist, dann wird das "Ergebnis-bis jetzt" gleich "Soweit-gekommen" sein. Das "verbleibende Länge"-Feld gibt an, wieviele Suchschlüsselziffern von der Suchmaschine nicht verwendet wurden; der Wert kann Null sein, was angibt, daß die allerletzte Ziffer dafür verantwortlich war, daß die Suchmaschine zum Terminal-Knoten geführt wurde.
b) NIL, SM, DE = 001: Diese Codierung bedeutet, daß die Suchmaschine angehalten hat, da ihr die Suchschlüsselziffern ausgegangen sind; sie würde sonst einen Übergang von dem Knoten, bei dem sie zur Ruhe gekommen ist, durchgeführt haben. Das "soweit-gekommen"-Feld enthält den Knoten, der von der Suchmaschine erreicht wurde, wenn die Ziffern ausgingen. Dieser Knoten ist weder ein NIL- noch ein Terminal-Knoten. 3 Wenn es einen an dem Knoten gespeicherten String gibt, dann wird er erfolgreich auf Übereinstimmung geprüft sein. Wenn das "SR"-Bit an diesem Knoten gesetzt ist, dann wird das "Ergebnis-bis jetzt"-Feld gleich "Soweit-gekommen" sein; andernfalls wird es den zuletzt durchlaufenen Knoten enthalten, der das "SR"-Bit gesetzt hatte. Es sei bemerkt, daß ein Level-1- oder ein DSP-Übergang sogar dann von einem Knoten durchgeführt werden kann, wenn die Suchadressenziffern erschöpft sind; somit kann weder ein DSP- noch ein Level-1- Übergang von dem erreichten Endknoten durchgeführt werden, wie es durch "Soweit-gekommen" angegeben ist.
c) NIL, SM, DE = 010: Diese Codierung bedeutet, daß die Suchmaschine angehalten hat, da sie eine Fehlübereinstimmung zwischen einer konstanten Stringziffer und der nächsten Ziffer des Suchschlüssels erfaßt hat. Das "soweit-gekommen"- Feld enthält den Knoten, bei dem der konstante String gespeichert ist. Das "Stringzähl"-Feld zeigt auf die Stringziffer, nach derjenigen, die eine Fehlübereinstimmung hatte. Das "verbleibende Länge"-Feld gibt an, wieviele Suchschlüsselziffern nicht von der Suchmaschine verarbeitet wurden; die erste dieser verbleibenden Ziffern folgt direkt der Ziffer, die eine Fehlübereinstimmung mit der konstanten Stringziffer aufwies.
Das "Ergebnis-bis jetzt"-Feld enthält den Knoten, der zuletzt besucht wurde (vor demjenigen, bei dem die Suche beendet wurde), der das "SRSF"-Bit gesetzt hatte.
d) NIL, SM, DE = 011: Diese Codierung bedeutet, daß die Suchmaschine angehalten hat, da sie den Stringziffer-Vergleichszyklus nicht durchführen konnte, mit der sie beauftragt wurde. Dies tritt auf, da entweder: i) die Ziffern in dem Suchargument erschöpft sind oder ii) insbesondere die IDP-Ziffern des Sucharguments erschöpft sind, während ein Vergleich mit einer Wegziffern-String durchgeführt wurde, der nur IDP-Ziffern speichert. Das "soweit-gekommen"-Feld enthält den Knoten, bei dem der String gespeichert ist. Das "Stringzähl"-Feld zeigt auf die Stringziffer, die mit i) der nächsten Suchschlüsselziffer oder ii) der nächsten IDP-Ziffer verglichen worden wäre, wenn es eine gegeben hätte.
Das "Ergebnis-bis jetzt"-Feld enthält den Knoten, der zuletzt besucht wurde (vor demjenigen, bei dem die Suche beendet wurde) und das "SR"-Bit gesetzt hatte.
e) NIL, 514, DE = 100: Diese Codierung bedeutet, daß die Suchmaschine einen NIL-Knoten erreichte. Das "soweitgekommen"-Feld enthält den vor dem NIL-Knoten zuletzt besuchten Knoten; ebenso enthält das "Ergebnis-bis jetzt"- Feld den zuletzt besuchten Knoten (vor dem NIL-Knoten), bei dem das "SR"-Bit gesetzt war.
Der Übergang zu dem NIL-Knoten wurde durchgeführt, indem eine Suchschlüsselziffer verwendet wurde, um den im "soweitgekommen"-Feld angegebenen Knoten zu verlassen. Diese Ziffer ist die letzte, die von der Suchmaschine verwendet wurde; sie ist nicht in den "verbleibende Länge"- oder "verbleibende IDI-Längen"-Zählwerten enthalten.
f) NIL, SM, DE = 110: Diese Codierung bedeutet ebenfalls, daß die Suchmaschine einen NIL-Knoten erreicht hat. In diesem Fall wurde der Übergang entweder unter Verwendung eines DSP- oder des Level-1-Zeigers durchgeführt, um den in dem "soweitgekommen"-Feld angegebenen Knoten zu verlassen. In dem gewöhnlichen Fall wird der Level-1-Zeiger nicht auf einen NIL-Knoten zeigen, und es kann somit angenommen werden, daß ein DSP-Übergang zu dem NTL-Knoten durchgeführt wurde.
Es sei bemerkt, daß obgleich der DSP-Übergang zu einem NIL- Knoten erfolgt, das Statusbit "DSP-Übergang durchgeführt" gesetzt sein wird; der Wert des "verbleibende IDI-Länge" wird Null sein. Der Wert des "verbleibende Länge"-Felds wird gleich der gesamten DSP-Länge des gelieferten Suchschlüssels sein.
g) NIL, SM, DE = 111: Diese Codierung bedeutet, daß eine verbotene Suchschlüssellänge an die Suchmaschine geliefert wurde; d. h. Null oder mehr als vierzig Ziffern. In diesem Fall macht die Suchmaschine an dem Suchschlüssel überhaupt keinen Fortschritt.

Überblick über die erforderlichen Wartungsunterstützung

Die Management-Maschine 18 fügt einen neuen Eintrag in die Datenbank ein, indem dieser zuerst als ein Suchargument an die Sucheinheit 40 geliefert wird. Die Sucheinheit 40 versucht das Suchargument in der Datenbank zu lokalisieren; wenn sie fehlschlägt, wird sie mindestens das längste Präfix des Sucharguments melden, das in der Datenbank existiert. (Dieses längste Präfix wird nicht notwendigerweise dem "Ergebnis" der Datenbank zugeordnet sein.)
Höchstens zwei neue Knoten werden in die Datenbank eingefügt; ein neuer Knoten wird hinzugefügt, um den neuen Eintrag von allen existierenden Einträgen zu differenzieren - dieser Knoten wird an dem Punkt eingefügt, an dem die Sucheinheit das nächste Präfix des neuen Eintrags lokalisierte; ein zusätzlicher neuer Knoten wird hinzugefügt und wird einen Wegkomprimierungs-String enthalten, der mit allen verbleibenden Ziffern des neuen Eintrags über die Präfix-Übereinstimmung mit der Datenbank hinaus gleich ist.
Der Differenzierungsknoten muß nur dort hinzugefügt werden, wo der neue Eintrag mit einem Wegkomprimierungs-String der Datenbank verglichen wurde, und eine Fehlübereinstimmung während einer der Vergleiche aufgetreten ist. In diesem Fall muß der Wegkomprimierungs-String in zwei an dem Punkt der Fehlübereinstimmung unterteilt werden. Der Teil, der erfolgreich mit dem neuen Eintrag verglichen wurde, wird in einem neuen Knoten gespeichert (dem Differenzierungsknoten), der zwei Nicht-Nil-Zeiger aufweisen wird. Ein Zeiger zeigt auf den Knoten, der ursprünglich die Wegkomprimierungs-String gehalten hat (der ursprüngliche Wegkomprimierungs-String wird mit dem Teil desselben ausgetauscht, der eine Fehlübereinstimmung mit dem neuen Eintrag aufwies). Der zweite Zeiger zeigt auf den neuen Knoten, der den Wegkomprimierungs-String (falls vorhanden) der verbleibenden Ziffern des neuen Eintrags hält.
Der Umkehrprozeß wird zum Löschen verwendet.

Anhang C: Speicherersparnis einer Zeiger- und Wegkomprimierung

Die hier vorgelegte Analyse zeigt, wieviel physischer Speicher durch Anwenden der Techniken der Wegkomprimierung und der Zeigerkomprimierung auf eine TRIE-basierte Datenbank gespart werden kann. Für die Analyse wird angenommen, daß es bis zu sechzehn Zeigern an einem Knoten gibt, die Vier-Bit- Zeichen (Halboktetten) des an jedem Knoten verarbeiteten Sucharguments entsprechen. Für unterschiedliche Zeichengrößen sollte die Analyse mit einem Parameter durchgeführt werden, der für die feste Größe der hier angenommenen sechzehn Zeiger ausgetauscht wird. Außerdem werden die Eigenarten der ISO- und DECnet-Phase-V-Adressen nicht betrachtet.
Die Analyse betrachtet den schlimmsten Fall für die Speicheranforderungen zum Speichern einer Datenbank mit einer gegebenen Anzahl von Einträgen. Zuerst wird eine Wegkomprimierung betrachtet, gefolgt von der Anwendung einer Zeigerkomprimierung zusätzlich zu der Wegkomprimierung.
Es sei eine TUE-basierte Datenbank angenommen, die erforderlich ist, um bis zu N Einträge zu speichern. Die Einträge seien von einer veränderlichen Länge, bis zu einem Maximum von L Halboktetten. Jeder Knoten in dem TRIE wird sechzehn Zeiger enthalten. Im schlimmsten Fall ist eine maximale Anzahl von Knoten erforderlich, um diese N Einträge zu halten.
Der schlimmste Fall wird auftreten, wenn alle Unterscheidungen zwischen den Einträgen an Knoten gemacht werden, die so nahe an der Wurzel wie möglich sind. Auf diesem Weg wird jeder Eintrag einer großen Kette von Knoten zugeordnet sein, wobei jeder nur einen Nicht-Nil-Zeiger verwendet, der auf den nächsten Link in der Kette zeigt. Die Tiefe des TRIEs, die erforderlich ist, um alle N Einträge zu spezifizieren, wird log&sub1;&sub6;N sein. Die Gesamtzahl der bis zu diesem Level aufgebrauchten Knoten wird (N-1)/15 sein.
Knoten, die innerhalb der langen Ketten verwendet werden, bilden die Masse der Gesamtzahl erforderlicher Knoten. Es wird N Ketten geben. Wenn jeder Eintrag in der Datenbank L Halboktette lang ist, dann wird jede Kette von einer Länge (L-log&sub1;&sub6;N) sein, wobei das Ende jeder Kette auf einen Terminal-Knoten zeigen wird, für den keine Speicheranforderung angenommen wird.
Somit wird die Gesamtzahl erforderlicher Knoten betragen:
(N-1)/15 + (L-log&sub1;&sub6;N) *N (1)
wobei jeder eine Größe von sechzehn Zeigern aufweist. In einer guten ersten Näherung kann dies auf
L*N Knoten (2)
vereinfacht werden.
Es sei nun betrachtet, daß eine Wegkomprimierung implementiert ist. Lange Ketten von Knoten werden nun in Terminal- Knoten oder in Knoten mit mindestens zwei Zeigern zusammenfallen. Die größte Speichermenge wird erforderlich sein, wenn es so viele (Nicht-Terminal)-Knoten wie möglich gibt. Dies ist der Fall, wenn jeder Nicht-Terminal-Knoten genau zwei Zeiger aufweist (beispielsweise ein binärer Trie). Die Gesamtzahl von Nicht-Terminal-Knoten wird N-1 sein. Terminal- Knoten werden keine Speicherung für Zeiger erfordern; somit wird die Speicheranforderung für die Zeiger (mit sechzehn Zeigern pro Knoten)
(N-1)*16 Zeiger (3)
sein.
Es gibt ebenfalls eine Speicheranforderung für die Wegkomprimierungs-Strings. Die Verteilung der Strings zwischen den Knoten kann stark schwanken; wenn es jedoch N Einträge in der Datenbank mit jeweils einer Länge von L Halboktetten gibt, kann die Gesamtspeicheranforderung nicht (N*L) Halboktette überschreiten. Wenn ein Zeiger mit vier Halboktetten gleichgesetzt wird, dann wird durch Addieren der Anforderung von Gleichung (3) eine Gesamtspeicheranforderung von
(N-1) *64 + (N*L) = N* (64+L) Halboktette (4)
mit einer guten Näherung erreicht. Verglichen mit der Speicheranforderung für die Datenbank mit gleicher Größe ohne Wegkomprimierung (Gleichung 2), ist das Verhältnis von (2) zu (4)
(64 · L) / (64 + L) (5)
das durch die Grenzen von 1 (für kleines L) und 64 (für große L) beschränkt ist. In dem Fall von ISO 8348/AD2-Netzwerkadressen, für die L = 40 ist, ist der Verringerungsfaktor 24,6, was eine sehr signifikante Ersparnis an physischen Speicher darstellt.
Es sei bemerkt, daß es sein kann, daß eine Implementierung genug Speicher für eine maximale Längenweg-Komprimierungs- String für jeden Knoten zuordnen möchte, um die Speicherverwaltung leichter zu machen. In diesem Fall ist etwa zweimal so viel Speicher erforderlich, um die Wegkomprimierungs- Strings zu speichern, und Gleichung (5) wird in
(32 · L) / (32 + L) (6)
modifiziert, die eine obere Grenze von 32 aufweist, und der Verringerungsfaktor für den Fall von ISO-Adressen ist 17,8, was immer noch sehr signifikant ist.
Es sei als nächstes ein Addieren einer Zeigerkomprimierung zu einem wegkomprimierten TRIE betrachtet. Die Speicheranforderung für den schlimmsten Fall für einen wegkomprimierten TRIE ohne eine Zeigerkomprimierung wird durch Gleichung (4) angegeben. Wenn eine Zeigerkomprimierung eingeführt wird, tritt der schlimmste Fall auf, wenn so viele tatsächliche (d. h. Nicht-Nil) Zeiger wie möglich verwendet werden. Da jeder Nicht-Nil-Zeiger auf einen Knoten zeigt, tritt dies auf, wenn so viele Knoten wie möglich verwendet werden. Somit tritt der schlimmste Fall für die gleiche binäre Trie-Struktur auf, die in dem obigen Nicht-Zeiger-komprimierten Fall verwendet wurde. Die Größe jedes Nicht-Terminal-Knotens wird zwei Zeiger plus einer Bit-Maske sein. Die Bit-Maske ist sechzehn Bit breit, d. h. sie weist im wesentlichen die gleiche Größe wie ein Zeiger auf. Somit ist die Speicheranforderung für den wegkomprimierten und den Zeiger-komprimierten TEIE im schlimmsten Fall
(N-1) · 3 Zeiger + (N * L) Halboktette = (7)
N* (12 + L) Halboktette (8)
in einer guten Näherung. Bei einem Vergleich mit der Speicheranforderung nur für die Wegkomprimierung, Gleichung (4), gibt es eine weitere Verringerung in der Speicheranforderung um einen Faktor von
(64 + L) / (12 + L) (9)
mit einem Wert zwischen 1 und 5. Für den Fall von ISO- Adressen, wobei L = 40 ist, beträgt der Verringerungsfaktor 2.
Der gesamte Verringerungsfaktor für eine Weg-komprimierte und eine Zeiger-komprimierte Datenbank, verglichen mit einer Datenbank mit keiner Komprimierung, ist das Produkt von Gleichung (5) und (9). Das ist
(64 + L) / (12 + L) (10)
das durch die Grenzen von 5 für kleine L und 64 für große L beschränkt ist. Für den Fall von ISO-Adressen beträgt der gesamte Verringerungsfaktor 49.

Claims

1. Ein Verfahren zum Durchführen einer Suche reduzierter Länge durch eine gespeicherte Datenbank, die eine Baumstruktur von Knoten (110) und Zeigern (105) enthält, wobei Knoten mit Zeigern Elternknoten (parent nodes) und Targets von Zeigern Kinderknoten (child nodes) sind, wobei Zeiger auf Kinderknoten jedem einer Anzahl möglicher Werte entsprechen, die als Fragmente eines Sucharguments auftreten können, wobei aufeinanderfolgende Fragmente des Sucharguments einen den Zeigern durch die Knoten folgenden Suchweg definieren, wobei mindestens einige der Knoten (110-11) einen Ergebniswert (120) identifizieren,

gekennzeichnet durch Eliminieren eines entfernbaren Knotens (110-7), der zwischen einem unmittelbar vorhergehenden (110-2) und einem unmittelbar folgenden (110- 11) Knoten in dem Suchweg auftritt, wobei der entfernbare Knoten nur einen Kinderknoten und entweder keinen Ergebniswert oder den gleichen Ergebniswert wie seine Eltern aufweist,

wobei das Verfahren folgende maschinen-implementierte Schritte umfaßt:

Speichern von Information (125), die Bedingungen beschreibt, unter denen - wäre der eliminierte Knoten vorhanden gewesen - die Suche zu dem folgenden Knoten vorangeschritten wäre,

Folgen des Suchweges durch die Knoten,

Bestimmen, ob das Suchargument die Bedingungen der gespeicherten Information (125) erfüllt, wenn die Suche den vorhergehenden Knoten (110-2) erreicht, und

Veranlassen, daß die Suche wirksam von dem vorhergehenden Knoten (110-2) direkt zu dem folgenden Knoten (110-11) voranschreitet, wenn der Vergleich angibt, daß - wäre der eliminierte Knoten (110-7) vorhanden gewesen - die Suche zu dem folgenden Knoten vorangeschritten wäre.

2. Das Verfahren gemäß Anspruch 1, wobei der Ergebniswert, der durch den eliminierten Knoten geliefert worden wäre, gleich dem Ergebniswert ist, der durch den folgenden Knoten geliefert wird.

3. Das Verfahren gemäß Anspruch 1, wobei die Information (125) in dem folgenden Knoten (110-11) gespeichert ist.

4. Das Verfahren gemäß Anspruch 3, wobei das Suchargument eine Reihe von Suchsegmenten umfaßt, wobei jedes Segment des Arguments einem Knoten (110) entlang des Suchweges entspricht,

mindestens ein einem gegebenen Knoten entsprechender Wert eines Segments mit einem Zeiger (105) in Beziehung steht, der von dem gegebenen Knoten zu einem weiteren Knoten führt, und einige weitere Werte des Segments mit einem terminierenden Modus der Suche in Beziehung stehen.

5. Das Verfahren gemäß Anspruch 4, wobei die gespeicherte Information (125) ein gegebener Wert eines Suchsegmentes ist, der dem eliminierten Knoten entspricht, wobei der gegebene Wert ein Wert ist, der mit einem Zeiger, der von dem eliminierten Knoten (110-7) zu dem folgenden Knoten (110&supmin;11) führt, in Beziehung gestanden wäre.

6. Das Verfahren gemäß Anspruch 5, das ferner umfaßt:

ein relatives Verknüpfen einer oder mehrerer Sätze von Indikatoren (115) mit einem oder mehreren Knoten (110), wobei jeder einem gegebenen Knoten zugeordneter Indikator in einem gegebenen Satz einen Wert eines Segments des Sucharguments angibt, der dem gegebenen Knoten entspricht, der mit dem terminierenden Modus in Beziehung steht, und wobei

ein Folgen des Suchweges ein Verarbeiten aufeinanderfolgender Suchsegmente des Sucharguments umfaßt, wobei ein Verarbeiten eines gegebenen Suchsegments mit einem gegebenen Wert die folgenden Schritte umfaßt:

ein Auslesen des Satzes von Indikatoren, die einem Knoten entlang des Suchweges zugeordnet sind, der dem gegebenen Suchargument zugeordnet ist, und ein Bestimmen, ob ein Indikator in dem Satz angibt, daß der gegebene Wert mit dem terminierenden Modus in Beziehung steht, und

ein Voranschreiten zu dem terminierenden Modus, wenn ein Indikator angibt, daß der gegebene Wert mit dem terminierenden Modus in Beziehung steht, andernfalls

ein Auslesen eines von dem gegebenen Knoten, der mit dem gegebenen Wert in Beziehung steht, führenden Zeigers und ein Folgen des Zeigers zu einem nachfolgenden Knoten entlang des Suchweges.

7. Das Verfahren gemäß Anspruch 6, wobei der terminierende Modus der Suche ein Terminieren der Suche umfaßt.

8. Das Verfahren gemäß Anspruch 7, wobei

das Suchargument eine Systemadresse in einem Netzwerk umfaßt, und

die Ergebniswerte eine Leitweginformation zum Übertragen von Paketen durch das Netzwerk an eine durch die Adresse bestimmte Vorrichtung umfaßt.

9. Ein Verfahren zum Zuordnen einer Leitweginformation zu einer Paketadresse in einem verteilten digitalen Datenverarbeitungsnetzwerk, das die folgenden maschinenimplementierten Schritten umfaßt:

Speichern einer Datenbank-Baumstruktur von Nicht-Null- Knoten (110) und Zeigern (105), die jeweils von einem der Knoten zu einem anderen der Knoten führen, wobei Knoten mit Zeigern Elternknoten und Targets von Zeigern Kinderknoten sind, wobei mindestens einige der Knoten einen Ergebniswert identifizieren,

wobei ein Weg durch die Knoten, der den Zeigern folgt, durch Werte entsprechender jeweiliger Segmente der Adresse identifiziert wird, wobei jeder Wert eines Segments einen unterschiedlichen Zeiger zu einem nachfolgenden Knoten entlang dieses einen Wegs identifiziert,

Speichern von Null-Knoten (110-10, 110-17), die die Wege beenden,

Speichern, als die Ergebniswerte, von Leitweginformation in einem oder mehreren der Knoten, wobei die in einem Knoten gespeicherte Leitweginformation mit einer beliebigen Paketadresse verknüpft ist, die einen durch den Knoten führenden Weg identifiziert, gekennzeichnet durch:

Ersetzen eines gegebenen Knotens (110-7), der nur einen von dem gegebenen Knoten (110-2) zu einem nachfolgenden Nicht-Null-Knoten (110-11) führenden Zeiger aufweist und entweder keinen Ergebniswert oder den gleichen Ergebniswert wie sein Elternknoten aufweist, durch einen Weg-String (125), wobei der Weg-String den Wert eines dem gegebenen Knoten entsprechenden Segmentes speichert, der den Zeiger zu einem nachfolgenden Nicht-Null-Knoten identifiziert.

10. Das Verfahren gemäß Anspruch 9, das ferner den folgenden Schritt umfaßt:

ein Ersetzen weiterer Knoten, die nur einen jeweils von den anderen Knoten zu einem nachfolgenden Nicht-Null-Knoten führenden Zeiger aufweisen, bis keine solchen Knoten in der Datenbank verbleiben.

11. Vorrichtung (20) zum Durchführen einer Suche reduzierter Länge durch eine gespeicherte Datenbank (50), die eine Baumstruktur von Knoten (110) und Zeigern (105) enthält, wobei Knoten mit Zeigern Elternknoten und Targets von Zeigern Kinderknoten sind, Zeiger zu Kinderknoten jedem einer Anzahl von möglichen Werten entsprechen, die als Fragmente eines Sucharguments auftreten können, wobei aufeinanderfolgende Fragmente des Sucharguments einen den Zeigern durch die Knoten folgenden Suchweg definieren, wobei mindestens einige der Knoten (110-11) einen Ergebniswert (120) identifizieren, wobei die Vorrichtung einen entfernbaren Knoten (110-7) eliminiert, der andernfalls zwischen einem unmittelbar vorhergehenden Knoten (110-2) und einem unmittelbar folgenden Knoten (110&supmin;11) in dem Suchweg auftreten würde, wobei der entfernbare Knoten nur einen Kinderknoten und entweder keinen Ergebniswert oder den gleichen Ergebniswert wie seine Eltern aufweist, mit folgenden Merkmalen:

einem Speicher (220), der Information (125) speichert, die Bedingungen beschreibt, unter denen - wäre der eliminierte Knoten vorhanden gewesen - die Suche zu dem folgenden Knoten vorangeschritten wäre,

einer Steuereinheit (40) zum Folgen des Suchweges durch die Knoten,

einem Komparator (300) zum Bestimmen, ob das Suchargument die Bedingungen der gespeicherten Information (125) erfüllt, wenn die Steuereinheit den vorhergehenden Knoten (110-2) erreicht, wobei

die Steuereinheit veranlaßt, daß die Suche wirksam von dem vorhergehenden Knoten (110-2) direkt zu dem folgenden Knoten (110-11) voranschreitet, wenn der Komparator anzeigt, daß - wäre der eliminierte Knoten (110-7) vorhanden gewesen - die Suche zu dem folgenden Knoten vorangeschritten wäre.

12. Die Vorrichtung gemäß Anspruch 11, wobei der Ergebniswert, der durch den eliminierten Knoten geliefert worden wäre, der Ergebniswert ist, der durch den folgenden Knoten geliefert wird.