(57)【特許請求の範囲】
【請求項１】
サブツリーインデックスによってアクセスされる複数個のサブツリーエントリと、
第１のサブツリーエントリに記憶される稠密サブツリー記述子とを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに記憶される複数個の疎サブツリー記述子を含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、サブツリーの葉のための値を与えるルックアップテーブル。
【請求項２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項１に記載のルックアップテーブル。
【請求項３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するマッパ論理をさらに含む、請求項１に記載のルックアップテーブル。
【請求項４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項１に記載のルックアップテーブル。
【請求項５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項１に記載のルックアップテーブル。
【請求項６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項５に記載のルックアップテーブル。
【請求項７】
複数のサブツリーの葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項６に記載のルックアップテーブル。
【請求項８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項６に記載のルックアップテーブル。
【請求項９】
前記サブツリー葉によってサーチ可能な連想メモリと、
選択された疎サブツリー記述子において前記ノード記述子を選択し、前記ノード記述子を８ビット符号化値に変換し、前記８ビット符号化値を前記連想メモリに記憶する変換論理とをさらに含む、請求項８に記載のルックアップテーブル。
【請求項１０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項９に記載のルックアップテーブル。
【請求項１１】
サブツリーインデックスによってアクセスされる複数個のサブツリーエントリと、
第１のサブツリーエントリに記憶される稠密サブツリー記述子とを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに複数個の疎サブツリー記述子を記憶するための手段を含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、サブツリーの葉のための値を与えるルックアップテーブル。
【請求項１２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項１１に記載のルックアップテーブル。
【請求項１３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するための手段をさらに含む、請求項１２に記載のルックアップテーブル。
【請求項１４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項１２に記載のルックアップテーブル。
【請求項１５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項１２に記載のルックアップテーブル。
【請求項１６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項１５に記載のルックアップテーブル。
【請求項１７】
複数のサブツリーの葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項１６に記載のルックアップテーブル。
【請求項１８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項１７に記載のルックアップテーブル。
【請求項１９】
前記サブツリー葉によってサーチ可能な連想メモリと、
選択された疎サブツリー記述子において前記ノード記述子を選択し、前記ノード記述子を８ビット符号化値に変換し、前記８ビット符号化値を前記連想メモリに記憶する変換するための手段とをさらに含む、請求項１８に記載のルックアップテーブル。
【請求項２０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項１９に記載のルックアップテーブル。
【請求項２１】
サブツリーインデックスによって複数個のサブツリーエントリにアクセスするステップと、
第１のサブツリーエントリに稠密サブツリー記述子を記憶するステップとを含み、前記稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含み、さらに、
第２のサブツリーエントリに複数個の疎サブツリーを記憶するステップを含み、各疎サブツリー記述子は少なくとも１つのノード記述子を含む、ルックアップテーブルに実現されるサブツリーの葉のための値を与えるための方法。
【請求項２２】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項２１に記載の方法。
【請求項２３】
前記稠密サブツリー記述子において「１」にセットされたビットの数に依存して前記稠密サブツリーの葉に対応する値を選択するステップをさらに含む、請求項２１に記載の方法。
【請求項２４】
サブツリーエントリに複数個の疎サブツリー記述子を記憶するために設けられたビットの数は、前記稠密サブツリー記述子におけるビットの数に等しい、請求項２１に記載の方法。
【請求項２５】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項２１に記載の方法。
【請求項２６】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項２５に記載の方法。
【請求項２７】
複数のサブツリー葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項２６に記載の方法。
【請求項２８】
前記ノード記述子におけるビットの数は９であり、前記サブツリー葉におけるビットの数は８である、請求項２７に記載の方法。
【請求項２９】
前記サブツリー葉によってサーチ可能な連想メモリを設けるステップと、
選択された疎サブツリー記述子において前記ノード記述子を選択するステップと、
前記ノード記述子を８ビット符号化値に変換するステップと、
前記８ビット符号化値を前記連想メモリに記憶するステップとをさらに含む、請求項２８に記載の方法。
【請求項３０】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビット「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項２９に記載の方法。
【請求項３１】
複数レベルルックアップテーブル中のキーに対応するルートをサーチするための方法であって、
サブツリーインデックスによってサブツリーエントリを選択するステップを含み、前記サブツリーエントリは複数個の疎サブツリー記述子を含み、さらに
選択されたサブツリーエントリ中の前記複数個の疎サブツリー記述子のうち１つを選択するステップを含み、前記疎サブツリー記述子は複数個のノード記述子を含み、さらに
選択された前記疎サブツリー記述子中の前記ノード記述子をマスクされた値に変換するステップと、
前記マスクされた値を最長プレフィックスの順序でメモリにロードするステップと、
前記キーの部分の最長プレフィックス一致を求めて前記メモリをサーチするステップと、
前記最長プレフィックス一致のアドレスに依存して別のメモリに記憶される前記ルートを選択するステップとを含む、方法。
【請求項３２】
前記メモリは連想メモリである、請求項３１に記載の方法。
【請求項３３】
前記ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する、請求項３２に記載の方法。
【請求項３４】
前記ノード記述子は、ランレングス符号化を用いて符号化される、請求項３３に記載の方法。
【請求項３５】
前記ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい、請求項３４に記載の方法。
【請求項３６】
複数のサブツリー葉のためのマスクされた値は、「１」にセットされた最初の最下位ビットの位置に依存して前記ノード記述子に符号化される、請求項３５に記載の方法。
【請求項３７】
前記ノード記述子におけるビットの数は９であり、前記マスクされた値におけるビットの数は８である、請求項３６に記載の方法。
【請求項３８】
前記ノード記述子は、「１」にセットされた前記最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた前記最初の最下位ビットを除去することにより変換される、請求項３７に記載の方法。
【請求項３９】
前記ルックアップテーブルは、少なくとも１つの稠密サブツリーと、複数個の疎サブツリーとを含み、各疎サブツリー記述子に含まれるノード記述子の数は前記疎サブツリーの葉の数より少ない、請求項１に記載のルックアップテーブル。
【請求項４０】
前記ルックアップテーブルは、少なくとも１つの稠密サブツリーと、複数個の疎サブツリーとを含み、各疎サブツリー記述子に含まれるノード記述子の数は前記疎サブツリーの葉の数より少ない、請求項１１に記載のルックアップテーブル。
【請求項４１】
前記ルックアップテーブルは、少なくとも１つの稠密サブツリーと、複数個の疎サブツリーとを含み、各疎サブツリー記述子に含まれるノード記述子の数は前記疎サブツリーの葉の数より少ない、請求項２１に記載の方法。
【請求項４２】
各疎サブツリー記述子に含まれるノード記述子の数は前記疎サブツリーの葉の数より少ない、請求項３１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の背景】
インターネットはルータで接続された１セットのネットワークである。ルータは、受信したデータパケットを転送すべき次のホップを、各々の可能なデスティネーションネットワークごとに示すルーティングテーブルを維持する。次のホップとは、別のルータまたは最終的なデスティネーションであろう。
【０００２】
ルータのポートで受信されるインターネットプロトコル（ＩＰ）データパケットはＩＰデスティネーションアドレスを含む。ＩＰデスティネーションアドレスはＩＰデータパケットの最終デスティネーションである。現在、ＩＰバージョン４（ＩＰｖ４）およびＩＰバージョン６（ＩＰｖ６）の２つのＩＰバージョンが存在する。ＩＰｖ４は、ＩＰデスティネーションアドレスを記憶する、データパケットに含まれるＩＰヘッダに３２ビットのフィールドを設ける。ルータは、ＩＰヘッダに記憶されたＩＰデスティネーションアドレスに依存して、接続された受信データパケットを次のループのルータかまたは、デスティネーションがローカルネットワークであれば最終的なデスティネーションに転送する。
【０００３】
３２ビットＩＰｖ４デスティネーションアドレスは４０億の可能なルートをもたらす。インターネットルータは典型的に、４０億の可能なルートのうち５万を記憶する。しかしながら、記憶されるルートの数は、インターネットの発展およびＩＰｖ６の広がりによって増加している。
【０００４】
もともと、ＩＰアドレス空間は３つのクラスのＩＰアドレス、すなわちＡ，ＢおよびＣに分割されていた。各々のＩＰアドレス空間はネットワークアドレスおよびホストアドレスに分割された。クラスＡは、１２６のネットワークおよびネットワーク当り１６００万個のホストを許容した。クラスＢは、ネットワーク当り６４，０００個のホストを備えて、１６３８２個のネットワークを許容し、クラスＣは、ネットワーク当り２５６個のホストを備えて、２００万個のネットワークを許容した。しかしながら、ＩＰアドレス空間を異なるクラスに分割することにより、利用可能なＩＰアドレスの数が減少してしまった。クラスＣはネットワーク当り最大で２５６個のホストしか許容しないが、これは大抵の組織にとっては少なすぎる。したがって、大抵の組織にクラスＢアドレスを割当てて、６４，０００個のホストアドレスをとった。このホストアドレスは、それらを割当てられた組織が使用しなくても、他の組織が使用不可能なものである。クラスＢのＩＰアドレスを有する組織のホストのすべては、たとえば、２７．３２．ｘｘ．ｘｘなどの、１６の最上位ビット（ＭＢＳ）に同じネットワークアドレスを記憶する。
【０００５】
クラスレス・インタードメイン・ルーティング（ＣＩＤＲ）は、未使用のＩＰホストアドレスを自由化するために導入された。残余の未使用のネットワークは、サイズ可変のブロックで組織に割当てられる。５００個のアドレスを必要とする組織は５００個の連続するアドレスを入手する。たとえば、ある組織に、１２８．３２．ｘｘで始まる５００個の利用可能なアドレスを割当て可能である。ルータが記憶するルートの数は、クラスレス・インタードメイン・ルーティングの導入以来増加した。クラスレス・インタードメイン・ルーティングは、一致するネットワークアドレスをサーチしてＩＰデスティネーションアドレスの対応する次のホップを見出す代わりに、対応するルートを見出すのに最長プレフィックス一致を必要とする。たとえば、サーチは、たとえば１２８．ｘｘ．ｘｘなどのクラスＢのＩＰアドレスの１６ＭＳＢの後はもはやストップできない。なぜなら、１２８．３２．４．ｘｘは別の組織に割当てられ得るからであり、これには次の異なるホップを必要とする。
【０００６】
キーに対して最長プレフィックス一致をサーチするための１つの方法は、バイナリツリーサーチの使用によるものである。バイナリツリーサーチは、１ビットずつ３２のレベルまで３２ビット入力を一致させ、３２ビットのキーに一致するエントリを見出すには３２のサーチが必要である。一致をサーチするための別の方法はパトリシアツリーの使用によるものである。パトリシアツリーは、バイナリツリーの葉までにエントリが存在しなければ、必要なサーチ数を減らす。
【０００７】
ＩＰデスティネーションアドレスと関連する次のホップを効率的にサーチするためのまた別の方法が、１９９８年５月１１日に出願された、ブロドニックら（Brodnick et al.）による「高速ルーティングルックアップのための方法およびシステム」（“Method and System for Fast Routing Lookups”）と題された、ＰＣＴ出願連続番号ＰＣＴ／ＳＥ９８／００８５４に記載されている。ブロドニックが記載する方法は、重複するルートを記憶しないことで、記憶される次のホップの数を減じる。次のホップの数を減じることにより、メモリの必要量を低減し、それによりルートルックアップテーブルを高速キャッシュメモリに記憶できるようになる。
【０００８】
ブロドニックらは、バイナリツリーを３レベルに分割する。バイナリツリーを３つのレベルに分割することにより、サーチ数を３に減らした。第１のレベルのインデックス付けされたエントリは、ルートをエントリからとる場合、サーチを第１のレベルで終了可能であるかまたは、ＩＰデスティネーションアドレスのさらなる部分を用いて、その後のレベルまでサーチを継続しなければならないかを示す。
【０００９】
図１Ａは、バイナリツリーの第１のレベルを表わす先行技術の６４Ｋ（６５５３６）ビットマップを図示する。６４Ｋビットマップ３０は、深度１６のバイナリツリーの葉またはノード４４を表わし、ノード４４当り１ビットである。ビットマップは長さ１６のビットマスクに分割される。６４Ｋビットマップには２12＝４０９６のビットマスクが存在する。図１Ａに１つのビットマスクが示される。ビットマップ３０中のビットは、ノード４４に対応するポインタのアレイに記憶されたルートインデックスまたはサブツリーが存在すれば、‘１’にセットされる。ノードが前のノード４４とルートエントリを共有していれば、ビットマップ３０中のビットは、‘０’にセットされる。
【００１０】
図１Ｂは、キャッシュメモリに実現される先行技術のルックアップテーブルを図示する。ルックアップテーブルは、コードワード３６のアレイ、ベースインデックス３４のアレイおよびマップテーブル４０を含む。図１Ｂには３２ビットのＩＰアドレス３８も示される。コードワード４６は、ビットマップ３０（図１Ａ）の各ビットマスクごとにコードワード３６のアレイに記憶される。コードワード４６は６ビットの値４６ａおよび１０ビットのオフセット４６ｂを含む。ベースインデックス４２は、コードワード３６のアレイ中の４つのコードワード４６ごとに、ベースインデックス３４のアレイに記憶される。
【００１１】
コードワード３６のアレイ、ベースインデックス３４のアレイおよびマップテーブル４０を用いて、ポインタ（図示せず）のアレイ中のポインタを選択する。ポインタは、ルートインデックスまたはインデックスを記憶してさらなるサーチを行なう。
【００１２】
ポインタのアレイ中のポインタ群は、コードワード３６のアレイ中のコードワード４６およびベースインデックス３４のアレイ中のベースインデックス４２を選択することによって選択される。コードワード４６は、ＩＰアドレス３８の最初の１２ビット５０を用いて選択される。ベースインデックス４２は、ＩＰアドレス３８の最初の１０ビット４８を用いて選択される。マップテーブル３２を用いて、ポインタ群の中の正しいポインタが選択される。
【００１３】
選択されたコードワード３６中の１０ビットの値４６ｂは、マップテーブル３２へのインデックスである。マップテーブル３２は、ビットマスク内のビット数を４ビットのオフセットにマッピングする。オフセットは、ポインタのアレイの中の選択されたポインタ群内のポインタを特定する。１０ビットの値４６ｂはマップテーブル３２中の列を選択し、ＩＰアドレス５２のビット１９：１６は４ビットのオフセット５４を選択する。
【００１４】
このように、ポインタのサーチには、以下のキャッシュメモリアクセスが必要である。すなわち、（１）１６ビットのコードワード４６を読出す；（２）１６ビットのベースアドレス４２を読出す；（３）マップテーブル３２から４ビットのオフセット５４を読出す；（４）ポインタインデックスがベースアドレス４２、コードワードオフセット４６ａおよび４ビットのオフセット５４の和であるポインタインデックスでポインタを読出す。
【００１５】
バイナリツリーの各レベルで同じメモリアクセスが必要である。したがって、３レベルのサーチには１２のメモリアクセスが必要である。
【００１６】
ＩＰ宛先アドレスと関連付けられる次のホップのために効率よくサーチを行なうための方法が、１９９８年５月１１日に出願されたブロドニックらによる「高速ルーティングルックアップのための方法およびシステム」と題するＰＣＴ出願連続番号第ＰＣＴ／ＳＥ９８／００８５４号に記載される。ブロドニックらは、疎であるサブツリー；すなわち、８個未満のルートが記憶されるサブツリーに必要とされるバイトの数を低減するための方法を記載する。２４バイトのメモリが、疎サブツリーのための８個のルートを記憶するために割当てられる。２４バイトは、サーチキーに対応する値を記憶する８個の８ビットルートエントリのアレイと、各ルートエントリごとのそれぞれの１６ビットのポインタとを含む。
【００１７】
値は、降順にメモリのアレイに記憶される。アレイは、サーチキーより小さいまたは等しい値を見つけるためにサーチされる。メモリへの複数アクセスが必要とされる。多くとも７個のメモリアクセスが、サーチキーに対応する値を見つけるために必要とされ得る。
【００１８】
【発明の概要】
複数の疎サブツリー記述子がメモリのサブツリーエントリに記憶されることを可能にするルックアップテーブルが提供される。ルックアップテーブルは、サブツリーインデックスによってアクセスされる複数個のサブツリーエントリを含む。稠密サブツリー記述子が、第１のサブツリーエントリに記憶される。稠密サブツリー記述子は、稠密サブツリーの各葉ごとに値の表示を含む。複数個の疎サブツリー記述子が、第２のサブツリーエントリに記憶される。疎サブツリー記述子の各々は、少なくとも１つのノード記述子を含む。
【００１９】
ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する。メモリは、疎サブツリー記述子および稠密サブツリー記述子の両方を記憶する。稠密サブツリー記述子が第１のサブツリーエントリに記憶される。稠密サブツリー記述子は、稠密サブツリーの葉当り１ビットを含む。稠密サブツリー記述子は、稠密サブツリーの葉のための値を示す。複数個の疎サブツリー記述子が第２のサブツリーエントリに記憶される。各疎サブツリー記述子は、少なくとも１つのノード記述子を含む。ノード記述子は、疎サブツリーの一組の葉のための共通値を識別する。
【００２０】
マッパ論理が、稠密サブツリー記述子において「１」にセットされたビットの数に依存して稠密サブツリーの葉に対応する値を選択する。サブツリーエントリに疎サブツリー記述子を記憶するために設けられたビットの数は、稠密サブツリー記述子におけるビットの数に等しい。
【００２１】
ノード記述子は、ランレングス符号化を用いて符号化される。ノード記述子におけるビットの数は、サブツリー葉におけるビットの数に１を加えたものに等しい。複数のサブツリー葉のための値は、「１」にセットされた最初の最下位ビットの位置に依存してノード記述子に符号化される。ノード記述子におけるビットの数は９であり、サブツリー葉におけるビットの数は８である。
【００２２】
サブツリー葉によってサーチ可能な連想メモリが設けられる。変換論理が、選択された疎サブツリー記述子においてノード記述子を選択し、ノード記述子を８ビット符号化値に変換し、８ビット符号化値を連想メモリに記憶する。ノード記述子は、「１」にセットされた最初の最下位ビットの右側の最下位ビットを「ドントケア」にセットし、「１」にセットされた最初の最下位ビットを除去することにより変換される。
【００２３】
この発明の以上およびその他の目的、特徴および利点は、添付の図面に図示されるように、この発明の好ましい実施例の以下のより特定的な説明から明らかになるであろう。図面中の同じ参照番号は異なる図面を通じて同じ部分を示す。図面は、この発明の原則を図示するのに供される代わりに、縮尺を変更したり、強調したりということを必ずしも行なわなくてよい。
【００２４】
【詳細な説明】
この発明の好ましい実施例の説明は以下のとおりである。
【００２５】
デンスモード
図２Ａは、この発明の原則に従う最長一致プレフィックスルックアップテーブル１００を図示する。ルックアップテーブル１００はキー１０４のルートインデックス１０２を与える。ルートインデックス１０２を用いて、ＩＰデスティネーションアドレスに向けた次のホップにアクセスする。図２Ａに示された実施例では、キー１０４は３２ビット幅であるが、キー１０４は３２ビットに限定されるものではない。ルックアップテーブル１００は３つのマッパ１０６ａ−ｃを含む。各々のマッパ１０６ａ−ｃは別個にアドレス指定されたメモリを含む。キー１０４に対応するデフォルトルートインデックスまたはルートインデックス１０２は、マッパ１０６ａ−ｃのうち１つの中の場所に記憶される。各マッパからのマッパ出力１１０ａ−ｃは、多数のマッパをサーチする必要がある場合、キーについてすべてのマッパ１０６ａ−ｃにアクセスするまで、遅延メモリ１５０ａ−ｃに記憶される。
【００２６】
マルチプレクサ１０８は、マルチプレクサ１０８の入力に転送されるマッパ出力１１０ａ−ｃの１つをルートインデックス１０２として選択する。マッパ出力１１０ａ−ｃは、マッパ出力１１０ａ−ｃの最上位ビット（ＭＳＢ）に依存して選択される。マッパ出力１１０ａ−ｃがルートインデックス１０２を含む場合のみ、マッパ出力１１０ａ−ｃのＭＳＢが‘１’となる。
【００２７】
図２Ｂは、図２Ａに示されたルックアップテーブル１００のマッパ１０６ａ−ｃに記憶されたエントリのバイナリツリー表示を図示する。図２Ｂは図２Ａと関連して説明される。３２ビットのキー１０４は３２レベルのバイナリツリーとして表わすことができる。バイナリツリー実現例は、１ビットずつ３２レベルまでサーチするには、３２のサーチを必要とする。サーチ数を減らすため、バイナリツリーの３２のレベルは３つのマッパレベル１１２ａ−ｃに分割され、各マッパレベル１１２ａ−ｃはマッパ１０６ａ−ｃ（図２Ａ）に対応する。マッパレベル＿１  １１２ａは、バイナリツリーの３２のレベルのうち最初の１６個を含む。しかしながら、簡潔さのため、図２Ｂには１６のレベルのうち５つしか示されない。マッパレベル＿２  １１２ｂは、３２レベルのバイナリツリーの次の８レベルを含み、図２Ｂには８つのレベルのうち３つが示される。マッパレベル＿３は、３２レベルのバイナリツリーのうち最後の８レベルを含み、図１Ｂには８つのレベルのうち３つが示される。各マッパレベル１１２ａ−ｃは複数のノードを含む。１６レベル（キー１０４の１６のＭＳＢ）がマッパレベル−１  １１２ａにあり、８レベルがマッパレベル＿２  １１２ｂにありかつ８レベルがマッパレベル＿３にあるように３２レベルを分割することが、現在のメモリ技術においては最適であるように思われるが、この発明はこの構成に限定されるものではない。
【００２８】
キー１０４の最初の１６ビットに対して１ビットずつ別個の１６のサーチを行なう代わりに、キー１０４の最初の１６ビットと関連するルートインデックス１０２をマッパ１０６ａ（図２Ａ）に記憶する。マッパ１０６ａ（図２Ａ）は、キー１０４の最初の１６ビットのＭＳＢによって直接にインデックス付けされる。次のマッパ１０６ｂは、前のマッパ１０６ａが、キー１０４と関連する次のホップ情報にアクセスするのに用いるルートインデックス１０２を記憶しているか否かに依存して、サーチされる。
【００２９】
図２Ｂに示されるように、マッパレベル＿１  １１２ａに示されるノードまたは葉は、それぞれｒ０およびｒ１と標識付けられた２つのルート１１４、１１６と、それぞれｓ０およびｓ１と標識付けられたマッパレベル＿２  １１２ｂへの２つのポインタ１３０4および１３０23とを含む。各ルート１１４、１１６ごとのルートインデックス１０２はＬ１マッパ１０６ａに記憶される。また、Ｌ２マッパ１０６ｂに向けたアドレスポインタ１２０はサブツリーインデックス１３０4に対して記憶され、Ｌ２マッパ１０６ｂに向けたアドレスポインタ（図示せず）はサブツリー１３０23に対して記憶される。サブツリーインデックス１３０4に対して、マッパ１０６ａ中のマッパエントリ１４０4に記憶されるアドレスポインタ１２０は、キー１０４と関連のルートインデックス１０２を見出すためには、次のレベルのサーチが必要であることを示す。
【００３０】
ツリー中のいずれのノードの値も、根１１４からの経路をトレースすることによって判定することができる。バイナリツリー中の各ノードは、右側の子および左側の子の２つの子を有して示される。親ノードが‘１’ならば右側の子が選択される。親ノードが‘０’ならば左側の子が選択される。根１１４からノード１１６への経路をトレースすると、ｒ１は、‘０１０’にセットされたＭＳＢを有するすべてのキーに対して、Ｌ１マッパ１０６ａ中にルートインデックス１０２として記憶される。根ノード１１４からｓ０ノード１３０4への経路をトレースすると、ｓ０は、‘０００１１’にセットされたＭＳＢを有するすべてのキーに対してＬ１マッパ１０６ａに記憶される。
【００３１】
Ｌ１マッパ１０６ａはダイレクト・マップト・マッパであり、マッパレベル＿１  １１２ａのボトムレベルの各ボトムレベルノードまたは葉ごとにルートインデックス１０２を記憶する。マッパレベル＿１  １１２ａのボトムレベルは、３２レベルバイナリツリーの１６番目のレベルである。１６番目のレベルは６４Ｋのノードを有する。しかしながら、例示の目的のため、マッパレベル＿１  １１２ａのボトムレベルは、３２レベルのバイナリツリーのレベル−５として示される。Ｌ１マッパ１０６ａに示されるルートインデックス１０２は、マッパレベル＿１  １１２ａのレベル−５の１３０1−１３０32ノードに対応する。根ノード１１４からレベル＿５のノード１３０1、１３０2、１３０3への経路をトレースすると、ルートインデックス１０２はｒ０である。したがって、ｒ０は、Ｌ１マッパ１０６ａの場所１４０1、１４０2、１４０3に、すなわち、インデックス０００００、００００１および０００１０に記憶される。ノード１３０4はサブツリーインデックスｓ０を記憶し、したがって、ｓ０は、アドレス０００１１に、Ｌ１マッパ１０６ａの中の場所１４０4に記憶される。同様に、レベル−５のノード１３０5−１３０8に対するルートインデックス１０２はｒ０であり、したがって、Ｌ１マッパ１０６ａの中のアドレス００１００、００１０１、００１１０および００１１１の場所１４０5、１４０6、１４０7、１４０8はｒ０を記憶する。レベル−５のノード１３０9−１３０12に対するルートインデックス１０２はｒ１であり、したがって、Ｌ１マッパ１０６ａの中のアドレス０１０００および０１０００１の場所１４０9、１４０10はｒ１を記憶する。
【００３２】
Ｌ１マッパ１０６ａ中の各々の場所は、直接にもしくはレベル−５のノード３００1-32の親を介してレベル−５のノード３００1−３００32に割当てられるルートインデックス１０２または次のマッパ１０６ｂ−ｃへのアドレスポインタを記憶する。マッパレベル＿３  １０６ｃは、３２レベルのバイナリツリーのボトムレベルで、ノード１３８のｈ０およびノード１４０のｈ１の２つのホストノードを含む。ホストノードのサーチは、キー１０４のすべてのビットのサーチを必要とする。図２Ａに示されるように、ｈ０に対するルートインデックス１０２は、Ｌ３＿マッパ１０６ｃ中の場所１４６4に記憶される。Ｌ１マッパ１０６ａと異なり、Ｌ２マッパ１０６ｂおよびＬ３マッパ１０６ｃは直接にマッピングされない。
【００３３】
マッパ１０６ｂおよび１０６ｃでは、ルートインデックス１０２は各々の可能な入力ごとに記憶されない。ノードに対するルートインデックス１０２がマッパ１０６ｂ−ｃに以前に記憶されたルートインデックス１０２と異なる場合にのみ、ルートインデックス１０２が記憶される。マッパレベル＿２  １１２ｂに示される第１のサブツリーＡのレベル−３ノードを見ると、ノード１３２1およびノード１３２2に対するルートインデックス１０２はｒ０であり、したがって、ｒ０に対するルートインデックスは、Ｌ２マッパ１０６ｂの中のノード１３２1およびノード１３２2の両者について、場所１４２1に記憶される。ノード１３２2に対するサブツリーインデックスｓ０は場所１４２2に記憶される。レベル−３のノード１３２4およびレベル−３のノード１３２5および１３２6と関連のルートインデックス１０２はｒ０であり、これは、前のノード１３２2に対して記憶されたｓ０とは異なる。したがって、ｒ０はＬ２マッパ１０６ｂ中の次の場所１４２3に記憶される。ルートｒ２は、ノード１３２7に対して、Ｌ２マッパ１０６ｂ中の場所１４２4に記憶される。なぜなら、ノード１３２7は前のノード１３２6と同じルートを共有しないからである。サブツリーインデックスｓ３は次のレベル−３のノード１３２7に対して記憶される。したがって、ｓ３はＬ２マッパ１０６ｂの中の場所１４２5に記憶される。前のノードからルート変更があるときにだけルートインデックスを記憶することにより、ルートインデックス１０２を記憶するのに必要なメモリが低減される。示されるように、マッパレベル＿２  １１２ｂの第１のサブツリーＡのレベル−３の８つのノード１３２1-8についてルートインデックスを記憶するためには、Ｌ２マッパ１０６ｂの中の場所は５つしか必要でない。ノンダイレクトマッパ１０６ｂ、１０６ｃは、図５と関連してより詳細に後述される。
【００３４】
図３は、この発明の原則に従う４０ビットのキー２１０のための最長一致プレフィックスルックアップテーブル２００を図示する。１つの実施例では、４０ビットのキーは、８ビットのプレフィックスおよび３２ビットのＩＰアドレスを含む。８ビットのプレフィックスは、３２ビットのＩＰアドレスと関連する仮想私設網（ＶＰＮ）識別子であり得る。ルックアップテーブル２００は４つのマッパ１０６ａ−ｄを含む。マッパ１０６ａは、図２Ａと関連して説明されたように、ダイレクト・マップト・マッパである。マッパ１０６ｂ−ｄはインダイレクトマッパである。マッパ１０６ａは、４０ビットのキー２１０の１６のＭＳＢに対応する、Ｌ２マッパ１０６ｂに対するサブツリーインデックスまたはルートインデックス１０２を記憶する。したがって、Ｌ１マッパは、第１のマッパレベル１１２ａ（図２Ｂ）中の６４Ｋのノードの各々ごとに１つの、６４Ｋの可能な場所を有する。Ｌ１マッパ１０６ａ中の対応する場所に記憶されるＬ１マッパエントリデータ２２０ａは、パイプライン２０８およびＬ２インダイレクトマッパ１０６ｂに転送される。Ｌ１マッパエントリデータ２２０ａが、キー２１０ｂの次の８ビットを用いる次のレベルのサーチが必要であることを示せば、キー２１０ｂの次の８ビットおよびＬ１マッパエントリデータ２２０ａに依存して、Ｌ２インダイレクトマッパ１０６ｂでサーチが行なわれる。
【００３５】
第２のレベルのサーチの結果がＬ２マッパエントリデータ２２０ｂ上に与えられ、これはパイプライン２０８およびＬ３インダイレクトマッパ１０６ｃに転送される。第３のレベルのサーチは、キー２１０ｃの次の８ビットおよびＬ２マッパエントリデータ２２０ｂに依存して、Ｌ３インダイレクトマッパ１０６ｃで行なわれる。
【００３６】
サーチの結果は、Ｌ３マッパエントリデータ２２０ｃ上を、パイプライン２０８およびＬ４インダイレクトマッパ１０６ｄに与えられる。Ｌ３マッパエントリデータ２２０ｃは、キー２１０ｄの最後の８ビットおよびＬ３マッパエントリデータ２２０ｃに依存して、Ｌ４インダイレクトマッパ１０６ｄで行なわれる。
【００３７】
第４のサーチの結果はＬ４マッパエントリデータ２２０ｄ上に与えられる。キー２１０に対する最長一致プレフィックスと関連するルートインデックス１０２は、マッパ１０６ａ−ｄのうちの１つの中のただ１つの場所に記憶される。したがって、パイプライン２０８に転送されるルートインデックス１０２は、ただ１つのマッパエントリデータ２２０ａ−ｄに含まれる。マッパ１０６ａ−ｄのうち１つ、たとえばマッパ１０６ｂにルートインデックス１０２を見出すと、残余のマッパ１０６ｃ−ｄのサーチは必要ではなく、マッパ１０６ｃ−ｄはアクセスされない。パイプライン２０８は、マッパエントリデータ２２０ａ−ｄのうち１つに含まれるルートインデックス１０２を選択するためのマルチプレクサ１０８（図２Ａ）を含む。たとえば、マッパエントリデータ２２０ａ−ｄのＭＳＢは、ルートインデックスが含まれているか否かの表示を与えることができる。
【００３８】
マッパ１０６ａ−ｄと関連してパイプライン２０８を用いることにより、異なるキー２１０による最長一致プレフィックステーブル２００の複数サーチを並行して行なうことができる。パイプライン２０８は、４０ビットのルックアップテーブル２００の複数のサーチを、必要に応じて、他のマッパ１０６ａ−ｄの各々のサーチが完了するまで、４０ビットのキー２１０と関連の各マッパ１０６ａ−ｄごとにマッパエントリデータ２２０ａ−ｄを記憶することによって並行して行なって、４０ビットキー２１０に対応するルートインデックスを見出すのを可能にする。したがって、ダイレクト・マップト・マッパ１０６ａへの単一のメモリアクセスを行なうことにより、受信したＩＰアドレスに対応するルートインデックスに対するサーチリクエストがルックアップテーブル２００に発せられる。別のキーに対応するルートインデックスに対するその後のサーチは、ダイレクト・マップト・マッパ１０６ａのための次のメモリアクセスサイクルの中でルックアップテーブル２００に発せられ得る。
【００３９】
図４は、図３に示されたダイレクト・マップト・マッパ１０６ａに記憶可能なマッパエントリのタイプを図示する。図２Ｂに示されたバイナリツリー中のいずれのノードに対するマッパエントリも、ノーエントリ３００、ルートエントリ３０２またはサブツリーエントリ記述子３０４を記憶することができる。マッパエントリ３００、３０２、３０４の各タイプは、サブツリーフラグ３０６を含む。サブツリーフラグ３０６の状態は、マッパエントリがサブツリーエントリ記述子３０４であるか否かを示す。サブツリーフラグ３０６が‘１’にセットされれば、マッパエントリはサブツリーエントリ記述子３０４であり、サブツリーインデックス３１２を含む。サブツリーインデックス３１２は、次のノンダイレクト・マップト・マッパ１０６ｂ−ｄに記憶されるサブツリーエントリ記述子３０４のアドレスである。サブツリーエントリは図４と関連して後述される。サブツリーフラグ３０６が‘０’ならば、ノーエントリフラグ３１４をチェックして、マッパエントリがノーエントリ３００であるかまたはルートエントリ３０２であるかを判定する。ノーエントリフラグ３１４が‘０’ならば、エントリはノーエントリ３００である。ノーエントリフラグ３１４が‘１’ならばエントリはルートエントリ３０２であり、ルートインデックスフィールド３１０中に、キー１０４と関連のルートインデックス１０２（図３）を記憶する。マルチプレクサ１０８（図２Ａ）は、サブツリーフラグ３０６を用いて、ルートインデックス１０２（図３）を含むマッパエントリデータ２２０ａ−ｄを選択する。
【００４０】
図５は、図２Ｂに示されたマッパレベル＿２  １１２ｂ中のノードに対応するマッパ１０６ｂを図示する。マッパ１０６ｂは、サブツリーメモリ４００、マッパアドレス論理４０２およびサブツリーマッパ４１８を含む。マッパ１０６ａに記憶されるキー２１０ａの最初の部分によって選択されたサブツリーインデックス３１２は、サブツリーメモリ４００に転送される。サブツリーメモリ４００は、サブツリーインデックス３１２が選択するサブツリーエントリ４０４を含む。サブツリーエントリ４０４はデータフィールド４０６およびポインタフィールド４０８を含む。
【００４１】
図２Ｂに戻って、サブツリーエントリ４０４は、マッパレベル＿２  １１２ｂに示されるサブツリーのうちの１つのボトムレベルに対応する。マッパレベル＿２  １１２ｂが８つのレベルを有すれば、各サブツリー（図示せず）のボトムレベルは、各ノードに１つの、最大２５６のルートを有する。
【００４２】
続いて図５で、サブツリーエントリ４０４は、サブツリーのボトムレベル上の各ノードに対応する２５６の可能なルートインデックス１０２（図３）へのアクセスを提供する。ルートインデックス１０２（図３）はサブツリーマッパ４１８に記憶される。２５６の可能なルートインデックスへのアクセスを提供するため、稠密サブツリー記述子がデータフィールド４０６に記憶される。データフィールド４０６は２５６ビット幅であり、サブツリーのボトムレベルで各ノードごとに１ビットを与える。データフィールド４０６は、図６Ａおよび図６Ｂと関連してより詳細に後述される。ポインタフィールド４０８は２５６ビット幅であり、１６の１６ビットポインタの記憶を可能にする。各ポインタは、サブツリーマッパ４１８中に、連続した１６のマッパエントリに対するベースアドレスを記憶して、２５６のルートインデックスへのアクセスを与える。したがって、ポインタフィールド４０８は、サブツリーのボトムレベルの各ノードごとにサブツリーマッパ４１８中のマッパエントリへのポインタを間接的に与えることができる。ポインタフィールド４０８は図６と関連してより詳細に説明される。
【００４３】
データフィールド４０６中の稠密サブツリー記述子に記憶されたサブツリーデータ４１２とポインタフィールド４０８に記憶されたサブツリーポインタ４１４とはマッパアドレス論理４０２に転送される。マッパアドレス論理４０２は、キー２１０ｂの次の部分（次の８ビット）も受ける。
【００４４】
マッパアドレス論理４０２は、キー２１２ｂの次の８ビットに依存するサブツリーのボトムレベルのノードと関連のマッパエントリ、すなわちサブツリーデータ４１２およびサブツリーと関連のサブツリーポインタ４１４のマッパアドレス４１６を判定する。マッパアドレス４１６は、サブツリーマッパ４１８中のマッパエントリを選択する。サブツリーマッパ４１８は、ダイレクト・マップト・マッパ１０６ａに対して、図４と関連して説明されたのと同じタイプのマッパエントリを含む。マッパデータエントリ２２０ｂの中身が、その後のサーチが必要であるか否かを決定する。マッパエントリデータ２２０ｂが、次のマッパレベル１１２ｃ（図２Ｂ）中に別のサブツリーエントリ４０４が存在することを示すサブツリーインデックス３１２（図４）を含めば、その後のサーチが必要である。
【００４５】
キー２１０ｂの第２の部分は、選択されたサブツリーのボトムレベル中のノードを選択する。サブツリーポインタ４１４は、サブツリー中のノードと関連のベースアドレスを選択し、サブツリーデータ４１２は、ベースアドレスと関連のマッパエントリのブロック内のオフセットを選択する。マッパアドレス論理４０２は、図７と関連して後述される。
【００４６】
図６Ａはサブツリーのバイナリツリー表示である。示されたサブツリーは５つのレベルを含む。サブツリーは、３つのルートインデックスｒ１、ｒ２およびｒ３ならびに２つのサブツリーインデックスｓ０およびｓ１を含む。サブツリーのボトムレベルには３２個のノード５００1−５００32が存在する。ボトムレベルの各ノード５００1−５００32と関連のルートインデックスまたはサブツリーインデックスが以下の表１に示される。
【００４７】
【表１】
0004741134.tif 000002
【００４８】
図６Ｂは、図６Ａに示されたサブツリーのボトムレベル中のノードに対応する、図５に示されたデータフィールド４０６に記憶された稠密サブツリー記述子を図示する。データフィールド４０６は、図６Ａに示されたサブツリーのボトムレベル中の各ノード５００ごとに１ビットの、３２ビットを含む。データフィールド４０６中のビット５０２1−５０２32は以下のように割当てられる。前のノードのルートインデックスを用いるならば、データフィールド４０６中のビットを‘０’にセットし、サブツリーマッパ４１８（図５）に記憶された次のルートインデックスを用いるならば、‘１’にセットして次のマッパエントリアドレスを増分する。ルートが特定されなければ、データフィールド４０２中の最初のビットは、マッパエントリ５０４1に記憶されたデフォルトルートｒ０を選択する。特定されたルートがないため、こうして、ビット５０２1を‘０’にセットしてデフォルトルートを選択する。マッパエントリ５０４1に記憶されたデフォルトルートｒ０は、次の３つのノード５００2−５００4に対して選択され、すなわち、対応するビット５０２2−５００4はデータフィールド４０６中で‘０’にセットされて、５０２1が用いた前のルートインデックスを用いる。ノード５００5ではルート変更がある。
【００４９】
マッパエントリ５０４2に記憶される、ノード５００5に用いられるルートｒ１はノード５０６6と共有される。したがって、ビット５０２5は、ルート変更を示す‘１’であり、サブツリーマッパ４１８（図５）中のマッパエントリ５０４2を選択する。ビット５０２6は、５０２5に記憶されるルートインデックスをこのノードに用いるべきであることを示す‘０’である。ノード５００7に対してはいずれのルートも与えられないため、ルート変更があり、デフォルトルートｒ０を記憶するサブツリーマッパ４１８（図５）中のマッパエントリ５０４3を必要として、ビット５０２7に‘１’が記憶される。
【００５０】
ノード５００8は前のノード５００7と同じルートを共有し、サブツリーマッパ４１８（図５）で新たなマッパエントリは必要ない。ノード５００8に対応するビット５０２8は‘０’にセットされる。ノード５００9は前のノード５００8とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなマッパエントリが必要である。ノード５００9に対応するビット５０２9は‘１’にセットされ、次の連続するメモリ場所中のサブツリーマッパ４１８（図５）に、ｒ２を記憶するマッパエントリ５０４4が加えられる。
【００５１】
ノード５００10は、前のノード５００9とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなルートエントリが必要である。ノード５００10に対応するビット５０２10は‘１’にセットされ、ｓ０を記憶するマッパエントリ５０４5が、次の連続するメモリ場所中のサブツリーマッパ４１８（図５）に加えられる。
【００５２】
ノード５００11は、前のノード５００10とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなマッパエントリが必要である。ノード５００11に対応するビット５０２11は‘１’にセットされ、ｒ２を記憶するマッパエントリ５０４6が、次の連続するメモリ場所中のサブツリーマッパ４１８（図５）に加えられる。
【００５３】
ノード５００12および５００13は、前のノード５００11と同じルートを共有し、サブツリーマッパ４１８（図５）で新たなマッパエントリは必要ない。ノード５００12に対応するビット５０２12およびノード５００13に対応するビット５０２13はデータフィールド４０６中で‘０’にセットされる。
【００５４】
ノード５００14は前のノード５００13とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなマッパエントリが必要である。ノード５００14に対応するデータフィールド４０６中のビット５０２14は‘１’にセットされ、ｓ１を記憶するマッパエントリ５０４7がサブツリーマッパ４１８（図５）に加えられる。ノード５００15は前のノード５００14とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなマッパエントリが必要である。ノード５００15に対応する、データフィールド中のビット５０２15は‘１’にセットされ、サブツリーマッパ４１８（図５）に、ｒ２を記憶するマッパエントリ５０４8が加えられる。ノード５００16は前のノード５００15と同じルートを共有し、サブツリーマッパ４１８（図５）で新たなマッパエントリは必要ない。
【００５５】
ノード５００17は前のノード５００16とは異なるルートを有し、サブツリーマッパ４１８（図５）で新たなマッパエントリが必要である。ノード５００17に対応する、データフィールド４０６中のビット５０２17は‘１’にセットされ、ｒ３を記憶するマッパエントリ５０４9がサブツリーマッパ４１８（図５）に加えられる。
【００５６】
ノード５００18−５００32はすべてノード５００17と同じルートを共有し、サブツリーマッパ４１８（図５）で新たなマッパエントリは必要ない。対応するビット５０２18−５０２32は‘０’にセットされる。したがって、３２個のノード５００1−５００32について、ルートエントリ３０２（図４）またはサブツリーエントリ３０４（図４）を記憶するには、マッパエントリ５０４1-9が９つ必要である。
【００５７】
ノード５００1−５００32に対応するマッパエントリ５０４1−５０４9は、データフィールド４０６に記憶される稠密サブツリー記述子に記憶される‘１’の数を計算することにより、サブツリーマッパ４１８（図５）中でインデックス付けされる。たとえば、ノード５００28に対応するマッパエントリ５０４1−５０４9を見出すには、データフィールド４０６のビット５０２1−５０２28に記憶される‘１’の数をカウントする。‘１’の数が８であると、対応するマッパエントリはデフォルトルートから８番目の場所、すなわち、マッパエントリ５０４9である。
【００５８】
ルート変更がある場合にのみマッパエントリを記憶することにより、サブツリーマッパ４１８（図５）中のサブツリー当りのマッパエントリ５０４1−５０４9の数が減少する。
【００５９】
図７は図５に示されたポインタフィールド４０８を図示する。ポインタフィールド４０８は、サブツリーマッパ４１８（図５）中の連続する１６のマッパエントリ場所５０４1−５０４16（図６Ｂ）のブロックのベースアドレスを記憶するためのブロックベースアドレスフィールド６００1、６００2を含む。連続する１６のマッパエントリのブロック６０２1、６０２2中のサブツリーマッパ４１８（図５）にメモリが割当てられる。８レベルのサブツリーは異なるルートを２５６まで有することができ、２５６のすべてのルートを記憶するためには、ブロック６０２1、６０２2が１６個必要である。必要なブロック６０２の数は、サブツリーに対するルートの数に依存する。ブロックベースアドレス６０２1、６０２2をブロックベースアドレス（図示せず）のフリーリストから除くことにより、ブロック６０２を特定のサブツリーに割当てる。メモリにアドレスのフリーリストを与えるための方法は技術分野では周知である。
【００６０】
１６のマッパエントリ５０４1-16のメモリブロックを割当てることにより、サブツリーマッパ４１８（図５）中のメモリの扱いがより容易になる。なぜなら割当てられた１６個の場所は連続しているからである。
【００６１】
図８は、図５に示されたマッパアドレス論理４０２を図示する。マッパアドレス論理４０２は、オフセット論理７００、ポインタ論理７０２およびアダー論理７０４を含む。オフセット論理７００はノードセレクト論理７０６および１カウント論理７０８を含む。ポインタ論理はベースアドレスセレクト論理７１０を含む。
【００６２】
ノードセレクト論理７０６は、キー２１０ｂの８ビットに対応する、サブツリーデータ４１２中のノード５００（図６Ｂ）を選択する。対応するノード番号はノードセレクト７１８上を１カウント論理７０８に転送される。１カウント論理７０８は、サブツリーデータフィールド４０６に記憶された‘１’の数を、選択されたノード５００に対応するビットまでカウントする。１の数はブロックセレクト７１２上をポインタ論理７０２へおよびブロックオフセット７１４上をアダー論理７０４へ転送される。
【００６３】
８ビット幅のカウントフィールドを必要とする２５６ビットのサブツリーデータフィールド４０６に記憶される‘１’は最大で２５６個であり得る。８ビットカウントフィールドは２つのフィールドに分割され、４つのＭＳＢがブロックセレクト７１２を与え、４つの最下位ビット（ＬＳＢ）がブロックオフセット７１４を与える。
【００６４】
たとえば、８ビットキー２１０ｂが‘０１０００１００’である場合、ノード番号６８を選択し、サブツリーデータ４１２の最初の６８ビットに記憶される‘１’が２７個存在すれば、カウントは１Ｃ  Ｈｅｘ（０００１１１００）、ＭＳＢ（０００１）である。すなわち、ブロックセレクト７１４、セレクトブロック６０２1（図６）およびＬＳＢ（１１００）である。すなわち、ベースブロックオフセットセレクトマッパエントリ５０４11（図６）であり、すなわちブロック５０２1中の１２番目のエントリである。
【００６５】
ベースアドレスセレクト論理７１０は、オフセット論理７００から転送されるブロックセレクト７１２に依存して、サブツリーポインタ４１４からベースアドレス７１６を選択する。アダー論理７０４は、オフセット論理７００から転送されるブロックオフセット７１４をベースアドレス７１６に加算し、マッパアドレス４１６を与える。マッパアドレス４１６はマッパ１０６ｂ−ｄ中のマッパエントリ５０４（図６Ｂ）のインデックスである。
【００６６】
図９は、この発明の原則に従う、ルックアップテーブル２００中のキー２１０（図３）に対して最長一致プレフィックスをサーチするためのステップを図示するフローチャートである。
【００６７】
ステップ８００で、キー２１０ａ（図３）の最初の部分がマッパ１０６ａへのインデックスとして転送される。処理はステップ８０２に継続する。
【００６８】
ステップ８０２で、キー２１０ａ（図３）の最初の部分によってインデックス付けされた第１のレベルのマッパ中のマッパエントリ５０４（図６Ｂ）に記憶されたマッパエントリデータ２２０ａ（図３）は、次のレベルのさらなるサーチが必要であるか否かを判定する。必要ならば、処理はステップ８０４に継続する。必要なければ、第１のレベルのマッパ中のインデックス付けされたマッパエントリ５０４（図６Ｂ）中のルートエントリ３０２（図４）が、キーに対して、対応する最長プレフィックスルートを記憶し、処理はステップ８０８に継続する。
【００６９】
ステップ８０４で、次のレベルのマッパ１０６ｂ−ｄがサーチされる。次のレベルのマッパのためのインデックスは、前のレベルのマッパ中のインデックス付けされたマッパエントリ５０４（図６Ｂ）中のサブツリーエントリ記述子３０４（図４）に記憶されたサブツリーインデックス３１２と、キー２１０ｂ−ｄの次の部分とに依存する。処理はステップ８０６に継続する。
【００７０】
ステップ８０６で、次のレベルのマッパ中のインデックス付けされたマッパエントリ５０４（図６Ｂ）は、キーに対する、対応する最長プレフィックスルートインデックスまたはさらなるサーチが必要であることを示すサブツリーインデックスを記憶する。さらなるサーチが必要ならば、処理はステップ８０４に継続する。必要なければ、処理はステップ８０８に継続する。
【００７１】
ステップ８０８で、マッパ１０６ａ−ｄのうち１つの中のマッパエントリ５０４（図６Ｂ）に記憶されたルートインデックス１０２（図３）は、ルートインデックス１０２（図３）としてルックアップテーブル２００から転送される。処理は完了する。
【００７２】
深度拡張（depth expansion）
図３に示されたルックアップテーブル２００に記憶可能なルートインデックス１０２（図３）の数は、サブツリーマッパ４１８（図５）中の利用可能なマッパエントリ５０４（図６Ｂ）の数によって限定される。たとえば、各々のサブツリーマッパ４１８（図５）が１２８Ｋのマッパエントリを含みかつルックアップテーブル中にサブツリーマッパ４１８（図５）が２つ存在すれば、ルックアップテーブル２００中に最大で２５６Ｋのルートインデックス１０２（図３）を記憶可能である。１２８Ｋのマッパエントリを有するサブツリーマッパ４１８（図５）は１７ビットのインデックスを必要とする。５１２Ｋのマッパエントリを有するサブツリーマッパ４１８（図５）は１９ビットのインデックスを必要とする。ルックアップテーブル２００中の２つの５１２Ｋサブツリーマッパ４１８（図５）は、３２ビットＩＰｖ４デスティネーションアドレスのために、可能な４０億個のルートインデックス１０２（図３）のうち１００万個のための記憶を提供する。
【００７３】
ルートインデックス１０２（図３）を記憶するためのマッパエントリ５０４（図６Ｂ）の数は、複数のルックアップテーブル２００を設けることによって増やすことができる。複数のルックアップテーブルは、ルックアップテーブル２００のうち１つの中のサブツリーマッパ４１８（図５）のマッパエントリ５０４（図６Ｂ）に記憶された、サーチキー２１０に対応する値を求めて並行してサーチされる。
【００７４】
図１０Ａは深度拡張のための実施例を図示する。２つのルックアップテーブル、すなわちマスタルックアップテーブル２００ａおよびスレーブルックアップテーブル２００ｂが示される。しかしながら、ルックアップテーブルの数は示された２つに限定されるのではなく、１つよりも多くのスレーブルックアップテーブル２００ｂを加えることができる。
【００７５】
ルックアップテーブル２００ａ−ｂの各々は、同じサーチキー２１０によって並行してサーチされる。サーチキー２１０に対応するルートインデックス１０２（図３）は、ルックアップテーブル２００ａ−ｂのうち１つの中のサブツリーマッパ４１８（図５）またはルックアップテーブル２００ａ、２００ｂの両者の中のダイレクトマッパ１０６ａに記憶される。最終ルートインデックス９００は、両者のルックアップテーブル２００ａ、２００ｂの並行したサーチの後に見出される。
【００７６】
図１０Ｂは、図１０Ａに示された実施例のルックアップテーブル２００ａの１つを図示する。ルックアップテーブル２００ａ−ｂの各々は、図３と関連してルックアップテーブル２００について既に説明されたようなマッパ１０６ａ−ｄおよびパイプライン２０８ならびにドライバ論理９０２を含む。ルックアップテーブル２００ａは、サーチキーに対応するルートインデックスを求めて、マッパ１０６ａ−ｄ中の複数レベルサーチを行なう。各レベルのサーチ結果は、マッパエントリデータ２２０ａ−ｄ上をパイプライン２０８に転送される。パイプライン２０８は、サーチ９０４の結果をドライバ論理９０２に転送する。ルックアップテーブル２００ａ−ｂの各々の中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）はサブツリーエントリ３０４（図４）を記憶するが、ルートエントリ３０２（図４）は、マスタルックアップテーブル２００ａ中のマッパ１０６ａにしか記憶されない。ルートエントリ３０２の代わりに、スレーブルックアップテーブル２００ｂ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）にノーエントリ３００（図４）が記憶される。マッパ１０６ａ中でただ１つのルックアップテーブルにルートインデックスを配することにより、ルックアップテーブルを選択して最終ルートインデックス９００を与えることを回避する。この結果、スレーブルックアップテーブル２００ｂ中のメモリ６４Ｋが与えられる。これは、ルートインデックスを記憶するのに用いることはできないが、図３と関連して説明されたように、同じルックアップテーブルをマスタルックアップテーブルとしてまたはスレーブルックアップテーブルとして構成できるようにする。代替的な実施例では、マッパ１０６ａを有しないスレーブルックアップデバイスを設けることができる。ルートインデックス１０２（図３）をマッパ１０６ａ中のルートエントリ３０２（図４）に記憶すれば、サーチは、マスタルックアップテーブル２００ａ中のマッパ１０６ａで終了する。
【００７７】
図１０Ａに示されたように、マスタルックアップテーブル２００ａおよびスレーブルックアップテーブル２００ｂは最終ルートインデックス９００を共有する。最終ルートインデックス９００を記憶するルックアップテーブル２００ａ、２００ｂはルートインデックス１０２（図３）を与える。ルックアップテーブル２００ａ、２００ｂの各々が別個のデバイスならば、最終ルートインデックス９００を共有することにより、各デバイスの外部ピンのカウントが減少する。いかなるときにも、最終ルートインデックス９００を駆動するのは、ルックアップテーブル２００ａ、ｂのうち１つだけである。
【００７８】
サーチキー２１０と関連のルートインデックスをルックアップテーブル２００ａ、２００ｂの両者に記憶して、ルックアップテーブルの両者が同時に最終ルートインデックス９００を駆動するエラー状態を回避するため、各ルックアップテーブル２００ａ、ｂはデバイスコード９０６を記憶する。３ビットのデバイスコードにより、拡張ルックアップテーブルが８つのデバイスを含むことが可能になる。
【００７９】
ドライバ論理９０２は、サーチ９０４の結果がルートインデックス１０２（図３）を含むか否かを判定する。含んでいれば、ルックアップテーブル２００ａ中のドライバ論理９０２は、バスリクエスト信号（図示せず）上に、最終ルートインデックス９００を駆動する意図を信号で伝える。２つ以上のルックアップテーブル２００ａ、２００ｂが同時にルートインデックス信号を駆動する意図を信号で伝えれば、ルートインデックスは、ルックアップテーブル２００ａ、２００ｂにより、最も低いデバイスコードを与えられる。バスリクエスト信号を用いることによりバス競合を解決するための方法は技術分野で周知である。
【００８０】
図１０Ｃは、サーチキー２１０に対応する値を記憶するのに利用可能なマッパエントリの数を増やすために深度拡張を与える別の実施例を図示する。図１０Ｃに示される実施例では、２つのルックアップテーブル２００ｃ−ｄ、すなわちマスタルックアップテーブル２００ｃおよびスレーブルックアップテーブル２００ｄが値を記憶するために設けられる。しかしながら、ルックアップテーブルの数は示された２つに限定されるものではなく、マッパエントリの数は、より多くのスレーブルックアップテーブル２００ｄを加えることによって増やすことができる。サーチキー［３９：０］２１０に対応するルックアップテーブル２００ｃ−ｄのうち１つの中のマッパエントリに記憶される値に対するサーチは、ルックアップテーブル２００ｃ−ｄで並行して行なわれる。
【００８１】
図１０Ｄは、図１０Ｃに示された実施例のスレーブルックアップテーブル２００ｄを図示する。各々のルックアップテーブルは、図３と関連してルックアップテーブル２００について説明されたような、マッパ１０６ａ−ｄを含む。ルックアップテーブル２００ｃ−ｄの各々の中のマッパ１０６ａのマッパエントリは、サブツリーエントリ３０４（図４）を記憶する。各々のルックアップテーブルｃ−ｄは、マッパ１０６ａ中のマッパエントリ５０４（図６Ｂ）に記憶されたサブツリーエントリ記述子３０４（図４）に記憶されたサブツリーインデックス３１２を次のマッパ１０６ｂ−ｄに転送する。しかしながら、ルートインデックス１０２（図３）は、マスタルックアップテーブル２００ｃ中のマッパ１６ａにのみ記憶される。スレーブルックアップテーブル２００ｄ中のマッパ１０６ａにノーエントリを記憶して、キーに対応するルートインデックスを１つよりも多くのルックアップテーブル２００ｂ、２００ｄに記憶しないようにする。
【００８２】
スレーブルックアップ２００ｄの複数レベルのサーチ９０４の結果は最終インデックス論理１００４に転送される。最終インデックス論理１００４は、複数レベルサーチ９０４の結果およびマスタルックアップテーブル２００ｃから転送された入結果（incoming result）１０００ａを出結果（outgoing result）１００２ａとして転送する。ルートインデックス１０２（図３）が複数レベルサーチ９０４の結果に含まれれば、複数レベルサーチの結果が出結果１００２ａとして転送される。ルートインデックス１０２（図３）が入結果１０００ａに含まれれば、入結果１０００ａが出結果１００２ａとして転送される。ルートインデックス１０２（図３）が入結果１０００ａまたは複数レベルサーチ９０４の結果のいずれにも含まれなければ、複数レベルサーチ９０４の結果が出結果１００２ａとして転送される。
【００８３】
図１０Ｃに示されるように、マスタルックアップテーブル２００ｃおよびスレーブルックアップテーブル２００ｄは、入結果１０００ａで標識付けられた共通のバスを介して接続される。ルートインデックス１０２（図３）は、出結果１００２ａの上を、スレーブルックアップテーブル２００ｄから転送されるのみである。１つよりも多くのスレーブルックアップテーブル２００ｄが存在する場合、最後のスレーブルックアップテーブルにより、拡張ルックアップテーブルに対するルートインデックス１０２（図３）が与えられる。この実施例は、図１０Ａと関連して説明されたマルチドライバ最終ルートインデックス９００の実現例を回避するが、入結果１０００ａ用に、より多くのデバイス外部ピンが必要である。
【００８４】
図１１Ａ−Ｂは、ルックアップテーブル２００ａ−ｂ（図１０Ａ）または２００ｃ−ｄ（図１０Ｃ）中の、図２Ｂに示されたルートの分布のバイナリツリー表示を図示する。
【００８５】
図１１Ａは、マスタルックアップテーブル２００ａ（図１０Ａ）または２００ｃ（図１０Ｃ）に記憶されたルートのバイナリツリー表示を図示する。図２Ｂに示されたルートのバイナリツリー表示に示されるサブツリーＢは、マスタルックアップテーブル２００ａには含まれない。ノード１３０1−１３０22および１３０24-32は、図３と関連して説明されたように、ルックアップテーブル２００ａ中のマッパ１０６ａでコード化される。サブツリーＢがインデックス付けされるノードは、それがマスタルックアップテーブル２００ａに記憶されれば、Ｘでグラフィックに表わされ、プルーニングされたサブツリーを示す。マスタルックアップテーブル２００ａ中のノード１３０23に対応するマッパエントリ５０４（図６Ｂ）は、もはやサブツリーＢへのサブツリーインデックス３１２（図４）を記憶しない。代わりに、ノード１３０23に対応するマッパエントリが別のスレーブルックアップテーブル２００ｂ中のサブツリーマッパ４１８（図５）に記憶されることを示すマスタルックアップテーブル２００ａ中の、ノード１３０23に対応するマッパエントリ５０４（図６Ｂ）に、ノーエントリ３００（図４）が記憶される。
【００８６】
図１１Ｂは、スレーブルックアップテーブル２００ｂ（図１０Ａ）または２００ｄ（図１０Ｃ）中のサブツリーマッパ４１８（図５）中のマッパエントリ５０４（図６Ｂ）に記憶されるルートのバイナリツリー表示を図示する。スレーブルックアップテーブル２００ｂに記憶されるルートのバイナリツリー表示は、サブツリーＡが含まれないという点で、図２Ｂに示されたバイナリツリー表示と異なっている。したがって、図２Ｂと関連して説明されたように、ノード１３０1−１３０3および１３０5−１３０32がコード化される。スレーブルックアップテーブル２００ｂ中のノード１３０4に対応するマッパエントリ５０４（図６Ｂ）は、もはやサブツリーＡへのサブツリーインデックス３１２（図４）を記憶しない。代わりに、スレーブルックアップテーブル２００ｂ中のノード１３０4に対応するマッパエントリは、ノード１３０4に対応するマッパエントリが別のルックアップテーブルに記憶されることを示すノーエントリ３００（図４）を記憶する。サブツリーＡへのサブツリーインデックスおよびしたがってホスト１３８（図１１Ａ）へのルートインデックスはマスタルックアップテーブル２００ａに記憶され、サブツリーＢへのサブツリーインデックスおよびしたがってホスト１４０へのルートインデックスはスレーブルックアップテーブル２００ｂに記憶される。スレーブルックアップテーブル２００ｂ、２００ｄはサブツリーに対する結果のみを記憶する。すなわち、スレーブルックアップテーブル２００ｂ、２００ｄは第１のレベルのマッパ１０６ａの結果を記憶しない。
【００８７】
図１１Ａおよび図１１Ｂを参照して、キー２１０ａの最初の部分による、スレーブマッパレベル＿１  １１０４ａまたはマスタマッパレベル＿１  １１０２（図３）中のノード１３０9−１３０12のいずれに対するサーチの結果も、マスタルックアップテーブル２００ａ、２００ｃ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）中のルートエントリ３０２（図４）と、スレーブルックアップテーブル２００ｂ、２００ｄ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）に記憶されるノーエントリ３００（図４）とに記憶されるｒ１  １１６となる。マスタルックアップテーブル２００ａ、２００ｃに記憶されるルートエントリ３０２（図４）は、入結果１０００ａ上をスレーブルックアップテーブル２００ｂ、２００ｄに転送され、スレーブルックアップテーブル２００ｂ、２００ｄにより出結果１００２ａ上を転送される。
【００８８】
キー２１０ａの最初の部分による、ノード１３０4に対するサーチの結果は、マスタルックアップテーブル２００ａ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）中にサブツリーエントリ記述子３０４（図４）に記憶されたサブツリーＡに対するサブツリーインデックス３１２（図４）となる。サブツリーインデックス３１２はマスタルックアップテーブル２００ａ中のマッパ１０６ｂに転送され、マスタルックアップテーブル２００ａに記憶されるルートエントリ３０２（図４）に対するサーチを継続する。
【００８９】
キー２１０の最初の部分による、ノード１３０23に対するサーチの結果は、マスタルックアップテーブル２００ａ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）に記憶されるサブツリーエントリ記述子３０４（図４）と、スレーブルックアップテーブル２００ｂ中のマッパ１０６ａのマッパエントリ５０４（図６Ｂ）に記憶されるノーエントリ３００（図４）とである。したがって、ルートエントリ３０２（図４）に対するサーチは、スレーブルックアップテーブル２００ｂ中のマッパ１０６ｂで、キー２１０ｂの次の部分を用いて継続する。
【００９０】
図１２は、図１０Ａに示されたルックアップテーブル２００ａ−ｂ中のマッパエントリ５０４（図６Ｂ）に記憶されるべきルートエントリ３０２（図４）を分散するための方法を図示するフローチャートである。同じ方法は、図１０Ｃに示されたルックアップテーブル２００ｃ−ｄに当てはまる。マッパエントリに記憶されるべきルートエントリ３０２（図４）はまず、ルックアップテーブル２００ａ−ｂに記憶される前に、プロセッサ（図示せず）によってメモリに記憶される。
【００９１】
ルートエントリ３０２（図４）がメモリに記憶される間、ルックアップテーブル２００ａ−ｂ（図１０Ａ）の各々に記憶されるべきルートエントリ３０２（図４）の数がカウントされる。マッパレベル＿１  １１０４ａ（図１１Ｂ）に対するルートエントリ３０２（図４）は、ルックアップテーブル２００ａ中のマッパ１０６ａに記憶される。マッパレベル＿１  １１０４ａ（図１１Ｂ）に対するサブツリーエントリ（図４）は、ルックアップテーブル２００ａ−２００ｂの各々の中のマッパ１０６ａに記憶される。
【００９２】
ステップ１２００で、ルックアップテーブル２００ａ−２００ｂ（図１０Ａ）の各々の中のマッパ１０６ａのサブツリーエントリ３０４（図４）の各々ごとの、記憶されるべきルートエントリ３０２（図４）の数を計算して、どのようにルートエントリ３０２（図４）をルックアップテーブル２００ａ−ｂ（図１０Ａ）の中に分散すべきかを判定する。ルートエントリ３０２（図４）を記憶するのに必要なマッパエントリ５０４（図６Ｂ）の総数を判定した後、処理はステップ１２０２に継続する。
【００９３】
ステップ１２０２で、サブツリーに対して記憶されるべきマッパエントリ５０４（図６Ｂ）の総数を、ルックアップテーブル２００ａ−ｂ（図１０Ａ）の数で除算して、各ルックアップテーブル２００ａ−ｂ（図１０Ａ）に記憶すべきルートエントリ３０２（図４）の数を定める。処理はステップ１２０４に継続する。
【００９４】
ステップ１２０４で、ルートエントリ３０２（図４）は、選択されたルックアップテーブル２００ａ−ｂ中のサブツリーマッパ４１８（図５）中のマッパエントリ５０４（図６Ｂ）に記憶される。処理はステップ１２０６に継続する。
【００９５】
ステップ１２０６で、選択されたルックアップテーブル２００ａ−ｂ（図１０Ａ）中のサブツリーマッパ４１８（図５）のマッパエントリ５０４（図６Ｂ）に記憶されたルートエントリの数が１／ｎ未満ならば、なおここでｎは利用可能なルックアップテーブル２００ａ−ｂ（図１０Ａ）の数であるが、プロセスはステップ１２０４に続く。それ以上ならば、選択されたルックアップテーブル２００ａ−ｂはマッパエントリの総数の１／ｎを記憶しており、処理はステップ１２０８に継続する。
【００９６】
ステップ１２０８で、選択されたルックアップテーブル２００ａ−ｂはマッパエントリの総数の１／ｎを記憶し、選択されたルックアップテーブル２００ａ−ｂのいずれの残余のサブツリーノードに対しても、ノーエントリ３００（図４）を記憶する。それぞれのサブツリーに対するルートインデックスは、現在選択されたルックアップテーブルに記憶されないからである。処理はステップ１２１０に続く。
【００９７】
ステップ１２１０で、すべてのルートエントリが記憶されれば、処理は完了する。記憶されていなければ、処理はステップ１２１２に継続する。
【００９８】
ステップ１２１２で、次のルックアップテーブル２００ａ−ｂ（図１０Ａ）が選択される。処理はステップ１２０４に続く。
【００９９】
ルートエントリは、ＩＰアドレスに対応するルートインデックスに対するサーチの前に、ルックアップテーブル２００ａ−ｂ（図１０Ａ）の中に分散される。サーチは、ルックアップテーブル２００ａ−ｂ（図１０Ａ）の各々の中で並行して行なわれる。ルックアップテーブルの各々の中で並行して実現されるサーチのための方法が、ルックアップテーブル２００ａ−ｂ（図１０Ａ）の１つのために説明される。
【０１００】
図１３は、図１０Ｃに示されたルックアップテーブル２００ｃ−ｄのいずれの１つにも記憶されるサーチキーに対応する値に対する、サーチキーによるサーチのための方法を図示するフローチャートである。
【０１０１】
ステップ１３００で、ルックアップテーブル２００ｃ−ｄ（図１０Ｃ）の各々はサーチキー２１０を受ける。ルックアップテーブル２００ｃ−ｄの各々の中のマッパ１０６ａは、キー２１０ａの最初の部分に対応する値を求めてサーチされる。処理はステップ１３０２に継続する。
【０１０２】
ステップ１３０２において、マッパ１０６ａ内のマッパエントリ５０４（図６Ｂ）に記憶されたエントリが読出される。マスタルックアップテーブル２００ｃ中のマッパエントリ５０４（図６Ｂ）は、ノーエントリ３００（図４）、ルートエントリ３０２（図４）またはサブツリーエントリ記述子３０４（図４）を記憶し得る。スレーブルックアップテーブル２００ｄ内のマッパエントリ５０４（図６Ｂ）は、ノーエントリ３００（図４）およびサブツリーエントリ記述子３０４（図４）を記憶し得る。それぞれのルックアップテーブル２００内のマッパエントリがルートエントリ３０２（図４）を記憶していれば、そのエントリは有効な値であり、ルックアップテーブル２００ｃ−２００ｄ内の後続のマッパ１０６ｂ−ｄのさらなるサーチは必要はなく、処理はステップ１３１０へ進む。そうでなければ、処理はステップ１３０４へ進む。
【０１０３】
ステップ１３０４において、このエントリがサブツリーエントリ記述子３０４（図４）を記憶していれば、ルックアップテーブル２００ｃ−ｄ内のさらなるサーチが必要となり、処理はステップ１３０６へ進む。そうでなければ、このエントリはノーエントリを記憶しており、これがさらなるサーチが必要でないことを示しているので、処理はステップ１３１０へ進む。
【０１０４】
ステップ１３０６において、選択されたサブツリーにおいてサーチが継続される。キー２１０ｂ−ｄの次の部分および前のレベルのサーチの結果得られたサブツリーインデックス３１２（図４）に依存して、次のレベルのマッパ１０６ｂ−ｄ（図３）がサーチされる。処理はステップ１３０８へ進む。
【０１０５】
ステップ１３０８において、現在のレベルのマッパ１０６ｂ−ｄのサーチの結果得られるマッパエントリに依存して、サーチを継続するか否かが判定される。マッパエントリ５０４（図６Ｂ）がサブツリーエントリ記述子３０４（図４）を記憶していれば、次のレベルのマッパ１０６ｂ−ｄでサーチが継続され、処理はステップ１３０６へ進む。マッパエントリ５０４（図６Ｂ）がサブツリーエントリ記述子３０４（図４）を記憶していなければ、さらなるサーチは必要なく、処理はステップ１３１０へ進む。
【０１０６】
ステップ１３１０において、サーチの結果が別のルックアップテーブルから受けた入結果１０００ａと比較される。たとえば、ルックアップテーブルがスレーブルックアップテーブル２００ｄの場合、マスタルックアップテーブル２００ｃでのサーチからの入結果は、入結果１０００ａ上でルックアップテーブル２００ｄへ転送され、スレーブルックアップテーブル２００ｄにおけるサーチの結果と比較される。処理はステップ１３１２へ進む。
【０１０７】
ステップ１３１２において、入結果１０００ａと現在のルックアップテーブル２００ｄのサーチ結果が異なる場合、処理はステップ１３１４へ進む。入結果１０００ａと現在のルックアップテーブル２００ｄのサーチ結果との両者が同じであれば、別々のルックアップテーブル２００ｃ−ｄ中のマッパエントリ５０４（図６Ｂ）に２つの有効な結果が記憶されている。同じキー２１０に対して２つの有効な結果を記憶すべきでなく、処理はステップ１３１６へ進む。
【０１０８】
ステップ１３１４において、入結果１０００ａがチェックされ、それが有効であるか否かが判定される。入結果１０００ａは、それがルートエントリ３０２（図４）であれば有効である。入結果１０００ａは、それがノーエントリ３００（図４）またはサブツリーエントリ記述子３０４（図４）であれば無効である。サブツリーエントリ記述子３０４（図４）、ルートエントリ３０２（図４）およびノーエントリ３００（図４）については図４に関連して既に説明した。入結果１０００ａが無効であれば、処理はステップ１３１８へ進む。そうでなければ、処理はステップ１３２０へ進む。
【０１０９】
ステップ１３１８において、入結果１０００ａは有効であり、現在のルックアップテーブル２００ｄのサーチ結果は無効である。入結果１０００ａは現在のルックアップテーブル２００ｄから出結果（出て行く結果）１００２ａ上で転送される。入結果１０００ａは、現在のルックアップテーブル２００ｄが最後のルックアップテーブルであればルートインデックス１０２（図３）として転送され、または、入結果１０００ａとして次のルックアップテーブルへ転送される。処理が完了する。
【０１１０】
ステップ１３１６において、２つの有効な結果の値がキーに対して別々のルックアップテーブルに記憶される。ルックアップテーブル２００ｃ−ｄ中のルートエントリの記憶中にエラーが起こる。エラーコードが生成されるのでこのエラーは修正され得る。処理が完了する。
【０１１１】
ステップ１３２０において、現在のルックアップテーブル２００ｄのサーチ結果も入結果１０００ａも有効でない。現在のルックアップテーブル２００ｄのサーチ結果は、たとえ無効であっても、入結果１０００ａとして次のルックアップテーブルへ転送される。処理が完了する。
【０１１２】
図１４は、図１０Ａに示すルックアップテーブル２００ａ−ｄのうちの１つに記憶されたサーチキーに対応する値をサーチするための方法を表わすフローチャートである。
【０１１３】
ステップ１３４０において、ルックアップテーブル２００ａおよび２００ｂの両者における第１のレベルのマッパ１０６ａが、キー２１０ａの第１の部分に対応する値についてサーチされる。処理はステップ１３４２へ進む。
【０１１４】
ステップ１３４２において、キー２１０ａの第１の部分で第１のレベルのマッパ１０６ａをサーチした後に有効な結果の値が見つかれば、処理はステップ１３５２へ進む。そうでなければ、処理はステップ１３４４へ進む。
【０１１５】
ステップ１３４４において、キー２１０ａの第１の部分で第１のレベルのマッパ１０６ａをサーチした結果の値がサブツリーエントリ記述子３０４（図４）であれば、処理はステップ１３４６へ進む。そうでなければ、そのキーに対する有効な値は現在のルックアップテーブルには記憶されておらず、処理は完了する。
【０１１６】
ステップ１３４６において、有効な値のサーチは、前のレベルのマッパのサーチ中に見つかったサブツリーエントリ記述子３０４（図４）において識別されたサブツリーで継続される。次のレベルのマッパが、キー２１０ｂ−ｃの次の部分および次のレベルのサーチの結果得られるサブツリーセレクトに依存する値に対してサーチされる。処理はステップ１３４８へ進む。
【０１１７】
ステップ１３４８において、このサーチ結果により、次のレベルのマッパのサーチが要求されるか否かが判定される。現在のサーチの結果得られるエントリは、ルートエントリ３０２、ノーエントリ３００（図４）またはサブツリーエントリ記述子３０４（図４）を記憶し得る。このエントリがサブツリーエントリ記述子３０４（図４）を記憶していれば、さらなるサーチが必要であり、処理はステップ１３４６へ進む。このエントリがサブツリーエントリ記述子３０４（図４）を記憶していなければ、処理はステップ１３５０へ進む。
【０１１８】
ステップ１３５０において、このエントリがルートインデックス１０２（図３）を記憶していれば、処理はステップ１３５２へ進む。そうでなければ、このエントリは別のルックアップテーブルに記憶されている。処理が完了する。
【０１１９】
ステップ１３５２において、キーに対応する有効な値が現在のルックアップテーブルに記憶されている。この有効な値は、キーに対応するルートインデックス１０２（図３）として転送される。処理が完了する。
スパースモード
図５を参照して、サブツリーエントリ４０４は２５６までの可能なルートインデックスのアクセスを、２５６のノードサブツリーにおいて各ノードに１つずつ提供する。これらのルートインデックスはサブツリーマッパ４１８（図５）におけるマッパエントリ５０４1−５０４nに記憶される。サブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）に対するマッパアドレス４１６は、データフィールド４０６に記憶された稠密サブツリー記述子と、サブツリーエントリ４０４内のポインタフィールド４０８に記憶されたサブツリーポインタとに依存して決定される。稠密サブツリー記述子の形式については図６Ａ−６Ｂに関連して既に説明した。稠密サブツリー記述子は、２５６のノードサブツリーにおける各ノードに対してノードビット５０２（図６Ｂ）を記憶する。しかしながら、すべてのサブツリーが、２５６個のノードの各々に対してある別個のルートインデックスを有する。たとえば、１つのサブツリーは１つのルートインデックスのみを有し得る。
【０１２０】
図１５は、第１のマッパレベル１１２ａにおけるサブツリーエントリ３０４（図４）によってインデックス付けされた第２のマッパレベル１１２ｂにおける疎サブツリーＡおよび稠密サブツリーＢのバイナリツリーを表わした図である。マッパ１０６ａ内のｓ１に対するサブツリーエントリ記述子３０４（図４）はサブツリーＡのサブツリーエントリ４０４に対するサブツリーインデックス３１２を記憶する。マッパ１０６ａ内のｓ０に対するサブツリーエントリ記述子３０４（図４）は、サブツリーＢのサブツリーエントリ４０４に対するサブツリーインデックス３１２を記憶する。
【０１２１】
密に配置されたサブツリーＢは１１個のルートインデックス、すなわちｒ６からｒ１６と、６個のサブツリーエントリ、すなわちｓ２からｓ７を有する。サブツリーＢに対してルートエントリ３０２（図４）とサブツリーエントリ３０４（図４）とを記憶するマッパエントリ５０４（図６Ｂ）に対応するマッパアドレス４１６は、図６Ｂに関連して既に述べたように、稠密サブツリー記述子においてコード化される。
【０１２２】
疎に配置されたサブツリーＡは２個のルートインデックス、すなわちｒ１およびｒ２を記憶する。これらが稠密サブツリー記述子に記憶されていれば、サブツリーエントリ４０４全体を用いてマッパエントリ５０４（図６Ｂ）に対する３つのマッパアドレス４１６、すなわちｒ０、ｒ１およびｒ２が提供される。
【０１２３】
ルックアップテーブル２００に記憶されたルートの数は、複数の疎サブツリー記述子のうちの１つにある疎サブツリーをコード化し、サブツリーエントリ４０４内の稠密サブツリー記述子にある密に配置されたサブツリーをコード化することによって、増加し得る。
【０１２４】
密に配置されたサブツリーは１６以上のマッパエントリ５０４（図６Ｂ）を有し、サブツリーエントリ４０４内のデータフィールド４０６は、図６Ａ−６Ｂに関して述べたように、稠密サブツリー記述子を記憶する。疎に配置されたサブツリーは１５以下のマッパエントリ５０４（図６Ｂ）を有し、サブツリーエントリ４０４内のデータフィールドは複数の疎サブツリー記述子を記憶する。疎に配置されたサブツリーを疎サブツリー記述子に記憶する能力を与えることにより、サブツリーメモリ４００により多くのサブツリーを記憶することができ、よって、ルックアップテーブル２００中により多くのルートエントリを記憶することができる。
【０１２５】
図１６Ａ−Ｃは、図５に示すサブツリーエントリ４０４内のデータフィールド４０６およびポインタフィールド４０８と、図４に示すサブツリーエントリ記述子３０４（図４）とを、サブツリーエントリ４０４内に複数の疎サブツリー記述子を記憶できるよう変形した例を表わす。
【０１２６】
図１６Ａを参照して、スパースモードで構成されたサブツリーエントリ４０４内のデータフィールド４０６は、図６Ｂに関連して述べたサブツリーの各ノードごとに１ビットを有する稠密サブツリー記述子の代わりに、複数の疎サブツリー記述子１４００1−１４００nを含む。疎サブツリー記述子１４００1−１４００nの各々は、ノード記述子１４０２1−１４０２nを含む。ノード記述子１４０２1−１４０２nは、サブツリーにおいて完全に符号化されたルートを表わす９ビットの値である。ノード記述子１４０２1−１４０２nは、サブツリー内の単一のノードまたは複数のノードを表わす。
【０１２７】
図１６Ｂを参照して、疎サブツリー記述子の記憶をサポートするために、モードフィールド１４０４がサブツリーエントリ４０４内のポインタフィールド４０８に加えられる。ポインタフィールド４０８は、ブロックベースアドレス６００1およびブロックベースアドレス６００2も記憶しており、各ブロックが１６個の割当てられたマッパアドレス４１６を含み、これらのアドレスは各サブツリーエントリ４０４ごとに合計３２のマッパアドレス４１６を提供する。モードフィールド１４０４はモード値を記憶する。モードフィールド１４０４に記憶されたモード値は、サブツリーエントリ４０４に記憶された疎サブツリー記述子１４００1−１４００nの数と、疎サブツリー記述子１４００1−１４００nの各々に記憶されたノード記述子１４０２1−１４０２nの数とを示す。表２は、各モードについてのサブツリーエントリ４０４の構成を表わす。
【０１２８】
【表２】
0004741134.tif 000003
【０１２９】
表２を参照して、たとえば、サブツリーエントリ４０４内のポインタフィールド４０８におけるモードフィールド１４０４に記憶されたモード値が「４」にセットされる場合、サブツリーエントリ４０４の疎サブツリー記述子１４００の各々は５から７のノード記述子１４０２1−１４０２nを記憶する。各ノード記述子１４０２1−１４０２nは９ビットを記憶する。疎サブツリー記述子１４００に記憶されたビットの総数は、疎サブツリー記述子１４００1−１４００nごとのノード記述子１４０２1−１４０２nの数を９（ノード記述子１４０２1−１４０２nごとのビット数）で乗じることにより計算される。モード４に対して疎サブツリー記述子１４００ごとのビット数を計算すると、７個のノード記述子１４０２を有する疎サブツリー記述子１４００は６３ビットを記憶している（７ノード記述子＊９ビット＝６３）。
【０１３０】
サブツリーエントリ４０４ごとの疎サブツリー記述子１４００の数は、データフィールド４０６内のビット数を疎サブツリー記述子１４００1−１４００n内のビット数で除することにより、算出される。モード４について、データフィールド４０６内のビット数は２５６であり、疎サブツリー記述子内のビット数は６３である。したがって、疎サブツリー記述子１４００1−１４００nの数は４である（ｉｎｔ（２５６／６３）＝４）。
【０１３１】
サブツリーエントリ４０４ごとのノード記述子１４０２1−１４０２nの総数は、各サブツリーごとのノードの数に各サブツリーエントリ４０４ごとのサブツリーの数を乗じたものである。モード４について計算すると、サブツリーエントリ４０４ごとのノード記述子１４０２の総数は、疎サブツリー記述子１４００1−１４００nに記憶されたノード記述子１４０２1−１４０２nが７個ある場合は２８であり（７＊４＝２８）、疎サブツリー記述子１４００1−１４００nごとのノード記述子１４０２が５個ある場合は２０である（５＊４＝２０）。
【０１３２】
表２のマッパエントリの列には、サブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）がいくつサブツリーエントリ４０４によって使用されているかが示される。マッパの値は、サブツリーごとのノードを１ずつ増分し、かつ疎サブツリー記述子のサブツリーの数で乗じることにより、算出される。サブツリーのデフォルトエントリを記憶するためには各サブツリーごとのノードの数より１以上多いマッパエントリが要求されるので、サブツリーごとのノードは１ずつ増分される。
【０１３３】
表２のモード４の行を参照して、疎サブツリー記述子１４００ごとに７個のノード記述子１４０２があれば、各サブツリーエントリ４０４ごとに３２（（７＋１）＊４＝３２）のマッパエントリが要求され、疎サブツリー記述子１４００ごとに５個のノード記述子１４０２があれば、疎サブツリー記述子１４００ごとに２４（（５＋１）＊４＝２４）のノード記述子１４０２が要求される。サブツリーごとのノードの数およびサブツリーエントリ４０４ごとのサブツリーの数は、サブツリーエントリ４０４ごとのノード記述子の最大数が３０を超えないように選択される。これは、サブツリーマッパ４１８（図５）内のマッパアドレス４１６が１６ブロック刻みで割当てられるからである。ポインタフィールド４０８に記憶された２つのブロックベースアドレス６００1および６００2を記憶することにより、３２のマッパアドレス４１６が提供される。
【０１３４】
図１６Ｃを参照して、サブツリーメモリ４００における各サブツリーエントリ４０４は、図６Ｂに関連して述べたようなデンス（稠密）モードで、またはスパース（疎）モードで構成され得る。デンスモードについて図４に関して述べたサブツリーマッパ４１８（図５）に記憶されるサブツリーエントリ記述子３０４（図４）は、サブツリーエントリ４０４がデンスモードでコード化されるかまたはスパースモードでコード化されるかの指示を提供することによりスパースモードを可能にするよう変更される。この指示（indicator）は、タイプフィールド１４０６により提供される。
【０１３５】
タイプフィールド１４０６の状態により、サブツリーエントリ４０４がデンスモードまたはスパースモードかのいずれで構成されているかが示される。サブツリーエントリ４０４がスパースモードで構成されている場合、スパースサブツリー記述子セレクトフィールド１４０８に記憶された値とサブツリーインデックス３１４とが用いられて、スパースサブツリー記述子１４００が選択される。スパースサブツリー記述子セレクト１４０８については、図１６を参照して後により詳細に説明する。
【０１３６】
図１７は、疎に配置されたサブツリーにおけるノードに対してマッパエントリ５０４（図６Ｂ）を選択するようにブロックオフセット７１４を与えるための、図８に示すオフセット論理７００のスパースモード論理１５０２を表わす。スパースモード論理１５０２は、サブツリーエントリ４０４中の疎サブツリー記述子１４００に記憶されたノード記述子１４０２に依存して、ブロックオフセット７１４を与える。オフセット論理７００はまた、デンスモード論理１５００も含む。デンスモード論理１５００は、密に配置されたサブツリーにおけるルートに対してブロックオフセット７１４を与えるためのノードセレクト７０６および１カウント論理７０８を含む。デンスモード論理１５００については、図８に関連して既に説明した。
【０１３７】
タイプフィールド１４０６の状態がサブツリーエントリ４０４がスパースモードで構成されていると示す場合、サブツリーエントリ４０４からのサブツリーデータ４１２はスパースモード論理１５０２へ転送される。スパースモードサブツリー論理１５０２については図１８に関連して説明する。
【０１３８】
図１８は、図１７のオフセット論理７００に示されるスパースモード論理１５０２を表わす。スパースモード論理１５０２は、サブツリーセレクト論理１６００、マルチプレクサ１６０２、連想メモリ（「ＣＡＭ」）１６０６および変換論理１６０４を含む。選択されたサブツリーエントリ４０４内のデータフィールド４０６に記憶された疎サブツリー記述子１４００1−１４００nは、サブツリーデータ４１２上でオフセット論理７００へ転送される。オフセット論理７００は疎サブツリー記述子１４００1−１４００nをスパースモード論理１５０２におけるマルチプレクサ１６０２へ転送する。サブツリーデータ４１２中の疎サブツリー記述子１４００1のうちの１つが、サブツリーセレクト論理１６００により生成されたセレクト１６１４によって選択される。
【０１３９】
サブツリーセレクト論理１６００はセレクト１６１４を生成し、前のマッパレベルにおいて選択されたマッパエントリから転送された疎サブツリー記述子セレクト１４０８の状態と、選択されたサブツリーエントリ４０４内のポインタフィールド４０８に記憶されたモード１４０４とに依存して、疎サブツリー記述子１４００1を選択する。表３は、モード４サブツリーエントリ４０４について、マルチプレクサ１６０２から、選択された疎サブツリー記述子１６１０上で転送された、選択された疎サブツリー記述子１４００1およびそれぞれのサブツリーデータビット４１２を表わす。表２のモード４の行を参照して、モード４サブツリーエントリ４０４には４つの疎サブツリー記述子が記憶され得る。４つの疎サブツリー記述子１４００の各々は６３ビットであり、７から５個のノード記述子１４０２を記憶し得る。よって、これら４つの疎サブツリー記述子１４００の各々は６３ビット境界から始まる。第１の疎サブツリー記述子１４００1はデータフィールド４０６のビット６２：０に記憶される。第２の疎サブツリー記述子１４００2はデータフィールド４０６のビット１２５：６３に記憶される。第３の疎サブツリー記述子１４００3はデータフィールド４０６のビット１８８：１２６に記憶され、第４の疎サブツリー記述子１４００4はデータフィールド中のビット２５１：１８９に記憶される。データフィールド４０６におけるそれぞれのビットは、疎サブツリー記述子セレクト１４０８により選択される。たとえば、表３を見ると、疎サブツリー記述子セレクト１４０８が「０００１」であれば、第２の疎サブツリー記述子１４００2が選択され、２５６ビットのサブツリーデータ４１２のビット１２５：６３が、マルチプレクサ１６０２を介して、選択された疎サブツリー記述子１６１０上で変換論理１６０４へ転送される。
【０１４０】
【表３】
0004741134.tif 000004
【０１４１】
サブツリーメモリ４００内の各サブツリーエントリ４０４はスパースモードまたはデンスモードで構成され得る。スパースモードで構成された各サブツリーエントリ４０４は、モード１４０４を介して疎サブツリー記述子１４００ごとに異なる数のノード記述子１４０２を記憶するよう構成され得る。スパースモードで構成されたサブツリーエントリ４０４内の疎サブツリー記述子１４００はすべて、疎サブツリー記述子１４００ごとに同数のノード記述子１４０２を記憶する。
【０１４２】
ノード記述子１４０２はサブツリーにおける複数のノードを表わすようにコード化され得る。ノード記述子１４０２によって表わされる複数の８ビットノードは、８ビットのうちのいくつかをマスキングすることにより識別される。マスクビットを各ノード記述子１４０２で記憶する代わりに、９個のビットノード記述子１４０２を用いてノード記述子１４０２が表わす８ビット幅のノードを完全に符号化する。この８ビット幅のノードは、ランビットレングス符号化を用いて９ビット幅のノード記述子１４０２において符号化される。ランビットレングス符号化により、そのノードの８ビットのうちのいずれがマスキングされるかが識別できるようになる。
【０１４３】
変換論理１６０４は、選択された疎サブツリー記述子１４００に記憶された９ビット幅のノード記述子１４０２1−１４０２nを、「Ｘ」（ドントケア）にセットされたビットを含む８ビットのＣＡＭ値１６１２へ変換し、この８ビットのＣＡＭ値１６１２をＣＡＭ１６０６へロードする。９ビットのノード記述子１４０２を変換論理１６０４により８ビットのＣＡＭ値１６１２へ変換する例を以下の表４に示す。
【０１４４】
【表４】
0004741134.tif 000005
【０１４５】
９ビットコードの列は、ノード記述子１４０２に記憶された値を表わす。表４の第１行目を見ると、ノード記述子１４０２に記憶された９ビットコードは「１０１１００１００」であり、対応する８ビット値「１０１１００ＸＸ」がＣＡＭ１６０６に記憶される。変換論理１６０４は、９ビットのコードを「１」にセットされた第１のビットに対して右から左へサーチすることにより、この９ビットコードを変換する。９ビットコード中のビットを右から左へ見ると、最初の２つのビットが「０」にセットされ、３番目のビットが「１」にセットされている。変換論理１６０４は、最初の「１」の右側に「０」が２つあるので、「１００」を２つのドントケア（「ＸＸ」）に変換する。１つ目の「１」は無視され、残りのビットが８ビット値の次の各ビットへと直接コピーされる。
【０１４６】
表４の第２行目を見ると、ノード記述子１４０２に記憶された９ビットコードは「１００１０００００」である。変換論理１６０４は、最初の「１」についてこの９ビットコードを右から左へサーチすることにより、この９ビットコードを変換する。５番目の数字が「１」を記憶している。この９ビットコードは、５つの最下位ビット（「ＬＳＢ」）が「ドントケア」（「Ｘ」）にセットされた８ビット値に変換される。９ビットのランビットレングス符号化を用いてノード記述子１４０２を記憶することにより、各ノード記述子１４０２ごとに要求されるビット数は最小になり、よって、ルックアップテーブル２００中に記憶され得るノード記述子１４０２の数が増加する。
【０１４７】
９ビットのノード記述子１４０２を８ビット値に変換した後、変換論理１６０４はこの８ビット値をＣＡＭ１６０６内へロードする。この８ビット値は、ノード記述子１４０２が選択された疎サブツリー記述子１４００に記憶されたのと同じ順序で、すなわち最短一致から最長一致の順序で、ＣＡＭ１６０６内にロードされる。ＣＡＭ１６０６は、疎サブツリー記述子１４００ごとのノード記述子１４０２の最大数を記憶するための記憶部を提供する。したがって、ＣＡＭ１６０６は８ビット幅×１６エントリの深さであり、デフォルトマッパアドレスおよびモード５疎サブツリー記述子１４００に対する最大数のノード記述子１４０２を記憶するために１５のエントリを提供する。ＣＡＭ１６０６にはターナリの能力（ternary capability）と複数一致リゾルバ（multi-match resolver）とが内蔵されている。真の連想メモリを提供するのとは対照的に、小さなサイズのＣＡＭ１６０６が、ゲートの形態で実現され得る。すなわち、ＣＡＭ１６０６は、ＣＡＭをエミュレートするハードウェア回路で実現され得る。
【０１４８】
疎サブツリー記述子１４００に記憶されたノード記述子１４０２の数は、疎サブツリー記述子１４００が記憶されるサブツリーエントリ４０４を決定する。特定のモードの範囲内のノード記述子１４０２を記憶する疎サブツリー記述子１４００は、同じサブツリーエントリ４０４に記憶される。各サブツリーのデフォルトルートに対して、デフォルトマッパアドレスが算出される。デフォルトの８ビット値は、ＣＡＭ１６０６内の第１の場所に永久に記憶され、デフォルトマッパアドレスを算出する。
【０１４９】
選択された疎サブツリー１４００に対する８ビット値がＣＡＭ１６０６内へロードされた後、ＣＡＭ１６０６はキー２１０ｂの次の部分でサーチされる。キー２１０ｂの次の部分において最大数のビットに一致するＣＡＭ１６０６内のエントリが選択される。ＣＡＭのサーチの結果得られた一致アドレスは、ブロックオフセット７１４として転送される。ブロックオフセット７１４を用いて、サブツリーマッパ４１８（図５）に記憶されたルートに対応するマッパエントリのマッパアドレス４１６が決定される。
【０１５０】
図１９Ａ−Ｄは、疎に配置されたサブツリー１７００内のあるノードに対するブロックオフセット７１４の選択を図示する。図１７Ａは疎に配置されたサブツリー１７００におけるルートを図示したものである。サブツリー１７００内のノードは３つのルートｒ０、ｒ１およびｒ２のうちの１つに対応しており、ｒ０はサブツリー１７００のデフォルトルートである。２つのルートｒ１およびｒ２は、疎サブツリー記述子１４００のノード記述子１４０２1および１４０２2で符号化される。デフォルトルートｒ０の値は、ＣＡＭ１６０６内の第１のエントリ１７０２に永久に記憶される。表２を参照して、２つのノード記述子１４０２を備える疎サブツリー記述子１４００は、サブツリーエントリ４０４に記憶され、モードフィールド１４０４は「１」にセットされる。
【０１５１】
サブツリー１７００を見ると、ｒ２は１０ＸＸＸＸＸＸに一致するすべてのノードに対応し、ｒ１は０１０ＸＸＸＸＸに一致するすべてのノードに対応する。各ノード記述子１４０２1および１４０２2により要求されるビット数を最小にして疎サブツリー記述子１４００中の各ルートを記述するために、ノード記述子１４０２1および１４０２2は、ランビットレングス符号化を用いてコード化される。コード化の方法は、そのノードを完全に符号化するのに用いられるビット数より１ビット多いものを用いる。最初の「Ｘ」（「ドントケア」）の場所に「１」が挿入され、残りのＸは０としてコード化される。すなわち、ルート１０ＸＸＸＸＸＸは１０１０００００に翻訳され、０１０ＸＸＸＸＸは０１０１０００００に翻訳される。
【０１５２】
図１９Ｂは、疎サブツリー記述子１４００中のノード記述子１４０２1および１４０２2の記憶部を表わす。ノード記述子１４０２1および１４０２2はサブツリーエントリ４０４に記憶され、モードフィールド１４０４は「１」にセットされる。これは、疎サブツリー記述子１４００に記憶された２つのノード記述子１４０２1および１４０２2があるからである。サブツリーの最長一致はｒ１である。なぜなら、ｒ１は最初の３ビットの一致を要求し、ｒ２は最初の２ビットの一致を要求するからである。ノード記述子１４０２1および１４０２2は疎サブツリー記述子１４００において最短一致から最長一致の順序で記憶され、最初にｒ２のノード記述子１４０２1が記憶されて次にｒ１のノード記述子１４０２2が次に記憶される。
【０１５３】
図１９Ｃは、ノード記述子１４０２2の８ビットのマスキングされた値１７０６への変換を表わす。ノード記述子ビット１７０８1−１７０８9を左から右へ見ると、最初の「１」がビット１７０８6に記憶され、これは８ビットのマスキング値１７０６のマスクビットの終わりを記している。ノード記述子１４０２2を８ビットのマスキングされた値１７０６に変換するために、以下のビット変換が行なわれる。ノード記述子のビット１７０８1に記憶された「０」は「Ｘ」に変換され、８ビットのマスキングされた値のビット１７１０1に記憶される。ノード記述子のビット１７０８2に記憶された「０」は「Ｘ」に変換され、８ビットのマスキングされた値のビット１７１０2に記憶される。ノード記述子のビット１７０８3に記憶された「０」は、「Ｘ」に変換され、８ビットのマスキングされた値のビット１７１０3に記憶される。ノード記述子のビット１７０８4に記憶された「０」は「Ｘ」に変換され、８ビットマスキングされた値のビット１７１０4に記憶される。ノード記述子のビット１７０８5に記憶された「０」は「Ｘ」に変換され、８ビットのマスキングされた値のビット１７１０5に記憶される。ノード記述子のビット１７０８6に記憶された「１」は無視される。ノード記述子のビット１７０８7に記憶された「０」は８ビットのマスキングされた値のビット１７１０6に記憶される。ノード記述子のビット１７０８8に記憶された「１」は８ビットのマスキングされた値のビット１７１０7に記憶される。ノード記述子のビット１７０８9に記憶された「０」は８ビットのマスキングされた値のビット１７１０8に記憶される。
【０１５４】
図１９Ｄは、ＣＡＭ１６０６内のノード記述子１４０２1および１４０２2の記憶部と、選択された疎サブツリー記述子１４００に対してサブツリーマッパ４１８（図５）に記憶された対応のマッパエントリ５０４1−５０４3とを表わす。選択されたサブツリー記述子１４００に記憶された９ビットのノード記述子１４０２1および１４０２2は変換論理１６０４（図１８）に変換され、ＣＡＭ１６０６内へロードされる。ＣＡＭ１６０６内の第１のエントリ１７０２は、図１９Ａのサブツリー１７００に示すｒ０に対するデフォルトエントリである。第２のエントリ１７０４は、選択された疎サブツリー記述子１４００に記憶された第１のノード記述子１４０２1から変換される。第２のエントリ１７０４は、ｒ２に対して変換される最短の一致である。選択されたサブツリー記述子１４００に記憶された第２のノード記述子１４０２2は、０１０１０００００から０１０ＸＸＸＸＸへ変換され、ＣＡＭ１６０６内の第３のエントリ１７０６に記憶される。
【０１５５】
ＣＡＭ１６０６のサーチの結果、ブロックオフセット７１４（図１８）が得られる。このブロックオフセット７１４は、サブツリーマッパ４１８（図５）に記憶されたマッパエントリ５０４1−５０４3のマッパアドレス４１６を決定するのに用いられる。ＣＡＭ１６０６は、最長一致を記憶するエントリ１７０２、１７０４および１７０６についてキー２１０ｂの第２の部分でサーチされる。ＣＡＭ１６０６により提供されたブロックオフセット７１４は、選択されたサブツリーエントリ４０４内のポインタフィールド４０８に記憶されたブロックベースアドレス６００1、６００1のうちの１つに依存するサブツリーベースアドレスと組合される。
【０１５６】
図２０は、図８に示すポインタ論理７０２中のスパースモードベースセレクト論理１８００を表わすブロック図である。ポインタロジック７０２は、サブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）のマッパアドレス４１６を算出するのに用いられるベースアドレス７１６を選択する。ポインタ論理７０２はデンスモードベースセレクト論理７１０およびスパースモードベースセレクト論理１８００を含み、それらのうちの１つが、前のマッパレベルから転送された、サブツリーエントリ記述子３０４（図４）に記憶されたタイプ１４０６の状態に依存して、選択される。既に述べたように、タイプ１４０６の状態は、サブツリーエントリ４０４がデンスモードで構成されるか否かを示す。
【０１５７】
スパースモードベースセレクト論理１８００は、サブツリーエントリ４０４が複数の疎サブツリー記述子１４００を記憶していれば、疎サブツリー記述子１４００のベースアドレス７１６を算出する。スパースモードベースセレクト論理１８００は、モードフィールド１４０４に記憶されたモード値１６０８と、サブツリーエントリ４０４内のブロックベースアドレスフィールド６００1および６００2に記憶されたサブツリーポインタ４１４と、前のマッパレベルから転送されたサブツリーエントリ記述子３０４（図４）に記憶された疎サブツリー記述子セレクト１４０８とを用いて、ベースアドレス７１６を算出する。ベースアドレス７１６は以下のように算出される。
【０１５８】
（疎サブツリー記述子の）ベースアドレス＝ブロックベースアドレス＋ベースオフセット
ここでベースオフセット＝（（１＋ノード／サブツリー）＊疎サブツリー記述子セレクト）
たとえば、スパースモード４で構成されたサブツリーエントリ４０４におけるサブツリー番号２の開始時のベースアドレス７１６を見つけるためには、最初にベースオフセットが計算される。サブツリー番号２に対する疎サブツリー記述子セレクト１４０８は「１」であり、ノード／サブツリーの数は７である（表２参照）。ベースオフセットは８（（１＋７）＊１）である。ブロックベースアドレス６００1および６００2の各々が、サブツリーエントリ４０４に対して割当てられた１６のマッパアドレスのブロックのベースアドレスである。サブツリー番号２のベースオフセットは８であり、これは１６より小さいので、サブツリー２のブロックベースアドレスはブロックベースアドレス６００1になり、疎サブツリー記述子のベースアドレス７１６はブロックベースアドレス６００1＋８になる。以下の表５に、モード４で構成されたサブツリーエントリ４０４における４つのサブツリーの各々についてのサブツリーベースアドレスを表わす。
【０１５９】
【表５】
0004741134.tif 000006
【０１６０】
図２１は、サブツリーメモリ４００に記憶された稠密サブツリー記述子および疎サブツリー記述子を表わす。図２１は図１５と関連して説明する。サブツリーＢ（図２１）の稠密サブツリー記述子がサブツリーエントリ４０４1内のデータフィールド４０６1に記憶される。サブツリーＡ（図２１）の疎サブツリー記述子１４００1は、サブツリーエントリ４０４2内のデータフィールド４０６2に記憶される。稠密サブツリー記述子は、図６Ｂに関連して既に述べたように、サブツリーＢの最下レベルにおいて各ノードに対してノードビットを記憶する。スパースモード記述子１４００1は、図１９Ｂに関連して既に述べたように、ルートｒ４およびｒ５に対応するノード記述子１４０２1および１４０２2を含む。サブツリーインデックス３１２はサブツリーエントリ４０４1および４０４2を選択する。
【０１６１】
ｓ０（図１５）に対してマッパ１０６ａ内のマッパエントリ５０４中のサブツリーエントリ記述子３０４（図４）に記憶されたサブツリーインデックス３１２がサブツリーエントリ４０４1を選択する。ｓ１（図１５）に対するマッパ１０６ａ内のマッパエントリ５０４（図６Ｂ）におけるサブツリーエントリ記述子３０４（図４）に記憶されたサブツリーインデックス３１２は、サブツリーエントリ４０４2を選択する。このように、サブツリーメモリ４００は、疎サブツリーおよび稠密サブツリーに対してサブツリーエントリ４０４1および４０４2を記憶し得る。
【０１６２】
図２２は、疎に配置されたサブツリーおよび密に配置されたサブツリーにおけるあるノードに対するルートを記憶するサブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）についてのマッパアドレス４１６（図５）を提供するための方法を図示するフローチャートである。いずれのサブツリーエントリ４０４も、複数の疎サブツリー記述子または単一の稠密サブツリー記述子を記憶し得る。バイナリツリー内でルートがいかに分散されるかに依存して、疎サブツリー記述子と密サブツリー記述子とのいかなる組合せも可能である。サブツリーメモリ４００内のサブツリーエントリ４０４でスパースモードと稠密サブツリー記述子とを混合させ一致させる柔軟性により、サブツリーメモリ４００をより有用化することが可能になる。
【０１６３】
ステップ１９００において、選択されたサブツリーエントリ４０４の構成は、前のマッパレベルで選択されたサブツリーエントリ記述子３０４（図４）に記憶されたタイプ１４０６（図１６Ｃ）の状態から決定される。サブツリーエントリ４０４タイプがスパースモードで構成される場合、処理はステップ１９０２へ進む。そうでなければ、処理はステップ１９１４へ進む。
【０１６４】
ステップ１９０２において、サブツリーエントリ４０４はスパースモードで構成される。スパースモードで構成されるサブツリーエントリ４０４は、複数の疎サブツリー記述子１４００を記憶する。サブツリーエントリ４０４に記憶された疎サブツリー記述子１４００の数は、モードフィールド１４０４の状態に依存する。オフセット論理７００におけるスパースモード論理１５０２により、図１４に関連して前に述べたように前のマッパレベルから転送されたサブツリーエントリ記述子３０４（図４）に記憶された疎サブツリー記述子セレクト１４０８とモードフィールド１４０４の内容とに依存して、サブツリーエントリ４０４から疎サブツリー記述子１４００が選択される。処理はステップ１９０４へ進む。
【０１６５】
ステップ１９０４において、選択された疎サブツリー記述子１４００内のノード記述子１４０２に記憶された９ビットコード化された値は８ビット値に変換され、最短一致から最長一致の順序で、ＣＡＭ１６０６に記憶される。処理はステップ１９０６へ進む。
【０１６６】
ステップ１９０６において、ＣＡＭ１６０６が、最長の一致を記憶するＣＡＭエントリについてキー２１０ｂの次の部分でサーチされる。処理はステップ１９０８へ進む。
【０１６７】
ステップ１９０８において、キー２１０ｂの次の部分の最長一致を記憶するＣＡＭ１６０６における場所のアドレスが、ブロックオフセット７１４として転送される。ブロックオフセット７１４を用いて、サブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）のマッパアドレス４１６（図５）が算出される。処理はステップ１９１０へ進む。
【０１６８】
ステップ１９１０において、選択された疎サブツリー記述子１４００のベースアドレス７１６（図２０）は、前のマッパレベルから転送されたサブツリーエントリ記述子３０４（図４）に記憶された疎サブツリー記述子セレクト１４０８と、選択されたサブツリーエントリ４０４に記憶されたモードフィールド１４０４の内容とに依存して、算出される。処理はステップ１９１２へ進む。
【０１６９】
ステップ１９１２において、マッパアドレス４１６は、アダー論理７０４（図８）内でブロックオフセット７１４とベースアドレス７１６とを加算することにより算出される。サブツリーマッパ４１８（図５）内のマッパアドレス４１６により識別されたマッパエントリ５０４（図６Ｂ）は、ルートエントリ３０２（図４）またはサブツリーエントリ記述子３０４（図４）のいずれかを記憶する。マッパエントリ５０４（図６Ｂ）がルートエントリ３０２（図４）を記憶する場合、サーチは完了する。マッパエントリ５０４（図６Ｂ）がサブツリーエントリ記述子３０４（図４）を記憶する場合、キー２１０に対応する値のサーチが次のマッパレベルにおいて継続される。
【０１７０】
ステップ１９１４において、サブツリーエントリ４０４はデンスモードで構成され、データフィールド４０６に単一の稠密サブツリー記述子を記憶する。ブロックオフセット７１４は、図６Ｂに関連して前述したように、サブツリーエントリ４０４内のデータフィールド４０６に記憶された稠密サブツリー記述子に記憶された「１」の数をカウントすることにより、算出される。処理はステップ１９１６へ進む。
【０１７１】
ステップ１９１６において、サブツリーエントリ４０４は、サブツリーエントリ４０４内のポインタフィールド４０８に１６個のブロックベースアドレス６００を記憶する。ブロックベースポインタ６００のうちの１つが、図８と関連して前述したポインタ論理７０２におけるデンスモードベースセレクト論理７１０により選択される。処理はステップ１９１２へ進む。
インクリメンタルな更新
図２３は、ルックアップテーブル２００に追加される新たなルートのバイナリツリーを表わす図である。このバイナリツリーは、マッパレベル＿１  ２０００、マッパレベル＿２  ２００２およびマッパレベル＿３  ２００４について、ルックアップテーブル２００に記憶されたルートを表わす。マッパレベル＿２  ２００２は、サブツリーＡおよびＢに対するルートを記憶する。マッパレベル＿３  ２００４はサブツリーＡ1、Ａ2、Ｂ1およびＢ2に対するルートを記憶する。ｓ５は、サブツリーマッパ４１８（図５）に記憶されたサブツリーエントリ記述子３０４（図４）を表わす。ｓ５に対するサブツリーエントリ記述子３０４（図４）はサブツリーＢ2に対するポインタを記憶し、キー２１０に対する最長一致のルートのサーチをマッパレベル＿３  ２００４で継続できるようにする。
【０１７２】
サブツリーＢ2  ２００６は、２つのルート、ｒ６およびｈ１のみを有するので、疎サブツリーである。したがって、ノードｒ６およびｈ１のノード記述子１４０２（図１６Ａ）は、図１４Ａに関連して既に述べたように、疎サブツリー記述子１４００に記憶される。サブツリーＢ2  ２００６の疎サブツリー記述子１４００はサブツリーエントリ４０４に記憶され、サブツリーメモリ４００においてモードフィールド１４０４は１にセットされる。これは、疎サブツリー記述子１４００に記憶されたノード記述子１４０２が２つあるためである。
【０１７３】
サブツリーＢ2′２００８に示す新たなルートｈ２は、ルックアップテーブル２００に追加されることになる。新たなルートｈ１をルックアップテーブル内のサブツリーＢ2  ２００６に直接追加することはできない。なぜなら、サブツリーＢ2  ２００６に対するルートを追加することにより、疎サブツリー記述子１４００に記憶されたノード記述子１４０２の数が２から３へ増加するからである。疎サブツリー記述子１４００へノード記述子１４０２を追加するとモードフィールド１４０４が「２」にセットされたサブツリーエントリ４０４において新たな疎サブツリー記述子１４００を割当てる必要が生じる。すなわち、新たなルートｈ１の追加により、サブツリーＢ2２００６をサブツリーＢ2′２００８で置き換える必要が生じる。
【０１７４】
図２４は、プロセッサメモリ２４００に記憶された更新ルートを表わす。ルックアップテーブル２００に記憶されたバイナリツリーのコピーもまた、ルックアップテーブル２００とは別のプロセッサメモリ２４００に記憶される。サブツリーＢ2  ２００６について記憶されたルートはプロセッサメモリ２４００内のサブツリーＢ2′２００８にコピーされ、新たなルートｈ２がサブツリーＢ2′２００８に追加される。
【０１７５】
ルート更新ルーチン２４０２は、ルート更新命令２４０４のシーケンスを生成してサブツリーＢ2′２００８をルックアップテーブル２００に追加し、ルート更新２４０４をテーブル更新ルーチン２４０６へ転送する。テーブル更新ルーチン２４０６はルート更新２４０２に対してテーブル更新２４１０を生成し、更新サイクル２４１２を転送し、ルックアップテーブル２００をルート更新２４０４で更新する。更新サイクル２４１２は、サブツリーマッパ４１８（図５）およびサブツリーメモリ４００（図５）における適切なメモリ場所にルート更新を書込む。
【０１７６】
図２３を参照して、更新サイクル２４１２はサブツリーマッパ４１８（図５）の一部分を割当て、新たなサブツリーＢ2′２００８のルートをマッパエントリ５０４（図６Ｂ）に記憶するための命令を含む。サブツリーＢ2′２００８は、ルートｈ１およびｒ６ならびに新たなルートｈ２に対してマッパエントリ５０４（図６Ｂ）に記憶されたルートエントリを含む。サブツリーＢ2′２００８に対するルートエントリがサブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）に記憶された後、ルートに対するノード記述子１４０２が作成され、疎サブツリー記述子１４００に記憶される。疎サブツリー記述子１４００はサブツリーエントリ４０４に記憶される。サブツリーエントリ４０４のモード１４０４は、疎サブツリー記述子１４００に記憶されたノード記述子１４０２の数に関連する。
【０１７７】
サブツリーＢ2′２００８の疎サブツリー記述子１４００がルックアップテーブル２００中のサブツリーメモリ４００のサブツリーエントリ４０４に記憶された後、ｓ５で表わされるサブツリーエントリ記述子３０４（図４）は、サブツリーＢ2２００６の代わりにサブツリーＢ2′２００８を指すように変更される。サブツリーＢ2′２００８がルックアップテーブルに追加される一方、サブツリーＢ2  ２００６に記憶されたルートｒ６およびｈ１はｓ５を介してアクセスされ得る。サブツリーＢ2′２００８がルックアップテーブルに記憶された後、ｓ５は、サブツリーＢ2′２００８およびルートｒ６を指すように変更され、新たなルートｈ２がアクセスされ得る。したがって、サブツリーＢ2  ２００６の、ルートｒ６およびｈ１に対応するルートインデックスについてのサーチを継続することができ、一方、新たなルートｈ２はルックアップテーブル２００に追加される。
【０１７８】
図２５は、ルックアップテーブル２００中のサブツリーマッパ４１８ｂにおけるマッパエントリ５０４ｃ4に記憶された、図２３に示す新たなルートｈ２を表わす。図２５は、図２４に示すバイナリツリーの図に関連して説明する。
【０１７９】
マッパレベル＿２  ２００２におけるサブツリーＢは３つのルート、すなわちｒ３、ｓ４およびｓ５を有する。サブツリーＢは１６未満のルートを有するので、疎サブツリーである。サブツリーＢのｒ３、ｓ４およびｓ５に対するノード記述子１４０２ａ1−１４０２ａ3は、サブツリーメモリ４００ａ内のサブツリーエントリ４０４ａにおける疎サブツリー記述子１４００ａ1に記憶される。マッパエントリ５０４ａ2−５０４ａ4は、サブツリーＢ内の各ルートに対してサブツリーマッパ４１８ａに記憶される。サブツリーＢのデフォルトルートは、サブツリーマッパ４１８ａ内のマッパエントリ５０４ａ1に記憶される。マッパエントリ５０４ａ2−５０４ａ4の各々は、そのノードに対するルートエントリ３０２（図４）またはサブツリーエントリ記述子３０４（図４）を記憶する。サブツリーエントリ記述子３０４（図４）は、ルートｓ４については５０４ａ3に、ｓ５については５０４ａ4に記憶される。ｓ５についてマッパエントリ５０４ａ4に記憶されたサブツリーエントリ記述子３０４（図４）は、サブツリーメモリ４００ｂにサブツリーインデックス３１２ｂを与え、次のレベルのサーチ、すなわちマッパレベル＿３  ２００４に対するサーチを開始する。
【０１８０】
サブツリーＢ2は、２つのルートすなわちｈ１およびｒ６を有するので、これもまた疎サブツリーである。ノード記述子１４０２ｂ1−１４０２ｂ2は、サブツリーメモリ４００ｂ内のサブツリーエントリ４０４ｂにおける疎サブツリー記述子１４００ｂ1に記憶される。サブツリーＢ2内の各ルートは、マッパエントリ５０４ｂ2−５０４ｂ3に記憶され、サブツリーＢ2のデフォルトルートがマッパエントリ５０４ｂ1に記憶される。
【０１８１】
サブツリーＢ2２００６内でルートｈ１についてサーチするために、ルートｓ５についてノード記述子１４０２を記憶する疎サブツリー記述子１４００ａを記憶しているサブツリーエントリ４０４ａのアドレスが、サブツリーインデックス３１２ａ上でサブツリーメモリ４００ａへ転送される。選択されたサブツリーエントリ４０４ａに記憶されたデータフィールド４０６およびポインタフィールド４０８は、サブツリーデータ４１２ａおよびサブツリーポインタ４１４ａ上でマッパアドレス論理４０２ａへ転送される。マッパアドレス論理４０２ａは、ｓ５についてサブツリーエントリを記憶しているマッパエントリ５０４ａ4のマッパアドレス４１６ａを生成する。マッパアドレス４１６ａは、サブツリーデータ４１２ａ、サブツリーポインタ４１４ａおよびキー２１０ｂの次の部分に依存する。ｓ５のサブツリーエントリは、サブツリーインデックス３１２ｂ上でサブツリーメモリ４００ｂへ転送される。
【０１８２】
サブツリーメモリ４００ｂは、サブツリーＢ2  ２００６についてノード記述子１４０２ｂ2および１４０２ｂ1を記憶する。Ｂ2についての疎サブツリー記述子１４００ｂ1がサブツリーエントリ４０４ｂに記憶される。サブツリーエントリ４０４ｂに記憶されたデータフィールド４０６およびポインタフィールド４０８は、サブツリーデータ４１２ｂおよびサブツリーポインタ４１４ｂ上でマッパアドレス論理４０２ｂへ転送される。マッパアドレス論理４０２ｂは、ｈ１についてルートエントリを記憶しているマッパエントリ５０４ｂ3のマッパアドレス４１６ｂを生成する。マッパアドレス４１６ｂは、サブツリーデータ４１２ｂ、サブツリーポインタ４１４ｂおよびキー２１０ｃの次の部分に依存している。
【０１８３】
ルートｈ２をサブツリーＢ2  ２００６に追加するためには、サブツリーマッパ４１８ｂ内のこれまでに未使用のマッパエントリ６０２ｂのブロックが割当てられ、サブツリーＢ2′２００８についてルートｒ６、ｈ１およびｈ２を記憶しているマッパエントリ５０４ｃ2−５０４ｃ4を記憶する。マッパエントリ５０４ｃ1は、サブツリーＢ2′２００８のデフォルトエントリ、すなわち、マッパエントリ５０４ｂ1に記憶されたものと同じ値を記憶する。マッパエントリ５０４ｃ2はルートｒ６のルートエントリ、すなわちマッパエントリ５０４ｂ2に記憶されたものと同じ値を記憶する。マッパエントリ５０４ｃ3はルートｈ１のルートエントリ、すなわちマッパエントリ５０４ｂ3に記憶されたものと同じ値を記憶する。マッパエントリ５０４ｃ4は、新たなルートｈ２に対するルートエントリを記憶する。マッパエントリ５０４ｃ1-4のブロックが書込まれている間に、マッパエントリ５０４ｂ1−５０４ｂ3に記憶されたルートエントリは、サブツリーマッパ４１８ａ内の５０４ａ4にルートｓ５について記憶されたサブツリーエントリを介して、アクセスされ得る。
【０１８４】
サブツリーマッパ４１８ｂにはサブツリーＢ2′２００８についてのマッパエントリ５０４ｃ1-4が記憶されており、疎サブツリー記述子１４００ｃ1がサブツリーメモリ４００ｂに追加される。ノード記述子１４０２ｃ1-3の数は１６未満であるので、ノード記述子１４０２ｃ1-3は疎サブツリー記述子１４００ｃ1に記憶される。サブツリーメモリ４００ｂ内のサブツリー記述子１４００1の場所は、疎サブツリー記述子１４００ｃ1に関連付けられるノード記述子１４０２ｃ1-3の数に依存する。サブツリーＢ2  ２００６に新たなルートを追加することにより、疎サブツリー記述子１４００ｃ1に対して記憶されるノード記述子１４０２ｃ1−１４０２ｃ3の数は２から３へ増加する。疎サブツリー記述子１４００ｃ1はサブツリーエントリ４０４ｃに記憶され、各疎サブツリー記述子ごとに３つのノード記述子があり、モードフィールド１４０４は「２」にセットされる。疎サブツリー記述子１４００ｃ1は、利用可能なスペースがあれば現在のモード３サブツリーエントリ４０４ｃに記憶されるか、または新たなモード３サブツリーエントリが割当てられる。Ｂ2′２００８内のルートについてのノード記述子は、モード３サブツリーエントリ４０４ｃの疎サブツリー記述子１４００ｃ1におけるノード記述子１４０２ｃ1-3に記憶される。
【０１８５】
疎サブツリー記述子１４００ｃ1およびノード記述子１４０２ｃ1-3がサブツリーメモリ４００ｂに記憶された後、サブツリーＢ2′２００８がアクセスされ得る。Ｂ2′２００８にアクセスを提供するために、サブツリーエントリ５０４ａ4は、サブツリーエントリ４０４ｂ内の疎サブツリー記述子１４００ｂ1の代わりにサブツリーエントリ４０４ｃ内の疎サブツリー記述子１４００ｃ1をインデックス付けするよう変更される。マッパエントリ５０４ｃ4に記憶されたルートｈ２についてのルートエントリならびにそれぞれのマッパエントリ５０４ｃ2および５０４ｃ3に記憶されたルートｒ６およびｈ１がアクセスされ得る。
【０１８６】
マッパエントリ５０４ｂ1−５０４ｂ3はもはやアクセス不可能であるので、割当解除され、将来の割当のためにフリーリスト（図示せず）上に置かれる。また疎サブツリー記述子１４００ｂ1ももはやアクセス不可能である。こうして、疎サブツリー記述子１４００ｂ1は割当解除され、将来の割当のためにフリーリスト（図示せず）に置かれる。
【０１８７】
疎サブツリーにルートを追加することについて説明した。ルートは、新たに割当てられたサブツリーエントリ４０４に新たな稠密サブツリー記述子を記憶し、対応のマッパエントリをサブツリーマッパ４１８に記憶することにより、また、マッパエントリ５０４ａ4に記憶されたサブツリーエントリを新たに割当てられたサブツリーエントリ４０４のインデックス付けを行なうように変更することにより、追加することもできる。
【０１８８】
図２６は、図２５に示すルックアップテーブル２００にあるルートを追加するためにインクリメンタルな更新を行なうためのステップを表わすフローチャートである。
【０１８９】
ステップ２２００において、サブツリーごとのルートの数が算出され、ルート更新結果が疎サブツリーであるか稠密サブツリーであるかが判定される。ルート更新後のサブツリーが稠密であれば、処理はステップ２２１８へ進む。ルート更新後のサブツリーが疎であれば、処理はステップ２２０２へ進む。
【０１９０】
ステップ２２０２において、サブツリーは疎である。疎サブツリーモードが決定される。処理は２２０４へ進む。
【０１９１】
ステップ２２０４において、サブツリーマッパ４１８（図５）に記憶された部分的にフルにされたサブツリーエントリ４０４のリストがサーチされ、新たな疎サブツリー記述子１４００ｃ1が前に割当てられたサブツリーエントリ４０４に記憶され得るか否かが判定される。たとえば、４つの疎サブツリー記述子１４００ｃ1−１４００ｃ4がモード４サブツリーエントリ４０４に記憶され得る。３つのみが記憶される場合、サブツリーエントリ４０４は部分的にフルにされており、部分的に満たされたサブツリーエントリ４０４のリストに記憶される。部分的にフルなサブツリーエントリ４０４が利用可能であれば、処理はステップ２２０８へ進む。そうでなければ、処理はステップ２２０６へ進む。
【０１９２】
ステップ２２０６において、新たなサブツリーエントリ４０４ｃが疎サブツリー記述子１４００ｃ1を記憶するために割当てられ、マッパエントリ５０４ｃ1−５０４ｃ4が、新たに割当てられたサブツリーエントリ４０４ｃ内の疎サブツリー記述子１４００ｃ1に記憶されたノード記述子１４０２ｃ1−１４０２ｃ3のマッパエントリ５０４（図６Ｂ）を記憶するために、サブツリーマッパに割当てられる。サブツリーマッパ４１８（図５）内のマッパエントリ５０４ｃ1−５０４ｃ4の割当てられたブロックに対するポインタは、新たなサブツリーエントリ４０４ｃ内のポインタフィールド４０８に記憶される。処理はステップ２２０８へ進む。
【０１９３】
ステップ２２０８において、疎サブツリー記述子１４００ｃ1に対するサブツリーマッパ内の第１のマッパエントリ５０４ｃ1の場所が、サブツリーエントリ４０４ｃ内のポインタフィールド４０８に記憶されたポインタおよびサブツリーエントリ４０４ｃ内のモードフィールド１４０４に記憶されたモードから判定される。処理はステップ２２１０へ進む。
【０１９４】
ステップ２２１０において、疎サブツリーのルートエントリが、サブツリーマッパ４１８ｂ内のマッパエントリ５０４ｃ1−５０４ｃ4に記憶される。処理はステップ２２１２へ進む。
【０１９５】
ステップ２２１２において、ノード記述子１４０２ｃ1−１４０２ｃ3を記憶している疎サブツリー記述子１４００ｃ1がサブツリーエントリ４０４ｃに記憶される。処理はステップ２２１４へ進む。
【０１９６】
ステップ２２１４において、マッパエントリ５０４ａ4に記憶されたサブツリーエントリ記述子３０４（図４）は、サブツリーエントリ４０４ｃに記憶された新たな疎サブツリー記述子１４００ｃ1のインデックス付けを行なうよう変更される。マッパエントリ５０４ｃ4に記憶されたｈ２のルートエントリがここでアクセス可能にある。処理はステップ２２１６へ進む。
【０１９７】
ステップ２２１６において、マッパエントリ５０４ｂ1−５０４ｂ3および疎サブツリー記述子１４００ｂはもはやアクセス不可能である。マッパエントリ５０４ｂ1−５０４ｂ3は、サブツリーマッパ４１８ｂのマッパエントリ５０４（図６Ｂ）のフリーリストに置かれ、他のルートを記憶するために割当てられ得る。サブツリーエントリ４０４ｂ内の第１の利用可能な場所は、部分的にフルなサブツリーエントリのリストにおいて更新される。処理が完了する。
【０１９８】
ステップ２２１８において、新たなサブツリーエントリ４０４がプロセッサメモリ２４００（図２４）に記憶されたフリーのサブツリーエントリ４０４のリストから割当てられる。この新たなサブツリーエントリ４０４は、新たな稠密サブツリー記述子を記憶するために割当てられる。サブツリーマッパ４１８ｂにおけるマッパエントリ５０４（図６Ｂ）のブロックが、ルートを記憶するために割当てられる。割当てられたマッパエントリ５０４（図６Ｂ）のブロックに対するポインタは、サブツリーエントリ４０４（図５）内のポインタフィールド４０８（図７）に記憶される。処理はステップ２２２０へ進む。
【０１９９】
ステップ２２２０において、新たな稠密サブツリー記述子が、図６Ａおよび６Ｂに関連して前述したように、新たなサブツリーエントリ４０４内のデータフィールド４０６に書込まれる。処理はステップ２２２２へ進む。
【０２００】
ステップ２２２２において、稠密サブツリーのルートエントリが、サブツリーエントリ４０４内のポインタフィールド４０８に記憶されたポインタにより識別されたサブツリーマッパ４１８（図５）内のマッパエントリ５０４（図６Ｂ）に記憶される。処理はステップ２２２４へ進む。
【０２０１】
ステップ２２２４において、マッパエントリ５０４ａ4に記憶されたサブツリーエントリ記述子３０４（図４）は、新たなサブツリーエントリ４０４ｃに記憶された新たな稠密サブツリー記述子をインデックス付けするよう変更される。マッパエントリ５０４ｃ4に記憶されたｈ２に対するルートエントリがここでアクセス可能になる。処理はステップ２２２６へ進む。
【０２０２】
ステップ２２２６において、古いサブツリーエントリ４０４内のポインタフィールド４０８に記憶されたポインタによりインデックス付けされたマッパエントリ５０４（図６Ｂ）は、プロセッサメモリ２４００（図２４）に記憶されたマッパエントリのフリーリストへ戻される。この古いサブツリーエントリ４０４ｂは、プロセッサメモリ２４００（図２４）に記憶されたサブツリーエントリのフリーリストに追加される。
【０２０３】
ルートをルックアップテーブルに追加する処理について述べてきた。ルートをルックアップテーブルから削除するためにも同様の処理が行なわれる。たとえば、ｈ２  ５０４ｃ4をサブツリーＢ2′から削除するためには、ルートｒ６およびｈ１の２つのノード記述子を有する新たな疎サブツリー記述子を記憶し、モード２サブツリーエントリに疎サブツリー記述子を記憶し、対応のサブツリーマッパを更新し、マッパエントリ５０４ａ4に記憶されたサブツリーエントリ記述子３０４（図４）を、新たなサブツリーエントリ４０４に記憶された更新されたサブツリー記述子のインデックス付けを行なうよう変更する必要がある。
【０２０４】
この発明はその好ましい実施例を参照して具体的に図示し説明してきたが、当業者には、前掲の請求項に包含される本発明の範囲から離れることなく、形式および内容の点で種々の変更をなすことができることがわかるであろう。
【図面の簡単な説明】
【図１Ａ】  バイナリツリーの第１のレベルを表わす先行技術のビットマップを示す図である。
【図１Ｂ】  キャッシュメモリで実現される先行技術のルックアップテーブルを示す図である。
【図２Ａ】  この発明の原則に従う最長一致プレフィックスルックアップテーブルを示す図である。
【図２Ｂ】  図２Ａに示されるルックアップテーブルに記憶されるルートインデックスのバイナリツリー表示を示す図である。
【図３】  この発明の原則に従う４０ビットキーに対する最長一致プレフィックスルックアップテーブルを示す図である。
【図４】  図２Ａに示されるダイレクト・マップト・マッパに記憶可能なマッパエントリのタイプを示す図である。
【図５】  図２Ｂに示されるマッパレベル＿２  １１２ｂ中のノードに対応するマッパを示す図である。
【図６Ａ】  サブツリーのバイナリツリー表示の図である。
【図６Ｂ】  図６Ａに示されたサブツリーのボトムレベルのノードに対応する、図５に示されたデータフィールドに記憶される稠密サブツリー記述子を示す図である。
【図７】  図５に示されたｐｔｒフィールドを示す図である。
【図８】  図５に示されたマッパアドレス論理を示す図である。
【図９】  最長一致をサーチするためのステップを図示するフローチャートの図である。
【図１０Ａ】  深度拡張を与えるための実施例を示す図である。
【図１０Ｂ】  図１０Ａに示された実施例のルックアップテーブルの１つを示す図である。
【図１０Ｃ】  値を記憶するのに利用可能なマップエントリの数を増やすために深度拡張を与えるための別の実施例を示す図である。
【図１０Ｄ】  図１０Ｃに示された実施例のスレーブルックアップテーブルを示す図である。
【図１１Ａ】  図１０Ａおよび図１０Ｃに示されたルックアップテーブル中のマッパエントリの中の、図２Ｂに示されたルートインデックスのバイナリツリー表示のノードの分布のバイナリツリー表示を示す図である。
【図１１Ｂ】  図１０Ａおよび図１０Ｃに示されたルックアップテーブル中のマッパエントリの中の、図２Ｂに示されたルートインデックスのバイナリツリー表示のノードの分布のバイナリツリー表示を示す図である。
【図１２】  図１０Ａおよび図１０Ｃに示されたルックアップテーブル中のマッパエントリの中に値を分散するための方法を図示するフローチャートの図である。
【図１３】  図１０Ｃに示されたルックアップテーブル中のマッパエントリのうち１つに記憶されるサーチキーに対応する値をサーチするための方法を図示するフローチャートの図である。
【図１４】  図１０Ａに示されたルックアップテーブル中のマッパエントリのうち１つに記憶されるサーチキーに対応する値をサーチするための方法を図示するフローチャートの図である。
【図１５】  第１のマッパレベルによってインデックス付けされる第２のマッパレベル中の疎らなサブツリーおよび稠密なサブツリーのバイナリツリー表示を示す図である。
【図１６Ａ】  図５に示されるサブツリーエントリおよび図４に示されるサブツリーエントリのデータフィールドおよびポインタフィールドに対して変更を加えて、サブツリーエントリ中への複数の疎らなサブツリー記述子の記憶を可能にするのを示す図である。
【図１６Ｂ】  図５に示されるサブツリーエントリおよび図４に示されるサブツリーエントリのデータフィールドおよびポインタフィールドに対する変更を加えてサブツリーエントリ中への複数の疎らなサブツリー記述子の記憶を可能にするのを示す図である。
【図１６Ｃ】  図５に示されるサブツリーエントリおよび図４に示されるサブツリーエントリのデータフィールドおよびポインタフィールドに対する変更を加えてサブツリーエントリ中への複数の疎らなサブツリー記述子の記憶を可能にするのを示す図である。
【図１７】  疎らに配されたサブツリー中のノードに対してブロックオフセットを選択するための、図８に示されたオフセット論理中のスパースモードサブツリー論理を示す図である。
【図１８】  図１７のオフセット論理に示されたスパースモード論理を示す図である。
【図１９Ａ】  疎らに配されたサブツリー中のノードに対するブロックオフセットの選択を示す図である。
【図１９Ｂ】  疎らに配されたサブツリー中のノードに対するブロックオフセットの選択を示す図である。
【図１９Ｃ】  疎らに配されたサブツリー中のノードに対するブロックオフセットの選択を示す図である。
【図１９Ｄ】  疎らに配されたサブツリー中のノードに対するブロックオフセットの選択を示す図である。
【図２０】  図８に示されたポインタ論理中のスパースモードベースセレクト論理を示すブロック図である。
【図２１】  サブツリーメモリに記憶される、稠密サブツリー記述子および疎サブツリー記述子を示す図である。
【図２２】  疎らに配されたサブツリーおよび密に配されたサブツリー中のノードに対してルートを記憶するサブツリーマッパ中のマッパエントリに対してマッパアドレスを与えるための方法を図示するフローチャートの図である。
【図２３】  ルックアップテーブルに加えるべき新たなルートのバイナリツリー表示を示す図である。
【図２４】  プロセッサメモリに記憶される更新ルートを示す図である。
【図２５】  ルックアップテーブルに記憶される、図２３に示された新たなルートを示す図である。
【図２６】  図２５に示されたルックアップテーブルに新たなルートを加えるためのステップを図示するフローチャートの図である。
【図１Ａ】
0004741134.tif 000007
【図１Ｂ】
0004741134.tif 000008
【図２Ａ】
0004741134.tif 000009
【図２Ｂ】
0004741134.tif 000010
【図３】
0004741134.tif 000011
【図４】
0004741134.tif 000012
【図５】
0004741134.tif 000013
【図６Ａ】
0004741134.tif 000014
【図６Ｂ】
0004741134.tif 000015
【図７】
0004741134.tif 000016
【図８】
0004741134.tif 000017
【図９】
0004741134.tif 000018
【図１０Ａ】
0004741134.tif 000019
【図１０Ｂ】
0004741134.tif 000020
【図１０Ｃ】
0004741134.tif 000021
【図１０Ｄ】
0004741134.tif 000022
【図１１Ａ】
0004741134.tif 000023
【図１１Ｂ】
0004741134.tif 000024
【図１２】
0004741134.tif 000025
【図１３】
0004741134.tif 000026
【図１４】
0004741134.tif 000027
【図１５】
0004741134.tif 000028
【図１６Ａ】
0004741134.tif 000029
【図１６Ｂ】
0004741134.tif 000030
【図１６Ｃ】
0004741134.tif 000031
【図１７】
0004741134.tif 000032
【図１８】
0004741134.tif 000033
【図１９Ａ】
0004741134.tif 000034
【図１９Ｂ】
0004741134.tif 000035
【図１９Ｃ】
0004741134.tif 000036
【図１９Ｄ】
0004741134.tif 000037
【図２０】
0004741134.tif 000038
【図２１】
0004741134.tif 000039
【図２２】
0004741134.tif 000040
【図２３】
0004741134.tif 000041
【図２４】
0004741134.tif 000042
【図２５】
0004741134.tif 000043
【図２６】
0004741134.tif 000044