(57)【要約】本発明は、パケット・フロー転送によって動作するブロードバンド・ネットワークにおけるルータまたはスイッチに関する。そのルータは、少なくともハードウェア部(22)、中間部(24)およびソフトウェア部(26)に区分された相互フロー・テーブル(20)をフロー転送に用いて、階層的フロー転送(HFF)に従ってＣＰＵ切換えソフトウェア・フロー(12)とハードウェア切換え高速フロー(10)を提供する。テーブルは、定期的に所定の期間検査され、時間当たりのパケット数の比率に応じてソートされる。ハードウェア部(22,22a)は最高比率で満たし、中間部(24,22a,26a)は中間比率で満たし、ソフトウェア部(26)は最低比率で満たす。前回の検査で中間フロー(22a,26a)に適合したパケット・フローは、中間部(24)に依然として適合する場合は、そのメモリ空間に残る。それによって、テーブルの中間部内のメモリ空間(22a,26a)の間で交換が生じるのを防止し、ＣＰＵの負荷を軽減する。
2006505188.tif 000002
【特許請求の範囲】
【請求項１】
中央処理装置切換えソフトウェア・フロー（１２）およびハードウェア切換え高速フロー（１０）を含むパケット・フローを転送するよう動作する、ブロードバンド・ネットワークにおけるルータまたはスイッチであって、
ルータ出力ポートを介してパケットのフロー転送切換え（１０、１２）を行うハードウェア手段（ＨＷ１、ＨＷ２）およびソフトウェア手段と、
前記ハードウェア手段（ＨＷ１、ＨＷ２）に接続された制限された記憶容量を用いてハードウェア・フロー転送テーブルを格納するメモリ手段と、
中央処理装置手段（ＣＰＵ１、ＣＰＵ２）に接続され中央処理装置関連の記憶容量を用いて動作するソフトウェア・フロー転送テーブルを格納するメモリ手段と、
前記メモリ手段におけるフロー転送用のエントリのメモリ空間用の、少なくともハードウェア部指定領域（２２）、中間部指定領域（２４）およびソフトウェア部指定領域（２６）からなる相互テーブルの区分を有し、前記メモリ手段用のエントリ・リストを有する相互テーブル（２０）であって、前記中間部（２４）は所定の割当てのメモリ空間に前記両メモリ手段における利用可能なメモリ空間（２２ａ、２６ａ）を指定するものである、相互テーブル（２０）と、
或る時間期間によって定まる定期的ベースで前記相互テーブル（２０）を検査し、時間期間当たりのパケット数の比率に基づいてソートし、前記相互テーブル（２０）においてハードウェア部（２２、２２ａ）を最高の比率のもので、中間部（２４、２２ａ、２６ａ）を中間の比率のもので、およびソフトウェア部（２６）を最低の比率のもので満たし、前の検査において中間フロー（２４）として適合したパケット・フローが依然として前記中間部（２４）として適合する場合にはそれをそれのメモリ空間に残して、それによって前記テーブル（２０）の前記中間部（２４）内のメモリ空間指定領域（２２ａ、２６ａ）間で交換が生じるのを防止して前記中央処理装置の負荷を軽減させる手段と、
ハードウェア・フロー転送テーブルを格納する前記メモリ手段と、ソフトウェア・フロー転送テーブルを格納する前記メモリ手段とに、前記相互テーブル（２０）のエントリ・リストを格納する手段と、
を具える、ルータまたはスイッチ。
【請求項２】
前記相互テーブルには、テーブル（２０）から取り除くべきメモリ空間占有領域を指定する下部のフラッシュ部分（２８）が設けられていることを特徴とする、請求項１に記載のルータ。
【請求項３】
システム・コンフィギュレーションによってまたはその他の理由で常にハードウェア高速化されるべき（１０）所定の特定のフローが、パケット・ヘッダ情報を照合してハードウェア高速化されるべきものとして認識されるよう設定されることを特徴とする、請求項１または２に記載のルータ。
【請求項４】
各フロー・エントリがシステム・ルーティング・テーブルを用いて検査されて、フロー・エントリが生成されたときに用いられたルートとは異なる場所の宛先位置への新しいルートが存在するかどうかが判定されることを特徴とする、請求項１乃至３のいずれかに記載のルータ。
【請求項５】
宛先へのルートが変更された場合、フロー・エントリが消去されて、フロー中の次のパケットが出現したときそれが確実に再生成されるようにし、それによって、パケット・フィルタ、再優先度付与または類似の処理が新しいパケット・パスについて正しく処理されるようにできるようにすることを特徴とする、請求項４に記載のルータ。
【請求項６】
中央処理装置切換えソフトウェア・フロー（１２）およびハードウェア切換え高速フロー（１０）を含むパケット・フローを転送するよう動作する、ブロードバンド・ネットワークにおけるルータまたはスイッチに用いられる方法であって、
ルータ出力ポートを介してパケットのフロー転送切換え（１０、１２）を行うハードウェア手段（ＨＷ１、ＨＷ２）およびソフトウェア手段を設定するステップと、
前記ハードウェア手段（ＨＷ１、ＨＷ２）に接続された制限された記憶容量を用いてハードウェア・フロー転送テーブルを格納するメモリ手段を設定するステップと、
中央処理装置手段（ＣＰＵ１、ＣＰＵ２）に接続され中央処理装置関連の記憶容量を用いて動作するソフトウェア・フロー転送テーブルを格納するメモリ手段を設定するステップと、
前記メモリ手段におけるフロー転送用のエントリのメモリ空間用の、少なくともハードウェア部指定領域（２２）、中間部指定領域（２４）およびソフトウェア部指定領域（２６）からなる相互テーブルの区分を有し、前記メモリ手段用のエントリ・リストを有する相互テーブル（２０）であって、前記中間部（２４）は所定の割当てのメモリ空間に前記両メモリ手段における利用可能なメモリ空間（２２ａ、２６ａ）を指定するものである、相互テーブル（２０）を設定するステップと、
或る時間期間によって定まる定期的ベースで前記相互テーブル（２０）を検査し、時間期間当たりのパケット数の比率に基づいてソートし、前記相互テーブル（２０）においてハードウェア部（２２、２２ａ）を最高の比率のもので、中間部（２４、２２ａ、２６ａ）を中間の比率のもので、およびソフトウェア部（２６）を最低の比率のもので満たし、前の検査において中間フロー（２４）として適合したパケット・フローが依然として前記中間部（２４）として適合する場合にはそれをそれのメモリ空間に残して、それによって前記テーブル（２０）の前記中間部（２４）内のメモリ空間指定領域（２２ａ、２６ａ）間で交換が生じるのを防止して前記中央処理装置の負荷を軽減させるステップと、
ハードウェア・フロー転送テーブルを格納する前記メモリ手段と、ソフトウェア・フロー転送テーブルを格納する前記メモリ手段とに、前記相互テーブル（２０）のエントリ・リストを格納するステップと、
を含む方法。
【請求項７】
前記相互テーブルには、テーブル（２０）から取り除くべきメモリ空間占有領域を指定する下部のフラッシュ部分（２８）が設けられていることを特徴とする、請求項６に記載の方法。
【請求項８】
システム・コンフィギュレーションによってまたはその他の理由で常にハードウェア高速化されるべき（１０）所定の特定のフローが、パケット・ヘッダ情報を照合してハードウェア高速化されるべきものとして認識されるよう設定されることを特徴とする、請求項６または７に記載の方法。
【請求項９】
各フロー・エントリがシステム・ルーティング・テーブルを用いて検査されて、フロー・エントリが生成されたときに用いられたルートとは異なる場所の宛先位置への新しいルートが存在するかどうかが判定されることを特徴とする、請求項６乃至８のいずれかに記載の方法。
【請求項１０】
宛先へのルートが変更された場合、フロー・エントリが消去されて、フロー中の次のパケットが出現したときそれが確実に再生成されるようにし、それによって、パケット・フィルタ、再優先度付与または類似の処理が新しいパケット・パスについて正しく処理されるようにできるようにすることを特徴とする、請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＣＰＵ（中央処理装置）切換えソフトウェア・フローおよびハードウェア切換え高速化フローを含むパケット・フローの転送を行うことによって動作する、ブロードバンド・ネットワークにおけるルータまたはスイッチ、およびその方法に関する。
【背景技術】
【０００２】
特定のタイプのアクセス・スイッチング・ルータ（ＡＳＲ、アクセス切換えルータ）は、ブロードバンド・ネットワークにおけるパケット転送用のＡＳＩＣ（特定用途集積回路）、即ちハードウェア解決手段（solution）を利用する。ＡＳＩＣには、パケット・フロー用のハードウェア高速化転送テーブル・メモリにおけるエントリ数に関して制限がある。これは、有線速度パケット転送を維持しつつ複雑なネットワーク・トポロジ形成が可能なブロードバンド・ルータの設計における関心または懸念の主要な要因（原因）である。
【０００３】
例えばＢｒｏａｄｃｏｍ５６ｘｘ層スイッチ（strata-switch）転送ＡＳＩＣ用のドライバを設計するとき、全てのフィルタリング・ルールがＡＳＩＣに静的に（固定的に）組み込まれていた。１０２４のルールだけが使用されていたので、特にネットワークに高度のポリシー（方針）およびサービスを配備するとき、これは重大な制限となる。
【０００４】
古いバージョンのパケット転送では、ルータのＣＰＵがＲＡＭを介してその転送を制御していた。そのような解決手段は、ＣＰＵが常にルータの他のタスクに従事するので、相対的に低いパケット伝送速度で伝送を行い、ＣＰＵとして用途が広くない。
【０００５】
より新しい世代のフロー転送用ルータは、ＣＰＵに膨大な量の負荷をかけないようにするためにフロー転送の目的で特に設計されたＡＳＩＣによるハードウェア高速化フロー転送を導入した。これらのＡＳＩＣでも、例えばＷＷＷ（ワールドワイドウェブ）におけるフロー転送用の、例えば、ルータ、スイッチ、サーバ等のようなその他の主要な装置に対して１５万個ものアドレス・エントリを有するようなＣＡＭテーブル・リストを有するＣＡＭ（コンテンツ・アドレス可能メモリ、内容参照可能メモリ）を配備しなければならない。これらのメモリは、非常に高価で、従ってルータのコストが増大する。
【０００６】
現世代のルータには、記憶容量が例えば２００個のアドレスに低減された小型のＣＡＭを有するＡＳＩＣＳが設けられている。従って、大量のトラフィック（トラヒック）が存在する場合は、ハードウェア・メモリにおけるそのアドレスだけがハードウェア高速化フロー転送による恩恵を受け、その他（のアドレス）はＣＰＵソフトウェア制御による恩恵を受ける。
【０００７】
ハードウェア高速化転送資源に限りのあるシステムにおいて、ハードウェアにはフロー・エントリに利用可能な充分な空間が存在しないというだけの理由で、完全なフロー切り換えを行うことはできない。フローのハードウェア高速化はＣＰＵ転送パケットよりも大きい性能上の利点を有するので、ハードウェア資源が不足によって、性能上の問題が生じ、または、ハードウェア・アーキテクチャの利用性が制限され、それによって高速化機能（能力）が制限される。
【発明の開示】
【０００８】
発明の概要
本発明の目的は、階層的フロー転送（Hierarchical Flow Forwarding）（ＨＦＦ）切り換えを導入することによって、既存のハードウェア・フロー転送を増強する（向上させる）ことである。階層的フロー転送（ＨＦＦ）切り換えは、本発明の通称名である。
【０００９】
その目的および目標を達成するために、本発明は、パケット・フロー転送によって動作するブロードバンド・ネットワークにおけるルータまたはスイッチを提供する。それは、中央処理装置（ＣＰＵ）切換えソフトウェア・フローおよびハードウェア切換え高速フローを含んで成る。そのルータまたはスイッチは、次の構成を具えている。
ルータ出力ポートを介してパケットのフロー転送切換えを行うハードウェア手段およびソフトウェア手段；
前記ハードウェア手段に接続された制限された記憶容量を用いてハードウェア・フロー転送テーブルを格納するメモリ手段；
中央処理装置手段に接続され中央処理装置関連の記憶容量を用いて動作するソフトウェア・フロー転送テーブルを格納するメモリ手段；
前記メモリ手段におけるフロー転送用のエントリのメモリ空間用の、少なくともハードウェア部指定領域、中間部指定領域およびソフトウェア部指定領域からなる（に）相互テーブルの区分を有し、前記メモリ手段用のエントリ・リストを有する相互テーブルであって、前記中間部は所定の割当てのメモリ空間に前記両メモリ手段における利用可能なメモリ空間を指定するものである、相互テーブル；
或る時間期間によって定まる定期的ベースで前記相互テーブルを検査し、時間期間当たりのパケット数の比率に基づいてソートし、前記相互テーブルにおいてハードウェア部を最高の比率のもので、中間部を中間の比率のもので、およびソフトウェア部を最低の比率のもので満たし、前の検査において中間フローとして適合したパケット・フローが依然として前記中間部として適合する場合にはそれをそれの前記メモリ空間に残して、それによって前記テーブルの前記中間部内のメモリ空間指定領域の間で交換が生じるのを防止して前記中央処理装置の負荷を軽減させる手段；および
ハードウェア・フロー転送テーブルを格納する前記メモリ手段と、ソフトウェア・フロー転送テーブルを格納する前記メモリ手段とに、前記相互テーブルのエントリ・リストを格納する手段。
【００１０】
一実施形態において、前記相互テーブルには、テーブルから取り除くべきメモリ空間占有領域を指定する下部のフラッシュ部分が設けられている。
【００１１】
別の実施形態において、システム・コンフィギュレーションによってまたはその他の理由で常にハードウェア高速化されるべき所定の特定のフローが、パケット・ヘッダ情報を照合してハードウェア高速化されるべきものとして認識されるよう設定される。
【００１２】
さらに別の実施形態において、各フロー・エントリがシステム・ルーティング・テーブルを用いて検査されて、フロー・エントリが生成されたときに用いられたルートとは異なる場所の宛先位置への新しいルートが存在するかどうかが判定される。
【００１３】
さらに別の実施形態において、宛先へのルートが変更された場合、フロー・エントリが消去されて、フロー中の次のパケットが出現したときそれが確実に再生成されるようにし、それによって、パケット・フィルタ、再優先度付与または類似の処理が新しいパケット・パスについて正しく処理されるようにできるようにする。
【００１４】
本発明は、中央処理装置切換えソフトウェア・フローおよびハードウェア切換え高速フローを含むパケット・フローを転送するよう動作する、ブロードバンド・ネットワークにおけるルータまたはスイッチに用いられる方法に関する。それは、次の各ステップを含んでいる。
ルータ出力ポートを介してパケットのフロー転送切換えを行うハードウェア手段およびソフトウェア手段を設定するステップ；
前記ハードウェア手段に接続された制限された記憶容量を用いてハードウェア・フロー転送テーブルを格納するメモリ手段を設定するステップ；
中央処理装置手段に接続され中央処理装置関連の記憶容量を用いて動作するソフトウェア・フロー転送テーブルを格納するメモリ手段を設定するステップ；
前記メモリ手段におけるフロー転送用のエントリのメモリ空間用の、少なくともハードウェア部指定領域、中間部指定領域およびソフトウェア部指定領域からなる（に）相互テーブルの区分を有し、前記メモリ手段用のエントリ・リストを有する相互テーブルであって、前記中間部は所定の割当てのメモリ空間に前記両メモリ手段における利用可能なメモリ空間を指定するものである、相互テーブルを設定するステップ；
或る時間期間によって定まる定期的ベースで前記相互テーブルを検査し、時間期間当たりのパケット数の比率に基づいてソートし、前記相互テーブルにおいてハードウェア部を最高の比率のもので、中間部を中間の比率のもので、およびソフトウェア部を最低の比率のもので満たし、前の検査において中間フローとして適合したパケット・フローが依然として前記中間部として適合する場合にはそれをそれの前記メモリ空間に残して、それによって前記テーブルの前記中間部内のメモリ空間指定領域の間で交換が生じるのを防止して前記中央処理装置の負荷を軽減させるステップ；および
ハードウェア・フロー転送テーブルを格納する前記メモリ手段と、ソフトウェア・フロー転送テーブルを格納する前記メモリ手段とに、前記相互テーブルのエントリ・リストを格納するステップ。
【００１５】
従って、次の詳細な説明において、本発明をより良く理解するために、図面を参照して所与の例および実施形態を用いて本発明を説明する。
【発明を実施するための最良の形態】
【００１６】
本発明の階層的フロー転送（Hierarchical Flow Forwarding）（ＨＦＦ）切り換えの概念をより良く理解するためには、フロー切り換え制御の基本を理解しなければならない。
【００１７】
ＴＣＰ／ＩＰ通信において、通信はフローの形で生じる。１つのフローは、ネットワークを介して２つの通信ホストの間で一方向に流れる（streaming）１シーケンスの関連（related）パケットである。ここで、“関連（related）”という表現は、キーワードであり、即ち、複数の送信パケットが互いに関連していることを表している。
【００１８】
ＩＰ（Internet Protocol）を用いた最も一般的な形態の通信は、開放型システム間相互接続（Open Systems Interconnection）（ＯＳＩ）トランスポート層プロトコルであるＵＤＰ（User Datagram Protocol）またはＴＣＰ（Transmission Control Protocol）を用いるものである。これらの双方のプロトコルは、２つの通信ホストの各々における通信ソフトウェアを識別するためのポート番号として知られているユニーク（一意的、固有の）識別子を含んでいる。ＩＰヘッダには発信元（source）および宛先（destination）ＩＰアドレスおよびプロトコル番号が、ＵＤＰまたはＴＣＰヘッダには発信元および宛先ポート（番号）が含まれ、それとともに、２つのホスト間における任意の特定の通信のための一意的な（ユニーク）１組（tuple）の識別子が存在する。２つのホストが同じプロトコルを用いて同時に２つの通信を行っていたとしても、少なくとも発信元または宛先ポートは異なる。
【００１９】
その情報を用いて、パケット転送を行うためのＡＳＩＣまたはネットワーク・プロセッサによって使用される例えばＡＳＩＣまたはＣＡＭテーブルのような転送ハードウェアをプログラム（設定）することができる。基本的思想は、いつパケットが入力され（エントリし）ても、そのパケットについて５つの組で構成された１つのフロー・エントリが存在するかどうかを検査し、そうであれば、そのＣＰＵにおいてそれを処理することなく、そのパケットを転送するようそのハードウェアをイネーブルする、というものである。フロー・エントリが存在しない場合は、そのパケットはそのＣＰＵに転送されて、さらに分析される。本発明の一実施形態において、その５つの組は、ＩＰｓｒｃ（発信元）ポート、ＩＰｄｓｔ（宛先）ポート、例えばＴＣＰ、ＵＤＰ、ＩＣＭＰ等のようなプロトコルのタイプ、プロトコルｓｒｃポート、およびプロトコルｄｓｔポートである。
【００２０】
分析は、課金および／または統計の目的のためのアカウント情報、許可の決定、ファイアウォール・フィルタおよびパケット検査（inspection）、パケット・タイプの再分類、パケット優先度付与（処理）、およびその他のオペレーション（操作）で構成される。ＣＰＵがいったんそのパケットをどのように処理すべきかを判断すると、パケットを受け入れるよう転送ハードウェアを再プログラム（設定）することもあればしないこともある。さらに強力なシステムでは、これ（分析）に、そのフロー中の後続パケットに対するそのハードウェアによる自動的な処理（アクション）が含まれていてもよい。
【００２１】
重要な結果は、大部分の事例において、同じフローに属するいかなる１シーケンスのパケットにおける第１（最初）のパケットだけはＣＰＵによって検査されなければならないということである。その他の全てのパケットは、ハードウェアによって処理され、従ってＣＰＵにおける貴重な処理サイクルをその他のタスクに充てる（取っておく）ことができる。その結果、アカウント処理、フィルタリングおよび転送における有線速度品質が得られるだけでなく、より低い能力の小さいハードウェア解決法でも高速通信が可能となる。
【００２２】
ハードウェア高速化転送資源が制限されているシステムにおいて、ハードウェアにはフロー・エントリに利用可能な充分な空間が存在しないというだけの理由で、完全なフロー切り換えを行うことはできない。フローのハードウェア高速化はパケットのＣＰＵ転送に比べてかなりの性能上の利点があるので、ハードウェア資源の不足によって、性能上の問題が生じることになり、または、高速化機能（容量）の制限（限界）に起因してハードウェア・アーキテクチャの利用性が制限されることになる。
【００２３】
システムがネットワーク環境において効率的に動作するためには、最高の活動状態のフロー、即ち最大量のトラフィックを有するフローは、ハードウェアへの供給の優先度を高くし、一方、より小さいトラフィック量のまたは重要度の低いその他のフロー、例えばより低い優先度が与えられたフローは、ＣＰＵによって処理されるべきである。
【００２４】
本発明によるＨＦＦにおける基本的思想は、ＣＰＵに全てのパケットを転送させ、ハードウェアを高速化器（accelerator）として用いることである。
【００２５】
本発明による切換えＡＳＩＣにおけるハードウェア転送エントリが制限されているルータにおける有線速度転送の問題に対する解決法は、古典的なＩＰｖ４の５組多層フロー・スイッチング・アルゴリズム（IPv4 five-tuple multi-layer flows switching algorithm）の適合化バージョンであり、ここでは、階層的フロー転送（ＨＦＦ）切換え（スイッチング）と称する。
【００２６】
図１は、本発明による、ルータまたはスイッチにおけるフロー転送ハードウェア・パス（path）１０およびＣＰＵソフトウェア・パス１２を示している。図１に示されているように、パケット（Ｐ）はスタートにおいてそのシステムに入る。そのパケットＰは、ハードウェアによって受信されて、判断点Ａに達する。点Ａにおいて、Ｐ（パケット）のフロー・エントリを求めてハードウェア転送テーブルを調査する（図示せず）。エントリが存在しない場合は、そのパケットはＣＰＵ１にデフォルト転送される。ＣＰＵ１において、図示されていないソフトウェア・フロー・キャッシュを調査して、そのパケットがＣＰＵ切換えフローの一部であるかどうかが判定される。フロー・エントリが存在する場合は、そのパケットはＣＰＵ２に転送される。そのパケット用のソフトウェア・フロー・エントリが存在しない場合は、そのパケットは新しいフローの第１（最初）のパケットであると判定される。そのパケットＰは任意の構成（コンフィギュア）されたフィルタまたはその他のポリシーと照合（マッチング）されて、そのパケットが転送されるべきかどうかが判定される。そのパケットが転送されるべきである場合は、適正なソフトウェア・フロー・エントリが生成されて、その後そのパケットはＣＰＵ２に転送される。それ以外の場合は、そのパケットは廃棄（discard）される。
【００２７】
ＣＰＵ２において、そのパケットＰは出力キューに入れるために準備処理される。任意の適当なヘッダ処理（オペレーション、操作）が実行され、そのパケットが出力ポートのキューに入れられる。フロー・テーブルにおけるフロー用のパケット・カウンタがインクレメント（増分）される。逆に、そのテーブルにハードウェア転送エントリが存在する場合は、そのパケットはハードウェア１（ＨＷ１）に転送される。ＨＷ１において、そのパケットは、例えば、フィルタリング、優先度付与、再カラー化（recolour、優先度再付与）、ルーティング・テーブル／ＣＡＭ、テーブル・ルックアップ、ヘッダ処理またはその他の処理のような任意のハードウェア機能によって処理（影響）され、その後ハードウェア２（ＨＷ２）に転送される。ＨＷ２において、そのパケットは分析されてハードウェア・フロー・テーブルにおいてフロー・カウンタ更新が行われ、その後、そのパケットは出力ポートのキューに入れられる。フロー・テーブルにおけるフロー用のパケット・カウンタがインクレメントされる。
【００２８】
再カラー化（recolour、優先度再付与）は、優先度付与に類似したもので、パケットの優先度値を変更することを表すための技術用語である。
【００２９】
Ｂにおいて、ハードウェアはポートの出力キューを処理実行して（走って）待ちパケットを送信する。例えば、レート（速度、率）制限、パケット・フィルタリング、アカウント処理、優先度再付与（再カラー化）、優先度付与、等のような処理のシーケンス（順）は、使用されるアーキテクチャに応じて決めてもよいが、フローの現在のトラフィック・レート（速度、率）に依存してハードウェアとソフトウェアのフロー・キャッシュの間でフローが移動するのを許容するアルゴリズムの基本的原理を変更するものではない。
【００３０】
本発明によるブロードバンドにおけるルータまたはスイッチには、ＣＰＵ切換えソフトウェア・フロー１２とハードウェア切換え高速化フロー１０とが供給される。ルータまたはスイッチは、ルータの出力ポートを通して各パケットのフロー転送の切り換えを行うためのハードウェア手段およびソフトウェア手段を含んでいる。ハードウェア手段には、制限された記憶容量を有するハードウェア・フロー転送テーブルを格納するメモリ手段が接続されている。ＣＰＵ手段には、ソフトウェア・フロー転送テーブルを格納するメモリ手段が接続されている。
【００３１】
次に図２を参照すると、図２は、本発明によって区分された相互フロー転送テーブル２０またはフロー・キャッシュを概略的に示している。本発明のこの実施形態において、図２に示されているようなフロー・テーブル２０が維持（保存）され、フロー・テーブル２０によってハードウェアとソフトウェアの双方のフロー・エントリが追跡される。テーブルの上部分は、ハードウェア・フロー・テーブル部分２２を介したハードウェア・フロー・パス１０用に指定されている。この上部分の後に、ソフトウェア・フロー・テーブル部分２６およびフラッシュ（flush）ゾーン部分２８が続く。
【００３２】
本発明によれば、図２における長方形の破線で示されたテーブル２０の中間部分２４が形成される。この中間部分２４は、テーブル２０のハードウェア部分２２とソフトウェア部分２６の双方に重なって（オーバラップして）いる。重なったハードウェア部分２２ａはフロー転送用のハードウェア・メモリ・エントリを指定し、重なったソフトウェア部分２６ａはフロー転送用のソフトウェア・メモリ・エントリを指定する。図２から分かるように、導入した中間部分２４は、ハードウェアおよびソフトウェア・フロー転送メモリ空間指定に関して相互（mutual、共通、共用、共同）部分２２ａおよび２６ａを有する。
【００３３】
フラッシュ部分２８を用いて、進行（転送）中のトラフィックを示（提示）していないエントリが削除される。フラッシュ部分２８においてエントリが除去されなかったならば、可能なフローの組み合わせの数が、可能な全てのプロトコルに対する可能なポート番号の何十万もの組み合わせ全てに対する可能な全てのＩＰアドレスとなるので、フロー・テーブル２０は無限に増加することになるであろう。従って、利用可能なメモリ空間は充分でなく、或る期間に全くトラフィックを示さ（提示し）なかった蓄積フローをそのテーブルから消去して、それ（フロー）がメモリ全体に指定されないようにする。
【００３４】
本発明を、制限されたハードウェア資源を有するシステムに用いると、ハードウェア・フロー・テーブル部分２２、２２ａは、利用可能なハードウェアによってイネーブル（可動化）される（量）より大きくなることがなく、一方、ソフトウェア・フロー・テーブル部分２６、２６ａは、何倍も大きくてよく、使用されるルータまたはスイッチのシステムの性能によってのみ制限される。
【００３５】
テーブル２０は、テーブルの底部から、ハードウェア指定メモリ空間とソフトウェア指定メモリ空間の間の境界を指す実線矢印まで、例えばＲＡＭのようなＣＰＵ制御されるメモリ空間２８、２６、２６ａを指定する。その境界は、中間部分２４内に位置し、中間部分２４を異なるタイプの２つの指定部分２２ａおよび２６ａに分割し、その一方の部分２６ａはソフトウェア・メモリ空間を指定するものであり、別の部分２２ａはハードウェア・メモリ空間を指定するものである。また、図２は、テーブル２０において、上向き破線矢印とＨＷで示されたハードウェア・メモリ指定空間２２の方向と、下向き破線矢印とＳＷで示されたソフトウェア指定空間２６の方向を示している。
【００３６】
ハードウェア指定メモリ空間２２、２２ａは、例えばＣＡＭタイプのものとし、ソフトウェア指定空間２６、２６ａはＲＡＭタイプのものとすることができる。従って、図２から分かるように、中間部分２４はハードウェア２２ａとソフトウェア２６ａの双方のメモリ空間を指定する。
【００３７】
中間部分２４は、フロー転送のトラフィック状況に応じて可能な最大性能をルータが発揮するよう設計すべきであることが分かり、その際、中間部分内のハードウェア指定メモリ空間とソフトウェア指定メモリ空間２２ａ、２６ａの間のパーセント割合は各アプリケーションごとに異なるものである。
【００３８】
例えば、フロー転送用の例えばＡＳＩＣにおけるハードウェア高速化メモリ・テーブルが２００個のエントリを保存できる場合、全体のフロー・テーブル・メモリは、例えば５０００個のエントリの大きさになってもよいであろう。中間部分２４のサイズ並びにフラッシュ部分２８のサイズは、共にルータのシステムの実際の状態に応じて決められる。性能を最大化するためには、ハードウェア指定フロー・テーブル２２、２２ａは、最高の活動状態のフローを含むべきであり、従って最も強い（大量の）パケット転送をハードウェアＨＷ１、ＨＷ２に移動させるべきである。これは、定期的間隔で、例えば、毎秒１回または別の適当な時間期間毎に１回、現在の相互フロー・テーブル２０を検査し、各フローにおいて決定される１秒当たりのパケット数または他の時間期間当たりのパケット数に基づいてテーブル２０をソートすることによって、行われる。
【００３９】
本発明は、或る時間期間によって定まる定期的ベースで（定期的に）相互テーブル２０を検査する手段を適用する。時間期間当たりのパケット数の比率に基づいてソートを行い、テーブル２０のハードウェア部分２２、２２ａを最高の比率（のもの）で満たす。図２から明らかなように、中間部分２４における中間比率の一部分は指定されたハードウェア・メモリ空間であり、その中間部分の別の一部分は指定されたソフトウェア・メモリ空間２６ａであり、最低の比率（のもの）は、中間部分２４におけるソフトウェア部分２６ａの下のソフトウェア・メモリ空間２６に指定される。
【００４０】
本発明に従って前に検査したときに流れた中間部分２４に適合する（その資格を有する、に等級付けされる）パケット・フローは、それら（フロー）が中間部分２４に依然として適合する場合にはそのフローの指定されたメモリ空間に残留し、それによって、テーブル２０の中間部分２４内のメモリ空間指定領域２２ａと２６ａの間での交換（移動、切換）が防止され、従ってＣＰＵの負荷が軽減される。それの意味は（i.a.）、中間部分２４におけるソフトウェア指定部分２６ａには、ハードウェア・メモリ空間２２ａに指定されるパケット転送用の比率よりも高い比率を有するパケット転送用のメモリ空間指定領域が存在しても、それらが依然として中間比率として適合しているのであればそれらがソフトウェア指定メモリ部分２６ａに残留することである。本発明によるこの解決法（アプローチ）は、テーブル２０の中間部分２４におけるメモリ指定空間２２ａと２６ａの間でパケット・フロー指定領域を移動させる必要がないことによって、ルータまたはスイッチにおけるＣＰＵの負荷を軽減する。
【００４１】
相互テーブル２０の検査の後、相互テーブル２０のエントリ・リストは、それぞれ、例えばＣＡＭのようなハードウェア・フロー転送テーブルを格納するメモリ手段と、例えばＲＡＭのようなソフトウェア・フロー転送テーブルを格納するメモリ手段とに、それらを格納する手段によって格納される。
【００４２】
従って、最高の活動状態のフローはテーブル２０の最上部にソートされ、一方、最低の活動状態のフローはそのテーブルの底部にソートされる。テーブル２２のハードウェア・フロー部分に利用可能なスロット／空間を満たすそのソートされたテーブル中のそれらエントリは、ハードウェア中に配置される。中間部分２４のフローとして指定されたスロットに整合するフローは、変更されない。それらがハードウェア２２ａに位置する（存在する）場合は、それらはハードウェアに残る。それらがソフトウェア部分２６ａに位置する場合は、それらはソフトウェアに残る。それによって、図１によるハードウェア・パスとソフトウェア・パスの間で（一方から他方へ他方から一方へと）移動するエントリのフラッピング（揺れ）／交換が最小化される。
【００４３】
中間部分より下のフローはテーブル２０のソフトウェア・フロー部分中に配置され、最後に、フラッシュ部分２８に位置する底部のエントリはルータから取り除かれる。これらの（底部）エントリは活動状態でないフローを表している。
【００４４】
システム構成（コンフィギュレーション）またはその他の理由により特定のフローが常にハードウェア高速化されるべきである場合には、制御ヘッダ情報が照合されて、高速化されるものとして認識される。特定のパケット・フローに対して固定的または永続的ハードウェア・フローを確立することができるようにするためには、固定的フロー確立のために照合されるべきパケット・ヘッダにおける、例えば２進法または１６進法のようなフィールドを定義する必要がある。その使用されるフィールドは、例えば、プロトコル発信元／宛先アドレス、特定のプロトコル・フラグ、等であってもよいであろう。
【００４５】
システム・ルーティング・テーブルを（に対して）各フロー・エントリについて検査して、フロー・エントリが生成されたときに用いられたルート以外のどこかの場所の宛先位置への新しいルートが存在するかどうかを判定する。その宛先へのルートが変更された場合は、フロー・エントリは一気に消去（フラッシュ）されて、フロー中の次のパケットが出現したときそれが確実に再生成（relearn、再記憶）されるようにする。それによって、任意のパケット・フィルタ、再優先度付与または類似の処理が、新しいパケット・パスについて正しく処理できる。
【００４６】
本明細書に記載した手段は、具体的な名称はなくても、ソフトウェア手段、ハードウェア手段またはそれらの組み合わせであることが分かる。
【００４７】
本発明の別の実施形態は、請求の範囲から明らかである。
【図面の簡単な説明】
【００４８】
【図１】図１は、本発明によるフロー転送ハードウェア・パスおよびＣＰＵソフトウェア・パスを概略的に示している。
【図２】図２は、本発明による分割されたフロー転送テーブルを概略的に示している。
【図１】
2006505188.tif 000003
【図２】
2006505188.tif 000004
【国際調査報告】
2006505188.tif 000005
2006505188.tif 000006