JPH03135668A - 圧縮された接頭語突き合わせデータベース検索方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （発明の背景） 本発明はデータベース検索に於ける接頭語突合せに関す
る。

データベースはストリング即ちキーを記憶情報と関係付
ける。データベースは与えられた入カストリング或いは
キーと関連する特定の情報を検索するためにしばしば使
用される。

成る応用例は入力ストリンゲスに最も適合する接頭語と
関連する検索情報を必要とする。例えば、ストリングｒ
ｃＡＲＴＪがデータベースに対する入力であり、データ
ベースがストリング「Ｃ」、ｒｃＡＪ及び「ＣＡＲＬ」
と関連する情報を保持する場合、「ＣＡＲＴ」に対する
最適突合せ接頭語はｒｃＡＪであり、「ＣＡ」と関連す
る情報が戻される。「Ｃ」はまたｒｃＡＲＴ」の接頭語
であり、「ＣＡ」が「Ｃ」より良い（より長い）接頭語
であることに注意。

最適突合せ接頭語検索は階層的、樹木構造を有するデー
タベースによって典型的に達成される。

データベースのこの形態はしばしばトリーと呼ばれる。

トリーデータベースは厳密な突合せ（即ち、入力ストリ
ングに厳密に等しいストリングの検索）と最適接頭語突
合せとの両方を達成することを可能にする。

第１図を参照する。他のノードに対するポインターを各
々含む多数のノード３２からトリーを構成される。各ノ
ードはｎ個のポインターの配列を有し、一つのポインタ
ーは、入力ストリングの文字で生じるｎ個の可能な文字
の各々に対応している。トリーは又根と呼ばれる単一の
ノード３３を有し、個々から検索が開始する。

ストリング例えばｒｃＡＤＪを探し出すために、検索が
トリーの根ノードで開始し、第１文字ｒ（１を根ノード
のポインターの配列に索引を付けるの使用する。「Ｃ」
ポインター３４は「Ｃ」で始まる全てのストリングに対
する情報を含むトリーの区分を指し示す。この検索はこ
の新たなノードに至り、入力ストリング内の次の文字を
、記憶されるポインターの配列に索引を付けるのに使用
される。ｒＡＪポインター３５はｒｃＡ」で始まる全て
のストリングに対する情報を含むトリーの別の区分の根
を生成する。最終的に、この検索は最終の文字ｒＡ」を
配列に索引を付けるのに使用して、「ＣＡＤ」に対応す
る実際の入力を得る。

−トリーが必要とする記憶容量は、（１）データベース
内の入力数、（２）異なる文字の数、（３）−語内の平
均文字数、（４）ポインタの記憶サイズの積に略比例し
て計算することができる。従って、（２）２６の可能な
文字、（３）項目当たり２０迄の文字、そして（４）４
バイトポインターを有する５０，０００人力登録データ
ベースに対しては、項目当たり略２にバイト、即ち１０
０Ｍバイト要求される。

この記憶容量の要請にも関わらず、トリーは高速調査及
び接頭語突合せのために魅力的である。

いくつかの有用な応用として、電話番号、オンライン辞
書、スペルチエッカ−に於ける登録簿検索、及び社会保
証番号の検索がある。

コンピュータネットワークはルータと呼ばれる装置によ
って互いに結合された多数のコンピュータから構成され
ており、コンピュータはパケットと呼ばれるメツセージ
を他のコンピュータに送ることができる。類推すると、
ルータは郵便局であり、パケットは手紙に対応する。各
パケットは宛先アドレスを運び、各ルータは宛先アドレ
スに対する最適の通路を計算する。この通路に沿う各ル
ータはパケットをこの通路上の次のルータに「前送り」
することに責任を負っている。この前送り工程は、パケ
ットがその宛先に到達するまで続（。

パケットはルータに到達すると、ルータは前送りデータ
ベース内の宛先アドレスを検索する。この前送りデータ
ベースは宛先アドレス及び各アドレスへの通路内の次の
ルータのリストを含む。

郵便システムは巨大であるので、各郵便局が世界中の全
アドレスに対する項目を含むデータベースを記憶するこ
とは不可能である。その代わりに、手紙をＷＲＩＴＥＨ
ＡＬＬ−ＬＯＮＤＯＮ−ＥＮＧＬＡＮＤに送るためには
、先ず宛先国（英国）に送り、次に都市（ロンドン）に
送り、そして宛先都市内のストリートアドレス（Ｗｈｉ
ｔｅｈａｌｌ）へおくる。従って、この郵便システムア
ドレスを３レベルの階層を有するものとして記述するこ
とができる。即ち、レベル０をストリートアドレス、レ
ベルｌを都市、レベル２を国としてである。ある理由の
ために、巨大なコンピュータネットワーク中の宛先アド
レスは階層的に分割されており、数種の階層レベルを有
している。

巨大ネットワークを構築するための一つの方法が、国際
標準委員会（ＩＳＯ）の配送基準によって記述される。

これは直ぐに、大きな広範ネットワークを建設するため
に使用される世界的な標準となるべきである。このＩＳ
Ｏ基準に従うと、各ルータは、ネットワーク内の全ての
可能なアドレスに対する配送情報を記憶することはしな
い。むしろ、部分的な配送情報を記憶する。

例えば、ルータは部分的なアドレスＤＥＣ−ＲＥＡＤ　
ＩＮＧ−ＥＮＧＬＡＮＤ　、　ＥＮＧＬＡＮＤ　、及び
ＬＯＮＤＯＮ−ＥＮＧＬＡＮＤにパケットを前送りする
最適な方法を記憶することができる。ルータはＷＨＩＴ
ＥＡＨＡＬＬ−ＬＯＮＤＯ−ＥＮＧＬＡＮＤにアドレス
付けされたパケットを得ると仮定する。

ＩＳＯ基準は、ルータは最適突合せアドレスに送られる
べきであることを宣言する。このアドレスはデータベー
ス内に存在する。従って、上記例においては、ルータが
パケットをどのようにしてＬＯＮＤＯＮ−ＥＮＧＬＡＮ
Ｄに送るのかを知っているので、パケットはここに送ら
れねばならない。この手法だと、パケットが前送りされ
る毎に、パケットはその宛先により近ずく。

世界的ネットワークに対するＩＳＯ配送基準は、ネット
ワーク内の各ルータが部分アドレスのデータベースを維
持することを規定している。パケットがルータに到達す
ると、ルータはデータベースを介して検索を行い、パケ
ット内の宛先アドレスに対する項目を呼び出さなければ
ならなく、さもなぐば、宛先アドレスの最適突合せ接頭
語に対応する項目を呼び出することを失敗する。

ＩＳＯ配送基準の特に興味のあることは、標準化のため
の国際組織によって頒布された、ＩＳＯ８３４８Ａｄｄ
ｅｎｄｕｍ　２　　（ＩＳＯ８３４８／ＡＤ２）の様な
公開システム相互接続（Ｏ８Ｉ）基準にある。この基準
の基で、Ｏ３Ｉアドレスの部分空間の管理が種々の国際
的に認知された組織に委任さてれている。

これらの組織の各々は委任された管理を示す一義的な初
期アドレスオクテツト（典型的に８ビツト）に割り付け
られている。個々の組織はアトシスの別の部分を割り振
るために責任を負っおり、他の組織による管理及び割当
のために、組織に特定な長さを有する一義的な初期的な
部分によって識別される。この工程は多数回繰り返され
、特定の指定されたノードアドレスが広く一義的である
ことを保証する。

Ｏ８Ｉネットワークアドレス（ＮＳＡＰ）フォーマット
が第２Ａ図に示されている。この図は初期区域部分ＩＤ
Ｐ６０及び区域特定部分ＤＳＰ７０を含んでいる。ＩＤ
Ｐ６０のフォーマット及び長さが標準化される。これは
、２つの部分、ＡＰＩ６２（識別子の権威とフォーマッ
ト）及びＩＤｌ６４（初期区域識別子）から成っている
。これらの要素は各々オクテツト（８ビツト）又はセミ
オクテツト（４ビツト）によって計数される特定の数の
ビットを要求する。ＡＰＩ及びＩＤＩ中の数字は２進化
コード１０進数である。各ｌθ進数は００００（１０進
０）から１００１（１０進９）の範囲内のセミオクテツ
ト値によって表せられる。

ＡＦ　Ｉ　６２は２つのセミオクテツト（即ち、２進化
コード１０進数）の長さであり、ＩＤＳ値を割り付ける
ため及びＩＤＩのフォーマットを決めることに責任を有
する権限を決めるために使用される。ＩＤｌ６４は、Ｄ
ＳＰ値が割り当てられる部分区域及びこの値を割り当て
ることに責務を有する権限を識別する。ＩＤＩフォーマ
ットに依存して、ＩＤｌ６４フイールド中の数の実際の
個数はＩＤＩフィールドに割り当てられるセミオクテツ
トの個数よりより少ない。ＩＳＯ８３４８／ＡＤ２によ
って特定される好適な２進化エンコーデイングは、ＩＤ
ｆｆに先行数が付加されることを規定して、必要な場合
は、ＡＰＩによって規定される最大のＩＤＰ長さを得る
。従って、ＩＤＩフィールドはアドレス情報を搬送する
数個の数６６、及び情報を搬送しない他の充填数６５を
含むことができる。有用なＩＤＩＤＣＣはＩＤＩフィー
ルド内で右位置が調整され、ＩＤＩフィールドの残りは
充填数６５を含む。ＡＰＩの値はＩＤＰの長さを決め、
以下に記述されるようにして有用なＩＤｒ数６６の位置
を決めるのに使用することができる。

ＩＳＯ８３４８／ＡＤ２基準で規定されるＩＤＩフォー
マットは、以下のものを含む異なる権限の数だけ発生さ
れるフォーマットを含む。

Ｘ、１２１（公衆ネットワーク番号区分）Ｉ　Ｓｏ　　
ＤＣＣ（ＩＳＯ制御化での地理的アドレス割付け） Ｆ、６９（テレックス番号区分） Ｅ、１６３（電話番号区分） Ｅ、１６４　（ＩＳＤＮ番号区分） ＩＳＯＩＣＤ（ＩＳＯ制御下での非地理的アドレス割付
け） Ｌｏｃａｌ　　（ＩＤＩが空であり、アドレスが一義的
であることを要しない。） ＩＤｌ６４はＤＳＰを管理する権限を特定する。

ＤＳＰ７０の特定のフォーマットは、最大長を除いて、
ＩＳＯによって直ちに処理されるのではなく、むしろ指
示された権限に残される。ＤＳＰはＩＤＰに類似する２
進化コード数シンタツクスを使用するか、又は直線的２
進化シンタツクスを使用することができる。ＤＳＯが２
進シンタツクスを使用する場合、ＤＰＳ値は直接２進化
オクテツトとして表現される。ＤＳＰが１０進シンタツ
クスを使用する場合、各１０進数は０ＯＯＯから１００
１（ＩＤＰにおけるように）の範囲においてセミオクッ
トによって表現される。後者の場合、必要な場合、１１
１１のセミオクテツトが、ＤＳＰの最後のセミオクテツ
トの後のパッドとして使用され、全アドレス長をオクテ
ツトの積分値に丸める。

第２Ｂ図及び第２Ｃ図は、ＡＰＩ値及びＩＤ０１ＤＳＰ
及び各ＩＤＩフォーマットに対応する全Ｎ５ＡＰアドレ
スのに要求される最大長さを指し示すテーブルである（
ＩＳＯ８３４８／ＡＤ２フオーマツトに於けるＮ５ＡＰ
アドレスにおいて、ＩＤＩが最大長に付加されているこ
とを注意すべきである。）。２つの値がＡＰＩに与えら
れており、第１のものが零（０００Ｑ）先行数を有する
最さ長に付加されるＩＤＩを識別するが、第２のものは
非零先行数（この非零付加数は値０００１で無ければな
らない）が付加されるＩＤＩを識別する。非零先行数は
、実際のＩＤＩ値の第１数がが００００に等しい時の混
乱を軽減するのに使用される。従って、非零付加数がＩ
ＤＩで使用される場合、ＩＤＩ中の第１の零敗が非充填
数で無ければならない。第２Ｂ図は、ＤＳＰシンタック
スが２進である場合に適用される。第２Ｃ図は１０進の
場合に適用される。

一例として、３６の２つのセミオクテツトＢＣＤ値は次
のことを示す。（１）宛先システムはＸ。

１２１公衆ネツトワークアドレスを使用する。（２）Ｉ
ＤＩ６４が部分区域の権限を識別する１４迄の重要なｌ
Ｏ進数からなる。（３１ＤＳＰ７０セミオクテツトは、
存在する場合、２進化コード１０進シンタツクスで宛先
装置を表現する。

ディジタル　イクイプメント、メイナード、マサチュー
セッツによって頒布される様な、デジタルネットワーク
アーキテクチュア（ＤＮＡ）に対するＤＥＣｎｅｔフェ
イズＶアドレスの最近版において、例えば、ＤＳＰ７０
は２進化シンタツクスを有し、Ｎ５ＡＰの最後の９つの
オクテツト（この内の７つはＤＳＰ内になければならな
い）は第２Ａ図において示される数種のフィールド内に
分配される。

（ＤＮＡに特定される第２Ａ図内のこれらのフィールド
には星（＊）が印される） ＬＯＧ−ＡＲＥＡ７２はＤＮＡの前の版と逆向きに互換
性を有するため及び将来の増強のために定義されたフィ
ールドである。ＬＯＧ−ＡＲＥＡ７２はＮ５ＡＰの最後
の９つのオクテツトの最小の２つのオクテツトとして定
義される。

レベルＩＩＤは６個のオクテツトフィールドであり、Ｄ
ＥＣｎｅｔ領域内の宛先システムを一義的に識別する。

ＤＮＡネットワーク配送層の正常な動作はＩＤ７４フイ
ールドがＤＥＣｎｅｔ領域内にあることのみを要求する
（レベル２ルータを除く、ここでは、レベル２ルータの
レベルＩＩＤは全構内ネットワーク内で通常一義的であ
る。）しかしながら、ＩＤフィールドは通常Ｉ　ＥＥＥ
８０２アドレス空間から通常選択され、この場合広範囲
に一義的であることが保証される。８０２アドレスが使
用される場合、これは８０２　ＬＡＮ上のノードの実際
のデータリンクアドレスに対応する場合があるが、この
対応は前記配送アルゴリズムによって仮定されたり、要
求されない。

Ｓ　Ｅ　Ｌ　７６　ハＤ　Ｅ　ＣＮ　Ｅ　Ｔ　７　ｘ　
イズＶ７ドレスの端部の一つのオクテツトフィールドで
ある。ＳＥＬはモジュールの選択として働き、このモジ
ュールはパケットがその宛先に到達する場合パケットを
受信さねばならない。ＩＤＰ６０の連結及びＤＳＰの先
行部分（即ち、これが存在する場合、ＤＳＰの部分は最
後の９つのオクテツトに先行する）はＰＲＥ−ＬＯＧ−
ＡＲＥＡ８０と呼ばれる。

ＰＲＥ−ＬＯＧ−ＡＲＥＡ及びＬＯＧ−ＡＲＥＡの連結
は領域アドレス９０として知られる（従って、領域アド
レスはＮ５ＡＰの最後の７バイト以外である）。パケッ
トが、ローカル領域のアドレスと正確に一致する領域ア
ドレス９０を有する場合、パケットの宛先は領域に対し
て局所的であり、レベルＩＩＤフィールドを使用するレ
ベル１配送によってこの宛先が搬送される。それ以外の
場合、パケットはレベル２配送によって搬送される。レ
ベル２配送は領域アドレスの接頭語部分上に機能し、パ
ケットを、パケットアドレスと最大に正確に一致する領
域アドレスを有する領域に向ける。

他方、非ＤＮＡノードはＤＮＡアドレス変換又はその要
請に従うことを要しない。しかしながら、ＤＮＡアドレ
スシンタックに対して設計されたルータは、成る要求が
満足されると、非ＤＮＡ及び非ＤＮＡネットワークに組
み入れられる。この組み入れには数々のモードが可能と
なる。

成るモードにおいては、非ＤＮＡ　　Ｅｎｄシステムは
ＤＮＡレベル２ネツトワークで作動する。

隣接のレベル２ルータは手動で適合されて、パケットが
ＤＮＡ　ｒ到達可能アドレス項目」を介してＥｎｄシス
テムに前送りされる。非ＤＮＡ　　Ｅｎｄシステムのア
ドレスの唯一の要求は、Ｅｎｄシステムのアドレスの全
接頭語が、最大１４の終端セミオクテツトを除くことに
より形成され、レベル２ネツトワーク内の全領域アドレ
スから区別される必要があることである。

特定のＤＮＡ領域内のＥｎｄシステムとして、非ＤＮＡ
ノードのアドレスは、最後の７オクテツトの前の先行オ
クテツトがノードが存在する領域の領域アドレスに等し
くなければならないと言う制限を受けなければならない
。更に、最後の７つのオクテツトの先行する６つのオク
テツトが領域内の一義的なレベルＩＩＤから構成される
必要がある。隣接するルータの構成は、ＥＳ／ｌ５（Ｉ
Ｓｏ　　９５４２）プロトコルを介して手動又は自動に
より発生する。

最後に、ＤＮＡネットワークは、アドレス接頭語を使用
して、到達可能なアドレスを介して非ＤＮＡの自立性ネ
ットワークと解釈される。

ネットワーク内の配送は前送りデータベースに基づく。

前送りデータベースにおいて、各リストされた宛先アド
レスは、パケットがその宛先に到達するのに取る配送通
路の次のリンク及びこのリンク上のアドレスを互いに参
照する。

データベースは２つの部分に分けられる。ｉ）ネットワ
ークアドレスを内部索引に対応させる部分、及びｉｉ）
内部インデックスをリンク及びリンクアドレス要素の組
に対応させる部分。

ネットワークルータは、宛先アドレス情報を受信された
パケットのヘッダーから受は取り、データベースにアク
セスして、パケットが通過する最適な次のリンク及びそ
のリンク上のデータリンクアドレスを決定し、そしてパ
ケットをこれを従って前送りする。

公知のデータベースのフォーマットは、パケットが前送
りされる速度に影響し、データベースの記憶容量を大き
くすることできる。

