(57)【要約】【課題】  効率的かつ高速に情報を管理できる情報管理装置を提供する。【解決手段】  情報管理装置が、情報エントリに関連する関連情報エントリを有効にする際に、情報エントリと関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、関連情報エントリの世代情報と同一の世代情報を関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理部と、情報エントリのいずれかが変更されたときに、変更された情報エントリに関連する関連情報エントリを無効にする処理をするとともに、関連情報エントリの世代情報を更新する関連性無効化処理部と、関連オブジェクトが有する世代情報と、関連オブジェクトに対応する関連情報エントリが有する世代情報とを比較し、この比較結果に応じて関連オブジェクトを回収するガーベジ収集処理部とを備える。【選択図】  図１１
2009017440.tif 000002
【特許請求の範囲】
【請求項１】
複数個の情報エントリを有する第１記憶部と、
単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、
前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部と、
前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理部と、
前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理部と、
前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理部と、
を備えることを特徴とする情報管理装置。
【請求項２】
前記第２記憶部が有する関連情報エントリは、前記第１記憶部が有する複数の前記情報エントリをまとめて保持するキャッシュブロックである
ことを特徴とする請求項１に記載の情報管理装置。
【請求項３】
請求項２に記載の情報管理装置を備え、
前記第１記憶部は、パケットを転送する際に参照されるデータを記憶するデータベースであり、
前記第２記憶部は、前記パケット内の所定のキー情報に基づき前記データベースから読み出されたデータを、当該キー情報ごとに保持しておくキャッシュブロックであり、
前記情報管理装置は、
前記パケット内の前記キー情報に基づき、前記第２記憶部に有効なデータが存在する場合には前記第２記憶部から読み出した前記データを参照して当該パケットを転送する処理をし、前記第２記憶部に有効なデータが存在しない場合には前記第１記憶部から読み出した前記データを参照して当該パケットを転送する処理をする転送処理部
をさらに備えることを特徴とするパケット転送装置。
【請求項４】
複数個の情報エントリを有する第１記憶部と、
単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、
前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部と、
を備える情報管理装置による情報管理方法であって、
前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理過程と、
前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理過程と、
前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理過程と、
を含むことを特徴とする情報管理方法。
【請求項５】
前記第２記憶部が有する関連情報エントリは、前記第１記憶部が有する複数の前記情報エントリをまとめて保持するキャッシュブロックである
ことを特徴とする請求項４に記載の情報管理方法。
【請求項６】
請求項５に記載の情報管理方法の各過程を含む、パケット転送方法であって、
前記第１記憶部は、パケットを転送する際に参照されるデータを記憶するデータベースであり、
前記第２記憶部は、前記パケット内の所定のキー情報に基づき前記データベースから読み出されたデータを、当該キー情報ごとに保持しておくキャッシュブロックであり、
前記パケット内の前記キー情報に基づき、前記第２記憶部に有効なデータが存在する場合には前記第２記憶部から読み出した前記データを参照して当該パケットを転送する処理をし、前記第２記憶部に有効なデータが存在しない場合には前記第１記憶部から読み出した前記データを参照して当該パケットを転送する処理をする転送処理過程
をさらに含むことを特徴とするパケット転送方法。
【請求項７】
複数個の情報エントリを有する第１記憶部と、
単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、
前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部と、
を備えるコンピュータに、
前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理過程と、
前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理過程と、
前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理過程と、
の処理を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報の管理・維持を行なう、情報管理装置、情報管理方法、およびコンピュータプログラムに関する。また、このような情報管理装置、情報管理方法およびコンピュータプログラムを用いた、パケット転送装置、パケット転送方法に関する。
【背景技術】
【０００２】
コンピュータを用いて高速な処理を行なうために、テーブルやリンクリストなどといったデータの構造体を互いに関連付ける方法がある。このような、データからデータへの関連付けは、例えばポインタを用いた参照により行なわれる。ポインタの典型的な実現方法は、ポインタが指し示す先のデータのアドレスを用いるものである。
【０００３】
例えば、データ通信のためのパケット転送装置（ルータや、スイッチなど）においては、パケットを転送するために必要な情報をテーブル上に保持し、適宜、それらのテーブルを参照することによってパケット転送処理が行なわれる。例としては、特許文献１の第００１１段落および図２などには、複数のテーブルを参照しながら、パケットのフィルタリングや送信を行なう発明の構成が記載されている。
【特許文献１】特開平６−２６１０７８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ポインタ等を用いて参照元データから参照先データへの関連付けが予め行なわれており、そのような状況下でデータ処理の結果として参照先データが無効になった場合、もはやその関連付けを維持することに意味がないため、無駄な処理を避ける観点や記憶装置の容量を有効に利用する観点から、そのような関連付けを削除することが望ましい。
【０００５】
参照先データが無効になる原因が参照元データ側にある場合は、参照元データ側に付随している関連付け情報（ポインタ）を削除すれば済む。しかし、参照先データが無効になる原因が参照元データ側にない場合は、無効になる当該参照先データを関連付けている参照元データを特定するのは、全件サーチするなどすれば可能ではあるが、困難であり、あるいは少なくとも時間がかかりすぎるという問題がある。
また、複数の参照元データから、単一の参照先データへの関連付けが行なわれており、各々の関連付け情報を参照元データ側で保持しており、ある一つの参照元データ側が原因となってその参照先データが無効になる場合に、無効になる参照先データを関連付けている参照元データであって、その無効になる原因となった参照元データ以外の参照元データ側に付随している関連付け情報を特定して削除するのは、上記と同様の困難があり、あるいは上記と同様に処理に時間がかかりすぎるという問題がある。
【０００６】
このような問題を解決する一つの方法は、参照先から参照元への逆ポインタを設けて双方向リンクの状態を予め作っておくことであるが、そうするとデータ構造が複雑になり、記憶装置の容量の問題や、処理時間の問題など、好ましくない問題が生じ得る。
【０００７】
本発明は、上記の課題認識に基づいて行なわれたものであり、ある参照先データに対して複数の参照元から関連付けが行なわれている場合にも、参照先データが無効になった場合には当該参照先データへの関連付けを適切に削除し、尚且つ記憶装置の容量を無駄にせずに情報の管理・維持を行なうことのできる、情報管理装置、情報管理方法、およびコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
［１］上記の課題を解決するため、本発明の一態様による情報管理装置は、複数個の情報エントリを有する第１記憶部と、単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部と、前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理部と、前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理部と、前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理部とを備えることを特徴とする。
この構成によれば、第１記憶部が記憶する情報エントリは、第２記憶部が記憶する関連情報エントリに関連しており、その関連は関連性情報として関連オブジェクト記憶部に記憶される。また関連情報エントリは、当該関連情報エントリの世代を表わす世代情報との組として記憶されている。そして、情報エントリに関連する関連情報エントリを有効にする際、関連性有効化処理部は、関連性情報を含む関連オブジェクトを生成するとともに、関連情報エントリに対応する世代情報を用いて、当該関連オブジェクト内の世代情報を記録（書き込み）する。情報エントリが変更されたときには、関連性無効化処理部は、その情報エントリに関連する関連情報エントリを無効にするとともに、その関連情報エントリと組になっている世代情報を更新する。これにより、当該関連情報エントリに関連する情報エントリが残ってしまっても、その情報エントリから当該関連情報エントリへの関連を表わす関連オブジェクトの中の世代情報は更新されないままであるので、両方の世代情報の値が異なることとなる。そして、ガーベジ収集処理部は、関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する関連情報エントリが有する世代情報とを比較し、この比較結果として両者が異なる場合には、関連情報エントリは既に無効になったものであり、当該関連オブジェクトは不要なものであるので、当該関連オブジェクトを回収する。つまり、不要な関連オブジェクトのメモリ領域を回収・解放することができる。
【０００９】
［２］また、本発明の一態様による情報管理装置は、前記第２記憶部が有する関連情報エントリは、前記第１記憶部が有する複数の前記情報エントリをまとめて保持するキャッシュブロックであることを特徴とする。
これにより、第１記憶部においてたとえ物理的に分散した位置に記憶されているデータであっても、第２記憶部のキャッシュブロックにまとめて保持しておけるため、データ参照速度を短縮することが出来、処理の高速化を図れる。また、このようなデータ構造を有する情報管理装置においても、前記の通り、不要な関連オブジェクトのメモリ領域を回収・解放することができる。
【００１０】
［３］また、本発明の一態様によるパケット転送装置は、上記の情報管理装置を備え、前記第１記憶部は、パケットを転送する際に参照されるデータを記憶するデータベースであり、前記第２記憶部は、前記パケット内の所定のキー情報に基づき前記データベースから読み出されたデータを、当該キー情報ごとに保持しておくキャッシュブロックであり、前記情報管理装置は、前記パケット内の前記キー情報に基づき、前記第２記憶部に有効なデータが存在する場合には前記第２記憶部から読み出した前記データを参照して当該パケットを転送する処理をし、前記第２記憶部に有効なデータが存在しない場合には前記第１記憶部から読み出した前記データを参照して当該パケットを転送する処理をする転送処理部を備えることを特徴とするパケット転送装置。
これにより、パケット転送の際に参照されるデータを、第１記憶部から読み出して使用したときに、第２記憶部に書き込んでおくことが出来る。よって、第２記憶部に有効にデータが残っている限り、第１記憶部から読むよりも短時間でそのデータを第２記憶部から読み出して、このデータを用いた処理を行なうことができる。つまり、パケット転送処理を高速化しながら、キャッシュブロックを用いるための関連オブジェクトが不要になった場合には適宜これを回収・解放できるため、メモリを有効に使用できる。
【００１１】
［４］また、本発明の一態様による情報管理方法は、複数個の情報エントリを有する第１記憶部と、単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部とを備える情報管理装置による情報管理方法であって、前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理過程と、前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理過程と、前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理過程とを含むことを特徴とするものである。
【００１２】
［５］また、本発明の一態様による情報管理方法は、上記の情報管理方法において、前記第２記憶部が有する関連情報エントリは、前記第１記憶部が有する複数の前記情報エントリをまとめて保持するキャッシュブロックであることを特徴とするものである。
【００１３】
［６］また、本発明の一態様によるパケット転送方法は、上記の情報管理方法の各過程を含むパケット転送方法であって、前記第１記憶部は、パケットを転送する際に参照されるデータを記憶するデータベースであり、前記第２記憶部は、前記パケット内の所定のキー情報に基づき前記データベースから読み出されたデータを、当該キー情報ごとに保持しておくキャッシュブロックであり、前記パケット内の前記キー情報に基づき、前記第２記憶部に有効なデータが存在する場合には前記第２記憶部から読み出した前記データを参照して当該パケットを転送する処理をし、前記第２記憶部に有効なデータが存在しない場合には前記第１記憶部から読み出した前記データを参照して当該パケットを転送する処理をする転送処理過程を含むことを特徴とするものである。
【００１４】
［７］また、本発明の一態様によるコンピュータプログラムは、複数個の情報エントリを有する第１記憶部と、単数又は複数の前記情報エントリに関連する情報を格納するための関連情報エントリと、当該関連情報エントリに対応する世代を表わす世代情報との組を複数有する第２記憶部と、前記情報エントリと該情報エントリに関連する前記関連情報エントリとの間に関連があることを表わす関連性情報と、当該関連性情報に対応する世代を表わす世代情報とを有する関連オブジェクトを記憶する関連オブジェクト記憶部とを備えるコンピュータに、前記情報エントリに関連する前記関連情報エントリを有効にする際に、当該情報エントリと当該関連情報エントリとの間に関連があることを表わす関連性情報を含んだ関連オブジェクトを生成するとともに、当該関連情報エントリの世代情報と同一の世代情報を当該関連オブジェクトの世代情報として書き込む処理を行なう関連性有効化処理過程と、前記情報エントリのいずれかが変更されたときに、変更された当該情報エントリに関連する関連情報エントリを無効にする処理をするとともに、当該関連情報エントリの世代情報を更新する関連性無効化処理過程と、前記関連オブジェクトが有する世代情報と、当該関連オブジェクトに対応する前記関連情報エントリが有する世代情報とを比較し、この比較結果に応じて当該関連オブジェクトを回収するガーベジ収集処理過程との処理を実行させるものである。
【発明の効果】
【００１５】
本発明によれば、情報エントリが変更されて、関連情報エントリを無効にしたとき、当該関連情報エントリに関連する他の情報エントリからの関連を表わす関連オブジェクトについても、適切に回収・解放することが出来るため、メモリを無駄に使うことがない。
また、本発明によれば、このような不要な関連オブジェクトを回収するために、双方向リンクを予め設定しておく必要がなく、データ構造の簡略化と、処理の簡素化を図ることも出来る。
また、本発明によれば、関連情報エントリが無効になったときにその関連情報エントリの世代情報を更新することによって関連オブジェクトが不要になったかどうかを表わせるようにしたため、たとえその関連情報エントリが再利用されて他の情報エントリのために有効になったとしても、正しく不要な関連オブジェクトの回収を行なうことができる。
【００１６】
また、本発明によれば、上記のようなデータ管理のしくみを、データベースとキャッシュブロックとの関係に適用することが出来、そのようなデータベースを有するシステムの処理を高速化するとともに、関連オブジェクトに用いられる記憶領域を無駄なく有効に使うことが出来る。
また、本発明によれば、上記のようなデータベースとキャッシュブロックを、パケット転送装置における、転送処理に必要な参照情報を記憶するしくみとに適用できるため、パケット転送装置の処理を高速化しながら、関連オブジェクトに用いられる記憶領域を無駄なく有効に使うことが出来る。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照し、本発明の実施形態を説明する。図１は本発明の一実施形態によるスイッチ装置１（パケット転送装置）の構成を示すブロック図である。スイッチ装置１は制御カード装置２と、入出力ラインカード装置３−１〜３−３と、フォワーディング処理装置４−１〜４−３と、スイッチ部６とを備える。制御カード装置２はスイッチ装置１の全体の制御を行う。また、フォワーディング処理装置４−１はパケット処理部５−１を備え、フォワーディング処理装置４−２はパケット処理部５−２を備え、フォワーディング処理装置４−３はパケット処理部５−３を備える。パケット処理部５−１〜５−３はスイッチ部６と接続されており、スイッチ部６を介しパケット処理部５−１〜５−３間でパケットの送受信を行うことが可能である。パケット処理部５−１は入出力ラインカード装置３−１と接続され、パケット処理部５−２は入出力ラインカード装置３−２と接続され、パケット処理部５−３は入出力ラインカード装置３−３と接続されている。パケット処理部５−１〜５−３は入出力ラインカード装置３より受信したパケットの転送処理を行う。入出力ラインカード装置３−１〜３−３はそれぞれポートを３つ備えており、ポートを介して外部装置（図示せず）とパケットの送受信を行う。
【００１８】
図２は本実施形態のパケット転送装置の構成を示す機能ブロック図である。パケット転送装置１は、入出力ポート３と、フィールド抽出部１１と、インデックス計算部１２（キャッシュブロック特定部）と、検証情報格納部１３と、検証部１４と、フォワーディング部１７と、キャッシュ部２００とデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）（記憶部）とを備える。また、フォワーディング部１７は、データベース参照フォワーディング部１５と、キャッシュ参照フォワーディング部１６とを備える。キャッシュ部２００はキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）を含む。
【００１９】
図示する例では、データベースはデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のｎ個がある。また、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）は、ＣＰＵが直接読み書き可能な主記憶装置である半導体メモリ（ＲＡＭ）に記憶される。データベース１（５２１−１）〜データベースｎ（５２１−ｎ）はパケットの転送処理に必要な情報である参照情報を保管している。データベース１（５２１−１）〜データベースｎ（５２１−ｎ）の種類としては、ポートに関する情報を記憶するポートデータベース、イーサネット（登録商標）アドレスを記憶するフォワーディング・データベース（Ｆｏｒｗａｒｄｉｎｇ  ＤａｔａＢａｓｅ，ＦＤＢ）、バーチャル・ローカル・エリア・ネットワーク（Ｖｉｒｔｕａｌ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ，ＶＬＡＮ）の情報を記憶するバーチャル・ローカル・エリア・ネットワーク・テーブル、ポートとバーチャル・ローカル・エリア・ネットワークをキーとして検索される情報を記憶するポート・バーチャル・ローカル・エリア・ネットワーク・テーブル、パケット転送のサービスレベルの情報を記憶するクオリティ・オブ・サービス（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ，ＱｏＳ）パラメータなどがある。また、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）は複数のエントリを有する。
【００２０】
フィールド抽出部１１は、入出力ポート３を介して受信した転送対象のパケットに含まれる、フォワーディングに関連するフィールドを抽出する。フォワーディングに関連するフィールドはパケットの一部分（ヘッダ）の中に含まれ、ソースアドレス、デスティネーションアドレス、クオリティ・オブ・サービス（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ，ＱｏＳ）等を含んだ制御情報の一部である。インデックス計算部１２はフィールド抽出部１１で抽出したフォワーディングに関連するフィールドのハッシュ値を計算し、計算したハッシュ値に基づいてインデックスを計算し、インデックスに基づいてキャッシュ部２００が含むキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の内一つを特定する。検証情報格納部１３は、フィールド抽出部１１で抽出したフォワーディングに関連するフィールドを検証情報とし、当該検証情報を、インデックス計算部１２が当該フィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に格納する。検証部１４（判断部）は、転送対象のパケットのフォワーディングに関連するフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に、当該パケットのフォワーディングに関連するフィールド（検証情報）と同一の検証情報が記憶されているか否か判断する。パケットの転送はフォワーディングに関連するフィールドに基づいて行われるため、検証情報が同一の場合は、パケットの転送処理も同一である。
【００２１】
なお、一般に、ルータやブリッジの処理では、パケットの一部分に含まれる制御情報のみが転送処理に影響を与えるという特徴があるため、パケットの転送に影響する部分のみをそのパケットの特徴として記録すれば、同種のパケットを選別できる。同種のパケットとは転送処理が同一のパケットを指す。同種のパケットを二度目以降に処理する場合には、最初の処理と同一の処理を行えばよい。そのため、同種の特徴を有するということを確認する手段とそのパケットを加工したり出力したりするときに、データベースから読み込んだパケットの転送に必要な情報すべてを一箇所のキャッシュに格納し、これをハッシュ関数で高速に検索できれば転送処理は格段に速くなる。
【００２２】
フォワーディング部１７は、パケットの加工およびパケットの転送を行う。フォワーディング部１７はデータベース参照フォワーディング部１５と、キャッシュ参照フォワーディング部１６とを備えており、パケットの加工およびバケットの転送は同様の処理を行うが、加工および転送に必要な情報の読み取り先が異なる。データベース参照フォワーディング部１５はデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）から加工及び転送に必要な情報を読み取る。また、データベース参照フォワーディング部１５は、読み取った情報を当該パケットのフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に書き込む。一方、キャッシュ参照フォワーディング部１６は、データベース参照フォワーディング部１５がデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）から読みだしキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に書き込んだ情報を、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）から読み取ってパケットの加工およびパケットの転送を行う。すなわち、一度フォワーディング部１７がデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）より読み取ったデータはキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に書き込まれているので、以前転送処理を行ったパケットと同種の特徴を有するパケットに対し、同一の転送処理を行う場合はキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）からデータを読み取り転送処理を行う。フォワーディング部１７は、検証部１４が転送対象のパケットのフォワーディングに関連するフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に、当該パケットのフォワーディングに関連するフィールド（検証情報）と同一の検証情報が記憶されていると判断した場合はキャッシュ参照フォワーディング部１６を用い、記憶されていないと判断した場合はデータベース参照フォワーディング部１５を用いる。
【００２３】
キャッシュ部２００はキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）を含んでおり、半導体メモリ（ＲＡＭ）上に記憶される。この半導体メモリはＣＡＭなど特殊なメモリではなく、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）が記憶される半導体メモリと同様の半導体メモリであっても良い。キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）はデータを記憶することができ、それぞれフォワーディング部１７が連続して読み取ることが出来る領域である。
【００２４】
図３は本実施形態におけるデータベース参照フォワーディング部の動作を説明したブロック図である。図示するように、パケット転送装置１は入出力ポート３と、処理部６０と、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）と、キャッシュ部２００とを含んで構成される。処理部６０は、図２に示したフィールド抽出部１１と、インデックス計算部１２と、検証情報格納部１３と、検証部１４と、フォワーディング部１７とを含む。フォワーディング部１７はデータベース参照フォワーディング部１５とキャッシュ参照フォワーディング部１６とを備える。受信パケット２０および送信パケット２１は転送対象のパケットであり、パケット転送装置１により加工、転送される。
【００２５】
図示する例では、処理部６０が含むフォワーディング部１７はデータベース参照フォワーディング部１５を用いて転送処理を行っている。データベース参照フォワーディング部１５を用いて転送処理を行う場合は、検証部１４が転送対象のパケットのフォワーディングに関連するフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に、当該パケットのフォワーディングに関連するフィールド（検証情報）と同一の検証情報が記憶されていないと判断した場合である。すなわち、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に参照情報が記憶されていないため、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）より参照情報を読み取り、パケットの転送処理を行い、転送対象のパケットのフォワーディングに関連するフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に読み取った参照情報を記憶させる。
【００２６】
図４は本実施形態におけるキャッシュ参照フォワーディング部の動作を説明したブロック図である。図示するように、パケット転送装置１は入出力ポート３と、処理部６０と、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）と、キャッシュ部２００とを含んで構成される。処理部６０は、図２に示したフィールド抽出部１１と、インデックス計算部１２と、検証情報格納部１３と、検証部１４と、フォワーディング部１７とを含む。フォワーディング部１７はデータベース参照フォワーディング部１５とキャッシュ参照フォワーディング部１６とを備える。受信パケット２０および送信パケット２１は転送対象のパケットであり、パケット転送装置１により加工、転送される。
【００２７】
図示する例では、処理部６０が含むフォワーディング部１７はキャッシュ参照フォワーディング部１６を用いて転送処理を行っている。キャッシュ参照フォワーディング部１６を用いて転送処理を行う場合は、検証部１４が転送対象のパケットのフォワーディングに関連するフィールドに基づいて特定されるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に、当該パケットのフォワーディングに関連するフィールド（検証情報）と同一の検証情報が記憶されていると判断した場合である。すなわち、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に参照情報が記憶されているため、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）より参照情報を読み取り、パケットの転送処理を行う。
【００２８】
図５は本発明の一実施形態のデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）が記憶する参照情報と、キャッシュ上のキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）が記憶する処理情報との関連を示したブロック図である。キャッシュブロック１（２１０−１）からキャッシュブロックｔ／２まではソースアドレス用キャッシュラインである。キャッシュブロック（ｔ／２）＋１からキャッシュブロックｔ（２１０−ｔ）はデスティネーションアドレス用キャッシュラインである。なお、ｔは偶数である。
【００２９】
データベース１（５２１−１）は参照情報３０−１と３０−２を記憶する。データベース２（５２１−２）は参照情報３０−３と３０−４を記憶する。データベースｎ（５２１−ｎ）は参照情報３０−５と３０−６を記憶する。参照情報３０−１と３０−４と３０−５は、転送処理においてソースアドレスの処理時に参照する参照情報である。参照情報３０−２と３０−３と３０−６は、転送処理においてデスティネーションアドレスの処理時に参照する参照情報である。
【００３０】
データベース１（５２１−１）〜データベースｎ（５２１−ｎ）が記憶する参照情報３０は、データベース参照フォワーディング部１５によって一度読み取られると、一つのパケットの転送に使用した参照情報ごとに一つのキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に書き込まれる。図示する例では、参照情報３０−１と、３０−４と、３０−５は、一つのパケットの転送処理においてソースアドレスの処理時に参照される参照情報であるため、ｔ個のキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）のうちの一つであるキャッシュブロック４（２１０−４）に書き込まれる。また、参照情報３０−２と、３０−３と、３０−６は、一つのパケットの転送処理においてデスティネーションアドレスの処理時に参照される参照情報であるため、ｔ個のキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）のうちの一つであるキャッシュブロックｔ−１（２１０−ｔ−１）に書き込まれる。
【００３１】
次に、パケット転送装置の動作手順について図６および図７を参照して説明する。図６および図７はパケット転送装置の動作手順について示したフローチャートである。はじめにフィールド抽出部１１は入出力ポート３より入力されたパケットよりフォワーディングに関連するフィールドを抽出する（ステップＳ１０１）。インデックス計算部１２はステップＳ１０１で抽出したフィールドの値から所定のハッシュ関数を用いてハッシュ値（１）を計算する（ステップＳ１０２）。インデックス計算部１２はステップＳ１０２で計算したハッシュ値（１）に基づいてインデックスを計算し、インデックスに基づいてキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）を特定する。検証情報格納部１３は、インデックス計算部１２が特定したキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に検証情報が存在するか否か検索する（ステップＳ１０３）。検証情報格納部１３はステップＳ１０３で特定したキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に検証情報が存在するか否か判断し（ステップＳ１０４）、検証情報（２）が存在する場合はステップＳ１０５に進み、存在しない場合はステップＳ１０８に進む。
【００３２】
ステップＳ１０５では、検証部１４はステップＳ１０４で存在した検証情報と、ステップＳ１０２で抽出したフィールド（検証情報）とに基づいて、検索した検証情報が含まれるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報が転送対象のパケットに対して有効か否か確認する（ステップＳ１０５）。ステップＳ１０５でキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報が有効と判断した場合はステップＳ１０７に進み、無効と判断した場合はステップＳ１０８に進む（ステップＳ１０６）。ステップＳ１０７では、キャッシュ参照フォワーディング部１６は、ステップＳ１０３で特定したキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に含まれる情報のうち、処理情報（３）に基づいて転送対象のパケットを加工し、処理情報（３）に記録された出力ポートに、処理情報（３）に記録されたパラメータで転送対象のパケットの送出制御を行い（ステップＳ１０７）、処理を終了する。
【００３３】
一方、ステップＳ１０８では、検証情報格納部１３は新たなキャッシュブロック（４）であるキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）を確保する（ステップＳ１０８）。データベース参照フォワーディング部１５は、転送対象のパケットのヘッダ部を解析し、解析した情報に基づいてデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）より参照情報を読み取り、参照情報に基づいてパケットを加工し、加工したパケットを送信パケット２１として出力ポートに送出する。また、データベース参照フォワーディング部１５はこの過程で読み取った複数の参照情報を一つにまとめて、一つの処理情報としてステップＳ１０８で確保したキャッシュブロック（４）に記憶させる（ステップＳ１０９）。データベース参照フォワーディング部１５は、ステップＳ１０９で処理情報を記憶させたキャッシュブロック（４）を、ステップＳ１０２で計算したハッシュ値（１）に基づいてステップＳ１０３で計算したインデックスで登録し（ステップＳ１１０）、処理を終了する。
【００３４】
上述したとおり、フォワーディング部１７は、初めて転送するパケットについては、パケットの転送に必要な複数の参照情報をデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）より読み取り、読み取った情報に基づいてパケットを転送するが、その際に読み取った複数の参照情報を一つにまとめ、一つの処理情報としてキャッシュブロックに記憶させ、再度同じ特徴を持ったパケットの転送処理の際には、一つのキャッシュブロックが記憶する処理情報に基づいて転送処理を行う。
【００３５】
データベースとキャッシュブロックはＲＡＭ上に記憶されており、同一アクセス速度でＣＰＵが直接アクセスすることができる同一のアドレス空間に存在する。ただし、各キャッシュブロックはＲＡＭ上にアドレスが連続するように記憶されている。同一の内容を読み取る場合、一つのキャッシュブロックからの連続した読み込みは、複数のデータベースからの読み込みよりも速い。これは以下の要因などによる。
【００３６】
ＣＰＵ内部キャッシュを備えたＣＰＵは、パケット転送処理を行う上で最初に使用するデータをＲＡＭ上から読み込むと、そのデータのアドレスに隣接したアドレスで指定されるデータをＣＰＵ内部キャッシュのラインサイズ単位でまとめてＣＰＵ内部キャッシュに格納する。本実施形態で、パケット転送処理に必要なデータをキャッシュブロックから読み込む場合には、目的とするデータがＲＡＭ上の所定の範囲内（例えば、ＣＰＵ内部キャッシュのラインサイズに対応する範囲内）にかたまって存在しているため、次に使用するデータは最初に使用するデータと一緒にＣＰＵ内部キャッシュに格納される確率が高い。従って、パケット転送処理に必要なデータがＲＡＭ上の連続したアドレスで指定される領域に記録されていないとき、すなわちアドレスの分散している複数のデータベースからデータを読み込む場合と比較すると、一つのキャッシュブロックからデータを読み込むほうが読み込み速度は速くなる。
なお、ＣＰＵ内部キャッシュのラインサイズとキャッシュブロックのサイズが一致する場合はさらに読み込みが速くなる。例えば、ＣＰＵ内部キャッシュのラインサイズが１２８バイトで、キャッシュブロックのサイズが１２８バイトであって、且つアドレス上の所定の境界内に一つのキャッシュブロックが収まるようにキャッシュブロックを配置させることにより、一つのキャッシュブロックのデータがＣＰＵ内部キャッシュに全て記憶されるため、さらに読み込みが速くなる。
【００３７】
また、ＲＡＭ上の連続したアドレスで指定される領域に記憶されているデータは、バースト転送により高速なデータ転送を行うことができる。バースト転送では、ＣＰＵは最初に読み取り先のアドレス情報をＲＡＭに対して一回だけ送信する。その後、送信したアドレス付近のデータがＲＡＭからＣＰＵに連続して転送される。よって一回のデータ転送ごとに一回ずつアドレス情報を送信する方法と比べると、バースト転送ではアドレス情報の送信にかかる時間を大幅に減らすことができる。そのため、ＣＰＵがＲＡＭ上から連続したアドレスに記憶されるデータ、すなわち一つのキャッシュブロックに記憶されるデータを連続して読み取る際にはバースト転送が効果を発揮するため、連続していないアドレスに記憶されるデータ、すなわち複数のデータベースに存在しているデータを読み取る場合に比べて参照情報を速く読み出せる。
【００３８】
上述したとおり、本発明を利用したパケット転送処理と、利用していないパケット転送処理とを比較すると、本発明を利用したパケット転送処理では、参照データを高速に読み出すことができる。その結果、従来、パケット転送処理のボトルネックとなっていた参照情報の読み出しが速くなり、パケット転送処理も速くなる。
【００３９】
次に、上述したパケット転送装置におけるデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリが持つカウンタの管理手法について図を参照して説明する。図８は本実施形態におけるカウンタの管理手法について説明したブロック図である。上述したパケット転送装置は、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリが持つカウンタを管理する手段として、以下に述べるカウンタ情報更新部を有している。
【００４０】
パケットのフォワーディング処理では、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）を参照するだけではなく、フォワーディングしたパケットに関する統計情報を記録する必要がある。統計情報（カウンタ）はフォワーディング処理でデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）を参照した際に、参照されたデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のいずれかのエントリに記録される。エントリはデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）内に複数存在し、図示する例ではデータベース１（５２１−１）のエントリ数はｍ1個、データベース２（５２１−２）のエントリ数はｍ2個である。また、エントリの各々はカウンタ（第一の統計情報）を持つ。しかし、本実施形態では、参照情報が処理情報に含まれた状態でキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に記憶されている場合、フォワーディング処理はキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報に基づいて行われるため、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリにアクセスすることなくフォワーディング処理が実施される。そのため、カウンタ管理方法を考慮しなければデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリに統計情報を記録することが出来ない。
【００４１】
本発明でのカウンタ管理方法は以下の通りである。キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の各々はカウンタ（第二の統計情報）を持つ。キャッシュ参照フォワーディング部１６は、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報に基づいてパケットのフォワーディング処理を実施した場合、アクセスしたキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）のカウンタをカウントアップする。図示する例では、キャッシュ参照フォワーディング部１６がパケットＡのフォワーディング処理を行う場合、キャッシュブロック１の処理情報を読み取る。その時にキャッシュ参照フォワーディング部１６は参照したキャッシュブロック１（２１０−１）のカウンタをカウントアップする。パケットＢのフォワーディング処理の場合についても同様である。
【００４２】
一方、カウンタ情報更新部は周期処理でキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の第二の統計情報を読み取り、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）が記憶する処理情報に含まれた参照情報を記憶する、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリの第一の統計情報に、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の第二の統計情報を加え、その後キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の第二の統計情報をクリアする。また、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）が削除される場合においても同様の処理を行い、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）が記憶する第二の統計情報をエントリの第一の統計情報に加える。
【００４３】
上述したとおり、本実施形態によれば、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリにアクセスすることなくフォワーディング処理が実施される場合においても、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリに統計情報を記録することができる。
【００４４】
次に、上述したパケット転送装置におけるデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）の各エントリが持つエージング情報（第一のエージング情報、第一の有効時刻）の更新方法について図を参照して説明する。図９は本実施形態におけるエージング処理方法について説明したブロック図である。上述したパケット転送装置は、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリの有効性を管理する手段として、以下に述べるエージング情報更新部を有している。また、キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の各々は第二のエージング情報を持つ。
【００４５】
パケット転送装置は、動的に収集されるデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリに関して、そのエントリの有効性をエージングという処理で管理する場合がある。この処理は、パケットの転送処理時にそのパケットによって特定のデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリが有効であることが確認された場合、その確認された時刻をデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリに記録し、一定時間内に有効であることが確認されなかった場合、そのデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリを自動的に削除する処理である。
【００４６】
しかし、本実施形態では、参照情報が処理情報に含まれた状態でキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）に記憶されている場合、フォワーディング処理はキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報に基づいて行われるため、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリにアクセスすることなくフォワーディング処理が実施される。そのため、有効であると確認された場合においても確認された時刻をデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリに記録することが出来ないため、有効であるデータベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリについても自動的に削除されてしまう。
【００４７】
本発明でのエージング処理は以下の通りである。キャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の情報に基づいてキャッシュ参照フォワーディング部１６がパケットのフォワーディング処理を実施した場合、キャッシュ参照フォワーディング部１６はアクセスしたキャッシュブロック１（２１０−１）〜キャッシュブロックｔ（２１０−ｔ）の第二の有効時刻（第二のエージング情報）に、キャッシュブロックを参照した時刻を記録する。図示する例では、キャッシュ参照フォワーディング部１６がパケットＡのフォワーディング処理を行う場合、キャッシュ参照フォワーディング部１６はキャッシュブロック１（２１０−１）の第二の処理情報を読み取る。その時にキャッシュ参照フォワーディング部１６は、キャッシュブロック１を参照した際に内部時計から取得した現在時刻を、キャッシュブロック１（２１０−１）の第二の有効時刻に記録する。パケットＢのフォワーディング処理についても、キャッシュ参照フォワーディング部１６は、パケットＡについてと同様の処理を行う。
【００４８】
一方、エージング情報更新部は、周期処理でキャッシュブロック１（２１０−１）の第二の有効時刻を読み取り、第二の有効時刻とキャッシュブロック１（２１０−１）に関連するエントリが有する第一の有効時刻とを比較する。第二の有効時刻の方が新しければ、エージング情報更新部は第一の有効時刻を第二の有効時刻の値に書き換える。その後エージング情報更新部はキャッシュブロック１（２１０−１）の第二の有効時刻をクリアする。キャッシュブロック２（２１０−２）〜キャッシュブロックｔ（２１０−ｔ）についても、エージング情報更新部は、キャッシュブロック１についてと同様の処理を行う。
【００４９】
上述したとおり、本実施形態によれば、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエントリにアクセスすることなくフォワーディング処理が実施される場合においても、データベース１（５２１−１）〜データベースｎ（５２１−ｎ）のエージング処理を行うことができる。
【００５０】
次に、上述したパケット転送装置におけるデータベースのエントリおよびキャッシュ（ｃａｃｈｅ）のエントリの情報を管理し維持する手法について説明する。上述したパケット転送装置は、データベースのエントリおよびキャッシュのエントリを管理する手段として、以下に述べる情報管理装置を有している。
【００５１】
図１０は、本実施形態による情報管理装置のハードウェア構成を示す概略ブロック図である。図示するように、この情報管理装置５０１は、ＣＰＵ（中央処理装置、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０２と、半導体ＲＡＭ（半導体により構成される読み書き可能なランダムアクセスメモリ）５０３と、バス５０４を含んで構成される。ＣＰＵ・５０２と半導体ＲＡＭ・５０３とはそれぞれバス５０４に接続されており、ＣＰＵ・５０２からはバス５０４を介して半導体ＲＡＭ・５０３からデータを読み出したり、半導体ＲＡＭ・５０３にデータを書き込んだりすることができるようになっている。バス５０４には、他の構成要素も接続されているが、ここでは記載を省略する。半導体ＲＡＭ・５０３の内部には、実行形式のコンピュータプログラムコードが記憶されている領域と処理対象のデータが記憶されている領域が含まれる。ＣＰＵ・５０２は、内部に有するプログラムカウンタの値に基づいて適宜、半導体ＲＡＭ・５０３の所定のアドレスからプログラムコードを読み出して実行する。このようなコンピュータプログラムを用いることにより、以下に述べる情報管理の機能が実現される。
【００５２】
図１１は、情報管理装置５０１の機能構成を示す概略機能ブロック図である。図示するように、情報管理装置５０１は、内部に、関連性有効化処理部５１１と、関連性無効化処理部５１２と、ガーベジ収集処理部５１３と、記憶部５１４を含んで構成される。記憶部５１４は、データを記憶する機能を有しており、上記の半導体ＲＡＭ・５０３によって実現される。関連性有効化処理部５１１や関連性無効化処理部５１２やガーベジ収集処理部５１３は、上記のＣＰＵ・５０２がコンピュータプログラムを実行することにより実現される。
【００５３】
関連性有効化処理部５１１（関連性有効化処理過程）は、データベースエントリ（情報エントリ）に関連するキャッシュブロック（関連情報エントリ）を有効にする際に、当該データベースエントリ（情報エントリ）と当該キャッシュブロック（関連情報エントリ）との間に関連があることを表わすキャッシュブロックポインタ（関連性情報）を含んだオブジェクト（関連オブジェクト）を生成するとともに、当該キャッシュブロック（関連情報エントリ）の世代番号（５２２−１、世代情報）と同一の世代情報を当該オブジェクト（関連オブジェクト）の世代番号（５２７−１、世代情報）として書き込む処理を行なう機能を有するものである。
関連性無効化処理部５１２（関連性無効化処理過程）は、データベースエントリ（情報エントリ）のいずれかが変更されたときに、変更された当該データベースエントリ（情報エントリ）に関連するキャッシュブロック（関連情報エントリ）を無効にする処理をするとともに、当該キャッシュブロック（関連情報エントリ）の世代番号（５２２−１、世代情報）を更新する処理を行なう機能を有するものである。
ガーベジ収集処理部５１３（ガーベジ収集処理過程）は、オブジェクト（関連オブジェクト）が有する世代番号（５２７−１、世代情報）と、当該オブジェクト（関連オブジェクト）に対応するキャッシュブロック（関連情報エントリ）が有する世代番号（５２２−１、世代情報）とを比較し、この比較結果に応じて当該オブジェクト（関連オブジェクト）を回収する（つまり、不要となっているオブジェクトを収集（回収）する機能を有するものである。
【００５４】
次に、情報管理装置５０１が管理の対象とするデータの構成および構造について説明する。図１２は、情報管理装置５０１が管理するデータ構造の一例を概念的に表わす概略図である。この図は、データ構造を単に概念的に表わしているに過ぎず、実際の、本実施形態の情報管理装置５０１における物理的なデータ構造については後述する。図１２において、符号５２１−１、５２１−２、・・・、５２１−ｎは、ｎ個のデータベース（第１記憶部）である。また、符号５２２は、キャッシュブロック群（第２記憶部）である。データベース１（５２１−１）は、エントリ１からエントリｍ1までのｍ1個のデータエントリ（情報エントリ）を有している。データベース２（５２１−２）は、エントリ１からエントリｍ2までのｍ2個のデータエントリを有している。以下、同様に続き、データベースｎ（５２１−ｎ）は、エントリ１からエントリｍnまでのｍn個のデータエントリを有している。一方、キャッシュブロック群５２２は、キャッシュブロック１からキャッシュブロックｔまでのｔ個のキャッシュブロック（関連情報エントリ）を有している。図中の矢印線は、それぞれ、データベースのエントリからキャッシュブロックへの関連を表わすものである。図示する例では、例えば、データベース１（５２１−１）のエントリ２は、キャッシュブロック２、キャッシュブロック３、キャッシュブロックｔに関連する。また、データベース２（５２１−２）のエントリ２は、キャッシュブロック２に関連する。また、データベース２（５２１−２）のエントリｍ2は、キャッシュブロック１に関連する。また、データベースｎ（５２１−ｎ）のエントリ２は、キャッシュブロックｔに関連する。また、データベースｎ（５２１−ｎ）のエントリｍnは、キャッシュブロック３に関連する。
【００５５】
図１２に示した例のように、あるデータベースエントリが複数のキャッシュブロックに関連する場合がある。また、複数のデータベースエントリが、ひとつのキャッシュブロックに関連する場合がある。つまり、データベースエントリとキャッシュブロックとの関連は、多対多（図示する例では、（ｍ1＋ｍ2＋・・・＋ｍn）対ｔ）の関係にある。
【００５６】
ところで、前述の通り、本実施形態では、データベース（５２１−１〜５２１−ｎ）は、パケット転送装置がパケット転送する際に参照する必要のある各種データを保持している。また、あるパケットを転送する際に必要となる情報が各データベースにばらばらに分散して存在しているとそれらのデータを読み出すのに時間がかかるため、各々のキャッシュブロックは、あるパケットを転送する際に必要となる情報をまとめて局所的な場所に保持しておくためのものである。
つまり、パケット転送装置を運用するとき、データベースエントリは、オペレータによる設定操作の結果として、あるいはルーティングプロトコルのやりとりの結果として、あるいはブリッジのＦＤＢ学習の結果として、変更されることがある。
【００５７】
データベースエントリが変更されると、そのデータベースエントリに対応する、変更前の値を保持するキャッシュブロックは、値の不整合が起こってしまうのを避けるために、削除するないしは無効にするなど、参照されないようにする必要がある。上記の通り、あるキャッシュブロックは、複数のデータベースエントリから抽出した情報から構成される。また上記の通り、あるデータベースエントリは、複数のキャッシュブロックに関連している。これは、あるキャッシュブロック、複数のデータベースエントリに依存していると言い換えることもできる。つまり、データベースエントリとキャッシュブロックの間には、多対多の依存関係がある。
【００５８】
次に、情報管理装置５０１が管理するデータの具体的な構造について、図１３、図１４、図１５を参照しながら説明する。
【００５９】
図１３は、データベースとキャッシュブロックとの間の関連付けを表わすデータ構造を示した概略図である。この図において、データベース１（５２１−１、第１記憶部）はｍ1個のエントリ（情報エントリ）を有し、キャッシュブロック群５２２（第２記憶部）はｔ個のエントリ（関連情報エントリ）を有している。また、符号５２６はオブジェクトハッシュであり、このオブジェクトハッシュ５２６はスロット１からスロットｘまでのｘ個のスロットを有している。データベース１（５２１−１）のエントリは、オブジェクトハッシュ５２６のスロットに関連付けられる。この関連付けの方法としては、様々な方法が考えられるが、例えば、データベース１（５２１−１）のエントリに固有な値（当該エントリが存在するアドレスや、当該エントリのデータのキー値など）を基に所定の関数（ハッシュ関数など）の計算を行なうことによりスロット１からスロットｘまでのいずれかのスロットに関連付ける方法がある。また、ハッシュ関数を用いた場合、データベース１（５２１−１）の複数のエントリに対応するハッシュ値が同一になってしまう場合もあるが、これを解決するためには例えば、一つのハッシュ値に対して複数のスロットを割り当てて適宜使用する方法がある。
【００６０】
符号５２７はオブジェクト（関連オブジェクト）であり、このオブジェクト５２７は、一つのスロットから複数のキャッシュブロックへの関連付けを行なうための構造体である。オブジェクト５２７は、メモリ上のオブジェクト記憶部（関連オブジェクト記憶部）に記憶される。オブジェクトハッシュ５２６内の各スロットは、一つのオブジェクト５２７へのポインタを有している。また、一つのオブジェクト５２７は、一つのキャッシュブロックへのポインタと、次の一つのオブジェクト５２７へのポインタを有している。つまり、一つのスロットのポインタは、複数のオブジェクト５２７からなるリストの先頭を指し示す。このリストの終端のオブジェクト５２７においては、次のオブジェクトへのポインタは「ヌル（ｎｕｌｌ）」にセットされている。また、このリストに属する各オブジェクト５２７は、それぞれ一つのキャッシュブロックを指し示している。つまり、一つのスロットから複数のキャッシュブロックへの関連付けが行なわれている。
【００６１】
図１４は、オブジェクト５２７の内部データ構造を示す概略図である。図示するように、オブジェクト５２７は、世代番号５２７−１（関連性情報に対応する世代を表わす世代情報）と、キャッシュブロックポインタ５２７−２（関連性情報）と、次のオブジェクトポインタ５２７−３とを含んで構成される。世代番号５２７−１は、このオブジェクト５２７およびこのオブジェクト５２７から指し示されるキャッシュブロックの更新の世代を管理するためのものであり、関連性有効化処理部５１１（図１１）や関連性無効化処理部５１２（図１１）によって更新される。世代番号５２７−１の使い方の詳細は、後述する。キャッシュブロックポインタ５２７−２は、前述の通り一つのキャッシュブロックを指し示すためのポインタである。つまり、キャッシュブロックポインタ５２７−２は、データベースエントリとキャッシュブロックとの間の関連を表わす。次のオブジェクトポインタ５２７−３は、前述の通り、リンクリスト上の次のオブジェクト５２７を指し示すためのポインタである。
【００６２】
図１５は、一つのキャッシュブロックの内部データ構造を示す概略図である。図示するように、キャッシュブロックは、世代番号５２２−１（関連情報エントリに対応する世代を表わす世代情報）と、有効／無効５２２−２と、検証情報５２２−３と、処理情報５２２−４とを含んで構成される。世代番号５２２−１は、キャッシュブロックの更新の世代を管理するためのものであり、前述の世代番号５２７−１とともに使用される。世代番号５２２−１の使い方の詳細は、後述する。有効／無効５２２−２は、現在、当該キャッシュブロックが有効な情報を有するエントリであるか否かを表わすフラグである。そのフラグの値は適宜設計により決めれば良いが、例えば「１」が有効を表わし、「０」が無効を表わすようにする。検証情報５２２−３は、例えば、当該キャッシュブロックに対応するキー値（複数のデータベースの複合キー値でも良い）を格納する。この検証情報５２２−３は、当該キャッシュブロックを参照する際のキー値の検証のために用いられる。処理情報５２２−４は、上記キー値に対応する情報であり、パケット転送装置が当該キー値に対応するパケットを転送する処理を行なう際に参照する情報である。この処理情報５２２−４は、複数のデータベース（５２１−１、５２１−２、・・・、５２１−ｎ）に分散している情報を高速に参照できるように一箇所にまとめて保持するための領域である。
【００６３】
次に、上で述べたデータ構造を用いた処理について、図１６、図１７、図１８を参照しながら説明する。
【００６４】
図１６は、情報管理装置５０１の関連性有効化処理部５１１（図１１）がデータベースのエントリに対応するキャッシュブロックについて、それら両者間を関連付けて登録する処理の手順を示すフローチャートである。つまり、依存関係を登録する処理の手順を示すフローチャートである。なおこの際、データベースのエントリから関連付ける先のキャッシュブロックについて、情報管理装置５０１は、検証情報５２２−３に適切なデータを格納し、処理情報５２２−４に適切なデータを格納し、有効／無効５２２−２のフラグが「有効」を表わすように設定し、世代番号５２２−１に適切な世代番号を格納する処理も適宜行なっている。ここで、世代番号は、例えば、一つのキャッシュブロックを有効にする都度、また無効にする都度、インクリメントしていくような数値を用いる。
データベースを検索してキャッシュブロックに検証情報と処理情報を記録する処理の例は、図６、図７のフローチャート（特に、ステップＳ１０９）に示した通りである。
【００６５】
図１６のフローチャートに沿って、関連性有効化処理部５１１は、まず、ステップＳ７０１において、登録すべきデータベースのエントリに固有な値として、当該エントリのメモリ上のアドレス値を用いて、この固有値に基づくハッシュ関数の計算を行ない、得られたハッシュ値により、使用する特定のスロットを決定する（つまり、スロットを計算する）。
次に、ステップＳ７０２において、関連性有効化処理部５１１は、依存関係を保持するための、つまりデータベースのエントリとキャッシュブロックとの関連付け情報を保持するための構造体であるオブジェクト５２７を一つ生成する。つまり、一つのオブジェクト５２７のためのメモリ上の領域を確保する。
【００６６】
次に、ステップＳ７０３において、関連性有効化処理部５１１は、関連付ける先のキャッシュブロックの世代番号５２２−１に格納されている世代番号の値を、上で生成したオブジェクト５２７の世代番号５２７−１の領域に格納する。これにより、これらオブジェクト５２７と対応するキャッシュブロックとは、同一の世代番号を保持することになる。
次に、ステップＳ７０４において、関連性有効化処理部５１１は、ステップＳ７０２で生成したオブジェクト５２７を、ステップＳ７０１で計算されたスロットに挿入する。つまり、ステップＳ７０１で計算されたスロットが指し示す、複数のオブジェクト５２７からなるリンクリストの先頭又は最後に、ステップＳ７０２で生成したオブジェクト５２７を挿入する。これは、このリンクリスト上のオベジェクト５２７の次のオブジェクトポインタ５２７−３を更新することにより行なう。なお、当該スロットが指し示すリンクリストが元々ヌル（オブジェクトが一つもない）であった場合には、ステップＳ７０２で生成したオブジェクト５２７のみからなるリンクリストを当該スロットが指し示すようにすれば良い。そして、関連性有効化処理部は、ステップＳ７０２で生成したオブジェクト５２７のキャッシュブロックポインタ５２７−２に、該当するキャッシュブロックのアドレスを格納する。
以上の一連の処理により、データベースのエントリと、対応するキャッシュブロックとの関連付けが登録される。
【００６７】
情報管理装置５０１は、キャッシュブロックの検証情報５２２−３や処理情報５２２−４を生成するために使ったデータベースのエントリ、つまり当該キャッシュブロックを関連付けているエントリが変更されたり削除されたりした場合には、登録されている依存関係（関連付け情報）に基づいて、変更又は削除されたデータベースのエントリに関連する（対応する）キャッシュブロックを無効にする処理を行なう。
【００６８】
図１７は、上記の、キャッシュブロックを無効にする処理の手順を示すフローチャートである。このフローチャートに沿って説明すると、関連性無効化処理部５１２（図１１）は、ステップＳ７１１において、変更（又は削除）されたデータベースのエントリに固有な値（例えば、当該エントリのメモリ上のアドレス値）を基にハッシュ関数による計算を行ない、得られたハッシュ値に基づいてスロットを特定する（つまり、スロットを計算する）。ここで特定されるスロットは、図１６のフローチャート（関連性有効化処理）のステップＳ７０１で決定されたスロットと同じになるはずである。
【００６９】
次に、関連性無効化処理部５１２は、ステップＳ７１２において、ステップＳ７１１で特定されたスロットが指し示すオブジェクト５２７のリンクリストをたどり、連結されているすべてのオブジェクト５２７それぞれについて、キャッシュブロックポインタ５２７−２が指し示すキャッシュブロックを無効にする（つまり、当該キャッシュブロックの有効／無効５２２−２のフラグを「無効」を表わす値にセットする）。そして、当該キャッシュブロックの世代番号５２２−１を更新する（例えばインクリメントする）。そして、上記の特定されたスロットが指し示すオブジェクト５２７のリンクリストに含まれる全てのオブジェクトを回収する。ここで、オブジェクトを回収するとは、つまりそのオブジェクトの領域を解放し、当該特定されたスロットに付随するリンクリストへのポインタの値を「ヌル」にセットすることである。
【００７０】
上記の、関連性無効化処理部５１２による処理（ステップＳ７１１、Ｓ７１２）により、特定のデータベースエントリの変更に対応して、その変更されたエントリに固有の値から計算されたスロットに継っているすべてのオブジェクト５２７をたどって、対応するキャッシュブロックを無効にすることができた。しかしながら、データベースエントリとキャッシュとは多対多に対応しており、上記処理で無効にしたキャッシュブロックを他のデータベースエントリに対応するオブジェクト５２７が指したままの状態で残っていることがある。
【００７１】
このような状態が放置されると、回収されないオブジェクト５２７がメモリの領域を占めることにより、メモリ領域が枯渇してしまうという問題が生じる。また、上記のような状態が放置されると、他のデータベースエントリから、オブジェクト５２７を経由して、キャッシュブロックの有効／無効５２２−２の領域や検証情報５２２−３の領域を参照して初めてそのキャッシュブロックが無効であることがわかるため、ポインタをたどる処理が無駄になるという問題も生じる。
【００７２】
そこで、情報管理装置５０１のガーベジ収集処理部５１３（図１１）は、所定のタイミングで（例えば周期的に）、オブジェクトハッシュ５２６のすべてのブロックを検査することにより、既に無効化されてしまったキャッシュブロックを指しているオブジェクト５２７（ガーベジ、ｇａｒｂａｇｅ、ゴミデータ）を回収する処理を行なう。あるオブジェクト５２７がガーベジであるか否か、つまり既に削除されたキャッシュブロックを指すオブジェクト５２７であるか否かは、キャッシュブロック内の世代番号５２２−１とオブジェクト５２７内の世代番号５２７−１を比較することにより行なえる。両者の世代番号が異なっていれば、キャッシュブロックは既に無効化されているか、あるいは一旦無効化された後に他のデータのために再度有効化されている状態であるので、そのようなオブジェクト５２７はガーベジであるとして収集する。両者の世代番号が同じであれば、キャッシュブロックは有効な状態であるので、そのようなオブジェクト５２７を回収対象とはしない。
【００７３】
図１８は、ガーベジ収集処理部５１３が、無効となったキャッシュブロックをポイントしているオブジェクト５２７を回収する処理例を説明するための概略データ構造図である。図示する例では、データベース１（５２１−１）のエントリ２が変更される。この変更処理に付随して、関連性無効化処理部５１２（図１１）が、エントリ２に固有な情報（当該エントリのメモリ上のアドレス）を基に、ハッシュ関数を用いて、スロットのインデックス値を計算する。そして、このインデックス値が指す場所のスロットを特定する（以上、図１７のステップＳ７１１）。図示する例では、オブジェクトハッシュ５２６内のスロット３が特定されたスロットである。そして、関連性無効化処理部５１２は、スロット３に接続されているオブジェクト５２７のリストをたどって、オブジェクト（Ｂ）を削除（回収）するとともにこれに対応するキャッシュブロック２を無効にし、またオブジェクト（Ｃ）を削除（回収）するとともにこれに対応するキャッシュブロック１を無効にする。このとき、無効化されたキャッシュブロック２および１の世代番号は、それぞれ更新（例えば、インクリメント）される（以上、図１７のステップＳ７１２）。
【００７４】
既に述べているようにデータベースエントリとキャッシュブロックの依存関係（関連付け）は多対多であるため、キャッシュブロック２および１が無効になったときにも、この状態では、キャッシュブロック２を指し示すオブジェクト（Ａ）は回収されないまま残ってしまっている。
【００７５】
ここで、ガーベジ収集部５１３は、所定の周期で、オブジェクトハッシュ５２６に含まれるすべてのスロットから、それらスロットにつながるすべてのオブジェクト５２７を検査する。その検査の結果、キャッシュブロックの世代番号５２２−１とオブジェクトの世代番号５２７−１が一致しないようなオブジェクトをすべて回収する。図示する例では、ガーベジ収集部５１３がオブジェクト（Ａ）を収集する。なお、オブジェクト（Ａ）が収集される前にはスロット１に付随するポインタにはオブジェクト（Ａ）へのポインタ値が格納されていたが、ガーベジ収集部５１３は、オブジェクト（Ａ）を収集する際には、スロット１に付随するポインタにオブジェクト（Ａ）の次のオブジェクトへのポインタの値を記録しなおす。
上記のように、世代番号を用いた管理を行なうため、ガーベジ収集部５１３が走る前にキャッシュブロック１やキャッシュブロック２が再び有効な状態になっていても、正しく、不要なオブジェクトのみを回収することができる。
【００７６】
なお、ガーベジ収集処理は、例えば、一定周期で実行するなど、適宜所定のタイミングで実行するようにすれば良いが、例えば、空きメモリ容量を監視する監視部を設けて、空きメモリ容量の監視結果に応じて（例えば、空きメモリ容量が所定の閾値を下回った場合などに）ガーベジ収集処理を実行するようにしても良い。また、例えば、監視部がＣＰＵ負荷を監視し、ＣＰＵ負荷の低い時間帯にガーベジ収集処理を実行するようにしても良い。
【００７７】
また、上では、データベースエントリとキャッシュブロックとの関係が多対多の場合について説明したが、これが、多対１となるようなデータについても、本実施形態を有効に適用することができる。また、上では、データベースの個数がｎ個の場合について説明したが、ｎは１以上の整数であれば良い。つまり、データベースの個数が１であっても、本実施形態を有効に適用できる。また、各データベースのエントリ数は任意であり、また各データベースのエントリ数が可変であっても良い。また、キャッシュブロックのエントリ数も任意であり、またこれが可変であっても良い。
【００７８】
なお、上述した実施形態におけるパケット転送装置や情報管理装置の一部、例えば、関連性有効化処理部５１１、関連性無効化処理部５１２、ガーベジ収集処理部５１３などの機能をコンピュータで実現する。この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００７９】
以上、本発明の実施形態を説明したが、本発明はさらに次のような形態でも実施することが可能である。
上記実施形態では、情報管理装置の機能をコンピュータシステムとプログラムとで実現したが、これをハードウェアによる組合せ回路および順序回路を用いて同等の機能を実現するようにしても良い。
上記実施形態では、図１３などに示したように、オブジェクトハッシュ５２６を設け、このオブジェクトハッシュ５２６を経由してデータベースからキャッシュブロックへの関連付けを表わすデータ構造としたが、オブジェクトハッシュを設けない構成を有する形態にも、本発明を有効に適用することができる。オブジェクトハッシュを設けない場合には、各データベースのエントリから、ポインタ等を用いて、直接的あるいは間接的にオブジェクト５２７のリンクリストを指し示すようにして、データベースエントリとキャッシュブロックとの関連付け（依存）を表わすデータとすれば良い。
上記実施形態では、世代情報として、世代番号を用いたが、この代わりに例えばタイムスタンプ等を用いても良い。世代番号およびタイムスタンプのいずれもが、キャッシュブロックが有効になったタイミングや無効になったタイミングを表わすという点で同様の作用を与える。
【００８０】
上記実施形態では、記憶部５１４（図１１）を半導体ＲＡＭによって実現することとしたが、この代わりにその全部又は一部を、例えば、磁気ハードディスク装置や、フラッシュメモリ装置や、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒなど）読み書き装置や、光磁気ディスク（ＭＯ）読み書き装置などを用いて構成するようにしても良い。例えば、データベースを磁気ハードディスクを用いて実現し、オブジェクトハッシュ５２６やオブジェクト５２７やキャッシュブロック群５２２を半導体ＲＡＭを用いて実現するようにしても良い。
また、上では、情報管理装置を用いてパケット転送装置を構成した実施形態を説明したが、パケット転送装置に限らず、本発明の情報管理装置を他の様々な装置に応用することも可能である。いかなる装置に応用した場合も、本発明の情報管理装置、情報管理方法、コンピュータプログラムにより、データの関連性（依存性）を管理し、記憶手段（半導体メモリや、磁気ハードディスク装置など）を効率的且つ有効に使用することができる。
【００８１】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００８２】
【図１】本発明の一実施形態によるパケット転送装置を備えたスイッチの構成を示すブロック図である。
【図２】同実施形態によるパケット転送装置の構成を示す機能ブロック図である。
【図３】同実施形態によるデータベース参照フォワーディング部の動作を示したブロック図である。
【図４】同実施形態によるキャッシュ参照フォワーディング部の動作を示したブロック図である。
【図５】同実施形態によるデータベースが記憶する情報と、キャッシュ上のキャッシュブロックが記憶する情報との関連を示したブロック図である。
【図６】同実施形態によるパケット転送装置の動作手順について示したフローチャートである。
【図７】同実施形態によるパケット転送装置の動作手順について示したフローチャートである。
【図８】同実施形態によるカウンタの管理手法について示したブロック図である。
【図９】同実施形態によるエージング処理方法について示したブロック図である。
【図１０】本発明の実施形態による情報管理装置のハードウェア構成を示す概略ブロック図である。
【図１１】同実施形態による情報管理装置の機能構成を示す概略機能ブロック図である。
【図１２】同実施形態による情報管理装置が管理するデータ構造の一例を概念的に表わす概略図である。
【図１３】同実施形態による、データベースとキャッシュブロックとの間の関連付けを表わすデータ構造を示した概略図である。
【図１４】同実施形態によるオブジェクト５２７（関連オブジェクト）の内部データ構造を示す概略図である。
【図１５】同実施形態による、一つのキャッシュブロックの内部データ構造を示す概略図である。
【図１６】同実施形態による関連性有効化処理部が、データベースのエントリとキャッシュブロックとの間を関連付けて登録する処理の手順を示すフローチャートである。
【図１７】同実施形態による関連性無効化処理部が、キャッシュブロックを無効にする処理の手順を示すフローチャートである。
【図１８】同実施形態によるガーベジ収集処理部が不要なオブジェクト（関連オブジェクト）を収集する処理例を説明するための概略データ構造図である。
【符号の説明】
【００８３】
５０１  ：  情報管理装置
５１１  ：  関連性有効化処理部
５１２  ：  関連性無効化処理部
５１３  ：  ガーベジ収集処理部
５１４  ：  記憶部
５２１−１，５２１−２，・・・，５２１−ｎ  ：  データベース（第１記憶部）
５２２  ：  キャッシュブロック群（第２記憶部）
５２２−１  ：  世代番号（関連情報エントリに対応する世代を表わす世代情報）
５２７  ：  オブジェクト（関連オブジェクト）
５２７−１  ：  世代番号（関連性情報に対応する世代を表わす世代情報）
５２７−２  ：  キャッシュブロックポインタ（関連性情報）
【図１】
2009017440.tif 000003
【図２】
2009017440.tif 000004
【図３】
2009017440.tif 000005
【図４】
2009017440.tif 000006
【図５】
2009017440.tif 000007
【図６】
2009017440.tif 000008
【図７】
2009017440.tif 000009
【図８】
2009017440.tif 000010
【図９】
2009017440.tif 000011
【図１０】
2009017440.tif 000012
【図１１】
2009017440.tif 000013
【図１２】
2009017440.tif 000014
【図１３】
2009017440.tif 000015
【図１４】
2009017440.tif 000016
【図１５】
2009017440.tif 000017
【図１６】
2009017440.tif 000018
【図１７】
2009017440.tif 000019
【図１８】
2009017440.tif 000020