(57)【要約】【課題】  様々なトラフィック・タイプの組合せを効率的かつ公平に処理するためのネットワーク・フロー制御メカニズムを提供すること。【解決手段】  ネットワーク・デバイス１のリソース３に対応するキュー４への複数のデータ・パケット・フローのフロー・レートを制御するための方法および装置が提供される。フローは、無応答フローのセット７と、応答フローまたは応答性が未知のフロー、あるいはその両方を有する可能性のある他のフローのセット８とを有する。フロー・レートはキュー管理方式に従って管理され、その結果として、リソース内の超過帯域幅に依存して各フロー・レートが調整され、調整量は各フローに対する１つまたは複数の調整パラメータに依存する。フロー・セット７、８に対するキュー４への合計フロー・レートの比率の所望の割り振り比率からの偏差に基づいて、エラー信号が生成される。その後、少なくとも１つのフローに対する少なくとも１つの調整パラメータが、エラー信号に依存して前述の偏差を減少させるような方法で変更される。このようにして、閉ループ制御方式は、基礎となるキュー管理方式と共に動作し、たとえ無応答および応答の両フローの組合せが存在する場合であっても、公平な帯域幅割り振りを促進させるように動作する。
2006511137.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための方法であって、前記複数のフローは無応答フローのセットおよび他のフローのセットを有し、前記方法が、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するステップであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するステップと、
前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存して、エラー信号を生成するステップと、
前記偏差を削減するために、エラー信号に依存して前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを変更するステップと、
を有する、方法。
【請求項２】
前記他のフローが応答フローを有する、請求項１に記載の方法。
【請求項３】
前記セットのうちの１つのみの各フローに対する少なくとも１つの調整パラメータがエラー信号に依存して変更される、請求項１に記載の方法。
【請求項４】
前記セットのうちの１つのみの各フローに対する単一の調整パラメータがエラー信号に依存して変更される、請求項１に記載の方法。
【請求項５】
前記フロー・レートは前記キュー管理方式に従って第１の期間で定期的に調整され、前記調整パラメータは第１の期間よりも長い第２の期間で定期的に変更される、請求項１に記載の方法。
【請求項６】
前記キュー管理方式に従って、各フロー・レートは、超過帯域幅が使用可能な場合は増加パラメータに応じた量だけ増加し、超過帯域幅が使用不能な場合は減少パラメータに応じた量だけ減少し、
前記セットのうちの少なくとも１つの少なくとも１つのフローに対する増加パラメータおよび減少パラメータのうちの少なくとも１つが、エラー信号に依存して変更される、請求項１に記載の方法。
【請求項７】
前記キュー管理方式がＢＡＴ方式を有する、請求項６に記載の方法。
【請求項８】
前記無応答フロー・セットのうちの少なくとも１つのフローに対する前記減少パラメータが、エラー信号に依存して変更される、請求項６に記載の方法。
【請求項９】
前記無応答フロー・セットの各フローに対する前記減少パラメータが、エラー信号に依存して変更される、請求項８に記載の方法。
【請求項１０】
前記フロー・レートは前記キュー管理方式に従って第１の期間で定期的に調整され、前記減少パラメータは前記第１の期間よりも長い第２の期間で定期的に変更される、請求項９に記載の方法。
【請求項１１】
各フローに対する前記パラメータの前記変更に最大制限値を適用することを含む、請求項９に記載の方法。
【請求項１２】
フローのフロー・レート管理ステップに対する入力フロー・レートの関数としてフローの前記最大制限値を計算することを含む、請求項１１に記載の方法。
【請求項１３】
前記キュー管理方式に従って、フロー・レートがフローの最低保証レートを超えた場合に超過帯域幅に依存したフロー・レートの調整が実行され、前記方法は、フローのフロー・レート管理ステップに対する入力フロー・レートが前記フローの前記最低保証レートを下回った場合に、前記フローの前記減少パラメータの変更を抑制することを含む、請求項９に記載の方法。
【請求項１４】
前記減少パラメータの変更の抑制中に、前記減少パラメータを前記抑制の開始時点の値で維持することを含む、請求項１３に記載の方法。
【請求項１５】
前記減少パラメータは前記エラー信号に依存して一定の時間間隔で変更され、前記方法は、前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させることを含む、請求項１３に記載の方法。
【請求項１６】
前記無応答フローのセットについて、前記所望の割り振り比率および前記キューの所定の最大リンク帯域幅に依存して、前記キュー管理ステップに対する合計入力フロー・レートがしきい値を下回った場合に、前記フローの減少パラメータの変更を抑制することを含む、請求項９に記載の方法。
【請求項１７】
前記減少パラメータの変更の抑制中に、前記減少パラメータを前記抑制の開始時点の値で維持することを含む、請求項１６に記載の方法。
【請求項１８】
前記減少パラメータは前記エラー信号に依存して一定の時間間隔で変更され、前記方法は、前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させることを含む、請求項１６に記載の方法。
【請求項１９】
前記所望の割り振り比率に反比例する、所定の初期値からの前記減少パラメータの変更を開始することを含む、請求項９に記載の方法。
【請求項２０】
前記減少パラメータの変更の開始時に、前記合計フロー・レートの比率に依存して前記減少パラメータの初期値を選択することを含む、請求項９に記載の方法。
【請求項２１】
ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための装置であって、前記複数のフローは、無応答フローのセットおよび他のフローのセットを有し、前記装置は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するためのキュー・マネージャであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するキュー・マネージャと、
前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを制御するための調整コントローラであって、前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存してエラー信号を生成するように、および、前記偏差を削減するためにエラー信号に依存して少なくとも１つの調整パラメータを変更するように、配置構成された調整コントローラと、
を有する装置。
【請求項２２】
前記調整コントローラが、前記セットのうちの１つのみの各フローに対する少なくとも１つの調整パラメータをエラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２３】
前記セットのうちの１つのみの各フローに対する単一の調整パラメータをエラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２４】
前記キュー・マネージャがキュー管理方式に従って前記フロー・レートを管理するように配置構成され、前記フロー・レートが第１の期間で定期的に調整され、前記調整コントローラが、前記第１の期間よりも長い第２の期間で前記調整パラメータを定期的に変更するように配置構成された、請求項２１に記載の装置。
【請求項２５】
前記キュー・マネージャがキュー管理方式に従って前記フロー・レートを管理するように配置構成され、各フロー・レートが、超過帯域幅が使用可能な場合は増加パラメータに応じた量だけ増加し、超過帯域幅が使用不能な場合は減少パラメータに応じた量だけ減少し、
前記調整コントローラが、前記セットのうちの少なくとも１つの少なくとも１つのフローに対する増加パラメータおよび減少パラメータのうちの少なくとも１つを、エラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２６】
前記キュー管理方式がＢＡＴ方式を有する、請求項２５に記載の装置。
【請求項２７】
前記調整コントローラが、前記無応答フロー・セットのうちの少なくとも１つのフローに対する前記減少パラメータをエラー信号に依存して変更するように配置構成された、請求項２５に記載の装置。
【請求項２８】
前記調整コントローラが、前記無応答フロー・セットの各フローに対する前記減少パラメータをエラー信号に依存して変更するように配置構成された、請求項２７に記載の装置。
【請求項２９】
前記キュー・マネージャが、前記キュー管理方式に従って前記フロー・レートを管理するように配置構成され、前記フロー・レートは第１の期間で定期的に調整され、前記キュー・マネージャが、前記減少パラメータを前記第１の期間よりも長い第２の期間で定期的に変更するように配置構成された、請求項２８に記載の装置。
【請求項３０】
前記調整コントローラが、各フローに対する前記パラメータの前記変更に最大制限値を適用するように配置構成された、請求項２８に記載の装置。
【請求項３１】
前記調整コントローラが、フローの前記キュー・マネージャに対する入力フロー・レートの関数としてフローの前記最大制限値を計算するように配置構成された、請求項３０に記載の装置。
【請求項３２】
前記キュー・マネージャが、前記キュー管理方式に従って前記フロー・レートを管理するように配置構成され、フロー・レートがフローの最低保証レートを超えた場合に超過帯域幅に依存したフロー・レートの調整が実行され、
前記調整コントローラが、フローの前記キュー・マネージャに対する入力フロー・レートが前記フローの前記最低保証レートを下回った場合に、前記フローの前記減少パラメータの変更を抑制するように配置構成された、
請求項２８に記載の装置。
【請求項３３】
前記減少パラメータの変更の抑制中に、前記調整コントローラが前記減少パラメータを前記抑制の開始時点の値で維持するように、前記調整コントローラが配置構成された、請求項３２に記載の装置。
【請求項３４】
前記調整コントローラが、前記減少パラメータを前記エラー信号に依存して一定の時間間隔で変更するように、ならびに前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させるように、配置構成された、請求項３２に記載の装置。
【請求項３５】
前記調整コントローラが、前記無応答フローのセットについて、前記所望の割り振り比率および前記キューの所定の最大リンク帯域幅に依存して、前記キュー・マネージャに対する合計入力フロー・レートがしきい値を下回った場合に、減少パラメータの変更を抑制するように配置構成された、請求項２８に記載の装置。
【請求項３６】
前記調整コントローラが、前記減少パラメータの変更の抑制中に、前記調整コントローラが前記減少パラメータを前記抑制の開始時点の値で維持するように配置構成された、請求項３５に記載の装置。
【請求項３７】
前記調整コントローラが、前記減少パラメータを前記エラー信号に依存して一定の時間間隔で変更するように、ならびに前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させるように、配置構成された、請求項３５に記載の装置。
【請求項３８】
前記調整コントローラが、前記所望の割り振り比率に反比例する、所定の初期値からの前記減少パラメータの変更を開始するように配置構成された、請求項２８に記載の装置。
【請求項３９】
前記調整コントローラが、前記減少パラメータの変更の開始時に、前記合計フロー・レートの比率に依存して前記減少パラメータの初期値を選択するように配置構成された、請求項２８に記載の装置。
【請求項４０】
通信ネットワークにおいてデータ・パケットを処理するためのネットワーク・デバイスであって、前記デバイスは、データ・パケットのキューに関連付けられたリソースと、前記キューへの無応答フローのセットおよび他のフローのセットを有する複数のデータ・パケット・フローのフロー・レートを制御するためのフロー制御論理とを有し、前記フロー制御論理は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するためのキュー・マネージャであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するキュー・マネージャと、
前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを制御するための調整コントローラであって、前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存してエラー信号を生成するように、および、前記偏差を削減するためにエラー信号に依存して少なくとも１つの調整パラメータを変更するように、配置構成された調整コントローラと、
を有する、ネットワーク・デバイス。
【請求項４１】
データ・パケットのキューに関連付けられたリソースを有するネットワーク・デバイスのプロセッサに、前記キューへの無応答フローのセットおよび他のフローのセットを有する複数のデータ・パケット・フローのフロー・レートを制御するためのフロー制御方法を実行させるためのコンピュータ読取り可能プログラム・コード手段を具体化しているコンピュータ使用可能メディアを有するコンピュータ・プログラムであって、前記フロー制御方法が、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するステップであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するステップと、
前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存して、エラー信号を生成するステップと、
前記偏差を削減するために、エラー信号に依存して前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを変更するステップと、
を有する、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、データ通信ネットワークにおけるフロー制御に関し、より具体的には、ネットワーク・デバイスのデータ・パケット・キューへのフロー・レートを制御するための方法および装置に関する。
【背景技術】
【０００２】
データ・パケットの処理に関与するネットワーク・デバイスの任意のリソースが、そのパケット処理可能レートを上回るレートでパケットを受け取った場合、パケットはバックアップされ、事実上データ・パケットのキューが生じることになる。一般に、様々なフローからデータ・パケットのキューへの伝送を管理するためにフロー制御メカニズムが提供され、ここで「フロー」とは、特定のソース・グループからのパケットまたは特定のプロトコルに準拠したパケット、あるいはたとえば特定クラスのサービスを必要とするパケットなどの、データ・パケットの何らかの定義されたセットまたはカテゴリのことである。具体的に言えば、リソース内での帯域幅の可用性に従って、各フローに関するキューへのフロー・レート（すなわち、エンキューイング・レートまたは「サービス・レート」）を制御するために、キュー管理方式をインプリメントすることができる。帯域幅の可用性は、通常、超過（ｅｘｃｅｓｓ）帯域幅（すなわち、予備または未使用の帯域幅）がオペレーションに使用できるかどうかを示す、何らかの形のキュー長さのしきい値分け技法によって査定される。その後フロー・レートは、特定フローに関するいずれかの保証されたサービス仕様に合致しながらも、フロー間で帯域幅を公平に共有するように保証する目的で、それに応じて制御される。たとえば、ＲＥＤ（Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ）などのＡｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔ（ＡＱＭ）方式およびその変形は、入力パケットを確率的にドロップすること（またはネットワーク輻輳を示すようにパケットをマークすること）によってフロー・レートを制御し、それぞれのフローについてのドロップ確率はキュー・レベルに基づいて定義された形で増加または減少する。Ｂａｎｄｗｉｄｔｈ  Ａｌｌｏｃａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ（ＢＡＴ）と呼ばれる最近のＡＱＭ方式については、２００２年２月付けのボーウェン等による「Ａｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔによる無応答フローの帯域幅割り振り」ブロードバンド通信国際チューリッヒ・セミナー、ＩＺＳ  ２００２に記載されている。この方式は、加法増加乗法減少（ＡＩＭＤ）制御アルゴリズムのファミリーに属し、キュー・レベルだけでなくキュー・レベルの変化率も感知することによって超過帯域幅を監視する。
【０００３】
このようにしてキュー管理方式は、ローカル輻輳レベルに基づいてフロー・レートを制御し、キューが対応する特定のローカル・リソース内の超過帯域幅に基づいてフロー・レートを調整する。追加のフロー制御メカニズムもネットワーク規模レベルで動作可能である。具体的に言えば、あるネットワーク・プロトコルが「応答（ｒｅｓｐｏｎｓｉｖｅ）」としてクラス分けされる。応答プロトコルは、ネットワークのいずれかの場所で輻輳状況が発生していることを示す、パケットのドロップまたはマーク付けなどのイベントに基づいてフロー・レートを調整するための何らかのメカニズムを提供する。たとえば、ＴＣＰ（伝送制御プロトコル）などのインターネット・プロトコルはエンドツーエンド・バックオフ・メカニズムを組み込んでおり、これによってデバイスは、輻輳が感知された場合に低いレートでデータを送信する。採用している特定のメカニズムに応じて様々な応答プロトコルが様々なレベルの応答性を提供することが可能であるが、すべてがある程度の輻輳制御をローカルよりも広いレベルで提供する。ＵＤＰ（ユーザ・データグラム・プロトコル）などの他のネットワーク・プロトコルは無応答（ｎｏｎ−ｒｅｓｐｏｎｓｉｖｅ）としてクラス分けされる。これらのプロトコルは、ネットワーク内の輻輳に関係なく同じレートでデータを送信し続ける。したがって無応答プロトコルは、輻輳制御を処理するためのローカル・メカニズムに依拠する。
【０００４】
典型的なネットワークは、様々な異なるプロトコルに準拠するトラフィックをサポートすることが可能であるため、応答と無応答の両方のトラフィックを搬送することができる。
【非特許文献１】２００２年２月付けのボーウェン等による「Ａｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔによる無応答フローの帯域幅割り振り」ブロードバンド通信国際チューリッヒ・セミナー、ＩＺＳ  ２００２
【非特許文献２】「コンピュータ・システムの性能分析技法」ラジ・ジャイン、ワイリー、１９９１年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって一般に、様々なトラフィック・タイプの組合せを効率的かつ公平に処理するためのネットワーク・フロー制御メカニズムが求められている。
【課題を解決するための手段】
【０００６】
本発明は、応答フローおよび無応答フローの組合せを処理する場合に、既存のキュー管理方式で深刻な問題が生じるという認識に基づくものである。具体的にいえば、応答フロー・レートは応答バックオフ・メカニズムによって自動的に低減されるのに対して、無応答フロー・レートは低減されない。これは、無応答フローが応答フローを「阻止（ｃｈｏｋｅ  ｏｕｔ）」して、ローカル・レベルのすべての超過帯域幅を取ることを意味する。これは、キュー管理システムによって処理されるすべてのフロー間での基礎となる公平な帯域幅割振りの達成に真っ向から反することである。
【０００７】
本発明の一態様は、ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための方法を提供し、複数のフローは無応答フローのセットおよび他のフローのセットを有する。この方法は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従ってフロー・レートを管理するステップであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するステップと、
前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存して、エラー信号を生成するステップと、
前記偏差を削減するために、エラー信号に依存して前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを変更するステップと、
を有する。
【０００８】
したがって本発明を具体化する方法は、無応答フローのセットおよび他のフローのセットを有する複数のフローについてキューへのフロー・レート（すなわち、サービス・レート）を制御する。各セットは１つまたは複数のフローを有することができるため、極端な場合、この方法は２つのフローに対してだけ動作可能である。第１のセットは無応答であることがわかっているフローを有する。第２のセットは他のフローを有する。これら他のフローは、応答フローであることがわかっているフローとすることができる。しかしながら、フロー制御システムによって処理されるすべてのフローの応答性が、すべての実施形態でわかっているとは限らない。このような場合、第２のセットが、応答性が未知のフローを含む可能性がある。したがって一般に、第２のセットは、無応答であることがわかっていないフローを有する可能性がある。いずれの場合も、フローに関するサービス・レートは、帯域幅の可用性に基づいてフロー・レートを調整するキュー管理方式を介して制御され、各フロー・レートはそのフローの１つまたは複数の調整パラメータに依存した量によって調整される。キュー管理プロセスのオペレーション中に、所望の割り振り比率と２つのフロー・セットの合計サービス・レートの比率との差異に基づいて、エラー信号が生成される。このエラー信号は、２つのフロー・セットの間の帯域幅割り振りの、所望の値からの偏差のインジケーションを提供する。その後このエラー信号を使用して、この偏差を減らすような形で、キュー管理プロセスで使用される少なくとも１つの調整パラメータを変更する。このようにして本発明の諸実施形態は、基礎となるキュー管理方式と共に動作する閉ループ制御方式を提供し、上記で論じた無応答フローによって引き起こされる問題を軽減する。したがって本発明の諸実施形態では、たとえ無応答および応答の両フローの組合せを管理しなければならない困難なトラフィック状況であっても、公平な帯域幅割り振りを達成することができる。したがって、本発明を具体化する方法全体が、従来のシステムに比べて大幅に改善されたフロー制御を提供する。
【０００９】
当業者であれば、キュー管理プロセスによって管理されるキューは実キュー（たとえば、バッファ・メモリ内のデータ・パケットのシーケンス）とするか、またはリソースに関連付けられた論理キューとすることが可能であり、論理キューとは当該リソースのオペレーションの論理抽象化を表すものであることを理解されよう。したがって、キューを単一のメモリにマッピングすること、またはしないことができる。同様に、キューが対応するリソースは、データ・パケットのキューイングに関連付けられた任意のリソースとすることができる。簡単な例として、当該リソースはバッファなどの単一のメモリ・アイテム、またはバッファのセットなどの複数のメモリ・アイテムとすることができる。別の方法として、たとえばリソースは単に何らかの方法でパケットを処理するための制御論理である可能性があり、そのオペレーションは論理キューとして抽象化することができる。したがって一般に当該リソースは、直接または論理抽象化によってパケット処理スループットをキューとして提示することができる任意のデバイス・リソースとすることができる。リソース内の超過帯域幅の可用性は、採用される特定のキュー管理方式に依存して様々な方法で査定可能であることを理解されよう。たとえば超過帯域幅は、キュー占有または何らかのその機能に基づいて、あるいは全体の入力対出力率または実際にリソースの使用の任意の他の尺度に基づいて、査定することができる。
【００１０】
エラー信号は、２つのフロー・セットに関する実際の割り振り比率と所望の割り振り比率との間の偏差に基づいて、様々な方法で導出することができる。本明細書では、「信号」という用語は最も広義に使用される。たとえば、エラー信号は、オペレーション中に定期的に更新される単なる離散的値とすることができる。特定の実施形態では、実際の割り振り比率（すなわち、２つのフロー・セットに関する合計サービス・レート間の比率）またはエラー信号あるいはその両方の決定が、何らかの形の平均化プロセスを含むことができる。
【００１１】
一般に、キュー管理方式で採用される特定の調整パラメータに応じて、１つまたは複数のフローに関する１つまたは複数の調整パラメータはエラー信号に基づいて変更される可能性がある。好ましい実施形態では、帯域幅全体の割り振りの特に効果的な制御と組み合わされたオペレーションを簡略化することは、前記セットのうちの１つのみの各フローについて少なくとも１つの調整パラメータを変更することによって達成される。最も好ましくは、前記セットのうちの１つのみの各フローについて単一の調整パラメータを変更することである。以下で説明する特に好ましい実施形態では、ＢＡＴ方式に従ってキュー管理プロセスが実行され、各フロー・レートは、超過帯域幅が使用可能な場合は増加パラメータに応じた量だけ増加し、超過帯域幅が使用不能な場合は減少パラメータに応じた量だけ減少する。特に効率的なオペレーションは、これらの好ましい実施形態において、無応答フロー・セットの各フローについて減少パラメータを変更することによって達成される。
【００１２】
キュー管理プロセスにおける第１の期間でフロー・レートが定期的に調整される実施形態では、エラー信号に基づいた調整パラメータの変更は、好ましくは第１の期間よりも長い第２の期間で定期的に実行される。本明細書の第２の期間は、好ましくは第１の期間の複数倍であり、たとえば第１の期間よりも少なくとも１桁（ａｎ  ｏｒｄｅｒ  ｏｆ  ｍａｇｎｉｔｕｄｅ）長く、さらに好ましくは第１の期間よりも２桁長い。以下で詳細に説明する特に好ましい実施形態では、調整パラメータの変更は、キュー管理プロセスによってフロー・レート調整の期間よりも３桁長い期間で実行される。キュー管理プロセスよりも長い時間目盛り（ｔｉｍｅ  ｓｃａｌｅ）でパラメータ変更プロセスが動作する場合、２つのプロセス間のいかなる潜在的な競合も禁止されるため、キュー管理プロセスはほぼ平常どおりに動作可能であり、パラメータ変更をより低速にするとこのプロセスに対する改良として作用し、結果として生じる帯域幅割り振りが必要に応じて改善される。本発明を具体化するフロー制御方法の様々な他の好ましい特徴について、以下に記載された特定の例を使用して説明する。
【００１３】
本発明の第２の態様は、ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための装置を提供し、前記複数のフローは、無応答フローのセットおよび他のフローのセットを有する。この装置は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するためのキュー・マネージャであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するキュー・マネージャと、
前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを制御するための調整コントローラであって、前記フロー・セットのキューへの合計フロー・レート比率の、所望の割り振り比率からの偏差に依存してエラー信号を生成するように、および、前記偏差を削減するためにエラー信号に依存して少なくとも１つの調整パラメータを変更するように、配置構成された調整コントローラと、
を有する。
【００１４】
一般に、本明細書では本発明を具体化する方法を参照しながら特徴を説明しており、対応する特徴は本発明を具体化する装置に従って提供することが可能であり、その逆もまた可能であることを理解されよう。
【００１５】
本発明の第３の態様は、通信ネットワークにおいてデータ・パケットを処理するためのネットワーク・デバイスを提供し、前記デバイスは、データ・パケットのキューに関連付けられたリソースと、無応答フローのセットおよび他のフローのセットを有する、キューへの複数のデータ・パケット・フローのフロー・レートを制御するためのフロー制御論理とを有し、フロー制御論理は、本発明の第２の態様に関して上記で定義されたようなキュー・マネージャおよび調整コントローラを有する。
【００１６】
本発明の他の態様は、ネットワーク・デバイスのプロセッサに前述のようなフロー制御方法を実行させるためのコンピュータ・プログラムを提供する。
【００１７】
次に、添付の図面を参照しながら例示的であり限定的でない例を使用して、本発明の好ましい実施形態について説明する。
【発明を実施するための最良の形態】
【００１８】
本発明を具体化するフロー制御システムは、スイッチ、ルータ、ブリッジ、トラフィック・シェイパ（ｓｈａｐｅｒ）、ロード・バランシング・デバイス、ミドルボックス、およびたとえばファイアウォールを組み込んだデバイスなどの、様々なネットワーク・デバイスで採用することができる。一般に、説明されるフロー制御システムは、キューの管理が必要な任意のデバイスで採用することができる。ルータなどの典型的なネットワーク・デバイスでは、デバイスによって受信された着信データ・パケットは、たとえば、メディア・アクセス制御コンポーネントにおけるバッファリング、ネットワークを横切って転送される前の内部スイッチング・ファブリックを横切るパケットの分類および伝送などの、様々な処理段階を経験する。パケットは、特定のデバイス・リソースによるこのプロセス保留処理の様々な段階でキューイングすることができる。本発明を具体化するフロー制御システムをこれらの段階のいずれか１つで採用し、輻輳条件下でのリソースの過負荷を防ぐことができる。次に、こうしたフロー制御システムの特定の例について、図１から３を参照しながら説明する。
【００１９】
図１は、フロー制御システムのオペレーションに関与するデバイスの主な要素を示す、ネットワーク・デバイス１の簡略化された概略図である。図に示されるように、デバイス１は、全体として２に示された、デバイス・リソースに対応するキューへの複数のフローのフロー・レートを制御するためのフロー制御装置を含む。この単純な例では、保護されるリソースは、システムによって管理されるデータ・パケットのキュー４を含むバッファ・メモリ３である。フロー制御装置２は、様々なフローのデータ・パケットを受信し、各フローについて制御されたレートでキュー４にパケットを送信する、キュー・マネージャ５を含む。具体的に言えば、キュー・マネージャ５は、超過帯域幅に基づいて各フロー・レートに対して調整が実行されるキュー管理方式に従って、各フローについてのキューへのフロー・レート、すなわちサービス・レートを管理する。この実施形態では、キュー・マネージャ５は、以下で詳細に述べるように超過帯域幅がキュー占有に応じて決定されるＢＡＴアルゴリズムをインプリメントする。超過帯域幅の可用性は、キュー４からのフィードバック信号として図中に概略的に表された超過帯域幅信号Ｂ（ｔ）で示される。フロー制御装置２は、以下で詳細に説明するように、キュー管理プロセスで使用される特定パラメータの値を制御するための調整コントローラ６も含む。一般にフロー制御装置２は、ハードウェアまたはソフトウェアあるいはそれらの組合せを有する好適に構成された制御論理によってインプリメント可能である。たとえば装置２は、記載された機能を実行するようにプロセッサを構成するソフトウェアを実行中のネットワーク・プロセッサによってインプリメント可能である。好適なソフトウェアは、本明細書の記載から当業者に明らかになろう。（もちろん、こうしたプロセッサは適切なソフトウェアで事前に構成することが可能である一方で、こうしたソフトウェアを構築するプログラム・コードをネットワーク・デバイス内へのローディング用に別に供給し、プロセッサを記載のように動作させるように構成することができる。こうしたプログラム・コードは、独立した要素として、またはいくつかの制御機能に関するプログラム・コードの要素として供給可能であり、ディスケットなどのコンピュータ可読メディアまたはネットワーク・オペレータに対して送信される電子伝送で具体化されるように供給可能である。）
【００２０】
装置２によって制御されるフローは、概念上、説明されるフロー制御方法のオペレーション時に別々に処理される２つの別個のセットに分割される。第１のセットは、無応答であるとして知られるフローを有する。第２のセットは応答であるとして知られるフロー、または応答性が未知であるために潜在的に応答であるとみなされるフロー、あるいはその両方を有する。説明しやすくするために、この実施形態のオペレーションはＴＣＰフローおよびＵＤＰフローの混合について説明するが、図１に示されるように、ＵＤＰフローは無応答フローのセット７を構成し、ＴＣＰフローは応答フローのセット８を構成する。（当業者であれば、ＵＤＰフローが何らかの環境において応答として分類され、その上に重ねられるアプリケーションがフローに何らかの応答メカニズムを賦課する場合があることを理解されよう。ＵＤＰフローは、本明細書では単に無応答フローの手頃な例として使用されており、そのためにＵＤＰフローは無応答として分類される。）各フローは、入力フロー・レートまたは「オファー・レート」Ｏｉで、キュー・マネージャ５によって受信される。キュー・マネージャ５は、一般に上記で参照した文書に記載のＢＡＴ方式に従って、各フローについての伝送部分Ｔｉを定期的に計算する。その後パケットがランダムにドロップされ、フローに対するサービス・レートＴｉ・Ｏｉが達成される。キュー・マネージャ５で採用されるＢＡＴ方式によれば、伝送部分の計算は期間ｄｔで実行され、時間（ｔ＋ｄｔ）での各フローに対する伝送部分Ｔｉは以下のように与えられ、
Ｔｉ（ｔ＋ｄｔ）＝ｍｉｎ（１，Ｔｉ（ｔ）＋ｗ）  ｉｆ      ｆｉ（ｔ）＜ｆｉｍｉｎ
Ｔｉ（ｔ）（１−ｗ）            ｅｌｓｅ  ｉｆ    ｆｉ（ｔ）＞ｆｉｍａｘ
ｍｉｎ（１，Ｔｉ（ｔ）＋Ｃｉ＊Ｂａｖｇ（ｔ））    ｅｌｓｅ  ｉｆ    Ｂ（ｔ）＝１
ｍａｘ（０，Ｔｉ（ｔ）（１−Ｄｉ＊Ｏｉ（ｔ）））    ｏｔｈｅｒｗｉｓｅ
上式で、ｆｉ（ｔ）＝Ｔｉ（ｔ）＊Ｏｉ（ｔ）は時間ｔでのフローに対するサービス・レートであり、
ｗはフローに対する所定の定数であり（０＜ｗ＜１）、
ｆｉｍｉｎおよびｆｉｍａｘはフローに対して保証された最低および最高のサービス・レートであり、
Ｂａｖｇ（ｔ）はＢ（ｔ）の指数重み付け移動平均であり、
Ｏｉ（ｔ）は時間ｔでのフローに対するオファー・レートであり、
パラメータＣｉおよびＤｉは、基本ＢＡＴ方式でのフローに対する所定の定数である。
超過帯域幅信号Ｂ（ｔ）は、以下のように与えられ、
Ｂ（ｔ）＝１    ｉｆ                Ｑ（ｔ）＜ｑｍｉｎ
０    ｅｌｓｅ  ｉｆ      Ｑ（ｔ）＞ｑｍａｘ
１    ｅｌｓｅ  ｉｆ      ｄＱ（ｔ）／ｄｔ＜ｄｍｉｎ＜０
０    ｏｔｈｅｒｗｉｓｅ
上式で、Ｑ（ｔ）は時間ｔでの合計キュー長さであり、ｑｍｉｎ、ｑｍａｘ、およびｄｍｉｎは所定のしきい値である。したがって、キュー長さがしきい値ｑｍｉｎより下である場合、およびキュー長さの減少レートがしきい値レートｄｍｉｎより大きい場合に、超過帯域幅は使用可能であるとみなされる（すなわちＢ（ｔ）＝１）ことがわかる。サービス・レートｆｉ（ｔ）がフローに対する最低および最高の保証レートｆｉｍｉｎとｆｉｍａｘとの間である場合、ＢＡＴ方式では、超過帯域幅に基づいて伝送部分Ｔｉの調整を介してサービス・レートを調整する。これらの調整量は、とりわけ、調整パラメータＣｉおよびＤｉの値に依存する。具体的に言えば、超過帯域幅が使用可能である場合（Ｂ（ｔ）＝１）、サービス・レートは増加パラメータＣｉに基づく量だけ線形に増加する。超過帯域幅が使用不能である場合（Ｂ（ｔ）＝０）、サービス・レートは減少パラメータＤｉに基づく量だけ指数関数的に減少する。
【００２１】
前述のように、従来技術の基本ＢＡＴ方式では、増加および減少パラメータＣｉおよびＤｉは各フローに対して指定された定数である。しかしながら本実施形態では、無応答のＵＤＰフロー７のそれぞれに対する減少パラメータＤｉは経時的に変化する。図１の調整コントローラ６は、すべてのフローについてサービス・レートｆｉを監視し、所望の帯域幅割り振り比率ｒｄと共にこれらを使用して、ＵＤＰフローの値Ｄｉを変更する。ここで所望の比率ｒｄはシステム・オペレータが設定するか、またはシステムに提供されたリソース管理ソフトウェア（図示せず）が供給することができる。このプロセスにおける調整コントローラ６の一般的なオペレーションが、図２の流れ図に示されている。ＵＤＰ減少パラメータＤｉＵＤＰの変更は、期間ｄｔよりも長い期間Δｔで定期的に実行される。したがってパラメータ変更プロセスは、図２のステップ１０で示されるように時間（ｔ＋Δｔ）ごとに開始される。ステップ１１では、調整コントローラがキュー・マネージャ５から受信したサービス・レートｆｉに基づいて、現在の帯域幅割り振り比率ｒ（ｔ）の値を計算する。この比率ｒ（ｔ）は、すべてのＵＤＰフロー７についての合計サービス・レートとすべてのＴＣＰフロー８についての合計サービス・レートとの比率であり、先行する期間Δｔにわたって取られた複数の測定値を平均化することによって便利に計算される。具体的に言えば、すべてのフローについてのサービス・レートｆｉは、コントローラ６によって期間Δｔの間に定期的にサンプリングすることができる。各サンプリングを使用してＵＤＰフローおよびＴＣＰフローについての個々のレートが別々に合計され、合計のＵＤＰおよびＴＣＰフロー・レートが与えられ、これら合計レートの比率がコントローラ６によって記録される。その後、図２のステップ１１で、サンプリング数全体にわたって記録された比率を平均化することによって、現在の期間Δｔについてのｒ（ｔ）の値が計算される。次にステップ１２では、調整コントローラが現在の割り振り比率ｒ（ｔ）と所望の比率ｒｄとを比較し、これら２つの値の間の偏差に基づいてエラー信号Δｒを生成する。本実施形態では、エラー信号は、Δｒ＝（ｒｄ−ｒ（ｔ））／ｒｄによって与えられる正規化された値である。その後ステップ１３では、コントローラ６が、所望と実際の割り振り比率ｒｄとｒ（ｔ）との間の差異を少なくするように決定される、古いＤｉＵＤＰを変更した減少パラメータＤｉＵＤＰの新しい値を計算する。新しいＤｉＵＤＰ値が計算される特定の方法については、以下でより詳細に説明する。最後にステップ１４では、後続のキュー管理プロセスで使用するための新しいＤｉＵＤＰ値がキュー・マネージャ５に供給される。その後、次の期間Δｔが経過するまでパラメータ変更プロセスが完了し、制御プロセスが繰り返される。
【００２２】
調整コントローラ６のオペレーションが、無応答フローの減少パラメータを変更することによって、応答フローと無応答フローとの間の帯域幅割り振りｒ（ｔ）を制御するための閉ループ制御プロセスを効果的に提供することは明らかであろう。具体的に言えば、減少パラメータは、実際の割り振り比率を所望の値ｒｄにさらに近づけるように変更される。次に、これを達成するためにＤｉＵＤＰ値が変更される特定の方法について、従来の制御エンジニアリング手法から説明する。
【００２３】
図３は、デバイス１で実行されたフロー制御プロセスと比較可能な基本的な制御ループの主要な要素を示す図である。本フロー制御システムでは、図３のプラント２０は、着信トラフィックがキュー４でエンキューイングされ、ある一定の遅延後にデキューイングされる、バッファ３に対応する。図３の測定デバイス２１は、このケースではサービス・レートおよび伝送部分などの必要なシステム情報を記録する。コンパレータ・ツール２２は、制御エラー、すなわち所望の値と実際の値との差異を評価する。このケースでは、１つの制御変数のみに注目しており、その状態を制御エラーの値によって定義していることから、これはエラー信号Δｒである。図３のコントローラ２３は、ある定義された原理に従って制御変数の値を評価する。この信号および妨害入力（たとえばオファリング負荷の振動（ｏｓｃｉｌｌａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ｏｆｆｅｒｅｄ  ｌｏａｄ））がプラントに影響を与えている。コントローラは操作済み変数を生成するように機能して、プラントを所望の状態に維持しながら妨害入力の影響を打ち消す。
【００２４】
この例では、
−このファミリーに必要な定期的な計算努力が比較的少ないこと、
−システムの広範なモデルが望ましいとみなされるが、モデル予測制御方式または観察者の見解とは対照的に、これはこのケースでは厳密には要求されていないこと、および
−比較的単純な構造にもかかわらず、このコントローラ・グループが優秀な結果を達成できること、
といったいくつかの理由から、ＰＩＤ（比例、積分、微分）ファミリーに属するコントローラを選択する。
理想的なＰＩＤコントローラを説明する式は、以下のとおりであり、
【数１】
2006511137.tif 000003
上式で、ｙ（ｔ）は操作済み変数を、ｘｄ（ｔ）は制御エラーを表し、どちらも時間依存変数であって、ＫＲ、ＴＮ、およびＴＶは定数である。大括弧の中の項は左から順に、比例、積分、および微分作用である。
【００２５】
本フロー制御システムは時間的に連続していないため、上記の数式（１）の離散的表記法を使用する。これは、（ａ）数式（１）の時間に関する微分、（ｂ）後方差分を使用する微分近似値、および（ｃ）操作済み変数の実際の値に関する解によって得られる。これにより、一般的な係数を使用した以下の数式が得られる。
ｙｋ＝ｙｋ−１＋ｂ０．ｘｄ，ｋ＋ｂ１．ｘｄ，ｋ−１＋ｂ２．ｘｄ，ｋ−２            （２）
パラメータｂ０、ｂ１、およびｂ２を選択することによって、コントローラの基本プロパティを決定することができる。本手法は、ｂ１，ｂ２≡０を使用して数式（２）から取得される以下の積分コントローラに基づくものであり、
ｙｋ＝ｙｋ−１＋ｂ０．ｘｄ，ｋ                                        （３）
これは、この式が構造ならびに計算努力がさらに削減されるためである。積分項を維持することによって、定常状態エラーがかなり少なくなり、理論的にはゼロになることが保証される。
【００２６】
本フロー制御システムでは、ＤｉＵＤＰは操作済み変数ｙｋであり、制御エラーｘｄ，ｋは前述のエラー信号Δｒである。したがって、数式（３）を使用すると以下の式が得られる。
ＤｉＵＤＰ（ｔ＋Δｔ）＝ＤｉＵＤＰ（ｔ）＋ｂ０．Δｒ                    （４）
制御エラー信号の影響をＤｉＵＤＰの現在の状態に合わせるために、ｂ０＝β. ＤｉＵＤＰ（ｔ），β＜０と定義して、以下のように一般的なバージョンのコントローラを取得する。
ＤｉＵＤＰ（ｔ＋Δｔ）＝ＤｉＵＤＰ（ｔ）＋β. ＤｉＵＤＰ（ｔ）．Δｒ                    （５）
したがって調整コントローラ６は、数式（５）に従って各フローについてＤｉＵＤＰの新しい値を計算する。パラメータβは、所望であればすべてのフローまたは個々のフローについて定数値に設定することが可能であり、当業者であれば好適な値が明らかであろう。しかしながら特に好ましい実施形態では、以下で詳細に論じるように、βの値はエラー信号Δｒの絶対値に基づいて選択される。減少パラメータＤｉＵＤＰの値が適切な方法で変更されることは、数式（５）から明らかである。現在の帯域幅割り振り比率ｒ（ｔ）が所望の比率ｒｄよりも大きい（すなわち、ＵＤＰトラフィックに広すぎる帯域幅が割り振られている）場合、エラー信号Δｒは負となる。β＜０であるため、ＤｉＵＤＰの値は数式（５）によって増加することになり、すなわちＤｉＵＤＰ（ｔ＋Δｔ）＞ＤｉＵＤＰ（ｔ）である。以前に定義されたＢＡＴアルゴリズムを考慮すると、ＤｉＵＤＰが増加すれば結果として伝送部分Ｔｉが減少することがわかる。したがって、ＵＤＰフローの帯域幅シェアは減少しＴＣＰフローのシェアは増加して、結果として比率ｒ（ｔ）は小さくなり、エラー信号の絶対値は減少する。エラー信号Δｒがゼロまで減少すると、ＤｉＵＤＰは調整されない。システムが厳密に所望の状態になり、一時的に調整の必要がないため、これは意図的なことである。
【００２７】
帯域幅割り振りにおける上記のフロー制御システムの効率性は、上記のようにキュー管理方式としてＢＡＴを使用する１つのボトルネック・リンクを伴う、１つのＵＤＰフローおよび多数の同時ＴＣＰフローを使用した単純なシミュレーションから明らかである。システムは、高、中、低の異なる３つの輻輳条件の下でテストされ、この輻輳レベルはＵＤＰのオファリング負荷量によって定義された。高輻輳条件は、２００、１５０、および１００Ｍビット／秒のＵＤＰオファリング負荷で表された。中輻輳条件は、８０、６５、および５０Ｍビット／秒のＵＤＰオファリング負荷で表された。低輻輳条件は、４０、３０、および２０Ｍビット／秒のＵＤＰオファリング負荷で表された。共用出力リンクの容量は、キュー４がドレーンされる最大レートに等しい１００Ｍビット／秒である。それぞれのオファリング負荷について、３つの異なる所望の割り振り比率がテストされ、ＵＤＰフローの実際の帯域幅シェアが所望のＵＤＰシェアと比較されて、一致の度合いが決定された。このシミュレーションの結果が図４の表に示されており、ここでは、前述のオファリング負荷が最高から最低へとなるようにシミュレーション１から９へと進められた。これらの結果は、それぞれ高、中、および低の輻輳状態に関する図５、６、および７のグラフにも示されている。これらの図から、高および中の輻輳状態では、実際と所望のＵＤＰシェアの間で、所望のＵＤＰシェアの１０％の差異のみという高度な一致が達成されていることがわかる。低輻輳状態の場合、すべての所望の割り振り比率について優れた一致が達成されている。同様に、ここでは単純なオペレーションと組み合わされた全体の有効性にとっては積分コントローラが好ましいが、パラメータ変更制御ループにおいて比例プラス積分コントローラを使用したシミュレーションでも良い結果が達成されている。単にＢＡＴフロー制御と比較してみると、帯域幅割振りが改善された全体として効果的なフロー制御が提供されている。次に、基本的なＢＡＴシステムを上回る改善を実証する比較結果について、本発明の諸実施形態に組み込むことができる何らかの追加の改善点について論じる。改善点の中には、無応答トラフィックのシェアが少ないオペレーションを改善するための好ましい特徴が示される。
【００２８】
上記実施形態の第１の修正では、各フローについての減少パラメータＤｉＵＤＰの変更に最大の制限値が適用される。Ｄｉが移送確率Ｔｉに影響を与えることから見て、この制限は望ましい。以下の、ＢＡＴアルゴリズムの重要な項を再検討すると、
Ｔｉ（ｔ＋ｄｔ）＝ｍａｘ（０，Ｔｉ（ｔ）（１−Dｉ.Oｉ(t))）
Dｉが何らかの所与の値よりも大きい場合、Ｔｉ（ｔ＋ｄｔ）＝０であることが明らかである（Oｉ(t)は一般に、単位元（ｕｎｉｔｙ）よりもかなり小さな値を与えるために最大オファリング負荷に正規化される）。こうした環境でDｉが不必要に増加するのを避けるために（実際に小さな値が必要になったときにDｉを減少させるために長い時間がかかる結果となる）、Dｉは好ましくはDｉ∈［０，Ｄｍａｘ］に制限される。制限値Ｄｍａｘは、所与のシステムに対して適宜オペレータ設定とすることが可能であり、一般に、インプリメンテーションを容易にするために使用される正規化に依存することになる。本明細書で説明する好ましい実施形態では、Ｄｍａｘは５０００に設定される。この制限の効果は、前述のようにシミュレーション環境で全般的にテストしてきており、以下のとおりである。
−所望の比率ｒｄ＝０．１５
−非常に高い輻輳状態（２００Ｍビット／秒のＵＤＰトラフィック）でｔ＝５秒から開始
−ｔ＝３０秒で、ＵＤＰオファリング負荷の低輻輳状態（３０Ｍビット／秒のＵＤＰトラフィック）への減少が発生
シミュレーションの結果は図８および９に示されており、図８はＤＵＤＰを制限しない結果を示し、図９はＤｍａｘ＝５０００でＤＵＤＰを制限した結果を示す。低い所望の比率と組み合わされた初期の高輻輳状態は、積分コントローラのＤＵＤＰを強制的に増加させる。制限が設定されていない場合、ＤＵＤＰの値は非常に高い値まで増加することができる。その後、オファリング負荷が大幅に削減された場合、所望の比率に合わせるためにより小さなＤＵＤＰ値が必要である。初期のＤＵＤＰの値が非常に高い場合、より大幅な削減が必要であり、コントローラが調整を実行するのにより長い時間がかかる。制限値Ｄｍａｘを適用することで、図８および９で実証されるようにこの時間枠が大幅に減少される。
【００２９】
代替の実施形態では、フローに対する最大制限値Ｄｍａｘを動的なプロセスで決定することができる。具体的に言えば、Ｄｉに対して（１−Ｄｉ.Ｏｉ（ｔ））＝０を解くことによって、調整コントローラは所与のオファー・レートＯｉ（ｔ）に関してＤｉに対する適切な上限を決定することができる。このプロセスを実施するために必要な追加の処理は、オファー・フロー・レートが広範囲に分散されたシステムにおいて実行する価値がある可能性がある。しかしながら通常は、すべてのフローまたは個々のフローについて適切に設定されたＤｍａｘの定数値で十分であるとみなされ、当業者には好適な値が明らかとなろう。
【００３０】
コントローラのオペレーションにおけるさらなる改善は、適切な時点でパラメータの変更プロセスを抑制することによって達成することができる。具体的に言えば、あるフローに対するオファー・フロー・レートＯｉが、そのフローに対する最低しきい値レートよりも小さい間に、パラメータ変更プロセスを抑制することができる。たとえば、通常、最低帯域幅はサービス品質項目として保証されるが、フローに対してこの帯域幅を占有するように強制することはできない。これが発生している期間、すなわちフロー・レート＜ｆｉｍｉｎの場合、ＢＡＴのオペレーションはＤｉを含む項を無視する。したがって、これまでに説明した諸実施形態では、調整コントローラはＤｉの調整によって所望の比率に合わせようとし続ける。このようにしてＤｉはゼロまで減少する可能性がある。その後、オファリング負荷が増加した場合に、Ｄｉの値が所望のオペレーティング・ポイントから遠く離れている可能性がある。その後、コントローラがＤｉの値を適切な値に戻すように調整する間に遅延が生じることになる。この問題に対処するために、好ましい実施形態では、あるフローに対するオファー・フロー・レートＯｉがそのフローに対する最低保証レートｆｉｍｉｎを下回っている、すなわちＯｉ（ｔ）＜ｆｉｍｉｎの間、通常のパラメータ変更プロセスが抑制される。したがってこうした実施形態では、調整コントローラ６は図１に示されたキュー・マネージャ５から、サービス・レートｆｉだけでなくＵＤＰフローのオファー・レートＯｉも受け取ることができる。別の方法として、コントローラ６は、キュー・マネージャ５からＵＤＰフローの伝送部分Ｔｉを受信し、伝送部分Ｔｉおよびサービス・レートｆｉからオファー・レートＯｉＵＤＰ値を計算することができる。（ここでは、サービス・レートｆｉに基づいて抑制ポイントが決められる間（すなわち、ｆｉ（ｔ）＜ｆｉｍｉｎ）は、オファー・レートを使用することが好ましいことに留意されたい。いかなる時でも最低レートを保証することを望むため、パラメータ変更手順はオファー・レートが最低を下回るとすぐに抑制することが可能であり、いずれかのパケット・ドロップがあれば、すなわちオファリング負荷が最低よりも大きい場合、すぐに再開しなければならない。Ｔｉ（ｔ＋ｄｔ）＝ｍｉｎ（１，Ｔｉ（ｔ）＋ｗ）に従って伝送部分が単位元でなくなる場合があり、サービス・レートは依然として最低を下回るが、その間にオファリング負荷は劇的に増加している可能性があり、他のパラメータ制御が必要となる。）あるフローについてパラメータ変更プロセスが抑制されている間、一部の実施形態ではＤｉの値はその最終算出値で維持され、その後パラメータ制御手順が再開される場合にこの値が開始値となる。図１０のグラフは、このプロセスの効果を単純なシミュレーションで実証するものであり、パラメータ制御が抑制されていない場合ならびに抑制されている場合の、ＵＤＰ／ＴＣＰ割り振り比率のその所望の値からの偏差が示されている。この図から、抑制プロセスの有益な効果が明らかであろう。
【００３１】
他の実施形態では、無応答フローのセットに対する合計オファー・レートが一定のしきい値を下回っている間に、パラメータ制御プロセスの抑制を実行することができる。具体的に言えば、抑制ポイントは、
ｆＵＤＰ，ｃｒｉｔｉｃａｌ＝ｒｄ＊ｍａｘｉｍａｌ  ｌｉｎｋ  ｂａｎｄｗｉｄｔｈ／（１＋ｒｄ）
ｆＴＣＰ，ｃｒｉｔｉｃａｌ＝ｍａｘｉｍａｌ  ｌｉｎｋ  ｂａｎｄｗｉｄｔｈ／（１＋ｒｄ）
によって定義可能であり、上式で、最大リンク帯域幅（ｍａｘｉｍａｌ  ｌｉｎｋ  ｂａｎｄｗｉｄｔｈ）とは、キュー４がドレーンされる最大レートである。ｒｄは前述のような所望の比率であり、一般に、たとえば最高−最低公平性などの任意の種類の公平性定義に基づいて導出することができる。したがって、計は最大リンク帯域幅に対応し、ｆＵＤＰ，ｃｒｉｔｉｃａｌ対ｆＴＣＰ，ｃｒｉｔｉｃａｌの比率はｒｄである。ＯＵＤＰ，ｔｏｔａｌを無応答フロー・セットの合計オファー・レート、ＯＴＣＰ，ｔｏｔａｌを応答フロー・セットの合計オファー・レートとすること。ＯＵＤＰ，ｔｏｔａｌ＞ｆＵＤＰ，ｃｒｉｔｉｃａｌおよびＯＴＣＰ，ｔｏｔａｌ＞ｆＴＣＰ，ｃｒｉｔｉｃａｌの両方である場合、本フロー制御システムは、２つのフロー・セットに対する合計サービス・レートをそれぞれｆＵＤＰ，ｃｒｉｔｉｃａｌおよびｆＴＣＰ，ｃｒｉｔｉｃａｌとするように動作可能である。本発明の諸実施形態では、それ以外の方法でパラメータ変更プロセスを抑制することができる。たとえば、以下で詳細に説明する好ましい実施形態では、上記で定義したように、ＵＤＰフローの合計オファー・レート&#8828;ｆＵＤＰ，ｃｒｉｔｉｃａｌである場合、ＤｉＵＤＰ値の変更が抑制される。
【００３２】
通常のパラメータ制御手順が抑制される期間中に、Ｄｉの値を前述のような最終算出値に維持するか、またはゼロに設定することができる。前者のケースでは、ＴＣＰトラフィックが大量である（すなわち、超過帯域幅がない）ためにＵＤＰトラフィックがさらに減少する可能性がある、という潜在的な欠点がある。これに対して後者のケースでは、システムを悪用して、デバイスを通る無応答トラフィックの量を押し上げてしまう可能性がある。したがって、好ましい実施形態では、調整コントローラ６が各制御期間Δｔ後に所定の量だけＤｉの値を減少させ、通常のパラメータ制御は抑制される。すなわち、コントローラ６は抑制期間中にＤｉの値を漸次減少させる。たとえば、抑制中の各期間Δｔ後に、Ｄｉの値をたとえば１０％などの特定の割合ずつ減少させることができる。制御期間Δｔは典型的にはキュー管理プロセスの制御期間ｄｔよりもかなり長いため、抑制期間中にＤｉの値を減少させることで、正味（ｈｏｎｅｓｔ）量の少ない無応答トラフィックに何らかの公平性が提供される。したがって、オーバシュート期間から恩恵を得るためには、長期間の低いスループットを受け入れなければならないため、システムの悪用にはもはや魅力がなくなる。
【００３３】
一般に、前述のようにＤｉ値を制限することおよび制御手順を抑制することによって、フロー制御が大幅に改善され、ループの統合の結果として不適切なＤｉ値が生じるのを回避し、少量の無応答トラフィックに対するオペレーションを改善し、さらにオファリング負荷の振動によって、移送されたシェアに関して不公平な利点を得るようにシステムを悪用する意図に対抗することができる。次に、上記で論じた様々な好ましい機能を組み込んだフロー制御システムの特定の例について説明し、そのオペレーションをパラメータ制御プロセスのない基本的なＢＡＴフロー制御方式と比較する。
【００３４】
図１１は、これから説明する例における調整コントローラ６のオペレーションを示す概略図であり、ＵＤＰフローとＴＣＰフローの組合せは図１と同様に想定される。この例では、調整コントローラ６の制御期間Δｔは１秒であり、キュー・マネージャ５は４ミリ秒ごとに伝送部分を計算する。コントローラ６はサービスＵＤＰレートとＴＣＰレートとの間の比率を０．１秒に１回測定し、制御期間Δｔにわたる１０の値を平均化してローパス効果を得る。調整コントローラへの入力は、図の入力インターフェース・ブロック３０内に示される。この実施形態では、調整コントローラは、キュー・マネージャ５からのオファーＵＤＰレートＯｉＵＤＰならびにサービス・レートｆｉを受け取る。サービス・レートの場合と同様に、オファー・レートＯｉＵＤＰは定期的にサンプリングされ、制御期間全体にわたって平均化される。ブロック３１から３６は、各制御期間Δｔの終わりにＵＤＰフローのセットに対して実行されるステップを表す。したがって、ステップ３１は制御手順の抑制に関するテストを表し、ここで採用されるテストはＯＵＤＰ，ｔｏｔａｌ≦ｆＵＤＰ，ｃｒｉｔｉｃａｌであり、この式では前述のようにｆＵＤＰ，ｃｒｉｔｉｃａｌ＝ｒｄ＊ｍａｘｉｍａｌ  ｌｉｎｋ  ｂａｎｄｗｉｄｔｈ／（１＋ｒｄ）である。抑制条件が満たされると、ブロック３２に示されるようにＵＤＰフローに対するパラメータ変更が抑制され、各フローに対する古いＤｉＵＤＰの値は１０％減少される。ステップ３１で抑制条件が満たされない場合、ステップ３３でコントローラは、これが抑制期間に続く第１の調整サイクルであるかどうかをチェックする。第１の調整サイクルである場合、ステップ３４に示されるように、各フローに対するＤｉＵＤＰの回復値がその最終算出値である。現在のサイクルがステップ３３の抑制からの回復でない場合、図３５に示されるように、現在のサイクルに対して生成されたエラー信号Δｒに基づいて各フローに対する新しいＤｉＵＤＰの値が計算される。この実施形態では、パラメータβに対して３つの異なる値が採用されることに留意されたい。選択されるβの特定の値は、現在のサイクルのエラー信号Δｒの絶対値に依存する。具体的に言えば、この例ではβは以下のように設定される。
β＝  ０．５    ｉｆ              Δｒ２＞０．０１
０．３３  ｅｌｓｅ  ｉｆ    Δｒ２＞０．１
０．０５  ｏｔｈｅｒｗｉｓｅ
次にステップ３６は、ステップ３５で計算されたＤｉＵＤＰの新しい値に、示された上限および下限を課す。その後、適宜ステップ３２、３４、または３６から、出力インターフェース・ブロック３７によって示されるように各ＵＤＰフローに関する新しいＤｉＵＤＰの値がキュー・マネージャに出力される。
【００３５】
上記システムの有効性を実証するために、一方が基本ＢＡＴキュー管理システムのみを使用し、他方がキュー・マネージャ５でのＢＡＴキュー管理および図１１のパラメータ制御をインプリメントする調整コントローラ６を備えた本実施形態のフロー制御システムを使用する、という点を除いて同一のシミュレーション・セットアップを使用する。シミュレーション・セットアップは、以下のとおりである。
−１００Ｍビット／秒の１つのボトルネック・リンク
−９０Ｍビット／秒の固定ビット・レートの１つのＵＤＰフロー
−１つの貪欲な（ｇｒｅｅｄｙ）ＴＣＰフロー
調整コントローラ６は、
【数２】
2006511137.tif 000004
という所望の比率ｒｄでリンク帯域幅を割り振るように設定される。結果は図１２および１３に示されており、図１２は基本ＢＡＴ方式に関する結果を示し、図１３は本発明の本実施形態に関する結果を示している。図１２は、応答フローおよび無応答フローの両方を備えた基本ＢＡＴ方式を使用して、所望の比率と実際の比率との間の許容不可能な差異を明確に実証している。この性質（ｂｅｈａｖｉｏｒ）は、公平性指標の分布からも明らかである。（公平性指標は、「コンピュータ・システムの性能分析技法」ラジ・ジャイン、ワイリー、１９９１年に定義されており、以下の式によって得られ、
公平性＝（ｘ１／ｗ１＋ｘ２／ｗ２）^２／（２*（（ｘ１／ｗ１）^２＋（ｘ２／ｗ２）^２））
上式で、ｘ１、ｘ２は測定レートｆｉ（ｔ）であり、ｗ１、ｗ２はｗ１＝ｒｄ／（１＋ｒｄ）およびｗ２＝１／（１＋ｒｄ）によって得られる重みである。）本発明を具体化するフロー制御システムによって改善が見られることは、図１３から明白である。ＵＤＰ／ＴＣＰ比率ｒ（ｔ）は依然として変動しているが、所望の比率付近で小刻みに変動するようになっており、その平均は非常に良好な値である。この改善は、図１２よりもかなり緊密な公平性指標でも反映されている。
【００３６】
上記実施形態は、バウンスするＵＤＰオファリング負荷の条件でもテストされた。前述のシミュレーション・セットアップは、次のように変更された。
−依然として１つのＵＤＰフローがあるが、そのビット・レートは、５秒のタイム・ステップで５０Ｍビット／秒と１２０Ｍビット／秒の固定ビット・レート間でバウンスしている
−所望のＵＤＰ／ＴＣＰ比率ｒｄが０．４に設定される
このシミュレーションの結果は図１４および１５に提示される。ここでプロットは、コントローラが始動段階にわたってそれ自体をシステムに合うように調整した時点のｔ＝３０秒から開始されている。図１４では、ＵＤＰおよびＴＣＰサービス・レートは、ＵＤＰトラフィック・パターンと並んで表される。図１５は、実際と所望のＵＤＰ／ＴＣＰ比率を比較し、公平性指標も示している。これらの図から、たとえより複雑なトラフィック・パターンが存在する場合であっても、本フロー制御システムが効果的であることが明らかである。図１３にはショート・スパイクが存在するが、この状況は迅速に通常に戻っている。
【００３７】
最終シミュレーションは、本フロー制御システムの汎用性および堅固さを実証する。シミュレーション・セットアップは図１４および１５の場合と同じであるが、ここでは上記で参照したラジ・ジャインのテキストで論じられるようなパレート・オン／オフ分散ＴＣＰフローを使用している。図１６は、基本ＢＡＴ方式のみを使用した結果を示し、図１７は本フロー制御システムでの結果を示す。ここでも本フロー制御システムは、明らかにＢＡＴ方式よりも優れている。
【００３８】
一般にオペレータは、所望の割り振り比率ｒｄを所与のフロー制御システムにとって適切な値に設定することが可能であり、当業者であれば好適な値が明らかとなろう。具体的に言えば、所与のケースでの適切な値は、通常、システム内の確実なレートｆｉｍｉｎおよびｆｉｍａｘの関数として決定することができる。加えて、無応答フローの各減少パラメータＤｉＵＤＰに対する開始値は、基本ＢＡＴ方式に対して通常の方法で計算された定数Ｄｉ値に基づいて設定することができる。しかしながら本発明の特定の実施形態では、初期のＤｉＵＤＰ値は、所望の比率ｒｄとＤｉＵＤＰの初期値との間の双曲線コヒーレンスの発見的観察に基づいて設定することができる。具体的に言えば、初期のＤｉＵＤＰ値は
ＤｉＵＤＰ（ｔ＝０）＝定数／ｒｄ
に応じて設定可能であり、上式で定数はすべての無応答フローについて設定可能である。ここでも、当業者には好適な値が明らかとなろう。これによって受け入れ可能な結果が提供される一方で、性能改善が達成可能であり、基本ＢＡＴ方式に基づく開ループ制御方式を使用して経験的に取得されたｒｄ値とＤｉＵＤＰ値との間の関係曲線から、調整コントローラ６が初期のＤｉＵＤＰ値を選択する。これらの値は、調整コントローラ６が使用するルックアップ・テーブルに提供することができる。ＤｉＴＣＰ値は、基本ＢＡＴ方式からわかったデフォルトの値に設定することができる。
【００３９】
上記の内容から、本発明の諸実施形態によって、応答フローと無応答フローの組合せで、たとえ困難なトラフィック状況であっても公平な帯域幅割り振りが可能な、かなり効率の良いフロー制御が提供されることが明らかであろう。さらに、上記で論じた好ましい実施形態では、無応答フローに対して単一の調整パラメータを変更するだけでこれが達成される。加えて、パラメータ変更制御は、基礎となるキュー管理方式よりもかなり遅い時間目盛りで実行することが可能であるため、パラメータ制御は特にソフトウェア・インプリメンテーションに適している。
【００４０】
以上、特定の実施形態について例を挙げて説明してきたが、もちろんこれらの実施形態に対して多くの変更および修正を想定することができる。例を挙げると、パラメータ制御手順の抑制は上記の実施形態における最低のしきい値レートに基づくものであるが、最高の保証レートを超えている場合、所望であればパラメータ制御手順を抑制するためのメカニズムも提供することができる。他の例として、上記システムでは、応答および無応答のフロー・セットのいずれかまたは両方について、パラメータＤｉおよびＣｉのいずれかまたは両方を適切に調整し、エラー信号を減少させることが可能である。にもかかわらず、フローの１セットのみについての信号調整パラメータの調整は、インプリメンテーションの簡潔さにとって好ましい。ＢＡＴ以外のキュー管理方式を本発明の諸実施形態で採用することも可能であり、パラメータ変更プロセスによって制御される調整パラメータは適宜選択される。また、パケットはキュー・マネージャ５がドロップするのではなくマーク付けすることも可能である。この場合、ドロップされたであろうパケットは単に輻輳を示すようにマーク付けされ、マーク付けされていないパケットと共にキューに伝送される。したがって、ここで、マーク付けされていないパケットのキューへのフロー・レート（すなわちサービス・レート）がキュー・マネージャ内の伝送部分の調整を介して制御されることが効果的である。さらに上記では、応答フローおよび無応答フローの手頃な例としてＴＣＰフローおよびＵＤＰフローを使用したが、もちろん本発明を具体化する方法は他のプロトコル・フローを用いても適用可能である。パラメータ変更プロセスは、上記で具体的に述べた基本制御数式以外の数式も利用することができる。さらに一般には、本発明を具体化するフロー制御方法によって、フロー制御システムの別々のインスタンスをそれぞれのキューに提供することで、複数のキューを制御することができる。本発明の趣旨および範囲の中で、前述の実施形態に対して多くの他の変更および変形を実行することができる。
【図面の簡単な説明】
【００４１】
【図１】本発明を具体化するフロー制御システムを組み込んだネットワーク・デバイスを示す概略図である。
【図２】図１のデバイスの調整コントローラのオペレーションを示す流れ図である。
【図３】基本的な制御システムを示すブロック図である。
【図４】３つの異なる輻輳条件の下で、本発明を具体化するフロー制御システムに関するシミュレーション結果を示す表である。
【図５】輻輳条件について、図４の結果を示すグラフである。
【図６】輻輳条件について、図４の結果を示すグラフである。
【図７】輻輳条件について、図４の結果を示すグラフである。
【図８】フロー制御システムの改良された実施形態を実証するシミュレーションの結果を示す図である。
【図９】フロー制御システムの改良された実施形態を実証するシミュレーションの結果を示す図である。
【図１０】フロー制御システムの他の改良された実施形態を実証するシミュレーションの結果を示す図である。
【図１１】フロー制御システムの他の実施形態における調整コントローラのオペレーションを示す概略図である。
【図１２】図１１の実施形態での第１のシミュレーションの結果を示す図である。
【図１３】図１１の実施形態での第１のシミュレーションの結果を示す図である。
【図１４】図１１の実施形態での第２のシミュレーションの結果を示す図である。
【図１５】図１１の実施形態での第２のシミュレーションの結果を示す図である。
【図１６】図１１の実施形態での第３のシミュレーションの結果を示す図である。
【図１７】図１１の実施形態での第３のシミュレーションの結果を示す図である。
【図１】
2006511137.tif 000005
【図２】
2006511137.tif 000006
【図３】
2006511137.tif 000007
【図４】
2006511137.tif 000008
【図５】
2006511137.tif 000009
【図６】
2006511137.tif 000010
【図７】
2006511137.tif 000011
【図８】
2006511137.tif 000012
【図９】
2006511137.tif 000013
【図１０】
2006511137.tif 000014
【図１１】
2006511137.tif 000015
【図１２】
2006511137.tif 000016
【図１３】
2006511137.tif 000017
【図１４】
2006511137.tif 000018
【図１５】
2006511137.tif 000019
【図１６】
2006511137.tif 000020
【図１７】
2006511137.tif 000021
【手続補正書】
【提出日】平成17年1月28日(2005.1.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための方法であって、前記複数のフローは無応答フローのセットおよび他のフローのセットを有し、前記方法が、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するステップであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するステップと、
所望の割り振り比率と、無応答フロー・セットについての合計サービス・フロー・レートに対する他のフロー・セットについての合計サービス・フロー・レートの比率との間の、差異に依存してエラー信号を生成するステップと、
前記偏差を削減するために、エラー信号に依存して前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを変更するステップと、
を有する、方法。
【請求項２】
前記他のフローが応答フローを有する、請求項１に記載の方法。
【請求項３】
前記セットのうちの１つのみの各フローに対する少なくとも１つの調整パラメータがエラー信号に依存して変更される、請求項１に記載の方法。
【請求項４】
前記セットのうちの１つのみの各フローに対する単一の調整パラメータがエラー信号に依存して変更される、請求項１に記載の方法。
【請求項５】
前記フロー・レートは前記キュー管理方式に従って第１の期間で定期的に調整され、前記調整パラメータは第１の期間よりも長い第２の期間で定期的に変更される、請求項１に記載の方法。
【請求項６】
前記キュー管理方式に従って、各フロー・レートは、超過帯域幅が使用可能な場合は増加パラメータに応じた量だけ増加し、超過帯域幅が使用不能な場合は減少パラメータに応じた量だけ減少し、
前記セットのうちの少なくとも１つの少なくとも１つのフローに対する増加パラメータおよび減少パラメータのうちの少なくとも１つが、エラー信号に依存して変更される、請求項１に記載の方法。
【請求項７】
前記キュー管理方式がＢＡＴ方式を有する、請求項６に記載の方法。
【請求項８】
前記無応答フロー・セットのうちの少なくとも１つのフローに対する前記減少パラメータが、エラー信号に依存して変更される、請求項６に記載の方法。
【請求項９】
前記無応答フロー・セットの各フローに対する前記減少パラメータが、エラー信号に依存して変更される、請求項８に記載の方法。
【請求項１０】
前記フロー・レートは前記キュー管理方式に従って第１の期間で定期的に調整され、前記減少パラメータは前記第１の期間よりも長い第２の期間で定期的に変更される、請求項９に記載の方法。
【請求項１１】
各フローに対する前記パラメータの前記変更に最大制限値を適用することを含む、請求項９に記載の方法。
【請求項１２】
フローのフロー・レート管理ステップに対する入力フロー・レートの関数としてフローの前記最大制限値を計算することを含む、請求項１１に記載の方法。
【請求項１３】
前記キュー管理方式に従って、フロー・レートがフローの最低保証レートを超えた場合に超過帯域幅に依存したフロー・レートの調整が実行され、前記方法は、フローのフロー・レート管理ステップに対する入力フロー・レートが前記フローの前記最低保証レートを下回った場合に、前記フローの前記減少パラメータの変更を抑制することを含む、請求項９に記載の方法。
【請求項１４】
前記減少パラメータの変更の抑制中に、前記減少パラメータを前記抑制の開始時点の値で維持することを含む、請求項１３に記載の方法。
【請求項１５】
前記減少パラメータは前記エラー信号に依存して一定の時間間隔で変更され、前記方法は、前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させることを含む、請求項１３に記載の方法。
【請求項１６】
前記無応答フローのセットについて、前記所望の割り振り比率および前記キューの所定の最大リンク帯域幅に依存して、前記キュー管理ステップに対する合計入力フロー・レートがしきい値を下回った場合に、前記フローの減少パラメータの変更を抑制することを含む、請求項９に記載の方法。
【請求項１７】
前記減少パラメータの変更の抑制中に、前記減少パラメータを前記抑制の開始時点の値で維持することを含む、請求項１６に記載の方法。
【請求項１８】
前記減少パラメータは前記エラー信号に依存して一定の時間間隔で変更され、前記方法は、前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させることを含む、請求項１６に記載の方法。
【請求項１９】
前記所望の割り振り比率に反比例する、所定の初期値からの前記減少パラメータの変更を開始することを含む、請求項９に記載の方法。
【請求項２０】
前記減少パラメータの変更の開始時に、前記合計フロー・レートの比率に依存して前記減少パラメータの初期値を選択することを含む、請求項９に記載の方法。
【請求項２１】
ネットワーク・デバイスのリソースに対応するキューへの複数のデータ・パケット・フローのフロー・レートを制御するための装置であって、前記複数のフローは、無応答フローのセットおよび他のフローのセットを有し、前記装置は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するためのキュー・マネージャであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するキュー・マネージャと、
前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを制御するための調整コントローラであって、所望の割り振り比率と、無応答フロー・セットについての合計サービス・フロー・レートに対する他のフロー・セットについての合計サービス・フロー・レートの比率との間の、差異に依存してエラー信号を生成するように、および、前記偏差を削減するためにエラー信号に依存して少なくとも１つの調整パラメータを変更するように、配置構成された調整コントローラと、
を有する装置。
【請求項２２】
前記調整コントローラが、前記セットのうちの１つのみの各フローに対する少なくとも１つの調整パラメータをエラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２３】
前記セットのうちの１つのみの各フローに対する単一の調整パラメータをエラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２４】
前記キュー・マネージャがキュー管理方式に従って前記フロー・レートを管理するように配置構成され、前記フロー・レートが第１の期間で定期的に調整され、前記調整コントローラが、前記第１の期間よりも長い第２の期間で前記調整パラメータを定期的に変更するように配置構成された、請求項２１に記載の装置。
【請求項２５】
前記キュー・マネージャがキュー管理方式に従って前記フロー・レートを管理するように配置構成され、各フロー・レートが、超過帯域幅が使用可能な場合は増加パラメータに応じた量だけ増加し、超過帯域幅が使用不能な場合は減少パラメータに応じた量だけ減少し、
前記調整コントローラが、前記セットのうちの少なくとも１つの少なくとも１つのフローに対する増加パラメータおよび減少パラメータのうちの少なくとも１つを、エラー信号に依存して変更するように配置構成された、請求項２１に記載の装置。
【請求項２６】
前記キュー管理方式がＢＡＴ方式を有する、請求項２５に記載の装置。
【請求項２７】
前記調整コントローラが、前記無応答フロー・セットのうちの少なくとも１つのフローに対する前記減少パラメータをエラー信号に依存して変更するように配置構成された、請求項２５に記載の装置。
【請求項２８】
前記調整コントローラが、前記無応答フロー・セットの各フローに対する前記減少パラメータをエラー信号に依存して変更するように配置構成された、請求項２７に記載の装置。
【請求項２９】
前記キュー・マネージャが、前記キュー管理方式に従って前記フロー・レートを管理するように配置構成され、前記フロー・レートは第１の期間で定期的に調整され、前記キュー・マネージャが、前記減少パラメータを前記第１の期間よりも長い第２の期間で定期的に変更するように配置構成された、請求項２８に記載の装置。
【請求項３０】
前記調整コントローラが、各フローに対する前記パラメータの前記変更に最大制限値を適用するように配置構成された、請求項２８に記載の装置。
【請求項３１】
前記調整コントローラが、フローの前記キュー・マネージャに対する入力フロー・レートの関数としてフローの前記最大制限値を計算するように配置構成された、請求項３０に記載の装置。
【請求項３２】
前記キュー・マネージャが、前記キュー管理方式に従って前記フロー・レートを管理するように配置構成され、フロー・レートがフローの最低保証レートを超えた場合に超過帯域幅に依存したフロー・レートの調整が実行され、
前記調整コントローラが、フローの前記キュー・マネージャに対する入力フロー・レートが前記フローの前記最低保証レートを下回った場合に、前記フローの前記減少パラメータの変更を抑制するように配置構成された、
請求項２８に記載の装置。
【請求項３３】
前記減少パラメータの変更の抑制中に、前記調整コントローラが前記減少パラメータを前記抑制の開始時点の値で維持するように、前記調整コントローラが配置構成された、請求項３２に記載の装置。
【請求項３４】
前記調整コントローラが、前記減少パラメータを前記エラー信号に依存して一定の時間間隔で変更するように、ならびに前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させるように、配置構成された、請求項３２に記載の装置。
【請求項３５】
前記調整コントローラが、前記無応答フローのセットについて、前記所望の割り振り比率および前記キューの所定の最大リンク帯域幅に依存して、前記キュー・マネージャに対する合計入力フロー・レートがしきい値を下回った場合に、減少パラメータの変更を抑制するように配置構成された、請求項２８に記載の装置。
【請求項３６】
前記調整コントローラが、前記減少パラメータの変更の抑制中に、前記調整コントローラが前記減少パラメータを前記抑制の開始時点の値で維持するように配置構成された、請求項３５に記載の装置。
【請求項３７】
前記調整コントローラが、前記減少パラメータを前記エラー信号に依存して一定の時間間隔で変更するように、ならびに前記減少パラメータの変更の抑制中に、前記時間間隔それぞれの後に前記減少パラメータを所定量だけ減少させるように、配置構成された、請求項３５に記載の装置。
【請求項３８】
前記調整コントローラが、前記所望の割り振り比率に反比例する、所定の初期値からの前記減少パラメータの変更を開始するように配置構成された、請求項２８に記載の装置。
【請求項３９】
前記調整コントローラが、前記減少パラメータの変更の開始時に、前記合計フロー・レートの比率に依存して前記減少パラメータの初期値を選択するように配置構成された、請求項２８に記載の装置。
【請求項４０】
通信ネットワークにおいてデータ・パケットを処理するためのネットワーク・デバイスであって、前記デバイスは、データ・パケットのキューに関連付けられたリソースと、前記キューへの無応答フローのセットおよび他のフローのセットを有する複数のデータ・パケット・フローのフロー・レートを制御するためのフロー制御論理とを有し、前記フロー制御論理は、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するためのキュー・マネージャであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するキュー・マネージャと、
前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを制御するための調整コントローラであって、
所望の割り振り比率と、無応答フロー・セットについての合計サービス・フロー・レートに対する他のフロー・セットについての合計サービス・フロー・レートの比率との間の、差異に依存してエラー信号を生成するように、および、前記偏差を削減するためにエラー信号に依存して少なくとも１つの調整パラメータを変更するように、配置構成された調整コントローラと、
を有する、ネットワーク・デバイス。
【請求項４１】
データ・パケットのキューに関連付けられたリソースを有するネットワーク・デバイスのプロセッサに、前記キューへの無応答フローのセットおよび他のフローのセットを有する複数のデータ・パケット・フローのフロー・レートを制御するためのフロー制御方法を実行させるためのコンピュータ読取り可能プログラム・コード手段を具体化しているコンピュータ使用可能メディアを有するコンピュータ・プログラムであって、前記フロー制御方法が、
リソース内の超過帯域幅に依存して各フロー・レートに対して調整が実行されるようなキュー管理方式に従って前記フロー・レートを管理するステップであって、前記調整の量が各フローの１つまたは複数の調整パラメータに依存するステップと、
所望の割り振り比率と、無応答フロー・セットについての合計サービス・フロー・レートに対する他のフロー・セットについての合計サービス・フロー・レートの比率との間の、差異に依存してエラー信号を生成するステップと、
前記偏差を削減するために、エラー信号に依存して前記セットのうちの少なくとも１つの少なくとも１つのフローについて、少なくとも１つの調整パラメータを変更するステップと、
を有する、コンピュータ・プログラム。
【国際調査報告】
2006511137.tif 000022
2006511137.tif 000023
2006511137.tif 000024