(57)【要約】  データ処理用の情報エントリを探索する探索木が複数の場合でも負荷を低減可能なデータ処理装置を提供する。探索木制御部１０にて探索木をグループ化した各グループのベース探索木を選択し、情報エントリの操作に際し、該情報エントリのデータ識別情報と重複する探索空間にあるノードの更新履歴情報を、また該ノードを含む探索木が属するグループのベース探索木について該データ識別情報と重複する探索空間にあるノードの共有更新履歴情報を更新する。キャッシュテーブル制御部４０にて探索木による情報エントリの探索結果の到達ノードと該ノードの更新履歴情報及び共有更新履歴情報とを含む情報をキャッシュエントリとして記憶し、該キャッシュエントリによるデータ処理に際し、該キャッシュエントリに関する更新履歴情報及び共有更新履歴情報の各キャッシュを最新のものと比較し、不整合がある場合該キャッシュエントリは無効とする。
2016125501.tif 000002
【特許請求の範囲】
【請求項１】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理するデータ処理装置であって、
１ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化手段と、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶手段と、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新する更新手段と、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶する情報エントリ記憶手段と、
前記第２の情報エントリを使用したデータ処理を行う際に、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに含まれる情報のうち少なくとも前記更新履歴情報に関し前記不整合が検出されたノードに係る情報は無効であるものと判定する再評価手段と
を備えるデータ処理装置。
【請求項２】
前記再評価手段は、前記情報エントリ記憶手段に記憶された前記第２の情報エントリが無効であるものと判定した際に、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と最新の更新履歴情報の値とに不整合があった前記ノードが属する前記探索木について前記第１の情報エントリの再探索を行い、再探索した結果を用いて当該情報エントリ記憶手段に記憶された当該第２の情報エントリを更新する
請求項１に記載のデータ処理装置。
【請求項３】
前記再評価手段は、前記第１の情報エントリの再探索を、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と最新の更新履歴情報の値とに不整合があった前記ノードが属する前記探索木のルートのノードから開始する代わりに、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記ノード識別子のキャッシュが示すノードから開始する
請求項２に記載のデータ処理装置。
【請求項４】
前記探索木初期化手段は、１ないし複数の前記探索木をグループ化する際に、各前記探索木に含まれる前記第１の情報エントリの特徴を用いてあらかじめ定めたグループ化基準に基づいて、前記探索木のグループ化を行う
請求項１ないし請求項３のいずれかに記載のデータ処理装置。
【請求項５】
前記探索木初期化手段は、前記グループ化基準として、前記第１の情報エントリに含まれる前記データ識別情報の粒度を用いる
請求項４に記載のデータ処理装置。
【請求項６】
前記更新履歴情報および前記共有更新履歴情報が、それぞれの更新回数をカウントする更新カウンタおよび共有更新カウンタからなっており、前記ノードの値と前記キャッシュの値に差異がある状態を不整合とみなす
請求項１ないし請求項５のいずれかに記載のデータ処理装置。
【請求項７】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理する情報エントリ管理方法であって、  １ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択し、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶し、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新し、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶し、
前記第２の情報エントリを使用したデータ処理を行う際に、前記第２の情報エントリを記憶することによって記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記記憶された当該第２の情報エントリは無効であると判定することで、第２の情報エントリを再評価する
情報エントリ管理方法。
【請求項８】
前記第２の情報エントリの再評価は、前記記憶された前記第２の情報エントリが無効であると判定した際に、前記記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と、最新の更新履歴情報の値と、に不整合があった前記ノードが属する前記探索木について前記第１の情報エントリの再探索を行い、再探索した結果を用いて前記記憶された当該第２の情報エントリを更新する
請求項７に記載の情報エントリ管理方法。
【請求項９】
前記第２の情報エントリの再評価は、前記第１の情報エントリの再探索を、前記記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と、最新の更新履歴情報の値と、に不整合があった前記ノードが属する前記探索木のルートのノードから開始する代わりに、前記記憶された当該第２の情報エントリに関する前記ノード識別子のキャッシュが示すノードから開始する
請求項８に記載の情報エントリ管理方法。
【請求項１０】
請求項７ないし９のいずれかに記載の情報エントリ管理方法を、コンピュータによって実行可能なプログラムとして実施する情報エントリ管理プログラムが記録された記録媒体。
【請求項１１】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から探索する際に用いられる探索木について、１ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化手段と、
前記探索木を構成するノードである中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶手段と、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新する更新手段と、
第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶する情報エントリ記憶手段と、
前記第２の情報エントリを使用したデータ処理を行う際に、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに含まれる情報のうち少なくとも前記更新履歴情報に関し前記不整合が検出されたノードに係る情報は無効であるものと判定する再評価手段と、
前記処理対象とするデータを処理する際に、当該データに関する前記第２の情報エントリが前記情報エントリ記憶手段に記憶されていた場合、当該第２の情報エントリを使用して当該データを処理するデータ処理実行手段と、を備える
データ処理装置。
【請求項１２】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理する情報エントリ管理方法であって、  １ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化処理と、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶処理と、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新する更新処理と、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶する第２の情報エントリ記憶処理と、
前記第２の情報エントリを使用したデータ処理を行う際に、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリは無効であるものと判定する再評価処理と、をコンピュータに実行させる
情報エントリ管理プログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、情報エントリ管理方法および情報エントリ管理プログラムに関し、特に、データ処理の一例として、受信したパケットを処理するデータ処理装置、情報エントリ管理方法および情報エントリ管理プログラムに関する。
【背景技術】
【０００２】
イーサネット（Ｅｔｈｅｒｎｅｔ）（登録商標）スイッチやルータ、オープンフロー（ＯｐｅｎＦｌｏｗ）スイッチのように、一定のルールにしたがってパケットを転送したり破棄したりするパケット処理装置は、パケットを受信し処理する場合、一般的に以下のような処理を実行する。【０００３】
（１）まず、パケットを通信インタフェースから受信する。【０００４】
（２）次に、受信したパケットを処理するために必要な情報を検索する。【０００５】
（３）最後に、検索した当該情報に基づき、受信した当該パケットを処理する。【０００６】
上記（２）の処理は、一般に、パケット分類分け（Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）とも呼ばれ、あらかじめ与えられたルールセットの中から受信パケットに適合する最高優先度のルールを探索する処理である。当該ルールは、マッチ条件（例えば適合するアドレスの範囲）と、当該マッチ条件に適合したパケットに対して実行される処理であるアクションとから構成される。また、当該ルールには優先度や統計情報が含まれる場合もある。【０００７】
ここで、探索木を用いたパケット分類分け（Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）方式に関する技術が非特許文献１（Ｂａｌａｊｅｅ  Ｖａｍａｎａｎらによる“ＥｆｆｉＣｕｔｓ：  Ｏｐｔｉｍｉｚｉｎｇ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｆｏｒ  Ｍｅｍｏｒｙ  ａｎｄ  Ｔｈｒｏｕｇｈｐｕｔ”（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ２０１０））に開示されている。該非特許文献１に記載の技術は、ｄフィールドのルール探索問題をｄ次元空間内の部分空間探索問題として扱う。該非特許文献１に記載の技術は、探索木を辿るたびに探索空間をカットして探索領域を狭めていくことによって、受信パケットに適合するルールを見つけ出すという技術である。【０００８】
ここで、探索木を構成するノードは、ｄ次元空間の部分空間を表し、ルートノードは、ｄ次元空間において採り得る全領域（初期探索領域）を表す。各ルールは、それぞれのルールが表すｄ次元部分空間と重複する部分空間を有する全てのノードに関連付けられる。或るノードに関連付けられる(含まれる)ルールの数が、あらかじめ定めた一定数（Ｂｉｎｔｈ）より多い場合、当該ノードは１つまたは複数の次元においてカット（Ｃｕｔ）され、子ノードが作成される（つまり、当該ノードは中間ノードである）。一方、或るノードに関連付けられる(含まれる)ルールの数が、一定数（Ｂｉｎｔｈ）以下の場合、当該ノードはリーフ（葉）ノードとなる。【０００９】
探索木を用いた探索処理の例を図２３〜図２５を用いて説明する。図２３は、ルールセットの一例を示す模式図である。図２３に示す例は、２フィールド（次元Ｘおよび次元Ｙ）のルール探索を想定し、次元Ｘおよび次元Ｙの採り得る範囲が、それぞれ、０〜２５５および０〜１２７である場合を示している。図２３において、各矩形は、それぞれ、ルールＲ１〜Ｒ７のマッチ条件に対応する２次元部分空間を示している。矩形が重複している場合、矩形の全てが表示されているルールが、より高い優先度を持つものとする。【００１０】
図２４は、探索木の一例を示す模式図であり、図２３に示したルールセットのルールＲ１〜Ｒ７からルール探索を行うための探索木の一例を示している（Ｂｉｎｔｈ＝２の場合）。つまり、図２４は、図２３に示したルールセット例に関して、ルートノードにおいて、探索空間をＸ軸で４つの部分空間にカット（Ｃｕｔ）し、また、ノード１において、探索空間をＹ軸で２つの部分空間にカット（Ｃｕｔ）した例を示している。なお、図２４において、楕円は中間ノードを示し、矩形はリーフノードを示している。【００１１】
図２５は、探索木のノードに係る情報の一例を示す表であり、図２４の探索木の各ノードが表す部分空間および各ノードが含むルールを示している。図２５に示すように、ルートノードが表す部分空間は、探索空間全体である。これより、当該ルートノードが表す部分空間は、次元Ｘおよび次元Ｙそれぞれが０≦Ｘ≦２５５および０≦Ｙ≦１２７の範囲であり、当該ルートノードに含まれるルールはＲ１〜Ｒ７である。また、リーフノード４については、ルートノードからリーフノード４に到達する過程において、探索空間がＸ軸で４つにカット（Ｃｕｔ）され、Ｙ軸で２つにカット（Ｃｕｔ）されている。また、Ｘ軸およびＹ軸の各カット（Ｃｕｔ）におけるリーフノード４の位置は、それぞれ、第４番目および第１番目である。これより、当該リーフノード４が表す部分空間は、次元Ｘおよび次元Ｙそれぞれが１９２≦Ｘ≦２５５および０≦Ｙ≦６３の範囲であり、当該リーフノード４に含まれるルールはＲ５、Ｒ７である。【００１２】
ここで、例えば、ＸおよびＹの値が、それぞれ、２３０および３０であるパケットを受信した場合のルール探索処理の例について説明する。まず、パケット処理装置は、ルートノードを確認し、受信パケットのＸの値が２３０であることから、４番目の部分空間を示すノード１（１９２≦Ｘ≦２５５）を選択する。次に、パケット処理装置は、ノード１を確認し、受信パケットのＹの値が３０であることから、第１番目の部分空間を示すリーフノード４（０≦Ｙ≦６３）を選択する。リーフノード４は、前述のように、ルールＲ５およびＲ７を含んでいる。パケット処理装置は、、これらのルールの中から、線形探索を行い、受信パケットに対応する最高優先度を持つルールとして例えばルールＲ７を発見する。【００１３】
以上の探索処理の説明においては、探索木が一つの場合を例示した。上記非特許文献１には、ルールの特徴を用いて分類することによってルールセットを複数のサブルールセットに分割し、サブルールセット毎に探索木を構築して、探索処理に使用する例が開示されている。サブルールセット毎に探索木を構築した場合、受信パケットに対するルール探索処理は、各サブルールセットの各探索木それぞれに対して実行され、得られた複数のルール（得られるルール数はサブルールセットの数と同じ）の中から最高優先度のルールが選択される。【００１４】
また、探索木を用いたルール探索処理の探索結果を記憶しておいて（キャッシュしておいて）、再利用することによって、探索性能を向上させる技術が、特許文献１（特開２０００−４１０６５号公報「データ検索回路」）に開示されている。該特許文献１に記載の技術においては、探索木による探索結果が、例えば、ハッシュテーブルとして実装されている、完全一致のキャッシュエントリ検索用テーブルに登録される。パケット受信時に、当該パケットに完全一致するキャッシュエントリがキャッシュエントリ検索用テーブルに存在する場合には、当該キャッシュエントリに記憶された探索木による探索結果が使用され、探索木を用いた探索処理は省略される。【００１５】
ここで、探索結果がキャッシュエントリ検索用テーブルにキャッシュされて使用される構成において、ルールセットの変更（すなわち、探索木へのルールの追加、変更、削除）が行われた場合、キャッシュされている探索結果も適切に更新されなければならない。適切に更新されない場合には、受信したパケットは古いルールセットにおける探索結果にしたがって処理されることとなり、ルールによる通信処理・制御が正しく行なわれなくなる。【００１６】
探索木（ルーティングテーブル）の変更に伴って、探索木による探索結果をキャッシュしていたキャッシュエントリを、キャッシュエントリ検索用テーブルから削除する場合の負荷を低減する技術が、特許文献２（特許第４６４６８２３号公報「ルータ装置、ルータ装置におけるルート決定方法」）に開示されている。該特許文献２に記載の技術においては、ルーティングテーブルに格納される、パケットの宛先アドレスと、ルートとの対応関係を表すルーティングエントリにカウンタ値が設けられ、ルーティングエントリが更新された際には、当該カウンタ値がインクリメントされる。【００１７】
そして、特許文献２に開示された装置は、パケットを受信し、当該パケットに対応するキャッシュエントリ（ルーティングテーブルの検索結果（すなわちルーティングエントリの情報）を含む）を使用して、当該パケットを処理する。この処理の際、該装置は、当該ルーティングエントリのカウンタ値を参照して、当該ルーティングエントリの更新の有無を判断する。該装置は、更新が検出された場合には、キャッシュエントリを削除する。これにより、該装置は、削除するキャッシュエントリを特定するための負荷を低減することができ、キャッシュエントリを削除する負荷を低減することができる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２０００−４１０６５号公報
【特許文献２】特許第４６４６８２３号公報
【００１９】
【非特許文献１】Ｂａｌａｊｅｅ  Ｖａｍａｎａｎ、Ｇｗｅｎｄｏｌｙｎ  Ｖｏｓｋｕｉｌｅｎ  ａｎｄ  Ｔ．Ｎ．  Ｖｉｊａｙｋｕｍａｒ；“ＥｆｆｉＣｕｔｓ：  Ｏｐｔｉｍｉｚｉｎｇ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｆｏｒ  Ｍｅｍｏｒｙ  ａｎｄ  Ｔｈｒｏｕｇｈｐｕｔ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ２０１０  ｃｏｎｆｅｒｅｎｃｅ、２０１０年、ｐ．ｐ．２０７−２１８
【発明の概要】
【発明が解決しようとする課題】
【００２０】
以上のように、ルールセットをサブルールセットに分割し、サブルールセット毎に探索木を構築して探索に使用するパケット分類分け（Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）方式においても、探索結果をキャッシュして再利用することによって、処理性能の向上を期待することができる。一方、最新のルールセットに基づく通信処理・制御を行うためには、探索木群への変更に応じて、キャッシュされた情報も適切に更新される必要がある。【００２１】
しかしながら、上記特許文献２に開示された技術は、単一の探索木を前提としたものである。該技術を、探索木が複数存在する場合に適用すると、パケットを受信する都度、全ての探索木それぞれについてカウンタ値を参照して、更新の有無を確認する処理が実行される。したがって、複数の探索木が存在する場合、パケット受信処理におけるデータ参照回数が増え、処理性能が悪化するという問題が発生する。かかる問題は、特に、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、キャッシュメモリを含む階層メモリ構成を備えたメモリとからなるコンピュータにおいて上記のような処理が実行される場合に、より顕著となる。【００２２】
つまり、カウンタ値は、探索木のノード毎に存在し、各パケットは、典型的には、異なるノードに含まれるルールに適合される。このため、カウンタ値へのメモリアクセスは、メモリアドレス空間において離散的な領域（アドレス）に対して実行される。メモリアクセスが離散的な領域に対して実行される場合、キャッシュメモリによるメモリアクセス遅延隠蔽効果が得難くなる。これにより、パケットの処理に要する時間が長くなるという問題が、より顕著に発生する。【００２３】
［本発明の目的］
本発明は、かかる問題に鑑みてなされたものである。即ち、本発明は、データ処理（例えばパケット処理）に用いる情報エントリを探索する際に用いる探索木を複数有する場合であっても、情報エントリの探索に要する負荷を低減することができるデータ処理装置等を提供することを、主たる目的の一つとする。
【課題を解決するための手段】
【００２４】
前述の課題を解決するため、本発明の一態様に係るデータ処理装置等は、主に、次のような構成を採用している。【００２５】
（１）本発明の一態様に係るデータ処理装置は、
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した上記第１の情報エントリを用いて上記データを処理する場合において、各上記探索木を構成するノードである中間ノードおよびリーフノードを上記データ識別情報の探索空間に対応付けて探索した際に得られた上記探索木による上記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、上記データを処理する際に、当該データに関する上記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理するデータ処理装置であって、
１ないし複数の上記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化手段と、
上記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、上記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの上記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶手段と、
上記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの上記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた上記ノードの更新履歴情報を更新するとともに、当該ノードを含む上記探索木が属する上記探索木グループのベース探索木について上記操作対象データ識別情報と重複する探索空間に対応付けられた上記ノードの共有更新履歴情報を更新する更新手段と、
上記第２の情報エントリとして、上記探索木による上記第１の情報エントリの探索結果として得られる、各上記探索木における探索によって到達したノードを示すノード識別子と当該ノードの上記更新履歴情報および上記共有更新履歴情報とのキャッシュを記憶する情報エントリ記憶手段と、
上記第２の情報エントリを使用したデータ処理を行う際に、上記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する上記ノードの上記共有更新履歴情報のキャッシュと当該ノードの最新の上記共有更新履歴情報とを、各上記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む上記ベース探索木が属する上記探索木グループの各上記探索木について、上記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する各上記ノードの上記更新履歴情報のキャッシュと各当該ノードの最新の上記更新履歴情報とを比較し、両者に不整合があった場合は、上記情報エントリ記憶手段に記憶された当該第２の情報エントリは無効であるものと判定する再評価手段と
を備える。【００２６】
（２）本発明の一態様に係る情報エントリ管理方法は、
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した上記第１の情報エントリを用いて上記データを処理する場合において、各上記探索木を構成するノードである中間ノードおよびリーフノードを上記データ識別情報の探索空間に対応付けて探索した際に得られた上記探索木による上記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、上記データを処理する際に、当該データに関する上記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理する情報エントリ管理方法であって、  １ないし複数の上記探索木をグループ化し、各探索木グループにおけるベース探索木を選択し、
上記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、上記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの上記ノードの更新の履歴を示す共有更新履歴情報を記憶し、
上記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの上記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた上記ノードの更新履歴情報を更新するとともに、当該ノードを含む上記探索木が属する上記探索木グループのベース探索木について上記操作対象データ識別情報と重複する探索空間に対応付けられた上記ノードの共有更新履歴情報を更新し、
上記第２の情報エントリとして、上記探索木による上記第１の情報エントリの探索結果として得られる、各上記探索木における探索によって到達したノードを示すノード識別子と当該ノードの上記更新履歴情報および上記共有更新履歴情報とのキャッシュを記憶し、
上記第２の情報エントリを使用したデータ処理を行う際に、上記記憶された当該第２の情報エントリに関する上記ノードの上記共有更新履歴情報のキャッシュと当該ノードの最新の上記共有更新履歴情報とを、各上記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む上記ベース探索木が属する上記探索木グループの各上記探索木について、上記記憶された当該第２の情報エントリに関する各上記ノードの上記更新履歴情報のキャッシュと各当該ノードの最新の上記更新履歴情報とを比較し、両者に不整合があった場合は、上記記憶された当該第２の情報エントリは無効であると判定することで、第２の情報エントリを再評価する。【００２７】
（３）本発明の一態様に係る情報エントリ管理プログラムは、上記（２）に記載の情報エントリ管理方法を、コンピュータによって実行可能なプログラムとして実施する。【００２８】
また、上記本発明の目的は、上記構成を有するデータ処理装置、データ処理方法をコンピュータによって実現する上記情報エントリ管理プログラムが格納されているコンピュータ読み取り可能な記録媒体等によっても達成される。
【発明の効果】
【００２９】
本発明によれば、以下のような効果を奏することができる。【００３０】
すなわち、本発明によれば、データ処理（例えばパケット処理）に用いる情報エントリを探索する際に用いる探索木を複数有する場合であっても、情報エントリの探索に要する負荷を低減することができる。
【図面の簡単な説明】
【００３１】
【図１】図１は、本発明の実施の形態に係るデータ処理装置のブロック構成の一例を示すブロック構成図である。
【図２】図２は、図１に示したデータ処理装置の探索木制御部の詳細なブロック構成の一例を示すブロック構成図である。
【図３】図３は、図１に示したデータ処理装置のキャッシュテーブル制御部の詳細なブロック構成の一例を示すブロック構成図である。
【図４】図４は、図１に示したデータ処理装置において使用されるルールの一構成例を説明するための表である。
【図５】図５は、図１に示したデータ処理装置において使用される探索木に係る情報およびノードに係る情報の一構成例を説明するための表である。
【図６】図６は、図１に示したデータ処理装置のキャッシュテーブル記憶部に記憶される、キャッシュテーブルおよびキャッシュエントリに関する情報の一例を示す表である。
【図７】図７は、図１に示したデータ処理装置の探索木制御部における探索木初期化部が探索木記憶部およびルール記憶部それぞれに記憶される探索木およびルールセットを初期化する際の動作の一例を示すフローチャートである。
【図８】図８は、図１に示したデータ処理装置の探索木制御部における探索木初期化部が探索木構築処理を行う際の動作の一例を示すフローチャートである。
【図９】図９は、図８のフローチャートのステップＳ１１２において実行される探索木構築サブ処理Ａの詳細な動作の一例を示すフローチャートである。
【図１０】図１０は、図１に示したデータ処理装置の探索木制御部におけるルール更新部が、探索木記憶部およびルール記憶部それぞれに記憶される探索木およびルールセットを更新する際の動作の一例を示すフローチャートである。
【図１１】図１１は、図１０のフローチャートのステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作の一例を示すフローチャートである。
【図１２】図１２は、図１１のフローチャートのステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作の一例を示すフローチャートである。
【図１３】図１３は、図１０のフローチャートのステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作の一例を示すフローチャートである。
【図１４】図１４は、図１０のフローチャートのステップＳ１３９において実行されるルール更新サブ処理Ｃの詳細な動作の一例を示すフローチャートである。
【図１５】図１５は、図１に示したデータ処理装置の探索木制御部における探索木探索部が、探索木記憶部およびルール記憶部それぞれに記憶される探索木およびルールセットを参照して与えられたキーに適合するルールを探索する際の動作の一例を示すフローチャートである。
【図１６】図１６は、図１５のフローチャートのステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作の一例を示すフローチャートである。
【図１７】図１７は、図１に示したデータ処理装置のパケット処理部がパケットを受信した際の動作の一例を示すフローチャートである。
【図１８】図１８は、図１に示したデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ作成部がキャッシュエントリを作成する際の動作の一例を示すフローチャートである。
【図１９】図１９は、図１に示したデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ探索部がキャッシュエントリを探索する際の動作の一例を示すフローチャートである。
【図２０】図２０は、図１に示したデータ処理装置のキャッシュテーブル制御部におけるキャッシュエントリ再評価部がキャッシュエントリを再評価する際の動作の一例を示すフローチャートである。
【図２１Ａ】図２１Aは、図１に示したデータ処理装置の探索木制御部における探索木初期化部がルールセットをルールの特徴に基づいて分割する際のサブルールセット例を示す説明図（１／２）である。
【図２１Ｂ】図２１Bは、図１に示したデータ処理装置の探索木制御部における探索木初期化部がルールセットをルールの特徴に基づいて分割する際のサブルールセット例を示す説明図（２／２）である。
【図２２】図２２は、図１に示したデータ処理装置の探索木制御部における探索木初期化部により作成される探索木グループの一例を示す表である。
【図２３】図２３は、ルールセットの一例を示す模式図である。
【図２４】図２４は、探索木の一例を示す模式図である。
【図２５】図２５は、探索木のノードに係る情報の一例を示す表である。
【図２６】図２６は、本発明の実施の形態に係るデータ処理装置を実現可能な情報処理装置のハードウェア構成を例示する図面である。
【発明を実施するための形態】
【００３２】
以下、本発明によるデータ処理装置等の好適な実施形態について添付図を参照して説明する。なお、以下においては、本発明によるデータ処理装置および情報エントリ管理方法の実施形態について説明する。かかる情報エントリ管理方法は、コンピュータにより実行可能な情報エントリ管理プログラムとして実施されてもよい。係る情報エントリ管理プログラムは、コンピュータにより読み取り可能な記録媒体に記録されてもよい。また、以下の各図面に付した図面参照符号は、理解を助けるための一例として、各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。
【００３３】
本発明の実施形態の詳細な説明に先立って、本発明に係るデータ処理装置等について、その概要をまず説明する。
【００３４】
本発明の実施形態に係るデータ処理装置は、処理対象とするデータを処理する方法を決定する第１の情報エントリを、上記データを適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から、１ないし複数の探索木を用いて探索する。
【００３５】
データ処理装置は、探索した第１の情報エントリを用いて上記データを処理する場合、各探索木を構成するノードである中間ノードおよびリーフノードを、上記データ識別情報の探索空間に対応付けて探索する。そして、探索木による第１の情報エントリの探索結果を、第２の情報エントリとして記憶する。データ処理装置は、データを処理する際に、当該データに関する第２の情報エントリが記憶されていた場合、第２の情報エントリを使用して当該データを処理する。
【００３６】
該データ処理装置は、１ないし複数の上記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化部（探索木初期化手段）を有する。
【００３７】
また、該データ処理装置は、以下のような処理を実行する探索木記憶部（探索木記憶手段）を備える。即ち、当該探索木記憶部（探索木記憶手段）は、上記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、当該ノードの更新の履歴を示す更新履歴情報、および、当該探索木を構成するいずれかの上記ノードの更新の履歴を示す共有更新履歴情報を記憶する。
【００３８】
また、データ処理装置は、以下のような処理を実行する更新部（更新手段）を備える。即ち、係る更新部は、第１の情報エントリの内容を操作した際に、操作された第１の情報エントリにおけるデータ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられたノードの更新履歴情報を更新する。また、更新部は、当該ノードを含む上記探索木が属する上記探索木グループのベース探索木について、上記操作対象データ識別情報と重複する探索空間に対応付けられた上記ノードの共有更新履歴情報を更新する。
【００３９】
また、該データ処理装置は、以下のような処理を実行する情報エントリ記憶部（情報エントリ記憶手段）を備える。即ち、情報エントリ記憶部は、探索木による第１の情報エントリの探索結果として得られる、各探索木における探索によって到達したノードを示すノード識別子と、当該ノードの更新履歴情報および共有更新履歴情報と、を含むキャッシュを、第２の情報エントリとして記憶する。
【００４０】
また、該データ処理装置は、以下のような処理を実行する再評価部（再評価手段）を備える。即ち、係る再評価部は、第２の情報エントリを使用したデータ処理を行う際、上記情報エントリ記憶部に記憶された第２の情報エントリに関する、ノードの共有更新履歴情報のキャッシュと、当該ノードの最新の共有更新履歴情報とを、各上記ベース探索木について比較する。係る比較処理の結果、両者に不整合があった場合、再評価部は、当該ノードを含むベース探索木が属する探索木グループの各探索木について、第２の情報エントリ記憶部に記憶された第２の情報エントリに関する各ノードの更新履歴情報のキャッシュと、各ノードの最新の更新履歴情報とを比較する。再評価部は、両者に不整合があった場合は、上記第２の情報エントリ記憶部に記憶された第２の情報エントリは無効であると判定する。
【００４１】
［実施の形態の説明］
以下に記載する本実施の形態の説明においては、一例として、データ処理としてパケット処理を実施し、当該データ処理に用いられる情報エントリとしてルールを使用する場合について説明する。また、本実施の形態においてはパケット（通信パケット）として、ＩＰｖ４（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ４）パケットを扱う例を示している。しかし、本発明は、上記のようなパケット処理の場合に限定されず、他の一般的なデータ処理についても広く適用可能である。
【００４２】
[実施の形態の構成例]
まず、本実施の形態の構成例について、図１を用いて説明する。図１は、本発明の実施の形態に係るデータ処理装置のブロック構成の一例を示すブロック構成図である。図１に例示するデータ処理装置１は、探索木制御部１０と、探索木記憶部２０と、ルール記憶部３０と、キャッシュテーブル制御部４０と、キャッシュテーブル記憶部５０と、パケット処理部６０と、通信ＩＦ部７０と、データ処理装置制御部８０と、を含む。
【００４３】
探索木制御部１０は、探索木記憶部２０に記憶される探索木およびルール記憶部３０に記憶されるルールの管理を行う。具体的には、探索木制御部１０は、例えば、探索木の初期化や探索、ルールの追加等を行う部位である。
【００４４】
探索木記憶部２０は、詳細は後述するが、主に、受信パケット（すなわち処理対象のデータの一種）に対応するルール（すなわち情報エントリの一種、第１の情報エントリ）を探索する際に用いられる探索木を記憶する。探索木記憶部２０に記憶される探索木は、１つまたは複数のノードによって構成される。該ノードは、中間ノードまたはリーフノードのいずれかである。また、探索木記憶部２０は、探索木のグループ化に係る情報を記憶する。探索木記憶部２０が記憶する探索木の数は、通常、２個以上であるが、一つであってもよい。探索木記憶部２０は、例えば、メモリを用いて探索木を記憶する。各探索木、各ノードおよび各探索木グループには、それぞれを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作の際に使用される。
【００４５】
ルール記憶部３０は、パケット処理するための情報であるルール（すなわち情報エントリの一種、第１の情報エントリ）の集合（ルールセット、サブルールセット）を記憶する。ルール記憶部３０は、例えば、メモリを用いてルールの集合を記憶する。ルール記憶部３０は、例えば、配列やハッシュテーブルなどのデータ構造を使用して、ルールの集合をメモリに記憶する。各ルールおよび各ルールセットや各サブルールセットには、それらを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作の際に使用される。
【００４６】
キャッシュテーブル制御部４０は、キャッシュテーブル記憶部５０に記憶されるキャッシュエントリの管理を行う。キャッシュテーブル制御部４０は、例えば、キャッシュエントリの作成や探索等を行う。
【００４７】
キャッシュテーブル記憶部５０は、探索木による探索の結果を含む（キャッシュする）キャッシュエントリ（すなわち情報エントリの一種、第２の情報エントリ）を記憶する部位である。キャッシュテーブル記憶部５０は、例えば、情報エントリ記憶手段として機能する。キャッシュテーブル記憶部５０は、例えば、メモリを用いてキャッシュエントリを記憶する。キャッシュテーブル記憶部５０は、例えば、ハッシュテーブルのデータ構造を使用してキャッシュエントリをメモリに記憶する。各キャッシュエントリにはそれぞれを一意に識別する識別子が割り当てられ、当該識別子が参照等の操作の際に使用される。
【００４８】
パケット処理部６０は、通信ＩＦ部７０からパケット（すなわち処理対象のデータの一種）を受信し、受信したパケットの処理を行う。その際、パケット処理部６０は、探索木制御部１０およびキャッシュテーブル制御部４０を使用して、当該パケットの処理に用いる情報エントリ（ノード、ルール、キャッシュエントリ）を探索し、探索結果を用いて当該パケットを処理する。なお、パケット処理部６０は、処理対象のデータの一種（パケット）を処理する、データ処理実行手段として機能してもよい。
【００４９】
通信ＩＦ部７０は、データ処理装置１と通信ネットワーク（図１には図示していない）とを接続するインタフェースであり、当該通信ネットワークで使用される通信プロトコル（以下、単に「プロトコル」と記載する場合がある）にしたがってパケットの送受信を行う。
【００５０】
データ処理装置制御部８０は、データ処理装置１がルールセットやサブルールセットにしたがってパケットを処理するように制御する。データ処理装置制御部８０は、例えば、データ処理装置１が起動する際、探索木初期化部１１（図２）に初期ルールセットを渡して初期化するように指示する。データ処理装置制御部８０は、当該初期ルールセットをデータ処理装置１が具備する記憶装置（図１には図示していない）から読み込んでもよい。また、データ処理装置制御部８０は、当該初期ルールセットを、他の制御装置（図１には図示していない）から受信してもよい。また、データ処理装置制御部８０は、ユーザインタフェース（図１には図示していない）を介して、ユーザからルール更新の命令を受け取った際に、探索木制御部１０に対してルール更新を指示する。また、データ処理装置制御部８０は、他の制御装置（図１には図示していない）からルール更新の命令を受信した際に、探索木制御部１０に対してルール更新を指示してもよい。
【００５１】
次に、図１に示した本実施の形態のデータ処理装置１において使用されるルールについて図４の表を用いて説明する。図４は、図１に示したデータ処理装置１において使用されるルールの一構成例を説明する表であり、図１のデータ処理装置１のルール記憶部３０に記憶されるルールの構成例を示している。
【００５２】
図４の表の項目欄３１に示すように、各ルールは、適用対象を示すデータ識別情報の一種であるマッチ条件や優先度、さらには、アクション、統計情報、削除フラグを含んで構成される。各ルールのマッチ条件は、図４の表の説明欄３２に示すように、当該ルールに適合するパケットが持つフィールド値の条件を規定する。例えば、本実施の形態においては、以下の五つのフィールド（５タプル（５Ｔｕｐｌｅ））をマッチ条件（データ識別情報の一種）として使用する。即ち、それら五つのフィールドは、開始送信先ＩＰアドレスおよび終了送信先ＩＰアドレス、開始送信元ＩＰアドレスおよび終了送信元ＩＰアドレス、開始送信先ポート番号および終了送信先ポート番号、開始送信元ポート番号および終了送信元ポート番号、開始プロトコル番号および終了プロトコル番号である。
【００５３】
例えば、本実施の形態においては、マッチ条件の一例として、以下のような具体例が図４の表の例欄３３に示されている。即ち、係る具体例においては、（開始および終了）送信先ＩＰアドレスは、‘０．０．０．０’〜‘２５５．２５５．２５５．２５５’の範囲内である。また、（開始および終了）送信元ＩＰアドレスは、‘１０．０．０．０’〜‘１０．２５５．２５５．２５５’の範囲内である。また、（開始および終了）送信先ポート番号は‘８０’である。また、（開始および終了）送信元ポート番号は、‘０’〜‘６５５３５’の範囲内である。また、プロトコル番号は‘１７’である。ただし、本発明は、かかるフィールド構成のみに限定されるものではない。
【００５４】
また、各ルールの優先度は、或るパケットに対して複数のルールが適合する場合に、採用されるルールを選択するために使用される。各ルールの優先度は、図４の表の説明欄３２に示すように、例えば、各ルールそれぞれの優先度を表す数値（例えば非負整数）であり、大きい数値ほど高い優先度を示してもよい。例えば、図４の表の例欄３３に示す当該ルールの優先度には、非負整数‘１００’が設定されている。
【００５５】
また、各ルールのアクションは、図４の表の説明欄３２に示すように、当該ルールに適合したパケットに対して実行する処理内容（処理方法）を規定する。適合したパケットに対するルールのアクションが、パケットの送受信に関わる場合には、図４の表の例欄３３に示すように、当該パケットが通信ＩＦ部７０に対して出力される。なお、各ルールそれぞれに含まれるアクションの数は、１つに限定されず、０であっても、あるいは、２つ以上であってもよい。ルールのアクションの一例を以下に示す。ただし、本実施形態は、ルールのアクションとして以下の処理に限定されるものではない。
【００５６】
（ａ）指定された通信ＩＦ部７０からパケットを出力する。
【００５７】
（ｂ）パケットの送信先ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスを指定された値に変更する。
【００５８】
（ｃ）パケットの送信元ＭＡＣアドレスを指定された値に変更する。
【００５９】
（ｄ）パケットの送信先ＩＰアドレスを指定された値に変更する。
【００６０】
（ｅ）パケットの送信元ＩＰアドレスを指定された値に変更する。
【００６１】
（ｆ）パケットの送信先ポート番号を指定された値に変更する。
【００６２】
（ｇ）パケットの送信元ポート番号を指定された値に変更する。
【００６３】
（ｈ）パケットにＶＬＡＮ（Ｖｉｒｔｕａｌ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）タグを追加する。
【００６４】
（ｉ）パケットのＶＬＡＮタグを削除する。
【００６５】
（ｊ）パケットのＶＬＡＮタグを変更する。
【００６６】
（ｋ）パケットを破棄する。
【００６７】
次に、各ルールの統計情報は、図４の表の説明欄３２に示すように、当該ルールに適合して、処理されたパケット群に関する統計値を表す。係る各ルールの統計情報は、例えば、図４の表の例欄３３に示すように、合計送信パケットサイズ、合計受信パケットサイズ、送信パケット数、受信パケット数、等である。
【００６８】
また、各ルールの削除フラグは、図４の表の説明欄３２に示すように、当該ルールに関して削除が要求されたものの、当該ルールが使用中であることから、削除処理が延期されているか否かを示すフラグである。
【００６９】
次に、図１に示した本実施の形態のデータ処理装置１における、探索木記憶部２０が記憶する探索木に係る情報およびノードに係る情報について図５の表を用いて説明する。
【００７０】
探索木記憶部２０は、探索木の集合と、探索木グループリストと、ノードの集合と、を記憶する。図５は、図１に示したデータ処理装置１において使用される探索木に係る情報およびノードに係る情報の一構成例を説明する表である。図５は、図１のデータ処理装置１の探索木記憶部２０に記憶される探索木に係る情報およびノードに係る情報の構成例を示す。図５における（Ａ）部分には、探索木に係る情報および探索木グループリストに係る情報が例示されている。また、図５における（Ｂ）部分には、ノードに係る情報が例示されている。なお、本実施の形態におけるノードは、中間ノードまたはリーフノードのいずれかである。図５の（Ｂ）部分においては、ノード種別欄２４に示すように、中間ノード・リーフノードともに共通に有する情報は“中間ノード・リーフノード共通”の部分に、中間ノードのみが有する情報は“中間ノード”の部分に、リーフノードのみが有する情報は“リーフノード”の部分に示されている。
【００７１】
また、図５の（Ｂ）部分の項目欄２５に示すノードの部分空間とは、当該ノードの探索対象である、当該ノードが表す部分空間の情報である。本部分空間の情報は、図２３〜図２５を用いて先に説明した一般的な探索木の例において、図２５の“ノードが表す部分空間”欄に記載の情報に相当する。図２５に示した例においては、探索空間の次元数が２次元の場合を示した。これに対して、本実施の形態におけるルールのマッチ条件は、前述のように、５タプル（５Ｔｕｐｌｅ）であることから、本実施の形態における探索空間の次元数は５次元となる。
【００７２】
したがって、図５の（Ｂ）部分におけるノード種別欄２４の“中間ノード”において、項目欄２５に示す“カット（Ｃｕｔ）する次元”および“カット（Ｃｕｔ）数”は、探索空間を５次元にカッティング（Ｃｕｔｔｉｎｇ）して、子ノードを作成する際に使用する情報である。例えば、図２５の例において、ルートノードに関する“カット（Ｃｕｔ）する次元”および“カット（Ｃｕｔ）数”の情報は、それぞれ、‘Ｘ軸’および‘４’である。また、図２５の例において、ノード１に関する“カット（Ｃｕｔ）する次元”および“カット（Ｃｕｔ）数”の情報は、それぞれ、‘Ｙ軸’および‘２’である。なお、探索木を作成する際、或るノードにおいて同時に複数の次元に関するカット（Ｃｕｔ）が実行されてもよい。その場合、“カット（Ｃｕｔ）する次元”および“カット（Ｃｕｔ）数”の組は、複数の次元毎に記憶される。
【００７３】
また、探索木に係る情報については、図５の（Ａ）部分における種別欄２１に示すように、探索木それぞれに係る情報と、１ないし複数の探索木をグループ化した探索木グループに係る情報と、が記憶されている。探索木それぞれに係る情報には、項目欄２２および説明欄２３に示すように、ルートとなるノード（ルートノード）を示すルートノード識別子、対応するサブルールセットを示すサブルールセット識別子、属する探索木グループを示す探索木グループ識別子、が含まれる。また、探索木グループに係る情報には、属する各探索木を示す探索木識別子リスト、ベースとなるベース探索木を示すベース探索木識別子、が含まれる。
【００７４】
次に、本発明に係る実施の形態において使用されるキャッシュテーブルおよびキャッシュエントリについて説明する。キャッシュエントリは、探索木を用いた、受信パケットに適合するルールの探索結果を記憶して再利用するために用いられる。探索木の探索処理への入力としては、受信パケットにおいてルールのマッチ条件として使用されるフィールド群（本実施の形態においては５フィールド、すなわち５タプル（５Ｔｕｐｌｅ））が用いられる。以降、当該フィールド群の値を‘キー’と呼称する。キーが同じパケット群に対して、同じルールセットによるルール探索を行った場合、同じルールが得られる。したがって、本実施の形態においては、データ処理装置１は、キーごとにキャッシュエントリを作成して使用する。なお、以降、キーが同じパケット群のことを‘フロー’と呼称する。
【００７５】
図６は、図１に示したデータ処理装置１のキャッシュテーブル記憶部５０に記憶される、キャッシュテーブルおよびキャッシュエントリに関する情報の一例を示す表であり、図６における（Ａ）の部分は、キャッシュエントリに係る情報の一例を示す。図６における（Ｂ）の部分は、キャッシュエントリノード状態の一例を示す。図６における（A）（B)いずれの部分も、本実施の形態が使用するキャッシュエントリに係る情報の一構成例を示している。本実施の形態においては、オープン・アドレス（Ｏｐｅｎ  Ａｄｄｒｅｓｓ）型のハッシュテーブルを使用して、キャッシュエントリを記憶する例を示している。ただし、本実施形態は、このようなオープン・アドレス型のハッシュテーブルに限定されるものではない。
【００７６】
キャッシュテーブルのバケツリスト（Ｂｕｃｋｅｔ  Ｌｉｓｔ）は、例えば、キャッシュエントリの配列として実現することができる。この場合、第Ｎ番目のバケツ（Ｂｕｃｋｅｔ）のＭ番目のキャッシュエントリは、バケツリスト（Ｂｕｃｋｅｔ  Ｌｉｓｔ）における第（Ｎ−１）＊（Ｍ−１）番目の要素にアクセスすることによって参照することができる。キャッシュエントリに係る情報は、図６の（Ａ）部分の項目欄５１に示すように、使用中フラグ、キー、ルール識別子、最終使用時刻、ノード状態リストに関する情報を含む。
【００７７】
図６の（Ａ）部分の説明欄５２に示すように、使用中フラグは、当該キャッシュエントリが使用中であるか否かを示すフラグである。使用中フラグがオンであれば、当該キャッシュエントリが使用中であることを示す。キーは、当該キャッシュエントリが表すフローに関するキーであり、ハッシュテーブル内探索用の探索キーとして使用される。また、ルール識別子は、当該キャッシュエントリに該当するパケットに適合するルールの識別子である。最終使用時刻は、当該キャッシュエントリを最後に使用した際の時刻を示す情報である。また、ノード状態リストは、図６の（Ｂ）部分に示すような、当該キャッシュエントリが最後に使用された際の、当該キャッシュエントリが表すフローが属するノードの状態（探索木毎の）リストを示している。
【００７８】
つまり、図６の（Ｂ）部分に示すキャッシュエントリのノード状態リストは、当該キャッシュエントリのキーを用いてルールを探索した際に最終的に到達したノード（探索木毎）の情報を記憶する。図６の（Ｂ）部分における項目欄５３に示すように、キャッシュエントリのノード状態は、探索木識別子、ノード識別子、更新カウンタキャッシュ、共有更新カウンタキャッシュを含む。
【００７９】
図６の（Ｂ）部分における説明欄５４に示すように、ノード状態の探索木識別子は、当該ノード状態が示す探索木の識別子を示す。また、ノード状態のノード識別子は、当該キャッシュエントリが表すフローが当該探索木において属するノードの識別子である。また、ノード状態の更新カウンタキャッシュおよび共有更新カウンタキャッシュには、それぞれ、当該キャッシュエントリが最後に使用された際の、当該ノードの更新カウンタの値および共有更新カウンタの値が記憶される。なお、共有更新カウンタキャッシュは、ベース探索木のノードについてのみ使用される。
【００８０】
次に、図１に示したデータ処理装置１の探索木制御部１０の詳細な構成例について、図２のブロック構成図を用いて説明する。図２は、図１に示したデータ処理装置１の探索木制御部１０の詳細なブロック構成の一例を示すブロック構成図である。図２に示すように、探索木制御部１０は、探索木初期化部１１と、ルール更新部１２と、探索木探索部１３と、更新カウンタ取得部１４と、を含む。
【００８１】
探索木初期化部１１は、初期状態において使用するルールセット（初期ルールセット）を基にして、探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールに係る情報を初期化する。当該初期ルールセットは、データ処理装置１が具備する記憶装置（図２には図示されていない）にあらかじめ記憶されていてもよい。また、当該初期ルールセットは、他の制御装置（図２には図示されていない）から与えられてもよい。
【００８２】
また、ルール更新部１２は、例えば図１に示したデータ処理装置制御部８０からの要求に応じて、探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルール（第１の情報エントリの一種）に係る情報を更新する部位である。ルール更新部１２は、例えば、更新手段として機能する。ルール更新部１２は、データ処理装置制御部８０からの要求に含まれる操作種別（追加、変更、削除、のいずれか）およびルールを、パラメータとして受け取る。データ処理装置制御部８０からの要求に含まれる操作種別がルール更新（ルール変更）の場合、該当するルールの優先度およびアクションの変更を要求することは可能であるが、マッチ条件は変更することができない。
【００８３】
また、探索木探索部１３は、例えば図１に示したパケット処理部６０からの要求に応じて、指定されたキーに適合するルールを探索する。探索木探索部１３は、探索に係るパラメータとして、探索に使用すべきキー（探索キー）をパケット処理部６０から受け取る。探索木探索部１３は、探索キーに適合する最高優先度のルールの識別子（最高優先度のルールが検出された場合）、および、探索木における探索において最終的に到達したノード（中間ノードもしくはリーフノード）の識別子（探索木毎）のリストを要求元に返す。
【００８４】
また、更新カウンタ取得部１４は、例えば図１に示したパケット処理部６０からの要求に応じて、指定されたノードの更新カウンタの最新の値および共有更新カウンタの最新の値を取得する。
【００８５】
次に、図１に示したデータ処理装置１のキャッシュテーブル制御部４０の詳細な構成例について、図３のブロック構成図を用いて説明する。図３は、図１に示したデータ処理装置１のキャッシュテーブル制御部４０の詳細なブロック構成の一例を示すブロック構成図である。図３に示すように、キャッシュテーブル制御部４０は、キャッシュエントリ作成部４１と、キャッシュエントリ探索部４２と、キャッシュエントリ再評価部４３と、を含む。
【００８６】
キャッシュエントリ作成部４１は、例えば図１に示したデータ処理装置１のパケット処理部６０からの要求に応じて、キャッシュエントリを作成する。また、キャッシュエントリ作成部４１は、指定されたキーに対応するバケツ（Ｂｕｃｋｅｔ）に空きがない場合、当該バケツ（Ｂｕｃｋｅｔ）内のキャッシュエントリを一つ削除し、新しいキャッシュエントリを作成する。
【００８７】
また、キャッシュエントリ探索部４２は、例えば図１に示したデータ処理装置１のパケット処理部６０からの要求に応じて、キャッシュエントリを探索する。キャッシュエントリ探索部４２は、パラメータとしてキーを受け取り、受け取った当該キーに対応するキャッシュエントリを探索して、探索したキャッシュエントリを要求元に返す。
【００８８】
また、キャッシュエントリ再評価部４３は、例えば図１に示したデータ処理装置１のパケット処理部６０からの要求に応じて、キャッシュエントリを再評価する。キャッシュエントリ再評価部４３は、キャッシュエントリの識別子を受け取る。ここで、キャッシュエントリの再評価とは、指定されたキャッシュエントリとして記憶している探索木探索結果（当該キャッシュエントリが表すフローに適合するルール）が、最新のルールセットの状態においても有効か否かを確認することである。キャッシュエントリ再評価部４３は、あるキャッシュエントリが最新のルールセットの状態において有効か否かを確認するために、当該キャッシュエントリとして記憶された、以下のような情報を含むノード状態リストと、関連するノードの更新カウンタおよび共有更新カウンタの最新の値とを使用する。
【００８９】
（ａ）当該フローが各探索木において属するノード、
（ｂ）当該キャッシュエントリが最後に使用された際の、各当該ノードの更新カウンタの値、
（ｃ）当該キャッシュエントリが最後に使用された際の、各当該ノードの共有更新カウンタの値（ベース探索木のノードのみ有効）。
【００９０】
[実施の形態の動作例]
次に、本実施の形態の構成例として図１〜図３に例示したデータ処理装置１における以下の各動作について、その一例を、図面を参照しながら詳細に説明する。
（Ａ）探索木初期化処理、
（Ｂ）ルール更新処理、
（Ｃ）ルール探索処理、
（Ｄ）パケット処理、
（Ｅ）キャッシュエントリ作成処理、
（Ｆ）キャッシュエントリ探索処理、
（Ｇ）キャッシュエントリ再評価処理。
【００９１】
＜（Ａ）探索木初期化処理＞
まず、図７〜図９のフローチャートを用いて、探索木初期化処理の動作例について説明する。図７は、図１に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１が、探索木記憶部２０およびルール記憶部３０にそれぞれ記憶される探索木およびルールセットを初期化する際の、動作の一例を示すフローチャートである。図７のフローチャートに例示する本探索木初期化処理の動作は、例えば、データ処理装置１の起動時に開始されてもよく、データ処理装置制御部８０からの初期化要求に応じて開始されてもよい。なお、本探索木初期化処理の動作の開始に際して、探索木制御部１０における探索木初期化部１１には、初期状態で使用するルールセット（すなわち初期ルールセット）がパラメータとして与えられる。
【００９２】
図７のフローチャートにおいて、探索木初期化部１１は、まず、パラメータとして与えられた初期ルールセットを、各ルールの特徴を用いてサブルールセットに分割し、ルール記憶部３０に記憶させる（ステップＳ１０１）。上記サブルールセットへの分割は、周知の技術を用いて行われて良く、例えば、上記非特許文献１に記載の分割方法を用いてもよい。
【００９３】
当該サブルールセットへの分割方法においては、まず、ルールのマッチ条件として使用される各フィールドについて、該当する当該フィールドにおけるマッチ条件の大小を判定する閾値を設定する。例えば、プロトコル番号フィールド（採り得る値０〜２５５）について閾値”０．５”を設定する。そして、或るルールの”（終了プロトコル番号）−（開始プロトコル番号）”が、”１２７（＝２５５＊０．５（整数部））”以上であれば、探索木初期化部１１が、当該ルールは、プロトコル番号について大きいと判定する。また、１２７未満であれば、探索木初期化部１１は、当該ルールは、プロトコル番号について小さいと判定する。
【００９４】
当該サブルールセットへの分割方法において、探索木初期化部１１は、各ルールの各フィールド（５タプル（５Ｔｕｐｌｅ））について、それぞれ大小判定を行う。次に、探索木初期化部１１は、各フィールドの大小判定結果が同じであるルール群を、一つのサブルールセットとする。探索木初期化部１１は、例えば、送信先ＩＰアドレスおよび送信先ポート番号のフィールドのみが大きく、残りのフィールドが小さいと判定されたルール群により一つのサブルールセットを構成する。ただし、マッチ条件が小さいフィールドの数が４以上のルール群については、纏めて一つのサブルールセットとする。サブルールセットの構成例を図２１Ａおよび図２１Ｂに例示する。このサブルールセットの構成例は図２１Ａおよび図２１Ｂの２つの図面で示してあり、図２１Ｂは図２１Ａの続きの部分を示す。即ち、図２１Ａおよび図２１Ｂは一続きの図面として理解するべき図面であるので、以下では両図面を一つの図面として纏めて図２１と称することとする。説明の便宜上、図２１Ａおよび図２１Ｂの上部には同じ内容の凡例を設けられている。但し、図２１Ａおよび図２１Ｂの両図を一体としてみる場合（即ち図２１Ａの下端に図２１Ｂの上端を接続した形で両図をみる場合）には、図２１Ｂ上部の凡例は省略されたものとして扱われてよい。図２１は、図１に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１が、ルールセットをルールの特徴に基づいて分割する際の、サブルールセットの例を示す説明図である。図２１には、ルールが、送信元ＩＰアドレス（ＩＰＳ）、送信先ＩＰアドレス（ＩＰＤ）、（通信）プロトコル（Ｐ）、送信元ポート（ＴＰＳ）、送信先ポート（ＴＰＤ）の５つのフィールド（５タプル）からなる場合の、サブルールセットの構成例が示されている。なお、図２１においては、各フィールドにおけるマッチ条件の指定が小さいフィールドを、ハッチング（網掛け）を施した四角形によって示している。
【００９５】
図２１のサブルールセット構成例において、図２１（図２１Ａ）における（ａ）部分は、マッチ条件の指定が５フィールド（５タプル）とも大きいルール群として‘サブセット５’の１個のサブルールセットが存在する場合を示す。また、図２１（図２１Ａ）の（ｂ）部分は、マッチ条件の指定が小さいフィールドの数が１個のルール群として、‘サブセット１−１’〜‘サブセット１−５’の５個のサブルールセットが存在する場合を示す。例えば、‘サブセット１−１’の場合は、ハッチングによって示しているように、送信元ＩＰアドレスのフィールドが、小さいフィールドであることを示している。
【００９６】
また、図２１（図２１Ａ）の（ｃ）部分は、マッチ条件の指定が小さいフィールドの数が２個のルール群として、‘サブセット２−１’〜‘サブセット２−１０’の１０個のサブルールセットが存在する場合を示している。例えば、‘サブセット２−１’の場合は、ハッチングによって示しているように、送信元ＩＰアドレスと送信先ＩＰアドレスとの２つのフィールドが、小さいフィールドであることを示している。また、図２１（図２１Ｂ）の（ｄ）は、マッチ条件の指定が小さいフィールドの数が３個のルール群として、‘サブセット３−１’〜‘サブセット３−１０’の１０個のサブルールセットが存在する場合を示している。例えば、‘サブセット３−１’の場合は、ハッチングによって示しているように、送信元ＩＰアドレスと送信先ＩＰアドレスとプロトコルとの３つのフィールドが、小さいフィールドであることを示している。
【００９７】
また、図２１（図２１Ｂ）の（ｅ）部分は、マッチ条件の指定が小さいフィールドの数が４個以上のルール群として、‘サブセット４’の１個のサブルールセットに纏められて収容される場合を示している。例えば、送信元ＩＰアドレスと送信先ＩＰアドレスとプロトコルと送信元ポートとの４つのフィールドが小さいフィールドである場合も、送信元ＩＰアドレスと送信先ＩＰアドレスとプロトコルと送信元ポートと送信先ポートの５つのフィールドが小さいフィールドである場合も、‘サブセット４’という一つのサブルールセットに纏めて収容される。
【００９８】
図７のフローチャートの説明に戻って、探索木初期化部１１は、次に、サブルールセット毎に探索木を構築する（ステップＳ１０２）。その動作の詳細については後述する。しかる後、探索木初期化部１１は、探索木グループと、各探索木グループのベース探索木と、を決定する（ステップＳ１０３）。ここで、探索木初期化部１１は、例えば、各探索木に含まれるルールの特徴を用いてあらかじめ定めたグループ化基準により、探索木をグループ化する。係るグループ化基準は、例えば、ルールのマッチ条件（データ識別情報の一種）の粒度を与える、以下に示すようなグループ化基準であってもよい。
【００９９】
（ａ）グループ化基準Ａ：マッチ条件の指定が５フィールドとも大きいルール群を収容する探索木（図２１の（ａ）部分の‘サブセット５’用探索木）は、単独で探索木グループを構成する。
【０１００】
（ｂ）グループ化基準Ｂ：マッチ条件の指定が小さいフィールド数が４以上のルール群を収容する探索木（図２１の（ｅ）部分の‘サブセット４’用探索木）についても、単独で探索木グループを構成するようにしてもよい。
【０１０１】
（ｃ）グループ化基準Ｃ：マッチ条件の指定が小さいフィールドの数が少ない（例えば１個の）ルール群を収容する探索木（図２１の（ｂ）部分の‘サブセット１−１’用探索木〜‘サブセット１−５’用探索木）は、それぞれ異なる探索木グループに含める。
【０１０２】
（ｄ）グループ化基準Ｄ：マッチ条件の指定の大小パターンが似ている探索木同士を同じ探索木グループに含め、似ていない探索木同士は別の探索木グループに含める。
【０１０３】
（ｄ−１）例えば、マッチ条件の指定が小さいフィールドを‘０’、大きいフィールドを‘１’と表し、各探索木についてマッチ条件の指定の大小パターンから５ビット２進数列を作成する。そして、各探索木について作成した５ビット２進数列間のハミング距離（具体的には、数値化されたハミング距離）を用いて、２つの探索木に関する類似度判定を行う。
【０１０４】
（ｄ−２）例えば、図２１の（ｃ）部分の‘サブセット２−５’用２進数列は‘１００１１’、図２１（ｄ）の‘サブセット３−７’用２進数列は‘１０００１’であり、その間のハミング距離は‘１’である。また、図２１の（ｃ）部分の‘サブセット２−７’用２進数列は‘１０１１０’であり、サブセット２−５用２進数列とのハミング距離は‘２’である。したがって、‘サブセット２−５’用探索木と同じ探索木グループに収容する探索木としては、ハミング距離が小さい‘サブセット３−７’用探索木の方が、‘サブセット２−７‘用探索木よりも望ましい。
【０１０５】
（ｅ）グループ化基準Ｅ：各探索木グループに含まれる探索木の数が、なるべく等しくなるようにする（ただし、グループ化基準Ａおよびグループ化基準Ｂによるグループを除く）。
【０１０６】
図２１のサブルールセット構成例における探索木初期化部１１によるグループ化の結果を示す探索木グループの一例を、図２２に示す。図２２は、図１に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１により作成される探索木グループの一例を示す表である。図２１のサブルールセット構成例の場合、前述のグループ化基準Ａ〜Ｅを適用することにより、図２２の探索木グループ欄１１１に示すように、サブルールセットは、探索木グループ１〜探索木グループ７の７個の探索木グループにグルーピングされる。
【０１０７】
例えば、探索木グループ１には、図２２の使用グループ化基準欄１１３に示すように、図２１に例示するサブルールセットに対して、グループ化基準Ｃ、Ｄ、Ｅを適用することによりグループ化された探索木が含まれる。即ち、図２２の所属探索木欄１１２に示すように、探索木グループ１には、図２１の‘サブセット１−１’、‘サブセット２−１’、‘サブセット２−２’、‘サブセット３−１’、‘サブセット３−３’の５個の探索木が属する。同様に、探索木グループ２には、図２１に例示するサブルールセットに対して、グループ化基準Ｃ、Ｄ、Ｅを適用することによりグループ化された探索木が含まれる。即ち、図２２の所属探索木欄１１２に示すように、探索木グループ２には、図２１の‘サブセット１−２’、‘サブセット２−５’、‘サブセット２−６’、‘サブセット３−７’、‘サブセット３−９’の５個の探索木が属する。また、探索木グループ６には、グループ化基準Ａを適用することにより、‘サブセット５’の１個の探索木が属する。探索木グループ７には、グループ化基準Ｂを適用することにより、‘サブセット４’の１個の探索木が属する。
【０１０８】
さらに、探索木初期化部１１は、例えば、決定された各探索木グループの中から、マッチ条件の指定が小さいフィールドの数が最も小さい（少ない）探索木を、当該探索木グループのベース探索木として選択する。図２２の例においては、探索木初期化部１１は、例えば、探索木グループ１のベース探索木として‘サブセット１−１’用探索木（マッチ条件の小さいフィールドの数が‘１’の探索木）を選択する。
【０１０９】
次に、図７のステップＳ１０２において、探索木初期化部１１がサブルールセット毎に探索木を構築する動作の一例について、図８および図９のフローチャートを参照して説明する。図８は、図１に示したデータ処理装置１の探索木制御部１０における探索木初期化部１１が、探索木構築処理を行う際の動作の一例を示すフローチャートであり、探索木初期化部１１が探索木を構築する際の動作の一例を示している。
【０１１０】
図８のフローチャートにおいて、探索木初期化部１１は、まず、構築する探索木のルートノードを割り当てる（ステップＳ１１１）。具体的には、探索木初期化部１１は、探索木記憶部２０にルートノードの情報を記憶するデータ領域を割り当て、当該ルートノードについて以下のような情報を設定する。
【０１１１】
（ａ）リーフノードフラグ：オフ、
（ｂ）親ノード識別子    ：無効値、
（ｃ）部分空間          ：下記の探索空間全体、
（ｃ−１）送信先ＩＰアドレス：０．０．０．０〜２５５．２５５．２５５．２５５、
（ｃ−２）送信元ＩＰアドレス：０．０．０．０〜２５５．２５５．２５５．２５５、
（ｃ−３）プロトコル番号    ：０〜２５５、
（ｃ−４）送信先ポート番号  ：０〜６５５３５、
（ｃ−５）送信元ポート番号  ：０〜６５５３５、
（ｄ）更新カウンタおよび共有更新カウンタ：０。
【０１１２】
次いで、探索木初期化部１１は、割り当てたルートノードについて、後述する探索木構築サブ処理Ａを実行する（ステップＳ１１２）。その際、探索木初期化部１１は、当該ルートノードと、処理対象のサブルールセットに含まれる全てのルールと、をパラメータとして使用する。
【０１１３】
次に、図８のフローチャートのステップＳ１１２において実行される探索木構築サブ処理Ａの詳細な動作について、図９のフローチャートを用いて説明する。図９は、図８のフローチャートのステップＳ１１２において実行される探索木構築サブ処理Ａの詳細な動作の一例を示すフローチャートである。本探索木構築サブ処理Ａは、パラメータとして、処理対象のノード（例えばノード識別子の形式、以降‘処理対象ノード’と記載）および当該ノードに含まれるルールの集合(例えばルール識別子のリストの形式、以降‘処理対象ルールセット’と記載)を受け取る。
【０１１４】
図９のフローチャートにおいて、探索木初期化部１１は、まず、処理対象ルールセットに含まれるルールの数があらかじめ定めた一定数（Ｂｉｎｔｈ）以下か否かを確認する（ステップＳ１２１）。ルールの数が一定数（Ｂｉｎｔｈ）以下ではなかった場合（ステップＳ１２１のＮO）、探索木初期化部１１は、処理対象ノードが表す部分空間をカット（Ｃｕｔ）する次元およびカット（Ｃｕｔ）数を決定する（ステップＳ１２２）。ここで、カット（Ｃｕｔ）する次元およびカット（Ｃｕｔ）数は、周知の技術を用いて決定されてもよく、例えば、係る技術として、上記非特許文献１および該非特許文献１が参照する文献に記載の分割方法が用いられてもよい。
【０１１５】
上記非特許文献１および該非特許文献１が参照する文献に記載の当該分割方法においては、処理対象ルールセットの各ルールのマッチ条件が、処理対象ノードの部分空間との共通部分に限定される。例えば、或るルールのプロトコル番号が１０〜２０であり、処理対象ノードの部分空間のプロトコル番号が１５〜２５であった場合、当該ルールのマッチ条件のプロトコル番号は、１５〜２０に決定される。
【０１１６】
さらに、当該分割方法は、各次元（フィールド）について、ユニークな範囲の数を計算する。例えば、ルールが３つあり、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１６〜２０、１７〜１７、であった場合、ユニークな範囲の数は３となる。また、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１５〜２０、１７〜１７、であった場合には、ユニークな範囲の数は２となる（すなわち、第１番目と第２番目とは同一のプロトコル番号であるため）。そして、当該分割方法は、全次元についてのユニークな範囲の数の平均より大きいユニークな範囲の数を有する次元を、カット（Ｃｕｔ）する次元として選択する。
【０１１７】
また、当該分割方法は、カット（Ｃｕｔ）する数の上限値を、メモリ使用量を調整するためのパラメータであるspfac（Ｓｐｅｃｉａｌ  Ｆａｃｔｏｒ）と、処理対象ルールセットの大きさ（ルール数）とから決定する。例えば、当該分割方法は、当該ルール数の平方根と、パラメータspfacとを積算した値をカット（Ｃｕｔ）する数の上限値とする。そして、当該分割方法は、カット（Ｃｕｔ）する数を２としたときの、各子ノードに含まれるルールの数の平均値および最大値を求める。
【０１１８】
さらに、当該分割方法は、カット（Ｃｕｔ）する数を増やし、その時の各子ノードに含まれるルールの数の平均値および最大値を求める。そして、当該分割方法は、カット（Ｃｕｔ）する値が上限値に達するか、もしくは、カット（Ｃｕｔ）する数を増やしても、各子ノードに含まれるルールの数の平均値および最大値に大きな変化が現れなくなった際のカット（Ｃｕｔ）する数を、処理対象ノードをカット（Ｃｕｔ）する数として決定する。
【０１１９】
図９のフローチャートの説明に戻る。探索木初期化部１１は、次に、ステップＳ１２２において決定したカット（Ｃｕｔ）方法（Ｃｕｔする次元と、Ｃｕｔする数）に基づき、処理対象ノードが表す部分空間をカット（Ｃｕｔ）した場合に得られる各部分空間について、子ノードを割り当てる（ステップＳ１２３）。具体的には、探索木初期化部１１は、探索木記憶部２０に各子ノードの情報を記憶するデータ領域を割り当てさせ、各子ノードについて以下のような情報を設定する。なお、カット（Ｃｕｔ）した結果得られた部分空間に含まれるルールの数が‘０’の場合には、当該部分空間を表す子ノードは割り当てなくてもよい。
【０１２０】
（ａ）リーフノードフラグ：オフ、
（ｂ）親ノード識別子    ：処理対象ノードの識別子、
（ｃ）部分空間情報      ：当該子ノードが表す部分空間、
（ｄ）更新カウンタおよび共有更新カウンタ：０。
【０１２１】
次いで、探索木初期化部１１は、ステップＳ１２３において割り当てた各子ノードについて、ステップＳ１２１〜Ｓ１２３までの本探索木構築サブ処理Ａを実行する（ステップＳ１２４）。その際、探索木初期化部１１は、処理対象の子ノードと、当該子ノードに含まれるルールの集合と、をパラメータとして使用する。
【０１２２】
なお、ステップＳ１２１において、ルールの数が一定数（Ｂｉｎｔｈ）以下であった場合には（ステップＳ１２１のＹＥＳ）、探索木初期化部１１は、処理対象ノードをリーフノードとしてセットアップする（ステップＳ１２５）。具体的には、探索木初期化部１１は、処理対象ノードについて以下のような設定変更・追加を行う。
【０１２３】
（ａ）リーフノードフラグ： オン、
（ｂ）ルール識別子リスト： 当該子ノードに含まれるルールの識別子のリスト。
【０１２４】
＜（Ｂ）ルール更新処理＞
次に、図１０〜図１４のフローチャートを用いて、ルール更新処理の動作例について説明する。図１０は、図１に示したデータ処理装置１の探索木制御部１０におけるルール更新部１２が、探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールセットを更新する際の動作の一例を示すフローチャートである。図１０のフローチャートに例示する本ルール更新処理の動作は、例えば、データ処理装置制御部８０からの要求により開始されてもよい。ルール更新部１２は、ルール更新処理に係るパラメータとして、操作種別（追加、変更、削除、のいずれか）およびルール（以降、‘処理対象ルール’と記載）を受け取る。
【０１２５】
図１０のフローチャートにおいて、ルール更新部１２は、まず、処理対象ルールが含まれる、処理対象のサブルールセットを選択する（ステップＳ１３１）。該サブルールセットの選択は、処理対象ルールの特徴に基づき、図７のフローチャートのステップＳ１０１によって用いられた方法と同じ方法によって行われる。
【０１２６】
次に、ルール更新部１２は、パラメータとして要求されている現在の操作が、ルール削除か否かを確認する（ステップＳ１３２）。要求されている現在の操作がルール削除であった場合には（ステップＳ１３２のＹＥＳ）、ルール更新部１２は、ルール記憶部３０に記憶されている処理対象ルールの削除フラグをオンに設定した後（ステップＳ１３４）、ステップＳ１３５に移行する。一方、要求されている現在の操作がルール削除ではなかった場合には（ステップＳ１３２のＮＯ）、ルール更新部１２は、処理対象のサブルールセットを、パラメータによる要求にしたがって更新した後（ステップＳ１３３）、ステップＳ１３５に移行する。具体的な更新処理としては、ルール追加の場合には、ルール更新部１２は、ルール記憶部３０に処理対象サブルールセットの一要素として処理対象ルールを新たに記憶させる。また、ルール変更の場合には、ルール更新部１２は、ルール記憶部３０に処理対象サブルールセットの一要素として記憶されている処理対象ルールの情報（優先度およびアクション）を変更する。
【０１２７】
次いで、ルール更新部１２は、パラメータとして要求されている現在の操作がルール追加か否かを確認する（ステップＳ１３５）。要求されている現在の操作がルール追加であった場合には（ステップＳ１３５のＹＥＳ）、ルール更新部１２は、処理対象サブルールセットの探索木（すなわち処理対象探索木）のルートノードについて、後述するルール更新サブ処理Ａ１を実行した後（ステップＳ１３６）、ステップＳ１３８に移行する。一方、要求されている現在の操作がルール追加ではなかった場合には（ステップＳ１３５のＮＯ）、ルール更新部１２は、処理対象探索木のルートノードについて、後述するルール更新サブ処理Ｂを実行した後（ステップＳ１３７）、ステップＳ１３８に移行する。
【０１２８】
しかる後、ルール更新部１２は、処理対象探索木のベース探索木を選択する（ステップＳ１３８）。具体的には、ルール更新部１２は、探索木記憶部２０に記憶されている探索木グループリストを参照し、処理対象探索木が属する探索木グループのベース探索木の識別子を取得する。次いで、ルール更新部１２は、ステップＳ１３８において選択したベース探索木のルートノードについて、後述するルール更新サブ処理Ｃを実行する（ステップＳ１３９）。
【０１２９】
詳細は後述するが、ステップＳ１３６のルール更新サブ処理Ａ１およびステップＳ１３７のルール更新サブ処理Ｂにより、処理対象探索木の、処理対象ルールを含んでいるノードの更新カウンタが更新される。また、ステップＳ１３９のルール更新サブ処理Ｃにより、処理対象探索木が属する探索木グループのベース探索木の、処理対象ルールを含んでいるノードの共有更新カウンタが更新される。
【０１３０】
次に、図１０のフローチャートのステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作について、図１１のフローチャートを用いて説明する。図１１は、図１０のフローチャートのステップＳ１３６において実行されるルール更新サブ処理Ａ１の詳細な動作の一例を示すフローチャートである。本ルール更新サブ処理Ａ１においては、処理対象のノード（処理対象ノード）および当該ノードに追加するルール(処理対象ルール)が与えられる。
【０１３１】
図１１のフローチャートにおいて、ルール更新部１２は、まず、処理対象ノードがリーフノードか否かを確認する（ステップＳ１４１）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かを確認することによって行われる。処理対象ノードがリーフノードではなかった場合には（ステップＳ１４１のＮＯ）、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ１４２）。或る子ノードが処理対象ルールを含んでいるか否かは、当該子ノードが表す部分空間と、処理対象ルールのマッチ条件が表す部分空間とに重なり（重なる部分）があるか否か（すなわち共通部分があるか否か）によって判定することができる。
【０１３２】
次いで、ルール更新部１２は、ステップＳ１４２において選択された各子ノード（未割り当ての子ノードを含む）それぞれについて、後述するルール更新サブ処理Ａ２を実行する（ステップＳ１４３）。その際、ルール更新部１２は、パラメータとして、選択された子ノード（新しい処理対象ノードとして）と、現在の処理対象ノード（新しい処理対象ノードの親ノードとして）と、処理対象ルールと、を使用する。
【０１３３】
しかる後、ルール更新部１２は、ステップＳ１４３において１回もしくは複数回実行されたルール更新サブ処理Ａ２のいずれかにおいて新規に割り当てられた子ノードがあるか否かを確認する（ステップＳ１４４）。その確認の結果、新規に割り当てられた子ノードがなかった場合には（ステップＳ１４４のＮＯ）、ルール更新部１２は、本ルール更新サブ処理Ａ１を終了する。一方、新規に割り当てられた子ノードがあった場合には（ステップＳ１４４のＹＥＳ）、ルール更新部１２は、処理対象ノードの更新カウンタを更新する（ステップＳ１４５）。具体的には、ルール更新部１２は、処理対象ノードの更新カウンタの値を、現在の値に‘１’加えたものに変更する。
【０１３４】
また、ステップＳ１４１において、処理対象ノードがリーフノードであった場合には（ステップＳ１４１のＹＥＳ）、ルール更新部１２は、ルール追加後の処理対象ノード（リーフノード）に対応するルールの数があらかじめ定めた一定数（Ｂｉｎｔｈ）以下か否かを確認する（ステップＳ１４６）。ルールの数が該一定数（Ｂｉｎｔｈ）以下であった場合（ステップＳ１４６のＹＥＳ）、ルール更新部１２は、処理対象ノード（リーフノード）のルール識別子リストに処理対象ルールの識別子を追加した後（ステップＳ１４７）、前述したステップＳ１４５に移行する。
【０１３５】
一方、ルールの数が該一定数（Ｂｉｎｔｈ）以下ではなかった場合には（ステップＳ１４６のＮＯ）、ルール更新部１２は、処理対象ノード（リーフノード）を中間ノードに変更（中間ノードとして設定）し、新たに、子ノードを作成した後（ステップＳ１４８）、前述したステップＳ１４５に移行する。ステップＳ１４８においては、具体的には、ルール更新部１２は、処理対象ノードのリーフノードフラグをオフに変更する。さらに、子ノードを作成するために、ルール更新部１２は、処理対象ノードの識別子と、処理対象ノードのルール識別子リストに処理対象ルールの識別子を加えたルールセットと、をパラメータとして、図９を用いて説明した探索木構築サブ処理Ａを実行する。
【０１３６】
次に、図１１のフローチャートのステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作について、図１２のフローチャートを用いて説明する。図１２は、図１１のフローチャートのステップＳ１４３において実行されるルール更新サブ処理Ａ２の詳細な動作の一例を示すフローチャートである。本ルール更新サブ処理Ａ２においては、処理対象のノード（処理対象ノード）と、処理対象ノードの親ノードの識別子と、処理対象ノードが表す部分空間と、当該ノードに追加するルール(処理対象ルール)と、がパラメータとして与えられる。
【０１３７】
図１２のフローチャートにおいて、ルール更新部１２は、まず、処理対象ノードのためのデータ領域が割り当て済みか否かを確認する（ステップＳ１５１）。データ領域が割り当て済みであった場合は（ステップＳ１５１のＹＥＳ）、ルール更新部１２は、処理対象ノードおよび処理対象ルールをパラメータとして、図１１に示したルール更新サブ処理Ａ１を実行する（ステップＳ１５２）。一方、データ領域が割り当て済みではなかった場合には（ステップＳ１５１のＮＯ）、ルール更新部１２は、処理対象ノードのためのデータ領域を割り当て、リーフノードとしてセットアップする（ステップＳ１５３）。具体的には、ルール更新部１２は、探索木記憶部２０に処理対象ノードの情報を記憶するデータ領域を割り当てさせ、当該ノードについて以下のような情報を設定する。
【０１３８】
（ａ）リーフノードフラグ：オン、
（ｂ）親ノード識別子    ：パラメータとして与えられた親ノード識別子、
（ｃ）部分空間          ：パラメータとして与えられた部分空間、
（ｄ）更新カウンタおよび共有更新カウンタ：０、
（ｅ）ルール識別子リスト：処理対象ルールの識別子。
【０１３９】
次に、図１０のフローチャートのステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作について、図１３のフローチャートを用いて説明する。図１３は、図１０のフローチャートのステップＳ１３７において実行されるルール更新サブ処理Ｂの詳細な動作の一例を示すフローチャートである。本ルール更新サブ処理Ｂにおいては、パラメータとして、処理対象のノード（処理対象ノード）と、削除もしくは変更するルール(処理対象ルール)と、を受け取る。
【０１４０】
図１３のフローチャートにおいて、ルール更新部１２は、まず、処理対象ノードがリーフノードか否かを確認する（ステップＳ１６１）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。処理対象ノードがリーフノードではなかった場合には（ステップＳ１６１のＮ）、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ１６２）。或る子ノードが処理対象ルールを含んでいるか否かは、当該子ノードが表す部分空間と、処理対象ルールのマッチ条件が表す部分空間とに重なる部分があるか否か（すなわち共通部分があるか否か）によって判定することができる。
【０１４１】
次いで、ルール更新部１２は、ステップＳ１６２において選択された各子ノード（割り当て済みの子ノードのみ）それぞれについて、ルール更新サブ処理Ｂを実行する（ステップＳ１６３）。
【０１４２】
ステップＳ１６１において、処理対象ノードがリーフノードであった場合には（ステップＳ１６１のＹＥＳ）、ルール更新部１２は、処理対象ノード（リーフノード）のルール識別子リストを更新する（ステップＳ１６４）。具体的には、要求されている現在の操作がルール削除である場合には、ルール更新部１２は、処理対象ルールの識別子を当該ルール識別子リストから削除する。また、要求されている現在の操作がルール更新である場合には、本動作を省略することができる。しかる後、ルール更新部１２は、処理対象ノード（リーフノード）の更新カウンタを更新する（ステップＳ１６５）。具体的には、ルール更新部１２は、処理対象ノード（リーフノード）の更新カウンタの値を、現在の値に‘１’加えたものに変更する。
【０１４３】
次に、図１０のフローチャートのステップＳ１３９において実行されるルール更新サブ処理Ｃの詳細な動作について、図１４のフローチャートを用いて説明する。図１４は、図１０のフローチャートのステップＳ１３９において実行されるルール更新サブ処理Ｃの詳細な動作の一例を示すフローチャートである。本ルール更新サブ処理Ｃにおいては、処理対象のノード（処理対象ノード）および当該ノードに追加するルール(処理対象ルール)が、パラメータとして与えられる。
【０１４４】
図１４のフローチャートにおいて、ルール更新部１２は、まず、処理対象ノードがリーフノードか否かを確認する（ステップＳ１７１）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。処理対象ノードがリーフノードではなかった場合には（ステップＳ１７１のＮＯ）、ルール更新部１２は、処理対象ルールを含む子ノード群を選択する（ステップＳ１７２）。或る子ノードが処理対象ルールを含んでいるか否かは、当該子ノードが表す部分空間と、処理対象ルールのマッチ条件が表す部分空間とに重なる部分があるか否か（すなわち共通部分があるか否か）によって判定することができる。
【０１４５】
次いで、ルール更新部１２は、ステップＳ１７２において選択された各子ノード（割り当て済みの子ノードのみ）それぞれについて、ルール更新サブ処理Ｃを実行する（ステップＳ１７３）。
【０１４６】
しかる後、ルール更新部１２は、以下の条件が満たされるか否かを確認する。即ち、ルール更新部１２は、ステップＳ１７２において選択された子ノードにデータ領域が未割り当ての子ノード（すなわち関係するルールの数が０の子ノード）があり、かつ、要求されている現在の操作がルール追加であり、かつ、当該未割当の子ノードが表す部分空間と処理対象ルールのマッチ条件が表す部分空間とに重なる部分がある、という条件を確認する（ステップＳ１７４）。データ領域が未割り当ての子ノードがあり、かつ、要求されている現在の操作がルール追加であり、かつ、当該未割当の子ノードが表す部分空間と処理対象ルールのマッチ条件が表す部分空間とに重なる部分がある場合には（ステップＳ１７４のＹＥＳ）、ルール更新部１２は、処理対象ノードの共有更新カウンタを更新して（ステップＳ１７５）、本ルール更新サブ処理Ｃを終了する。具体的には、ルール更新部１２は、処理対象ノードの共有更新カウンタの値を、現在の値に‘１’加えたものに変更する。一方、ステップＳ１７４において、データ領域が未割り当ての子ノードがなかったか、もしくは、要求されている現在の操作がルール追加ではなかった場合には（ステップＳ１７４のＮＯ）、ルール更新部１２は、本ルール更新サブ処理Ｃを終了する。なお、ステップＳ１７４において、未割当の子ノードが表す部分空間と処理対象ルールのマッチ条件が表す部分空間とに重なる部分が無い場合も、ルール更新部１２は、本ルール更新サブ処理Ｃを終了してもよい。
【０１４７】
また、ステップＳ１７１において、処理対象ノードがリーフノードであった場合には（ステップＳ１７１のＹＥＳ）、ルール更新部１２は、処理対象ノード（リーフノード）の共有更新カウンタを更新して（ステップＳ１７６）、本ルール更新サブ処理Ｃを終了する。具体的には、ルール更新部１２は、処理対象ノード(リーフノード)の共有更新カウンタの値を、現在の値に‘１’加えたものに変更する。ルール更新部１２は、図１４にフローチャートで示したルール更新サブ処理Ｃ（すなわち、図１０のステップＳ１３９）の実行と並行して、削除待ちフラグがオンのルールを削除する処理を、例えば、定期的に実行する。ルール更新部１２は、ルール記憶部３０に記憶されたルールのうち、削除フラグがオンであり、かつ、参照カウンタが０であるルールについて、ルール記憶部３０に削除させる。
【０１４８】
＜（Ｃ）ルール探索処理＞
次に、図１５、図１６のフローチャートを用いて、ルール探索処理の動作例について説明する。図１５は、図１に示したデータ処理装置１の探索木制御部１０における探索木探索部１３が、探索木記憶部２０およびルール記憶部３０それぞれに記憶される探索木およびルールセットを参照して、与えられたキーに適合するルールを探索する際の動作の一例を示すフローチャートである。図１５のフローチャートに例示する本ルール探索処理の動作は、例えば、パケット処理部６０からの要求により開始され、本ルール探索処理に係るパラメータとして、探索木探索部１３は、探索に使用すべきキー（探索キー）を受け取る。
本ルール探索処理においては、探索木探索部１３は、パラメータとして与えられた探索キーに適合する最高優先度のルールの識別子（探索された場合）を、要求元（例えば、パケット処理部６０）に返す。探索木探索部１３は、また、探索木における探索において最終的に到達したノード（中間ノードもしくはリーフノード）の識別子（探索木毎）のリストを、要求元に返す。
【０１４９】
図１５のフローチャートにおいて、探索木探索部１３は、まず、各探索木について、後述するルール探索サブ処理Ａを実行する（ステップＳ１８１）。次いで、探索木探索部１３は、ステップＳ１８１において得られた、各探索木内で発見されたルールの集合の中から最高優先度のルールを選択する。探索木探索部１３は、選択したルールを、パラメータとして受け取った探索キーに適合するルールとして要求元に返す（ステップＳ１８２）。また、探索木探索部１３は、ステップＳ１８１において各探索木について得られる、探索により最終的に到達したノード（中間ノードもしくはリーフノード）の識別子（探索木毎）のリストも要求元に返す。
【０１５０】
次に、図１５のフローチャートのステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作について、図１６のフローチャートを用いて説明する。図１６は、図１５のフローチャートのステップＳ１８１において実行されるルール探索サブ処理Ａの詳細な動作の一例を示すフローチャートである。本ルール探索サブ処理Ａにおいては、探索木探索部１３は、パラメータとして、処理対象の探索木（例えば探索木識別子の形式、以降‘処理対象探索木’と記載）および探索に使用すべきキー（探索キー）を受け取る。また、本ルール探索サブ処理Ａにおいては、探索木探索部１３は、探索の結果、探索されたルールおよび探索により最終的に到達したノードの識別子を要求元に返す。なお、本ルール探索サブ処理Ａにおいて処理の対象としているノードを‘処理対象ノード’と呼称する。
【０１５１】
図１６のフローチャートにおいて、探索木探索部１３は、まず、処理対象ノードとして処理対象探索木のルートノードを選択する（ステップＳ１９１）。次に、探索木探索部１３は、処理対象ノードがリーフノードか否かを確認する（ステップＳ１９２）。リーフノードか否かの確認は、処理対象ノードのリーフノードフラグがオンか否かによって行われる。
【０１５２】
処理対象ノードがリーフノードではなかった場合には（ステップＳ１９２のＮＯ）、探索木探索部１３は、パラメータとして受け取った探索キーに対応する子ノードを選択する（ステップＳ１９３）。次いで、探索木探索部１３は、ステップＳ１９３において選択した子ノードに対してデータ領域が割り当て済みか否かを確認する（ステップＳ１９４）。データ領域が割り当て済みであった場合には（ステップＳ１９４のＹＥＳ）、探索木探索部１３は、処理対象ノードとして当該子ノードを選択して（ステップＳ１９５）、ステップＳ１９２に復帰する。
【０１５３】
一方、ステップＳ１９４において、データ領域が割り当て済みではなかった場合には（ステップＳ１９４のＮＯ）、探索木探索部１３は、探索キーに対応するルールは存在しないので、本探索において最終的に到達したノードを現在の処理対象ノードとして本ルール探索サブ処理Ａを終了する。
【０１５４】
また、ステップＳ１９２において、処理対象ノードがリーフノードであった場合には（ステップＳ１９２のＹＥＳ）、探索木探索部１３は、処理対象ノード（リーフノード）のルール識別子リストを基にして、ルール記憶部３０を参照して、本リーフノードに関係するルールを取得する（ステップＳ１９６）。さらに、探索木探索部１３は、例えば、当該ルール群内において線形探索処理を実施して、当該ルール群の中から探索キーに適合する最高優先度のルールを選択し、探索キーに適合するルールとして出力する。その後、探索木探索部１３は、本ルール探索サブ処理Ａを終了する。この場合、本探索で最終的に到達したノードは、現在の処理対象ノード（リーフノード）となる。
【０１５５】
＜（Ｄ）パケット処理＞
次に、図１７のフローチャートを用いて、パケット処理の動作例について説明する。図１７は、図１に示したデータ処理装置１のパケット処理部６０がパケットを受信した際の動作の一例を示すフローチャートである。図１７のフローチャートに例示する本パケット処理の動作は、データ処理装置１の通信ＩＦ部７０がパケット（処理対象パケット）を受信し、パケット処理部６０にパケットの受信通知がなされた際に開始される。
【０１５６】
図１７のフローチャートにおいて、パケット処理部６０は、まず、受信した処理対象パケットからルール探索に使用するためのキー（探索キー）を抽出する（ステップＳ２０１）。具体的には、パケット処理部６０は、受信したパケットから、送信元ＩＰアドレス、送信先ＩＰアドレス、プロトコル番号、送信元ポート番号、送信先ポート番号を探索キーとして取り出す。次に、パケット処理部６０は、ステップＳ２０１において抽出された探索キーをパラメータとして、図３に示すキャッシュテーブル制御部４０のキャッシュエントリ探索部４２に依頼して、キャッシュエントリを探索する（ステップＳ２０２）。
【０１５７】
パケット処理部６０は、キャッシュエントリ探索部４２に対する依頼結果として、パラメータとして引き渡した探索キーに対応するキャッシュエントリ（処理対象キャッシュエントリ）が検出されたか否かを確認する（ステップＳ２０３）。処理対象キャッシュエントリが検出された場合には（ステップＳ２０３のＹＥＳ）、パケット処理部６０は、図３に示すキャッシュテーブル制御部４０のキャッシュエントリ再評価部４３に依頼して、当該処理対象キャッシュエントリの再評価を行う（ステップＳ２０４）。キャッシュエントリ再評価部４３は、再評価の結果として、当該処理対象キャッシュエントリが更新されたか（探索キーに適合するルールが検出された場合）、もしくは、削除されたか（探索キーに適合するルールが検出されなかった場合）、のいずれかを返す。
【０１５８】
パケット処理部６０は、キャッシュエントリ再評価部４３からの再評価の結果を受け取ると、ステップＳ２０４において探索キーに適合するルールが検出されたか否かを確認する（ステップＳ２０５）。探索キーに適合するルールが検出された場合には（ステップＳ２０５のＹＥＳ）、パケット処理部６０は、当該適合ルールのアクションに従い、処理対象パケットを処理する（ステップＳ２０６）。
【０１５９】
一方、ステップＳ２０５において、探索キーに適合するルールが検出されなかった場合には（ステップＳ２０５のＮＯ）、パケット処理部６０は、処理対象パケットについて、適合ルールが不明の場合の処理を実行する（ステップＳ２０７）。具体的には、例えば、パケット処理部６０は、以下に示すいずれかもしくは組み合わせの処理を実行する。
【０１６０】
（ａ）当該パケットを破棄する。
（ｂ）当該パケットの適合ルールが不明の旨をログ出力する。
（ｃ）当該パケットの適合ルールが不明の旨をデータ処理装置制御部８０に通知する。
（ｄ）当該パケットの適合ルールが不明の旨を他の装置（例えば、ネットワーク管理装置。図１〜図３には図示されていない）に通知する。
【０１６１】
また、ステップＳ２０３において、処理対象キャッシュエントリが検出されなかった場合には（ステップＳ２０３のＮＯ）、パケット処理部６０は、図２に示す探索木制御部１０の探索木探索部１３に依頼して、探索キーに適合するルールを探索する（ステップＳ２０８）。パケット処理部６０は、探索木探索部１３への依頼結果として、探索キーに適合するルールが探索されたか否かを確認する（ステップＳ２０９）。探索キーに適合するルールが探索されなかった場合（ステップＳ２０９のＮＯ）、パケット処理部６０は、ステップＳ２０７へ移行して、前述のような適合ルールが不明の場合の処理を実行する。
【０１６２】
一方、探索キーに適合するルールが探索された場合には（ステップＳ２０９のＹＥＳ）、パケット処理部６０は、図３に示すキャッシュテーブル制御部４０のキャッシュエントリ作成部４１に依頼して、当該処理対象パケットを処理するためのキャッシュエントリを作成して、キャッシュテーブル記憶部５０に記憶させる（ステップＳ２１０）。なお、キャッシュエントリ作成部４１に依頼する際、パケット処理部６０は、パラメータとして、ステップＳ２０１において抽出した探索キーと、ステップＳ２０８において発見されたルールの識別子と、ステップＳ２０８において探索木探索部１３から返されたノード識別子のリストと、をキャッシュエントリ作成部４１に渡す。
【０１６３】
しかる後、パケット処理部６０は、ステップＳ２０６に移行して、ステップＳ２０８において探索された適合ルールが示すアクションに従い、処理対象パケットを処理する。
【０１６４】
＜（Ｅ）キャッシュエントリ作成処理＞
次に、図１８のフローチャートを用いて、キャッシュエントリ作成処理の動作例について説明する。図１８は、図１に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ作成部４１が、キャッシュエントリを作成する際の動作の一例を示すフローチャートである。図１８のフローチャートに例示する本キャッシュエントリ作成処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ作成部４１は、本キャッシュエントリ作成処理に係るパラメータとして、キー（探索キー）と、ルール識別子と、キーを用いた探索木の探索において最終的に到達したノードの識別子（探索木毎）と、を受け取る。
【０１６５】
図１８のフローチャートにおいて、キャッシュエントリ作成部４１は、まず、パラメータとして受け取ったキーのハッシュ値を計算し、計算結果を基にして、当該キーに対応するハッシュテーブルのバケツ（Ｂｕｃｋｅｔ）を選択する（ステップＳ２２１）。次に、キャッシュエントリ作成部４１は、ステップＳ２２１において選択したバケツ（Ｂｕｃｋｅｔ）に空きがあるか否かを確認する（ステップＳ２２２）。バケツ（Ｂｕｃｋｅｔ）の空きの有無は、当該バケツ（Ｂｕｃｋｅｔ）内の各キャッシュエントリについて、使用中フラグを確認することによって確認することができる。
【０１６６】
選択したバケツ（Ｂｕｃｋｅｔ）に空きがあった場合には（ステップＳ２２２のＹＥＳ）、ステップＳ２２４に移行する。選択したバケツ（Ｂｕｃｋｅｔ）に空きがなかった場合は（ステップＳ２２２のＮＯ）、キャッシュエントリ作成部４１は、当該バケツ（Ｂｕｃｋｅｔ）内の各キャッシュエントリのうち、いずれか一つのキャッシュエントリを削除した後（ステップＳ２２３）、ステップＳ２２４に移行する。ここで、キャッシュエントリ作成部４１は、キャッシュエントリの使用中フラグをオフに設定することによってキャッシュエントリを削除することができる。その際、キャッシュエントリ作成部４１は、当該キャッシュエントリの適合ルールの参照カウンタを１減らす。また、キャッシュエントリ作成部４１は、例えば、最終使用時刻が最も古いキャッシュエントリを削除対象として選択してもよい。
【０１６７】
ステップＳ２２４においては、キャッシュエントリ作成部４１は、当該バケツ（Ｂｕｃｋｅｔ）内の空きキャッシュエントリの一つを選択して、セットアップする（ステップＳ２２４）。具体的には、キャッシュエントリ作成部４１は、選択したキャッシュエントリに対して、以下のような情報を設定する。また、キャッシュエントリ作成部４１は、パラメータとして与えられたルールの参照カウンタを１増やす。
【０１６８】
（ａ）使用中フラグ：オン、
（ｂ）キー        ：パラメータとして与えられたキー、
（ｃ）ルール識別子：パラメータとして与えられたルールの識別子、
（ｄ）最終使用時刻： 処理実行時点における時刻、
（ｅ）ノード状態．ノード識別子 (探索木毎)：パラメータとして与えられたノード識別子、
（ｆ）ノード状態．更新カウンタキャッシュ (探索木毎)：前記ノード識別子を基に図２に示す更新カウンタ取得部１４に依頼して取得した値、
（ｇ）ノード状態．共有更新カウンタキャッシュ (ベース探索木毎)：前記ノード識別子を基に図２に示す更新カウンタ取得部１４に依頼して取得した値。
【０１６９】
＜（Ｆ）キャッシュエントリ探索処理＞
次に、図１９のフローチャートを用いて、キャッシュエントリ探索処理の動作例について説明する。図１９は、図１に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ探索部４２が、キャッシュエントリを探索する際の動作の一例を示すフローチャートである。図１９のフローチャートに例示する本キャッシュエントリ探索処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ作成部４１は、本キャッシュエントリ探索処理に係るパラメータとして、キー（探索キー）を受け取る。
【０１７０】
図１９のフローチャートにおいて、キャッシュエントリ探索部４２は、まず、パラメータとして受け取ったキーのハッシュ値を計算する。キャッシュエントリ探索部４２は、係る計算結果を基にして、当該キーに対応するハッシュテーブルのバケツ（Ｂｕｃｋｅｔ）を選択する（ステップＳ２３１）。次に、キャッシュエントリ探索部４２は、ステップＳ２３１において選択したバケツ（Ｂｕｃｋｅｔ）内の最初のキャッシュエントリを選択する（ステップＳ２３２）。
【０１７１】
次いで、キャッシュエントリ探索部４２は、選択したキャッシュエントリの使用中フラグがオンであり、かつ、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致するか否かを確認する（ステップＳ２３３）。キャッシュエントリの使用中フラグがオンであり、かつ、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致した場合は（ステップＳ２３３のＹＥＳ）、キャッシュエントリ探索部４２は、キーに合致するキャッシュエントリの探索に成功したと判定する。この場合、キャッシュエントリ探索部４２は、本キャッシュエントリ探索処理を終了し、探索の結果として、当該キャッシュエントリの識別子を要求元に返す。
【０１７２】
一方、ステップＳ２３３において、キャッシュエントリの使用中フラグがオンであり、かつ、当該キャッシュエントリのキーと本キャッシュエントリ探索処理のパラメータとして与えられたキーとが一致しなかった場合は（ステップＳ２３３のＮＯ）、キャッシュエントリ探索部４２は、選択したキャッシュエントリがバケツ（Ｂｕｃｋｅｔ）内の最後のキャッシュエントリか否かを確認する（ステップＳ２３４）。選択したキャッシュエントリがバケツ（Ｂｕｃｋｅｔ）内の最後のキャッシュエントリであった場合には（ステップＳ２３４のＹＥＳ）、キャッシュエントリ探索部４２は、本キャッシュエントリ探索処理を終了する。キャッシュエントリ探索部４２は、探索の結果として、キーに合致するキャッシュエントリを探索することができなかったことを要求元に通知する。なお、選択したキャッシュエントリの使用中フラグがオフの場合も（ステップＳ２３３においてＮＯ）、上記と同様に、ステップＳ２３４以降の処理が実行される。
【０１７３】
また、ステップＳ２３４において、バケツ（Ｂｕｃｋｅｔ）内の最後のキャッシュエントリではなかった場合には（ステップＳ２３４のＮＯ）、キャッシュエントリ探索部４２は、バケツ（Ｂｕｃｋｅｔ）内の次のキャッシュエントリを選択して（ステップＳ２３５）、ステップＳ２３３に復帰する。
【０１７４】
＜（Ｇ）キャッシュエントリ再評価処理＞
次に、図２０のフローチャートを用いて、キャッシュエントリ再評価処理の動作例について説明する。図２０は、図１に示したデータ処理装置１のキャッシュテーブル制御部４０におけるキャッシュエントリ再評価部４３が、キャッシュエントリを再評価する際の動作の一例を示すフローチャートである。図２０のフローチャートに例示する本キャッシュエントリ再評価処理の動作は、例えば、パケット処理部６０からの要求に基づいて開始される。なお、キャッシュエントリ再評価部４３は、本キャッシュエントリ再評価処理に係るパラメータとして、再評価対象のキャッシュエントリ（処理対象キャッシュエントリ）の識別子を受け取る。
【０１７５】
図２０のフローチャートにおいて、キャッシュエントリ再評価部４３は、まず、処理対象キャッシュエントリのノード状態リストを参照する。キャッシュエントリ再評価部４３は、図２に示す探索木制御部１０の更新カウンタ取得部１４に依頼して、処理対象キャッシュエントリが表すフローが属するノードの最新の共有更新カウンタ値（ベース探索木毎）を取得する（ステップＳ２４１）。次に、キャッシュエントリ再評価部４３は、ステップＳ２４１において取得された最新の共有更新カウンタ値と、キャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各ベース探索木の共有更新カウンタ値との間に差分があるか否かを確認する（ステップＳ２４２）。
【０１７６】
最新の共有更新カウンタ値とキャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各ベース探索木の共有更新カウンタ値との間に差分がない場合は（ステップＳ２４２のＮＯ）、ステップＳ２４７に移行する。一方、最新の共有更新カウンタ値と、キャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各ベース探索木の共有更新カウンタ値との間に差分がある場合は（ステップＳ２４２のＹＥＳ）、キャッシュエントリ再評価部４３は、以下の処理を実行する。即ち、キャッシュエントリ再評価部４３は、当該処理対象キャッシュエントリのうち、適合ルールおよび共有更新カウンタ値に差分があった探索木グループ内のノードに係る情報は無効である可能性があるものと判定する。そして、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのノード状態リストを参照し、図２に示す探索木制御部１０の更新カウンタ取得部１４に依頼して、処理対象キャッシュエントリが表すフローが属するノードの最新の更新カウンタ値（探索木毎）を取得する（ステップＳ２４３）。その際、キャッシュエントリ再評価部４３は、ステップＳ２４２において差分が検出されたベース探索木が属する探索木グループ内の探索木群を、更新カウンタ値（探索木毎）の取得対象とする。
【０１７７】
次いで、キャッシュエントリ再評価部４３は、ステップＳ２４３において取得された最新の更新カウンタ値と、キャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各探索木の更新カウンタ値との間に差分があるか否かを確認する（ステップＳ２４４）。最新の更新カウンタ値とキャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各探索木の更新カウンタ値との間に差分がない場合は（ステップＳ２４４のＮＯ）、ステップＳ２４７に移行する。
【０１７８】
一方、ステップＳ２４４において、最新の更新カウンタ値と、キャッシュテーブル記憶部５０に記憶された処理対象キャッシュエントリに関する各探索木の更新カウンタ値との間に差分があった場合は（ステップＳ２４４のＹＥＳ）、キャッシュエントリ再評価部４３は、以下の処理を実行する。即ち、キャッシュエントリ再評価部４３は、当該処理対象キャッシュエントリのうち、適合ルールおよび更新カウンタ値に差分があった探索木のノードに係る情報は無効であると判定する。そして、キャッシュエントリ再評価部４３は、図２に示す探索木制御部１０の探索木探索部１３に依頼して、当該処理対象キャッシュエントリのキーに適合するルールを再度探索し直す（ステップＳ２４５）。このとき、キャッシュエントリ再評価部４３は、ステップＳ２４４において更新カウンタ値に差分があったと判定された探索木の識別子のリストを、探索木探索部１３に渡す。当該探索木の識別子のリストを受け取った探索木探索部１３は、探索対象を当該探索木に限定して探索処理を行ってもよい。また、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのノード状態リストに含まれるノード識別子のリストを、探索木探索部１３に渡す。当該ノード識別子のリストを受け取った探索木探索部１３は、探索木の探索処理を、ルートノードからではなく、受け取ったノード識別子によって識別されるノードから始めてもよい。
【０１７９】
しかる後、キャッシュエントリ再評価部４３は、ステップＳ２４５において探索されたルールの情報を基にして、処理対象キャッシュエントリを更新する（ステップＳ２４６）。具体的には、ステップＳ２４５においてキーに適合するルールを探索することができなかった場合には、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリの使用中フラグをオフに設定し、処理対象キャッシュエントリを削除する。その際、キャッシュエントリ再評価部４３は、以前の適合ルールの参照カウンタを１減らす。
【０１８０】
一方、キーに適合するルールを探索することができた場合には、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリのルール識別子に、探索された当該適合ルールの識別子を設定する。その際、キャッシュエントリ再評価部４３は、以前の適合ルールの参照カウンタを１減らし、新しい適合ルールの参照カウンタを１増やす。また、キャッシュエントリ再評価部４３は、処理対象キャッシュエントリの最終使用時刻に、処理時点の時刻を設定する。さらに、キャッシュエントリ再評価部４３は、ステップＳ２４１およびＳ２４３において、最新の共有更新カウンタ値および最新の更新カウンタ値を取得していた場合には、取得した最新の共有更新カウンタ値、最新の更新カウンタ値をそれぞれ処理対象キャッシュエントリの共有更新カウンタキャッシュ、更新カウンタキャッシュに記憶する。
【０１８１】
なお、ステップＳ２４２において、最新の共有更新カウンタ値と処理対象キャッシュエントリに記憶された各ベース探索木の共有更新カウンタ値との間に差分がなかった場合（ステップＳ２４２のＮＯ）、または、ステップＳ２４４において、最新の更新カウンタ値と処理対象キャッシュエントリに記憶された各探索木の更新カウンタ値との間に差分がなかった場合には（ステップＳ２４４のＮＯ）、キャッシュエントリ再評価部４３は、以下の処理を実行する。すなわち、キャッシュエントリ再評価部４３は、ステップＳ２４７において、当該処理対象キャッシュエントリは有効であるものと評価して、処理対象キャッシュエントリの最終使用時刻を、処理実行時点の時刻に設定する（ステップＳ２４７）。
【０１８２】
また、キャッシュエントリ再評価部４３は、本キャッシュエントリ再評価処理を終了する際に、処理対象キャッシュエントリが更新されたか（キーに適合するルールを探索できた場合）、あるいは、削除されたか（キーに適合するルールを探索できなかった場合）、のいずれかを示す情報を要求元に返す。
【０１８３】
（本実施の形態の効果）
以上に詳細に説明したように、本実施の形態においては、次のような効果が得られる。
【０１８４】
本実施の形態によれば、図２に示す探索木制御部１０の探索木初期化部１１は、ルールセットをルールの特徴に基づいてサブルールセットに分割して、サブルールセット毎に探索木を構築する。さらに、探索木初期化部１１は、各サブルールセットの特徴に基づいて探索木をグループ化し、探索木グループ毎にベース探索木を決定する。また、図１に示す探索木記憶部２０が記憶する探索木のノードは、更新カウンタおよび共有更新カウンタに関する情報を有している。
【０１８５】
また、図２に示す探索木制御部１０のルール更新部１２は、ルール更新（追加、変更、削除）に際し、処理対象ルールのマッチ条件が表す部分空間と重複する部分空間を表しているノード（群）に関し、処理対象ルールが含まれるサブルールセットに対する探索木における、当該ノードの更新カウンタを更新する。さらに、探索木制御部１０は、当該探索木が属する探索木グループのベース探索木における当該ノードの共有更新カウンタをも更新する。また、図１に示すキャッシュテーブル記憶部５０が記憶するキャッシュエントリは、当該キャッシュエントリが表すフローが属するノードの情報（探索木毎；ノードの更新カウンタおよび共有更新カウンタのキャッシュを含む情報）を有する。当該情報は、キャッシュエントリ作成部４１およびキャッシュエントリ再評価部４３によって当該キャッシュエントリが使用される毎に更新される。
【０１８６】
また、図１に示すパケット処理部６０は、受信パケットを処理する際に、当該パケット（フロー）用のキャッシュエントリが存在する場合、当該キャッシュエントリを再評価してから使用する。
【０１８７】
また、図３に示すキャッシュテーブル制御部４０のキャッシュエントリ再評価部４３は、キャッシュエントリが表すフローが属するノード（群）に関し、記憶されている更新カウンタキャッシュの値（更新履歴情報のキャッシュの一種）と当該ノードの最新の更新カウンタの値（最新の更新履歴情報の一種）とを比較する。そして、両者に不整合がある場合、キャッシュエントリ再評価部４３は、適合するルールの再探索が必要であると判断する。その際、キャッシュエントリ再評価部４３は、記憶されている共有更新カウンタキャッシュの値（共有更新履歴情報のキャッシュの一種）と、当該ノード（ベース探索木に属する）の最新の共有更新カウンタの値（最新の共有更新履歴情報の一種）とを比較する。キャッシュエントリ再評価部４３は、両者に不整合があった場合にのみ、当該ノードが属する探索木グループ内において更新カウンタキャッシュの値（更新履歴情報のキャッシュの一種）が無効であるものとして扱う。この場合、キャッシュエントリ再評価部４３は、前述した記憶されている更新カウンタキャッシュの値と当該ノードの最新の更新カウンタの値との比較を行う。
【０１８８】
よって、本実施の形態によれば、パケット処理（データ処理の一種）に用いる情報エントリを探索する探索木が複数の探索木から構成されている場合であっても、以下のような効果を期待することができる。
【０１８９】
具体的には、ルールセット（情報エントリの集合の一種）の更新時における、探索木による探索結果（第１の情報エントリ）と、該探索結果をキャッシュしているキャッシュエントリ（第２の情報エントリ）との間の同期処理（キャッシュエントリの再評価処理）を想定する。本実施の形態によれば、当該同期処理の際、パケット（処理対象のデータの一種）を受信する毎に確認する必要がある、共有更新カウンタ（共有更新履歴情報の一種）及び更新カウンタ（更新履歴情報の一種）の確認回数を、探索木の数から、ベース探索木の数に減らすことができる。その結果、パケット（処理対象のデータの一種）の処理におけるメモリアクセス回数を減らすことができる。さらには、アクセス先メモリアドレス領域が限定され（アクセス離散度が下がり）、かつ、キャッシュメモリによりメモリアクセス遅延の隠蔽効果も得られ易くなる。これにより、パケット処理（データ処理の一種）の性能の安定化、高速化を図ることができる。以上より、本実施形態におけるデータ処理装置１によれば、データ処理（例えばパケット処理）に用いる情報エントリを探索する際に用いる探索木を複数有する場合であっても、情報エントリの探索に要する負荷を低減することができる。
【０１９０】
なお、上記説明では、データ処理装置１は、受信したパケットに適合するルールが存在しない場合（ステップＳ２０９のＮＯ、ステップＳ２０５のＮＯ）に、当該パケットのフローに対応するキャッシュエントリを作成しないもしくは削除する（ステップＳ２０７）。しかしながら、本実施形態を用いて説明した本発明は、これに限定されるものではない。他の例として、データ処理装置１は、例えば、ステップＳ２０７において、上記に加え、適合するルールがない、という情報を記憶したキャッシュエントリを作成もしくは維持してもよい。これにより、データ処理装置１は、適合するルールがないパケットを受信した場合の探索木探索の実行回数を減らすことができる。
【０１９１】
また、上記説明では、探索木は木構造であり、ルートノード以外のノードの親ノードの数は１である例を示した。しかしながら、本実施形態を用いて説明した本発明は、これに限定されるものではない。他の例として、ノードは複数の親ノードを持ってもよい。この場合、探索木は純粋な木ではなく、グラフとなる。ノードが複数の親ノードを持つ状態は、当該複数の親ノードが表す部分空間に重複がある場合に発生する。また、そのような重複は、あるノードの子ノード群を作成する際、各子ノードが表す部分空間の一部または全部に重なりを持たせることで発生する。そのような子ノード群の作成方法は、探索処理最適化の一環として行われてもよい。なお、探索処理においては、子ノード群の部分空間に重複があり、かつ探索キーが当該重複する部分空間に含まれる場合、当該部分空間を含む複数の子ノードを探索すればよい。
【０１９２】
また、上記説明では、ルール更新の際、データ処理装置１は、常に、ベース木の共有更新カウンタを更新する。しかしながら、本実施形態を用いて説明した本発明は、これに限定されるものではない。他の例として、ルール更新の際、データ処理装置１は、所定の条件が成立する場合には、ベース木の共有更新カウンタを更新しないよう処理してもよい。その場合、ノードに係る情報に共有更新カウンタ非更新フラグを設け、データ処理装置１は、共有更新カウンタを更新せずに更新されたノードに係る情報の当該フラグをオンにする。また、キャッシュエントリのノード状態に当該フラグを追加し、キャッシュエントリ作成の際、データ処理装置１は、ノードの当該フラグの値をキャッシュエントリに記憶する。ステップＳ２０４においてキャッシュエントリを再評価する際、キャッシュエントリ再評価部４３は、当該フラグを参照する。そして、キャッシュエントリ再評価部４３は、当該フラグがオンのノードがある場合、当該ノードが属する探索木グループについて、ステップＳ２４１およびステップＳ２４２を省略し、ステップＳ２４２においてＹＥＳであったとして処理を行う。共有更新カウンタの利用は、前述したとおり、パケットを受信する毎に確認する必要がある共有更新カウンタ及び更新カウンタの確認回数を減らす効果がある一方、Ｆａｌｓｅ  Ｐｏｓｉｔｉｖｅを発生させる可能性がある。すなわち、当該更新の影響を受けないキャッシュエントリであっても、当該共有更新カウンタを参照している場合、当該共有更新カウンタの変更を検出して、各探索木の更新カウンタの取得および比較処理を行う場合が発生しうる。当該更新の影響を受けないキャッシュエントリについては、更新カウンタの比較では差異（不整合）が存在しないため、探索木の再探索は行われないものの、更新カウンタ取得および比較処理の負荷が発生する。所定の条件が成立する場合にベース木の共有更新カウンタを更新しないことで、そのようなＦａｌｓｅ  Ｐｏｓｉｔｉｖｅの発生、およびそれに伴う負荷の発生を抑制することができる。所定の条件として、例えば、下記（１）及び（２）のいずれかもしくは組み合わせを使用できる。
（１）更新されるルールの部分空間が、ベース木において多くのノードの部分空間と重複している場合 (すなわち、ルール更新により共有更新カウンタが更新されるノードの数が多い場合)
（２）更新されるルールに関係するノードを使用しているキャッシュエントリの数が少ない場合
あるノードを使用しているキャッシュエントリの数は、例えば、以下のような方法で確認することができる。即ち、ノードに係る情報に参照カウンタを追加する。そして、当該ノードを使用・参照するキャッシュエントリが作成された際に当該参照カウンタを1増やし、当該キャッシュエントリが当該ノードの使用・参照を終了する際に当該参照カウンタを１減らす。これにより、あるノードを使用しているキャッシュエントリの数を確認できる。
【０１９３】
また、上記説明では、データ処理装置１は、ベース木をルールの探索に使用する探索木の中から選択する。しかしながら、本実施形態を用いて説明した本発明は、これに限定されるものではない。他の例として、各探索木グループに探索用の探索木とは別の探索木（共有更新カウンタ用探索木）を追加し、当該共有更新カウンタ用探索木をベース木としてもよい。共有更新カウンタ用探索木は、ルールの収容を行わず、その構築は当該探索木グループの初期ルールセットと独立であってもよい。例えば、共有更新カウンタ用探索木の構築における各ノードでのＣｕｔする次元やＣｕｔ数は予め与えられてもよい。
【０１９４】
＜ハードウェア及びソフトウェア・プログラム（コンピュータ・プログラム）の構成＞
以下、上記説明した実施形態を実現可能なハードウェア構成について説明する。
【０１９５】
以下の説明においては、上記実施形態において説明したデータ処理装置１を、単に「データ処理装置」と記載する。また、データ処理装置の各構成要素を、単に「データ処理装置の構成要素」と記載する場合がある。
【０１９６】
上記実施形態において説明したデータ処理装置は、１つ又は複数の専用のハードウェア装置により構成されてもよい。その場合、上記各図（図１乃至図3）に示した各構成要素は、その一部又は全部を統合したハードウェア（処理ロジックを実装した集積回路あるいは記憶デバイス等）を用いて実現されてもよい。
【０１９７】
データ処理装置が専用のハードウェアにより実現される場合、係るデータ処理装置の構成要素は、例えば、それぞれの機能を提供可能な回路構成（ｃｉｒｃｕｉｔｒｙ）により実現されてもよい。係る回路構成は、例えば、ＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｃｈｉｐ）等の集積回路や、当該集積回路を用いて実現されたチップセット等を含む。この場合、データ処理装置の構成要素が保持するデータは、例えば、ＳｏＣとして統合されたＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）領域やフラッシュメモリ領域、あるいは、当該ＳｏＣに接続された記憶デバイス（半導体記憶装置等）に記憶されてもよい。
【０１９８】
また、この場合、データ処理装置の各構成要素を接続する通信回線としては、周知の通信ネットワーク（例えば通信バス等）を採用してもよい。また、各構成要素を接続する通信回線は、それぞれの構成要素間をピアツーピアで接続してもよい。
【０１９９】
また、上述したデータ処理装置は、図２６に例示するような汎用のハードウェア２６００と、係るハードウェアによって実行される各種ソフトウェア・プログラム（コンピュータ・プログラム）とによって構成されてもよい。この場合、データ処理装置は、任意の数の、汎用のハードウェア装置及びソフトウェア・プログラムにより構成されてもよい。即ち、データ処理装置を構成する構成要素毎に、個別のハードウェア装置が割当てられてもよく、複数の構成要素が、一つのハードウェア装置を用いて実現されてもよい。
【０２００】
図２６における演算装置２６０１は、汎用のＣＰＵ（中央処理装置：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）やマイクロプロセッサ等の演算処理装置である。演算装置２６０１は、例えば後述する不揮発性記憶装置２６０３に記憶された各種ソフトウェア・プログラムを記憶装置２６０２に読み出し、係るソフトウェア・プログラムに従って処理を実行してもよい。この場合、上記実施形態におけるデータ処理装置の構成要素の機能は、演算装置２６０１により実行されるソフトウェア・プログラムを用いて実現される。
【０２０１】
記憶装置２６０２は、演算装置２６０１から参照可能な、ＲＡＭあるいはＲＯＭ等のメモリ装置であり、ソフトウェア・プログラムや各種データ等を記憶する。なお、記憶装置２６０２は、揮発性のメモリ装置であってもよく、不揮発性のメモリ装置であってもよい。記憶装置２６０２には、データ処理装置の構成要素が保持するデータが一時的に記憶されてもよい。
【０２０２】
なお、記憶装置２６０２、あるいは、演算装置２６０１には、記憶装置２６０２よりも比較的高速にアクセス可能なキャッシュメモリ２６０２ａが設けられてもよい。ハードウェア２６００は、CPUと、キャッシュメモリとを含む階層メモリ構成を備えたコンピュータを構成することができる。
【０２０３】
不揮発性記憶装置２６０３は、例えば磁気ディスクドライブや、フラッシュメモリによる半導体記憶装置等の、不揮発性の記憶装置である。不揮発性記憶装置２６０３は、各種ソフトウェア・プログラムやデータ等を記憶可能である。
【０２０４】
ネットワークインタフェース２６０６は、通信ネットワークに接続するインタフェース装置であり、例えば有線及び無線のＬＡＮ接続用インタフェース装置を採用してもよい。例えば、データ処理装置は、ネットワークインタフェース２６０６を介して、各種通信ネットワークを介して、通信パケットを取得してもよい。
【０２０５】
ドライブ装置２６０４は、例えば、後述する記録媒体２６０５に対するデータの読み込みや書き込みを処理する装置である。
【０２０６】
記録媒体２６０５は、例えば光ディスク、光磁気ディスク、半導体フラッシュメモリ等、データを記録可能な任意の記録媒体である。
【０２０７】
入出力インタフェース２６０７は、外部装置との間の入出力を制御する装置である。
【０２０８】
上述した実施形態を例に説明した本発明におけるデータ処理装置、あるいはその構成要素は、例えば、図２６に例示するハードウェア装置に対して、上記実施形態において説明した機能を実現可能なソフトウェア・プログラムを供給することにより実現されてもよい。より具体的には、例えば、係るハードウェア装置に対して供給したソフトウェア・プログラムを、演算装置２６０１が実行することによって、本発明が実現されてもよい。この場合、係るハードウェア装置で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト、仮想環境基盤等のミドルウェアなどが各処理の一部を実行してもよい。
【０２０９】
上述した実施形態において上記各図に示した各部は、上述したハードウェアにより実行されるソフトウェア・プログラムの機能（処理）単位である、ソフトウェアモジュールとして実現することができる。ただし、これらの図面に示した各ソフトウェアモジュールの区分けは、説明の便宜上の構成であり、実装に際しては、様々な構成が想定され得る。
【０２１０】
例えば、図１乃至図３に例示したデータ処理装置の各構成要素をソフトウェアモジュールとして実現する場合、これらのソフトウェアモジュールが不揮発性記憶装置２６０３に記憶される。そして、演算装置２６０１がそれぞれの処理を実行する際に、これらのソフトウェアモジュールを記憶装置２６０２に読み出す。
【０２１１】
また、これらのソフトウェアモジュールは、共有メモリやプロセス間通信等の適宜の方法により、相互に各種データを伝達できるように構成されてもよい。このような構成により、これらのソフトウェアモジュールは、相互に通信可能に接続される。
【０２１２】
更に、上記ソフトウェア・プログラムは記録媒体２６０５に記録されてもよい。この場合、上記ソフトウェア・プログラムは、上記データ処理装置の構成要素の出荷段階、あるいは運用段階等において、適宜ドライブ装置２６０４を通じて不揮発性記憶装置２６０３に格納されるよう構成されてもよい。
【０２１３】
なお、上記の場合において、上記ハードウェアへの各種ソフトウェア・プログラムの供給方法は、出荷前の製造段階、あるいは出荷後のメンテナンス段階等において、適当な治具を利用して当該装置内にインストールする方法を採用してもよい。また、各種ソフトウェア・プログラムの供給方法は、インターネット等の通信回線を介して外部からダウンロードする方法等のように、現在では一般的な手順を採用してもよい。
【０２１４】
そして、このような場合において、本発明は、係るソフトウェア・プログラムを構成するコード、あるいは係るコードが記録されたところの、コンピュータ読み取り可能な記録媒体によって構成されると捉えることができる。この場合、係る記録媒体は、ハードウェア装置と独立した媒体に限らず、ＬＡＮやインターネットなどにより伝送されたソフトウェア・プログラムをダウンロードして記憶又は一時記憶した記録媒体を含む。
【０２１５】
また、上述したデータ処理装置の構成要素は、図２６に例示するハードウェア装置を仮想化した仮想化環境と、当該仮想化環境において実行される各種ソフトウェア・プログラム（コンピュータ・プログラム）とによって構成されてもよい。この場合、図２６に例示するハードウェア装置の構成要素は、当該仮想化環境における仮想デバイスとして提供される。なお、この場合も、図２６に例示するハードウェア装置を物理的な装置として構成した場合と同様の構成にて、本発明を実現可能である。
【０２１６】
以上、本発明の好適な実施形態の構成を説明した。しかし、かかる実施形態は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。
【０２１７】
即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【０２１８】
この出願は、２０１５年２月６日に出願された日本出願特願２０１５−０２２０１０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２１９】
１      データ処理装置
１０    探索木制御部
１１    探索木初期化部
１２    ルール更新部
１３    探索木探索部
１４    更新カウンタ取得部
２０    探索木記憶部
２１    種別欄
２２    項目欄
２３    説明欄
２４    ノード種別欄
２５    項目欄
２６    説明欄
３０    ルール記憶部
３１    項目欄
３２    説明欄
３３    例欄
４０    キャッシュテーブル制御部
４１    キャッシュエントリ作成部
４２    キャッシュエントリ探索部
４３    キャッシュエントリ再評価部
５０    キャッシュテーブル記憶部
５１    項目欄
５２    説明欄
５３    項目欄
５４    説明欄
６０    パケット処理部
７０    通信ＩＦ部
８０    データ処理装置制御部
１１１  探索木グループ欄
１１２  所属探索木欄
１１３  使用グループ化基準欄
【図１】
2016125501.tif 000003
【図２】
2016125501.tif 000004
【図３】
2016125501.tif 000005
【図４】
2016125501.tif 000006
【図５】
2016125501.tif 000007
【図６】
2016125501.tif 000008
【図７】
2016125501.tif 000009
【図８】
2016125501.tif 000010
【図９】
2016125501.tif 000011
【図１０】
2016125501.tif 000012
【図１１】
2016125501.tif 000013
【図１２】
2016125501.tif 000014
【図１３】
2016125501.tif 000015
【図１４】
2016125501.tif 000016
【図１５】
2016125501.tif 000017
【図１６】
2016125501.tif 000018
【図１７】
2016125501.tif 000019
【図１８】
2016125501.tif 000020
【図１９】
2016125501.tif 000021
【図２０】
2016125501.tif 000022
【図２１Ａ】
2016125501.tif 000023
【図２１Ｂ】
2016125501.tif 000024
【図２２】
2016125501.tif 000025
【図２３】
2016125501.tif 000026
【図２４】
2016125501.tif 000027
【図２５】
2016125501.tif 000028
【図２６】
2016125501.tif 000029
【手続補正書】
【提出日】平成29年7月24日(2017.7.24)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理するデータ処理装置であって、
１ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化手段と、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶手段と、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新する更新手段と、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶する情報エントリ記憶手段と、
前記第２の情報エントリを使用したデータ処理を行う際に、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに含まれる情報のうち少なくとも前記更新履歴情報に関し前記不整合が検出されたノードに係る情報は無効であるものと判定する再評価手段と
を備えるデータ処理装置。
【請求項２】
前記再評価手段は、前記情報エントリ記憶手段に記憶された前記第２の情報エントリが無効であるものと判定した際に、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と最新の更新履歴情報の値とに不整合があった前記ノードが属する前記探索木について前記第１の情報エントリの再探索を行い、再探索した結果を用いて当該情報エントリ記憶手段に記憶された当該第２の情報エントリを更新する
請求項１に記載のデータ処理装置。
【請求項３】
前記再評価手段は、前記第１の情報エントリの再探索を、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と最新の更新履歴情報の値とに不整合があった前記ノードが属する前記探索木のルートのノードから開始する代わりに、前記情報エントリ記憶手段に記憶された当該第２の情報エントリに関する前記ノード識別子のキャッシュが示すノードから開始する
請求項２に記載のデータ処理装置。
【請求項４】
前記探索木初期化手段は、１ないし複数の前記探索木をグループ化する際に、各前記探索木に含まれる前記第１の情報エントリの特徴を用いてあらかじめ定めたグループ化基準に基づいて、前記探索木のグループ化を行う
請求項１ないし請求項３のいずれかに記載のデータ処理装置。
【請求項５】
前記探索木初期化手段は、前記グループ化基準として、前記第１の情報エントリに含まれる前記データ識別情報の粒度を用いる
請求項４に記載のデータ処理装置。
【請求項６】
前記更新履歴情報および前記共有更新履歴情報が、それぞれの更新回数をカウントする更新カウンタおよび共有更新カウンタからなっており、前記ノードの値と前記キャッシュの値に差異がある状態を不整合とみなす
請求項１ないし請求項５のいずれかに記載のデータ処理装置。
【請求項７】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理する情報エントリ管理方法であって、
１ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択し、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶し、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新し、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶し、
前記第２の情報エントリを使用したデータ処理を行う際に、前記第２の情報エントリを記憶することによって記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記記憶された当該第２の情報エントリは無効であると判定することで、第２の情報エントリを再評価する
情報エントリ管理方法。
【請求項８】
前記第２の情報エントリの再評価は、前記記憶された前記第２の情報エントリが無効であると判定した際に、前記記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と、最新の更新履歴情報の値と、に不整合があった前記ノードが属する前記探索木について前記第１の情報エントリの再探索を行い、再探索した結果を用いて前記記憶された当該第２の情報エントリを更新する
請求項７に記載の情報エントリ管理方法。
【請求項９】
前記第２の情報エントリの再評価は、前記第１の情報エントリの再探索を、前記記憶された当該第２の情報エントリに関する前記更新履歴情報のキャッシュの値と、最新の更新履歴情報の値と、に不整合があった前記ノードが属する前記探索木のルートのノードから開始する代わりに、前記記憶された当該第２の情報エントリに関する前記ノード識別子のキャッシュが示すノードから開始する
請求項８に記載の情報エントリ管理方法。
【請求項１０】
処理対象とするデータを処理する方法を決定するための第１の情報エントリを、それぞれの適用対象とするデータ識別情報を含む第１の情報エントリの集合の中から１ないし複数の探索木を用いて探索し、探索した前記第１の情報エントリを用いて前記データを処理する場合において、各前記探索木を構成するノードである中間ノードおよびリーフノードを前記データ識別情報の探索空間に対応付けて探索した際に得られた前記探索木による前記第１の情報エントリの探索結果を第２の情報エントリとして記憶しておき、前記データを処理する際に、当該データに関する前記第２の情報エントリが記憶されていた場合、当該第２の情報エントリを使用して当該データを処理する情報エントリ管理プログラムであって、
１ないし複数の前記探索木をグループ化し、各探索木グループにおけるベース探索木を選択する探索木初期化処理と、
前記探索木を構成する中間ノードおよびリーフノードの各ノードに関し、前記ノードの更新の履歴を示す更新履歴情報および当該探索木を構成するいずれかの前記ノードの更新の履歴を示す共有更新履歴情報を記憶する探索木記憶処理と、
前記第１の情報エントリの内容を操作した際に、当該第１の情報エントリの前記データ識別情報である操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの更新履歴情報を更新するとともに、当該ノードを含む前記探索木が属する前記探索木グループのベース探索木について前記操作対象データ識別情報と重複する探索空間に対応付けられた前記ノードの共有更新履歴情報を更新する更新処理と、
前記第２の情報エントリとして、前記探索木による前記第１の情報エントリの探索結果として得られる、各前記探索木における探索によって到達したノードを示すノード識別子と当該ノードの前記更新履歴情報および前記共有更新履歴情報とのキャッシュを記憶する第２の情報エントリ記憶処理と、
前記第２の情報エントリを使用したデータ処理を行う際に、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリに関する前記ノードの前記共有更新履歴情報のキャッシュと当該ノードの最新の前記共有更新履歴情報とを、各前記ベース探索木について比較し、両者に不整合があった場合には、当該ノードを含む前記ベース探索木が属する前記探索木グループの各前記探索木について、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリに関する各前記ノードの前記更新履歴情報のキャッシュと各当該ノードの最新の前記更新履歴情報とを比較し、両者に不整合があった場合は、前記第２の情報エントリ記憶処理によって記憶された当該第２の情報エントリは無効であるものと判定する再評価処理と、をコンピュータに実行させる
情報エントリ管理プログラム。
【国際調査報告】
2016125501.tif 000030
2016125501.tif 000031
2016125501.tif 000032