(19)【発行国】日本国特許庁(JP)
(12)【公報種別】公開特許公報(A)
(11)【公開番号】2019145970
(43)【公開日】20190829
(54)【発明の名称】検索装置、検索方法及び検索プログラム
(51)【国際特許分類】
   H04L 12/743 20130101AFI20190802BHJP
【FI】
   !H04L12/743
【審査請求】未請求
【請求項の数】7
【出願形態】OL
【全頁数】13
(21)【出願番号】2018027422
(22)【出願日】20180219
(71)【出願人】
【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【住所又は居所】東京都千代田区大手町一丁目5番1号
(74)【代理人】
【識別番号】110002147
【氏名又は名称】特許業務法人酒井国際特許事務所
(72)【発明者】
【氏名】金子 斉
【住所又は居所】東京都千代田区大手町一丁目5番1号 日本電信電話株式会社内
(72)【発明者】
【氏名】内田 博志
【住所又は居所】東京都千代田区大手町一丁目5番1号 日本電信電話株式会社内
【テーマコード(参考)】
5K030
【Fターム(参考)】
5K030HA08
5K030KA04
5K030LE16
5K030MD06
(57)【要約】
【課題】パケットの検索を効率化する。
【解決手段】検索装置10の記憶部12は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。また、検索部132は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。
【選択図】図1
【特許請求の範囲】
【請求項1】
パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部と、
検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索部と、
を有することを特徴とする検索装置。
【請求項2】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kが、logK>2を満たす場合に、前記第1のルールを基に、長さが前記第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項1に記載の検索装置。
【請求項3】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、前記第1のルール以外のルール数Mが、log(K+M)>2+logMを満たす場合に、前記第1のルールを基に、前記第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項1に記載の検索装置。
【請求項4】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数Lが、log(K+L)>4を満たす場合に、前記第1のルールを基に、前記第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、前記第2のルールを基に、前記第2の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項1に記載の検索装置。
【請求項5】
前記パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数をK、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数をL、前記第1のルール以外のルール数をMとしたときに、logK>2、log(K+M)>2+logM、及びlog(K+L)>4の不等式のうち少なくともいずれかが満たされる場合、前記不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成する作成部をさらに有することを特徴とする請求項1に記載の検索装置。
【請求項6】
パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部を有する検索装置で実行される検索方法であって、
検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索工程と、
を含むことを特徴とする検索方法。
【請求項7】
コンピュータを、請求項1から5のいずれか1項に記載の検索装置として機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、検索装置、検索方法及び検索プログラムに関する。
【背景技術】
【0002】
従来、IPパケットの高速な検索手法として、TCAM(Ternary Content Addressable Memory)、ハッシュ検索、二分木検索等が知られている。また、これらの手法の中で、TCAMは特に高速であるが、消費電力等のコストが高い。一方、ハッシュ検索は、条件が整えば、TCAMに劣らない速度で検索を行うことができることが知られている。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】アラクサラネットワークス株式会社 製品開発部、「D1 パケットフォワーディングを支える技術 ハードウェア処理ルータの内部詳解」、Internet Week 2012プレゼンテーション、2012年11月20日、[online]、[平成30年2月2日検索]、インターネット(https://www.nic.ad.jp/ja/materials/iw/2012/proceedings/d1/d1-uchiya.pdf)
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、従来の技術では、パケットの検索を効率化することが困難な場合があるという問題がある。ここで、前述の通り、TCAMは高速であるが高コストでもある。また、ハッシュ検索は、条件が整えば、TCAMより低コストで、かつTCAM並みの速度で検索を行うことができるが、逆にいえば、条件が整わない状況ではTCAMに検索速度が劣ることになる。なお、二分木検索は、実行可能な条件の面ではハッシュ検索より有利であるが、速度ではハッシュ検索に劣る。
【0005】
例えば、プレフィックス(Prefix)長が異なる複数のマッチングルールがある場合、LPM(Longest Prefix Matching)を行うことで検索を効率化できる。一方で、ハッシュ検索では、プレフィックス長が一定でなければマッチングを行うことが難しい。このため、ハッシュ検索にLPMを適用して効率化することは困難である。
【課題を解決するための手段】
【0006】
上述した課題を解決し、目的を達成するために、本発明の検索装置は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する記憶部と、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、前記プレフィックスの部分については、前記プレフィックスから計算したハッシュ値及び前記ハッシュテーブルを用いてハッシュ検索を行う検索部と、を有することを特徴とする。
【発明の効果】
【0007】
本発明によれば、パケットの検索を効率化することができる。
【図面の簡単な説明】
【0008】
【図1】図1は、第1の実施形態に係る検索装置の構成の一例を示す図である。
【図2】図2は、第1の実施形態に係る検索装置の処理の概要を説明するための図である。
【図3】図3は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図4】図4は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図5】図5は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【図6】図6は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図7】図7は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図8】図8は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図9】図9は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図10】図10は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【図11】図11は、第1の実施形態に係る検索装置の検索処理の流れを示すフローチャートである。
【図12】図12は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【0009】
以下に、本願に係る検索装置、検索方法及び検索プログラムの実施形態を図面に基づいて詳細に説明する。なお、本発明は、以下に説明する実施形態により限定されるものではない。
【0010】
[第1の実施形態の構成]
まず、図1を用いて、第1の実施形態に係る検索装置の構成について説明する。図1は、第1の実施形態に係る検索装置の構成の一例を示す図である。図1に示すように、検索装置10は、入出力部11、記憶部12及び制御部13を有する。例えば、検索装置10は、受信したパケットを、検索によって特定した転送先及び転送経路等に転送するスイッチやルータ等の通信機器である。
【0011】
入出力部11は、他の装置との間でデータのやり取りを行う。例えば、入出力部11は、ネットワークを介してパケットの入力を受け付ける。また、入出力部11は、パケットを所定の装置に転送することができる。例えば、入出力部11はNIC(Network Interface Card)である。
【0012】
記憶部12は、HDD(Hard Disk Drive)、SSD(Solid State Drive)、光ディスク等の記憶装置である。なお、記憶部12は、RAM(Random Access Memory)、フラッシュメモリ、NVSRAM(Non Volatile Static Random Access Memory)等のデータを書き換え可能な半導体メモリであってもよい。記憶部12は、検索装置10で実行されるOS(Operating System)や各種プログラムを記憶する。さらに、記憶部12は、プログラムの実行で用いられる各種情報を記憶する。また、記憶部12は、ハッシュテーブル記憶部121及び二分木モデル記憶部122を有する。
【0013】
記憶部12のハッシュテーブル記憶部121は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。例えば、ハッシュテーブル記憶部121は、26bitのプレフィックス「192.68.211.192/26」のハッシュ値をインデックスとするハッシュテーブルを記憶する。また、記憶部12の二分木モデル記憶部122は、二分木検索で用いられるパラメータ等を記憶する。なお、ハッシュテーブルの各インデックスに対する値は、対応する二分木モデルを特定するための情報であってよい。
【0014】
制御部13は、検索装置10全体を制御する。制御部13は、例えば、CPU(Central Processing Unit)、MPU(Micro Processing Unit)等の電子回路や、ASIC(Application Specific Integrated Circuit)、FPGA(Field Programmable Gate Array)等の集積回路である。また、制御部13は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部13は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部13は、作成部131及び検索部132を有する。
【0015】
作成部131は、パケットの所定のフィールドの値とマッチさせるルールに関する所定の条件が満たされた場合、ハッシュテーブルを作成する。ここで、ルールは、条件にマッチしたパケットの転送先を決定すること等に利用されるものである。また、ルールは、随時追加や変更が行われることがあるため、作成部131は、定期的にルールをチェックし、ハッシュテーブルを作成する条件が満たされているか否かを確認することができる。
【0016】
ここで、ルールには、パケットの所定のフィールドの値と完全一致させるためのものが含まれる。さらに、ルールには、フィールドの値と前方一致させるもの、すなわちフィールドの値のプレフィックスに一致させるためのものが含まれる。
【0017】
従来、フィールドの値のプレフィックスに一致させるルールについては、ハッシュ検索を用いることが困難であり、二分木検索が用いられる場合があった。これに対し、本実施形態では、フィールドの値のプレフィックスに一致させるルールについて、ハッシュ検索と二分木検索を組み合わせた検索手法により検索を行うことで、検索の高速化を実現している。
【0018】
検索部132は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。
【0019】
例えば、検索対象のパケットの宛先IPアドレスの値が「192.68.211.200」であって、ハッシュテーブル記憶部121に26bitのプレフィックスのハッシュ値をインデックスとするハッシュテーブルが記憶されている場合、検索部132は、「192.68.211.200」の26bitのプレフィックス「192.68.211.192/26」から計算したハッシュ値とマッチするインデックスをハッシュテーブルから検索する。
【0020】
図2を用いて、検索装置10の処理について説明する。図2は、第1の実施形態に係る検索装置の処理の概要を説明するための図である。図2の例では、フィールドの値のプレフィックスに一致させるためのルールとして、「192.68.211.204/30」等が存在している。まず、作成部131は、長さが26bitから30bitのプレフィックスで表されるルールの数が所定の条件を満たす場合にハッシュテーブルを作成する。例えば、作成部131は、ルールの数が所定の数を超えたこと、又はルールの全ルールに対する割合が所定の割合を超えたこと等を条件とすることができる。
【0021】
図2の例では、作成部131は、「192.68.211.204/30」、「129.60.10.152/29」、「10.100.8.224/29」及び「11.55.11.192/26」というルールを基に、26bitのプレフィックス「192.68.211.192/26」、「129.60.10.128/26」、「10.100.8.192/26」及び「11.55.11.192/26」のハッシュ値をハッシュテーブルのインデックスとすることができる。そして、検索部132は、26bitのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを用いて、/26でのハッシュ検索を行うことができる。
【0022】
同様に、図2の例において、作成部131は、長さが20bitから22bitのプレフィックスで表されるルールの数が所定の条件を満たす場合にハッシュテーブルを作成する。これにより、検索部132は、/20でのハッシュ検索を行うことができる。
【0023】
作成部131がハッシュテーブルを作成する際の条件は、あらかじめ指定されたハッシュテーブルに割り当て可能なリソース量に基づくものであってもよい。ここで、図2の例における、長さが26bitから30bitのプレフィックスで表されるルール(以降、ルール1)の数を100、長さが20bitから22bitのプレフィックスで表されるルール(以降、ルール2)の数を200とする。そして、利用可能なリソース量を24bitとすると、ルール1のリソース量は(1)式により求められ、ルール2のリソース量は(2)式により求められる。
log(224×100/(100+200))≒22bit ・・・ (1)
log(224×200/(100+200))≒23bit ・・・ (2)
【0024】
また、図3に示すように、作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kが、logK>2を満たす場合に、第1のルールを基に、長さが第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。
【0025】
図3は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。図3の例では、第1の範囲は26bitから30bitである。また、第1の範囲の下限は26bitである。また、第1のルールの種類の数Kは3である。また、図3では、左から3つ目の列までは、IPアドレスを8bitずつ10進数で表している。また、4つ目以降の列では、IPアドレスの25bit目以降を2進数で表している。
【0026】
図3の方法の条件は、二分木検索のみを行う場合よりも、ハッシュ検索と二分木検索を組み合わせた方が検索が高速化される条件である。ここで、ルール数がNの場合、二分木検索における検索回数は、及びlogNである。また、ハッシュ検索の場合はハッシュ衝突のリスクがあるため、K種類のルールについて2回程度の検索が行われる。これより、logK>2の場合、すなわちK>4の場合に、ハッシュ検索と二分木検索を組み合わせた方が検索が高速化されることになる。
【0027】
同様に、作成部131は、長さが第1の範囲に含まれないルールが存在する場合は以下のように条件判定を行う。すなわち、図4に示すように、作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、第1のルール以外のルール数Mが、log(K+M)>2+logMを満たす場合に、第1のルールを基に、第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。図4は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【0028】
同様に、作成部131は、複数の異なる範囲のプレフィックスについてルールが存在する場合は以下のように条件判定を行う。すなわち、図5に示すように、作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数Lが、log(K+L)>4を満たす場合に、第1のルールを基に、第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、第2のルールを基に、第2の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。図5は、第1の実施形態に係るハッシュテーブルの作成条件について説明するための図である。
【0029】
なお、図3から5のパターンのいずれが現れるかは、指定するプレフィックスの長さ及び指定数によって異なる。このため、作成部131は、上記の各不等式の左辺と右辺の差が最も大きいパターンを、検索が最も高速化されるパターンとして採用し、採用したパターンに合わせたプレフィックスの長さを指定した上でハッシュテーブルを作成することができる。
【0030】
例えば、作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数をK、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数をL、第1のルール以外のルール数をMとしたときに、logK>2、log(K+M)>2+logM、及びlog(K+L)>4の不等式のうち少なくともいずれかが満たされる場合、不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成することができる。
【0031】
なお、上記の各条件の説明は、ハッシュ検索において、ハッシュ衝突のリスクを考慮して2回の検索が行われると仮定した場合のものである。一方、ハッシュ検索における検索回数は2回に限られない。ここで、第iのルールの検索回数をn(ただし、n>0)とすると、図3の例の条件をlogK>n、図4の条件をlog(K+M)>n+logM、図5の例の条件をlog(K+L)>n1+のように書くことができる。さらに、プレフィックスの長さの範囲が複数の場合、条件を一般化して、log(K+L+・・・)>n1++・・・のように書くことができる。
【0032】
[第1の実施形態の処理]
図6を用いて、検索装置10の作成部131による処理の流れを説明する。図6は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。図6に示すように、まず、作成部131は、ハッシュテーブル作成の要否を判定する(ステップS11)。そして、作成部131は、ハッシュテーブルの作成が必要と判定した場合(ステップS12、Yes)、ハッシュテーブルを作成する(ステップS13)。一方、作成部131は、ハッシュテーブルの作成が不要と判定した場合(ステップS12、No)、処理を終了する。
【0033】
図7から9を用いて、作成部131によるハッシュテーブル作成の要否を判定する処理について説明する。図7から9は、第1の実施形態に係る検索装置の作成処理の流れを示すフローチャートである。
【0034】
図7を用いて、第1の判定方法について説明する。まず、図7に示すように、作成部131は、第1のルールの種類の数をKとする(ステップS101)。第1のルールは、長さが第1の範囲に含まれるプレフィックスで表されるルールである。
【0035】
ここで、logK>2が満たされる場合(ステップS102、Yes)、作成部131は、ハッシュテーブルの作成が必要と判定する(ステップS103)。一方、logK>2が満たされない場合(ステップS102、No)、作成部131は、ハッシュテーブルの作成が不要と判定する(ステップS104)。
【0036】
図8を用いて、第2の判定方法について説明する。まず、図8に示すように、作成部131は、第1のルールの種類の数をK、第1のルール以外のルール数をMとする(ステップS201)。第1のルールは、長さが第1の範囲に含まれるプレフィックスで表されるルールである。第2のルールは、長さが第1の範囲と異なる2の範囲に含まれるプレフィックスで表されるルールである。
【0037】
ここで、log(K+M)>2+logMが満たされる場合(ステップS202、Yes)、作成部131は、ハッシュテーブルの作成が必要と判定する(ステップS203)。一方、log(K+M)>2+logMが満たされない場合(ステップS202、No)、作成部131は、ハッシュテーブルの作成が不要と判定する(ステップS204)。
【0038】
図9を用いて、第3の判定方法について説明する。まず、図9に示すように、作成部131は、第1のルールの種類の数をK、第2のルールの種類の数をLとする(ステップS301)。第1のルールは、長さが第1の範囲に含まれるプレフィックスで表されるルールである。第2のルールは、長さが第1の範囲と異なる2の範囲に含まれるプレフィックスで表されるルールである。
【0039】
ここで、log(K+L)>4が満たされる場合(ステップS302、Yes)、作成部131は、ハッシュテーブルの作成が必要と判定する(ステップS303)。一方、log(K+L)>4が満たされない場合(ステップS302、No)、作成部131は、ハッシュテーブルの作成が不要と判定する(ステップS304)。
【0040】
図10を用いて、第4の判定方法及び作成するハッシュテーブルのパターンの選定方法について説明する。まず、図10に示すように、作成部131は、第1のルールの種類の数をK、第2のルールの種類の数をL、第1のルール以外のルール数をMとする(ステップS401)。
【0041】
次に、作成部131は、d=logK−2、d=log(K+M)−(2+logM)、d=log(K+L)−4とする(ステップS402)。ここで、d、d、dがいずれも0以下である場合(ステップS403、Yes)、作成部131は、ハッシュテーブルの作成が不要と判定する(ステップS404)。
【0042】
、d、dがいずれかが0より大きい場合(ステップS403、No)、作成部131は、ハッシュテーブルの作成が必要と判定する(ステップS405)。そして、d、d、dのうちdが最大である場合、作成部131は、全てのルールが第1のルールに含まれるような第1のハッシュテーブルのパターンを選定する(ステップS407)。また、d、d、dのうちdが最大である場合、作成部131は、一部のルールが第1のルールに含まれるような第2のハッシュテーブルのパターンを選定する(ステップS408)。また、d、d、dのうちdが最大である場合、作成部131は、全てのルールが第1のルールと第2のルールのいずれかに含まれるような第3のハッシュテーブルのパターンを選定する(ステップS409)。
【0043】
なお、第1のパターンは、図3に示すハッシュテーブルのパターンである。また、第2のパターンは、図4に示すハッシュテーブルのパターンである。また、第3のパターンは、図5に示すハッシュテーブルのパターンである。
【0044】
次に、図11を用いて、検索部132による検索処理について説明する。図11は、第1の実施形態に係る検索装置の検索処理の流れを示すフローチャートである。図11に示すように、まず、検索部132は、検索対象のパケットのフィールドの値でハッシュテーブルを検索する(ステップS21)。このとき、検索部132は、フィールドの値からハッシュテーブルごとの対応する長さだけのプレフィックスを抽出し、抽出したプレフィックスのハッシュ値を計算しておく。そして、検索部132は、ハッシュテーブルにマッチしなかった部分を二分木を用いて検索する(ステップS22)。
【0045】
[第1の実施形態の効果]
記憶部12は、パケットの所定のフィールドの値のうち、所定の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを記憶する。また、検索部132は、検索対象のパケットの各フィールドの値を用いて二分木検索を行い、プレフィックスの部分については、プレフィックスから計算したハッシュ値及びハッシュテーブルを用いてハッシュ検索を行う。これにより、本実施形態では、従来は二分木を用いて行われていた検索の一部又は全部を、ハッシュテーブルを用いて行うことができるようになるため、パケットの検索を効率化することができる。
【0046】
作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kが、logK>2を満たす場合に、第1のルールを基に、長さが第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、全てのルールを1つのプレフィックス長のハッシュテーブルを用いて検索した場合に、検索が高速化されるか否かを判定することができる。
【0047】
作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、第1のルール以外のルール数Mが、log(K+M)>2+logMを満たす場合に、第1のルールを基に、第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、ルールの一部を1つのプレフィックス長のハッシュテーブルを用いて検索し、他のルールの検索にハッシュテーブルを用いなかった場合に、検索が高速化されるか否かを判定することができる。
【0048】
作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数Kと、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数Lが、log(K+L)>4を満たす場合に、第1のルールを基に、第1の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成し、第2のルールを基に、第2の範囲の下限の長さのプレフィックスのハッシュ値をインデックスとするハッシュテーブルを作成する。これにより、全てのルールを2つのプレフィックス長のハッシュテーブルを用いて検索した場合に、検索が高速化されるか否かを判定することができる。
【0049】
作成部131は、パケットの所定のフィールドの値とマッチさせるルールのうち、長さが第1の範囲に含まれるプレフィックスで表される第1のルールの種類の数をK、長さが第2の範囲に含まれるプレフィックスで表される第2のルールの種類の数をL、第1のルール以外のルール数をMとしたときに、logK>2、log(K+M)>2+logM、及びlog(K+L)>4の不等式のうち少なくともいずれかが満たされる場合、不等式のうち左辺と右辺の差が最も大きい不等式に対応したハッシュテーブルを作成する。これにより、ハッシュテーブルの作成パターンが複数考えられる場合に最適なパターンを選定することができる。
【0050】
[その他の実施形態]
本実施形態では、パケットのフィールドとしてIPアドレスを例に挙げて説明したが、検索対象のフィールドは、ポート番号等のIPアドレス以外のフィールドであってもよい。
【0051】
[システム構成等]
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部又は任意の一部が、CPU及び当該CPUにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【0052】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【0053】
[プログラム]
一実施形態として、検索装置10は、パッケージソフトウェアやオンラインソフトウェアとして上記の検索を実行する検索プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の検索プログラムを情報処理装置に実行させることにより、情報処理装置を検索装置10として機能させることができる。ここで言う情報処理装置には、スイッチやルータ等のネットワーク機器の他、デスクトップ型又はノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やPHS(Personal Handyphone System)等の移動体通信端末、さらには、PDA(Personal Digital Assistant)等のスレート端末等がその範疇に含まれる。
【0054】
図12は、検索プログラムを実行するコンピュータの一例を示す図である。コンピュータ1000は、例えば、メモリ1010、CPU1020を有する。また、コンピュータ1000は、ハードディスクドライブインタフェース1030、ディスクドライブインタフェース1040、シリアルポートインタフェース1050、ビデオアダプタ1060、ネットワークインタフェース1070を有する。これらの各部は、バス1080によって接続される。
【0055】
メモリ1010は、ROM(Read Only Memory)1011及びRAM1012を含む。ROM1011は、例えば、BIOS(Basic Input Output System)等のブートプログラムを記憶する。ハードディスクドライブインタフェース1030は、ハードディスクドライブ1090に接続される。ディスクドライブインタフェース1040は、ディスクドライブ1100に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ1100に挿入される。シリアルポートインタフェース1050は、例えばマウス1110、キーボード1120に接続される。ビデオアダプタ1060は、例えばディスプレイ1130に接続される。
【0056】
ハードディスクドライブ1090は、例えば、OS1091、アプリケーションプログラム1092、プログラムモジュール1093、プログラムデータ1094を記憶する。すなわち、検索装置10の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール1093として実装される。プログラムモジュール1093は、例えばハードディスクドライブ1090に記憶される。例えば、検索装置10における機能構成と同様の処理を実行するためのプログラムモジュール1093が、ハードディスクドライブ1090に記憶される。なお、ハードディスクドライブ1090は、SSDにより代替されてもよい。
【0057】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ1094として、例えばメモリ1010やハードディスクドライブ1090に記憶される。そして、CPU1020は、メモリ1010やハードディスクドライブ1090に記憶されたプログラムモジュール1093やプログラムデータ1094を必要に応じてRAM1012に読み出して、上述した実施形態の処理を実行する。
【0058】
なお、プログラムモジュール1093やプログラムデータ1094は、ハードディスクドライブ1090に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ1100等を介してCPU1020によって読み出されてもよい。あるいは、プログラムモジュール1093及びプログラムデータ1094は、ネットワーク(LAN(Local Area Network)、WAN(Wide Area Network)等)を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール1093及びプログラムデータ1094は、他のコンピュータから、ネットワークインタフェース1070を介してCPU1020によって読み出されてもよい。
【符号の説明】
【0059】
10 検索装置
11 入出力部
12 記憶部
13 制御部
121 ハッシュテーブル記憶部
122 二分木モデル記憶部
131 作成部
132 検索部
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】