(57)【特許請求の範囲】
【請求項１】
出力帯域幅を有する一つまたは複数のノードの双方向リングネットワークに対するアクセスを管理するための方法であって、
輻輳した下流リンクを含む輻輳スパンの先頭に位置するヘッド・ノードを識別することを含み、前記一つまたは複数のノードを輻輳スパンの一部として識別するステップと、
前記一つまたは複数のノードの前記出力帯域幅を調整するステップであって、該ステップは、
前記ヘッド・ノードにおいて、
前記輻輳に寄与するノードの数の関数としてターゲット・レートを初期設定するステップと、
前記帯域幅の利用度をモニタし、該帯域幅の利用度の関数として前記ターゲット・レートを調整する、モニタおよび調整ステップと、
所定の時間に、前記輻輳スパンの前記下流リンクにおける輻輳に寄与するノードの追加レートを調整するため宣伝レートとして前記ターゲット・レートを上流ノードに送るステップと、
を含む、前記アクセスを管理する方法。
【請求項２】
前記識別するステップは、トラフィックをモニタし前記輻輳した下流リンクを検出すること、および前記輻輳した下流リンクを検出するノードを前記ヘッド・ノードとして識別することを含む、請求項１に記載の方法。
【請求項３】
前記出力帯域幅を調整するステップは、前記ヘッド・ノードにおいて、該ヘッド・ノードの追加レートを前記ターゲット・レートの関数として設定することを含む、請求項２に記載の方法。
【請求項４】
前記出力帯域幅を調整するステップは、前記ヘッド・ノードにおいて、前記ターゲット・レートがしきい値に達するまで、前記モニタおよい調整ステップ、前記送るステップ、および前記追加レートを設定するステップを繰り返す、請求項３に記載の方法。
【請求項５】
前記帯域幅の利用度をモニタし、該帯域幅の利用度の関数として前記ターゲット・レートを調整するステップは、
前記下流リンクの利用度を測定し、前記ターゲット・レートを前記下流リンクの利用度の関数として調整するステップを含む、
請求項１に記載の方法。
【請求項６】
前記ターゲット・レートを前記下流リンクの利用度の関数として調整するステップは、該下流リンクが第１の予め定めた所望の利用度レベルを超えて使用されることに応じて、前記ターゲット・レートを低減させることを含む、請求項５に記載の方法。
【請求項７】
前記ターゲット・レートを前記下流リンクの利用度の関数として調整するステップは、該下流リンクが第２の予め定めた所望のレベルに満たないで使用されることに応じて、前記ターゲット・レートを増大させることを含む、請求項５に記載の方法。
【請求項８】
前記第１の予め定めた所望の利用度レベルが前記下流リンクの最大帯域幅の関数として定められている、請求項６に記載の方法。
【請求項９】
前記第２の予め定めた所望の利用度レベルが前記下流リンクの最大帯域幅の関数として定められている、請求項７に記載の方法。
【請求項１０】
前記出力帯域幅を調整するステップが、ヘッド・ノードにおいて、該ヘッド・ノードの追加レートを前記ターゲット・レートの関数として設定することを含む、請求項６または７に記載の方法。
【請求項１１】
前記出力帯域幅を調整するステップが、
前記ターゲット・レートをしきい値と比較するステップと、
前記ターゲット・レートが前記しきい値に達するまで、前記モニタおよび調整ステップ、前記送るステップ、および前記追加レートを設定するステップを繰り返す、請求項１０に記載の方法
【請求項１２】
前記出力帯域幅を調整するステップが、
前記ヘッド・ノード以外の一つまたは複数のノードにおいて、
その下流リンクから下流（DS）レートとして宣伝レートを受け取るステップと、
トラフィックをモニタするステップと、
前記モニタの結果に基づいて前記宣伝レートをその上流リンクに送るステップと、
を含む請求項１に記載の方法。
【請求項１３】
前記識別するステップが、前記輻輳スパンにおいてチェーン・ノードまたはテール・ノードを識別することを含む、請求項１に記載の方法。
【請求項１４】
前記出力帯域幅を調整するステップが、
前記チェーン・ノードにおいて、
その下流リンクから前記宣伝レートを下流（DS）レートとして受け取り、
上流リンクのノードの前記追加レートを調整するため、前記宣伝レートを前記上流リンクに送ることを含み、
前記テール・ノードにおいて、
その下流リンクから受け取った前記宣伝レートの送出を停止すること、
を含む、請求項１３に記載の方法。
【請求項１５】
前記出力帯域幅を調整するステップが、
前記ヘッド・ノードにおいて、
下流リンクにおけるもう一つの輻輳スパンの一部であり前記識別するステップで識別されるもう一つのヘッド・ノードから発せられた宣伝レートを受け取ることと、
当該ヘッド・ノードの前記追加レートを前記ターゲット・レート、前記DSレートまたはこれらの組み合わせの関数として設定することと、
を含む、請求項１に記載の方法。
【請求項１６】
前記ヘッド・ノード以外の一つまたは複数のノードがもう一つのヘッド・ノードを含み、該もう一つのヘッド・ノードがもう一つの輻輳スパンの一部であり前記識別ステップで識別され、
前記出力帯域幅を調整するステップが、
前記もう一つのヘッド・ノードにおいて、
その下流リンクの輻輳を検出するためトラフィックをモニタし、
前記初期設定のステップおよびモニタするステップを使用してさらなるターゲット・レートを設定し、輻輳を検出するとき調整を行い、
前記さらなるターゲット・レート、前記DSレートまたはこれらの組み合わせの関数として前記追加レートを設定することを含む、
請求項１に記載の方法。
【請求項１７】
前記ターゲット・レートが公平性によって指定される最大許容追加レートである、請求項１から１６のいずれかに記載の方法。
【請求項１８】
コンピュータによって実行され、請求項１から１７のいずれかに記載の方法を実現するコンピュータ・プログラムを記録したコンピュータ読取可能記録媒体。
【請求項１９】
出力帯域幅を有する一つまたは複数のノードの双方向リングネットワークに対するアクセスを管理するシステムであって、
輻輳した下流リンクを含む輻輳スパンの先頭に位置するヘッド・ノードを識別することを含み、前記一つまたは複数のノードを輻輳スパンの一部として識別する手段と、
前記一つまたは複数のノードの前記出力帯域幅を調整する手段であって、該調整する手段は、前記ヘッド・ノードとして識別されたとき、
前記輻輳に寄与するノードの数の関数としてターゲット・レートを初期設定し、
前記帯域幅の利用度をモニタし、該帯域幅の利用度の関数として前記ターゲット・レートを調整し、
所定の時間に、前記輻輳スパンの前記下流リンクにおける輻輳に寄与するノードの追加レートを調整するため前記下流ノードへの宣伝レートとして前記ターゲット・レートを送る、
よう構成されている、前記アクセスを管理するシステム。
【請求項２０】
前記調整する手段は、
WAN入力ポートからパケットを受け取り、通過FIFOおよびスケジューラを介して該パケットをWAN出力に送り、または引込みキューを介してWAN出口ポートに該パケットを引き込むための転送フィルタデータベースと、
WAN入口ポートからパケットを受け取り、追加キュー、リーキーバケットおよび前記スケジューラを介して該パケットをWAN出力ポートに送るための入口フィルタデータベースと、
第１の時間にわたって前記通過FIFOを通過するパケットを数えることによりタンデム・レートを計算するためのタンデム・レート評価器と、
第２の時間にわたって前記リーキーバケットを通過するパケットを数えることにより前記追加レートを計算するための追加レート評価器と、
前記タンデム・レートおよび前記追加レートから前記WAN出力ポートの帯域幅利用度を計算し、前記帯域幅利用度および下流（DS）レート受信モジュールで受け取られたレートの関数として宣伝レートを求めるための宣伝レート生成器と、
を備える、請求項１９に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークにおけるノード間の通信の管理に関連し、より具体的には、双方向リングネットワークにおけるノード間のデータフローを管理するための方式に関連する。
【０００２】
【従来の技術】
輻輳は、ノードの帯域幅の要求がネットワークの帯域幅を越えたときにネットワーク内で生じる。公平性（fairness）方式は、ネットワーク間のノードに帯域幅を割り当てるために使用されることができる。
【０００３】
例えばトークンリング・ネットワーク（token ring network）等に利用されるようなグローバル公平性方式（global fairness scheme）は、ネットワーク内のどこで輻輳が生じているかに関係なく、全リングネットワークを考慮する。グローバル公平性方式は、空間再利用（spacial reuse）を利用しないので帯域幅の利用度の点で効率が悪い。空間再利用は、宛て先のノード（destination node）がネットワークからパケットを取り出すときに達せられる。これは、利用可能なリング帯域幅を倍増させる効果を与える。対照的に、ローカル公平性方式(local fairness scheme)は、空間再利用を増やし、より効果的に輻輳を管理する。
【０００４】
ローカル公平性方式は、リングネットワークの輻輳した区間またはスパン（span）を隔離し、このためにより効率的である。リングネットワーク内のスパンだけを考えることによって、ネットワークにおけるノード間の帯域幅の割り当て問題は、線形モデルと化す。したがってローカル公平性方式は、線形ネットワーク（linear network）に対して同じように適用可能である。この明細書では、線形ネットワークをリングネットワークの一種とみなす。すなわち線形ネットワークを、切断されたリングネットワーク（broken ring network）ともいえるリングネットワークの特殊なケースとみなす。
【０００５】
ローカル公平性方式は、リングネットワークへのアクセスを制限されるノードを認め、それ自身の送信にどのようなノードが与えられたとしてもリングのトラフィックを優先する割当量（quota）の割り振りを含んでいる。各ノードによるリングへのアクセスは、リングに制御メッセージを巡回させることによって制御されることができる。そのメッセージは、ある制御メッセージの受信から次の制御メッセージの転送までの期間の間に送信することができる最大パケット数を各ノードに示す。持続した輻輳状態（sustained congested state）において、割当量方式（quota scheme）は、公平性の判断（fairness decision）を必要とする。この公平性の判断は、それぞれの割当量に対してなされ、実行される。そのような方式は、遅延とジッターに関連づけられる。
【０００６】
ローカル公平性方式は、ノードを通るタンデム・レート（tandem rate）またはデータフローに基づいて周期的に変更を加えて上流のノードにターゲット・レート（target rate）を宣伝（advertise;通知）するアルゴリズムを利用することができる。ターゲット・レートは、ネットワーク内に実際に輻輳があるかどうかにかかわらず宣伝される。そのような方式は、一般的にその方式における周期的な変動が原因で事実上スケールを変えない。そのような局所的なレート制御のアルゴリズムは、ある程度の規模以下のネットワークに限定される。適応性のあるレート制御のメカニズムは、統計量に基づいてデータを集めて、集めたデータの変化にすばやく適応する。そのデータにおける不確実さは、公平性アルゴリズムにおいて不正な振る舞い（misbehaviour）を引き起こし、それゆえ、そのスケーラビリティ（scalability）を制限する。
【０００７】
【発明が解決しようとする課題】
したがって、帯域幅をより効率的に利用する優れた性能を有する双方向リングネットワークにおいて、ノード間のデータフローを管理するローカル公平性方式の要求がある・
【０００８】
【課題を解決するための手段】
本発明は、双方向リングネットワークにおけるノード間のデータフローを管理するための方式に向けられる。
【０００９】
本発明の１つの側面によると、双方向リングネットワークへのノードのアクセスを管理するための方法が提供される。ノードは、下流リンクおよび出力帯域幅を有する。その方法は、ノードを輻輳したスパンの一部として識別するステップ、およびノードの出力帯域幅をスパン内の輻輳の関数として調整するステップを含む。
【００１０】
本発明のさらなる側面によると、双方向リングネットワークへのノードのアクセスを管理するための方法が提供される。ノードは、下流リンクおよび出力帯域幅を有する。その方法は、ノードがその一部である輻輳スパンにおける下流ノードからＤＳレートをノードで受信するステップ、ノードの下流リンクが輻輳したかどうかを判断するステップ、ＤＳレートおよび下流リンクにおける輻輳の関数としてノードの出力帯域幅を調整するステップ、および下流リンクにおける輻輳に寄与する１つまたは複数の上流ノードの出力帯域幅をＤＳレートおよび下流リンクにおける輻輳の関数として調整するステップを含む。
【００１１】
本発明のさらなる側面によると、双方向リングネットワークへのノードのアクセスを管理するための方法が提供される。その方法は、輻輳した下流リンクを有するヘッド・ノード、および下流リンクにおける輻輳に寄与する複数のチェーン・ノードを含む輻輳したスパンを識別するステップ、下流リンクにおける輻輳の関数としてヘッド・ノードの出力帯域幅を調整するステップ、および下流リンクにおける輻輳の関数としてチェーン・ノードの出力帯域幅を調整するステップを含む。
【００１２】
本発明のさらなる側面によると、双方向リングネットワークへのノードのアクセスを管理するための装置が提供される。ノードは、下流リンクおよび出力帯域幅を有する。その装置は、複数のノードを含む輻輳したスパンを識別するための手段、および輻輳したスパンにおけるノードの出力帯域幅を、スパンにおける輻輳の関数として調整するための手段を含む。
【００１３】
本発明のさらなる側面によると、コンピュータで読み込み可能な媒体に記憶される、コンピュータで実行可能なソフトウェア・コードが提供される。そのコードは、双方向リングネットワークへのノードのアクセスを管理するためものである。そのノードは、下流リンクおよび出力帯域幅を有する。そのコードは、ノードを輻輳スパンの一部として識別するコード、およびスパンにおける輻輳の関数としてノードの出力帯域幅を調整するコードを含む。
【００１４】
本発明のさらなる側面によると、双方向リングネットワークへのノードのアクセスを管理するためにプログラムされたコンピュータが提供される。ノードは、下流リンクおよび出力帯域幅を有し、コンピュータで実行可能なプログラム・コードを記憶するために、少なくとも１つの領域を持つメモリ、およびメモリに記憶されたプログラム・コードを実行するためのプロセッサを含む。プログラム・コードは、ノードが輻輳スパンの一部であることを識別するコード、およびスパンにおける輻輳の関数としてノードの出力帯域幅を調整するコードを含む。
【００１５】
本発明のさらなる側面によると、コンピュータで実行可能なソフトウェア・コードを有するコンピュータで読み込み可能な媒体が提供される。そのコードは、双方向リングネットワークへのノードのアクセスを管理するためのものである。ノードは、下流リンクおよび出力帯域幅を有し、輻輳スパンの一部としてノードを識別するコード、およびスパンにおける輻輳の関数としてノードの出力帯域幅を調整するコードを含む。
【００１６】
本発明のさらなる側面によると、双方向リングネットワークへのノードのアクセスを管理する装置が提供される。ノードは、下流リンクおよび出力帯域幅を有する。その装置は、輻輳スパンの一部としてノードを識別する識別器（identifier）と、スパンにおける輻輳の関数としてノードの出力帯域幅を調節する調整器(adjuster)とを含む。
【００１７】
本発明の他の側面および機能は、本発明の具体的な実施形態の以下の説明と添付の図面の検討で本分野の通常の当業者に対して明らかになる。
【００１８】
【発明の実施の形態】
図１は、双方向リングネットワークを表す。双方向リングネットワークは、複数のネットワーク要素またはノード１０を含む。本発明のために、双方向リングネットワークは、多数のノードを含むこともあれば、わずか３個のノードしか含まないこともある。双方向リングネットワークは、相反する方向に巡回する２つのリングも含む。リング−１（１５）は、反時計回りに巡回し、リング−２（２０）は、時計回りに巡回する。各ノード１０は、リング−１ＷＡＮ入力ポート６５（Ring-1 WAN input port）およびリング−１ＷＡＮ出力ポート７０（Ring-1 WAN output port）で、リング−１（１５）に接続される。各ノード１０は、リング−２入力ポート７５（Ring-2 input port）およびリング−２出力ポート８０（Ring-2 output port）で、リング−２（２０）に接続される。双方向リングネットワークの内外への通信を可能にするために、各ノード１０は、ＷＡＮ入口ポート２５（WAN ingress port）およびＷＡＮ出口ポート３０（WAN egress port）も備える。
【００１９】
図２は、３個のノード１０を含む双方向リングネットワークの一部分を図示する。図２は、双方向線形ネットワークを表すこともある。線形ネットワークがリングネットワークの一種（切断されたリングネットワークといえるリングネットワークの特殊なケース）とみなされることを思い起こすべきである。
【００２０】
図３は、図１および図２に示すノード１０を図示している。リング−1 ＷＡＮ入力ポート６５で、データパケットは、リング−1（１５）からノード１０に入る。パケットは、転送フィルタ・データベース３５（forwarding filter database）に入る。パケットのアドレスを参照して、そのパケットがその特定のノード１０宛てのものであるかどうかに関して、転送フィルタ・データベース３５において判断がなされる。そのパケットがそのノード１０宛てのものであれば、引き込みキュー（drop queue）６０に転送されるか引き込まれ、それからＷＡＮ出口ポート３０に引き込まれる。
【００２１】
パケットがノード１０宛てのものでなければ、通過インターフェース（pass through interface）または通過ＦＩＦＯ４０（すなわち先入れ先出しシフトレジスタ）に転送される。それからパケットは、出力スケジューラ４５（output scheduler）に転送される。出力スケジューラ４５は、リング−１ＷＡＮ入力ポート６５とＷＡＮ入口ポート２５との間でスケジュールを設定する。リング−１（１５）宛てのものであって、ＷＡＮ入口ポート２５でノード１０に入るパケットは、入口フィルタ・データベース５５に転送され、出力スケジューラ４５に転送される前に、追加キュー（add queue）５０に転送される。パケットは、出力スケジューラ４５からリング−１ＷＡＮ出力ポート７０に転送される。ノード１０とノード１３との間のリング１（１５）の部分は、下流リンク１６と呼ばれることになる。
【００２２】
リング−２ＷＡＮ入力ポート７５で、リング−２（２０）からノード１０に入るデータパケットは、先に述べたのと同じような経路をとる。
【００２３】
輻輳は、１秒当たりのビット数（ｂｐｓ）で一般に測定される出力帯域幅またはデータフローレートが、ある値をこえたときに下流のリンク１６において生じる。この文脈において輻輳は、下流のリンク１６が処理することのできる最大帯域幅またはデータフローレートを意味することで規定される。輻輳は、他の方法で規定されてもよく、例えば下流のリンクの最大帯域幅またはレートの関数として規定されてもよい。
【００２４】
本明細書では、タンデム・レートは、ノード１０を通過する（すなわち通過ＦＩＦＯ４０を通る）データフローレートである。追加レートは、特定のノードがリングに寄与しているデータフローレートである（すなわちＷＡＮ入口ポートからスケジューラまでのレート）。輻輳は、タンデム・レートと追加レートの総和が下流リンクの帯域幅を越えるときに下流リンク１６において生じる。与えられる公平性方式においては、タンデム・レートと追加レートの総和があらかじめ定めた帯域幅またはデータフローレートに達したときに、輻輳が下流リンク１６において生じると考えられる。ターゲット・レートは、公平性方式によって指定されるような最大許容追加レートである。宣伝レートは、下流のノードによって、輻輳したスパン内の上流のノードに指定されるターゲット・レートである。宣伝ターゲット・レートは、ひとたび特定のノードによって受信されたならばＤＳレートと呼ばれる。
【００２５】
図４は、双方向リングネットワークへのノードのアクセスを管理するための公平性アルゴリズム２００のフローチャートである。ステップ２０５で、アルゴリズム２００は始まる。
【００２６】
ステップ２１０で、下流リンクが輻輳しているかどうかに関して判断がなされる。ノードの出力帯域幅があらかじめ定めたレベル（例えば下流リンクの最大帯域幅またはその関数など）に達しているならば、下流のリンクは輻輳している。
【００２７】
下流リンクが輻輳しているとわかれば、ステップ２１５で、ノードのターゲット・レートが初期値に設定される。下流リンクが輻輳していれば、そのノードは、輻輳したスパン内のヘッド・ノード (先頭ノード；head node)である。
【００２８】
ステップ２１０で下流リンクが輻輳していることがわかるかどうかに関わらず、ステップ２２０でＤＳレートが下流のノードから受信されたかどうかに関して判断がなされる。ＤＳレートの受信は、そのノードが輻輳したスパンにおけるチェーン・ノード（連鎖ノード；chain node）であることを示している。
【００２９】
ステップ２２５（２２０）でＤＳレートが受信されていないことがわかれば、ステップ２１５（２２５）でターゲット・レートが設定されたかどうかに関して判断がなされる。ターゲット・レートが設定されてなかった場合、そのノードは、輻輳したスパンの一部ではない。すなわちヘッド・ノード（ステップ２１０）でもなければ、チェーン・ノード（ステップ２２０）でもない。次にアルゴリズム２００は、ステップ２１０に折りかえして、先に述べたように下流のリンクが輻輳しているかどうかに関して再び判断がなされる。
【００３０】
ステップ２２５で、ＤＳレートが受信されたとわかれば、ステップ２３０でノードの追加レートが、ターゲット・レートおよびＤＳレートの関数として設定される。ターゲット・レートだけか、ＤＳレートだけか、またはターゲット・レートとＤＳレートの両方であってもよいことに留意すべきである。
【００３１】
ステップ２３５で、ノードの宣伝レートは、ターゲット・レート及びＤＳレートの関数として設定される。ターゲット・レートだけか、ＤＳレートだけか、またはターゲット・レートとＤＳレートの両方であってもよいことに再び留意すべきである。
【００３２】
ステップ２４０で、宣伝レートは、輻輳したスパンの上流のノード（すなわちチェーン・ノード）に送られる。好ましくは、そのチェーン・ノードは、アルゴリズム２００を利用する。
【００３３】
ステップ２４５で、ターゲット・レートが（ステップ２１５、ステップ２６５、またはステップ２７５で）設定されたかどうかに関して判断がなされる。ターゲット・レートが設定されていなければ、そのノードは、輻輳したスパンの一部ではない。すなわちヘッド・ノードまたはチェーン・ノードのどちらでもない。それからアルゴリズム２００は、ステップ２１０に折りかえして、先に述べたように下流のリンクが輻輳しているかどうかに関して再び判断がなされる。
【００３４】
ステップ２４５でターゲット・レートが設定されているとわかれば、ステップ２５０で下流リンクの利用度が測定される。下流リンクの利用度とは、下流リンクの輻輳レベルの程度、すなわち例えば下流のリンクの最大帯域幅、またはその関数などのあらかじめ定めたレベルに対するノードの出力帯域幅の程度である。下流リンクの所望の利用度レベルは、ステップ２１０において使用される輻輳の規定と同じであってもよいし、そうでなくてもよい。
【００３５】
ステップ２５５で、下流リンクが十分に利用されていない、すなわちノードの出力帯域幅があらかじめ定めた所望の利用度レベル以下であるかどうかに関して判断がなされる。
【００３６】
ステップ２５５で、下流リンクが十分に利用されているとわかれば、ステップ２６０で、下流リンクが過剰に利用されているかどうか、すなわちノードの出力帯域幅が、あらかじめ定めた所望の利用度レベル以上であるかどうかに関して判断がなされる。
【００３７】
ステップ２６０で、下流リンクが過剰に利用されていないとわかれば、ノードの出力帯域幅は、あらかじめ定めた所望の利用度レベルに等しい。したがって、ターゲット・レートを調整する必要はなく、アルゴリズム２００はステップ２２０に折りかえして、先に述べたようにＤＳレートが下流のノードから受信されたかどうかに関して再び判断がなされる。
【００３８】
ステップ２６０で、下流リンクが過剰に利用されているとわかれば、ステップ２６５で、ターゲット・レートが減らされる。量子化レート制御方式（quantized rate control scheme）において、ターゲット・レートは、次に最も小さな値に減らされる。それからアルゴリズム２００は、ステップ２２０に折りかえして先に述べたようにＤＳレートが下流のノードから受信されたかどうかに関して再び判断がなされる。
【００３９】
ステップ２５５で、下流のリンクが十分に利用されていないとわかれば、ステップ２７０でターゲット・レートが増やされる。量子化レート制御方式において、ターゲット・レートは、次に最も大きな値に増やされる。
【００４０】
ステップ２７５で、ターゲット・レートがあらかじめ定めた最大しきい値に達したかどうかに関して判断がなされる。最大しきい値は、下流リンクの最大帯域幅またはその関数と等しくてもよい。最大しきい値は、ステップ２５５および２６０において使用された下流リンクの所望の利用度レベルの関数か、またはステップ２１０で使用された輻輳の規定であってもよい。ターゲット・レートが最大しきい値に達したとわかれば、アルゴリズム２００がステップ２１０に折りかえして、先に述べたように下流のリンクが輻輳しているかどうかに関して判断がなされる。ターゲット・レートが最大しきい値に達していないとわかれば、アルゴリズム２００がステップ２２０に折りかえして先に述べたようにＤＳレートが下流のノードから受信されたかどうかに関して再び判断がなされる。
【００４１】
図５は、本発明を実施するノード１０を表す。ノード１０は、以下のコンポーネントを含む。
−タンデム・レート評価器（tandem rate estimator）８５。
−統計量を計算するために使用されるタイマ９０（Tstat）。
−ノードでの実際の追加トラフィック・レートを計算するために使用される追加レート評価器９５（add rate estimator）。
−輻輳したスパン内のノードのために、新しいターゲット・レートを計算する宣伝レート生成器１００（Advertised rate generator）。
−下流レート受信モジュール１０５（Downstream rate receive module）。この方式（mode）は、トラフィック・レートを測定するリングと反対方向のリング上で公平性メッセージ（Fairness message）を聞く。
−追加トラフィック・レートを制御するリーキー・バケット（Leaky bucket）１１０。
−公平性メッセージを周期的に送信するタイマ１１５。この公平性メッセージは、輻輳したスパン内の輻輳したノードのためのターゲット・レートを含んでいる。このタイマの持続時間を、Tmsgと呼ぶ。
【００４２】
輻輳がなければ、各ノードは、最大リング帯域幅までパケットを送信することができる。輻輳が検出される場合、複数のノードの集団が輻輳したスパンまたは輻輳スパンとして識別される。公平性アルゴリズムは、使用可能になる。閉ループ制御機構は、１つのリング上で、１つの方向におけるデータフローレートを監視して、その反対方向における輻輳したスパン内の上流ノードに公平性メッセージを送信し、出力レートを制御することによって輻輳を軽減する。
【００４３】
パケットがＷＡＮ入力ポート６５に到着する時、そのパケットをこのノードに引き込むか、あるいはそのパケットを通過ＦＩＦＯおよびスケジューラを介して外部にむけてリング上に引き続き転送するか、のいずれかの判断がなされる。通過パケットは、Tstatにわたってタンデム・レート評価器８５によってカウントされる。同様に、現在のノードによってリングに追加されるすべてのパケットは、追加レート評価器９５によってカウントされる。輻輳していない場合には、リーキー・バケットは有効ではない。そのためＷＡＮ入口ポート５５からのすべてのパケットは、追加レート評価器によってスケジュール通りにカウントされ、リング上に出される。
【００４４】
以下の動作は、連続的に実行される。
−追加レート及びタンデム・レートは、全てのTstatに対して測定される。
−各ノードは、Tmsg毎に上流のノードに公平性メッセージを送信する。メッセージは、宣伝レートを含む。この宣伝レートは、リーキー・バケットを制御する１つまたは複数の上流ノードのためのターゲット・レートである。
−各ノードは、タンデム（縦続接続）の送信元（source）の数を監視する。
−各ノードは、反対側のリング上で公平性メッセージを連続的に受信し、このメッセージを処理する。
−宣伝レート生成器は、ＷＡＮ出力ポート６５の帯域幅の利用度が、輻輳を規定するしきい値を越えているかどうかを調べる。輻輳が無ければ、上流のノードに対する宣伝レートは、最大のリング帯域幅である。このメッセージは、ＷＡＮポート８０で外に送信される。輻輳が検出される場合、このノードは、輻輳したスパン内の全ノードの出力帯域幅を制御することになる。このノードを、ＨＥＡＤノードとよぶ。出力帯域幅の制御は、上流のノードにターゲット・レートを宣伝することによって達せられる。上流のノードによって受信されるターゲット・レートは、リーキー・バケットに適用される。上流のノードが宣伝レートに一致させるとき、その結果は、タンデム・レートの監視において、ＨＥＡＤノードによって測定されることができる。
【００４５】
−輻輳の各段階で、上流のノードに様々なレートが宣伝される。宣伝レート生成器は、上流の全てのノードに対して公平なレートを宣伝することができる。ターゲット・レートを宣伝した後、ＨＥＡＤノードは、その出力リンク上で帯域幅の利用度を監視し続ける。輻輳が無くならないのであれば、前よりも小さなターゲット・レートを宣伝することになる。このプロセスは、ＨＥＡＤノードの出力帯域幅の利用度が最大値に達するまで続く。平衡に達したとき、全ノードは、同じレートを送信することになる。リンク帯域幅が等しく分けられる。空き容量（spare capacity）が出力リンクで検出されれば、宣伝レート生成器１００は、上流のノードにより大きなターゲット・レートを宣伝する。
【００４６】
下流レート受信モジュール１０５は、２つのタスクを実行する。
−それは、データフローに対して反対のリングトラフィックを、下流のノードからの公平性メッセージのために継続的に監視する。
−それは、ターゲット・レートを上流のノードに転送するか、またはターゲット・メッセージを終了させるかのいずれかを行う宣伝レート生成器１１５に、下流のノードから受信されたターゲット・レートを転送する。
【００４７】
公平性アルゴリズムは、輻輳スパンに適用される。スパンは、ＨＥＡＤ（先頭；ヘッド）、ＣＨＡＩＮ（連鎖；チェーン）、ＴＡＩＬ（後尾；テール）を有する。ＨＥＡＤは、その出力リンク１５で輻輳を検出するノードである。複数のノードによって輻輳が生じる場合、輻輳は、有限のノード数からなる。ＨＥＡＤおよび最後のノードを除いて、全てのノードは、ＣＨＡＩＮノードである。最後のノードは、ＴＡＩＬノードと呼ばれる。１つまたは複数のＣＨＡＩＮノードとＴＡＩＬノードとの違いは、ＴＡＩＬノードが、最大しきい値以下のタンデム・トラフィックを有することである。公平性アルゴリズムは、輻輳したスパンにおける全てのノードに対して帯域幅を等しく割り当てることを確実にしようとする。
【００４８】
ヘッド・ノードの形成は、上で説明されている。ＣＨＡＩＮまたはＴＡＩＬの形成は、輻輳しきい値と等しくない下流レートを受信するノードによって確立される。
【００４９】
図６は、本発明を具体化する公平性アルゴリズムを図示する状態図である。
公平性方式の中心は、２つの重要な値を制御するステート・マシン（state machine）である。
−上流のノードへの宣伝ターゲット・レート、および
−リーキー・バケットに適用されるリークレート。
【００５０】
公平性ステート・マシン（fairness state machine）は、６個の主状態（main state）と４個の副状態（minor state）を含んでいる。
−非輻輳状態３００（Un-congested state）。これは、デフォルトの状態である。
−通常輻輳状態３０５（Normal Congested State）。単一のノードか、またはトラフィックを追加しないノード（すなわち、それの出力リンク１５で輻輳に寄与しないノード）によって輻輳が生じる場合、この状態である。
−ＨＥＡＤ１状態３１０（HEAD 1 state）。輻輳が最初に検出される場合、輻輳したスパンの先頭は、ターゲット・レートを上流のノードに宣伝して、上流のノードの追加トラフィックにそれを適用させることで対処しなければならない。
この状態は、出力リンクの利用度に応じてその宣伝レートを上または下に連続的に調整する。
【００５１】
−ＨＥＡＤ＝ＨＥＡＤ＋１状態３１１（HEAD = HEAD - 1 state）。これは、宣伝レートを次に低い値にする副状態である。
−ＨＥＡＤ＝ＨＥＡＤ−１状態３１２（HEAD = HEAD + 1 state）。これは、宣伝レートを次に高い値に上げる副状態である。宣伝レートを上げるための判断は、空き容量が出力リンク上で観測されることを理由とする。
【００５２】
輻輳状態が終わったとき、各ノードは、通常の非輻輳状態３００に戻る。
【００５３】
−ＨＥＡＤ２状態３１５（HEAD 2 state）。この第２のヘッド状態は、スパン内部で輻輳が生じるかどうかを考慮に入れるのに必要とされる。例えばトラフィックフローが変わるのに応じて、スパン内のクワイエット・ノード（quiet nodes）が、データを送信し始める。輻輳は、現行のスパン内部で生じてもよいし、さもなければ複数のスパンが一体となって合わさってもよい。ＨＥＡＤ２状態は、単一のスパンがほかの複数のスパンを取り込むことを可能にする。ＨＥＡＤ１とＨＥＡＤ２は、宣伝レートの計算において異なる。ＨＥＡＤ１は、輻輳したスパンの真の先頭のノードである。それは、スパンにおける全ノードのためにターゲット・レートを制御する。ＨＥＡＤ２は、ＨＥＡＤ１から受信される最小ターゲット・レートを伝搬する。この概念は、一部重複するスパンを取り込むのに必要とされる。
【００５４】
−ＨＥＡＤ＝ＨＥＡＤ＋１状態３１６（HEAD = HEAD - 1）。これは、次に低い値まで宣伝レートを下げる副ステートである。
−ＨＥＡＤ＝ＨＥＡＤ−１状態３１７（HEAD = HEAD + 1）。これは、宣伝レートを次のより高い値に上げる副ステートである。宣伝レートを上げるための判断は、空き容量が出力リンク上で観測されることを理由とする。
【００５５】
輻輳状態が終わったとき、各ノードは、通常の非輻輳状態３００に戻る。
【００５６】
チェーン状態３２０（Chain state 320）。輻輳したスパンにおいて、ノードが先頭のノードでなければ、それはチェーン・ノードか、またはテール・ノードのいずれかである。これらのノードは、許容最大リークレート以下のターゲット・レートを受信するノードとして単に識別される。この許容最大リークレートは、輻輳しきい値でありうる。チェーン・ノードは、受信された下流レートを上流に転送し、受信された下流レートをリーキー・バケットに適用する。
【００５７】
テール状態３２５（Tail state）。テール状態は、タンデム・トラフィックが小さいという事実によってチェーン・ノードとは異なる。それゆえ、そのタンデム・トラフィックは、下流の輻輳に寄与していない。テール・ノードは、その下流レートを上流のノードに転送しないで、受信された下流レートをそのリーキー・バケットに適用する。テール・ノードがトラフィックを輻輳スパンに追加するのをやめれば、それ自身は、そのスパンからはずれる。その下流のノードが、自動的にテールになる。テール・ノードが有意な通過トラフィック量を検出すれば、それはチェーン・ノードになり、上流のノードのうちの１つが新しいテールになる。これは、スパンが伸びることを可能にする。
【００５８】
図７は、双方向リングネットワークにおける４つのノードを図示する。ノード２がノード１からみて上流であり、ノード３がノード２からみて上流であり、ノード４がノード３からみて上流である。リング上の最大許容帯域幅は、輻輳しきい値と同じであり、最大帯域幅の９５％で規定される。有効とみなされる最小トラフィック・レートは、リング帯域幅の５%で規定される。
【００５９】
初期状態を、ここに記述する。
全ノードは、非輻輳状態で始まる。各ノードは、リーキー・バケット１１０が有効にされてないのでリング帯域幅までバースト（burst）することができる。開始時には、ネットワークに輻輳はない。
【００６０】
各ノードは、継続的にタンデム・トラフィック・レートを監視する。レートの監視は、固定ウィンドウ評価器（fix window estimator）によって実施されることができる。それは、期間がTstatに設定されているプログラム可能なタイマである。タイマが切れるときに、現在のタンデムカウント（tandem count）がレート計算のために使用され、ビン（貯蔵器；bin）がクリアされる。次のパケットが通過経路に受信されるとき、パケットサイズがビンに累積される。累積は、受信される全てのパケットに対して、次のTstatタイマの満了イベントまで続く。このプロセスが繰り返される。
【００６１】
全リング帯域幅は、様々なクラスに細分されてもよい。クラスのそれぞれは、それ自身の公平性アルゴリズムの実行を有することができる。各ノードは、クラスのそれぞれに対してタンデムおよび追加レートを測定する。
【００６２】
各ノードは、継続的に追加トラフィック・レートを監視する。同じメカニズムは、タンデム・レートの推定のために使用される。追加トラフィックは、異なる宛先に対して記憶されることができる。輻輳したリンクを通過する宛先のパケットは、制限されたレートになるが、輻輳する前のノードに宛てたパケットは、別のレートリミッタ（rate limiter）で送られることができる。
【００６３】
各ノードは、プログラム可能なタイマ値（Tmsg）を有するメッセージ・タイマを持つ。このタイマが切れるとき、公平性メッセージが上流のノードに送られる。メッセージの内容は、上流のノードのための宣伝レートである。輻輳がない場合には、宣伝レートは９５%のリング帯域幅である。
【００６４】
もう一つの方法として、公正性メッセージは、ネットワークにおけるイベントの変化をトリガとして送られることができる。例えば、変化イベントは、輻輳の検出として規定されることができる。ＨＥＡＤノードが、過剰に利用されている下流リンク帯域幅を検出する。；ＨＥＡＤノードが十分に利用されていない下流リンク帯域幅を検出する。；または輻輳したスパン内の送信元に対して監視されたレートの変化；または追加トラフィックに対する線遅延の超過ヘッド。
【００６５】
公正性メッセージは、輻輳が検出された場所の情報を含むことができる。公平性メッセージはTmsg時間ごとを送られるか、または新しいメッセージが受信されたときに送られることができる。
【００６６】
各ノードは、その下流のノードから公正性メッセージを受信する。非輻輳の場合、受信される下流レートは、９５%のリング帯域幅である。
【００６７】
輻輳帯域幅の分配（Congestion Bandwidth Allocation）を、ここに説明する。
【００６８】
輻輳は、以下のように生成される。ノード２、３、および４は、ノード１に、リング帯域幅の４０%相当のデータを送り始めるか、または送ろうとする。ノード４は、そのトラフィックの全てをリング上におくことができる。その出力リンク４２０は、４０％利用される。ノード３は、そのトラフィックの全てをリング上におくことができる。その出力リンク４２５は、８０％利用される。しかしながら、ノード２は、リング上にそのトラフィックの５０％しかおくことができない。
【００６９】
その利用度が輻輳しきい値と交差するので、ノード２は、その出力リンクが輻輳することを検出する。ノード２は、ヘッド・ノードになる。それは、上流のノードのために初期ターゲットの値を選択する。初期値は、ノード２までタンデム接続されている送信元の数を監視することによって判断される。この場合、その数は２である。次にその状態参照テーブルから、現在のヘッド・ノードの状態と対応する宣伝レートを見つける。それから、このレートが上流のノードに宣伝されて、それら自身のリーク・バケット１１０を制御するために使用される。この例では、輻輳スパンに３つのノードがあるので、公平な宣伝レートはリング帯域幅の３１%である。
【００７０】
状態テーブルにおいて、エントリは、現在のヘッド状態を識別する。ヘッド状態のそれぞれのために、宣伝レートのためのエントリ、および出力リンクの利用度のためのエントリがある。ヘッド・ノードは、その出力リンクの利用度を継続的に監視する。輻輳は、他のノードが加わるにつれて増大する。ヘッド・ノードは、輻輳を見つけて、そのヘッド状態数（head state number）を増加させる。ヘッド状態数が大きくなればなるほど、宣伝レートの値は小さくなる。このようにして制限されたリング帯域幅は、競合するノードの間で等しく分けられる。
【００７１】
もう一つの方法として、輻輳が検出されるとき、先頭ノードはプローブ・レート（probe rate；ネットワーク内のノードの総数以下である任意のレート）を宣伝することができる。それからヘッド・ノードは、サンプリング時間にわたってタンデム・レートを測定し、プローブ・レートでサンプリング・レートを割って上流のノード数を判断する。
【００７２】
もう一つの方法として、ノードのそれぞれは、ノードまでタンデム接続されている送信元のそれぞれに対するタンデム・レートを監視することができる。もし輻輳スパン内のすべてのノードが同じ量のトラフィックを送信するわけではないならば、より高度な判断がなされて、最も重いトラフィックを送信するノードをターゲットにすることできる。
【００７３】
各ノードは、各送信元に関連づけられた優先権（preference）を有することもできる。輻輳が検出されるとき、それは、最初により低い優先権をつけられたノードを選択的にターゲットにすることができる。
【００７４】
ノード３は、リング帯域幅の３１%の下流レートを受信して、そのリーキー・バケットをターゲット・レートに設定する。ノード３のタンデム・レート評価器は、有意なタンデム・トラフィックを検出し、ノード４にタンデム・レートを転送する。
【００７５】
ノード４は、リング帯域幅の３１%の下流レートを受信し、そのリーキー・バケットをターゲット・レートに設定する。ノード４のタンデム・レート評価器は、タンデム・トラフィックを検出しない。このため、その上流のノードにターゲット・レートを転送しない。ノード４は、テール・ノードになる。
【００７６】
リーキー・バケットが有効になっているので、全てのノードが公平なレートを送信する。このレートは、所望のレート以下である。余分なパケットは、追加キュー１５０にバッファされることになる。それが充てんされるか、ある程度充てんされた場合、ＷＡＮ入口ポート２５に背圧（back pressure）をかけるか、さもなければ（たとえばランダム早期処分（Random Early Discard ；RED）などのアルゴリズムに基づいて、）パケットを処分する。
【００７７】
輻輳したノードは、ＤＳレート（公平なレート）を受信し、ＤＳレートまたは局所的な追加レートの関数に基づいて、そのリーキー・バケットを制御する。関数は、パケットの優先順位のプロファイル（packet priority profile）であってよい。ＤＳレートより大きなレートで、優先順位の高いトラフィックを送信するノードは、そのリーキー・バケットを優先順位の高いトラフィック・レートに設定することができる。これは、ヘッド・ノードの下流リンクで、輻輳を引き起こすことになる。ＨＥＡＤノードは、それに応じてより低いレート（公平ではないレート）を上流のノードに宣伝する。優先順位の低いトラフィックの送信元ノードだけが、その追加レートを宣伝レートに合わせることになる。これは、優先順位の高いトラフィックに優先的な扱いを提供する方法である。
【００７８】
ノードのリークレート（leak rate）は、欠陥診断目的（fault diagnostic purpose）のためにヘッド・ノードにエコーバック（echo back）されてよい。
【００７９】
輻輳の除去（Congestion Removal）をここで説明する。
【００８０】
この例において、ノード４は、送信するデータが無いのでパケットを送信するのをやめる。ノード４は、その追加レートが最小しきい値以下に減少したことを検出し、ＴＡＩＬ状態３２５から非輻輳状態３００に状態を変える。ノード２は、その出力リンクの利用度が、状態テーブルにおける最小利用度の値以下に落ちたことを検出する。これは、状態テーブルに記憶される第２の値である。ノード２は、状態テーブルからそのＨＥＡＤ状態数を減らし、より大きな宣伝レートを選択してノード３にそれを送信する。同時にノード３は、ノード４から有意ではないトラフィックを検出し、ＴＡＩＬとなることを引き継ぐ。ノード３は、ノード２から新しいターゲット・レートを受信し、それをそのリーキー・バケットに適用する。ここでスパンがそのサイズを減少して、より公平性の高い新しいレートがスパン内の全てのノードに適用される。
【００８１】
ノード２の帯域幅の需要量が低下する。それが最小しきい値の帯域幅より小さいトラフィックを送り出している場合、それは状態をＨＥＡＤ状態から非輻輳状態に変える。ノード２は、ノード３に最大許容リング帯域幅を宣伝する。
【００８２】
最後に、ノード３は、最大許容リング帯域幅のターゲット・レート、およびＴＡＩＬ状態から非輻輳状態への変化を受信する。
【００８３】
ここで全てのノードは、初期条件にもどる。
【００８４】
実施をここに説明する。
【００８５】
このアルゴリズムは、ハードウェアにおいて完全に実施されることができる。プロセッサ・モジュールがＷＡＮポートのレートでデータを受信することができれば、アルゴリズムはソフトウェアにおいて実施されることもできる。以下の機能がハードウェアにおいて実施されるならば、より遅いプロセッサが公正性アルゴリズムを実施するために使用されることができる。
【００８６】
−タンデム・レート評価器。
−追加レート評価器。
−下流レート受信ブロック。
−宣伝レート送信ブロック。
【００８７】
発明を最も現実的かつ好ましい実施形態に関連づけて説明したけれども、発明が開示された実施形態に制限されないことは理解されるべきである。しかしながら本発明は、請求項の範囲内に含まれる様々な改良、変形、改造、および同様の装置に及ぶことを意図されている。請求の範囲は、そのような改修並びに同様の構造および機能を取り込むことができるように広く解釈されるべきである。
【図面の簡単な説明】
【図１】図１は、双方向リングネットワークを図示する。
【図２】図２は、図１の双方向リングネットワークの一部分を図示する。
【図３】図３は、図１の双方向リングネットワークのノードを図示する。
【図４】図４は、本発明を具体化する公平性アルゴリズムを表すフローチャートである。
【図５】図５は、本発明を具体化する図１の双方向リングネットワークのノードを図示する。
【図６】図６は、本発明を具体化する公正性アルゴリズムを表す状態図である。
【図７】図７は、双方向リングネットワークにおける４つのノードを図示する。
【符号の説明】
１０        ノード
１５      リング−１
２０      リング−２
２５      ＷＡＮ入口ポート
３０      ＷＡＮ出口ポート
【図１】
0004605859.tif 000002
【図２】
0004605859.tif 000003
【図３】
0004605859.tif 000004
【図４】
0004605859.tif 000005
【図５】
0004605859.tif 000006
【図６】
0004605859.tif 000007
【図７】
0004605859.tif 000008