(57)【特許請求の範囲】
【請求項１】
それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能なＣＡＭメモリから構成されるマスク付検索メモリに格納しておき、検索条件に合致し、かつ更なる検索の開始点をピンポイントするために使用される、前記グループへの対応情報をコンテンツデータとして前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞るステップと；
先頭ビットから順にビット値が「０」及び「１」のいずれかを採り得る点をノードとしてツリーの状態に検索対象となる前記エントリを分類しておき、前記エントリを対象グループ内データに絞った後の合致エントリの検索を行うステップと；
すべての検索対象の前記エントリについて前記ツリーを構成し、このツリー内の末端のリーフのうち最も先端のルートから遠いものから一定ホップ数上流にさかのぼった中間のノード位置を検索グループを代表する仮想エントリに選び、この選択された仮想エントリのノード位置以降の枝を除外して再度この手順を繰り返し、前記エントリのすべてを網羅するまで選択された前記仮想エントリを前記対応情報として前記マスク付検索メモリに格納しておき、検索の際に条件に合致する前記仮想エントリを前記マスク付検索メモリで判定し、以降の検索を前記ツリーにより行うステップと；
を備えることを特徴とする高速検索方法。
【請求項２】
それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能なＣＡＭメモリから構成されるマスク付検索メモリに格納しておき、検索条件に合致し、かつ更なる検索の開始点をピンポイントするために使用される、前記グループへの対応情報をコンテンツデータとして前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞るステップと；
前記対象グループ内の検索を行うとき、そのグループ内で検索対象の前記エントリの検索キーの値で最初にビット列が異なるビット位置から最大データ長までの範囲をテーブル検索オフセットとしてテーブルを引くステップと；
検索グループを代表する仮想エントリを前記対応情報として決定するとき、先頭ビットから順にビット値が「０」及び「１」のいずれかを採り得る点をノードとするツリーの状態に検索対象の前記エントリを分類しておき、分岐するビット位置が偏在する枝を前記グループとし、条件に合致するグループまでの検索を前記マスク付検索メモリで行い、以降の検索を前記テーブルの参照で行うステップと；
を備えることを特徴とする高速検索方法。
【請求項３】
ＩＰプロトコルに則って通信を提供するネットワークにおいてパケットの転送を経路情報対応のエントリに基づいて行うルータに適用したことを特徴とする請求項１または２記載の高速検索方法。
【請求項４】
それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能に格納し、ＣＡＭメモリから構成されるマスク付検索メモリと；
検索条件に合致し、かつ更なる検索の開始点をピンポイントするために使用される、前記グループへの対応情報をコンテンツデータとして前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞る検索手段と；
先頭ビットから順にビット値が「０」及び「１」のいずれかを採り得る点をノードとしてツリーの状態に検索対象となる前記エントリを分類したツリー構成手段とを備え；
前記検索手段は、前記ツリーの状態に分類された前記エントリを対象グループ内データに絞った後の合致エントリの検索を行い、
前記ツリー構成手段は、すべての検索対象の前記エントリについて前記ツリーを構成し、このツリー内の末端のリーフのうち最も先端のルートから遠いものから一定ホップ数上流にさかのぼった中間のノード位置を検索グループを代表する仮想エントリに選び、この選択された仮想エントリのノード位置以降の枝を除外して再度この手順を繰り返し、前記エントリのすべてを網羅するまで選択された前記仮想エントリを前記対応情報として前記マスク付検索メモリに格納しておき、
前記検索手段は、検索の際に条件に合致する前記仮想エントリを前記マスク付検索メモリで判定し、以降の検索を前記ツリーにより行う
ことを特徴とする高速検索装置。
【請求項５】
それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能に格納し、ＣＡＭメモリから構成されるマスク付検索メモリと；
検索条件に合致し、かつ更なる検索の開始点をピンポイントするために使用される、前記グループへの対応情報をコンテンツデータとして前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞る検索手段と；
前記検索手段が前記対象グループ内の検索を行うとき、そのグループ内で検索対象の前記エントリの検索キーの値で最初にビット列が異なるビット位置から最大データ長までの範囲をテーブル検索オフセットとして引くテーブルを構成する記憶手段と；
先頭ビットから順にビット値が「０」及び「１」のいずれかを採り得る点をノードとするツリーの状態に検索対象の前記エントリを分類したツリー構成手段とを備え；
前記検索手段は、検索グループを代表する仮想エントリを前記対応情報として決定するとき、分岐するビット位置が偏在する枝を前記グループとし、条件に合致するグループまでの検索を前記マスク付検索メモリで行い、以降の検索を前記テーブルの参照で行う
ことを特徴とする高速検索装置。
【請求項６】
ＩＰプロトコルに則って通信を提供するネットワークにおいてパケットの転送を経路情報対応のエントリに基づいて行うルータに適用したことを特徴とする請求項４または５記載の高速検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータを格納するテーブルの中から与えられた入力データと合致するものを高速に検索するための高速検索方法及び高速検索装置に関する。
【０００２】
【従来の技術】
近年、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）プロトコルをネットワーク層プロトコルとして利用するネットワークがインターネットや企業内網への適用の形態で急増している。これに伴い、ＩＰネットワークにおいてパケットの中継処理を行うＩＰルータの高性能化が求められている。
【０００３】
しかし、ＩＰパケットの中継処理は、そのパケットの中継経路選定をネットワークアドレス（ネットワークプレフィックス）単位で管理する経路情報に基づいて実行される。このネットワークアドレスはＩＰアドレスの一部を用いる。この「一部」とは、例えばアドレスの上位から可変長で定義されたアドレス値であり、この長さ（プレフィックス長）はネットワークアドレス（ネットワークプレフィックス）により異なる値をとる。すなわち、個々の宛先を示すアドレスのうちネットワークを示すために用いるフィールドがネットワークアドレス毎に可変となっている。
【０００４】
したがって、あるパケットを中継しようとする場合、その宛先アドレスからネットワークアドレス（ネットワークプレフィックス）に対応した情報を得るために管理テーブルを参照するときに、経路エントリ毎に異なるデータ長で比較処理することを実施する必要がある。そのため、ＩＰパケットの中継処理の高速化には、この可変長プレフィックスを持つ経路情報の検索処理を高速に行う必要がある。
【０００５】
このように比較対象のフィールドがエントリ毎に異なった値をとるため、従来よりさまざまな高速検索のアプローチがなされてきた。例えば、ＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）の実装リファレンスとなっているＢＳＤ（Ｂｅｒｋｌｅｙ  Ｓｏｆｔｗａｒｅ  Ｄｉｓｔｒｉｂｕｔｉｏｎ）系ＯＳにおけるネットワーク処理では、ラディックスツリー（Ｒａｄｉｘ  Ｔｒｅｅ）やラディッシュツリー（Ｒａｄｉｓｈ  Ｔｒｅｅ）という高速検索アルゴリズムを採用している。
【０００６】
こうしたアルゴリズムでは、アドレスフィールドの最上位ビットから順にエントリ候補の分岐が生じる箇所に、分岐対象ビットであることを示すエントリを作成する。そして、分岐対象ビット（検査対象ビット）の「０／１」の値に応じて、続くビット並びによってとりうるエントリを分類しておく。したがって、検索の際に候補の分岐が起こりうるビット位置に進んではその値により分岐し、これ以上分岐のない点まで順にツリーを辿り、行き着いたエントリが検索条件を満たしているか否か判定する。
【０００７】
【発明が解決しようとする課題】
しかし、こうしたツリー系アルゴリズムにおいては、単一のエントリに行き着くまでの分岐の段数が各エントリで同じにならず、条件次第ではあるエントリは一回の分岐で行き着くのに対して、別のエントリについては最悪アドレス長分の分岐を繰り返すこともあり得る。
【０００８】
さらに、こうしたアルゴリズムは高速化のためにハードウェア化しようとしても、検索処理の各ステップに依存関係があるため、パイプライン処理やパラレル処理といった手法で高速化するのが困難である。
【０００９】
一方、ハードウェア検索により高速に行う手法として、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）の利用がある。しかし、上記のように経路情報の検索はエントリ毎に異なる長さになるため、固定長のデータを検索するＣＡＭはそのまま利用できず、ルートキャッシュなどの手法と併用せざるを得ない。
【００１０】
ルートキャッシュは、一度検索処理を実行した対象アドレスとそのアドレスに合致したエントリとの対応をリストとして保持するもので、ＣＡＭを使って構成するのが容易である。その一方で、ネットワークアドレスという一種のアドレスの集合体で示されるエントリを個別アドレス単位に展開した形で扱うため、同等の情報を持つためには、はるかに大きなテーブルサイズを必要とする。逆にテーブルサイズを抑制すると、キャッシュにヒットしないケースが増えてしまい、ルートキャッシュによる高速化が機能しにくくなるという問題がある。
【００１１】
また、複数ビット単位でツリーを構成する手法もあるが、ツリーの分岐位置が固定ビット位置になるため、比較対象のエントリのビット幅がエントリ毎に異なる値をとる用途では、ルートキャッシュと同様に何らかの形でアドレスを展開した形態のテーブルを構成する必要が生じる。この結果、テーブルサイズの肥大化を免れない。この問題回避のためには、一部をキャッシュ的に収容する構成をとらざるを得ず、前述のルートキャッシュの場合と同様に効率が悪い。
【００１２】
そこで、従来型ＣＡＭメモリにおいて、エントリ毎に個別に比較対象ビットを指定するためのマスクビットを追加し、ＩＰネットワークでの経路情報検索に不可欠なエントリ単位に独立に指定されるデータ長をＣＡＭレベルで取り込む構成の「マスク付き検索メモリ回路」（特開平３ー１２８９６号公報、特開平７ー１４３１５６号公報、特開平１０ー１１２７２８号公報など）があるが、半導体の集積度などの制約により、経路情報をすべて格納するだけの容量を確保できないことがある。
【００１３】
本発明の目的は、マスク付検索メモリと、ツリーあるいは多段インデックス形式のメモリテーブルとを組み合わて検索可能にすることにより、検索時間のアンバランスあるいはテーブル量の増大という問題を大幅に緩和するだけでなく、容量の小さなマスク付検索メモリしか利用できなくても検索テーブルを大きく持てる検索処理を実現することにある。
【００１４】
【課題を解決するための手段】
上記課題を解決するために、本発明の高速検索方法においては、それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能なマスク付検索メモリに格納しておき、検索条件に合致する前記グループへの対応情報を前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞る。
【００１５】
そして、先頭ビットから順にビット値が「０」及び「１」のいずかを採り得る点をノードとしてツリーの状態に検索対象となる前記エントリを分類しておき、前記エントリを対象グループ内データに絞った後の合致エントリの検索を行う。
【００１６】
この構成において、すべての検索対象の前記エントリについて前記ツリーを構成し、このツリー内の末端のリーフのうち最も先端のルートから遠いものから一定ホップ数上流にさかのぼった中間のノード位置を検索グループを代表する仮想エントリに選び、この選択された仮想エントリのノード位置以降の枝を除外して再度この手順を繰り返し、前記エントリのすべてを網羅するまで選択された前記仮想エントリを前記マスク付検索メモリに格納しておき、検索の際に条件に合致する前記仮想エントリを前記マスク付検索メモリで判定し、以降の検索を前記ツリーにより行う。
【００１７】
また、前記対象グループ内の検索を行うとき、そのグループ内で検索対象の前記エントリの検索キーの値で最初にビット列が異なるビット位置から最大データ長までの範囲をテーブル検索オフセットとしてテーブルを引く。
【００１８】
そして、検索グループを代表する仮想エントリを決定するとき、先頭ビットから順にビット値が「０」及び「１」のいずかを採り得る点をノードとするツリーの状態に検索対象の前記エントリを分類しておき、分岐するビット位置が偏在する枝を前記グループとし、条件に合致するグループまでの検索を前記マスク付検索メモリで行い、以降の検索を前記テーブルの参照で行う。
【００１９】
本発明の高速検索装置は、それぞれが可変長の比較条件を持ちかつ検索対象となるエントリを複数のグループに分け、これらのグループのそれぞれを代表する検索キーを検索用データとして、一致候補について一致範囲を指定するマスクデータ及び比較対象データを前記エントリ毎に指定可能に格納するマスク付検索メモリを備え、検索条件に合致する前記グループへの対応情報を前記マスク付検索メモリから得て検索対象の前記エントリを対象グループ内データに絞る。
【００２０】
この構成において、先頭ビットから順にビット値が「０」及び「１」のいずれかを採り得る点をノードとしてツリーの状態に検索対象となる前記エントリを分類しておき、前記エントリを対象グループ内データに絞った後の合致エントリの検索を行う検索手段を備える。
【００２１】
また、前記対象グループ内の検索を行うとき、そのグループ内で検索対象の前記エントリの検索キーの値で最初にビット列が異なるビット位置から最大データ長までの範囲をテーブル検索オフセットとして引くテーブルを構成する記憶手段を備える。
【００２２】
これらの高速検索方法及び高速検索装置は、ＩＰプロトコルに則って通信を提供するネットワークにおいてパケットの転送を経路情報対応のエントリに基づいて行うルータに適用できる。
【００２３】
本発明においては、検索ツリーを構成したときに、末端までの分岐の数が一定値以下の分岐点を仮想的なエントリとしてマスク付検索メモリに登録する、あるいは複数の経路情報エントリで共通なビット列の部分を仮想的なエントリとしてマスク付検索メモリに格納しておき、残りのエントリ毎に異なるアドレスフィールドをインデックスとして通常のテーブル形式に格納された各エントリの情報を持つことにより、通常のテーブルを多段に並べる場合より検索段数やテーブルサイズを抑制できる。
【００２４】
このように、マスク付検索メモリで経路検索の一次分類を行うことで残りの検索の処理量を減らすことができる。
【００２５】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
本発明の第１の実施の形態の高速検索方法及び高速検索装置をＩＰネットワークのルータにおける経路情報検索に適用する場合を例に説明する。
【００２６】
ＩＰネットワーク構成を示す図１を参照すると、参照符号ＲＴで示すルータのそれぞれは、あるＬＡＮから別のＬＡＮあるいは専用線などと云ったＩＰネットワーク１内の異なるサブネット間のパケットを中継し、直接パケットの授受が行えない通信ノード間での通信を可能にする役割を担う。各ルータＲＴは複数のインタフェースを持ち、あるインタフェースから受信したＩＰパケットをそのパケット内の宛先アドレスに応じ、どのインタフェースからどこに送出すれば、宛先に届けることができるか否かを判定してパケット中継を行う。
【００２７】
このパケット中継を行う際に必要となるパケットの宛先アドレスに応じてどこへ中継したら良いかの情報を格納したテーブルが経路（ルーティング）テーブルである。各ルータＲＴはこのルーティングテーブルを有する。また、各ルータＲＴはＬＡＮ及びＷＡＮなどのネットワークＮＥＴ間を接続する。
【００２８】
図１に示した各ルータＲＴは一例として図２に示す詳細構成を採る。図２を参照すると、ルータＲＴはネットワークＮＥＴ（厳密には、ＥｔｈｅｒｎｅｔなどのＬＡＮのインタフェース部）からパケットを受信する受信インタフェース（Ｉ／Ｆ）部２０と、受信Ｉ／Ｆ部２０からの中継すべきパケットに基づいて宛先ＩＰアドレス情報を抽出してルーティングテーブル検索部２２に渡す宛先ＩＰアドレス抽出部２１とを有する。
【００２９】
ルーティングテーブル検索部２２は経路情報を格納し、中継するパケットの宛先アドレスに対応する経路情報を調べ、該当する宛先インタフェースと、その宛先インタフェースで付与する送信先の物理アドレスの宛先ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ：媒体アクセス制御）アドレスを得る。この検索部２２は後に詳述するように、マスク付検索メモリ２２１及びＲａｄｉｓｈＴｒｅｅ検索エンジン２２２から構成される。また、宛先ＭＡＣアドレス更新部２３はルーティングテーブル検索結果に基づき、宛先に対応したＭＡＣアドレスを宛先ＩＰアドレス抽出部２１からのパケットに上書きして付与する。
【００３０】
ルータＲＴは、さらにルーティングテーブル検索結果に基づき決定された送信インタフェース（Ｉ／Ｆ）部２５にパケットを送出するスイッチ・ファブリック２４を有する。この送信Ｉ／Ｆ部２５はスイッチ・ファブリック２４から受けたパケットをネットワークＮＥＴ（厳密には、ＥｔｈｅｒｎｅｔなどのＬＡＮのインタフェース部）に送出する。ルータＲＴはネットワーク対応に複数のインタフェースを有し、このインタフェース毎に上述した回路を構成している。
【００３１】
各ルータＲＴが有するルーティングテーブルは、各宛先ネットワークに対し、その宛先ネットワークにパケットを送出するときに、次に中継してくれるルータＲＴのＩＰアドレス（最終宛先に直接送信することができる場合は最終宛先の通信ノードのアドレス）と、そのルータＲＴとつながっているインタフェースの情報を持つ。すなわち、図１に示すＩＰネットワークの例では、ルータＲＴ・Ａの有するルーティングテーブルは図３に示す構成になる。また、このルーティングテーブルで想定しているＩＰアドレスと各ホストのネットワーク上でのＭＡＣアドレスとの対応を図４に示す。
【００３２】
図３のルーティングテーブル３は、宛先ネットワークをそのアドレス（同図中「宛先ネットワークアドレス」の項）とそのプレフィックス長（同図中「プレフィックス長」の項）とで示し、その宛先ネットワークについて宛先に向いた経路を与える情報として送信先インタフェース（同図中「送信先インタフェース」の項）と送信時に宛先として指定するＭＡＣアドレス（同図中「送信先アドレス」の項）とを得るためのテーブルである。
【００３３】
このルーティングテーブル３の例では、ルータＲＴ・Ａは自分から直接送信できる各ルータ（またはホスト）のＩＰアドレス及びＭＡＣアドレスを既に知っていることを前提にしており、かつこのルーティングテーブル３ではこれらのルータＲＴについて個別に経路エントリを作成してある状態で表記している。また、自身を示すＩＰアドレスがこの例では３つあり、そのエントリでは送信先インタフェースを「local（自分自身宛）」、ＭＡＣアドレスを「Ｎ．Ａ．（無効）」を示す識別子によりそれぞれ設定している。
【００３４】
図１、図３及び図４を併せ参照すると、ルータＲＴ・ＡがＩＰアドレス「１９２．１６８．６３．１１５」のルータＲＴ・Ｂへパケットを送信する場合、「１９２．１６８．６３．１１５」というアドレスが属するネットワークへパケットを送るには、どこにパケットを送ったら良いかを判断するために、このルーティングテーブル３を検索する。ルーティングテーブル３において、宛先ネットワークアドレス（ＩＰアドレス）「１９２．１６８．６３．１１５」に合致するエントリは、宛先ネットワークアドレス：「１９２．１６８．６３．０」／プレフィックス長：「２４」のエントリと、宛先ネットワークアドレス：「１９２．１６８．６３．１１５」／プレフィックス長：「３２」のエントリとである。
【００３５】
ＩＰパケットのルーティングでは、複数の経路エントリが宛先として合致する場合、プレフィックス長の長いものを優先する規約になっているため、ここでは後者のエントリが選択される。このエントリに格納されている情報に基づき、ルータＲＴ・Ａはこのパケットを送信先インタフェース「＃２」から送信先アドレス（宛先ＭＡＣアドレス）「０：０：ｃ０：ａ１：ａ：９ｆ」として送信する。ルータＲＴ・Ａのインタフェース＃２に接続されているネットワーク（ネットワークアドレス「１９２．１６８．６３．０／２４」が割り当てられているＬＡＮ）を通知、「０：０：ｃ０：ａ１：ａ：９ｆ」の宛先ＭＡＣアドレスを持つ通信ノード（図４に示す対応表により、ここではＩＰアドレス「１９２．１６８．６３．１１５」が付与されている通信ノード）がこのパケットを受信する。これにより、このパケットが宛先アドレスに届く。
【００３６】
また、ルータＲＴ・Ａから見てアドレス「１９２．１６８．６３．１１５」の先にあるネットワークアドレス「１９２．１６８．１１５．０／２４」のネットワーク内にある通信ノードのアドレス「１９２．１６８．１１５．３５」宛のパケットをルータＲＴ・Ａが送信する場合も、同様にルーティングテーブル３を参照し、宛先ネットワークアドレス：「１９２．１６８．１１５．０」／プレフィックス長：「２４」のエントリがこの宛先に該当するという結果を得る。
【００３７】
そして、このエントリの情報に基づきインタフェース＃２から宛先ＭＡＣアドレス「０：０：ｃ０：ａ１：ａ：９ｆ」を付与して送信すると、ＩＰアドレス「１９２．１６８．６３．１１５」が付与されているルータＲＴ・Ｂにこのパケットが届く。このルータＲＴ・ＢがルータＲＴ・Ａと同様なルーティング処理（パケット中継のための判定）を行いアドレス「１９２．１６８．１１５．０／２４」のネットワークＮＥＴへそのパケットを送出し、宛先通信ノードがこのパケットを受けることにより、宛先通信ノードに届く。
【００３８】
以上、ルータＲＴ・Ａが送信元となる場合の例を挙げたが、例えば「１９２．１６８．３．１」のＩＰアドレスを与えられているルータＲＴ・ＣがルータＲＴ・Ａを宛先の途上にあるルータとみなして同様な宛先アドレスを持つパケットをルータＲＴ・Ａが中継したときも、ルータＲＴ・Ａ内の中継動作は同様の処理を行う。また、他のノードが送信元のパケットでも、その送信元ノードから宛先までの経路上にルータＲＴ・Ａがあり、ルータＲＴ・Ａがそのパケットを受信して中継処理する場合も同様に処理される。
【００３９】
上述した例では、ルーティングテーブル３で次ホップのルータ（次ホップが最終宛先の場合はその宛先）のＭＡＣアドレスを得る構成としているが、実装によっては、ルーティングテーブル３では宛先アドレスはＩＰアドレスについて知り、各インタフェースの送信処理の段階でそのゲートウェイＩＰアドレスから実際にパケットに付与するＭＡＣアドレスを得る構成を採ることもできる。
【００４０】
図５は図３に示す経路情報をＲａｄｉｓｈ  Ｔｒｅｅでツリー化したものである。この図では、最初の分岐点をルート、中途の経由点をノード、及び末端の点をリーフ（leaf）と呼ぶことにする。なお、ノードはルート、ノード及びリーフの総称として用いることもある。同図中、ルート及びノードにおいては注目するビット番号を示しており、検索対象の値のこのビット値が「０」か「１」かで分岐する。また、網掛けとなっているノード及びリーフは、実際の経路情報（実経路エントリ）に対応するものである。
【００４１】
同図中、リーフに行き着き、そのネットワークプレフィックスが検索対象のアドレスと合致するものであればエントリ発見、不一致なら経由したノードで網かけされているもののうち最後に通ったものが合致エントリ、どちらも合致しなければ該当エントリなしとなる。この例では最短のもので２回の分岐、最長のもので１０回の分岐を経てエントリにたどり着くため、Ｒａｄｉｓｈ  Ｔｒｅｅだけでの検索は最大１０回の分岐判定を行う必要がある。
【００４２】
経路情報はそのルータに静的に設定するか、経路情報交換プロトコル（ルーティングプロトコル）により隣接ルータ間で経路情報を形成することで得る。この経路情報の形成において、新たな経路エントリが追加されたとき、あるいは既存のエントリが削除されたときに、ルーティングテーブル３の変更がなされる。このときには、ルーティングテーブル及びＲａｄｉｓｈ  Ｔｒｅｅの再構成を行う必要がある。
【００４３】
経路情報に変更があった場合、それが新たな経路エントリの追加であれば、次の手順でツリー（Ｒａｄｉｓｈ  Ｔｒｅｅ）の追加を行う。
（１）構築済みのツリーに対して新たに追加する経路情報で検索を行う（検索手順については後に詳述する）。
【００４４】
（２）あるノードまではマッチし、次のノード（あるいはリーフ）で不一致となったときは、その不一致になるノードと不一致となる最初のビット位置にノードを挿入し、その検査対象ビットの「０／１」に応じ、新たに挿入するエントリか既存のノード（あるいはリーフ）に続くかの分岐を再構築する。
【００４５】
（３）リーフでマッチしてしまった場合、そのリーフの部分集合となっているときは、そのリーフのエントリをノードのエントリに変更し、新たに追加するエントリをそのノードの下に接続する。リーフでマッチして部分集合でないときは、全く同一のエントリとなるので、エントリの上書きとなる。
【００４６】
また、経路エントリの削除となる場合は、次の手順でツリー（Ｒａｄｉｓｈ  Ｔｒｅｅ）の削除を行う。
（１）削除対象のエントリのノードについてそのネットワークエントリをキーにしてツリーを辿ることで探す（検索手順は後に詳述する）。
【００４７】
（２）そのエントリがリーフであるときは、そのリーフを削除する。このとき、直前のノードがエントリを持たないノードであれば、そこでの分岐が不要となるためそのノードも削除する。
【００４８】
（３）そのエントリがリーフでなく、中間のノードになっているときは、そのノードでツリーが分岐していればエントリ情報のみ削除してノードを残し、分岐がなければノードも含めて削除する。
【００４９】
なお、これらの手順はＲａｄｉｓｈ  Ｔｒｅｅのアルゴリズムでツリーの更新を行うための手順そのものであるが、一例の手順である。
次に、上記経路エントリの追加・削除の手順により構築されたルーティングテーブル対応のツリーによる検索動作を説明する。図５に示すツリーは図３に示すルーティングテーブル３をもとに前述の手順でＲａｄｉｓｈ  Ｔｒｅｅを構成したときの構成例である。
【００５０】
上記同様に、ルータＲＴ・ＡがＩＰアドレス「１９２．１６８．６３．１１５」のルータＲＴ・Ｂへパケットを送信する場合を例にとると、ルーティングテーブル検索動作においては、図５のＲａｄｉｓｈ  Ｔｒｅｅを次のように検索する。
【００５１】
まず、ツリーのルートとなっているノードをみると、そのノードが持つアドレス情報は、宛先ネットワークアドレス「１９２．１６８．６３．１１５（２進数表記で１１００００００１０１０１０００００１１１１１１０１１１００１１）」を含んでいる（プレフィックス長が「０」であるため、あらゆるアドレスが合致する）ので、先に候補がある可能性があるので検索を続ける。ここで、ｂｉｔ３１の値によって候補が分岐することを示しているので、アドレス「１９２．１６８．６３．１１５」のｂｉｔ３１を検査する。
【００５２】
このビットは「１」であるため、「１」が示している枝に進む。その先にあるノードの持つアドレス情報は「１９２．１６８．０．０／１７」であり、依然宛先ネットワークアドレス「１９２．１６８．６３．１１５」に合致する。そこで、このノードにおける分岐対象ビットであるｂｉｔ１４の値を宛先ネットワークアドレス「１９２．１６８．６３．１１５」について検査すると、このビットは「０」となる。そこで、「０」が示している枝に進む。
【００５３】
この手順を順次繰り返すと、アドレス「１９２．１６８．０．０／１８」のノードでｂｉｔ１３を検査して「１」に進み、「１９２．１６８．３２．０／１９」のノードでｂｉｔ１２を検査して「１」に進み、「１９２．１６８．６３．０／２４」のノードにたどり着く。このノードは実経路エントリが対応しており、かつ宛先ネットワークアドレス「１９２．１６８．６３．１１５」に合致するので、この時点で合致するエントリを見つけたことになる。
【００５４】
しかし、ツリーにはまだ先があるので、さらに長いプレフィックス長で合致する候補を探すためにツリー検索を継続する。すると、アドレス「１９２．１６８．６３．０／２５」のノードに進みｂｉｔ６を検査して「１」の枝に進み、「１９２．１６８．６３．１１４／３１」のノードでｂｉｔ０を検査して「１」側に進み、「１９２．１６８．６３．１１５／３２」のノード（リーフ）にたどり着く。このノードのアドレスは宛先ネットワークアドレスに合致し、先はないため、このノードに対応づけられたエントリが選ぶべき経路情報の入ったエントリとなる。  したがって、そのエントリに対応した送信先アドレス（図５にはこの経路情報を記載していない）に従ってパケットを送信することにより、パケット送信あるいはパケット中継動作が完了する。
【００５５】
図５に示すＲａｄｉｓｈ  Ｔｒｅｅの構成において、リーフ中で最も遠いものを選び、そこから上流に４個ノードを辿った位置にあるノードを仮想エントリに選ぶ。もし、その仮想エントリより上流に実経路エントリを持つノードがある場合は、それより末端を仮想エントリとして選ぶと、ヒットなしのときに最後に経由した実経路エントリを持つノードのエントリを得ることができなくなるので、そのような中間ノードがあるときはそれを登録する仮想エントリとして選び、そこより下流は仮想エントリ候補から除外する。
【００５６】
こうして選んだ仮想エントリの下流にあるエントリを除外してこれを順次繰り返し、最も遠いエントリが４個以内にすべて収まったら、ツリーのルートを最後に仮想エントリに追加する。この結果、選択されたノードを含むＲａｄｉｓｈ  Ｔｒｅｅ構成を図６に、またこの選択ノードに対応して作成され、マスク付検索メモリ（図２中の２２１）に登録する仮想エントリを図７に示す。
【００５７】
図７において、仮想エントリは、最上位ビットから分岐対象ビットまでを検索対象とするビットとして、マスク付検索メモリにその際参照すべきプレフィックス長の長いものが優先度が高くなるように格納する。すると、ツリーをルートから検索する代わりに、マスク付検索メモリをまず引いて、マッチするエントリを見つけ、そのエントリ位置に対応する情報に基づいて、引き続き検索すべき図６に示すＲａｄｉｓｈ  Ｔｒｅｅのノード位置を得て、ツリー検索を続行する。これにより、あらゆる実経路エントリにたどり着くまでの参照回数が５回以下に設定でき、検索に必要なステップ数を大幅に減らすことができる。
【００５８】
なお、このエントリの選び方はあくまで一例であり、ツリーの中間ノード（あるいは状況によってはリーフやルート）をうまく選択し、最終的に選択したノードからリーフまでのノード経由数が少なくなるように仮想エントリを選択しさえすれば機能する。
【００５９】
ここで、ツリーに実経路エントリを持つ中間ノードがあるときの制約により、リーフまでの段数が設定段数より増えてしまう場合（図６、図７の例は仮想エントリ＃５がこれに該当）は、そのような中間エントリを２つ以上のエントリに分割し、そのような中間ノードからリーフまでの段数が設定値まで少なくなるように経路ツリーを構成し直してから上記の手順を実施すれば良い。
【００６０】
また、図７に示すテーブルからは、仮想エントリとして選んだノードが持つ宛先ネットワークアドレスとマスク値とをキーとして、そのノード情報が格納されたノードへのポインタが得られる。このテーブルはマスク付ＣＡＭで構成することを想定している。ここで、宛先ネットワークアドレスがＣＡＭメモリのデータ部として、またマスク値に記載している数値のビット数分だけ上位ビットから「１」が並び、残りの各ビットが「０」であるような値（「１」のビットは一致判定の対象外、「０」のビットが一致対象という仕様の場合）をマスク部として格納する。
【００６１】
この例で検索を開始すると、まず中継対象パケットの宛先ネットワークアドレスをキーに図７のテーブルを格納したマスク付検索メモリ（図２中の２２１）の検索を行う。すると、その宛先ネットワークアドレス対応の仮想エントリへの情報（具体的には、ツリーが格納されているメモリ上における仮想エントリのアドレスなど）が得られる。上記と同例のルータＲＴ・Ａがアドレス「１９２．１６８．６３．１１５」のルータＲＴ・Ｂへパケットを送信する場合で検索動作を説明する。
【００６２】
まず、宛先ネットワークアドレス「１９２．１６８．６３．１１５」をキーにして、図７の内容が格納されたマスク付検索メモリで検索を行う。すると、宛先ネットワークアドレス「１９２．１６８．６３．０」／マスク値「２４」のエントリにヒットする。すると、その内容は仮想エントリ＃５を示している。そこで、図６に示したツリーにおいて、仮想エントリ＃５からツリー検索を開始する。したがって、以下先の例でアドレス「１９２．１６８．６３．０／２４」のノードにたどり着いた処理以降の動作を行う。
【００６３】
このノードには実経路エントリが対応しており、かつ宛先ネットワークアドレス「１９２．１６８．６３．１１５」に合致するので、この時点で合致するエントリを見つけたことになる。しかし、ツリーにはまだ先があるので、さらに長いプレフィックス長で合致する候補を探すためツリー検索を継続する。すると、アドレス「１９２．１６８．６３．０／２５」のノードに進みｂｉｔ６を検査して「１」の枝に進み、アドレス「１９２．１６８．６３．１１４／３１」のノードでｂｉｔ０を検査して「１」側に進み、アドレス「１９２．１６８．６３．１１５／３２」のノード（リーフ）にたどり着く。
【００６４】
このノードのアドレスは宛先ネットワークアドレスに合致し、先はないため、このノードに対応づけられたエントリが選ぶべき経路情報の入ったエントリとなる。したがって、そのエントリに対応した送信先アドレス（図６にはこの経路情報を記載していない）に従いパケットを送信することにより、パケット送信あるいはパケット中継動作が完了する。
【００６５】
この検索手法では、マスク付検索メモリを使って一気に仮想ノード位置までたどり着ける分、検索処理が高速化される。
次に、本発明の第２の実施の形態の高速検索方法及び高速検索装置について説明する。
【００６６】
ＩＰアドレス（宛先ネットワークアドレス）から対応するパケット中継先情報を得るメモリテーブルとしては、ＩＰアドレス空間と同じ容量のエントリ数のテーブルがあれば、１回のメモリ参照で中継先情報を得ることができるが、これは必要なメモリ容量を考えると現実的でない。そこで、アドレスを構成するビット列の一部のみテーブル参照の際に使用するテーブル内エントリオフセットとして使用し、このようなテーブルをメモリ（ＲＡＭ）テーブルに複数設け、それぞれのテーブルで表現できるアドレス集合を仮想的なエントリとしてマスク付検索メモリに登録しておく。第２の実施の形態の高速検索を可能にするルータＲＴは、図８に示すように、図２に示すルータＲＴのルーティングテーブル検索部２２をマスク付検索メモリ（ＣＡＭ）２２３及びメモリ（ＲＡＭ）テーブル２２４から構成する。
【００６７】
上述した第１の実施の形態と同様に、図３に示すルーティングテーブル３の経路情報にこの検索手法を適用した場合を例に説明する。
このようなメモリテーブルのブロック範囲の決定は、例えば図９（図５対応）のようにＲａｄｉｓｈ  Ｔｒｅｅをまず作成し、あるノード以下のツリーにおいて分岐対象となるビットが比較的密集しているようなノードを探し、そのようなノードを仮想エントリとしてマスク付検索メモリ２２３に登録する（図１０参照）。ここで、ひととおり分岐対象ビット範囲が密集しているツリーを除外してまだ散在する実経路エントリがあれば、それを網羅するような仮想エントリを作成してもよいし、検索メモリの容量に空きがあれば単独でエントリを割り当ててもよい。図１０では、（オ）及び（カ）が単独のエントリに割り当てた仮想エントリである。
【００６８】
そして、仮想エントリとして選んだノード以下のツリーに含まれる経路エントリ情報を通常のメモリで容易に構成可能なテーブル形式で参照する。このテーブルには、各エントリに対応した情報を格納しておく。その構成は、仮想エントリとして選んだノード以下のツリー中に含まれるノードで分岐対象となるビットの最上位ビットから、それらノードに含まれる経路エントリ中で最長のネットワークプレフィックス長のビットまでのビットフィールドをメモリテーブル内におけるインデックスあるいはテーブル内エントリオフセットとして利用し、その位置に対応した経路情報の内容を実際のメモリの内容とする。
【００６９】
ここで、インデックスに使うビットの範囲を最長のネットワークプレフィックス長となるビットまでとするのは、そのビットまで判定しないと、そのエントリに該当しないエントリが含まれてしまう場合が起こりうるからである。
【００７０】
図１０に示すマスク付検索メモリ２２３内の仮想エントリ（ア）〜（カ）からそれぞれ参照されるメモリテーブル２２４の内容例を図１１及び図１２に示す。このようなテーブルを構成する際、実際のエントリはネットワークプレフィックス長が揃っているわけではないので、一番長いものに合わせてオフセットアドレスとして使うビット範囲を選択すると、それより短いプレフィックス長を持つエントリでは無視しなければならないビットを明示的に与える必要がある。
【００７１】
しかし、これは無視するビットの値が「０」であるテーブル内エントリオフセット位置も、「１」であるテーブル内エントリオフセット位置も同じ内容を登録することにより、事実上そのビットに依存しない内容を得ることが実現できる。図１１の中では、テーブル（ウ）のエントリオフセット６４以降がこれに該当する。
【００７２】
また、テーブル（エ）では、エントリオフセット６３の位置は、テーブル（エ）より優先度が高く参照されるテーブル（ア）があるため（この例では優先順位は図１０に示したマスク付検索メモリ２２３への格納順で与えるものとしている）、このエントリ位置は実際に参照されることはない。このようにテーブル形式に展開すると、実際は経路情報のないアドレス集合に対するエントリができてしまう。
【００７３】
ＩＰネットワークとＬＡＮによるネットワークの場合、自分から直接送信できる宛先であって経路情報のないエントリは、その宛先ＩＰアドレスのＭＡＣアドレスが分からないだけであるので、そのようなケースではＡＲＰ（Ａｄｄｒｅｓｓ  Ｒｅｓｏｌｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ：アドレス解決プロトコル）を使って対応ＭＡＣアドレスを調べることになる。このＡＲＰプロトコルについては、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ）にてＲＦＣ８２６（ｆｔｐ：／／ｆｔｐ．ｉｓｉ．ｅｄｕ／ｉｎ−ｎｏｔｅｓ／ｒｆｃ８２６．ｔｘｔ）としてインターネット標準プロトコル化されている。
【００７４】
この実施の形態では、こうした手続きをする必要があるところまで分かれば、後はこの検索機構を利用するシステムの実装依存の問題であるため、図１１及び図１２中ではそのようなエントリを「（不完全）」としている。
【００７５】
一方、本当に経路がなく、パケットの送信先の判定のしようがない分については、「Ｎ．Ａ．（無効）」を示す情報をエントリに格納しておく。このようなエントリに該当したときの処理は、マスク付検索メモリ２２３において合致するエントリが見つからなかったときと同じに扱い、ＩＰプロトコルで定められている「経路情報なし」に従った処理を行うようにする。この処理の実行部分もＡＲＰプロトコルを実行する部分同様、本出願の検索機構の外部で実施すべきものである。
【００７６】
また、個別にメモリテーブル２２４を持つエントリ集合を決める別の方法として、自分のインタフェースから直接最終の宛先に送信可能なネットワークプレフィックスについては、宛先ホスト毎のエントリが必要になることから、自分のインタフェースが属するネットワークプレフィックスについてそれぞれテーブルを作成し、ＩＰアドレスからネットワークプレフィックスを除いた部分（ホストアドレス部）をオフセットアドレスとしてテーブルを検索するように割り当てる構成を採ってもよい（このテーブルはネットワーク送信プロセスにおける実装として別途ＡＲＰプロトコルによるテーブルとして持つ実装を行うことも考えられる）。
【００７７】
なお、仮想エントリを割り当てる場合、そのエントリ以下の経路を与えるためのテーブルが大きくなりすぎるときは、複数のアドレスブロックに分け、それぞれに仮想エントリを定義し、これをマスク付検索メモリに登録しておくことにより、一つのテーブルサイズが大きくなることを回避することができる。
【００７８】
また、このブロック分割でも規模が大きくなりすぎることに対応可能な構成として、マスク付検索メモリに直接最終的なテーブルへの情報の代わりに中間テーブルへの情報を登録するようにし、テーブルへのテーブルを経由する構成としてもよい。
【００７９】
また、図１０、図１１及び図１２のテーブル構成では、単独の実経路エントリに対してマスク付検索メモリ２２３のエントリを割り当てた場合でも必ず一度メモリテーブル２２４を参照するようにしているが、検索メモリ２２３で該当するエントリに関連付けた情報に、メモリテーブル２２４へのポインタの代わりに実際の経路情報データを入れておく形式を採ってもよい。この場合、テーブル参照がさらに必要か、そのまま経路情報が入っているかを識別するためのフラグ情報を併せて持つ必要がある。
【００８０】
図３のルーティングテーブル３について図５のツリー（Ｒａｄｉｓｈ  Ｔｒｅｅ）を構築し、各リーフからツリーを上流に辿っていき、分岐条件となるビット数が集中している範囲を意識しながらメモリ参照ポイント（ア）、（イ）、…（カ）を選んだ様子、つまり仮想ノードの選択方法の詳細を図９に示している。
【００８１】
メモリテーブル化する際のメモリテーブルのデータ幅、つまり分岐対象ビットが集中している範囲をどこまでとするかについては、基本的にはメモリテーブルとして使うメモリの容量に依存する。このようなメモリテーブルに利用するメモリ素子として、高速性と同期設計のしやすさから同期型ＳＲＡＭが有効である。同期型ＳＲＡＭは、現在マイクロプロセッサの外部キャッシュメモリとして多く使われており、例えば６４ビット幅×６４ｋ語の容量を持つ４Ｍｂｉｔのメモリチップが比較的容易に入手可能である。
【００８２】
このようなメモリであれば、２５６個のエントリ（２５６エントリ）のテーブルを２５６個格納できる。例えば、マスク付検索メモリのＣＡＭメモリのエントリ数が２５６エントリであれば、高々２５６個のメモリテーブルしか持てないので、これを単一のメモリチップに格納する場合でも平均テーブルサイズが２５６エントリを目安に、すなわちツリーを作成したときに分岐対象ビットが連続する８ビットの範囲内に収まる範囲を選ぶようにすればよい。
【００８３】
なお、経路情報を多く必要とするネットワークで利用するには、このメモリを複数メモリチップで構成し、一つのメモリテーブルの容量を増やすことにより、同じＣＡＭメモリへのエントリ数で一層多くの経路情報を格納することができる。ＣＡＭメモリと異なり、通常のメモリは複数チップ構成により容量を増やすことが容易であるため、この方法は有効である。
【００８４】
メモリテーブル化するツリー範囲の決定方法の手順の一例は次のようになる。
（１）各リーフから一つづつ上流ノードに辿っていく。
（２）一つ上流ノードに進んだとき、そこまでの参照ビット範囲とそのノード以下に存在できる経路情報の数との関数を評価関数とし、この評価関数の値がある値以下になるまで、あるいは参照ビット範囲が一定値（例えば、メモリの入力アドレスビット数）を超えるまで上流のノードへ辿る操作を繰り返す。
【００８５】
（３）手順（２）の評価関数は、「そのビット幅で必要とするテーブルサイズと収容経路エントリ数との比」のように単純なものとしても良いし、あらかじめビット幅に対応した最低収納エントリ数を表の形で保持しても良い。
【００８６】
（４）上記（１）〜（３）の手順をメモリテーブルに収容されていないリーフについて最低１回処理されるまで繰り返す。
（５）網羅できなかったエントリを順次個別にＣＡＭメモリに単一のエントリとして登録する。
【００８７】
厳密には、メモリテーブル数をＣＡＭメモリのエントリ数以下にしなければならないため、ＣＡＭメモリの容量が十分確保できない、あるいはメモリテーブルの容量の制限により全経路が収容しきれない場合が存在しうる。基本的には、こういう状況にならないようにＣＡＭエントリ数／メモリ量を設計する必要がある。しかし、ＣＡＭメモリでミスヒットとなった宛先を持つパケットはソフトウェア処理により経路を検索して中継するなどの対処で容量オーバに対する適応力を高められるが、ミスヒットは処理性能の大幅な低下を招く。
【００８８】
これを回避するために、ミスヒットの頻度の高い経路情報をメモリテーブルに先に格納する、あるいはＣＡＭメモリを単独で使うエントリとの間で入れ替えるなどの最適化処理の適用を行っても良い。
【００８９】
図９中、参照符号（ア）〜（カ）のマークをした部分が、以降をメモリテーブル（ＲＡＭテーブル）２２４を用いて検索することとしたノードである。また、（ア）〜（カ）のノードまでの検索については、これらのノードを仮想エントリとして、図１０で示すマスク付検索メモリ２２３のテーブルに登録しておく。
【００９０】
この検索テーブルは、仮想エントリとして選んだノードが持つ宛先ネットワークアドレスとマスク値とをキーとして、その仮想エントリ以下の検索を行うためのＲＡＭテーブルを示す情報及びその際にインデックスとして使用すべきビットフィールドが得られるテーブルであり、マスク付きＣＡＭで構成することを想定している。ここで、宛先ネットワークアドレスがＣＡＭメモリのデータ部として、またマスク値をＣＡＭメモリのマスク部に格納する。
【００９１】
また、ＲＡＭテーブル２２４は図１１及び図１２のような構成になる。ここで、（ア）〜（カ）の６つの表は、それぞれ図９の中の仮想ノードとして選んだ点（ア）〜（カ）に対応する。それぞれのテーブルはその仮想ノードにおける検査対象ビット位置から最遠端のリーフのマスクビット位置までの範囲のビットフィールドで表現できるだけのエントリ数を持ち、各エントリにはルーティング結果として利用する送信すべきインタフェースとその際付与するアドレス（ＭＡＣアドレス）が入っている。
【００９２】
テーブル参照のときに使用するビットフィールドは、図１０のテーブルに入れておくことで簡単に判定できるようにしておく。つまり、宛先ネットワークアドレスから該当仮想エントリのネットワークアドレス部を除外した値に対し、図８のテーブルに基づいて得られる対応情報中の「最下位ビット」フィールドで示される宛先アドレスのビット位置を最下位ビットとして見た値を該当テーブル参照の際のエントリ位置として使う（図１３参照）。
【００９３】
それぞれのテーブル内に格納されたエントリは、すべて同じプレフィックス長として取り扱われるため、そのテーブルに対応する仮想ノードのツリー以下にある実経路エントリのうち、プレフィックス長が短いものについては一つの実経路エントリをテーブル内の複数エントリで表現する。図１１中のテーブル（ウ）のエントリオフセット６４〜１２７がこの一例である。
【００９４】
なお、図１１及び図１２において、「テーブル長」として示した値をオフセットとして取り扱う「ビット幅」を入れる形式（例えば、「１２８」の代わりに「７」を入れる）で持つ構成とすることができる。この方が上記ネットワークアドレス部の除外処理が簡単になる可能性がある。
【００９５】
この例で検索を開始すると、まず中継対象パケットの宛先ネットワークアドレスをキーに図１０のテーブルを格納したマスク付検索メモリ２２３で検索を行う。すると、その宛先ネットワークアドレスが該当する仮想エントリに対応したＲＡＭテーブル２２４への情報（具体的には、ツリーが格納されているメモリ上における仮想エントリのアドレスなど）が得られる。
【００９６】
上記と同様に、ルータＲｔ・Ａがアドレス「１９２．１６８．６３．１１５」のルータＲＴ・Ｂへパケットを送信する場合の検索動作について説明する。まず、宛先ネットワークアドレス「１９２．１６８．６３．１１５」をキーに、図１０に示す内容が格納されたマスク付検索メモリ２２３を検索する。すると、宛先ネットワークアドレス「１９２．１６８．６３．０」／マスク値「０ｘＦＦＦＦＦＦ００」のエントリにヒットする。この結果、その内容が仮想エントリ（ア）を示している。そこで、図１１中のテーブル（ア）を次に参照する。
【００９７】
図１０を参照したときに得られる最下位ビットはｂｉｔ０なので宛先ネットワークアドレス「１９２．１６８．６３．１１５（１１００００００１０１０１０００００１１１１１１０１１１００１１）」から仮想エントリ（ウ）のネットワークアドレス部分（１９２．１６８．６３．０／２４）を除外した値（あるいはマスク値「０ｘＦＦＦＦＦＦ００」の各ビットを反転させた値とビット毎のＡＮＤ演算を行った値）である「０．０．０．１１５（２進数表記で０００００００００００００００００００００００００１１１００１１）」を０ビットだけ右シフトした値、すなわち１１５番目のエントリが求める経路を収容したエントリである。
【００９８】
ここで、テーブル（ア）から該当経路情報としては、送信先インタフェースが「＃２」であり、送信先アドレス（ＭＡＣアドレス）を「０：０：ｃ０：ａ１：ａ：９ｆ」とする送信先情報が得られる。この検索を行うより、マスク付検索メモリ２２３の参照と、メモリ（ＲＡＭ）テーブル２２４へのアクセスとの計２回の参照動作で求める経路検索が行え、検索処理を高速化できる。
以上、本発明の高速検索方法及び高速検索装置について、ＩＰパケットの中継処理に適用した場合を例に採り説明したが、その他の適用領域として、何らかのＩＤ値から属するグループなどの情報を得る処理などに適用できる。
【００９９】
例えば、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ：非同期転送モード）通信によるセル中継処理あるいはセル受信処理においては、アクティブなコネクションをＶＰＩ及びＶＣＩという識別子により識別する。したがって、セル中継装置あるいはセル受信装置において、そのセルをどこに中継するかあるいは内部の通信バッファに蓄積するかの情報を参照する際に、このＶＰＩ及びＶＣＩをキーに管理テーブルを検索する必要がある。
【０１００】
これらのエントリをすべてマスク付検索メモリ（ＣＡＭメモリ）に格納する構成では、ＡＴＭ−ＵＮＩ（Ｕｓｅｒ  Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ）の場合で、ＶＰＩが８ビット、かつＶＣＩが１６ビットのアドレス長を有するため、アクティブなコネクション数だけＣＡＭメモリへのエントリ数が必要となる。したがって、大容量化が難しいＣＡＭメモリではあまり多くのコネクション数を処理できないことになる。
【０１０１】
上述した本発明の高速検索手法、すなわちＲａｄｉｓｈ  Ｔｒｅｅの中途までＣＡＭメモリで検索する第１の手法及びＣＡＭメモリ参照後にメモリテーブル（ＲＡＭテーブル）で最終的なエントリ情報を得る第２の手法を利用することにより、小容量のＣＡＭメモリで多くのエントリ数を収容することができ、高速な検索と実現コストとの両立が可能となる。
【０１０２】
ＡＴＭのコネクション管理テーブルは、ＩＰのルーティング情報と異なりフルマッチのみできれば良いが、Ｒａｄｉｓｈ  Ｔｒｅｅによる検索を適用することは可能である。したがって、Ｒａｄｉｓｈ  Ｔｒｅｅを上記ＩＰルーティングテーブルと同様に作成し（この例ではプレフィックス長の考慮は不要となる）、仮想エントリを割り当て、その先の検索をＲａｄｉｓｈ  ＴｒｅｅあるいはＲＡＭテーブルで行うことが可能となる。
【０１０３】
また、ＶＰＩ及びＶＣＩ値をフルマッチで検索せず、例えば特定のＶＰＩ値を持つものはＶＣＩ値によらず同一に扱う場合（ＶＰ単位での処理とＶＣ単位の処理とを一元的に行う場合）には、ＶＰＩまでをプレフィックス長と想定して同様の手法を採ることができる。さらに、複数のＶＣに対し同一の管理情報で処理可能の場合、フルマッチではなく下位の複数ビットをマスクすることにより、エントリを削減することも可能である。
【０１０４】
【発明の効果】
以上説明したように、本発明によれば、マスク付検索メモリとツリーあるいはメモリテーブルとによるエントリサーチを用いた検索により、マスク付検索メモリ単独では収容しきれないエントリ毎の可変長の比較条件を持つエントリの検索をツリーあるいはメモリテーブルによる単独的な検索よりも高速に実行することができる。
【０１０５】
この検索手法を例えばＩＰルータのパケット中継先判定に適用すれば、宛先判定を高速処理することが可能となる。
【図面の簡単な説明】
【図１】  本発明の第１の実施の形態におけるＩＰネットワークの構成を示す。
【図２】  図１におけるルータの詳細構成を示す。
【図３】  ルーティングテーブルの構成例を示す。
【図４】  図３のテーブルにおいて想定しているＩＰアドレスとＭＡＣアドレスとの対応を示す。
【図５】  図３に示すルーティングテーブル対応のＲａｄｉｓｈ  Ｔｒｅｅの構成を示す。
【図６】  第１の実施の形態における仮想エントリ選択後のＲａｄｉｓｈ  Ｔｒｅｅの構成例を示す。
【図７】  第１の実施の形態におけるマスク付検索メモリへの仮想エントリの登録例を示す。
【図８】  第２の実施の形態におけるルータの構成を示す。
【図９】  第２の実施の形態におけるメモリ参照ポイントを選択したＲａｄｉｓｈ  Ｔｒｅｅを示す。
【図１０】  第２の実施の形態におけるマスク付検索メモリの構成を示す。
【図１１】  第２の実施の形態におけるメモリテーブルの構成を示す。
【図１２】  第２の実施の形態におけるメモリテーブルの構成を示す。
【図１３】  図１１及び図１２に示すメモリテーブルの参照を説明するための図である。
【符号の説明】
１    ＩＰネットワーク
３    ルーティングテーブル
ＲＴ    ルータ
ＮＥＴ    ネットワーク
２２    ルーティングテーブル検索部
２２１、２２３    マスク付検索メモリ（ＣＡＭメモリ）
２２２    Ｒａｄｉｓｈ  Ｔｒｅｅ検索エンジン
２２４    メモリ（ＲＡＭ）テーブル
【図１】
0004156112.tif 000002
【図２】
0004156112.tif 000003
【図３】
0004156112.tif 000004
【図４】
0004156112.tif 000005
【図５】
0004156112.tif 000006
【図６】
0004156112.tif 000007
【図７】
0004156112.tif 000008
【図８】
0004156112.tif 000009
【図９】
0004156112.tif 000010
【図１０】
0004156112.tif 000011
【図１１】
0004156112.tif 000012
【図１２】
0004156112.tif 000013
【図１３】
0004156112.tif 000014