(57)【要約】【課題】データ長の長いキー情報についてのハッシュテーブルを高速に検索可能とする。【解決手段】所定の長さ以上のデータ長を持つキー情報は、前置ハッシュ演算手段により所定の長さ以下の縮退キー情報に変換させられた上で、この縮退キー情報から得られるハッシュ値に従って一次ハッシュテーブルに格納される。また、登録管理手段により、元のキー情報が登録された二次ハッシュテーブルを用意しておき、一次ハッシュテーブルに登録された縮退キーに重複が発生した場合に、重複表示手段によってその旨を示し、検索手段に二次ハッシュテーブルの参照を促すことにより、同一の縮退キー情報に変換されるキー情報についても確実に、それぞれのキー情報に関連付けられた関連情報との対応を示し、関連情報テーブルから対応する関連情報を検索させる。【選択図】      図１
2010050600.tif 000002
【特許請求の範囲】
【請求項１】
データ長が所定の長さを超えているキー情報に関連して登録された関連情報を、ハッシュテーブルを利用して検索する情報検索装置において、
前記キー情報を前記所定の長さ以下のデータ長を有する縮退キー情報に変換する前置ハッシュ演算手段と、
前記前置ハッシュ演算手段によって得られた縮退キー情報に対して所定のハッシュ演算を行って得られたハッシュ値で示されるエントリに、前記縮退キー情報と対応する関連情報との対応付けを示す連係情報とを格納する一次ハッシュテーブルと、
前記縮退させる前の元のキー情報とこれに対応する連係情報とを前記元のキー情報に対応する別のハッシュ値で示されるエントリに格納する二次ハッシュテーブルと、
前記キー情報に対応する情報を前記一次ハッシュテーブルあるいは前記二次ハッシュテーブルに登録する処理を管理する登録管理手段と、
前記一次ハッシュテーブルあるいは前記二次ハッシュテーブルに格納された縮退キー情報あるいはキー情報に関連付けられた関連情報を格納する関連情報テーブルと、
前記一次ハッシュテーブルおよび前記二次ハッシュテーブルとに基づいて、前記キー情報あるいは縮退キー情報に対応付けられた関連情報を前記関連情報テーブルから検索する検索手段と
を備え、
前記一次ハッシュテーブルは、各エントリにおいて前記縮退キー情報についての重複が検出されたか否かを前記検索手段に対して示す重複表示手段を備え、
前記検索手段は、前記重複表示手段によって前記縮退キー情報についての重複があったことが示されたときに、前記二次ハッシュテーブルに基づいて関連情報の検索を行う
ことを特徴とする情報検索装置。
【請求項２】
請求項１に記載の情報検索装置において、
前記前置ハッシュ演算手段は、
前記キー情報に含まれる特定の項目の情報を縮退させる縮退手段と、
前記縮退させた特定の項目の情報を前記元のキー情報に含まれる他の項目の情報と組み合わせて前記縮退キー情報を生成する編成手段とを備え、
前記登録管理手段は、
前記一次ハッシュテーブルに前記縮退キー情報と対応する連係情報とを登録する際に、前記縮退させられる前の特定の項目を示す情報を、前記連係情報に対応する関連情報の一部として前記関連情報テーブルに登録する特定項目登録手段と、
前記一次ハッシュテーブルに前記縮退キー情報を登録する際に、既に登録されている別の縮退キー情報との重複を検出する検出手段と、
前記検出手段によって縮退キー情報の重複が検出されたときに、前記一次ハッシュテーブルに登録済みの縮退キー情報であって、前記重複が検出された縮退キー情報と同一のハッシュ値に変換される縮退キー情報と、これに対応する関連情報の一部として前記関連情報テーブルに登録された特定項目とから前記登録済みの縮退キー情報に対応する元のキー情報を復元する復元手段とを備え、
前記検出手段によって重複が検出された縮退キー情報に対応する元のキー情報と対応すう連係情報および前記復元手段によって復元されたキー情報と対応する連係情報を前記二次ハッシュテーブルに登録する
ことを特徴とする情報検索装置。
【請求項３】
請求項１に記載の情報検索装置において、
前記検索手段は、前記キー情報に対応するハッシュ値で示される前記一次ハッシュテーブルのエントリの前記重複表示手段によってハッシュ値の重複が示されていた場合に、検索先を前記二次ハッシュテーブルに切り替えるとともに、検索に用いるハッシュ値を前記前記データ長の長い種類のキー情報に対応する別のハッシュ値に切り替える切り替え制御手段を備える
ことを特徴とする情報検索装置。
【請求項４】
データ長が所定の長さを超えている長タイプキー情報およびデータ長が所定の長さを超えない短タイプキー情報とこれらのキー情報に関連する関連情報との対応付けを格納するハッシュテーブルに基づいて前記関連情報の検索を行う検索装置において、
前記長タイプキー情報を、前記短タイプキー情報のデータ長と等しい長さの縮退キー情報に変換する前置ハッシュ演算手段と、
前記前置ハッシュ演算手段によって得られた縮退キー情報と前記短タイプキー情報とを、所定のデータ長のハッシュ値に変換するハッシュ演算手段と、
前記縮退キー情報と対応する関連情報との対応付けを示す連係情報と前記短タイプキー情報と対応する関連情報との対応付けを示す連係情報との双方を、それぞれに対応して前記ハッシュ演算手段で得られたハッシュ値で示されるエントリに格納する一次ハッシュテーブルと、
前記縮退させる前の元のキー情報とこれに対応する連係情報とを前記元のキー情報に対応する別のハッシュ値で示されるエントリに格納する二次ハッシュテーブルと、
前記キー情報に対応する情報を前記一次ハッシュテーブルあるいは前記二次ハッシュテーブルに登録する処理を管理する登録管理手段と、
前記一次ハッシュテーブル又は前記二次ハッシュテーブルに格納されたキー情報および縮退キー情報に関連付けられた関連情報を格納する関連情報テーブルと、
前記一次ハッシュテーブルおよび前記二次ハッシュテーブルとに基づいて、前記キー情報あるいは縮退キー情報に対応付けられた関連情報を前記関連情報テーブルから検索する検索手段と
を備え、
前記一次ハッシュテーブルは、各エントリを示すハッシュ値について、前記縮退キー情報についての重複が検出されたか否かを前記検索手段に対して示す重複表示手段を備え、
前記検索手段は、前記重複表示手段によって前記縮退キー情報についての重複があったことが示されたときに、前記二次ハッシュテーブルに基づいて関連情報の検索を行う
ことを特徴とする情報検索装置。
【請求項５】
請求項４に記載の情報検索装置において、
前記長タイプキー情報はＩＰＶ６ヘッダ情報を含むキー情報であるとともに、前記短タイプキー情報はＩＰＶ４ヘッダ情報を含むキー情報であり、
前記前置ハッシュ演算手段は、
前記長タイプキー情報のＩＰＶ６ヘッダに含まれるアドレス情報をＩＰＶ４ヘッダ内のアドレス情報と同等の長さに縮退させる縮退手段と、
前記縮退させたアドレス情報を前記元の長タイプキー情報に含まれる他の項目の情報と組み合わせて前記縮退キー情報を生成する編成手段とを備え、
前記登録管理手段は、
前記一次ハッシュテーブルに前記縮退キー情報と対応する連係情報とを登録する際に、前記縮退させられる前のアドレス情報を、前記連係情報に対応する関連情報の一部として前記関連情報テーブルに登録するアドレス退避手段と、
前記一次ハッシュテーブルに前記縮退キー情報を登録する際に、既に登録されている別の縮退キー情報との重複を検出する検出手段と、
前記検出手段によって縮退キー情報についての重複が検出されたときに、前記一次ハッシュテーブルに登録済みの縮退キーであって、前記重複が検出された縮退キー情報と同一のハッシュ値に変換される縮退キー情報と、これに対応する関連情報の一部として前記関連情報テーブルに登録されたアドレス情報とから前記登録済みの縮退キー情報に対応する元の長タイプキー情報を復元する復元手段とを備え、
前記検出手段によって衝突が検出された縮退キー情報に対応する元の長タイプキー情報と対応する連係情報および前記復元手段によって復元された長タイプキー情報と対応する連係情報を前記二次ハッシュテーブルに登録する
ことを特徴とする情報検索装置。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュテーブルを利用して長いデータ長を持つキー情報に基づく情報検索を行う情報検索装置に関する。
【背景技術】
【０００２】
ハッシュテーブルを用いた情報検索は、情報検索を高速化する技術として様々な分野で利用されている(特許文献１参照)。
【０００３】
例えば、ＩＰパケットのルーティング処理では、図１０に示したように、ＩＰＶ４用のハッシュテーブル４１１とＩＰＶ６用のハッシュテーブル４２１とが用意され、ＩＰＶ４ネットワークについてのルーティング情報とＩＰＶ６ネットワークについてのルーティング情報の検索処理に供される。
【０００４】
ＩＰＶ４ネットワークにおけるフローを特定する発信元アドレスや送信先アドレスなどからなるキー情報は、このキー情報にハッシュ演算を適用して得られたハッシュ値で示されるハッシュテーブル４１１のエントリに登録される。このとき、各フローに関連するルーティング情報やＱｏＳ情報を含むフロー情報の登録先として、アソシエートテーブル４１２のエントリが取得され、このエントリを特定するアソシエートテーブル(ＡＴ)ＩＤが、上述したキー情報とともに登録される。
【０００５】
同様に、ＩＰＶ６ネットワークにおけるフローを特定するキー情報は、対応するハッシュ値で示されるハッシュテーブル４２１のエントリに登録される。また同様に、各フローに関連するルーティング情報やＱｏＳ情報は、アソシエートテーブル４２２のエントリに登録され、このエントリを特定するアソシエートテーブル(ＡＴ)ＩＤが、上述したキー情報とともにハッシュテーブル４２１に登録される。
【０００６】
ハッシュ演算によってキー情報を縮退させることにより、異なるキー情報が同一のハッシュ値に対応付けられる衝突が発生することは良く知られており、この衝突に対応するために、ハッシュテーブル４１１，４２１には、次に検索するべきエントリを示すポインタ(Ｎｅｘｔ−Ｐｔ)が設けられている。
【０００７】
例えば、新たに登録しようとするキー情報に対応するハッシュ値が、既にキー情報が登録されているエントリを示していた場合に、衝突が検出されたエントリの代わりのエントリを新たなキー情報の登録先として割り当て、この登録先のエントリを示す情報を衝突が検出されたエントリのポインタに登録することで、検索時に、ポインタで結ばれた複数のエントリを検索対象とすることができる。つまり、キー情報のハッシュ値で示されたエントリに格納されたキー情報と検索対象のキー情報が一致しなかった場合に、ポインタを辿って次の候補となるエントリを見つけることができる。
【０００８】
このようなハッシュテーブルをキャッシュメモリに格納しておくことも情報検索を高速化する技術の一つである。
【特許文献１】特開２００４−５６３４０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところで、ＩＰパケットのルーティング処理では、ＩＰＶ４／ＩＰＶ６ヘッダ情報の一部とＵＤＰヘッダ情報の一部がキー情報としてハッシュテーブル４１１，４２１に登録されている。発信元アドレス(Source Address)および送信先アドレス(Destination Address)をそれぞれ３２ｂｉｔで表すＩＰＶ４では、キー情報のデータ長は１０８ｂｉｔとなり、ＡＴ−ＩＤやポインタ情報およびエントリが登録済みか否かを示すＶＡＬＩＤフラグを加えた１エントリのデータ長は１４３ｂｉｔである。これに対して、ＩＰＶ６では発信元アドレス、送信先アドレスがそれぞれ１２８ｂｉｔで表されるため、キー情報のデータ長はＩＰＶ４のキー情報の２倍以上である３００ｂｉｔとなり、ＩＰＶ６用のハッシュテーブルの１エントリのデータ長は３３５ｂｉｔとなる。
【００１０】
ここで、一般的なキャッシュメモリでは、１回の読出操作で読出可能なデータ長(キャッシュライン)は３２バイト(２５６ｂｉｔ)であるので、ＩＰＶ４用のハッシュテーブルであれば、１回の読出操作でハッシュテーブルのエントリを参照することができる。これに対して、ＩＰＶ６用のハッシュテーブルでは、各エントリに格納されたキー情報のデータ長が、上述したキャッシュラインを超えているため、ハッシュテーブルのエントリを参照するごとに２回の読出動作が必要となってしまう。つまり、ＩＰＶ６用のハッシュテーブルを１回参照するためには、２回の読出操作が必要となり、ＩＰＶ４用のハッシュテーブルを２回参照するのと同等な時間がかかってしまう。
【００１１】
更に、ＩＰＶ６用のハッシュテーブルでは各エントリのデータ長が長いために、キャッシュメモリ内に格納できるエントリ数が制限され、キャッシュミスが発生しやすくなってしまう。キャッシュミスが発生した場合には、動作の遅いメモリへのアクセスが必要となるため、ハッシュテーブルの検索処理に要する時間が著しく増大してしまう。
【００１２】
このように、ＩＰＶ６用のハッシュテーブルのようにデータ長の長いキー情報が登録されるハッシュテーブルを、ＩＰＶ４用のハッシュテーブルのようにデータ長の短いキー情報が登録されたハッシュテーブルと同じようにキャッシュメモリに格納して運用しても、データ長の短いキー情報が登録されたハッシュテーブルの検索において得られたような高速化を実現することはできなかった。
【００１３】
本発明は、データ長の長いキー情報についてのハッシュテーブルを高速に検索可能とする情報検索装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した目的は、以下に開示する情報検索装置によって達成することができる。
【００１５】
この情報検索装置の特徴は、データ長が所定の長さを超えているキー情報に関連して登録された関連情報を、ハッシュテーブルを利用して検索する情報検索装置において、キー情報を所定の長さ以下のデータ長を有する縮退キー情報に変換する前置ハッシュ演算手段と、前置ハッシュ演算手段によって得られた縮退キー情報に対して所定のハッシュ演算を行って得られたハッシュ値で示されるエントリに、縮退キー情報と対応する関連情報との対応付けを示す連係情報とを格納する一次ハッシュテーブルと、縮退させる前の元のキー情報とこれに対応する連係情報とを元のキー情報に対応する別のハッシュ値で示されるエントリに格納する二次ハッシュテーブルと、キー情報に対応する情報を一次ハッシュテーブルあるいは二次ハッシュテーブルに登録する処理を管理する登録管理手段と、一次ハッシュテーブルあるいは二次ハッシュテーブルに格納された縮退キー情報あるいはキー情報に関連付けられた関連情報を格納する関連情報テーブルと、一次ハッシュテーブルおよび二次ハッシュテーブルとに基づいて、キー情報あるいは縮退キー情報に対応付けられた関連情報を関連情報テーブルから検索する検索手段とを備え、一次ハッシュテーブルは、各エントリにおいて縮退キー情報についての重複が検出されたか否かを検索手段に対して示す重複表示手段を備え、検索手段は、重複表示手段によって縮退キー情報についての重複があったことが示されたときに、二次ハッシュテーブルに基づいて関連情報の検索を行う点にある。
【００１６】
このように構成された情報検索装置では、所定の長さ以上のデータ長を持つキー情報は、前置ハッシュ演算手段により所定の長さ以下に縮退させられた上で一次ハッシュテーブルに格納される。したがって、上述した前置ハッシュ演算手段によって、１回のメモリアクセスで読出可能なデータ長よりも短くなるようにキー情報を縮退させることにより、検索手段は、元のキー情報の長さにかかわらず、関連情報の検索のための一次ハッシュテーブルの参照処理を１回のメモリアクセスで完了することができる。
【００１７】
一方、登録管理手段により、元のキー情報が登録された二次ハッシュテーブルを用意しておき、一次ハッシュテーブルに登録された縮退キーに重複が発生した場合に、重複表示手段によってその旨を示し、検索手段に二次ハッシュテーブルの参照を促すことにより、同一の縮退キー情報に変換されるキー情報についても確実に対応する関連情報を検索させることができる。
【００１８】
また、上述した目的は、以下に開示する情報検索装置によっても達成することができる。
【００１９】
この情報検索装置の特徴は、データ長が所定の長さを超えている長タイプキー情報およびデータ長が所定の長さを超えない短タイプキー情報とこれらのキー情報に関連する関連情報との対応付けを格納するハッシュテーブルに基づいて関連情報の検索を行う検索装置において、長タイプキー情報を、短タイプキー情報のデータ長と等しい長さの縮退キー情報に変換する前置ハッシュ演算手段と、前置ハッシュ演算手段によって得られた縮退キー情報と短タイプキー情報とを、所定のデータ長のハッシュ値に変換するハッシュ演算手段と、縮退キー情報と対応する関連情報との対応付けを示す連係情報と短タイプキー情報と対応する関連情報との対応付けを示す連係情報との双方を、それぞれに対応してハッシュ演算手段で得られたハッシュ値で示されるエントリに格納する一次ハッシュテーブルと、縮退させる前の元のキー情報とこれに対応する連係情報とを元のキー情報に対応する別のハッシュ値で示されるエントリに格納する二次ハッシュテーブルと、キー情報に対応する情報を一次ハッシュテーブルあるいは二次ハッシュテーブルに登録する処理を管理する登録管理手段と、一次ハッシュテーブル又は二次ハッシュテーブルに格納されたキー情報および縮退キー情報に関連付けられた関連情報を格納する関連情報テーブルと、一次ハッシュテーブルおよび二次ハッシュテーブルとに基づいて、キー情報あるいは縮退キー情報に対応付けられた関連情報を関連情報テーブルから検索する検索手段とを備え、一次ハッシュテーブルは、各エントリを示すハッシュ値について、縮退キー情報についての重複が検出されたか否かを検索手段に対して示す重複表示手段を備え、検索手段は、重複表示手段によって縮退キー情報についての重複があったことが示されたときに、二次ハッシュテーブルに基づいて関連情報の検索を行う点にある。
【００２０】
このように構成された情報検索装置では、長タイプキー情報は、前置ハッシュ演算手段により、短タイプキー情報と同等のデータ長に縮退させられた上で、短タイプキー情報とともに一次ハッシュテーブルに格納される。これにより、一次ハッシュテーブルを２つのタイプのキー情報について共用することができる。また、上述した前置ハッシュ演算手段によって、短タイプのキー情報と同様に１回のメモリアクセスで読出可能なデータ長よりも短くなるようにキー情報を縮退させることにより、検索手段は、元のキー情報の長さにかかわらず、関連情報の検索のための一次ハッシュテーブルの参照処理を１回のメモリアクセスで完了することができる。
【００２１】
一方、登録管理手段により、元の長タイプキー情報が登録された二次ハッシュテーブルを用意しておき、一次ハッシュテーブルに登録された縮退キーに重複が発生した場合に、重複表示手段によってその旨を示し、検索手段に二次ハッシュテーブルの参照を促すことにより、同一の縮退キー情報に変換されるキー情報についても確実に対応する関連情報を検索させることができる。
【発明の効果】
【００２２】
以上に開示した基本構成を備えた情報検索装置では、一次ハッシュテーブルに登録するキー情報を、例えば上述したキャッシュラインにまで縮退させることにより、キー情報の長さにかかわらず、一次ハッシュテーブルの参照に要する時間をメモリアクセス１回分に抑えることができる。これにより、例えば、ＩＰＶ６ヘッダを含むデータ長の長いキー情報に基づいてフロー情報を検索する情報検索装置においても、ハッシュテーブルをキャッシュメモリに格納しておくことで得られる高速化効果を享受することができる。
【００２３】
また、上述したように縮退させたキー情報を一次ハッシュテーブルに格納する構成としたことにより、キャッシュメモリに格納できる一次ハッシュテーブルのエントリ数の減少を抑えることができる。これにより、キャッシュミスの発生確率を低減し、検索処理全体に要する時間の短縮を図ることができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面に基づいて、本発明の実施形態について詳細に説明する。
【００２５】
図１に、情報検索装置の実施形態の一例を示す。
【００２６】
図１において、情報検索装置は、ＩＰＶ４ネットワークおよびＩＰＶ６ネットワークにそれぞれ接続された通信装置２１０に備えられたルーティング処理部２１３からの要求に応じて、ルーティングテーブル２２０へのフロー情報の登録および検索を行う。
【００２７】
図１に示したルーティング処理部２１３は、ＩＰＶ４ネットワークインタフェース２１２およびＩＰＶ６ネットワークインタフェース２１１を介してそれぞれＩＰＶ４ネットワークおよびＩＰＶ６ネットワークに接続されており、これらのネットワークにおけるパケットのルーティング処理を行っている。
【００２８】
ＩＰＶ６ネットワークインタフェース２１１、ＩＰＶ４ネットワークインタフェース２１２を介して新たなパケットのフローの設定要求を受け取ったときに、ルーティング処理部２１３は、フロー設定のためのルーティング処理を行う。そして、このルーティング処理で得られたルーティング情報や必要とされるＱｏＳ情報を含むフロー情報と、このフローを特定するキー情報とは、ルーティング処理部２１３から情報検索装置に渡され、ルーティングテーブル２２０に登録する処理に供される。
【００２９】
また、既に設定されたフローを介してパケットを転送する際には、該当するフローに対応するキー情報に基づいて、ルーティングテーブル２２０からフロー情報を検索する処理が情報検索装置に依頼される。
【００３０】
ＩＰＶ４パケットのフロー情報の登録処理および検索処理は、図１に示したＩＰＶ４登録部２１４およびＩＰＶ４検索部２１８によって行われ、一方、ＩＰＶ６パケットのフロー情報の登録処理および検索処理は、ＩＰＶ６登録部２１５およびＩＰＶ６検索部２１７によって行われる。
【００３１】
図１に示したルーティングテーブル２２０において、ＩＰＶ４パケットのフロー情報は、アソシエートテーブル(Ｖ４)２２２に格納され、その格納場所を示す情報は一次ハッシュテーブル２２１によって示される。また、ＩＰＶ６パケットのフロー情報は、アソシエートテーブル(Ｖ６)２２４に格納され、その格納場所を示す情報は一次ハッシュテーブル２２１あるいは二次ハッシュテーブル２２３によって示される。
【００３２】
以下、一次ハッシュテーブル２２１、二次ハッシュテーブル２２３、アソシエートテーブル(Ｖ４)２２２およびアソシエートテーブル(Ｖ６)２２４についての管理動作について詳細に説明する。
【００３３】
図２に、ハッシュテーブルとアソシエートテーブルの関係を説明する図を示す。また、図３に、ＩＰＶ４フロー情報の登録動作を表す流れ図を示し、図４から図６に、ＩＰＶ６フロー情報の登録動作を表す流れ図を示す。
【００３４】
なお、図４〜６に示した構成要素のうち、図３に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【００３５】
図２に示すように、ＩＰＶ４パケットのフロー情報は、送信元アドレスおよび送信先アドレスを含むアドレス情報(６４ｂｉｔ)と、バージョン情報(Ｖｅｒ)やプロトコル識別子，ＵＤＰポート情報を含むデータ長１０８ｂｉｔの検索キー(ＩＰＶ４)で特定することができる。一方、ＩＰＶ６では、送信元アドレスおよび送信先アドレスがそれぞれ１２８ｂｉｔに拡張されているために、ＩＰＶ６パケットのフロー情報を特定するための検索キー(ＩＰＶ６)のデータ長は３００ｂｉｔとなっている。
【００３６】
このため、図１に示した情報検索装置では、ＩＰＶ６パケットのフロー情報を登録する際に、ＩＰＶ６登録部２１５は、検索キー(ＩＰＶ６)に含まれるアドレス情報をハッシュ演算部２１４によってＩＰＶ４におけるアドレス情報と同じデータ長に縮退させ、この縮退アドレス情報とバージョン情報(Ｖｅｒ)やプロトコル識別子，ＵＤＰポート情報を組み合わせることで、検索キー(ＩＰＶ４)と同じ長さの縮退キーを生成する。そして、この縮退キーと対応するフロー情報の格納場所を示すアソシエートテーブル識別情報(ＡＴ−ＩＤ)との組み合わせは、検索キー(ＩＰＶ４)と対応するＡＴ−ＩＤとの組み合わせともに一次ハッシュテーブルに登録される(図３参照)。
【００３７】
図３に示した一次ハッシュテーブルでは、各エントリに登録情報が存在することを示すフラグ(VALID)に加えて、個々のエントリに格納されたキー情報が上述した縮退キーであるか否かを示すＶ６フラグと、エントリに格納された縮退キーについて後述する重複が検出されたときにオンとされる重複フラグ(FD)が設けられている。また、検索キー(IPV4)とともに格納されたＡＴ−ＩＤは、アソシエートテーブル(Ｖ４)２２２における格納場所を示すのに対して、検索キー(IPV6)とともに格納されたＡＴ−ＩＤは、アソシエートテーブル(Ｖ６)２２４における格納場所を示す。
【００３８】
まず、ＩＰＶ４フロー情報の登録動作について説明する。
【００３９】
ＩＰＶ４登録部２１５は、ルーティング処理部２１３から渡された検索キー(ＩＰＶ４)をハッシュ演算部２１４によってハッシュ値に変換し(ステップ３０１)、このハッシュ値で示される一次ハッシュテーブル２２１のエントリのＶＡＬＩＤフラグによってそのエントリが空いていることが示されている場合は(ステップ３０２の否定判定)、このエントリを登録先として決定して(ステップ３０３)、ステップ３０４からステップ３０５のフロー情報の登録処理を実行する。ＩＰＶ４登録部２１５は、アソシエートテーブル(Ｖ４)２２２の格納場所を確保してその識別情報(ＡＴ−ＩＤ)を検索キー(ＩＰＶ４)と組み合わせて登録先のエントリに登録して(ステップ３０４)、検索キー(ＩＰＶ４)とＡＴ−ＩＤとの対応付けを示す。このような一次ハッシュテーブル２２１への登録処理とともに、ＩＰＶ４登録部２１５は、上述したＶＡＬＩＤフラグをオンにするとともに、ルーティング処理部２１３から渡されたルーティング情報をアソシエートテーブル２２２に確保した格納場所に登録する処理を行い(ステップ３０５)、これらの処理の完了後にフロー情報の登録処理を終了する。
【００４０】
一方、ハッシュ値で示されるエントリのＶＡＬＩＤフラグによって登録情報が存在する旨が示されている場合に(ステップ３０２の肯定判定)、ＩＰＶ４登録部２１５は、まず、エントリに設けられたＶ６フラグに基づいて、登録された情報がＩＰＶ６パケットに関するものであるか否かを判定する(ステップ３０６)。ステップ３０６の否定判定の場合に、ＩＰＶ４登録部２１５は、更に、登録対象の検索キーが登録済みの検索キーと一致しないことを確認し(ステップ３０７の否定判定)、エントリに設けられたポインタ情報(Next-Pt)を参照する。ポインタ情報で結ばれたエントリが存在することが示された場合に(ステップ３０８)、ＩＰＶ４登録部２１５は、ポインタ情報で示されたエントリを参照し(ステップ３０９)、ステップ３０６に戻って、ポインタ情報で結び付けられたエントリに登録されている情報がＩＰＶ６パケットに関するものであるか否かを判定する。
【００４１】
ポインタ情報で示されたエントリにＩＰＶ６パケットに関する縮退キーが格納されていた場合に(ステップ３０６の肯定判定)、ＩＰＶ４登録部２１５は、上述したステップ３０８をスキップしてステップ３０８に進む。
【００４２】
このようにステップ３０６からステップ３０９を繰り返してポインタ情報を辿っていき、ポインタ情報が登録されていないエントリに到達したときに(ステップ３０８の否定判定)、ＩＰＶ４登録部２１５は、一次ハッシュテーブル２２１への新たな登録情報の登録先のエントリを決定するとともに、このエントリを示すポインタ情報をステップ３０９で最後に参照したエントリに登録してから(ステップ３１０)、ステップ３０４、ステップ３０５のフロー登録処理を行って処理を終了する。
【００４３】
なお、登録対象の検索キー(Ｖ４)と既に登録されている検索キー(Ｖ４)とが一致した場合に(ステップ３０７の肯定判定)、ＩＰＶ４登録部２１５は、登録誤りが発生したと判断して処理を異常終了させる。
【００４４】
このようにして、ＩＰＶ４登録部２１５は、検索キー(Ｖ４)について得られたハッシュ値に基づいて、検索キー(Ｖ４)とフロー情報の格納先を示すＡＴ−ＩＤとの組み合わせを一次ハッシュテーブル２１１に登録していく。
【００４５】
上述した登録処理では、ステップ３０２でハッシュ値の衝突を検出した際に、参照したエントリに設けられたＶ６フラグがオフである場合に限って、登録対象の検索キー(Ｖ４)と既に登録されている検索キー(Ｖ４)との一致を判定することにより(ステップ３０７)、一次ハッシュテーブル２１１において、ＩＰＶ４パケットについての登録情報とＩＰＶ６パケットについての登録情報との共存が図られている。
【００４６】
一方、ＩＰＶ６パケットについてのフロー情報は、ＩＰＶ６登録部２１６により、一次ハッシュテーブル２２１と二次ハッシュテーブル２２３との両方と、アソシエートテーブル(Ｖ６)２２４とを用いて登録される。
【００４７】
以下、ＩＰＶ６フロー情報の登録動作について説明する。
【００４８】
ＩＰＶ６登録部２１６は、まず、ルーティング処理部２１３から渡されたキー情報(ＩＰＶ６)からアドレス情報を抽出してハッシュ演算部２１４に渡し、ハッシュ演算処理によって得られたＩＰＶ４のアドレス情報と同じ長さの縮退アドレスとプロトコル識別子やポート情報と組み合わせて縮退キーを生成する(ステップ３１１)。
【００４９】
このようにして生成された縮退キーは、検索キー(Ｖ４)と同じデータ長である。したがって、後述する縮退キーの衝突が起きない限りは、ステップ３１２において、ハッシュ演算部２１４によってこの縮退キーに対応して得られたハッシュ値に基づいて、検索キー(Ｖ４)と同様にして縮退キーを一次ハッシュテーブル２２１に登録することができる。
【００５０】
図４に示した流れ図では、図３に示したＩＰＶ４フロー情報の登録処理と同様にしてフロー情報をアソシエートテーブル(Ｖ６)２２４に登録するとともに、このフロー情報の格納場所を示すＡＴ−ＩＤと縮退キーとの組み合わせを一次ハッシュテーブル２２１に登録する過程で、参照したエントリに設けられたＶ６フラグがオンのときに限って、参照しているエントリに登録された縮退キーと新たな登録対象の縮退キーとを照合し(ステップ３１３)、一致している場合に(ステップ３１３の肯定判定)、重複処理を行っている。
【００５１】
また、ＩＰＶ６登録部２１６は、アソシエートテーブル２２４にフロー情報を登録する際に、フロー情報とともに縮退前のアドレス情報を登録し(ステップ３１４)、後述する重複処理に備えている。
【００５２】
図５に示す重複処理の前半では、ＩＰＶ６登録部２１６は、まず、上述したステップ３１３で縮退キーの一致が検出されたエントリに設けられた重複フラグ(ＦＤ)をオンとして縮退キーの重複が発生したことを示す(ステップ３１５)。
【００５３】
次いで、ＩＰＶ６登録部２１６は、縮退前の検索キー(ＩＰＶ６)をハッシュ演算部２１４に渡して二次ハッシュテーブル２２３用のハッシュ値を求め(ステップ３１６)、このハッシュ値で示された二次ハッシュテーブル２２３のエントリを参照して、既に登録されているか否かを判定する(ステップ３１７)。ステップ３１７の否定判定の場合に、ＩＰＶ６登録部２１６は、この二次ハッシュテーブル２２３のエントリを登録先として決定して(ステップ３１８)、ステップ３０４からステップ３０５と同様に、アソシエートテーブル(Ｖ６)２２４および二次ハッシュテーブル２２３への登録処理を実行する(ステップ３１９，３１４)。
【００５４】
一方、ステップ３１７の肯定判定の場合に、ＩＰＶ６登録部２１６は、登録対象の検索キー(ＩＰＶ６)と登録済みの検索キーとが一致していないことを確かめた後に(ステップ３２０の否定判定)、上述したステップ３０８，３０９と同様にして、ポインタ情報を調べて辿る処理を行う(ステップ３２１，３２２)。検索キーが一致した場合は登録エラーとして登録をスキップする（ステップ３２４）。そして、ステップ３２０からステップ３２２を繰り返して、ポインタ情報が登録されていないエントリに辿りついたときに(ステップ３２１の否定判定)、新たな登録先を決定するとともに、そのエントリを示すポインタ情報をステップ３２２で最後に参照したエントリに登録し(ステップ３２３)、フロー情報の登録処理を開始する(ステップ３１９，３１４)。
【００５５】
図５において、太い破線で囲んで示した二次登録処理の完了後に、ＩＰＶ６登録部２１６は、続いて、一次ハッシュテーブル２２１を使って登録された情報を二次ハッシュテーブル２２３に登録し直す再登録処理を行う。
【００５６】
また、ステップ３２０において、検索キー(ＩＰＶ６)についての重複が検出された場合に(ステップ３２０の肯定判定)、ＩＰＶ６登録部２１６は、登録誤りが発生したと判断し、登録対象のフロー情報の登録をスキップして、一次ハッシュテーブル２２１から二次ハッシュテーブル２２３への再登録処理を行う。
【００５７】
上述したようにして、重複処理の前半で登録対象のフロー情報についての登録処理が完了した後に、重複処理の後半として、ＩＰＶ６登録部２１６は、以下に述べる一次ハッシュテーブル２２１から二次ハッシュテーブル２２３への再登録処理を行う。
【００５８】
図６に示した再登録処理において、ＩＰＶ６登録部２１６は、まず、上述したステップ３１３で縮退キーの重複を検出したエントリに登録されたＡＴ−ＩＤを抽出し(ステップ３３１)、得られたＡＴ−ＩＤに基づいてアソシエートテーブル２２４にフロー情報とともに登録された縮退前のアドレス情報を読み出す(ステップ３３２)。
【００５９】
次いで、ＩＰＶ６登録部２１６は、ステップ３３２で得られた縮退前のアドレス情報と上述したエントリに登録された縮退キーに含まれる縮退アドレス以外の情報とを組み合わせて、縮退前の検索キー(ＩＰＶ６)を復元する(ステップ３３３)。
【００６０】
このようにして復元された検索キー(ＩＰＶ６)について、ＩＰＶ６登録部２１６は、図５に太い破線で囲んで示した二次登録処理と同様にして、この検索キー(ＩＰＶ６)に対応するハッシュ値で示される二次ハッシュテーブル２２３のエントリに検索キー(ＩＰＶ６)とフロー情報の格納先を示すＡＴ−ＩＤとを登録する(ステップ３３４)。
【００６１】
ステップ３３４で二次ハッシュテーブル２２３に登録される検索キー(ＩＰＶ６)で特定されるフローに対応するフロー情報は、既にアソシエートテーブル(Ｖ６)２２４に登録されており、その登録先は、一次ハッシュテーブル２２１に示されている。したがって、ステップ３３４では、一次ハッシュテーブルから得られるＡＴ−ＩＤを検索キー(ＩＰＶ６)とともに二次ハッシュテーブル２２３に登録する処理を行えばよい。
【００６２】
このようにして、縮退キーの重複が検出されたエントリに登録された情報を二次ハッシュテーブル２２３に再登録する処理が完了した後に、ＩＰＶ６登録部２１６は、このエントリにポインタ情報が登録されているか否かを判定する(ステップ３３５)。ＩＰＶ６登録部２１６は、このステップ３３５の肯定判定の場合に、ポインタ情報で示されたエントリを参照し(ステップ３３６)、そのエントリに設けられたＶ６フラグを調べ、そのエントリに縮退キーが登録されていた場合には(ステップ３３７の肯定判定)、このエントリの登録情報についても再登録が必要と判断する。
【００６３】
この場合に、ＩＰＶ６登録部２１６は、ステップ３３６で参照したエントリに登録されたＡＴ−ＩＤを抽出し(ステップ３３８)、ステップ３３２〜ステップ３３４の再登録処理を行う。
【００６４】
一方、ステップ３３６で参照したエントリに検索キー(ＩＰＶ４)が登録されていた場合に(ステップ３３７の否定判定)、ＩＰＶ６登録部２１６は、再登録処理をスキップしてステップ３３５に戻り、ポインタ情報を辿る処理を続ける。
【００６５】
このようにして、ステップ３３２〜ステップ３３７の処理を繰り返すことにより、縮退キーの重複が検出されたエントリとポインタ情報によって結ばれたエントリに登録された情報のうち、ＩＰＶ６パケットのフロー情報に関する情報を二次ハッシュテーブル２２３に再登録することができる。
【００６６】
その後、ポインタ情報が登録されていないエントリに辿りついたときに(ステップ３３５の否定判定)、ＩＰＶ６登録部２１６は、再登録処理を含めた登録処理が完了したと判断し、処理を終了する。
【００６７】
このようにして、データ長の長い検索キー(ＩＰＶ６)に代えて縮退キーを用いることにより、ＩＰＶ４と共通の一次ハッシュテーブル２２１に、ＩＰＶ６パケットのフロー情報を検索するための情報を登録することができる。
【００６８】
また、個々のネットワーク機器に備えられたルーティングテーブルにおいて扱うフロー数、つまり、一次ハッシュテーブル２２１において同時に使用されるエントリ数は数千から数万であり、上述した３２ｂｉｔの縮退アドレスで表される値の範囲(４Ｇ：４×１０９)に比べて十分に小さい。したがって、異なるフロー情報に対応する検索キー(ＩＰＶ６)がハッシュ演算によって同一の縮退キーに変換される可能性はきわめて低いので、一次ハッシュテーブル２２１において、縮退キーの重複が起こる可能性は非常に低く、ほとんどのフロー情報を一次ハッシュテーブル２２１に登録することができる。
【００６９】
なお、ＩＰＶ６パケットを特定する検索キー(ＩＰＶ６)から縮退キーを生成する際に、上述したアドレス情報に加えてポート情報など他の情報をあわせて縮退させることもできる。その場合は、縮退キーの生成のために縮退させた全ての情報を、上述した縮退前のアドレス情報と同様に、アソシエートテーブル(Ｖ６)２２４に退避しておき、二次ハッシュテーブル２２３への再登録処理に備える。
【００７０】
上述したようにしてルーティングテーブル２２０に登録されたフロー情報は、ＩＰＶ４検索部２１８およびＩＰＶ６検索部２１７が以下に述べるような検索処理を行うことによって検索することができる。
【００７１】
図７に、ＩＰＶ４フロー情報の検索動作を表す流れ図を示す。
【００７２】
ＩＰＶ４検索部２１８は、ハッシュ演算部２１４を用いて、ルーティング処理部２１３から渡された検索キー(ＩＰＶ４)からハッシュ値を求め(ステップ３４１)、一次ハッシュテーブル２２１のハッシュ値で示されるエントリを参照する(ステップ３４２)。
【００７３】
ＶＡＬＩＤフラグによってそのエントリが登録済みであることが示されている場合に(ステップ３４３の肯定判定)、ＩＰＶ４検索部２１８は、Ｖ６フラグに基づいて、そのエントリへの登録が検索キー(ＩＰＶ４)であるか否かを判定し(ステップ３４４)、肯定判定の場合に、登録された検索キーとルーティング処理部２１３から渡された検索キーとを照合する(ステップ３４５)。
【００７４】
２つの検索キーが一致した場合に(ステップ３４５の肯定判定)、ＩＰＶ４検索部２１８は、一次ハッシュテーブル２２１の参照中のエントリに登録されたＡＴ−ＩＤを読み出し(ステップ３４６)、このＡＴ−ＩＤに対応してアソシエートテーブル(Ｖ４)２２２に登録されたフロー情報を読み出して、ルーティング処理部２１３に返して(ステップ３４７)処理を終了する。
【００７５】
一方、２つの検索キーが不一致の場合(ステップ３４５の否定判定)およびステップ３４４の否定判定の場合に、ＩＰＶ４検索部２１８は、ポインタ情報を辿って、同一のハッシュ値に変換された検索キーが登録されている別のエントリを探索する(ステップ３４８，３４９)。ポインタ情報で示されたエントリに登録されている検索キーとルーティング処理部２１３から渡された検索キーとが一致するまで、ポインタ情報を辿る処理と検索キーを照合する処理を繰り返す。
【００７６】
上述したポインタ情報を辿る処理の過程で参照したエントリに一致する検索キーが見出せなかった場合(ステップ３４８の否定判定)とハッシュ値に対応するエントリに有効な登録情報がないことが示された場合(ステップ３４３の否定判定)に、ＩＰＶ４検索部２１８は、ルーティング処理部２１３に検索ミスを通知して処理を終了する。
【００７７】
また、図８、図９に、ＩＰＶ６フロー情報の検索動作を表す流れ図を示す。
【００７８】
なお、図８，９に示した構成要素のうち、図７に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【００７９】
ＩＰＶ６検索部２１７は、ルーティング処理部２１３から受け取った検索キー(ＩＰＶ６)をハッシュ演算部２１４を用いて縮退キーに変換し(ステップ３５１)、更に、この縮退キーに対応するハッシュ値を求めて(ステップ３５２)、このハッシュ値で示される一次ハッシュテーブル２２１のエントリを参照する(ステップ３４２)。
【００８０】
参照したエントリに登録情報があった場合に(ステップ３４３の肯定判定)、ＩＰＶ６検索部２１７は、Ｖ６フラグに基づいて縮退キーが登録されているか否かを判定し(ステップ３５３)、肯定判定の場合に、重複フラグがオンとなっていないことを確かめて(ステップ３５４の否定判定)、登録されている縮退キーとステップ３５１で生成した縮退キーとを照合する(ステップ３５５)。
【００８１】
２つの縮退キーが一致した場合に(ステップ３５５の肯定判定)、ＩＰＶ６検索部２１７は、上述したステップ３４６と同様にして、一次ハッシュテーブル２２１の参照中のエントリに登録されたＡＴ−ＩＤを読み出す。次いで、アソシエートテーブル(Ｖ６)２２４にこのＡＴ−ＩＤに対応して登録されたフロー情報を読み出して、ルーティング処理部２１３に返して処理を終了する。
【００８２】
一方、ステップ３５３の否定判定の場合およびステップ３５５の否定判定の場合に、ＩＰＶ６検索部２１７は、上述したＩＰＶ４フロー情報の検索と同様に、ステップ３５３，３５４，３５５およびステップ３４８，３４９を繰り返して、ポインタ情報で示された一次ハッシュテーブル２２１のエントリを辿っていく過程で、ステップ３５２で生成した縮退キーと一致する縮退キーが登録されたエントリを探索する。
【００８３】
上述した探索過程で最後にたどり着いたエントリにポインタ情報が登録されていなかった場合(ステップ３４８の否定判定)と上述したステップ３４３の否定判定の場合に、ＩＰＶ６検索部２１７は、検索ミスをルーティング処理部２１３に通知して処理を終了する。
【００８４】
一方、参照したエントリの重複フラグによって縮退キーの重複が発生したことが示された場合に(ステップ３５４の肯定判定)、ＩＰＶ６検索部２１７は、後述するようにして、二次ハッシュテーブル２２３の検索処理を行う。
【００８５】
図９に示す二次ハッシュテーブルの検索処理では、ＩＰＶ６検索部２１７は、ルーティング処理部２１３から受け取った検索キー(ＩＰＶ６)に対応するハッシュ値を求め(ステップ３６１)、このハッシュ値で示される二次ハッシュテーブル２２３のエントリを参照する(ステップ３６２)。
【００８６】
該当するエントリに検索キーが登録されている場合に(ステップ３６３の肯定判定)、ＩＰＶ６検索部２１７は、上述した一次ハッシュテーブル２２１の検索と同様にして、ポインタ情報で結び付けられたエントリを次々に参照して、ルーティング処理部２１３から渡された検索キーと登録された検索キーとを照合する(ステップ３６４〜ステップ３６７)。そして、２つの検索キーが一致したときに(ステップ３６４の肯定判定)、ＩＰＶ６検索部２１７は、対応して登録されたＡＴ−ＩＤに基づいてフロー情報をアソシエートテーブル(Ｖ６)２２４から読み出して(ステップ３６５、ステップ３５６)、ルーティング処理部２１３に読み出したフロー情報を返して処理を終了する。
【００８７】
一方、ステップ３６３の否定判定の場合やステップ３６６の否定判定の場合に、ＩＰＶ６検索部２１７は、検索ミスをルーティング処理部２１３に通知して、処理を終了する。
【００８８】
上述したように、一次ハッシュテーブル２２１に設けられた重複フラグに基づいて、ＩＰＶ６検索部２１７により、一次ハッシュテーブル２２１に対する検索動作と二次ハッシュテーブル２２３に対する検索動作とが切り替えられる。
【００８９】
ここで、上述したように、ＩＰＶ６パケットに対応するフロー情報の検索のために一次ハッシュテーブル２２１に登録される縮退キーのデータ長は、一般的なキャッシュメモリのキャッシュライン以下のビット数に抑えられている。したがって、ＩＰＶ４パケットのフロー情報の検索と同様に、ＩＰＶ６パケットのフロー情報の検索を１回のメモリアクセスで行うことが可能となり、ＩＰＶ６パケットについてのフロー情報の検索に要する時間の短縮を図ることができる。
【００９０】
また、上述したようにして、ＩＰＶ６フロー情報の検索に用いる情報を登録するエントリのデータ長を抑えたことにより、一般的なキャッシュメモリに一次ハッシュテーブルを格納した場合に、キャッシュメモリに格納されるエントリ数を、ＩＰＶ４用のハッシュテーブルと同程度にすることができる。これにより、ＩＰＶ６フロー情報の検索においてもキャッシュミスの可能性を低くして、検索処理に要する時間の短縮を図ることができる。
【００９１】
なお、上述したように、縮退キーが登録された一次ハッシュテーブルと縮退前の検索キーが登録された二次ハッシュテーブルとを検索キーに関連付けられた関連情報(例えば、フロー情報)の検索処理に供する構成は、一般的なメモリから１回のアクセスで読み出し可能なデータ長を超える長さを持つ検索キーを用いる情報検索装置であれば、いかようなものにも適用できる。
【００９２】
また、例えば、ＩＰＶ４パケットについてのフロー情報の検索に用いるハッシュテーブルとは別に、ＩＰＶ６パケットについてのフロー情報の検索のみに用いる一次ハッシュテーブルと二次ハッシュテーブルを設けることもできる。このような構成では、ＩＰＶ４用のハッシュテーブルに加えて、ＩＰＶ６用の２つのハッシュテーブルを設けるので、その分ハードウェア量が増大する反面、一次ハッシュテーブルをＩＰＶ４とＩＰＶ６とで共用した場合のように、登録された検索キーの種類を判別する処理などが不要となる。
【図面の簡単な説明】
【００９３】
【図１】情報検索装置の実施形態を示す図である。
【図２】ハッシュテーブルとアソシエートテーブルの関係を説明する図である。
【図３】ＩＰＶ４フロー情報の登録動作を表す流れ図である。
【図４】ＩＰＶ６フロー情報の登録動作を表す流れ図（１）である。
【図５】ＩＰＶ６フロー情報の登録動作を表す流れ図（２）である。
【図６】ＩＰＶ６フロー情報の登録動作を表す流れ図（３）である。
【図７】ＩＰＶ４フロー情報の検索動作を表す流れ図である。
【図８】ＩＰＶ６フロー情報の検索動作を表す流れ図（１）である。
【図９】ＩＰＶ６フロー情報の検索動作を表す流れ図（２）である。
【図１０】ハッシュテーブルを用いたフロー情報の検索の説明図である。
【符号の説明】
【００９４】
２１１  ＩＰＶ６ネットワークインタフェース(Ｉ／Ｆ)
２１２  ＩＰＶ４ネットワークインタフェース(Ｉ／Ｆ)
２１３  ルーティング処理部
２１４  ハッシュ演算部
２１５  ＩＰＶ４登録部
２１６  ＩＰＶ６登録部
２１７  ＩＰＶ６検索部
２１８  ＩＰＶ４検索部
２２０  ルーティングテーブル
２２１  一次ハッシュテーブル
２２２  アソシエートテーブル(Ｖ４)
２２３  二次ハッシュテーブル
２２４  アソシエートテーブル(Ｖ６)
４１１，４２１  ハッシュテーブル
４１２，４２２  アソシエートテーブル
【図１】
2010050600.tif 000003
【図２】
2010050600.tif 000004
【図３】
2010050600.tif 000005
【図４】
2010050600.tif 000006
【図５】
2010050600.tif 000007
【図６】
2010050600.tif 000008
【図７】
2010050600.tif 000009
【図８】
2010050600.tif 000010
【図９】
2010050600.tif 000011
【図１０】
2010050600.tif 000012