JP4032231B2 - データ伝送方法 - Google Patents

Description

【０００１】
本発明は、コンピュータ・ネットワークを介して、特に送られるべきデータがＩＰパケットに分割されるインターネットを介して、顧客からのデータを伝送する方法に関する。更に、各パケットには少なくとも２つの状態（イン及びアウト）により印が付けられ、その状態は、もし伝送中にネットワーク輻輳に起因してパケットが落とされる（ドロップされる）場合、どのパケットが最初に落とされるかを決定する。
【０００２】
今日、コンピュータ・ネットワークを介して顧客からのデータを伝送する多様な方法がある。インターネットを介して伝送されるべきデータは一般にパケットに分割される。データは、ＩＰプロトコルを介して伝送されるならば、インターネット・プロトコル（ＩＰ）パケットに分割される。ネットワークを介してパケットがスムーズに、即ち輻輳無しで、伝送されることを保証するために、パケットは少なくとも２つの状態のうちの１つによって印が付けられる。これらの状態の目的は、伝送中にパケットが落とされるとすれば、どのパケットが最初に落とされどのパケットが最後に落とされるかを決定することである。パケットの廃棄は、ネットワーク輻輳に起因して生じる。この場合、高い廃棄優先順位が印されているパケット（アウト・パケット）は最初に捨てられ、低い廃棄優先順位が印されているパケット（イン・パケット）は捨てられないという高い確率を有する。
【０００３】
パケットは、ネットワークに入るときに、即ち例えばインターネット・サービス・プロバイダ（ＩＳＰ）の端のノードで、印が付けられる。パケットには、例えばパケットのサイズが特定のバイト数より小さいか否かなど、それぞれのパケットが特定の条件に準拠するか否か調べるアルゴリズムに従って、印が付けられる。この条件に準拠しないパケットには、パケットがネットワーク輻輳の場合に最初に落とされる（アウト・パケット）状態で印が付けられる。
【０００４】
パケットに印を付ける前記のシステムは、パケットが条件を満たさないならば高い廃棄優先順位の状態で印を付けるだけであるので、特に問題である。普通そうであるように、パケットが伝送中に割り当てられている最大帯域幅を上回れば高い廃棄優先順位で印が付けられるという条件をアルゴリズムが含んでいる場合には、特にそうである。このことは、顧客の割り当てられている最大帯域幅を既に上回っているときには高い廃棄優先順位で印が付けられているパケットが落とされるということを意味する。パケットが準拠しないときにだけ高い廃棄優先順位でパケットに印を付けることは、準拠しないパケットを輻輳の場合に捨てることを可能にするが、輻輳を防ぐことはできない。
【０００５】
本発明の目的は、端のルータにおいてパケットに印を付ける方法を最適化するすることによって、ネットワーク輻輳を回避することを目的とする、冒頭で述べた種類のデータ伝送方法を提供することである。
【０００６】
本発明によれば、この目的は、高廃棄優先順位の状態でのパケットの印付けがランダム確率に基づくことを特徴とする請求項１の特徴を示すデータ伝送方法により達成される。
【０００７】
本発明によれば、ランダム確率に基づいてパケットに印を付けることにより、パケットは割り当てられている最大帯域幅を上回っていないときに既に高廃棄優先順位の状態で印を付けられることができる。従って、パケットは、パケットの伝送中に割り当てられている最大帯域幅を上回っていないときに早期に落とされることもあり得る。パケットがＴＣＰプロトコルによって転送されるならば、早期のパケット廃棄はソースに伝送速度（パケットがネットワークに送り込まれる速度）を低下させ、これはネットワーク輻輳を予防することを可能にする。これは、顧客がデータを送る帯域幅または顧客の束ねたトラフィックを制御し最適化する非常に有利で単純な方法を提供する。
【０００８】
特に有効な伝送を保証することに関して、高廃棄優先順位でのパケットの印付けは、各顧客について単一のランダム確率に基づき、それにより計算量を最小限にする。
【０００９】
ネットワークのノードはリンクにより互いに接続される。複数の顧客が特に有線及び／又は無線接続のリンクを共有することができる。この場合、各顧客について、顧客が送るトラフィックを特徴づけるために１つのランダム確率が使用される。本発明による方法は、リンクでの総帯域幅を最大にしようと試みる既存の方法とは異なって、各顧客が使用する帯域幅を最適化しようとする。換言すると、従来の方法では、他の顧客を犠牲にして一人または複数の顧客が、自分が支払った分よりも著しく大きい帯域幅を受け取るということがあり得る。本発明による方法では、各顧客は自分が支払った分の値に近い帯域幅を使用することができる。
【００１０】
リンクは最大帯域幅を有し、及び／又は顧客にはデータ伝送のために最大の帯域幅が割り当てられる。割り当てられた最大帯域幅に基づく課金及び支払いは特に簡単であるので、ＩＳＰ及び顧客に関してはこの様なシナリオが良くある。
【００１１】
パケットがネットワークに入るとき、そのパケットが準拠するか否か判定するために、即ち顧客により使用される帯域幅がその顧客が支払った分の値を上回るか否か判定するために、一つの方法が適用される。一定の契約へのパケットの準拠を査定するために使用される方法はポリサーと呼ばれる。もっとも一般的なポリサーは、トークン・バケットである。パケットがネットワークに入るとき、与えられたトークン・バケット・サイズによって特徴付けられるトークン・バケットは、顧客が購入した帯域幅に対応する率で満たされる。トークン・バケットのサイズ（深さとも呼ばれる）と割り当てられた帯域幅とは、両方とも、一般にＩＳＰと顧客との間の契約の一部分である。
【００１２】
顧客からの与えられたサイズまたは長さのパケットが端のノードで受信されるとき、パケット長さ（バイト単位で測られる）がトークン・バケットのバイト数、即ちトークン・バケット・オキュパンシー、を上回っていれば高廃棄優先順位でそれに印が付けられる。もしこのパケットのためにバケット内に充分なバイトがあれば、それには低廃棄優先順位で印が付けられる。もしパケットに低廃棄優先順位で印が付けられれば、パケット長さに等しい数のバイトがトークン・バケットから差し引かれる。もし高廃棄優先順位でパケットに印が付けられれば、トークン・バケットからバイトは差し引かれない。トークン・バケットが空ならば、全てのパケットが高廃棄状態で印を付けられる。
【００１３】
コア・ノードにおいて、全てのパケットがその印（イン／アウト）に関わらず同じバッファーに入れられる。このバッファーは、輻輳が生じた場合にアウト・パケットが最初に落とされるように管理される。この様にして、イン・パケットだけでは輻輳を生じさせないようにネットワークが構成されている限りはイン・パケットが決して落とされないことが保証される。
【００１４】
提案されている本発明は、標準的トークン・バケットを次のように拡張する。パケットは、端のルータに到着すると、トークン・バケットに入る。もしパケットのサイズがトークン・バケット内のバイト数を上回っていなくても、パケットは（標準的トークン・バケットの場合とは異なって）一定の確率で準拠していないと印される（高廃棄優先順位）。ネットワークの輻輳の場合には、このパケットはおそらく落とされるであろう（以下、この廃棄を早期廃棄と称する）。本発明は、もしパケットが伝送制御プロトコル（ＴＣＰ）（特に伝送制御プロトコル／インターネット・プロトコル、即ちＴＣＰ／ＩＰ）により伝送されるならば、早期廃棄は重大なレベルの輻輳が発生する前にソースが伝送を抑えることを可能にするという事実に基づいている。換言すると、早期廃棄は多数のパケットが落とされる事態を防止することになる。
【００１５】
非常に簡単な実施態様では、パケットはディフサーブ（ＤｉｆｆＳｅｒｖ）環境において転送されることができる。ディフサーブ（ディフサーブアーキテクチャとも称される。）はインターネットでサービス品質（ＱｏＳ）を提供する（小規模から大規模まで）拡張可能な方法である。拡張可能性は、端の方向へ複雑な機能性を移動させると共に非常に簡単な機能性をコアに残しておくことによって達成される。ＤｉｆｆＳｅｒｖでは、パケットにネットワークの入り口でＤｉｆｆＳｅｒｖコードポイント（ＤＳＣＰ）で印が付けられ、コアにおいてはそれらのＤＳＣＰに応じてそれらに転送処理が与えられる。各ＤＳＣＰはパーホップ挙動（Per-Hop Behavior （ＰＨＢ））に対応する。
【００１６】
２グループのＰＨＢ、すなわち優先転送（ＥＦ）ＰＨＢ及び保証付き転送（ＡＦ）ＰＨＢがこれまでに定義されている。
【００１７】
ディフサーブサービスを提供するサービス・プロバイダ、特にＩＳＰは、一般に保証付き転送（ＡＦ）を用いてサービスを提供する。ＡＦでは、顧客のパケットは、該顧客からの総トラフィックが、契約された帯域幅、即ち割り当てられた最大帯域幅を上回らない限り非常に高い確率で転送される。ネットワーク輻輳の場合に、もし総トラフィックが割り当てられている最大帯域幅を上回ると、顧客の準拠しないパケットは高い確率で捨てられる。
【００１８】
一般に、サービス・プロバイダによるデータ伝送についての課金は契約され割り当てられた最大帯域幅に基づくので、顧客は割り当てられた最大帯域幅に少なくとも等しい伝送速度を受けると期待する。実際には、ＴＣＰと共にＡＦを使用すると、平均総トラフィックが割り当てられた最大帯域幅より著しく低いという結果をもたらす。それは、パケットが落とされるときにＴＣＰがそのトラフィックを減少させるからである。従って、ＴＣＰとＡＦとを組み合わせると、もし割り当てられた最大帯域幅を上回れば常に前述の挙動が行われる結果となる。場合によっては、この組み合わせは、全ての顧客のＴＣＰソースの、全てがその送信速度を同時に低下させるという同時（同期）挙動という結果をももたらす。その結果として、顧客の送信速度が変動して、トラフィックが契約された帯域幅より著しく低くなるという結果をもたらす。
【００１９】
ＤｉｆｆＳｅｒｖでは、前述したＡＦと組み合わされたＴＣＰ伝送の挙動は非常に頻繁に観察される。送信速度がＣＩＲ（Committed Information Rate（委託情報速度）、他には割り当てられた最大速度とも称される）を上回ると、トークン・バケットは空になり幾つかのパケットはアウトと印される。従って、この印付けは、割り当てられた最大帯域幅を上回るとパケット廃棄という結果をもたらす。
【００２０】
この印付けアルゴリズムは、３レベルの廃棄優先順位に拡張されることができる。その様な解決策は、特に高度にパケットを区別することを可能にする。廃棄優先順位のレベルは如何なる数にも拡張されることができる。
【００２１】
コア・ノードでは、全てのパケットが、その印に関わらず、同じバッファーに入れられる。このバッファーは、輻輳が生じた場合に高廃棄優先順位の印を付されたパケットが最初に落とされるように管理される。高廃棄優先順位パケットが最初に落とされるようにバッファーを管理するために通常使用される１つのメカニズムはＷＲＥＤ（Weighted Random Early Detection（重み付きランダム早期検出））である。ＷＲＥＤは、低廃棄優先順位で印を付けられたパケットだけではパケット輻輳を生じさせないようにネットワークが構成されている限りは、これらのパケットが決して落とされないということを保証する。
【００２２】
ＴＣＰは、これらの廃棄に反応して、トラフィックを、割り当てられた最大帯域幅より低い値まで減少させる。ＴＣＰは、それ以上のパケット廃棄を検出しなければ、次のパケット廃棄が発生するまでトラフィックを再び増大させる。その結果として、ＴＣＰの送信速度は割り当てられた最大帯域幅と時には相当低い値との間で変動し、その結果として平均トラフィックは割り当てられた最大帯域幅より低くなる。この挙動は、付加的ランダム確率に基づいてパケットに印を付けることによって相当減少させられる。
【００２３】
総トラフィックを最適化するために、与えられたとき（ステップ）におけるランダム確率は、以下の数１３に示される数式で表すことができる。
【００２４】
【数１３】

