(57)【要約】【課題】キャッシュシステムにおいて、同一のフローに属するプロセッサを複数のプロセッサで処理し、負荷分散を実現する。【解決手段】キャッシュ装置１は、受信したパケットのフロー識別子からキャッシュデータを検索し、フロー識別子に対応するキャッシュデータが存在する場合、データとパケット処理用の情報をパケット処理装置２に渡し、存在しなければパケット処理装置２にデータの処理を依頼して、処理データをもらった後キャッシュし、フローごとにパケットの到着順序を管理して、パケット処理装置２で処理してもらったデータを転送装置への到着順にソートする。【選択図】図１
2008131351.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュを提供するキャッシュ装置と、複数のパケット処理装置からなり、
前記キャッシュ装置は、受信したパケットのフロー識別子からキャッシュデータを検索し、前記フロー識別子に対応するキャッシュデータが存在する場合、データとパケット処理用の情報を前記パケット処理装置に渡し、前記フロー識別子に対応するキャッシュデータが存在しなければ前記パケット処理装置にデータの処理を依頼して、処理データをもらった後キャッシュし、フローごとにパケットの到着順序を管理して、前記パケット処理装置で処理してもらったデータを転送装置への到着順にソートし、
前記パケット処理装置は、前記キャッシュ装置からパケット処理用の情報を受け取り、前記キャッシュ装置からデータを処理する指示を受けるとデータを処理した後、結果を前記キャッシュ装置に渡し、前記指示がない場合、一緒に受け取ったキャッシュデータを用いてパケット処理を行い、処理が終わると前記キャッシュ装置にパケット処理用の情報を送る
キャッシュシステム。
【請求項２】
パケットの処理データを格納するキャッシュと、フローごとの転送装置への到着順序をＦＩＦＯのキューで記録する順序データベースと、パケットを処理させるパケット処理装置を決定するアルゴリズムを記録したアルゴリズムテーブルと、パケットのフロー識別子から前記キャッシュのエントリを探すためのキャッシュ検索手段と、パケットを処理してもらうパケット処理装置を決定するパケット分配手段と、前記パケット処理装置から受信したキャッシュデータを前記キャッシュに記録するキャッシュアップデート手段と、前記パケット処理装置での処理が終了したパケットを転送装置の到着順にソートするソート手段と、を備え、
前記キャッシュ検索手段は、パケットからフロー識別子を調べ、前記キャッシュの中に該フロー識別子に対応するキャッシュのデータが存在するか否か調べ、存在するならば該キャッシュデータをパケット処理用の情報に追加し、存在しなければ、前記順序データベースに該フロー識別子に対するエントリが存在するか否か調べ、存在するならば対応するキャッシュデータが到着するまで待機し、存在しなければ前記キャッシュに書き込まれるデータの処理を前記パケット処理装置に指示する情報をパケット処理用の情報に追記し、
前記パケット分配手段は、パケットを処理させるパケット処理装置を前記アルゴリズムテーブルに存在するアルゴリズムに従って決定し、決定したパケット処理装置の識別子を前記順序データベースに存在するフロー識別子に対するＦＩＦＯのキューに入力し、
前記キャッシュアップデート手段は、前記パケット処理装置から送られてきたキャッシュデータを前記キャッシュに追記し、データが前記キャッシュの容量を超えると前記キャッシュからデータを削除し、
前記ソート手段は、前記パケット処理装置からパケット処理用の情報が送られてくると、パケット処理装置の識別子と、パケットのフロー識別子を確認し、前記順序データベースにおけるフロー識別子に対応するＦＩＦＯキューの先頭の識別子とパケット処理装置の識別子を比較し、異なればパケットをバッファに格納し、同じであればパケットを送信し、前記ＦＩＦＯキューの先頭の識別子を削除し、バッファに格納しているパケットの存在を確認し、もし存在すれば、ＦＩＦＯキューの先頭に存在する識別子と比較する、前記の動作と同様の動作を繰り返す
キャッシュ装置。
【請求項３】
前記パケット分配手段は、前記キャッシュの中に受信パケットが属するフローに対応するデータが存在せず、かつ該フローに対応する前記順序データベースのＦＩＦＯキューにパケット処理装置の識別子が存在するときに、パケットを待機させずに、処理を行っているパケット処理装置とキャッシュを共有できるパケット処理装置を、受信パケットを処理する装置として決定する、請求項２に記載のキャッシュ装置。
【請求項４】
キャッシュ装置から送られてきたパケット処理用の情報における、キャッシュ対象データの処理を指示する情報の有無を確認するキャッシュ有無判定手段と、前記指示があった場合、キャッシュ対象データの処理を行うキャッシュ対象データ処理手段と、前記キャッシュ対象データ以外のパケット処理行うパケット処理手段と、キャッシュ対象データの処理が終了したとき、データを前記キャッシュ装置に送るキャッシュアップデート手段と
を有し、
前記キャッシュ有無判定手段は、前記指示の情報が存在する場合、前記キャッシュ対象データ処理手段を用いてキャッシュ対象データの処理を行い、存在しなければ一緒に送られてきたキャッシュデータを用いて、前記パケット処理手段によりキャッシュ対象のデータと関連のない、もしくはキャッシュ対象のデータを使用する処理を行い、
前記キャッシュ対象データ処理手段は、前記キャッシュ対象データの処理が終了すると、前記キャッシュアップデート手段に処理結果を送り、データを前記キャッシュ装置に送る動作を行う
パケット処理装置。
【請求項５】
前記キャッシュ対象データ処理手段は、パケットを処理する際に請求項２に記載のキャッシュ装置から送られてきたパケット処理用の情報の中にキャッシュ対象処理を実行する指示が存在せず、かつキャッシュデータが存在しない場合に、情報を受信したパケットに対してはキャッシュ対象データを利用しない処理を行い、処理終了後はパケット処理装置のキャッシュに対象データが書き込まれるまで待機し、受信したパケットと同じフロー識別子を持つキャッシュ対象データの処理を行っているパケットについてはデータ処理終了後、データをキャッシュ装置に送るだけでなく、パケット処理装置のキャッシュにも書き込む、請求項４に記載のパケット処理装置。
【請求項６】
パケットの処理データを格納するキャッシュと、フローごとの転送装置への到着順序をＦＩＦＯのキューで記録する順序データベースと、パケットを処理させるパケット処理装置を決定するアルゴリズムを記録したアルゴリズムテーブルと、パケットのフロー識別子から前記キャッシュのエントリを探すためのキャッシュ検索手段と、パケットを処理してもらうパケット処理装置を決定するパケット分配手段と、前記パケット処理装置から受信したキャッシュデータを前記キャッシュに記録するキャッシュアップデート手段と、前記パケット処理装置での処理が終了したパケットを転送装置の到着順にソートするソート手段と、を備えたキャッシュ装置で行われるキャッシュ方法であって、
前記キャッシュ検索手段が、パケットからフロー識別子を調べ、前記キャッシュの中に該フロー識別子に対応するキャッシュのデータが存在するか否か調べ、存在するならば該キャッシュデータをパケット処理用の情報に追加し、存在しなければ、前記順序データベースに該フロー識別子に対するエントリが存在するか否か調べ、存在するならば対応するキャッシュデータが到着するまで待機し、存在しなければ前記キャッシュに書き込まれるデータの処理を前記パケット処理装置に指示する情報をパケット処理用の情報に追記するステップと、
前記パケット分配手段が、パケットを処理させるパケット処理装置を前記アルゴリズムテーブルに存在するアルゴリズムに従って決定し、決定したパケット処理装置の識別子を前記順序データベースに存在するフロー識別子に対するＦＩＦＯのキューに入力するステップと、
前記キャッシュアップデート手段が、前記パケット処理装置から送られてきたキャッシュデータを前記キャッシュに追記し、データが前記キャッシュの容量を超えると前記キャッシュからデータを削除するステップと、
前記ソート手段が、前記パケット処理装置からパケット処理用の情報が送られてくると、パケット処理装置の識別子と、パケットのフロー識別子を確認し、前記順序データベースにおけるフロー識別子に対応するＦＩＦＯキューの先頭の識別子とパケット処理装置の識別子を比較し、異なればパケットをバッファに格納し、同じであればパケットを送信し、前記ＦＩＦＯキューの先頭の識別子を削除し、バッファに格納しているパケットの存在を確認し、もし存在すれば、ＦＩＦＯキューの先頭に存在する識別子と比較する、前記の動作と同様の動作を繰り返すステップと、
を有するキャッシュ方法。
【請求項７】
前記パケット分配手段が、前記キャッシュの中に受信パケットが属するフローに対応するデータが存在せず、かつ該フローに対応する前記順序データベースのＦＩＦＯキューにパケット処理装置の識別子が存在するときに、パケットを待機させずに、処理を行っているパケット処理装置とキャッシュを共有できるパケット処理装置を、受信パケットを処理する装置として決定するステップをさらに有する、請求項６に記載のキャッシュ方法。
【請求項８】
キャッシュ装置から送られてきたパケット処理用の情報における、キャッシュ対象データの処理を指示する情報の有無を確認するキャッシュ有無判定手段と、前記指示があった場合、キャッシュ対象データの処理を行うキャッシュ対象データ処理手段と、前記キャッシュ対象データ以外のパケット処理行うパケット処理手段と、キャッシュ対象データの処理が終了したとき、データを前記キャッシュ装置に送るキャッシュアップデート手段とを有するパケット処理装置で行われるパケット処理方法であって、
前記キャッシュ有無判定手段が、前記指示の情報が存在する場合、前記キャッシュ対象データ処理手段を用いてキャッシュ対象データの処理を行い、存在しなければ一緒に送られてきたキャッシュデータを用いて、前記パケット処理手段によりキャッシュ対象のデータと関連のない、もしくはキャッシュ対象のデータを使用する処理を行うステップと、
前記キャッシュ対象データ処理手段が、前記キャッシュ対象データの処理が終了すると、前記キャッシュアップデート手段に処理結果を送り、データを前記キャッシュ装置に送る動作を行うステップと
を有する、パケット処理方法。
【請求項９】
前記キャッシュ対象データ処理手段が、パケットを処理する際に請求項６に記載のキャッシュ装置から送られてきたパケット処理用の情報の中にキャッシュ対象処理を実行する指示が存在せず、かつキャッシュデータが存在しない場合に、情報を受信したパケットに対してはキャッシュ対象データを利用しない処理を行い、処理終了後はパケット処理装置のキャッシュに対象データが書き込まれるまで待機し、受信したパケットと同じフロー識別子を持つキャッシュ対象データの処理を行っているパケットについてはデータ処理終了後、データをキャッシュ装置に送るだけでなく、パケット処理装置のキャッシュにも書き込む、請求項８に記載のパケット処理方法。
【請求項１０】
請求項２または３に記載のキャッシュ装置をコンピュータとして機能させるためのキャッシュプログラム。
【請求項１１】
請求項４または５に記載のパケット処理装置をコンピュータとして機能させるためのパケット処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプロセスやデータを複数のプロセッサ、ならびにプロセッサ内に存在するスレッドを用いて並列処理を行う計算機に関する。特にパケット処理プロセッサが複数の処理を並列に処理することができるデータ転送装置におけるキャッシュの実現方法に関するものである。
【背景技術】
【０００２】
近年、プロセッサの性能向上に限界が見えてきたのに伴い複数のプロセッサを用意し、それぞれで並列処理を行うようなマルチプロセッサシステムが提供されている。また、プロセッサの処理能力の向上の一手法として、高速なキャッシュを用いて、低速なキャッシュへのアクセス回数を削減する方式が存在する。パケット処理を行う場合でもこのような高速手法は有効であり、現在、多くの方法が検討されている。このような手法をマルチプロセッサシステムに適用する際、次の非特許文献１に示されるような方式が使用される。
【０００３】
パケット処理では、同一フローに属するパケット同士で経路などの検索結果を共用することができる。このため、同一フローに属するパケット同士でキャッシュされたデータを使用することで処理の高速化が見込まれる。非特許文献１で紹介する方式では、同一フローに属するパケットを同一のプロセッサで処理させることでキャッシュの効果を利用している。これを実現するために、処理プロセッサの前にフローＩＤを元にハッシュ計算を行い、計算結果を、パケットを処理するプロセッサのＩＤと関連づけるという機能を用意している。ハッシュを利用すると、同一のフローＩＤを持つパケットは同じプロセッサによりパケットを処理されることになる。
【非特許文献１】Ｗ．  Ｓｈｉ，  ｅｔ  ａｌ．，  “Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  ｆｏｒ  Ｐａｒａｌｌｅｌ  Ｆｏｒｗａｒｄｉｎｇ，”  ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，  ｐｐ．７９０−８０１，  ２００５
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ハッシュの問題点として、パケットの振り分け先をプロセッサの処理に応じて変更することができない点にある。この場合、１つのプロセッサに処理が集中する可能性が存在し、並列処理の効果を十分に得ることができない。これはフローＩＤごとに計算結果が決まっているというハッシュの特徴によるものである。
本発明の目的は、同一のフローに属するプロセッサを複数のプロセッサで処理し、負荷分散を実現するキャッシュシステム、キャッシュ装置、パケット処理装置、キャッシュ方法、パケット処理方法、キャッシュプログラム、およびパケット処理プログラムを提供することにある。
【課題を解決するための手段】
【０００５】
本発明のキャッシュシステムは、
キャッシュを提供するキャッシュ装置と、複数のパケット処理装置からなり、
前記キャッシュ装置は、受信したパケットのフロー識別子からキャッシュデータを検索し、前記フロー識別子に対応するキャッシュデータが存在する場合、データとパケット処理用の情報を前記パケット処理装置に渡し、前記フロー識別子に対応するキャッシュデータが存在しなければ前記パケット処理装置にデータの処理を依頼して、処理データをもらった後キャッシュし、フローごとにパケットの到着順序を管理して、前記パケット処理装置で処理してもらったデータを転送装置への到着順にソートし、
前記パケット処理装置は、前記キャッシュ装置からパケット処理用の情報を受け取り、前記キャッシュ装置からデータを処理する指示を受けるとデータを処理した後、結果を前記キャッシュ装置に渡し、前記指示がない場合、一緒に受け取ったキャッシュデータを用いてパケット処理を行い、処理が終わると前記キャッシュ装置にパケット処理用の情報を送る。
【０００６】
パケットの到着順序を管理することで、同一フローに属するパケットを異なるパケット処理装置に送る場合であっても到着順序と同じ順序でパケットを送信するシステムを提供することが可能になる。結果として、パケットの処理を担当するパケット処理装置を自由に選べるため、パケット処理の負荷分散を行うことが可能となる。
【０００７】
本発明のキャッシュ装置は、
パケットの処理データを格納するキャッシュと、フローごとの転送装置への到着順序をＦＩＦＯのキューで記録する順序データベースと、パケットを処理させるパケット処理装置を決定するアルゴリズムを記録したアルゴリズムテーブルと、パケットのフロー識別子から前記キャッシュのエントリを探すためのキャッシュ検索手段と、パケットを処理してもらうパケット処理装置を決定するパケット分配手段と、前記パケット処理装置から受信したキャッシュデータを前記キャッシュに記録するキャッシュアップデート手段と、前記パケット処理装置での処理が終了したパケットを転送装置の到着順にソートするソート手段と、を備え、
前記キャッシュ検索手段は、パケットからフロー識別子を調べ、前記キャッシュの中に該フロー識別子に対応するキャッシュのデータが存在するか否か調べ、存在するならば該キャッシュデータをパケット処理用の情報に追加し、存在しなければ、前記順序データベースに該フロー識別子に対するエントリが存在するか否か調べ、存在するならば対応するキャッシュデータが到着するまで待機し、存在しなければ前記キャッシュに書き込まれるデータの処理を前記パケット処理装置に指示する情報をパケット処理用の情報に追記し、
前記パケット分配手段は、パケットを処理させるパケット処理装置を前記アルゴリズムテーブルに存在するアルゴリズムに従って決定し、決定したパケット処理装置の識別子を前記順序データベースに存在するフロー識別子に対するＦＩＦＯのキューに入力し、
前記キャッシュアップデート手段は、前記パケット処理装置から送られてきたキャッシュデータを前記キャッシュに追記し、データが前記キャッシュの容量を超えると前記キャッシュからデータを削除し、
前記ソート手段は、前記パケット処理装置からパケット処理用の情報が送られてくると、パケット処理装置の識別子と、パケットのフロー識別子を確認し、前記順序データベースにおけるフロー識別子に対応するＦＩＦＯキューの先頭の識別子とパケット処理装置の識別子を比較し、異なればパケットをバッファに格納し、同じであればパケットを送信し、前記ＦＩＦＯキューの先頭の識別子を削除し、バッファに格納しているパケットの存在を確認し、もし存在すれば、ＦＩＦＯキューの先頭に存在する識別子と比較する、前記の動作と同様の動作を繰り返す。
【０００８】
パケットの到着順序を管理することで、同一フローに属するパケットを異なるパケット処理装置に送る場合であっても到着順序と同じ順序でパケットを送信するシステムを提供することが可能になる。結果として、パケットの処理を担当するパケット処理装置を自由に選べるため、パケット処理の負荷分散を行うことが可能となる。また、パケット処理を担当するパケット処理装置を決定するアルゴリズムを複数用意することが可能であるため、管理者のポリシーに応じた負荷分散を行うことが可能になる。
【０００９】
本発明の実施態様によれば、キャッシュ装置は、パケット分配手段は、前記キャッシュの中に受信パケットが属するフローに対応するデータが存在せず、かつ該フローに対応する前記順序データベースのＦＩＦＯキューにパケット処理装置の識別子が存在するときに、パケットを待機させずに、処理を行っているパケット処理装置とキャッシュを共有できるパケット処理装置を、受信パケットを処理する装置として決定する。
【００１０】
パケットの到着順序を管理することで、同一フローに属するパケットを異なるパケット処理装置に送る場合であっても到着順序と同じ順序でパケットを送信することが可能になる。さらに、同一フローに属するパケットが連続して到着し、かつキャッシュ装置に該フローに関連するキャッシュデータが存在しないと時に、先頭以外のパケットをキャッシュ装置に待機させずに、先頭のパケットを処理するパケット処理装置とキャッシュ装置とは別に設けているキャッシュを共有しているパケット処理装置に該パケットを送信することが可能であり、結果的にキャッシュ装置での待ち時間が短縮される。
【００１１】
本発明のパケット処理装置は、
キャッシュ装置から送られてきたパケット処理用の情報における、キャッシュ対象データの処理を指示する情報の有無を確認するキャッシュ有無判定手段と、前記指示があった場合、キャッシュ対象データの処理を行うキャッシュ対象データ処理手段と、前記キャッシュ対象データ以外のパケット処理行うパケット処理手段と、キャッシュ対象データの処理が終了したとき、データを前記キャッシュ装置に送るキャッシュアップデート手段と
を有し、
前記キャッシュ有無判定手段は、前記指示の情報が存在する場合、前記キャッシュ対象データ処理手段を用いてキャッシュ対象データの処理を行い、存在しなければ一緒に送られてきたキャッシュデータを用いて、前記パケット処理手段によりキャッシュ対象のデータと関連のない、もしくはキャッシュ対象のデータを使用する処理を行い、
前記キャッシュ対象データ処理手段は、前記キャッシュ対象データの処理が終了すると、前記キャッシュアップデート手段に処理結果を送り、データを前記キャッシュ装置に送る動作を行う。
【００１２】
送られてきたパケットをフローの種類を問わずに処理することが可能であり、キャッシュデータと共に送られてきたパケットに対してデータの処理を行う必要がなくなるため、パケット処理装置の負荷を低減することが可能となる。
【００１３】
本発明の実施態様によれば、前記キャッシュ対象データ処理手段は、パケットを処理する際に請求項２に記載のキャッシュ装置から送られてきたパケット処理用の情報の中にキャッシュ対象処理を実行する指示が存在せず、かつキャッシュデータが存在しない場合に、情報を受信したパケットに対してはキャッシュ対象データを利用しない処理を行い、処理終了後はパケット処理装置のキャッシュに対象データが書き込まれるまで待機し、受信したパケットと同じフロー識別子を持つキャッシュ対象データの処理を行っているパケットについてはデータ処理終了後、データをキャッシュ装置に送るだけでなく、パケット処理装置のキャッシュにも書き込む。
【００１４】
送られてきたパケットをフローの種類を問わずに処理することが可能であり、キャッシュデータと共に送られてきたパケットに対してデータの処理を行う必要がなくなるため、パケット処理装置の負荷を低減することが可能となる。また、請求項３の発明と組み合わせることでキャッシュ装置とは別に設けられたキャッシュを共有するパケット処理装置に、同一フローに属するパケットを送信することができる。これにより、キャッシュ装置でパケットを待機させる必要がなくなり、結果としてパケットの待ち時間が短縮される。
【発明の効果】
【００１５】
本発明によれば、同一フローに属するパケットであっても、任意のパケット処理装置に処理をさせることが可能となり、結果として、負荷分散が実現される。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１を参照すると、本発明の一実施形態のキャッシュシステムは、キャッシュデータを格納するキャッシュ装置１と、パケットを処理する３台のパケット処理装置２からなる。キャッシュ装置１はキャッシュデータの提供と、パケットを処理させるパケット処理装置２を決定する機能を有する。さらに、キャッシュ装置１は、この実施形態では、同一フローに属するパケットを複数のパケット処理装置２で処理させるために、パケットの処理終了順序がパケット処理装置２の負荷の状況などの要因により、必ずしもパケットの到着順序と同じでない場合が存在するため、パケットの到着順序をそろえるソート機能を持つ。
キャッシュ装置１は、図２に示すように、プロセッサ１１と記憶媒体１６からなる。記憶媒体１６には、フローＩＤごとにキャッシュされたデータを格納するキャッシュ１７と、パケットを処理させるパケット処理装置２を決定するア分配アルゴリズムが格納されているデータベースである分配アルゴリズム１８と、フローごとの転送装置への到着順序をＦＩＦＯのキューで記録する順序データベース１９とが含まれる。プロセッサ１１には、パケット処理装置２から受信した、パケット処理装置２で処理されたキャッシュデータをキャッシュ１７に記録するキャッシュアップデート部１２と、キャッシュ１７のなかに調査対象のパケットのフローＩＤ用のキャッシュデータが存在する否かを、パケットのフロー識別子から検索するキャッシュ検索部１３と、パケットを処理してもらうパケット処理装置２を決定するとともに、パケットをパケット処理装置２に送るときに送る順序を順序データベース１９に記録するパケット分配部１４と、パケット処理装置２での処理が終了したパケットを転送装置の到着順にソートするソーター１５とが含まれる。
【００１８】
パケット処理装置２は、図３に示すように、キャッシュ装置１から送られてきたパケットの情報に含まれる、キャッシュ対象データに対する処理を行うかどうかを指示するデータの有無をチェックするキャッシュ有無判定部２１と、キャッシュ対象データ処理指示があったときにキャッシュ対象データのデータ処理を行うキャッシュ対象データ処理部２２と、キャッシュ対象データの処理が終了したときに、処理結果をキャッシュ装置１に送るキャッシュアップデート部２３と、キャッシュ対象データ処理以外のパケット処理を行うパケット処理部２４と、パケット処理に使用するデータが格納されている記憶媒体２５を有する。
【００１９】
まず、キャッシュ装置１の動作について説明する。キャッシュ装置１の動作は、一部のパケット処理装置２との間で装置内のキャッシュを共有できる場合とそうでない場合の２種類の動作が存在する。
【００２０】
まず、パケット処理装置２との間でキャッシュを共有できない場合の動作を、図４を参照して説明する。キャッシュ装置１のキャッシュ検索部１３はパケットを受信すると（ステップ１０１）、ヘッダ内のフローＩＤを抽出する（ステップ１０２）。そして、キャッシュ１７を検索し、前記フローＩＤと同じＩＤに対するエントリにキャッシュデータが存在するかどうかを確認する（ステップ１０３）。もし存在していれば、パケット処理装置２でデータ処理を行う必要がないため、パケット処理装置２にキャッシュ対象データ処理を行わないように指示する情報を作成し、パケット情報に追加する（ステップ１０４）。そして、パケットを処理させるパケット処理装置２を決定する（ステップ１０９）。もし、エントリ自体は存在するが、キャッシュデータが存在しない場合は、同じフローに属する別のパケットに対し、パケット処理装置２がキャッシュ対象のデータの処理を行っている場合であるので、その処理が終了するまで待機する（ステップ１０５、１０６）。キャッシュ対象データの処理が終了し、処理結果がキャッシュ１７に格納されると、そのキャッシュデータをパケット情報に記録する。そして、待機していた同一フローに属するすべてのパケットに対し、処理してもらうパケット処理装置２を決定し、そのパケット処理装置２にパケットを送出する（ステップ１０７）。エントリ自体が存在しない場合、パケット処理装置２にデータ処理を指示する情報を作成し、パケット情報に追記する（ステップ１０８）。そして、パケットを処理してもらうパケット処理装置２を決定する（ステップ１０９）。パケットを処理させるパケット処理装置２が決定すると、パケットを到着順に並べるため、順序データベース１９に記録されているＦＩＦＯキューに処理させるパケット処理装置２のＩＤを入れる（ステップ１１０）。そして、選択したパケット処理装置２にパケットの情報を送信する（ステップ１１１、１１２）。
【００２１】
次に、パケット処理装置２が装置間でキャッシュの共通利用が可能な場合の動作を、図５を参照して説明する。図４の場合との違いは、キャッシュ１７内にエントリは存在するが、キャッシュデータが存在しない場合（図４のステップ１０３、１０５）の動作である。図５ではエントリは存在するが、キャッシュデータが存在しない場合、パケットを待機させずに、現在データ処理中のパケットを処理しているパケット処理装置２とキャッシュを共通利用できるパケット処理装置２に送り込む（ステップ１１３）。このとき、パケット処理装置２ではデータ処理を行わない。
【００２２】
次に、パケット処理装置２の動作を図６により説明する。パケット処理装置２はパケットをキャッシュ装置１から受信すると（ステップ２０１）、パケット情報中に、キャッシュ対象データの処理の指示を示す情報が存在するかどうかを確認する（ステップ２０２）。もし指示が存在すれば、データ処理を実行する（ステップ２０３）。処理が終了すると、処理結果をキャッシュするようキャッシュ装置１に指示を送る（ステップ２０４）。このとき、処理された結果も同時に送信する。もし、キャッシュ対象データの処理の指示が存在しなければ、ステップ２０３，２０４をスキップする。これらの処理が終了すると、データ処理以外の、処理結果を利用する処理を含めた処理を行う（ステップ２０５）。そして、自身のＩＤを含んだパケット情報をキャッシュ装置１に送り、処理を終える（ステップ２０６）。
【００２３】
次に、パケット処理装置２間でキャッシュの共有が可能である場合の動作を図７により説明する。図６の場合との違いは、ステップ２０２におけるキャッシュ対象データの処理の指示の存在の処理以降で、特に指示が存在しない場合の動作である。指示が存在しない場合、パケット処理装置２はキャッシュを共有している別のパケット処理装置２で、同一フローに属するパケットがないか確認する（ステップ２０７）。存在する場合、先に処理結果を利用しない処理を行い、処理終了後は処理中のデータがキャッシュ１７に書き込まれたか否かを確認し、もし書き込まれていれば、処理結果を用いた処理を行い、そうでなければキャッシュ１７にデータが書き込まれるまで待機する（ステップ２０８）。その他の処理は図６と同じである。
【００２４】
次に、パケットの処理が終了した後にキャッシュ装置１がパケットを到着順に並べる処理を図８により説明する。パケット情報をパケット処理装置２から受信すると（ステップ３０１）、パケットのフローＩＤとパケットを処理したパケット処理装置２のＩＤを確認する（ステップ３０２）。そして、順序データベース１９内にある、フローＩＤごとのＦＩＦＯキューの先頭にある、パケット処理装置のＩＤと比較し、次に送信するパケットかどうかを確認する（ステップ３０３）。ＩＤが一致しなければ、先に到着しているパケットがまだ処理中であるため、待機させる（ステップ３０４）。もし一致すれば、現在処理中のパケットのうち、一番先に到着したものであるため、次に送信する（ステップ３０５）。このとき、ＦＩＦＯキューの先頭にあった、送信したパケットを処理していたパケット処理装置のＩＤを削除し、次に送信するパケットを処理しているパケット処理装置のＩＤを見る（ステップ３０６）。その後、送信したパケットより先に処理が終了し、待機しているパケットがないか確認する（ステップ３０７）。もし存在すれば、ＦＩＦＯキューの先頭に位置するＩＤと、待機しているパケットを処理していたパケット処理装置のＩＤを比較し（ステップ３０８）、同じであればパケットを送信する（ステップ３０５）。そして再びステップ３０６の処理を行う。もし、ＩＤが異なれば、まだ先に到着しているパケットが処理中であるため、再び待機する（ステップ３０９）。
【００２５】
なお、パケット処理装置２間でキャッシュを共有できる場合の具体例としては、１プロセッサ内でマルチスレッディングを行っており、各スレッドがコアのキャッシュを互いに使用する場合などがある。その具体的な動作については後ほど述べる。
【００２６】
次に、具体的なパケット処理例を、図９以降の各図を用いて説明する。図９では、キャッシュ装置１がいかなるエントリももっていない状況下でフローＩＤとしてＡをもつフローＡのパケットが到着した時の状況を示す。キャッシュ装置１はエントリがないため、キャッシュ対象データの処理を指示する情報を、パケット処理に使用するパケット情報に記載し、パケット処理装置２にアルゴリズムにしたがって送信する。ここではアルゴリズムにより、パケット処理装置２3にパケットを処理させることにしたとする。キャッシュ装置１はフローＡのパケットがパケット処理装置２3で処理されていることを順序データベース１９で管理する。このため、順序データベース１９におけるフローＩＤがＡのエントリとなるＦＩＦＯキューにパケット処理装置２3のＩＤである３を入れる。
【００２７】
図１０はその後、フローＩＤがＢのパケットとフローＡのパケットの２つめが到着したときを示す。フローＩＤがＢのパケットは図９におけるフローＡのパケットと同じ処理を行う。そして、フローＩＤがＡの２つめのパケットが到着すると、キャッシュ装置１はフローＩＤがＡに対するキャッシュ情報を有するかどうか確認する。キャッシュ情報がまだなく、順序データベース１９にパケットを処理しているパケット処理装置のＩＤが存在することを確認すると、キャッシュ装置１は現在フローＡのパケットがパケット処理装置２でデータ処理中であると判断し、２つめのパケットを待機させる。
【００２８】
図１１で、パケット処理装置２3でのフローＡの１つめのパケットに対するキャッシュ対象データの処理が終了したときの様子を説明する。パケット処理装置２3はデータ処理が終了すると、キャッシュ装置１に処理結果を送信する。これを受け、キャッシュ装置１は処理結果をキャッシュする。これと同時に待機していたフローＡの２つめのパケットのパケット処理装置を決定し、そこにパケット情報を送る。このとき、アップデートされたキャッシュの情報をパケット情報の一部に加えて送信する。ここで、２つめのパケットをパケット処理装置２2で処理すると考える。キャッシュ装置１はパケットをパケット処理装置２2に送るときに、順序データベース１９内のフローＡに対するＦＩＦＯキューの後ろにパケット処理装置２2のＩＤである２を挿入する。
【００２９】
図１２にフローＡの１つめのパケットの処理が終了し、情報がキャッシュ装置１に戻されるときの動作が記載されている。キャッシュ装置１はパケット処理装置２3からパケット情報を受信すると、順序データベース１９を参照し、フローＡにおける次に送信するパケットがどこで処理されていたかを確認する。この場合、パケット処理装置２3で処理されているパケットが次に送信するものであることを示されており、到着したパケットが次に送信するパケットであることがわかる。これを受けてキャッシュ装置１は次の処理を行うパケット処理装置にパケットを送る。そして、順序データベース１９の先頭にあった、パケット処理装置２2を示すＩＤを削除する。これにより、次に送信するパケットがパケット処理装置２2で処理されていることがわかる。そして、現在フローＡのパケットがキャッシュ装置１で待機させられているかどうかを確認する。この場合、パケットは待機させられていないので、処理は終了する。もし待機させられていたら、ＦＩＦＯキューの先頭のＩＤと待機しているパケットが処理されていたパケット処理装置２のＩＤを比較し、送信するかどうかを判定するという処理が走る。
【００３０】
図１３で、フローＩＤがＡの３番目のパケットが新たに到着し、パケット処理装置２2で処理されている２番目のパケットより先に処理が終了したときの動作の説明を行う。キャッシュ装置１は順序データベース１９から次に送信するパケットは現在処理装置２2で処理されていることがわかるため、到着した３番目のパケットを待機させる。その後、２番目のパケットを送信した後に、順序データベース１９が３番目のパケットを送信することを示すため、そのときに３番目のパケットを送信する。
【００３１】
最後に、パケット処理装置２の一部でキャッシュを共有できるときの動作例を図１４に示す。この例では、パケット処理装置２として、複数のタスクを１つのプロセッサリソースを用いて実行するマルチスレッディング可能なプロセッサ（パケット処理装置を複数収容した装置）を利用する。この中では、前回までの説明におけるパケット処理装置２が１つのスレッドに相当する。同一のプロセッサで走るスレッド同士では、プロセッサ内に存在するキャッシュを共有することが可能となる。この場合、フローＡの１番目のパケットがプロセッサ３のスレッド１番で処理されているとすると、２番目のパケットが到着したとき、キャッシュ装置１は２番目のパケットの処理をプロセッサ３のいずれかのスレッドに行わせる。１番目のパケットのキャッシュ対象データ処理が終了すると（図１５）、キャッシュ結果はキャッシュ装置１と１番目のパケットを処理したプロセッサのキャッシュに書き込まれる。２番目のパケットにおけるキャッシュ対象のデータを使用した処理はプロセッサのキャッシュに書き込まれたデータを用いて行われる。２番目のパケットを行う際、キャッシュにデータがある場合はそれを利用して処理を行い、ない場合は先にキャッシュ対象のデータを使用しない処理を行う。そして、キャッシュ対象データ処理結果を使用する処理は、処理結果がキャッシュに書き込まれるまで待つ。そのほかの処理は前述の説明と同じ動作を行う。
【００３２】
なお、キャッシュ装置およびパケット処理装置の機能は、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータ内の揮発性メモリのように、一定時間プログラムを保持しているものを含む。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態のキャッシュシステムの構成図である。
【図２】キャッシュ装置のブロック図である。
【図３】パケット処理装置のブロック図である。
【図４】パケット分配時（マルチスレッド不可）のキャッシュ装置の動作を示すフローチャートである。
【図５】パケット分配時（パケット処理装置キャッシュ共有可）のキャッシュ装置の動作を示すフローチャートである。
【図６】パケット処理装置の動作を示すフローチャートである。
【図７】パケット処理装置（キャッシュ共有可）の動作を示すフローチャートである。
【図８】ソート時のキャッシュ装置の動作を示すフローチャートである。
【図９】具体的なパケット処理例（その１）を示す図である。
【図１０】具体的なパケット処理例（その２）を示す図である。
【図１１】具体的なパケット処理例（その３）を示す図である。
【図１２】具体的なパケット処理例（その４）を示す図である。
【図１３】具体的なパケット処理例（その５）を示す図である。
【図１４】具体的なパケット処理例（その６）を示す図である。
【図１５】具体的なパケット処理例（その７）を示す図である。
【符号の説明】
【００３４】
１    キャッシュ装置
２，２1〜２4    パケット処理装置
１１    プロセッサ
１２    キャッシュアップデート部
１３    キャッシュ検索部
１４    パケット分配部
１５    ソーター
１６    記憶媒体
１７    キャッシュ
１８    分配アルゴリズム
１９    順序データベース
２１    キャッシュ有無判定部
２２    キャッシュ対象データ処理部
２３    キャッシュアップデート部
２４    パケット処理部
２５    記憶媒体
１０１〜１１３，２０１〜２０８，３０１〜３０８    ステップ
【図１】
2008131351.tif 000003
【図２】
2008131351.tif 000004
【図３】
2008131351.tif 000005
【図４】
2008131351.tif 000006
【図５】
2008131351.tif 000007
【図６】
2008131351.tif 000008
【図７】
2008131351.tif 000009
【図８】
2008131351.tif 000010
【図９】
2008131351.tif 000011
【図１０】
2008131351.tif 000012
【図１１】
2008131351.tif 000013
【図１２】
2008131351.tif 000014
【図１３】
2008131351.tif 000015
【図１４】
2008131351.tif 000016
【図１５】
2008131351.tif 000017