赤字ラウンドロビン

Deficit Round Robin ( DRR )、またはDeficit Weighted Round Robin ( DWRR )は、ネットワークスケジューラのスケジューリングアルゴリズムです。DRRは、Weighted Fair Queueing (WFQ)と同様に、理想的なGeneralized Processor Sharing (GPS)ポリシーのパケットベースの実装です。これは、1995年にM. ShreedharとG. Vargheseによって、効率的（ O(1)の計算量）かつ公平なアルゴリズムとして提案されました。 ^{[ 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 は、空でないすべてのキューを順番にスキャンします。空でないキューが${\displaystyle i}$パケットが選択されると、その不足カウンタがその量子値だけ増加します。次に、不足カウンタの値は、このターンで送信できる最大バイト数です。不足カウンタがキューの先頭 (HoQ) にあるパケットのサイズよりも大きい場合、このパケットを送信でき、カウンタの値はパケットのサイズだけ減少します。次に、次のパケットのサイズがカウンタの値と比較されます。キューが空になるか、カウンタの値が不足すると、スケジューラは次のキューにスキップします。キューが空の場合、不足カウンタの値は 0 にリセットされます。

変数と定数 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] while (not queue[i].empty() and DC[i] ≥ queue[i].head().size()) do DC[i] := DC[i] − queue[i].head().size() send( queue[i].head() ) queue[i].dequeue() ループ終了もしqueue[i] が空ならば DC[i] := 0 end if end if end for end while

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

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

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

欠損ラウンドロビンアルゴリズムの実装は、Patrick McHardyによってLinuxカーネル向けに作成され^{[ 4 ]}、GNU一般公衆ライセンスの下で公開されました。

Cisco および Juniper ルーターでは、DRR の修正バージョンが実装されています。一部のトラフィッククラスでは DRR の遅延が大きくなる可能性があるため、これらの修正バージョンでは一部のキューに高い優先順位が与えられ、他のキューは標準の DRR アルゴリズムで処理されます。^{[ 5 ] [ 6 ]}

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

• カリフォルニア大学バークレー校 EE122 講義：欠損ラウンドロビン方式を用いた効率的かつ公平な待ち行列システム