(57)【要約】  処理対象のデータに関して適用されるルールが、複数個、一斉に更新される場合であっても、該処理対象のデータに関する処理を短期間に実現可能な情報処理装置等が提供される。情報処理装置１０１は、メモリ１０４に格納されている情報を更新可能な更新部１０６が、キャッシュメモリ１０５を介することなく更新された情報を格納可能なメモリ１０４に格納されている一部の情報を格納可能なキャッシュメモリ１０５に、第１情報と、該第１情報がキャッシュメモリ１０５に格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、該キャッシュ情報がキャッシュメモリ１０５に格納されている場合にはキャッシュメモリ１０５から該キャッシュ情報を読み取り、該キャッシュ情報がキャッシュメモリ１０５に格納されていない場合にはメモリ１０４から該第１情報を読み取り、該第１情報をキャッシュメモリ１０５に格納するタイミングと該第１情報とが関連付けされた該キャッシュ情報を作成し、作成した該キャッシュ情報をキャッシュメモリ１０５に格納するキャッシュ制御部１０２と、該キャッシュ制御手段によって読み取られた、または、作成された複数セットの該キャッシュ情報であって、該複数セットの該キャッシュ情報における該第１情報が作成または更新された第２タイミングを含んでいる該キャッシュ情報のうち、最新である該第２タイミングよりも前のタイミングを該第１タイミングとして含んでいる該キャッシュ情報を対象として、該キャッシュ情報に該第１情報が更新された第３情報を該メモリから読み取り、読み取った該第３情報を該キャッシュメモリに格納するタイミングと該第３情報とが関連付けされている該キャッシュ情報を作成し、作成した該キャッシュ情報をキャッシュメモリ１０５に格納するデータ制御部１０３とを有する。
2017130824.tif 000002
【特許請求の範囲】
【請求項１】
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段と、
前記キャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御手段と
を備える情報処理装置。
【請求項２】
ある対象データに対して処理を適用するか否かを判定する条件を表す判定条件と、前記判定条件が成立している場合に前記ある対象データ対して適用する前記処理とが関連付けされた処理情報に従い、対象データに関して成立している前記判定条件に関連付けされた前記処理を、前記対象データに対して実行する処理実行手段
をさらに備え、
前記第１情報は、前記判定条件を表す情報である
請求項１に記載の情報処理装置。
【請求項３】
前記対象データに関して成立している前記判定条件のうち、前記対象データに対して実行する前記処理を選択する処理選択手段
をさらに備え、
前記処理情報は、前記判定条件に、さらに、前記処理を選択する順序を表す優先度が関連付けされた情報であり、
前記処理選択手段は、成立している前記判定条件に関連付けされた前記処理のうち、高い前記優先度に関連付けされた前記処理を選択する
請求項２に記載の情報処理装置。
【請求項４】
前記対象データに関して成立している前記判定条件を探索する探索手段
をさらに備え、
前記第１情報は、前記第１情報における前記判定条件に関する判定処理の後に判定される前記判定条件に関する情報、または、前記処理情報を識別可能な処理情報識別子を含み、
前記第３情報は、前記第３情報における前記判定条件に関する判定処理の後に判定される前記判定条件に関する情報、または、前記処理情報を識別可能な処理情報識別子を含み、
前記探索手段は、前記第１情報、または、前記第３情報における前記判定条件が前記対象データに関して成立しているか否かを判定処理と、成立している場合には、前記第１情報または前記第３情報に関する前記判定処理の後にて判定される前記判定条件を含む情報のうち、前記対象データに関して成立している前記判定条件を含む情報を選択する選択処理とを実行することによって、前記対象データに関して成立している前記判定条件に関連付けされた前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する
請求項３に記載の情報処理装置。
【請求項５】
前記データ制御手段は、前記キャッシュ制御手段が読み取った前記キャッシュ情報における前記第１情報に基づき前記探索手段が、前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する場合に参照した前記第１情報における前記第２タイミングのうち最新である前記第２タイミングが、前記第１タイミングよりも後である前記キャッシュ情報に関する第３情報を前記メモリから読み取る
請求項４に記載の情報処理装置。
【請求項６】
前記第１情報が表す前記判定条件は、前記判定処理の後にて判定される前記判定条件よりも緩い条件である
請求項５に記載の情報処理装置。
【請求項７】
前記データ制御手段は、前記探索手段が、前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する場合に参照した前記第１情報における前記第２タイミングのうち最新である前記第２タイミングが前記第１タイミングよりも後である前記キャッシュ情報を特定する場合に参照した前記第１情報を、前記メモリから読み取る
請求項４乃至請求項６のいずれかに記載の情報処理装置。
【請求項８】
前記メモリには、前記第１情報、または、前記第３情報に関連付けされたノードを含む探索木が格納されており、
前記探索木における各ノードは、前記ノードを表すノード識別子によって識別され、
前記第１情報、及び、前記第３情報は、前記ノードを表す前記ノード識別子と、前記判定条件を表す情報と、自ノード情報が更新された更新タイミングと、前記判定条件が成立している場合に前記判定条件の後にて判定される判定条件が関連付けされているノードを表すノード識別子とが関連付けされたノード情報、または、前記ノードを表す前記ノード識別子と、前記判定条件を表す情報と、前記更新タイミングと、前記処理情報を識別可能な前記処理情報識別子とが関連付けされたノード情報であって、
前記探索手段は、前記探索木に含まれている前記ノードに関連付けされた前記ノード情報に基づき、前記対象データに関して成立している前記判定条件を含む前記ノード情報に関連付けされたノードを特定することによって、特定された前記ノードに関連付けされた前記ノード情報に含まれている前記処理情報識別子、または、前記判定処理の後にて判定される前記判定条件を含む前記ノード情報に関連付けされた前記ノード識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する
請求項４乃至請求項７のいずれかに記載の情報処理装置。
【請求項９】
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納する情報処理方法。
【請求項１０】
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御機能と、
前記キャッシュ制御機能によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御機能と
をコンピュータに実現させる情報処理プログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークを介して送受信される情報を処理する情報処理装置等に関する。
【背景技術】
【０００２】
イーサネット（Ｅｔｈｅｒｎｅｔ、登録商標）スイッチ、ルータ、オープンフロー（ＯｐｅｎＦｌｏｗ）スイッチ等のパケット処理装置は、所定のルールに従って、通信ネットワークを介して送受信されるパケットを転送したり、破棄したりする。該パケット処理装置は、パケットを受信し、受信したパケットに適用する処理を実行する場合に、次に示されたステップＳ１乃至ステップＳ３に示されているような処理を順に実行する。【０００３】
（ステップＳ１）通信インターフェースを介してパケットを受信する、
（ステップＳ２）受信したパケットに関する転送処理を実行するのに必要な情報を特定する、
（ステップＳ３）特定した情報に従い、受信したパケットを処理する。【０００４】
特許文献１は、パケット処理装置における処理を、キャッシュメモリを用いて高速に処理可能なキャッシュテーブル管理装置の一例を開示している。【０００５】
特許文献１に開示されたキャッシュテーブル管理装置は、通信ネットワークを介して送受信されるパケットを転送するルータにおいて、該パケットを転送する転送先を決定する場合に従うルールを含むルール情報を、キャッシュメモリに格納する処理を実行する。該キャッシュテーブル管理装置は、該パケットに関する情報（たとえば、記憶領域を表すアドレス、使用時刻等）を表すエントリをキャッシュメモリに格納する場合に、該パケットに適用され得るエントリもキャッシュメモリに格納する。【０００６】
パケット処理装置が実行する処理のうち、上述したステップＳ２に示された処理は、パケット分類（Ｐａｃｋｅｔ＿Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）処理とも呼ばれる。該パケット分類処理は、所定のルールセット（複数のルール、ルール情報）の中の受信したパケットに適合しているルールのうち、優先度の高い（または、優先度が最も高い）ルールを特定する処理である。当該ルールは、マッチ条件（判定条件、たとえば、適合しているアドレスの範囲）と、当該マッチ条件に適合しているパケットに適用する処理を表すアクションとを含む。また、当該ルールは、優先度や統計情報を含む場合もある。たとえば、非特許文献１は、探索木に従いパケットを分類するパケット分類方式に関する技術を開示している。【０００７】
非特許文献１に開示された技術においては、ｄ（ただし、ｄは、自然数）個のフィールド（たとえば、アドレス、ポート番号）に関するルール探索問題が、ｄ次元空間内の部分空間に関する探索問題として扱われている。該技術は、探索木に含まれているノード（節点）を経由するたびに、該ノードに割り当てられている探索空間をカット（分割）することによって、受信したパケットに関するアクションを短期間に探索することが可能な探索木を作成する。すなわち、該技術によれば、探索木におけるルートノードから順に探索することによって、受信したパケットに適用すべき処理は特定される。【０００８】
また、キャッシュメモリを用いて高速な処理を実現する場合には、たとえば、特許文献２に開示されたキャッシュ制御システムに従って、キャッシュメモリに格納されるデータを制御することが可能である。特許文献２は、キャッシュメモリを制御することが可能なキャッシュ制御システムを開示している。特許文献２に開示されたキャッシュ制御システムは、データと、該データが作成された作成時刻とが関連付けされた情報を格納することができるキャッシュメモリを有する。該キャッシュ制御システムは、あるデータを参照する処理においてミスヒットが発生した場合、または、該あるデータに関連付けされた作成時刻が所定の時刻以前であった場合に、該あるデータをデータベースから読み取り、読み取った該あるデータをキャッシュメモリに格納する。【０００９】
また、特許文献３は、通信ネットワークを介して送受信されるデータを処理する技術を開示している。特許文献３に開示された情報処理装置は、通信ネットワークにおいて、階層的に通信接続されている機器が出力する情報を収集する。各機器は、自機器が情報を出力した時刻のうち最後に該情報を出力した時刻と、出力した情報に関する履歴とを記憶している。該情報処理装置は、該機器に格納されている時刻が第１時刻から第２時刻に変更された場合に、該第１時刻にて出力された情報と、該第２時刻にて出力された情報との差分を算出する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００１−２９０７１８号公報
【特許文献２】特開平１０−１２４３７２号公報
【特許文献３】特開２００５−２５０５２１号公報
【非特許文献】
【００１１】
【非特許文献１】Ｂａｌａｊｅｅ  Ｖａｍａｎａｎ、Ｇｗｅｎｄｏｌｙｎ  Ｖｏｓｋｕｉｌｅｎ、ａｎｄ  Ｔ．Ｎ．  Ｖｉｊａｙｋｕｍａｒ、「ＥｆｆｉＣｕｔｓ：  Ｏｐｔｉｍｉｚｉｎｇ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｆｏｒ  Ｍｅｍｏｒｙ  ａｎｄ  Ｔｈｒｏｕｇｈｐｕｔ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ２０１０  ｃｏｎｆｅｒｅｎｃｅ、２０１０年、ｐ．ｐ．２０７−２１８
【発明の概要】
【発明が解決しようとする課題】
【００１２】
受信したパケットに関するルールが、一斉に、複数個更新される場合には、パケット処理装置における処理を、キャッシュメモリを用いることによって短期間に実行することができない。この理由は、図２１Ａ及び図２１Ｂ等を参照しながら詳細に後述するように、複数個のルールを一斉に更新した場合には、キャッシュメモリに格納されているルールと、メインメモリに格納されているルールとの間に、不整合（不一致）が生じる可能性があるからである。したがって、パケット処理装置は、メインメモリに格納されているルールを参照しながら、受信したパケットに関する処理を実行する。【００１３】
より具体的に、特許文献１、及び、特許文献２は、複数個のルールが一斉に更新された場合において、キャッシュメモリを用いることによって高速な処理を実現する処理に関して言及していない。したがって、特許文献１に開示された装置、及び、特許文献２に開示された装置を用いたとしても、キャッシュメモリに格納されているルールと、メインメモリに格納されているルールとの間に生じる可能性がある不整合に関する課題を解決することができない。【００１４】
そこで、本発明の目的の１つは、処理対象のデータに関して適用されるルールが、複数個、一斉（または、一度）に更新される場合であっても、該データに関する処理を短期間に実現可能な情報処理装置等を提供することである。
【課題を解決するための手段】
【００１５】
本発明の一態様において、情報処理装置は、
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段と、
前記キャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御手段と
を備える。【００１６】
また、本発明の他の見地として、情報処理方法は、
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納する。【００１７】
また、本発明の他の見地として、情報処理プログラムは、
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御機能と、
前記キャッシュ制御機能によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御機能と
をコンピュータに実現させる。【００１８】
さらに、同目的は、係る情報処理プログラムを記録するコンピュータが読み取り可能な記録媒体によっても実現される。
【発明の効果】
【００１９】
本発明に係る情報処理装置等によれば、処理対象のデータに関して適用されるルールが、複数個、一斉に更新される場合であっても、該データに関する処理を短期間に実現することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施形態に係る情報処理装置が有する構成の一例を表すブロック図である。
【図２】第１の実施形態に係る探索木制御部が有する構成の一例を示すブロック図である。
【図３】情報処理装置において参照されるルール情報の一例を概念的に表す図である。
【図４Ａ】探索木情報の一例を概念的に表す図である。
【図４Ｂ】中間ノード属性情報の一例を概念的に表す図である。
【図４Ｃ】リーフノード属性情報の一例を概念的に表す図である。
【図５】ノードキャッシュの一例を概念的に表す図である。
【図６】探索木初期化部が、探索木記憶部２０に格納されている探索木に関する情報、及び、ルール記憶部に格納されているルールセットを初期化する場合における処理の流れを示すフローチャートである。
【図７】探索木初期化部が探索木を作成する処理の流れの一例を示すフローチャートである。
【図８】探索木作成サブ処理Ａにおける処理の流れの一例を示すフローチャートである。
【図９】ルールを更新する処理における処理の流れの一例を示すフローチャートである。
【図１０】ルール更新サブ処理Ａにおける処理の流れの一例を示すフローチャートである。
【図１１】ルール更新サブ処理Ｃにおける処理の流れの一例を示すフローチャートである。
【図１２】ルール更新サブ処理Ｂにおける処理の流れの一例を示すフローチャートである。
【図１３】パケットに適合しているルールを探索する処理の流れの一例を示すフローチャートである。
【図１４】ルール探索サブ処理Ａにおける処理の流れの一例を示すフローチャートである。
【図１５】パケットにアクションを適用する処理の流れの一例を示すフローチャートである。
【図１６Ａ】所定の分割手順において、マッチ条件に含まれている各フィールドに関する値をカットする基準を概念的に表す図である。
【図１６Ｂ】所定の分割手順において、マッチ条件に含まれている各フィールドに関する値をカットする基準を概念的に表す図である。
【図１６Ｃ】所定の分割手順において、マッチ条件に含まれている各フィールドに関する値をカットする基準を概念的に表す図である。
【図１６Ｄ】所定の分割手順において、マッチ条件に含まれている各フィールドに関する値をカットする基準を概念的に表す図である。
【図１６Ｅ】所定の分割手順において、マッチ条件に含まれている各フィールドに関する値をカットする基準を概念的に表す図である。
【図１７】ルールに関する優先度の一例を概念的に表す図である。
【図１８】図１７に示されたルールセットに基づき作成された探索木の一例を概念的に表す図である。
【図１９】ノード情報の一例を概念的に表す図である。
【図２０Ａ】パケット処理装置が有する構成の一例を示すブロック図である。
【図２０Ｂ】パケット処理装置が有する構成の一例を示すブロック図である。
【図２１Ａ】２つの探索木がメモリに格納されている場合におけるパケット処理装置が有する構成の一例を示すブロック図である。
【図２１Ｂ】パケット処理装置が有する構成の一例を示すブロック図である。
【図２２】本発明の第２の実施形態に係る情報処理装置が有する構成を示すブロック図である。
【図２３】本発明の各実施形態に係る情報処理装置を実現可能な計算処理装置のハードウェア構成例を、概略的に示すブロック図である。
【発明を実施するための形態】
【００２１】
本願発明の理解を容易にするために、探索木に関する探索処理（図１７乃至図１９を参照しながら後述する）、及び、複数のルール（処理情報、ルールセット）を一斉に更新することによって生じる課題（図２０Ａ、図２０Ｂ、図２１Ａ、及び、図２１Ｂを参照しながら後述する）について説明する。
【００２２】
探索木に含まれているノードには、たとえば、ｄ（ただし、ｄは、自然数）個のフィールドによって構成されている探索空間を表すｄ次元空間内の部分空間が割り当てられている。該探索空間（または、部分空間）は、各フィールドに関して、ルールに関する判定条件（マッチ条件）が成立している（または、不成立である）値が成す空間を表している。各ルールに関する判定条件は、該ルールが表すｄ次元部分空間と重複している部分空間を含む全てのノードに配置されている。
【００２３】
ノードは、中間ノードおよびリーフノード（葉ノード）のいずれかである。
【００２４】
探索木に含まれているリーフノード（葉ノード）には、探索対象であるデータに関する所定の判定条件を表すマッチ条件と、該マッチ条件が成立した場合に該データに適用する処理を表すアクション（処理内容情報）とが関連付けされたルールを識別可能なルール識別子とが配置されている。リーフノードは、該リーフノードに関する子ノードが存在していないノードを表す。探索木に含まれている中間ノードは、リーフノード以外のノードを表す。
【００２５】
以降、識別子を「ＩＤ」と表す。
【００２６】
探索木に含まれているルートノード（根ノード）は、ｄ次元空間における全空間（すなわち、上述した探索空間）を表す。ルートノードは、該ルートノードに関する親ノードが存在していないノードを表す。
【００２７】
探索木を作成する処理においては、あるノードに割り当てられたルールの個数が所定の個数（Ｂｉｎｔｈ）よりも多い場合に、当該ノードは、少なくとも、１つの次元に関してカット（Ｃｕｔ、分割）されることによって、当該ノードを親ノードとする子ノードが作成される。この場合に、該親ノードは、リーフノードとは異なっている中間ノードを表す。これに対して、該あるノードに割り当てられたルールの個数が所定の個数（Ｂｉｎｔｈ）以下である場合に、当該あるノードを親ノードとする子ノードは作成されない。この場合に、当該ノードは、リーフノードを表す。探索木を作成する処理については、図６乃至図８を参照しながら後述する。
【００２８】
図１７乃至図１９を参照しながら、該探索木に従いパケットに適用する処理を探索する探索処理の例について説明する。
【００２９】
まず、図１７を参照しながら、探索木を用いてルールを特定する場合の優先度について説明する。図１７は、ルールに関する優先度の一例を概念的に表す図である。
【００３０】
図１７には、２つのフィールド（次元Ｘ（横軸方向、Ｘ軸方向）、及び、次元Ｙ（縦軸方向、Ｙ軸方向））に関するルールを特定する処理の例が示されている。次元Ｘは、たとえば、０から２５５までの整数値（たとえば、プロトコル番号）を表す。次元Ｙは、たとえば、０から１２７までの整数値（たとえば、アドレス）を表す。図１７において、Ｒ１乃至Ｒ７によって示された各矩形は、それぞれ、ルールＲ１乃至ルールＲ７に含まれている各マッチ条件が成立している値の範囲が設定された２次元の部分空間を表す。探索空間において矩形が重複している場合に、矩形の全てが表示されているマッチ条件は、該矩形よりも背面に配置された矩形よりも、高い優先度（すなわち、適用されるマッチ条件）に関連付けされたルールであることを表す。
【００３１】
次に、図１８を参照しながら、探索木を作成（または、更新）する処理について説明する。図１８は、図１７に示されたルールセットに基づき作成された探索木の一例を概念的に表す図である。図１８は、「Ｂｉｎｔｈ」が２の場合の探索木の一例を示している。
【００３２】
説明の便宜上、ルールセットは、図１７に例示されたルール（すなわち、ルールＲ１乃至ルールＲ７）を含むとする。
【００３３】
たとえば、処理の初期において、ルートノード（この場合、リーフノードである）には、ルールＲ１乃至ルールＲ７が配置されている。該ルートノードに配置されたルールの個数が所定の個数（Ｂｉｎｔｈ）よりも多いので、該ルートノードに配置されたルールセットは、Ｘ軸方向に４つの部分空間（第１矩形と、第２矩形と、第３矩形と、第４矩形及び第５矩形）にカット（Ｃｕｔ、分割）されている。たとえば、図１８に例示された探索木において、ルートノードから、該ルートノードを親ノードとする子ノード（すなわち、リーフ１乃至リーフ３、及び、ノード１）に至る経路は、Ｘ軸方向に４つの部分空間（図１７における第１矩形と、第２矩形と、第３矩形と、第４矩形及び第５矩形）に分割されたことを表す。すなわち、リーフノードであったルートノードは、該４つの各部分空間が割り当てられたノードを子ノードとして有する中間ノードに変換される。
【００３４】
上述した処理の後に、ノード１には、リーフノードとして、ルールＲ５乃至ルールＲ７が配置されている。該ノード１に配置されたルールの個数が所定の個数（Ｂｉｎｔｈ）よりも多いので、該ノード１に配置されたルールセットは、Ｙ軸方向に２つの部分空間（図１７における第４矩形及び第５矩形）に分割される。たとえば、ノード１から、ノード１を親ノードとする子ノード（すなわち、リーフ４、または、リーフ５）に至る経路は、Ｙ軸方向に２つの部分空間（第４矩形と、第５矩形）に分割されたことを表す。すなわち、リーフノードであったノード１は、該２つの各部分空間が割り当てられたノードを子ノードとして有する中間ノードに変換される。図１８において、楕円は中間ノードを表し、矩形はリーフノードを表す。
【００３５】
次に、図１９を参照しながら、探索木の各ノードに配置されたルール（または、ルールセット）と、該ノードを識別可能なノードＩＤとが関連付けされたノード情報について説明する。図１９は、ノード情報の一例を概念的に表す図である。ノード情報は、図２１Ａ等を参照しながら後述するように、メモリに格納されている。また、ノード情報のうち一部の情報が、図２１Ｂ等を参照しながら後述するように、キャッシュメモリに格納されている。
【００３６】
ノード情報は、ノードを表すノードＩＤと、該ノードに割り当てられたルールセットにおける各ルールに含まれているマッチ条件を満たしている値が成す部分空間と、該ルールを表すルールＩＤとが関連付けされた情報である。あるノードＩＤが表すノードに関するノード情報は、該ノードＩＤに関連付けされた部分空間と、該ノードＩＤに関連付けされたルールＩＤとを含む（すなわち、図１９における１つの行）。図１９に例示されたノード情報は、図１８に例示された探索木の各ノードに割り当てられたルールセットに含まれているマッチ条件を満たしている値が成す部分空間に関する情報、及び、各ノードに配置されたルールを表すルールＩＤを含む。図１９に例示されたノード情報においては、ノードＩＤ「ルート」と、部分空間（次元Ｘ「０〜２５５」、及び、次元Ｙ「０〜１２７」）と、ルールＩＤ「Ｒ１〜Ｒ７」とが関連付けされている。これは、当該ルートノードに割り当てられたルールセットに含まれているマッチ条件を満たしている値が成す部分空間が、次元Ｘに関して０から２５５までの値であり、かつ、次元Ｙに関して０から１２７までの値であり、かつ、当該ルートノードに配置されているルールがルールＩＤ「Ｒ１」乃至ルールＩＤ「Ｒ７」であることを表す。言い換えれば、これは、図１８に例示された探索木において、ルートノードに割り当てられた部分空間が、探索空間全体であることを表す。
【００３７】
図１９に例示されたノード情報においては、ノードＩＤ「リーフ４」と、次元Ｘ「１９２〜２５５」と、次元Ｙ「０〜６３」と、ルールＩＤ「Ｒ５、Ｒ７」とが関連付けされている。これは、リーフ４に割り当てられたルールに含まれているマッチ条件を満たしている値が成す部分空間が、次元Ｘに関して１９２から２５５までの値であり、かつ、次元Ｙに関して０から６３までの値であり、かつ、リーフ４に割り当てられたルールがルールＲ５、及び、ルールＲ７であることを表す。図１８に例示された探索木において、リーフ４は、ルートノードからリーフ４に至る経路に位置し、さらに、ノード１にて２つにカットされることによって作成されたリーフであることを表す。また、リーフ４の位置は、ルートノードにおけるカットの方向（すなわち、Ｘ軸方向、図１７）に関して４番目の矩形（すなわち、第４矩形、または、第５矩形）によって示された場所である。さらに、リーフ４の位置は、ノード１におけるカットの方向（すなわち、Ｙ軸方向、図１７）に関して１番目の矩形（すなわち、第５矩形）によって示された場所である。
【００３８】
図１９に例示されたノード情報においては、中間ノードであるルートノードに関して、該ルートノードの子ノードを表す子ノードＩＤ（図１９における、リーフ１、リーフ２、リーフ３、及び、ノード１）が関連付けされている。また、中間ノードであるノード１に関して、ノード１の子ノードを表す子ノードＩＤ（図１９における、リーフ４、及び、リーフ５）が関連付けされている。
【００３９】
ノード情報は、上述した例に限定されない。
【００４０】
図１７に例示された探索空間、図１８に例示された探索木、及び、図１９に例示されたノード情報に従った処理であり、かつ、Ｘの値が２３０であり、Ｙの値が３０であるパケットを受信した場合に、該パケットに適用するアクション（処理）を特定する処理について説明する。説明の便宜上、ルール特定装置は、該パケットに適用するアクションを特定するとする。
【００４１】
ルール特定装置は、受信したパケットに関するＸの値（たとえば、プロトコル番号）、及び、Ｙの値（たとえば、アドレス）がルートノードに配置された次元Ｘの範囲、及び、ルートノードに配置された次元Ｙの範囲に含まれているか否かを判定する。受信したパケットに関するＸの値が２３０であるので、ルール特定装置は、ルートノードに配置された次元Ｘ（０から２５５までの値）が値「２３０」を含んでいると判定する。同様に、受信したパケットに関するＹの値が３０であるので、ルール特定装置は、ルートノードに配置された次元Ｙ（０から１２７までの値）が値「３０」を含んでいると判定する。したがって、該パケットは、該ルートノードに配置された部分空間に含まれている。すなわち、該パケットは、該部分空間に関する判定条件（マッチ条件）を満たしている。
【００４２】
次に、ルール特定装置は、該ルートノードの子ノードであるリーフ１、リーフ２、リーフ３、及び、ノード１に関して、それぞれ、受信したパケットに関するＸの値、及び、受信したパケットに関するＹの値が、当該部分空間に含まれているか否かを判定する。受信したパケットに関するＸの値が２３０であるので、ルール特定装置は、ノード１に関連付けされた次元Ｘ（１９２から２５５までの値）が値「２３０」を含んでいると判定する。また、受信したパケットに関するＹの値が３０であるので、ルール特定装置は、ノード１に関連付けされた次元Ｙ（０から１２７までの値）が値「３０」を含んでいると判定する。したがって、ルートノードに関して、ルール特定装置は、ノード１に割り当てられたルールに含まれているマッチ条件を満たしている値が成す部分空間（Ｘの値が１９２から２５５までの値、かつ、Ｙの値が０から１２７までの値）が受信した値を含んでいると判定する。
【００４３】
次に、ルール特定装置は、リーフ４、及び、リーフ５に関して、上述した処理と同様の処理を実行する。すなわち、受信したパケットに関するＸの値が２３０であるので、ルール特定装置は、リーフ４に割り当てられたルールにおけるマッチ条件を満たしている値が成す次元Ｘ（１９２から２５５までの値）が、受信したパケットに関する値を含んでいると判定する。受信したパケットに関するＹの値が３０であるので、ルール特定装置は、リーフ４に関連付けされた次元Ｙ（０から６３までの値）が、受信したパケットに関する値を含んでいると判定する。したがって、ノード１に関して、ルール特定装置は、探索木に従い、１番目の部分空間を示すリーフ４（Ｘの値が１９２から２５５までの値、かつ、Ｙの値が０から６３までの値）にて、上述した処理と同様の判定処理を実行する。尚、リーフ４には、ルールＩＤ「Ｒ５」、及び、ルールＩＤ「Ｒ７」が割り当てられている。
【００４４】
次に、ルール特定装置は、リーフ４に割り当てられたルールのうち、優先度が高いルールを特定する。ルール特定装置は、たとえば、リーフ４に割り当てられたルール群内を線形探索する（各ルールにおけるマッチ条件と、受信したパケットに関するＸの値、及び、Ｙの値を比較する）ことによって、ルールＩＤ「Ｒ５」が表すルール、及び、ルールＩＤ「Ｒ７」が表すルールのうち、受信したパケットに判定条件が適合し、かつ、最も優先度が高いルール（たとえば、ルールＲ７）を特定する。
【００４５】
以降の説明においては、説明の便宜上、探索処理において最後に参照したノード（図１８におけるリーフ４）を「到達ノード」と表すとする。
【００４６】
上述した探索処理の説明においては、探索木が一つの場合を例示したが、非特許文献１に記載の技術は、ルールの特徴を用いて分類することによってルールセットを複数のサブルールセットに分割する。次に、該技術においては、該サブルールセットごとに探索木を作成することによって探索する処理を実現する例が開示されている。サブルールセットごとに探索木を作成した場合に、受信したパケットに関するルール探索処理は、各サブルールセットに関する各探索木に対して実行され、各サブルールセットに関して得られたルール（すなわち、得られるルール数は最大でサブルールセットの数と同じ）の中から最も優先度が高いルールが選択される。
【００４７】
次に、図２０Ａ、図２０Ｂ、図２１Ａ、及び、図２１Ｂを参照しながら、複数のルールを一斉に更新することによって生じる課題について説明する。
【００４８】
図２０Ａを参照しながら、パケット処理装置９４が有する構成について説明する。図２０Ａは、パケット処理装置９４が有する構成の一例を示すブロック図である。
【００４９】
パケット処理装置９４は、探索処理を実行する探索処理回路９０と、バス９１と、探索木に含まれているノード情報が格納されているメモリ９２とを有する。メモリ９２は、探索木に関する情報と、ノード情報（図１９に例示）が格納されている。図２０Ａにおいて、楕円は、探索木におけるノードを表している。
【００５０】
探索処理回路９０は、バス９１を介して、メモリ９２からノード情報（図１９に例示）を読み取り、読み取ったノード情報に基づき、パケットに適用する処理を特定する探索処理を実行する。探索処理回路９０は、専用の論理回路として実現されてもよいし、ソフトウェアに従い、中央演算処理装置（ＣＰＵ）を制御することによって実現されてもよい。
【００５１】
メモリ９２に格納されているノード情報に含まれている情報が多量である場合に、該多量の情報を読み取ることによって、メモリ９２と、探索処理回路９０とを通信接続しているバス９１が処理可能な処理量が飽和してしまう（すなわち、バス９１の帯域が不足してしまう）可能性がある。バス９１に関する帯域が不足した場合には、探索処理回路９０がメモリ９２に格納されているノード情報を読み取る所要時間が長くなってしまうので、探索処理回路９０は、パケットに適用する処理を特定する探索処理を短期間に実行することができない。
【００５２】
バス９１に関する帯域が不足することによって探索処理に要する所要時間が長期化してしまう状況を軽減する手法として、図２０Ｂに示されているように、バス９１を経由したデータを一時的に格納可能なキャッシュメモリ９３に格納する手法がある。図２０Ｂは、パケット処理装置９４が有する構成の一例を示すブロック図である。
【００５３】
パケット処理装置９４は、探索処理回路９０と、メモリ９２と、キャッシュメモリ９３とを有する。キャッシュメモリ９３は、探索処理回路９０と、メモリ９２との間にて入出力されるデータ（ノード）のコピーを一時的に格納することができる。キャッシュメモリ９３は、たとえば、探索処理回路９０の内部に設置されたり、バス９１と探索処理回路９０との接続点に設置されたり、探索処理回路９０の外部に設けられ、バス９１より広帯域なバスを介して探索処理回路９０に接続されたりする。図２０Ｂにおいては、探索処理回路９０がキャッシュメモリ９３を有している。
【００５４】
図２０Ｂに示された例において、キャッシュメモリ９３は、ノード１に関するノード情報のコピー、ノード２１に関するノード情報のコピー、及び、ノード３１に関するノード情報のコピーを記憶（キャッシュ）している。これは、探索処理回路９０がメモリ９２に格納されているノード１、ノード２１、及び、ノード３１に関するノード情報を参照することによって、キャッシュメモリ９３がノード１、ノード２１、及び、ノード３１に関するノード情報を記憶している状態を表す。
【００５５】
しかし、キャッシュメモリ９３に格納されているデータと、メモリ９２に格納されているデータとは、必ずしも、一致しているとは限らない。キャッシュメモリ９３に格納されているデータと、メモリ９２に格納されているデータとが一致していない状況は、たとえば、メモリ９２に格納されている探索木、及び、ノード情報に対して、ルールを追加（削除、または、変更）する等の更新処理に応じて生じる可能性がある。このような状況は、たとえば、探索処理にて参照されたノード情報がキャッシュメモリ９３に格納され、その後、メモリ９２に格納されている複数の探索木が探索にて参照され、さらに、更新処理にて一斉に適用されるルールがメモリ９２にて複数個ある場合に生じる可能性がある。
【００５６】
図２１Ａを参照しながら、キャッシュメモリ９３に格納されているデータと、メモリ９２に格納されているデータとが一致していない状況が生じる例について説明する。図２１Ａは、２つの探索木がメモリ９２に格納されている場合におけるパケット処理装置９４が有する構成の一例を示すブロック図である。
【００５７】
メモリ９２には、２つの探索木（第１探索木（ノード１がルートノードである探索木）、及び、第２探索木（ノード７がルートノードである探索木））が格納されている。
【００５８】
キャッシュメモリ９３には、ノード１、ノード２１、及び、ノード３１に関する情報が格納されている。これは、たとえば、パケット処理装置９４が、処理対象である対象パケットに適用する処理を第１探索木に従い探索した場合に、第１探索木において、ノード１、及び、ノード２１を経由して、ノード３１に到達した状態を示している。また、キャッシュメモリ９３には、さらに、ノード７、ノード８１、及び、ノード９１に関する情報が格納されている。これは、パケット処理装置９４が、たとえば、対象パケットに適用する処理を第２探索木に従い探索した場合に、該第１探索木において、ノード７、及び、ノード８１を経由して、ノード９１に到達した状態を示している。
【００５９】
説明の便宜上、図２１Ａに示すように、キャッシュメモリ９３には、ノード１、ノード２１、ノード３１、ノード７、ノード８１、及び、ノード９１が格納されているとする。また、メモリ９２にて、更新（変更、追加、削除等）が一斉に適用される２つのルールが更新されたとする。すなわち、第１ルール（後述）がノード３１に追加され、及び、第２ルール（後述）がノード９２に追加されたとする。ここで、第１ルール、及び、第２ルールは、以下に示されているようなルールであるとする。すなわち、
第１ルール：
マッチ条件：パケットの送信先を表すあて先ＩＰアドレスは、「１９２．１６８．１００．０／２４」であるか、当該パケットの送信先を表すあて先ポート番号は、「８０」であるか否か（「１９２．１６８．１００」等は、プレフィクスビットを表す。ドットで区切られた数字は、それぞれ８ビットを用いて１０進数を表す。この８ビットで構成される１０進数が０の場合には、この８ビットは、１から２５５までの整数値を表す。また、「／」の後の数は、プレフィクスの長さを表す。この場合に、「１９２．１６８．１００．０／２４」は、２４ビットを用いて「１９２．１６８．１００」なるプレフィックスを表す）、
優先度：優先度（大きな値ほど優先される）は、１０００である、
アクション：マッチ条件を満たしている場合に、パケットを破棄する。
【００６０】
第２ルール：
マッチ条件：あて先ＩＰアドレスは、「１９２．１６８．１００．０／２４」であるか否か、
優先度：優先度は、１００である、
アクション：マッチ条件を満たしている場合に、通信インターフェース（以降、インターフェースを「ＩＦ」と表す）を介してパケットを送信する。
【００６１】
ＩＰは、Ｉｎｔｅｒｎｅｔ＿Ｐｒｏｔｏｃｏｌの略称を表す。
【００６２】
第１ルール、及び、第２ルールは、通信ＩＦを介して、あて先ＩＰアドレスが「１９２．１６８．１００．０／２４」であるパケットを送信するものの、該パケットのうち、あて先ポート番号が８０であるパケットを破棄するという一つの通信制御を実現する通信制御方法を表す。したがって、第１ルール、及び、第２ルールが更新される場合に、第１ルール、及び、第２ルールは、一斉に更新される必要がある。
【００６３】
１つの通信制御を実現しているルールのうち、いずれかのルールのみがパケット処理に適用された場合に、当該通信制御の意図と異なるパケット処理が行われてしまう。たとえば、第１ルールに基づき、あて先ポート番号が「８０」であるパケットを破棄する必要があるにもかかわらず、第１ルールが適用されずに第２ルールのみが適用された場合には、あて先ＩＰアドレスが「１９２．１６８．１００．０／２４」であり、かつ、あて先ポート番号が「８０」であるパケットが、通信ＩＦを介して送信されてしまう。
【００６４】
図２１Ｂを参照しながら、探索木が更新された後に生じる状況について説明する。図２１Ｂは、図２１Ａに示された状況にて、第１探索木におけるノード３１に第１ルールが追加され、さらに、第２探索木におけるノード９２に第２ルールが追加された場合におけるパケット処理装置９４が有する構成の一例を示すブロック図である。
【００６５】
メモリ９２に格納されている第１探索木におけるノード３１には、第１ルールが追加されることによって、ノード３１がノード３１Ｍに更新されている。メモリ９２に格納されている第２探索木におけるノード９２には、第２ルールが追加されることによって、該ノード９２がノード９２Ｍに更新されている。
【００６６】
図２１Ｂに示された状態において、パケットに適用する処理を探索する例を参照しながら、キャッシュメモリ９３に格納されているデータ、及び、メモリ９２に格納されているデータが一致していない場合に生じる課題について説明する。パケットは、あて先ＩＰアドレスが「１９２．１６８．１００．１」であり、かつ、あて先ポート番号が「８０」であるパケット（「第１パケット」と表す）であるとする。
【００６７】
探索木に従って該第１パケットに適用する処理が探索される場合には、当該第１パケットが、該探索木に従って分類されることによって、第１探索木におけるノード３１Ｍ、及び、第２探索木におけるノード９２Ｍに分類されるのが正しい処理であるとする。
【００６８】
しかし、キャッシュメモリ９３には、該対象パケットに関する第１探索木に従った探索処理にて、該対象パケットの探索処理にて参照されたノード群（ノード１、及び、ノード２１、及び、ノード３１）が格納されている。探索処理回路９０は、キャッシュメモリ９３に格納されているノード（すなわち、ノード３１）に従い、受信した第１パケットに適用する処理を特定する。この結果、探索処理回路９０は、該第１パケットに関する探索処理にて、メモリ９２に格納されているノード３１Ｍを参照しないので、ノード３１Ｍに配置された第１ルールを特定することができない。
【００６９】
これに対して、該対象パケットに関する第２探索木に従った探索処理によって、キャッシュメモリ９３には、該対象パケットの探索処理にて参照されたノード群（ノード７、ノード８１、及び、ノード９１）が格納されている。当該探索処理においては該第１パケットが分類される分類先（カテゴリ、クラス）を表すノード９２Ｍがキャッシュメモリ９３には格納されていない。したがって、探索処理回路９０は、該第１パケットに関する探索処理にて、メモリ９２に格納されているノード９２Ｍを参照するので、追加された第２ルールを特定することができる。
【００７０】
言い換えれば、パケット処理装置９４は、受信した第１パケットに適用する処理を、第１探索木、及び、第２探索木に従って特定する場合に、第１ルールではなく、第２ルールにおけるアクションが、受信した第１パケットに適用すべき処理であると特定する。したがって、特許文献１、または、特許文献２に開示された装置によれば、一斉に適用する必要がある複数のルールに関する更新処理が行われた場合には、キャッシュメモリを用いてデータに関する処理を短期間に実現することができない。
【００７１】
以降の説明においては、説明の便宜上、情報処理は、パケット処理であるとする。当該情報処理に用いられる情報エントリは、ルールであるとする。また、パケットは、ＩＰｖ４（Ｉｎｔｅｒｎｅｔ＿Ｐｒｏｔｏｃｏｌ＿ｖｅｒｓｉｏｎ＿４）に従ったパケットであるとする。しかし、上記のように仮定されたパケット処理の場合に限定されるものではなく、一般的な情報処理についても広く適用することができる。
【００７２】
上述したような、パケット処理装置における処理を、キャッシュメモリを用いて高速化する場合に生じる課題を踏まえて、発明を実施する実施形態について図面を参照しながら詳細に説明する。
【００７３】
＜第１の実施形態＞
図１を参照しながら、本発明の第１の実施形態に係る情報処理装置１が有する構成について詳細に説明する。図１は、本発明の第１の実施形態に係る情報処理装置１が有する構成の一例を表すブロック図である。
【００７４】
本発明の第１の実施形態に係る情報処理装置１は、探索木制御部１０と、探索木記憶部２０と、ノードキャッシュ記憶部３０と、ルール記憶部４０と、パケット処理部５０と、通信ＩＦ６０と、制御部７０とを有する。
【００７５】
探索木制御部１０（図２を参照しながら後述する）は、たとえば、探索木記憶部２０に格納される（格納されている）探索木、及び、ルール記憶部４０に格納される（格納されている）ルールを管理する。探索木制御部１０は、たとえば、探索木を初期化する処理、探索木に従って受信したパケットに適用する処理を探索する探索処理、探索木を更新する処理（ルールを追加する処理等）等の処理を実行する。
【００７６】
探索木記憶部２０には、受信したパケット（すなわち、処理対象であるデータ）に対して適用する処理を特定する場合に参照する探索木等が格納される（格納されている）。この場合に、探索木は、少なくとも１つのノード（中間ノード、または、リーフノード）を含む。探索木記憶部２０に格納されている探索木の個数は、少なくとも１個であるが、複数個であってもよい。探索木記憶部２０は、たとえば、メインメモリを用いて実現される。
【００７７】
説明の便宜上、探索木には、該探索木を一意に識別可能な探索木ＩＤ（たとえば、第１探索木、または、第２探索木）が割り当てられているとする。ノードには、該ノードを一意に識別可能なノードＩＤが割り当てられているとする。複数の探索木が分類された探索木グループには、該探索木グループを一意に識別可能なグループＩＤが割り当てられているとする。
【００７８】
ノードキャッシュ記憶部３０には、探索木制御部１０が探索処理を実行した場合に参照したノードに関するノード情報のコピー（キャッシュ情報、以降、「ノードキャッシュ」と表す、図５を参照しながら後述する）が格納（キャッシュ）される。ノードキャッシュ記憶部３０は、たとえば、メインメモリが有する機能を用いて実現されていてもよいし、セットアソシエイティブ方式に従うキャッシュメモリが有する機能を用いて実現されていてもよい。ノードキャッシュ記憶部３０を実現する態様は、上述した例に限定されない。
【００７９】
ノードキャッシュ記憶部３０においては、新たなノード情報がキャッシュされる処理にて、当該ノード情報を格納可能な記憶領域の候補を表すエントリが選択される。または、ノードキャッシュ記憶部３０においては、新たなノード情報がキャッシュされる処理にて、該エントリが表す候補のうち、当該ノードが格納される格納先を表すタグに空き領域がない場合に、当該記憶領域の中から最も長く参照されていないエントリが削除され、その後、削除された記憶領域に当該ノードをキャッシュしてもよい。最も長く参照されていないエントリを削除される処理方式は、ＬＲＵ（Ｌｅａｓｔ＿Ｒｅｃｅｎｔｌｙ＿Ｕｓｅｄ）アルゴリズムとも呼ばれる。
【００８０】
ルール記憶部４０は、パケットに適用する処理を探索する場合に参照されるルールを記憶することができる。ルール記憶部４０は、複数のルール（ルールセット、サブルールセット）を記憶してもよい。ルール記憶部４０は、たとえば、メインメモリが有する機能を用いて実現することができる。ルール記憶部４０は、たとえば、配列やハッシュテーブル等のデータ構造に従って、ルールセットを記憶している。各ルール、各ルールセット、及び、各サブルールセットには、一意に識別するサブルールセットＩＤが割り当てられている。
【００８１】
パケット処理部５０は、通信ＩＦ６０を介してパケット（すなわち、処理対象であるデータの一種）を受信し、受信したパケットに適用する処理を、該受信したパケットに対して実行する。この処理にて、パケット処理部５０は、まず、探索木制御部１０、及び、制御部７０に対して、当該パケットに適用する処理を特定するよう要求する要求（リクエスト、指示）信号を出力する。探索木制御部１０、及び、制御部７０は、該要求信号を入力し、その後、当該パケットに適用する処理に関するエントリ（たとえば、ノード、ルール等の記憶領域を表す）を特定する。パケット処理部５０は、探索木制御部１０、及び、制御部７０が特定した情報エントリに格納されている処理（アクション）を、受信したパケットに対して適用する。
【００８２】
まとめると、探索木制御部１０、及び、パケット処理部５０は、処理情報（たとえば、図１７等を参照しながら説明したルール）に基づき、処理対象であるデータを表す対象データが判定条件（マッチ条件）を満たしている場合に、該判定条件に関連付けされたアクション（処理）を、該対象データに対して適用する。すなわち、情報処理装置１は、探索木制御部１０、及び、パケット処理部５０が有する機能を実現する処理実行部を有していてもよい。この結果、情報処理装置１は、たとえば、受信したパケットをルールに従って処理する通信処理装置を実現することができる。
【００８３】
通信ＩＦ６０は、情報処理装置１と、通信ネットワーク（不図示）とを通信可能に接続している通信インターフェースである。通信ＩＦ６０は、当該通信ネットワークにて実行されている通信に関する通信プロトコルに従い、パケットを送受信する。
【００８４】
制御部７０は、ルールセットやサブルールセットに従ってパケットを処理するように、情報処理装置１における各部を制御する。情報処理装置１が起動した場合に、制御部７０は、たとえば、探索木制御部１０におる探索木初期化部１１（図２）に対して初期ルールセットを出力し、その後、該初期ルールセットに従い初期化する要求信号を探索木初期化部１１に対して出力する。制御部７０は、当該初期ルールセットを記憶装置（不図示）から入力してもよいし、他の制御装置（不図示）から受信してもよい。また、制御部７０は、たとえば、ユーザーインターフェース（不図示）を介して、ユーザからルールを更新する更新命令（信号）を受け取った場合に、探索木制御部１０に対してルールを更新する更新処理を要求する信号を出力する。また、制御部７０は、他の制御装置（不図示）からルールを更新する更新命令を受信した場合に、探索木制御部１０に対してルールを更新する更新処理を要求する信号を出力してもよい。
【００８５】
次に、図３を参照しながら、情報処理装置１において参照されるルール（ルール情報）について説明する。図３は、情報処理装置１において参照されるルール情報の一例を概念的に表す図である。
【００８６】
ルール情報においては、送受信されたパケットに対して適用する処理を選択する場合に参照される判定条件を表すマッチ条件と、該マッチ条件が成立した場合に該パケットに対して適用される処理を表すアクションとが関連付けされている。ルール情報においては、さらに、マッチ条件が成立しているルールが複数ある場合に、複数のルール間における順序を表す優先度と、該マッチ条件が成立したパケットに関する統計情報（パケットサイズ、パケット数等）と、該ルールが削除待ちであるか否かを表す削除情報（削除情報）とが関連付けされてもよい。
【００８７】
以降、説明の便宜上、ルール情報を、単に、「ルール」と表すこともある。
【００８８】
各ルールに含まれているマッチ条件は、たとえば、当該ルールに適合しているパケットに含まれている各フィールドの値に関する条件によって設定されている。たとえば、フィールドは、あて先ＩＰアドレス、送信元ＩＰアドレス、あて先ポート番号、送信元ポート番号、または、プロトコル番号等のフィールド（タプル）である。より具体的に、マッチ条件は、たとえば、あて先ＩＰアドレスを表す範囲、送信元ＩＰアドレスを表す範囲、あて先ポート番号を表す範囲、送信元ポート番号を表す範囲、及び、プロトコル番号を表す範囲が関連付けされた判定条件である。たとえば、あて先ＩＰアドレスを表す範囲は、開始あて先ＩＰアドレス、及び、終了あて先ＩＰアドレスを用いて表されてもよい。送信元ＩＰアドレスを表す範囲は、開始送信元ＩＰアドレス、及び、終了送信元ＩＰアドレスを用いて表されてもよい。あて先ＩＰアドレスを表す範囲は、開始あて先ポート番号、及び、終了あて先ポート番号を用いて表されてもよい。送信元ポート番号を表す範囲は、開始送信元ポート番号、及び、終了送信元ポート番号を用いて表されてもよい。プロトコル番号を表す範囲は、開始プロトコル番号、及び、終了プロトコル番号を用いて表されてもよい。
【００８９】
図３に例示されたルールに含まれているマッチ条件は、次の条件１乃至条件５に関する条件を含んでいる。
【００９０】
条件１：あて先ＩＰアドレスが「０．０．０．０」（開始送信元ＩＰアドレス）から「２５５．２５５．２５５．２５５」（終了送信元ＩＰアドレス）に至る範囲内であるか否か、
条件２：送信元ＩＰアドレスが「１０．０．０．０」（開始送信元ＩＰアドレス）から「１０．２５５．２５５．２５５」（終了送信元ＩＰアドレス）に至る範囲内であるか否か、
条件３：送信元ポート番号が「８０」（開始送信元ポート番号、及び、終了送信元ポート番号が「８０」）であるか否か、
条件４：送信元ポート番号が「０」（開始送信元ポート番号）から「６５５３５」（終了送信元ポート番号）に至る範囲であるか否か、
条件５：プロトコル番号が「１７」（開始プロトコル番号、及び、終了プロトコル番号が「１７」）であるか否か。
【００９１】
ただし、マッチ条件は、上述したフィールドに限定されない。
【００９２】
ルールに関する優先度は、あるパケットに対して適合しているルールが複数個ある場合に、適合しているルールの中から、該あるパケットに適用するルールを選択する基準を表す。各ルールに関する優先度は、たとえば、非負整数等の数値であり、大きな数値であるほど高い優先度を示す。図３に例示されたルールは、優先度「１００」に関連付けされている。
【００９３】
また、アクションは、受信したパケットに関してマッチ条件が成立している場合に、該パケットに適用する処理を表す。アクションがパケットを送信（または、受信）する処理である場合に、パケット処理部５０は、通信ＩＦ６０を介して該パケットを送信（または、受信）する。各ルールに関するアクションの個数は、必ずしも、１個である必要はなく、０個であっても、あるいは、複数個であってもよい。ルールが成り立つ場合に実行されるアクションの一例を以下に示す。ただし、ルールが成り立つ場合に実行されるアクションとして以下に示すアクションａ乃至アクションｋに示された処理に限定されない。
【００９４】
アクションａ：指定された通信ＩＦを介してパケットを送信する、
アクションｂ：パケットのあて先を表すＭＡＣ（Ｍｅｄｉａ＿Ａｃｃｅｓｓ＿Ｃｏｎｔｒｏｌ）アドレスを指定された値に変更する、
アクションｃ：パケットの送信元を表すＭＡＣアドレスを指定された値に変更する、
アクションｄ：パケットのあて先を表すＩＰアドレスを指定された値に変更する、
アクションｅ：パケットの送信元を表すＩＰアドレスを指定された値に変更する、
アクションｆ：パケットのあて先を表すポート番号を指定された値に変更する、
アクションｇ：パケットの送信元を表すポート番号を指定された値に変更する、
アクションｈ：パケットにＶＬＡＮ（Ｖｉｒｔｕａｌ＿Ｌｏｃａｌ＿Ａｒｅａ＿Ｎｅｔｗｏｒｋ）タグを追加する、
アクションｉ：パケットにおけるＶＬＡＮタグを削除する、
アクションｊ：パケットにおけるＶＬＡＮタグを変更する、
アクションｋ：パケットを破棄する。
【００９５】
図３に示された統計情報は、当該ルールにおけるマッチ条件を満たしたパケットに関する統計値である。統計値は、たとえば、送信パケットサイズの合計値、受信したパケットサイズの合計値、送信パケット数の合計値、受信したパケット数の合計値等である。
【００９６】
削除情報は、当該ルールを削除する要求を受けたものの、当該ルールが参照中であるので、当該要求に応じた削除処理が延期されているか（すなわち、削除待ちであるか）否かを示す情報（フラグ）である。
【００９７】
次に、図４Ａ乃至図４Ｃを参照しながら、探索木記憶部２０に格納可能な探索木に関する情報を表す探索木情報、及び、ノードに関する情報を表すノード属性情報（中間ノード属性情報、及び、リーフノード属性情報）について説明する。図４Ａは、探索木情報の一例を概念的に表す図である。図４Ｂは、中間ノード属性情報の一例を概念的に表す図である。図４Ｃは、リーフノード属性情報の一例を概念的に表す図である。
【００９８】
探索木記憶部２０には、複数の探索木に関する探索木情報と、ノード属性情報（中間ノード属性情報、及び、リーフノード属性情報）とを格納することができる。
【００９９】
図４Ａを参照すると、探索木情報は、探索木におけるルートノードを表すノードＩＤ（ルートノードＩＤ）と、該探索木におけるノードに割り当てられたサブルールセットを表すサブルールセットＩＤとが関連付けされた情報を表す。
【０１００】
図４Ｂを参照すると、中間ノード属性情報においては、リーフ情報と、親ノードを表す親ノードＩＤと、部分空間を表す情報と、カットする次元と、カット後におけるノードの個数（分割数）と、分割によって作成されたノード（すなわち、子ノード）を表す子ノードＩＤリストとが関連付けされている。さらに、中間ノード属性情報においては、ノードが最後に更新されたタイミングを表す更新タイミングに関連付けされている。図４Ｃを参照すると、リーフノード属性情報においては、リーフ情報と、親ノードを表す親ノードＩＤと、部分空間を表す情報と、ノードが最後に更新されたタイミングを表す更新タイミングを表す情報と、該ノードに割り当てられたルールを表すルールＩＤリストとが関連付けされている。以降の説明においては、更新タイミングを表す情報を、単に、「更新タイミング」と表す。
【０１０１】
すなわち、中間ノード属性情報は、親ノードを表すノードＩＤと、該部分空間を表す情報と、子ノードを表すノードＩＤとが関連付けされたデータ構造を有している。
【０１０２】
リーフ情報と、親ノードを表すノードＩＤと、部分空間を表す情報と、更新タイミングとは、中間ノード属性情報、及び、リーフノード属性情報に、共通に含まれている。次に、中間ノード属性情報、または、リーフノード属性情報に含まれている各項目に関して説明する。
【０１０３】
リーフ情報は、当該ノードがリーフノードであるか否かを表す情報である。リーフ情報がオンである場合に、当該ノードは、リーフノードである。リーフ情報がオフである場合に、当該ノードは、中間ノードである。
【０１０４】
親ノードＩＤは、当該ノードが配置された探索木において、当該ノードの親ノード（ルートノード側の隣接しているノード）を表すノードＩＤである。
【０１０５】
更新タイミングは、当該ノードが最後に更新されたタイミングを表す。ここで、該タイミングとは、時刻でもよいし、たとえば、情報処理装置１において時間が経過するのに応じて増加する非負整数であってもよい。
【０１０６】
部分空間を表す情報は、当該ノードにおいてルールを探索する範囲を表す部分空間に関する情報である。該部分空間に関する情報は、図１９に示された部分空間に関する情報と同様の情報である。ただし、探索空間は、必ずしも、２次元であるとは限らず、たとえば、５つのタプル（５―Ｔｕｐｌｅ）に関するマッチ条件の場合に、次元数は、５次元である。
【０１０７】
図４Ｂにおいて、「カットする次元」、及び、「カット数」は、該ノードに割り当てられた探索空間を、たとえば、５つの次元に関してカッティング（Ｃｕｔｔｉｎｇ）することによって、該ノードの子ノードを作成する処理に関する制約条件を表す情報を表す。たとえば、図１８に例示された探索木において、ルートノードに関する項目「カットする次元」に関する値は、「Ｘ軸」であり（図１７における縦方向の点線に相当）、項目「カット数」に関する値は、「４」である。また、図１９に例示されたノード情報において、ノード１に関する項目「カットする次元」に関する値は、「Ｙ軸」であり（図１７における横方向の点線に相当）、項目「カット数」に関する値は、「２」である。探索木の作成においては、あるノードにおいて同時に複数の次元に関してカットされてもよく、この場合に、「カットする次元」、及び、「カット数」の組は、次元ごとに格納される。
【０１０８】
図４Ｂにおいて、子ノードＩＤリストは、分割によって作成されたノード（すなわち、子ノード）を表すノードＩＤを含む。たとえば、図１８に例示された探索木において、ルートノードに関する子ノードＩＤリストは、リーフ１、リーフ２、リーフ３、及び、ノード１を含む。子ノードＩＤリストに含まれているノードＩＤが表すノードは、該中間ノードに割り当てられた探索空間（部分空間）に関する判定処理の後で判定されるマッチ条件を満たしている値が成す探索空間が割り当てられたノードである。
【０１０９】
図４Ｃにおいて、ルールＩＤリストは、ノードに割り当てられたルールを表すルールＩＤを含む。すなわち、ルールＩＤリストは、対象データが、当該リーフノード属性情報が含む部分空間にある（すなわち、対象データに関してマッチ条件が成立している）場合に、該対象データに対して適用するアクション（処理）が含まれているルールを表すルールＩＤを含む。たとえば、図１８に例示された探索木において、リーフ１に関するルールＩＤリストは、ルールＲ１、及び、ルールＲ２を含む。また。リーフ４に関するルールＩＤリストは、ルールＲ５、及び、ルールＲ７を含む。
【０１１０】
図４Ｂ、及び、図４Ｃにおいて、中間ノード属性情報、及び、リーフノード属性情報は、異なるデータ構造を有していたが、共通したデータ構造を有していてもよい。この場合に、中間ノード属性情報、及び、リーフノード属性情報は、ともに、図４Ｂ、及び、図４Ｃに例示された項目を含んでいる。以降の説明においては、説明の便宜上、中間ノード属性情報、及び、リーフノード属性情報を、「ノード属性情報」にて総称する。
【０１１１】
次に、図５を参照しながらノードキャッシュ記憶部３０に格納することが可能なノードキャッシュ（キャッシュ情報）に関する情報について説明する。図５は、ノードキャッシュの一例を概念的に表す図である。
【０１１２】
ノードキャッシュ（キャッシュ情報）は、ノード属性情報（図４Ｂ、図４Ｃに例示）のコピーを表すコピー情報と、該コピー情報に含まれているノードを表すノードＩＤと、該コピー情報が作成されたタイミングを表す情報とが関連付けされた情報である。ノードキャッシュ記憶部３０は、１個以上のノードキャッシュ（キャッシュ情報）を記憶することが可能である。言い換えれば、ノードキャッシュは、探索木記憶部２０に格納されているノード属性情報（図４Ｂ、図４Ｃに例示）のコピーであるコピー情報を含む。
【０１１３】
以降においては、説明の便宜上、タイミングを表す情報を、単に、「タイミング」と表す。
【０１１４】
次に、図２を参照しながら、探索木制御部（処理選択部）１０が有する構成の一例について説明する。図２は、第１の実施形態に係る探索木制御部１０が有する構成の一例を示すブロック図である。
【０１１５】
探索木制御部１０は、探索木初期化部１１と、ルール更新部１２と、探索木探索部１３とを有する。
【０１１６】
探索木初期化部１１は、初期状態にて適用されるルールセット（初期ルールセット）に基づき、探索木記憶部２０（図１）に格納されている探索木に関する情報、及び、ルール記憶部４０（図１）に格納されているルールに関する情報を初期化する。初期ルールセットは、記憶装置（不図示）にあらかじめ記憶されていてもよいし、他の制御装置（不図示）から受信してもよい。
【０１１７】
ルール更新部１２は、たとえば、制御部７０から入力した要求信号に基づき、探索木記憶部２０（図１）に格納されている探索木に関する探索木情報（図４Ａに例示）、及び、ルール記憶部４０（図１）に格納されるルールに関する情報（エントリ）を更新する。したがって、ルール更新部１２は、情報エントリを更新する。ルール更新部１２は、操作種別を表す種別情報（追加、変更、または、削除のいずれか）、及び、ルールを制御部７０から入力した要求信号として受信する。ルール更新部１２は、制御部７０から入力した要求信号における種別情報がルール更新（ルール変更）である場合に、該当するルールの優先度、及び、アクションを変更する変更要求を出力することは可能である。しかし、ルール更新部１２は、マッチ条件（判定条件）を変更することができない。
【０１１８】
探索木探索部１３は、たとえば、パケット処理部５０（図１）から、受信したパケットに適用する処理を特定する要求信号を受信するのに応じて、該要求信号にて指定された該パケットに関する探索キー（たとえば、５つのタプル）に適合しているマッチ条件を特定する。探索木探索部１３は、該パケットに関する情報に適合しているマッチ条件を含むルールのうち、最も優先度が高いルールを表すルールＩＤをパケット処理部５０に送信する。探索木探索部１３は、受信したパケットに適用する処理を探索する処理にて、参照する対象であるノードに関するノードキャッシュがノードキャッシュ記憶部３０に格納されている場合に、ノードキャッシュ記憶部３０から当該ノードキャッシュを読み取る。探索木探索部１３は、読み取った当該ノードキャッシュ（図５に例示）に基づき、パケットに適用する処理を探索する探索処理を実行する。
【０１１９】
探索木探索部１３は、参照する対象であるノードに関するノードキャッシュがノードキャッシュ記憶部３０に格納されていない場合に、探索木記憶部２０に格納されているノード属性情報（図４Ｂ、図４Ｃに例示）を参照する。探索木探索部１３は、探索木記憶部２０に格納されているノード属性情報（図４Ｂ、図４Ｃに例示）を参照した場合に、当該ノード属性情報のコピーを含むノードキャッシュ（図５に例示）を作成し、作成したノードキャッシュをノードキャッシュ記憶部３０に格納する。
【０１２０】
さらに、探索木探索部１３は、ルールを探索する処理において、到達したノードに関する参照先がノードキャッシュであった各探索木について以下の処理を実行する。
【０１２１】
到達したノード群における更新タイミングのうち最大の値（以降、「最新更新タイミング」と表す）と、当該ノードキャッシュにおけるキャッシュ作成タイミングとを比較する、
最新更新タイミングが当該キャッシュ作成タイミングより大きい（新しい）場合に、当該探索木に関して再探索を実行する。この場合において、ノードキャッシュ記憶部３０に格納されているノードキャッシュを参照することなく、探索木記憶部２０に格納されているノード属性情報を参照する。
【０１２２】
［各処理に関する説明］
次に、情報処理装置１において実行される処理Ａ乃至処理Ｄについて、それぞれ、説明する。
【０１２３】
処理Ａ：探索木を初期化する処理、
処理Ｂ：ルールを更新する処理、
処理Ｃ：ルールを探索する処理、
処理Ｄ：パケットにアクションを適用する処理。
【０１２４】
（探索木を初期化する処理（処理Ａ）について）
図６乃至図８を参照しながら、探索木を初期化する処理の例について説明する。
【０１２５】
図６は、探索木初期化部１１が、探索木記憶部２０に格納されている探索木に関する情報、及び、ルール記憶部４０に格納されているルールセットを初期化する場合における処理の流れを示すフローチャートである。
【０１２６】
情報処理装置１は、図６に例示された処理を、自装置が起動するのに応じて開始してもよいし、制御部７０から初期化要求を入力するのに応じて開始してもよい。
【０１２７】
探索木初期化部１１は、初期状態にて適用されるルールセット（すなわち、ルートノードに割り当てられたルールセット、以降、「初期ルールセット」と表す）を入力する（ステップＳ１０１）。探索木初期化部１１は、入力した初期ルールセットを、所定の分割手順に従いサブルールセットに分割し（ステップＳ１０２）、作成されたサブルールセットをルール記憶部４０に格納する（ステップＳ１０３）。
【０１２８】
該所定の分割手順においては、まず、ルールにおけるマッチ条件にて参照される各フィールドについて、該当するフィールドにおけるマッチ条件の大小を判定する閾値が設定される。たとえば、プロトコル番号に関するフィールド（０から２５５までの値）について、閾値として０．５を設定し、あるルールに関する「（終了プロトコル番号）−（開始プロトコル番号）」が、１２７（＝（２５５×０．５）の小数点以下を切り捨て）以上であれば、当該ルールは、プロトコル番号について大きいと判定し、１２７未満であれば、当該ルールは、プロトコル番号について小さいと判定する。
【０１２９】
また、該所定の分割手順においては、次に、各ルールにおける各フィールド（５タプル（５Ｔｕｐｌｅ））について、それぞれ、上述した閾値と同様の閾値に基づき大小判定処理を実行し、その後、各フィールドに関して、大小判定処理の結果が同一であるルール群を、一つのサブルールセットとして設定する。たとえば、あて先ＩＰアドレス、及び、あて先ポート番号に関するマッチ条件のみが大きく、残りの３つのフィールドに関する値が小さいと判定されたルール群が一つのサブルールセットを構成する。ただし、小さいフィールドの数が４以上のルール群については、まとめて、一つのサブルールセットとして設定する。
【０１３０】
プロトコル番号の場合に、フィールドに関する値は、たとえば、「（終了プロトコル番号）−（開始プロトコル番号）」に従い算出される。また、あて先ＩＰアドレスの場合に、フィールドに関する値は、たとえば、「（終了あて先ＩＰアドレス）−（開始あて先ＩＰアドレス）」に従い算出される。
【０１３１】
所定の分割手順は、たとえば、非特許文献１に記載された分割手順であってもよい。
【０１３２】
たとえば、ルールにおけるマッチ条件が５つのフィールド（５つのタプル、５―Ｔｕｐｌｅ）における値に基づく判定条件である場合に、探索木初期化部１１は、所定の分割手順に従い、該大小判定処理の結果が同一であるルール群を、１つのサブルールセット（図１６Ａ乃至図１６Ｅに例示）として設定する。図１６Ａ乃至図１６Ｅは、所定の分割手順に従い設定されたサブルールセットを概念的に表す図である。説明の便宜上、図１６Ａ乃至図１６Ｅにおいては、フィールドに関する値が閾値以上である条件に、該フィールドに丸印を付している。
【０１３３】
図１６Ａ乃至図１６Ｅにおいては、サブルールセットは、送信元ＩＰアドレス、あて先ＩＰアドレス、プロトコル番号、送信元ポート番号、及び、あて先ポート番号なる５つのフィールド（５つのタプル）に関する大小判定処理によって設定されたサブルールセットとして設定する。
【０１３４】
図１６Ａを参照すると、サブルールセットＡは、５つのタプルに関する値がいずれも大きな値であるサブルールセット（Ａ−１）を含んでいる。たとえば、図１６Ａに例示されたサブルールセット（Ａ−１）においては、送信元ＩＰアドレス（丸印付き）、あて先ＩＰアドレス（丸印付き）、プロトコル番号（丸印付き）、送信元ポート番号（丸印付き）、及び、あて先ポート番号（丸印付き）が関連付けされている。これは、上記の５つのフィールドに関する値が、それぞれ、閾値以上であるというサブルールセットを表す。
【０１３５】
図１６Ｂを参照すると、サブルールセットＢは、５つのフィールドに関する値のいずれか１つが小さな値であるという、５個のサブルールセットを表す。すなわち、サブルールセットＢは、サブルールセット（Ｂ−１）、サブルールセット（Ｂ−２）、サブルールセット（Ｂ−３）、サブルールセット（Ｂ−４）、及び、サブルールセット（Ｂ−５）を含む。たとえば、サブルールセット（Ｂ−１）は、フィールド「送信元ＩＰアドレス」に関する値が小さく、他の４つのフィールドに関する値がいずれも大きいというサブルールセットを表す。
【０１３６】
たとえば、図１６Ｂに例示されたサブルールセット（Ｂ−２）においては、送信元ＩＰアドレス（丸印付き）、あて先ＩＰアドレス、プロトコル番号（丸印付き）、送信元ポート番号（丸印付き）、及び、あて先ポート番号（丸印付き）が関連付けされている。これは、フィールド「あて先ＩＰアドレス」に関する値が小さく、該５つのフィールドのうち、他の４つのフィールドに関する値が、それぞれ、閾値以上であるというサブルールセットを表す。
【０１３７】
図１６Ｃを参照すると、サブルールセットＣは、５つのフィールドに関する値のいずれか２つが小さな値であるという、１０個のサブルールセットを表す。すなわち、サブルールセットＣは、サブルールセット（Ｃ−１）、乃至、サブルールセット（Ｃ−１０）を含む。たとえば、サブルールセット（Ｃ−１）は、フィールド「送信元ＩＰアドレス」に関する値、及び、フィールド「あて先ＩＰアドレス」に関する値が小さく、他の３つのフィールドに関する値がいずれも大きいというサブルールセットを表す。
【０１３８】
たとえば、図１６Ｃに例示されたサブルールセット（Ｃ−５）においては、送信元ＩＰアドレス（丸印付き）、あて先ＩＰアドレス、プロトコル番号、送信元ポート番号（丸印付き）、及び、あて先ポート番号（丸印付き）が関連付けされている。これは、フィールド「あて先ＩＰアドレス」、及び、フィールド「プロトコル番号」に関する値が閾値未満であり、該５つのフィールドのうち、他の３つのフィールドに関する値が、それぞれ、閾値以上であるというサブルールセットを表す。
【０１３９】
図１６Ｄを参照すると、サブルールセットＤは、５つのフィールドに関する値のいずれか３つが小さな値であるという、１０個のサブルールセットを表す。すなわち、サブルールセットＤは、サブルールセット（Ｄ−１）、乃至、サブルールセット（Ｄ−１０）を含む。たとえば、サブルールセット（Ｄ−１）は、フィールド「送信元ＩＰアドレス」に関する値、フィールド「あて先ＩＰアドレス」に関する値、及び、フィールド「プロトコル番号」に関する値が小さく、他の２つのフィールドに関する値がいずれも大きいというサブルールセットを表す。
【０１４０】
たとえば、図１６Ｄに例示されたサブルールセット（Ｄ−６）においては、送信元ＩＰアドレス、あて先ＩＰアドレス（丸印付き）、プロトコル番号（丸印付き）、送信元ポート番号、及び、あて先ポート番号が関連付けされている。これは、フィールド「あて先ＩＰアドレス」、及び、フィールド「プロトコル番号」に関する値が閾値以上であり、該５つのフィールドのうち、他の３つのフィールドに関する値が、それぞれ、閾値未満であるというサブルールセットを表す。
【０１４１】
図１６Ｅを参照すると、サブルールセットＥは、次の第１サブルールセット、または、第２サブルールセットに大別される、６個のサブルールセットを表す。すなわち、
第１サブルールセット：５つのフィールドに関する値のいずれか４つが小さな値であるサブルールセット（サブルールセット（Ｅ−１）、乃至、サブルールセット（Ｅ−５））、
第２サブルールセット：５つのフィールドに関する値のいずれもが小さな値であるサブルールセット（サブルールセット（Ｅ−６））。
【０１４２】
すなわち、サブルールセットＥは、サブルールセット（Ｅ−１）、乃至、サブルールセット（Ｅ−６）を含む。たとえば、サブルールセット（Ｅ−１）は、フィールド「送信元ＩＰアドレス」に関する値が大きく、他の４つのフィールドに関する値がいずれも小さいというサブルールセットを表す。すなわち、サブルールセットＥは、５つのフィールドに関する値のうち、いずれか４つ以上が小さな値であるという６個のサブルールセットを含む。
【０１４３】
たとえば、図１６Ｅに例示されたサブルールセット（Ｅ−４）においては、送信元ＩＰアドレス、あて先ＩＰアドレス、プロトコル番号、送信元ポート番号（丸印付き）、及び、あて先ポート番号が関連付けされている。これは、フィールド「送信元ポート番号」に関する値が閾値以上であり、該５つのフィールドのうち、他の４つのフィールドに関する値が、それぞれ、閾値未満であるというサブルールセットを表す。
【０１４４】
図６に示されたステップＳ１０３の後に、探索木初期化部１１は、作成したサブルールセットごとに探索木を作成する（ステップＳ１０４）。このとき、たとえば、探索木初期化部１１は、図１６Ａ乃至図１６Ｅにて示された以下の２７個のサブルールセットごとに探索木を作成する。
【０１４５】
・サブルールセット（Ａ−１）、
・サブルールセット（Ｂ−１）乃至サブルールセット（Ｂ−５）、
・サブルールセット（Ｃ−１）乃至サブルールセット（Ｃ−１０）、
・サブルールセット（Ｄ−１）乃至サブルールセット（Ｄ−１０）、
・サブルールセットＥ。
【０１４６】
ステップＳ１０４に示された処理の詳細については、図７、及び、図８を参照しながら後述する。
【０１４７】
次に、図７を参照しながら、探索木初期化部１１がサブルールセットごとに探索木を作成する処理（図６におけるステップＳ１０４）の一例について説明する。図７は、探索木初期化部１１が探索木を作成する処理の流れの一例を示すフローチャートである。
【０１４８】
探索木初期化部１１は、作成する探索木におけるルートノードを作成する（割り当てる）（ステップＳ１１１）。より具体的に、探索木初期化部１１は、探索木記憶部２０にルートノードに関するノード属性情報（図４Ｂに例示）を記憶することが可能な記憶領域を確保し、確保した記憶領域に各項目に関する値を格納する。すなわち、
リーフ情報：オフ（すなわち、中間ノードであることを表す情報）、
親ノードＩＤ：無効値（すなわち、親ノードが存在していないルートノードであることを表す）、
部分空間：探索空間に関する情報（以下の、あて先ＩＰアドレス、送信元ＩＰアドレス、プロトコル番号、あて先ポート番号、及び、送信元ポート番号）、
あて先ＩＰアドレス：０．０．０．０から２５５．２５５．２５５．２５５までの値、
送信元ＩＰアドレス：０．０．０．０から２５５．２５５．２５５．２５５までの値、
プロトコル番号：０から２５５までの値、
あて先ポート番号：０から６５５３５までの値、
送信元ポート番号：０から６５５３５までの値、
更新タイミング：ノード属性情報に関して上述した値が格納されたタイミング。
【０１４９】
探索木初期化部１１は、作成したルートノードについて、後述する探索木作成サブ処理Ａ（図８を参照しながら後述する）を実行する（ステップＳ１１２）。その場合に、探索木初期化部１１は、当該ルートノードと、処理対象であるサブルールセットとを参照する。
【０１５０】
図８のフローチャートを参照しながら、探索木作成サブ処理Ａ（図７におけるステップＳ１１２）に示された処理について説明する。図８は、探索木作成サブ処理Ａにおける処理の流れの一例を示すフローチャートである。探索木作成サブ処理Ａは、処理対象であるノード（たとえば、ノードＩＤの形式、以降「処理対象であるノード」と表す）と、当該ノードに配置されたルール（たとえば、ルールＩＤのリストの形式、以降「処理対象であるルールセット」と表す）とを入力する。
【０１５１】
探索木初期化部１１は、処理対象であるノードに割り当てられたルールの個数が所定の個数（Ｂｉｎｔｈ）以下であるか否かを判定する（ステップＳ１２１）。処理対象であるノードに割り当てられたルールの個数が所定の個数（Ｂｉｎｔｈ）以下でない場合（ステップＳ１２１にてＮＯ）に、探索木初期化部１１は、所定の分割手順に従い、当該ノードが表す部分空間をカットする次元と、分割数（カット数）とを算出する（ステップＳ１２２）。この場合に、探索木初期化部１１は、当該ノードに関して算出したカットする次元と、算出したカット数とに基づき、当該ノードを分割（カット）する。所定の分割手順は、たとえば、非特許文献１、及び、非特許文献１にて参照されている文献に記載された分割方法に従い実現してもよい。
【０１５２】
非特許文献１、及び、非特許文献１において参照されている文献に記載の分割方法においては、処理対象ルールセットの各ルールのマッチ条件について、処理対象ノードの部分空間との共通部分に限定する。たとえば、あるルールにおけるプロトコル番号が１０から２０までの値であり、処理対象ノードの部分空間におけるプロトコル番号が１５から２５までの値であった場合、当該ルールのマッチ条件におけるプロトコル番号は、１５から２０までの値に設定する。
【０１５３】
さらに、当該分割方法においては、各次元（フィールド）について、ユニークな範囲の数を計算する。たとえば、ルールが３つあり、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１６〜２０、１７〜１７であった場合、ユニークな範囲の数は３となる。また、各ルールのマッチ条件のプロトコル番号が、それぞれ、１５〜２０、１５〜２０、１７〜１７であった場合には、ユニークな範囲の数は２となる（この例では、第１番目と第２番目とは同一のプロトコル番号であるため）。そして、当該分割方法においては、全次元についてのユニークな範囲の数の平均より大きいユニークな範囲の数を有する次元を、カット（Ｃｕｔ）する次元として選択する。
【０１５４】
また、当該分割方法においては、カット（Ｃｕｔ）する数の上限値が、メモリ使用量を調整するためのパラメータであるｓｐｆａｃ（Ｓｐｅｃｉａｌ＿Ｆａｃｔｏｒ）と処理対象ルールセットの大きさ（ルール数）とに基づき決定される。たとえば、当該分割方法においては、当該ルール数の平方根とパラメータｓｐｆａｃとの積をカット（Ｃｕｔ）する数の上限値として設定される。そして、当該分割方法においては、カット（Ｃｕｔ）する数が２に設定された場合に、各子ノードに含まれるルールの数の平均値および最大値を求める。
【０１５５】
さらに、当該分割方法においては、カット（Ｃｕｔ）する数を増やし、そのときの各子ノードに含まれるルールの数の平均値および最大値を求める。そして、当該分割方法においては、カット（Ｃｕｔ）する値が上限値に達するか、もしくは、カット（Ｃｕｔ）する数を増やしても、各子ノードに含まれるルールの数の平均値および最大値に大きな変化が現れなくなった場合におけるカット（Ｃｕｔ）する数を、処理対象ノードをカット（Ｃｕｔ）する数として決定して使用する。
【０１５６】
探索木初期化部１１は、ステップＳ１２２（図８）において算出した次元、及び、分割数に基づき、処理対象であるノードが表す部分空間をカットした場合に算出される各部分空間に対して、子ノードを割り当てる（ステップＳ１２３）。具体的に、探索木初期化部１１は、探索木記憶部２０において、各子ノードに関するノード属性情報（図４Ｂに例示）を記憶することが可能な記憶領域を確保し、確保した記憶領域に各項目に関する値を格納する。すなわち、
リーフ情報：オフ（すなわち、中間ノードであることを表す）、
親ノードＩＤ：処理対象であるノードを表すＩＤ、
部分空間情報：分割方法に従い算出された、当該子ノードが表す部分空間、
更新タイミング：中間ノード属性情報に関して上述した値が格納されたタイミング。
【０１５７】
探索木初期化部１１は、カットした結果、得られた部分空間に含まれるルールの個数が「０」の場合には、当該部分空間を表す子ノードは割り当てなくてもよい。
【０１５８】
探索木初期化部１１は、ステップＳ１２３にて割り当てた各子ノードについて、当該探索木作成サブ処理Ａを実行する（ステップＳ１２４）。すなわち、探索木初期化部１１は、各子ノードに関して当該探索木作成サブ処理Ａを再帰的に繰り返しながら実行する。各子ノードに対しても図８に示された処理が実行されることによって、探索木は作成される。探索木初期化部１１は、処理対象である子ノードと、当該子ノードに含まれるルールの集合とを入力する。当該子ノードに含まれるルールの集合は、当該子ノードの部分空間と重複する判定条件を持つルールで構成される。
【０１５９】
ステップＳ１２１にてルールの個数が所定の個数（Ｂｉｎｔｈ）以下である場合に、探索木初期化部１１は、探索木記憶部２０において、処理対象であるノードに関するノード属性情報（図４Ｃに例示）を記憶することが可能な記憶領域を確保する（ステップＳ１２５）。探索木初期化部１１は、確保した記憶領域に各項目に関する値を格納する（ステップＳ１２６）。すなわち、
リーフ情報：オン（すなわち、リーフノードであることを表す）、
ルールＩＤリスト：当該子ノードに含まれるルールを表すＩＤのリスト。
【０１６０】
（ルールを更新する処理（処理Ｂ）について）
次に、図９乃至図１２に示されたフローチャートを参照しながら、ルールを更新する処理の例について説明する。図９は、ルールを更新する処理における処理の流れの一例を示すフローチャートである。
【０１６１】
ルール更新部１２は、たとえば、制御部７０から、ルール更新処理に関する処理の種別（追加、変更、削除等）を表す種別情報、及び、追加、変更、削除等が適用されるルールを表すルールＩＤと、変更内容（追加の場合ルールすべての情報、変更の場合変更箇所の情報）とを入力する（ステップＳ１３１）。
【０１６２】
ルール更新部１２は、所定の選択手順に従い、入力したルールが含まれているサブルールセットを選択する（ステップＳ１３２）。所定の選択手順は、図６におけるステップＳ１０１によって用いられた所定の分割手順と同様の方法であり、たとえば、入力したルール内のマッチ条件に含まれる各フィールドに関する条件に従い、図１６Ａ乃至図１６Ｅに例示されたサブルールセットのうち、いずれに関連しているのかに基づき選択される。
【０１６３】
次に、ルール更新部１２は、入力した種別情報が削除を要求する信号であるか否かを判定する（ステップＳ１３３）。入力した種別情報が削除を要求する信号である場合に（ステップＳ１３３にてＹＥＳ）、ルール更新部１２は、ルール記憶部４０に格納されている処理対象ルールに関連付けされた削除情報に「オン」（すなわち、削除することを表す）を格納する（ステップＳ１３５）。これに対して、入力した種別情報が削除を要求する信号でない場合に（ステップＳ１３３にてＮＯ）、ルール更新部１２は、ステップＳ１３２にて選択したサブルールセットを、入力した種別情報に応じて更新する（ステップＳ１３４）。入力した種別情報が追加を要求する信号である場合に、ルール更新部１２は、選択したサブルールセットに、該処理対象ルールを格納する。また、入力した種別情報が変更を要求する信号である場合に、ルール更新部１２は、選択したサブルールセットにおける処理対象ルールに関する優先度、及び、処理対象ルールに関するアクションを変更する。
【０１６４】
ルール更新部１２は、入力した種別情報が追加を要求する信号であるかを判定する（ステップＳ１３６）。入力した種別情報が追加を要求する信号である場合に（ステップＳ１３６にてＹＥＳ）、ルール更新部１２は、選択したサブルールセットに関する探索木（すなわち、処理対象である探索木）に含まれているルートノードについて、ルール更新サブ処理Ａ（図１０を参照しながら後述する）を実行する（ステップＳ１３７）。入力した種別情報が追加を要求する信号でない場合に（ステップＳ１３６にてＮＯ）、ルール更新部１２は、処理対象である探索木におけるルートノードについて、ルール更新サブ処理Ｂ（図１１を参照しながら後述する）を実行する（ステップＳ１３８）。
【０１６５】
図１０を参照しながら、ルール更新サブ処理Ａ（図９におけるステップＳ１３７）について説明する。図１０は、ルール更新サブ処理Ａにおける処理の流れを示すフローチャートである。
【０１６６】
ルール更新部１２は、ルール更新サブ処理Ａにて、処理対象であるノードを表すノードＩＤ、及び、当該ノードに追加するルール（処理対象であるルール）を入力する。
【０１６７】
ルール更新部１２は、ノードＩＤが表すノードがリーフノードであるか否かを判定する（ステップＳ１４１）。ルール更新部１２は、処理対象であるノードがリーフノードであるか否かを判定する判定処理を、たとえば、ノードＩＤが表すノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）におけるリーフ情報が「オン」であるか否かに基づき実行する。処理対象であるノードがリーフノードでない場合に（ステップＳ１４１にてＮＯ）、ルール更新部１２は、ノード属性情報（図４Ｂに例示）に含まれている子ノードＩＤリストのうち、入力したルールに適合している子ノードを表すノードＩＤを選択する（ステップＳ１４２）。ルール更新部１２は、たとえば、当該子ノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）における部分空間と、入力したルールに含まれているマッチ条件が表す部分空間とに重なり（共通部分）があるか否かに応じて、子ノードが入力したルールに適合しているか否かを判定する。
【０１６８】
ルール更新部１２は、ステップＳ１４２にて選択した各子ノードについて、ルール更新サブ処理Ｃ（図１１を参照しながら後述する）を実行する（ステップＳ１４３）。
【０１６９】
ルール更新部１２は、ステップＳ１４３において、少なくとも１回実行されたルール更新サブ処理Ｃのいずれかにおいて、新規に割り当てられた（すなわち、図１１におけるステップＳ１５３にて記憶領域を確保された）子ノードがあるか否かを判定する（ステップＳ１４４）。新規に割り当てられた子ノードがない場合に（ステップＳ１４４にてＮＯ）、ルール更新部１２は、ルール更新サブ処理Ａを終了する。これに対して、新規に割り当てられた子ノードがある場合には（ステップＳ１４４にてＹＥＳ）、ルール更新部１２は、処理対象であるノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）における更新タイミングを更新する（ステップＳ１４５）。ルール更新部１２は、たとえば、処理対象であるノードに関する更新タイミングの値を、該処理を開始した（または、ステップＳ１４４等のステップを処理した）タイミングに変更する。
【０１７０】
また、処理対象であるノードがリーフノードである場合に（ステップＳ１４１にてＹＥＳ）、ルール更新部１２は、ノード（この場合、リーフノード）に関するリーフノード属性情報（図４Ｃに例示）内のルールＩＤリストに含まれているルールの個数を算出する。ルール更新部１２は、算出した個数と、追加するルールＩＤの個数との合計値を算出し、算出した合計値が所定の個数（Ｂｉｎｔｈ）以下であるか否かを判定する（ステップＳ１４６）。ルールの個数が該所定の個数（Ｂｉｎｔｈ）以下である場合に（ステップＳ１４６にてＹＥＳ）、ルール更新部１２は、処理対象であるノード（リーフノード）に関するノード属性情報（図４Ｃに例示）内のルールＩＤリストに、処理対象であるルールを表すルールＩＤを追加する（ステップＳ１４７）。その後、ルール更新部１２は、処理対象であるノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）における更新タイミングを更新する（ステップＳ１４５）。
【０１７１】
これに対して、ルールの個数が該所定の個数（Ｂｉｎｔｈ）以下でない場合に（ステップＳ１４６にてＮＯ）、ルール更新部１２は、処理対象であるノード（リーフノード）を中間ノードとして設定し（ステップＳ１４８）、新たに、設定した中間ノードに関する子ノードを作成する（ステップＳ１４９）。具体的に、ルール更新部１２は、処理対象であるノードに関するリーフノード属性情報（図４Ｃに例示）におけるリーフ情報にオフを設定する。この処理によって、ルール更新部１２は、該ノード属性情報を、中間ノード属性情報（図４Ｂに例示）として処理することができる。さらに、ルール更新部１２は、ステップＳ１４６にてルールＩＤリストから読み取った各ルールＩＤが表すルールと、追加するルールＩＤが表すルールとに基づき、探索木作成サブ処理Ａ（図８）を実行することによって、設定した中間ノードに関する子ノードを作成する。その後、ルール更新部１２は、処理対象であるノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）における更新タイミングを更新する（ステップＳ１４５）。
【０１７２】
次に、図１１のフローチャートを参照しながら、ルール更新サブ処理Ｃ（図１０におけるステップＳ１４３）の詳細な動作について説明する。図１１は、ルール更新サブ処理Ｃ（図１０におけるステップＳ１４３）における処理の流れの一例を示すフローチャートである。
【０１７３】
ルール更新部１２は、処理対象であるノードを表すノードＩＤ（処理対象ノード）と、処理対象であるノードの親ノードを表すノードＩＤと、ノードＩＤが表すノードに関する部分空間と、当該ノードに追加されるルール（処理対象ルール）を表すルールＩＤとを入力する。
【０１７４】
ルール更新部１２は、ノードＩＤが表すノードに関するノード属性情報を格納する記憶領域が確保されているか否かを判定する（ステップＳ１５１）。探索木記憶部２０に記憶領域が確保されていた場合に（ステップＳ１５１にてＹＥＳ）、ルール更新部１２は、入力したノードＩＤが表すノード、及び、入力したルールに基づき、ルール更新サブ処理Ａ（図１０）を実行する（ステップＳ１５２）。これに対して、探索木記憶部２０に記憶領域が確保されていない場合には（ステップＳ１５１にてＮＯ）、ルール更新部１２は、処理対象であるノードを格納する探索木記憶部２０においてノード属性情報を格納する記憶領域を確保し（ステップＳ１５３）、確保した記憶領域にリーフノードであることを表す値を格納する（ステップＳ１５４）。具体的に、ルール更新部１２は、ノードＩＤが表すノードに関するリーフノード属性情報（図４Ｃに例示）を記憶することが可能な記憶領域を探索木記憶部２０に確保し、確保した記憶領域に当該リーフノード属性情報に関する以下の各項目を設定する。
【０１７５】
リーフ情報：オン（すなわち、リーフノードであることを表す）、
親ノードＩＤ：親ノードを表すノードＩＤ、
部分空間：ノードＩＤが表すノードに関する部分空間、
更新タイミング：ステップＳ１５４を実行したタイミング、
ルールＩＤリスト：入力したルールＩＤ。
【０１７６】
次に、図１２を参照しながら、ルール更新サブ処理Ｂ（図９におけるステップＳ１３８）について説明する。図１２は、ルール更新サブ処理Ｂにおける処理の流れの一例を示すフローチャートである。
【０１７７】
ルール更新部１２は、ノードＩＤ（すなわち、処理対象であるノードを表す）と、処理に関する種別を表す種別情報（この場合に、削除、または、更新）と、処理する対象を表すルールを入力する。
【０１７８】
ルール更新部１２は、入力したノードＩＤが表すノードがリーフノードであるか否かを判定する（ステップＳ１６１）。ルール更新部１２は、たとえば、ノードＩＤが表すノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）におけるリーフ情報の値に応じて受信したノードＩＤが表すリーフがリーフノードであるか否かを判定する。入力したノードＩＤが表すノードがリーフノードでない場合に（ステップＳ１６１にてＮＯ）、ルール更新部１２は、該ノードＩＤが表すノードに関するノード属性情報（図４Ｂに例示）内の子ノードＩＤリストのうち、入力したルールを含む子ノードを表す子ノードＩＤを選択する（ステップＳ１６２）。たとえば、ルール更新部１２は、子ノードＩＤが表すノードに格納されているノード属性情報（図４Ｂ、図４Ｃに例示）に含まれている部分空間と、入力されたルールにおけるマッチ条件を満たしている値が成す部分空間とに重なり（共通部分）があるか否かに応じて、ある子ノードが入力したルールを含んでいるか否かを判定する。
【０１７９】
ルール更新部１２は、ステップＳ１６２にて選択した各子ノードＩＤが表すノードに関して、ルール更新サブ処理Ｂを実行する（ステップＳ１６３）。この場合に、ルール更新部１２は、各子ノードＩＤが表す子ノードに関して、ルール更新サブ処理Ｂを再帰的に繰り返しながら実行する。
【０１８０】
入力したノードＩＤが表すノードがリーフノードである場合に（ステップＳ１６１にてＹＥＳ）、ルール更新部１２は、入力した種別情報が削除であるか否かを判定する（ステップＳ１６４）。入力した種別情報が削除である場合に（ステップＳ１６４にてＹＥＳ）、ルール更新部１２は、入力したノードＩＤが表すノード（この場合、リーフノード）に関するノード属性情報（図４Ｃ）内のルールＩＤリストを更新する（ステップＳ１６５）。具体的に、ルール更新部１２は、入力した種別情報が削除である場合に、当該ルールＩＤリストから、処理対象であるルールを表すルールＩＤを削除する。入力した種別情報が更新である場合に（ステップＳ１６４にてＮＯ）、ルール更新部１２は、ステップＳ１６５を実行しない。
【０１８１】
ルール更新部１２は、入力したノードＩＤが表すノード（リーフノード）に関するリーフノード属性情報（図４Ｃ）内の更新タイミングを、ステップＳ１６６に関する処理を開始したタイミングに設定する（ステップＳ１６６）。
【０１８２】
ルール更新部１２は、図９乃至図１２のいずれかに示されたルール更新処理を実行するとともに、削除情報がオンである（すなわち、削除するよう要求された）ルールを削除する処理を、たとえば、定期的に実行する。ルール更新部１２は、ルール記憶部４０に格納されているルールのうち、削除情報がオンであり、かつ、いずれのノードにおいても参照されていないルールについて、ルール記憶部４０から削除する。
【０１８３】
（ルールを探索する処理（処理Ｃ）について）
図１３、及び、図１４に示されたフローチャートを参照しながら、パケットに適合しているルールを探索する処理（すなわち、パケットに適用する処理を探索する処理）について説明する。図１３は、パケットに適合しているルールを探索する処理の流れの一例を示すフローチャートである。
【０１８４】
探索木探索部１３は、探索木記憶部２０に格納されている探索木、ノードキャッシュ記憶部３０に格納されているノードキャッシュ、及び、ルール記憶部４０に格納されているルールセットを参照しながら処理Ｃを実行する。処理Ｃについて詳細に説明する。
【０１８５】
探索木探索部１３は、たとえば、パケット処理部５０から受信したパケットに適用するアクション（処理）を探索する要求を受信するのに応じて処理を開始する。探索木探索部１３は、パケットに適用する処理を探索するに要する探索キー（たとえば、５つのタプルに関する値）を入力する（ステップＳ１８１）。
【０１８６】
探索木探索部１３は、入力した探索キーに基づき、各探索木についてルール探索サブ処理Ａ（図１４を参照しながら後述する）を実行する（ステップＳ１８２）。
【０１８７】
探索木探索部１３は、ステップＳ１８２に従い算出されたノード（すなわち、探索キーに適合しているマッチ条件を含むルールが割り当てられたノード）に関するノード属性情報（図４Ｂ、図４Ｃに例示）のうち、該ノード属性情報における更新タイミングが最大である更新タイミングを算出する（ステップＳ１８３）。すなわち、探索木探索部１３は、該更新タイミングのうち、タイミングが最も新しいタイミングを算出する。具体的に、探索木探索部１３は、入力した探索キーに適合しているルールを各探索木に従い探索した結果、適合していると判定されたマッチ条件が割り当てられているノード（すなわち、到達したノード）に関するノード属性情報（図４Ｂ、図４Ｃに例示）における更新タイミングが最も新しいノードを選択する。探索木探索部１３は、選択したノードに関するノード属性情報における更新タイミングを、最新更新タイミングとして算出する。
【０１８８】
探索木探索部１３は、到達したノードを参照した場合に、探索木記憶部２０に格納されているノードではなく、ノードキャッシュに格納されているノードを読み取り、当該ノードキャッシュに関するキャッシュ作成タイミングが、算出した最新更新タイミング以前の各探索木について、ルール探索サブ処理Ａ（図１４）を実行する（ステップＳ１８４）。なお、到達したノードすべてについて、探索木記憶部２０に格納されているノードではなく、ノードキャッシュに格納されているノードを読み取り使用した場合、ステップＳ１８４を省略することとしてもよい。これは、当該条件が満たされる場合、探索木記憶部２０に格納されているノードへの変更が本探索処理に影響を及ぼさないからである。
【０１８９】
図１４を参照しながら後述するように、探索木探索部１３は、ルール探索サブ処理Ａを実行する場合に、ノードキャッシュ記憶部３０に格納されているノードキャッシュを読み取るのではなく、探索木記憶部２０に格納されているノードを読み取る（すなわち、図１４におけるステップＳ１９２にてＮＯと判定される）。
【０１９０】
言い換えれば、探索木探索部１３は、到達したノードに関するキャッシュ作成タイミングが最新更新タイミング以前であるノードを含む探索木に関して、該探索木に含まれているノードに関するノード属性情報を、探索木記憶部２０から読み取る。
【０１９１】
探索木探索部１３は、ステップＳ１８１、及び、ステップＳ１８３にて、各探索木に従い算出されたルールＩＤのうち、該ルールＩＤに関連付けされた優先度（図３に例示）が最も高いルールＩＤを選択する（ステップＳ１８５）。探索木探索部１３は、入力した探索キーに適合しているルールとして、選択したルールＩＤを出力する。
【０１９２】
言い換えれば、探索木制御部１０は、対象データに関して成立している判定条件（マッチ条件）のうち、該判定条件に関連付けされた優先度が最も高い判定条件に関連付けされたアクション（処理）を選択する処理選択部であってもよい。
【０１９３】
次に、図１４のフローチャートを参照しながら、ルール探索サブ処理Ａ（図１３におけるステップＳ１８２、ステップＳ１８４）について説明する。図１４は、ルール探索サブ処理Ａにおける処理の流れの一例を示すフローチャートである。
【０１９４】
探索木探索部１３は、処理対象である探索木を表す探索木ＩＤ、及び、探索キー（たとえば、５つのタプルに関する値）を入力する。探索木探索部１３は、図１４に示されたルール探索サブ処理Ａを実行することによって、探索処理の結果を表す情報と、探索されたルール、及び、到達したノード（すなわち、探索キーに適合しているマッチ条件を含むルールが割り当てられた最下位のノード）を表すノードＩＤとを出力する。
【０１９５】
探索木探索部１３は、探索する対象ノードとして、入力した探索木ＩＤが表す探索木におけるルートノードを選択する（ステップＳ１９１）。
【０１９６】
探索木探索部１３は、ノードキャッシュ記憶部３０に、対象ノードのコピーを含むノードキャッシュが格納されているか否かを判定する（ステップＳ１９２）。探索木探索部１３は、たとえば、該対象ノードを表すノードＩＤに基づき、ノードキャッシュ記憶部３０に、該対象ノードのコピーであるノードキャッシュが格納されているか否かを判定する。
【０１９７】
対象ノードのコピーであるノードキャッシュがノードキャッシュ記憶部３０に格納されている場合に（ステップＳ１９２にてＹＥＳ）、探索木探索部１３は、ノードキャッシュ記憶部３０から、当該ノードキャッシュ（「対象ノードキャッシュ」と表す）を読み取る（ステップＳ１９３）。探索木探索部１３は、該対象ノードキャッシュに関して有効期限を超過しているか（すなわち、対象ノードキャッシュが有効期限切れであるか）否かを判定する（ステップＳ１９４）。たとえば、探索木探索部１３は、対象ノードキャッシュ（図５に例示）におけるキャッシュ作成タイミングを読み取り、読み取ったキャッシュ作成タイミングに所定の期間（「キャッシュ有効期間」と表す）を加えたタイミングを算出する。探索木探索部１３は、算出したタイミングが、ステップＳ１９４を実行しているタイミングより前である場合に、対象ノードキャッシュ（データ）が有効期限切れであると判定する。キャッシュ有効期間は、たとえば、探索木探索部１３に格納されていてもよい。
【０１９８】
対象ノードキャッシュが有効期限を超過している場合に（ステップＳ１９４にてＹＥＳ）、探索木探索部１３は、探索木記憶部２０から対象ノードを読み取る（ステップＳ１９５）。次に、探索木探索部１３は、読み取った対象ノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）を含むノードキャッシュ（図５に例示）を作成し（ステップＳ１９６）、作成したノードキャッシュを、ノードキャッシュ記憶部３０に格納する（ステップＳ１９７）。ステップＳ１９６にて、探索木探索部１３は、該ノードキャッシュ（図５に例示）におけるキャッシュ作成タイミングとして、該ノードキャッシュに関する処理（たとえば、ステップＳ１９５等）を実行したタイミングを設定する。ステップＳ１９４にてＹＥＳの場合に、探索木探索部１３は、ノードキャッシュ記憶部３０に格納されている対象ノードキャッシュを削除してもよい。
【０１９９】
ステップＳ１９４にてＮＯの場合に、探索木探索部１３は、対象ノードがリーフノードであるか否かを判定する（ステップＳ１９８）。たとえば、探索木探索部１３は、ステップＳ１９８において、対象ノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）内のリーフ情報がオンであるか否かに応じて、対象ノードがリーフノードであるか否かを判定する。
【０２００】
処理対象であるノードがリーフノードでない場合に（ステップＳ１９８にてＮＯ）、探索木探索部１３は、入力した探索キー（たとえば、５つのタプルに関する値）に適合している子ノードを表すノードＩＤを選択する（ステップＳ１９９）。探索木探索部１３は、ステップＳ１９９にて選択した子ノードに関する記憶領域が確保されているか否かを判定する（ステップＳ２００）。記憶領域が確保されている場合に（ステップＳ２００にてＹＥＳ）、探索木探索部１３は、対象ノードとして当該子ノードを設定する（ステップＳ２０１）。その後、探索木探索部１３は、当該子ノードに関してステップＳ１９２以降の処理を開始する。
【０２０１】
これに対して、記憶領域が確保されていない場合に（ステップＳ２００にてＮＯ）、探索木探索部１３は、探索キーに対応するルールが存在していないことを表す「適合しているルールなし」なる出力情報を作成する（ステップＳ２０４）。この場合に、対象ノードが到達したノードを表す。したがって、探索木探索部１３は、対象ノードを表すノードＩＤを出力する。
【０２０２】
対象ノードがリーフノードである場合に（ステップＳ１９８にてＹＥＳ）、探索木探索部１３は、対象ノードに関するリーフノード属性情報（図４Ｃに例示）内のルールＩＤリストからルールＩＤを読み取る（ステップＳ２０２）。探索木探索部１３は、読み取った各ルールＩＤが表すルールに含まれているマッチ条件（図３）のうち、入力した探索キーに適合しているマッチ条件を含むルールであって、かつ、該ルールＩＤに関連付けされた優先度が最も高いルールＩＤを選択する（ステップＳ２０３）。探索木探索部１３は、選択したルールＩＤ、及び、当該対象ノード（この場合、リーフノード）を表すノードＩＤを出力する。
【０２０３】
（パケットにアクションを適用する処理（処理Ｄ）について）
図１５を参照しながら、パケットにアクションを適用する処理について説明する。図１５は、パケットにアクションを適用する処理の流れの一例を示すフローチャートである。
【０２０４】
パケット処理部５０は、たとえば、通信ＩＦ６０から、パケット（処理対象パケット）を受信したことを表す受信通知を入力するのに応じて、パケットにアクションを適用する処理を開始する。
【０２０５】
パケット処理部５０は、受信したパケットに含まれている探索キー（たとえば、５つのタプルに関する値）を読み取る（ステップＳ２１１）。たとえば、パケット処理部５０は、受信したパケットから、送信元ＩＰアドレス、あて先ＩＰアドレス、プロトコル番号、送信元ポート番号、及び、あて先ポート番号の各項目に関する値を探索キーとして読み取る。
【０２０６】
パケット処理部５０は、読み取った探索キーに適合しているルール（すなわち、受信したパケットに適用する処理）を特定することを要求する信号を、探索木探索部１３に対して出力する（ステップＳ２１２）。
【０２０７】
探索木探索部１３は、該信号を受信し、受信した信号に応じて、図１３、及び、図１４に示された処理に従い該探索キーに適合しているルールを特定する。探索木探索部１３は、該探索キーに適合しているルールを特定した場合に、該ルールをパケット処理部５０に対して出力する。探索木探索部１３は、該探索キーに適合しているルールを特定できなかった場合に特定できなかったことを表す信号をパケット処理部５０に対して出力する。
【０２０８】
パケット処理部５０は、探索木探索部１３が出力した結果に基づき、探索キーに適合しているルールがあるか否かを判定する（ステップＳ２１３）。
【０２０９】
パケット処理部５０は、探索キーに適合しているルールがある場合に（ステップＳ２１３にてＹＥＳ）、特定された当該ルールが成り立つ場合に実行されるアクションに従い、受信したパケットを処理する（ステップＳ２１４）。
【０２１０】
パケット処理部５０は、探索キーに適合しているルールがなかった場合（ステップＳ２１３にてＮＯ）、適合しているルールが不明である場合に実行される処理を表す不明処理（以下に例示された、不明処理Ａ、乃至、不明処理Ｄのいずれか）を実行する（ステップＳ２１５）。すなわち、
不明処理Ａ：受信したパケットを破棄する、
不明処理Ｂ：受信したパケットに適用する処理が不明であることを表すログ出力する、
不明処理Ｃ：受信したパケットに適用する処理が不明であることを表すメッセージ（信号）を制御部７０に対して出力する、
不明処理Ｄ：受信したパケットに適用する処理が不明であることを表すメッセージ（信号）を、他の装置（たとえば、ネットワーク管理装置）に送信する。
【０２１１】
図２１Ａ、及び、図２１Ｂを参照しながら、上述した課題が本発明によって解決される理由について説明する。
【０２１２】
説明の便宜上、キャッシュメモリ９３は、図１におけるノードキャッシュ記憶部３０が有する機能を用いて実現されているとする。メモリ９２は、図１における探索木記憶部２０、及び、ルール記憶部４０が有する機能を用いて実現されているとする。探索処理回路９０は、図１における探索木制御部１０、制御部７０、パケット処理部５０、及び、通信ＩＦ６０が有する機能を用いて実現されているとする。
【０２１３】
説明の便宜上、メモリ９２に格納されているノードに関する更新タイミング（図１０におけるステップＳ１４５、または、図１２におけるステップＳ１６６にて設定）は、すべてのノードに関して、タイミング０であるとする。また、キャッシュメモリ９３に格納されているノードキャッシュにおけるキャッシュ作成タイミング（図１４におけるステップＳ１９６にて設定）は、すべてのノードに関して、タイミング１であるとする。
【０２１４】
説明の便宜上、さらに、図２１Ｂに示されているように、一斉に適用される２つのルール更新処理（第１ルールがノード３１（図２１Ａ）に追加される処理、及び、第２ルールがノード９２（図２１Ａ）に追加される処理）が実行されたとする。ノード３１（図２１Ａ）は、第１ルールが追加される処理によって、ノード３１Ｍに更新されるとする。ノード９２（図２１Ａ）は、第１ルールが追加される処理によって、ノード９２Ｍに更新されるとする。ノード３１がノード３１Ｍに更新されるタイミング、及び、ノード９２がノード９２Ｍに更新されるタイミングは、タイミング２であるとする。該タイミングは、たとえば、図１０におけるステップＳ１４５、図１１におけるステップＳ１５４、または、図１２におけるステップＳ１６６にて設定される。
【０２１５】
図２１Ｂに例示された探索木、及び、キャッシュメモリに格納されている情報に従い、パケット処理装置９４は、第１パケット（たとえば、あて先ＩＰアドレスが「１９２．１６８．１００．１」であり、あて先ポート番号が「８０」である）に適用する処理を探索するとする。ノード１を含む探索木を「第１探索木」と表す。ノード７を含む探索木を「第２探索木」と表す。また、キャッシュメモリ９３は、第１探索木におけるノード１、ノード２１、及び、ノード３１の各ノードに関するノードキャッシュ（図５に例示）と、第２探索木におけるノード７、ノード８１、及び、ノード９１の各ノードに関するノードキャッシュ（図５に例示）とを記憶しているとする。これらのノードキャッシュは、前記２つのルール更新処理の実行以前に受信したパケット（対象パケット）に関する探索処理の結果記憶されたものとする。図２１Ｂに示された例において、第１ルールにおけるマッチ条件が成立している第１パケットは、第１探索木におけるノード３１Ｍに分類され、第２ルールにおけるマッチ条件が成立している第１パケットは、第２探索木におけるノード９２Ｍに分類される処理が、正しい処理であるとする。
【０２１６】
図２１Ｂを参照すると、第１パケットに適用する処理を第１探索木に従い探索する探索処理が実行される場合に、該探索処理にて参照されるノード群（ノード１、及び、ノード２１、及び、ノード３１）に関する各ノードキャッシュ（図５に例示）は、キャッシュメモリ９３に格納されている。また、探索処理回路９０は、キャッシュメモリ９３に格納されているノードに関するノードキャッシュ（キャッシュ情報、図５に例示）を参照した結果に基づき、当該探索処理を実行する。すなわち、探索処理回路９０は、ノード１、ノード２１の各ノードに関するノードキャッシュ（図５に例示）におけるノード属性情報（図４Ｂ、図４Ｃに例示）から、子ノードＩＤリスト（図４Ｂに例示）を読み取り、読み取った子ノードＩＤリストに基づきノード３１を特定する。したがって、探索処理回路９０は、受信した第１パケットに適合しているルールとして、第１探索木におけるノード３１（図２１Ａ）を特定する。
【０２１７】
また、図２１Ｂを参照すると、第１パケットに適用する処理を第２探索木に従い探索する探索処理が実行される場合に、該探索処理にて参照されるノード群のうち、ノード７、及び、ノード８１に関する各ノードキャッシュ（図５に例示）は、キャッシュメモリ９３に格納されている。探索処理回路９０は、ノード７に関するノードキャッシュ（図５に例示）におけるノード属性情報（図４Ｂに例示）から、子ノードＩＤリストを読み取り、読み取った子ノードＩＤリストに基づきノード８１を特定する。次に、探索処理回路９０は、ノード８１に関するノードキャッシュ（図５に例示）におけるノード属性情報（図４Ｂに例示）から、子ノードＩＤリストを読み取り、読み取った子ノードＩＤリストに基づき、第１パケットに適合しているルールを含むノード９２を特定する。しかし、キャッシュメモリ９３には、ノード９２に関するノードキャッシュ（図５に例示）が格納されていないので、探索処理回路９０は、メモリ９２を参照することによって、ノード９２に関するノード属性情報（図４Ｂ、図４Ｃに例示）を読み取る。上述したようにノード９２に関するノード属性情報には、第２ルールを表すルールＩＤが追加されているので、探索処理回路９０は、メモリ９２に格納されているノード９２Ｍに関するノード属性情報（図４Ｂ、図４Ｃに例示）を読み取る。言い換えれば、探索処理回路９０は、第１パケットに適用する処理に関するルールとして、第２探索木におけるノード９２Ｍを特定する。
【０２１８】
上述した仮定によれば、第１探索木に関して到達したノード（すなわち、ノード３１）に関する更新タイミングは、タイミング０であり、第２探索木に関して到達したノード（すなわち、ノード９２Ｍ）に関する更新タイミングはタイミング２である。したがって、探索処理回路９０は、タイミング２と、タイミング０とを比較することによって、最新更新タイミングがタイミング２であると算出する（たとえば、図１３のステップＳ１８３）。
【０２１９】
探索処理回路９０は、キャッシュメモリ９３からノード３１に関するノードキャッシュ（図５に例示）を読み取ったので、読み取ったノードキャッシュにおけるキャッシュ作成タイミングに関する値（すなわち、タイミング１）と、タイミング２とを比較する。タイミング１がタイミング２よりも前であるので、探索処理回路９０は、第１探索木に関して、メモリ９２から読み取ったノード属性情報に基づき、パケットに適用する処理を探索する（図１３におけるステップＳ１８４）。この結果、探索処理回路９０は、メモリ９２からノード３１Ｍに関するノード属性情報を読み取る。したがって、探索処理回路９０は、パケットに適用する処理に関するルールとして、第１探索木におけるノード３１Ｍ（すなわち、第１ルールを表すルールＩＤを含む）を特定する。探索処理回路９０は、ノード３１Ｍに関するノード属性情報（図４Ｃ）におけるルールＩＤリストに含まれている各ルールＩＤに関して、ルールに関する部分空間等に基づき、パケットに適用する処理を線形探索する処理を実行する。探索処理回路９０は、該処理の結果として、ルールＩＤリストのうち、第１ルールを表すルールＩＤを特定する。
【０２２０】
すなわち、探索処理回路９０は、パケットに適用する処理を探索する処理にて、第１探索木に関してノード３１Ｍを特定し、第２探索木に関してノード９２Ｍを特定する。探索処理回路９０は、特定した第１ルールに関する優先度（図３に例示）、及び、特定した第２ルールに関する優先度（図３に例示）を比較し、高い優先度に関連付けされた第１ルールを選択する。探索処理回路９０は、パケットに適用する処理として、特定した第１ルールにおけるアクションを特定する。
【０２２１】
したがって、探索処理回路９０は、複数のルールが一斉に更新された場合であっても、キャッシュメモリに格納されているノードキャッシュ（キャッシュ情報）を参照しながら、ノードに適用する処理を短期間に探索することができる。
【０２２２】
次に、本実施形態に係る情報処理装置１によって奏される効果について説明する。
【０２２３】
本実施形態に係る情報処理装置１によれば、処理対象のデータに関して適用されるルールが、複数個、一斉に更新される場合であっても、該処理対象のデータに関する処理を短期間に実現することができる。この理由は、情報処理装置１が、最新更新タイミングと、キャッシュ作成タイミングとを比較することによって、ノードキャッシュ記憶部３０におけるノードキャッシュと、記憶装置における記憶内容との間における不整合を検出することができるからである。そして、情報処理装置１は、該不整合を検出した場合に、ノードキャッシュ記憶部３０に格納されているノードキャッシュではなく、探索木記憶部２０、または、ルール記憶部４０に格納されている記憶内容に基づき、該処理対象のデータに対して適用すべき処理を探索する。上述した効果が奏される理由について、さらに、図１を参照しながら詳細に説明する。
【０２２４】
探索木記憶部２０は、探索木に含まれている各ノードについて、当該ノードが最終的に更新されたタイミングを、当該ノードに関するノード属性情報（図４Ｂ、図４Ｃに例示）に記憶することが可能である。また、探索木制御部１０は、該処理対象のデータに対して適用すべき処理を含むルールを特定する場合に、参照するノードに関するノードキャッシュがノードキャッシュ記憶部３０に格納されていれば当該ノードキャッシュを参照し、格納されていなければ探索木記憶部２０に格納されているノード属性情報を参照する。探索木制御部１０は、探索木記憶部２０に格納されているノード属性情報を参照した場合に、ノードキャッシュ記憶部３０に、作成したタイミングを含むノードキャッシュ（キャッシュ情報）を作成し、作成したノードキャッシュをノードキャッシュ記憶部３０に格納する。
【０２２５】
また、探索木制御部１０は、ルールを特定した場合に、各到達したノードに関する最新更新タイミングを求める。探索木制御部１０は、到達したノードに関する参照先がノードキャッシュであった探索木ごとに、求めた最新更新タイミングと、到達したノードに関するキャッシュ作成タイミングとを比較する。探索木制御部１０は、最新更新タイミングが到達したノードに関するキャッシュ作成タイミング以降である探索木について、ノードキャッシュ記憶部３０に格納されているノードキャッシュではなく、探索木記憶部２０に格納されているノード属性情報（図４Ｂ、図４Ｃに例示）を参照し、参照したノード属性情報に基づき、該処理対象のデータに適用する処理を特定する。したがって、処理対象のデータに関して適用されるルールが、複数個、一斉に更新される場合であっても、該処理対象のデータに関する処理を短期間に実現することができる。
【０２２６】
＜第２の実施形態＞
次に、上述した第１の実施形態における主要な機能を実現する本発明の第２の実施形態について説明する。
【０２２７】
図２２を参照しながら、本発明の第２の実施形態に係る情報処理装置１０１が有する構成について詳細に説明する。図２２は、本発明の第２の実施形態に係る情報処理装置１０１が有する構成を示すブロック図である。
【０２２８】
第２の実施形態に係る情報処理装置１０１は、キャッシュ制御部１０２と、データ制御部１０３とを有する。情報処理装置１０１は、さらに、メモリ１０４と、キャッシュメモリ１０５と、更新部１０６とを有してもよい。
【０２２９】
メモリ１０４には、図４Ｂに例示された中間ノード属性情報、または、図４Ｃに例示されたリーフノード属性情報を表す第１情報を格納することができる。言い換えれば、第１情報は、該第１情報が作成（または、更新）された第２タイミングを表す情報を含む。説明の便宜上、第２タイミングを表す情報を、単に、「第２タイミング」と表す。キャッシュメモリ１０５には、図５に例示されたノードキャッシュ等のキャッシュ情報を格納することができる。たとえば、キャッシュメモリ１０５には、メモリ１０４に格納されている一部の情報を表す該第１情報と、該第１情報がキャッシュメモリ１０５に格納されるタイミングを表す情報とが関連付けされたキャッシュ情報を格納することができる。
【０２３０】
更新部１０６は、メモリ１０４に格納されている情報を更新し、キャッシュメモリ１０５を介することなく、更新した情報をメモリ１０４に格納することができる。
【０２３１】
キャッシュ制御部１０２は、第１情報を含むキャッシュ情報がキャッシュメモリ１０５に格納されているか否かを判定する。キャッシュ制御部１０２は、該キャッシュ情報がキャッシュメモリ１０５に格納されている場合に、キャッシュメモリ１０５から該第１情報を含むキャッシュ情報を読み取る。
【０２３２】
キャッシュ制御部１０２は、該キャッシュ情報がキャッシュメモリ１０５に格納されていない場合に、メモリ１０４に格納されている第１情報を読み取り、読み取った第１情報と、該第１情報をキャッシュメモリ１０５に格納するタイミングを表す情報とが関連付けされたキャッシュ情報を作成する。説明の便宜上、キャッシュメモリ１０５に格納するタイミングを、「第１タイミング」と表す。キャッシュ制御部１０２は、作成したキャッシュ情報をキャッシュメモリ１０５に格納する。
【０２３３】
以降では、説明の便宜上、タイミングを表す情報を、単に、「タイミング」と表すのと同様に、第１タイミングを表す情報を、単に、「第１タイミング」と表す。
【０２３４】
データ制御部１０３は、キャッシュ制御部１０２によって、複数セットのキャッシュ情報が読み取られた場合に、各セットのキャッシュ情報に含まれている第２タイミングのうち、最新であるタイミング（最新更新タイミング）を算出する。言い換えると、データ制御部１０３は、キャッシュメモリ１０５から読み取ったキャッシュ情報、メモリ１０４に格納されている第１情報に基づき作成されたキャッシュ情報、または、その両者に基づき、最新更新タイミングを算出する。データ制御部１０３は、複数セットのキャッシュ情報のうち、算出した最新更新タイミングが、該セットのキャッシュ情報に含まれている第１タイミングよりも後であるキャッシュ情報に関して、該キャッシュ情報に関する第１情報をメモリ１０４から読み取る。言い換えれば、データ制御部１０３は、キャッシュメモリ１０５にキャッシュ情報が格納された処理よりも後に更新された第１情報（説明の便宜上、更新された第１情報を「第３情報」と表す）を、メモリ１０４から読み取る。すなわち、データ制御部１０３は、算出した最新更新タイミングよりも前のタイミングを第１タイミングとして含んでいるキャッシュ情報を対象として、メモリ１０４から第３情報を読み取る。データ制御部１０３は、読み取った第３情報と、該第３情報をキャッシュメモリ１０５に格納するタイミングを表す情報とが関連付けされたキャッシュ情報を作成し、作成したキャッシュ情報をキャッシュメモリ１０５に格納する。
【０２３５】
キャッシュメモリ１０５は、たとえば、図１に示されたノードキャッシュ記憶部３０が有する機能を用いて実現することができる。メモリ１０４は、たとえば、図１に示された探索木記憶部２０、または、ルール記憶部４０が有する機能を用いて実現することができる。更新部１０６は、たとえば、図１に示された探索木制御部１０が有する機能を用いて実現することができる。
【０２３６】
キャッシュ制御部１０２は、たとえば、図１に示された探索木制御部１０、または、制御部７０が有する機能を用いて実現することができる。データ制御部１０３は、たとえば、図１に示された探索木制御部１０、または、制御部７０が有する機能を用いて実現することができる。
【０２３７】
次に、第２の実施形態に係る情報処理装置１０１に関する効果について説明する。
【０２３８】
第２の実施形態に係る情報処理装置１０１によれば、処理対象のデータに関して適用されるルールが、複数個、一斉に更新される場合であっても、該処理対象のデータに関する処理を短期間に実現することができる。この理由は、複数個のルールが一斉に更新される場合であっても、本実施形態に係る情報処理装置１０１が実行する処理によって、キャッシュメモリ１０５に格納されている第１情報と、メモリ１０４に格納されている第１情報とが一致するので、キャッシュメモリ１０５を介した処理が可能であるからである。
【０２３９】
これに対して、特許文献１及び特許文献２に開示された装置が、データに関する処理を短時間に実現することができない理由について説明する。図２１Ａ、及び、図２１Ｂを参照しながら説明したように、複数個のルールが一斉に更新された場合に、メモリ１０４に格納されている第１情報と、キャッシュメモリ１０５に格納されている第１情報とは、一致していない（不整合が生じている）可能性がある。したがって、特許文献１、及び、特許文献２に開示された装置は、一斉に更新されたルールを参照する場合に、キャッシュメモリに格納されている第１情報を参照するのではなく、メモリに格納されている第１情報を参照しながら該第１情報に関する処理を実行する。この結果、メモリに格納されている多くのデータを処理装置に転送する場合には、該転送する処理が、全体の処理時間を律速してしまう可能性がある。
【０２４０】
（ハードウェア構成例）
上述した本発明の各実施形態における情報処理装置を、１つの計算処理装置（コンピュータ）を用いて実現するハードウェア資源の構成例について説明する。但し、係る情報処理装置は、物理的または機能的に少なくとも２つの計算処理装置を用いて実現してもよい。また、係る情報処理装置は、専用の装置として実現してもよい。
【０２４１】
図２３は、第１の実施形態及び第２の実施形態に係る情報処理装置を実現可能な計算処理装置のハードウェア構成例を概略的に示す図である。計算処理装置２００は、中央処理演算装置（Ｃｅｎｔｒａｌ＿Ｐｒｏｃｅｓｓｉｎｇ＿Ｕｎｉｔ、以降「ＣＰＵ」と表す）２１０、メモリ２２０、ディスク２３０、不揮発性記録媒体２４０、通信インターフェース（以降、「通信ＩＦ」と表す）２７０、及び、ディスプレー２８０を有する。計算処理装置２００は、入力装置２５０、出力装置２６０に接続可能であってもよい。計算処理装置２００は、通信ＩＦ２７０を介して、他の計算処理装置、及び、通信装置と情報を送受信することができる。
【０２４２】
不揮発性記録媒体２４０は、コンピュータが読み取り可能な、たとえば、コンパクトディスク（Ｃｏｍｐａｃｔ＿Ｄｉｓｃ）、デジタルバーサタイルディスク（Ｄｉｇｉｔａｌ＿Ｖｅｒｓａｔｉｌｅ＿Ｄｉｓｃ）である。また、不揮発性記録媒体２４０は、ユニバーサルシリアルバスメモリ（ＵＳＢメモリ）、ソリッドステートドライブ（Ｓｏｌｉｄ＿Ｓｔａｔｅ＿Ｄｒｉｖｅ）等であってもよい。不揮発性記録媒体２４０は、電源を供給しなくても係るプログラムを保持し、持ち運びを可能にする。不揮発性記録媒体２４０は、上述した媒体に限定されない。また、不揮発性記録媒体２４０の代わりに、通信ＩＦ２７０、及び、通信ネットワークを介して係るプログラムを持ち運びしてもよい。
【０２４３】
すなわち、ＣＰＵ２１０は、ディスク２３０に記憶されているソフトウェア・プログラム（コンピュータ・プログラム：以下、単に「プログラム」と称する）を、実行する際にメモリ２２０にコピーし、演算処理を実行する。ＣＰＵ２１０は、プログラム実行に必要なデータをメモリ２２０から読み取る。表示が必要な場合には、ＣＰＵ２１０は、ディスプレー２８０に出力結果を表示する。外部への出力が必要な場合には、ＣＰＵ２１０は、出力装置２６０に出力結果を出力する。外部からプログラムを入力する場合、ＣＰＵ２１０は、入力装置２５０からプログラムを読み取る。ＣＰＵ２１０は、上述した図１、図２、または、図２２に示す各部が表す機能（処理）に対応するところのメモリ２２０にある情報処理プログラム（図６乃至図１５）を解釈し実行する。ＣＰＵ２１０は、上述した本発明の各実施形態において説明した処理を順次実行する。
【０２４４】
すなわち、このような場合、本発明は、係る情報処理プログラムによっても成し得ると捉えることができる。さらに、係る情報処理プログラムが記録されたコンピュータが読み取り可能な不揮発性の記録媒体によっても、本発明は成し得ると捉えることができる。
【０２４５】
以上、上述した実施形態を模範的な例として本発明を説明した。しかし、本発明は、上述した実施形態には限定されない。すなわち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【０２４６】
この出願は、２０１６年１月２６日に出願された日本出願特願２０１６−０１２３３４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２４７】
１    情報処理装置
１０    探索木制御部
２０    探索木記憶部
３０    ノードキャッシュ記憶部
４０    ルール記憶部
５０    パケット処理部
６０    通信ＩＦ
７０    制御部
１１    探索木初期化部
１２    ルール更新部
１３    探索木探索部
１０１    情報処理装置
１０２    キャッシュ制御部
１０３    データ制御部
１０４    メモリ
１０５    キャッシュメモリ
１０６    更新部
９０    探索処理回路
９１    バス
９２    メモリ
９４    パケット処理装置
９３    キャッシュメモリ
２００    計算処理装置
２１０    ＣＰＵ
２２０    メモリ
２３０    ディスク
２４０    不揮発性記録媒体
２５０    入力装置
２６０    出力装置
２７０    通信ＩＦ
２８０    ディスプレー
【図１】
2017130824.tif 000003
【図２】
2017130824.tif 000004
【図３】
2017130824.tif 000005
【図４Ａ】
2017130824.tif 000006
【図４Ｂ】
2017130824.tif 000007
【図４Ｃ】
2017130824.tif 000008
【図５】
2017130824.tif 000009
【図６】
2017130824.tif 000010
【図７】
2017130824.tif 000011
【図８】
2017130824.tif 000012
【図９】
2017130824.tif 000013
【図１０】
2017130824.tif 000014
【図１１】
2017130824.tif 000015
【図１２】
2017130824.tif 000016
【図１３】
2017130824.tif 000017
【図１４】
2017130824.tif 000018
【図１５】
2017130824.tif 000019
【図１６Ａ】
2017130824.tif 000020
【図１６Ｂ】
2017130824.tif 000021
【図１６Ｃ】
2017130824.tif 000022
【図１６Ｄ】
2017130824.tif 000023
【図１６Ｅ】
2017130824.tif 000024
【図１７】
2017130824.tif 000025
【図１８】
2017130824.tif 000026
【図１９】
2017130824.tif 000027
【図２０Ａ】
2017130824.tif 000028
【図２０Ｂ】
2017130824.tif 000029
【図２１Ａ】
2017130824.tif 000030
【図２１Ｂ】
2017130824.tif 000031
【図２２】
2017130824.tif 000032
【図２３】
2017130824.tif 000033
【手続補正書】
【提出日】平成30年7月9日(2018.7.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段と、
前記キャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御手段と
を備える情報処理装置。
【請求項２】
ある対象データに対して処理を適用するか否かを判定する条件を表す判定条件と、前記判定条件が成立している場合に前記ある対象データに対して適用する前記処理とが関連付けされた処理情報に従い、対象データに関して成立している前記判定条件に関連付けされた前記処理を、前記対象データに対して実行する処理実行手段
をさらに備え、
前記第１情報は、前記判定条件を表す情報である
請求項１に記載の情報処理装置。
【請求項３】
前記対象データに関して成立している前記判定条件のうち、前記対象データに対して実行する前記処理を選択する処理選択手段
をさらに備え、
前記処理情報は、前記判定条件に、さらに、前記処理を選択する順序を表す優先度が関連付けされた情報であり、
前記処理選択手段は、成立している前記判定条件に関連付けされた前記処理のうち、高い前記優先度に関連付けされた前記処理を選択する
請求項２に記載の情報処理装置。
【請求項４】
前記対象データに関して成立している前記判定条件を探索する探索手段
をさらに備え、
前記第１情報は、前記第１情報における前記判定条件に関する判定処理の後に判定される前記判定条件に関する情報、または、前記処理情報を識別可能な処理情報識別子を含み、
前記第３情報は、前記第３情報における前記判定条件に関する判定処理の後に判定される前記判定条件に関する情報、または、前記処理情報を識別可能な処理情報識別子を含み、
前記探索手段は、前記第１情報、または、前記第３情報における前記判定条件が前記対象データに関して成立しているか否かを判定処理と、成立している場合には、前記第１情報または前記第３情報に関する前記判定処理の後にて判定される前記判定条件を含む情報のうち、前記対象データに関して成立している前記判定条件を含む情報を選択する選択処理とを実行することによって、前記対象データに関して成立している前記判定条件に関連付けされた前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する
請求項３に記載の情報処理装置。
【請求項５】
前記データ制御手段は、前記キャッシュ制御手段が読み取った前記キャッシュ情報における前記第１情報に基づき前記探索手段が、前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する場合に参照した前記第１情報における前記第２タイミングのうち最新である前記第２タイミングが、前記第１タイミングよりも後である前記キャッシュ情報に関する第３情報を前記メモリから読み取る
請求項４に記載の情報処理装置。
【請求項６】
前記第１情報が表す前記判定条件は、前記判定処理の後にて判定される前記判定条件よりも緩い条件である
請求項５に記載の情報処理装置。
【請求項７】
前記データ制御手段は、前記探索手段が、前記処理情報識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する場合に参照した前記第１情報における前記第２タイミングのうち最新である前記第２タイミングが前記第１タイミングよりも後である前記キャッシュ情報を特定する場合に参照した前記第１情報を、前記メモリから読み取る
請求項４乃至請求項６のいずれかに記載の情報処理装置。
【請求項８】
前記メモリには、前記第１情報、または、前記第３情報に関連付けされたノードを含む探索木が格納されており、
前記探索木における各ノードは、前記ノードを表すノード識別子によって識別され、
前記第１情報、及び、前記第３情報は、前記ノードを表す前記ノード識別子と、前記判定条件を表す情報と、自ノード情報が更新された更新タイミングと、前記判定条件が成立している場合に前記判定条件の後にて判定される判定条件が関連付けされているノードを表すノード識別子とが関連付けされたノード情報、または、前記ノードを表す前記ノード識別子と、前記判定条件を表す情報と、前記更新タイミングと、前記処理情報を識別可能な前記処理情報識別子とが関連付けされたノード情報であって、
前記探索手段は、前記探索木に含まれている前記ノードに関連付けされた前記ノード情報に基づき、前記対象データに関して成立している前記判定条件を含む前記ノード情報に関連付けされたノードを特定することによって、特定された前記ノードに関連付けされた前記ノード情報に含まれている前記処理情報識別子、または、前記判定処理の後にて判定される前記判定条件を含む前記ノード情報に関連付けされた前記ノード識別子、または、前記対象データに関して成立している前記判定条件が存在しないことを特定する
請求項４乃至請求項７のいずれかに記載の情報処理装置。
【請求項９】
情報処理装置によって、メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御手段によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納する情報処理方法。
【請求項１０】
メモリに格納されている情報を更新可能な更新装置が、キャッシュメモリを介することなく更新された情報を格納可能な前記メモリに格納されている一部の情報を格納可能な前記キャッシュメモリに、第１情報と、前記第１情報が前記キャッシュメモリに格納される第１タイミングとが関連付けされたキャッシュ情報が格納されているか否かを判定し、前記キャッシュ情報が前記キャッシュメモリに格納されている場合には前記キャッシュメモリから前記キャッシュ情報を読み取り、前記キャッシュ情報が前記キャッシュメモリに格納されていない場合には前記メモリから前記第１情報を読み取り、前記第１情報を前記キャッシュメモリに格納するタイミングと前記第１情報とが関連付けされた前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するキャッシュ制御機能と、
前記キャッシュ制御機能によって読み取られた、または、作成された複数セットの前記キャッシュ情報であって、前記複数セットの前記キャッシュ情報における前記第１情報が作成または更新された第２タイミングを含んでいる前記キャッシュ情報のうち、最新である前記第２タイミングよりも前のタイミングを前記第１タイミングとして含んでいる前記キャッシュ情報を対象として、該キャッシュ情報に前記第１情報が更新された第３情報を前記メモリから読み取り、読み取った前記第３情報を前記キャッシュメモリに格納するタイミングと前記第３情報とが関連付けされている前記キャッシュ情報を作成し、作成した前記キャッシュ情報を前記キャッシュメモリに格納するデータ制御機能と
をコンピュータに実現させる情報処理プログラム。
【国際調査報告】
2017130824.tif 000034
2017130824.tif 000035
2017130824.tif 000036
2017130824.tif 000037