(57)【要約】      （修正有）【課題】探索木とキャッシュとの同期に係る偽陽性判定の発生を抑制し、情報エントリの探索に要する負荷を低減可能なデータ処理装置を提供する。【解決手段】データ処理装置１は、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するルール記憶部３０と、ルールに含まれるマッチ条件の特徴に従って多次元空間を所定の方向に分割して部分空間を生成する探索木制御部１０と、部分空間に対応付けられたノードを有する探索木を記憶し、ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子をノードに関連付けて保持する探索木記憶部２０と、マッチ条件と照合すべきキーとキーに対応するノードとを関連付けて保持するキャッシュテーブル記憶部５０と、探索木記憶部２０またはキャッシュテーブル記憶部５０を参照してキーにマッチするマッチ条件を含むルールを抽出するデータ処理と、を備える。【選択図】図１
2018148247.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するルール記憶部と、
前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成する探索木制御部と、
前記部分空間に対応付けられたノードを有する探索木を記憶し、前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持する探索木記憶部と、
前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持するキャッシュテーブル記憶部と、
前記探索木記憶部または前記キャッシュテーブル記憶部を参照して、キーにマッチするマッチ条件を含むルールを抽出し、抽出したルールを用いて前記キーに対応するデータを処理するデータ処理部と、を備える、
ことを特徴とするデータ処理装置。
【請求項２】
前記所定の方向は、前記複数のルールに含まれるマッチ条件が前記多次元空間において占める領域のサイズが相対的に小さい方向である、
請求項１に記載のデータ処理装置。
【請求項３】
前記探索木制御部は、前記部分空間の前記所定の方向の幅が所定の閾値以下となるように前記多次元空間を分割する、
請求項１または２に記載のデータ処理装置。
【請求項４】
前記探索木制御部は、前記多次元空間に含まれる第１の領域において前記部分空間の前記所定の分割方向の幅が所定の第１閾値以下となるように前記多次元空間を分割するとともに、前記多次元空間に含まれる第２の領域において前記部分空間の前記所定の分割方向の幅が所定の第２の閾値以下となるように前記多次元空間を分割する、
請求項３に記載のデータ処理装置。
【請求項５】
前記探索木記憶部は、ノードに対応付けられた部分空間と少なくも一部が重なるマッチ条件を含むルールが変更された場合に更新されるカウント値を前記ノードに関連付けて保持し、
前記キャッシュテーブル記憶部は、前記キーと前記キーに対応するノードとの関連付けが参照された時点において、前記ノードに関連付けられたカウント値を前記キーおよび前記ノードに関連付けて保持し、
前記データ処理部は、前記キャッシュテーブル記憶部において前記キーに関連付けられたカウント値と、前記探索木記憶部において前記キーに対応するノードに関連付けられたカウント値とが一致する場合、前記キャッシュテーブル記憶部を参照して前記キーにマッチするマッチ条件を含むルールを抽出する、
請求項１ないし４のいずれか１項に記載のデータ処理装置。
【請求項６】
前記探索木制御部は、前記キャッシュテーブル記憶部においてノードに関連付けられたキーの数が所定の閾値以上である場合、前記ノードに対応付けられた部分空間をさらに分割して複数の部分空間を生成する、
請求項１ないし４のいずれか１項に記載のデータ処理装置。
【請求項７】
前記探索木制御部は、前記キャッシュテーブル記憶部において第１のノードに関連付けられたキーの数と第２のノードに関連付けられたキーの数の和が所定の閾値以下である場合、前記第１のノードに対応付けられた部分空間と前記第２のノードに対応付けられた部分空間を併合して単一の部分空間を生成する、
請求項１ないし６のいずれか１項に記載のデータ処理装置。
【請求項８】
前記探索木制御部は、前記複数のルールを複数の集合に分類するとともに前記複数の集合を複数のグループに分割した場合、１つのグループに所属する１つの集合に属するルールに含まれるマッチ条件の特徴を考慮する際、前記１つのグループに所属する他の集合に属するルールに含まれるマッチ条件の特徴も考慮する、
請求項１ないし７のいずれか１項に記載のデータ処理装置。
【請求項９】
コンピュータが、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するステップと、
前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成するステップと、
前記部分空間に対応付けられたノードを有する探索木を記憶するステップと、
前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持するステップと、
前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持するステップと、
前記探索木および前記ルールの識別子と前記ノートの関連付け、または、前記キーと前記ノードとの関連付けを参照して、キーにマッチするマッチ条件を含むルールを抽出するステップと、
抽出したルールを用いて前記キーに対応するデータを処理するステップと、を含む、
ことを特徴とするデータ処理方法。
【請求項１０】
それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持する処理と、
前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成する処理と、
前記部分空間に対応付けられたノードを有する探索木を記憶する処理と、
前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持する処理と、
前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持する処理と、
前記探索木および前記ルールの識別子と前記ノートの関連付け、または、前記キーと前記ノードとの関連付けを参照して、キーにマッチするマッチ条件を含むルールを抽出する処理と、
抽出したルールを用いた前記キーに対応するデータの処理と、をコンピュータに実行させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法およびプログラムに関し、特に、データ処理の一例として、受信したパケットを処理するデータ処理装置、データ処理方法およびプログラムに関する。
【背景技術】
【０００２】
イーサネット（Ethernet）（登録商標）スイッチやルータ、オープンフロー（OpenFlow）スイッチのように、一定のルールに従ってパケットを転送したり破棄したりするパケット処理装置は、パケットを受信して処理する場合、一般に以下のような処理を実行する。
【０００３】
（１）まず、通信インタフェースからパケットを受信する。
（２）次に、受信したパケットを処理するために必要な情報を検索する。
（３）最後に、検索した情報に基づき、受信したパケットを処理する。
【０００４】
上記（２）の処理は、一般に、パケット分類（Packet Classification）とも呼ばれ、予め与えられたルールセットの中から受信パケットに適合する最高優先度のルールを探索する処理である。ここで、ルールは、マッチ条件（例えば適合するアドレスの範囲）とマッチ条件に適合したパケットに対して実行すべき処理であるアクションを含む。また、ルールは、優先度や統計情報を含む場合もある。
【０００５】
非特許文献１には、探索木を用いたパケット分類（Packet Classification）方式に関する技術が開示されている。非特許文献１に記載された技術は、ｄフィールドのルール探索問題をｄ次元空間内の部分空間探索問題として捉え、探索木を辿るたびに探索空間をカットして探索領域を狭めていくことによって、受信パケットに適合するルールを見つけ出すものである。
【０００６】
非特許文献１において、探索木を構成するノードは、ｄ次元空間の部分空間を表し、ルートノードは、ｄ次元空間において採り得る全領域（初期探索領域）を表す。各ルールは、それぞれのルールが表すｄ次元部分空間と重複する部分空間を有するすべてのノードに関連付けられる。あるノードに関連付けられる(含まれる)ルールの数が、予め定めた一定数（Binth）より多い場合、当該ノードは１つまたは複数の次元においてカット（Cut）され、子ノードが作成される。このとき、カット（Cut）されたノードは、中間ノードとなる。一方、あるノードに関連付けられる(含まれる)ルールの数が、一定数（Binth）以下の場合、当該ノードはリーフ（葉）ノードとなる。
【０００７】
非特許文献１に記載された、探索木を用いた探索処理の例を図３５ないし図３７を参照して説明する。図３５は、ルールセットの一例を示す模式図である。図３５に示した例では、２フィールド（次元Ｘおよび次元Ｙの２次元）のルール探索を想定し、次元Ｘおよび次元Ｙの採り得る範囲が、それぞれ、０〜２５５および０〜１２７である場合を示す。図３５において、各矩形（角丸矩形）は、それぞれ、ルールＲ１〜Ｒ７のマッチ条件に対応する２次元部分空間を示す。矩形が重なり合う場合、矩形のすべてが表示されているルールがより高い優先度を持つものとする。例えば、ルールＲ２とルールＲ３とが重なる領域については、ルールＲ２よりもルールＲ３の優先度が高い。
【０００８】
図３６は、探索木の一例を示す模式図である。図３６は、図３５に示したルールセットのルールＲ１〜Ｒ７からルール探索を行うための探索木の一例（Binth = 2の場合）を示す。つまり、図３６は、図３５に示したルールセットの例に関して、ルートノードにおいて、Ｘ軸で４つの部分空間にカット（Cut）し、また、ノード１においてＹ軸について２つの部分空間にカット（Cut）した例を示す。なお、図３６において、楕円はルートノードと中間ノードを示す。一方、矩形（角丸矩形）はリーフノードを示す。
【０００９】
図３７は、探索木のノードに係る情報を例示する表である。図３７は、図３６の探索木の各ノードが表す部分空間および各ノードが含むルールを示す。図３７に示すように、ルートノードが表す部分空間は、探索空間全体である。したがって、ルートノードが表す部分空間は、次元Ｘおよび次元Ｙそれぞれが０≦Ｘ≦２５５および０≦Ｙ≦１２７であり、ルートノードに含まれるルールはＲ１〜Ｒ７である。また、リーフノード４については、ルートノードからリーフノード４に到達する過程において、Ｘ軸につき４つにカット（Cut）され、Ｙ軸で２つにカット（Cut）されており、かつ、Ｘ軸およびＹ軸についての各カット（Cut）におけるリーフノード４の位置は、それぞれ、第４番目および第１番目である。したがって、リーフノード４が表す部分空間は、次元Ｘおよび次元Ｙのそれぞれが１９２≦Ｘ≦２５５および０≦Ｙ≦６３であり、リーフノード４に含まれるルールはＲ５、Ｒ７である。
【００１０】
ここで、一例として、ＸおよびＹの値が、それぞれ、２３０および３０であるパケットを受信した場合のルール探索処理の例について説明する。まず、ルートノードを確認し、受信パケットのＸの値が２３０であることから、４番目の部分空間を示すノード１（１９２≦Ｘ≦２５５）に進む。次に、ノード１を確認し、受信パケットのＹの値が３０であることから、第１番目の部分空間を示すリーフノード４（０≦Ｙ≦６３）に進む。リーフノード４は、前述のように、ルールＲ５およびＲ７を含んでいる。これらのルールＲ５、Ｒ７の中から、線形探索を行い、受信パケットに対応する最高優先度を持つルールとして、例えばルールＲ７を発見する。
【００１１】
以上の探索処理の説明においては、探索木が１つである場合を例示した。一方、非特許文献１には、ルールの特徴を用いて分類することによってルールセットを複数のサブルールセットに分割し、サブルールセット毎に探索木を構築して、探索処理に使用する例が開示されている。サブルールセット毎に探索木を構築した場合、受信パケットに対するルール探索処理は、各サブルールセットの各探索木それぞれに対して実行され、得られた複数のルールの中から最高優先度のルールが選択される。なお、得られるルール数は最大でサブルールセットの数と同一である。
【００１２】
また、特許文献１（３頁）には、探索木を用いたルール探索処理の探索結果を記憶（キャッシュ）しておいて再利用することによって、探索性能を向上させる技術が開示されている。特許文献１に記載された技術においては、探索木による探索結果が、例えば、ハッシュテーブルとして実装された、完全一致のキャッシュエントリ検索用テーブルに登録される。パケット受信時に、パケットに完全一致するキャッシュエントリがキャッシュエントリ検索用テーブルに存在する場合、キャッシュエントリに記憶された探索木による探索結果が使用され、探索木を用いた探索処理は省略される。
【００１３】
ここで、探索結果がキャッシュエントリ検索用テーブルにキャッシュされて使用される構成において、ルールセットの変更（すなわち、探索木へのルールの追加、変更、削除）が行われた場合、キャッシュされている探索結果も適切に更新されなければならない。なぜなら、適切に更新されない場合、受信したパケットは変更前のルールセットにおける探索結果に従って処理されることになり、変更後のルールによる通信処理・制御を正しく行えないおそれがあるからである。
【００１４】
特許文献２（１３〜１７頁）には、探索木（ルーティングテーブル）の変更に伴って、探索木による探索結果をキャッシュしていたキャッシュエントリをキャッシュエントリ検索用テーブルから削除する場合の負荷を低減する技術が開示されている。特許文献２に記載された技術においては、ルーティングテーブルに格納された、パケットの宛先アドレスとルートとの対応関係を表すルーティングエントリにカウンタ値を設け、ルーティングエントリが更新された際には、カウンタ値をインクリメントする。
【００１５】
そして、パケットを受信し、パケットに対応するキャッシュエントリ（ルーティングテーブルの検索結果（すなわちルーティングエントリの情報）を含む）を使用して、パケットを処理する際、ルーティングエントリのカウンタ値を参照して、ルーティングエントリの更新の有無を判断する。更新が検出された場合、当該キャッシュエントリを削除する。これにより、削除すべきキャッシュエントリを特定するための負荷を低減し、キャッシュエントリを削除する負荷を低減することができる。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２０００−４１０６５号公報
【特許文献２】特許第４６４６８２３号公報
【非特許文献】
【００１７】
【非特許文献１】Balajee Vamanan、Gwendolyn Voskuilen and T.N. Vijaykumar;“EffiCuts: Optimizing Packet Classification for Memory and Throughput”、Proceedings of the ACM SIGCOMM 2010 conference、2010年、p.p.207-218
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上記特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。
【００１９】
特許文献２に開示された技術を探索木に適用する場合、一例として次のようにすることができる。
１．探索木の各ノードに更新カウンタを設け、キャッシュエントリ作成時に、当該エントリ作成に使用したノードの更新カウンタを記憶する。
２．キャッシュエントリに記憶された探索結果を使用してパケットを処理する際、キャッシュエントリ再評価処理として、当該ノードの最新の更新カウンタの値とキャッシュエントリに記憶された更新カウンタの値とを比較する。両値に差異がない場合、当該記憶された探索結果を使用する。一方、両値に差異がある場合、当該記憶された探索結果を無効と判断し、探索木の再探索を行う。
【００２０】
このように、探索結果をキャッシュしておいて再利用することにより、処理性能の向上を期待することができる。一方、最新のルールセットに基づく通信処理・制御を行うためには、探索木への変更に合わせて、キャッシュされた情報も適切に更新する（すなわち、探索木とキャッシュを同期させる）ことが必要となる。そのために、上記のように探索木のノードにカウンタ値を設け、当該カウンタ値を参照してキャッシュされた情報を更新することができる。
【００２１】
しかしながら、非特許文献１に開示された技術は、探索木を与えられたルールセットに基づき構築し、その際ノードに含まれるルールの数が一定数（Binth）以下になった場合にノードの分割を終了する。そのため、例えば、ある広い大きな部分空間に含まれるルールの数が少なく、かつ当該ルール群が疎に分布する等した場合、対応する部分空間が大きいノードが作成される可能性がある。そのようなノードが存在し、以下の条件が満たされた場合、キャッシュエントリの再評価に関し、多数の「偽陽性（False Positive）判定」が発生するおそれがある。
‐当該ノードにルールの更新が発生する
‐当該ルールが表す部分空間の大きさが当該ノードの部分空間に比べ小さい
‐当該ノードの部分空間と当該ルールが表す部分空間との差の空間に対応するキャッシュエントリが多数存在する
【００２２】
ここで、偽陽性判定とは、あるキャッシュエントリに関し、ルールの更新に伴う当該キャッシュエントリに関連する当該ノードの更新カウンタの更新を契機としてキャッシュエントリ再評価処理により探索木の再探索を実施したものの、当該キャッシュエントリに当該ルールの更新は影響せず、当該ルールの更新発生前と同一の探索結果が得られることをいう。
【００２３】
偽陽性判定が生じるメカニズムについて、図３８を参照して説明する。図３８（Ａ）は２次元のルールセットを例示する。図３８（Ｂ）は当該ルールセットに対応する探索木（Binth = 4）とキャッシュエントリとノードの対応関係を例示する。図３８（Ｂ）はノードの部分空間が大きい探索木の例を示す。ノード２（全探索空間の下半分に対応）に着目すると、キャッシュエントリが５つあり、各キャッシュエントリに対応する探索空間中の点はノード２の部分空間内に存在する。
【００２４】
ここで、図３８（Ｃ）に示すように、ルール８が追加された場合を考える。ノード２にルール８が追加されたことによりノード２の更新カウンタが増やされる。その後、各キャッシュエントリに対応するパケットが受信された場合、キャッシュエントリ再評価処理において当該更新カウンタの変化が検出され、探索木の再探索が行われる。本例の場合、その契機となったルール８は１つのキャッシュエントリにのみ影響を与えるものであり、その他４つのキャッシュエントリに関する再探索結果はルール８が追加される前と同一の結果となる。すなわち、ルール８の追加によるノード２の更新カウンタの更新は、これらの４つのキャッシュエントリに対して偽陽性判定を引き起こす。
【００２５】
このように偽陽性判定が発生すると、不必要な探索木の再探索処理を実行することになり、計算資源を浪費してしまう。
【００２６】
そこで、データ処理（例えばパケット処理）に用いる情報エントリを探索するために探索木と探索木の探索結果をキャッシュする構成において、探索木とキャッシュとの同期に係る偽陽性判定の発生を抑制し、情報エントリの探索に要する負荷を低減することが課題となる。本発明の目的は、かかる課題解決に寄与するデータ処理装置、データ処理方法、および、プログラムを提供することにある。
【課題を解決するための手段】
【００２７】
本発明の第１の態様に係るデータ処理装置は、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するルール記憶部と、前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成する探索木制御部と、前記部分空間に対応付けられたノードを有する探索木を記憶し、前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持する探索木記憶部と、前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持するキャッシュテーブル記憶部と、前記探索木記憶部または前記キャッシュテーブル記憶部を参照して、キーにマッチするマッチ条件を含むルールを抽出し、抽出したルールを用いて前記キーに対応するデータを処理するデータ処理部と、を備えている。
【００２８】
本発明の第２の態様に係るデータ処理方法は、コンピュータが、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するステップと、前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成するステップと、前記部分空間に対応付けられたノードを有する探索木を記憶するステップと、前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持するステップと、前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持するステップと、前記探索木および前記ルールの識別子と前記ノートの関連付け、または、前記キーと前記ノードとの関連付けを参照して、キーにマッチするマッチ条件を含むルールを抽出するステップと、抽出したルールを用いて前記キーに対応するデータを処理するステップと、を含む。
【００２９】
本発明の第３の態様に係るプログラムは、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持する処理と、前記複数のルールに含まれるマッチ条件の特徴に従って前記多次元空間を所定の方向に分割して部分空間を生成する処理と、前記部分空間に対応付けられたノードを有する探索木を記憶する処理と、前記ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子を前記ノードに関連付けて保持する処理と、前記複数のルールに含まれるマッチ条件と照合すべきキーと前記キーに対応するノードとを関連付けて保持する処理と、前記探索木および前記ルールの識別子と前記ノートの関連付け、または、前記キーと前記ノードとの関連付けを参照して、キーにマッチするマッチ条件を含むルールを抽出する処理と、抽出したルールを用いた前記キーに対応するデータの処理と、をコンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【００３０】
本発明に係るデータ処理装置、データ処理方法およびプログラムによると、データ処理（例えばパケット処理）に用いる情報エントリを探索するために探索木と探索木の探索結果をキャッシュする構成において、探索木とキャッシュとの同期に係る偽陽性判定の発生を抑制し、情報エントリの探索に要する負荷を低減することが可能となる。
【図面の簡単な説明】
【００３１】
【図１】一実施形態に係るデータ処理装置の構成を例示するブロック図である。
【図２】第１の実施形態に係るデータ処理装置の構成を例示するブロック図である。
【図３】第１の実施形態に係るデータ処理装置において使用されるルールの構成を例示する表である。
【図４】第１の実施形態に係るデータ処理装置において使用される探索木に係る情報、ノードに係る情報、および、ノードの分割に係る情報の構成を例示する表である。
【図５】図２に示したデータ処理装置のキャッシュテーブル記憶部に記憶される、キャッシュテーブルおよびキャッシュエントリに関する情報を例示する表である。
【図６】第１の実施形態に係るデータ処理装置の探索木制御部の詳細な構成を例示するブロック図である。
【図７】第１の実施形態に係るデータ処理装置のキャッシュテーブル制御部の詳細な構成を例示するブロック図である。
【図８】第１の実施形態に係るデータ処理装置の探索木制御部における探索木初期化部が探索木記憶部およびルール記憶部のそれぞれに記憶される探索木およびルールセットを初期化する際の動作を例示するフロー図である。
【図９】第１の実施形態に係るデータ処理装置の探索木制御部における探索木初期化部がルールセットをルールの特徴に基づいて分割する際のサブルールセットを例示する図である。
【図１０】第１の実施形態に係るデータ処理装置の探索木制御部における探索木初期化部が探索木構築処理を行う際の動作を例示するフロー図である。
【図１１】図１０のフロー図のステップＳ１１３において実行される探索木構築サブ処理Ａの詳細な動作を例示するフロー図である。
【図１２】図２に示したデータ処理装置の探索木制御部におけるルール更新部が探索木記憶部およびルール記憶部のそれぞれに記憶される探索木およびルールセットを更新する際の動作を例示するフロー図である。
【図１３】図１２のフロー図のステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作を例示するフロー図である。
【図１４】図１３のフロー図のステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作を例示するフロー図である。
【図１５】図１２のフロー図のステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作を例示するフロー図である。
【図１６】第１の実施形態に係るデータ処理装置の探索木制御部における探索木探索部が探索木記憶部およびルール記憶部のそれぞれに記憶される探索木およびルールセットを参照して与えられたキーに適合するルールを探索する際の動作を例示するフロー図である。
【図１７】図１６のフロー図のステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作を例示するフロー図である。
【図１８】第１の実施形態に係るデータ処理装置のパケット処理部がパケットを受信した際の動作を例示するフロー図である。
【図１９】第１の実施形態に係るデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ作成部がキャッシュエントリを作成する際の動作を例示するフロー図である。
【図２０】第１の実施形態に係るデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ探索部がキャッシュエントリを探索する際の動作を例示するフロー図である。
【図２１】第１の実施形態に係るデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ再評価部がキャッシュエントリを再評価する際の動作を例示するフロー図である。
【図２２】第１の実施形態の効果を説明するための、ルールセット、探索木およびルール追加を例示する模式図である。
【図２３】第２の実施形態に係るデータ処理装置の探索木制御部の詳細な構成を例示するブロック図である。
【図２４】第２の実施形態に係るデータ処理装置において使用されるノードの分割に係る情報の一構成例を説明するための表である。
【図２５】第２の実施形態における、図２に示したデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ作成部がキャッシュエントリを作成する際の動作を例示するフロー図である。
【図２６】図２５のフロー図のステップＳ２２５において実行される動的ノード分割処理の詳細な動作を例示するフロー図である。
【図２７】図２６のフロー図のステップＳ３０３において実行される動的ノード分割サブ処理Ａの詳細な動作を例示するフロー図である。
【図２８】第３の実施形態に係るデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ作成部がキャッシュエントリを作成する際の動作を例示するフロー図である。
【図２９】図２８のフロー図のステップＳ２２３ｂにおいて実行される動的ノード併合処理の詳細な動作を例示するフロー図である。
【図３０】第４の実施形態に係るデータ処理装置において使用される探索木に係る情報、探索木グループに係る情報、および、ノードの分割に係る情報の構成を例示する表である。
【図３１】第４の実施形態に係るデータ処理装置のキャッシュテーブル記憶部が保持する情報を例示する表である。
【図３２】第４の実施形態に係るデータ処理装置の探索木制御部における探索木初期化部が探索木を初期化する際の動作を例示するフロー図である。
【図３３】第４の実施形態に係るデータ処理装置の探索木制御部における探索木初期化部により作成される探索木グループを例示する表である。
【図３４】第４の実施形態に係るデータ処理装置のルール更新部の動作を例示するフロー図である。
【図３５】ルールセットの一例を示す模式図である。
【図３６】探索木の一例を示す模式図である。
【図３７】探索木のノードに係る情報の一例を示す表である。
【図３８】偽陽性判定の説明のための、ルールセット、探索木およびルール追加の一例を示す模式図である。
【発明を実施するための形態】
【００３２】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００３３】
図１は、一実施形態に係るデータ処理装置１の構成を例示するブロック図である。図１を参照すると、データ処理装置１は、それぞれ多次元空間における一部の領域に相当するマッチ条件を含む複数のルールを保持するルール記憶部３０と、複数のルールに含まれるマッチ条件の特徴に従って多次元空間を所定の方向に分割して部分空間を生成する探索木制御部１０と、部分空間に対応付けられたノードを有する探索木を記憶し、ノードに対応付けられた部分空間と少なくとも一部が重なるマッチ条件を含むルールの識別子をノードに関連付けて保持する探索木記憶部２０と、複数のルールに含まれるマッチ条件と照合すべきキーとキーに対応するノードとを関連付けて保持するキャッシュテーブル記憶部５０と、探索木記憶部２０またはキャッシュテーブル記憶部５０を参照して、キーにマッチするマッチ条件を含むルールを抽出し、抽出したルールを用いてキーに対応するデータ（例えば、パケット）を処理するデータ処理部９０と、を備えている。
【００３４】
かかるデータ処理装置１によると、探索木とキャッシュとの同期に係る偽陽性判定の発生を抑制し、情報エントリの探索に要する負荷を低減することが可能となる。なぜなら、ルールに含まれるマッチ条件の特徴に従って多次元空間を所定の方向（例えば、マッチ条件が多次元空間において占める領域のサイズが相対的に小さい方向、例えば後述の「優先分割次元」によって定義される方向（ただし、複数の次元によって定義される方向であってもよい））に分割して部分空間を生成することにより、ルールの更新に合わせて更新カウンタを更新すべきノードの数を削減することができるからである。
【００３５】
このように、データ処理装置１によると、データ処理（例えばパケット処理）に用いる情報エントリを探索するために探索木と探索木の探索結果をキャッシュする構成において、ルールセット（ルール（第１の情報エントリ）の集合）の更新時における探索木による探索結果と該探索結果をキャッシュしているキャッシュエントリ（第２の情報エントリ）との間の同期処理（キャッシュエントリの再評価処理）において、偽陽性判定の発生を抑制することができる。その結果、偽陽性判定により引き起こされる探索木再探索処理の実行を削減でき、情報エントリの探索に要する負荷を低減することができる。
【００３６】
以下、本発明によるデータ処理装置、データ処理方法およびプログラムの好適な実施形態について添付図を参照して説明する。なお、以下の説明においては、本発明によるデータ処理装置およびデータ処理方法について説明するが、かかるデータ処理方法をコンピュータにより実行可能なプログラムとして実施するようにしてもよいし、または、プログラムをコンピュータにより読み取り可能な記録媒体に記録するようにしてもよい。また、以下の各図面に付した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。
【００３７】
＜実施形態１＞
以下に記載する本実施形態の説明においては、データ処理としてパケット処理を実施し、当該データ処理に用いられる情報エントリとしてルールを使用する場合を一例として用いて説明する。また、本実施形態においては、パケットとしてＩＰｖ４（Internet Protocol version 4）パケットを扱う例を示す。しかし、本発明は、かかるパケット処理の場合に限定されるものではなく、一般的なデータ処理についても広く適用することができる。
【００３８】
［構成］
まず、第１の実施形態の構成について、図２を参照して説明する。図２は、本発明の実施形態に係るデータ処理装置の構成の一例を示すブロック図である。図２に例示するデータ処理装置１は、探索木制御部１０、探索木記憶部２０、ルール記憶部３０、キャッシュテーブル制御部４０、キャッシュテーブル記憶部５０、パケット処理部６０、通信インタフェース（ＩＦ：Interface）部７０、および、データ処理装置制御部８０を備えている。
【００３９】
データ処理装置１は、例えば、モバイル網におけるパケット処理装置であってもよく、例えば、ＬＴＥ（Long Term Evolution）のＥＰＣ（Evolved Packet Core）に使用されるパケット処理装置であってもよい。
【００４０】
探索木制御部１０は、探索木記憶部２０に記憶される探索木およびルール記憶部３０に記憶されるルールを管理し、例えば、探索木の初期化や探索、ルールの追加等を行う。
【００４１】
探索木記憶部２０は、詳細は後述するが、主に、受信パケット（すなわち処理対象のデータの一種）に対応するルール（すなわち情報エントリの一種、第１の情報エントリ）を探索するための探索木を記憶する。探索木記憶部２０に記憶される探索木は、１つまたは複数のノードによって構成され、該ノードは、中間ノードまたはリーフノードのいずれかである。探索木記憶部２０が記憶する探索木の数は、通常、２個以上であるが、１つであってもよい。探索木記憶部２０は、例えば、メモリを用いて探索木を記憶する。各探索木および各ノードには、それぞれを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作時に使用される。
【００４２】
ルール記憶部３０は、パケットを処理するための情報であるルール（すなわち、情報エントリの一種、第１の情報エントリ）の集合（ルールセット、サブルールセット）を記憶する。また、ルール記憶部３０は、各サブルールセットに収容されるルールの特徴を記憶する。ルール記憶部３０は、例えば、メモリを用いてルールの集合を記憶する。ルール記憶部３０は、例えば、配列やハッシュテーブル等のデータ構造を使用してルールの集合をメモリ上に記憶する。各ルールおよび各ルールセットや各サブルールセットには、それらを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作時に使用される。
【００４３】
キャッシュテーブル制御部４０は、キャッシュテーブル記憶部５０に記憶されるキャッシュエントリを管理し、例えば、キャッシュエントリの作成や探索等を行う。
【００４４】
キャッシュテーブル記憶部５０は、探索木による探索の結果を記憶する（キャッシュする）キャッシュエントリ（すなわち、情報エントリの一種、第２の情報エントリ）を記憶し、第２の情報エントリ記憶手段を提供する。キャッシュテーブル記憶部５０は、例えば、メモリを用いてキャッシュエントリを記憶する。キャッシュテーブル記憶部５０は、例えば、ハッシュテーブルのデータ構造を使用してキャッシュエントリをメモリ上に記憶する。各キャッシュエントリには、それぞれを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作時に使用される。
【００４５】
パケット処理部６０は、通信ＩＦ部７０からパケット（すなわち、処理対象のデータの一種）を受信し、受信したパケットの処理を行う。その際、パケット処理部６０は、探索木制御部１０およびキャッシュテーブル制御部４０を使用して、当該パケットの処理に用いる情報エントリ（ノード、ルール、キャッシュエントリ）を探索し、探索結果を用いて当該パケットを処理する。通信ＩＦ部７０は、データ処理装置１と通信ネットワーク（図２には図示していない）とを接続するためのインタフェースであり、当該通信ネットワークで使用される通信プロトコルに従ってパケットを送受信する。
【００４６】
データ処理装置制御部８０は、データ処理装置１がルールセットやサブルールセットに従ってパケットを処理するように制御する。データ処理装置制御部８０は、例えば、データ処理装置１が起動する際、後述する探索木初期化部１１（図６）に初期ルールセットを渡して初期化するように指示する。データ処理装置制御部８０は、当該初期ルールセットをデータ処理装置１が具備する記憶装置（図２には図示していない）から読み込んでもよいし、他の制御装置（図２には図示していない）から受信するようにしてもよい。また、データ処理装置制御部８０は、ユーザインタフェース（図２には図示していない）を介して、ユーザからルール更新の命令を受け取った際に、探索木制御部１０に対してルール更新を指示する。また、データ処理装置制御部８０は、他の制御装置（図２には図示していない）からルール更新の命令を受信した際に、探索木制御部１０に対してルール更新を指示するようにしてもよい。
【００４７】
次に、図２に示した本実施形態のデータ処理装置１において使用されるルールについて、図３の表を参照して説明する。図３は、図２に示したデータ処理装置１において使用されるルールの一構成例を説明するための表である。図３は、図２のデータ処理装置１のルール記憶部３０に記憶されるルールの構成例について説明している。
【００４８】
図３の表の項目３１に示すように、各ルールは、適用対象を示すデータ識別情報の一種であるマッチ条件や優先度、さらには、アクション、統計情報、削除フラグを含んでいる。各ルールのマッチ条件は、図３の表の説明３２に示すように、当該ルールに適合するパケットが持つべきフィールド値の条件を規定する。例えば、本実施形態においては、開始送信先ＩＰアドレスおよび終了送信先ＩＰアドレス、開始送信元ＩＰアドレスおよび終了送信元ＩＰアドレス、開始送信先ポート番号および終了送信先ポート番号、開始送信元ポート番号および終了送信元ポート番号、開始プロトコル番号および終了プロトコル番号の５つのフィールド（５タプル（5 Tuple））をマッチ条件（データ識別情報の一種）として使用する。
【００４９】
例えば、本実施形態においては、図３の表の例３３に示すように、マッチ条件の一例は、（開始および終了）送信先ＩＰアドレスは「０．０．０．０」〜「２５５．２５５．２５５．２５５」の範囲内であり、（開始および終了）送信元ＩＰアドレスは「１０．０．０．０」〜「１０．２５５．２５５．２５５」の範囲内である。また、（開始および終了）送信先ポート番号は「８０」であり、（開始および終了）送信元ポート番号は「０」〜「６５５３５」の範囲内である。さらに、プロトコル番号は「１７」である。ただし、本発明は、かかるフィールド構成に限定されるものではない。
【００５０】
また、各ルールの優先度は、あるパケットに対して複数のルールが適合する場合に、どのルールを採用するかを選択するために使用される。各ルールの優先度は、図３の表の説明３２に示すように、各ルールそれぞれの優先度を表す数値（例えば、非負整数）である。ここでは、一例として、大きい数値ほど高い優先度を示すものとする。例えば、図３の表の例３３に示す当該ルールの優先度の場合、非負整数「１００」が設定されている。
【００５１】
また、各ルールのアクションは、図３の表の説明３２に示すように、当該ルールに適合したパケットに対して実行すべき処理内容（処理方法）を規定する。適合したパケットに対するルールのアクションがパケットの送受信に関わる場合、図３の表の例３３に示すように、通信ＩＦ部７０に対して出力される。なお、各ルールそれぞれに含まれるアクションの数は、１つに限定されず、ゼロであってもよいし、２つ以上であってもよい。ルールに含まれるアクションの一例を、以下に示す。ただし、本発明におけるルールに含まれるアクションは、以下の処理に限定されるものではない。
【００５２】
（ａ）指定された通信ＩＦ部７０からパケットを出力する。
（ｂ）パケットの送信先ＭＡＣ（Media Access Control）アドレスを指定された値に変更する。
（ｃ）パケットの送信元ＭＡＣアドレスを指定された値に変更する。
（ｄ）パケットの送信先ＩＰアドレスを指定された値に変更する。
（ｅ）パケットの送信元ＩＰアドレスを指定された値に変更する。
（ｆ）パケットの送信先ポート番号を指定された値に変更する。
（ｇ）パケットの送信元ポート番号を指定された値に変更する。
（ｈ）パケットにＶＬＡＮ（Virtual Local Area Network）タグを追加する。
（ｉ）パケットのＶＬＡＮタグを削除する。
（ｊ）パケットのＶＬＡＮタグを変更する。
（ｋ）パケットを破棄する。
【００５３】
次に、各ルールの統計情報は、図３の表の説明３２に示すように、当該ルールに適合して、処理されたパケット群に関する統計値であり、例えば、図３の表の例３３に示すように、合計送信パケットサイズ、合計受信パケットサイズ、送信パケット数、受信パケット数等である。
【００５４】
また、各ルールの削除フラグは、図３の表の説明３２に示すように、当該ルールに関して削除が要求されたものの、当該ルールが使用中であり、削除処理が延期されているか否かを示すフラグである。
【００５５】
次に、図２に示した本実施形態のデータ処理装置１の探索木記憶部２０が記憶する探索木に係る情報、ノードに係る情報、および、ノードの分割に係る情報について、図４の表を参照して説明する。探索木記憶部２０は、探索木の集合と、ノードの集合と、ノードの分割に係る情報の集合とを記憶する。図４は、図２に示したデータ処理装置１において使用される探索木に係る情報、ノードに係る情報、および、ノードの分割に係る情報の一構成例を説明するための表である。図４は、図２のデータ処理装置１の探索木記憶部２０に記憶される探索木に係る情報、ノードに係る情報、およびノードの分割に係る情報の構成例について説明している。図４（Ａ）は、探索木に係る情報を例示する。一方、図４（Ｂ）は、ノードに係る情報を例示する。また、図４（Ｃ）は、ノードの分割に係る情報を例示する。なお、本実施形態におけるノードは、中間ノードまたはリーフノードのいずれかである。図４（Ｂ）のノード種別２４に示すように、中間ノード・リーフノードともに共通に有する情報を「中間ノード・リーフノード共通」の部分に示す。一方、中間ノードのみが有する情報を 「中間ノード」の部分に示す。また、リーフノードのみが有する情報を「リーフノード」の部分に示す。
【００５６】
図４（Ｂ）のノード種別２４の「中間ノード・リーフノード共通」において、図４（Ｂ）の項目２５に示すノードの部分空間とは、当該ノードの探索対象である、当該ノードが表す部分空間の情報である。本部分空間の情報は、図３５ないし図３７を参照して先に説明した一般的な探索木の例において、図３７の「ノードが表す部分空間」に記載の情報に該当する。図３７に示した例においては、探索空間の次元数が２次元の場合を示した。一方、本実施形態におけるルールのマッチ条件は前述のように５タプル（5 Tuple）である。すなわち、本実施形態における探索空間の次元数は５次元となる。
【００５７】
したがって、図４（Ｂ）の項目２５に示すように、図４（Ｂ）のノード種別２４の「中間ノード」において、中間ノードの「カット（Cut）する次元」および「カット（Cut）数」は、探索空間を５次元にカッティング（Cutting）して、子ノードを作成する際に使用する情報となる。例えば、図３７の例におけるルートノードに関する「カット（Cut）する次元」および「カット（Cut）数」の情報は、それぞれ、「Ｘ軸」および「４」となり、ノード１に関する「カット（Cut）する次元」および「カット（Cut）数」の情報は、それぞれ、「Ｙ軸」および「２」となる。なお、探索木の作成においては、あるノードにおいて同時に複数次元においてカット（Cut）してもよく、その場合、「カット（Cut）する次元」および「カット（Cut）数」の組は、次元毎に記憶される。
【００５８】
また、探索木に係る情報については、図４（Ａ）の種別２１に示すように、探索木それぞれに係る情報が記憶されている。探索木それぞれに係る情報としては、項目２２および説明２３に示すように、ルートとなるノード（ルートノード）を示すルートノード識別子、対応するサブルールセットを示すサブルールセット識別子を含む。
【００５９】
探索木記憶部２０は、ノードの分割に係る情報を探索木毎に記憶する。各探索木のノードの分割に係る情報は、図４（Ｃ）の項目２７に示すように、探索木識別子、優先分割次元、部分空間サイズ閾値を含む。なお、部分空間サイズ閾値は異なる部分空間に対して異なる値を使用してもよい。例えば、送信先ＩＰアドレスの次元に関し当該閾値を設定する場合、１９２．１６８．０．０／１６および１０．０．０．０／８の部分空間については当該閾値を／２４とし、それ以外の部分空間については／１６とする等してよい。部分空間ごとに異なる閾値を設定することにより、例えば、特定の部分空間にフローが密に発生することが予想される場合、当該部分空間に対してより細かく分割したノードを作成することで、偽陽性判定を減らすことができる。また、部分空間サイズ閾値は、予め与えられてもよい。その場合、部分空間サイズ閾値は、ノードを分割することにより得られる偽陽性判定減少による負荷削減量と、ノードを分割することに発生する負荷増加量(例えば、探索時間の増加)を考慮し、全体として処理負荷が軽減されるような閾値を設定してもよい。
【００６０】
次に、本実施形態において使用されるキャッシュテーブルおよびキャッシュエントリについて説明する。キャッシュエントリは、探索木を用いた、受信パケットに適合するルールの探索結果を記憶して再利用するために用いられる。探索木の探索処理への入力には、受信パケットのうちルールのマッチ条件として使用されるフィールド群（本実施形態においては５フィールド、すなわち５タプル（5 Tuple））が用いられるが、当該フィールド群の値を以下「キー」という。キーが同一のパケット群に対して同一のルールセットにおいてルール探索を行った場合、同一のルールが得られる。したがって、本実施形態においては、キーごとにキャッシュエントリを作成して使用する。なお、キーが同一のパケット群のことを、以下「フロー」という。
【００６１】
図５は、図２に示したデータ処理装置１のキャッシュテーブル記憶部５０に記憶される、キャッシュテーブルおよびキャッシュエントリに関する情報の一例を示す表である。図５（Ａ）は、キャッシュエントリに係る情報を例示する。一方、図５（Ｂ）は、キャッシュエントリノード状態を例示する。図５（Ａ）、（Ｂ）は、いずれも、本実施形態が使用するキャッシュエントリに係る情報の構成を例示する。本実施形態においては、オープン・アドレス（Open Address）型のハッシュテーブルを使用して、キャッシュエントリを記憶する例を示す。ただし、本発明は、このようなオープン・アドレス型のハッシュテーブルに限定されるものではない。
【００６２】
キャッシュテーブルのバケツリスト（Bucket List）は、例えば、キャッシュエントリの配列として実現することができ、第Ｎ番目のバケツ（Bucket）のＭ番目のキャッシュエントリには、バケツリスト（Bucket List）における第（Ｎ−１）＊（Ｍ−１）番目の要素にアクセスすることによって参照することができる。キャッシュエントリに係る情報は、図５（Ａ）の項目５１に示すように、使用中フラグ、キー、ルール識別子、最終使用時刻、および、ノード状態リストに関する情報を含む。
【００６３】
図５（Ａ）の説明５２に示すように、使用中フラグは、当該キャッシュエントリが使用中であるか否かを示すフラグであり、オンであれば使用中であることを示す。キーは、当該キャッシュエントリが表すフローに関するキーであり、ハッシュテーブル内探索用の探索キーとして使用される。また、ルール識別子は、当該キャッシュエントリに該当するパケットに適合するルールの識別子である。さらに、最終使用時刻は、当該キャッシュエントリを最後に使用した際の時刻を示す情報である。また、ノード状態リストは、図５（Ｂ）に示すような、当該キャッシュエントリが最後に使用された際の、当該キャッシュエントリが表すフローが属するノードの状態（探索木毎の）リストを示す。
【００６４】
つまり、図５（Ｂ）に示すキャッシュエントリのノード状態リストは、当該キャッシュエントリのキーを用いてルールを探索した際に最終的に到達したノード（探索木毎）の情報を記憶する。図５（Ｂ）の項目５３に示すように、キャッシュエントリのノード状態は、探索木識別子、ノード識別子、および、更新カウンタキャッシュを含む。
【００６５】
図５（Ｂ）の説明５４に示すように、ノード状態の探索木識別子は、当該ノード状態が示す探索木の識別子を示し、ノード状態のノード識別子は、当該キャッシュエントリが表すフローが当該探索木において属するノードの識別子である。また、ノード状態の更新カウンタキャッシュには、当該キャッシュエントリが最後に使用された際の、当該ノードの更新カウンタの値が記憶される。
【００６６】
次に、図２に示したデータ処理装置１の探索木制御部１０の詳細な構成について、図６のブロック図を参照して説明する。図６は、図２に示したデータ処理装置１の探索木制御部１０の詳細な構成を例示するブロック図である。図６に示すように、探索木制御部１０は、探索木初期化部１１、ルール更新部１２、探索木探索部１３、および、更新カウンタ取得部１４を備えている。
【００６７】
探索木初期化部１１は、初期状態において使用するルールセット（初期ルールセット）を基にして、探索木記憶部２０に記憶される探索木およびルール記憶部３０に記憶されるルールに係る情報を初期化する。当該初期ルールセットは、データ処理装置１が具備する記憶装置（図６には図示されていない）に予め記憶されていてもよいし、他の制御装置（図６には図示されていない）から与えられるようにしてもよい。また、探索木初期化部１１は、各探索木について当該探索木が収容するサブルールセットの特徴を参照し、ノードの分割に係る情報を決定する。
【００６８】
また、ルール更新部１２は、例えば、図２に示したデータ処理装置制御部８０からの要求を基にして、探索木記憶部２０に記憶される探索木およびルール記憶部３０に記憶されるルール（第１の情報エントリの一種）に係る情報を更新し、第１の情報エントリ更新手段を提供する。ルール更新部１２は、パラメータとして、操作種別（追加、変更、削除のいずれか）およびルールをデータ処理装置制御部８０からの要求として受け取る。データ処理装置制御部８０からの要求における操作種別がルール更新（ルール変更）の場合、該当するルールの優先度およびアクションの変更要求は可能であるが、マッチ条件は変更することができない。
【００６９】
また、探索木探索部１３は、例えば、図２に示したパケット処理部６０からの要求を基にして、指定されたキーに適合するルールを探索する。探索木探索部１３は、探索に係るパラメータとして、探索に使用すべきキー（探索キー）をパケット処理部６０から受け取る。探索木探索部１３における処理は、探索キーに適合する最高優先度のルールの識別子（最高優先度のルールが検出された場合）、および、探索木における探索において最終的に到達したノード（中間ノードまたはリーフノード）の識別子（探索木毎）のリストを要求元に返す。
【００７０】
また、更新カウンタ取得部１４は、例えば、図２に示したパケット処理部６０からの要求を基にして、指定されたノードの更新カウンタの最新の値を取得する。
【００７１】
次に、図２に示したデータ処理装置１のキャッシュテーブル制御部４０の詳細な構成について、図７のブロック図を参照して説明する。図７は、図２に示したデータ処理装置１のキャッシュテーブル制御部４０の詳細な構成を例示するブロック図である。図７に示すように、キャッシュテーブル制御部４０は、キャッシュエントリ作成部４１、キャッシュエントリ探索部４２、および、キャッシュエントリ再評価部４３を備えている。
【００７２】
キャッシュエントリ作成部４１は、例えば、図２に示したデータ処理装置１のパケット処理部６０からの要求を基にして、キャッシュエントリを作成する。また、キャッシュエントリ作成部４１は、指定されたキーに対応するバケツ（Bucket）に空きがない場合、当該バケツ（Bucket）内のキャッシュエントリを１つ削除した上で、新しいキャッシュエントリを作成する。
【００７３】
また、キャッシュエントリ探索部４２は、例えば、図２に示したデータ処理装置１のパケット処理部６０からの要求を基にして、キャッシュエントリを探索する。キャッシュエントリ探索部４２は、パラメータとしてキーを受け取り、受け取った当該キーに対応するキャッシュエントリを探索して、探索したキャッシュエントリを要求元に返す。
【００７４】
また、キャッシュエントリ再評価部４３は、例えば図２に示したデータ処理装置１のパケット処理部６０からの要求を基にして、キャッシュエントリを再評価する。キャッシュエントリ再評価部４３は、キャッシュエントリの識別子を受け取る。ここで、キャッシュエントリの再評価とは、指定されたキャッシュエントリとして記憶している探索木探索結果（当該キャッシュエントリが表すフローに適合するルール）が、最新のルールセットの状態においても有効か否かを確認し、有効でない場合、探索木の再探索を行うことである。キャッシュエントリ再評価部４３は、最新のルールセットの状態においても有効か否かの確認のために、当該キャッシュエントリとして記憶された、以下のような情報を含むノード状態リストと関連するノードの更新カウンタの最新の値を使用する。
【００７５】
（ａ）当該フローが各探索木において属するノード
（ｂ）当該キャッシュエントリが最後に使用された際の、各当該ノードの更新カウンタの値
【００７６】
［動作］
次に、図２ないし図７に例示した本実施形態のデータ処理装置１における以下の各動作について、その一例を、図面を参照しながら詳細に説明する。
（Ａ）探索木初期化処理
（Ｂ）ルール更新処理
（Ｃ）ルール探索処理
（Ｄ）パケット処理
（Ｅ）キャッシュエントリ作成処理
（Ｆ）キャッシュエントリ探索処理
（Ｇ）キャッシュエントリ再評価処理
【００７７】
＜（Ａ）探索木初期化処理＞
まず、図８ないし図１１のフロー図を参照して、探索木初期化処理の動作例について説明する。
【００７８】
図８は、図２に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１が探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールセットを初期化する際の動作を例示するフロー図である。図８のフロー図に例示する本探索木初期化処理の動作は、例えば、データ処理装置１の起動時に開始してもよいし、データ処理装置制御部８０からの初期化要求によって開始するようにしてもよい。なお、本探索木初期化処理の動作の開始に当たって、探索木制御部１０における探索木初期化部１１は、初期状態で使用するルールセット、すなわち初期ルールセットがパラメータとして与えられる。
【００７９】
図８のフロー図において、探索木初期化部１１は、まず、パラメータとして与えられた初期ルールセットを各ルールの特徴を用いてサブルールセットに分割し、ルール記憶部３０に記憶させる（ステップＳ１０１）。探索木初期化部１１は、当該分割に用いた各ルールの特徴をサブルールセット毎にルール記憶部３０に記憶させる。このようなサブルールセットへの分割は、公知の技術によって行うことができ、一例として、非特許文献１に記載された分割方法によって分割してもよい。
【００８０】
当該サブルールセットへの分割方法においては、まず、ルールのマッチ条件として使用される各フィールドについて、該当する当該フィールドにおけるマッチ条件の大小を判定する閾値を定義する。例えば、プロトコル番号フィールド（採り得る値０〜２５５）について閾値０．５を定義しておき、あるルールの（終了プロトコル番号）−（開始プロトコル番号）が、１２７（＝２５５×０．５）以上であれば、当該ルールは、プロトコル番号について大きいと判定し、１２７未満であれば、当該ルールは、プロトコル番号について小さいと判定する。
【００８１】
また、当該サブルールセットへの分割方法においては、次に、各ルールの各フィールド（５タプル（5 Tuple））についてそれぞれ大小判定を行った後、各フィールドの大小判定結果が同一のルール群を纏めて１つのサブルールセット（「サブセット」ともいう。）とする。例えば、送信先ＩＰアドレスおよび送信先ポート番号のマッチ条件のみが大きく、残りのフィールドが小さいと判定されたルール群が１つのサブルールセットを構成する。ただし、小さいフィールドの数が４以上のルール群については、纏めて１つのサブルールセットとする。
【００８２】
サブルールセットの構成例を図９に例示する。なお、図９には、便宜のために凡例を設けた。図９は、図２に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１がルールセットをルールの特徴に基づいて分割する際のサブルールセットを例示する説明図である。図９は、ルールが、送信元ＩＰアドレス（ＩＰＳ）、送信先ＩＰアドレス（ＩＰＤ）、通信プロトコル（Ｐ）、送信元ポート（ＴＰＳ）、送信先ポート（ＴＰＤ）の５つのフィールド（５タプル）から成る場合のサブルールセットの構成例を示す。なお、図９においては、各フィールドにおけるマッチ条件の指定が小さいフィールドを、ハッチングを施した四角形によって示す。
【００８３】
図９のサブルールセット構成例において、図９（ａ）は、マッチ条件の指定が５フィールド（５タプル）とも大きいルール群として「サブセット５」の１個のサブルールセットが存在する場合を示す。また、図９（ｂ）は、マッチ条件の指定が小さいフィールドの数が１個のルール群として、「サブセット１−１」〜「サブセット１−５」の５個のサブルールセットが存在する場合を示す。例えば、「サブセット１−１」の場合は、ハッチングによって示すように、送信元ＩＰアドレスのフィールドが小さいフィールドであることを示す。
【００８４】
また、図９（ｃ）は、マッチ条件の指定が小さいフィールドの数が２個のルール群として、「サブセット２−１」〜「サブセット２−１０」の１０個のサブルールセットが存在する場合を示す。例えば、「サブセット２−１」の場合、ハッチングによって示すように、送信元ＩＰアドレスと送信先ＩＰアドレスとの２つのフィールドが小さいフィールドであることを示す。
【００８５】
また、図９（ｄ）は、マッチ条件の指定が小さいフィールドの数が３個のルール群として、「サブセット３−１」〜「サブセット３−１０」の１０個のサブルールセットが存在する場合を示す。例えば、「サブセット３−１」の場合、ハッチングによって示すように、送信元ＩＰアドレスと送信先ＩＰアドレスと通信プロトコルとの３つのフィールドが小さいフィールドであることを示す。
【００８６】
また、図９（ｅ）は、マッチ条件の指定が小さいフィールドの数が４個以上のルール群として、「サブセット４」の１個のサブルールセットに纏められて収容される場合を示す。例えば、送信元ＩＰアドレスと送信先ＩＰアドレスと通信プロトコルと送信元ポートとの４つのフィールドが小さいフィールドである場合も、送信元ＩＰアドレスと送信先ＩＰアドレスと通信プロトコルと送信元ポートと送信先ポートの５つのフィールドが小さいフィールドである場合も、「サブセット４」という１つのサブルールセットに纏めて収容される。
【００８７】
図８のフロー図の説明に戻って、探索木初期化部１１は、次に、サブルールセット毎に探索木を構築する（ステップＳ１０２）。その動作の詳細については後述する。
【００８８】
次に、図８のステップＳ１０２において、探索木初期化部１１がサブルールセット毎に探索木を構築する動作の一例について、図１０および図１１のフロー図を参照して説明する。図１０は、図２に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１が探索木構築処理を行う際の動作を例示するフロー図であり、探索木初期化部１１が探索木を構築する際の動作を例示する。
【００８９】
図１０のフロー図において、探索木初期化部１１は、まず、ルール記憶部３０に記憶された当該探索木が収容するサブルールセットの特徴を参照し、ノードの分割に係る情報を決定する（ステップＳ１１１）。探索木初期化部１１は、当該探索木が収容するサブルールセットの特徴から、小さいフィールド（次元）を選択し、当該次元（群）を当該探索木のノードの分割に係る情報の優先分割次元に設定する。
【００９０】
次に、探索木初期化部１１は、構築する探索木のルートノードを割り当てる（ステップＳ１１２）。具体的には、探索木初期化部１１は、探索木記憶部２０にルートノードの情報を記憶するデータ領域を割り当てさせ、当該ルートノードについて以下のような情報を設定する。
【００９１】
（ａ）リーフノードフラグ：オフ
（ｂ）親ノード識別子    ：無効値
（ｃ）部分空間          ：下記の探索空間全体
（ｃ−１）送信先ＩＰアドレス：０．０．０．０
〜２５５．２５５．２５５．２５５
（ｃ−２）送信元ＩＰアドレス：０．０．０．０
〜２５５．２５５．２５５．２５５
（ｃ−３）プロトコル番号    ：０〜２５５
（ｃ−４）送信先ポート番号  ：０〜６５５３５
（ｃ−５）送信元ポート番号  ：０〜６５５３５
（ｄ）更新カウンタ：０
（ｅ）参照カウンタ：０
【００９２】
次に、探索木初期化部１１は、割り当てたルートノードについて、後述する探索木構築サブ処理Ａを実行する（ステップＳ１１３）。その際、探索木初期化部１１は、当該ルートノードと、処理対象のサブルールセットに含まれるすべてのルールと、をパラメータとして使用する。
【００９３】
次に、図１０のフロー図のステップＳ１１３において実行される探索木構築サブ処理Ａの詳細な動作について、図１１のフロー図を参照して説明する。図１１は、図１０のフロー図のステップＳ１１３において実行される探索木構築サブ処理Ａの詳細な動作を例示するフロー図である。本探索木構築サブ処理Ａは、パラメータとして、処理対象のノード（例えばノード識別子の形式、以下「処理対象ノード」という。）および当該ノードに含まれるルールの集合(例えば、ルール識別子のリストの形式、以下「処理対象ルールセット」という。)を受け取る。
【００９４】
図１１のフロー図において、探索木初期化部１１は、まず、処理対象ルールセットに含まれるルールの数が予め定めた一定数（Binth）以下か否かを確認する（ステップＳ１２１）。ルールの数が一定数（Binth）以下ではない場合（ステップＳ１２１のＮｏ）、処理対象ノードは中間ノードとなる。探索木初期化部１１は、処理対象ノードが表す部分空間をカット（Cut）する次元およびカット（Cut）数を決定する（ステップＳ１２２）。ここで、カット（Cut）する次元およびカット（Cut）数の決定は、当該探索木のノードの分割に係る情報を参照して、または、公知技術に基づいて行われるようにしてもよい。例えば、非特許文献１および非特許文献１が参照する文献に記載された分割方法に基づいて実施するようにしてもよい。
【００９５】
探索木初期化部１１は、例えば、処理対象ノードの部分空間のサイズが当該探索木のノードの分割に係る情報の部分空間サイズ閾値より大きい場合、当該情報を用いた分割を行い、そうでない場合、従来技術による分割を行うこととしてもよい。当該情報を用いて分割を行う場合、探索木初期化部１１は、カットする次元を、当該情報の優先分割次元のすべてまたは一部から選択する。その際、一部の次元を選択する方法、およびカット数を決定する方法には、従来技術による方法を用いてもよい。また、探索木初期化部１１は、処理対象ノードを分割することにより作成される子ノードの部分空間のサイズが当該情報の部分空間サイズ閾値以下となるようなカットする次元およびカット数の組み合わせを選択してもよい。
【００９６】
非特許文献１および非特許文献１が参照する文献に記載された当該分割方法においては、処理対象ルールセットの各ルールのマッチ条件について、処理対象ノードの部分空間との共通部分に限定する。例えば、あるルールのプロトコル番号が１０〜２０であり、処理対象ノードの部分空間のプロトコル番号が１５〜２５である場合、当該ルールのマッチ条件のプロトコル番号は１５〜２０であるものとして決定する。
【００９７】
さらに、当該分割方法においては、各次元（フィールド）について、ユニークな範囲の数を計算する。例えば、ルールが３つあり、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１６〜２０、１７〜１７である場合、ユニークな範囲の数は３となる。また、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１５〜２０、１７〜１７である場合、ユニークな範囲の数は２となる（すなわち第１番目と第２番目とは同一のプロトコル番号であるため）。そして、当該分割方法においては、全次元についてのユニークな範囲の数の平均より大きいユニークな範囲の数を有する次元を、カット（Cut）する次元として選択する。
【００９８】
また、当該分割方法においては、カット（Cut）する数の上限値を、メモリ使用量を調整するためのパラメータであるspfac（Special Factor）と処理対象ルールセットの大きさ（ルール数）とから決定する。例えば、当該分割方法においては、当該ルール数の平方根とパラメータspfacとを積算した値をカット（Cut）する数の上限値とする。そして、当該分割方法においては、カット（Cut）する数を２としたときの、各子ノードに含まれるルールの数の平均値および最大値を求める。
【００９９】
さらに、当該分割方法においては、カット（Cut）する数を増やし、そのときの各子ノードに含まれるルールの数の平均値および最大値を求める。そして、当該分割方法においては、カット（Cut）する値が上限値に達するか、または、カット（Cut）する数を増やしても、各子ノードに含まれるルールの数の平均値および最大値に大きな変化が現れなくなったときのカット（Cut）する数を、処理対象ノードをカット（Cut）する数として決定して使用する。
【０１００】
図１１のフロー図の説明に戻って、探索木初期化部１１は、次に、ステップＳ１２２において決定したカット（Cut）方法に基づき、処理対象ノードが表す部分空間をカット（Cut）した場合に得られる各部分空間について、子ノードを割り当てる（ステップＳ１２３）。具体的には、探索木記憶部２０に各子ノードの情報を記憶するデータ領域を割り当てさせ、各子ノードについて以下のような情報を設定する。
【０１０１】
（ａ）リーフノードフラグ：オフ
（ｂ）親ノード識別子    ：処理対象ノードの識別子
（ｃ）部分空間情報      ：当該子ノードが表す部分空間
（ｄ）更新カウンタ：０
（ｅ）参照カウンタ：０
【０１０２】
次に、探索木初期化部１１は、ステップＳ１２３において割り当てた各子ノードについて、探索木構築サブ処理Ａを実行する（ステップＳ１２４）。その際、探索木初期化部１１は、処理対象の子ノードと、当該子ノードに含まれるルールの集合と、をパラメータとして使用する。なお、探索木構築サブ処理Ａの結果、子ノードがリーフとなった場合、当該子ノードの割り当てを解放してもよい。その場合、処理対象ノードのノードに係る情報の子ノード識別子リストにおける当該子ノードに対応するエントリに、未割り当てを示す値を設定する。
【０１０３】
一方、ステップＳ１２１において、ルールの数が一定数（Binth）以下である場合（ステップＳ１２１のＹｅｓ）、探索木初期化部１１は、探索木記憶部２０が記憶する当該探索木に関するノードの分割に係る情報を参照し、更なる分割が必要か否かを判定する（ステップＳ１２５）。探索木初期化部１１は、処理対象ノードの部分空間のサイズが当該情報の部分空間サイズ閾値以下である場合、さらなる分割は不要と判定する。
【０１０４】
ステップＳ１２５において、さらなる分割が必要な場合には（ステップＳ１２５のＹｅｓ）、探索木初期化部１１は、ステップＳ１２２を実行する。
【０１０５】
ステップＳ１２５において、さらなる分割が必要ない場合（ステップＳ１２５のＮｏ）、探索木初期化部１１は、処理対象ノードをリーフノードとしてセットアップする（ステップＳ１２６）。具体的には、処理対象ノードについて以下のような設定変更・追加を行う。
【０１０６】
（ａ）リーフノードフラグ： オン
（ｂ）ルール識別子リスト： 当該子ノードに含まれるルールの識別子のリスト
【０１０７】
＜（Ｂ）ルール更新処理＞
次に、図１２ないし図１５のフロー図を参照して、ルール更新処理の動作例について説明する。
【０１０８】
図１２は、図２に示したデータ処理装置１の探索木制御部１０におけるルール更新部１２が探索木記憶部２０およびルール記憶部３０のそれぞれに記憶される探索木およびルールセットを更新する際の動作を一例示するフロー図である。図１２のフロー図に例示する本ルール更新処理の動作は、例えば、データ処理装置制御部８０からの要求により開始され、ルール更新処理に係るパラメータとして、ルール更新部１２は、操作種別（追加、変更、削除のいずれか）およびルール（以下、「処理対象ルール」という。）を受け取る。
【０１０９】
図１２のフロー図において、ルール更新部１２は、まず、処理対象ルールが含まれるべき、処理対象のサブルールセットを選択する（ステップＳ１３１）。該サブルールセットの選択は、処理対象ルールの特徴に基づき、図８のフロー図のステップＳ１０１によって用いられた方法と同一の方法によって行われる。
【０１１０】
次に、ルール更新部１２は、パラメータとして要求されている現在の操作がルール削除か否かを確認する（ステップＳ１３２）。
【０１１１】
要求されている現在の操作がルール削除である場合（ステップＳ１３２のＹｅｓ）、ルール更新部１２は、ルール記憶部３０に記憶されている処理対象ルールの削除フラグをオンに設定した後（ステップＳ１３４）、ステップＳ１３５に移行する。
【０１１２】
一方、要求されている現在の操作がルール削除ではない場合（ステップＳ１３２のＮｏ）、ルール更新部１２は、処理対象のサブルールセットをパラメータによる要求に従って更新した後（ステップＳ１３３）、ステップＳ１３５に移行する。具体的な更新処理としては、ルール追加の場合、ルール更新部１２は、ルール記憶部３０に処理対象サブルールセットの一要素として処理対象ルールを新たに記憶させる。また、ルール変更の場合には、ルール更新部１２は、ルール記憶部３０に処理対象サブルールセットの一要素として記憶されている処理対象ルールの情報（優先度およびアクション）を変更する。
【０１１３】
次に、ルール更新部１２は、パラメータとして要求されている現在の操作がルール追加か否かを確認する（ステップＳ１３５）。
【０１１４】
要求されている現在の操作がルール追加である場合（ステップＳ１３５のＹｅｓ）、ルール更新部１２は、処理対象サブルールセットの探索木（すなわち処理対象探索木）のルートノードについて、後述するルール更新サブ処理Ａ１を実行する（ステップＳ１３６）。
【０１１５】
一方、要求されている現在の操作がルール追加ではない場合（ステップＳ１３５のＮｏ）、ルール更新部１２は、処理対象探索木のルートノードについて、後述するルール更新サブ処理Ｂを実行する（ステップＳ１３７）。
【０１１６】
詳細は後述するが、ステップＳ１３６のルール更新サブ処理Ａ１およびステップＳ１３７のルール更新サブ処理Ｂにより、処理対象探索木の、処理対象ルールを含んでいるノードの更新カウンタが更新される。
【０１１７】
次に、図１２のフロー図のステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作について、図１３のフロー図を参照して説明する。図１３は、図１２のフロー図のステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作を例示するフロー図である。本ルール更新サブ処理Ａ１においては、パラメータとして、処理対象のノード（処理対象ノード）および当該ノードに追加するルール(処理対象ルール)を受け取る。
【０１１８】
図１３のフロー図において、ルール更新部１２は、まず、処理対象ノードがリーフノードか否かを確認する（ステップＳ１４１）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。
【０１１９】
処理対象ノードがリーフノードではない場合（ステップＳ１４１のＮｏ）、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ１４２）。ある子ノードが処理対象ルールを含んでいるか否かは、当該子ノードが表す部分空間と、処理対象ルールのマッチ条件が表す部分空間とに重なりがあるか否か（すなわち、共通部分があるか否か）によって判定することができる。
【０１２０】
次に、ルール更新部１２は、ステップＳ１４２において選択された各子ノード（未割り当ての子ノードを含む）それぞれについて、後述するルール更新サブ処理Ａ２を実行する（ステップＳ１４３）。その際、ルール更新部１２は、パラメータとして、選択された子ノード（新しい処理対象ノードとして）と、現在の処理対象ノード（新しい処理対象ノードの親ノードとして）と、処理対象ルールと、を使用する。
【０１２１】
次に、ルール更新部１２は、ステップＳ１４３において１回または複数回実行されたルール更新サブ処理Ａ２のいずれかにおいて新規に割り当てられた子ノードがあるか否かを確認する（ステップＳ１４４）。
【０１２２】
その確認結果、新規に割り当てられた子ノードがない場合（ステップＳ１４４のＮｏ）、ルール更新部１２は、本ルール更新サブ処理Ａ１を終了する。
【０１２３】
一方、新規に割り当てられた子ノードがある場合（ステップＳ１４４のＹｅｓ）、ルール更新部１２は、処理対象ノードの更新カウンタを更新する（ステップＳ１４５）。具体的には、ルール更新部１２は、処理対象ノードの更新カウンタの値を、現在の値に「１」を加えたものに変更する。
【０１２４】
また、ステップＳ１４１において、処理対象ノードがリーフノードである場合（ステップＳ１４１のＹｅｓ）、ルール更新部１２は、ルール追加後の処理対象ノード（リーフノード）に対応するルールの数が予め定めた一定数（Binth）以下か否かを確認する（ステップＳ１４６）。
【０１２５】
ルールの数が該一定数（Binth）以下である場合（ステップＳ１４６のＹｅｓ）、ルール更新部１２は、処理対象ノード（リーフノード）のルール識別子リストに処理対象ルールの識別子を追加した後（ステップＳ１４７）、前述したステップＳ１４５に移行する。
【０１２６】
一方、ルールの数が該一定数（Binth）以下ではない場合（ステップＳ１４６のＮｏ）、ルール更新部１２は、処理対象ノード（リーフノード）を中間ノード化し、新たに、子ノードを作成した後（ステップＳ１４８）、前述したステップＳ１４５に移行する。ステップＳ１４８においては、具体的には、ルール更新部１２は、処理対象ノードのリーフノードフラグをオフに変更する。さらに、子ノードを作成するために、ルール更新部１２は、処理対象ノードの識別子と、処理対象ノードのルール識別子リストに処理対象ルールの識別子を加えたルールセットと、をパラメータとして、図１１を参照して説明した探索木構築サブ処理Ａを実行する。
【０１２７】
次に、図１３のフロー図のステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作について、図１４のフロー図を参照して説明する。図１４は、図１３のフロー図のステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作を例示するフロー図である。本ルール更新サブ処理Ａ２においては、パラメータとして、処理対象のノード（処理対象ノード）と、処理対象ノードの親ノードの識別子と、処理対象ノードが表す部分空間と、当該ノードに追加するルール(処理対象ルール)と、を受け取る。
【０１２８】
図１４のフロー図において、ルール更新部１２は、まず、処理対象ノードのためのデータ領域が割り当て済みか否かを確認する（ステップＳ１５１）。
【０１２９】
データ領域が割り当て済みである場合（ステップＳ１５１のＹｅｓ）、ルール更新部１２は、処理対象ノードおよび処理対象ルールをパラメータとして、図１３に示したルール更新サブ処理Ａ１を実行する（ステップＳ１５２）。
【０１３０】
一方、データ領域が割り当て済みではない場合（ステップＳ１５１のＮｏ）、ルール更新部１２は、処理対象ノードのためのデータ領域を割り当て、リーフノードとしてセットアップする（ステップＳ１５３）。具体的には、ルール更新部１２は、探索木記憶部２０に処理対象ノードの情報を記憶するデータ領域を割り当てさせ、当該ノードについて以下のような情報を設定する。
【０１３１】
（ａ）リーフノードフラグ：オン
（ｂ）親ノード識別子    ：パラメータとして与えられた親ノード識別子
（ｃ）部分空間          ：パラメータとして与えられた部分空間
（ｄ）更新カウンタ：０
（ｅ）参照カウンタ：０
（ｆ）ルール識別子リスト：処理対象ルールの識別子
【０１３２】
次に、図１２のフロー図のステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作について、図１５のフロー図を参照して説明する。図１５は、図１２のフロー図のステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作を例示するフロー図である。本ルール更新サブ処理Ｂにおいては、パラメータとして、処理対象のノード（処理対象ノード）と、削除または変更するルール(処理対象ルール)と、を受け取る。
【０１３３】
図１５のフロー図において、ルール更新部１２は、まず、処理対象ノードがリーフノードか否かを確認する（ステップＳ１６１）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。
【０１３４】
処理対象ノードがリーフノードではない場合（ステップＳ１６１のＮｏ）、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ１６２）。ある子ノードが処理対象ルールを含んでいるか否かは、当該子ノードが表す部分空間と、処理対象ルールのマッチ条件が表す部分空間とに重なりがあるか否か（すなわち、共通部分があるか否か）によって判定することができる。
【０１３５】
次に、ルール更新部１２は、ステップＳ１６２において選択された各子ノード（割り当て済みの子ノードのみ）それぞれについて、ルール更新サブ処理Ｂを実行する（ステップＳ１６３）。
【０１３６】
ステップＳ１６１において、処理対象ノードがリーフノードである場合（ステップＳ１６１のＹｅｓ）、ルール更新部１２は、処理対象ノード（リーフノード）のルール識別子リストを更新する（ステップＳ１６４）。具体的には、要求されている現在の操作がルール削除である場合、ルール更新部１２は、処理対象ルールの識別子を当該ルール識別子リストから削除する。一方、要求されている現在の操作がルール更新である場合、本動作を省略することができる。次に、ルール更新部１２は、処理対象ノード（リーフノード）の更新カウンタを更新する（ステップＳ１６５）。具体的には、ルール更新部１２は、処理対象ノード（リーフノード）の更新カウンタの値を、現在の値に「１」を加えたものに変更する。
【０１３７】
＜（Ｃ）ルール探索処理＞
次に、図１６および図１７のフロー図を参照して、ルール探索処理の動作例について説明する。図１６は、図２に示したデータ処理装置１の探索木制御部１０における探索木探索部１３が探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールセットを参照して与えられたキーに適合するルールを探索する際の動作を例示するフロー図である。図１６のフロー図に例示する本ルール探索処理の動作は、例えば、パケット処理部６０からの要求により開始され、本ルール探索処理に係るパラメータとして、探索木探索部１３は、探索に使用すべきキー（探索キー）を受け取る。本ルール探索処理においては、探索木探索部１３は、パラメータとして与えられた探索キーに適合する最高優先度のルールの識別子（探索された場合）、および、探索木における探索において最終的に到達したノード（中間ノードもしくはリーフノード）の識別子（探索木毎）のリストを、要求元例えばパケット処理部６０に返す。
【０１３８】
図１６のフロー図において、探索木探索部１３は、まず、各探索木について、後述するルール探索サブ処理Ａを実行する（ステップＳ１８１）。
【０１３９】
次に、探索木探索部１３は、ステップＳ１８１において得られた、各探索木内で発見されたルールの集合の中から最高優先度のルールを選択し、パラメータとして受け取った探索キーに適合するルールとして要求元に返す（ステップＳ１８２）。また、探索木探索部１３は、ステップＳ１８１において各探索木について得られる、探索で最終的に到達したノード（中間ノードもしくはリーフノード）の識別子（探索木毎）のリストも要求元に返す。
【０１４０】
次に、図１６のフロー図のステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作について、図１７のフロー図を参照して説明する。図１７は、図１６のフロー図のステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作を例示するフロー図である。本ルール探索サブ処理Ａにおいては、パラメータとして、処理対象の探索木（例えば、探索木識別子の形式、以下「処理対象探索木」という。）および探索に使用すべきキー（探索キー）を受け取る。また、本ルール探索サブ処理Ａにおいては、探索の結果、探索されたルールおよび探索により最終的に到達したノードの識別子を要求元に返す。なお、本ルール探索サブ処理Ａにおいて処理の対象としているノードを「処理対象ノード」という。
【０１４１】
図１７のフロー図において、探索木探索部１３は、まず、処理対象ノードとして処理対象探索木のルートノードを選択する（ステップＳ１９１）。
【０１４２】
次に、探索木探索部１３は、処理対象ノードがリーフノードか否かを確認する（ステップＳ１９２）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。
【０１４３】
処理対象ノードがリーフノードではない場合（ステップＳ１９２のＮｏ）、探索木探索部１３は、パラメータとして受け取った探索キーに対応する子ノードを選択する（ステップＳ１９３）。
【０１４４】
次に、探索木探索部１３は、ステップＳ１９３において選択した子ノードに対してデータ領域が割り当て済みか否かを確認する（ステップＳ１９４）。
【０１４５】
データ領域が割り当て済みである場合（ステップＳ１９４のＹｅｓ）、探索木探索部１３は、処理対象ノードとして当該子ノードを選択して（ステップＳ１９５）、ステップＳ１９２に復帰する。
【０１４６】
一方、ステップＳ１９４において、データ領域が割り当て済みではない場合（ステップＳ１９４のＮｏ）、探索木探索部１３は、探索キーに対応するルールは存在しないため、本探索において最終的に到達したノードを現在の処理対象ノードとして本ルール探索サブ処理Ａを終了する。
【０１４７】
また、ステップＳ１９２において、処理対象ノードがリーフノードである場合（ステップＳ１９２のＹｅｓ）、探索木探索部１３は、処理対象ノード（リーフノード）のルール識別子リストを基にして、ルール記憶部３０を参照して、本リーフノードに関係するルールを取得する（ステップＳ１９６）。さらに、探索木探索部１３は、例えば、当該ルール群内において線形探索処理を実施して、当該ルール群の中から探索キーに適合する最高優先度のルールを選択し、探索キーに適合するルールとして出力することにより、本ルール探索サブ処理Ａを終了する。この場合、本探索で最終的に到達したノードは、現在の処理対象ノード（リーフノード）となる。
【０１４８】
＜（Ｄ）パケット処理＞
次に、図１８のフロー図を参照して、パケット処理の動作例について説明する。図１８は、図２に示したデータ処理装置１のパケット処理部６０がパケットを受信した際の動作を例示するフロー図である。図１８のフロー図に例示する本パケット処理の動作は、データ処理装置１の通信ＩＦ部７０がパケット（処理対象パケット）を受信し、パケット処理部６０にパケットの受信通知がなされた際に開始される。
【０１４９】
図１８のフロー図において、パケット処理部６０は、まず、受信した処理対象パケットからルール探索に使用するためのキー（探索キー）を抽出する（ステップＳ２０１）。具体的には、パケット処理部６０は、受信したパケットから、送信元ＩＰアドレス、送信先ＩＰアドレス、プロトコル番号、送信元ポート番号、送信先ポート番号を探索キーとして取り出す。
【０１５０】
次に、パケット処理部６０は、ステップＳ２０１において抽出された探索キーをパラメータとして、図７に示すキャッシュテーブル制御部４０のキャッシュエントリ探索部４２に依頼して、キャッシュエントリを探索する（ステップＳ２０２）。
【０１５１】
パケット処理部６０は、キャッシュエントリ探索部４２に対する依頼結果として、パラメータとして引き渡した探索キーに対応するキャッシュエントリ（処理対象キャッシュエントリ）が検出されたか否かを確認する（ステップＳ２０３）。
【０１５２】
処理対象キャッシュエントリが検出された場合（ステップＳ２０３のＹｅｓ）、パケット処理部６０は、図７に示すキャッシュテーブル制御部４０のキャッシュエントリ再評価部４３に依頼して、当該処理対象キャッシュエントリの再評価を行う（ステップＳ２０４）。キャッシュエントリ再評価部４３は、再評価の結果として、当該処理対象キャッシュエントリが更新されたか（探索キーに適合するルールが検出された場合）、または、削除されたか（探索キーに適合するルールが検出されなかった場合）、のいずれかを返してくる。
【０１５３】
パケット処理部６０は、キャッシュエントリ再評価部４３からの再評価の結果を受け取ると、ステップＳ２０４において探索キーに適合するルールが検出されたか否かを確認する（ステップＳ２０５）。
【０１５４】
探索キーに適合するルールが検出された場合（ステップＳ２０５のＹｅｓ）、パケット処理部６０は、当該適合ルールのアクションに従い、処理対象パケットを処理する（ステップＳ２０６）。
【０１５５】
一方、ステップＳ２０５において、探索キーに適合するルールが検出されない場合（ステップＳ２０５のＮｏ）、パケット処理部６０は、処理対象パケットについて、適合ルールが不明の場合の処理を実行する（ステップＳ２０７）。具体的には、例えば、パケット処理部６０は、以下に示すいずれか、または、組み合わせの処理を実行する。
【０１５６】
（ａ）当該パケットを破棄する。
（ｂ）当該パケットの適合ルールが不明の旨をログ出力する。
（ｃ）当該パケットの適合ルールが不明の旨をデータ処理装置制御部８０に通知する。
（ｄ）当該パケットの適合ルールが不明の旨を他の装置（例えば、ネットワーク管理装置。図２ないし図７には図示されていない）に通知する。
【０１５７】
また、ステップＳ２０３において、処理対象キャッシュエントリが検出されない場合（ステップＳ２０３のＮｏ）、パケット処理部６０は、図６に示す探索木制御部１０の探索木探索部１３に依頼して、探索キーに適合するルールを探索する（ステップＳ２０８）。
【０１５８】
次に、探索木探索部１３への依頼結果として、探索キーに適合するルールが探索されたか否かを確認する（ステップＳ２０９）。
【０１５９】
探索キーに適合するルールが探索されない場合（ステップＳ２０９のＮｏ）、パケット処理部６０は、ステップＳ２０７へ移行して、前述のような適合ルールが不明の場合の処理を実行する。
【０１６０】
一方、探索キーに適合するルールが探索された場合（ステップＳ２０９のＹｅｓ）、パケット処理部６０は、図７に示すキャッシュテーブル制御部４０のキャッシュエントリ作成部４１に依頼して、当該処理対象パケットを処理するためのキャッシュエントリを作成して、キャッシュテーブル記憶部５０に記憶させる（ステップＳ２１０）。なお、キャッシュエントリ作成部４１に依頼する際、パケット処理部６０は、パラメータとして、ステップＳ２０１において抽出した探索キーと、ステップＳ２０８において発見されたルールの識別子と、ステップＳ２０８において探索木探索部１３から返されたノード識別子のリストと、をキャッシュエントリ作成部４１に引き渡す。
【０１６１】
次に、パケット処理部６０は、ステップＳ２０６に移行して、ステップＳ２０８において探索された適合ルールが示すアクションに従って、処理対象パケットを処理する。
【０１６２】
＜（Ｅ）キャッシュエントリ作成処理＞
次に、図１９のフロー図を参照して、キャッシュエントリ作成処理の動作例について説明する。図１９は、図２に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ作成部４１がキャッシュエントリを作成する際の動作を例示するフロー図である。図１９のフロー図に例示する本キャッシュエントリ作成処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ作成部４１は、本キャッシュエントリ作成処理に係るパラメータとして、キー（探索キー）と、ルール識別子と、キーを用いた探索木の探索において最終的に到達したノードの識別子（探索木毎）と、を受け取る。
【０１６３】
図１９のフロー図において、キャッシュエントリ作成部４１は、まず、パラメータとして受け取ったキーのハッシュ値を計算し、計算結果を基にして、当該キーに対応するハッシュテーブルのバケツ（Bucket）を選択する（ステップＳ２２１）。
【０１６４】
次に、キャッシュエントリ作成部４１は、ステップＳ２２１において選択したバケツ（Bucket）に空きがあるか否かを確認する（ステップＳ２２２）。バケツ（Bucket）の空きの有無は、当該バケツ（Bucket）内の各キャッシュエントリについて、使用中フラグを確認することによって確認することができる。
【０１６５】
選択したバケツ（Bucket）に空きがある場合（ステップＳ２２２のＹｅｓ）、ステップＳ２２４に移行する。
【０１６６】
一方、選択したバケツ（Bucket）に空きがない場合（ステップＳ２２２のＮｏ）、キャッシュエントリ作成部４１は、当該バケツ（Bucket）内の各キャッシュエントリのうち、いずれか１つのキャッシュエントリを削除した後（ステップＳ２２３）、ステップＳ２２４に移行する。ここで、キャッシュエントリ作成部４１は、キャッシュエントリの使用中フラグをオフに設定することによってキャッシュエントリを削除することができる。その際、当該キャッシュエントリの適合ルールの参照カウンタを１減らす。さらに、当該キャッシュエントリのノード状態リストで参照される各ノードの参照カウンタをそれぞれ１減らす。また、キャッシュエントリ作成部４１は、例えば、最終使用時刻が最も古いキャッシュエントリを削除対象として選択するようにすればよい。
【０１６７】
ステップＳ２２４においては、キャッシュエントリ作成部４１は、当該バケツ（Bucket）内の空きキッシュエントリの１つを選択して、セットアップする（ステップＳ２２４）。具体的には、キャッシュエントリ作成部４１は、選択したキャッシュエントリに対して、以下のような情報を設定する。また、パラメータとして与えられたルールの参照カウンタを１増やす。また、パラメータとして与えられた各ノードの参照カウンタを１増やす。
【０１６８】
（ａ）使用中フラグ：オン
（ｂ）キー：パラメータとして与えられたキー
（ｃ）ルール識別子：パラメータとして与えられたルールの識別子
（ｄ）最終使用時刻：処理実行時点における時刻
（ｅ）ノード状態．ノード識別子 (探索木毎)：パラメータとして与えられたノード識別子
（ｆ）ノード状態．更新カウンタキャッシュ (探索木毎)：前記ノード識別子を基に図７に示す更新カウンタ取得部１４に依頼して取得した値
【０１６９】
＜（Ｆ）キャッシュエントリ探索処理＞
次に、図２０のフロー図を参照して、キャッシュエントリ探索処理の動作例について説明する。図２０は、図２に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ探索部４２がキャッシュエントリを探索する際の動作を例示するフロー図である。図２０のフロー図に例示する本キャッシュエントリ探索処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ作成部４１は、本キャッシュエントリ探索処理に係るパラメータとして、キー（探索キー）を受け取る。
【０１７０】
図２０のフロー図において、キャッシュエントリ探索部４２は、まず、パラメータとして受け取ったキーのハッシュ値を計算し、計算結果を基にして、当該キーに対応するハッシュテーブルのバケツ（Bucket）を選択する（ステップＳ２３１）。
【０１７１】
次に、キャッシュエントリ探索部４２は、ステップＳ２３１において選択したバケツ（Bucket）内の最初のキャッシュエントリを選択する（ステップＳ２３２）。
【０１７２】
次に、キャッシュエントリ探索部４２は、選択したキャッシュエントリの使用中フラグがオンで、かつ、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致するか否かを確認する（ステップＳ２３３）。
【０１７３】
キャッシュエントリの使用中フラグがオンで、かつ、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致した場合（ステップＳ２３３のＹｅｓ）、キャッシュエントリ探索部４２は、キーに合致するキャッシュエントリの探索に成功した場合として、本キャッシュエントリ探索処理を終了し、探索の結果として、当該キャッシュエントリの識別子を要求元に返す。
【０１７４】
一方、ステップＳ２３３において、キャッシュエントリの使用中フラグがオフ、または、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致しない場合（ステップＳ２３３のＮｏ）、キャッシュエントリ探索部４２は、選択したキャッシュエントリがバケツ（Bucket）内の最後のキャッシュエントリか否かを確認する（ステップＳ２３４）。
【０１７５】
バケツ（Bucket）内の最後のキャッシュエントリである場合（ステップＳ２３４のＹｅｓ）、キャッシュエントリ探索部４２は、本キャッシュエントリ探索処理を終了し、探索の結果として、キーに合致するキャッシュエントリを探索することができなかったことを要求元に通知する。
【０１７６】
一方、ステップＳ２３４において、バケツ（Bucket）内の最後のキャッシュエントリではない場合（ステップＳ２３４のＮｏ）、キャッシュエントリ探索部４２は、バケツ（Bucket）内の次のキャッシュエントリを選択して（ステップＳ２３５）、ステップＳ２３３に移行する。
【０１７７】
＜（Ｇ）キャッシュエントリ再評価処理＞
次に、図２１のフロー図を参照して、キャッシュエントリ再評価処理の動作例について説明する。図２１は、図２に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ再評価部４３がキャッシュエントリを再評価する際の動作を例示するフロー図である。図２１のフロー図に例示する本キャッシュエントリ再評価処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ再評価部４３は、本キャッシュエントリ再評価処理に係るパラメータとして、再評価対象のキャッシュエントリ（処理対象キャッシュエントリ）の識別子を受け取る。
【０１７８】
図２１のフロー図において、キャッシュエントリ再評価部４３は、まず、処理対象キャッシュエントリのノード状態リストを参照し、図６に示す探索木制御部１０の更新カウンタ取得部１４に依頼して、処理対象キャッシュエントリが表すフローが属するノードの最新の更新カウンタ値（探索木毎）を取得する（ステップＳ２４１）。
【０１７９】
次に、キャッシュエントリ再評価部４３は、ステップＳ２４１おいて取得された最新の更新カウンタ値とキャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各探索木の更新カウンタ値との間に差分があるか否かを確認する（ステップＳ２４２）。
【０１８０】
最新の更新カウンタ値とキャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各探索木の更新カウンタ値との間に差分がない場合（ステップＳ２４２のＮｏ）、ステップＳ２４５に移行する。
【０１８１】
一方、いずれかの探索木に関し、最新の更新カウンタ値とキャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する探索木の更新カウンタ値との間に差分がある場合（ステップＳ２４２のＹｅｓ）、キャッシュエントリ再評価部４３は、当該処理対象キャッシュエントリのうち、適合ルール、および更新カウンタ値に差分があった探索木のノードに係る情報、は無効であると判定して、図６に示す探索木制御部１０の探索木探索部１３に依頼して、当該処理対象キャッシュエントリのキーに適合するルールを再度探索し直す（ステップＳ２４３）。このとき、キャッシュエントリ再評価部４３は、ステップＳ２４２において得られた、更新カウンタ値に差分があった探索木の識別子のリストを探索木探索部１３に引き渡し、当該探索木の識別子のリストを受け取った探索木探索部１３は、探索対象を当該探索木に限定して探索処理を行うようにしてもよい。また、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのノード状態リストに含まれるノード識別子のリストを探索木探索部１３に引き渡し、当該ノード識別子のリストを受け取った探索木探索部１３は、探索木の探索処理をルートノードからではなく受け取ったノード識別子によって識別されるノードから始めるようにしてもよい。
【０１８２】
次に、キャッシュエントリ再評価部４３は、ステップＳ２４３において探索されたルールの情報を基にして、処理対象キャッシュエントリを更新する（ステップＳ２４４）。具体的には、ステップＳ２４３においてキーに適合するルールを探索することができなかった場合には、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリの使用中フラグをオフに設定し、処理対象キャッシュエントリを削除する。その際、以前の適合ルールの参照カウンタを１減らす。さらに、ノード状態リストで参照する各ノードの参照カウンタをそれぞれ１減らす。
【０１８３】
一方、キーに適合するルールを探索することができた場合、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのルール識別子に、探索された当該適合ルールの識別子を設定する。その際、以前の適合ルールの参照カウンタを１減らし、新しい適合ルールの参照カウンタを１増やす。さらに、以前のノード状態リストが参照する各ノードの参照カウンタをそれぞれ１減らし、新しいノード状態リストが参照する各ノードの参照カウンタをそれぞれ１増やす。また、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリの最終使用時刻に、処理時点の時刻を設定する。さらに、キャッシュエントリ再評価部４３は、ステップＳ２４１において取得した最新の更新カウンタ値を処理対象キャッシュエントリの更新カウンタキャッシュに記憶する。
【０１８４】
また、ステップＳ２４２において、最新の更新カウンタ値と処理対象キャッシュエントリに記憶された各探索木の更新カウンタ値との間に差分がない場合（ステップＳ２４２のＮｏ）、キャッシュエントリ再評価部４３は、当該処理対象キャッシュエントリは有効であるものと評価して、処理対象キャッシュエントリの最終使用時刻を処理実行時点の時刻に設定する（ステップＳ２４５）。
【０１８５】
また、キャッシュエントリ再評価部４３は、本キャッシュエントリ再評価処理を終了する際に、処理対象キャッシュエントリが更新されたか（キーに適合するルールを探索できた場合）、あるいは、削除されたか（キーに適合するルールを探索できなかった場合）、のいずれかを示す情報を要求元に返す。
【０１８６】
［効果］
以上に詳細に説明したように、本実施形態においては、次のような効果が得られる。
【０１８７】
本実施形態によれば、図６に示す探索木制御部１０の探索木初期化部１１は、ルールセットをルールの特徴に基づいてサブルールセットに分割して、サブルールセット毎に探索木を構築する。また、探索木初期化部１１は、探索木毎に、当該探索木に収容されるサブルールセットの特徴を参照し、小さいフィールド（次元）を優先して分割すべき次元として選択し、ノードの分割に係る情報として探索木記憶部２０に記憶させる。さらに、探索木初期化部１１は、探索木の構築におけるノードの分割において、優先して分割すべき次元（ノードの分割に係る情報の一部）を優先的に用いて分割し、かつ、ノードの部分空間のサイズが所定の閾値（ノードの分割に係る情報の一部）以下となるまで分割を継続する。また、図２に示す探索木記憶部２０が記憶する探索木のノードは、更新カウンタに関する情報を有している。
【０１８８】
また、図６に示す探索木制御部１０のルール更新部１２は、ルール更新（追加、変更、削除）に際し、処理対象ルールのマッチ条件が表す部分空間と重複する部分空間を表しているノード（群）に関し、処理対象ルールが含まれるサブルールセットに対する探索木における当該ノードの更新カウンタを更新する。また、図２に示すキャッシュテーブル記憶部５０が記憶するキャッシュエントリは、当該キャッシュエントリが表すフローが属するノードの情報（探索木毎；ノードの更新カウンタのキャッシュを含む情報）を有し、当該情報は、キャッシュエントリ作成部４１およびキャッシュエントリ再評価部４３によって当該キャッシュエントリが使用される毎に更新される。また、ルール更新部１２は、ルールの追加において発生するノードの分割に際し、優先して分割すべき次元（ノードの分割に係る情報の一部）を優先的に用いて分割する。
【０１８９】
また、図２に示すパケット処理部６０は、受信パケットを処理する際、当該パケット（フロー）用のキャッシュエントリが存在する場合、当該キャッシュエントリを再評価した上で使用する。
【０１９０】
また、図７に示すキャッシュテーブル制御部４０のキャッシュエントリ再評価部４３は、キャッシュエントリが表すフローが属するノード（群）に関し、記憶されている更新カウンタキャッシュの値（更新履歴情報のキャッシュの一種）と当該ノードの最新の更新カウンタの値（最新の更新履歴情報の一種）とを比較し、両者に不整合がある場合には、適合するルールの再探索が必要であると判断する。
【０１９１】
よって、本実施形態によれば、データ処理（例えばパケット処理）に用いる情報エントリを探索するために探索木と当該探索木の探索結果をキャッシュする構成において、ルールセット（情報エントリの集合の一種）の更新時における探索木による探索結果（第１の情報エントリ）と該探索結果をキャッシュしているキャッシュエントリ（第２の情報エントリ）との間の同期処理（キャッシュエントリの再評価処理）において、偽陽性判定の発生を抑制することができる。その結果、偽陽性判定により引き起こされる探索木再探索処理の実行を削減でき、情報エントリの探索に要する負荷を低減することができる。
【０１９２】
これは、ノードの分割に係る情報を用いてノードが分割されたことにより、特にリーフノードにおいて対応する部分空間のサイズが小さくなり、その結果あるノードの更新カウンタが更新されたことにより再評価が開始されるキャッシュエントリの数が少なくなることによる。また、探索木が収容するサブルールセットの特徴を参照して決定された、優先して分割に使用すべき次元（ノードの分割に係る情報の一部）を分割に使用することにより、ルールの更新が発生した際その更新に合わせて更新カウンタを更新すべきノードの数を削減できる。このことも、偽陽性判定の発生を抑制する効果を生じる。
【０１９３】
発明が解決しようとする課題の欄で示したルールセットの例（図３８）について、本実施形態を適用した場合の効果について、図２２を参照して説明する。
【０１９４】
図２２（Ａ）は、２次元のルールセット（ルールセットは図３８（Ａ）と同様）を例示する。図２２（Ｂ）は当該ルールセットに対して、本実施形態が構築する探索木（Binth = 4）と、キャッシュエントリとノードの対応関係を例示する。なお、ここでは、当該探索木に収容されるルールセットのルールはＹ次元が小さいという特徴を持つものとする。すなわち、当該探索木に対するノードの分割に係る情報の優先分割次元はＹ次元となる。また、当該探索木に対するノードの分割に係る情報の部分空間サイズ閾値は、Ｙ次元についてＹ次元全体のサイズの１／６であるとする。
【０１９５】
図３８（Ａ）および（Ｂ）では、Ｙ次元の下半分がノード２に対応付けられていた。一方、図２２（Ａ）では、ノードの分割に係る情報に基づきノードが分割された結果、Ｙ次元の下半分に３つのノード（ノード２、４、６）が対応付けられている（Ｙ次元全体では６つのノード）。その結果、図３８ではノード２に対応付けられていた５つのキャッシュエントリが、図２２では異なる３つのノードに対応付けられることとなる。
【０１９６】
この状態において、ノードの４の部分空間に含まれるルール８が追加された場合、ノード４の更新カウンタが更新されるが、それによってキャッシュエントリ再評価が実施されるのは、ノード４に属するキャッシュエントリ１つのみとなる。図３８の例においてはルール８の追加でキャッシュエントリ再評価が実施されるキャッシュエントリは５つであり、そのうち４つは偽陽性判定によるものであった。一方、本実施形態を用いることにより、本例における偽陽性判定の発生を４回抑制できることとなる。
【０１９７】
一方、図２２（Ｄ）は、ノードの分割をノードの分割に係る情報の優先分割次元（Ｙ次元）ではなく、Ｘ次元で行った場合を例示する。このとき、ルール８の追加により複数のノードの更新カウンタが更新され、より多くのキャッシュエントリに対しキャッシュエントリ再評価が実施されることになり、優先分割次元（Ｙ次元）で分割した場合よりも多くの偽陽性判定が発生する。
【０１９８】
なお、上記説明では、受信したパケットに適合するルールが存在しない場合（図１８のステップＳ２０９のＮｏ、ステップＳ２０５のＮｏ）に当該パケットのフローに対応するキャシュエントリを作成しない、または、削除することとしたが（ステップＳ２０７）、本発明はこれに限定されるものではない。他の例として、例えば、ステップＳ２０７において、上記説明に加え、適合するルールがない、という情報を記憶したキャッシュエントリを作成または維持してもよい。これにより、適合するルールがないパケットを受信した場合の探索木探索の実行回数を減らすことができる。
【０１９９】
また、上記説明では、探索木は木構造でありルートノード以外のノードの親ノードの数は１である例を示したが、本発明はこれに限定されるものではない。他の例として、ノードは複数の親ノードを持ってもよい。この場合、探索木は純粋な木ではなくグラフとなる。ノードが複数の親ノードを持つ状態は、当該複数の親ノードが表す部分空間に重複がある場合に発生する。また、そのような重複は、あるノードの子ノード群を作成する際、各子ノードが表す部分空間の一部または全部に重なりを持たせるようにすることで発生する。そのような子ノード群の作成方法は、探索処理最適化の一環として行ってよい。なお、探索処理においては、子ノード群の部分空間に重複があり、かつ探索キーが当該重複する部分空間に含まれる場合、当該部分空間を含む複数の子ノードを探索することとする。
【０２００】
＜実施形態２＞
第１の実施形態では、ノードの分割に係る情報を用いたノードの分割を、探索木の初期化時および更新時に行う例を示したが、本発明はこれに限定されるものではない。他の例として、ノードに属するフローの数（すなわち、キャッシュエントリの数）を参照し、ノードの分割に係る情報を用いた当該ノードの分割を実施してもよい。以下、かかる例を第２の実施形態として説明する。なお、第２の実施形態は基本的に第１の実施形態における構成および動作を踏襲するものとし、差異がある部分について説明する。
【０２０１】
［構成］
図２に示したデータ処理装置１の探索木制御部１０の第２の実施形態における詳細な構成について、図２３のブロック図を参照して説明する。図２３は、図２に示したデータ処理装置１の探索木制御部１０の本実施形態における詳細な構成を例示するブロック図である。
【０２０２】
図２３に示すように、探索木制御部１０は、探索木初期化部１１、ルール更新部１２、探索木探索部１３、更新カウンタ取得部１４、および、動的ノード分割処理部１５を備えている。
【０２０３】
本実施形態の探索木制御部１０は、動的ノード分割処理部１５以外について、第１の実施形態と同様の構成を有する。
【０２０４】
動的ノード分割処理部１５は、例えば、図２に示したキャッシュテーブル制御部４０からの要求を基にして、ノードに属するフローの数（すなわち、キャッシュエントリの数）を参照して当該ノードの分割要否を判断し、必要な場合に当該ノードの分割を行う。
【０２０５】
第２の実施形態におけるデータ処理装置１の探索木記憶部２０が記憶するノードの分割に係る情報は、図４(Ｃ)を参照して説明した第１の実施形態におけるノードの分割に係る情報に加え、キャッシュエントリ数閾値を含む（図２４）。
【０２０６】
なお、キャッシュエントリ数閾値は異なる部分空間に対して異なる値を使用してもよい。例えば、送信先ＩＰアドレスの次元に関し当該閾値を設定する場合、１９２．１６８．０．０／１６および１０．０．０．０／８の部分空間については当該閾値を１００００とし、それ以外の部分空間については１００００００としてもよい。このように部分空間に応じて異なるキャッシュエントリ数閾値を用いることにより、例えば、特定の部分空間にフローが密に発生することが予想される場合に、当該部分空間に対し、より細かく分割したノードを作成することで、偽陽性判定を減らすことが可能となる。キャッシュエントリ数閾値は、予め与えられてもよい。その場合、キャッシュエントリ数閾値は、ノードを分割することにより得られる偽陽性判定減少による負荷削減量と、ノードを分割することに発生する負荷増加量(例えば、探索時間の増加)を考慮し、全体で処理負荷が軽減されるような閾値を設定してもよい。
【０２０７】
第２の実施形態におけるデータ処理装置１のキャッシュテーブル制御部４０のキャッシュエントリ作成部４１は、キャッシュエントリを作成した際、動的ノード分割処理部１５に対し処理を要求する。
【０２０８】
［動作］
＜（Ｅ）キャッシュエントリ作成処理＞
図２５のフロー図を参照して、本実施形態におけるキャッシュエントリ作成処理の動作例について説明する。図２５は、第２の実施形態におけるデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ作成部４１がキャッシュエントリを作成する際の動作を例示するフロー図である。
【０２０９】
ステップＳ２２１〜ステップＳ２２４は、第１の実施形態と同様である。
【０２１０】
次に、本実施形態におけるキャッシュエントリ作成部４１は、探索木制御部１０の動的ノード分割処理部１５に依頼し、動的ノード分割処理を実行する（ステップＳ２２５）。その処理の詳細については、後述する。
【０２１１】
次に、図２５のステップＳ２２５において実行される動的ノード分割処理の詳細な動作について、図２６を参照して説明する。図２６は、図２５のステップＳ２２５において実行される動的ノード分割処理を例示するフロー図である。本動的ノード分割処理においては、パラメータとして、処理対象のノード（処理対象ノード）を受け取る。
【０２１２】
動的ノード分割処理部１５は、処理対象ノードの参照カウンタの値がノードの分割に係る情報のキャッシュエントリ数閾値以上が否かを確認する（ステップＳ３０１）。
【０２１３】
参照カウンタの値がキャッシュエントリ数閾値未満である場合（ステップＳ３０１のＮｏ）、動的ノード分割処理部１５は処理を終了する。
【０２１４】
一方、参照カウンタの値がキャッシュエントリ数閾値以上である場合（ステップＳ３０１のＹｅｓ）、動的ノード分割処理部１５は処理対象ノードがリーフかどうかを確認する（ステップＳ３０２）。
【０２１５】
処理対象ノードがリーフでない場合（ステップＳ３０２のＮｏ）、動的ノード分割処理部１５は動的ノード分割サブ処理Ａを実行する（ステップＳ３０３）。その詳細は後述する。
【０２１６】
一方、処理対象ノードがリーフである場合（ステップＳ３０２のＹｅｓ）、動的ノード分割処理部１５は処理対象ノード（リーフノード）を中間ノード化し、新たに、子ノードを作成する（ステップＳ３０４）。ステップＳ３０４においては、具体的には、動的ノード分割処理部１５は、処理対象ノードのリーフノードフラグをオフに変更する。さらに、子ノードを作成するために、動的ノード分割処理部１５は、処理対象ノードの識別子と、処理対象ノードのルール識別子リストと、をパラメータとして、図１１を参照して説明した探索木構築サブ処理ＡのステップＳ１２２以降を実行する。
【０２１７】
動的ノード分割処理部１５は、処理対象ノードの更新カウンタを更新する（ステップＳ３０５）。具体的には、動的ノード分割処理部１５は、処理対象ノードの更新カウンタの値を、現在の値に「１」を加えたものに変更する。
【０２１８】
次に、図２６のステップＳ３０３において実行される動的ノード分割処理の詳細な動作について、図２７を参照して説明する。図２７は、図２６のステップＳ３０３において実行される動的ノード分割サブ処理Ａを例示するフロー図である。本動的ノード分割サブ処理Ａにおいては、パラメータとして、処理対象のノード（処理対象ノード）を受け取る。
【０２１９】
動的ノード分割処理部１５は、未割り当ての子ノード群を選択する（ステップＳ３１１）。処理対象ノードのある子ノードが未割り当てか否かは、処理対象ノードのノードに係る情報の子ノード識別子リストを参照し、処理対象ノードに対応するエントリに含まれる識別子が未割り当てを示す値であった場合、未割り当てと判定することができる。
【０２２０】
動的ノード分割処理部１５は、ステップＳ３１１において選択された各子ノードそれぞれについて、ノードを割り当てリーフとしてセットアップする（ステップＳ３１２）。具体的には、動的ノード分割処理部１５は、探索木記憶部２０に処理対象ノードの情報を記憶するデータ領域を割り当てさせ、当該ノードについて以下のような情報を設定する。
【０２２１】
（ａ）リーフノードフラグ：オン
（ｂ）親ノード識別子    ：処理対象ノードのノード識別子
（ｃ）部分空間          ：当該子ノードが表す部分空間
（ｄ）更新カウンタ：０
（ｅ）参照カウンタ：０
（ｆ）ルール識別子リスト：空
【０２２２】
以上に詳細に説明したように、本実施形態においては、ノードの分割に係る情報はキャッシュエントリ数閾値を含み、あるノードに属するフローの数がキャッシュエントリ数閾値以上となった場合、当該ノードを分割する。
【０２２３】
よって、本実施形態によれば、フローの発生の状況に応じて動的に、偽陽性判定が多数発生するおそれがあるノードを分割することで、偽陽性判定の発生を効率的に抑制することができる。
【０２２４】
＜実施形態３＞
第２の実施形態では、ノードに属するフローの数（すなわち、キャッシュエントリの数）を参照し、ノードの分割に係る情報を用いた当該ノードの分割を実施する例を示したが、本発明はこれに限定されるものではない。他の例として、ノードに属するフローの数（すなわち、キャッシュエントリの数）を参照し、当該ノードおよび子ノードの併合を実施してもよい。以降、かかる例を第３の実施形態として説明する。なお、第３の実施形態は基本的に第２の実施形態における構成および動作を踏襲するものとし、差異がある部分について説明する。
【０２２５】
［構成］
図２に示したデータ処理装置１の探索木制御部１０の第３の実施形態における詳細な構成例は、第２の実施形態と基本的に同様である。
【０２２６】
第３の実施形態における動的ノード分割処理部１５は、例えば図２に示したキャッシュテーブル制御部４０からの要求を基にして、ノードに属するフローの数（すなわち、キャッシュエントリの数）を参照して当該ノードの併合要否を判断し、必要な場合に当該ノードの併合を行う。
【０２２７】
第３の実施形態におけるデータ処理装置１のキャッシュテーブル制御部４０のキャッシュエントリ作成部４１は、キャッシュエントリを削除した際、動的ノード分割処理部１５に対し処理を要求する。
【０２２８】
［動作］
＜（Ｅ）キャッシュエントリ作成処理＞
図２８のフロー図を参照して、第３の実施形態におけるキャッシュエントリ作成処理の動作例について説明する。図２８は、第３の実施形態におけるデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ作成部４１がキャッシュエントリを作成する際の動作を例示するフロー図である。
【０２２９】
ステップＳ２２１ないしＳ２２５は、第２の実施形態と同様である。
【０２３０】
ステップＳ２２３の次に、第３の実施形態におけるキャッシュエントリ作成部４１は、探索木制御部１０の動的ノード分割処理部１５に依頼し、動的ノード併合処理を実行する（ステップＳ２２３ｂ）。その処理の詳細については、後述する。
【０２３１】
次に、図２８のステップＳ２２３ｂにおいて実行される動的ノード併合処理の詳細な動作について、図２９を参照して説明する。図２９は、図２８のステップＳ２２３ｂにおいて実行される動的ノード併合処理を例示するフロー図である。本動的ノード併合処理においては、パラメータとして、処理対象のノード（処理対象ノード）を受け取る。
【０２３２】
動的ノード分割処理部１５は、処理対象ノードおよび処理対象ノード以下のすべての子ノードを参照し、各ノードの参照カウンタの値の合計を計算し、処理対象ノードの部分空間に含まれるルールのリストを作成する（ステップＳ４０１）。
【０２３３】
動的ノード分割処理部１５は、ステップＳ４０１で求めた参照カウンタ値の合計が０か否かを確認する（ステップＳ４０２）。
【０２３４】
参照カウンタ値の合計が０でない場合（ステップＳ４０２のＮｏ）、動的ノード分割処理部１５は本処理を終了する。
【０２３５】
一方、参照カウンタ値の合計が０である場合（ステップＳ４０２のＹｅｓ）、動的ノード分割処理部１５はステップＳ４０１で求めたルールの総数がBinth以下か否か確認する（ステップＳ４０３）。
【０２３６】
ルールの総数がBinthより多い場合（ステップＳ４０３のＮｏ）、動的ノード分割処理部１５は処理を終了する。
【０２３７】
一方、ルールの総数がBinth以下である場合（ステップＳ４０３のＹｅｓ）、動的ノード分割処理部１５は処理対象ノード以下のすべての子ノードを削除する（ステップＳ４０４）。
【０２３８】
次に、動的ノード分割処理部１５は、処理対象ノードをリーフ化する（ステップ４０５）。ステップＳ４０５においては、具体的には、動的ノード分割処理部１５は、処理対象ノードについて下記のように更新する。
【０２３９】
（ａ）リーフノードフラグ：オン
（ｂ）更新カウンタ：０
（ｃ）参照カウンタ：０
（ｄ）ルール識別子リスト：ステップＳ４０１で求めたルールの識別子のリスト
【０２４０】
以上に詳細に説明したように、第３の実施形態においては、ある中間ノードが表す部分空間に属するキャッシュエントリが０となり、当該中間ノードのリーフ化が可能な場合、当該中間ノードをリーフ化する。
【０２４１】
よって、本実施形態によれば、属するキャッシュエントリの数が少ない部分空間に関しノード数を削減することで、探索木の探索速度を改善したり、必要なメモリ量を削減することができる。
【０２４２】
本実施形態と第２の実施形態と組み合わせて使用することで、第２の実施形態による機能により動的に分割されたノード群を、フローの発生状況に応じて動的に併合することができる。
【０２４３】
＜実施形態４＞
第１ないし第３の実施形態では、ノードの分割に係る情報が探索木毎に独立して決定される例を示したが、本発明はこれに限定されるものではない。他の例として、複数の探索木がグループ化されており、ある探索木に関するノードの分割に係る情報が、当該探索木が属するグループおよび当該グループに属する他の探索木に係る情報を参照して決定されてもよい。
【０２４４】
複数の探索木がグループ化は、例えば、キャッシュエントリ再評価処理におけるノードの最新の更新カウンタ値の参照を階層化する目的で導入されてもよい。探索木が複数存在する場合、パケットを受信する都度、すべての探索木それぞれについてカウンタ値を参照して更新の有無を確認することになる。したがって、パケット受信処理におけるデータ参照回数が増え、処理性能が低下するおそれがある。そこで、下記の構成および動作を採用することが考えられる。
【０２４５】
・複数の探索木をグループ化する
・グループ内のいずれかの探索木をベース探索木として選択し、ベース探索木のノードに、更新カウンタに加え、グループ内のいずれかの探索木におけるルール更新に伴い更新される共有更新カウンタを設ける
・ある探索木においてルール更新が発生した場合、当該探索木のノードの更新カウンタの更新に加え、当該探索木が属するクループのベース探索木について、当該ルールが表す部分空間と重複する部分空間に対応するノードの共有更新カウンタを更新する
・キャッシュエントリには、更新カウンタ値のキャッシュに加え、共有更新カウンタ値のキャッシュを記憶する
・キャッシュエントリ再評価処理において、個々の探索木のノードの最新の更新カウンタを参照する前に、各グループのベース探索木のノードの共有更新カウンタ最新値を参照する。両者が一致するグループについては、当該グループ内の個々の探索木のノードの最新の更新カウンタ値確認を省略する。
【０２４６】
上記により、キャッシュエントリ再評価処理におけるノードの最新の更新カウンタ値の参照が階層化され、更新カウンタ値の参照回数を削減することができる。
【０２４７】
以降、複数の探索木がグループ化されており、ある探索木に関するノードの分割に係る情報が、当該探索木が属するグループおよび当該グループに属する他の探索木に係る情報を参照して決定される例を第４の実施形態として説明する。なお、第４の実施形態は基本的に第１の実施形態における構成および動作を踏襲するものとし、差異がある部分について説明する。
【０２４８】
［構成］
図２に示したデータ処理装置１の探索木制御部１０の第４の実施形態における詳細な構成例は、第１の実施形態と基本的に同様である。
【０２４９】
第４の実施形態におけるデータ処理装置１の探索木制御部１０の探索木初期化部１１は、探索木グループと、各探索木グループのベース探索木と、を決定する。また、第４の実施形態における探索木初期化部１１は、各ベース探索木について、当該探索木が属する探索木グループに含まれる他の探索木が収容するサブルールセットの特徴をも参照し、ノードの分割に係る情報を決定する。
【０２５０】
第４の実施形態におけるデータ処理装置１の探索木記憶部２０は、探索木に係る情報および探索木グループに係る情報を記憶する（図３０（Ａ））。第４の実施形態におけるデータ処理装置１の探索木記憶部２０が記憶する探索木に係る情報は、図４(Ａ)を参照して説明した第１の実施形態における探索木に係る情報に加え、探索木グループ識別子を含む。また、探索木グループに係る情報は、属する各探索木を示す探索木識別子リスト、ベースとなるベース探索木を示すベース探索木識別子、を含む。
【０２５１】
また、第４の実施形態におけるデータ処理装置１の探索木記憶部２０は、ノードに係る情報を記憶する（図３０（Ｂ））。第４の実施形態におけるデータ処理装置１の探索木記憶部２０が記憶するノードに係る情報は、図４(Ｂ)を参照して説明した第１の実施形態におけるノードに係る情報に加え、共有更新カウンタを含む。ノードの共有更新カウンタは、当該ノードの探索木が属する探索木グループ内において、当該ノードが表す部分空間に含まれるルールに更新があった場合に更新される。ノードの共有更新カウンタは、ベース探索木についてのみ記憶されてよい。
【０２５２】
また、第４の実施形態におけるデータ処理装置１の探索木記憶部２０は、ノードの分割に係る情報の優先分割次元に関し、格納される各次元について優先度を保持してもよい（図３０（Ｃ））。
【０２５３】
図３１は、第４の実施形態におけるデータ処理装置１のキャッシュテーブル記憶部５０に記憶される、キャッシュテーブルおよびキャッシュエントリに関する情報の一例を示す表である。図３１（Ａ）は、キャッシュエントリに係る情報を例示する。一方、図３１（Ｂ）は、キャッシュエントリノード状態を例示する。第４の実施形態におけるデータ処理装置１のキャッシュテーブル記憶部５０が記憶するキャッシュエントリノード状態は、図５（Ｂ）を参照して説明した第１の実施形態におけるキャッシュエントリノード状態に加え、共有更新カウンタキャッシュを含む。共有更新カウンタキャッシュはベース探索木についてのみ記憶されてよい。ノード状態の共有更新カウンタキャッシュには、当該キャッシュエントリが最後に使用された際の、当該ノードの共有更新カウンタの値が記憶される。
【０２５４】
［動作］
＜（Ａ）探索木初期化処理＞
図３２のフロー図を参照して、第４の実施形態における探索木初期化処理の動作例について説明する。図３２は、第４の実施形態におけるデータ処理装置１の探索木制御部１０における探索木初期化部１１が探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールセットを初期化する際の動作を例示するフロー図である。
【０２５５】
ステップＳ１０１およびＳ１０２は、第１の実施形態と同様である。
【０２５６】
ステップＳ１０１の次に、第４の実施形態における探索木初期化部１１は、探索木グループと、各探索木グループのベース探索木とを決定する（ステップＳ１０３）。ここで、探索木初期化部１１は、例えば、各探索木に含まれるルールの特徴を用いて予め定めたグループ化基準、例えば、ルールのマッチ条件（データ識別情報の一種）の粒度を与える以下に示すようなグループ化基準を用いて、探索木をグループ化する。
【０２５７】
（ａ）グループ化基準Ａ：マッチ条件の指定が５フィールドとも大きいルール群を収容する探索木（図９（ａ）の‘サブセット５’用探索木）は、単独で探索木グループを構成する。
【０２５８】
（ｂ）グループ化基準Ｂ：マッチ条件の指定が小さいフィールド数が４以上のルール群を収容する探索木（図９（ｅ）の「サブセット４」用探索木）についても、単独で探索木グループを構成するようにしてもよい。
【０２５９】
（ｃ）グループ化基準Ｃ：マッチ条件の指定が小さいフィールドの数が少ない（例えば、１個の）ルール群を収容する探索木（図９（ｂ）の「サブセット１−１」用探索木〜「サブセット１−５」用探索木）は、それぞれ異なる探索木グループに含める。
【０２６０】
（ｄ）グループ化基準Ｄ：マッチ条件の指定の大小パターンが似ている探索木同士を同一の探索木グループに含め、似ていない探索木同士は別の探索木グループに含める。
（ｄ−１）例えば、マッチ条件の指定が小さいフィールドを「０」、大きいフィールドを「１」と表し、各探索木についてマッチ条件の指定の大小パターンから５ビット２進数列を作成する。そして、２つの探索木に関する類似度判定を、各探索木について作成した５ビット２進数列間のハミング距離を用いて数値化した上で行う。
（ｄ−２）例えば、図９（ｃ）の「サブセット２−５」用２進数列は「１００１１」、図９（ｄ）の「サブセット３−７」用２進数列は「１０００１」であり、その間のハミング距離は「１」である。また、図９（ｄ）の「サブセット３−７」用２進数列は「１０１１０」であり、サブセット２−５用２進数列とのハミング距離は「２」である。したがって、「サブセット２−５」用探索木と同一の探索木グループに収容する探索木としては、「サブセット３−７」用と「サブセット２−５」用との場合には、ハミング距離が小さい前者の方が望ましい。
【０２６１】
（ｅ）グループ化基準Ｅ：各探索木グループに含まれる探索木の数がなるべく等しいようにする（ただし、グループ化基準Ａおよびグループ化基準Ｂによるグループを除く）。
【０２６２】
図９のサブルールセット構成例における探索木初期化部１１によるグループ化の結果を示す探索木グループの一例を、図３３に示す。図３３は、第４の実施形態における図２に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１により作成される探索木グループの一例を示す表である。図９のサブルールセット構成例の場合、前述のグループ化基準Ａ〜Ｅを適用して、図３３の探索木グループ１１１に示すように、探索木グループ１〜探索木グループ７の７個の探索木グループにグルーピングされる。
【０２６３】
例えば、探索木グループ１には、図３３の使用グループ化基準１１３に示すように、グループ化基準Ｃ、Ｄ、Ｅを適用して、図３３の所属探索木１１２に示すように、図９の「サブセット１−１」、「サブセット２−１」、「サブセット２−２」、「サブセット３−１」、「サブセット３−３」の５個の探索木が属し、探索木グループ２の場合も、グループ化基準Ｃ、Ｄ、Ｅを適用して、図３３の所属探索木１１２に示すように、図９の「サブセット１−２」、「サブセット２−５」、「サブセット２−６」、「サブセット３−７」、「サブセット３−９」の５個の探索木が属することになる。また、探索木グループ６には、グループ化基準Ａを適用して、「サブセット５」の１個の探索木が属し、探索木グループ７には、グループ化基準Ｂを適用して、「サブセット４」の１個の探索木が属することになる。
【０２６４】
さらに、探索木初期化部１１は、例えば、決定された各探索木グループの中から、マッチ条件の指定が小さいフィールドの数が最も小さい探索木を、当該探索木グループのベース探索木として選択する。図３３の例においては、探索木初期化部１１は、例えば、探索木グループ１のベース探索木として「サブセット１−１」用探索木（マッチ条件の小さいフィールドの数が「１」の探索木）を選択する。
【０２６５】
ステップＳ１０２において実行される、図１０および図１１を参照して説明した探索木初期化部１１がサブルールセット毎に探索木を構築する動作のステップＳ１１１において、第４の実施形態における探索木初期化部１１は、当該探索木がベース探索木である場合、当該探索木が属する探索木グループに含まれる他の探索木が収容するサブルールセットの特徴をも参照し、ノードの分割に係る情報を決定する。探索木初期化部１１は、属する探索木グループに含まれる探索木が収容するサブルールセットの特徴から、小さいフィールド（次元）を選択し、当該次元（群）を当該探索木のノードの分割に係る情報の優先分割次元に設定する。このとき、探索木初期化部１１は、より多くの探索木で小さいフィールド（次元）となっているフィールドに対し高い優先度を割り当ててもよい。
【０２６６】
図１１を参照して説明した探索木構築サブ処理ＡのステップＳ１２２において、第４の実施形態における探索木初期化部１１は、ノードの分割に係る情報の優先分割次元を参照して処理対象ノードの部分空間をカットする次元を決定する際、当該優先分割次元に含まれる次元の中からより高い優先度を持つものを優先的に選択して使用してもよい。
【０２６７】
＜（Ｂ）ルール更新処理＞
図１２を参照して説明したルール更新処理のステップＳ１３６およびステップＳ１３７の動作の後、第４の実施形態におけるルール更新部１２は、処理対象探索木が属する探索木グループのベース探索木を選択し、当該ベース探索木のルートノードについて、後述するルール更新サブ処理Ｃを実行する（ステップＳ１３８）。
【０２６８】
図３４のフロー図を参照して、第４の実施形態におけるルール更新部１２がステップＳ１３８で実行するルール更新サブ処理Ｃの動作例について説明する。本処理は、パラメータとして、処理対象のノード（処理対象ノード）および更新対象のルール(処理対象ルール)を受け取る。
【０２６９】
ルール更新部１２は、処理対象ノードがリーフかどうか確認する（図３４のステップＳ５０１）。この確認は、ノードのリーフフラグがオンか否かによって行われる。
【０２７０】
ステップＳ５０１においてＮｏであった場合、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ５０２）。
【０２７１】
ルール更新部１２は、ステップＳ５０２で選択された子ノード(割り当て済みの子ノードのみ)それぞれについてルール更新サブ処理Ｃを実行する（ステップＳ５０３）。
【０２７２】
ルール更新部１２は、ステップＳ５０２で選択された子ノードにデータ領域が未割り当ての子ノード（すなわち関係するルールの数が０の子ノード）があり、かつ、現在の操作がルール追加であるかどうか確認する（ステップＳ５０４）。
【０２７３】
ステップＳ５０４においてＹｅｓの場合、ルール更新部１２は、処理対象ノードの共有更新カウンタを更新する（ステップＳ５０５）。具体的には、ルール更新部１２は、処理対象ノードの共有更新カウンタの値を、現在の値に１加えたものに変更する。
【０２７４】
ステップＳ５０４においてＮｏであった場合、ルール更新部１２は、本処理を終了する。
【０２７５】
ステップＳ５０１においてＹｅｓであった場合、ルール更新部１２は、処理対象ノード（リーフ）の共有更新カウンタを更新する（ステップＳ５０６）。具体的には、ルール更新部１２は、処理対象ノード(リーフ)の共有更新カウンタの値を、現在の値に１加えたものに変更する。
【０２７６】
＜（Ｅ）キャッシュエントリ作成処理＞
図１９を参照して説明したキャッシュエントリ作成処理のステップＳ２２４において、第４の実施形態におけるキャッシュエントリ作成部４１は、第１の実施形態における動作に加え、選択したキャッシュエントリのノード状態．共有更新カウンタキャッシュに前記ノード識別子を基に図７に示す更新カウンタ取得部１４に依頼して取得した当該各ノードの共有更新カウンタの値を設定する(ベース探索木毎)。
【０２７７】
＜（Ｇ）キャッシュエントリ再評価処理＞
図２１を参照して説明したキャッシュエントリ再評価処理のステップＳ２４１に先立ち、第４の実施形態におけるキャッシュエントリ再評価部４３は、以下のステップＳ２４０ａ、Ｓ２４０ｂ（非図示）を実行する。
【０２７８】
キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのノード状態リストを参照して、更新カウンタ取得部１４に依頼し処理対象キャッシュエントリが表すフローが属するノードの最新の共有更新カウンタ値（ベース探索木毎）を取得する（ステップＳ２４０ａ）。
【０２７９】
キャッシュエントリ再評価部４３は、ステップＳ２４０ａで得られた最新の共有更新カウンタ値と処理対象キャッシュエントリに記憶された各ベース探索木の共有更新カウンタ値に差分があるかどうか確認する（ステップＳ２４０ｂ）。差分がない場合（ステップＳ２４０ｂのＮｏ）、ステップＳ２４５に移行する。
【０２８０】
ステップＳ２４０ｂにおいてＹｅｓの場合、キャッシュエントリ再評価部４３は、ステップＳ２４１に移行する。その際、キャッシュエントリ再評価部４３は、ステップＳ２４０ｂにおいて差分が検出されたベース探索木が属する探索木グループ内の探索木群を更新カウンタ値取得対象とする。
【０２８１】
以上に詳細に説明したように、第４の実施形態においては、ある探索木に関するノードの分割に係る情報を、当該探索木が属するグループおよび当該グループに属する他の探索木に係る情報を参照して決定する。
【０２８２】
よって、本実施形態によれば、探索木のグループ化に起因する偽陽性判定の発生を抑制することができる。
【０２８３】
以上、本発明の好適な実施形態の構成を説明した。しかし、かかる実施形態は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。
【０２８４】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の態様に係るデータ処理装置のとおりである。
［形態２］
前記所定の方向は、前記複数のルールに含まれるマッチ条件が前記多次元空間において占める領域のサイズが相対的に小さい方向である、
形態１に記載のデータ処理装置。
［形態３］
前記探索木制御部は、前記部分空間の前記所定の方向の幅が所定の閾値以下となるように前記多次元空間を分割する、
形態１または２に記載のデータ処理装置。
［形態４］
前記探索木制御部は、前記多次元空間に含まれる第１の領域において前記部分空間の前記所定の分割方向の幅が所定の第１閾値以下となるように前記多次元空間を分割するとともに、前記多次元空間に含まれる第２の領域において前記部分空間の前記所定の分割方向の幅が所定の第２の閾値以下となるように前記多次元空間を分割する、
形態３に記載のデータ処理装置。
［形態５］
前記探索木記憶部は、ノードに対応付けられた部分空間と少なくも一部が重なるマッチ条件を含むルールが変更された場合に更新されるカウント値を前記ノードに関連付けて保持し、
前記キャッシュテーブル記憶部は、前記キーと前記キーに対応するノードとの関連付けが参照された時点において、前記ノードに関連付けられたカウント値を前記キーおよび前記ノードに関連付けて保持し、
前記データ処理部は、前記キャッシュテーブル記憶部において前記キーに関連付けられたカウント値と、前記探索木記憶部において前記キーに対応するノードに関連付けられたカウント値とが一致する場合、前記キャッシュテーブル記憶部を参照して前記キーにマッチするマッチ条件を含むルールを抽出する、
形態１ないし４のいずれか一に記載のデータ処理装置。
［形態６］
前記探索木制御部は、前記キャッシュテーブル記憶部においてノードに関連付けられたキーの数が所定の閾値以上である場合、前記ノードに対応付けられた部分空間をさらに分割して複数の部分空間を生成する、
形態１ないし４のいずれか一に記載のデータ処理装置。
［形態７］
前記探索木制御部は、前記キャッシュテーブル記憶部において第１のノードに関連付けられたキーの数と第２のノードに関連付けられたキーの数の和が所定の閾値以下である場合、前記第１のノードに対応付けられた部分空間と前記第２のノードに対応付けられた部分空間を併合して単一の部分空間を生成する、
形態１ないし６のいずれか一に記載のデータ処理装置。
［形態８］
前記探索木制御部は、前記複数のルールを複数の集合に分類するとともに前記複数の集合を複数のグループに分割した場合、１つのグループに所属する１つの集合に属するルールに含まれるマッチ条件の特徴を考慮する際、前記１つのグループに所属する他の集合に属するルールに含まれるマッチ条件の特徴も考慮する、
形態１ないし７のいずれか一に記載のデータ処理装置。
［形態９］
上記第２の態様に係るデータ処理方法のとおりである。
［形態１０］
前記所定の方向は、前記複数のルールに含まれるマッチ条件が前記多次元空間において占める領域のサイズが相対的に小さい方向である、
形態９に記載のデータ処理方法。
［形態１１］
前記コンピュータは、前記部分空間の前記所定の方向の幅が所定の閾値以下となるように前記多次元空間を分割する、
形態９または１０に記載のデータ処理方法。
［形態１２］
前記コンピュータは、前記多次元空間に含まれる第１の領域において前記部分空間の前記所定の分割方向の幅が所定の第１閾値以下となるように前記多次元空間を分割するとともに、前記多次元空間に含まれる第２の領域において前記部分空間の前記所定の分割方向の幅が所定の第２の閾値以下となるように前記多次元空間を分割する、
形態１１に記載のデータ処理装置。
［形態１３］
上記第３の態様に係るプログラムのとおりである。
［形態１４］
前記所定の方向は、前記複数のルールに含まれるマッチ条件が前記多次元空間において占める領域のサイズが相対的に小さい方向である、
形態１３に記載のプログラム。
［形態１５］
前記コンピュータは、前記部分空間の前記所定の方向の幅が所定の閾値以下となるように前記多次元空間を分割する、
形態１３または１４に記載のプログラム。
［形態１６］
前記多次元空間に含まれる第１の領域において前記部分空間の前記所定の分割方向の幅が所定の第１閾値以下となるように前記多次元空間を分割するとともに、前記多次元空間に含まれる第２の領域において前記部分空間の前記所定の分割方向の幅が所定の第２の閾値以下となるように前記多次元空間を分割する処理を、前記コンピュータに実行させる、
形態１５に記載のプログラム。
【０２８５】
なお、上記特許文献および非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想に従って当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０２８６】
１      データ処理装置
１０    探索木制御部
１１    探索木初期化部
１２    ルール更新部
１３    探索木探索部
１４    更新カウンタ取得部
１５    動的ノード分割処理部
２０    探索木記憶部
２１    種別
２２    項目
２３    説明
２４    ノード種別
２５    項目
２６    説明
２７    項目
２８    説明
３０    ルール記憶部
３１    項目
３２    説明
３３    例
４０    キャッシュテーブル制御部
４１    キャッシュエントリ作成部
４２    キャッシュエントリ探索部
４３    キャッシュエントリ再評価部
５０    キャッシュテーブル記憶部
５１    項目
５２    説明
５３    項目
５４    説明
６０    パケット処理部
７０    通信ＩＦ部
８０    データ処理装置制御部
９０    データ処理部
１１１  探索木グループ
１１２  所属探索木
１１３  使用グループ化基準
【図１】
2018148247.tif 000003
【図２】
2018148247.tif 000004
【図３】
2018148247.tif 000005
【図４】
2018148247.tif 000006
【図５】
2018148247.tif 000007
【図６】
2018148247.tif 000008
【図７】
2018148247.tif 000009
【図８】
2018148247.tif 000010
【図９】
2018148247.tif 000011
【図１０】
2018148247.tif 000012
【図１１】
2018148247.tif 000013
【図１２】
2018148247.tif 000014
【図１３】
2018148247.tif 000015
【図１４】
2018148247.tif 000016
【図１５】
2018148247.tif 000017
【図１６】
2018148247.tif 000018
【図１７】
2018148247.tif 000019
【図１８】
2018148247.tif 000020
【図１９】
2018148247.tif 000021
【図２０】
2018148247.tif 000022
【図２１】
2018148247.tif 000023
【図２２】
2018148247.tif 000024
【図２３】
2018148247.tif 000025
【図２４】
2018148247.tif 000026
【図２５】
2018148247.tif 000027
【図２６】
2018148247.tif 000028
【図２７】
2018148247.tif 000029
【図２８】
2018148247.tif 000030
【図２９】
2018148247.tif 000031
【図３０】
2018148247.tif 000032
【図３１】
2018148247.tif 000033
【図３２】
2018148247.tif 000034
【図３３】
2018148247.tif 000035
【図３４】
2018148247.tif 000036
【図３５】
2018148247.tif 000037
【図３６】
2018148247.tif 000038
【図３７】
2018148247.tif 000039
【図３８】
2018148247.tif 000040