(57)【要約】【課題】検索対象のデータを迅速に取得可能な情報処理装置を提供する。【解決手段】情報処理方法は、複数のブロックに分かれたメモリを有する情報処理装置で実行される。情報処理装置は、データの検索に使用する検索キーのハッシュ値を計算する。情報処理装置は、ハッシュ値を用いて、検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定する。情報処理装置は、格納ブロックに含まれるエントリの使用状況を情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、格納ブロックから読み込む。情報処理装置は、データの登録に使用されていることが使用情報に記録されているエントリのいずれかから、検索キーに対応付けられたデータを抽出する。【選択図】図２
2016224840.tif 000002
【特許請求の範囲】
【請求項１】
複数のブロックに分かれたメモリを有する情報処理装置に、
データの検索に使用する検索キーのハッシュ値を計算し、
前記ハッシュ値を用いて、前記検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定し、
前記格納ブロックに含まれるエントリの使用状況を前記情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、前記格納ブロックから読み込み、
データの登録に使用されていることが前記使用情報に記録されているエントリのいずれかから、前記検索キーに対応付けられたデータを抽出する
処理を行わせることを特徴とする情報処理方法。
【請求項２】
前記情報処理装置に、
前記メモリに登録する対象のデータである登録対象データを取得すると、前記登録対象データの検索に使用する検索キーのハッシュ値である他のハッシュ値を計算し、
前記他のハッシュ値に対応づけられたブロックを格納先のブロックとして特定し、
前記格納先のブロックから、前記格納先のブロックに含まれるエントリの使用状況を前記プロセッサが１回の命令で読み込み可能なビット長で表わした情報を読み込み、
前記格納先のブロック中でデータの登録に使用されていないエントリのいずれかに、前記登録対象データを記録する
処理をさらに行わせることを特徴とする請求項１に記載の情報処理方法。
【請求項３】
前記格納先のブロックにデータの登録に使用されていないエントリがない場合、前記格納先のブロックとは異なる他のブロックから処理対象として選択した対象エントリに、前記登録対象データを登録し、
前記対象エントリに、前記他のハッシュ値を記録することにより、前記対象エントリを前記格納先のブロックの拡張領域として使用する
処理を前記情報処理装置に行わせることを特徴とする請求項２に記載の情報処理方法。
【請求項４】
前記格納ブロックに検索対象のデータが記録されていない場合、前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリを、前記複数のブロックのうちの前記格納ブロック以外のブロックで検索し、
前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリの情報を前記検索対象のデータとして抽出する
処理を前記情報処理装置に行わせることを特徴とする請求項３に記載の情報処理方法。
【請求項５】
複数のブロックに分かれたメモリを有する情報処理装置であって、
データの検索に使用する検索キーのハッシュ値を計算すると共に、前記ハッシュ値を用いて、前記検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定する特定部と、
前記格納ブロックに含まれるエントリの使用状況を前記情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、前記格納ブロックから読み込むと共に、データの登録に使用されていることが前記使用情報に記録されているエントリのいずれかから、前記検索キーに対応付けられたデータを抽出する抽出部
を備えることを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置と情報処理装置で行われるデータの処理に関する。
【背景技術】
【０００２】
複数の装置を含むネットワーク中の通信装置は、処理対象のパケットの処理などに関する情報の特定を行う際に、特定する対象となる情報を保持しているテーブルの検索処理を行う。例えば、ルータ、スイッチ、ゲートウェイなどとして動作する装置は、処理対象のパケットの出力ポートなどを特定する際に、処理対象のパケットから取得したアドレスやポートの情報をキーとした検索処理を行う。このような処理を行う場合、通信装置が保持している情報量が多くなると、検索に時間がかかってしまう。そこで、高速検索を行うために、通信装置に、ハッシュ関数を用いた検索処理を行わせる場合がある。
【０００３】
図１は、ハッシュ関数を用いた検索テーブルと検索テーブルの更新処理の例を説明する図である。通信に使用されるフロー情報が検索テーブルに記録されるが、検索にハッシュ関数が用いられない場合、使用され得るフロー情報が記録されている全てのメモリ領域（図１のｍ１）が検索対象とされる。一方、検索処理にハッシュ関数を用いる通信装置は、送信元のＩＰ（Internet Protocol）アドレスなどのフロー情報の一部をハッシュ関数で演算し、得られたハッシュ関数に対応する領域にフロー情報を記録する。この場合、メモリ領域は、図１のｍ２に示すようにハッシュ値に対応する複数の領域に分けられる。このため、フロー情報に対応付けられた情報の検索の際の検索対象は、フロー情報の一部とハッシュ関数を用いて算出されたハッシュ値に対応付けられた領域に限定される。従って、ハッシュ関数を用いることにより検索にかかる時間が短縮される。さらに、個々のハッシュ値に対応付けられた領域には、その領域の先頭から順に複数のエントリが記録されている。例えば、図１のｍ３に示すように、あるハッシュ値に対応するブロックに１０のエントリが含まれ、フローＡ〜Ｈの情報が記録される場合、領域の先頭から順に８つのエントリにフローの情報が記録され、末尾の２エントリ分の領域は空きエントリとなる。このため、検索処理の際には、検索対象のフローの情報から得られたハッシュ値に対応付けられた領域の先頭のエントリから検索が行われ、空きエントリが検出されると、処理対象の領域の末尾までの検索が終了したと判定される。なお、一部のエントリが削除された場合は、使用されている複数のエントリの間に空きエントリが発生しないように検索テーブルの更新処理が行われる。
【０００４】
例えば、図１のｍ４に示すように、フローＤの情報が削除されたとする。すると、フローＤに関する情報の記録に使用されていた領域に、フローＥの情報が登録し直される。同様に、フローＦ〜Ｈの情報も、有効なエントリの間に使用されていないエントリが発生しないように、それぞれ登録領域が変更される。その結果、更新処理が終わった後の検索テーブルは、図１のｍ５に示す通りになる。
【０００５】
関連する技術として、データと識別情報を格納するデータ部と、第１索引テーブル、第２索引テーブルを保持する管理装置が提案されている（例えば、特許文献１）。第１索引テーブルは、識別情報から求めたハッシュ値、識別情報、格納位置を格納するブロックを有し、第２索引テーブルは、各ブロックの見出しとなるハッシュ値を記憶する。管理装置は、識別情報を取得すると、識別情報から得たハッシュ値と第２索引テーブルを用いて、ブロックを特定し、第１索引テーブル中の特定したブロック中の格納位置を用いて、データを取得する。また、ブロック番号と各ブロックに記録された情報のハッシュ値レンジを対応付けたテーブルを、処理対象のファイル名のハッシュ値をキーとして参照することで、処理対象のデータが記録されたブロックを特定する装置も提案されている（例えば、特許文献２）。この装置は、特定したブロックからデータを取得する。連想メモリやフロー制御用メモリで生じる消費電力を低減するために、アクティブにする物理バンクを経路制御用のハッシュ関数を用いて限定する装置も提案されている（例えば、特許文献３）。さらに、検索キーのハッシュ値を用いた検索方法についての提案もある（例えば、特許文献４、５）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平９−９１３０３号公報
【特許文献２】特開２００６−５８９６５号公報
【特許文献３】特開２００６−１６５６０３号公報
【特許文献４】特開平１−１９１２２９号公報
【特許文献５】特開平４−３４４５６８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
検索テーブルにおいて、有効なエントリの間に使用されていないエントリが発生しないように登録領域が決定される場合、エントリの削除に伴い、検索テーブルの更新が発生する。検索テーブルの更新中は、有効なエントリよりも前に空きエントリが発生することなどから、正常な検索ができない。さらに、検索テーブルの更新には時間がかかるため、通信フローの発生や通信フローの終了に起因して、フロー情報の取得が遅延してしまう。また、データの格納先を示す格納位置や、データを格納したブロックの情報を示すテーブルを検索テーブル以外に使用する方法でも、処理対象のデータを取得するまでに複数のテーブルを検索するため、処理に時間がかかってしまう。なお、このような問題は、フロー情報以外の情報を、ハッシュ値を用いて管理する場合にも発生しうる。
【０００８】
本発明では、検索対象のデータを迅速に取得可能な情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
ある態様にかかる情報処理方法は、複数のブロックに分かれたメモリを有する情報処理装置で実行される。情報処理装置は、データの検索に使用する検索キーのハッシュ値を計算する。情報処理装置は、前記ハッシュ値を用いて、前記検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定する。情報処理装置は、前記格納ブロックに含まれるエントリの使用状況を前記情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、前記格納ブロックから読み込む。情報処理装置は、データの登録に使用されていることが前記使用情報に記録されているエントリのいずれかから、前記検索キーに対応付けられたデータを抽出する。
【発明の効果】
【００１０】
情報処理装置は、管理しているデータから、検索対象のデータを迅速に取得できる。
【図面の簡単な説明】
【００１１】
【図１】ハッシュ関数を用いた検索テーブルと検索テーブルの更新処理の例を説明する図である。
【図２】実施形態にかかる検索テーブルと検索テーブルの更新処理の例を説明する図である。
【図３】実施形態にかかる処理の例を説明するフローチャートである。
【図４】情報処理装置の構成の例を説明する図である。
【図５】情報処理装置のハードウェア構成の例を説明する図である。
【図６】第１の実施形態にかかる検索テーブルの例を説明する図である。
【図７】検索テーブルの例を説明する図である。
【図８】エントリに登録される情報の例を説明する図である。
【図９Ａ】登録処理の例を説明するフローチャートである。
【図９Ｂ】登録処理の例を説明するフローチャートである。
【図１０】検索処理の例を説明するフローチャートである。
【図１１】空塞表の長さの求め方の例を説明するフローチャートである。
【図１２】空きエントリの検索方法の例を説明するフローチャートである。
【図１３】パケット転送の際に行われる処理の例を説明するフローチャートである。
【図１４】統計情報収集の際に行われる処理の例を説明するフローチャートである。
【図１５】パケットのフィルタリングの際に行われる処理の例を説明するフローチャートである。
【図１６】パケット転送の際に行われる処理の例を説明するフローチャートである。
【図１７】エントリの登録情報が削除された場合のブロック中の情報の例を説明する図である。
【図１８】エントリ中の登録情報の削除の際に行われる処理の例を説明するフローチャートである。
【図１９】第２の実施形態にかかる検索テーブルの例を説明する図である。
【図２０】第２の実施形態にかかる検索テーブルと登録の例を説明する図である。
【図２１Ａ】登録処理の例を説明するフローチャートである。
【図２１Ｂ】登録処理の例を説明するフローチャートである。
【図２２】空きエントリの検索方法の例を説明するフローチャートである。
【図２３Ａ】検索処理の例を説明するフローチャートである。
【図２３Ｂ】検索処理の例を説明するフローチャートである。
【図２４】エントリ中の登録情報の削除の際に行われる処理の例を説明するフローチャートである。
【発明を実施するための形態】
【００１２】
図２は、実施形態にかかる検索テーブルと検索テーブルの更新処理の例を説明する図である。実施形態にかかる情報処理装置は、図２に示す検索テーブルを備えているものとする。図２のｍ１は、通信に使用されるフロー情報の記録に使用されている全てのメモリ領域であり、各フロー情報は、図２のｍ２に示すように、フロー情報の一部とハッシュ関数から得られたハッシュ値に対応する領域に分類される。図２では、一例として、送信元ＩＰアドレスから得られたハッシュ値が０〜９のいずれかである情報が、ハッシュ値に対応するブロックに記憶されている場合を示す。
【００１３】
図２のｍ１１は、ハッシュ値＝０に対応付けられたブロックに格納される情報の例を示している。ｍ１１に示すブロックは、ブロックの先頭に空塞表５１を格納しており、空塞表５１に続けて、各フローに関する情報を記録するエントリ５２（５２ａ〜５２ｉ）を含む。空塞表５１は、ブロック中の各エントリがフローの情報の格納に使用されているかを表わす情報である。空塞表５１は、そのブロックに格納することが可能なフロー情報の数と同じビット数のビット列であり、また、情報処理装置に備えられているプロセッサが１回の処理で読み込み可能なビット長以下のビット列でもある。以下の説明では、空塞表５１の各ビットは、フロー情報の格納に使用するエントリのうち、先頭のアドレスの番号が小さい順に、下位側のビットから使用状況が記録されるものとする。また、空塞表５１の各ビットの値は、そのビットに対応付けられたエントリにフロー情報が記録されている場合は１、そのビットに対応付けられたエントリにフロー情報が記録されていない場合は０であるとする。図２の例では、各ブロックに９個のエントリがあり、空塞表５１は９ビットである。ｍ１１では、ハッシュ値＝０に対応付けられたブロックでは、先頭から３番目（５２ｃ）、８番目（５２ｈ）、９番目（５２ｉ）が空きエントリであるので、ハッシュ値＝０に対応付けられたブロックの空塞表５１は００１１１１０１１となる。一方、エントリ５２ａ、５２ｂ、５２ｄ〜５２ｇは、フロー情報の格納に使用されているので、それぞれのエントリに対応する空塞表５１中のビットの値が１に設定されている。
【００１４】
このように、実施形態にかかる情報処理装置は、ブロック中のエントリの各々にアクセスしなくても、空塞表５１を用いて、ブロック中でデータが格納されている位置を特定し、処理を行うことができる。例えば、登録済みのフロー情報を用いて、パケットの出力ポートを特定する場合、情報処理装置は、処理対象のフロー情報の送信元ＩＰアドレスから得られたハッシュ値に対応するブロックの先頭の空塞表５１を参照する。情報処理装置は、空塞表５１でのビットの値が１に設定されているビットに対応するエントリを検索対象とすることにより、検索対象のフロー情報に迅速にアクセスできる。
【００１５】
一方、新たなフロー情報を格納する場合、情報処理装置は、送信元ＩＰアドレスのハッシュ値に対応付けられたブロックの空塞表５１において、ビットの値が０に設定されているエントリに新たなフロー情報を格納するとともに、空塞表５１を更新する。例えば、ハッシュ値＝０に対応付けられたブロックに新たなフロー情報を格納する場合、情報処理装置は、ｍ１１に示す空塞表５１を元に、先頭から３番目のエントリ（５２ｃ）が未使用であることを特定する。すると、情報処理装置は、新たなフローの情報をエントリ５２ｃに格納すると共に、エントリ５２ｃに対応するビットの値を１に変更する。エントリ５２ｃに対応するビットは空塞表５１の下位から３番目のビットであるため、空塞表５１は、ｍ１２に示すように、００１１１１１１に変更される。
【００１６】
同様に、格納しているフロー情報の一部を削除する場合、情報処理装置はフロー情報の削除と共に空塞表５１を更新する。例えば、ｍ１２に示す状態からエントリ５２ｄ中の情報を削除する場合、ｍ１３に示すようにエントリ５２ｄの情報を削除すると共に、空塞表５１中でエントリ５２ｄに対応するビットの値を０に更新する。エントリ５２ｄに対応するビットは空塞表５１の下位から４番目のビットであるため、空塞表５１は、ｍ１３に示すように、００１１０１１１に変更される。
【００１７】
なお、図２を参照しながら説明した処理や実施形態は一例であり、実装に応じた変更が行われうる。例えば、各ブロック中のエントリの数や空塞表５１のビット長は、実装に応じて変更される。さらに、図２では、分かりやすくするために、各ブロックに１つのハッシュ値が対応付けられる場合を例として説明したが、各ブロックに複数のハッシュ値が対応付けられても良い。さらに、ハッシュ値の計算に使用されるフロー情報は、送信元ＩＰアドレスに限られず、送信元ＩＰアドレスと宛先ＩＰアドレスの組み合わせや、アドレス情報とポート情報の組み合わせであっても良い。また、情報処理装置に複数のプロセッサが含まれている場合、プロセッサごとに処理対象のメモリ領域を割り当てられても良い。また、空塞表５１中の各ビットとエントリの対応は、空塞表５１からエントリの使用状況が特定できる任意の関係でよく、例えば、空塞表５１の下位ビットほど、先頭アドレスの値が大きいエントリに対応付けられても良い。
【００１８】
図３は、実施形態にかかる処理の例を説明するフローチャートである。図３は、情報処理装置に複数のプロセッサが搭載されている場合の処理の例である。情報処理装置１０は、処理対象のフローの情報を取得すると、取得したフローの情報を用いて、ハッシュ値を計算する（ステップＳ１、Ｓ２）。情報処理装置は、ハッシュ値を用いて、処理対象のフロー情報に関する処理を行うプロセッサを決定する（ステップＳ３）。プロセッサは、ハッシュ値を用いて、処理対象のフローの情報の格納先のブロックを特定する（ステップＳ４）。情報処理装置は、格納先のブロックの空塞表を用いて、格納先のブロックの使用状況を認識するとともに、処理対象のフロー情報に対する処理を行う（ステップＳ５）。
【００１９】
図２、図３を参照しながら説明したように、空塞表を用いると、一部のエントリの情報が削除されたことに伴う他のエントリの格納位置の変更が発生しない。このため、検索テーブルの更新にかかる時間が短縮される。この結果、情報処理装置は、検索テーブルを有効に使用して迅速にフローの処理を行うことができる。
【００２０】
実施形態にかかる方法では、空塞表５１は、各ブロック内に、プロセッサが１回の処理で読み込み可能なビット長以下のビット列として格納されている。このため、実施形態にかかる情報処理装置のプロセッサは、フロー情報のハッシュ値によって特定されたブロックへの１回のアクセスによって、そのブロックの空塞表５１を取得することができる。換言すると、実施形態にかかる情報処理装置では、フロー情報のハッシュ値によって特定されたブロックへの１回のアクセスによって、処理対象のブロックの使用状況を取得することができる。その後は、行われる処理がフロー情報の検索であれば、使用中のエントリが検索対象となる。一方、行われる処理がフロー情報の登録であれば、使用されていないエントリが処理対象として選択される。このように、実施形態にかかる情報処理装置では、複数のテーブル等を参照するよりも迅速にアクセス先のブロックが特定できる上、空塞表を用いることにより、アクセス先のブロック中で処理対象とするエントリも特定できる。従って、実施形態にかかる情報処理装置では、データの検索や登録などの管理が迅速に行われる。
【００２１】
なお、以上の処理はフロー情報が処理対象である場合を例として説明したが、他の情報が同様に管理対象や検索対象となっても良い。すなわち、図２、図３を参照しながら説明した処理や検索テーブルを他のデータの処理に適用することで、情報処理装置は、処理対象のデータを迅速に処理できる。
【００２２】
＜装置構成＞
図４は、情報処理装置１０の構成の例を説明する図である。情報処理装置１０は、物理ポート１１（１１ａ〜１１ｃ）、通信処理部１２、振分部１３、制御部２０（２０ａ〜２０ｃ）、記憶部４０を備える。制御部２０ａ〜２０ｃは、各々が、取得部２１、特定部２２、抽出部２３、更新部２４、パケット処理部３０を有する。パケット処理部３０は、パケット転送処理部３１、統計処理部３２、フィルタリング処理部３３を有する。記憶部４０は、検索テーブル４２を格納する。検索テーブル４２は、複数のブロックを含み、個々のブロックには、空塞表とフロー情報の格納に使用される複数のエントリが含まれている。また、検索テーブル４２は、適宜、情報処理装置１０によって集計されている統計情報などの他の情報も含んでも良い。
【００２３】
物理ポート１１と通信処理部１２は、情報処理装置１０と他の装置との間の間でのパケットの送受信を行う。振分部１３は、物理ポート１１と通信処理部１２を介して他の装置から受信したパケットを、処理対象のパケットを処理する制御部２０（２０ａ〜２０ｃ）に振り分ける。取得部２１は、処理対象のパケットからフロー情報を取得する。特定部２２は、処理対象のパケットのフロー情報とハッシュ関数を用いてハッシュ値を計算し、得られたハッシュ値を用いて処理対象のフロー情報の処理に使用するブロックを特定する。抽出部２３は、処理対象のフロー情報が既に検索テーブル４２に格納されている場合、特定されたブロックから、パケットの処理に使用される情報を抽出する。更新部２４は、処理対象のフロー情報がまだ検索テーブル４２に格納されていない場合、特定されたブロックに、フロー情報やパケットの処理に使用される情報を格納する。
【００２４】
パケット処理部３０は、抽出部２３で抽出された情報を用いてパケットを処理する。パケット転送処理部３１は、抽出部２３で抽出された情報から、転送対象のパケットの出力先ポートを特定し、通信処理部１２や物理ポート１１を介した転送処理を行う。統計処理部３２は、フロー情報に基づいて抽出された情報を用いて、検索テーブル４２中の統計情報を更新する。フィルタリング処理部３３は、フロー情報に基づいて抽出された情報を用いて、パケットのフィルタリング処理を行う。
【００２５】
図５は、情報処理装置１０のハードウェア構成の例を説明する図である。情報処理装置１０は、プロセッサ１０１、メモリ１０２、ネットワーク接続装置１０３、バス１０４を有する。プロセッサ１０１、メモリ１０２、ネットワーク接続装置１０３は、バス１０４により、互いにデータが入出力可能になるように接続されている。
【００２６】
プロセッサ１０１は、ＣＰＵ（Central Processing Unit）やＮＰＵ（Network Processing Unit）を含む任意の処理回路とすることができる。プロセッサ１０１は、振分部１３および制御部２０として動作する。なお、図５には、プロセッサ１０１は１つだけ図示しているが情報処理装置１０に含まれるプロセッサの数は任意である。複数のプロセッサ１０１が情報処理装置１０に含まれる場合、振分部１３として動作するプロセッサ１０１と制御部２０として動作するプロセッサ１０１は、同じであっても異なっていても良い。メモリ１０２は、記憶部４０として動作する他、プロセッサ１０１の処理に使用されるデータやプログラムなどを記憶する。ネットワーク接続装置１０３は、物理ポート１１および通信処理部１２として動作する。
【００２７】
＜第１の実施形態＞
以下、情報処理装置１０が複数のプロセッサを備え、検索テーブル４２中の各ブロックに複数のハッシュ値が対応付けられている場合を例として、情報処理装置１０が受信したパケットを処理する際に行う動作の例を説明する。また、ハッシュ値の計算に、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号等の組合せが用いられることにより、各フローは他のフローと異なるハッシュ値に対応付けられる場合を例とする。
【００２８】
振分部１３は、受信パケットを、フローごとに、制御部２０のいずれかに出力する。このとき、振分部１３は、各制御部２０を実現しているプロセッサ１０１間での負荷分散が行われるように、出力先の制御部２０を選択する。振分部１３が負荷分散のために行う処理は、任意の負荷分散方法である。例えば、フロー情報から求めたハッシュ値を、情報処理装置１０中のプロセッサの総数で割ったときに得られる剰余に応じて、出力先の制御部２０が決定されても良い。また、振分部１３は、受信パケットを、受信ポートの番号と共に、制御部２０に出力する。以下、受信パケットが制御部２０ａ中の取得部２１に出力された場合を例として説明するが、受信パケットが他の制御部２０に出力された場合に行われる処理も同様である。
【００２９】
図６は、第１の実施形態にかかる検索テーブルの例を説明する図である。図６のｍ２１は、制御部２０ａが処理するフロー情報の記録に使用されている全てのメモリ領域であり、各フロー情報は、ｍ２２に示すように、フロー情報から得られたハッシュ値に対応するブロックに分類される。取得部２１は、入力されたパケットからフロー情報を取得して、特定部２２に出力する。特定部２２は、フロー情報とハッシュ関数からハッシュ値を計算するとともに、そのフローに関する情報の格納に使用されるブロックを識別するブロック識別子（Ｊ）を求める。ここで、ブロック識別子Ｊは、ハッシュ値を、空塞表５１のビット長で割ったときに得られる商の値とする。例えば、図６のｍ２３に示すように、空塞表５１のビット長が９ビットであるとする。すると、ハッシュ値＝０のフローの情報は、Ｊ＝０のブロックに記録される。一方、ハッシュ値＝２０のフローの情報は、Ｊ＝２のブロックに格納される。各ブロックには、ｍ２３に示すように、空塞表５１とフローの情報の格納に使用されるエントリが含まれている。第１の実施形態においても、空きエントリへの新たなフロー情報の登録や、フロー情報の削除処理は、図２のｍ１２、ｍ１３を参照しながら説明した手順と同様の処理により行われる。
【００３０】
図７は、検索テーブル４２の例を説明する図である。情報処理装置１０でのフロー情報の格納に使用される検索テーブル４２のメモリ領域全体を図７のｍ１に示す。検索テーブル４２は、情報処理装置１０に含まれている各制御部２０がアクセスする領域ごとに分かれている。図７のｍ１では、領域Ａ１〜Ａ３が図示されているが、領域の数は任意である。図７では、領域Ａ３が制御部２０ａによって処理される領域であるとする。各端末２０がアクセスする領域には、ｍ３１に示すように、複数のブロックが含まれ、各ブロックには、ｍ３２に示すように、空塞表５１と複数のエントリが含まれる。
【００３１】
図８のＥは、エントリに登録される情報の例を示す。図８の例では、エントリは、空塞表、登録状態、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号、プロトコルＩＤ、入力ポート番号、制御情報、出力ポート番号が含まれる。さらに、エントリには、パケットの受信数、受信バイト数、転送パケット数、転送バイト数、空塞位置、ブロック識別子、登録位置などの情報も含まれる。エントリに含まれる各情報の用途は、用途欄に記載されている通りである。例えば、空塞表は、アクセス先のエントリを特定するための管理情報として使用され、送信元ＩＰアドレス等の情報は、フロー情報に対応付けられた情報の検索に用いられる情報（検索情報）である。転送処理の際の出力ポートは、検索によって特定され、パケット転送処理部３１に出力される情報であるので、図８では出力情報に分類されている。図８のＥに示す例では、各エントリには、管理情報、検索情報、制御情報、出力情報、統計情報の各々として用いられる情報が含まれているが、エントリ中の情報は実装に応じて変更され得る。例えば、制御情報、パケットの受信数、受信バイト数、転送パケット数、転送バイト数などの情報はエントリに含まれていなくてもよい。
【００３２】
図８のｍ４２では、各エントリが図８のＥに示す情報要素を含むエントリである場合のブロックの例を、エントリＥ０、Ｅ１、Ｅ２の詳細が分かるように示している。図８のＥに示すエントリが使用される場合、各エントリに空塞表があるため、各ブロックには、図８のｍ４２に示すように各エントリの先頭に空塞表の領域が確保される。しかし、ブロック中のエントリの使用状況の取得を容易にするため、ブロック中の各エントリの登録情報は、ブロックの先頭のエントリの空塞表に記録される。空塞位置は、そのエントリの使用状況を記録している空塞表の特定に使用される情報である。例えば、図８のｍ４２に示すブロックでは、エントリＥ０〜Ｅ２のいずれにおいても、空塞位置（Ｅの項目１５）として、エントリＥ０の空塞表を特定する情報が記録される。登録状態（Ｅの項目２）は、エントリにフロー情報が登録されているかを示す値であり、空塞表と同様に、空のエントリの場合は登録状態＝０、フロー情報を含むエントリでは、登録状態＝１が記録される。送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号は、処理対象のパケットが送受信されるフローの情報である。入力ポートは、エントリに登録されているフローのパケットを、情報処理装置１０が受信する際に使用したポートの番号である。出力ポートは、エントリに登録されているフローのパケットを、情報処理装置１０が転送する際に使用したポート番号であり、各フローの最初のパケットの転送処理の際に決定される。プロトコルＩＤは、フローの処理に使用されているプロトコルの識別に使用される。制御情報は、そのエントリに登録されているフローのパケットに対して情報処理装置１０が行う処理の種類を示す。制御情報には、パケット転送、統計情報収集、フィルタリングなどが指定される。ブロック識別子には、そのエントリの情報が記録されているブロックを識別する情報が記録されるが、第１の実施形態では、各エントリはそのエントリが含まれているブロックに対応付けられた情報を記録するため、エントリから省略されうる。登録位置は、各エントリの情報の先頭アドレス等であり、オペレータの処理に使用されるが、実装に応じて省略されうる。
【００３３】
以下、情報処理装置１０で行われる処理の詳細を、フロー情報の登録、登録されたフロー情報を用いた処理、フロー情報の削除に分けて説明する。
【００３４】
（ａ）フロー情報の登録
図９Ａと図９Ｂは、登録処理の例を説明するフローチャートである。以下の説明では、フロー情報のうちでハッシュ値の計算に使用される情報とその他の情報を区別しやすくするために、あるフローに関する情報のうち、ハッシュ値の検出に使用する情報要素を「検索キー」と記載することがある。以下の説明では、各エントリに含まれる情報要素が図８に示すとおりである場合を例として説明するが、各エントリに登録される情報要素に応じて、処理が変更されることがある。例えば、エントリに登録位置が含まれない場合、ステップＳ１８の処理は省略されうる。
【００３５】
取得部２１は、通信処理部１２と振分部１３を介して、受信パケットを取得する。なお、このとき、取得部２１には、受信パケットの受信に使用した物理ポート１１の識別情報も通知される。取得部２１は、受信パケットの送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル識別子、送信元ポート番号、宛先ポート番号を、検索キーとして抽出する（ステップＳ１１）。ここで、プロトコル識別子は、パケットの送信に使用されているプロトコルを一意に識別する任意の情報である。特定部２２と抽出部２３は、受信パケットのフロー情報が既に登録されているかを判定するために、検索キーを用いて、受信パケットのフロー情報を記録しているエントリの検索を行う（ステップＳ１２）。エントリ検索の詳細については、図１０を参照しながら説明する。更新部２４は、抽出部２３での検索結果を取得して、受信パケットに関するフロー情報が登録済みであるかを判定する（ステップＳ１３）。抽出部２３が受信パケットのフロー情報を格納したエントリの検索に成功すると、更新部２４は、受信パケットを含むフローの情報は既に登録済みであると判定して、処理を終了する（ステップＳ１３でＹｅｓ）。
【００３６】
抽出部２３が受信パケットのフロー情報を格納したエントリの検索に失敗すると、更新部２４は、受信パケットを含むフローの情報は未登録であると判定して、新たなフロー情報の登録が可能な空きエントリを検索する（ステップＳ１３でＮｏ、ステップＳ１４）。空きエントリの検索処理の詳細については、図１２を参照しながら説明する。なお、空きエントリは、検索キーのハッシュ値に対応付けられたブロックの空塞表において、登録に使用されていないことが記録されているエントリである。検索キーのハッシュ値に対応付けられたブロック中に空きエントリがない場合、更新部２４は、登録に失敗したと判定して処理を終了する（ステップＳ１５でＮｏ、ステップＳ１６）。
【００３７】
検索キーのハッシュ値に対応付けられたブロック中で空きエントリを発見した場合、更新部２４は、空きエントリに受信パケットを含むフロー情報を設定する（ステップＳ１７）。このとき、更新部２４は、エントリ中の送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号、プロトコルＩＤには、受信パケットから得られた情報を記録する。さらに、更新部２４は、入力ポート番号のフィールドには、受信パケットの受信ポートの番号を記録する。更新部２４は、受信パケットのフロー情報に対応付けられた制御の内容を予め記憶部４０に記憶している場合、エントリ中の制御情報フィールドに、記憶している情報を格納する。一方、受信パケット中に制御内容が含まれている場合、更新部２４は、受信パケットから特定した制御内容を制御情報フィールドに格納する。更新部２４は、受信パケットが他の装置に転送される場合、パケット転送処理部３１に受信パケットを出力するとともに、出力ポートの情報を要求する。更新部２４は、パケット転送処理部３１から出力ポートの情報を取得すると、エントリ中の出力ポートフィールドに記録する。さらに、更新部２４は、統計処理部３２に受信パケットを出力すると共に、受信パケットについてのエントリの先頭アドレスを統計処理部３２に通知する。統計処理部３２は、受信パケットを用いた統計処理を行うと、更新部２４から通知されたエントリ中のパケットの受信数、受信バイト数、転送パケット数、転送バイト数などの統計情報を、通知されたアドレスから開始するエントリに記録する。更新部２４は、フロー情報を登録したエントリ中に登録位置を設定する（ステップＳ１８）。更新部２４は、処理対象のエントリの情報を記録している空塞表５１を更新する（ステップＳ１９）。
【００３８】
なお、図９ＡのステップＳ１３において、フロー情報が登録済みであると判定された場合においても、統計処理部３２での統計処理は行われ得る。この場合、抽出部２３は、受信パケットのフロー情報が登録されていることを特定すると、フロー情報が登録されているエントリの先頭アドレスの情報と共に、受信パケットを統計処理部３２に出力する。統計処理部３２は、受信パケットを用いて処理対象のフローの統計情報を更新すると、抽出部２３から通知されたアドレスを用いて特定したエントリの統計情報を更新する。
【００３９】
図１０は、検索処理の例を説明するフローチャートである。図１０は、図９ＡのステップＳ１２で行われる処理の例を示している。なお、図１０中のＮは、空塞表５１中で注目するビットのビット数をカウントするために使用される変数である。
【００４０】
特定部２２は、受信パケットから取得された検索キーからハッシュ値を算出する（ステップＳ３１）。特定部２２は、得られたハッシュ値を用いて、処理対象のフロー情報が格納されるブロックのブロック識別子を算出する（ステップＳ３２）。ステップＳ３２において、処理対象のフロー情報が格納されるブロックのブロック識別子Ｊは（１）式から求められる。
Ｊ＝ｆｌｏｏｒ（ｈａｓｈ／Ｎ１）  ・・・（１）
ここで、ｆｌｏｏｒ（）は床関数、ｈａｓｈは検索キーから得られたハッシュ値であり、Ｎ１は空塞表５１のビット長である。空塞表５１は、抽出部２３が１回の処理で取得可能なビット長に設定されている。なお、抽出部２３が１回の処理で取得可能なビット長は、情報処理装置１０に備えられているプロセッサ１０１が１回の命令で読み出し可能なビット長と同じ値である。特定部２２は、得られたブロック識別子を抽出部２３に通知する。
【００４１】
抽出部２３は、変数Ｎを１に設定する（ステップＳ３３）。抽出部２３は、特定部２２から通知されたブロック識別子に対応するブロックから、各エントリの使用状況を表わす空塞表５１を取得する。抽出部２３は、空塞表５１の最下位ビットからＮビット目のビットの値が１（塞、使用中）に設定されているかを判定する（ステップＳ３４）。空塞表５１の最下位からＮ番目のビットの値が１に設定されている場合、抽出部２３は、最下位からＮ番目のビットに対応するエントリに記録されている情報を読み出す（ステップＳ３４でＹｅｓ、ステップＳ３５）。受信パケットのフロー情報と読み出した情報が一致すると、抽出部２３は、受信パケットのフロー情報はＪ番目のブロックのＮ番目のエントリに登録されていると判定して処理を終了する（ステップＳ３６でＹｅｓ、ステップＳ３９）。
【００４２】
受信パケットのフロー情報と読み出した情報が一致しない場合、抽出部２３は、変数Ｎを１つインクリメントする（ステップＳ３６でＮｏ、ステップＳ３７）。抽出部２３は、変数ＮがＪ番目のブロックに含まれているエントリ数を超えたかを判定する（ステップＳ３８）。変数ＮがＪ番目のブロックに含まれているエントリ数を超えていない場合、ステップＳ３４に戻る。変数ＮがＪ番目のブロックに含まれているエントリ数を超えている場合、抽出部２３は、受信パケットのフロー情報は未登録であると判定して処理を終了する（ステップＳ３８でＹｅｓ、ステップＳ４０）。なお、ステップＳ３４において、空塞表５１の最下位ビットからＮビット目のビットの値が１（使用中）に設定されていないと判定された場合もステップＳ３７以降の処理が行われる。
【００４３】
図１０に示すフローチャートでは、ステップＳ３４において、空塞表中で注目しているビットの値が０（未使用）に設定されている場合に、変数Ｎをインクリメントして、注目するビットを変更する。すなわち、検索処理において、情報処理装置１０は、フロー情報の格納に使用されていないエントリに対する処理を行わずに、フロー情報が格納されているエントリを処理対象としている。この処理により、ブロック中でフロー情報が格納されているエントリを集めて配置しなくても良くなるため、検索テーブル４２の更新にかかる時間が短くなる。従って、図２や図６を参照しながら説明したように、情報処理装置１０では、迅速にデータを検索できる。
【００４４】
図１１は、空塞表５１の長さの計算例を説明するフローチャートである。特定部２２は、検索処理を行うためのビット幅が自動設定されるかを判定する（ステップＳ５１）。検索処理を行うためのビット幅が自動設定される場合、特定部２２は、プロセッサ１０１に読み込まれているカーネルの処理に使用されるビット幅（Ｘ）とプロセッサ１０１の演算レジスタビット幅（Ｙ）を取得する（ステップＳ５２）。特定部２２は、カーネルの処理に使用されるビット幅（Ｘ）とプロセッサ１０１の演算レジスタビット幅（Ｙ）のいずれも１６ビットであるかを判定する（ステップＳ５３）。ＸとＹのいずれもが１６ビットである場合、特定部２２は、空塞表５１の長さ（Ｎ１）は１６ビットであると判定する（ステップＳ５３でＹｅｓ、ステップＳ５４）。ＸとＹのいずれか１つ以上が１６ビットではない場合、特定部２２は、ＸとＹのいずれもが３２ビットであるかを判定する（ステップＳ５３でＮｏ、ステップＳ５５）。ＸとＹのいずれもが３２ビットである場合、特定部２２は、空塞表５１の長さ（Ｎ１）は３２ビットであると判定する（ステップＳ５５でＹｅｓ、ステップＳ５６）。ＸとＹのいずれか１つ以上が３２ビットではない場合、特定部２２は、ＸとＹは、３２ビットと６４ビットの組み合わせかを判定する（ステップＳ５５でＮｏ、ステップＳ５７）。ＸとＹが３２ビットと６４ビットの組み合わせである場合、特定部２２は、空塞表５１の長さ（Ｎ１）は３２ビットであると判定する（ステップＳ５７でＹｅｓ、ステップＳ５８）。一方、ＸとＹのいずれもが６４ビットである場合、特定部２２は、空塞表５１の長さ（Ｎ１）は６４ビットであると判定する（ステップＳ５７でＮｏ、ステップＳ５９）。
【００４５】
なお、ステップＳ５１において、検索処理を行うためのビット幅が自動設定ではないと判定された場合、特定部２２は、空塞表５１のビット幅がオペレータによって設定されていると判定する（ステップＳ５１でＮｏ）。この場合、空塞表５１のビット幅は、予め、メモリ１０２に記録されている。そこで、特定部２２は、メモリ１０２中の設定から空塞表５１のビット幅を取得する（ステップＳ６０）。
【００４６】
図１２は、空きエントリの検索方法の例を説明するフローチャートである。なお、図１２中のｍは、空塞表５１中のビット数をカウントするために使用される変数である。また、ステップＳ７１〜Ｓ７２は、図１０を参照しながら説明したステップＳ３１〜Ｓ３２と同様である。
【００４７】
更新部２４は、変数ｍを１に設定する（ステップＳ７３）。更新部２４は、検索キーから求められたブロック識別子に対応するブロックから、各エントリの使用状況を表わす空塞表５１を取得する。更新部２４は、空塞表５１の最下位からｍビット目のビットの値が０（未使用、空）に設定されているかを判定する（ステップＳ７４）。空塞表５１の最下位からｍ番目のビットの値が０に設定されている場合、最下位からｍ番目のビットに対応するエントリを処理対象とし、処理対象のエントリが未使用であるかを判定する（ステップＳ７４でＹｅｓ、ステップＳ７５）。処理対象のエントリが未使用である場合、抽出部２３は、処理対象のエントリを使用する領域として予約するために、空塞表５１中で処理対象のエントリに対応するビットの値を１（使用中）に更新する（ステップＳ７５でＹｅｓ、ステップＳ７６）。更新部２４は、処理対象のエントリを空きエントリとして特定し、処理を終了する（ステップＳ７７）。
【００４８】
ステップＳ７４かステップＳ７５でＮｏと判定された場合、更新部２４は変数ｍを１つインクリメントし、変数ｍが処理対象のブロックに含まれているエントリ数を超えたかを判定する（ステップＳ７８、Ｓ７９）。変数ｍがＪ番目のブロックに含まれているエントリ数を超えていない場合、ステップＳ７４以降の処理が繰り返される（ステップＳ７９でＮｏ）。一方、変数ｍが処理対象のブロックに含まれているエントリ数を超えた場合、更新部２４は、処理対象のブロックには空きエントリがないと判定して処理を終了する（ステップＳ７９でＹｅｓ、ステップＳ８０）。
【００４９】
図１２に示すフローチャートでは、ステップＳ７４において、空塞表中で注目しているビットの値が１（使用中）に設定されている場合に、変数ｍをインクリメントして、注目するビットを変更する。すなわち、空きエントリの検索においては、フロー情報の格納に使用されているエントリを避けて、フロー情報が格納されていないエントリを空塞表５１から特定している。従って、図２や図６を参照しながら説明したように、情報処理装置１０では、空塞表５１を用いて、迅速に空きエントリを検索できる。
【００５０】
（ｂ）登録されたフロー情報を用いた処理の例
次に、図１３〜図１６を参照しながら、受信パケットの処理の例を説明する。図１３〜図１５では、処理対象とするフローの情報は所定期間中に登録され、その後の新規のエントリ登録は自律的に行われないものとする。自律的な新規のエントリ登録を制限する期間中は、未登録のフローのパケットは廃棄される。
【００５１】
図１３は、パケット転送の際に行われる処理の例を説明するフローチャートである。図１３を参照しながら、情報処理装置１０が他の装置宛のパケットを受信した場合の処理の例を説明する。
【００５２】
情報処理装置１０は、パケットを受信する（ステップＳ９１）。取得部２１は、通信処理部１２と振分部１３を介して、受信パケットを取得する。取得部２１は、宛先アドレス等を用いて、自装置宛のパケットではないことを特定すると、受信パケットから検索キーを取得する（ステップＳ９２）。その後、特定部２２と抽出部２３によって、エントリ検索が行われる（ステップＳ９３）。ステップＳ９３で行われる処理は、図１０を参照しながら説明した処理と同様である。
【００５３】
受信パケットを含むフローの情報が既に登録されている場合、抽出部２３は、受信パケットのフロー情報が登録されているエントリ中の制御情報を用いて、受信パケットに対して行う処理を特定する（ステップＳ９４でＹｅｓ）。図１３の例では、フロー情報が登録されているエントリ中の制御情報は転送処理であるため、抽出部２３は、受信パケットに対する転送処理を行うことを決定する（ステップＳ９５）。抽出部２３は、受信パケットに適用可能な情報が記録されているエントリの先頭アドレスと受信パケットを、パケット転送処理部３１と統計処理部３２に出力する。統計処理部３２は、受信パケットを用いて統計情報を更新する（ステップＳ９６）。パケット転送処理部３１は、通信処理部１２を介して、受信パケットに対応付けられた出力ポートからパケットを転送する（ステップＳ９７）。一方、受信パケットを含むフローの情報が検索テーブル４２に登録されていない場合、抽出部２３は、受信パケットを廃棄する（ステップＳ９４でＮｏ、ステップＳ９８）。ステップＳ９７かＳ９８のいずれかの処理が終了すると、ステップＳ９１以降の処理が繰り返される。
【００５４】
図１４は、統計情報収集の際に行われる処理の例を説明するフローチャートである。ステップＳ１０１〜Ｓ１０４、Ｓ１０８の処理は、図１３を参照しながら説明したステップＳ９１〜Ｓ９４、Ｓ９８の処理と同様である。
【００５５】
受信パケットの情報が検索テーブル４２に登録されている場合、抽出部２３は、受信パケットのフロー情報が登録されているエントリ中の制御情報を用いて、受信パケットに対して行う処理を特定する（ステップＳ１０４でＹｅｓ）。図１４の例では、フロー情報が登録されているエントリ中の制御情報は統計情報の更新であるため、抽出部２３は、受信パケットを用いた統計情報の更新を行うことを決定する（ステップＳ１０５）。抽出部２３は、受信パケットに適用可能な情報が記録されているエントリの先頭アドレスと受信パケットを、統計処理部３２に出力する。統計処理部３２は、受信パケットを用いて統計情報を更新する（ステップＳ１０６）。その後、受信パケットは廃棄される（ステップＳ１０７）。ステップＳ１０７かＳ１０８のいずれかの処理が終了すると、ステップＳ１０１以降の処理が繰り返される。
【００５６】
図１５は、パケットのフィルタリングの際に行われる処理の例を説明するフローチャートである。ステップＳ１１１〜Ｓ１１４、Ｓ１２０の処理は、図１３を参照しながら説明したステップＳ９１〜Ｓ９４、Ｓ９８の処理と同様である。
【００５７】
受信パケットの情報が検索テーブル４２に登録されている場合、抽出部２３は、受信パケットのフロー情報が登録されているエントリ中の制御情報を用いて、受信パケットに対して行う処理を特定する（ステップＳ１１４でＹｅｓ、ステップＳ１１５）。検索テーブル４２を用いてフィルタリングが行われる場合、転送対象のフローのエントリでは制御情報に「転送」が指定されており、フィルタリングにより廃棄されるフローのエントリでは、制御情報に「廃棄」が指定されている。ステップＳ１１６、Ｓ１１７は、転送が指定されているフローに対する処理であり、図１３を参照しながら説明したステップＳ９６、Ｓ９７と同様の処理である。ステップＳ１１８、Ｓ１１９は、廃棄が指定されているフローに対する処理であり、図１４を参照しながら説明したステップＳ１０６、Ｓ１０７と同様の処理である。
【００５８】
図１６は、パケット転送の際に行われる処理の例を説明するフローチャートである。図１６を参照しながら、新規のエントリ登録が自律的に行われる場合のパケットの転送処理の例を説明する。なお、図１６で説明する処理でも、検索テーブル４２に登録されているフローについての処理は図１３と同様である。このため、図１６のステップＳ１３１〜Ｓ１３７の処理は、図１３を参照しながら説明したステップＳ９１〜Ｓ９７と同様である。受信パケットを含むフローの情報が検索テーブル４２に登録されていない場合、更新部２４は、受信パケットを含むフローの情報のエントリ登録処理を行う（ステップＳ１３４でＮｏ、ステップＳ１３８）。エントリ登録処理は、図９Ａ〜図１２を参照しながら説明した処理と同様である。フロー情報の登録に成功すると、統計情報の更新やパケットの転送が行われる（ステップＳ１３９でＹｅｓ、ステップＳ１３６、Ｓ１３７）。一方、フロー情報の登録に失敗すると、受信パケットは廃棄される（ステップＳ１３９でＮｏ、ステップＳ１４０）。
【００５９】
（ｃ）フロー情報の削除
図１７は、エントリの登録情報が削除される場合のブロック中の情報の例を説明する図である。図１７では、抽出部２３による１回の処理では１６ビットが読み込まれ、空塞表５１が１６ビットに設定されている場合を例として説明する。なお、この場合、１つのブロックには、１６のエントリが含まれている。
【００６０】
検索テーブル４２−１１に示すブロックでは、ブロックの先頭から５つのエントリにフロー情報が登録されている。検索テーブル４２−１１に示す空塞表では、下位５ビットが１（使用中）、上位１１ビットが０（未使用）に設定されている。検索テーブル４２−１１において、ブロックの先頭アドレスをＭで表わしている。空塞表５１として、先頭のエントリ中の空塞表が使用されるため、各エントリの空塞位置は、Ｍ＋０に指定されている。なお、図１７では、図を見やすくするために、２番目のエントリ以降の空塞表は図示していない。また、検索テーブル４２−１１では、相対位置、登録状態、空塞位置、登録位置以外の情報は図示していないが、各エントリには図８を参照しながら説明した情報が記録されているものとする。相対位置は、そのエントリがブロック中の何番目のエントリであるかを示す情報であり、エントリの先頭アドレスとブロックの先頭アドレスの差を１つのエントリの長さで割って得られる値である。登録位置は、各エントリの先頭アドレスの特定に使用可能な値である。図１７の例では、登録位置は、データの登録に使用されているブロックの先頭アドレス（Ｍ）に相対位置の値を続けて表わされている。
【００６１】
その後、情報処理装置１０がフロー情報の削除の要求を受信したとする。フロー情報の削除の要求は、削除対象となるフロー情報が特定できる任意の形式のメッセージが使用され得る。取得部２１は、削除対象のフローの情報から、削除対象のフローの検索に使用する検索キーを取得する。特定部２２は、得られた検索キーと各ブロック中の空塞表５１のビット長を用いて、削除対象のフロー情報が格納されているブロックを特定する。抽出部２３は、特定されたブロックの空塞表５１を読み込むことにより、処理対象のブロックのうちでデータの登録に使用されているエントリを特定する。抽出部２３は、特定したエントリに登録されている情報を用いて、削除対象の情報を登録しているエントリを特定する。更新部２４は、抽出部２３での検索結果を取得し、削除対象のフロー情報をエントリから削除する。さらに、更新部２４は、空塞表５１中でフロー情報を削除したエントリに対応付けられたビットの値を０に変更する。
【００６２】
例えば、検索テーブル４２−１１の相対位置＝＋１のエントリ中のフロー情報が削除対象であることを、抽出部２３が特定したとする。すると、更新部２４は、相対位置＝＋１のエントリ中のフロー情報を削除すると共に、エントリ中の登録情報を０（未使用）に設定する。さらに、相対位置＝＋１のエントリ中のフロー情報の削除に伴って、空塞表５１の下位から２ビット目の値が１から０に変更される。このため、空塞表５１は、検索テーブル４２−１１から検索テーブル４２−１２に示すように変更される。
【００６３】
図１８は、エントリ中の登録情報の削除の際に行われる処理の例を説明するフローチャートである。ステップＳ１５１〜Ｓ１５３は、図９Ａを参照しながら説明したステップＳ１１〜Ｓ１３と同様である。削除対象のフロー情報を格納したエントリの検索に失敗する場合、削除対象のフローの情報は未登録であるか削除済みである（ステップＳ１５３でＮｏ）。この場合、更新部２４は、削除処理に成功していると判定して処理を終了する（ステップＳ１５４）。
【００６４】
一方、抽出部２３が削除対象のフロー情報を格納したエントリの検索に成功すると、更新部２４は、削除対象のフローの情報が登録されているエントリの情報を抽出部２３から取得する（ステップＳ１５３でＹｅｓ）。更新部２４は、削除対象のフローが登録されているエントリ中の情報を削除し、登録状態を未使用に設定する（ステップＳ１５５）。なお、情報処理装置１０において、登録状態が０（未使用）に設定されている場合、そのエントリに情報が残っていても読み込まないように設定される場合がある。この場合、抽出部２３は、削除対象の情報を含むエントリ中の登録状態を、未使用を示す値にすることにより、そのエントリ中の情報を削除せずに無効にすることもできる。更新部２４は、情報を削除したエントリの使用状況を表わす空塞表中のビットを０に設定することにより、空塞表を更新する（ステップＳ１５６）。
【００６５】
このように第１の実施形態にかかる情報処理装置１０では、フロー情報を保持しているエントリを空塞表５１から特定することができる。従って、フロー情報の検索の際には、空塞表５１において、情報の登録に使用されていることが記録されているエントリを検索対象とすることにより、空きエントリを避けて検索処理を行うことができる。また、空塞表５１を用いることにより、ブロック中でフロー情報の登録に使用されているエントリをまとめて配置するためのエントリの移動を行わなくてよいので、検索テーブル４２の更新に時間がかからない。従って、検索テーブル４２を使用できない期間が短くなり、検索処理が効率化される。さらに、第１の実施形態にかかる情報処理装置１０では、フロー情報のハッシュ値によって特定されたブロックへの１回のアクセスによって、処理対象のブロックの使用状況を取得することができ、効率的に処理が行われる。
【００６６】
＜第２の実施形態＞
第１の実施形態では、フロー情報は、検索キーのハッシュ値から計算されたブロック識別子に対応付けられたブロックのみに格納される場合について説明したが、あるプロセッサで処理するフロー情報の格納先が一部のブロックに集中することもある。すると、ブロック中にそのブロックに対応付けられた全てのフロー情報を格納できない場合も発生する。そこで、第２の実施形態では、フロー情報を、検索キーのハッシュ値から求められたブロック以外にも格納する場合について説明する。
【００６７】
図１９は、第２の実施形態にかかる検索テーブルの例を説明する図である。図１９に示す検索テーブル４２−１は、ブロック識別子Ｊ＝０とＪ＝１の２つのブロックに含まれている情報の例を示している。Ｊ＝０のブロックと、Ｊ＝１のブロックのいずれにも、複数のエントリが含まれている。検索テーブル４２−２は、Ｊ＝０のブロックの全てのエントリが使用されており、さらに、Ｊ＝１のブロックのエントリＥ０、Ｅ２、Ｅ４が使用されている場合を示す。すなわち、検索テーブル４２−２では、Ｊ＝０のブロックには空きエントリがないが、Ｊ＝１のエントリＥ１、Ｅ３、Ｅ５以降が空きエントリとなっている。なお、図１９、図２０の例では、空塞表５１の長さは３２ビットであり、各ブロックにはエントリＥ０〜Ｅ３１の３２個のエントリが含まれているものとする。
【００６８】
検索テーブル４２−２に示す登録状態のときに、新たに登録対象のフローが発生したとする。さらに、登録対象のフロー情報に対して、特定部２２によって特定された格納先のブロックのブロック識別子がＪ＝０であるとする。この場合、Ｊ＝０の全てのエントリが使用済みであるため、更新部２４は、Ｊ＝１中のエントリに登録対象のフローの情報を登録する。
【００６９】
図２０に示す検索テーブル４２−３は、Ｊ＝１のブロックのエントリＥ１に、Ｊ＝０に対応付けられている登録対象のフローが登録された場合の例を示している。ここで、検索キーのハッシュ値に対応付けられているブロックを明確にするために、新たに登録されたフローは、仮想的なＪ＝０のブロックでのエントリとして「Ｊ＝０、Ｅ３２のエントリ」と表記することがある。なお、Ｊ＝０には、物理的には、エントリＥ０〜Ｅ３１までの３２個のエントリしか含まれない。
【００７０】
Ｊ＝１のエントリＥ０に登録されている情報の詳細をエントリ５２−０、Ｊ＝１のエントリＥ１に登録されている情報の詳細をエントリ５２−１に示す。各エントリに記録される情報は、図８を参照しながら説明した各情報と、格納されているフローの検索キーから得られたハッシュ値である。
【００７１】
第２の実施形態では、各エントリにおいて、検索キーのハッシュ値の値が記録される。なお、図８に示したブロック識別子の代わりに検索キーのハッシュ値が記録されても良い。検索キーのハッシュ値を記録することにより、記録されている情報が本来対応付けられているブロックを特定することもできる。例えば、エントリ５２−１には、Ｊ＝０、Ｅ３２のエントリが格納されているので、Ｊ＝０に対応付けるために、Ｊ＝０、Ｅ３２のエントリのハッシュ値が記録される。このため、Ｊ＝１のブロックのエントリＥ１は、Ｊ＝０のブロックのエントリＥ３２として使用されていることが特定可能になる。ただし、Ｊ＝１のブロックのエントリＥ１の使用状態は、Ｊ＝１のブロックの空塞表５１に記録されるので、Ｊ＝１のブロックのエントリＥ１の空塞位置として、Ｊ＝１のエントリＥ０の先頭のアドレスが記録される。
【００７２】
第２の実施形態では、フロー情報の検索の際には、検索対象となるフロー情報から取得した検索キーのハッシュ値を用いて、第１の実施形態と同様に、格納先のブロックのブロック識別子を求める。その後、抽出部２３は、特定部２２によって求められたブロック識別子に対応付けられたブロックの空塞表５１で使用されているエントリの各々について、検索対象のフローの検索キーから計算されたハッシュ値と、エントリ中のハッシュ値を比較する。特定部２２から通知されたブロック識別子で識別されるブロック中のいずれのエントリ中のハッシュ値も、検索対象のフローの検索キーから得られたハッシュ値と一致しない場合、抽出部２３は、他のブロックを検索対象として同様の処理を行うことにより、全てのブロックを検索対象とすることができる。なお、この場合でも、各ブロックでの検索の際に空塞表５１が使用されるので、検索対象のエントリへのアクセスは迅速に行われる。
【００７３】
このような処理を行うことにより、第２の実施形態にかかる情報処理装置１０では、ハッシュ値に対応づけられたブロックに空きエントリがない場合に、他のブロック中の空きエントリを、ハッシュ値に対応づけられたブロックの拡張領域として使用する。このため、第２の実施形態では、第１の実施形態よりも多くのフロー情報を管理することができる。以下、フローチャートを参照しながら第２の実施形態で行われる処理の詳細を説明する。
【００７４】
図２１Ａと図２１Ｂは、登録処理の例を説明するフローチャートである。なお、ステップＳ１６８〜Ｓ１７０の処理の順序は、実装に応じて、任意に変更され得る。ステップＳ１６１、Ｓ１６３、Ｓ１６５〜Ｓ１６７は、図９Ａ、図９Ｂを参照しながら説明したステップＳ１１、Ｓ１３、Ｓ１５〜Ｓ１７と同様である。ステップＳ１６２で行われるエントリ検索の詳細は、図２３Ａと図２３Ｂを参照しながら後述する。また、ステップＳ１６４で行われる空きエントリ検索の詳細は、図２２を参照しながら後述する。更新部２４は、フロー情報を登録したエントリ中に、検索キーから算出したハッシュ値を記録する（ステップＳ１６８）。更新部２４は、フロー情報を登録したエントリ中に登録位置を設定する（ステップＳ１６９）。さらに、更新部２４は、処理対象のエントリの情報を記録している空塞表５１を更新する（ステップＳ１７０）。
【００７５】
図２２は、空きエントリの検索方法の例を説明するフローチャートである。ステップＳ１８１〜Ｓ１８６の処理は、図１２を参照しながら説明したステップＳ７１〜Ｓ７６の処理と同様である。更新部２４は、ハッシュ値をエントリ中に記録し、処理対象のエントリを登録処理に使用できるエントリとして特定する（ステップＳ１８７、Ｓ１８８）。
【００７６】
ステップＳ１８４かステップＳ１８５でＮｏと判定された場合、更新部２４は変数ｍを１つインクリメントし、変数ｍが処理対象のブロックに含まれているエントリ数を超えたかを判定する（ステップＳ１８８、Ｓ１８９）。変数ｍが処理対象のブロックに含まれているエントリ数を超えていない場合、ステップＳ１８４以降の処理が繰り返される（ステップＳ１９０でＮｏ）。一方、変数ｍが処理対象のブロックに含まれているエントリ数を超えた場合、更新部２４は、全てのブロックが処理対象となったかを判定する（ステップＳ１９０でＹｅｓ、ステップＳ１９１）。全てのブロックが処理対象となっていない場合、検索対象となっていないブロックを新たな処理対象のブロックに選択し、選択したブロックの先頭のアドレスを取得する（ステップＳ１９１でＮｏ、ステップＳ１９２）。更新部２４は、変数ｍを１に設定して、ステップＳ１８４以降の処理を繰り返す（ステップＳ１９３）。一方、ステップＳ１９１において、全てのブロックが処理対象となっていると判定された場合、更新部２４は、処理対象のブロックには空きエントリがないと判定して処理を終了する（ステップＳ１９１でＹｅｓ、ステップＳ１９４）。
【００７７】
図２３Ａと図２３Ｂは、検索処理の例を説明するフローチャートである。ステップＳ２０１〜Ｓ２０４は、図１０を参照しながら説明したステップＳ３１〜Ｓ３４と同様である。空塞表５１の最下位からＮ番目のビットの値が１に設定されている場合、抽出部２３は、最下位からＮ番目のビットに対応するエントリ中のハッシュ値と、検索対象のフローから得られたハッシュ値を比較する（ステップＳ２０４でＹｅｓ、ステップＳ２０５）。検索対象のフローから得られたハッシュ値とエントリ中のハッシュ値が一致する場合、抽出部２３は、処理対象のエントリに格納された各種情報と、検索対象のフローの情報を比較する（ステップＳ２０５でＹｅｓ、ステップＳ２０６、Ｓ２０７）。検索対象のフロー情報と読み出した情報が一致すると、抽出部２３は、検索対象のフロー情報は処理対象のブロックのＮ番目のエントリに登録されていると判定して処理を終了する（ステップＳ２０７でＹｅｓ、ステップＳ２０８）。
【００７８】
ステップＳ２０４、Ｓ２０５、Ｓ２０７でＮｏと判定された場合、抽出部２３は変数Ｎを１つインクリメントし、変数Ｎが処理対象のブロックに含まれているエントリ数を超えたかを判定する（ステップＳ２０９、Ｓ２１０）。変数Ｎが処理対象のブロックに含まれているエントリ数を超えていない場合、ステップＳ２０４以降の処理が繰り返される（ステップＳ２１０でＮｏ）。
【００７９】
一方、変数Ｎが処理対象のブロックに含まれているエントリ数を超えた場合、更新部２４は、全てのブロックが処理対象となったかを判定する（ステップＳ２１０でＹｅｓ、ステップＳ２１１）。全てのブロックが処理対象となっていない場合、検索対象となっていないブロックを新たな処理対象のブロックに選択し、選択したブロックの先頭のアドレスを取得する（ステップＳ２１１でＮｏ、ステップＳ２１２）。抽出部２３は、変数Ｎを１に設定して、ステップＳ２０４以降の処理を繰り返す（ステップＳ２１３）。一方、ステップＳ２１１において、全てのブロックが処理対象となっていると判定された場合、抽出部２３は、検索対象のフローの情報は未登録と判定する（ステップＳ２１１でＹｅｓ、ステップＳ２１４）。その後、検索対象のフローの情報の登録処理が行われる（ステップＳ２１５）。検索対象のフローの情報の登録処理は、図２１Ａと図２１Ｂを参照しながら説明したステップＳ１６４以降の処理と同様である。
【００８０】
図２４は、エントリ中の登録情報の削除の際に行われる処理の例を説明するフローチャートである。なお、図２４のフローチャートでは、抽出部２３は、登録状態の欄が未使用（０）を示す値に設定されたエントリ中の情報は読み込まないように設定されている場合を例としている。この場合、検索テーブル４２中の情報の削除は、削除対象の情報を含むエントリの登録状態の値を０（不使用）に設定するものとする。
【００８１】
ステップＳ２２１〜Ｓ２２３の処理は、図９Ａを参照しながら説明したステップＳ１１〜Ｓ１３と同様である。削除対象のフロー情報を格納したエントリの検索に失敗する場合、削除対象のフローの情報は未登録であるか削除済みであるため、更新部２４は、削除処理に成功していると判定して処理を終了する（ステップＳ２２３でＮｏ、ステップＳ２２４）。
【００８２】
一方、抽出部２３が削除対象のフロー情報を格納したエントリの検索に成功すると、更新部２４は、削除対象のフローの情報が登録されているエントリの情報を抽出部２３から取得する（ステップＳ２２３でＹｅｓ）。更新部２４は、削除対象のフローの情報が登録されているエントリのハッシュ値を削除すると共に、登録状態の値を０（未使用）に設定する（ステップＳ２２５、Ｓ２２６）。さらに、更新部２４は、削除対象のフローの情報が登録されているエントリの使用状況を表わす空塞表中のビットを０に設定することにより、空塞表を更新する（ステップＳ２２７）。
【００８３】
以上の処理を行うことにより、第２の実施形態にかかる情報処理装置１０では、多数のフロー情報を管理することができる。例えば、情報処理装置１０を用いたパケット転送装置では、数百万から一千万程度のエントリを管理することができ、さらに、４０Ｇｂｐｓ程度の転送速度に対応できる。
【００８４】
なお、実施形態は上記に限られるものではなく、様々に変形可能である。例えば、複数のエントリに空塞表５１が含まれている場合、先頭のエントリの空塞表５１が使用される場合を例として説明したが、先頭のエントリ以外のエントリに含まれている空塞表５１がブロック中のエントリの使用状況の記録に使用されても良い。この場合、予め、空塞表５１が記録されているエントリはいずれもブロックでも同じエントリに設定されており、さらに、抽出部２３は、空塞表５１を含むエントリの情報を保持しているものとする。
【００８５】
上述の第１および第２の実施形態を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
複数のブロックに分かれたメモリを有する情報処理装置に、
データの検索に使用する検索キーのハッシュ値を計算し、
前記ハッシュ値を用いて、前記検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定し、
前記格納ブロックに含まれるエントリの使用状況を前記情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、前記格納ブロックから読み込み、
データの登録に使用されていることが前記使用情報に記録されているエントリのいずれかから、前記検索キーに対応付けられたデータを抽出する
処理を行わせることを特徴とする情報処理方法。
（付記２）
前記情報処理装置に、
前記メモリに登録する対象のデータである登録対象データを取得すると、前記登録対象データの検索に使用する検索キーのハッシュ値である他のハッシュ値を計算し、
前記他のハッシュ値に対応づけられたブロックを格納先のブロックとして特定し、
前記格納先のブロックから、前記格納先のブロックに含まれるエントリの使用状況を前記プロセッサが１回の命令で読み込み可能なビット長で表わした情報を読み込み、
前記格納先のブロック中でデータの登録に使用されていないエントリのいずれかに、前記登録対象データを記録する
処理をさらに行わせることを特徴とする付記１に記載の情報処理方法。
（付記３）
前記格納先のブロックにデータの登録に使用されていないエントリがない場合、前記格納先のブロックとは異なる他のブロックから処理対象として選択した対象エントリに、前記登録対象データを登録し、
前記対象エントリに、前記他のハッシュ値を記録することにより、前記対象エントリを前記格納先のブロックの拡張領域として使用する
処理を前記情報処理装置に行わせることを特徴とする付記２に記載の情報処理方法。
（付記４）
前記格納ブロックに検索対象のデータが記録されていない場合、前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリを、前記複数のブロックのうちの前記格納ブロック以外のブロックで検索し、
前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリの情報を前記検索対象のデータとして抽出する
処理を前記情報処理装置に行わせることを特徴とする付記３に記載の情報処理方法。
（付記５）
複数のブロックに分かれたメモリを有する情報処理装置であって、
データの検索に使用する検索キーのハッシュ値を計算すると共に、前記ハッシュ値を用いて、前記検索キーに対応付けられたデータが格納されているブロックである格納ブロックを特定する特定部と、
前記格納ブロックに含まれるエントリの使用状況を前記情報処理装置が備えるプロセッサが１回の命令で読み込み可能なビット長で表わした使用情報を、前記格納ブロックから読み込むと共に、データの登録に使用されていることが前記使用情報に記録されているエントリのいずれかから、前記検索キーに対応付けられたデータを抽出する抽出部
を備えることを特徴とする情報処理装置。      
（付記６）
前記メモリに登録する対象のデータである登録対象データを取得する取得部と、
前記メモリに格納する情報の更新処理を行う更新部
をさらに備え、
前記特定部は、前記登録対象データの検索に使用する検索キーのハッシュ値に対応付けられたブロックを格納先のブロックとして特定し、
前記更新部は、
前記格納先のブロックから、前記格納先のブロックに含まれるエントリの使用状況を前記プロセッサが１回の命令で読み込み可能なビット長で表わした情報を読み込み、
前記格納先のブロック中でデータの登録に使用されていないエントリのいずれかに、前記登録対象データを記録する
ことを特徴とする付記５に記載の情報処理装置。    
（付記７）
前記更新部は、
前記格納先のブロックにデータの登録に使用されていないエントリがない場合、前記格納先のブロックとは異なる他のブロックから処理対象として選択した対象エントリに、前記登録対象データを登録し、
前記対象エントリに、前記登録対象データの検索に使用する検索キーのハッシュ値を記録することにより、前記対象エントリを前記格納先のブロックの拡張領域として使用する
ことを特徴とする付記６に記載の情報処理装置。                
（付記８）
前記抽出部は、
前記格納ブロックに検索対象のデータが記録されていない場合、前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリを、前記複数のブロックのうちの前記格納ブロック以外のブロックで検索し、
前記検索対象のデータに対応する検索キーのハッシュ値を含むエントリの情報を前記検索対象のデータとして抽出する
ことを特徴とする付記７に記載の情報処理装置。                
【符号の説明】
【００８６】
１０  情報処理装置
１１  物理ポート
１２  通信処理部
１３  振分部
２０  制御部
２１  取得部
２２  特定部
２３  抽出部
３０  パケット処理部
３１  パケット転送処理部
３２  統計処理部
３３  フィルタリング処理部
４０  記憶部
４２  検索テーブル
５１  空塞表
５２  エントリ
１０１  プロセッサ
１０２  メモリ
１０３  ネットワーク接続装置
１０４  バス
【図３】
2016224840.tif 000003
【図４】
2016224840.tif 000004
【図５】
2016224840.tif 000005
【図８】
2016224840.tif 000006
【図９Ａ】
2016224840.tif 000007
【図９Ｂ】
2016224840.tif 000008
【図１０】
2016224840.tif 000009
【図１１】
2016224840.tif 000010
【図１２】
2016224840.tif 000011
【図１３】
2016224840.tif 000012
【図１４】
2016224840.tif 000013
【図１５】
2016224840.tif 000014
【図１６】
2016224840.tif 000015
【図１７】
2016224840.tif 000016
【図１８】
2016224840.tif 000017
【図１９】
2016224840.tif 000018
【図２０】
2016224840.tif 000019
【図２１Ａ】
2016224840.tif 000020
【図２１Ｂ】
2016224840.tif 000021
【図２２】
2016224840.tif 000022
【図２３Ａ】
2016224840.tif 000023
【図２３Ｂ】
2016224840.tif 000024
【図２４】
2016224840.tif 000025
【図１】
2016224840.tif 000026
【図２】
2016224840.tif 000027
【図６】
2016224840.tif 000028
【図７】
2016224840.tif 000029