ここでｐ_ｏｌｄ及びｂ_ｏｌｄは前のステップ（前の更新時）にそれぞれｐ及びｂが持った値である。次のステップを評価するために、ｐ_ｏｌｄはｐに等しくセットされなければならず、ｂ_ｏｌｄはｂに等しくセットされなければならない。ｂ_ｒｅｆは、望まれるトークン・バケット・オキュパンシー、即ちトラフィックを安定させるためにその値に調整したい制御ループの値である。
【００２５】
パケットがトークン・バケットに入るたび毎に、この確率は０と１との間に一様に分布された乱数と比較される。もし該確率がその乱数より大きければ、そのパケットは高廃棄優先順位で印を付けられる。
【００２６】
トークン・バケット・オキュパンシーを安定させるとき、ＴＣＰウィンドウのサイズの変化は、以下の数１４に示された数式で表すことができる。
【００２７】
【数１４】

トークン・バケット・オキュパンシーの値の変化は、以下の数１５に示された数式で表すことができる。
【００２８】
【数１５】

ここでＷ（ｔ）はＴＣＰウィンドウのサイズであり、Ｒ（Ｔ）は往復遅延時間（ＲＴＴ）であり、Ｎ（ｔ）は顧客のＴＣＰソースの数であり、Ｃは割り当てられた最大帯域幅（他の場所ではＣＩＲとも称される）である。
【００２９】
トークン・バケット・オキュパンシーを安定させるために、一定の往復遅延時間Ｒ_０及び／又は一定のＴＣＰソース数Ｎを仮定して、操作点におけるＴＣＰウィンドウ・サイズ及び／又はトークン・バケット・オキュパンシーの値の変化を以下の数１６、数１７に示される数式で線形化することができる。
【００３０】
【数１６】