（発明の要約） 本発明の従うと、配送データベースは同一の機能に対す
る従来のデータベースより領域が狭い。

更に、配送情報は、より安価な計算ハードウェアを使用
してより高速に位置される。

本発明の一つの特徴は、減少された長さの検索通路に沿
った検索を管理する方法である。検索通路内の前の及び
次のノード間で発生しうるノードが除去される。除去さ
れたノードが存在すると仮定した場合に、検索が次のノ
ードに進むか否かに関する情報が記憶される。この検索
の間、検索引き数は記憶された情報と比較され、この検
索は、この比較が正である場合、前のノードから次のノ
ードに効率的に進行する。

好適な態様は次の特徴を含む。幾つかのノードは検索に
対する結果値を与える。ノードは、その存在が検索に対
する結果値に影響を及ぼす場合に除去される。比較され
るべき情報は次のノード内に記憶される。この検索は第
１及び第２のモードを有しており、第１のモードは検索
路に沿って処理ノードを有している。除去されたノード
は、もし存在すれば、検索を次のノードに進ませるか、
検索を第２モードに導入するの何れかを行う。この検索
引き数は一連の検索セグメントから成り、前記引き数の
セグメントの成る値は検索通路に沿ったノードに対応す
る。このセグメントの他の値は検索の第２モードに関係
する。記憶された情報は前記検索セグメントのシーフェ
ンスである。標識はノードに関連する。検索路は連続す
る検索セグメントを処理することにより検索される。こ
の処理は各ノードに関連する標識を検査し、標識がセグ
メントが第２モードに関連することを示す場合第２検索
に進むことを含む。検索の第２モードは前記検索を終了
することを含む。検索引き数はネットワーク中のシステ
ムアドレスを含む。

本発明の他の特徴は減少された長さの２つのモード検索
を管理する方法である。検索の第１モードに対して、検
索路に沿ったノードが与えられており、ノードの少なく
とも幾つかが他のノードを指し示す１つ以上のポインタ
を含んでいる。一連の検索セグメントを含む検索引き数
が与えられ、引き数のセグメントの幾つかの値が検索路
の沿ったノードに対応する。セグメントの幾つかの他の
値は検索の第２モードに関連する。ノードに関連する標
識が設けられ、セグメントを指示する各標識が第２モー
ドに対応する。検索路は、各ノードに関連する標識を検
査し、セグメントが第２モードに関連するすることを標
識が示す場合第２検索モードに進むことによって連続す
る検索セグメントを処理することにより検索がなされる
。

好適な実施態様は以下の特徴を有する。前記セグメント
が第２検索モードに対応することを標識が指示しない場
合は、標識及びセグメントが検査され、一つのポインタ
を決定する。この検索は次のモードに続く。各標識は、
複数のセグメント値にそれぞれ関連する数列内の１ビツ
トである。検索の第２モードは検索を終了することを含
む。検索引き数はネットワーク内のシステムアドレスか
ら成る。

本発明の別の特徴は検索路を階層的に検索する方法にあ
る。検索路に沿ってノードの階層が与えられ、ノード少
なくとも幾つかが、別の階層的レベルの他のノードを示
している１つ以上のポインターを含んでいる。一連の検
索セグメントから成る検索引き数が与えられ、引き数の
連続セグメントが検索路に沿って連続するノードに対応
する。

検索路はノード内の連続する検索セグメントを処理する
ことにより検索され、ポインターを検査し、検索引き数
が有効な状態を満足する場合、指示されたノードに進む
ことを含む。

好適な態様は以下の特徴を含む。有効な状態は処理され
た又は未処理のセグメントの数を計数することを含む。

検索引き数は１３０　８３４８／ＡＤ２とに従うコンピ
ュータネットワークに対するシステムアドレスである。

検索は第１階層レベルにおけるレベル２配送検索及び第
２階層レベルにおけるレベルｌ配送検索からなる。検索
は第１階層レベルにおけるＩＤＰ検索及び第２階層レベ
ルにおけるＤＳＰ検索を含む。

本発明の別の特徴は、幾つかが所定の値を有するセグメ
ントの検索引き数を分析する方法にある。

検索路に沿ってノードが設けられ、少なくとも幾つかの
ノードが後続のノードを示す１つ以上のポインターを含
み、各ポインターはセグメントの一つの可能な値に対応
する。所定のセグメント値に対応するポインターは、ノ
ードがポインターを後続のノードとして記憶しているこ
とを指示するように向けられている。

好適な態様は以下の特徴を含んでいる。検索引き数はＩ
ＳＯ８３４８／ＡＤ２に関連するネットワークアドレス
であり、所定の値が充填数の値である。

本発明の別の特徴は、コンピュータネットワーク配送用
トリー形状配送データベース、種々の形態のトリー記憶
データのノードを記憶するための装置である。この装置
は異なるアクセス時間及び電力要求を有する複数のメモ
リー装置を含み、各装置は２つ以上のノードに対して特
定の形態のデータを記憶する。メモリー装置は、類アク
セス時間を有するメモリー装置内に高速アクセスを要求
するデータ形態を記憶し、それ以外の場合、低電力消費
を有するメモリー装置内により遅いアクセスを要求する
データ形態を記憶するように選択される。

本発明は記憶空間、処理時間及びハードウェアを節約す
る。

他の利点及び特徴は以下の好適な実施態様及び特許請求
の範囲から明らかになるであろう。

（実施例） 乳産又グ皇罫 トリーはＩＳＯルータ内の部分アドレスのデータベース
を維持するための適当な候補者である。

トリーは宛先アドレスの最適突合せ接頭語を容易に支持
する。更に、トリーはＩＳＯ部分アドレスの様な大きな
及び可変長ストリングを検索するために好適である。し
かしながら、トリーの記憶要求は実現不可能な実際のル
ータ内のトリーを利用する。又、ＩＳＯアドレスに対し
てトリーを適用するために、トリー検索方法がＩＳＯア
ドレスの特定の特徴、例えば上述された可変長フィール
ド及び充填数に適用されねばならない。

本発明はトリーデータベースの記憶要求を減少し、また
ＩＳＯアドレスに対してトリーを採用する。本発明によ
って達成された記憶容量の減少は付録Ｃに詳述される。

トリー要求記憶容量を減少するための方法は好適な態様
の外の種々の状況におけるトリーに適用できる。トリー
検索をＩＳＯアドレスに適用するための方法は他の状況
でも利用できる。

第３図を参照する。ルータ１０の第１欠勤作において、
パケット１１は受信ユニット１２に受信される。受信ユ
ニット１２はパケットを前送りエンジン１４に与える。

前送りエンジンＩ４はパケットヘッダーを処理する。宛
先ネットワークを抽出し、これを認識エンジン２０へ転
送する。論理ユニット２２は前送りエンジン１４によっ
て使用される論理信号を与え、認識エンジン２０とイン
ターフェースで接続する。認識エンジン２０は宛先アド
レスを使用して、インデックスをメモリー５０内に記憶
されるデータベースから呼び出す。

このインデックスは前送りエンジン１４に戻され、この
エンジンはその値を使用して前送りデータベース（図示
せず）をアクセスする。前送りデータベースはリンク参
照及びリンクアドレスの組からなる。前送りエンジン１
４は次にリンク参照を使用してパケット１１を種々の転
送ユニット２６Ａから２６Ｄ（４つが説明のために示さ
れている）の一つに向ける。転送ユニット２６Ａ及び２
６Ｄはパケットを待ち行列化し、それらをネットワーク
に通信リンク１６を介して他のルータ又は宛先システム
に送る。

アドレス識別エンジン２０において、フェッチユニット
３０は前送りエンジンＩ４からパケット宛先アドレスを
受信し、アドレス又はこのアドレスの特定の部分を検索
ユニット４０に与える。検索ユニット４０はフェッチユ
ニット３０によって与えられるアドレス又はアドレス部
分を使用して直接メモリー５０にアクセスする。メモリ
ー５０からフェッチされた中間結果は検索ユニット４０
によって処理され、フェッチユニット３０によって与え
られたアドレスと関連して中間結果をにアクセスし、結
果的に最終結果を得る。この最終結果は検索ユニット４
０によって前送りエンジン１４によって戻され、このエ
ンジンはこの結果を前送りデータベース（図示せず）の
インデックスとして使用する。

他の動作モードにおいて、データベースは管理エンジン
１８によって使用することができる（付録Ｂを参照）。

管理エンジン１８はメモリー５０内に記憶されるデータ
ベースを生成し、それを維持するための責務を有する。

管理エンジン１８は連続的な基礎の上の現在のネットワ
ークの接続性に関する情報を、図示されていない通路を
通して受信する。管理エンジン１８は、ネットワーク接
続性情報から発生されるアドレス部分を検索ユニット４
０に与える。この検索の結果は戻されてエンジン１８を
管理する。このエンジンはこの結果を使用してデータベ
ース内の現在の情報を学習する。データベースを更新す
る必要があり、それが現在のネットワーク接続性を正し
く表現する場合、管理エンジン１８は直接メモリー５０
をアクセスしてその変化を達成する。

本発明の背景技術において述べられた様に、ルータｌＯ
はレベルｌ及びレベル２配送を達成する能力を有さねば
ならない。レベル１配送はフェッチユニット３０によっ
て与えられるネットワーク宛先アドレスの厳密な一致が
データベース内にあることを要求する。実現されるべき
厳密一致を可能にする多数の公知のデータベース構造が
ある。

レベル２配送は、しかしながら、厳密な一致が見出され
ない場合は、ネットワーク宛先アドレスの最も長い接頭
語であるデータベース内の項目が位置されるべきことを
要求する。この要求は使用することのできる異なるデー
タベース構造の数を制限する。

本発明において、メモリー５０内に記憶されるデータベ
ースはトリーとして知られる樹木構造の特定の形態であ
る。第４図はトリー構造データベースの如き部分の一例
である。トリーの各ノードは他のノード１１０に対して
１６のポインターの配列を有している。トリーの根から
の他のノードへの遷移は、検索引き数（例えば、ネット
ワーク宛先アドレス）をセグメント数列（例えば、セミ
オクテツト）に分解することによって達成される。

トリー内の各ノードにおいて、この数列内の次のセミオ
クテツトは、零から１５までの値を有しており、１６の
ポインターの一つを選択するのに使用される。

第３図を参照する。現在ノードレジスタ４１は検索中に
横断するトリーのノードを示す。検索が開始されると、
現在ノードレジスタ４１がトリーの根のポイントに設定
される。検索引き数のセミオクテツトへの分解において
、形成されたセミオクテツトは前で議論されたＮ５ＡＰ
の構成数に対応する。

第４図を参照する。ポインターを有するノード１１０は
親ノードと呼ばれる。ポインターの目標は子ノードとな
る。他のノード（例えば、ノード１１０−８．１１０−
９及び１１０−１１）に対するポインターを含まないト
リー内のノードは「ターミナルノード」と呼ばれる。検
索がターミナルノードに到達する時、検索を終了する。

この検索は、次のセミオクテツトポイントが空ノード１
１５を指し示す場合も同様に終了する。（第３図の数個
のノードが空結果値を含むが、明瞭のために、多くの他
の空ノードが除去されている。）ターミナルノードに検
索引き数円のセミオクテツトの全てを使用して到達する
と、厳密一致がデータベース内に位置し、ターミナルノ
ードは、検索引き数に対応する結果値１２０を保持する
。しかしながら、セミオクテツトの数列の全てが使用さ
れる前に、空ノード１１５に到達するか、又はターミナ
ルノードに到達すると、検索対象の厳密一致がデータベ
ース内に含まれない。

検索対象の接頭語はデータベースに含まれことが可能で
ある。この場合、検索中に横切られるノードの少なくと
も一つのノードは結果値１２０を保持する。横切られた
ノードは結果値（例えば、ノード１１０−１３で終了す
る検索）を含まない場合、データベース内にこのような
接頭語は存在しない。結果値を保持する複数ノードが横
切られる場合、検索対象の複数接頭語がデータベース内
に含まれる。第１のこの様な横切られたノードは最も短
い接頭語に対応する結果を保持し、最後に横切られたこ
の様なノードは最も長い接頭語に対応する結果を保持す
る。最も長い接頭語に対応する結果は検索の結果として
戻される。

多くの場合に、子ノード及び親ノードに対する結果値１
２０は同じである。これらの場合（例えば、ノード１１
０−５及び１１０−７）　、子ノードは結果値１２０を
保持しない。検索が、結果値１２０を含まない子ノード
で終了する場合、結果値を有する最も最近横切られた前
のノードの結果値１２０が戻される。この様にして、デ
ータベースに記憶される接頭語は、単一のみのノードで
導入された対応する結果値を有しており、保守を簡略化
している。

以上の記述は、トリー構造データベースがどの様にして
所与の検索引き数の厳密一致又は最適接頭語一致を検索
工程が達成するのに使用できるかを概説した。データベ
ースの圧縮の２つの形態は本発明の好適な態様で使用さ
れて、トリー構造を支持するのに必要とされるメモリー
量を減少する。

これらはポインター圧縮及び通路圧縮として知られてい
る。

第５図を参照する。ポインター圧縮は空ノードの全て及
び空ノードに対するポインターの全てをトリーから除去
して達成される。これは、ポインタービットマスク１１
５をトリー内の各親ノードに関連することにより行われ
る。ビットマスクはどの子ノードが空であるか、即ち、
どのポインター１０５が空ノードを示すのかを指示する
。マスク内の各ビットは、親ノードポインターの一つに
対応し、且つこのポインター目標ノードが非空である場
合に設定され、その他の場合クリアーされる。

例えば、根ノード１００はビットマスク１１５０に関連
する。２つの非空子ノード１１０−１．１１０−２は根
ノード１００以下に存在する。従って、根ノードビット
マスク１１５−０は２つのｒｌＪ　ビットを含み、それ
ぞれ非空子ノードに対応する。マスクの全ての他のビッ
トは「０」であり、根ノードの全ての他の子ノードは空
ノードであることを示している。

第５図を第４図と比較することによって、これらの２つ
の「１」ビットの位置が２つのポインターの位置に厳密
に対応することが分かる。動作において、子ノードに移
動する前に、検索ユニット４０が親ビットマスク１１５
をチエツクして新たなノードが非空であることを決定す
る。新たなノードが空の場合、新たなノードに移動する
ことなしに直ちに終了する。

ここで、第５図を参照する。全ての空ノード（及び空ノ
ードを示すポインター）はトリーから除去されて記憶領
域を節約する。全トリーに対して一つのみの空ノードを
記憶することが必要となる場合があるので、メモリー節
約は空ノードに対するポインターの除去の結果である。

ポインター比較により、トリー構造データベースに必要
とされるメモリーが減少できるが、現在ノードアドレス
の計算がより複雑になる。新たなノードのアドレスを決
定するために、検索ユニット４０は親ビットマスク１１
５を参照して、ポインター１０５の数及び配布を決定し
なければならない。ビットマスクが、数列内の次のセミ
オクテツトに対応するポインターが存在することを示す
場合、ビットマスクか、親ノード内に記憶されたポイン
ターのリスト内の要求されるポインター１１５の位置を
決定するのに使用される。

通路圧縮を導入するために、先ず、ポインター圧縮は空
ノードを及び空ノードに対するポインターを除去するが
、根ノードから所与の結果ノード塩の通路長（即ち、ノ
ードの数）は減少しないことに注意する。通路圧縮はこ
の様な減少を達成するのに使用される。

通路圧縮はデータベース内の各ノードを除去する。この
データベースは（１）一つのみの子ノード、及び（２）
非結果値又は親ノードと同じ結果値を有する。第５図の
ノード１１０−７はこれらの要求を満足する。第６図を
参照する。通路圧縮の後、ノード１１０−７が除去され
、ノード１１０−１１はノード１１０−２の直接下であ
る。

本発明の好適な態様に於いて、（一つ以上の）除去され
たノードに対応するセミオクテツトが通路圧縮数ストリ
ング１２５として記憶される。

（第１図において、ストリングは単一数の長さである）
。動作において、検索ユニット４０は通路圧縮数ストリ
ング１２５の番数を検索対象の連続するセミオクテツト
と比較する。次のノードに進むためには、全ての比較が
同等であることを示さねばならない。ある比較が失敗す
ると、検索は、通路比較数ストリング１２５の直前を横
切るノードで終了する。通路比較をこの様にして実施す
ることにより、トリーデータベースは検索対象に対する
最適接頭語を探すのに使用できる。これは、スキップさ
れたセミオクテツトが処理されない場合は可能ではない
。

好適な態様において、通路数ストリングは子ノードに記
憶される。ストリングが子ノードに存在する場合、スト
リングは、子ノードに到達するために検索対象の後続の
セミオクテツトに連続的に突き合わされる。ストリング
突合せが失敗すると、失敗は空ポインターが親ノードで
選択されるかの様に取り扱われる。

この工程は、ノード１１０−２と１１０−１１との間の
通路数ストリング１２５の挿入によって第６図内に図示
される。ノード内の通路数ストリングの存在がそのノー
ドのフラッグビットによって示される。このフラグがセ
ットされると、ノードは関連する通路数ストリングを有
する。セットされないと、ノードはこの様なストリング
を含まない。第６図に示される様に、フラグビットはノ
ード１１０の各々に含まれる。

従って、ポインター圧縮及び通路圧縮はトリー構造デー
タベースに必要とされるメモリーを減少するが、非圧縮
データベースと同じ機能を正確に許容する。

上述された最適化されたトリー構造は成る補強を伴って
、ＤＥＣＮＥＴフェイズＶ配送の状況のＯ８Ｉネットワ
ーク宛先アドレス（ＮＳＡＰ）を正しく処理することを
可能する。この記述された機構は、厳密な一致及び入力
アドレスの最大接頭語一致を見出すことのできる検索に
対して設けられる。これらの機構は、１）ＩＤＰよりも
より短い記憶アドレス接頭語を、先行有効ＩＤＩ数が記
憶された接頭語の有効ＩＤＩ数に等しいアドレスに一致
することを可能にし、ｉｉ）領域アドレスの認識を許容
して、レベル１データベースへの遷移を指示するために
補強されねばならない（ネットワークアドレスは長さが
可変であるので、記憶された領域アドレスが入力アドレ
スの先行セミオクテツトと突き合うことが、突合せ領域
アドレス以後に正確に１４個のセミオクテツトが残って
いるという要求を入力アドレスが満足することなしに可
能となる。）。

