(57)【要約】【課題】パケットの検索を効率化する。【解決手段】検索装置１０の記憶部１２は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。また、検索部１３２は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。【選択図】図１
2019145970.tif 000002
【特許請求の範囲】
【請求項１】
パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部と、
検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索部と、
を有することを特徴とする検索装置。
【請求項２】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋが、ｌｏｇ２Ｋ＞２を満たす場合に、前記第１のルールを基に、長さが前記第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、前記第１のルール以外のルール数Ｍが、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍを満たす場合に、前記第１のルールを基に、前記第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項１に記載の検索装置。
【請求項４】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数Ｌが、ｌｏｇ２（Ｋ＋Ｌ）＞４を満たす場合に、前記第１のルールを基に、前記第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、前記第２のルールを基に、前記第２の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項１に記載の検索装置。
【請求項５】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数をＫ、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数をＬ、前記第１のルール以外のルール数をＭとしたときに、ｌｏｇ２Ｋ＞２、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍ、及びｌｏｇ２（Ｋ＋Ｌ）＞４の不等式のうち少なくともいずれかが満たされる場合、前記不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項１に記載の検索装置。
【請求項６】
パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部を有する検索装置で実行される検索方法であって、
検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索工程と、
を含むことを特徴とする検索方法。
【請求項７】
コンピュータを、請求項１から５のいずれか１項に記載の検索装置として機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法及び検索プログラムに関する。
【背景技術】
【０００２】
従来、ＩＰパケットの高速な検索手法として、ＴＣＡＭ（Ternary  Content  Addressable  Memory）、ハッシュ検索、二分木検索等が知られている。また、これらの手法の中で、ＴＣＡＭは特に高速であるが、消費電力等のコストが高い。一方、ハッシュ検索は、条件が整えば、ＴＣＡＭに劣らない速度で検索を行うことができることが知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】アラクサラネットワークス株式会社  製品開発部、「Ｄ１  パケットフォワーディングを支える技術  ハードウェア処理ルータの内部詳解」、Internet  Week  2012プレゼンテーション、2012年11月20日、[online]、[平成３０年２月２日検索]、インターネット（https://www.nic.ad.jp/ja/materials/iw/2012/proceedings/d1/d1-uchiya.pdf）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の技術では、パケットの検索を効率化することが困難な場合があるという問題がある。ここで、前述の通り、ＴＣＡＭは高速であるが高コストでもある。また、ハッシュ検索は、条件が整えば、ＴＣＡＭより低コストで、かつＴＣＡＭ並みの速度で検索を行うことができるが、逆にいえば、条件が整わない状況ではＴＣＡＭに検索速度が劣ることになる。なお、二分木検索は、実行可能な条件の面ではハッシュ検索より有利であるが、速度ではハッシュ検索に劣る。
【０００５】
例えば、プレフィックス（Prefix）長が異なる複数のマッチングルールがある場合、ＬＰＭ（Longest  Prefix  Matching）を行うことで検索を効率化できる。一方で、ハッシュ検索では、プレフィックス長が一定でなければマッチングを行うことが難しい。このため、ハッシュ検索にＬＰＭを適用して効率化することは困難である。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明の検索装置は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部と、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索部と、を有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、パケットの検索を効率化することができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、第１の実施形態に係る検索装置の構成の一例を示す図である。
【図２】図２は、第１の実施形態に係る検索装置の処理の概要を説明するための図である。
【図３】図３は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図４】図４は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図５】図５は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図６】図６は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図７】図７は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図８】図８は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図９】図９は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図１０】図１０は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図１１】図１１は、第１の実施形態に係る検索装置の検索処理の流れを示すフローチャートである。
【図１２】図１２は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【０００９】
以下に、本願に係る検索装置、検索方法及び検索プログラムの実施形態を図面に基づいて詳細に説明する。なお、本発明は、以下に説明する実施形態により限定されるものではない。
【００１０】
［第１の実施形態の構成］
まず、図１を用いて、第１の実施形態に係る検索装置の構成について説明する。図１は、第１の実施形態に係る検索装置の構成の一例を示す図である。図１に示すように、検索装置１０は、入出力部１１、記憶部１２及び制御部１３を有する。例えば、検索装置１０は、受信したパケットを、検索によって特定した転送先及び転送経路等に転送するスイッチやルータ等の通信機器である。
【００１１】
入出力部１１は、他の装置との間でデータのやり取りを行う。例えば、入出力部１１は、ネットワークを介してパケットの入力を受け付ける。また、入出力部１１は、パケットを所定の装置に転送することができる。例えば、入出力部１１はＮＩＣ（Network  Interface  Card）である。
【００１２】
記憶部１２は、ＨＤＤ（Hard  Disk  Drive）、ＳＳＤ（Solid  State  Drive）、光ディスク等の記憶装置である。なお、記憶部１２は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non  Volatile  Static  Random  Access  Memory）等のデータを書き換え可能な半導体メモリであってもよい。記憶部１２は、検索装置１０で実行されるＯＳ（Operating  System）や各種プログラムを記憶する。さらに、記憶部１２は、プログラムの実行で用いられる各種情報を記憶する。また、記憶部１２は、ハッシュテーブル記憶部１２１及び二分木モデル記憶部１２２を有する。
【００１３】
記憶部１２のハッシュテーブル記憶部１２１は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。例えば、ハッシュテーブル記憶部１２１は、２６ｂｉｔのプレフィックス「192.68.211.192/26」のハッシュ値をインデックスとするハッシュテーブルを記憶する。また、記憶部１２の二分木モデル記憶部１２２は、二分木検索で用いられるパラメータ等を記憶する。なお、ハッシュテーブルの各インデックスに対する値は、対応する二分木モデルを特定するための情報であってよい。
【００１４】
制御部１３は、検索装置１０全体を制御する。制御部１３は、例えば、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部１３は、作成部１３１及び検索部１３２を有する。
【００１５】
作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールに関する所定の条件が満たされた場合、ハッシュテーブルを作成する。ここで、ルールは、条件にマッチしたパケットの転送先を決定すること等に利用されるものである。また、ルールは、随時追加や変更が行われることがあるため、作成部１３１は、定期的にルールをチェックし、ハッシュテーブルを作成する条件が満たされているか否かを確認することができる。
【００１６】
ここで、ルールには、パケットの所定のフィールドの値と完全一致させるためのものが含まれる。さらに、ルールには、フィールドの値と前方一致させるもの、すなわちフィールドの値のプレフィックスに一致させるためのものが含まれる。
【００１７】
従来、フィールドの値のプレフィックスに一致させるルールについては、ハッシュ検索を用いることが困難であり、二分木検索が用いられる場合があった。これに対し、本実施形態では、フィールドの値のプレフィックスに一致させるルールについて、ハッシュ検索と二分木検索を組み合わせた検索手法により検索を行うことで、検索の高速化を実現している。
【００１８】
検索部１３２は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。
【００１９】
例えば、検索対象のパケットの宛先ＩＰアドレスの値が「192.68.211.200」であって、ハッシュテーブル記憶部１２１に２６ｂｉｔのプレフィックスのハッシュ値をインデックスとするハッシュテーブルが記憶されている場合、検索部１３２は、「192.68.211.200」の２６ｂｉｔのプレフィックス「192.68.211.192/26」から計算したハッシュ値とマッチするインデックスをハッシュテーブルから検索する。
【００２０】
図２を用いて、検索装置１０の処理について説明する。図２は、第１の実施形態に係る検索装置の処理の概要を説明するための図である。図２の例では、フィールドの値のプレフィックスに一致させるためのルールとして、「192.68.211.204/30」等が存在している。まず、作成部１３１は、長さが２６ｂｉｔから３０ｂｉｔのプレフィックスで表されるルールの数が所定の条件を満たす場合にハッシュテーブルを作成する。例えば、作成部１３１は、ルールの数が所定の数を超えたこと、又はルールの全ルールに対する割合が所定の割合を超えたこと等を条件とすることができる。
【００２１】
図２の例では、作成部１３１は、「192.68.211.204/30」、「129.60.10.152/29」、「10.100.8.224/29」及び「11.55.11.192/26」というルールを基に、２６ｂｉｔのプレフィックス「192.68.211.192/26」、「129.60.10.128/26」、「10.100.8.192/26」及び「11.55.11.192/26」のハッシュ値をハッシュテーブルのインデックスとすることができる。そして、検索部１３２は、２６ｂｉｔのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを用いて、/26でのハッシュ検索を行うことができる。
【００２２】
同様に、図２の例において、作成部１３１は、長さが２０ｂｉｔから２２ｂｉｔのプレフィックスで表されるルールの数が所定の条件を満たす場合にハッシュテーブルを作成する。これにより、検索部１３２は、/20でのハッシュ検索を行うことができる。
【００２３】
作成部１３１がハッシュテーブルを作成する際の条件は、あらかじめ指定されたハッシュテーブルに割り当て可能なリソース量に基づくものであってもよい。ここで、図２の例における、長さが２６ｂｉｔから３０ｂｉｔのプレフィックスで表されるルール（以降、ルール１）の数を１００、長さが２０ｂｉｔから２２ｂｉｔのプレフィックスで表されるルール（以降、ルール２）の数を２００とする。そして、利用可能なリソース量を２４ｂｉｔとすると、ルール１のリソース量は（１）式により求められ、ルール２のリソース量は（２）式により求められる。
ｌｏｇ２（２２４×１００／（１００＋２００））≒２２ｂｉｔ  ・・・  （１）
ｌｏｇ２（２２４×２００／（１００＋２００））≒２３ｂｉｔ  ・・・  （２）
【００２４】
また、図３に示すように、作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋが、ｌｏｇ２Ｋ＞２を満たす場合に、第１のルールを基に、長さが第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。
【００２５】
図３は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。図３の例では、第１の範囲は２６ｂｉｔから３０ｂｉｔである。また、第１の範囲の下限は２６ｂｉｔである。また、第１のルールの種類の数Ｋは３である。また、図３では、左から３つ目の列までは、ＩＰアドレスを８ｂｉｔずつ１０進数で表している。また、４つ目以降の列では、ＩＰアドレスの２５ｂｉｔ目以降を２進数で表している。
【００２６】
図３の方法の条件は、二分木検索のみを行う場合よりも、ハッシュ検索と二分木検索を組み合わせた方が検索が高速化される条件である。ここで、ルール数がＮの場合、二分木検索における検索回数は、及びｌｏｇ２Ｎである。また、ハッシュ検索の場合はハッシュ衝突のリスクがあるため、Ｋ種類のルールについて２回程度の検索が行われる。これより、ｌｏｇ２Ｋ＞２の場合、すなわちＫ＞４の場合に、ハッシュ検索と二分木検索を組み合わせた方が検索が高速化されることになる。
【００２７】
同様に、作成部１３１は、長さが第１の範囲に含まれないルールが存在する場合は以下のように条件判定を行う。すなわち、図４に示すように、作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、第１のルール以外のルール数Ｍが、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍを満たす場合に、第１のルールを基に、第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。図４は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【００２８】
同様に、作成部１３１は、複数の異なる範囲のプレフィックスについてルールが存在する場合は以下のように条件判定を行う。すなわち、図５に示すように、作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数Ｌが、ｌｏｇ２（Ｋ＋Ｌ）＞４を満たす場合に、第１のルールを基に、第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、第２のルールを基に、第２の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。図５は、第１の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【００２９】
なお、図３から５のパターンのいずれが現れるかは、指定するプレフィックスの長さ及び指定数によって異なる。このため、作成部１３１は、上記の各不等式の左辺と右辺の差が最も大きいパターンを、検索が最も高速化されるパターンとして採用し、採用したパターンに合わせたプレフィックスの長さを指定した上でハッシュテーブルを作成することができる。
【００３０】
例えば、作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数をＫ、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数をＬ、第１のルール以外のルール数をＭとしたときに、ｌｏｇ２Ｋ＞２、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍ、及びｌｏｇ２（Ｋ＋Ｌ）＞４の不等式のうち少なくともいずれかが満たされる場合、不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成することができる。
【００３１】
なお、上記の各条件の説明は、ハッシュ検索において、ハッシュ衝突のリスクを考慮して２回の検索が行われると仮定した場合のものである。一方、ハッシュ検索における検索回数は２回に限られない。ここで、第ｉのルールの検索回数をｎｉ（ただし、ｎｉ＞０）とすると、図３の例の条件をｌｏｇ２Ｋ＞ｎ１、図４の条件をｌｏｇ２（Ｋ＋Ｍ）＞ｎ１＋ｌｏｇ２Ｍ、図５の例の条件をｌｏｇ２（Ｋ＋Ｌ）＞ｎ１＋ｎ２のように書くことができる。さらに、プレフィックスの長さの範囲が複数の場合、条件を一般化して、ｌｏｇ２（Ｋ＋Ｌ＋・・・）＞ｎ１＋ｎ２＋・・・のように書くことができる。
【００３２】
［第１の実施形態の処理］
図６を用いて、検索装置１０の作成部１３１による処理の流れを説明する。図６は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。図６に示すように、まず、作成部１３１は、ハッシュテーブル作成の要否を判定する（ステップＳ１１）。そして、作成部１３１は、ハッシュテーブルの作成が必要と判定した場合（ステップＳ１２、Ｙｅｓ）、ハッシュテーブルを作成する（ステップＳ１３）。一方、作成部１３１は、ハッシュテーブルの作成が不要と判定した場合（ステップＳ１２、Ｎｏ）、処理を終了する。
【００３３】
図７から９を用いて、作成部１３１によるハッシュテーブル作成の要否を判定する処理について説明する。図７から９は、第１の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【００３４】
図７を用いて、第１の判定方法について説明する。まず、図７に示すように、作成部１３１は、第１のルールの種類の数をＫとする（ステップＳ１０１）。第１のルールは、長さが第１の範囲に含まれるプレフィックスで表されるルールである。
【００３５】
ここで、ｌｏｇ２Ｋ＞２が満たされる場合（ステップＳ１０２、Ｙｅｓ）、作成部１３１は、ハッシュテーブルの作成が必要と判定する（ステップＳ１０３）。一方、ｌｏｇ２Ｋ＞２が満たされない場合（ステップＳ１０２、Ｎｏ）、作成部１３１は、ハッシュテーブルの作成が不要と判定する（ステップＳ１０４）。
【００３６】
図８を用いて、第２の判定方法について説明する。まず、図８に示すように、作成部１３１は、第１のルールの種類の数をＫ、第１のルール以外のルール数をＭとする（ステップＳ２０１）。第１のルールは、長さが第１の範囲に含まれるプレフィックスで表されるルールである。第２のルールは、長さが第１の範囲と異なる２の範囲に含まれるプレフィックスで表されるルールである。
【００３７】
ここで、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍが満たされる場合（ステップＳ２０２、Ｙｅｓ）、作成部１３１は、ハッシュテーブルの作成が必要と判定する（ステップＳ２０３）。一方、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍが満たされない場合（ステップＳ２０２、Ｎｏ）、作成部１３１は、ハッシュテーブルの作成が不要と判定する（ステップＳ２０４）。
【００３８】
図９を用いて、第３の判定方法について説明する。まず、図９に示すように、作成部１３１は、第１のルールの種類の数をＫ、第２のルールの種類の数をＬとする（ステップＳ３０１）。第１のルールは、長さが第１の範囲に含まれるプレフィックスで表されるルールである。第２のルールは、長さが第１の範囲と異なる２の範囲に含まれるプレフィックスで表されるルールである。
【００３９】
ここで、ｌｏｇ２（Ｋ＋Ｌ）＞４が満たされる場合（ステップＳ３０２、Ｙｅｓ）、作成部１３１は、ハッシュテーブルの作成が必要と判定する（ステップＳ３０３）。一方、ｌｏｇ２（Ｋ＋Ｌ）＞４が満たされない場合（ステップＳ３０２、Ｎｏ）、作成部１３１は、ハッシュテーブルの作成が不要と判定する（ステップＳ３０４）。
【００４０】
図１０を用いて、第４の判定方法及び作成するハッシュテーブルのパターンの選定方法について説明する。まず、図１０に示すように、作成部１３１は、第１のルールの種類の数をＫ、第２のルールの種類の数をＬ、第１のルール以外のルール数をＭとする（ステップＳ４０１）。
【００４１】
次に、作成部１３１は、ｄ１＝ｌｏｇ２Ｋ−２、ｄ２＝ｌｏｇ２（Ｋ＋Ｍ）−（２＋ｌｏｇ２Ｍ）、ｄ３＝ｌｏｇ２（Ｋ＋Ｌ）−４とする（ステップＳ４０２）。ここで、ｄ１、ｄ２、ｄ３がいずれも０以下である場合（ステップＳ４０３、Ｙｅｓ）、作成部１３１は、ハッシュテーブルの作成が不要と判定する（ステップＳ４０４）。
【００４２】
ｄ１、ｄ２、ｄ３がいずれかが０より大きい場合（ステップＳ４０３、Ｎｏ）、作成部１３１は、ハッシュテーブルの作成が必要と判定する（ステップＳ４０５）。そして、ｄ１、ｄ２、ｄ３のうちｄ１が最大である場合、作成部１３１は、全てのルールが第１のルールに含まれるような第１のハッシュテーブルのパターンを選定する（ステップＳ４０７）。また、ｄ１、ｄ２、ｄ３のうちｄ２が最大である場合、作成部１３１は、一部のルールが第１のルールに含まれるような第２のハッシュテーブルのパターンを選定する（ステップＳ４０８）。また、ｄ１、ｄ２、ｄ３のうちｄ３が最大である場合、作成部１３１は、全てのルールが第１のルールと第２のルールのいずれかに含まれるような第３のハッシュテーブルのパターンを選定する（ステップＳ４０９）。
【００４３】
なお、第１のパターンは、図３に示すハッシュテーブルのパターンである。また、第２のパターンは、図４に示すハッシュテーブルのパターンである。また、第３のパターンは、図５に示すハッシュテーブルのパターンである。
【００４４】
次に、図１１を用いて、検索部１３２による検索処理について説明する。図１１は、第１の実施形態に係る検索装置の検索処理の流れを示すフローチャートである。図１１に示すように、まず、検索部１３２は、検索対象のパケットのフィールドの値でハッシュテーブルを検索する（ステップＳ２１）。このとき、検索部１３２は、フィールドの値からハッシュテーブルごとの対応する長さだけのプレフィックスを抽出し、抽出したプレフィックスのハッシュ値を計算しておく。そして、検索部１３２は、ハッシュテーブルにマッチしなかった部分を二分木を用いて検索する（ステップＳ２２）。
【００４５】
［第１の実施形態の効果］
記憶部１２は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。また、検索部１３２は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。これにより、本実施形態では、従来は二分木を用いて行われていた検索の一部又は全部を、ハッシュテーブルを用いて行うことができるようになるため、パケットの検索を効率化することができる。
【００４６】
作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋが、ｌｏｇ２Ｋ＞２を満たす場合に、第１のルールを基に、長さが第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、全てのルールを１つのプレフィックス長のハッシュテーブルを用いて検索した場合に、検索が高速化されるか否かを判定することができる。
【００４７】
作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、第１のルール以外のルール数Ｍが、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍを満たす場合に、第１のルールを基に、第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、ルールの一部を１つのプレフィックス長のハッシュテーブルを用いて検索し、他のルールの検索にハッシュテーブルを用いなかった場合に、検索が高速化されるか否かを判定することができる。
【００４８】
作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数Ｋと、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数Ｌが、ｌｏｇ２（Ｋ＋Ｌ）＞４を満たす場合に、第１のルールを基に、第１の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、第２のルールを基に、第２の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、全てのルールを２つのプレフィックス長のハッシュテーブルを用いて検索した場合に、検索が高速化されるか否かを判定することができる。
【００４９】
作成部１３１は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第１の範囲に含まれるプレフィックスで表される第１のルールの種類の数をＫ、長さが第２の範囲に含まれるプレフィックスで表される第２のルールの種類の数をＬ、第１のルール以外のルール数をＭとしたときに、ｌｏｇ２Ｋ＞２、ｌｏｇ２（Ｋ＋Ｍ）＞２＋ｌｏｇ２Ｍ、及びｌｏｇ２（Ｋ＋Ｌ）＞４の不等式のうち少なくともいずれかが満たされる場合、不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成する。これにより、ハッシュテーブルの作成パターンが複数考えられる場合に最適なパターンを選定することができる。
【００５０】
［その他の実施形態］
本実施形態では、パケットのフィールドとしてＩＰアドレスを例に挙げて説明したが、検索対象のフィールドは、ポート番号等のＩＰアドレス以外のフィールドであってもよい。
【００５１】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部又は任意の一部が、ＣＰＵ及び当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００５２】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００５３】
［プログラム］
一実施形態として、検索装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記の検索を実行する検索プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の検索プログラムを情報処理装置に実行させることにより、情報処理装置を検索装置１０として機能させることができる。ここで言う情報処理装置には、スイッチやルータ等のネットワーク機器の他、デスクトップ型又はノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等のスレート端末等がその範疇に含まれる。
【００５４】
図１２は、検索プログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００５５】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００５６】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、検索装置１０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、検索装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤにより代替されてもよい。
【００５７】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０は、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した実施形態の処理を実行する。
【００５８】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００５９】
１０  検索装置
１１  入出力部
１２  記憶部
１３  制御部
１２１  ハッシュテーブル記憶部
１２２  二分木モデル記憶部
１３１  作成部
１３２  検索部
【図１】
2019145970.tif 000003
【図２】
2019145970.tif 000004
【図３】
2019145970.tif 000005
【図４】
2019145970.tif 000006
【図５】
2019145970.tif 000007
【図６】
2019145970.tif 000008
【図７】
2019145970.tif 000009
【図８】
2019145970.tif 000010
【図９】
2019145970.tif 000011
【図１０】
2019145970.tif 000012
【図１１】
2019145970.tif 000013
【図１２】
2019145970.tif 000014