【数１７】

操作点（ｗ_０、ｂ_０、ｐ_０）は、以下の数１８に示される数式を満たすような条件を課すことによって決定される。ＴＣＰソースの数についてはＮ（ｔ）＝Ｎ、往復遅延時間についてはＲ（ｔ）＝Ｒ_{０ 、}即ちそれらは定数であると仮定する。
【００３１】
【数１８】

以下の数１９に示される条件を仮定すると、制御ループの伝達関数は、以下の数２０に示される数式で表すことができる。この伝達関数は、上記の微分方程式に対してラプラス変換を実行することによって得られる。
【００３２】
【数１９】

【数２０】

非常に有利な実施態様では、トークン・バケット・オキュパンシーはコントローラにより、特に以下の数２１に示される数式を満たすようなＰＩコントローラにより安定化されることができる。ラプラス変換を実行することにより得られたＣ（ｓ）の値を伴うＰＩコントローラは、最大入力過渡と高いセットリングタイムとを有するが、オフセットは有さない。従って、ＰＩコントローラはトークン・バケット・オキュパンシーを安定させるのに良く適している。
【００３３】
【数２１】

開ループの伝達関数は以下の数２２に示される数式のように表される。
【００３４】
【数２２】

ＴＣＰソースの数についてＮ≧Ｎ⁻、往復遅延時間（ＲＴＴ）について Ｒ_０≦Ｒ^＋という範囲を仮定すると、目的は線形制御ループを安定させる定数Ｋ及びｚの値を選択することである。
【００３５】
この目的のために、ＴＣＰ時定数より大きい制御システム定数を選択することができ、該コントローラについてのゼロ点は、以下の数２３に示される数式を満たすように選択され得る。
【００３６】
【数２３】

上記選択の理論的根拠はコントローラに閉ループ挙動を支配させることであり、ここで制御定数は１／ω_ｇにニアリーイコールであり、ＴＣＰ時定数は以下の数２４に示される値として定義される。
【００３７】
【数２４】

ナイキスト安定判別法を実施すると、システムは以下の数２５に示されるＫ値に対するω_ｇで安定する。
【００３８】
【数２５】

ナイキスト安定判別による基準は、ω_ｇについてシステムが安定である時を定義する。方程式｜Ｌ（ｊω_ｇ）｜＝０．１を課すことにより、Ｋについての値を得る。
【００３９】
位相差についての方程式を計算することにより、以下の数２６に示される数式が得られる。
【００４０】
【数２６】

従って、ループはこれらの値について安定である。
【００４１】
ラプラス領域からｚ領域への変換、好ましくは双一次変換、を実行することにより、以下の数２７に示される数式を満たすｋ１値及びｋ２値が得られる。
【００４２】
【数２７】