第１補強に対する要求を図示する例として、データベー
ス内に記憶される接頭語３７−１２３を記憶する。この
例において、ＡＦ　Ｉ　　ｒ３７Ｊは、ＩＤＰ長が１６
数（即ち、ＩＤＩ長が１４数）であることを示している
。ハイフンの後に続く数、即ちｒｌ　２３ＪはＩＤＩの
先行有効数である。例えばフェッチ３０によって与えら
れ、そのＡＰＩが「３７」に等しく、先行有効ＩＤＩ数
がｒ１２３」に等しい全アドレスは、接頭語３７−１２
３の認識を示すトリー内のノードを横切らばならない。

フェッチ３３０で与えられる以下の３つのアドレスを考
える。

（ｉ）　　　３７０００００００００１２３４５６７８
９ａｂｃｄｅｆ（ｉｉ）　　３７００００００００００
０１２３４５６７８９ａｂ（ｉｉｉ）’３７０００００
０００００００１２３４５６７８９ａｂｃｄｅｆ第１ア
ドレスがｒ１２３４５Ｊに等しい有効ＩＤＩを有してい
る。第２アドレスはｒｌ　２３Ｊに等しい有効ＩＤＩ数
を有している。第３アドレスは「１２」に等しい有効Ｉ
ＤＩ数を有している。

従って、第１及び第２アドレスは接頭語３７−１２３を
含み、第３アドレスは含まない。上記接頭語３７−１２
３を含むアドレス内のＩＤＩ　（零と１１の間）内に付
加数が幾つでも存在することができるので、改良されな
いアドレス認識トリーは接頭語３７−１２３に対して１
２の異なる分岐を有する。各々の分岐は異なる数の付加
数（零から１１の範囲内）を表しており、接頭語３７−
１２３に対応する結果がラベルされた異なるノードに先
行する。しかしながら、この構造は、不格好であり、メ
モリーをより必要とする。

接頭語３７−１２３を記憶する好ましい方法は、全ての
ＩＤＩ付加数を捨て去ることの出来るものとして取り扱
うことである。次に、接頭語３７−１２３に対応する結
果を記憶するノードはセミオクテツト数列３．７．１．
２．３の後に到達する。好ましい態様においては、パッ
ド数は容易に捨て去られ、トリーの基本動作は変化しな
い。異なる子ノードではなく、親ノードを指し戻すポイ
ンター１０５をＩＤＩ付加数が選択するようにトリーを
構成することによってパッド数は捨てられる。

（この自己参照の結果として、ＩＤＩの第１数に対応す
るノードは関連する通路圧縮数ストリングを有すること
ができない。） さらに改良することなしに、上に挙げられた側内の第３
のアドレスは、−度ＩＤＩ付加数が捨てられると、通路
３．７、■、２．３に沿って伝達し、接頭語３７−１２
３を含むことを間違って示す。これを克服するために、
２つの機構が基本トリーに加えられる。ｉ）カウンター
、入力検索アアドレスの残りのＩＤＩ数の計数を保守す
る残りＩＤＩ長カウンタ４３（第３図）、及び１ｉ）１
７個のポインター、これはＤＳＰと呼ばれ、ＩＤＩの数
を表す親ノードからＤＳＰの第１数を表す子ノードを指
し示す。ＩＤＩ長カウンタが零に減少される時、１７ポ
インターがアクセスされる。

作動において、ネットワーク宛先アドレスの検索中、ア
ドレスの第２セミオクテツトを処理した後到達するトリ
ー内のノードに対応するＩＤＩ長である。ＩＤＩ長が記
憶されたことが、付加フラグビットによって示される。

検索ユニット４０はフラグがセットされ、ノードに記憶
されるＩＤＩ長を読み、これをＩＤＩ長カウンタ４３に
転送することを認識する。セミオクテツトが検索ユニッ
ト４０（ＩＤＩの付加数を含む）によって処理される時
毎に、ＩＤＩ長カウンター４２が１だけ減少される。Ｉ
ＤＩ長は零まで減少され、全ＩＤＩが処理される。この
点で、１７（即ちＤＳＰ）ポインターが現在ノードで選
択される。ＡＦＩ値が４８又は４９である場合、ＩＤＩ
が存在しない。

従って、これらＡＦＩ値に対応するデータベース内のノ
ードは、ＩＤＩ長が零であり、データベースのＤＳＰ区
域内への瞬間遷移に対する１７番目のポインターを提供
せねばならない。

別の例が、領域アドレスの認識に関連して、基本トリー
の第２補強の必要性を例示している。ルータが領域アド
レス４７１２３３４００００００００ａｂｃｄによって
定義されるＤＥＣＮＥＴで作動することを考える。第２
Ａ図及び第２Ｂ図を参照すると、この領域アドレスの異
なるフィールドが以下の如く認識される。

次に、以下の３つのネットワーク宛先アドレスがフェッ
チユニット３０によって検索ユニット４０に与えられる
（ネットワークを伝播するパケットから取り出される）
。

（ｉ）　　４７１２３４００００００００ａｂｃｄ０１
２３４５６７８９ａｂＯＯ（ｉｉ）　４７１２３４００
００００００ａｂｃｄ０１２３４５６ｆｆ（ｉｉｉ）４
７１２３４００００００００ａｂｃｄＯ１２３４５６７
ｆｆ８９ａｂ００第１アドレスの先行数が、ルータが所
在する領域の領域アドレスに厳密に一致する。残り数は
２つのフィールドとして解釈される。即ち、（ａ）アド
レスのＤＥＣＮＥＴレベルＩＩレベ分である１２セミオ
クテツトフイールド０１２３４５６７８９ａｂ、及び（
ｂ）ＤＥＣＮＥＴ　　ＳＥＬフィールドのセミオクテツ
トフィールドＯＯである。従って、第１アドレスが抜き
取られたパケットは、この領域内のＥｎｄシステムに対
して宛てられたものと見做されるべきであり、ＤＥＣＮ
ＥＴレベルｌ配送によって配送されるべきである。レベ
ルＩＩＤの厳密一致がデータベース内で見出されで、パ
ケットが正しい終了システムに前送りできるようにすべ
きである。

第２のアドレスの先行数はまたルータが存在する領域の
領域アドレスと厳密に一致する。残りの数が試験される
時、９個存在する。従って、残りの数はレベルＩＩＤ部
分足すＳＥＬ部分として解釈することはできず、従って
、特定の宛先アドレスを含むパケットは、ルータが存在
する領域内の終了システムには宛てられない。宛先アド
レスの先行数と領域アドレス間での偶発的な一致が無視
されねばならない。全アドレスの最長接頭語はレベル２
データベース内で探されねばならなく、パケットはレベ
ル２配送で配送される。

同様に、第３の例のアドレスの先行数は厳密に領域アド
レスと一致する。ここで、残りの数ストリングはレベル
ＬＩＤ部分足すＳＥＬ部分として解釈するには長すぎる
ので、この一致が無視されねばならない。再び、全アド
レスの最長接頭語がレベル２データベース内で探さねば
ならなく、パケットはレベル２配送で配送される。

上記３つのアドレスの検索がトリーデータベースで有効
な時、有効アドレスとの一致に対応するデータベース内
のノード化及びこれを越えてこれらアドレスが同じ通路
を通ることは明らかである。

上述された様に、第１アドレスは、−度領域アドレスと
の一致が発生すると、異なる通路を通ることが必要とな
る。この地点で、分岐は、全レベル１アドレスを保持す
る論理的に分離したデータベースであるサブトリーを構
成せねばならない。

レベル２データベースからレベル１データベースへの分
岐を許容するために、別の１８番目のポインターが各ト
リーノードに加えられる。１８番目即ち「レベル１」ポ
インターを使用するために、２つの付加的な機構が基本
トリーに加えられる。

（ｉ）現存する長さレジスタ（第３図のＣＲＬ　４２）
内のカウンタ及び比較器であり、これらは、検索対象の
残りの正確に１４のセミオクテツトであることを示す。

及び（ｉｉ）各ノードに記憶される付加フラグビットで
あり、これは、領域アドレス（即ち、ルータが存在する
領域の領域アドレス）に厳密に一致した後到達するトリ
ー内のノードのみにおいてセットされる。このフラグビ
ットは「レベルｌ遷移可能ｊビットとして参照される。

全検索対象の長さ（即ち、構成セミオクテツトの数）が
、それが前送りエンジン１４によって初めてフェッチユ
ニット３０に与えられる時に、ＣＲＬレジスタ４２にロ
ードされる。アドレス自体の部分でないが、アドレスの
長さがＩＳＯ８３４８／ＡＤ内で規定されたパケットヘ
ッダーに含まれる。ＣＲＬレジスタ４２は、セミオクテ
ツトが検索ユニット４０で処理される時に一度減少され
る。

レベルｌ遷移可能ビットがセットされ、且つＣＲＬレジ
スタに厳密に１４のセミオクテツトが残っている場合の
み、１８番目のポインターが選択される。１８番目のポ
インターの子ノードがレベルｌデータベースの根ノード
である。検索対象からの次のセミオクテツトは、レベル
１データベースへの遷移の後迄は使い尽くされないこと
に注意すべきである。

作動において、レベル１データベースへの遷移が、ネッ
トワーク宛先アドレスの検索中に発生する場合、アドレ
スを含むパケットがルータが存在する領域内の終了シス
テムに宛てられる。上述されたように、厳密一致が宛先
アドレスのレベルＩＩＤ部分に対するレベルｌデータベ
ースに見出されねばならない。即ち、レベル２データベ
ースの初期の横切りの間得られる前の「最適接頭語」は
、レベルｌ内のへの遷移が一度発生すると、重要でな（
なる。厳密な一致がレベル１データベース内に見出すこ
とができない場合は、パケットは、その宛先アドレスが
存在しないので、廃棄されねばならない。レベル１内で
の検索から戻される結果は従って厳密突合せに対応しな
ければならず、その他の場合は、空の結果が戻されねば
ならない。

第７図に戻る。部分データベースの４つのノードが図示
され、本発明に従うデータベースを通しての検索の漸進
の一例として使用される。この例において、通路圧縮が
使用され、ポインター圧縮は使用されない。

検索は次の様にして漸進される。アドレス検索はノード
１１０−Ａに到達する。通路及びＩＤＩフラグは到達し
た際にチエツクされる。両フラグがノード１１０−Ａ内
で「０」にセットされないので、ノード１１０−Ａは特
定の処理を必要としない。従って、検索は次のセミオク
テ・ソトを使用してポインターの配列に索引をつけ、子
ノードに進む。この例において、フェッチされたセミオ
クテツトは値７を有している。それで検索ユニット４０
はポインター７を使用してノード１１０−Ｂへ移動する
。

ノード１１０−Ｈに到達した際に、検索ユニット４０は
、通路ストリングフラグが「０」であり、従って、ノー
ド１１０−Ｂが関連する数ストリングを有さないことを
知る。しかしながら、ｒＩＤ■」フラグは「１」である
。これはノード１ｌＯ−Ｂが、ｔＤｌフィールドの長さ
を含むＩＤＩ情報１３０を含む。（従って、全ての可能
性において、ちょうど処理されたセミオクテツトｒ１ｊ
が第２ＡＰＩの数であると想定することができる。）検
索ユニット４０はこの情報を回収し、この値をＩＤＩ長
さレジスタにロードする。このレジスタは次にセミオク
テツトが処理された時毎に一度減少される。次のセミオ
クテツト（ＩＤＩフィールドの第１数）がフェッチされ
、検索が進行される。

この例の検索において、検索路に対するＡＰＩは、ＩＤ
Ｉ充填数が１０進値０に等しいことを規定する。充填ビ
ットを無視するために、セミオクテツト値００００に対
応するノード１１０−Ｂ内のポインターがノード１１０
−Ｂを指し示す。従って、ＩＤＩ充填数が処理されて、
ＩＤＩ長さレジスタが零に減少されない限り、検索はノ
ード１１０−Ｂを離れない。検索は、非充填（非００（
１０）の数が分析された後のみにノードを通常離れる。

検索が順次従う成る通路に於いて、通路ストリングフラ
グがセットされるノード１１０−Ｄに検索が到達するこ
とがある。これは、ノード１１０−Ｄが通路数ストリン
グ１２５を含むことを示している。ノード１１０−Ｄで
処理が更に行われる前に、検索ユニットは、通路数スト
リング１２５を回収し、ストリングの要素を検索ユニッ
トに与えられる次のセミオクテツトと比較する。全数ス
トリングが連続的に比較された後のみに、検索はノード
１１０−Ｄを更に処理する。

更に処理が行われている際、検索ユニットは、結果フィ
ールドは値ｘｙｚを含み、今までに処理されたセミオク
テツトが、配送情報と関連する接頭語であることを示し
ていることを発見する（接頭語は結果値ｘｙｚと関連す
る）。結果値ｘｙｚは検索ユニットによって記憶される
。検索中に別の結果に遭遇しない場合、値ｘｙｚが検索
結果として戻され、この関連する接頭語が、この特定の
検索引き数に対するデータベース中に記憶された最適接
頭語であることが示される。

その後、検索ユニットは、ＤＳＰフラグが設定されるこ
とを発見する。これは、ノード１１０−Ｄが、データベ
ースのＤＳＰ区域内を指し示す非空１７番目のポインタ
ーを有する。（実際の実行の際は、ＤＳＰフラグビット
は、明示的ビットよりも空及び非空ＤＳＰポインターを
使用することにより実行さる。）ＩＤＩ長さレジスタが
厳密に零に減少された場合及びその場合のみに、この１
７番目のポインターがアクセスされる。この場合、検索
はデータベースのＤＳＰ区域内で続行する。

ＩＤＩ長さが零に減少した場合、検索対象の次のセミオ
クテツトがノード１１０−Ｄの第１の１６ポインターの
一つを選択するのに使用される。

検索が従う他の通路において、検索はノード１ｔｏ−Ｃ
に到達する場合がある。ノード１１０−Ｃにおいて、レ
ベルｌフラグがセットされる。これは、以前に処理され
た検索引き数のセミオクテツトがルータ（即ち、このデ
ータベースが含まれるルータ）が存在する領域の領域ア
ドレスに厳密に一致することを示す。この点でもし、検
索引き数の残りに１４のセミオクテツトが存在すると、
検索引く数がこのＤＥＣＮＥＴ領域内の終了システムの
アドレスとして見做され、従って、１８番目のポインタ
ーがノード１１０−Ｃで選択され、検索がレベル１サブ
トリーで再開される。

従って、各ノードは数種のフラグ及びあり得る情報片を
含んでいる。各ノードは（ポインター圧縮が使用される
所で）１８ビツトポインタービツトマスク、後続のノー
ド（又はそれ自体）に対する１６個のポインター、ＤＳ
Ｐポインター、レベルＩポインター、通路圧縮ストリン
グ及びその長さ表示、結果情報、及びＩＤＩ長さ情報を
含むことができる。

毘阻呈説」 検索ユニットの特定の実施例がここで記述される。要求
によって、容易に利用可能な最小数の部品を使用し、又
消費される電力を最小にするように設計される。

最小数の容易に利用可能な部品を使用するという要求に
悩まされる。通路圧縮及びポインター圧縮の技法を介し
てメモリーの使用を最小化することが上述された。実行
の観点からこれらの技法を見ると、通路圧縮が実行され
ねばならず、ポインター圧縮は実行されてはならないこ
とが決定されることがある。ポインター圧縮は必要とさ
れるメモリー量の減少を可能にするが、成るメモリー管
理工程によって管理される小片に、メモリーが分解され
ることが要求される。付加的なオーバーヘッドは、ビッ
トマスクを読出し且つデコードする予備の論理回路、マ
スクの有効ビットを累積する多重レベルハードウェア、
及び圧縮されたベクトルのブロックのアドレス上でこの
累積値を加算する付加的な加算器を有している。

このオーバーヘッドは、余分な制御論理回路の使用を要
求するばかりでなく、この余分な論理回路が全サイクル
の臨界通路内にあるので、機械の潜在的なサイクル時間
を減少する。ポインター圧縮を除去することによって、
制御論理回路が大幅に簡略化され、サイクル時間が改善
される。さらにこのメモリー増加は、ポインター圧縮が
効果を有する迄は部品の総数を増加しない。特により大
きなデータベースを用いる別の方法は、かなりより大き
なメモリー使用量を要求する場合がある。

この様な別の要求下では、ポインター圧縮を有効に使用
することができるかもしれない。

認識エンジンは、ここではｒＷｉｄｇｅｔ−２」システ
ムに適合して設計される。このシステムは小さな３スロ
ット背面基板を有しており、この内の一つはアドレス認
識エンジン（ＡＲＥ）の形態に対応するものである。背
面基板バスは、特にホスト６８０２０モトローラ社製の
マイクロプロセッサのためのものであり、３２アドレス
ビツトでなく、２４のみのアドレスビットを有している
。

バスのタイミングは、バスインターフェースロジックを
簡単化するために、ＣＰＵに比例してスローダウンされ
る。機能的な要求がこのことを指示する場合、ＣＰＵが
ＡＲＥをアクセスする時に２つの待ち状態（２００ｎ　
ｓ）以下を依然として保証する。

最大のフレキシビリティ−を可能にするため、装置は検
索を初期化するための８つの異なる根ノードを支持する
。特有の根ノードが、異なるアドレスフォーマットを検
索するため又は−級化された検索の種々の形態を達成す
るために選択されることができる。

中央部品 第３図を参照する。認識エンジン２０のメモリーに必要
な４つの基本部品、及び同時に作動する多数のレジスタ
及び基本状態マシン（検索エンジン４０として正確に知
られている）がある。４つの中央メモリ一部品が以下に
記述される。

