(57)【特許請求の範囲】
【請求項１】
所与の入力検索引数に応答して、最長一致プレフィックス選択に基づいて、ノード・テーブルの複数レベル配置でのルックアップ動作を使用して、出力を決定する方法であって、
連続するステップで、連続するレベルのノード・テーブル内のテーブル項目が、終了表示が見つかるまで質問され、
・それぞれが個別に決定可能な長さを有する検索引数の選択されたセグメントが、ノード・テーブル内の項目にアクセスするためのインデックスとして使用され、
・それぞれが個別に決定可能な長さを有する前記検索引数の他の選択されたセグメントが、検索手順の次のステップを決定するために、ノード・テーブルの項目に保管されたテスト値（ＴＶ）との比較のためのテスト引数として使用される
方法。
【請求項２】
ノード・テーブル項目の選択およびアクセスが、
・後にアクセスされる項目を含むノード・テーブルを識別するテーブル・ベース・ポインタ（ＰＴＲ）と、
・オフセット値と
によって行われる、請求項１に記載の方法。
【請求項３】
前記オフセット値が、
・前記検索引数のセグメント（インデックス）であって、前記セグメントが、前記それぞれの項目に含まれる選択情報（ＣＮＴ）に応答して選択される、セグメント（インデックス）、または、
・保管されたテスト値（ＴＶ）と前記検索引数の選択されたセグメント（テスト引数）との間の比較の２進テスト結果
のいずれかによって決定される、請求項２に記載の方法。
【請求項４】
前記オフセット値が、ノード・テーブル項目に保管されたテスト値と前記検索引数の選択されたセグメントとの間の比較の２進テスト結果に応答して決定され、
ａ）前記テスト結果が、第１の２進値（たとえば０）を有する場合に、前記オフセット値が、前記テーブル・ベース・ポインタ（ＰＴＲ）によって選択される前記ノード・テーブル内の所定の項目を選択する所与の値であり、
ｂ）前記テスト結果が、第２の２進値（たとえば１）を有する場合に、前記検索引数のもう１つのセグメントが、前記それぞれの項目に含まれる第２選択情報（ＣＮＴ２）に応答して選択され、前記テーブル・ベース・ポインタ（ＰＴＲ）によって選択される前記ノード・テーブル内の項目のアクセスのためのオフセット値を導出するためのインデックスとして使用される
請求項２に記載の方法。
【請求項５】
前記オフセット値が、ノード・テーブル項目に保管されたテスト値と前記検索引数の選択されたセグメントとの間の比較の２進テスト結果に応答して決定され、
ａ）前記テスト結果が、第１の２進値（たとえば０）を有する場合に、前記オフセット値が、前記テーブル・ベース・ポインタ（ＰＴＲ）によって選択される前記ノード・テーブル内の第１の所定の項目を選択する第１の所与の値であり、
ｂ）前記テスト結果が、第２の２進値（たとえば１）を有する場合に、前記オフセット値が、前記テーブル・ベース・ポインタ（ＰＴＲ）によって選択される前記ノード・テーブル内の第２の所定の項目を選択する第２の所与の値である
請求項２に記載の方法。
【請求項６】
・ノード・テーブル項目を選択するステップと、
・テスト値の適用が示される場合に、前記テーブル項目からまたはもう１つのノード・テーブル内の所定の項目からテスト値（ＴＶ）を抽出するステップと、
・前記テスト値に関連し、前記選択されたテーブル項目に含まれる選択情報（ＣＮＴ；ＣＮＴ１）に応答して、テスト引数として前記検索引数からのセグメントを選択するステップと、
・前記テスト値を前記検索引数の前記選択されたテスト引数セグメントと比較するステップと、
・前記検索手順の次のステップを決定するために前記テスト結果を使用するステップと
を含む、請求項１に記載の方法。
【請求項７】
・テーブル・ベース・ポインタ（ＰＴＲ）が、もう１つのノード・テーブルを選択するために、前記選択されたノード・テーブル項目から抽出され、
・前記テスト値（ＴＶ）が、前記選択された他のノード・テーブルの所定の項目から抽出される
請求項６に記載の方法。
【請求項８】
テーブル・ベース・ポインタ（ＰＴＲ）が、もう１つのノード・テーブルを選択するために、前記選択されたノード・テーブル項目から抽出され、
・前記テスト値（ＴＶ）も、同一の選択されたノード・テーブル項目から抽出される
請求項６に記載の方法。
【請求項９】
・テーブル・ベース・ポインタ（ＰＴＲ）が、もう１つのノード・テーブルを選択するために、前記選択されたノード・テーブル項目から抽出され、
・第２選択情報（ＣＮＴ２）を前記それぞれの項目から入手し、前記検索引数のもう１つのセグメントを抽出するのに使用されるサブステップであって、前記もう１つのセグメントが、前記選択された他のノード・テーブル内の項目にアクセスするためのオフセット値を決定するためのインデックスとして使用される、サブステップ、または、
・前記他のノード・テーブル内の所定の位置がアクセスされるサブステップ
のいずれかが、前記２進テスト結果に応答して実行される、請求項６に記載の方法。
【請求項１０】
テーブル・ベース・ポインタ（ＰＴＲ）が、もう１つのノード・テーブルを選択するために、前記選択されたノード・テーブル項目から抽出され、
・前記２進テスト結果に依存して、前記他のノード・テーブルの２つの所定の項目の一方または他方が選択される
請求項６に記載の方法。
【請求項１１】
再利用表示（Ｒ）が、前記それぞれの項目に含まれ、２つの可能なテスト結果の所定の１つが得られた時に、
・前記検索引数の前に選択されたテスト引数セグメントのすべてまたは一部と少なくとも部分的に同一であるもう１つの選択されたセグメントを前記検索引数から得るために、もう１つの選択情報（ＣＮＴ２）が使用され、
・前記他の選択されたセグメントが、もう１つのノード・テーブル項目にアクセスするためのインデックス値、またはもう１つのテスト値と比較されるテスト引数のいずれかとして使用される
請求項６に記載の方法。
【請求項１２】
・前記他の選択されたセグメントが、前に使用されたテスト引数セグメントの一部である
請求項１１に記載の方法。
【請求項１３】
・前記他の選択されたセグメントが、前に使用されたテスト引数セグメントと同一であるかこれを含む
請求項１１に記載の方法。
【請求項１４】
所与の入力検索引数に応答して、最長一致プレフィックス選択に基づいて、ノード・テーブルの複数レベル配置でのルックアップ動作を使用して、出力を決定するシステム内の、それぞれが複数の項目を有するノード・テーブルを含む保管されたデータ構造であって、
・各ノード・テーブル項目が、テーブル・インデックスとして使用される前記検索引数の選択されたセグメントに応答してアクセスされる、または、比較テスト動作の結果に応答して直接にアクセスされる、のいずれかであり、
・前記ノード・テーブル項目が、
ａ）基本項目であって、それぞれが、少なくとも、
・動作表示（Ｆ１、Ｆ２）と、
・前記検索引数のセグメントを選択するための選択情報（ＣＮＴ）と、
・使用される次のノード・テーブルを識別するテーブル・ベース・ポインタ（ＰＴＲ）と
を保持する、基本項目と、
ｂ）追加項目（ＴＶ、ＮＨＰ、ＮＩＬ）と
を含む
保管されたデータ構造。
【請求項１５】
各追加項目が、
・出力インジケータ（ＮＨＰ）または停止インジケータ（ＮＩＬ）のいずれかである終了表示（ＥＮＤ）と、
・前記検索引数の選択されたセグメントと比較されるテスト値（ＴＶ）と
の１つを保持する、請求項１４に記載の保管されたデータ構造。
【請求項１６】
基本項目が、追加的に、
・同一項目の処理中に前記検索引数からさらなるセグメントを抽出するための第２選択情報（ＣＮＴ２）
を含むことができる、請求項１４に記載の保管されたデータ構造。
【請求項１７】
ノード・テーブル内の前記基本項目の少なくともいくつかが、
・それぞれが前記所与の検索引数のセグメントを選択するための、選択情報の２つの項目（ＣＮＴ１、ＣＮＴ２）であって、前記選択されたセグメントの一方が、テーブル・ベース・ポインタ（ＰＴＲ）によって指定されるノード・テーブル内の項目にアクセスするためのインデックス値を構成し、前記選択されたセグメントの他方が、保管されたテスト値（ＴＶ）と比較されるテスト引数を構成する、選択情報の２つの項目（ＣＮＴ１、ＣＮＴ２）
を含む、請求項１４に記載の保管されたデータ構造。
【請求項１８】
前記ノード・テーブルの少なくとも１つが、
ａ）テスト結果に応答して直接にアクセスされる所定の項目を有するセクションと
ｂ）前記検索引数の選択されたセグメントであるインデックス値から導出されるオフセット値に応答してアクセスされる項目を含むもう１つのセクションと
を含む、請求項１４に記載の保管されたデータ構造。
【請求項１９】
・前記基本項目の少なくとも１つが、前記検索引数の選択されたセグメントと比較されるテスト値（ＴＶ）を追加的に含む
請求項１４に記載の保管されたデータ構造。
【請求項２０】
・前記基本項目の少なくとも１つが、使用される次のノード・テーブルに関するテーブル・ベース・ポインタ（ＰＴＲ）のほかに、前記テーブル・ベース・ポインタによって識別される前記次のノード・テーブルの所定の位置に含まれるテスト値（ＴＶ）が使用されなければならないことの表示を含む
請求項１４に記載の保管されたデータ構造。
【請求項２１】
・基本項目が、テスト引数としての前記検索引数からの第１セグメントの最初の選択の後に、前に選択された検索引数セグメントのすべてまたは一部と少なくとも部分的に同一であるもう１つのセグメントが、前記検索引数から選択されなければならないことを示す再利用フラグ（Ｒ）を含む
請求項１４に記載の保管されたデータ構造。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、特に、スイッチング・ノードにおいて、ＩＰアドレスなどの所与の検索引数に応答して出力または転送経路を決定するための最長一致プレフィックス・ルックアップに関する。
【０００２】
【従来の技術】
現代の通信ネットワーク、特にインターネットで、多くのユーザが、アドレス付きのメッセージ（またはパケット）を交換するためにネットワークに接続する。ネットワークの伝送リンクは、受信したメッセージ（パケット）のアドレスに応答してこのメッセージを出力リンクの選択された１つに転送する交換局または経路指定ノード（転送ノード）によって相互接続される。したがって、これらは、アドレスを評価することによって各パケットを経路指定しなければならない。これは、ＯＳＩ、ＡＴＭ、および他の通信ネットワークでのメッセージ伝送についてもそうである。
【０００３】
現在のネットワークの問題は、（ａ）システム内の異なるユーザまたはアドレスの数の多さと、（ｂ）伝送しなければならないメッセージ（パケット）の数の巨大さである。インターネットの転送ノード（経路指定センタ）は、毎秒約１００万メッセージをディスパッチしなければならない場合がある。
【０００４】
もう１つの課題は、異なるサイズを有する、アドレスの「ドメイン」の提供である。使用されるアドレスのそれぞれが、固定された全長（たとえば３２ビット）を有することができ、共通の「プレフィックス」を有するアドレスのグループ全体、たとえばプレフィックス「４．２２／１６」を有するすべてのアドレスが、同一のドメインに割り当てられ、したがって、同一の経路指定を必要とする。１つの問題は、多数のシステム（たとえばインターネット）での経路指定のための評価中に検討されるこれらのドメイン、したがってプレフィックスが、異なるサイズを有することである。もう１つの問題は、例外の存在すなわち、主ドメインのサブドメインのアドレスが、それぞれの主ドメインのアドレスの大多数と異なる経路指定を必要とする場合があることである。これは、これらの特定のアドレスを経路指定中に「フィルタ・アウト」することを必要とする。たとえば、グループ４．２２．ｘｘｘ．ｘｘｘ（４．２２／１６）のアドレスを有するユーザの大半が、同一の地域に配置される場合に、サブドメインのアドレス４．２２．４８．ｘｘｘ、…、４．２２．５５．ｘｘｘ（４．２２．４８／２０）と、もう１つのさらに小さいサブドメインのアドレス４．２２．１７．１９２、…、４．２２．１７．２５５（４．２２．１７．１９２／２６）が、それぞれの宛先（ユーザ）が別の領域に配置されているので、他のリンクを介する経路指定を必要とする場合がある。
【０００５】
これは、各転送ノード（経路指定センタ）でのアドレスのそれぞれの評価を必要とする最長一致プレフィックス（または最善一致プレフィックス）経路指定の技法につながる。
【０００６】
最長一致プレフィックス経路指定を実現するために複数の技法が開発された。ほとんどは、階層木様構造の使用に基づく。そのような木で、採用される出力リンクまたは経路に関する情報（たとえば次ホップ・ポインタ）が、木の葉（出口点／端点）に保管され、木を通るパスが、評価されるアドレスによって決定される。正しいパスを見つけるため、すなわち、分岐（木の各ノードでの）を決定するために、各アドレス（またはその一部）が、（ａ）各ノードでそこに保管されたアドレス情報と比較される、または（ｂ）分岐の制御すなわち、採用される次の部分的パスの選択に、直接に（または間接的に）使用されるのいずれかになる。
【０００７】
どの場合でも、どの技法が使用されるかに無関係に、下記を達成しなければならない。
（１）アドレス評価および経路決定は、各メッセージ（パケット）のワースト・ケース（すなわち高トラフィック情況）で使用可能な平均時間に対応する時間間隔内に行わなければならない。
（２）各アドレス評価に必要な記憶域アクセスまたは処理演算は、できる限り少なくしなければならない。
（３）テーブル（データ・ベース）に必要なストレージ・スペースは、できる限り少なくしなければならない。
ある解決策を、（２）と（３）の間の妥協にすることができるが、第１の判断基準は、過度の遅延または経路指定ノードの滞りを防ぐために、どの場合でも満足されなければならない。
【０００８】
そのような経路指定システムを設計するためのもう１つの態様が、柔軟性すなわち、システム内の変化するドメイン・サイズおよびアドレス分布に構造を適応させる能力である。
【０００９】
既知の手法
所与の検索引数の最長一致プレフィックスを見つけ、対応する（割り当てられた）ポインタを作るか識別を出力する、複数の方法およびシステムが提案された。
【００１０】
スリニバサン（V. Srinivasan）およびバーギース（G.Varghese）共著の論文、「Faster IP Lookups using Controlled Prefix Expansion」（Perform.Eval.Rev. (USA) Vol.26, No.1, June 1998 pp.1-10に記載）に、選択された数の異なるプレフィックス長だけが許容され、アドレスの所与のプレフィックスが、選択された長さの１つを有しない場合に長さを拡張される方法が記載されている。検索データベースは、複数のレベルのテーブルを有し、各レベルが、プレフィックス長の１つに対応するように設計される。その場合、各レベルで、所与の検索アドレスの部分だけを使用して、増分検索を行うことができる。各レベルのテーブル項目に、検索アドレスの次の部分を用いて検索される次のテーブルへのポインタが含まれる。この手法を用いると、必要なストレージ・スペースおよび必要な動作の数を減らすことができる。しかし、検索アドレスのセグメントをテスト値と直接に比較して、特定のプレフィックスが存在する時の即時判定を可能にすることはできない。さらに、この提案された方法は、すべてのプレフィックスを所与の長さで直接に使用するのではなく、プレフィックスの拡張を必要とする。事前に選択された長さに基づく所与の構造に起因して、選択された長さの変更は、データベースの構造全体の適合を必要とする。また、異なるサイズの検索アドレス・セグメントを異なるレベルで使用することができるが、１レベルあたり１つのセグメント長だけが可能である。
【００１１】
米国特許第５７８１７７２号明細書で、ポインタ圧縮（すなわちＮＩＬノードへのポインタの除去）とパス圧縮（追加の関連する情報に寄与しないノードの除去と、所与のアドレスのそれぞれの部分と比較されるパス桁文字列としての関連するプレフィックス桁の保管）による、検索の長さおよびストレージ要件を減らす技法が記載されている。しかし、この方法は、固定長セグメント（またはその整数倍）への検索アドレスの分割だけを提供し、ノード項目のインデックス付きポインタアドレス指定と、保管された値に対する選択可能な長さのアドレス部分の比較との組合せを提供しないと思われる。
【００１２】
ハルバウム（T. Harbaum）、マイヤ（D. Meier）、ジッターバート（M. Zitterbart）、およびブローケルマン（D. Brokelmann）共著の論文、「Hardware-Assist for IPv6 Routing Table Lookup」（Proc. Internat. Symposium on Broadband Networks (SYBEN'98), Zurich/Switzerland May 1998に記載）に、ＩＰアドレスの異なる長さのプレフィックスに関する最善一致を見つける２進木検索方法が記載されている。この方法を用いると、短縮された検索データ・ベースを可能にするための、保管された値に対するアドレス・プレフィックスの可変長部分の比較が可能になる。しかし、２進検索決定だけが提供され、したがって、多くの場合に、同一の出力経路について複数の比較および決定が必要になる。
【００１３】
一致検索で異なるプレフィックス長を扱うもう１つの手法が、グプタ（P. Gupta）、リン（S. Lin）、およびマッケオウン（N. McKeown）共著の論文、「Routing Lookups in Hardware at Memory Access Speeds」（Proc. IEEE INFOCOM'98, 1998, Vol.3 pp.240-247に記載）に記載されている。開示された方法は、３２ビット・アドレスの場合に２つのテーブルを提供する。１つは、最初の２４ビットによってアドレス指定され、２４ビット・プレフィックスごとに１つの２24個の項目を有する。関連するプレフィックスが、２４ビット未満または多くとも２４ビットである場合に、それぞれの項目に、関連する出力またはリンクへのポインタが含まれる。関連するプレフィックスがそれより長い場合には、項目に、第２のテーブルへのポインタが含まれ、この第２のテーブルは、そのポインタと、プレフィックスの残りの８ビット（３２ビットへの拡張の後の）を組み合わせることによってアドレス指定される。第２のテーブルの項目には、より長いプレフィックスの出力／リンクへのポインタが含まれる。追加の中間テーブルを用いて、特定の情況（３２ビットより短いプレフィックスの場合）に第２のテーブルのサイズを減らすことができる。この方法は、アドレス突合せごとに１回、２回、または３回の記憶域アクセスだけを必要とするが、より大きい記憶容量を必要とし、プレフィックスの追加または削除が、多数の項目の変更を必要とする。
【００１４】
米国特許第５３８６４１３号明細書によって、所与のアドレスの異なるプレフィックス・セグメントに関する高速同時ルックアップが可能になるが、連想記憶装置が必要である。
【００１５】
これらの開示された方法およびシステムのどれもが、変化する異なるアクセス判断基準を有する項目を有する複数テーブル構造での最長一致プレフィックス発見のための、柔軟な組合せで部分的にテスト値として、部分的にアドレス指定・インデックスとして選択可能な長さの検索引数セグメントの使用を可能にしない。
【００１６】
【発明が解決しようとする課題】
【課題を解決するための手段】
本発明の目的は、保管されたテーブルの複数レベル配置で、所与の入力アドレスまたは検索引数に関する最長一致プレフィックスを見つける方法およびデータ構造設計であって、１検索あたりごく少数のルックアップ動作を必要とし、適度なストレージ要件を有し、システム内で使用されるプレフィックスの分配に対する保管されたデータ構造の柔軟な適合を可能にする、方法およびデータ構造設計を提供することである。
【００１７】
この目的を達成する発明は、請求項で定義される。この発明を用いると、具体的には、テスト値またはアドレス指定・インデックスのいずれかとしての所与の検索引数の可変長セグメントの使用が可能になり、また、最長一致プレフィックスおよびそれに割り当てられた出力表示の検出のルックアップ手順中に、テストとその後の、そのような可変長セグメントを用いるインデックス付きアクセスとの組合せが可能になる。
【００１８】
本発明を用いると、使用されるノード・テーブル・データ構造および最長一致プレフィックスに関する検索手順を、全アドレス空間に対するプレフィックスの実際の分布に最適に適合させることすなわち、まばらな分布またはクラスタ化された分布のどちらが存在するかという事実に依存して異なる構造を使用することが可能になる。
【００１９】
特定のプレフィックスのアクセスの頻度に応じて、最も頻繁に使用されるプレフィックスの検索パスを、それらに検索を短縮する扱いを与えることによって最適化することができ、それに対して、ほとんど使用されないプレフィックスについて、多少長い検索を許容して、他の長所、たとえばストレージ・スペースの節約を得ることができる。本発明は、保管されたテスト値に対する長いアドレス・セグメントの可能な直接比較に起因して、特定のプレフィックスに関する検索の高速完了を可能にする。さらに、本発明を使用する時には、単一のルックアップ動作で複数（３つ以上）の選択肢の間での選択が可能になる。
【００２０】
本発明は、項目の２段アドレス指定も提供する、すなわち、ノード・テーブルが、テーブル・ベース・ポインタによって選択され、テーブル内の項目選択を、テスト結果またはインデックス動作に応答するオフセットによって行うことができ、その結果、項目間の高速で柔軟な移動が可能になる。
【００２１】
本発明は、データ構造を簡略化し、項目へのアクセスならびに更新を簡略化する、ノード・テーブル内の一定サイズの項目の使用も可能にする。
【００２２】
最後に、本発明を使用するシステムに再利用機能を設けることによって、まず検索引数の長いセグメントに対するテストを行い、次に、その結果に応じて、より小さいステップで後続の微細な評価を行う可能性が提供される。
【００２３】
本発明の実施形態の例を、図面を参照して以下で説明する。
【００２４】
【発明の実施の形態】
以下では、本発明の実施形態の３つの例（１つは基本的、２つは変形形態）を説明する。最後のセクションで、最適化されたデータ構造の例を与え、検索引数のプレフィックスの所与の組についてそのようなデータ構造を生成し最適化する方法を示す。
【００２５】
可変長の検索引数の選択可能部分が、ノード・テーブル項目の選択／アクセスのためのインデックス（値）または保管されたテスト値と比較されるテスト引数のいずれかとして使用されるが、発生するプレフィックスの既存のまたは期待される分布に検索手順を適合させるために、両方の可能性が組み合わせて使用されることに留意することが重要である。これによって、処理速度、動作の数、または検索（ルックアップ）データ・ベースのストレージ要件のいずれかに関する最適化が可能になる。さらに、検索データ・ベース内の項目のアクセスのために、フルアドレス指定が必要ではない。そうではなく、テーブル・ベース・ポインタが、それぞれのノード・テーブルの選択に使用され、テーブル内のアクセスは、オフセット値（テーブルのベース・アドレスからの）またはテストの結果を使用して行うことができる。
【００２６】
以下の用語および略語を、後続の説明で使用する。
・検索引数：ＩＰアドレスまたはパケット・アドレスまたはキーワードなど。
・ノード・テーブル：それぞれに検索情報または出力経路情報が含まれる項目のテーブル（ノード・テーブルは、複数の連続するレベルに配置される）。
・インデックス：ノード・テーブル項目にアクセスする時に、ベース・アドレスからのオフセットを決定するのに使用される値。
・オフセット値：ノード・テーブルの開始アドレスとアクセスされる項目の位置との間の距離を示す値。
・テーブル・ベース・ポインタ：ノード・テーブルの先頭（アドレス）を示すポインタ＝ＰＴＲ。
・終了インジケータ：検査パスの最終項目の表示＝ＥＮＤ；出力インジケータまたは出力につながらない停止インジケータ（空の項目＝ＮＩＬにすることができる）のいずれか。
・出力インジケータ：選択された出力経路へのポインタ（たとえば次ホップ・ポインタ＝ＮＨＰ）。・テスト値：テーブル項目に保管される、検索引数の一部と比較されるビット・シーケンス＝ＴＶ。
・テスト結果：テスト値とテスト引数（検索引数の選択された部分）の間の比較の結果：これは２進値（一致／不一致、または１／０）である。
【００２７】
実施形態の第１の（基本的な）例
本発明による検索（ルックアップ）データ構造の基本的な実施形態を、概略的に図１に示す。この説明は、図２の流れ図によってサポートされる。選択されたノード・テーブル（この例で使用されるものだけ）が、それぞれのマークされたＩＰアドレス（＝検索引数）と共に、異なるレベルで示されている。
【００２８】
第１の例では、以下の４つの異なる（種類の）項目が、ノード・テーブルに現れる。
0003663355.tif 000002
【００２９】
基本項目では、Ｆ１＋Ｆ２が、実行される動作（テスト値との比較／テーブル項目の単一のインデックス付きアクセス／両方の組合せ）を示し；ＣＮＴまたはＣＮＴ１およびＣＮＴ２が、要求された動作について検索引数から取られるビット数（テスト引数またはインデックスとして）を示す選択情報であり；ＰＴＲが、テスト値が含まれるか次の項目（１つまたは複数）がアクセスされるノード・テーブルの開始位置を示すテーブル・ベース・ポインタである。
【００３０】
追加項目には：出力インジケータ（次ホップ・ポインタＮＨＰ）または検索を終了する（使用可能な出力経路がない）ことを示す停止インジケータ（ＮＩＬ）を伴う、フラグＦ１およびＦ２（最終項目を示す）；または、単一のテスト値（ＴＶ）のいずれかが含まれる。
【００３１】
この例および他の例で使用されるフラグ組合せは、下記の意味を有する。
【表１】
0003663355.tif 000003
【００３２】
この例（および他の２つの例）で使用されるプレフィックスおよび関連する次ホップ情報の組は、次の通りである。
【表２】
0003663355.tif 000004
【００３３】
この例で説明する基本的な方法は、次の特徴を有する。
・テスト値が、次レベルのノード・テーブルの先頭に保管される。
・各テストが、「一致」または「一致なし」という２進結果を有する。
・再利用フラグなし；ＩＰアドレスの各部分が、多くとも１回だけ使用される。
基本的な実施形態の手順は、次の通りである。
【００３４】
ステップ１：
ＩＰアドレス（検索引数）の最初の１６ビットが、初期セグメントとして選択され、２16＝６５５３６項目からなるレベル１のテーブルへのインデックスとして使用される。インデックス１０４６の項目が選択されるのは、ＩＰアドレスが４．２２／１６から始まる（それに等しいプレフィックスを有する）時である。
【００３５】
ステップ２：
このインデックス１０４６の項目は、フラグ組合せ「１１」を有し、これは、まずテスト、その後、条件によって、インデックスアドレス指定動作を行わなければならないことを意味する。選択された項目に基づいて、ＩＰアドレス内の８つの連続するビット（＝ＣＮＴ１）からなるセグメントが選択され、テスト値１７に対してテストされる。このテスト値は、次のレベル２のノード・テーブルの最初の（最も下の）項目で見つかるが、このノード・テーブルは、項目１０４６のテーブル・ベース・ポインタによって識別される。
【００３６】
テストが「一致なし」をもたらす場合には、レベル２のテーブルで「一致なし」項目が選択される。この項目は、所与のプレフィックスについて結果（出力）が指定されないことを意味する停止インジケータ「−」を含む最終項目である。
【００３７】
テストが、「一致」をもたらす場合には、ＩＰアドレス内の２つの連続するビット（＝ＣＮＴ２）からなるセグメントが、選択され、レベル２の選択されたテーブルの「一致」部分へのインデックスとして使用される。この部分は、テスト値および一致なし結果の２つの「固定された」項目の上から始まり、これには、インデックスから導出されるオフセット値を使用してアクセスされる４つの項目が含まれる（図では、インデックス値０ないし３が示されており；これらは、オフセット値２ないし５をもたらし、項目０にテスト値が含まれるそれぞれのノード・テーブルの項目２ないし５が、テーブル・ベース・ポインタによって識別されることを意味する）。
【００３８】
・プレフィックスＢ（インデックス・ビット００）を有するＩＰアドレスは、次ホップ・ポインタ「２」を含む最終項目（フラグ＝００）であるインデックス０の項目の選択をもたらす。
・プレフィックスＣ（インデックス・ビット０１）を有するＩＰアドレスは、次ホップ・ポインタ「３」を含む、やはり最終項目（フラグ＝００）であるインデック１の項目の選択をもたらす。
・プレフィックスＤに等しい最初の２６ビット（現在はインデックス・ビット１１が使用される）を有するＩＰアドレスは、下のステップ３で説明する、追加テストを必要とする（フラグ＝１０）インデックス３を有する項目の選択をもたらす。
・前のテストで「一致」結果をもたらす他のすべてのＩＰアドレス（これらは、インデックス・ビット１０を有する、残りの一致するアドレスである）は、プレフィックスＡを有し、次ホップ・ポインタ「１」を含む最終項目（フラグ＝００）である、レベル２のノード・テーブルの一致部分のインデックス２の項目の選択をもたらす。
【００３９】
ステップ３
レベル２のテーブルの一致部分のインデックス３にある項目に基づいて、ＩＰアドレス内の６つの連続するビット（ＣＮＴ＝６）からなるセグメントが、選択され、テスト値５１（レベル３のテーブルの最も下の項目にある。このレベル３のテーブルは、レベル２の最後に使用されたノード・テーブルのそれぞれの項目にあるテーブル・ベース・ポインタによって識別される）に対してテストされる。
【００４０】
・プレフィックスＤを有する（それぞれのアドレス位置にビット・シーケンス１１００１１＝５１を有する）ＩＰアドレスの場合、テストが、レベル３の選択されたノード・テーブル内の「一致」項目につながる「一致」をもたらす。この「一致」項目は、次ホップ・ポインタ「４」を含む最終項目（フラグ＝００）である。
・プレフィックスＤを有しないＩＰアドレスの場合、値５１に対するテストが、「一致なし」条件をもたらし、したがって、レベル３の選択されたノード・テーブルの「一致なし」項目の選択をもたらす。この項目も、次ホップ・ポインタ「１」を含む最終項目（フラグ＝００）である。これらのアドレスは、プレフィックスＡを有する（プレフィックスＡを有するすべての残りのアドレスすなわち、ステップ２で既に処理されたもの以外のアドレス）。
【００４１】
図２の流れ図に、各基本項目に含まれるフラグ（最初の位置のビット対）に応答して項目がどのように処理されるかを示す。この方式は、上の説明に対応する。
【００４２】
第２の実施形態の例
第２の実施形態の例を、図３に示す。これは、第１の例に非常に類似しているが、使用されるテスト値が、別々の項目（次レベルのノード・テーブルの）に保存されるのではなく、テストが行われることを必要とするそれぞれの項目に直接に含まれることが異なる。したがって、ノード・テーブル項目は、下の変更された組に示された追加フィールドを有しなければならない。
0003663355.tif 000005
【００４３】
テスト値が通常は短い（数ビットのみ）時には、この変更が有用であるが、検索データ・ベースに多数の長いテスト値が含まれる時には、第１の例の解決策のほうがよいことは明白である。この第２の解決策では、別々のテスト値項目のためのストレージ・スペースが節約され、さらに、テスト値を取り出すための追加のアクセス動作が回避される。
【００４４】
図３に基づいて、第１の例について与えた説明から、第２の例についてこれ以上の詳細な説明は不要であると思われる。
【００４５】
第３の実施形態の例
もう１つの、第３の実施形態の例を、図４に示す。これも、多少第１の例に似ている。プレフィックスの同一の組ＡないしＤも使用されている。しかし、第１（および第２）の例と異なって、この例では、検索引数（ＩＰアドレス）のうちで、前のステップで既に評価された部分（ビット・グループ）の再利用が提供される。第１（および第２）の例では、必ず、検索引数からのビットの後続の（新しい）グループが、テスト動作に使用されるか、ノード・テーブル項目のアクセスでインデックスとして使用された。
【００４６】
ＩＰアドレス（検索引数）からの選択された部分（ビット・グループ）の再利用は、次の情況で有用になる可能性がある。アプリケーションで発生するプレフィックスの組に、１つまたは少数の非常に特有の（長い）プレフィックスが含まれる時に、この特有のプレフィックスの長いセグメントの、それぞれのテスト値に対するテストをまず行って、一致が検出される場合に即座に結果を得ることができる。そうでない場合（結果が、この特有のプレフィックスが存在しないことを示す「一致なし」の場合）に、既に使用した長いプレフィックス・セグメントの一部を、別の動作に使用して、複数の後続の動作で他のより類似するプレフィックスを互いに区別する。これによって、そのような特有の分離されたプレフィックスが発生するシステムで、より高速の検索（ＩＰアドレス評価）動作がもたらされる。
【００４７】
この例で使用されるノード・テーブル項目の組は、例１のそれに類似するが、基本項目に追加の「再利用」フラグが含まれることが異なる。
0003663355.tif 000006
【００４８】
図４による、この第３の例の手順は、次の通りである（プレフィックスの組ＡないしＤは、第１の例と同一であるが、ノード・テーブルに保管されたデータ構造は、もちろん異なる）。
【００４９】
基本項目のＲ（再利用）フラグは、ＩＰアドレスのあるセグメントが、初めて使用され、再利用されなければならない（テスト結果に依存するある条件の下で）時にセットされる。
【００５０】
ステップ１：（例１の基本的な方法と同一）
ＩＰアドレス（検索引数）の最初の１６ビットが、初期セグメントとして選択され、２16＝６５５３６アドレスからなるレベル１のテーブルへのインデックスとして使用される。インデックス１０４６の項目が選択されるのは、ＩＰアドレスが４．２２／１６から始まる（それに等しいプレフィックスを有する）時である。
【００５１】
ステップ２：
レベル１のテーブルのインデックス１０４６にある選択された項目に基づいて、ＩＰアドレス内の１６個の連続するビット（ＣＮＴ）からなるセグメントが、選択され、テスト値１７．２４３（ビット・シーケンス０００１  ０００１  １１１１  ００１１）に対してテストされる。再利用フラグ（Ｒ）がセットされるが、これは、選択されたセグメントの少なくとも一部を、もう一度使用できることを意味する。テスト値は、レベル２のノード・テーブルの最も下の位置で見つかり、この位置は、項目１０４６のテーブル・ベース・ポインタによって識別される。
【００５２】
テストが「一致」をもたらす場合、レベル２の選択されたノード・テーブルで「一致」項目がアクセスされる。これは、次ホップ・ポインタ「４」を含む最終項目（フラグ＝００）である。プレフィックスＤを有するＩＰアドレスの場合にこうなる。
【００５３】
テストが「一致なし」をもたらす場合には、レベル２の選択されたノード・テーブルで「一致なし」項目がアクセスされる。この項目では、下のステップ３で説明するテスト／インデックス動作の組合せ（フラグ＝１１）が指定され、この組合せは、４．２２（ビット・シーケンス００００  ０１００  ０００１  ０１１０）から始まるが、プレフィックスＤを有しないすべてのＩＰアドレスについて選択される。
【００５４】
ステップ３：
レベル２のノード・テーブルの「一致なし」項目（まずＣＮＴ１＝８に基づくテスト動作を指定する）に基づいて、８つの連続するビットの新しいセグメントが、ＩＰアドレスの、前の動作で使用された１６ビットのセグメントから選択される。この再利用は、レベル１の項目１０４６でＲフラグに１がセットされていることによって判定されたものである。レベル２の「一致なし」項目の再利用フラグＲには、０がセットされている。というのは、ここで選択された８ビットのセグメントが、二度と再利用されないからである。
【００５５】
テストが「一致なし」をもたらす場合には、最後にアクセスされた項目のテーブル・ベース・ポインタによって指定されるレベル３のノード・テーブルで、「一致なし」項目が選択される。新たに選択される項目は、停止インジケータ「−」を含む最終項目（フラグ＝００）である（出力経路が、４．２２．１７以外のプレフィックスを有するＩＰアドレスについて指定されず、検索が終了したことを意味する）。
【００５６】
テストが、「一致」をもたらす場合には、レベル２のテーブルの「一致なし」項目で指定されたインデックス付け動作が、ＣＮＴ２＝２を使用して行われる。したがって、２つの連続するビットのセグメント（テスト動作のために前のステップで選択された８つのアドレス・ビットに続く）が、ＩＰアドレスから選択され、レベル３の選択されたノード・テーブルの「一致」部分の項目にアクセスするためのインデックスとして使用される。この部分は、４つの項目を有し、そのうちの１つが、最近選択された２つのインデックス・ビットから演繹されたオフセットによって識別される。
【００５７】
・プレフィックスＢ（インデックス・ビット００）から始まるＩＰアドレスは、インデックス０に関連する、レベル３のテーブルの「一致」部分の項目の選択をもたらす。これは、次ホップ・ポインタ「２」を含む、最終項目である。
・プレフィックスＣ（インデックス・ビット０１）から始まるＩＰアドレスは、インデックス１に関連する、レベル３のテーブルの「一致」部分の項目の選択をもたらす。これも、次ホップ・ポインタ「３」を含む、最終項目である。
・Ｂ、Ｃ、およびＤ以外のプレフィックスを有する（シーケンス４．２２．１７から始まる）ＩＰアドレスは、この段階ではインデックス・ビット１０または１１を有しなければならず、したがって、レベル３のテーブルの「一致」項目の２つの残りの項目の１つすなわちインデックス２または３に関連する項目の選択をもたらす。これらの両方に、プレフィックスＡに対応する次ホップ・ポインタ「１」が含まれる。
【００５８】
結論：例１の基本的な解決策を例３の変形形態と比較すると、これらの両方が、同一の結果すなわち、プレフィックスＡ、Ｂ、Ｃ、またはＤを有するＩＰアドレスが、それぞれ次ホップ・ポインタ１、２、３、または４に対応する出力経路に正しく向けられることがわかる。他のすべてのＩＰアドレスが、検索の終了をもたらす。しかし、基本的な解決策（例１）は、プレフィックスＢまたはＣを有するアドレスが、より頻繁に発生する情況でより有利になる可能性がある。というのは、これらのプレフィックスについて、ルックアップがより高速になるからである。対照的に、例３の変形形態は、プレフィックスＤに関するルックアップ時間が短いので、プレフィックスＤを有するアドレスがより頻繁に発生する情況でより効率的である。
【００５９】
項目選択に関する注釈：最初に述べ、３つの例で示したたように、テーブル・ベース・ポインタによって識別されたノード・テーブル内の項目の選択を、異なる形で行うことができる：
テストが行われた（保管されたテスト値に対して）時に、２進結果「一致」または「一致なし」がある。ここで、２つの可能性がある：
ａ）２つの結果のそれぞれが、必ずその結果に関連する、ノード・テーブル内の１特定の項目の選択を引き起こす（図４のレベル１からレベル２への遷移を参照されたい）。
ｂ）２つの結果の１つ（「一致なし」）が、必ずのその結果に関連する、ノード・テーブル内の１特定の項目の選択を引き起こす。２つの結果のもう一方（「一致」）が、インデックス値の追加選択を引き起こし、そのインデックス値が、それぞれのノード・テーブルの特殊な部分（「一致」）の２つ（もしくは４つまたは８つ）の項目の１つの選択に使用される（図４のレベル２からレベル３への遷移を参照されたい）。
もちろん、インデックス値を使用する、項目（テスト動作の結果に固定的に関連する項目を含まないテーブルの）の直接アドレス指定も可能である。これは、たとえば、図１および図４のレベル１での最初のステップの場合である。
【００６０】
これらの異なる項目選択の可能性によって、プレフィックスの期待される分布に対する、検索手順および毛割くデータ・ベースの非常に柔軟な適合が可能になる。
【００６１】
プレフィックス・ルックアップ用の最適化されたデータ構造の生成
上で説明した３つの例では、最長一致プレフィックス用の発明されたルックアップ手順によって提供される、異なるデータ構造要素と基本動作および組み合わされた動作を提示し、説明した。上で述べたように、これらによって、動作速度またはストレージ要件およびプロセッサ要件に関するルックアップ処理の最適化が可能になる。検索データ・ベースおよびノード・テーブル項目は、発生するプレフィックスの期待される分布に最もよくあてはまるように構成され、配置されなければならない。
【００６２】
そのような最適化の例を、図５ないし８と、図９および図１０に示し、下で説明する。
【００６３】
使用される項目のタイプおよびフィールドの指定は、この詳細な説明の最初に提示した第１の例と同一である。
【００６４】
現在の最適化の例について仮定されるプレフィックスの組を、下に示す。これは、もちろん、実際に発生する者よりはるかに小さい、異なるプレフィックスの縮小された組である。しかし、これは、原理の説明に十分である。
【表３】
0003663355.tif 000007
【００６５】
図５および図６に、このプレフィックスの組のための、複数レベル・ノード・テーブル配置の第１のデータ構造を示す。このデータ構造は、次の形で作成される。プレフィックスが、共通の最上位部分（先行プレフィックス）を共有する場合に、この部分が、最初のテスト動作のテスト値として選択され、保管される。その後、次のビットすなわち、異なる最初のビットが、２つの別々の検索パスの間で選択するためのインデックスとして使用されるものとして決定される。同一の形で、所与の検索パスに沿って、その検索パスのプレフィックスの残りの部分の共通の最上位部分が、テスト動作のテスト値として選択され、保管される。その後、次のビットすなわち、この検索パスのプレフィックスの残りの部分で異なる最初のビットが、２つの連続するパスの間で選択するためのインデックスとして使用されるものとして決定され、以下同様である。別の長いプレフィックスの一部である（したがって、異なるビットを有するのではなく短いだけである）プレフィックスの場合、インデックスは使用されず、テスト値に、他のプレフィックスの一部である、より短いプレフィックスの末尾までのビットが含まれる。
【００６６】
この処理中のテスト値およびインデックスの選択および結果の分岐方式を、図９に示す。この図では、長方形の箱が、アドレス・セグメントと箱の中に示されたビット・シーケンス（テスト値）の間のテスト動作を示す。これらのテスト値は、それぞれのノード・テーブル項目に保管される。二重の円は、インデックス付け動作を示し、「ｂ」の数は、インデックス付けに使用されるアドレスの連続するビット数を表し、その実際の値は、そこから出る線の横に示されている。テスト動作またはインデックス動作の出力が、プレフィックスの出力インジケータ（次ホップ・ポインタ）に達する時に、これが、その出力の円で囲まれたプレフィックス文字によって表される。
【００６７】
手順の詳細：プレフィックスＡは、プレフィックスＢ、Ｃ、およびＤに共通する。したがって、データ構造（図５および図６）は、プレフィックスＡの末尾まで（’００００  １００１  ０００１  ０１ｂ’）をカバーするテスト動作から始まる。プレフィックスＢ、Ｃ、およびＤの残りの部分は、共通部分’００  １００ｂ’を共有する。これが、レベルのテーブルに保管されるテスト値になる。否定のテスト結果の場合には、プレフィックスＡが、それぞれの検索引数の最長一致プレフィックスであり、対応する次ホップ・ポインタ「１」が、レベル２のテーブルの「一致なし」項目に保管される。
【００６８】
その後、１ビット・インデックスを使用して、２つの別々のパスの間で選択する。プレフィックスＣだけが、インデックス値「０」を有する検索パスに沿って「進む」。プレフィックスＣの残りのビットは、レベル３の下のテーブルにテスト値として含まれる。肯定のテスト結果は、プレフィックスＣが最長一致プレフィックスであることを意味し、したがって、プレフィックスＣに対応する次ホップ・ポインタ「３」が、「一致」項目に保管される。否定のテスト結果は、プレフィックスＡが、それぞれのすべての検索引数に関する最長一致プレフィックスであることを意味し、したがって、プレフィックスＡに対応する次ホップ・ポインタ「１」が、「一致なし」項目に保管される。同一の手法が、他の、プレフィックスＢおよびＤに関する検索パスに沿って使用される。
【００６９】
上の規則に従って生成された、図５および図６に示されたデータ構造を、特定のプレフィックスに関する検索パスに沿って使用されるインデックスのサイズを増やし、連続する検索パスの残りの部分を適応させる（たとえば、連続するテスト動作のテスト値から、現在はインデックスの一部になっているビットを除去することによって）ことによって、さらに最適化して、あるプレフィックスのルックアップ速度を改善することができる。図７および図８に、プレフィックスＢおよびＤについて、インデックスのサイズ（ビット数）を１から３に増やす（図８のレベル２のテーブル内のインデックス「１」の「一致」項目のＣＮＴ２フィールドに３の値が与えられる）ことによって、ルックアップ速度が改善されている、最適化されたデータ構造を示す。
【００７０】
図１０に、図７および図８に示された最適化された検索データ構造の生成中のテスト値およびインデックスの選択と、結果の分岐方式を示す。図９と図１０の比較から、検索木の特定の場所で、検索速度を高めるためにテーブル記憶域内の項目数の増加と引き換えに必要な動作の数を減らすことによって、またはその逆によって、設計をどのように変更することができるかが示される。
【図面の簡単な説明】
【図１】  本発明の第１の一般的な実施形態の例を示す図である。
【図２】  検索引数の評価での異なる可能なステップを示す、図１の実施形態の流れ図である。
【図３】  テスト値が別々に保管されず、それぞれのテーブル項目内に保管される、本発明の実施形態の第２の例を示す図である。
【図４】  検索引数（ＩＰアドレス）のうちの既に評価された部分をもう一度再利用できる、実施形態の第３の例を示す図である。
【図５】  異なるプレフィックス値の所与の組に適合されたノード・テーブル構造の生成を示す図である。
【図６】  異なるプレフィックス値の所与の組に適合されたノード・テーブル構造の生成を示す図である。
【図７】  図５および図６に示された事例に基づく、最適化されたノード・テーブル構造の生成を示す図である。
【図８】  図５および図６に示された事例に基づく、最適化されたノード・テーブル構造の生成を示す図である。
【図９】  図５および図６のテーブル構造生成手順の、テスト値およびインデックスの選択と結果の分岐方式を示す図である。
【図１０】  図７および図８のテーブル構造生成手順の、テスト値およびインデックスの選択と結果の分岐方式を示す図である。
【図１】
0003663355.tif 000008
【図２】
0003663355.tif 000009
【図３】
0003663355.tif 000010
【図４】
0003663355.tif 000011
【図５】
0003663355.tif 000012
【図６】
0003663355.tif 000013
【図７】
0003663355.tif 000014
【図８】
0003663355.tif 000015
【図９】
0003663355.tif 000016
【図１０】
0003663355.tif 000017