ここでＫはコントローラにおける利得であり、ω_ｇはシステムの周波数領域である。Ｔは、例えば到着間時間として定義されるサンプリング時間であり、これは逆最大帯域幅１／ＣＩＲに等しい、即ち顧客は自身が契約した最大帯域幅で送信する。
【００４３】
本発明を応用し更に発展させるいろいろな有利な方法がある。この目的のために、本発明の請求項と、図面を参照しての本発明に係る方法の好ましい実施態様についての記述を参照のこと。図面を参照しての好ましい実施態様についての記述は、該教示の一般的に好ましい実施態様も含む。
【００４４】
図１は、パケットがＡＦ及びＷＲＥＤでＰＨＢを介して送られるＤｉｆｆＳｅｒｖ環境で二人の顧客Ｃ１及びＣ２がＩＳＰを介して顧客Ｄ１及びＤ２にデータを送るシナリオ例を示している。Ｃ１及びＣ２は、それらのＩＳＰと１０Ｍｂｐｓの割り当てられた最大帯域幅（ＣＩＲ）を協定している。更に、顧客Ｃ１及びＣ２は、２０ｍｓ（Ｃ１）及び１００ｍｓｅｃ（Ｃ２）のＲＴＴで、２０Ｍｂｐｓの最大帯域幅のリンクを共有して、共に２０ＴＣＰフローを各々送信する。
【００４５】
シミュレーション結果によると、この模範的実施態様では、顧客Ｃ１及びＣ２のトラフィックはランダム確率に基づく付加的な印付け方式無しで既知のトークン・バケット・アルゴリズムを使用するとき、各々９．８３Ｍｂｐｓ及び８．３２Ｍｂｐｓである。顧客Ｃ２のトラフィックは１０Ｍｂｐｓの割り当てられた最大帯域幅ＣＩＲより相当低いことに注意されたい。
【００４６】
図２は、既知のトークン・バケット・アルゴリズムの概略図を示している。このアルゴリズムにより、実際の帯域幅が割り当てられた最大帯域幅、ＣＩＲと比較される。パケットがＩＳＰのネットワークに入るとき、サイズＢのトークン・バケットが割り当てられた最大帯域幅ＣＩＲにより明示される速度で満たされる。トークン・バケット・サイズＢ及び割り当てられた最大帯域幅ＣＩＲは共にＩＳＰと顧客Ｃ１及びＣ２との間にそれぞれ契約されたものの一部分である。
【００４７】
長さＬのパケットがトークン・バケットに入るとき、それは、もしトークン・バケット・オキュパンシーｂが必要なバイトより少ないバイトを有するならば、アウトと印される（即ち、高廃棄優先順位で印を付けられる）。もしこのパケットのために充分なバイトがあれば、それにはインという印が付けられる、即ち低廃棄優先順位で印が付けられる。イン印付けの場合、パケット長さＬに等しい数のバイトがトークン・バケット・オキュパンシーｂから差し引かれる。トークン・バケット・オキュパンシーｂが充分なバイトを持っていないためにアウトという印がパケットに付けられたならば、トークン・バケット・オキュパンシーｂから何も差し引かれない。
【００４８】
図３はパケットが図２に示されているトークン・バケット・オキュパンシー・アルゴリズムのみに基づいて印が付けられる場合、顧客Ｃ２についてのトークン・バケット・オキュパンシーｂを描いている。該プロットは束ねられたＴＣＰトラフィックの振動する挙動を示している。トークン・バケットが空になるとき、それはＴＣＰトラフィックがその速度を割り当てられた最大帯域幅ＣＩＲより高めているからである。輻輳の場合、高廃棄優先順位で印を付けられているパケット（アウト・パケット）は落とされる。図３は、ＴＣＰがその廃棄に反応してその速度を相当低下させることを明らかに示している。この時点で、トークン・バケットは再びフィルアップを開始する、即ちトークン・バケット・オキュパンシーｂが増大する。ＴＣＰがその速度を再びＣＩＲより高くなるとトークン・バケット・オキュパンシーｂが再び減少する。バケットが満杯である間、顧客Ｃ２は割り当てられた最大帯域幅ＣＩＲより低い速度で送信する。
【００４９】
図４において、流れ図は発明された方法によるパケットの印付けを示している。パケットがネットワークに入るとき、図２のトークン・バケット・アルゴリズムは始めに該パケットが割り当てられた最大帯域幅ＣＩＲ以内かどうか調べる。この目的のために、パケットの長さＬはトークン・バケット・オキュパンシーｂと比較される（ステップＳ１０１）。もしパケットの長さＬの値がトークン・バケット・オキュパンシーｂの値より大きければ（ステップＳ１０１でｎｏ）、該パケットにはアウトという印が付けられる。もしトークン・バケット・オキュパンシーｂが充分なバイトを持っていれば（ステップＳ１０１でｙｅｓ）、該パケットがインと印されるかアウトと印されるかをランダム確率ｐが決定する。もし確率ｐが０と１との間に一様に分布する乱数ｕより大きければ（ステップＳ１０２でｙｅｓ）、該パケットにはアウトという印が付けられ；さもなければ（ステップＳ１０２でｎｏ）、それにインという印が付けられる。もしトークン・バケットが空ならば、ランダム確率ｐに関わらず全てのパケットにアウトという印が付けられる。
【００５０】
トークン・バケット・オキュパンシーｂを安定させるという問題は、ランダム確率ｐに基づく付加的な印付け方式により達成されることができる。トークン・バケット・オキュパンシーｂを安定させるという問題は、以下の数２８に示すように、トークン・バケット・オキュパンシーの時間微分
【外３】

を０に等しくすることとして表現される。
【００５１】
【数２８】