ＤＲＡＭポインターメモリー 認識エンジン２０のコアーは、ノードポインターメモリ
ー及び「現在ノード＋現在数→次のノード」検索ユニッ
ト４０から成る。第８図を参照する。ポインターメモリ
ーは少数の制御論理によって支持されるＤＲＡＭメモリ
２００の配列によって実現される。１６ビツト状態ベク
トル（即ち、ライン２０２によって運ばれるノードアド
レス）及び（ライン２０４によって運ばれる）４ビツト
数が１ＭＸ１６（２０ビツト×１６ビツト）の様に構成
されたＤＲＡＭメモリーを要求し、実現されるべき６４
にの状態を可能にする。これは、（「次の状態」の子ノ
ードを有さない）３２に空ノード及び次の状態を有する
３２に非ターミナルノードが存在することを主張するこ
とにより、実際、認識されるべき少なくとも３２にアド
レスを可能とする。その時多くの物理メモリーの半分の
み、即ち、１メガバイト（５１２ＫＸ１６として構成さ
れる）のみが必要とされる。このサイズのＤＲＡＭ配列
２００が８チツプ（２５６ＫＸ４）チップのみ又は（メ
モリー技術のルックアヘッドを使用して）４チツプ（１
ＭＸ４）のみを必要とする。

基本マシンは、ＤＲＡＭ２００を最高速度でサイクルす
る。この速度は所定のアドレスに対する検索時間に大き
く影響する（現在サイクルに対するデータが変化し始め
た後の次のサイクルに於けるＤＲＡＭアドレスを発生す
るのに時間があると仮定してでのことであるが、次のＤ
ＲＡＭアドレスは、本質的に４ビツト数を有するビット
ポインターデータと連結しているので、これは容易に達
成できる。） ノードは従ってライン２０２上に運ばれた１６ビツトに
よって決められる。アドレスの最上位ビットは零に等し
いとすると、ノードが（次のポイ］５．・ターを有さな
い）終点であると（この実行で）で決められるが、他の
場合は、終点でない（即ち、次のポインターを有する）
とされる。

高速ステチックＲＡＭ 全６４にノードは（次のノードに対するポインターに加
えて）より早（言及された予備情報を提供する必要があ
る。この情報を供給するためには、高速６４ＫＸＬ６ス
タチツクＲＡＭ２１０はＤＲＡＭポインター２００によ
って同時にアクセスされる。スタチックＲＡＭは現在の
ノードについての以下の情報を与える。

−ＮＩＬ（空）フラグ：ノードが空（且つ処理が一時停
止）される場合セットされる。

−通路ストリング二通路ストリングがノードに記憶され
る場合、非零長がＳＲＡＭ内に記憶される。

一結果フラグ：ＡＦＩが行われ（且つノードがＩＤＩ長
を含む）場合、セットされる。

レベル−１フラグニレペルー１遷移可能（ＤＥＣｎｅｔ
領域がこのノードで認識される）この情報の物理メモリ
ーへのマツピングは、「メモリーマツプ」ヘッディング
の基で、以下で詳細に説明される。

通路数ストリングメモリ 通路数ストリングメモリー２２０はＤＲＡＭポインター
配列２００によって同時にアクセスされる。ストリング
記憶空間は６４にノードの各々に割り当てられる。各ノ
ードに記憶される数の個数は高速スタチックＲＡＭ２１
０内に記憶されるストリング長によって示される。ノー
ドに記憶できる数の最大個数はノードのアドレスによっ
て決められる。３つの異なる最大数がある。４８数、１
６数、又は零敗である。ライン２０２上のノードアドレ
スはどの最大値が有効であるかを示す。この指示は部分
的に結線により及び部分的に論理プログラムにより行う
ことが可能であり、物理メモリーの量を最小にする様設
計される。

本実施例は、４にノードで４８個の数の記憶及び５２に
ノードで１６個の数の記憶をサポートする。８にノード
はストリング記憶空間を有さない。

必要とされる全メモリーは５１２Ｋ又は４　（ＩＭＸｉ
）チップである１Ｍ個の数である。再び、次世代の４Ｍ
ＤＲＡＭを使用すると、単一のチップのみが必要とされ
る。

本発明に従うと、ノードアドレス（１６ビツト）及びス
トリング数カウンタ（６ビツト）をＩＭＸ４ＤＲＡＭア
ドレスライン（２０ビツト）上にマツプする技術が使用
される。実際上、マツピングはノードアドレスラインの
関数として変化する。

これは「メモリーマツプＪとして題される以下のセクシ
ョンで更に詳述される。

ＤＳＰポインターメモリー ＤＳＰポインターメモリー２３０はＤＲＡＭポインター
配列２００で同時にアクセスされる。

「遷移ノード」　（ノードアドレスＭＳＢが１に等しい
所）として知られるノード３２にのみがこのメモリーに
アクセスすることができる。このメモリー要求は従って
３２ＫＸ１６であり、２つのみのチップと等しい。ノー
ドにアクセスされるＤＳＰポインターは、ＩＤＰの終わ
りが認識された時、即ち、ＣＲＬカウンタが零に減少し
た時のＩＤＩ検索の後にのみに使用される。

制御論理 ＡＲＥに対する中央論理の中央部品が以下に記述される
。

タイミング発生器（図示されない）は、メモリー配列の
正しいシーフェンス、即ち、ＲＡＳ及びＣＡＳ制御、リ
フリッシュタイミング、サイクル対サイクル制御等に対
して責任をおっている。

フェッチユニット２８０．２９０は、要求に基づいて検
索ユニットにアドレスのセミオクテツトを供給する責任
を追っている。このセミオクテツトは、ホストＣＰＵに
よって（この場合）レジスタファイル２７０へ供給され
る検索アドレスの順序で引き出される。セミオクテツト
は検索エンジンに与えられて、そのタイミング発生器と
同期する。インターロックが与えられる。この場合、検
索エンジンが、ホストＣＰＵがまだ供給していないセミ
オクテツトを必要とする時、検索エンジンはセミオクテ
ツトが準備されるまで停止される。

同時操作を行うことのできる３つの数カウンタがある。

現在残余長（ＣＲＬ）カウンタ２４０には、ＣＰＵによ
って認識レジスタに最初にそれが与えられた時、全検索
引き数のセミオクテツト長がロードされる。このカウン
タは、数が検索エンジンによって消費（処理）された時
毎に１減少される。

カウントがゼロに到達する場合、それは、検索が終了し
なければならないことを示す。

ＣＲＬカウンタ２４０はサイクル制御器（図示されず、
以下のサイクル制御器の記述を見よ）へライン３１０上
に信号が送られる。厳密の１４個の検索引き数が、レベ
ル−１遷移のために残される。

残余ＩＤＩ長ＩＤＩＬカウンタ２５０には、（ＤＥＣＮ
ＥＴフェイズＶ配送明細で規定されるように）ＡＦＩ値
によって指令されたＩＤＩ長がロードされる。ローディ
ングが、ノード（第２ＡＦＩ数に直ぐ続くノード）で設
定された制御ビットの命令下で発生する。このカウンタ
は、数が検索エンジンで消費された時、１減少される。

このカウント値が零に到達すると、次のマシンサイクル
はＤＳＰ遷移サイクルである必要がある。ＩＤＩＬカウ
ンタの値は、新たな検索がスタートする時毎に−６４に
リセットされる。この値−６４は「長さがロードされな
い」ことを示す。

ＡＲＥは任意のデータベース内で任意のワードを検索す
るのに使用することができ、ＩＤＩＬカウンタをロード
することが必要でないことに注意（ロードされない場合
、ＤＳＰ遷移は発生できず且つ発生しない。） ストリング数カウンタ２６０は、ノードに入った際は常
に零にリセットされる。カウンタは、ストリング数比較
サイクルである全マシンサイクルの終わりに増大され、
従って、このカウンタは、ノードが定数ストリングが記
憶されている場所に到達されるまで、零にリセットされ
続ける。長さＮのストリングがノードに記憶される場合
、ストリング数カウンタはその値を零からＮ−１へ増大
し、（比較が成功したと仮定すると）８個ストリング数
比較サイクルが発生する。ストリング数カウンタが値Ｎ
に到達すると比較は最早行われない。

カウンタは次のマシンサイクルで零にリセットされる。

サイクル制御器（図示せず）は、検索エンジンの中央イ
ンテリジェントであると見做すことができる。これは、
現在マシンサイクルに付いての情報及びバス３３０上の
ノード制御ワードから制御情報を検査する。サイクル制
御器は、現在のサイクルをどのようにして継続するか（
即ち、ストリング数を比較するか、他のサイクルに対す
るポインターを選択するか、又は停止するか否か）、他
のマシンサイクルを開始するか否か、そしてその場合新
たな数及び／又は新たなノードアドレスを使用するか否
かを決定する。サイクル制御器はまた信号を種々のレジ
スタ及びカウンタに発生する。

状態レジスタ２４５．２４８は最も最近横切られた接頭
語（即ち、現在までの最適接頭語）のノードアドレスを
セーブし、且つ有用な過去の履歴、特に、ＤＳＰ及び／
又はレベル１遷移が生じたか否か、「現在までの最適接
頭語」がロードされたか否か、残余ＩＤＩ長レジスタ２
５０がロードされたか否かをセーブするのに使用される
。

ホストＣＰＵアクセス送受信器２５２．２５４．２５８
．２６２は、ホストＣＰＵがメンテナンスのためにＡＲ
Ｅの内部メモリーにアクセスすることを可能にする。検
索エンジンによって採用される同時オペレーションはこ
の目的のために使用不能となる。ホストＣＰＵに対して
、メモリーは集団として、［プログラマ−に友好的な」
構造及びアドレスマツプとして意図される単一データベ
ースとして表れる。この構造において、特定のトリー構
造に関連するデータの全てが、同一基準で構成されたデ
ータ構造内に表れる。

ＡＲＥに対する機能的インターフェースＡＲＥに対して
基本的に３つの機能的インターフェースが存在する。

１、検索インターフェース−パケット送り；２、検索イ
ンターフェース−メンテナンス；３、メンテナンスイン
ターフェース； これらの内の第１のものは単純である。これはＡＲＥを
構成するための第１の理由と考えられる。

このモードにおいて、ネットワークを横切るパケットか
ら除去された前送りアドレス（及び／又は他のアドレス
、例えばデータリンクアドレス）はＡＲＥへ与えられる
。ＡＲＥはそのアドレスのルックアップを行って、前送
り情報を前送りエンジン（この場合、前送りエンジンは
ホストＣＰＵである）へ戻す。

第２及び第３の機能は両者ともメンテナンスに関係して
いる。メンテナンスに対する検索インターフェースはパ
ケット前送りに対する検索インターフェースと類似して
いる。この場合において、ＡＲＥに与えられるアドレス
は完全アドレスであることを必要とされない。通常、ア
ドレスの部分は、データベースに対してどの様な構造的
変化がエントリを付加し、削除し、又は改良するために
要求されるかを決めるために、存在する。ＡＲＥの作動
的振る舞いに対する若干の改良が、メンテナンス検索が
アドレス意味の微妙な違いをうまく処理するために使用
される。

メンテナンスインターフェースは検索を行わない。実際
、検索エンジンはこのモードにおける作動を禁止してい
る。ＡＲＥ内のアドレス、データ、及び制御通路は完全
に再構成されて、ＡＲＥの初期メモリーがホストＣＰＵ
に対して可視的であるようにされる。ＡＲＥの各メモリ
ー成分は、検索エンジンでなく、ＣＰＵアドレスライン
をデコーディングすることによりアクセスされる。

検索を行う目的のためのＡＲＥに対するＣＰＵインター
フェースは、その検索がパケットを前送りするか、デー
タベースを検査する目的であれば機能的に同じである。

このインターフェースは直接メモリーマツプ制御、ステ
ィタス及びデータレジスタにより支持される。制御レジ
スタはＡＲＥの作動モードが制御されることを可能にし
、スティタスレジスタはアドレス付与手段及び検索結果
を読出す手段をＡＲＥに与える。

制御レジスタは以下の制御を与える。

■、検索モード又はメンテナンスモードの選択、２、ア
ドレスフォーマットモード（結果の解釈に影響する） ３、（メンテナンス検索に対する）レベル−１遷移を禁
止する。

４、　Ｄ　Ｓ　Ｐ遷移（メンテナンス検索）に対する■
ＤＰを禁止する。

５、検索が完了するまでポール又は停止を選択する。

６、　Ａ　ＲＥメモリーの制御パリティ−保護。

■、検索エンジン（リセット、検索、−時停止）の状態
。

２、検索エンジンに対するアドレスの状態データレジス
タが８つのブロックに分割される。

各ブロックは８つの根ノードの一つにおける検索開始に
対応する。ブロックは機能的に同じである。

（８つ根ノードの幾つかは、検索の異なる形態に対して
使用されるデータベースを開始し、他のものは、例えば
、アドレス検索データベースのレベル−１分岐の開始に
対応することができる）。レジスタブロックは６４バイ
トのサイズであり、第２の３２バイトは第１の３２バイ
トの別名であるである（即ち、同じ物理メモリーを使用
する）。

−ブロック内の３２物理バイトに関して、２４バイトま
でが、検索されるべきＡＲＥヘアドレスを書き込むため
に使用することができる。第１バイトは供給されるべき
アドレスの全長の長さの指示でなければならない。（こ
のフォーマットは、ｌ８０８３４８／ＡＤ２からネット
ワークを横切るパケットを直接引き抜くことを可能にす
る。）何れのの別名にアドレスが書き込まれるかの選択
が、長さバイトが、オクテツトで測定された又はセミオ
クテツトで測定されたアドレスの長さとして解釈される
かを決める。オクテツト長さは、■５Ｏ８３４８／ＡＤ
２からの直接引き抜きを可能とする。セミオクテツト長
は検索されるべき任意の長さの接頭語を可能にし、メン
テナンス検索に対して特に有用である。（この実施例に
おける）検索できる最大長さアドレスは２３オクテツト
又は４６セミオクテツトである。

検索動作は、検索アドレスの最初の４つのオクテツトが
書かれると直ぐに開始される。４から８のオクテツトを
、これらがＣＰＵによって書き込まれるまで、検索エン
ジンが使用することをインターロック機構は禁止する。

同様に、インターロックが４つのグループ内の残余のオ
クテツトに対して与えられる。４つのオクテツトが、Ａ
ＲＥが３２ビツトデータインターフエースを有している
ので、１書き込み動作によって書き込まれることに注意
する。全長さ中に４つのオクテツトの集合が必要とされ
る場合、長さバイトを含む検索アドレスには任意のデー
タが付は加えられる。検索結果は検索エンジンによって
、検索アドレスがＣＰＵによって書き込まれるのと同じ
ブロック内に書き込まれる。検索エンジンのスティタス
がＣＰＵによって（スティタスレジスタ２４８を使用し
て）監視され、検索結果が正しいことを決められるか、
又は、インターロックが作動して、この結果が正しくな
るまで結果を読み出す時にＣＰＵが停止されるようにす
る。

検索結果は８バイト群である。この群は次のフィールド
に分けられる。

■、要約（ｌバイト） ２、現在までの結果（２バイト） ３、現在までの取得（２バイト） ４、内部カウンタ値（３バイト） 要約バイト検索成功又は失敗の急速な検出を達成する。

検索が成功の場合は、パケット前送りモードにおいて、
現在までの結果が、全必要な前送り情報を与える遠隔テ
ーブル（即ち、認識エンジンの外部）内へインデックス
を与える。検索失敗の場合において、特にメンテナンス
検索の場合、要約が失敗の理由を指示する。他のフィー
ルドが十分な情報を与えて、所望の場合ＣＰｔＪによっ
て容易に且つ迅速にＡＲＥデータベースが更新されるこ
とを可能にする。更に、これらレジスタ及びその説明の
詳細は付録Ｂに与えられる。

ＣＰＵは検索エンジンを（「検索」モードでなく）、１
ビツトを制御レジスタに書き込むことにより、「メンテ
ナンス」モードにすることかできる。

メンテナンスモードにある場合、検索エンジンは機能し
なく、前に得られた全スティタス（データベースに対す
るものを除いて）が失われる。このモードにおいて、Ａ
ＲＥの内部メモリーの全てがＣＰＵアドレス空間の成る
部分にマツピング（対応）される。アドレス空間のこの
部分は、検索エンジンがメンテナンスモードになるまで
、アクセルできない。（これは、内部メモリー及びバス
に対する仲裁を大幅に簡略にし、最小部品総数の目標と
一致する） メモリーマツプ このマツピングは６４にの連続ノードとして構成される
。各ノードは２５６オクテツトのサイズである。従って
、メモリーによって張られる全仮想空間は１６Ｍバイト
である。各ノードのメモリーマツプが第９図に示される
。種々の部分を構成する物理的メモリ一部分が括弧内に
示される。

このメモリーマツビッグ手法において、ｍの（第９図に
示される）オフセットを有するノードＮ内のリソース（
資源）はＣＰＵ供給アドレスによってアドレスされる。

Ｎ＊２”８＋ｍ；即ち、ｍが続くＮの濃度。

幾つかの厳密なルールが、第９図のマツピング手法によ
って補強される。このルールは、１．８０００の１６進
数よりも少ないアドレスを有する全ノードは終端ノード
である。通路数ストリングは同じ終端に記憶される。他
のノードへの遷移は、終端ノードでは全く許されていな
い。

２、４８セミオクテツトまでの通路数ストリング記憶に
対する設備を有する４にノードが存在する。これらのノ
ードの半分が終端ノード（ノード７８００−７の１６進
数）であり及び他の半分が遷移ノード（ノードｆ　８０
０−ｆ　ｆ　ｆ　ｆの１６進数）である。これらのノー
ドが、データベース内のレベル２エントリを記憶するた
めに先ず与えられる。

３、１６セミオクテツトの通路数記憶に対する設備を有
する５２にノードが存在する。これらのノードの半分が
終端ノード（ノード１０００−７７ｆｆの１６進数であ
る）及び他の半分が遷移ノード（ノード９０００−ｆ７
ｆｆの１６進数）である。これらのノードが、レベル−
１エントリ、データリンクアドレス及びデータベース内
の１６のセミオクテツトを除く全長の他のエントリを記
憶するために与えられる。

４、　通路数ストリング記憶に対する設備を有さない８
にノードが存在する。これは、何が１６セミオクテツト
に対する記憶となることを諦め、メモリーを４８セミオ
クテツト記憶を有する４にノードに割り当てる結果であ
る。これらのノードは、例えば、ＩＤＰカウント値がノ
ード内に位置される場所のノードに対して使用すること
ができ（且つストリング記憶が従って許可されない）、
若しくは定数ストリングが存在しない場所のノードに対
して使用することができる。

