SrTCMとtrTCMの紹介

6139 ワード
本稿は,QoS Meter機能のアルゴリズムに用いられるRFCの読解ノートである.DPDKのQoS_meterサンプルプログラムはこのアルゴリズムを用いている.
srTCM
SrTCMの英語フルネームはSingle Rate Three Color Marker、単速度三色タグ
Configuration
このアルゴリズムは予めシステムに3つのパラメータを設定し、3つのパラメータは以下の通りである.
  • Committed Information Rate(CIR)、送信情報率.
  • Committed Burst Size(CBS)、Burstサイズをコミットします.
  • Excess Burst Size(EBS)、超過Burstサイズ.

    • CIRは、1秒あたりのIPパケットのバイト数を表すために使用され、ヘッダは含まれる.bytes of IP packets per second, it includes the IP header
    CBSとEBSはバイト単位である.設定する必要があります.推奨値:これらの1つは0より大きく、0より大きいCBSおよびEBSの場合はMTUより大きい値でなければなりません.
    色は緑、黄、赤の3種類があります.簡単に言えば、色とパラメータの対応関係は次のようになります.
  • CBSを超えなければ緑です.
  • はCBSを超えたがEBSを超えなかったのは黄色だった.
  • EBSを超えると赤くなります.

    • Metering & Marking
    アルゴリズムフローチャートの長さは次のとおりです.
                    +------------+
                |   Result   |
                |            V
            +-------+    +--------+
            |       |    |        |
