(57)【要約】  パケット処理装置は、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部と、ルールテーブルに含まれるルールを更新するルール制御部と、受信したパケットに適用するアクションを、ルールテーブルを用いてアクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部と、を備え、パケット処理部は、ポインターを蓄積した後、ルール制御部によりルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを蓄積したポインターに従ってアクションテーブルから抽出する。ソフトウェアで実装されたパケット処理部によるパケット処理を高速化する。
2015133448.tif 000002
【特許請求の範囲】
【請求項１】
パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部と、
前記ルールテーブルに含まれるルールを更新するルール制御部と、
受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部と、を備え、
前記パケット処理部は、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する
ことを特徴とするパケット処理装置。
【請求項２】
前記ルール制御部は、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
前記パケット処理部は、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
請求項１に記載のパケット処理装置。
【請求項３】
前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定する
請求項２に記載のパケット処理装置。
【請求項４】
前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
請求項２または３に記載のパケット処理装置。
【請求項５】
前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定のタイミングで特定し、特定したポインターを削除する
請求項４に記載のパケット処理装置。
【請求項６】
前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定の周期で、または、無効化された際に削除する
請求項５に記載のパケット処理装置。
【請求項７】
前記パケット処理部は、検索したアクションに対するポインターを蓄積するフローキャッシュテーブルと、
前記フローキャッシュテーブルに蓄積したポインターの有効性を示すフラグを蓄積するフラグテーブルと、を有し、
前記蓄積したポインターが無効化されると、無効化されたポインターに対応するフラグを前記フラグテーブルにおいて無効に設定し、前記所定の周期で前記フラグテーブルを参照することにより、無効化されたポインターを特定する
請求項６に記載のパケット処理装置。
【請求項８】
コンピュータが、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する工程と、
第１のプロセスが、前記ルールテーブルに含まれるルールを更新する工程と、
第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する工程と、
前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する工程と、を含む
ことを特徴とするパケット処理方法。
【請求項９】
前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
請求項８に記載のパケット処理方法。
【請求項１０】
パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する処理と、
第１のプロセスが、前記ルールテーブルに含まれるルールを更新する処理と、
第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する処理と、
前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する処理と、をコンピュータに実行させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１４−０４１６２４号（２０１４年３月４日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、パケット処理装置、パケット処理方法およびプログラムに関し、特に、集中制御型のネットワークにおけるパケット処理装置、パケット処理方法およびプログラムに関する。
【背景技術】
【０００２】
近年、通信システムに設けられたスイッチ等のパケット処理装置において、パケット処理部をソフトウェアで実装することが多くなってきている。特に、汎用プロセッサの性能向上とＮＦＶ(Network Functions Virtualization)やＳＤＮ（Software-Defined Networking）の潮流により、パケット処理部をソフトウェアで実装するニーズが高まっている。また、ソフトウェア処理に基づいてパケット処理を行う際に、ハードウェア処理と同等の処理性能を満たすことが求められている。【０００３】
ＮＦＶやＳＤＮに基づいて集中制御型のネットワークを実現する技術として、例えば、非特許文献１、２にオープンフロー（OpenFlow）が記載されている。オープンフローは、通信をエンドツーエンドのフローとして捉え、フロー単位で経路制御、障害回復、負荷分散、最適化を行うものである。非特許文献２に規定されているオープンフロースイッチ（ＯＦＳ：OpenFlow Switch）は、オープンフローコントローラ（ＯＦＣ：OpenFlow Controller）との通信用のセキュアチャネルを備え、ＯＦＣから適宜追加または書き換え指示されるフローテーブルに従って動作する。フローテーブルには、フロー毎に、パケットヘッダと照合するマッチ条件（Match Fields）と、フロー統計情報（Counters）と、処理内容を定義したインストラクション（Instructions）と、の組が定義される（非特許文献２の「5.2 Flow Table」の項参照）。【０００４】
ＯＦＳは、パケットを受信すると、フローテーブルから、受信パケットのヘッダ情報に適合するマッチ条件（非特許文献２の「5.3 Matching」参照）を持つエントリーを検索する。検索の結果、受信パケットに適合するエントリーが見つかった場合、ＯＦＳは、フロー統計情報（カウンタ）を更新するとともに、受信パケットに対して、当該エントリーのインストラクションフィールドに記述された処理内容（指定ポートからのパケット送信、フラッディング、廃棄など）を実施する。一方、検索の結果、受信パケットに適合するエントリーが見つからなかった場合、ＯＦＳは、セキュアチャネルを介して、ＯＦＣに対してエントリー設定の要求、すなわち、受信パケットを処理するための制御情報の送信要求（Packet-Inメッセージ）を送信する。ＯＦＳは、処理内容が定められたフローエントリを受け取ってフローテーブルを更新する。このように、ＯＦＳは、フローテーブルに格納されたエントリーを制御情報として用いてパケット転送を行う。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Nick McKeownほか７名、“OpenFlow: Enabling Innovation in Campus Networks”、[online]、［平成２６（２０１４）年２月２４日検索］、インターネット〈URL:http://www.openflow.org/documents/openflow-wp-latest.pdf〉
【非特許文献２】“OpenFlow Switch Specification”Version 1.3.1 (Wire Protocol 0x04)、[online]、［平成２６（２０１４）年２月２４日検索］、インターネット〈URL:https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.1.pdf〉
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【０００７】
上述のとおり、汎用プロセッサの性能向上、および、ＮＦＶ(Network Function Virtualization) やＳＤＮ（Software-Defined Networking）の潮流により、パケット処理部をソフトウェアで実装する機会が増加している。【０００８】
しかし、一般に、パケット処理部をソフトウェアで実装した場合、ハードウェア処理と比較して処理速度が遅いことが知られている。特に、パケット処理時のルール検索をソフトウェアで行う場合、完全一致検索のような一部の検索方式を除くと、ハードウェア処理と比較して検索処理に長い時間を要する。また、最長一致検索やマスク検索、範囲指定の検索が必要とされる場合が多く、これらの場合には、ソフトウェア検索によると、ハードウェア検索と比較して処理速度が遅くなる。【０００９】
ソフトウェアに基づくパケット処理を高速化するための関連技術として、フローキャッシュテーブルを用いる方法が発明されている。フローキャッシュテーブルとは、パケット毎に必要な複数回のルール検索をキャッシュとして保持するためのテーブルである。フローキャッシュテーブルを用いることにより、パケットがいずれのフローに属するかを一回検索することにより、複数回分のルール検索結果をまとめて取得することが可能となる。【００１０】
ところで、上記関連技術におけるフローキャッシュテーブルは、パケット処理部とは別個のルール制御部のようなプロセスによって作成および管理されている。かかる技術によると、パケット処理部がフローキャッシュテーブルにアクセスする場合、パケット処理部とルール制御部との間で排他処理を行う必要が生じる。したがって、パケット処理部がフローキャッシュテーブルにアクセスする際、排他処理による待ち時間が生じ、パケット処理に時間を要するという問題がある。【００１１】
そこで、ソフトウェアで実装されたパケット処理部によるパケット処理を高速化することが課題となる。本発明の目的は、かかる課題解決に寄与するパケット処理装置、パケット処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第１の態様によると、パケット処理装置が提供される。前記パケット処理装置は、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部を備えている。また、前記パケット処理装置は、前記ルールテーブルに含まれるルールを更新するルール制御部を備えている。さらに、前記パケット処理装置は、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部を備えている。ここで、前記パケット処理部は、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する。【００１３】
本発明の第２の態様によると、パケット処理方法が提供される。前記パケット処理方法は、コンピュータが、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する工程を含む。また、前記パケット処理方法は、第１のプロセスが、前記ルールテーブルに含まれるルールを更新する工程を含む。さらに、前記パケット処理方法は、第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する工程を含む。また、前記パケット処理方法は、前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する工程を含む。【００１４】
本発明の第３の態様によると、プログラムが提供される。前記プログラムは、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する処理をコンピュータに実行させる。また、前記プログラムは、第１のプロセスが、前記ルールテーブルに含まれるルールを更新する処理前記コンピュータに実行させる。さらに、前記プログラムは、第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する処理を前記コンピュータに実行させる。また、前記プログラムは、前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する処理を前記コンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【００１５】
本発明に係るパケット処理装置、パケット処理方法およびプログラムによると、ソフトウェアで実装されたパケット処理部によるパケット処理を高速化することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】一実施形態に係るパケット処理装置の構成を例示するブロック図である。
【図２】第１の実施形態に係るパケット処理装置の構成を例示するブロック図である。
【図３】第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。
【図４】第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。
【図５】第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。
【発明を実施するための形態】
【００１７】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００１８】
一実施形態では、ロックレスなフローキャッシュテーブルを提案する。フローキャッシュテーブルによるルール検索高速化に加えて、フローキャッシュテーブルをロックレスで実装することでフローキャッシュテーブルに対するアクセス時の待ち時間を解消し、パケット処理の高速化を図る。
【００１９】
ロックレスなフローキャッシュテーブルを実現する手段として、パケット処理部でフローキャッシュテーブルの作成・管理を行う。また、フローキャッシュテーブルをルールテーブルと同期する処理をパケット処理部で行うことで、ルール制御部によるフローキャッシュテーブルに対するアクセスを不要とし、ロックレスなフローキャッシュテーブルを実現する。
【００２０】
図１は、一実施形態に係るパケット処理装置の構成を例示するブロック図である。図１を参照すると、パケット処理装置１０は、パケットの処理内容を規定するアクションを含むアクションテーブル２６と、パケットに適用するアクションを検索するためのルールを含むルールテーブル２４を保持する記憶部１３と、ルールテーブル２４に含まれるルールを更新するルール制御部１２と、受信したパケットに適用するアクションを、ルールテーブル２４を用いてアクションテーブル２６から検索し、検索したアクションに従って当該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部１６と、を備えている。パケット処理部１６は、ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを、蓄積したポインターに従ってアクションテーブル２６から抽出する。
【００２１】
このように、ルール制御部１２ではなく、パケット処理部１６自身が検索したアクションに対するポインターを蓄積することで、ルール制御部１２とパケット処理部１６との間の排他処理が不要となる。したがって、パケット処理部１６をソフトウェアで実装した場合におけるパケット処理を高速化することが可能となる。
【００２２】
パケット処理部１６が、ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定するために、例えば、以下の構成を採用することができる。
【００２３】
図２を参照すると、ルール制御部１２は、ルールテーブル２４に含まれるルールを更新する際、当該更新を識別する識別子（例えば、シーケンス番号）を記憶部（例えば、共有メモリ１４が保持するアクションテーブル２６内）に記録し、パケット処理部１６は、前記ポインターを蓄積する際、記憶部（共有メモリ１４）に記録された識別子を保持する。パケット処理部１６は、保持した識別子とルール制御部１２により記憶部（共有メモリ１４）に記録された識別子を比較することにより、前記ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定する。
【００２４】
より具体的には、ルール制御部１２はエントリーの更新（例えば、追加・変更・削除など）時にアクションテーブル２６のエントリー内のシーケンス番号を更新する。パケット処理部１６はフローキャッシュテーブル２８を作成する際に、アクションテーブル２６へのポインターをキャッシュするのに加えて、アクションテーブル２６のエントリー内のシーケンス番号をクッキーとしてキャッシュする。パケット処理部１６はフローキャッシュテーブル２８を検索し、ヒットした場合にフローキャッシュテーブル２８に登録されたアクションテーブル２６へのポインターに従い、アクションエントリーを参照するが、このときフローキャッシュテーブル２８内にキャッシュしたシーケンス番号のクッキーとアクションテーブル２６に登録されている現在のシーケンス番号を比較する。両者が一致すれば、パケット処理部１６はアクションテーブル２６は前回から変更がないと判定し、パケット処理を継続する。一方、両者が一致しない場合、パケット処理部１６はアクションテーブル２６が変更されていると判定し、フローキャッシュエントリーは無効であると判定する。このとき、パケット処理部１６は、新規のフローキャッシュエントリーを作成するために、ルールテーブル２４の検索とアクションテーブル２６の参照、フローキャッシュテーブル２８の登録を行う。
【００２５】
かかる構成によると、フローキャッシュテーブル２８によるルール検索高速化に加えて、フローキャッシュテーブル２８をロックレスで実装することができ、パケット処理部１６がフローキャッシュテーブル２８にアクセスする際の待ち時間を解消し、パケット処理部１６をソフトウェアで実装した場合におけるパケット処理の高速化が可能となる。
【００２６】
＜実施形態１＞
次に、第１の実施形態に係るパケット処理装置について、図面を参照して説明する。図２は、本実施形態のパケット処理装置１０の構成を一例として示すブロック図である。
【００２７】
図２を参照すると、パケット処理装置１０は、ルール制御部１２、共有メモリ１４、および、パケット処理部１６を備えている。共有メモリ１４は、ルールテーブル２４とアクションテーブル２６を保持している。パケット処理部１６は、ローカルメモリ１８を有し、ローカルメモリ１８上にフローキャッシュテーブル２８を保持している。
【００２８】
本実施形態では、ルールテーブル２４の検索でヒットした場合に、その結果として得られるアクションテーブル２６へのポインター情報をパケット処理部１６内のローカルなフローキャッシュテーブル２８に登録する。同一のフローに属する後続パケットについては、パケット処理部１６によるルールテーブル２４の検索をバイパスし、フローキャッシュテーブル２８を検索することで検索処理を高速化する。
【００２９】
ルール制御部１２は、パケット処理で使用されるアクションテーブル２６と、アクションテーブル２６を検索するために使用されるルールテーブル２４に対して、追加・変更・削除といった管理を行う。アクションテーブル２６およびルールテーブル２４はルール制御部１２とパケット処理部１６の双方からアクセスする必要があるため、共有メモリ１４に実装される。
【００３０】
パケット処理部１６は、パケット受信時に、まず、ルールテーブル２４を検索する。次に、パケット処理部１６は、検索結果として得られるポインターに従って、アクションテーブル２６内の該当アクションエントリーを参照し、アクションエントリーに従ってパケット処理する。
【００３１】
ここで、同一のフローに属する後続のパケットついては、同一のアクションエントリーで処理することができる。そこで、パケット処理部１６は、パケット処理後にフロー情報をキーとしたフローキャッシュエントリーを、パケット処理部１６内のローカルメモリ上のフローキャッシュテーブル２８に登録する。これにより、パケット処理部１６によるアクションエントリーの検索を高速化することができる。
【００３２】
また、パケット処理部１６で作成したフローキャッシュテーブル２８と、ルールテーブル２４との間で同期をとる必要がある。同期をとるために、本実施形態では、以下の方法を採用する。
【００３３】
ルール制御部１２は、ルールテーブル２４に対して、更新（例えば、追加・変更・削除など）を行う際、アクションテーブル２６内にシーケンス番号を登録する。ここで、シーケンス番号とは、アクションテーブルを更新した際に、アクションテーブルの情報が書き換えられたことを示す情報をいう。一例として、シーケンス番号として、オーバフローしないような値（例えば、タイムスタンプ値等）を用いることができる。なお、本発明において、シーケンス番号は、タイムスタンプ値に限定されない。
【００３４】
パケット処理部１６は、フローキャッシュテーブル２８の作成時に、アクションテーブル２６内のシーケンス番号をクッキー情報としてキャッシュし、フローキャッシュテーブル２８内に登録する。
【００３５】
パケット処理部１６は、フローキャッシュテーブル２８を検索し、アクションテーブル２６を参照する際に、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号とを比較する。両者が一致した場合、パケット処理部１６は、ルールテーブル２４が前回から更新されておらず、フローキャッシュテーブル２８は有効であるものと判定して、処理を継続する。
【００３６】
一方、両者が一致しない場合、パケット処理部１６はルールテーブル２４が前回参照してフローキャッシュエントリーを作成した時点からルール制御部１２によって更新されたものと判定し、フローキャッシュテーブル２８の該当エントリーは無効であると判定する。この場合、パケット処理部１６は、フローキャッシュテーブル２８の該当エントリーに対する無効フラグをＯＮにする。また、パケット処理部１６は、無効フラグをＯＮに設定後、新規のフローキャッシュエントリーを作成するためにルールテーブル２４を検索し、アクションテーブル２６を参照する。このとき、検索がヒットすれば、パケット処理部１６はヒットしたエントリーに従ってパケットを処理する。また、パケット処理部１６は、パケット処理後、フローキャッシュテーブル２８に新しいエントリーを登録する。
【００３７】
ただし、この方法だけでは、フローキャッシュテーブル２８内の無効エントリーが残存し、メモリリソースが枯渇するおそれがある。そこで、パケット処理部１６は、フローキャッシュテーブル２８を周期的に検索し、無効フラグがＯＮのエントリーを特定する。パケット処理部１６は、無効フラグがＯＮのエントリーを特定すると、該当エントリーの削除を行う。なお、フローキャッシュテーブル２８から該当エントリーを削除した際にテーブルの構成に変更が生じる場合には、併せて、テーブルの構成の変更(例えば、ハッシュテーブルをチェーン法で形成しているときには、チェーンの組み換え操作)を行う。
【００３８】
次に、図面を参照して、本実施形態のパケット処理装置１０の動作について説明する。図３〜図５は、パケット処理装置１０の動作を一例として示すシーケンス図である。
【００３９】
図３は、ルール制御部１２によるルールテーブルへ２４のルールの登録の動作と、パケット処理部１６による同一のフローに属する1stパケットと2ndパケットの処理の動作を例示するシーケンス図である。
【００４０】
図３を参照すると、ルール制御部１２は、アクションテーブル２６を検索するのに使用されるルールテーブル２４に対して、更新（例えば、ルールの追加、変更または削除）を行う（ステップＳ２）。ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う際、アクションテーブル２６内にシーケンス番号を登録する（ステップＳ１）。
【００４１】
パケット処理部１６が受信したパケットがファーストパケットである場合（ステップＳ３）、フローキャッシュテーブル２８には、当該パケットに相当するフローキャッシュエントリーが未登録である（ステップＳ４）。そこで、パケット処理部１６は、ルールテーブル２４を検索する（ステップＳ５）。次に、パケット処理部１６は、検索結果として得られるポインターに従って、アクションテーブル２６内の該当アクションエントリーを参照し（ステップＳ６）、アクションエントリーに従ってパケット処理する（ステップＳ７）。
【００４２】
また、パケット処理部１６は、パケット処理の後、フロー情報をキーとしたフローキャッシュエントリーを、パケット処理部１６内のローカルメモリ上のフローキャッシュテーブル２８に登録する（ステップＳ８）。なお、パケット処理部１６は、フローキャッシュテーブルへのエントリーの登録後（ステップＳ８）、パケットを処理（ステップＳ７）してもよい。
【００４３】
また、パケット処理部１６は、フローキャッシュテーブル２８の作成時に、アクションテーブル２６内のシーケンス番号をクッキー情報としてキャッシュし、フローキャッシュテーブル２８内に登録する。さらに、パケット処理部１６は、登録したフローキャッシュエントリーが有効であることを示すために、当該フローキャッシュエントリーに対する無効フラグをＯＦＦに設定する。
【００４４】
パケット処理部１６は、同一のフローに属する２番目以降のパケットを受信すると（ステップＳ９）、フローキャッシュテーブル２８を検索し（ステップＳ１０）、アクションテーブル２６を参照する際に（ステップＳ１１）、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号を比較する。両者が一致した場合、パケット処理部１６は、ルールテーブル２４が前回から更新されておらず、フローキャッシュテーブル２８は有効であると判定して、処理を継続する。すなわち、パケット処理部１６は、フローキャッシュテーブル２８に登録されたフローキャッシュエントリーに従って得られたアクションテーブル２６内のアクションエントリーに基づいて、当該パケットを処理する（ステップＳ１２）。
【００４５】
図４は、ルール制御部１２がアクションテーブル２６と、ルールテーブル２４に対して、追加、変更または削除を行った場合のパケット処理装置１０の動作を例示するシーケンス図である。
【００４６】
図４を参照すると、ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う（ステップＳ２２）。また、ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う際、アクションテーブル２６内に新たなシーケンス番号を登録する。
【００４７】
パケット処理部１６は、ルール制御部１２よるルール変更後のパケットを受信すると（ステップＳ２３）、フローキャッシュテーブル２８を検索し（ステップＳ２４）、アクションテーブル２６を参照する際に（ステップＳ２５）、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号とを比較する。後者のシーケンス番号はルール制御部１２より新しい番号に更新されているため、両者は一致しない。そこで、パケット処理部１６はルールテーブル２４が前回参照してフローキャッシュエントリーを作成した時点からルール制御部１２によって更新されたものと判定し、フローキャッシュテーブル２８の該当エントリーは無効であると判定する。この場合、パケット処理部１６は、フローキャッシュテーブル２８の該当エントリーに対する無効フラグをＯＮにする（ステップＳ２６）。
【００４８】
また、パケット処理部１６は、無効フラグをＯＮに設定後、新規のフローキャッシュエントリーを作成するためにルールテーブル２４を検索し（ステップＳ２７）、検索したルールに従ってアクションテーブル２６を参照する（ステップＳ２８）。このとき、検索がヒットすれば、パケット処理部１６はヒットしたエントリーに従ってパケットを処理する（ステップＳ２９）。また、パケット処理部１６は、パケット処理後、新しいエントリーをフローキャッシュテーブル２８に登録する（ステップＳ３０）。なお、パケット処理部１６は、フローキャッシュテーブルへのエントリーの登録後（ステップＳ３０）、パケットを処理（ステップＳ２９）してもよい。
【００４９】
図５は、フローキャッシュテーブル２８内の無効エントリーを削除する動作を例示するシーケンス図である。図５を参照すると、パケット処理部１６は、フローキャッシュテーブル２８を周期的に検索し、無効フラグがＯＮのエントリーを特定する（ステップＳ４１）。パケット処理部１６は、無効フラグがＯＮのエントリーを特定すると、該当エントリーの削除とフローキャッシュテーブル２８の更新を行う（ステップＳ４２）。
【００５０】
次に、本実施形態のパケット処理装置１０による効果について説明する。ルールテーブル２４の検索はパケット処理によっては複数回発生する。フローキャッシュテーブル２８を用いることにより、複数回のルールテーブル２４検索をバイパスし、一度のフローキャッシュテーブル２８検索によりすべてのアクションを特定することができる。これにより、検索回数を削減でき、パケット処理を高速化することが可能となる。
【００５１】
また、ルールテーブル２４の検索は完全一致検索とは限らない。最長一致検索やマスク検索、範囲指定エントリーの検索を行う場合、ソフトウェア処理ではハードウェア処理と比較して検索に多くの処理時間を要する。フローキャッシュテーブル２８は完全一致検索で実装することができるため、例えば、ハッシュテーブルで実装することが可能である。ハッシュ検索によると、ソフトウェア処理であっても、ハードウェア処理に匹敵する高速な検索が可能となる。このように、フローキャッシュテーブル２８によると、検索の高速化により、パケット処理を高速化することが可能となる。
【００５２】
さらに、本実施形態では、パケット処理部１６がフローキャッシュテーブル２８に対して追加・変更・削除処理を行い、他のプロセスがフローキャッシュテーブル２８にアクセスすることがない。これにより、フローキャッシュテーブル２８をロックレスで実装することができるため、パケット処理部１６がアクセスする際に排他処理により待ち時間が発生しない。したがって、パケット処理部１６(プロセッサ)の空転による無駄なコストが発生せず、パケット処理を高速化することができる。
【００５３】
＜他の実施形態＞
第１の実施形態では、パケット処理部１６がフローキャッシュテーブル２８を無効と判定した場合、該当エントリーの無効フラグをＯＮに設定し、実際の削除処理とそれによるフローキャッシュテーブル２８の更新処理は別途周期的な処理で実施するものとした。
【００５４】
他の実施形態として、パケット処理部１６は、フローキャッシュテーブル２８が無効であると判定した際、該当エントリーを逐次削除処理するようにしてもよい。
【００５５】
また、第１の実施形態では、パケット処理部１６がフローキャッシュテーブル２８を無効と判定した場合、該当エントリーの無効フラグをＯＮに設定し、実際の削除処理とそれによるフローキャッシュテーブル２８の更新処理は別途周期的な処理で実施するものとした。
【００５６】
他の実施形態として、別途、フローキャッシュエントリーリストテーブルを実装する方法も可能である。パケット処理部１６はフローキャッシュテーブル２８にエントリーを追加した際、フローキャッシュエントリーリストテーブルにもエントリーを追加する。パケット処理部１６は該当エントリーを無効と判定した際、フローキャッシュテーブル２８ではなく、フローキャッシュエントリーリストテーブルの該当エントリーに無効フラグを設定する。これにより、周期的な無効エントリーの検索処理時には、フローキャッシュテーブル２８を検索する必要がなく、フローキャッシュエントリーリストテーブルを横断的に順次エントリー参照するだけで、検索なしで無効エントリーを特定することが可能になる。
【００５７】
本発明は、一例として、ＮＦＶ(Network Functions Virtualization)やＳＤＮ（Software-Defined Networking）のようなパケット処理をソフトウェアで実装する必要がある分野に適用することができる。
【００５８】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の態様に係るパケット処理装置のとおりである。
［形態２］
前記ルール制御部は、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
前記パケット処理部は、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
形態１に記載のパケット処理装置。
［形態３］
前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定する
形態２に記載のパケット処理装置。
［形態４］
前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
形態２または３に記載のパケット処理装置。
［形態５］
前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定のタイミングで特定し、特定したポインターを削除する
形態４に記載のパケット処理装置。
［形態６］
前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定の周期で、または、無効化された際に削除する
形態５に記載のパケット処理装置。
［形態７］
前記パケット処理部は、検索したアクションに対するポインターを蓄積するフローキャッシュテーブルと、
前記フローキャッシュテーブルに蓄積したポインターの有効性を示すフラグを蓄積するフラグテーブルと、を有し、
前記蓄積したポインターが無効化されると、無効化されたポインターに対応するフラグを前記フラグテーブルにおいて無効に設定し、前記所定の周期で前記フラグテーブルを参照することにより、無効化されたポインターを特定する
形態６に記載のパケット処理装置。
［形態８］
上記第２の態様に係るパケット処理方法のとおりである。
［形態９］
前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
形態８に記載のパケット処理方法。
［形態１０］
前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定する
形態９に記載のパケット処理方法。
［形態１１］
前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
形態９または１０に記載のパケット処理方法。
［形態１２］
上記第３の態様に係るプログラムのとおりである。
［形態１３］
前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
形態１２に記載のプログラム。
［形態１４］
前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定する
形態１３に記載のプログラム。
［形態１５］
前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
形態１３または１４に記載のプログラム。
【００５９】
なお、上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００６０】
１０    パケット処理装置
１２    ルール制御部
１３    記憶部
１４    共有メモリ
１６    パケット処理部
１８    ローカルメモリ
２４    ルールテーブル
２６    アクションテーブル
２８    フローキャッシュテーブル
【図１】
2015133448.tif 000003
【図２】
2015133448.tif 000004
【図３】
2015133448.tif 000005
【図４】
2015133448.tif 000006
【図５】
2015133448.tif 000007
【国際調査報告】
2015133448.tif 000008
2015133448.tif 000009