５、単一のレベル−１ポインターが存在する。これは、
全遷移ノードに於いてアクセス可能である。

ポインターはデータベースのレベル−１分岐の根に対す
るポイントにセットされるべきである。

ＡＲＥに・する作動理論 本発明に従う検索に対する動作の基本理論がここで記述
される。開始を検索する前の正しいデータペーストリー
構造をＣＰｔＪが構築すると仮定する。

第８図を参照する。レジスタファイル２７０は、ＣＰＵ
がＡＲＥに与える検索アドレスを保持し、ＣＰＵに返還
されるべき結果を保持するために必要なメモリーを提供
するのに使用される。レジスタファイル２７０は２重の
ポートを有し、ＡＲＥ及びＣＰＵによって同時にアクセ
スすることを可能にしている。これは機能を向上し、任
意の制御論理の必要性を除去する。

検索は、ＣＰＵが検索引き数をレジスタファイル２７０
内へ書き込む時に開始される。特に、ＣＰＵが長いエン
トリの第３オクテツト（これは全ロングワードの書き込
みと通常同時に発生する）を書き込む時、ハードウェア
フラグがセットされて、関連するロングワードが正しい
データを含むことを指示する。同時に、選ばれたブロッ
クは、正しい根ノードで検索を開始するために呼び出さ
れ、このブロック内で使用される別名物が呼び出されて
、第１オクテツトがオクテツト又はセミオクテツト長と
して正しく解釈できるようにする。

６つの「準備」フラグが存在し、ブロック内の最初の６
つのロングワードの各々に対応する。プラグは２つの方
法の一つでクリアーされる。ＣＰＵは、メンテナンスモ
ード命令によって−（及びこのモードを検索モードに次
に戻すことにより）これらフラグを陽にクリアーするす
るか、又はＣＰＵが検索引き数に新たな検索引き数を重
ね書きする。第１０ングワードを重ね書きすると、ＡＲ
Ｅシステムリセットが発生されるが、第１０ングワード
「準備」フラグセットは残される。後者の方法は、制御
オーバーヘッドを殆ど又は全く有さないて多重検索を可
能にする。

レジスタファイル２７０の周辺の制御論理２９０はフラ
グを試験して、ロングワードを（これが、準備されてい
て、即ち正しい場合）一対のプログラム可能な論理配列
内に構築されるマルチプレクサ２８０へ配送する。マル
チプレクサ２８０の出力はデータのセミオクテツトをバ
ス２０４上の検索エンジンへ遅り、「データ準備」指示
を発生する。「データ準備」が（検索エンジンがファイ
ルを空にできるのど同じ様にはＣＰＵはファイルを充填
することができないと言う理由で）停止した場合は、検
索エンジンが同様に停止する。レジスタファイル制御論
理は、検索エンジンからライン２８２上の「次の数」信
号を探す。そして、このレジスタファイル制御論理は、
次のセミオクテツトをマルチプレクサ２８０の出力バス
に送る。

「準備」フラグの同期は各ロングワードの８つのセミオ
クテツトへのシリアル化と並列に発生する。

このパイプライン技法は同期化のオーバーヘッドが完全
に補償されることを可能する。

レジスタファイルブロック内の第１オクテツト（即ち、
最小アドレスを有するオクテツト）がＣＲＬレジスタ２
４０に配送される。その長さは（セミオクテツトでなく
）オクテツト長として解釈されるべきである場合は、そ
の値は２倍されて、ＣＲＬレジスタ２４０が常にセミオ
クテツトカウント数を保持する。第２及び次のオクテツ
トは全てセミオクテツトマルチプレクサ２８０へ送られ
る。マルチプレクサ２８０に導入する各オクテツトに対
する、最上位４ビツトが最初に出力され、最下位４ビツ
トがこれに続く。各セミオクテツトがセミオクテツトバ
ス２０４で正しい時、制御論理２９０はライン２９２上
に「準備」を信号する。

ライン２８２上の次の数信号が主張される場合及び時に
、ＣＲＬレジスタ２４０は１だけ減少され、セミオクテ
ツトが消費される。セミオクテツトの全てがセミオクテ
ツトデータバス（ライン２０４）上に出力された後、セ
ミオクテツト発生器論理は、もはやセミオクテツトが存
在しない場合でも検索エンジンに「準備」をライン２９
２上で示す。

「次の数」がライン２８２上で制御論理２９０に与えら
れると、未定義のデータがセミオクテツトデータライン
２０４上に送られる。しかしながら、このデータは、「
残余長がゼロＪ　　（ＲＬＥＱＯ）であることをライン
２８４上に示すことにより適切なものとされる。

「データ準備」が、セミデータバス２０４上に第１のセ
ミオクテツトに対して示されると直ぐに、第１のマシン
サイクルがスタートする。このサイクルは、正しい数を
セミオクテツトデータバス２０４に与え、正しいノード
アドレスをノードアドレスバス２０２に与えるこきによ
り開始される。

第１のマシンサイクルに対するノードアドレス（即ち、
根ノードアドレス）は、０から７のブロックの何れに検
索アドレスがロードされるかによって決められる、８０
００から８００７　（１６進数）の８つの値の内の一つ
である。

マシンサイクルはＤＲＡＭサイクルに等しい。

マスタークリスタル発振器周波数はサイクル時間を最小
にするように選択されるが、最悪の場合の状態下での正
しいＤＲＡＭ動作を補償する。この時間はマシンサイク
ル当たり約２０８ナノ秒である。

一般の場合のマシンサイクルが考慮される。この一般の
場合は極めて高速のマシンサイクルを含む。レジスタフ
ァイルの不当に遅いロードによって引き起こされる、（
「データ準備」が無視されたことによって指示される）
次の数を得るための遅延がない場合、マシンサイクルは
、遅れなしに、バックに対するバック（ｂａｃｋ　　ｔ
ｏ　　ｂａａｋ）を実施する。近似的に１５マイクロ秒
毎に、マシンサイクルは、ＤＲＡＭ配列をリフレッシュ
するに寄与する。このリフレッシュサイクルの期間検索
は進行しない。

マシンサイクルの始めに、現在ノードアドレスはノ・−
ドアドレスバスに送られる。そして、現在検索アドレス
数が数データバスに送られる。同時アクセスが以下のメ
モリーに対してなされる。

１、次のノードポインターがポインターＤＲＡＭ配列２
００からフェッチされる。

２、　Ｄ　Ｓ　ＰポインターがＤＳＰポインタースタチ
ックＲＡＭ２３０からフェッチされる。

３、次のストリング数が通路数ストリングＤＲＡＭ配列
２３０からフェッチされる。

４、ストリング／ＩＤＩ長及び制御ビットが高速スタチ
ックＲＡＭ２１０からフェッチされる。

次のノードポインター及びＤＳＰポインターが、レベル
−１ポインターデータレジスタ３４０が行うのと同様に
、両方ともノードデータバス２０６に対して競合する。

制御論理は、どの競合物がバス上に利用可能になるかを
決める（以下を見よ）。

次のストリング数がバス２０８上で使用可能になり、（
ストリング数が存在しない場合でさえ、）バス２０４上
の現在検索数と比較される。この比較は比較器３００に
よって達成される。ライン３０２上の「数一致」信号に
よって示される比較スティタスが制御論理に対して利用
可能とされる。

高速スティタスＲＡＭからフェッチされる制御情報は、
マシンサイクル内で比較的早く、約６０ｎｓに、利用可
能になる。この時まで、付加的な情報が、検索エンジン
内のレジスタ及び制御回路から利用可能になる。この付
加的スティタスは以下のものを含む。

１、ＣＲＬ＝１４（ライン３１０）：１４のセミオクテ
ツトが残り、レベル−１遷移可能な場合。

２、ＣＲＬ＝０（ライン２８４）：最後の数が使用され
た場合。

３．１ＤＩＬ＝０（ライン３１２）：ＩＤＩＬが零に減
少されるか、又はＩＤＩＬに零がロードされる場合。

４、ｒＩＤＩがロードされた」　（ライン３１４）：Ｉ
ＤＩが充填数ループノードに再ロードすることを禁止す
る場合。

５、「ストリングが消耗した」　（ライン３１６）：ス
トリング数カウンカ２６０内の値が、高速スタチックＲ
ＡＭからの（バス３２０で運ばれた）「ストリング長」
に等しいこと、ストリングが記憶されていない場合、両
方の値が０であることを示す。

上記のスティタスピットを設定することは、高速スタチ
ックＲＡＭ２１０からのバス３３０上に運ばれたノード
制御情報と共に、何が、このマシンサイクルの第２の半
分で発生するかを決める。

基本的に、マシンサイクルは４つの形態の一つである。

１、ストリング数比較サイクル（ストリングサイクル）
、 ２、レベル−１遷移サイクル（レベル−１サイクル）、 ３、ＤＳＰ遷移に対するＩＤＰ　（ＤＳＰ＋ｌ−イクル
）、４、正常の次のノードポインタサイクル（ポインタ
サイクル）。

形態２．３、及び４は全体として「正規サイクル」とし
て呼ぶことができる。検索エンジンが新たなノードに進
まない以外は「ストリングサイクル」について異常でナ
イ。

サイクルの形態がどの様にして決められるかの以下の記
述が、逐次的な形態により与えられる。

この検索エンジンがこれらの決定を同時に行う。

「ロードＩＤＩ長」　（バス３３０上のノード制御）が
主張され、（ライン３１４上で）ｒＩＤＩがロードされ
た」が誤りの場合、ＩＤＩ長がこのレジスタ内にロード
され、ｒＩＤＩがロードされた」が主張される。レジス
タ内容が零であり、ｒＩＤＩがロードされた」が主張さ
れた場合は常に、（ライン３１２上で）ｒＩＤＩ長＝０
」が主張される。

「ロードＩＤＩ長」が無視された場合、ストリング比較
が必要とされる。「ストリングが消耗した」　（ライン
３１６上）が主張された場合、これは「正常サイクル」
であり、他の場合はこのマシンサイクルは通路ストリン
グ数比較サイクルである。後者の場合、次の数及びＤＳ
Ｐポインターが無視される。マシンは、「数一致」フラ
グ（ライン３０２上）が有効なまで待機する。（約ＩＳ
Ｏｎｓの後）次に、それが無視される場合、「ストリン
グ一致」が主張される場合、「次の数」　（ライン２８
２上）がセミオクテツト発生器から要求される。ストリ
ングカウントレジスタ２６０は増大され、ＩＤＩ長レジ
スタ２５０及びＣＲＬレジスタ２４０が減少される。マ
シンは現在のサイクルを終了し、ノードアドレスバス２
０２上の値を変化することなしに次のサイクルをスター
トする。

ストリング比較サイクルは、数の不一致が存在するまで
、又は「ストリングが消耗した」がライン３１６で主張
されるまで続いて、全数が連続して一致することが示さ
れるか、もしくはｒＣＲＬＯ」が（不一致であると考慮
される）ＣＲＬカウンタ２４０によってライン２８４上
で発生されるまで続く。

「ストリングが消耗した」がライン３１６上で主張され
た時は常に、ストリングカウントレジスタ２６０は次の
マシンサイクルにおいて、（既に零であっても）零にリ
セットされる。

「ストリングサイクル」は、「ストリングが消耗した」
がマシンサイクル中に主張された場合は発生しない。こ
れは、「ストリングが消耗した」は（１）ノードに通路
数ストリングが存在しない時、又は（２）現在ノードが
既に連続して一致した時のみに主張されるためである。

「ストリングサイクル」「ロードＩＤＩ長レジスタ」が
主張されている場合に発生しない。これは、ノードに記
憶されたＩＤＩ長が存在するからである（これは、ＩＤ
Ｉ遷移が発生した時、メモリー内の単一のフィールドが
長さ情報を記憶されるために与えられ、このフィールド
がＩＤＩ長を記憶し、及びストリング長を記憶出来ない
からである。） 「正常サイクル」は３つの潜在的次ノードアドレスの一
つを３つの源、次のポインター、ＤＳＰポインター及び
レベル−１ポインターから選択する。この選択は板のル
ールに従う。

（ａ）　ｒ　Ｉ　Ｄ　Ｉ長−〇」がライン３１２上で主
張される場合、ｒｌＤＩがロードされた」がライン３１
４上で主張され、ＤＳＰ遷移が広範に可能になり、ｒＤ
ｓＰサイクル」が選択される。メモリー２３０からアク
セスされるＤＳＰポインターの値は、次のノードのアド
レスになる。単一の「ＤＳＰサイクル」のみが、この検
索操作中に許容される。これは、検索エンジンが無限ル
ープ内で張りつくことが禁止される。

（ｂ）　（ａ）が当てはまらなく、ｒＣＲＬ＝　１４Ｊ
がライン２３０上のカウンタ２４０によって主張され、
「レベル−１遷移」が広範に可能になる場合、レジスタ
３４０からのアクセスされたレベル−１ポインターが次
ノードアドレス源となる。この場合、サイクルは「レベ
ル−ｌサイクル」である。再び、「レベル−１サイクル
」のみが検索操作ごとに許容される。

（ａ）又は（ｂ）の何れかが適用される場合、次のマシ
ンサイクルは、「次の数」をセミオクテツト発生器から
フェッチすることなしに、走りだす。即ち、同じ数は、
レベル−１又はＤＳＰ遷移が発生される毎に再検査され
る。（ａ）又は（ｂ）のいずれも適用されない場合は、
ポインターＤＲＡＭ配列２００からアクセスされた「次
のノードポインター」は次のノードアドレス源であり、
即ち、このマシンサイクルは「ポインタサイクル」であ
る。この場合、「次の数」はライン２８２上でセミオク
テツト発生器２９０に発生され、次の数が次のマシンサ
イクルの始めで利用可能となる。ＣＲＬレジスタ２４０
及びＩＤＩＬレジスタ２５０は両方とも減少される。

「正常サイクル」に対して、以下のルールが同様に適用
される。最上位ノートアドレスビットが零に等しい場合
、又はｒＮＩ　ＬＪフラッグがセラとされる場合、この
マシンサイクルは現在検索引き数（即ち、検索される現
在ネットワークアドレス）である。［セーブ現在ノード
アドレス」がセットされる場合、現在サイクルのノード
アドレスは（これが空ノードでない場合のみ）「現在ま
での結果」レジスタ２９５内にセーブされ、前の値に重
ね書きされる。

「ストリングサイクル」に対して、又は「ポインタサイ
クル」　（即ち、検索数が吸収するマシンサイクル）に
対して、ｒｃＲＬ＝ｏ」がライン２８４が主張される場
合、現在マシンサイクルが最終となる。「ストリングサ
イクル」の場合において、ストリング不一致が宣言され
る。「ポインターサイクル」の場合において、現在ノー
ドが宣言され、検索アドレス上でなされる最大の増進を
表す。信号ｒｃＲＬ＝０．＋がｒＤＳＰサイクルＪ又は
「レベル−１サイクル」中に主張される場合、適当な遷
移は、それがセミオクテツトデータバス２０４上に存在
すべき正しいセミオクテツトを必要としないので、依然
として行うことができる。

データベース内のエラーはマシンによって識別すること
ができ、早期エラー終了を引き起こす。

以下のエラーが認識される。

１、パリティ−チエツクエラー３００によって検出され
る、現在セミオクテツト及び現在通路数ストリング間の
パリティ−エラー ２、エラーが「ポインターサイクル」中に発生する場合
の（即ち、このメモリーからのデータが次のノードアド
レスとして使用されるべき時の）パリティ−チエツク素
子３０２によって検出される、ポインターＤＲＡＭ配列
２００内のパリティ−エフ− ３、ストリング長カウンタ２６０が「ストリングサイク
ル」中の合法的範囲を越えて増加される時、マシンがサ
イクルを停止する毎に、ｒＢＵｓＹ」スティタスビット
がクリアーされ、検索結果がＣＰＵによって読むことが
できる。付録Ｂは検索結果の形式及び内容を詳述する。

ＡＲＥに・する機能予測 検索時間 ＡＲＥの機能が比較的容易に予測する。検索時間は検索
引き数的の数の個数にマシンサイクル時間を掛けたもの
に略等しい。幾分かのオーバーヘッドがこの見積に加え
る必要がある。

１５ミリ秒毎に、■マシンサイクルがＤ　ＲＡＭ２００
．２２０をリフレッシュするのに走らされる。単一のこ
の様な「余分」のサイクルが、検索毎に期待することが
できる。更に、数が吸収されない２つの他のマシンサイ
クノペ即ちｒＤｓＰサイクル」及び「レベル−１サイク
ル」が存在することができる。本発明に従うと、上述し
た様に、組み込みハードウェアインターロックが、改変
されたデータベースを有する場合であっても、各検索引
き数毎の２つ以上の各遷移サイクルを禁止する。

従って、検索引き数の最大炎が数４０である場合、最大
４４のマシンサイクルを引き数を進めるのに取る。（こ
れは、一つの最終の「ダミー」マシンサイクルを含み、
セミオクテツトデータバス２０４上に正しくないセミオ
クテツトを有して走る）。これに、入力をロードする及
び出力レジスタを読み出すオーバーヘッドが加えられる
必要がある。この計算は複雑である、特にデータ書き込
み及びデータ読み出しサイクルが、これを引き起こす命
令として挿入される時に複雑である。

ＣＰＵレジスタロードサイクルは全て、多くて２つの待
ち状態を有することができる。第１のマシンサイクルは
、第ルジスタファイルロードサイククが検出されると直
ぐにスタートすることができる。この時間は、ＣＰＵ書
き込みサイクルのＳＯの開始から第１マシンサイクルま
でで測定された３００ｎｓのオーダである。結果を読み
出すために、最終マシンサイクルと同時にＣＰＵ　　Ｄ
ＳＡＣＫ信号が主張される（又は、これら信号のブロッ
クが免除される）。ＣＰＵ読み出しサイクルのＳ５の終
了が次に１５０ｎｓ以内で発生する。

ＣＰＵは（４６個の数までの、最初の４０までのみが重
要である）６つのロングワードを通常レジスタファイル
に転送する。第１の転送の開始から結果を読み取る読み
取りサイクルの終了迄の時間は、２０８ｎｓのマシンサ
イクルに対して、３００ｎｓ１４４＊２０８ｎｓ＋１５
０ｎｓ＝９．６μｓである。

