(57)【要約】【課題】  範囲指定に対応する検索用のエントリの生成を最小限に抑えることができるエントリ生成方法、エントリ生成プログラムを提供する。【解決手段】  ＣＰＵ４における処理において、最初に、数値範囲の最大値及び最小値のｂｉｔパターンに対して、上位ビットから比較を行い、ｂｉｔ値が異なるｂｉｔ位置（Ｓ）を特定する。次に、最大値のｂｉｔパターンに対しては、Ｓ−１番目のｂｉｔから順次ｂｉｔ値が１であるｂｉｔを０に反転し、反転したｂｉｔ位置より上位のｂｉｔを全て１、下位のｂｉｔを０としたマスク生成を行う。一方、最小値のｂｉｔパターンに対しては、Ｓ−１番目のｂｉｔからｂｉｔ値０となるｂｉｔを１に反転し、反転したｂｉｔ位置より上位のｂｉｔを全て１、下位のｂｉｔを０としたマスクを生成を行う。これを、最下位ｂｉｔまで繰り返すことにより、指定された数値範囲すべてを網羅した、ＴＣＡＭデバイス２に登録するエントリが生成できる。このエントリの数は最大でも範囲指定する対象となるエリアのｂｉｔ幅×２＋１個で済む。【選択図】  図１
2005303865.tif 000002
【特許請求の範囲】
【請求項１】
特定の数値を検索するために、ｂｉｔ列を有し、数値範囲を表現するエントリを生成するエントリ生成方法において、
前記ｂｉｔ列を構成するｂｉｔに対してｂｉｔ演算を行うことにより、前記エントリを生成することを特徴とするエントリ生成方法。
【請求項２】
前記数値範囲の最大値及び最小値があって、
前記ｂｉｔ演算は、前記最大値並びに前記最小値に係るｂｉｔ列を構成するｂｉｔのｂｉｔ値を操作すること及び前記最大値並びに前記最小値に係るｂｉｔ値を各々比較することによりｂｉｔ値の操作を行うｂｉｔを特定することを組み合わせたものであることを特徴とする請求項１に記載のエントリ生成方法。
【請求項３】
前記エントリは、
前記数値範囲の数値に対応するｂｉｔ列と、検索時に比較対照とするｂｉｔを示すマスク機能を有するｂｉｔ列を有することを特徴とする請求項１又は２に記載のエントリ生成方法。
【請求項４】
特定の数値を検索するために、ｂｉｔ列を有し、数値範囲を表現するエントリを生成するエントリ生成方法におけるエントリ生成プログラムにおいて、
前記ｂｉｔ列を構成するｂｉｔに対してｂｉｔ演算を行うことにより、前記エントリを生成する処理を、コンピュータに実行させることを特徴とするエントリ生成プログラム。
【請求項５】
前記数値範囲の最大値及び最小値があって、
前記ｂｉｔ演算は、前記最大値並びに前記最小値に係るｂｉｔ列を構成するｂｉｔのｂｉｔ値を操作すること及び前記最大値並びに前記最小値に係るｂｉｔ値を各々比較することによりｂｉｔ値の操作を行うｂｉｔを特定することを組み合わせたものであることを特徴とする請求項４に記載のエントリ生成プログラム。
【請求項６】
前記エントリは、
前記数値範囲の数値に対応するｂｉｔ列と、検索時に比較対照とするｂｉｔを示すマスク機能を有するｂｉｔ列を有することを特徴とする請求項４又は５に記載のエントリ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索用にエントリを生成するエントリ生成方法、エントリ生成プログラムに関し、特に数値範囲検索指定時において、ＴＣＡＭデバイスに対してエントリを生成するエントリ生成方法、エントリ生成プログラムに関する。
【背景技術】
【０００２】
ルータ、ファイアーウォール機器等に実装されているＴＣＡＭデバイスに対してエントリを設定する場合、ＩＰアドレス（＋ネットワークマスク）のようにｂｉｔ範囲を指定した場合は１エントリのみの設定で済むが、レイヤ４宛先ポート番号など数値範囲を検索対象とする場合、数値ｂｉｔ列とｂｉｔマスクを用いて指定するためには、範囲内の数値全てに対しエントリを生成する必要がある。このため、ＴＣＡＭリソースを多大に消費してしまい、検索性能が低下するという問題がある。
【０００３】
特許文献１には、検索性能を向上させる技術が開示されている。つまり、ＣＰＵが検索エントリをＣＡＭ及び小容量高速メモリに登録する際、レイヤ４宛先ポートが［下限〜上限］の範囲条件で与えられているため、所定のアルゴリズムを用いて宛先ポートの［下限〜上限］の範囲を複数に分割して、ＣＡＭに登録するエントリを求める方法が採り上げられている。こうすることにより、検索ヒット条件を少ないエントリ数で登録することを可能にし、検索性能を向上させている。
【特許文献１】特開２００２−３７４２８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１の技術を用いたとしても検索により生成されるエントリ数そのものを低減することはできないため、エントリ生成に伴うリソースの消費がそれほど低減されるとは言い難く、検索性能の向上の効果は小さい。
本発明では上記事情を鑑みて、範囲指定に対応する検索用のエントリの生成を最小限に抑えることができるエントリ生成方法、エントリ生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するための本発明の態様は、特定の数値を検索するために、ｂｉｔ列を有し、数値範囲を表現するエントリを生成するエントリ生成方法において、前記ｂｉｔ列を構成するｂｉｔに対してｂｉｔ演算を行うことにより、前記エントリを生成することにある。
【０００６】
このとき、前記数値範囲の最大値及び最小値があって、前記ｂｉｔ演算は、前記最大値並びに前記最小値に係るｂｉｔ列を構成するｂｉｔのｂｉｔ値を操作すること及び前記最大値並びに前記最小値に係るｂｉｔ値を各々比較することによりｂｉｔ値の操作を行うｂｉｔを特定することを組み合わせたものであることを特徴とする。
【０００７】
又前記エントリは、前記数値範囲の数値に対応するｂｉｔ列と、検索時に比較対照とするｂｉｔを示すマスク機能を有するｂｉｔ列を有することを特徴とする。
【０００８】
上記目的を達成するための本発明の他の態様は、特定の数値を検索するために、ｂｉｔ列を有し、数値範囲を表現するエントリを生成するエントリ生成方法におけるエントリ生成プログラムにおいて、前記ｂｉｔ列を構成するｂｉｔに対してｂｉｔ演算を行うことにより、前記エントリを生成する処理を、コンピュータに実行させることにある。
【０００９】
このとき、前記数値範囲の最大値及び最小値があって、前記ｂｉｔ演算は、前記最大値並びに前記最小値に係るｂｉｔ列を構成するｂｉｔのｂｉｔ値を操作すること及び前記最大値並びに前記最小値に係るｂｉｔ値を各々比較することによりｂｉｔ値の操作を行うｂｉｔを特定することを組み合わせたものであることを特徴とする。
【００１０】
又前記エントリは、前記数値範囲の数値に対応するｂｉｔ列と、検索時に比較対照とするｂｉｔを示すマスク機能を有するｂｉｔ列を有することを特徴とする。
【００１１】
結局本発明の論理は、数値範囲の最大値及び最小値のｂｉｔ列に対し、ｂｉｔの比較及びｂｉｔ操作といったｂｉｔ演算のみでエントリを生成することにある。以下にその手順を説明する。
【００１２】
最初に、数値範囲の最大値及び最小値のｂｉｔパターンに対して、上位ビットから比較を行い、ｂｉｔ値が異なるｂｉｔ位置を特定する（このｂｉｔ位置をｂｉｔ操作開始位置と呼ぶ。）。
【００１３】
次に、最大値のｂｉｔパターンに対しては、「ｂｉｔ操作開始位置−１」のｂｉｔから順次ｂｉｔ値が１であるｂｉｔを０に反転し、反転したｂｉｔ位置より上位のｂｉｔを全て１、下位のｂｉｔを０としたマスク生成を行う。
【００１４】
一方、最小値のｂｉｔパターンに対しては、「ｂｉｔ操作開始位置−１」のｂｉｔからｂｉｔ値０となるｂｉｔを１に反転し、反転したｂｉｔ位置より上位のｂｉｔを全て１、下位のｂｉｔを０としたマスクを生成を行う。
【００１５】
これを、最下位ｂｉｔまで繰り返すことにより、指定された数値範囲すべてを網羅するエントリが生成できる。
【００１６】
本発明の論理を用いると、最大でも範囲指定する対象となるエリアのｂｉｔ幅の２倍＋１個のエントリのみで対象エリアが取りうる全ての数値の範囲を網羅するエントリを生成することができる。
【発明の効果】
【００１７】
本発明により、範囲指定に対応する検索エントリを最小限に抑えるとこができる。その理由は、エントリをｂｉｔ演算のみで求めることにより、検索対象のｂｉｔ幅の２倍＋１を超えることが無いためである。
【００１８】
又範囲指定に対応する最悪ケースの必要検索エントリ数を予測できる。その理由は、エントリをｂｉｔ演算のみで求めることにより、検索対象となるｂｉｔ幅から最悪ケースのエントリ数が特定できるためである。
【発明を実施するための最良の形態】
【００１９】
以下、本発明を実施するための最良の形態を添付図面を参照して説明する。本実施形態では、ルータ装置のパケットフィルタリング処理を採り上げることにする。パケットフィルタリング処理は、特定の端末（又はネットワーク）に対して特定のサービスを拒否するような場合、端末のＩＰアドレスと、レイヤ４宛先ポート番号によるＴＣＡＭエントリを生成し、このエントリにＨＩＴ（該当）した場合パケットを廃棄する処理である。
【００２０】
この場合、レイヤ４宛先ポート番号は、ある範囲を指定するものが多く（例えば０ｘ１９４〜０ｘ２４１といった範囲指定など）、このような場合のエントリ生成に本発明の論理を適用していく。そして適用したことにより生成されたエントリはＴＣＡＭに対して設定されることになる。
【００２１】
以降ルータ装置は、受信したパケットのヘッダ情報からＩＰアドレス、レイヤ４宛先ポート番号等を取り出し、それらを検索キーとしてＴＣＡＭデバイスに入力し、検索結果を得る。検索の結果、生成したエントリの何れかに合致する場合にはパケット破棄という転送処理を表すフロー識別子が得られるので、それに従いパケットを破棄する。エントリに合致しない場合は、処理を続行する。
【００２２】
図１は、本実施形態におけるルータ装置の構成ブロック図であり、パケットのヘッダ情報を入力とし、そのパケットが属するフロー識別子を出力する検索機能を有する。このルータ装置は、検索エンジン１と、ＴＣＡＭ（Ternary Content Addressable Memory）デバイス２と、小容量高速メモリ３と、ＣＰＵ（中央処理装置）４と、大容量低速メモリ５と、記録媒体６とから構成されており、検索エンジン１及びＣＰＵ４が実行するプログラムは記録媒体６に格納されている。
【００２３】
検索エンジン１はパケットのヘッダ情報が入力されると、ＴＣＡＭデバイス２と小容量高速メモリ３とを用いてヘッダ情報に対応するフロー識別子を検索し、検索が成功すると、その検索結果として得られたフロー識別子を出力する。また、検索エンジン１は検索が失敗すると、ＣＰＵ４と大容量低速メモリ５とを用いて再検索を行い、その検索結果として得られたフロー識別子を出力する。
【００２４】
ＴＣＡＭデバイス２及び小容量高速メモリ３は高速であり、設定されたＴＣＡＭエントリを基にして検索キーに対する検索結果を瞬時に出力する。ＴＣＡＭデバイス２はＴＣＡＭエントリの情報のうち比較対照とするｂｉｔをマスク情報にてマスクしてから検索を行うためのマスク機能を持っている。
【００２５】
一方、ＣＰＵ４はソフトウェア処理のため、ＴＣＡＭデバイス２に比べて検索に長い時間を要するが、本発明の論理によるアルゴリズムを行い、ＴＣＡＭエントリを生成する。このアルゴリズムは記録媒体６のプログラムを実行することにより実現される。生成されたＴＣＡＭエントリはＴＣＡＭ２、小容量高速メモリ３に設定される。
【００２６】
大容量低速メモリ５にはルータ装置が扱う全てのヘッダ情報とフロー識別子との対応が検索エントリとして格納されている。
【００２７】
次に、ＣＰＵ４が処理するアルゴリズムによってＴＣＡＭエントリが生成されるまでのフロー（１−１〜１−６）を図２から図７を用いて説明する。なお、生成されるＴＣＡＭエントリのｂｉｔ幅は８であり、生成される際に指定される数値範囲の最大値、最小値が予め入力されているものとする。
【００２８】
図２はフロー１−１に相当するフローチャートである。１−１では、最大値のｂｉｔ列及び最小値のｂｉｔ列を比較してｂｉｔ操作を開始する位置（ｂｉｔ操作開始位置（Ｓ）と呼ぶ）の特定、及び最小値ｂｉｔ列に対するｂｉｔ検索を行い最小値に対するｂｉｔ操作を終了する位置（最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））と呼ぶ）の特定、及び最大値ｂｉｔ列に対してビット検索を行いｂｉｔ操作を終了する位置（最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））と呼ぶ）の特定を行う。
【００２９】
両ビット列の上位ビット側から比較していき最大値のＮｂｉｔ目と最小値のＮｂｉｔ目が不一致するところをｂｉｔ操作開始位置（Ｓ）とする（ステップＡ）。
【００３０】
次に、最小値のｂｉｔ列に関して下位ビット側から比較してｂｉｔ１が検出される位置を最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））とする（ステップＢ）。
【００３１】
次に、最大値のｂｉｔ列に関して下位ビット側から比較してｂｉｔ０が検出される位置を最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））とする（ステップＣ）。このようなステップＡ〜Ｃの処理を経てフロー１−６に進む。
【００３２】
図３はフロー１−６に相当するフローチャートである。フロー１−６は、本発明の論理の唯一の例外ケースであり、ｂｉｔ操作開始位置（Ｓ）から最下位ｂｉｔまで全て１でかつ最小値が０の場合等を識別するためのものである。ｂｉｔ操作開始位置（Ｓ）が最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））かつ最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））よりも小さい場合、ｂｉｔ操作開始位置（Ｓ）より上位のｂｉｔが最小値と等しく、下位のｂｉｔが０のエントリ値及びｂｉｔ操作開始位置（Ｓ）より上位のｂｉｔが１、下位のｂｉｔが０のエントリマスクを生成する。それ以外の場合はフロー１−３に進む。
【００３３】
図４はフロー１−２に相当するフローチャートである。フロー１−２では、最小値ｂｉｔ列に対してフロー１−１で特定したｂｉｔ操作開始位置（Ｓ）−１のｂｉｔから最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））の間に位置するｂｉｔを０から１に反転しエントリ値を生成するとともに、反転したｂｉｔ位置を含む上位ｂｉｔを１、反転したｂｉｔ位置より下位のｂｉｔを０としたエントリマスクを生成する。最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））まで処理を済ませたらフロー１−３に進む。
【００３４】
図５はフロー１−３に相当するフローチャートである。フロー１−３では、最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））より上位のｂｉｔが最小値ｂｉｔ列に等しく、下位のｂｉｔが０のエントリ及び最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））より上位ｂｉｔを１、下位ｂｉｔを０としたエントリマスクを生成する。その後フロー１−４へ進む。
【００３５】
図６はフロー１−４に相当するフローチャートである。フロー１−４では、最大値ｂｉｔ列に対してフロー１−１で特定したｂｉｔ操作開始位置（Ｓ）−１のｂｉｔ位置から最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））の間に位置するｂｉｔを１から０に反転しエントリ値を生成するとともに、反転したｂｉｔ位置を含む上位ｂｉｔを１、反転したｂｉｔ位置より下位のｂｉｔを０としたエントリマスクを生成する。最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））まで処理を済ませたらフロー１−５に進む。
【００３６】
図７はフロー１−５に相当するフローチャートである。フロー１−５では、最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））より上位のｂｉｔが最大値ｂｉｔ列に等しく、下位のｂｉｔが０のエントリ及び最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））より上位ｂｉｔを１、下位ｂｉｔを０としたエントリマスクを生成する。以上のｂｉｔ操作により、指定された範囲を網羅するエントリ及びマスクの生成が可能である。
【００３７】
次に上述したアルゴリズムを実行してＴＣＡＭエントリが生成されるまでの処理内容２−１〜２−５を図８〜図１０を用いて説明する。ここで、生成されるＴＣＡＭエントリのｂｉｔ幅は８であり、生成される際に指定される数値範囲の最大値は２４１、最小値は１９４が入力されるものとする。なお、最大値のｂｉｔ列は「１１１１０００１」、最小値のｂｉｔ列は「１１００００１０」である。
【００３８】
図８は２−１に相当する処理内容を示したものであり、フロー１−１に相当する。２−１の処理内容では、最大値ｂｉｔ列と最小値ｂｉｔ列を上位ｂｉｔから比較し、ｂｉｔ操作開始位置（Ｓ）を特定する（本例の場合、Ｓ＝５）。
【００３９】
次に最小値ｂｉｔ列を最下位ｂｉｔから「ｂｉｔ幅−１＝７」のｂｉｔ位置まで検索し、最小値ｂｉｔ操作終了位置（Ｅ（ｍｉｎ））を特定する（本例の場合、（Ｅ（ｍｉｎ）＝１）。
【００４０】
次に最大値ｂｉｔ列を最下位ｂｉｔから「ｂｉｔ幅−１＝７」のｂｉｔ位置まで検索し、最大値ｂｉｔ操作終了位置（Ｅ（ｍａｘ））を特定する（本例の場合、（Ｅ（ｍａｘ）＝１）。
【００４１】
図９は２−２、２−３に相当する処理内容を示したものであり、フロー１−２、１−３に相当する。最小値ｂｉｔ列に対しては、２−１の結果から４ｂｉｔ目（Ｓ−１）から１ｂｉｔ目（Ｅ（ｍｉｎ））までのｂｉｔを上位ｂｉｔから順次０となるｂｉｔを検索し、該当ｂｉｔを反転したエントリ値と、ｂｉｔ反転したｂｉｔを含む上位ｂｉｔがａｌｌ１及びｂｉｔ反転したｂｉｔより下位のｂｉｔをall０としたエントリマスク値を生成する。
【００４２】
図１０は２−４、２−５に相当する処理内容を示したものであり、フロー１−４、１−５に相当する。最大値ｂｉｔ列に対しては、２−１の結果から４ｂｉｔ目（Ｓ−１）から１ｂｉｔ目（Ｅ（ｍａｘ））までのｂｉｔを上位ｂｉｔから順次１となるｂｉｔを検索し、該当ｂｉｔを反転したエントリ値と、ｂｉｔ反転したｂｉｔを含む上位ｂｉｔがａｌｌ１、ｂｉｔ反転したｂｉｔより下位のｂｉｔをall０としたエントリマスク値を生成する。
【００４３】
以上の様にして、本例にて指定した最大値２４１から最小値１９４までの全てをカバーするエントリが生成できる。生成されたＴＣＡＭエントリを図１１に示す。同様の論理にて一定のｂｉｔ幅で表現できる全ての数値範囲に対してｂｉｔ操作のみでＴＣＡＭエントリを生成することが可能となる。
【００４４】
但し、上記の論理の例外のケースとなる数値範囲が存在し、その数値範囲の最大値、最小値に対してはフロー１−６による処理が行われる。この処理を行う必要のある最大値、最小値の組合せを以下に例示しておく。なお、数値は２進数表記である。
【００４５】
（最大値、最小値）＝（１，０）、（１１，１０）、（１０１，１００）、（１１１，１１０）、（１１１，１００）、（１００１，１０００）、（１１０１，１１００）、（１１１１，１１１０）、（１１１１，１１００）、（１１１１，１０００）、…
【００４６】
つまり、ｂｉｔ操作開始位置（Ｓ）より上位のｂｉｔ列が最大値と最小値で同じであり、かつｂｉｔ操作開始位置（Ｓ）以下のｂｉｔ列が最大値ではすべて１であり、最小値ではすべて０の組合せが該当する。
【００４７】
なお、本発明は上記の形態に限定されるものではなく、要旨を変更しない範囲において種々変形することが可能である。
【産業上の利用可能性】
【００４８】
ＴＣＡＭデバイスを実装したルータ及びＦｉｒｅｗａｌｌ機器のＩＰフィルタリングのエントリ生成といった用途に適用できる。また、ＤａｔａＢａｓｅストレージ機器の高速検索といった用途にも適用可能である。
【００４９】
また、データベースから同義語を検索したり、半角英数文字列の範囲指定検索を行う情報検索装置や、情報検索装置をコンピュータに実現するためのプログラムといった用途に適用できる。
また、同義語を検索する機能をパソコンやワードプロセッサに搭載されている、かな漢字変換装置や、コンピュータにかな漢字変換機能といった用途にも適用できる。
【図面の簡単な説明】
【００５０】
【図１】ルータ装置のブロック構成図である。
【図２】１−１に相当するフローチャートである。
【図３】１−６に相当するフローチャートである。
【図４】１−２に相当するフローチャートである。
【図５】１−３に相当するフローチャートである。
【図６】１−４に相当するフローチャートである。
【図７】１−５に相当するフローチャートである。
【図８】２−１に相当する処理内容である。
【図９】２−２、２−３に相当する処理内容である。
【図１０】２−４、２−５に相当する処理内容である。
【図１１】２−１〜２−５の処理により生成されたＴＣＡＭエントリである。
【符号の説明】
【００５１】
１    検索エンジン
２    ＴＣＡＭデバイス
３    小容量高速メモリ
４    ＣＰＵ
５    大容量低速メモリ
６    記録媒体
【図１】
2005303865.tif 000003
【図２】
2005303865.tif 000004
【図３】
2005303865.tif 000005
【図４】
2005303865.tif 000006
【図５】
2005303865.tif 000007
【図６】
2005303865.tif 000008
【図７】
2005303865.tif 000009
【図８】
2005303865.tif 000010
【図９】
2005303865.tif 000011
【図１０】
2005303865.tif 000012
【図１１】
2005303865.tif 000013