Packet Stream ===>| Meter |===>| Marker |===> Marked Stream
            |       |    |        |
            +-------+    +--------+

    Meter(速度制限器)は速度制限に用いられ、具体的な論理は異なる具体的な設定によって異なる(例えば、赤色のパケット損失、黄色の正常な送信、緑色の特定のキューへの送信など).また、Meterは各packetを計算し、得られた結果をMarker(マーカー)に渡す.Markerは各packetとそれに対応する結果値を受け取り、計算結果に基づいてすべてのpacketのIPヘッダのDS fieldに異なる「色」(着色、mark、またはtag)をマークする.
    Meterには2つの動作モードがあります.
  • 色盲モード(Color-Bind mode)は、すべてのincoming packetが無色であると仮定する.
  • 非色盲モード(Color-Aware mode)は、すべてのincoming packetが以前のネットワーク要素によって着色されたと仮定する.Meterが非色盲モードで動作している場合、各packetには緑か黄か赤の色があると考えられます.

    • Meter動作は2つのトークンバケツで表される(CとE).CとEには共通のCIRがある.トークンバケツのCのsizeはCBS、EのsizeはEBSです.
    t時刻をTc(t)で表し、トークンバケツCにあるトークン数は、Te(t)と同様である.開始時、Tc(0)=CBS、Te(0)=EBSとなる.
    その後、毎秒CIRは、トークンバケットが不満であれば、トークン数は1増加し、Tcを増加した後にTeを増加する.
  • If Tc is less than CBS, Tc is incremented by one, else
  • if Te is less then EBS, Te is incremented by one, else
  • neither Tc nor Te is incremented.

    • Meterの動作アルゴリズムは以下の通りです.
    色盲モードで動作し、Bバイトサイズのパケットがt時間に到着した場合、アルゴリズムは、トークンバケツCがBを通過させるのに十分である場合、tagはこのパケットを緑色とし、対応するTcを減算する.CがBを通過させるのに十分でなく、EがBを通過させるのに十分でない場合、tagはこのパケットを黄色にし、対応するTeを減算する.そうでなければtagこのパッケージは赤です.
  • If Tc(t)-B >= 0, the packet is green and Tc is decremented by B down to the minimum value of 0, else
  • if Te(t)-B >= 0, the packets is yellow and Te is decremented by B down to the minimum value of 0, else
  • the packet is red and neither Tc nor Te is decremented.

    • 非色盲モードで動作し、サイズBバイトのパケットがt時間に到着すると、アルゴリズムは、パケットが以前tagが緑色になり、トークンバケツCがBを通過させるのに十分である場合、パケットは依然としてtagが緑色になり、対応するTcを減算する.トークンバケットCがBを通過させるのに十分でなく、パケットが以前tagの緑色または黄色であり、トークンバケットEがBを通過させるのに十分である場合、tagは黄色になり、対応するTeを減算する.そうでない場合(2つの場合:以前はこのパケットtagが赤色になっていたか、トークンバケツEがBを通過させるのに十分ではなかった)tagが赤色になっている.
  • If the packet has been precolored as green and Tc(t)-B >= 0, the packet is green and Tc is decremented by B down to the minimum value of 0, else
  • If the packet has been precolored as green or yellow and if Te(t)-B >= 0, the packets is yellow and Te is decremented by B down to the minimum value of 0, else
  • the packet is red and neither Tc nor Te is decremented.

    • trTCM
    全称Two Rate Three Color Marker、デュアルレート3色タグ.基本的な考え方はsrTCMと同じで,いくつかの細部の違いがある.
    Configuration
    4つのパラメータ
  • Peak Information Rate(PIR)、ピーク情報率.
  • Peak Burst Size(PBS)、ピークBurstサイズ.
  • Committed Information Rate(CIR)、送信情報率.
  • Committed Burst Size(CBS)、Burstサイズをコミットします.

    • PIRおよびCIRは、1秒あたりのIPパケットのバイト数を表すために使用される.PBSとCBSはバイト単位で0より大きくなければならず、現在のパスMTUより大きく設定することを推奨する.
    簡単に言えば、pktの色と4つのパラメータの対応関係は、packetがPIRを超えると赤色とマークされる.PIRを超えなければ、packetがCIRを超えたかどうかを見て、超えたら黄色とマークします.超えていない場合は緑と表記します.
    A packet is marked red if it exceeds the Peak Information Rate (PIR). Otherwise it is marked either yellow or green depending on whether it exceeds or doesn't exceed the Committed Information Rate (CIR).
    Metering & Marking
    Meterは同様に色盲モードと非色盲モードに分けられる.
    PとCは2つのトークンバケツで表される.PとCの速度はそれぞれPIRとCIRであり,大きさはそれぞれPBSとCBSであった.開始時、Tp(0)=PBS、Tc(0)=CBS.その後、トークンバケツが満タンでない場合、バケツPは1ずつ増加し、毎秒PIR回となる.バケツCは1ずつ増加し、毎秒CIR回である.
    Thereafter, the token count Tp is incremented by one PIR times per second up to PBS and the token count Tc is incremented by one CIR times per second up to CBS.
    ワークアルゴリズムは次のとおりです.
    色盲モードで動作し、サイズBバイトのパケットがt時間に到着した場合、アルゴリズムは、トークンバケツPがBを通過させるのに十分でない場合、tagは赤色であり、そうでない場合、トークンバケツCがBを通過させるのに十分でない場合、tagは黄色であり、バケツPを差し引くトークンである.トークンバケツCがBを通過させるのに十分である場合、tagは緑色であり、バケツCとバケツPのトークンを同時に差し引く.
  • If Tp(t)-B < 0, the packet is red, else
  • if Tc(t)-B < 0, the packet is yellow and Tp is decremented by B, else
  • the packet is green and both Tp and Tc are decremented by B.

    • 非色盲モードで動作し、サイズBバイトのパケットがt時間に到着すると、アルゴリズムは、前のtagが赤色になったり、トークンバケツPがBを通過させるのに十分でない場合、tagが赤色になったり、そうでない場合、前のtagが黄色になったり、トークンバケツCがBを通過させるのに十分でない場合、tagは黄色であり、バケツPを差し引くトークンである.トークンバケツCがBを通過させるのに十分であり、以前に緑色としてマークされていた場合、tagは緑色であり、バケツCとバケツPのトークンを同時に差し引く.
  • If the packet has been precolored as red or if Tp(t)-B < 0, the packet is red, else
  • if the packet has been precolored as yellow or if Tc(t)-B < 0, the packet is yellow and Tp is decremented by B, else
  • the packet is green and both Tp and Tc are decremented by B.

    • Service Example
    実際のQoS Meter実装は、RFCに対する参照のみであり、必ずしも完全に同じではない可能性がある(The actual implementation of a Meter doesn't need to be modeled according to the above formal specification.)
    アプリケーションは、DS fieldのtagのcolorに基づいてpacketを適切にスケジュールできます.たとえば、次のようになります.
    For example, a service may discard all red packets, because they exceeded both the committed and excess burst sizes, forward yellow packets as best effort, and forward green packets with a low drop probability.
    まとめ
    srTCMアルゴリズムはlength of burstに基づいて速度制限を行うことが分かる.「単一レート」とは、このアルゴリズムにおける2つのトークンバケツの成長速度が同じ毎秒CIRであることを意味する.2つのトークンバケツは異なる大きさを持っていて、まるで1本の数軸が2つの点で3つの段階に分かれているようで、緑、黄、赤に対応しています.
    trTCMの「二重速度」とは、2つのトークンバケツが異なる成長速度を有することを意味する.成長の遅いトークンバケツは緑のマークを発行する厳しい指標であり、成長の速いトークンバケツは下限であり、このトークンバケツもhandleが来ない流量では非情なtagが赤であり、両者の間は黄色である.
    Reference
    RFC 2697 and 2698
    最小生成ツリーprimeアルゴリズムとクルーズカールアルゴリズム
    leaky bucketアルゴリズムの実現について話します