利用可能な予備ＣＰＵ時間に対してより正確な数字を与
えるために、６個のロングワードの転送時間がこの数字
（６＊２００ｎｓ＝１．２μｓ）から引かれる。これは
８．４μｓの結果を与える。

レベル−１アドレス又はＩ　Ｅ　Ｅ　Ｅ　８０２．３デ
ータリンクアドレスの検索時間はより少ない。ＣＰＵは
アドレスを値「１２」のオクテツトで装う場合、結果を
レジスタファイル２７０に転送し、２つのロングワード
書き込みが要求される（このロングワードの最後のオク
テツトは無視される）。

レジスタファイル２７０内のデータが重ね書きされない
という事実を利用すことにより、８つの入力ブロックの
一つ（及び、これに対応する８つの根ノードの一つ）が
レベル−１ルツクアツプに対して検出される。−度第１
オクテツトに値「１２」が書き込まれると、このオクテ
ツトはそこに滞在する。この方法で、レベル−１アドレ
スは直接ファイルに書き込まれる。これは、依然として
２つの書き込み動作を必要とする。しかし、少ないとも
３つのＣＰＵバスサイクルが、位置が一致しないために
、インターフェースハードウェアにより発生される。

レベル−１ルツクアツプに対する根ノードは、データベ
ースのレベル−１分岐内の初期ノードと（多分）同じで
ある。区域遷移は期待出来ない。

リフレッシュサイクルがルックアップ中に発生する場合
、ルックアップ時間は１２個の数＋リフレッシュ＋ダミ
ー即ち、 ３００ｎｓ＋１４＊２０８ｎｓ＋１５０ｎｓ＝３．４μ
ｓである。

書き込みサイクルに対する時間を引くと、２．８μｓの
有効ルックアップ時間が与えられる。

ここに与えられる本発明のＡＲＥのデータベースの容１
を計算するのは比較的容易である。２つのデータベース
の形態がＡＲＥで共存できるものと考えられる。この形
態は、全長で１６個のセミオクテツト迄のアドレスが認
識されることを可能にし、また、４０個の（潜在的に４
６個の）セミオクテツトまでのアドレスが認識されるこ
とを可能にする。８個迄の異なるデータベースの全てが
、共存できる。これは根ノードの数によって制限されて
いる。

前者のデータベースはレベル−１アドレス、データリン
クアドレス及び地内のルータＩＤのために使用される。

２６Ｋがターミナルである５２にのノード及び各ノード
に於いて１６個のセミオクテツト定数ストリング記憶が
存在すると仮定すると、これらのデータベースに対して
、結合総数で２６に迄のエントリが補償される。（最悪
の場合、各遷移は多（て次のノードポインターを有する
。

従って、トリーは、最終ノードと同じ数の多（の遷移ノ
ードを有する２進化トリーとなる。）長さで４８セミオ
クテツト迄の４にのノード記憶定数ストリングが存在す
るので、最小に、２に迄のエントリーがより長いアドレ
スを検索するために補償されると仮定することが合理的
である。

しかしながら、最悪の場合、余分の遷移ノードを要求す
ることができる。これらの余分のノードは一つの出口、
即ちＤＳＰポインター出口のみを有する。（ＤＳＰ遷移
は定数ストリングの部分として記憶される。）これらの
条件下では、ＩＫエントリのみが補償される。ＡＲＥは
再定義することが可能であり、ＤＳＰ遷移がターミナル
ノードから許容され、次いでこの補償により最悪の場合
１．３　Ｋエントリまで増加することに注意する。また
、他のデータベースからノードを盗み、これらノードを
、より小さい定数ストリング容量で「鎖結合」すること
か可能であることに注意する。実際、定義される現在最
大炎ＩＤＩは長さで１８個の数のみを有し、１６数の容
量ストリング記憶長が、超過するノード容量を有すると
言う恐れなくしてＩＤＰ数を保持すために使用すること
かできる。

（最大炎ＩＤＰが１８個の数である場合、最大炎ＩＤＩ
は２つ少なくなり、ＡＦＩ数は、通常定数ストリングの
部分としては記憶されない。）パケット前送り目的のた
めには、レベル−２データベースがレベル−１ポインタ
ーを介してレベル−１データベースへ分岐されることに
注意する。

従って、（レベル−１配送によって配送される）領域内
に２６にアドレス化及び（最大接頭語に従って送られる
）領域外にＩＫアドレス迄の認識を補償するデータベー
スが構築できることが主張される。

他の実施例は特許請求の範囲内にある。

例えば、本発明は、長さが（好ましくはより広く）変化
するストリングを含む大きなデータベースの検索のため
に使用できる。この様なデータベースは共通であり、具
体的には、電話源、オンライン辞書、スペルチエッカ−
１社会保健番号等のディレクトリルックアップを含む。

この様な内容に於いて、ディレクトリルックアップが、
検索トリーを使用して達成される場合、本発明が適用可
能である。語「ノード」はここでは階層的樹木構造にお
ける要素を記述するのに使用されたが、本発明は、語「
ノード」が樹木構造を記述するのに使用されるか否かを
、樹木構造検索に利用する。

付録Ａ：ＡＲＥメモリーマツプ ＡＲＥはウェッジメモリーマツプ内の１６Ｍスペースへ
、アドレスｏｓｏｏ　　ｏｏｏｏ及び０８ｆｆ　　ｆｆ
ｆｆ間でマツプされる。

１６ＭＢ　　ＡＲＥ空間は６４Ｋ「ノード」内へ分割さ
れる。ここで、各ノードは２５６オクテツトサイズであ
る。従って、ＡＲＥアドレス（８個の１６進数字から成
る）が、次に示される様に、３つのフィールドに分解で
きる。

０８１ｎｎｎｎ　　ａａ ここで、最初の２つの数字「０８」はＡＲＥを選択し、
次の４つの数字ｒｒＦｎｎｎＪが６４にノードの一つを
選択し、最終の２つの数字ｒａａＪはノード内・の部分
空間を選択する。

各ノードでアクセスできる利用可能な空間が第９図内に
示される。

１亙立旦Ａ ノード制御語 ノード制御語は、全ノードで支持されるバイトアドレス
可能な１６ビツト語である。全ビットが検索エンジンに
よって解釈されることはないが、全ビットをＡＲＥメン
テナンスを（例えば、フリーノードを鎖結合することに
より）促進するために使用することができる。この語の
フォーマット及び説明が以下に与えられる。

空Ｉ　ＳＲＩ　ＩＣＩ　Ｌｌｌ　ｄｌｌ　ｌ　ｄｌｏ　
ｌ　ｄ９１　ｄ８１　ｄ７ｄ６１←長さ→ 空（空ノード）：これはビットが設定された場合、この
ノードが検索エンジンによって空ノードとして解釈され
る。空ノードにおいて、他の制御ビットの設定は無意味
である。空ノードに入ると直ちに、検索エンジンは停止
し、停止のための理由として「空ノード」を示す。空ノ
ードに記憶されたストリングは無視される。空ノードの
アドレスは、検索エンジンによって戻されるいかなる結
果内にも報告されない。

注意：そのアドレスのＭＳＢがゼロに等しい全ノード（
即ち、ノード００００から７　ｆ　ｆ　ｆ）は終了ノー
ドである。検索動作中、終了ノードに遭遇すると、検索
エンジンはノードから遷移をおこすのでなく、停止する
。

ＳＶ（セーブ結果）：検索動作中、このビットセットを
有する遭遇する全ノードは現在迄の結果レジスタ２４５
内にセーブされる。この信号語レジスタ２４５は常に、
ＳＲピットセットと最も最近遭遇するノードのアドレス
を含む。ＳＲビットは、定数ストリング存在が検索キー
と連続的に突き合わされるまで、検索エンジンによって
試験される。（検索キー数字の早期の消耗を含む）スト
リング不一致は、ＳＲビットの状態に関わらず、セーブ
されるノードＮＯＴを結果する。ノードアドレスは、ノ
ードが空でない場合にはセーブされない。

ＩＣ（ＩＤＰカウント存在）：このビットがセットされ
る場合、「長さ」フィールドの値は検索エンジンによっ
てＩＤＰの長さとして解釈される。

このビットはＡＰＩの第２の数字に続く第１のノルドで
設定されねばならない。長さフィールドは、関連するＡ
ＰＩによって示される適当なＩＤＰ長さにセットされる
。この様な値の一つのみが検索動作中にロードされる。

ＩＣビットは、ノードが空の場合無視される。

注意；定数ストリングは、ＩＣビットセットを有するノ
ードで記憶されることができない（無視される）。

ＬＬ（レベル−１遷移可能）：このビットは、厳密に１
４個の数字の検索キーの残りを有し、検索アドレスに対
する定数ストリング存在と連続して突き合わされる時の
みに検索エンジンによって試験される。この場合、Ｌｌ
ビットがセットされ、検索エンジンが次のノードのアド
レスとしてレベル−１ポインターの値を使用する。

ｄｌｌ、ｄｌｏ、・・・、ｄ６：　これらのビットは検
索エンジンによって使用されない。

長さ（５ビツト）：このフィールドは２通りで解釈され
る。

１、　Ｉ　Ｃがセットされる場合、空はセットされない
。このフィールドはＩＤＰの長さとして解釈される（上
述の如く）。

２、　Ｉ　Ｃがセットされないく、空がセットされない
場合、このフィールドがノードに記憶された定数ストリ
ングの長さとして解釈される。定数ストリングは、不一
致があるまで、又はソースが消耗されるまで検索キーの
数字に対して突き合わされる。

ストリング記憶空間 ストリング記憶空間が、ノードで可変長の定数ストリン
グを記憶するために与えられる。このストリングは、バ
イト当たり１数字で、連続する数字として記憶される（
各バイトの４つの最上位ビットは書き込みの際無視され
、常に零として読まれる。）。ストリング長（記憶され
た数字の数）はノード制御語内で指示される。記憶する
ことのできる数字の最大数はノードアドレスの関数であ
り、以下に示される。

遷移ノード ｆ８００≦ノードアドレス≦ｆｆｆｆ−最大４８数字 ９０００≦ノードアドレス≦ｆ７ｆｆ−最大１６数字 ８０００≦ノードアドレス≦８ｆｆｆ−許容される記憶
なし 端子ノード ７８００≦ノードアドレス≦７ｆｆｆ−最大４８数字 １０００≦ノードアドレス≦７７ｆｆ−最大１６数字 ００００≦ノードアドレス≦０ｆｆｆ−許容される記憶
なし くｒｘ≦ｙ」は、ｙ未満か等しいことを意味する。） 検索エンジンは通路数が記憶されるノードに遭遇する時
、ストリングが、数ソースが消耗されるか、不一致が生
じるまで、残りの検索アドレス数字に対して比較される
。

次のノードポインター １８個の「次のノード」ポインターが３２に遷移ノード
に対して与えられる（ポインター圧縮が実行される。）
第１の３２にノードは「終了ノード」であり、遷移はそ
こからは生じない。

（検索能力のある場所で）ストリング突き合わせが連続
して完了される場合、ノードが終了又は空ノードでない
場合、且つ検索アドレス数が残っている場合、次のノー
ドポインターが検索エンジンによって選択される。この
選択は、以下のルール（以上で作動の理論とで呼ばれて
いる）に従ってなされる。

１、　Ｉ　Ｄ　Ｉ長がＩＤＩＬレジスタ２５０内にロー
ドされる場合、この長さが厳密に零に減少される（又、
このロードがない場合、現在ノードが全ＩＤＰ長２のＩ
ＤＩＬをロードする。）。即ち、検索エンジンが、処理
されるべき次の検索キー数字ＤＳＰの第１の数であり、
次にＤＳＰポインターが選択される。ＤＳＰポインター
が、選択操作中に多くて一度選択することができる。Ｄ
ＳＰポインターの選択は現在検索キー数を消費しない。

このキー数字は次のマシンサイクル内で使用される。

２、他方、厳密に１４個の検索キー数が残り、Ｌ１ビッ
トがこのノードのノード制御語内でセットされる場合、
レベル−１ポインターが選択される。このレベル−１ポ
インターは検索操作中に多くて一度選択できる。レベル
−１遷移ポインターの選択は現在検索キー数字を消費で
きない。このキー数字は次のマシンサイクルで使用され
る。

注意：（１）及び（２）の両方が当てはまる場合、（２
）に対する条件が、（１）が達成された後に際に再試験
される。

３、他方、検索キーの次の数字が最初の１６個の次のノ
ードポインターの一つを選択するのに使用される。例え
ば、数が零の場合、アドレス４０に於けるポインターが
使用される（ポインターアドレスオフセットは、第９図
で４０として参照される。）。

青アドレス記恩領域 ３２バイトの記憶空間がノード８０００から８００７の
各々に与えられる。これらの３２バイトの最初の２４バ
イトは新たな検索アドレスをロードするのに使用される
。検索の結果は検索エンジンにより最後の８バイトに書
き込まれる。８個までの検索エンジン内容が指示される
。新たな検索は、現在の検索が完了するまで開始されな
いことに注意する（新たな検索は現在の検索を打ち切る
ため）。検索が開始される時、検索アドレスをロードす
るのに使用されるノードは検索エンジンにより使用され
る根ノードである。検索アドレスのフォーマットは以下
の通りでなければならない。

第１バイト（アドレス８０／ａｏ）：検索アドレス長 後続のバイト：検索アドレス、第１バイト内で定義され
る長さ。

第１バイトに書き込まれる長さ情報は２通りに解釈され
る。二バイトがアドレス８０に書き込まれる場合９、こ
のバイトはオクテツト長として解釈される。即ち、与え
られる数字の数は、長さバイトの値の２倍である。長さ
バイトがアドレスａＯに書かれる場合、このバイトはセ
ミオクテツト長として解釈され、検索キー内の数を明示
する。アドレス空間ａｏ−ｂｆは他方アドレス空間８Ｏ
−９ｆの別称である。（現在ＡＲＥの実施形態は４０（
１０進数）以上の又は零に等しいセミオクテツトをエラ
ーとみなす。） 長さオクテツトによって示唆されたよりも多い数を検索
キー領域に書き込むことができる。合計で最大３２のオ
クテツトが書き込まれなければならず、３３番目のオク
テツトは検索を再初期化するか、バスエラーを発生する
。２５以上のオクテツトが供給される場合、検索結果が
利用可能となる時に、過剰なオクテツトが、この検索結
果とともに重ね書きされる。長さフィールドが示すより
もより少ないオクテツトが供給される場合、検索エンジ
ンは、検索を恒久的に終了、しない場合に供給されるべ
きオクテツトを無期限に待ち続ける。

良ｉ級困■１ 検索の結果は、検索キーがロードされる同じノード（即
ち、ノード８０００から８００７の一つ）におけるアド
レス９８−９ｆ　（ｂ８−ｂｆ）において利用可能であ
る。結果のフォーマットは以下の通りである。

９９又はｂ９　　検索の終了における検索アドレスの残
りのセミオクテツト 長〔バイト〕 ９ａ−９ｂ又は　ＳＲピットセットと遭遇するｂａ−ｂ
ｂ　　　　最近ノード〔符号なし語〕９ｃ又はｂｃ 検索の終了でのストリング数 字カウンタの値 制御及びスティタスレジスタ ス０８００００ｃＯ ９ｄ又はｂｄ 検索の終了での記憶数字カラ ンタの値 ｅ ｅ ９ｆ又は ｆ 検索中に最も最近遭遇するノ ード（このノードが空ノード である場合を除＜）〔符号な し語〕 結果情報を解釈する場合の詳細な情報に対する付録Ｂを
参照する。

スティタスレジスタ０がパリティ−制御及びＣＰＵアド
レスに対するスティタスを、ＤＲＡＭが与えられたデー
タベースメモリーに与えられる。

ＰＥＳ　：パリティーエラーが、ストリング記憶メモリ
ーを読むＣＰＵ上で検出される時にセットされ、ＣＰＵ
が１を重ね書きすることによりリセットされる。

ＰＥＰ　：パリティーエラーが、次のノードポインター
を読むＣＰＵ上で検出される時にセットされ、ＣＰ、Ｕ
が１を重ね書きすることによりリセットされる。

ＥＰＳ　：　ＣＰＵによって読み出され／書き込まれる
。零の時、ストリング記憶メモリー上に奇数パリティ−
を使用（生成し且つチエツク）し、ｌに設定される時、
偶数パリティ−を使用する。

ＥＰＰ　：　ＣＰＵによって読み出され／書き込まれる
。零の時、次のノードポインターメモリー上に奇数パリ
ティ−を使用（生成し且つチエツク）し、１に設定され
る時、偶数パリティ−を使用する。

全ＡＲＥに対して一つの制御レジスタが存在する。これ
らビットは以下に定義される。

８Ｍ（検索モード）：　ＳＭ＝０　（＝　ｒメンテナン
ス　モード」）の時、検索モードが開始され、検索結果
情報は無効である。検索エンジンはリセットされる。こ
のモードは、ＣＰＵがアドレス７ｆ以下の資源にアクセ
スすることができる。ＳＭ＝１の場合、検索モードが使
用可能になる。このモードは、検索キーがロードされる
以前に選択され、結果が読み出されるまで維持される必
要がある。このモードにおいて、アドレス７ｆ以下の全
資源にはアクセス不能である。

Ｎ５ＡＰ　（ＮＳＡＰモード）：このビットは、検索の
終わりの結果要約オクテツト内の成功／失敗ビットのセ
ツティングのみに影響する（付録Ｂを参照する）。

ＩＬＩ　（禁止レベル−１遷移）：このビットがセット
される場合、いかなる検索中にもレベル−１遷移はなさ
れない。

ＩＤ５Ｐ　（禁止ＤＳＰ遷移）：このビットがセットさ
れる場合、いかなる検索中にもＤＳＰ遷移が生じない。

ＳＤＫ　（停止ＤＳＡＣＫ）このビットがセットされる
場合、（検索結果情報下で定義される）検索結果情報の
読み出しは、結果が使用可能であるまで停止される可能
性拡張バスサイクルを結果する。これは、結果が利用可
能であるかをチエツクする必要性を除去する。これは、
検索モードのみで全コンチクストに適用可能である。

ｄ２、ｄｌ、ｄ　０−ＡＲＥによって使用されない。

