(57)【要約】【課題】  ファイバチャネルネットワークのようなネットワークにおける輻輳を制御する方法および装置を提供する。輻輳したネットワークノードにおけるトラフィックフローを特性付ける手法を提供する。【解決手段】  輻輳したネットワークノードは、輻輳したネットワークノードへのトラフィックフローを制御するための抑制メッセージのようなさまざまなインストラクションを生成しえる。抑制メッセージは、任意選択で、輻輳の特性についての情報を含みえる。インストラクションは、ネットワーク中の他のノードに分散される。他のネットワークノードは、このインストラクションおよび輻輳したノードへのトラフィックフローを解釈できる。
2005535154.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークスイッチにおいて輻輳を制御する方法であって、前記方法は、
送信元ノードに対応する送信元識別子フィールドおよび宛先ノードに対応する宛先識別子フィールドを持つフレームを受信することであって、前記フレームは、前記ネットワークスイッチおよび前記送信元ノードの間の第１中間スイッチを通って前記ネットワークスイッチに送信された、受信すること、
前記ネットワークスイッチにおけるトラフィックフローを特性付けること、および
前記ネットワークスイッチから前記第１中間スイッチに第１インストラクションを送ることによって前記送信元ノードから前記宛先ノードへのトラフィックを制御すること
を含む方法。
【請求項２】
請求項１に記載の方法であって、前記第１中間スイッチは、前記送信元ノードに結合されたエッジスイッチである方法。
【請求項３】
請求項１〜２のいずれかに記載の方法であって、第１中間スイッチに送られた前記第１インストラクションは、エッジ抑制フレームを備える方法。
【請求項４】
請求項３に記載の方法であって、前記エッジ抑制フレームは、前記宛先ノードに対応する送信元識別子フィールドおよび前記送信元ノードに対応する宛先識別子フィールドを有する方法。
【請求項５】
請求項４に記載の方法であって、前記エッジ抑制フレームはネットワークスイッチ輻輳情報を含む方法。
【請求項６】
請求項４〜５のいずれかに記載の方法であって、前記エッジ抑制フレームはネットワークスイッチキューレベル情報を含む方法。
【請求項７】
請求項４〜６のいずれかに記載の方法であって、前記エッジ抑制フレームは、前記第１中間スイッチが、前記送信元ノードおよび前記宛先ノードから送信ための前記許容されたレートを半分に制御するよう指示する方法。
【請求項８】
請求項１〜７のいずれかに記載の方法であって、前記第１中間スイッチおよび前記ネットワークスイッチは、ファイバチャネルを用いて接続される方法。
【請求項９】
請求項１〜７のいずれかに記載の方法であって、前記フレームは、前記第１中間スイッチおよび前記ネットワークスイッチの間の第２中間スイッチを通して送信された方法。
【請求項１０】
請求項９に記載の方法であって、
第２インストラクションを前記ネットワークから前記第２中間スイッチへ送ることによって、前記送信元ノードから前記宛先ノードへのトラフィックを制御すること
をさらに含む方法。
【請求項１１】
請求項１０に記載の方法であって、前記第１中間スイッチに送られる前記第１インストラクションは、パス抑制フレームを備える方法。
【請求項１２】
請求項１１に記載の方法であって、前記第２中間スイッチに送られた前記第２インストラクションは、前記パス抑制フレームを備える方法。
【請求項１３】
請求項１１〜１２のいずれかに記載の方法であって、前記パス抑制フレームは、前記宛先ノードに対応する送信元識別子フィールドおよび前記送信元ノードに対応する宛先識別子を有する方法。
【請求項１４】
請求項１１〜１３のいずれかに記載の方法であって、前記パス抑制フレームは、ネットワークスイッチ輻輳情報を含む方法。
【請求項１５】
請求項１１〜１４のいずれかに記載の方法であって、前記パス抑制フレームは、ネットワークスイッチキューレベル情報を含む方法。
【請求項１６】
請求項１１〜１５のいずれかに記載の方法であって、前記パス抑制フレームは、前記第１および第２中間スイッチが、前記送信元ノードおよび前記宛先ノードから送信する前記許容されたレートを０ｂｐｓに低減するよう指示する方法。
【請求項１７】
請求項１〜１７のいずれかに記載の方法であって、トラフィックフローを特性付けることは、前記ネットワークスイッチキューレベルをチェックすることを含む方法。
【請求項１８】
請求項１７に記載の方法であって、トラフィックフローを特性付けることは、送信パス抑制またはエッジ抑制フレームを送信するかどうかを決定することを含む方法。
【請求項１９】
請求項１７〜１８のいずれかに記載の方法であって、前記キューレベルが高スレッショルドを超えるとき、パス抑制フレームが送信される方法。
【請求項２０】
請求項１７〜１９のいずれかに記載の方法であって、前記キューレベルが高スレッショルドおよび低スレッショルドの間であるとき、エッジ抑制フレームが送信される方法。
【請求項２１】
請求項１７〜２０のいずれかに記載の方法であって、前記エッジ抑制およびパス抑制フレームはバッファレベル指示子を含む方法。
【請求項２２】
第１および第２中間ノードを通る第１および第２エンドノード間のトラフィックフローを制御する方法であって、
前記第１エンドノードに対応する送信元識別子および前記第２エンドノードに対応する宛先識別子を持つ第１フレームを送信することであって、前記フレームは第１中間ノードにおいて、前記第１中間ノードおよび前記第２エンドノードの間の第２中間ノードに送信される、送信すること、
前記第２中間ノードから第２フレームを受信することであって、前記第２フレームは前記第２エンドノードに対応する送信元識別子および前記第１エンドノードに対応する宛先識別子を持ち、前記第２フレームは、前記第１エンドノードから前記第２エンドノードへの前記現在の許容されたレートを調整するインストラクションを含む、受信すること、および
前記第１エンドノードから前記第２エンドノードへの前記現在の許容されたレートを前記第２フレームの受信と共に調整すること
を含む方法。
【請求項２３】
請求項２２に記載の方法であって、前記現在の許容されたレートは最大許容レートを超えない方法。
【請求項２４】
請求項２１〜２２のいずれかに記載の方法であって、前記現在の許容されたレートを調整することは、
前記第２フレームがエッジ抑制フレームであることを決定すること
を含む方法。
【請求項２５】
請求項２１〜２４のいずれかに記載の方法であって、前記第１中間ノードが、前記第１エンドノードに結合されたエッジスイッチであると決定された後で、前記現在の許容されたレートが調整される方法。
【請求項２６】
請求項２４に記載の方法であって、前記第１中間ノードが、輻輳制御をサポートしない近接ノードに結合すると決定された後で、前記現在の許容されたレートが調整される方法。
【請求項２７】
請求項２１〜２５のいずれかに記載の方法であって、前記現在の許容されたレートは初期状態では最大許容レートである方法。
【請求項２８】
請求項２１〜２７のいずれかに記載の方法であって、前記現在の許容されたレートは、エッジ抑制フレームの受信と共に２で除される方法。
【請求項２９】
請求項２１〜２８のいずれかに記載の方法であって、前記現在の許容されたレートはリカバリレートで増加する方法。
【請求項３０】
請求項２９に記載の方法であって、前記リカバリレートは、前記受信されたエッジ抑制フレーム中に含まれる情報に基づいて設定される方法。
【請求項３１】
請求項２９〜３０のいずれかに記載の方法であって、前記リカバリレートは、前記第２中間ノードに関連付けられた入力キューに基づいて設定される方法。
【請求項３２】
請求項２９〜３１のいずれかに記載の方法であって、前記現在の許容されたレートを調整することは、
前記第２フレームがパス抑制フレームであると決定すること
を含む方法。
【請求項３３】
請求項３２に記載の方法であって、前記現在の許容されたレートは初期状態では最大許容レートである方法。
【請求項３４】
請求項３３に記載の方法であって、前記現在の許容されたレートは、パス抑制フレームの受信と共に０ｂｐｓに低減される方法。
【請求項３５】
請求項３４に記載の方法であって、前記現在の許容されたレートはリカバリレートで増加する方法。
【請求項３６】
請求項３３〜３５のいずれかに記載の方法であって、前記リカバリレートは、前記受信されたパス抑制フレーム中に含まれる情報に基づいて設定される方法。
【請求項３７】
請求項３６に記載の方法であって、前記リカバリレートは、前記第２中間ノードに関連付けられた入力キューに基づいて設定される方法。
【請求項３８】
送信元ノードおよび宛先ノード間のトラフィックフローを制御するスイッチであって、
第１外部ノードに結合する第１ポート、
第２外部ノードに結合する第２ポート、
前記第１外部ノードからデータを受信する前記第１ポートに関連付けられた第１キューであって、前記第１キューは、前記第１ポートを通した送信についてのデータを保持する第１部分および前記第２ポートを通した送信についてのデータを保持する第２部分を含む、第１キュー、および
前記第１キューに結合されたフィルタであって、前記フィルタは前記第１キューからデータを受信し、前記データの送信が遅延されるべきかを前記第２外部ノードから受信された情報に基づいて決定するよう構成される、フィルタ
を備えるスイッチ。
【請求項３９】
請求項３８に記載のスイッチであって、フィルタキューをさらに備え、前記フィルタキューは、遅延された送信について設定されたデータを保持するよう構成されるスイッチ。
【請求項４０】
請求項３９に記載のスイッチであって、それぞれのフィルタキューはフローに関連付けられたスイッチ。
【請求項４１】
請求項３８〜４０のいずれかに記載のスイッチであって、前記フローは送信元ノードから宛先ノードへのトラフィックであるスイッチ。
【請求項４２】
請求項４１に記載のスイッチであって、前記第１キューは仮想出力キューであるスイッチ。
【請求項４３】
請求項３８〜４２のいずれかに記載のスイッチであって、それぞれのフィルタキューは優先度に関連付けられたスイッチ。
【請求項４４】
請求項３８〜４３のいずれかに記載のスイッチであって、それぞれのフィルタキューは入力ポートおよび出力ポートに関連付けられたスイッチ。
【請求項４５】
請求項３８〜４４のいずれかに記載のスイッチであって、フィルタキューに結合されたレートリミッタをさらに備えるスイッチ。
【請求項４６】
請求項４５に記載のスイッチであって、前記遅延の量は、前記レートリミッタによって決定されるスイッチ。
【請求項４７】
請求項４６に記載のスイッチであって、前記レートリミッタはトークンバケットを用いるスイッチ。
【請求項４８】
請求項４７に記載のスイッチであって、前記遅延の量は、前記第２外部ノードから受信された情報に基づいて決定されるスイッチ。
【請求項４９】
請求項４８に記載のスイッチであって、フローに関連付けられたフィルタキューに割り当てられたトークンの個数は、前記フローを特定する前記第２外部ノードからエッジ抑制フレームが受信されると共に半分にされるスイッチ。
【請求項５０】
請求項４７〜４９のいずれかに記載のスイッチであって、前記フローに関連付けられたフィルタキューに割り当てられたトークンの個数は、リカバリレートで増加するスイッチ。
【請求項５１】
請求項４７〜５０のいずれかに記載のスイッチであって、前記リカバリレートは、第２外部ノードキューレベル情報に基づいて設定されるスイッチ。
【請求項５２】
請求項４７〜５１のいずれかに記載のスイッチであって、特定のフローに関連付けられたフィルタキューに割り当てられたトークンの個数は、前記特定のフローを特定する前記第２外部ノードからパス抑制フレームを受信すると共にゼロに設定されるスイッチ。
【請求項５３】
請求項５２に記載のスイッチであって、前記フローに関連付けられたフィルタキューに割り当てられたトークンの個数は、リカバリレートで増加するスイッチ。
【請求項５４】
輻輳を制御する装置であって、
送信元ノードに対応する送信元識別子フィールドおよび宛先ノードに対応する宛先識別子フィールドを持つフレームを受信する手段であって、前記フレームは、前記ネットワークスイッチおよび前記送信元ノードの間の第１中間スイッチを通って前記ネットワークスイッチに送信された、受信する手段、
前記ネットワークスイッチにおけるトラフィックフローを特性付ける手段、および
前記ネットワークスイッチから前記第１中間スイッチに第１インストラクションを送ることによって前記送信元ノードから前記宛先ノードへのトラフィックを制御する手段
を備える装置。
【請求項５５】
輻輳を制御するコンピュータで読み取り可能な媒体であって、
送信元ノードに対応する送信元識別子フィールドおよび宛先ノードに対応する宛先識別子フィールドを持つフレームを受信するコンピュータコードであって、前記フレームは、前記ネットワークスイッチおよび前記送信元ノードの間の第１中間スイッチを通って前記ネットワークスイッチに送信された、受信するコンピュータコード、
前記ネットワークスイッチにおけるトラフィックフローを特性付けるコンピュータコード、および
前記ネットワークスイッチから前記第１中間スイッチに第１インストラクションを送ることによって前記送信元ノードから前記宛先ノードへのトラフィックを制御するコンピュータコード
を備えるコンピュータで読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク輻輳制御に関する。より具体的には本発明は、輻輳を検出し、輻輳を緩和する命令を生成し、その命令を分配し、かつ輻輳を制御する方法および装置に関する。
【背景技術】
【０００２】
多くの従来のネットワークプロトコルは、ネットワークノードにおいて輻輳を緩和させるためにパケット廃棄を用いる。ある例ではＩＰベースのネットワークにおけるネットワークノードは、入力データを複数のソースからその出力帯域幅を超えるレートで受け取る。従来の実現例では、割り当てられた帯域幅の中で残りのパケットを伝送できるよう選択されたパケットが廃棄される。パケットはランダムに、またはさまざまな選択基準を用いて廃棄されえる。廃棄されたパケットは、ＴＣＰのようなより高いレベルのプロトコルの制御のもとで最終的には再送信される。
【０００３】
ファイバチャネルネットワークのようなネットワークにおいて、パケット廃棄は一般には許されない。その代わりにファイバチャネルネットワークのようなネットワークは、エンドツーエンドおよびバッファツーバッファのフロー制御メカニズムを利用する。エンドツーエンドおよびバッファツーバッファのフロー制御メカニズムは、第２ネットワークがフレームを受け取る準備ができるまで、第１ネットワークノードが第２ネットワークノードに送信することを許さない。第２ネットワークノードは典型的には、第１ネットワークノードにクレジットを認めることによってフレームを受け取る準備ができていることを示す。フレームが送信されるとき、クレジットが用いられる。クレジットが残っていないとき、第１ネットワークノードは、第２ネットワークノードにもはや送信できない。しかしエンドツーエンドおよびバッファツーバッファフロー制御メカニズムは、このメカニズムは特定のリンクに沿った全てのトラフィックをブロックするので、輻輳を制御するには非常に大まかな技術しか提供しない。このようなブロッキングは、ファイバチャネルネットワークトポロジで上流の他のリンクにすぐに伝搬しえる。これらリンクのいくつかは、もともと輻輳していたリンクを含まないパスのためのコリドーとして働きえる。したがってあるネットワークパスのうちの一つのリンクにおける輻輳が、ファイバチャネルトポロジのずっと広い部分にわたってブロッキングを生じることもときにはありえる。
【０００４】
エンドツーエンドクレジットメカニズムは、受信ノード中のバッファの利用可能性も考慮する。しかしそれはネットワーク環境の変化に対して反応しないので、そのネットワーク上での輻輳およびブロッキングはやはり起こりえる。さらに、エンドツーエンドクレジットメカニズムは典型的には、クラス２トラフィックを交換するエンドノード間に適用される。しかしたいていのファイバチャネルデバイスはクラス２トラフィックを交換しない。その結果、エンドツーエンドおよびバッファツーバッファクレジットメカニズムは、ネットワーク中のトラフィックフローを最適化しないし、そうしようと試みすらしない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
よって、上述のパフォーマンス制限の一部または全てについて、ファイバチャネルネットワークのようなネットワーク中のネットワークノードにおける輻輳制御を改良する方法および装置を提供することが望ましい。
【課題を解決するための手段】
【０００６】
ファイバチャネルネットワークのようなネットワークにおける輻輳を制御する方法および装置が提供される。輻輳したネットワークノードにおけるトラフィックフローを特性付ける手法が提供される。輻輳したネットワークノードは、輻輳したネットワークノードへのトラフィックフローを制御するための抑制メッセージのようなさまざまなインストラクションを生成しえる。抑制メッセージは、任意選択で、輻輳の特性についての情報を含みえる。インストラクションは、ネットワーク中の他のノードに分散される。他のネットワークノードは、このインストラクションおよび輻輳したノードへのトラフィックフローを解釈できる。
【０００７】
ある実施形態において、ネットワークスイッチにおいて輻輳を制御する方法が提供される。送信元ノードに対応する送信元識別子フィールドおよび宛先ノードに対応する宛先識別子フィールドを持つフレームが受信され、前記フレームは、前記ネットワークスイッチおよび前記送信元ノードの間の第１中間スイッチを通って前記ネットワークスイッチに送信されている。前記ネットワークスイッチにおけるトラフィックフローが特性付けられる。前記ネットワークスイッチから前記第１中間スイッチに第１インストラクションが送られることによって前記送信元ノードから前記宛先ノードへのトラフィックを制御する。
【０００８】
他の実施形態においては、第１および第２中間ノードを通る第１および第２エンドノード間のトラフィックフローを制御する方法が提供される。前記第１エンドノードに対応する送信元識別子および前記第２エンドノードに対応する宛先識別子を持つ第１フレームが送信される。前記フレームは第１中間ノードにおいて、前記第１中間ノードおよび前記第２エンドノードの間の第２中間ノードに送信される。前記第２中間ノードから第２フレームが受信される。前記第２フレームは前記第２エンドノードに対応する送信元識別子および前記第１エンドノードに対応する宛先識別子を持ち、前記第２フレームは、前記第１エンドノードから前記第２エンドノードへの前記現在の許容されたレートを調整するインストラクションを含む。前記第１エンドノードから前記第２エンドノードへの前記現在の許容されたレートは前記第２フレームの受信と共に調整される。
【０００９】
他の実施形態によれば、送信元ノードおよび宛先ノード間のトラフィックフローを制御するスイッチが提供される。このスイッチは、第１外部ノードに結合する第１ポート、
第２外部ノードに結合する第２ポート、前記第１外部ノードからデータを受信する前記第１ポートに関連付けられた第１キューであって、前記第１キューは、前記第１ポートを通した送信についてのデータを保持する第１部分および前記第２ポートを通した送信についてのデータを保持する第２部分を含む、第１キュー、および前記第１キューに結合されたフィルタであって、前記フィルタは前記第１キューからデータを受信し、前記データの送信が遅延されるべきかを前記第２外部ノードから受信された情報に基づいて決定するよう構成される、フィルタを含む。
【００１０】
さらに他の本発明の局面は、上述の方法および手法の全部またはその一部を実現するプログラムインストラクションがその上に提供される機械で読み取り可能な媒体を含むコンピュータプログラム製造物に関する。本発明の方法の任意のものの全体またはその一部は、そのような機械で読み取り可能な媒体上に提供されえるプログラムインストラクションとして表現されえる。さらに本発明は、ここで上述のように生成される、および／または使用されるデータのさまざまな組み合わせおよび構成に関する。例えば、ここで記述されたフォーマットを持ち、適切な媒体上に提供された（媒体上で送信された）抑制フレームは本発明の一部である。
【００１１】
本発明のこれらや他の特徴および優位性は、本発明の以下の明細書および添付図面においてより詳細に示され、これらは本発明の原理を例示により示す。
【発明を実施するための最良の形態】
【００１２】
本発明は、本発明の具体的な実施形態を示す添付図面と併せ、以下の説明を参照すれば最もよく理解されよう。
【００１３】
本発明は、ネットワーク中の輻輳を制御することに関する。より具体的には、本発明は、輻輳したネットワークノードへのトラフィックフローを制御するために、抑制メッセージを輻輳したネットワークノードから他のネットワークノードに送信する方法および装置に関する。
【００１４】
本発明を実施するために発明者がベストモードであると考えるものを含む、本発明のいくつかの具体的な実施形態がこれから参照される。これら具体的な実施形態は添付の図面に示される。本発明はこれら具体的な実施形態について説明されるが、本発明はこれらの説明された実施形態に限定されないことが理解されよう。むしろ添付の特許請求の範囲によって規定されるように本発明の精神および範囲に含まれる代替物、改変、および等価物をカバーするように意図される。
【００１５】
例えば、本発明の技術は、ストレージエリアネットワーク内で用いられるファイバチャネルのコンテキストにおいて説明される。しかし本発明の技術は、さまざまな異なるプロトコルおよびネットワークにも応用されえることに注意されたい。さらに本発明によって可能になるソリューションは、非ファイバチャネルネットワークにも同様に応用可能である。本発明の技術はＩＰネットワークを含むさまざまな異なるネットワークに応用できるが、ある例ではこの技術は、一般にパケット廃棄を許さないネットワークにも応用できる。以下の記載において、本発明の完全な理解を与えるために多くの具体的な詳細が述べられる。本発明はこれら具体的な詳細の一部または全てがなくても実施されえる。あるいは既知のプロセス操作は、本発明の趣旨を不必要にぼかさないために詳細には記載されていない。
【００１６】
ネットワークノードにおける輻輳を緩和するための装置および方法が提供される。任意のネットワークにおける輻輳は、さまざまなタイプのデータが転送されるときの遅延につながりえる。特にファイバチャネルを用いるネットワークノードにおける輻輳は特に有害であり、これはさらに後で詳述される波及的輻輳（cascading congestion）およびヘッドオブラインブロッキングのような効果がネットワークに及ぼされえるからである。その結果、ネットワークノードにおける輻輳を検出し特徴付ける技術が提供される。輻輳したネットワークノードへのトラフィックフローを制御するための異なるタイプの命令が、そのネットワークノードにおける輻輳を特徴付ける情報と共にそれから生成され、送信される。この命令を受け取るいくつかの他のネットワークノードは、輻輳したネットワークノードに向かうトラフィックフローを選択的に制御するために命令中に提供される情報を用いる。
【００１７】
図１は、本発明の技術を用いえるネットワークの概略図である。本発明の技術は、ストレージエリアネットワーク中のファイバチャネルのコンテキストにおいて説明されるが、上述のように本発明の技術は、さまざまなローカルおよびワイドエリアネットワークを含むさまざまなコンテキストに応用されえる。さまざまな技術が、単一のネットワークノードが複数のフローまたはパスについての輻輳点として働く任意のネットワークにおいて応用されえる。図１は、ファイバチャネルを用いて実現されたストレージエリアネットワークを示す。スイッチ１０１は、ホスト１１１および記憶装置１２１に結合されると共にスイッチ１０３および１０５にも結合される。ある実施形態においては、ホスト１１１は、サーバまたはクライアントシステムでありえ、一方、記憶装置１２１は単一のディスクまたは冗長ディスクアレイ（ＲＡＩＤ）でありえる。相互接続されたスイッチ１０３および１０５は、共にスイッチ１０７に結合される。スイッチ１０７はホスト１１３に結合され、スイッチ１０３は記憶装置１２３に結合される。スイッチ１０９は、ホスト１１５、スイッチ１０７、およびファイバチャネルを使用するかまたは使用しないかのいずれでもよい外部ネットワーク１５１に接続される。ホスト１１１がネットワーク１５１にアクセスするためには、いくつかのパスが使用されえる。あるパスはスイッチ１０３を通って到達し、一方、他のパスはスイッチ１０５を通って到達する。しかしスイッチ１０９における輻輳は、ホスト１１１およびネットワーク１５１の間の通信を遅くしえる。
【００１８】
上述のように、従来のＩＰネットワークにおけるスイッチまたはルータが輻輳するとき、パケットは廃棄される。パケットはランダムに、またはある程度のインテリジェンスをもって選択的に廃棄されえる。パケットを廃棄することによって、多量の帯域幅を消費していたフローは、一般に、より少ない量の帯域幅を消費していたものよりも、より多くのパケットを廃棄することになる。輻輳したスイッチまたはルータを通るフローレートは、パケットの廃棄で低下するが、パケットはスイッチ１０９を通ってネットワーク１５１に到達する。スイッチ１０７または１０９における輻輳のせいで、スイッチ１０３および１０５における輻輳は引き起こされない。
【００１９】
しかしファイバチャネルは、パケットの廃棄を許さない。代わりに、ネットワーク１５１がより多くのフレームを受け取るのに失敗するか、またはそうする能力がないようなさまざまな理由でスイッチ１０９が輻輳するときは、スイッチ１０７からスイッチ１０９へのトラフィックフローを制御するためにバッファツーバッファクレジットメカニズムが用いられる。典型的な実現例では、スイッチ１０９は、所定の数のクレジットをスイッチ１０７に割り当てる。スイッチ１０７がフレームをスイッチ１０９に送信するたびにクレジットが用いられる。スイッチ１０９が利用可能なバッファを持つときは、それからスイッチ１０９は、追加のクレジットをスイッチ１０７に割り当てえる。ネットワーク１５１がより多くのフレームを受け取るのに失敗するか、またはそうする能力がないため、スイッチ１０９、およびその結果としてスイッチ１０７はネットワーク１５１に送信できない。ネットワーク１５１はある実施形態における輻輳点として記載されるが、他の実施形態においてはディスクアレイ１５３またはホスト１１５が輻輳源でありえることに注意されたい。
【００２０】
バッファツーバッファクレジットメカニズムは、スイッチ１０９へのトラフィックフローを減らす非常に大まかなやりかたである。ホスト１１５およびそれに関連付けられたリンクは追加フレームをスイッチ１０９から受け取る帯域幅を持つかもしれないが、クレジットメカニズムは、トラフィックがスイッチ１０７からスイッチ１０９へ、およびその結果、ネットワーク１５１へ移動することを阻止するだけでなく、トラフィックがスイッチ１０７からスイッチ１０９さらにはホスト１１５へ移動することも阻止する。バッファツーバッファクレジットメカニズムは、ホスト１１５のような非輻輳宛先へ移動するトラフィックのブロッキングにつながりえる。ある例では、ホスト１１１は、輻輳したネットワーク１５１と通信しえる。ネットワーク１５１における輻輳のせいで、スイッチ１０９は、ホスト１１１からの大量のフレームをキューに入れ、その結果、バッファツーバッファクレジットメカニズムを用いて、ホスト１１１またはホスト１１３からのそれ以上のフレームをスイッチ１０７が送信しないようにする。
【００２１】
一方、ホスト１１３は、いくつかのフレームをホスト１１５に送信しようと単に試みているだけかもしれない。ネットワーク輻輳は、スイッチ１０７およびスイッチ１０９間のバッファツーバッファクレジットメカニズムをスイッチ１０９が実現するようにするので、真の輻輳点はネットワーク１５１であるにもかかわらず、スイッチ１０７およびスイッチ１０９を結合するリンクを通ってホスト１１３からホスト１１５へはフレームは移動できない。フレームは、ネットワーク１５１またはディスクアレイ１５３における輻輳のせいで、もはやホスト１１５へ、またはネットワーク１５１へ送信されえない。
【００２２】
フレームは一般に、レイヤ３パケット構成物（layer three packet constructs）を含むレイヤ２構成物（layer two constructs）であることに注意されたい。フレームおよびパケットは一般に、ネットワーク送信を記述するためにここでは同じ意味で用いられる。ここでの輻輳点はネットワーク１５１であるにもかかわらず、他の想定される輻輳の点は、ホスト１１５、またはスイッチ１０９に接続されたディスクアレイ１５３でありえる。
【００２３】
スイッチ１０７はもはやスイッチ１０９に送信できないので、スイッチ１０７は同じバッファツーバッファクレジットメカニズムをスイッチ１０３および１０５についても実現しなければならない。スイッチ１０３および１０５がもはやスイッチ１０７に送信できないとき、スイッチ１０３および１０５はバッファツーバッファクレジットメカニズムをスイッチ１０１について実現しなければならない。輻輳は結果としてネットワーク全体に波及しえる。波及する輻輳現象は、輻輳拡散とも呼ばれえる。
【００２４】
図２は、ヘッドオブラインブロッキングを描く簡略化されたネットワークの概略図である。図２において、送信元ノード２１１は、宛先ノード２１７へスイッチ２０１および２０３を通してデータを送信している。送信元ノード２１３は、宛先ノード２１９へスイッチ２０１および２０３を通してデータを送信している。宛先ノード２１７および２１９と共に送信元ノード２１１および２１３は、スイッチ、ホスト、外部ネットワーク、またはディスクのようなエンティティでありえる。ある例ではリンク２２１、２２３、および２２９はそれぞれ、毎秒１０バイトの送信が可能である。リンク２２５は、毎秒１００バイトの送信が可能である。しかしリンク２２７は毎秒１バイトの送信しか可能ではない。もし宛先ノード２１１および送信元ノード２１３の両方がそれぞれの宛先２１７および２１９に毎秒１０バイトで送信しているなら、リンク２２７は毎秒１バイトでしか送信できないので輻輳がスイッチ２０３で生じる。送信元ノード２１１からのパケットまたはフレームは、スイッチ２０３が宛先ノード２１７に対して充分なレートで送信できないために、スイッチ２０３において累積する。スイッチ２０３は、リンク２２５と関連付けられた共用メモリ２３１を持つ。スイッチ２０１は、リンク２２１および２２３と関連付けられた共用メモリ２３３および共用メモリ２３５をそれぞれ持つ。共用メモリおよびそれぞれのスイッチの輻輳特性のさらなる詳細は、図３を参照して以下に述べられる。
【００２５】
共用メモリの実現例において、スイッチ２０３は、リンク２２５から起こる全てのトラフィックのための共用メモリ２３１を持つ。この共用メモリ２３１は、宛先ノード２１７または宛先ノード２１９のいずれに向けられたパケットおよびフレームでも保存できる。もし宛先ノード２１７に向けられたパケットまたはフレームがスイッチ２０３に関連付けられた共用メモリを一杯にするなら、宛先ノード２１７または宛先ノード２１９のいずれかに向けられたフレームはもはやスイッチ２０３において受け付けられない。そうなるとスイッチ２０３は、バッファツーバッファクレジットメカニズムを用いて入ってくるさらなるトラフィックをブロックできる。バッファツーバッファクレジットメカニズムは、送信元２１１から宛先２１７への輻輳したパスに沿って流れるトラフィックだけでなく、送信元２１３から宛先２１９へのもともとは輻輳していなかったパスに沿ったトラフィックを遅くする。遅くされたトラフィックの結果、リンク２２５上の帯域幅が、ノード２１３およびノード２１９間のトラフィックを転送するのよりもより適しているにもかかわらず、ノード２１３はノード２１９へ毎秒１バイトしか送信できない。
【００２６】
本発明の技術は、輻輳を検出し、輻輳したパスに沿ったフローのトラフィックを減らしながら他のトラフィックフローを許しつづけることができる命令を生成するメカニズムを提供する。本発明の技術は、宛先に関係なくトラフィックを無差別にブロックする標準的なバッファツーバッファクレジットメカニズムを起動することを避けようと試みる。無差別ブロッキングは、変動するファイバチャネルの標準が存在するために、ファイバチャネルネットワークにおいては頻繁に起こりえる。ある例では、あるラインは毎秒１ギガビットを扱うように構成されえるが、一方、他のラインは毎秒２または１０ギガビットを扱うように構成されえる。
【００２７】
図３は、バッファツーバッファクレジットメカニズムと共に本発明の技術を実現できるスイッチの概略図である。スイッチ３０１は、外部ノード３５１、３５３、３５５、および３５７に接続される。スイッチ３０１は、それぞれのスイッチポートに関連付けられた共用メモリであるバッファ３０３を含む。バッファ３０３は、外部ノード３５１に関連付けられる。外部ノード３５３、３５５、および３５７に関連付けられたバッファは、簡潔さのために示されない。バッファ３０３は、外部ノード３５３、３５５、３５７が宛先のトラフィックをホールドでき、外部ノード３５１へのトラフィックをループバックできる。
【００２８】
典型的な実現例では、さまざまな外部ノードが宛先のフレームは全て同じバッファ３０３に置かれる。その結果、外部ノード３５３のような特定のノードが宛先の大量のフレームをスイッチ３０１が受け取るとき、外部ノード３５３に関連付けられたフレームはバッファ３０３全体を消費しえる。バッファ３０３がフルのとき、外部ノード３５１からのさらなるトラフィックはブロックされるが、それはスイッチ３０１が追加のクレジットを外部ノード３５１に割り当てないからである。外部ノード３５３が宛先のトラフィックは、他の非輻輳外部ノード群のうちいずれかが宛先のトラフィックと共にブロックされる。
【００２９】
さまざまな実施形態によれば、バッファ３０３に格納されたフレームは、フレーム記述子キュー３１１〜３４７中のポインタによって参照される。それぞれのフレーム記述子は、バッファ３０３中のどこにフレームが格納されているかを特定するポインタまたは参照を含みえる。共用バッファへのポインタまたは参照は、ここでは記述子と呼ばれる。記述子はまた、フレーム優先度のような他の情報を特定することもできる。
【００３０】
ある例では、アービトレータ３０５は、ラウンドロビン法を用いてフレームを選択する。第１ラウンドで、外部ノード３５３が宛先のフレームが選択される。第２ラウンドでは外部ノード３５５が宛先のフレームが選択される、などのようになる。より具体的には、アービトレータ３０５は、外部ノード３５３が宛先である記述子３１１に関連付けられた高優先度のフレームをまず選択し、外部ノード３５５が宛先である記述子３２１に関連付けられた高優先度のフレームをそれから選択し、外部ノード３５７が宛先である記述子３３１に関連付けられた高優先度のフレームを次に選択する、などのようになる。当業者には理解されるように、フレームを選択するためのさまざまな技術が使用されえることに注意されたい。
【００３１】
宛先に基づいて割り当てられたバッファを持つキューイングシステムは、仮想出力キュー（ＶＯＱ）と呼ばれる。ＶＯＱは、Tamir Y., Frazier G.らの「High Performance multi-queue buffers for VLSI communications switches」、Proc. Of 15th Ann.Symp.On Comp. Arch.,pp.343-354, June 1988にさらに記載され、その全体が全ての目的のためにここで参照によって援用される。上述のように、特定の外部ノードに関連付けられた共用バッファ空間が、特定の宛先に宛てられたトラフィックのためにフルになるとき、その特定の外部ノードから任意の宛先に宛てられた全てのトラフィックはブロックされる。これは、トラフィックが以前には非輻輳である宛先へと流れることさえ阻止しえ、輻輳が波及することを引き起こしえる。その結果、ターゲットフロー上の輻輳を検出し特に緩和するための技術を提供することが望まれる。特定の特性を持つ２つのノード間のトラフィックを示す抽象化された概念をここではフローと呼ぶ。ある例では、フローは、送信元識別子、宛先識別子、優先度、クラス、および交換識別子によって参照される。他の特性も可能である。しかしフローは送信元および宛先識別子だけによって参照されてもよいことに注意されたい。
【００３２】
図４は、輻輳検出に用いられるテーブルである。図４は、輻輳を緩和するための命令が生成されるべきときを示す値を持つテーブルを示す。輻輳したネットワークノードからネットワーク中の他のノードに送信される輻輳緩和のためのメッセージおよび命令は、抑制メッセージとここでは呼ばれる。
【００３３】
テーブル４０１中のカラム４０３は、抑制メッセージが生成されえるスイッチのバッファレベルを示す。バッファレベルカラム４０３は、抑制メッセージ生成の間に受信された、受信フレームの数を示すインターバルカラム４０５と関連付けられる。ロウ４１１は、５１２個のパケットをホールドできるバッファ内のパケットの数が０および１０の間にあるとき、抑制メッセージが生成されないことを示す。パケットの数が１１および１５の間のとき、２６０フレーム毎に一つの抑制メッセージが生成される。キュー中のパケットの数が１１２および１２７の間のとき、６つのフレームが処理された後に一つの抑制メッセージが生成される。抑制メッセージ生成の間のインターバルを決定する一つの式は次の通りである。
【００３４】
Ｘ＝５１２個のパケットのバッファ容量に基づくパケットによるバッファレベル
Ｎ＝抑制メッセージ生成間のインターバル
もしＸ／１６≧８ならＮ＝４、そうでなければＮ＝４＋２＾（８−（Ｘ／１６））
【００３５】
当業者には理解されるように、さまざまな異なる方程式が用いられえる。方程式は、バッファ容量またはサービスパラメータのネットワーク品質に基づいて変化しえる。
【００３６】
図４に示されるテーブルは、いつ抑制メッセージを生成すべきかを決めるための決定論的手法を提供する。さまざまな他の技術も用いられえることに注意されたい。ある例では、それぞれのバッファレベルは、抑制メッセージ生成の確率に関連付けられえる。例えばバッファレベルが８０パーセントに達するとき、フレームを受信して抑制メッセージが生成されるのは７０パーセントの確率である。バッファレベルが５０パーセントの容量に達するとき、フレームを受信して抑制メッセージが生成されるのは１０パーセントの確率である。バッファレベルが１０パーセントの容量に達するとき、フレームを受信して抑制メッセージが生成されるのは０．０１パーセントの確率である。
【００３７】
しかし決定論的手法は、非決定論的手法に比べていくつかの利点を提供する。特に決定論的手法は、抑制メッセージのバーストを発生することを防ぐ。ランダム確率関数を用いると、いくつかの抑制メッセージは、乱数発生器の特性に基づいて近接して発生されえる。抑制メッセージのバーストは、トラフィックの低減に対して大きすぎる影響を与えかねず、バースト間のラグは救済されない輻輳につながりえる。決定論的手法はよりバースティではないようになりえる。しかし非決定論的手法も、抑制メッセージバーストを最小化するために、より複雑な制御アルゴリズムを使用できることに注意されたい。
【００３８】
抑制メッセージの送信のための間隔および頻度を決定するために多くのテーブルおよび多くの異なる値が用いられえる。テーブルの値を設定するファクタは、ネットワークサイズ、出力ポートの数、バッファサイズ、および遅延許容範囲を含みえる。抑制メッセージは、トラフィックの性質がバースティであるときには、より頻繁に生成されえる、一方、抑制メッセージはトラフィックがより定常であるときには、より頻繁ではないように生成されえる。さまざまな実施形態によれば、抑制メッセージのための頻度および間隔は、バッファサイズそのものではなく、バッファサイズにおける変化またはバッファサイズにおける変化の微分に依存しえる。もしバッファレベルが急速に大きくなっているなら、抑制メッセージはより頻繁に生成されえる。ある例では、バッファレベルが充分に速い速度で大きくなっているなら、連続した抑制メッセージがすぐに生成されえる。
【００３９】
図５は、輻輳を検出する手法を示すプロセスフロー図である。５０１においてフレームは上流の外部ノードから受信される。５０３において、フレームは、特定の外部ノードに関連付けられたバッファ内の正しいキューに分類される。分類器（classifier）ロジックは、宛先ポート、優先度、および送信元および宛先アドレスのようなさまざまなパラメータを使用して、フレームを正しいキューに置きえる。５０５において、特定の外部ノードに関連付けられたバッファのレベルが決定される。
【００４０】
５０７において、バッファレベル決定を用いて、図４に示されるようなデータ構造が参照され、抑制メッセージが送信されるフレーム間隔が見つかる。ある例では、抑制メッセージはＮフレームが受信された後に送信される。すなわち、スイッチは、その上流外部ノードへ抑制メッセージを送信する前に、その上流外部ノードからさまざまな外部ノードへＮフレーム送信できる。５０９において、最後の抑制メッセージが生成されてからＮフレーム以上が転送されたかどうか決定される。もしＮフレーム間隔が経ったなら、５１１においてバッファレベルが低スレッショルド未満であるかどうかが決定される。もしバッファレベルが低スレッショルド未満であるなら、抑制メッセージは生成されず、フレームは５１３において送信スケジューリングのためにキューイングされる。そうでなければ、抑制メッセージは５１５で生成される。抑制メッセージは上流外部ノードに送信される。上流外部ノードから受信されたフレームは、フレーム中の宛先識別子によって示された宛先ノードへ向けた送信スケジューリングのためにキューイングされる。
【００４１】
抑制メッセージが生成されるときを決定するさまざまな手法が考えられることに注意されたい。例えば抑制メッセージは、周期的な時間間隔で生成されえる。すなわち、抑制メッセージは、一定の期間が経過した後に生成されえる。周期的時間間隔は、所定のものとして設定されても動的に設定されてもよい。バッファレベルも抑制メッセージが生成される時間間隔を支配するために用いられえる。バッファレベルが高いとき、抑制メッセージは、より小さい時間間隔でより頻繁に生成されえる。バッファレベルが低いとき、抑制メッセージが生成される前には、より大きい時間間隔が経過しえる。他の例では、抑制メッセージは、同じフローに関連付けられたフレームの数がバッファの特定のセットされた部分を超えるときに生成されえる。ある例では、バッファの５０パーセントより多くの部分が同じ送信元および宛先のペアに関連付けられたフレームで満たされるとき、抑制メッセージが生成され、送信元ノードに送信されえる。さらに他の実施形態においては、抑制メッセージは、ある送信元ノードから多数のフレームを小さい時間間隔で受信するとランダムに生成されえる。
【００４２】
バッファおよびバッファ内のフレームの特性を分析することによって、抑制メッセージは必要に応じて生成され、特定のフローに向けて導かれえる。抑制メッセージは、特定のフローについてサービス品質を提供するためにも用いられえる。例えば、バッファの特定のパーセンテージは、クリチカルな外部ノードからの優先度の高いトラフィックについてのフレームを受信するために予約されえる。もしバッファレベルが確保されたレベルに近づくと、抑制メッセージが生成され、優先トラフィックに関連付けられていないさまざまなフローに送信されえるか、または抑制メッセージが生成され、非クリチカル外部ノードに送信されえる。優先トラフィックがクリチカル外部ノードから受信されるときは、バッファレベルがほとんど全部がフルになるまで抑制メッセージが生成されない。予約されたバッファ部分は、複数の外部ノードについての複数のフローに割り当てされえる。ある例では、出力バッファの２５パーセントを４つの外部ノードのそれぞれに提供することがゴールでありえる。ある特定の外部ノードに関連付けられたバッファの部分が３５パーセントを超えるときか、またはバッファ全体のレベルが８０パーセントを超えるとき、抑制メッセージは生成されえる。それから抑制メッセージは、バッファレベルが８５または９０パーセントを超えるときにより頻繁に生成されえる。サービス品質を提供するためのさまざまなメカニズムは、抑制メッセージの生成を用いて実現されえる。バッファレベルの分析および特性に関する情報も抑制メッセージ中に提供されえる。
【００４３】
さらにより正確な輻輳制御は、異なる抑制メッセージを用いることによって、またはそれぞれの抑制メッセージ中の情報を提供することによって実現されえる。図６は、バッファまたはキューレベルに基づいて輻輳したスイッチにおけるさまざまな抑制メッセージの生成を描く図である。バッファレベルが高スレッショルド６０７を超えると、パス抑制（path quench）が生成されえる。パス抑制は、送信元ノードおよび輻輳したスイッチの間の全てのスイッチが、特定のフローに関連付けられた輻輳スイッチに向けられたトラフィックを送信するのをすぐに止めるよう指示する。パス抑制は、輻輳スイッチにおけるバッファレベルが容量に近く、かつクレジットおよびバッファツーバッファクレジットメカニズムの枯渇を防ぐために即時のトラフィック低減が必要なときに使用されえる。高スレッショルドは、バッファサイズとクレジットの枯渇を避ける重要性とに基づいて変わりえる。ある例では、高スレッショルドはバッファサイズの９０パーセントに設定される。
【００４４】
もしバッファレベルが高スレッショルド６０７および低スレッショルド６０３の間にあるなら、エッジ抑制メッセージ（edge quench message）が輻輳スイッチによって生成されえる。このエッジ抑制メッセージは、送信元ノードに最も近い輻輳制御スイッチが、その輻輳したスイッチへのトラフィックフローを減らすよう指示する。トラフィックフローを減らすために他のネットワークノードからのインストラクション（instructions）を認識できるネットワークノードは、ここでは輻輳制御スイッチと呼ばれる。エッジ抑制メッセージは、特定の送信元ノードからのトラフィックフローを徐々に減らすことができる。抑制メッセージの生成を阻止するためにカットオフスレッショルド６０１も提供されえる。抑制メッセージを送信しないことによって、抑制メッセージが不必要なときには輻輳制御および他のトラフィックの低減が避けられる。
【００４５】
抑制メッセージは、バッファレベルについての情報も含みえる。ある例では、パス抑制（path quench）およびエッジ抑制（edge quench）メッセージは、バッファレベルがターゲットまたは平衡レベルを超えるかどうかについての情報を提供する指示子（indicator）を含む。ターゲットまたは平衡レベル６０５は、特定の輻輳制御スイッチにおける最大スループットを提供する最適なバッファレベルでありえる。もしバッファレベルがターゲットレベル６０５より上、または下であるなら、輻輳制御スイッチがさまざまな時刻においての送信レートをよりよく決定できるようにするため、その情報は輻輳制御スイッチに送信されえる。ある例では、もしバッファレベルがターゲットレベル６０５より上なら、輻輳制御スイッチはそのフローに関連付けられたその送信レートを下げ、調整のあと送信レートを徐々に上げるよう選択しえる。あるいは、もしバッファレベルがターゲットレベル６０５より下なら、輻輳制御スイッチはそのフローに関連付けられたその送信レートを下げ、調整のあと送信レートをより急激に上げるよう選択しえる。
【００４６】
現在および過去のバッファレベル情報は、輻輳制御スイッチに提供されえる。ある実施形態においては、バッファレベルにおける変化も輻輳制御スイッチに提供されえる。もしバッファレベルが増加しているなら、輻輳制御スイッチは、そのフローに関連付けられたその送信レートを減少させ、より低い送信レートを維持し、その後、ある期間が経過した後で徐々にその送信レートを上げるよう選択しえる。
【００４７】
図６は、パス抑制またはエッジ抑制メッセージを送るかどうかを決定する高および低スレッショルドを示すが、さまざまな個数のスレッショルド群が用いられえることに注意されたい。ある例では、パス抑制は、その輻輳したスイッチおよび送信元ノードの間の全ての輻輳制御スイッチが、特定のフローに関連付けられた送信レートを０に落とすよう指示する。エッジ抑制は、送信元ノードに最も近い輻輳制御スイッチが特定のフローに関連付けられた送信レートを以前に許されたレートの半分に落とすよう指示する。他の例では、３つの異なるスレッショルドに対するバッファレベル群の比較に基づいて、３つのタイプの抑制メッセージ群が用いられる。
【００４８】
パス抑制は、その輻輳したスイッチおよび送信元ノードの間の全ての輻輳制御スイッチが特定のフローに関連付けられた送信レートを０に落とすよう指示しえる。しかしこの場合のリカバリレートは急速でありえることに注意されたい。エッジ抑制は、送信元ノードに最も近い輻輳制御スイッチが、送信レートを許されたレートの半分に落とすよう指示する。ある実施形態においては、エッジ抑制およびパス抑制メッセージは、バッファ特性情報を含まなくてもよい。他の実施形態においては、抑制メッセージがバッファレベルの現在、過去、および変化についての充分な情報を含む、単一の抑制メッセージが用いられえる。ホストはパス抑制またはエッジ抑制メッセージを理解できないかもしれないので、抑制メッセージは、さまざまな実施形態によればネットワークのエッジにおいて止められるべきである。
【００４９】
図７は、輻輳したスイッチにおいて生成されえる抑制メッセージの概略図である。輻輳したスイッチはフレーム７００を特定する。フレーム７００は、ランダムに選択されるか、またはＮフレーム間隔の後に選択されたフレームでありえる。フレーム７００は、パケットヘッダ７０３およびパケットペイロード７０５を含む。パケットヘッダ７０３は、アドレスＡを持つ宛先識別子７１１およびアドレスＢを持つ送信元識別子７１３を含む。パケットヘッダは、タイプ７１５、パラメータ情報７２１、さらにＯＸ＿ＩＤ  ７１７も含む。送信パスに沿ったそれぞれのスイッチは、次のホップを決定するために送信元識別子７１３、宛先識別子７１１、およびＯＸ＿ＩＤ  ７１７を使用できる。パケットペイロード７０５は、宛先ノードによって抽出されるデータ７２３を含みえる。
【００５０】
典型的には輻輳制御スイッチそのものであり、輻輳したスイッチはアドレスＡを持つ宛先識別子およびアドレスＢを持つ送信元識別子を取り、２つの値を交換することによって、抑制メッセージ７５０がアドレスＢに設定された宛先識別子７７１およびアドレスＡに設定された送信元識別子７７３を含むようにする。抑制メッセージパケットヘッダ７５３は、フレームがパス抑制またはエッジ抑制のような抑制メッセージであることを示すタイプ７７５を含む。フレームがパスまたはエッジ抑制メッセージであることを示すのに用いられる値は、タイプフィールド７７５についてのベンダーに特有の値のセットでありえる。さまざまな実施形態によれば、抑制メッセージパケットは、バッファ特性情報を含むＯＸ＿ＩＤ  ７１７およびパラメータ情報７８１とは異なるＯＸ＿ＩＤ  ７７７も含みえる。異なるＯＸ＿ＩＤ  ７７７を持つことによって、送信元識別子７７３、送信元識別子７７１、およびＯＸ＿ＩＤを用いたパス選択は、異なるパスを生成する。異なるＯＸ＿ＩＤはランダムに選択されえる。パケットペイロード７５５を参照して、抑制メッセージはデータ７８３を何も含まなくてもよい。
【００５１】
図８は、抑制メッセージの生成を描くフロープロセス図である。さまざまな実施形態によれば、上述のように他の手法も用いられえるが、最後の抑制メッセージが生成されてから受信されたＮ番目のフレームに関連付けられたフローは抑制のために選択される。８０３において、フレーム送信元識別子Ｓおよびフレーム宛先識別子Ｄが抽出される。８０５において、どのタイプの抑制メッセージを生成すべきか決定するだけでなく、輻輳したスイッチおよび送信元ノード間の輻輳制御スイッチに情報を提供するためにも、バッファは特徴付けられえる。
【００５２】
８０５において、もしバッファレベルが高スレッショルドより上であると決定されるなら、Ｄに設定された送信元識別子およびＳに設定された宛先識別子を持つパス抑制メッセージが８２１において生成される。バッファ特性付け情報（buffer characterization information）は、他のパラメータ情報と共に、８２５において抑制メッセージに付加されえる。抑制メッセージはそれから、８２７においてファイバチャネルを用いて送信スケジューリングのためにキューイングされえる。あるいは、Ｄに設定された送信元識別子およびＳに設定された宛先識別子を持つエッジ抑制メッセージが８２３において生成される。バッファ特性付けおよびパラメータ情報は同様に、８２５においてエッジ抑制メッセージに付加されえ、抑制メッセージはファイバチャネルを用いて最終的に転送されるよう８２７においてキューイングされえる。
【００５３】
図９は、パス抑制またはエッジ抑制フレームのような抑制メッセージを受信できるネットワークノードを含むネットワークの概略図である。上述のように、輻輳制御スイッチ９０９は、受信されたフレームの送信元および宛先識別子を交換することによって抑制メッセージを生成できる。ある例では、受信されたフレームの送信元は、ホスト９１１であり、一方、受信されたフレームの宛先はネットワーク９５１のノードでありえる。フレームは、スイッチ９０９へスイッチ９０１、９０３、および９０７を通って移動したかもしれない。輻輳制御スイッチ９０９は、上述のように抑制メッセージを生成しえる。抑制メッセージは、ホスト９１１に設定された宛先およびネットワーク９５１のノードに設定された送信元を持つだろう。もしパス抑制メッセージが生成されるなら、パス抑制メッセージが転送されるそれぞれの輻輳制御スイッチは、輻輳制御メカニズムを実現しえる。この例では、輻輳制御スイッチ９０７、９０３、および９０１がそれぞれ輻輳制御を実現する。
【００５４】
パス抑制メッセージは、スイッチ９０３の代わりにスイッチ９０５に転送されえることに注意されたい。もしパス抑制が、輻輳制御スイッチ９０１に到達する前に、９０３への代わりにスイッチ９０５へ転送されるなら、輻輳制御スイッチ９０５は抑制メッセージを無視しえるが、これはそれが、ホスト９１１に設定された送信元およびネットワーク９５１に設定された宛先を持つフレームが輻輳制御スイッチ９０５を通って送信されなかったことを認識できるよう構成されえるからである。そうであっても輻輳制御はやはり実現されえる。
【００５５】
もしエッジ抑制メッセージが生成されるなら、ホスト９１１に最も近いスイッチは、輻輳制御メカニズムを実現する。エッジ抑制は輻輳制御スイッチ９０７に転送され、その後、輻輳制御スイッチ９０３または輻輳制御スイッチ９０５のいずれかに転送され、これらの全てはエッジ抑制メッセージを無視する。輻輳制御スイッチ９０１は、それがホスト９１１に結合されていることを認識できるので、その結果、エッジ抑制メッセージに関連付けられた輻輳制御メカニズムを実現するだろう。
【００５６】
図１０は、輻輳制御スイッチが、抑制メッセージを生成するフレームを送信したホストに直接に結合されていない、パス抑制のような抑制メッセージを受信できるネットワークノードを含むネットワークの概略図である。この例において、ホスト１０１１は、フレームをネットワーク１０５１に向けて送信し、その結果、輻輳制御スイッチ１００９においてエッジ抑制メッセージの生成を生じた。輻輳制御スイッチ１００９は、エッジ抑制メッセージをホスト１０１１に向けて輻輳制御スイッチ１００７を通して送信する。輻輳制御スイッチのそれぞれにおいて、宛先は、輻輳制御スイッチがホスト１０１１に最も近いものであるかについての決定がなされえる。
【００５７】
輻輳制御スイッチがそれがホスト１０１１に最も近いかどうかを決定できるようにするためにはさまざまなメカニズムが用いられえる。ある例では、もし輻輳制御スイッチがホスト１０１１と同じドメインにあるなら、特定のスイッチにおいて輻輳制御はすぐに実現されえる。ドメイン情報は、抑制メッセージ中に提供されえ、輻輳制御スイッチ中の任意のドメイン情報と一致判定されえる。他の例では、輻輳制御スイッチは、近接スイッチおよびそれらに関連付けられたドメインのリストを保持しえる。さらに他の実施形態では、トポロジ情報が、どの近接ノードが輻輳制御スイッチであるかについての特定のデータと共に記憶されえる。輻輳制御スイッチがエッジ抑制制御メカニズムを実現すべきかどうかを決定できるようにするために、ストレージエリアネットワークのトポロジマップのような全体のトポロジマップが保持されえる。
【００５８】
トポロジ情報は、グラフ、テーブル、および他のネットワークノードからの個々のリンク制御情報フレームを含むさまざまなフォーマットで保持されえる。トポロジマップの方法および装置は、Andrew S. Tanenbaumによる「Computer Networks」（ISBN: 0133499456）に記載されており、その全体が全ての目的のために参照によって援用される。ファイバチャネルネットワークにおいては、ファブリックコンフィギュレーションサーバ（ＦＣＳ）と呼ばれるプロトコルが物理的なトポロジの発見を可能にする。
【００５９】
図１１は、抑制メッセージを転送する手法を示すプロセスフロー図である。１１０１において、抑制メッセージは輻輳制御スイッチにおいて受信される。優先度、送信元識別子、宛先識別子、ポート、およびバッファレベル情報のようなフローパラメータは、輻輳制御のために抽出されえる。１１０５において、抑制メッセージによって示される宛先の前に他の輻輳制御スイッチが存在するか決定される。上述のように輻輳制御スイッチは、パス抑制およびエッジ抑制メッセージのような抑制メッセージを識別するスイッチでありえる。１１０７において、他の輻輳制御スイッチが宛先の前に存在するので、抑制メッセージは、それがパス抑制であるかまたはエッジ抑制メッセージであるかにかかわらず、ファイバチャネルを用いた送信スケジューリングのためにキューされる。１１０９において、抑制メッセージがエッジ抑制であるかが決定される。もし抑制メッセージがエッジ抑制であるなら、他のアクションが取られる必要はない。そうでなければ、メッセージはパス抑制であり、輻輳制御に関連するパラメータは１１１１において記憶される。
【００６０】
ある例では、抑制パラメータは、輻輳制御スイッチに関連付けられたフィルタまたはコントローラ中に１１１１において記憶されえる。１１１３において、もしそのインストラクションがエッジ抑制メッセージであるなら、特定のパラメータ情報に関連付けられたフローの送信のための現在許容されるレートが半分に低減される。さまざまな実施形態によれば、それぞれのフローは、最大許容レートを持ちえる。そうでなければ、そのパラメータ情報に関連付けられたフローについての現在許容されるレートは０に落とされる。特定のフローについての最大送信レートは、ここでは最大許容レートと呼ばれる。抑制インストラクションによって調整された送信レートは、ここでは現在の許容レートと呼ばれる。ある実施形態において送信レートは、最初は最大許容レートであり、抑制インストラクションを受け取ると現在の許容レートに低減される。現在の許容レートはそれから、それが他の抑制インストラクションを受信するか、または最大許容レートに達するかするまで、リカバリレートにおいて増大する。この例では、２つのタイプの抑制メッセージが用いられることに注意されたい。さまざまな実施形態によれば、エッジ抑制メッセージは、宛先に最も近い輻輳制御スイッチにおいて許容レートを半分に落とす。パス抑制メッセージは、宛先に向かうパスに沿った全ての輻輳制御スイッチにおいて許容レートをゼロに落とす。
【００６１】
図１２は、輻輳制御スイッチの一例の概略図である。輻輳制御スイッチ１２０１は、外部ノード１２５１、１２５３、１２５５、および１２５７に結合される。しかし外部ノード１２５１からフレームを受信するバッファだけが簡明さのために示される。フレームがスイッチ１２０１において外部ノード１２５１から受信されるとき、分類器ロジック１２９９は、フレームを共用バッファプール（shared buffer pool）１２０３に置き、それを記述子またはポインタ１２１１〜１２４７で参照する。記述子はフレーム優先度を示す情報と関連付けられえる。
【００６２】
さまざまな実施形態によれば、本発明の手法は、受信された抑制メッセージに対応するフレームのためのフィルタキュー１２６１〜１２７７を提供する。フィルタ１２０９は、パス抑制またはエッジ抑制メッセージのような抑制メッセージから抽出された抑制パラメータを保持する。アービトレータ１２０５は典型的には、送信のためのフレームをラウンドロビン法を用いて選択するが、ＦＩＦＯおよびランダムのような他の方法も用いられえる。フレームが、バッファ１２０３から外部ノードへの送信のためにアービトレータ１２０５によって選択されるとき、フィルタ１２０９は、選択されたフレームのパラメータを受信された抑制メッセージに関連付けられた抑制パラメータと比較する。ある実施形態においては、フィルタは、３２セットの抑制パラメータおよび選択されたフレームのパラメータ間の３２の同時比較を実行する。３２セットの抑制パラメータのうちの一つと一致するフレーム記述子は、フィルタキュー１２０７中の３２の異なるキューのうちの一つの中に置かれる。
【００６３】
もし送信元および宛先アドレス対、出力ポート、優先度、および／または他のパラメータが対応するなら、フレーム記述子は、フィルタキュー内への格納のために選択されえる。記述子は、共用バッファプール１２０３を変えることなく、入力キュー１２１１〜１２４７のうちの一つからフィルタキュー１２６１〜１２７７へ移動されえる。もしフレームのパラメータがフィルタ１２０９に保持されたパラメータに対応しないなら、フレーム記述子は、外部ノード１２５３、１２５５、１２５７、および１２５１のような外部ノードへ転送されえる。そうでなければ、フレームは、レートリミッタに関連付けられたフィルタキュー内に置かれえる。ある例ではフィルタフレームは、レートリミッタ１２８１に関連付けられたフィルタキュー１２６１内に置かれる。レートリミッタ１２８１は、フィルタキュー１２６１内の記述子に関連付けられたフレームが現在の許容レートに基づいて送信されえるときを決定する。
【００６４】
図１３は、抑制メッセージの受信に基づく１つ以上のレートリミッタに関連付けられた許容レートの考えられる変化を示すグラフである。上述のようにある実施形態においては、パス抑制メッセージは、許容されたレートをゼロに低減し、一方、エッジ抑制メッセージは、その許容されたレートを半分に低減する。グラフによれば、１３０１において受信されたエッジ抑制は、許容されたレートを半分に低減する。１３０１および１３０３の間では、許容されたレートは、スイッチコントローラによって決定されえるリカバリレートで徐々に増加する。リカバリレートは、予め定められたレートでもよく、または抑制メッセージ中で与えられるバッファレベル特性付け情報のような情報に基づく動的に設定されるレートでもよい。
【００６５】
ある例では、輻輳したスイッチのバッファレベルが平衡点に対して低いことをバッファレベル特性付け情報が示すとき、リカバリレートは増加されえる。あるいは輻輳したスイッチのバッファレベルが平衡点に対して高いことをバッファレベル特性付け情報が示すとき、リカバリレートは減少されえる。１３０３において、レートリミッタに関連付けられた他のエッジ抑制メッセージが受信される。許容されたレートは再び１３０３において半分に減少される。１３０３および１３０５の間で、バッファレベル特性付け情報のようなファクタのために、減少されたリカバリレートが適用される。１３０５において、パス抑制メッセージが受信され、許容されたレートはゼロに低減される。増加されたレートは、１３０５および１３０７の間で適用される。許容されたレートは、１３０７において最大許容またはラインレートに達し、フィルタキューはこの時点で解放されえる。
【００６６】
図１４は、抑制メッセージを受信するスイッチにおける輻輳制御の実現法を示すプロセスフロー図である。１４０１において、フレームが特定される。１４０３において、フレームパラメータはフィルタ中のパラメータと比較される。比較されるパラメータは、送信元および宛先アドレス、優先度、および出力ポートを含みえる。もしパラメータが１４０３において一致するなら、フレーム記述子は、レートリミッタと関連付けられたフィルタキュー内に１４０７において置かれる。フィルタキューは、フレームの送信を遅らせることができる。レートリミッタは、トークンバケット、リーキーバケット、および仮想時間レートリミッタを含むさまざまなメカニズムを用いて実現できる。レートリミッタによって用いられるレートは、受信された抑制メッセージのタイプおよび抑制メッセージ中のバッファレベル特性付け情報に基づいて設定されえる。１４０９において、レートリミッタは、許容されたレートに基づいてフレームの送信を制御しえる。送信を制御することは、フレームの送信を遅延させることも含む。１４０５において、フレームは、ファイバチャネルを用いた転送のためにキューされる。もし特定されたフレームのパラメータがフィルタ内のパラメータと１４０３において一致しないなら、フレームは、ファイバチャネルを用いた即時転送のために１４０５においてキューされえる。
【００６７】
本発明は、その特定の実施形態を参照して示され記述されてきたが、開示された実施形態の形態および詳細の変更が本発明の精神または範囲から逸脱することなくなされえることが当業者には理解されよう。例えば、本発明の実施形態は、さまざまなネットワークプロトコルおよびアーキテクチャで実現されえる。抑制メッセージのようなインストラクションは、さまざまな異なる時刻において送られえる。したがって本発明は、本発明の精神および範囲に入る全ての改変物および等価物を含むように解釈されるよう意図される。
【図面の簡単な説明】
【００６８】
【図１】本発明の技術を用いえるネットワークの概略図である。
【図２】ヘッドオブラインブロッキングを示す概略図である。
【図３】輻輳制御の一例を実現できるスイッチの概略図である。
【図４】バッファレベルに基づいてどのくらい頻繁に抑制メッセージが生成されえるかを示すテーブルである。
【図５】輻輳を検出するスイッチを示すプロセスフロー図である。
【図６】抑制メッセージの生成に用いられえる抑制レベルのグラフである。
【図７】生成されえるエッジ抑制またはパス抑制メッセージの概略図である。
【図８】エッジ抑制またはパス抑制メッセージの生成および送信を示すプロセスフロー図である。
【図９】輻輳制御を実現できるネットワークの概略図である。
【図１０】輻輳制御を実現できる混合ネットワークの概略図である。
【図１１】抑制メッセージを転送する手法を示すプロセスフロー図である。
【図１２】抑制メッセージ受信と共に輻輳制御の可能な実現例を実現できるスイッチの概略図である。
【図１３】受信されたエッジ抑制およびパス抑制メッセージに基づいて変化する許容されたレートのグラフである。
【図１４】輻輳制御の実現を示すプロセスフロー図である。
【図１】
2005535154.tif 000003
【図２】
2005535154.tif 000004
【図３】
2005535154.tif 000005
【図４】
2005535154.tif 000006
【図５】
2005535154.tif 000007
【図６】
2005535154.tif 000008
【図７】
2005535154.tif 000009
【図８】
2005535154.tif 000010
【図９】
2005535154.tif 000011
【図１０】
2005535154.tif 000012
【図１１】
2005535154.tif 000013
【図１２】
2005535154.tif 000014
【図１３】
2005535154.tif 000015
【図１４】
2005535154.tif 000016
【国際調査報告】
2005535154.tif 000017
2005535154.tif 000018
2005535154.tif 000019