ここでトークン・バケット・オキュパンシーｂは０より大きくてトークン・バケット・サイズＢより小さく、ｂはトークン・バケット・オキュパンシーであり、Ｂはバケット・サイズであり、ｒ（ｔ）は顧客の送信速度であり、ＣＩＲは顧客の契約された最大帯域幅である。
【００５２】
バッファー・オキュパンシーを安定させる問題（キューイング・システムにおける）はアクティブ・キュー・マネージメント（ＡＱＭ）の環境下において広く研究されている。上記のトークン・バケット・オキュパンシーｂを安定させる問題は、速度ｒ（ｔ）で満たされるサイズＢ及びキャパシティーＣ（ＣＩＲに等しい）のキューのオキュパンシーｑを安定させるという問題に変換することができる。一定の伝送遅延と、全てのアウト・パケットが落とされるということとを仮定すると、この２つの問題は実際上同等であり、それは変数の変更（ｑ＝Ｂ−ｂ）で容易に分かる。
【００５３】
これらの方式は細部では異なるけれども、アーキテクチャのレベルでは同様である。それらは、バッファー・オキュパンシーの増減を監視して、このデータを、入ってくるパケットについて廃棄確率を得るためのアルゴリズムで処理する。いろいろなＡＱＭ方式は、基本的には、廃棄確率を得るために使用されるアルゴリズムにおいて異なる。
【００５４】
入ってくる全てのパケットについて確率ｐは以下の数２９に示される数式にて計算される。
【００５５】
【数２９】

ここでｐ_ｏｌｄ及びｂ_ｏｌｄはそれぞれｐ及びｂが前のステップ（前の更新時）に持った値である。次のステップを評価するために、ｐ_ｏｌｄはｐに、ｂ_ｏｌｄはｂに等しくセットされなければならない。ｂ_ｒｅｆは、それに調整したい所望のトークン・バケット・オキュパンシーである。アウトという印を付けるとき、トークン・バケットから何も差し引かれないということに注意されたい。
【００５６】
トークン・バケット・オキュパンシーｂの安定性はパラメータｋ１及びｋ２による。従って、ｋ１及びｋ２の選択は、性能目的を達成するための鍵である。図５はトークン・バケット・オキュパンシーｂを安定させる線形化された制御ループのブロック図を示しており、これに基づいてｋ１及びｋ２は既に説明されたアルゴリズムに従って計算される。
【００５７】
図６は、発明された方法に従って、即ちランダム確率ｐを使用することによって、データが伝送される場合における顧客Ｃ２のトークン・バケット・オキュパンシーｂを描いている。トークン・バケット・オキュパンシーは約ｂ_ｒｅｆ＝０．７５Ｂの値で安定する。この場合に顧客Ｃ２により得られる総トラフィックは９．６５Ｍｂｐｓであり、これは、第１のシミュレーションで得られる８．３２Ｍｂｐｓより遙かに割り当てられた最大帯域幅に近い。図６では、図３と比べて、トークン・バケットが満杯になっている時間間隔は相当短いことに注意されたい。
【００５８】
割り当てられた最大帯域幅ＣＩＲになるべく近いスループットを提供する目的は、トークン・バケット・オキュパンシーｂを基準値ｂ_ｒｅｆのあたりに安定させることであると再公式化されることができる。この特定の代表的実施態様ではｂ_ｒｅｆは下記の数３０に示されるとおりである。
【００５９】
【数３０】

一定の最大限でないトークン・バケット・オキュパンシーｂは、割り当てられた最大帯域幅ＣＩＲにほぼ等しいイン・パケットの送信速度を暗に意味する。イン・パケットが落とされることは殆どなさそうなので、これは割り当てられた最大帯域幅ＣＩＲにほぼ等しいスループットに通じる。
【００６０】
従って本発明の方法は、ランダム確率ｐに基づくアウト印付けを介して来るべき輻輳をＴＣＰソースに早期に知らせることに依拠する。この様にして、本発明の方法はＣ１及びＣ２それぞれのＴＣＰソース間の同期化を回避し、その結果として、契約されたスループットの利用を良好にすると共に、顧客Ｃ１及びＣ２が異なるＣＩＲを契約している場合に総帯域幅を良好に分布させる。その結果として、顧客Ｃ１とＣ２とが高度に公平となる。
【００６１】
本発明の方法の主な利点の一つは、単純であることである。各アクティブ接続の状態を保つ代わりに、本発明の方法は単に各トークン・バケットについて少数の付加的な固定されたパラメータ及び可変パラメータを必要とするだけである。もう一つの特別の利点は、その構成が顧客のトラフィックに関する具体的な知識を必要とはせず、ＴＣＰセッションの数についての下限と往復遅延時間（ＲＴＴ）についての上限とを必要とするだけであることである。
【００６２】
以下では、本発明の教示を更に説明するために幾つかのシミュレーション・シナリオとその結果とを説明する。トークン・バケットとＷＲＥＤキューとを使用するＤｉｆｆＳｅｒｖ環境を仮定し続ける。この様なシナリオは多くのシミュレートされたシナリオにおいて同意されたＣＩＲを提供するのに非常に効率が良いことが判明している。
【００６３】
しかし、実際上興味ある幾つかの場合に、その様な従来アーキテクチャはＴＣＰフロー制御メカニズムの故に公平の問題を解決することはできない。ランダム確率を用いることにより、結果を著しく改善することができる。本シミュレーション・シナリオでは、ＷＲＥＤメカニズムにおけるトラフィックを適合させるための廃棄スレショルド（しきい値）はイン・パケット廃棄を回避する値にセットされる。その上、アウトと印されているパケットについての最大スレショルドＯＵＴ_ｍａｘは１０に等しい。最後に、本発明に係る方法のシミュレーションのために、システムが早期印付けにより速く反応するように、ＡＱＭメカニズムについてのその時点でのキュー長さが考慮される。シミュレーションはｎｓ−２を使って行われた。
【００６４】
以下において、始めに幾つかの不均一なシナリオを考察することにより得た幾つかのシミュレーション結果を示す。始めの３つのシナリオでは、完全に加入されたリンク、即ちＣＩＲの合計がボトルネック容量に等しいことを仮定した。対照的に、第４のシナリオではリンクが部分的にのみ加入されたときの挙動を探求した。提案された印付け方式の性能をいろいろなパラメータの関数として査定して本項を終える。全てのシミュレーションはＴＣＰリーノー（TCP Reno)を用いて行われた。
【００６５】
第１のシナリオは図７に描かれ、以下の表１によって記述されている。アクセス・リンクは遅延もパケット廃棄ももたらさない。無応答ユーザー・データグラム・プロトコル（ＵＤＰ）トラフィックは、ＴＣＰフローと相互に作用し合うときに公平の問題を引き起こすということが知られている。従って、このシナリオで、ＴＣＰのみのフローまたはＴＣＰ及びＵＤＰの混合トラフィックを送信する顧客同士の相互作用を調べる。ＵＤＰトラフィックをモデル化するために、各々１．５Ｍｂｐｓで送信する定ビットレート（ＣＢＲ）フローを考察した。この場合ＵＤＰ速度は同意されたＣＩＲの７５％になる。
【００６６】
【表１】