検索スティタスレジスタ　２ −アドレス　０８００００ｃ２　（読し出しのみ）ビッ
トが診断目的のために先ず与えられる。これらビットは
、検索エンジンが（スティタスレジスタ３で定義された
）ＨＡＬＴｅｄ又はＢＵＳＹの何れかに成る時のみ正し
い。

ＢＣＮＴ：このビットは、検索エンジンが検索アドレス
の第１のバイトがオクテツト長カウントであると仮定す
る時にセットされる。次にセミオクテツト（数字）カウ
ントが仮定される。

ＲＴ２．．０：これら３つのビットは、検索引き数を読
み出す目的のために検索エンジンが使用する根ルートの
３つ最下位ビットに等しい。

−アドレス　０８００００ｃ３　（読み出しのみ）この
レジスタから利用可能な４つのスティタスこのスティタ
スレジスタは応用及び診断使用のための検索エンジンを
与える。

ＢＵＳＹ　：このビットは、検索エンジンがノードを処
理し又は結果のロードを処理する時セットされる。

ＨＡＬＴ　：このビットが、検索エンジンが処理ノード
を停止した時にセットされる。

上記２つのビットが対としてデコードされる必要がある
。

ＢＵＳＹ　　ＨＡＬＴ　　解釈 ００　　検索エンジンがリセットされるＩ　Ｏ検索エン
ジンが検索を行う １１　　　結果がロードされる（短い遷移状態）０１　
　結果が読み出しのために利用可能ｆ５．．ｆｏ：これ
らのビットが、検索キーの構成部分を書き込むことによ
ってレジスタファイル内にセットされ、正しいデータが
存在することを示すのに検索エンジンによって使用され
る。

レジスタ３の全ビットは、マシンがメンテナンスモード
（制御レジスタのビット７がゼロ）にある時にリセット
される。ビットｆ５からｆｌは、ＣＰＵが検索キーの最
初のロングワードの最後のバイトに書き込みを行う時に
リセットされる。同時に、ビットｆＯが（検索モードが
イネーブルされる場合）セットされる。ＣＰＵが検索キ
ーの第２０ングワードの最終バイトに書き込みを行う時
、ビットｆｌが、検索モードで、セットされ、ビットｆ
２からＦ５が同様に第３から第６０ングワードの最終バ
イトが書き込み中に同様にセットされる。

アドレス　０８００００ｃ４　（読み出しのみ）このス
ティタスはＣＰＵが基板上のスイッチパック内の８つの
スイッチの位置を読み出すことを可能にする。

録　Ｂ：ＡＲＥからの検索結果をデコードする検索キー
かロードされるのと同じノード、即ち、８０００から８
００７の一つのアドレス９８−９ｆ　（ｂ８−ｂｆ）で
利用可能である。制御ビットｒＳＫＤＪがセットされる
場合（制御レジスタ１内のビット３）、検索キーをロー
ドした後に読み出すことができる。ＣＰＵは、正しいデ
ータが戻されるまでハードウェアによって停止される。

「ＳＫＤ」ビットがセットされない場合、ＣＰＵはステ
ィタスレジスタ３をポールして、検索結果状態が正しい
時を決定しなければならない。

結果のフォーマットは以下の通りである。最小遅延が、
結果が２つのロングワードを読み出すまで、生じる。

要約 残余長 現在迄の 結果 残余ＩＤＩ バイト　要約スティタスバイト（以 下参照） バイト　検索エンジンによって処理 されない残余検索キー数字 の数 ワード　「セーブ結果」ビットセッ トを有する検索エンジンに よって横切られるＴＲＩＥ内最 近ノード バイト　検索エンジンによって処理 されない検索キー内の残余 ストリング　バイト カウンタ 現在迄の 取得 バイト ＩＤＩ数字の数 ストリング不一致検索終了 の場合情報を与える、スト リングカウンタ値 （空ノードの場合を除き） 終了時間に検索エンジンに よって処理されるノード 要約スティタスバイト 要約スティタスバイトが与えられると、ホストＣＰＵは
、検索が成功したかしないかを直ちに決定し、成功しな
い場合は、検索の失敗の理由を決定する。

エンコーディングは、データベースが破壊されるべきか
否かが検索エンジンによって見做されるか否かに依存し
、更に制御レジスタｌ内のｒＮＡＳＰＪ　ビットによっ
て影響される。

２つの場合が以下に分けて記述される。

場合１；破壊されたデータベース 破壊されたデータベースに対して、出力のエンコーディ
グは、 ＩＳＯ＝到達した不合法ストリング係数（ＣＰＵが、１
ノードで許される最大よりも多くのストリング数字が存
在した。） ＰＥＰ＝ポインターメモリー上のパリティ−エラＬＩ　
ＮＤ＝レベル１遷移が達成され、ＤＳＰ遷移は達成され
ない（Ｎ　Ｓ　Ａ　Ｐモードのみ）。

ＬＩＮＥ＝レベル１遷移が達成され、ソース数字が費や
された（ＮＳＡＰモードのみ）。

ビットＩＳＣ，ＰＥＰ及びＰＥＳの設定ビットは、互い
に排他的である。

ＩＳＣが設定される場合、一つのノードで許される最大
ストリング長を越す数字ポインターによりストリング比
較サイクルを開始することを試みる。「現在までの取得
」フィールドは、ストリングが記憶されるノードを含む
。［ストリングカウント」フィールドが大きすぎるスト
リング数字ポインターを含む。

ＰＥＰが設定される場合、遷移が１６個の「次ノード」
ポインターの一つを通して一つのノードから達成される
。アドレスが、パリティ−エラーを含む次のノードに対
して示される。「現在までの取得」フィールドは破壊さ
れた「次のノード」ポインターが記憶されるノードを含
む。「残糸長」フィールドが検索エンジンによって処理
されべきにどれだけ多くの検索キー数字が残るかを示す
。

これらの残りの数字の第１のものは、破壊された「次の
ノード」ポインターを選択するのに使用された数字に直
後の数字である。

ＰＥＳが設定される場合、次のストリング比較サイクル
が開始されたが、記憶されたストリング数字はパリティ
−エラーは含まなかった。「現在までの取得」フィール
ドは破壊されたストリングが記憶されたノードを含む。

「ストリングカウント」フィールドは、パリティ−エラ
ーが検出された後の数字を示す。

ＬＩＮＤ及びＬＩＤＥＩＤ上を設定することは、ＩＳＣ
，ＰＥＰ及びＰＥＳビットと独立している。

検索の終了時に、理由は何であっても、ＬＩＮＤビット
が、ＮＡＳＰモードが選択される場合設定され、レベル
１遷移が達成され、ＤＳＰ遷移は達成されない。ＬＩＤ
ＥＩＤ上は、レベルｌ遷移が達成された場合、同様に設
定され、残りの検索キー数字は存在しない。検索エンジ
ンは、レベルｌ遷移が達成された場合、Ｎ５ＡＰの遷移
において最小２つの残りの数字が通常存在することを期
待する（これら２つ数字はＳＥＬフィールドである。ン
場合２：データベースが破壊されない データベースが破壊されないと考えれる場合、次ぎに要
約スティタスバイト内のビットのエンコーディングは、 Ｆ＝検索失敗（０＝成功）。このビットはＮ５ＡＰモー
ドピツトによって影響される。

ＲＬ−ｒ現在までの結果」フィールドが有効。

ＮＩＬ−空ノードが到達。

ＳＭ＝ストリング不一致が発生した。

ＤＥ＝ソース数字が費やされた。

Ｌ１＝レベルｌ遷移が達成された。

ＤＳＰ＝ＤＳＰ遷移が達成した。

検索が成功した場合、Ｆビットは０である。成功した検
索は、データベースが破壊されなかったものと定義され
る。供給された長さが１から４０のセミオクテツトの範
囲内にあり、更に、Ｎ５ＡＰモードにおいては（ａ）レ
ベル１遷移が達成され、現在までの結果が少なくとも一
度ロードされ、要約スティタスのエンコーディングがｏ
ｏｔｘｘｘＯＸであるか、ｆｂ）レベル１遷移が達成さ
れ、ストリグの不一致がなく、端子ノードがＳＲがセッ
トされる場所に到達し、（暗示的に）ＤＳＰ遷移が達成
され、検索キー数字の全ては使用されなかったのいずれ
かである。この場合の要約スティタスバイトのエンコー
ディングは００１０００１１である。

非Ｎ５ＡＰモードに於いて、成功検索は、データベース
が破壊されていなく、検索アドレス長が指定された長さ
にあり、検索アドレス数字の全てが使用され、ストリン
グ不一致がなく、（且つ検索アドレス数字が、検索突き
合わせの際に費やされない）、且つ到達した最終ノード
（空ノードでない）がＳＲビットセットを有する場合で
ある。

最終ノードはターミナルノードである場合もあるしない
場合もある。このノードがターミナルノードである場合
、「ＤＥ」ビットは０である（例え、数字が費やされた
場合でも）。要約スティタスバイトのエンコーディング
は００１０　０ＸＸ 検索期間中に「現在までの結果」フィールドにノードア
ドレスがロードされた後ＲＬビットがセットされる。こ
のビットは、「現在までの結果」フィールドが有効なデ
ータを含むことを示す。ＲＬが零の場合、「現在までの
結果」フィールドの値は定義されない（好ましい例にお
いて、この値は根ノードを含んでいる。）。

Ｌ１ビットの設定は、制御レジスタ内の制御ビットｒＩ
ＬＩＪがセットされるかされないかに依存している。こ
の制御ビットがセットされない場合、レベル１遷移が利
用可能になり、Ｌ１スティタスビットは、レベル１遷移
が検索中に成された場合のみにセットされる。他方、ｒ
ＩＬｌ」ビットがセットされる場合、レベルｌ遷移が禁
止され、この場合、検索中のいかなる時においても、遷
移が、ノード制御ビット「イネーブルレベル１遷移」が
セットされたノードから成された場合（ＤＳＰ遷移では
ない）、Ｌ１スティタスがセットされる。

検索期間中にＤＳＰ遷移が達成された場合及びその場合
のみＤＳＰビットがセットされる。制御ビット「ＩＤ５
Ｐ」が制御レジスタｌ内にセットされる場合、ＤＳＰ遷
移が禁止され、ＤＳＰ　（遷移達成）スティタスビット
が常に零になる。

Ｎ　Ｉ　Ｌ、ＳＭ、ＤＥビットはデータベースが破壊さ
れない場合に検索エンジンが停止した理由をエンコード
する。各場合が以下の詳細に記述される。上述された様
に、「現在までの結果」フィールドは、ＲＬビットがセ
ットされる場合のみ有効である。

（ａ）Ｎ　Ｉ　Ｌ、　５Ｍ５ＤＥ＝０００　＋こツエン
コーディングは、ターミナルノードに検索エンジンが到
達したことを意味する。「現在までの取得」フィールド
はターミナルノードを含む。「現在までの結果」フィー
ルドは「５Ｒ８Ｆ」ノード制御ビットセットを有した最
近横切られたノードを含む。

「５Ｒ８Ｆ」がターミナルノードにセットされると、「
現在までの結果」は「現在までの取得」る等しい。「残
糸長」フィールドは、どれだけ多くの検索キー数字が検
索エンジンによって使用され無かったかを示し、その値
が零であり場合は、最後の数字が検索エンジンがターミ
ナルノードに行くことに対して責任があることを示して
いる。

（ｂ）Ｎ　Ｉ　Ｌ、　ＳＭ、　ＤＥ＝００１　：このエ
ンコーディングは、検索キー数字を使い切ったために検
索エンジンが停止したことを意味する。その他の場合は
、検索エンジンが停止した場所のノードから遷移が達成
されていた。「現在までの取得」フィールドは、数字が
使い切られた時に検索エンジンによって到達されたノー
ドを含む。このノードはＮＩＬでもターミナルノードで
もない。このノードに記憶されたストリングが存在する
と、それは連続的に突き合わされる。「ＳＲ」ビットが
このノードに設定される場合は、「現在までの結果」は
「現在までの取得」に等しい。他方、ｒｓＲＪビットセ
ットを有して最近され横切られたノードを含む。レベル
１又はＤＳＰ遷移は、検索アドレス数字が使い切られた
時でさえノードから達成され、従って、ＤＳＰ又はレベ
ル１遷移は「現在までの取得」によって示される到達し
た最終ノードからは達成することができないことに注意
すべきである。

（Ｃ）ＮＩＬＳＳＭ、ＤＥ＝０１０　：このエンコーデ
ィングは、検索キーの定数ストリング数字及び次ぎの数
字の間の不一致を検出してことにより検索エンジンが停
止したことを意味する。「現在までの取得」フィールド
は、定数ストリングが記憶される場所のノードに含まれ
る。「ストリングカウント」フィールドは一致しない数
字の後のストリング数字を指し示す。「残糸長Ｊフィー
ルドはどれだけ多くの検索キー数字が検索エンジンによ
って処理されなかっかかを示し。これら残りの数字の第
１のものは、定数ストリング数字と一致しなかった数字
の直後に続く。

「現在までの結果」フィールドはｒｓＲ８Ｆ」ビットセ
ットを有する（検索が終了したノードの前の）最も最近
訪れられたノードを含む。

（ｄ）Ｎ　Ｉ　ＬＸＳＭ、　ＤＥ＝０１１　：これは、
検索エンジンに課せられたストリング数字比較サイクル
を達成することかできないので検索エンジンが停止した
ことを意味する。これは、（ｉ）検索引き数円の数字が
費やされ始めたか、又は（ｉｆ）特に、ＩＤＰ数字のみ
を記憶する通路数字ストリングに対する比較を行う間に
検索引き数のＩＤＰ数字が費やされ初めだかの何れかの
理由による。「現在までの取得」フィールドはストリン
グが記憶されたノードを含む。「ストリングカウント」
フィールドが、（ｉｉ次ぎの検索キー数字、又は（ｉｉ
）次ぎのＩＤＰ数字の一方と比較されるストリング数字
を指し示す。

「現在までの結果」フィールドは（検索が終了したノー
ドの前の）、「ＳＲ」ビットセットを有した最も最近訪
れたノードを含む。

（ｅ）Ｎ　Ｉ　Ｌ、　ＳＭ、　ＤＥ＝　ｌ　００　：こ
れは、検索エンジンがＮＩＬノードに到達したことを意
味する。「現在までの取得」フィールドは空ノードの前
の最も最近訪れたノードを含む。同様に、「現在までの
結果」は「ＳＲ」ビットがセットされた（空ノードの前
の）最も最近訪れたノードを含む。

空ノードに対する遷移が、検索キー数字によって成され
、「現在までの取得」フィールド内にそのノードが示さ
れ続ける。この数字は、検索エンジンによって使用され
た最後のものであり、この数字は、「残余長」又は「残
りｒＤＩ長」カウント内には含まれない。

げ）ＮＩ　Ｌ、ＳＭ、ＤＥ＝１１０　：これは、検索エ
ンジンが空ノードに到達したことを意味する。

この場合、ＤＳＰ又はレベル１ポインターを使用してこ
の遷移が達成せれ、そのノードが「現在までの取得」フ
ィールド内に示され続ける。通常の場合、レベル１ポイ
ンターは空ノードを指し示し、従って、ＤＳＰ遷移が空
ノードに対してなされたことを想定することができる。

ＤＳＰ遷移が空ノードの対して達成された場合において
も、スティタスビットｒＤＳＰ遷移達成」がセットされ
る。「残りのＩＤＩ長」の値が零になる。「残余長」フ
ィールドの値は供給検索キーの完全ＤＳＰ長に等しい。

（勅ＮＩＬ、ＳＭ、ＤＥ＝１１１　：これは非合法検索
キー長が検索エンジンに供給されたことを意味する。即
ち、零又は４１個以上の数字である。

この場合、検索エンジンは検索キー上で全く進歩しない
。

求されたメンテナンスサポートの概 メンテナンスエンジン１８は、新たなエントリーを、検
索ユニット４０に対する引き数として先ず与えることに
よりデータベースに挿入する。検索ユニット４０はデー
タベース内に検索引き数を位置させようと試みる。これ
が失敗すると、検索エンジンは少なくともデータベース
内に存在する検索引き数の最長接頭語を報告する（この
最長接頭語はデータベース内の「結果」と関係する必要
はない）。

多くとも２つの新たなノードがデータベース内に挿入さ
れる。一つの新たなノードが加えられて、全ての既存の
ノードからこの新たなエントリーは識別される。このノ
ードは、検索ユニットが新たなエントリーの最長接頭語
を置（ポイントに挿入される。一つの別の新たなノード
が加えられ、このノードはデータベースと一致する接頭
語を越える新たなエントリーの残りの数字の全てに等し
い通路圧縮ストリングを含む。

識別ノードは、新たなエントリーがデータベースの通路
圧縮ストリングと比較され、この比較の一つの間に不一
致が発生した場合にのみ付加される必要がある。この場
合、通路圧縮ストリングが不一致点で２つに分けられる
必要がある。新たなエントリーに対しての比較が成功し
た部分は、新たなノード（識別ノード）に記憶される。

このノードは２つの非空ポインターを有する。一つのポ
インターが、元の通路圧縮ストリングを有するノードを
指し示す（元の通路圧縮ストリングは、新たなエントリ
ーに対して一致しないストリングの部分に置き換えられ
る。）。第２のポインターは新たなエントリーの残りの
数字の通路圧縮ストリングを（若しあれば）保持する新
たなノードを指し示す。

この逆工程は消去の為に使用される。

Ｃ：ポインター及び通路圧縮によるメモリ節約 ここで与えられた解析は、とれだけ多くの物理的メモリ
ーが、通路圧縮及びポインター圧縮技法をトリーベース
のデータベースに適用することにより節約できるかを大
まかに示している。この解析のために、１６個のポイン
ターが一つのノードにあり、これらは各ノードで処理さ
れる検索引き数の４ビット文字（セミオクテツト）に対
応する。

異なるサイズの文字に対して、解析は、ここで想定され
る１６個のポインターの固定サイズと置き換えられたパ
ラメータで達成されるべきである。

更に、ＩＳＯ及びＤ）ｉＣｎｅｔフェイズＶアドレスの
特異性は考慮に入れない。

