赤字ラウンドロビン

デフィシットラウンドロビン（DRR）は、デフィシット加重ラウンドロビン（DWRR ）とも呼ばれ、ネットワークスケジューラのスケジューリングアルゴリズムです。DRRは、加重公平キューイング（WFQ）と同様に、理想的な一般化プロセッサ共有（GPS）ポリシーのパケットベースの実装です。これは、効率的（ O(1)の計算量）かつ公平なアルゴリズムとして、1995年にM. ShreedharとG. Vargheseによって提案されました。 ^[1]

DRRでは、N個のフローを処理するスケジューラ^[a]は、フローごとに1つの量子を使用して設定されます。この全体的な考え方は、各ラウンドでフローは最大バイトを送信でき、残りがあれば次のラウンドに報告されるというものです。このように、フローが長期的に達成する最小レートは です。ここで はリンクレートです。 ${\displaystyle Q_{i}}$${\displaystyle i}$${\displaystyle Q_{i}}$${\displaystyle i}$${\displaystyle {\frac {Q_{i}}{(Q_{1}+Q_{2}+...+Q_{N})}}R}$${\displaystyle R}$

DRR は、空でないキューをすべて順番にスキャンします。空でないキューが選択されると、その不足カウンタがその量子値だけ増加します。次に、不足カウンタの値は、このターンに送信できる最大バイト数です。不足カウンタがキューの先頭 (HoQ) のパケット サイズより大きい場合、このパケットは送信でき、カウンタの値はパケット サイズだけ減少します。次に、次のパケットのサイズがカウンタ値と比較されます。キューが空になるか、カウンタの値が不十分になると、スケジューラは次のキューに進みます。キューが空の場合、不足カウンタの値は 0 にリセットされます。 ${\displaystyle i}$

変数と定数
    const integer N // キューの数
    const integer Q[1..N] // キュークォンタムごと
    整数DC[1..N] // キューごとの不足カウンタ
    queue queue[1..N] // キュー

スケジューリングループ
while true do 
    for i in 1..N do 
        if not queue[i].empty() then
            DC[i]:= DC[i] + Q[i]
            ( queue[i].empty() ではなく、 
                         DC[i] ≥ queue[i].head().size() )の場合、
                DC[i] := DC[i] − キュー[i].head().size()
                送信(キュー[i].head())
                キュー[i].dequeue()
            終了 while  
            if queue[i].empty() then
                DC[i] := 0
            end if 
        end if 
    end for 
end while

他の GPS のようなスケジューリング アルゴリズムと同様に、重みの選択はネットワーク管理者に任されています。

WFQ と同様に、DRR はパケットのサイズに関係なく、各フローに最小レートを提供します。加重ラウンドロビン スケジューリングでは、使用される帯域幅の割合はパケットのサイズによって異なります。

WFQスケジューラの複雑度はO(log(n))（nはアクティブなフロー/キューの数）であるのに対し、量子がこのフローの最大パケットサイズより大きい場合、 DRRの複雑度はO(1)です。ただし、この効率にはコストが伴います。つまり、レイテンシ、つまり理想的なGPSまでの距離は、WFQよりもDRRの方が長くなります。^[2]最悪の場合のレイテンシの詳細については、こちらをご覧ください。^[3]${\displaystyle Q_{i}}$

デフィシットラウンドロビンアルゴリズムの実装は、Linuxカーネル^[4]用にPatrick McHardyによって書かれ、GNU General Public Licenseの下で公開されました。

CiscoとJuniperのルータでは、DRRの修正版が実装されています。DRRの遅延は一部のトラフィッククラスでは大きくなる可能性があるため、これらの修正版では一部のキューに高い優先度を与え、他のキューには標準のDRRアルゴリズムを適用しています。^{[5] [6]}

• スケジューリングアルゴリズム
• 公平なキューイング
• 汎用プロセッサ共有
• 重み付け公平キューイング
• 加重ラウンドロビン
• 公平性の尺度

• UC Berkeley EE122 講義: デフィシットラウンドロビンを使用した効率的な公平キューイング