表１は、この試験のために選択した幾つかのセッティングを伝えると共に、終わりの２つのコラムにおいて標準方法及び本発明の方法についてのトラフィックに関する結果をそれぞれ示している。表１は、ランダム確率ｐの使用は顧客がＴＣＰフローを送信して総帯域幅のうちのより大きな部分を取るのを助けることを示している。特に、小さなＲＴＴを特徴とするＣ１は同意されたＣＩＲを達成するのに対してＣ２は、標準方法により許される８０％とは対照的に、その９０％以上を得る。
【００６７】
第２のシナリオでは、割り当てられた最大帯域幅ＣＩＲについて不均一な値を仮定する。いろいろな顧客が割り当てられた最大帯域幅ＣＩＲについて雑多な値を契約するときにも公平問題が発生する。実際、低いＣＩＲ値を特徴とする顧客は、同意されたＣＩＲを達成する上で有利である。次のシナリオはこの挙動の例である。ボトルネック・リンク速度は２２Ｍｂｐｓに等しくセットされる。以下の表２は、考察される場合において、本発明の方法が総リンク利用を１５％以上改善することを可能にすると共に特に顕著に公平な帯域幅分配をもたらすことを示している。
【００６８】
【表２】

第３のシミュレーション・シナリオでは、顧客の数の影響を調べる。顧客及びフローの数が大きな値に増えると、標準的トークン・バケットが使用されるときでも多重化利得はリンク利用及び帯域幅分配を良好にする明確な効果を有する。ボトルネック・リンク速度は１００Ｍｂｐｓに等しくセットされる。以下の表３において、これを確証するシミュレーション結果を示す。しかし、この場合にも、本発明の方法は全体としての性能を僅かに改善する。
【００６９】
【表３】

第４のシミュレーションでは、帯域に余裕のあるリンク（under-subscribed link)におけるＴＣＰフローだけまたはＵＤＰフローだけを有する顧客同士の相互作用を調べる。５３Ｍｂｐｓのリンク速度を考察したが、以下の数３１に示される値（７５％加入リンク）であった。Ｃ３及びＣ４は共に各々１．５Ｍｂｐｓの速度で１０個のＣＢＲフローを送信する、即ちその送信速度はＣＩＲより僅かに大きい。
【００７０】
【数３１】

以下の表４は、ＴＣＰが超過の帯域幅のうちの標準的アプローチと比べて顕著に高い部分を得ることを本発明の方法が可能にするということを示している。これは、小さなＲＴＴを有するＣ１などの意欲的なＴＣＰ顧客について特に当てはまり、一方、割合に少数のデータフローと大きなＲＴＴと（それぞれ１０及び１００ｍｓ）を有するＣ２は割り当てられた最大帯域幅ＣＩＲを達成できるに過ぎない。
【００７１】
【表４】

