(57)【要約】  パターンマッチング装置は、複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリを備えるマルチコアＣＰＵを有するマルチコアプロセッサ環境において動作する。前記共有メモリ上は、検索パターンを備えるパターンテーブルを含む。パターンマッチング装置は、前記複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行する。
2011078108.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリを備えるマルチコアＣＰＵを有するマルチコアプロセッサ環境において、
前記共有メモリ上は、検索パターンを備えるパターンテーブルを含み、
前記複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行する
ことを特徴とするパターンマッチング装置。
【請求項２】
前記パターンテーブルは、ハッシュテーブルとして構成することを特徴とする請求項１に記載のパターンマッチング装置。
【請求項３】
１つのマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
前記マルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスと
を備えたことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項４】
抽出した検索キーを含むパケット受信イベントを生成、発行し、
パケット受信イベントは、前記マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする請求項３に記載のパターンマッチング装置。
【請求項５】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、同一のパターンテーブルが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項６】
抽出した検索キーを含むパケット受信イベントを生成し、
パケット受信イベントは、複数個のマルチコアＣＰＵのうちの１つに対して発行する
ことを特徴とする請求項５に記載のパターンマッチング装置。
【請求項７】
前記パケット受信イベントを受信したマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする請求項６に記載のパターンマッチング装置。
【請求項８】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
各マルチコアＣＰＵ内の複数のプロセッサコアにおけるパターンマッチング結果を収集し、最終的なパターンマッチング結果を決定する最終結果決定ブロックと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリと最終結果決定ブロックを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項９】
抽出した検索キーを含むパケット受信イベントを生成し、
生成したパケット受信イベントは、複数個のマルチコアＣＰＵの全てに対して発行する
ことを特徴とする請求項８に記載のパターンマッチング装置。
【請求項１０】
前記複数個のマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする請求項９に記載のパターンマッチング装置。
【請求項１１】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出する検索キー抽出ブロックと、
抽出した検索キーに対するハッシュ値の算出を行い、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させるハッシュ値計算ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとハッシュ値計算ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項１２】
抽出した検索キーと算出したハッシュ値を含むパケット受信イベントを生成し、
生成したパケット受信イベントは、算出したハッシュ値に対応したエントリ群を保持するサブパターンテーブルを有するマルチコアＣＰＵに対して発行する
ことを特徴とする請求項１１に記載のパターンマッチング装置。
【請求項１３】
前記パケット受信イベントを受信したマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする請求項１２に記載のパターンマッチング装置。
【請求項１４】
複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリから構成されるマルチコアＣＰＵを有するマルチコアプロセッサ環境において、
共有メモリ上に検索パターンを備えるパターンテーブルを構成し、
複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行することを特徴とするパターンマッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサから構成されるマルチプロセッサ環境に関し、特に、複数個のプロセッサとそれらのプロセッサで共有される共有メモリを一ユニットとし、複数のユニットが存在するシステムにおいて、各ユニットにおける共有メモリにパターン管理テーブルを分割して構成し、システム内の複数個のプロセッサを用いて並列にパターンマッチング処理を実行することで、パターンマッチング処理を行うシステムに関する。
【背景技術】
【０００２】
入力された文字列がある文字列（パターン）に一致するかを特定するパターンマッチング処理は、ネットワーク分野においても重要な要素技術であり、例えば、ルータやスイッチ等のネットワーク中継装置において、入力されたパケットのヘッダ情報を用いて、そのパケットがどのフローに属するかを特定するための処理（以下、これをフロー検索処理と呼ぶ）や、パケットのヘッダ情報のみならずパケットペイロード内のデータに対してパターンマッチング処理を行い、よりきめ細やかにフローを特定し、各フローに対するＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃe）の提供や、負荷分散制御等を行うためのＤｅｅｐ  Ｐａｃｋｅｔ  Ｉｎｓｐｅｃｔｉｏｎ（ＤＰＩ）と呼ばれる技術に用いられる。【０００３】
フロー検索処理では、一般的に入力されたパケットのＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ヘッダに定義されている送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル番号に加え、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｃｏｌ）/ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｃｏｌ）ヘッダに定義されている送信ポート番号、宛先ポート番号等のフィールドを用いて特定される一連のパケット列をフローと呼び、例えば、ハッシュ法、又はハッシングと呼ばれる技術を用いてフローの特定を行う。ハッシュ法では、フローの特定を行う上記のようなフィールドの組を検索キーとし、検索キーに対してハッシュ関数と呼ばれる演算を行うことで、検索キーをハッシュ値と呼ばれる特定長のビット列に変換し、得られたハッシュ値に相当するテーブル内のエントリ位置に、検索キーと次のエントリへのポインタを格納したテーブルを用いてフロー検索処理を行う。このようなテーブルをハッシュテーブルと呼び、特にフローを特定する検索キーが格納されているため、フローテーブルと呼ぶこともある。ハッシュ法については、例えば特許文献１に記載されているため詳細については省略するが、図１７にハッシュテーブルの構成例を示す。【０００４】
図１８に１つのみのプロセッサコアをもつ１つのみのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を含む通常のサーバアーキテクチャの概略構成例を示し、本サーバ上でフロー検索処理を行う場合の動作概要について説明する。図１８に示す通常のサーバアーキテクチャの例では、１つのみのプロセッサコアを持つＣＰＵ１１と、ＤＲＡＭ（Ｄｙｎaｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリ６と、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）や送受信ＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ  Ｆｉｒｓｔ−Ｏｕｔ）等を含むパケット送受信ブロック１０が、バス３を通じて接続されている。また、ＣＰＵ１１は、プロセッサコア１１−１とレベル２キャッシュ（Ｌ２キャッシュ）１１−０を含む。なお、ＣＰＵ１１とメインメモリ６とパケット送受信ブロック１０は、Ｎｏｒｔｈ  ＢｒｉｄｇｅやＳｏｕｔｈ  Ｂｒｉｄｇｅと呼ばれるチップセットを通じて接続されている場合もあるが、ここではこれらのチップセットも含めバス３として示している。【０００５】
通常、フローテーブルは大容量であるため、メインメモリ６上に構築される。パケットがパケット送受信ブロック１０で受信されると、ＭＡＣや受信ＦＩＦＯを経由し、例えばＤＭＡ（Ｄｉｒｅｃｔ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ）機能を用いてメインメモリ６上に書き込まれる。また、パケットがパケット送受信ブロック１０で受信されると、パケット送受信ブロック１０がＣＰＵ１１のプロセッサコア１１−１へ割り込み制御をかける、又は、イベントキューにイベントが発行され、プロセッサコア１１−１によるイベントのポーリングが行われること等により、プロセッサコア１１−１はパケットの到着を判断し、メインメモリ６から当該パケットのヘッダ情報を読み出す。続いて、プロセッサコア１１−１は、検索キーである複数のヘッダのフィールドの組に対して、ハッシュ値を導出し、ハッシュ値に対応するフローテーブルのエントリをメインメモリ６から読み出し、検索キーの比較を行う。これらの検索キーが一致している場合、当該パケットはそのエントリに対応するフローに属すると判断する。一致していない場合、そのエントリに格納されているポインタを辿り、次のエントリを読み出し、検索キーとそのエントリ内の検索キーとの比較を行うという処理を繰り返すことで、当該パケットがエントリ内のフローに属しているかを確認するという処理を行う。なお、当該パケットの検索キーがフローテーブル内のエントリと最後まで一致しなかった場合の処理、例えば、新規フローとしてテーブルエントリを登録する等については、個々のシステム仕様に依存するため、ここでは省略する。【０００６】
このようなネットワーク分野におけるパターンマッチング処理、特にフロー検索処理は、入力されたパケット毎に行うため、ネットワークの帯域に見合った高速な検索スループットでこれを実現することが必要である。このため、上記のように、メインメモリ上にフローテーブルを構築し、ＣＰＵによるソフトウェア処理でフロー検索処理を実行した場合、１パケットに対する検索処理あたりアクセス性能の低いメインメモリ上のフローテーブルに複数回のアクセスが必要であることから、処理性能の低下が課題となる。ＣＰＵ内部のキャッシュメモリ、例えば、図１８におけるＬ２キャッシュ１１−０にメインメモリのフローテーブルの一部を保持することで、メインメモリへのアクセスに関わる遅延を削減することが可能である。しかし、ネットワークにおいては多数のフローに属するパケットがほぼランダムに到着するため、このようなフロー検索処理のように処理毎に異なるデータ（フロー検索処理ではテーブルエントリ）を参照する必要がある場合には有効に機能せず、結果的にメインメモリへのアクセスが劇的に減少するとは考えにくく、有効に機能しないことが考えられる。同様に、例えば、特許文献２のように、ＣＰＵに具備されているデータキャッシュとは別に、ハッシュテーブルの一部をキャッシュしたテーブルを用意しても、上記と同様の課題が存在することが考えられる。【０００７】
一方、近年、複数個のプロセッサコアを内蔵したマルチコアＣＰＵ（マルチコアプロセッサ）が登場し、さらにそれらを複数個搭載したサーバも提供されている。例えば、図１９に２つのプロセッサコアをもつ２つのＣＰＵから構成される通常のサーバアーキテクチャの概略構成例を示す。図１９は、図１８に示した構成のうち、ＣＰＵ１１の代わりに２つのプロセッサコアを持つＣＰＵ１２、ＣＰＵ１３が具備された構成である。ここで、ＣＰＵ１２は２つのプロセッサコア１２−１、１２−２とＬ２キャッシュ１２−０を、ＣＰＵ１３は２つのプロセッサコア１３−１、１３−２とＬ２キャッシュ１３−０を含む。このようなサーバでは、プロセッサコアが４つ存在することになり、これらのプロセッサコア間で並列にフロー検索処理を行うことで、図１８に示すような構成のサーバにおいてフロー検索処理を行う場合よりも検索性能が向上する。しかし、フローテーブルはメインメモリに構築されるため、低速なメインメモリへのアクセスが必要である上、複数のプロセッサコアが同一のメインメモリへアクセスするためのアクセス競合の調停等が必要となる。このため、各プロセッサコアを有効に活用することができず、性能面での課題は残る。より一般的に、複数個のプロセッサコアをもつＣＰＵを複数個具備するサーバにおいても同様の課題は存在する。同様に、このようなＣＰＵにおいてもキャッシュメモリは存在するが、上述したような処理毎に異なるデータを参照する必要がある場合の課題は解決されていない。【０００８】
また、特許文献３では、図１９に示すようなマルチコアプロセッサ環境における共有キャッシュのミスヒット率を低減させるためのリプレイスメント制御についての開示があり、特許文献４では、マルチプロセッサ環境における共有メモリに対する排他制御についての開示があり、特許文献５では、マルチコアプロセッサ環境における共有キャッシュに対するプリフェッチ機能についての開示があるが、フロー検索処理のような処理毎に異なるデータを参照する必要がある場合の課題そのものを解決するものではない。さらに、非特許文献１では、最長一致検索（ＬＰＭ：  Ｌｏｎｇｅｓｔ  Ｐｒｅｆｉｘ  Ｍａｔｃｈ）を対象とし、検索キーとなるデータが格納された一部のデータ領域をキャッシュのような高速なアクセス性能を持つメモリ領域に格納し、低速なメモリへのアクセス回数を低減させるような手法について開示されている。【０００９】
特許文献６では、図１が示すように、（複数の）プロセッサ、キャッシュメモリ、メモリ、周辺機器（ペリフェラル）、パケットコントローラがシステム・バスで接続された構成が開示されている（たとえば、第７段落参照）。【００１０】
また、パケットコントローラにて、パケットを受信すると、パケット受信部に構成されているパターンマッチングロジック、およびハッシュ機構によって、予め定義され、パターンマッチングロジック内のレジスタに保持されているパターンと受信パケット内のアドレス等が比較され、当該パケットの受信可否が判定される（たとえば、第９段落参照）。【００１１】
更に、システム内のキャッシュメモリには、受信を許可されたパケットの一部が書き込まれ、引き続きプロセッサにて行われるパケット処理を行うために保持される（たとえば、第１１段落参照）。【００１２】
しかし、上述したように、特許文献６では、パケットコントローラの内部でパターンマッチを行う機能があり、そこでパターンマッチを行う。パターンマッチが各プロセッサにおいて行われるようなことはない。【００１３】
また、上述したように、特許文献６のキャッシュメモリには、パターンマッチングにより受信を許可されたパケットデータの一部が書き込まれ、プロセッサによるパケット処理に利用される。キャッシュメモリに、パターンマッチの対象となるパターン（フロー情報）が書き込まれており、フロー管理テーブルとして利用するようなことはない。【００１４】
特許文献７の図７には、複数のマイクロエンジン（プロセッサ）、それらで共有されるメモリ（ＳＲＡＭ、ＤＲＡＭ）、パケット受信部等がバスで接続された構成（たとえば、第５０段落参照等）が開示されている。各マイクロエンジンには、ローカルメモリと計算コア（プロセッサコア）が含まれる。【００１５】
また、共有メモリ（ＳＲＡＭ）で保持されたフローの状態情報（パターン、パターンマッチで利用する状態遷移情報）を、マイクロエンジン内のローカルメモリに読み出し、マイクロエンジン内のプロセッサコアにてパターンマッチ処理が行われる（たとえば、第５５段落参照）。【００１６】
しかし、上述したように、特許文献７では、複数のプロセッサで共有して利用するＳＲＡＭ、ＤＲＡＭ等のメインメモリは存在するが、それらよりもより高速にアクセスできるキャッシュのようなメモリとしては、各プロセッサに対応するローカルメモリしか存在せず、複数のプロセッサで共有できるキャッシュメモリは存在しない。複数のプロセッサで共有されるメインメモリ（ＳＲＡＭ、ＤＲＡＭ等）に加えて、特定の数のプロセッサで共有するキャッシュメモリが存在するようなことはない。【００１７】
また、上述したように、特許文献７のパターンマッチ処理では、パターン等の情報は複数のプロセッサで共有利用するメインメモリ上で保持されており、キャッシュメモリ（マイクロエンジン内のローカルメモリ）には、対象となるパケットのパターンマッチ処理を行う間だけメインメモリから情報を読み出し、利用する。キャッシュメモリに、パターンマッチの対象となるパターン（フロー情報）が書き込まれており、キャッシュメモリがフロー管理テーブルとして直接利用されるようなことはない。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開平１１−５３１９９号公報
【特許文献２】特表２００２−５１１７０３号公報
【特許文献３】特開２００２−３７３１１５号公報
【特許文献４】特開２００８−２９３３６８号公報
【特許文献５】特開２００７−２０７２４０号公報
【特許文献６】特表２００７−５２５０３７号公報
【特許文献７】特表２００８−５４４７２８号公報
【非特許文献】
【００１９】
【非特許文献１】Ｂｕｔｌｅｒ  Ｌａｍｐｓｏｎ、  Ｖｅｎｋａｔａｃｈａｒｙ  Ｓｒｉｎｉｖａｓａｎ、Ｇｅｏｒｇｅ  Ｖａｒｇｈｅｓｅ、「ＩＰ  Ｌｏｏｋｕｐｓ  Ｕｓｉｎｇ  Ｍｕｌｔｉｗａｙ  ａｎｄ  Ｍｕｌｔｉｃｏｌｕｍｎ  Ｓｅａｒｃｈ」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、ｖｏｌ．７、Ｎｏ．３、１９９９年、第３２４−３３４頁
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上記のようなネットワーク分野におけるマルチプロセッサ環境を用いたパターンマッチング処理では、ネットワークの帯域に見合った高速な検索スループットでこれを実現することが必要であるが、それを満たす高い処理性能を提供できないことに課題がある。【００２１】
その理由は、フローテーブルがアクセス性能の低いメインメモリ上に構築され、メインメモリ上のフローテーブルに複数回のアクセスが必要であるためである。また、メインメモリよりも高速にアクセス可能なキャッシュメモリのようなメモリにフローテーブルの一部をキャッシュし、メインメモリへのアクセス回数を削減しようとしても、到着するパケットが属するフローがランダムな場合には、到着するパケット間での依存性が少なく、キャッシュしたフローテーブルの一部のエントリにマッチする可能性が小さいため、メインメモリへのアクセス回数削減の効果が少ないことにある。【００２２】
本発明の目的は、ネットワーク帯域に見合った高速な検索性能を有するパターンマッチング処理を実現できるパターンマッチングシステムを提供することにある。
【課題を解決するための手段】
【００２３】
本発明の第１、第２のパターンマッチング装置は、複数個のプロセッサコアとそれらのプロセッサコア間で共有される共有メモリを有する１個、又は複数個のマルチコアＣＰＵ（図１の１、図６の１、２、・・・、Ｍ）と、パケットの送受信を行うパケット送受信ブロック（図１の５、図６の５）と、受信したパケットからフロー検索処理における検索キーとなるヘッダ情報を抽出すると共に、パケット受信イベントの生成と発行、及びパケットをメインメモリへ書き込む検索キー抽出ブロック（図１の４、図６の４）と、パケット受信イベントや必要に応じてパケットそのものが書き込まれるＤＲＡＭ等のメインメモリ（図１の６、図６の６）と、マルチコアＣＰＵ、検索キー抽出ブロック、メインメモリをそれぞれ接続するバス（図１の３、図６の３）とを有する。また、ハッシュテーブルをベースとしたパターンテーブルは、マルチコアＣＰＵ内の共有メモリにおいて構成される。このような構成を採用し、検索キー抽出ブロックにより、予めパケットのヘッダ情報から検索キーとなるフィールドの組を抽出し、それをプロセッサコアに通知すると共に、メインメモリよりも高速なアクセスが可能な共有メモリ内のパターンテーブルを用いてパターンマッチング処理を行うことにより、本発明の目的を達成することができる。【００２４】
また、本発明の第３のパターンマッチング装置は、第２のパターンマッチング装置に加え、最終結果決定ブロック（図９の７）を有する。また、各マルチコアＣＰＵ内は、その共有メモリ上に、元の１つのパターンテーブルを分割したサブパターンテーブルを持つ。このような構成を採用し、検索キー抽出ブロックにより、予めパケットのヘッダ情報から検索キーとなるフィールドの組を抽出し、それを各マルチコアＣＰＵの１つのプロセッサコアに通知し、分散してパターンマッチング処理を行うと共に、メインメモリよりも高速なアクセスが可能な共有メモリ内のパターンテーブルを用いてパターンマッチング処理を行うことにより、本発明の目的を達成することができる。【００２５】
さらに、本発明の第４のパターンマッチング装置は、第３のパターンマッチング装置における最終結果決定ブロック（図９の７）を除き、ハッシュ値計算ブロック（図１３の９）を加えた構成である。このような構成を採用し、検索キー抽出ブロック（図１３の８）により、予めパケットのヘッダ情報から検索キーとなるフィールドの組を抽出し、さらに、ハッシュ値計算ブロック（図１３の９）において、検索キーに対するハッシュ値を算出することで、当該ハッシュ値に対応するパターンエントリ群が保持されているパターンテーブルを有するマルチコアＣＰＵを特定することができ、当該マルチコアＣＰＵの１つのプロセッサコアにおいてパターンマッチング処理を行うと共に、メインメモリよりも高速なアクセスが可能な共有メモリ内のパターンテーブルを用いてパターンマッチング処理を行うことにより、本発明の目的を達成することができる。
【発明の効果】
【００２６】
本発明によれば、ネットワーク帯域に見合った高速な検索性能を有するパターンマッチング処理を実現できる。
【図面の簡単な説明】
【００２７】
【図１】本発明の第１の実施の形態による装置の構成を示すブロック図である。
【図２】本発明の第１の実施による装置の動作を示す流れ図である。
【図３】図２におけるステップＡ４を示す流れ図である。
【図４】フローテーブルの一例を示す図である。
【図５】本発明の第１の実施による装置の動作概要を示す図である。
【図６】本発明の第２の実施の形態による装置の構成を示すブロック図である。
【図７】本発明の第２の実施による装置の動作を示す流れ図である。
【図８】本発明の第２の実施による装置の動作概要を示す図である。
【図９】本発明の第３の実施の形態による装置の構成を示すブロック図である。
【図１０】本発明の第３の実施の形態におけるフローテーブルの分割の一例を示す図である。
【図１１】本発明の第３の実施による装置の動作を示す流れ図である。
【図１２】本発明の第３の実施による装置の動作概要を示す図である。
【図１３】本発明の第４の実施の形態による装置の構成を示すブロック図である。
【図１４】本発明の第４の実施による装置の動作を示す流れ図である。
【図１５】図１４におけるステップＡ１３を示す流れ図である。
【図１６】本発明の第４の実施による装置の動作概要を示す図である。
【図１７】ハッシュテーブルの構成例である。
【図１８】通常の１つのＣＰＵ（シングルコア）を持つサーバにおけるソフトウェアによるフロー検索処理のアーキテクチャ例である。
【図１９】通常の２つのＣＰＵ（デュアルコア）を持つサーバにおけるソフトウェアによるフロー検索処理のアーキテクチャ例である。
【発明を実施するための形態】
【００２８】
以下、図面を参照して本発明を実施するための形態について詳細に説明する。
＜実施の形態１＞
図１は、本発明の第１の実施の形態の構成を示すブロック図である。図１を参照すると、本発明の第１の実施の形態は、マルチコアＣＰＵ１と、パケットの送受信を行うパケット送受信ブロック５と、受信したパケットからフロー検索処理における検索キーとなるヘッダ情報を抽出すると共に、パケット受信イベントの生成と発行、及びパケットをメインメモリへ書き込む検索キー抽出ブロック４と、パケット受信イベントや必要に応じてパケットそのものが書き込まれるＤＲＡＭ等のメインメモリ６と、マルチコアＣＰＵ１、検索キー抽出ブロック４、メインメモリ６を相互に接続するバス３とを含む。
【００２９】
マルチコアＣＰＵ１は、Ｎ個のプロセッサコア１−１、１−２、・・・、１−Ｎと、上記Ｎ個のプロセッサコアで共有される共有メモリ１−０を含む。また、共有メモリ１−０には、ハッシュテーブルとして構成されたフローテーブルの全てを保持している。なお、本共有メモリがデータキャッシュとして利用されている場合、本フローテーブルはデータキャッシュとは論理的に分離された領域に保持されるものとする。
【００３０】
パケット送受信ブロック５は、ネットワークがＥｔｈｅｒｎｅｔ（登録商標）である場合には、ＭＡＣの機能を持ち、入力されたビットストリームをＥｈｅｒｎｅｔ（登録商標）フレームとして整形した後に、検索キー抽出ブロック４へ出力する。このようなパケット送受信ブロック５は、当業者にとってよく知られているため、その詳細な構成は省略する。
【００３１】
検索キー抽出ブロック４は、パケット送受信ブロック５から受信したパケットを受け取り、フロー検索処理における検索キーとなるヘッダ情報を抽出する。抽出した検索キーの情報を含むパケット受信イベントを生成し、マルチコアＣＰＵ１に対するイベントキューへ書き込むと共に、検索キーを抽出した後のパケットをメインメモリへ書き込む。本書き込み処理には、一般的にＤＭＡ機能が用いられる。なお、パケット送信時には、本ブロックはメインメモリからパケットデータを読み出し、そのままパケット送受信ブロック５へ出力する。
【００３２】
なお、図１では、マルチコアＣＰＵ１、検索キー抽出ブロック４、メインメモリ６をバス３によってバス接続している形態であるが、本接続形態はサーバ等に備えられたＮｏｒｔｈ  ＢｒｉｄｇｅやＳｏｕｔｈ  Ｂｒｉｄｇｅと呼ばれるチップセットを通じて接続される形態や、クロスバー、リングバスの形態でも構わない。また、本実施の形態は、サーバ等のマザーボード上で構成しても良いし、メインメモリ６を除いた全てを１つのＳｏＣ（Ｓｙｓｔｅｍ−ｏｎ−ａ−Ｃｈｉｐ）として、１つのチップ上に構成しても良い。
【００３３】
次に、図１、及び図２の流れ図を参照して、本発明の第１の実施の形態の動作について詳細に説明する。
【００３４】
ネットワークから入力されたパケットは、パケット送受信ブロック５で受信する。パケット送受信ブロック５で受信したパケットは、例えばネットワークがＥｔｈｅｒｎｅｔ（登録商標）である場合には、Ｅｈｅｒｎｅｔ（登録商標）フレーム（本明細書では、これらを総じてパケットと呼ぶ）として整形した後に、検索キー抽出ブロック４に出力する（ステップＡ１）。
【００３５】
検索キー抽出ブロック４は、パケット送受信ブロック５からパケットを受け取ると、パケットのヘッダ情報のうち、フロー検索処理における検索キーとして、予め決められた任意のフィールドを抜き出し、パケットに装置内で一意に識別できる識別子を付与し、検索キー抽出ブロック４に含まれるＦＩＦＯに書き込む（ステップＡ２）。ここで、検索キーとして用いるパケットヘッダのフィールドとしては、例えば、ＩＰヘッダに定義されている送信元ＩＰアドレス（３２ｂｉｔｓ）、宛先ＩＰアドレス（３２ｂｉｔｓ）、プロトコル番号（８ｂｉｔｓ）、ＴＣＰ/ＵＤＰヘッダに定義されている送信ポート番号（１６ｂｉｔｓ）、宛先ポート番号（１６ｂｉｔｓ）の５つのフィールドの組が用いられ、この場合の検索キーの長さは、１０４ｂｉｔｓ（＝１３ｂｙｔｅｓ）となる。
【００３６】
次に、検索キー抽出ブロック４は、パケット受信をマルチコアＣＰＵ１に通知するためのイベントを生成、発行し、イベントキューへ書き込むと共に、対応するパケットをメインメモリ６に書き込む（ステップＡ３）。ここで生成するイベントには、抽出した検索キーの情報と、対応するパケットの識別子を含まれれば良く、イベントキューが例えばメインメモリ６に構成されている場合は、メインメモリ６のイベントキューに書き込む。なお、イベントキューがメインメモリ６に構成されている場合、マルチコアＣＰＵ１に対するイベントキューの領域と、パケットデータを書き込む領域は論理的に分離されており、そのベースとなるアドレスはマルチコアＣＰＵ１にとって既知であるものとする。
【００３７】
一方、マルチコアＣＰＵ１は、イベントキューにイベントが存在するかをポーリング（ｐｏｌｌｉｎｇ）によって監視しており、イベントキューにイベントが存在すれば、その先頭のイベントを読み出し、特定のプロセッサコアによってフロー検索処理を行う（ステップＡ４）。
【００３８】
図３は、ステップＡ４のより詳細な動作を説明するための流れ図である。
【００３９】
マルチコアＣＰＵ１は、イベントキューにイベントが存在すると、その先頭のイベントを読み出し、特定のプロセッサコアに割り当てる（ステップＢ１）。ここで、マルチコアＣＰＵ１のように複数個のプロセッサコアをもつＣＰＵでは、ポーリングに特化した処理を特定のプロセッサコア、例えば、プロセッサコア１−１が行い、イベントキューからイベントを読み出した後、処理を行っていない他の空き状態のプロセッサコアに割り当てるという手法が考えられる。また、各プロセッサコアがそれぞれイベントキューに対してポーリングを行うことでイベントを引き取る手法もある。後者の場合は、各プロセッサコアが同じイベントキューが存在するメモリ領域に対してアクセスを行うため、これらのプロセッサコア間での調停が必要となる。本実施形態では、このようなイベントの読み出し処理については、既存の手法を用いることとし、各プロセッサコア（特定のプロセッサコアがポーリングに特化した処理を行う場合には、これを除くプロセッサコア）に平均的にイベントの割り当てが行われれば良い。以下では、簡単化のため、イベントが割り当たったプロセッサコアをプロセッサコア１−ｋ（ｋ＝１、・・・、Ｎ）とし、プロセッサコア１−ｋの処理について説明する。
【００４０】
イベントが割り当たったプロセッサコア１−ｋは、イベント内に格納されている検索キーに対して、予め設定されたハッシュ関数を用いてハッシュ値を計算する（ステップＢ２）。ここで、ハッシュ関数やハッシュ値は、当業者にとってよく知られているため、その詳細な説明は省略する。
【００４１】
続いて、プロセッサコア１−ｋは、算出したハッシュ値をアドレス値として（ステップＢ３）、フローテーブルからエントリを読み出す（ステップＢ４）。図４に、共有メモリ１−０に構成されているフローテーブルの一例を示す。フローテーブルはハッシュテーブルをベースに構成されており、同じハッシュ値をもつ複数のエントリは双方向リストで接続されている。１つのエントリは検索キーと、フローを特定するためのフローＩＤと、リストの次のエントリへのポインタとなるアドレス値と、リストの前のエントリへのポインタを保持している。但し、図４で示すエントリの検索キー、フローＩＤ、次のエントリへのポインタ、前のエントリへのポインタのデータ長の合計が共有メモリ１−０のワード長よりも長い場合には、連続する複数のワードを用いて１つのエントリが構成されるものとし、例えば、物理アドレスのビット長の下位ビットを無視する等、アドレス値は各エントリの先頭ワードを示す論理的なアドレス値を意味するものとする。エントリは、基本的に空き領域に追加され、双方向リストによって管理される。一方、既にエントリが管理されているアドレス値、つまりハッシュ値にエントリが追加される場合は、当該エントリのアドレス値をハッシュ値とするエントリの優先度の方が高く、既に管理されているエントリは別の空き領域に移動させるものとする。なお、図４はあくまで一例であり、衝突の発生を考慮して、エントリの先頭ワードを示す論理的なアドレス空間よりも小さい範囲でハッシュ値を計算するようにしても良いし、他の既存のハッシュテーブルの構成に従ってフローテーブルを構成しても構わない。また、エントリの格納場所の移動が発生しないようなフローテーブルを構成した場合には、フローを特定するフローＩＤにアドレス値を用いることができるため、フローＩＤをエントリ内に保持する必要はない。
【００４２】
フローテーブルからエントリを読み出したプロセッサコア１−ｋは、読み出したエントリの検索キーと、当該イベントの検索キーが一致するかを判断し（ステップＢ５）、一致すればエントリ内に保持しているフローＩＤを取得し（ステップＢ６）、フロー検索処理（ステップＡ４）を終了する。一致しない場合、リンクで接続された次のエントリが存在するかを確認し（ステップＢ７）、次のエントリが存在する場合には、当該エントリの次のポインタをアドレス値とし（ステップＢ８）、次のエントリを読み出す（ステップＢ４）という処理を繰り返すことでフロー検索処理を行う。また、次のエントリが存在しない場合には、該当するフローは登録されていないため、結果としてフロー未登録と判断し（ステップＢ９）、フロー検索処理（ステップＡ４）を終了する。
【００４３】
最後に、該当するプロセッサコア１−ｋは、フロー検索処理（ステップＡ４）で得た結果を出力する（ステップＡ５）。ここで、一般的に、フロー検索処理は、ＱｏＳ処理のような、パケットが属するフローを識別し、そのフローに対する個別の処理を行うために行われるため、これらの処理を行う処理ブロックや、ＣＰＵ等がバス３を経由して、又は何らかの通信手段によって備わっている場合が想定される。本実施の形態では、フロー検索処理に焦点を当てているため、これらの処理ブロックについては省略しているが、ステップＡ５における結果出力先としては、このようなフロー毎に個別の処理を行わせる処理ブロックへ出力することを想定する。なお、上記では、一致する検索キーを持つエントリが無ければ、フロー未登録と判断して処理を終了していたが、当該フローを新規フローとして登録する処理を行っても良い。同様に、既にエントリとして登録されているフローの削除を行うことも可能であるが、これらの処理は、フローテーブルであるハッシュテーブルの構成に大きく依存するため、それぞれの詳細については、省略する。
【００４４】
さらに、そのようなフロー毎に個別の処理を行う処理ブロックで何らかの処理を行った後、当該パケットを送信する場合の処理については、検索キー抽出ブロック４がメインメモリ６からパケットを読み出し、読み出したパケットデータをパケット送受信ブロック５に出力し、パケットデータを受け取ったパケット送受信ブロック５がパケットを送信することを想定するが、本実施形態ではフロー検索処理に着目しているため、詳細は省略する。
【００４５】
或いは、本実施の形態では、パケットそのものをパケット送受信ブロック５にて、ネットワークから受信する形態であったが、本実施の形態で示したフロー検索装置に対して、パケットヘッダのみが入力される場合も想定される。この場合、パケット送受信ブロック５が、外部から入力されたパケットヘッダを受信し、それを検索キー抽出ブロック４へ出力する。パケットヘッダを受け取った検索キー抽出ブロック４は、パケットヘッダから検索キーとなるフィールドの組を抽出し、イベントを生成、発行する。この場合、パケットのペイロードデータは受信していないため、メインメモリ６へのパケットデータの書き込みは不要となる。
【００４６】
さらに、本実施の形態では、マルチコアＣＰＵ１に対するイベントキューは、メインメモリ６において構成されることを想定したが、本イベントキューは、マルチコアＣＰＵ１内の共有メモリ１−０において、フローテーブルとは論理的に分離された領域に構成し、検索キー抽出ブロック４から直接共有メモリ１−０内のイベントキューへイベントを書き込んでも構わないし、検索キー抽出ブロック内の特定内のメモリ、レジスタを用いて構成しても構わない。いずれにせよ、マルチコアＣＰＵ１から見ることのできるアドレス空間上で特定できる領域であれば問題無い。
【００４７】
最後に、上記で説明した本実施の形態における処理概要を、図５を用いて説明する。本実施の形態を用いたフロー検索処理、図５に示すように、パケットｐｋｔ１、ｐｋｔ２、・・・が到着すると、順に検索キーＫｅｙ＃１、Ｋｅｙ＃２、・・・を抽出し、それぞれの検索キーをマルチコアＣＰＵ内の複数のプロセッサコアへ割り当て、フロー検索処理を行う。ここでマルチコアＣＰＵ内の複数のプロセッサコアへの割り当て方式は、例えばラウンドロビン（Ｒｏｕｎｄ−Ｒｏｂｉｎ）のような手法によって、順次割り当てていく方法が考えられるが、これに限定されるものではない。
【００４８】
次に、本発明の第１の実施の形態の作用効果について説明する。
【００４９】
上記のように、本実施の形態では、検索キー抽出ブロックにより、予めパケットのヘッダ情報から検索キーとなるフィールドの組を抽出し、それをプロセッサコアに通知することにより、メインメモリに格納されるパケットヘッダを読み出す必要が無いことから、フロー検索の処理性能を向上できる。
【００５０】
また、本実施の形態では、フローテーブルをマルチコアＣＰＵ内の複数のプロセッサコアで共有する共有メモリ上で構成することにより、ＤＲＡＭ等のメインメモリ上にフローテーブルを構成した場合よりも、エントリの読み出しにかかるアクセスレイテンシが大幅に低減されるため、フロー検索処理に関わる処理性能を向上させることが可能となる。
【００５１】
以上のことから、ネットワーク帯域に見合った高速な検索性能を有するパターンマッチング処理を実現できるパターンマッチングシステムを提供することが可能となる。
【００５２】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
＜実施の形態２＞
図６は、本発明の第２の実施の形態の構成を示すブロック図である。図６を参照すると、本発明の第２の実施の形態は、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭと、パケットの送受信を行うパケット送受信ブロック５と、受信したパケットからフロー検索処理における検索キーとなるヘッダ情報を抽出すると共に、パケット受信イベントの生成と発行、及びパケットをメインメモリへ書き込む検索キー抽出ブロック４と、パケット受信イベントや必要に応じてパケットそのものが書き込まれるＤＲＡＭ等のメインメモリ６と、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、検索キー抽出ブロック４、メインメモリ６をそれぞれ接続するバス３とを含む。本実施の形態は、図１に示した前記第１の実施の形態に、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭを加えたものであり、その他は前記第１の実施の形態と同じである。
【００５３】
マルチコアＣＰＵ２は、マルチコアＣＰＵ１と同様の形態であり、Ｎ個のプロセッサコア２−１、２−２、・・・、２−Ｎと、上記Ｎ個のプロセッサコアで共有される共有メモリ２−０を備え、共有メモリ２−０には、ハッシュテーブルとして構成されたフローテーブルを保持している。なお、このような形態は他のマルチコアＣＰＵについても同じであり、各マルチコアＣＰＵ内の共有メモリ内に構成されるフローテーブルも、全て同じフローテーブルが構成される。なお、本共有メモリがデータキャッシュとして利用されている場合、本フローテーブルはデータキャッシュとは論理的に分離された領域に保持されるものとする。
【００５４】
なお、図６に示すように、本実施の形態は、第１の実施の形態と同様、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、検索キー抽出ブロック４、メインメモリ６をバス３によってバス接続している形態であるが、本接続形態はサーバ等に備えられたＮｏｒｔｈ  ＢｒｉｄｇｅやＳｏｕｔｈ  Ｂｒｉｄｇｅと呼ばれるチップセットを通じて接続される形態や、クロスバー、リングバスの形態でも構わない。また、本実施の形態は、サーバ等のマザーボード上で構成しても良いし、メインメモリ６を除いた全てを１つのＳｏＣとして、１つのチップ上に構成しても良い。
【００５５】
次に、図６、及び図７の流れ図を参照して、本発明の第２の実施の形態の動作について詳細に説明する。
【００５６】
図７の流れ図は、第１の実施の形態の流れ図を変更したものであり、ステップＡ３をステップＡ６に、ステップＡ５をステップＡ７に置き換えたものである。その他のステップについては、第１の実施の形態と同様であるため、詳細な説明は省略する。
【００５７】
パケット送受信ブロック５（ステップＡ１）を経由して、検索キー抽出ブロック４は、ネットワークから入力されたパケットを受け取り、検索キーの抽出等のステップＡ２に対する処理を行う。
【００５８】
次に、検索キー抽出ブロック４は、パケット受信を複数のマルチコアＣＰＵのうちの１つに通知するためのイベントを生成、発行し、イベントキューへ書き込むと共に、対応するパケットをメインメモリ６に書き込む（ステップＡ６）。ここで、生成するイベントには、第１の実施の形態と同様、抽出した検索キーの情報と当該パケットの識別子を含まれれば良い。また、イベントキューが例えばメインメモリ６に構成されている場合は、メインメモリ６のイベントキューに書き込むが、各マルチコアＣＰＵに対するイベントキューは、それぞれのマルチコアＣＰＵのイベントキューの領域と、パケットデータを書き込む領域が論理的に分離されており、各マルチコアＣＰＵに対するイベントキューの領域のベースアドレスは、それぞれのマルチコアＣＰＵにとって既知であるものとする。イベントの発行は、複数のマルチコアＣＰＵのうちの１つに対してのみ行われ、イベントを発行するマルチコアＣＰＵの選択は、例えば、フロー検索処理を各マルチコアＣＰＵに対して平滑化して行うために、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、マルチコアＣＰＵ１、・・・のように、Ｒｏｕｎｄ−Ｒｏｂｉｎの手法を用いる方法が考えられるが、これに限定されるものではない。
【００５９】
一方、Ｍ個のマルチコアＣＰＵは、それぞれ自身のイベントキューにイベントが存在するかをポーリング（ｐｏｌｌｉｎｇ）によって監視しており、イベントキューにイベントが存在すれば、その先頭のイベントを読み出し、自身の持つ特定のプロセッサコアによってフロー検索処理を行う（ステップＡ４）。ここで、ステップＡ４は、それぞれのマルチコアＣＰＵが独立に行う処理となり、それぞれの処理の内容は、第１の実施の形態と同様であるため、ここでは詳細な説明を省略する。
【００６０】
最後に、実際のフロー検索処理を行った各マルチコアＣＰＵ内のプロセッサコアは、そこで得た結果を出力する（ステップＡ７）。第１の実施の形態では、１つのマルチコアＣＰＵ内の複数のプロセッサコアがこの処理を行っていたが、ここでは、複数のマルチコアＣＰＵ内の複数のプロセッサコアのうち、実際にフロー検索処理を行ったプロセッサコアが結果の出力を行う点で、第１の実施の形態におけるステップＡ５と異なる。その他のステップＡ７の処理内容については、ステップＡ５と同じであるため、詳細は省略する。
【００６１】
なお、本実施の形態では、各マルチコアＣＰＵ内の共有メモリに構成されるフローテーブルは、全てのマルチコアＣＰＵにおいて同一の内容である。このため、もし、未登録フローを新規フローとして登録する処理を行う場合、あるマルチコアＣＰＵ内のプロセッサコアにおいて更新したフローテーブルの内容を、他のマルチコアＣＰＵ内のフローテーブルに対しても更新作業を行う必要がある。
【００６２】
また、本実施の形態では、パケットそのものをパケット送受信ブロック５にて、ネットワークから受信する形態であったが、パケットヘッダのみが入力される場合の処理についても第１の実施の形態と同様であり、イベントキューの構成箇所（メインメモリ６、各マルチコアＣＰＵ内の共有メモリ、検索キー抽出ブロック４内の特定内のメモリ、レジスタ等）についても、第１の実施の形態と同様であるため、詳細は省略する。
【００６３】
最後に、上記で説明した本実施の形態における処理概要を、図８を用いて説明する。図８に示すように、本実施の形態を用いたフロー検索処理は、パケットｐｋｔ１、ｐｋｔ２、・・・が到着すると、順に検索キーＫｅｙ＃１、Ｋｅｙ＃２、・・・を抽出し、各検索キーを複数個あるマルチコアＣＰＵのうちの１つへ送出する。送出された各検索キーは、それぞれのマルチコアＣＰＵ内の複数のプロセッサコアのうちの１つに割り当て、それぞれのマルチコアＣＰＵ内のプロセッサコアによってフロー検索処理を行うことになる。ここで、各マルチコアＣＰＵ内の複数のプロセッサコアへの割り当て方法は、例えばＲｏｕｎｄ−Ｒｏｂｉｎのような手法を用いることが考えられるが、これに限定されるものではない。
【００６４】
次に、本発明の第２の実施の形態の作用効果について説明する。
【００６５】
上記のように、本実施の形態では、第１の実施の形態における作用効果に加えて、マルチコアＣＰＵが複数個あり、それぞれのマルチコアＣＰＵに対して、フロー検索処理を分散させて行うことより、増加したマルチコアＣＰＵ分に応じてより一層フロー検索の処理性能を向上できる。また、複数個のマルチコアＣＰＵに対して分散処理が可能となるので、１つのマルチコアＣＰＵ内の複数個のプロセッサコア間における共有メモリへのアクセス競合の頻度も低下し、より効率的なフロー検索処理が可能となる。
【００６６】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
＜実施の形態３＞
図９は、本発明の第３の実施の形態の構成を示すブロック図である。図９を参照すると、本発明の第３の実施の形態は、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭと、パケットの送受信を行うパケット送受信ブロック５と、受信したパケットからフロー検索処理における検索キーとなるヘッダ情報を抽出すると共に、パケット受信イベントの生成と発行、及びパケットをメインメモリへ書き込む検索キー抽出ブロック４と、複数のマルチコアＣＰＵにおける個別のフロー検索処理の結果を収集し、最終的なフロー検索処理結果を選択する最終結果決定ブロック７と、パケット受信イベントや必要に応じてパケットそのものが書き込まれるＤＲＡＭ等のメインメモリ６と、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、検索キー抽出ブロック４、メインメモリ６、最終結果決定ブロック７をそれぞれ接続するバス３とを含む。本実施の形態は、図６に示した前記第２の実施の形態に、最終結果決定ブロック７を加えたものであり、その他は前記第２の実施の形態と同じである。
【００６７】
第２の実施の形態では、各マルチコアＣＰＵ内の共有メモリには、全て同一のフローテーブルが構成されていたが、本実施の形態では、元のフローテーブルをＭ個に分割したうちの１つのフローテーブルが構成される。なお、本共有メモリがデータキャッシュとして利用されている場合、本フローテーブルはデータキャッシュとは論理的に分離された領域に保持されるものとする。図１０に、本実施の形態におけるフローテーブルの分割の一例を示す図を示す。図１０に示すように、本実施の形態では、元の１つのフローテーブルをＭ個に分割し、それぞれのサブフローテーブルｋ（ｋ＝１、・・・、Ｍ）を、マルチコアＣＰＵｋ（ｋ＝１、・・・、Ｍ）内の共有メモリ上に構成する。各サブフローテーブルは、基本的には第１、第２の実施例と同様、ハッシュテーブルをベースとしたフローテーブルであるので、各エントリの内容等についての説明は省略するが、各サブフローテーブルは、そのテーブルだけで完全に独立して構成される。つまり、１つのサブフローテーブルに割り当てられたハッシュ値に対するフローは、同一サブフローテーブル内の空きエントリ領域に格納される。このため、衝突の発生を考慮して、エントリの先頭ワードを示す論理的なアドレス空間よりも小さい範囲でハッシュ値を計算するようにしていた場合には、各サブフローテーブルにおいて、上記が成り立つように構成する必要がある。補足すると以下のようになる。
【００６８】
例えば、元のフローテーブルにおいて衝突の発生を考慮し、エントリの先頭ワードを示す論理的なアドレス空間よりも小さい範囲でハッシュ値を計算するようにし、ハッシュ値によって特定できない領域のエントリがアドレス値の大きな領域に位置していた場合、このテーブルをサブフローテーブルに分割すると、ハッシュ値によって特定できないエントリ領域がＭ番目のサブフローテーブル等に偏ってしまうことになる。この場合、ハッシュ値によって特定できるエントリ領域しか持たないサブフローテーブルでは、衝突が多発することになり、逆にハッシュ値によって特定できないエントリ領域を多く持つ領域や、又は特定できないエントリ領域しか持たないサブフローテーブルでは、そのエントリ領域を有効に使い切れず、効率的なフローテーブルを構成することができない。このため、サブフローテーブル単位で衝突を考慮したエントリ領域を確保しておく必要がある。
【００６９】
なお、図９に示すように、本実施形態は、第１、第２の実施の形態と同様、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、検索キー抽出ブロック４、メインメモリ６、最終結果決定ブロック７をバス３によってバス接続している形態であるが、本接続形態はサーバ等に備えられたＮｏｒｔｈ  ＢｒｉｄｇｅやＳｏｕｔｈ  Ｂｒｉｄｇｅと呼ばれるチップセットを通じて接続される形態や、クロスバー、リングバスの形態でも構わない。また、本実施の形態は、サーバ等のマザーボード上で構成しても良いし、メインメモリ６を除いた全てを１つのＳｏＣとして、１つのチップ上に構成しても良い。
【００７０】
次に、図９、及び図１１の流れ図を参照して、本発明の第３の実施の形態の動作について詳細に説明する。
【００７１】
図１１の流れ図は、図７に示す第２の実施の形態の流れ図を変更したものであり、ステップＡ６をステップＡ８に、ステップＡ７をステップＡ１０に置き換え、フロー検索処理（ステップＡ４）と結果出力ステップ（ステップＡ１０）の間に最終結果決定ステップ（ステップＡ９）を追加したものである。その他のステップについては、第１、第２の実施の形態と同様であるため、詳細な説明は省略する。
【００７２】
パケット送受信ブロック５（ステップＡ１）を経由して、検索キー抽出ブロック４は、ネットワークから入力されたパケットを受け取り、検索キーの抽出等のステップＡ２に対する処理を行う。
【００７３】
次に、検索キー抽出ブロック４は、パケット受信を複数のマルチコアＣＰＵの全てに通知するためのイベントを生成、発行し、イベントキューへ書き込むと共に、対応するパケットをメインメモリ６に書き込む（ステップＡ８）。ここで、生成するイベントの情報や、各マルチコアＣＰＵに対するイベントキューについては、第２の実施の形態と同様であるため、詳細は省略する。
【００７４】
一方、Ｍ個のマルチコアＣＰＵは、それぞれ自身のイベントキューにイベントが存在するかをポーリング（ｐｏｌｌｉｎｇ）によって監視しており、イベントキューにイベントが存在すれば、その先頭のイベントを読み出し、自身の持つ特定のプロセッサコアによってフロー検索処理を行う（ステップＡ４）。ここで、ステップＡ４は、それぞれのマルチコアＣＰＵが独立に行う処理となり、それぞれの処理の内容は、第１、第２の実施の形態と同様であるため、ここでは詳細な説明を省略する。
【００７５】
各マルチコアＣＰＵ内の複数のプロセッサコアのうち、フロー検索処理を行ったプロセッサコアは、そこで得た結果と、処理を行ったパケットを識別する識別子を最終結果決定ブロック７に出力する。Ｍ個のマルチコアＣＰＵがフロー検索処理を行った同一パケットに対する検索結果が全て（Ｍ個）揃うと、最終結果決定ブロック７は、そのうちフローＩＤを特定できた結果が存在するかの確認を行い、特定できていれば、その結果を最終結果とし、出力する。一方、全ての検索結果がフローＩＤを特定できていなければ、最終結果を未登録フローとして出力する（ステップＡ９、ステップＡ１０）。なお、この最終結果の出力先は、第１、第２の実施形態と同じであるので、詳細は省略する。さらに、上記では、Ｍ個のマルチコアＣＰＵからの検索結果が全て揃った時点で最終結果の確認、決定を行っているが、処理対象のパケットに対する最終結果を特定できる変数やレジスタ等を用意し、マルチコアＣＰＵからの検索結果が返信される度に順次結果を確認していく手法を用いても良い。
【００７６】
なお、本実施の形態では、各マルチコアＣＰＵ内の共有メモリに構成されるサブフローテーブルは、全て独立した内容となっている。このため、もし、最終結果決定ブロック７で、フローＩＤを特定できなかった未登録フローを新規フローとして登録する処理を行う場合には、各マルチコアＣＰＵ内のサブフローテーブルのうち、適切なサブフローテーブルにフロー登録を行う処理が必要である。
【００７７】
また、本実施の形態では、パケットそのものをパケット送受信ブロック５にて、ネットワークから受信する形態であったが、パケットヘッダのみが入力される場合の処理についても第１の実施の形態と同様であり、イベントキューの構成箇所（メインメモリ６、各マルチコアＣＰＵ内の共有メモリ、検索キー抽出ブロック４内の特定内のメモリ、レジスタ等）についても、第１、第２の実施の形態と同様であるため、詳細は省略する。
【００７８】
最後に、上記で説明した本実施の形態における処理概要を、図１２を用いて説明する。図１２に示すように、本実施の形態におけるフロー検索処理は、パケットｐｋｔ１、ｐｋｔ２、・・・が到着すると、順に検索キーＫｅｙ＃１、Ｋｅｙ＃２、・・・を抽出し、各検索キーを全てのマルチコアＣＰＵへ送出する。送出された各検索キーは、各マルチコアＣＰＵ内の複数のプロセッサコアのうちの１つに割り当て、それぞれのマルチコアＣＰＵ内のプロセッサコアによってフロー検索処理を行い、最後に最終結果決定ブロックによって最終結果を決定することになる。ここで、各マルチコアＣＰＵ内の複数のプロセッサコアへの割り当ては、例えばＲｏｕｎｄ−Ｒｏｂｉｎのような手法を用いることが考えられるが、これに限定されるものではない。
【００７９】
次に、本発明の第３の実施の形態の作用効果について説明する。
【００８０】
上記のように、本実施の形態では、第２の実施の形態とは異なり、複数個のマルチコアＣＰＵ内に存在するフローテーブルは、全て独立した内容となっている。このため、複数個のマルチコアＣＰＵに対する分散処理はできないが、第１の実施の形態における作用効果に加えて、第２の実施の形態におけるフローエントリ数がＭ倍となり、より多くのフローを登録、管理、検索することが可能となる。
【００８１】
次に、本発明の第４の実施の形態について図面を参照して詳細に説明する。
＜実施の形態４＞
図１３は、本発明の第４の実施の形態の構成を示すブロック図である。図１３を参照すると、本発明の第４の実施の形態は、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭと、パケットの送受信を行うパケット送受信ブロック５と、受信したパケットからフロー検索処理における検索キーとなるヘッダ情報を抽出する検索キー抽出ブロック８と、抽出した検索キーに対するハッシュ値を計算すると共に、パケット受信イベントの生成と発行、及びパケットをメインメモリへ書き込むハッシュ値計算ブロック９と、パケット受信イベントや必要に応じてパケットそのものが書き込まれるＤＲＡＭ等のメインメモリ６と、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、検索キー抽出ブロック８、ハッシュ値計算ブロック９、メインメモリ６をそれぞれ接続するバス３とを含む。本実施の形態は、図９に示した前記第３の実施の形態から、最終結果決定ブロック７を除き、検索キー抽出ブロック４を検索キー抽出ブロック８に変更し、ハッシュ値計算ブロック９を加えたものであり、その他は前記第２の実施の形態と同じである。
【００８２】
また、本実施の形態における各マルチコアＣＰＵ内の共有メモリには、第３の実施の形態と同様、元のフローテーブルをＭ個に分割したうちの１つのフローテーブルを構成する。本フローテーブルについては、第３の実施の形態と同様であるため、詳細な説明は省略する。
【００８３】
なお、図１３においても、第１、第２、第３の実施の形態と同様、マルチコアＣＰＵ１、マルチコアＣＰＵ２、・・・、マルチコアＣＰＵＭ、ハッシュ値計算ブロック９、メインメモリ６をバス３によってバス接続している形態であるが、本接続形態はサーバ等に備えられたＮｏｒｔｈ  ＢｒｉｄｇｅやＳｏｕｔｈ  Ｂｒｉｄｇｅと呼ばれるチップセットを通じて接続される形態や、クロスバー、リングバスの形態でも構わない。また、本実施の形態は、サーバ等のマザーボード上で構成しても良いし、メインメモリ６を除いた全てを１つのＳｏＣとして、１つのチップ上に構成しても良い。
【００８４】
次に、図１３、及び図１４の流れ図を参照して、本発明の第３の実施の形態の動作について詳細に説明する。
【００８５】
図１３の流れ図におけるステップＡ１、ステップＡ２は、第１、第２、第３の実施の形態におけるステップＡ１、ステップＡ２と同様であるため、詳細な説明は省略するが、パケット送受信ブロック５（ステップＡ１）を経由して、検索キー抽出ブロック８は、ネットワークから入力されたパケットを受け取り、検索キーの抽出等のステップＡ２に対する処理を行う。
【００８６】
次に、検索キー抽出ブロック８は、抽出した検索キーとパケット送受信ブロック５から受け取ったパケットをハッシュ値計算ブロック９へ出力し、ハッシュ値計算ブロック９は、受け取った検索キーに対するハッシュ値を計算する（ステップＡ１１）。ここで、ハッシュ値計算ブロック９において算出するハッシュ値については、第１、第２、第３の実施例におけるフロー検索処理（ステップＡ４）におけるハッシュ値の算出（ステップＢ２）と同じであるため、詳細な説明は省略する。
【００８７】
ハッシュ値計算ブロック９は、ハッシュ値の計算を行うと、パケット受信を複数のマルチコアＣＰＵのうちの１つに通知するためのイベントを生成、発行し、イベントキューへ書き込むと共に、対応するパケットをメインメモリ６に書き込む（ステップＡ１２）。ここで、生成するイベントには、抽出した検索キーの情報と、対応するパケットの識別子に加え、算出したハッシュ値の値を含むものであれば良く、各マルチコアＣＰＵに対するイベントキューの構成については、第３の実施の形態と同様である。
【００８８】
また、ハッシュ値計算ブロック９が生成し、発行するイベントは、Ｍ個のマルチコアＣＰＵのうちの１つである。このイベントを発行するマルチコアＣＰＵの選択方法については、以下に説明する。上述したように、本実施の形態におけるマルチコアＣＰＵは、第３の実施の形態と同様、元の１つのフローテーブルをＭ個に分割したサブフローテーブルのうちの１つを共有メモリ上に構成している。ハッシュ値計算ブロック９には、各サブフローテーブルに含まれるベースアドレスを予め設定しておく。このため、ハッシュ値計算ブロック９は、ハッシュ値の算出を行うと、当該ハッシュ値に対応するエントリ群が、Ｍ個のマルチコアＣＰＵのうちのどのサブフローテーブル内に登録されているかを判断することが可能となる。ハッシュ値計算ブロック９は、算出したハッシュ値に応じて、そのハッシュ値に対応するエントリ群が登録されているマルチコアＣＰＵに対して、パケット受信イベントを発行する。
【００８９】
一方、Ｍ個のマルチコアＣＰＵは、それぞれ自身のイベントキューにイベントが存在するかをポーリング（ｐｏｌｌｉｎｇ）によって監視しており、イベントキューにイベントが存在すれば、その先頭のイベントを読み出し、自身の持つ特定のプロセッサコアによってフロー検索処理を行う（ステップＡ１３）。
【００９０】
図１５は、ステップＡ１３のより詳細な動作を説明するための流れ図である。本フロー検索処理は、Ｍ個のマルチコアＣＰＵにおいてフロー検索処理を行うプロセッサコアに共通の処理であり、以下では、任意のマルチコアＣＰＵにおける任意のプロセッサコアに対する処理として説明する。
【００９１】
図１５を参照すると、本実施の形態におけるフロー検索処理（ステップＡ１３）は、第１、第２、第３の実施の形態におけるフロー検索処理（ステップＡ４）のうち、ハッシュ値の計算処理（ステップＢ２）を除いた処理の流れであり、上述したように、受信したイベントにはハッシュ値計算ブロック９において算出されたハッシュ値が含まれる。本実施の形態におけるフロー検索処理においては、第１、第２、第３の実施の形態におけるステップＢ２において算出するはずのハッシュ値として、受信したイベントに含まれるハッシュ値を用いて処理を行う。本実施の形態におけるフロー検索処理（ステップＡ１３）における他の詳細な処理については、第１、第２、第３の実施の形態におけるフロー検索処理（ステップＡ４）と同じであるため、詳細な説明は省略する。
【００９２】
フロー検索処理（ステップＡ１３）が終了すると、プロセッサコアは、その結果を出力する（ステップＡ７）。本結果出力ステップＡ７は、第２の実施の形態と同様であるため、詳細な説明は省略する。なお、本実施の形態では、各マルチコアＣＰＵ内の共有メモリに構成されるサブフローテーブルは、全て独立した内容となっている。このため、もし、フローＩＤを特定できなかった未登録フローを新規フローとして登録する処理を行う場合には、フロー登録処理を行う必要があるが、第３の実施の形態と異なり、１つのパケットに対するフロー検索処理は、１つのマルチコアＣＰＵのうちの１つのプロセッサコアでのみ行われるため、各マルチコアＣＰＵに独立した登録処理となる。
【００９３】
また、本実施の形態では、パケットそのものをパケット送受信ブロック５にて、ネットワークから受信する形態であったが、パケットヘッダのみが入力される場合の処理についても第１の実施の形態と同様である。さらに、各マルチコアＣＰＵに対するイベントキューは、各マルチコアＣＰＵ内の共有メモリにおいて、フローテーブルとは論理的に分離された領域に構成し、ハッシュ値計算ブロック９から直接共有メモリ内のイベントキューへイベントを書き込んでも構わないし、ハッシュ値計算ブロック９内の特定内のメモリ、レジスタを用いて構成しても構わない。いずれにせよ、各マルチコアＣＰＵから見ることのできるアドレス空間上で、自身のマルチコアＣＰＵに対するイベントキューとして特定できる領域であれば問題無い。
【００９４】
最後に、上記で説明した本実施の形態における処理概要を、図１６を用いて説明する。本実施の形態を用いたフロー検索処理、図１６に示すように、パケットｐｋｔ１、ｐｋｔ２、・・・が到着すると、順に検索キーＫｅｙ＃１、Ｋｅｙ＃２、・・・を抽出し、各検索キーに対するハッシュ値を算出する。続いて、算出したハッシュ値に応じて、当該ハッシュ値に対するエントリ群が登録されているマルチコアＣＰＵに対して検索キーとハッシュ値を送出する。送出された検索キーとハッシュ値は、それぞれのマルチコアＣＰＵ内の複数のプロセッサコアのうちの１つに割り当て、それぞれのマルチコアＣＰＵ内のプロセッサコアによってフロー検索処理を行うことになる。ここで、各マルチコアＣＰＵ内の複数のプロセッサコアへの割り当ては、例えばＲｏｕｎｄ−Ｒｏｂｉｎのような手法を用いることが考えられるが、これに限定されるものではない。
【００９５】
次に、本発明の第４の実施の形態の作用効果について説明する。
【００９６】
上記のように、本実施の形態では、第３の実施の形態と同様、各マルチコアＣＰＵ内のフローテーブルは全て独立した内容となっている。このため、より多くのフローを登録、管理、検索することが可能である。また、本実施の形態では、ハッシュ値の算出を各プロセッサコアではなく、ハッシュ値計算ブロックにて行い、算出したハッシュ値に応じてフロー検索処理を行うべきフローテーブルを有するマルチコアＣＰＵを特定することが可能となる。このため、第３の実施の形態とは異なり、全てのマルチコアＣＰＵ内の１つのプロセッサコアでフロー検索処理を行う必要が無く、複数個のプロセッサコアに対して効率的にフロー検索処理を分散させることができるため、フロー検索処理の性能が向上する。
【００９７】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限定されない。
（付記１）複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリから構成されるマルチコアＣＰＵを有するマルチコアプロセッサ環境において、
共有メモリ上に検索パターンを備えるパターンテーブルを構成し、
複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行する
ことを特徴とするパターンマッチング方法。
【００９８】
（付記２）前記パターンテーブルは、ハッシュテーブルとして構成されることを特徴とする付記１に記載のパターンマッチング方法。
【００９９】
（付記３）パケットの送受信を行い、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させ、
１つのマルチコアＣＰＵでパターンマッチング処理を行うこと
を特徴とする付記１又は付記２に記載のパターンマッチング方法。
【０１００】
（付記４）抽出した検索キーを含むパケット受信イベントを生成、発行し、
受信したパケット受信イベントを前記マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当て、
パケット受信イベントが割り当たったプロセッサコアでパターンマッチング処理を行うこと
を特徴とする付記３に記載のパターンマッチング方法。
【０１０１】
（付記５）パケットの送受信を行い、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させ、
複数個のマルチコアＣＰＵが有する共有メモリ上に、同一のパターンテーブルを構成し、
複数個のマルチコアＣＰＵのうちの１つでパターンマッチング処理を行うこと
を特徴とする付記１又は付記２に記載のパターンマッチング方法。
【０１０２】
（付記６）抽出した検索キーを含むパケット受信イベントを生成し、
生成したパケット受信イベントは、複数個のマルチコアＣＰＵのうちの１つに対して順次発行する
ことを特徴とする付記５に記載のパターンマッチング方法。
【０１０３】
（付記７）前記パケット受信イベントを受信したマルチコアＣＰＵにおいて、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記６に記載のパターンマッチング方法。
【０１０４】
（付記８）パケットの送受信を行い、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させ、
複数個のマルチコアＣＰＵが有する共有メモリ上に、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つを構成し、
複数個のマルチコアＣＰＵの全てでパターンマッチング処理を行い、
各マルチコアＣＰＵ内の複数のプロセッサコアにおいて行ったパターンマッチングの結果を収集し、最終的なパターンマッチング結果を決定する
ことを特徴とする付記１又は付記２に記載のパターンマッチング方法。
【０１０５】
（付記９）抽出した検索キーを含むパケット受信イベントを生成し、
生成したパケット受信イベントは、複数個のマルチコアＣＰＵの全てに対して発行する
ことを特徴とする付記８に記載のパターンマッチング方法。
【０１０６】
（付記１０）前記複数個のマルチコアＣＰＵにおいて、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記９に記載のパターンマッチング方法。
【０１０７】
（付記１１）パケットの送受信を行い、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、
抽出した検索キーに対するハッシュ値の算出を行い、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させ、
複数個のマルチコアＣＰＵが有する共有メモリ上に、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つを構成し、
複数個のマルチコアＣＰＵのうちの１つでパターンマッチング処理を行う
ことを特徴とする付記１又は付記２に記載のパターンマッチング方法。
【０１０８】
（付記１２）抽出した検索キーと算出したハッシュ値を含むパケット受信イベントを生成し、
生成したパケット受信イベントは、算出したハッシュ値に対応したエントリ群を保持するサブパターンテーブルを有するマルチコアＣＰＵに対して発行する
ことを特徴とする付記１１に記載のパターンマッチング方法。
【０１０９】
（付記１３）前記パケット受信イベントを受信したマルチコアＣＰＵにおいて、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記１２に記載のパターンマッチング方法。
【０１１０】
（付記１４）複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリを備えるマルチコアＣＰＵを有するマルチコアプロセッサ環境において、
前記共有メモリ上は、検索パターンを備えるパターンテーブルを含み、
前記複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行する
ことを特徴とするパターンマッチング装置。
【０１１１】
（付記１５）前記パターンテーブルは、ハッシュテーブルとして構成することを特徴とする付記１４に記載のパターンマッチング装置。
【０１１２】
（付記１６）１つのマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
前記マルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスと
を備えたことを特徴とする付記１４又は付記１５に記載のパターンマッチング装置。
【０１１３】
（付記１７）抽出した検索キーを含むパケット受信イベントを生成、発行し、
パケット受信イベントは、前記マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記１６に記載のパターンマッチング装置。
【０１１４】
（付記１８）複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、同一のパターンテーブルが構成される
ことを特徴とする付記１４又は付記１５に記載のパターンマッチング装置。
【０１１５】
（付記１９）抽出した検索キーを含むパケット受信イベントを生成し、
パケット受信イベントは、複数個のマルチコアＣＰＵのうちの１つに対して発行する
ことを特徴とする付記１８に記載のパターンマッチング装置。
【０１１６】
（付記２０）前記パケット受信イベントを受信したマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記１９に記載のパターンマッチング装置。
【０１１７】
（付記２１）複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
各マルチコアＣＰＵ内の複数のプロセッサコアにおけるパターンマッチング結果を収集し、最終的なパターンマッチング結果を決定する最終結果決定ブロックと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリと最終結果決定ブロックを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする付記１４又は付記１５に記載のパターンマッチング装置。
【０１１８】
（付記２２）抽出した検索キーを含むパケット受信イベントを生成し、
生成したパケット受信イベントは、複数個のマルチコアＣＰＵの全てに対して発行する
ことを特徴とする付記２１に記載のパターンマッチング装置。
【０１１９】
（付記２３）前記複数個のマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記２２に記載のパターンマッチング装置。
【０１２０】
（付記２４）複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出する検索キー抽出ブロックと、
抽出した検索キーに対するハッシュ値の算出を行い、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させるハッシュ値計算ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとハッシュ値計算ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする付記１４又は付記１５に記載のパターンマッチング装置。
【０１２１】
（付記２５）抽出した検索キーと算出したハッシュ値を含むパケット受信イベントを生成し、
生成したパケット受信イベントは、算出したハッシュ値に対応したエントリ群を保持するサブパターンテーブルを有するマルチコアＣＰＵに対して発行する
ことを特徴とする付記２４に記載のパターンマッチング装置。
【０１２２】
（付記２６）前記パケット受信イベントを受信したマルチコアＣＰＵは、
受信したパケット受信イベントを、当該マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする付記２５に記載のパターンマッチング装置。
【０１２３】
本発明の代表的な実施形態が詳細に述べられたが、様々な変更(changes)、置き換え(substitutions)及び選択(alternatives)が請求項で定義された発明の精神と範囲から逸脱することなくなされることが理解されるべきである。また、仮にクレーム場出願手続きにおいて補正されたとしても、クレームされた発明の均等の範囲は維持されるものと発明者は意図する。
【０１２４】
この出願は、２００９年１２月２１日に出願された日本出願特願２００９−２８９０１１号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１２５】
本発明の活用例として、パケットのヘッダ情報から特定のフィールドの組によって、パケットが属するフローを識別し、ＱｏＳ処理や負荷分散等、フロー毎に特定の処理を行わせるスイッチやルータ等のネットワーク装置、及びロードバランサー等のアプライアンス装置といった用途に適用できる。
【符号の説明】
【０１２６】
１  マルチコアＣＰＵ
２  マルチコアＣＰＵ
３  バス
４  検索キー抽出ブロック
５  パケット送受信ブロック
６  メインメモリ
７  最終結果決定ブロック
８  検索キー抽出ブロック
９  ハッシュ値計算ブロック
１０  パケット送受信ブロック
１１  ＣＰＵ
１２  マルチコアＣＰＵ
１３  マルチコアＣＰＵ
Ｍ  マルチコアＣＰＵ  
１−０  共有メモリ
１−１、１−２、１−Ｎ  プロセッサコア
２−０  共有メモリ
２−１、２−２、１−Ｎ  プロセッサコア
１１−０  Ｌ２キャッシュ
１１−１  プロセッサコア
１２−０  Ｌ２キャッシュ
１２−１、１２−２  プロセッサコア
１３−０  Ｌ２キャッシュ
１３−１、１３−２  プロセッサコア
Ｍ−０  共有メモリ
Ｍ−１、Ｍ−２、Ｍ−Ｎ  プロセッサコア
【図１】
2011078108.tif 000003
【図２】
2011078108.tif 000004
【図３】
2011078108.tif 000005
【図４】
2011078108.tif 000006
【図５】
2011078108.tif 000007
【図６】
2011078108.tif 000008
【図７】
2011078108.tif 000009
【図８】
2011078108.tif 000010
【図９】
2011078108.tif 000011
【図１０】
2011078108.tif 000012
【図１１】
2011078108.tif 000013
【図１２】
2011078108.tif 000014
【図１３】
2011078108.tif 000015
【図１４】
2011078108.tif 000016
【図１５】
2011078108.tif 000017
【図１６】
2011078108.tif 000018
【図１７】
2011078108.tif 000019
【図１８】
2011078108.tif 000020
【図１９】
2011078108.tif 000021
【手続補正書】
【提出日】平成24年6月21日(2012.6.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のプロセッサコアと、同一ＣＰＵ内に存在するそれらプロセッサコア間で共有される共有メモリを備えるマルチコアＣＰＵを有するマルチコアプロセッサ環境において、
前記共有メモリ上は、検索パターンを備えるパターンテーブルを含み、
前記複数のプロセッサコアで検索対象となる検索キーに対するパターンマッチング処理を並列に実行する
ことを特徴とするパターンマッチング装置。
【請求項２】
前記パターンテーブルは、ハッシュテーブルとして構成することを特徴とする請求項１に記載のパターンマッチング装置。
【請求項３】
１つのマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
前記マルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスと
を備えたことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項４】
抽出した検索キーを含むパケット受信イベントを生成、発行し、
パケット受信イベントは、前記マルチコアＣＰＵが有する複数個のプロセッサコアのうちの１つに順次割り当てる
ことを特徴とする請求項３に記載のパターンマッチング装置。
【請求項５】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、同一のパターンテーブルが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項６】
抽出した検索キーを含むパケット受信イベントを生成し、
パケット受信イベントは、複数個のマルチコアＣＰＵのうちの１つに対して発行する
ことを特徴とする請求項５に記載のパターンマッチング装置。
【請求項７】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出し、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させる検索キー抽出ブロックと、
パケットデータを記憶するメインメモリと、
各マルチコアＣＰＵ内の複数のプロセッサコアにおけるパターンマッチング結果を収集し、最終的なパターンマッチング結果を決定する最終結果決定ブロックと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとメインメモリと最終結果決定ブロックを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項８】
抽出した検索キーを含むパケット受信イベントを生成し、
生成したパケット受信イベントは、複数個のマルチコアＣＰＵの全てに対して発行する
ことを特徴とする請求項７に記載のパターンマッチング装置。
【請求項９】
複数個のマルチコアＣＰＵと、
パケットの送受信を行うパケット送受信ブロックと、
受信したパケットのヘッダ情報から検索キーとなる任意のフィールドの組を抽出する検索キー抽出ブロックと、
抽出した検索キーに対するハッシュ値の算出を行い、パケット受信イベントを生成し、発行すると共に、パケットデータをメインメモリへ記憶させるハッシュ値計算ブロックと、
パケットデータを記憶するメインメモリと、
複数個のマルチコアＣＰＵと検索キー抽出ブロックとハッシュ値計算ブロックとメインメモリを接続するバスとを備え、
複数個のマルチコアＣＰＵが有する共有メモリ上には、パターンテーブルをマルチコアＣＰＵと同数に分割したサブパターンテーブルのうちの１つが構成される
ことを特徴とする請求項１又は請求項２に記載のパターンマッチング装置。
【請求項１０】
抽出した検索キーと算出したハッシュ値を含むパケット受信イベントを生成し、
生成したパケット受信イベントは、算出したハッシュ値に対応したエントリ群を保持するサブパターンテーブルを有するマルチコアＣＰＵに対して発行する
ことを特徴とする請求項９に記載のパターンマッチング装置。
【国際調査報告】
2011078108.tif 000022
2011078108.tif 000023
2011078108.tif 000024
2011078108.tif 000025