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