汎用セル レート アルゴリズム(GCRA) は、非同期転送モード(ATM) ネットワークで使用されるネットワーク スケジューラのリーキー バケット型スケジューリング アルゴリズムです。 [1] [2]これは、仮想チャネル(VC) や仮想パス (VP)上のセルのタイミングを、そのセルが属する VC または VP のトラフィック コントラクトに含まれる帯域幅とジッタ制限と比較して測定するために使用されます。トラフィック コントラクトで指定された制限に適合しないセルは、トラフィック シェーピングで再タイミング (遅延) されたり、トラフィック ポリシングでドロップ (破棄) されたり、優先順位が下げられたり (降格) されることがあります。優先順位が下げられた不適合セルは、輻輳が発生しているネットワークの下流コンポーネントによって、優先順位の高いセルよりも優先してドロップされることがあります。あるいは、契約上は超過セルであっても、十分な容量があれば宛先 (VC または VP 終端) に到達できます。「優先制御」を参照してください。
GCRAは、ネットワーク内の接続のトラフィック、すなわちユーザ・ネットワーク・インタフェース（UNI）またはネットワーク間インタフェースまたはネットワーク・ネットワーク・インタフェース（INI/NNI）での使用量/ネットワーク・パラメータ制御（UPC/NPC）をチェックするための基準として提供されています。 [3]また、ホストのネットワーク・インタフェース・カード（NIC）によってATMネットワークに送信されるセル（ATM PDU Data_Requests）のタイミングの基準としても提供されています。[3]これにより、ネットワーク内、すなわちUNIのネットワーク側でセルがUPC/NCPによって破棄されないことが保証されます。 ただし、GCRAはあくまでも基準として提供されているため、ネットワーク・プロバイダとユーザは、同じ結果をもたらす他のアルゴリズムを使用できます。
GCRAの説明
GCRAは、ATMフォーラムのユーザネットワークインタフェース（UNI）[1]とITU-T勧告I.371「B-ISDNにおけるトラフィック制御と輻輳制御」[2]で説明されています 。どちらの情報源も、GCRAを仮想スケジューリングアルゴリズムと連続状態リーキーバケットアルゴリズムという2つの同等の方法で説明しています（図1）。
リーキーバケットの説明
概念的には、リーキーバケツアルゴリズムによる説明の方が理解しやすいかもしれません。これは、漏れのあるバケツという単純なアナロジーに基づいているためです（リーキーバケツのページの図1を参照）。しかし、リーキーバケツのアナロジーを適用したアルゴリズムがGCRAにまで及ぶことに関して、文献では混乱が生じています。GCRAは、リーキーバケツをキューとしてではなく、リーキーバケツをメーターとして解釈したものと考えるべきです。
しかしながら、このリーキーバケットの記述を理解することには利点がある一方で、直接実装した場合に必ずしも最良（最速）のコードが得られるとは限りません。これは、2つの記述のフロー図で実行されるアクションの相対的な数からも明らかです（図1）。
ITU-T では、連続状態リーキー バケット アルゴリズムについて次のように説明しています。「連続状態リーキー バケットは、実数値の内容が時間単位あたり 1 単位の内容の連続速度で流出し、適合セルごとに増分Tで内容が増加する有限容量のバケットと考えることができます...セルの到着時にバケットの内容が限界値τ以下の場合、セルは適合しています。それ以外の場合、セルは不適合です。バケットの容量 (カウンターの上限) は ( T + τ ) です。」[2]漏洩は時間単位あたり 1 単位の内容であるため、各セルの増分Tと限界値τは時間の単位であることは注目に値します。
連続状態リーキー バケット アルゴリズムのフロー ダイアグラムを考えてみましょう。ここで、Tは放出間隔、τは限界値です。セルが到着すると、最後の適合セルが到着したときの状態Xと、間隔t a – LCTにどれだけリークしたかからバケットの状態が計算されます。この現在のバケット値はX'に格納され、限界値τと比較されます。 X'の値がτより大きくない場合、セルの到着が早すぎず、コントラクト パラメータに適合しています。X ' の値がτより大きい場合は、適合していません。適合している場合、セルが遅れたために適合している、つまりバケットが空である ( X' <= 0) 場合、XはTに設定され、早かったが早すぎない ( τ >= X' > 0) 場合、XはX' + Tに設定されます。
したがって、フロー図は漏れやすいバケツのアナロジー (メーターとして使用) を直接模倣しており、XとX'はバケツのアナログとして機能します。
仮想スケジュールの説明
仮想スケジューリングアルゴリズムは、リーキーバケットのような分かりやすいアナロジーとはそれほど関連が明確ではありませんが、GCRAの機能とその最適な実装方法をより明確に理解するのに役立ちます。その結果、このバージョンを直接実装することで、リーキーバケットの記述を直接実装するよりも、よりコンパクトで高速なコードを実現できます。
仮想スケジューリング アルゴリズムに関する説明は、ITU-T によって次のように与えられています。「仮想スケジューリング アルゴリズムは理論上の到着時間 (TAT) を更新します。TAT とは、送信元がアクティブなときにセル レートΛ [= 1/ T ] に対応する送信間隔Tでセルが均等に送信されるという仮定のもとでの、セルの「公称」到着時間です。セルの実際の到着時間が、 TATおよびセル レートに関連付けられた許容値τに対して「早すぎる」ものでない場合、つまり、実際の到着時間が理論上の到着時間から制限値を引いた値 (t a > TAT – τ ) より後である場合、セルは適合しています。そうでない場合、セルは不適合です。」[2]セルが不適合の場合、TATは変更されません。セルが適合しており、その TAT より前に到着した場合 (バケットが空ではなく制限値未満である場合に相当)、次のセルのTATは単にTAT + Tになります。ただし、セルがTATより遅く到着した場合、次のセルのTATは、そのセルのTATではなく、そのセルの到着時刻に基づいて計算されます。これにより、送信にギャップが生じた場合（バケットが空でなくなる場合と同等）、クレジットが蓄積されるのを防ぎます。
このアルゴリズムのバージョンが機能するのは、τがジッタがない場合と比べてセルがどれだけ早く到着できるかを定義するためです。「リーキーバケット：遅延変動許容値」を参照してください。別の見方をすると、TATはバケットが次に空になる時刻を表し、そのτ前はバケットがちょうど限界値まで満たされる時刻です。したがって、どちらの見方でも、 TATよりτ以上前にセルが到着した場合、適合するには早すぎることになります。
トークンバケットとの比較
GCRAは、トークンバケットアルゴリズムの実装とは異なり、バケットの更新プロセス（リークや定期的なトークンの追加）をシミュレートしません。代わりに、セルが到着するたびに、バケットのレベルが最後に計算されてからリークした量、またはバケットが次に空になる時間（= TAT）を計算します。これは本質的に、リークプロセスを（リアルタイム）クロックに置き換えるものであり、ほとんどのハードウェア実装は既にこの機能を実装していると考えられます。
このプロセスをRTCに置き換えることが可能なのは、ATMセルの長さが固定長（53バイト）であるため、Tは常に定数であり、新しいバケットレベル（またはTAT ）の計算に乗算や除算が含まれないためです。その結果、計算はソフトウェアで迅速に実行でき、セル到着時にトークンバケットよりも多くのアクションが実行されますが、タスクを実行するプロセッサの負荷という点では、個別の更新プロセスが存在しないことで十分に補えます。さらに、バケット更新のシミュレーションが行われないため、接続が静止しているときはプロセッサに負荷がかかりません。
しかし、可変長パケット（リンク層PDU）を使用するプロトコルにおいて、パケット/フレーム レートではなく帯域幅を制限するために GCRA を使用する場合、乗算が必要になります。基本的に、各適合パケットのバケツ（または TAT）に追加される値は、パケット長に比例する必要があります。ただし、前述の GCRA ではバケツの水の単位は時間ですが、可変長パケットの場合は、パケット長と時間の積の単位が必要になります。したがって、高速ハードウェア乗算器（FPGA など）にアクセスせずに GCRA を適用して可変長パケットの帯域幅を制限することは、実用的ではない可能性があります。ただし、パケットまたはセルの長さを無視する限り、GCRA は常にパケットまたはセル レートを制限するために使用できます。
デュアルリーキーバケットコントローラ
GCRAの複数の実装は、デュアルリーキーバケットトラフィックポリシングまたはトラフィックシェーピング機能において、VCまたはVPに同時に適用できます。例えば、可変ビットレート（VBR）VCに適用できます。これにより、このVBR VC上のATMセルを、平均セルレート（SCR）と最大バーストサイズ（MBS）に制限できます。同時に、デュアルリーキーバケットトラフィックポリシング機能は、バースト内のセルレートをピークセルレート（PCR）と最大セル遅延変動許容値（CDVt）に制限することもできます。詳細については、トラフィック契約#トラフィックパラメータを参照してください。
これは、VBR VC 上の送信が固定長メッセージ (CPCS-PDU) の形式で行われる場合、つまり一定の間隔またはメッセージ間時間 (IMT) で送信され、その送信にセル数 (MBS) を要する場合を最もよく理解できます。ただし、VBR トラフィックの説明とデュアル リーキー バケットの使用は、このような状況に限定されません。この場合、IMT 間隔での平均セル レートは SCR (=MBS/IMT) です。個々のメッセージは PCR で送信でき、PCR は物理リンクの帯域幅 (1/ δ ) と SCR の間の任意の値にすることができます。これにより、メッセージ間隔 IMT よりも短い期間で、メッセージのインスタンス間にギャップを伴ってメッセージを送信できます。
デュアルリーキーバケットでは、1つのバケットがトラフィックに適用され、その送信間隔は1/SCR、制限値τ SCRで、MBSはメッセージ内のセル数となります。リーキーバケット#最大バーストサイズを参照してください。2つ目のバケットは、送信間隔が1/PCR、制限値τ PCRで、接続パスのその時点までのCDVを許容します。リーキーバケット#遅延変動許容値を参照してください。その後、セルはPCRでτ PCRのジッタで、MBSセルの最大数まで通過を許可されます。次のMBSセルバーストは、最初のMBSセルバーストの後にMBS x 1/SCRから開始して通過を許可されます。
セルが 1/PCR よりも高いレートでバーストして到着する場合（MBS セルは (MBS - 1)/PCR - τ PCRよりも低いレートで到着します）、または MBS を超えるセルが PCR に到着する場合、あるいは MBS セルのバーストが IMT よりも近い間隔で到着する場合、デュアル リーキー バケットはこれを検出し、接続を適合させるのに十分なセルを遅延（シェーピング）またはドロップまたは優先順位を下げ（ポリシング）します。
図3は、セル損失優先度（CLP）値が1（低）と0（高）の両方のセルフローに対するSCRおよびPCR制御の参照アルゴリズムを示しています。つまり、両方の優先度を持つセルは同じ扱いとなります。高優先度セルと低優先度セルを異なる扱いにする同様の参照アルゴリズムは、I.371の付録Aにも示されています。[2]
参照
参考文献
- ^ ATMフォーラム、ユーザーネットワークインターフェース（UNI）、v. 3.1、ISBN 0-13-393828-X、Prentice Hall PTR、1995年。
- ^ abcde ITU-T、「B ISDNにおけるトラフィック制御と輻輳制御」、勧告I.371、国際電気通信連合、2004年、付録A、87ページ。
- ^ ab ITU-T、B ISDNにおけるトラフィック制御と輻輳制御、勧告I.371、国際電気通信連合、2004年、17ページ