次に、本発明により与えられる利益を顧客の数の関数として調べる。この目的のために、第３のシナリオについて実施されたセッティングを考察した。Ｃ１及びＣ２によりそれぞれ達成されるスループットを顧客の総数の関数として査定した。顧客Ｃ１は低いＲＴＴと多数のデータフローとを特徴とし、従って顧客は割り当てられた最大帯域幅ＣＩＲを大いに達成しそうである。逆にＣ２は大きなＲＴＴと割合に少数のフローとを有し、従って顧客は帯域幅分配に関しては不利な立場に置かれる。このシミュレーションでは、常にｎ人の顧客を有するシナリオについて表３における始めのｎ人の顧客を考察した。
【００７２】
図８において、本発明の方法と標準的トークン・バケットとを使用するときにＣ１及びＣ２により得られるスループットを比較する。本発明の方法は常に最善の性能を達成することを可能にする。しかし、最も顕著な改善は顧客の総数が８未満であるときに顧客Ｃ２により達成される。本発明の方法を使用することにより、顧客Ｃ２は常に割り当てられた最大帯域幅ＣＩＲの少なくとも９０％を得、一方標準的トークン・バケットは顧客の総数が少ないときにはそれをかなり不利にする。後者の場合はＩＳＰアクセス・リンクでは概して一般的である。
【００７３】
更に、第３のシミュレーションについて総リンク利用率も評価した。結果は図９で報告されている。本発明の方法による改善は顕著である。
【００７４】
今、数ユニット（例えば家庭ユーザーなど）の程度の、顧客あたりに少数のフローの効果を考察する。特に、比較的に少数のフローを送信する一人の顧客を除いて各々１０個のフローを送信する１０人の顧客を有するシナリオの性能を分析する。全ての顧客に１０ＭｂｐｓのＣＩＲが割り当てられ、ＲＴＴはいろいろな顧客につき２０及び１００ｍｓの間でまちまちであり、ボトルネック速度リンクは１００Ｍｂｐｓに等しい。
【００７５】
少数のフローを送信する顧客について、本発明の方法を使用するとき標準的トークン・バケットと比べて、達成されるスループットをフローの数の関数として評価する。結果は図１０で報告されている。期待通りに、フローの数が少ないときには、得られるスループットは割り当てられた最大帯域幅ＣＩＲより相当少ない。しかし、本発明の方法を使用することにより、関連のある改善を認める。このシミュレーションでは、５個のフローを送信することにより、顧客は既に割り当てられた最大帯域幅ＣＩＲを得るが、早期印付けが行われないときには達成されるスループットは依然として割り当てられた最大帯域幅ＣＩＲより１０％低い。
【００７６】
本発明の付加的な有利な実施態様に関して、反復を避けるために、本解説の一般項とこの請求項とを参照されたい。
【００７７】
最後に、上記の模範的な実施態様は請求されている教示を説明するために役立つに過ぎず、模範的実施態様には限定されない。
【００７８】
尚、以下に、本詳細な説明中に使用された符号とその意味について列挙する。
ｂ：トークン・バケット・オキュパンシー
ｂ_ｏｌｄ：旧トークン・バケット・オキュパンシー
ｂ_ｒｅｆ：トークン・バケット・オキュパンシーをそれに調整したいところの値
Ｂ：トークン・バケットのサイズ
ＣＩＲ：割り当てられた最大帯域幅
Ｃ１、Ｃ２・・・Ｃ１０：顧客（送信者）
Ｄ１、Ｄ２：顧客（受信者）
イン：低廃棄優先順位の状態
Ｋ：コントローラにおける利得
Ｌ：パケット長さ
Ｎ：ＴＣＰソースの数
アウト：高廃棄優先順位の状態
ｐ：確率
ｐ_ｏｌｄ：旧確率
Ｒ、ＲＴＴ：往復遅延時間
ｕ：均一に分布する乱数
Ｗ：ＴＣＰウィンドウのサイズ
ｚ：コントローラのゼロ点
ω_ｇ：最大周波数
ＡＦ：保証付き転送
ＡＱＭ：アクティブ・キュー・マネージメント
ＣＢＲ：定ビットレート
ＤｉｆｆＳｅｒｖ：ディフサーブ
ＤＳＣＰ：ディフサーブサービス・コードポイント
ＩＰ：インターネット・プロトコル
ＩＳＰ：インターネット・サービス・プロバイダ
ＰＨＢ：パーホップ挙動
ＱｏＳ：サービス品質
ＴＣＰ：伝送制御プロトコル
ＷＲＥＤ：重み付きランダム早期検出
【図面の簡単な説明】
【図１】既知の方法と発明された方法とによるデータの送信の模範的実施態様を示した図である。
【図２】既知のトークン・バケット・アルゴリズムの大要を示した図である。
【図３】ランダム確率無しでの既知の方法による送信におけるトークン・バケット・オキュパンシーを時間の関数として示したグラフである。
【図４】発明された方法によるパケットの印付けを示す略流れ図である。
【図５】トークン・バケット・オキュパンシーを安定させる線形化された制御ループの略ブロック図である。
【図６】発明された方法によるデータの送信におけるトークン・バケット・オキュパンシーを時間の関数として示したグラフである。
【図７】既知の方法と発明された方法とのデータ送信の付加的な模範的実施態様を示した図である。
【図８】発明された方法と比べて既知の方法を使用するときの顧客数の関数として達成されるスループットを示したグラフである。
【図９】発明された方法と比べて既知の方法を使用するときの顧客数の関数として達成される総リンク利用を示したグラフである。
【図１０】発明された方法と比べて既知の方法を使用するときのＴＣＰデータフローの数の関数として達成されるスループットを示したグラフである。

Claims (25)

1. コンピュータ・ネットワークを介して、特にインターネットを介して、顧客（Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７、Ｃ８、Ｃ９、Ｃ１０）からデータを伝送する方法であって、この方法では送信されるべきデータはパケットに、特にＩＰパケットに分割され、前記各パケットには少なくとも２つの状態（イン、アウト）のうちの一つで印が付けられ、その状態は、もし伝送中にパケットが落とされるとすればどのパケットが最初に落とされるかを決定し、高廃棄優先順位（アウト）の状態でのパケットの印付けがランダム確率（ｐ）に基づき、
   該ネットワークのコンピュータは互いに結合（リンク）され、
   データ伝送の目的でリンクは最大帯域幅を有し、顧客には割り当てられた最大帯域幅（ＣＩＲ）が提供され、
   パケットの印付けは現在の帯域幅と割り当てられた最大帯域幅（ＣＩＲ）との比較に基づくことを特徴とするデータ伝送方法。