この解析は、所定数のエントリーを有する最悪の場合の
データベースを記憶するためのメモリー要求を考慮する
。第１に、通路圧縮が考えられ、通路圧縮に加えて、ポ
インター圧縮の適用が続く。

Ｎ個までのエントリーを記憶するのに必要とされるトリ
ーベースデータベースを考える。エントリーはＬセミオ
クテツトの最大値までの可変長を有すると考える。トリ
ー内の各ノードは１６個のポインターを含む。最悪の場
合、最大数のノードがこれらＮ個のエントリーを保持す
るのに必要とされる。

最悪の場合は、エントリー間の全区別が可能な限り根に
近いノードでなされる場合発生する。この場合において
、全エントリーは大きなノード鎖と関連され、各ノード
はこの鎖内の次ぎのリンクを指し示す非空ポインターの
みを使用する。全Ｎエントリーを特定するのに必要とさ
れるトリーの深さは、１０ｇ１６Ｎである。このレベル
まで使用されるノードの全数は（Ｎ−１）／１５である
。

長い鎖内で使用されるノードは、必要とされるノードの
全数の集団を決めている。Ｎ個の鎖が存在する。データ
ベース内の全エントリーがＬセミオクテツト長の場合、
全路は（Ｌ　　１ｏｇ＋ａＮ）長を有し、６鎖の端部が
、記憶要求が想定されないターミナルノードを指し示す
。

従って、必要とされるノードの全数は （Ｎ　−１）　／　１５　＋　（Ｌ　−ｌ　ｏ　ｇ、８
Ｎ）　＊Ｎ（１）各サイズは１６ポインターである。第
１近似としてこれは Ｌ＊Ｎノードに簡略化される。　　　　　　　（２）通
路圧縮が実行されることを今考える。ノードの長い鎖は
ターミナルノード又は少なくとも２つのポインターを有
するノードに崩壊される。メモリーの最大量は、可能な
限り多くの（非ターミナル）ノードが存在する時に必要
となる。これは、全ての非端子ノードが正確に２つのポ
インター（例えば、２進トリー）を有する時の場合であ
る。

非端子ノードの全数がＮ−１である。端子ノードがポイ
ンターに対する記憶を必要としない。従って、ポインタ
ーに対するメモリー要求は（ノード当たり１６個のポイ
ンターを有し）、 （Ｎ−１）＊１６ポインターである。　　（３）通路圧
縮ストリングに対するメモリー要求がある。ノード間の
ストリングの分布は大幅に変化できるが、データベース
内に各長さがＬセミオクテツトであるＮ個のエントリー
が存在する場合、全記憶要求は（Ｎ＊Ｌ）セミオクテツ
トを越えることが出来ない。ポインターが４つのセミオ
クテツトに等しくされる場合、式（３）の要求を加えて
、全メモリー要求は、良い近似として、 （Ｎ−１）＊６４＋　（Ｎ＊Ｌ）＝Ｎ＊　（６４＋Ｌ）
セミオクテツト　　　　　　　　　　　　　　　（４）
となる。通路圧縮無しで同じサイズのデータベースに対
する記憶要求と式（２）が比較される時、（４）に対す
る（２）の比は （６４＊Ｌ）　／　（６４＋Ｌ）である。　　　　（５
）これは、（小さなＬに対する）１及び（大きなしに対
する）６４の制限によって境界付けられる。

Ｌ＝４０に対するＩ　８０８３４８／ＡＤ２ネツトワー
クアドレスの場合、減少率は２４．６であり、極めて大
きな物理メモリーの節約がもたらされる。

実施形態においては、メモリー管理をより容易にするこ
めに全ソードで最大長通路圧縮ストリングに対して全ノ
ードで最大通路圧縮ストリングに対して十分なメモリー
が割り当てられることがあることが望まれることがある
ことに注意する。この場合、約２倍のメモリーが通路圧
縮を記憶するのに必要とされ、式（５）が、 （３２＊Ｌ）／　（３２＋Ｌ）と変形される。　（６）
これは、３２の上限を有し、ＩＳＯアドレスの場合の減
少率は１７．８であり、依然としてかなりのものである
。

ポインター圧縮を、通路圧縮されたトリーに加えること
を次に考える。ポインター圧縮を有さない通路圧縮され
たトリーに対する最悪の場合の記憶要求は、式（４）で
与えられる。ポインター圧縮が導入される時、可能な限
り多くの実際の（即ち、非空）ポインターが使用される
場合に最悪の場合が発生する。従って、最悪場合は、上
述のポインターが圧縮されない場合において使用される
同じ２進トリー構造に対して発生する。各非ターミナル
ルートのサイズは２つのポインター足すビットマスクで
ある。ビットマスクは１６個のビット巾であり、特にポ
インターと同じ大きさである。従って、通路圧縮された
及びポインター圧縮されたトリーに対する記憶要求量は
最悪の場合、よい近似として、 （Ｎ−１）＊３ポインター＋（Ｎ＊Ｌ）セミオクテツト
＝（７） Ｎ＊　（１２＋Ｌ）セミオクテツト　　　　　　　（８
）となる。通路圧縮のみに要求される記憶量、式（４）
と比較すると、■と５の間の値を有する。

（６４＋Ｌ）／　（１２＋Ｌ）　　　　　　　　　（９
）の割合だけメモリー要求に更に減少がもたらされる。

Ｌ＝４０の場合ＩＳＯアドレスの場合に対して、減少率
は２である。

通路圧縮された及びポインター圧縮されたデータベース
に対する全体の減少率は、圧縮のないデータベースと比
較すると、式（５）及び式（９）の積となる。これは、 （６４＋Ｌ）　／　（１２＋Ｌ）　　　　　　　　　（
１０）である。これは小さなＬに対して５、大きなしに
対して６４の制限によって境界付けられる。

ＩＳＯアドレスの場合に対して、全体としての減少率は
４９である。

【図面の簡単な説明】

第１図はトリーデータベースの概略図、第２Ａ図は、Ｏ
８Ｉネットワークアドレスフォーマットを示す図、 第２Ｂ図及び第２Ｃ図はＩＤＩフォーマットの表図、 第３図は認識エンジンを有するデータベース構造を表す
図、 第４図は圧縮されない通路データベース構造を表す図、 第５図はポインター圧縮通路データベース構造を表す図
、 第５Ａ図はポインター圧縮されたノード構造の図、 第６図は通路圧縮されたノード構造の図、第７図はＩＤ
Ｉ、ＤＳＰ及びレベルｌ処理のための部分的データベー
ス構造の図、 第８図は認識エンジンのデータ通路の図、第９図は第８
図内のメモリー内のノードデータの位置を説明する表図
。 １０・・・ルータ、１１・・・パケット、１２・・・受
信ユニット、１４・・・前送りエンジン、１６・・・通
信リンク、１８・・・管理エンジン、２０・・・認識エ
ンジン、３０・・・フェッチユニット、４０・・・検索
ユニット、５０・・・メモリー ＦＩＧ、４ ＦＩＧ、５ ＦＩＧ、６ ボンルターＢ縮 なＬノード′ ボイ〉ターＥ縮 あり　ノード′ ＦＩＧ、９ 手 続 補 正 書（方式） ％式％ １、事件の表示 平成２年特許願第１８５１４７号 ２、発明の名称 圧縮された接頭語突き合わせデータ ベース検索方法及び装置 ３、補正をする者 事件との関係 出 願人 ４、代 理 人

Claims (34)

【特許請求の範囲】
1. （１）検索路内の前と次のノードの間に生じるノードを
   除去することにより長さが減少された検索を制御する方
   法が、 前記除去されたノードが存在した場合に、検索が前記次
   のノードに進んだか否かに関する情報を記憶し、 検索引き数を前記記憶された情報と比較し、この比較が
   正の場合、前記検索を、前記前のノードから前記次のノ
   ードに直接的に効率的に進ませることから成る検索を制
   御する方法。
2. （２）前記ノードの幾つかが前記検索に対する結果値を
   与え、前記ノードが、その存在が前記検索のための結果
   値に影響を及ぼさない場合のみ除去されることを特徴と
   する請求項（１）記載の方法。
3. （３）前記情報が前記以下のノードに記憶されているこ
   とを特徴とする請求項（１）記載の方法。
4. （４）前記検索が第１及び第２のモードを有し、前記検
   索の前記第１のモードが前記検索路に沿った処理ノード
   から成り、そして 前記除去されたノードが、それが存在する場合、前記検
   索を前記次のノードに進めるか、又は前記検索を前記第
   ２のモードに進ませるノードを含むことを特徴とする請
   求項（１）記載の方法。
5. （５）前記検索引き数が、一連の検索セグメントから成
   り、前記引き数のセグメントの値の幾つかが、前記検索
   路に沿ったノードに対応しており、前記セグメントの他
   の値が前記第２のモードに関係していることを特徴とす
   る請求項（４）記載の方法。
6. （６）前記記憶された情報が、一連の前記検索引き数で
   あることを特徴とする請求項（５）記載の方法。
7. （７）ノードに関連し且つ前記第２のモードに対応する
   セグメントを各々指示する標識を与え、前記連続する検
   索セグメントを処理することにより前記検索路を検索す
   る工程をさらに有し、前記処理が各ノードに関連する標
   識を検査し、且つ前記標識が前記セグメントが前記第２
   のモードに関係する場合のみ前記第２の検索に進むこと
   を特徴とする請求の範囲（６）記載の方法。
8. （８）前記検索の前記第２のモードが前記検索を終了す
   ることから成ることを特徴とする請求項（７）記載の方
   法。
9. （９）前記検索用き数がネットワーク内のシステムアド
   レスから成ることを特徴とする請求項（８）記載の方法
   。
10. （１０）通路決め情報を分散型デジタルデータ処理ネッ
    トワーク内のパケットアドレスと関係付ける方法が、 樹木構造にされた非空ノード、前記アドレスのセグメン
    トによって識別される前記ノードを通過する通路であり
    、１つのセグメントの各値が前記通路上に沿った次の可
    能性のあるノードを識別し、 前記通路を終了するために空ノードを与え、単一の非空
    次ノードを有するノードを、他のノード内に記憶された
    通路ストリングで置き換え、前記通路ストリングが、置
    き換えられたノードに対応する一連のセグメントの値を
    記憶することから成る方法。
11. （１１）単一の非空次ノードを有する他のノードを、こ
    の様なノードが前記樹木構造内に残らなくなるまで更に
    置き換えることを含む請求項（１０）の記載の方法。
12. （１２）減少された２つのモードを制御する方法が、前
    記検索の第１のモードに対して、検索路に沿うノードを
    与え、前記ノードの少なくとも幾つかが、他のノードを
    指し示す一つ以上のポインターを含み、 一連の検索引き数から成る検索引き数を与え、前記引き
    数のセグメントの幾つかの値が前記検索路に沿うノード
    に対応し、前記セグメントの幾つかの他の値が、前記検
    索の第２のモードに関係し、 ノードと関連する標識を与え、各標識が前記第２のモー
    ドに対応するセグメントを指示し、連続する検索セグメ
    ントを処理することにより前記検索路を検索し、前記処
    理が各ノードに関連する標識を検査し、前記セグメント
    が前記第２のモードに関連することを前記標識が指示す
    る場合前記第２の検索モードを処理することから成る方
    法。
13. （１３）前記標識が、前記セグメントが前記第２の検索
    モードに対応することを示さない場合、前記標識及び前
    記セグメントを検査して前記ポインターの一つを決め、
    前記検索を次のノードに続けることを更に含む請求項（
    １２）の方法。
14. （１４）各前記標識が、複数の前記セグメント値にそれ
    ぞれ関連する一連のビット内のビットであることを特徴
    とする請求項（１２）記載の方法。
15. （１５）前記検索の前記第２のモードが前記検索を終了
    することから成ることを特徴とする請求項（１２）記載
    の方法。
16. （１６）前記検索引き数がネットワーク内のシステムア
    ドレスから成ることを特徴とする請求項（１２）記載の
    方法。
17. （１７）検索路を階層的検索する方法が、 前記検索路に沿うノード階層を与え、前記ノードの少な
    くとも幾つかが、異なる階層レベルの他の前記ノードを
    指示する一つ以上のポインターを含み、 一連の検索セグメントから成る検索引き数を与え、前記
    引き数の連続するセグメントが前記検索路の沿う連続す
    るノードに対応し、 前記検索路を前記ノード内の連続する検索セグメントを
    処理することにより検索し、前記処理が前記ポインター
    を検査し、前記検索引き数が有効条件を満足する場合前
    記指示されたノードに進むことから成る方法。
18. （１８）前記有効条件が未処理セグメントの数を計数す
    ることから成ることを特徴とする請求項（１７）記載の
    方法。
19. （１９）前記有効条件が処理されたセグメントの数を計
    数することから成る請求項（１７）記載の方法。
20. （２０）前記検索引き数がコンピュータネットワークの
    システムアドレスであることを特徴とする請求項（１７
    ）記載の方法。
21. （２１）前記検索引き数が、ＩＳＯ８３４８／ＡＤ２に
    従うコンピュータネットワーク内のシステネアドレスを
    表し、 前記階層的検索が、第１階層レベルのレベル２検索及び
    第２階層レベルのレベル１検索から成り、 レベル２検索は、領域間の検索に対応し、レベル１検索
    は前記ネットワークの領域内の検索に対応することを特
    徴とする請求項（１８）記載の方法。
22. （２２）前記引き数がＩＳＯ８３４８／ＡＤ２に従うコ
    ンピュータネットワーク内のシステムアドレスを表して
    おり、 前記階層的検索が、第１の階層的レベルのＩＤＰ検索及
    び第２の階層的レベルのＤＳＰ検索から成ることを特徴
    とする請求項（１９）記載の方法。
23. （２３）検索引き数を、その幾つかが所定の値を有する
    セグメントに分解する方法が、 検索路に沿うノードを与え、前記ノードの少なくとも幾
    つかが、次の前記ノードを指示する一つ以上のポインタ
    ーを含み、各前記ポインターは前記セグメントの一つの
    可能な値に対応し、前記所定のセグメント値に対応する
    ポインターに、そのポインターを記憶するノードを次の
    ノードとして示させることから成る方法。
24. （２４）前記検索引き数がＩＳＯ８３４８／ＡＤ２に従
    うネットワークアドレスであり、前記所定の値が充填数
    の値であることを特徴とする請求項（２３）記載の方法
    。
25. （２５）コンピュータネットワーク経路決めに対する樹
    木形状経路決めデータベースを記憶するための装置が、 異なるアクセス時間及び電力要求を有する複数のメモリ
    ー素子を有し、各素子が２つ以上のノードに対する特定
    の形態のデータを記憶し、前記メモリー素子の選択が、 短アクセス時間を有するメモリー素子へ高速アクセスを
    必要とする形態のデータを記憶し、低電力消費を有する
    メモリー素子へより低速アクセスしか必要とない形態の
    データを記憶することにより前記メモリー素子の選択が
    行われることを特徴とする装置。
26. （２６）検索路内の前及び次のノード間に生じるノード
    を除去することにより減少した長さの検索を制御するた
    めの装置であり、 前記除去されたノードが存在した場合、前記検索が前記
    以下のノードに進むか否かに関する情報を記憶するメモ
    リー、 検索引き数を前記記憶情報と比較する比較器、前記比較
    が正の場合、前記検索を前記前のノードから前記次のノ
    ードに効率的に進ませる制御器からなる検索を制御する
    ための装置。
27. （２７）前記ノードの幾つかが前記検索に対する結果値
    を与え、その存在が前記検索に対する結果値に影響を与
    えない場合のみ除去されることを特徴とする請求項（２
    ６）記載の方法。
28. （２８）減少された２つのモード検索を制御する装置で
    あり、 前記検索の第１のモードに対して、検索路に沿うノード
    を記憶し、前記ノードの少なくとも幾つかが他の前記ノ
    ードを指し示す一つ以上のポインターを含むメモリー、 一連の検索セグメントから成る検索引き数を与え、この
    引き数のセグメントの幾つかの値が前記検索路に沿うノ
    ードに対応し、前記セグメントの幾つかの他の値は前記
    検索の第２のモードに関係するフェッチユニット、 ノードに関連する標識を記憶し、各標識が前記第２のモ
    ードに対応するセグメントを示すメモリー、 連続する検索セグメントを処理することにより前記検索
    路を検索し、前記処理が各ノードに関係する標識を検査
    し、前記セグメントが第２のモードに関係することを前
    記標識示す場合前記第２の検索モードに進む制御器から
    なることう特徴とする装置。
29. （２９）前記セグメントが前記第２の検索モードに対応
    することを前記標識が示さない場合、前記制御器が前記
    標識及び前記セグメントを検査して前記ポインターの一
    つを決定して、前記検索を次のノードに続けることを特
    徴とする請求項（２８）記載の装置。
30. （３０）各前記標識が複数の前記セグメント値とそれぞ
    れ関連する一連のビットの一つのビットであることを特
    徴とする請求項（２９）記載の装置。
31. （３１）前記検索路に沿うノードの階層を記憶し、前記
    ノードの少なくとも幾つかが異なる階層レベルの他の前
    記ノードを指示する一つ以上のポインターを含むメモリ
    ー、 一連のセグメントから成る検索引き数を与え前記引き数
    の一連のセグメントが前記検索路に沿う一連のノードに
    対応するフェッチユニット、前記ノード内の一連の検索
    セグメントを処理することにより前記検索路を検索し、
    前記処理が前記ポインターを検査し、前記検索引き数が
    有効条件を満足する場合前記指示されたノードに進む制
    御器からなる装置。
32. （３２）前記有効条件が未処理セグメントの数を計数す
    ることから成る請求項（３１）記載の方法。
33. （３３）前記有効条件が処理されたセグメントの数を計
    数することから成ることを特徴とする請求項（３１）記
    載の方法。
34. （３４）検索引き数を複数のセグメントに分解し、この
    セグメントの幾つかが所定の値を有する装置であって、
    この装置が、検索路に沿うノードを記憶するメモリーを
    有し、前記ノード少なくとも幾つかが次の前記ノードを
    指示する一つ以上のポインターを含み、各前記ポインタ
    ーが前記セグメントの一つの可能な値に対応し、前記所
    定のセグメントに対応するポインターがポインターを次
    のノードとして記憶するノードを指示することを特徴と
    する装置。