2. 前記高廃棄優先順位（アウト）でのパケットの印付けは単一のランダム確率（ｐ）に基づくことを特徴とする請求項１に記載のデータ伝送方法。
3. 前記ランダム確率（ｐ）は各顧客（Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７、Ｃ８、Ｃ９、Ｃ１０）のトラフィックについて測定されることを特徴とする請求項１又は２に記載のデータ伝送方法。
4. 数人の顧客（Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７、Ｃ８、Ｃ９、Ｃ１０）がリンクの少なくとも一部分を、特に有線及び無線接続の少なくとも一つを共有することを特徴とする請求項１に記載のデータ伝送方法。
5. 前記顧客（Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７、Ｃ８、Ｃ９、Ｃ１０）のトラフィックが測定されることを特徴とする請求項１に記載のデータ伝送方法。
6. 伝送中に、前記顧客（Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７、Ｃ８、Ｃ９、Ｃ１０）に割り当てられた最大帯域幅（ＣＩＲ）を越えたとき、もしくは接続の最大帯域幅がパケットを伝送するに充分でないときのいずれか少なくとも一方のとき、前記パケットが落とされることを特徴とする請求項１又は５に記載のデータ伝送方法。
7. 現在の帯域幅と割り当てられた最大帯域幅（ＣＩＲ）との比較はトークン・バケットに基づくことを特徴とする請求項１に記載のデータ伝送方法。
8. 現在の帯域幅が割り当てられた最大帯域幅（ＣＩＲ）より高い場合に、前記パケットに前記高廃棄優先順位で印が付けられることを特徴とする請求項１，５，６，７のいずれか一つに記載のデータ伝送方法。
9. データの送信はＴＣＰ輸送プロトコルを介して、特にＴＣＰ／ＩＰを介して、行われることを特徴とする請求項１，５，６，７，８のいずれか一つに記載のデータ伝送方法。
10. 前記パケットはＤｉｆｆＳｅｒｖ環境で、好ましくはＰＨＢを介して、特にＷＲＥＤによる保証付き転送（ＡＦ）で、転送されることを特徴とする請求項１，５〜９のいずれか一つに記載のデータ伝送方法。
11. 前記印付けは２つの状態により行われることを特徴とする請求項１，５〜１０のいずれか一つに記載のデータ伝送方法。
12. 与えられたステップでの確率（ｐ）は、以下の数１に示される数式のように表現され、
    

    

    次のステップにおいてｐ_ｏｌｄはｐに等しくセットされｂ_ｏｌｄはｂに等しくセットされることを特徴とする請求項１〜３のいずれか一つに記載のデータ伝送方法。
13. 確率（ｐ）は、０と１との間に一様に分布された乱数（ｕ）と比較されることを特徴とする請求項１〜１２のいずれか一つに記載のデータ伝送方法。
14. 確率（ｐ）が乱数（ｕ）より大きい場合に、前記パケットは前記高廃棄優先順位（アウト）で印を付けられることを特徴とする請求項１３に記載のデータ伝送方法。
15. 前記パケットは、好ましくはコア・ノードに割り当てられたバッファーに入れられることを特徴とする請求項１〜１４のいずれか一つに記載のデータ伝送方法。
16. 伝送中におけるパケット輻輳の場合に、前記高廃棄優先順位（アウト）で印が付けられているパケットは捨てられることを特徴とする請求項１〜１５のいずれか一つに記載のデータ伝送方法。
17. ＴＣＰウィンドウのサイズ（
    【外１】
    

    

    ）の変化は、以下の数２に示される数式のように表現されることを特徴とする請求項１〜１６のいずれか一つに記載のデータ伝送方法。
    

    
18. トークン・バケット・オキュパンシー（
    【外２】
    

    

    ）の変化は、以下の数３に示される数式のように表現されることを特徴とする請求項１〜１７のいずれか一つに記載のデータ伝送方法。
    

    
19. ＴＣＰウィンドウ・サイズ（Ｗ）及びトークン・バケット・オキュパンシー（ｂ）の少なくとも一つの変化は、以下の数４及び数５に示される数式で決定される操作点で、好ましくは一定の往復遅延時間（ＲＴＴ）及びＴＣＰソースの一定数（Ｎ）の少なくとも一つで線形化されることを特徴とする請求項１７又は１８に記載のデータ伝送方法。
    

    

    
20. 以下の数６に示されるように１／Ｒ_０がＮ／Ｒ_０ ^２Ｃよりも著しく大きいと仮定して、
    

    

    伝達関数は以下の数７に示される数式のように表すことができることを特徴とする請求項１〜１９のいずれか一つに記載のデータ伝送方法。
    

    
21. トークン・バケット・オキュパンシー（ｂ）は、コントローラ、特に、以下の数８に示された数式を満たすＰＩコントローラによって、
    

    

    安定させられることを特徴とする請求項１〜２０のいずれか一つに記載のデータ伝送方法。
22. 制御システム定数はＴＣＰ時定数より大きな値にセットされ、特にコントローラのゼロ点は、コントローラに閉ループの挙動を支配させるために、以下の数９に示される数式を満たすようにセットされることを特徴とする請求項２１に記載のデータ伝送方法。
    

    
23. 特にナイキスト判定法を用いることによりコントローラにおける利得（Ｋ）は以下の数１０に示されるような数式を満たすようにセットされることを特徴とする請求項２１又は２２に記載のデータ伝送方法。
    

    
24. ｋ１は、好ましくは以下の数１１に示される数式を満たすような双線形変換（bilinear transformation）により、
    

    

    計算されることを特徴とする請求項１２、２２、又は２３に記載のデータ伝送方法。
25. ｋ２は、好ましくは以下の数１２に示される数式を満たすような双線形変換（bilinear transformation）により計算されることを特徴とする請求項１２、２２、２３、又は２４に記載のデータ伝送方法。
    

    

Images