加重ラウンドロビン

加重ラウンドロビン( WRR ) は、データ フローのネットワーク スケジューラですが、プロセスのスケジュールにも使用されます。

加重ラウンドロビン^{[ 1 ]}は、ラウンドロビンスケジューリングの一般化です。複数のキューまたはタスクに対してサービスを提供します。ラウンドロビンはキューまたはタスクを循環的に処理し、1サイクルごとに1つのサービス機会を与えますが、加重ラウンドロビンは、設定された重みによって指定された固定数の機会を各キューまたはタスクに提供します。重みは、各キューまたはタスクが受け取る容量の割合に影響を与えます。コンピュータネットワークにおいて、サービス機会とは、選択されたキューが空でない場合、1つのパケットを送信することです。

すべてのパケットが同じサイズの場合、WRRは汎用プロセッサ共有（GPS）の最も単純な近似です。WRRにはいくつかのバリエーションがあります。^{[ 2 ]}主なものは、古典的なWRRとインターリーブWRRです。

アルゴリズム

原則

以下では、WRR をネットワーク スケジューラとして説明します。同様の方法でタスクのスケジュール設定にも使用できます。

重み付きラウンドロビン方式のネットワークスケジューラには、入力キューが存在します。各キューには、重みと呼ばれる正の整数 が関連付けられています。WRRスケジューラは周期的な動作をします。各サイクルにおいて、各キューには 送信機会 が与えられます。 ${\displaystyle n}$ ${\displaystyle q_{1},...,q_{n}}$ ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$

さまざまな WRR アルゴリズムは、サイクル内でのこれらの機会の分布によって異なります。

古典的なWRR

古典的なWRR ^{[ 2 ] [ 3 ] [ 4 ]}では 、スケジューラはキューを巡回します。キューが選択されると、スケジューラはパケットの送信またはキューの終端までパケットを送信します。 ${\displaystyle q_{i}}$ ${\displaystyle w_{i}}$

定数と変数: const N // キューの数 const weight[1..N] // 各キューの重み queues[1..N] // キュー i // キューのインデックス c // パケットカウンター 指示: while true do for i in 1 .. N do c := 0 (queue[i].emptyではない)かつ(c<weight[i])の場合 送信(キュー[i].head()) キュー[i].dequeue() c:= c+1

インターリーブWRR

最大重みを とする。IWRRでは、[ ^{1 ] [ 5 ]各}サイクルはラウンドに分割される。重み のキューは、 の場合にのみラウンドごとに1つのパケットを送出できる。 ${\displaystyle w_{max}=\max\{w_{i}\}}$ ${\displaystyle w_{max}}$ ${\displaystyle w_{i}}$ ${\displaystyle r}$ ${\displaystyle r\leq w_{i}}$

定数と変数: const N // キューの数 const weight[1..N] // 各キューの重み 定数w_max queues[1..N] // キュー i // キューのインデックス r // ラウンドカウンター 説明書： trueの場合、 rが1..w_maxの場合、 iが1..Nの場合、(queue[i].emptyではない)かつ( weight [ i ] > = r )の場合、 送信(キュー[i].head()) キュー[i].dequeue()

例

CWRRとIWRRのスケジュール例

3つのキューとそれぞれ重みを持つシステムを考えてみましょう。最初のキューに7つのパケット（A、B、C、D、E、F、G）、2番目のキューに3つのパケット（U、V、W）、3番目のキューに2つのパケット（X、Y）がある状況を考えてみましょう。これ以上のパケットの到着はないものとします。 ${\displaystyle q_{1},q_{2},q_{3}}$ ${\displaystyle w_{1}=5,w_{2}=2,w_{3}=3}$

従来の WRR では、最初のサイクルで、スケジューラはまずキューの先頭にある 5 つのパケットA、B、C、D、E ( 以降) を選択して送信し、次に 2 番目のキュー を選択して キューの先頭にある 2 つのパケットU、V ( 以降) を送信し、最後に重みが 3 に等しいがパケットが 2 つしかない 3 番目のキューを選択します。そのため、X、Yが送信されます。 Yの送信が終了するとすぐに2 番目のサイクルが開始され、からF、Gが送信され、続いて から W が送信されます。 ${\displaystyle q_{1}}$ ${\displaystyle w_{1}=5}$ ${\displaystyle q_{2}}$ ${\displaystyle w_{2}=2}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

インターリーブWRRでは、最初のサイクルは5ラウンドに分割されます（）。最初のラウンド（r=1）では、各キューから1つのパケットが送信され（A、U、X）、2番目のラウンド（r=2）では、各キューから別のパケットも送信され（B、V、Y）、3番目のラウンド（r=3）では、キューのみが パケットを送信できます（、および）。ただし、 が空であるため、からは Cのみが送信され、4番目と5番目のラウンドでは からは D、Eのみが送信されます。その後、2番目のサイクルが開始され、F、W、Gが送信されます。 ${\displaystyle max(w_{1},w_{2},w_{3})=5}$ ${\displaystyle q_{1},q_{3}}$ ${\displaystyle w_{1}>=r}$ ${\displaystyle w_{2}<r}$ ${\displaystyle w_{3}>=r}$ ${\displaystyle q_{3}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{1}}$

タスクのスケジュール

タスクやプロセスのスケジューリングは、WRRではパケットスケジューリングと同様の方法で行うことができます。アクティブなタスクのセットを考えると、それらは周期的にスケジュールされ、各タスクは量子またはプロセッサ時間のスライスを取得します。^{[ 6 ] [ 7 ]} ${\displaystyle n}$ ${\displaystyle \tau _{i}}$ ${\displaystyle w_{i}}$

プロパティ

ラウンドロビンと同様に、加重ラウンドロビン スケジューリングはシンプルで、実装が簡単で、作業を節約でき、飢餓状態になりません。

パケットをスケジュールする際、すべてのパケットのサイズが同じであれば、WRRとIWRRは一般化プロセッサ共有の近似値になります。^{[ 8 ]}キューは（すべてのキューがアクティブな場合）に等しい帯域幅の長期部分を受け取りますが、GPSは空でない各キューから微量のデータを提供し、この部分を任意の間隔で提供します。 ${\displaystyle q_{i}}$ ${\displaystyle {\frac {w_{i}}{\sum _{j=1}^{n}w_{j}}}}$

キューに可変長のパケットがある場合、各キューが受信する帯域幅の部分は重みだけでなくパケット サイズにも依存します。

各キューの平均パケットサイズが既知である場合、各キューは に等しい帯域幅の長期部分を受け取ります 。各キューにリンク容量の一部（ の場合）を割り当てることが目的である場合、 を設定できます 。 ${\displaystyle s_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle {\frac {s_{i}\times w_{i}}{\sum _{j=1}^{n}s_{j}\times w_{j}}}}$ ${\displaystyle q_{i}}$ ${\displaystyle \rho _{i}}$ ${\displaystyle \sum _{i=1}^{n}\rho _{i}=1}$ ${\displaystyle w_{i}={\frac {\rho _{i}}{s_{i}}}}$

IWRRはWRRよりもクラスあたりのバーストが小さいため、最悪の場合の遅延も小さくなります。^{[ 9 ]}

制限と改善

ネットワークパケットスケジューリングのためのWRRは、1991年にKatevenis、Sidiropoulos、Courcoubetisによって初めて提案されました^{[ 1 ]}。特に、固定サイズのパケット（セル）を使用するATMネットワークのスケジューリングを対象としています。重み付けラウンドロビンキューイングの主な制限は、すべてのキュー内のすべてのパケットが同じサイズであるか、平均パケットサイズが事前にわかっている場合にのみ、各サービスクラスに正しい割合の帯域幅が提供されることです。可変サイズのパケットを使用するIPネットワークのより一般的なケースでは、GPSを近似するために、重み係数をパケットサイズに基づいて調整する必要があります。これには平均パケットサイズの推定が必要であり、WRRを使用して適切なGPS近似を実際に達成することは困難です^{[ 1 ] 。}

デフィシットラウンドロビンはWRRの後継であり、各接続の平均パケットサイズを事前に知ることなく、より正確なGPS近似を実現します。また、上記の制限に対処するための、より効果的なスケジューリング手法（例えば、重み付け公平キューイング）も導入されました。

参照

• 公平な待ち行列
• 公平性の尺度
• プロセッサ共有
• 統計的時分割多重化

参考文献

1. Katevenis, M.; Sidgiropoulos, S.; Courcoubetis, C. (1991). 「汎用ATMスイッチチップにおける重み付けラウンドロビンセル多重化」. IEEE Journal on Selected Areas in Communications . 9 (8): 1265– 1279. Bibcode : 1991IJSAC...9.1265K . doi : 10.1109/49.105173 . ISSN  0733-8716 .
2. Chaskar, HM; Madhow, U. (2003). 「調整可能なレイテンシによる公平なスケジューリング：ラウンドロビン方式」. IEEE/ACM Transactions on Networking . 11 (4): 592– 601. Bibcode : 2003ITNet..11..592C . doi : 10.1109/TNET.2003.815290 . ISSN 1063-6692 . S2CID 8010108 .  
3. Brahimi, B.; Aubrun, C.; Rondeau, E. (2006). 「カラーペトリネットを用いたイーサネットスイッチにおけるスケジューリングポリシーのモデリングとシミュレーション」2006 IEEE 新興技術・ファクトリーオートメーション会議pp.  667– 674. doi : 10.1109/ETFA.2006.355373 . ISBN 0-7803-9758-4. S2CID  6089006 .
4. F. Baker; R. Pan (2016年5月). 「2.2.2. ラウンドロビンモデル」.キューイング、マーキング、およびドロップについて（技術レポート）. IETF. RFC 7806.
5. Semeria, Chuck (2001). 「差別化されたサービスクラスのサポート：キュースケジューリング規律」（PDF）（レポート）pp.  15– 18. 2020年5月4日閲覧。
6. Beaulieu, Alain (2017年冬). 「リアルタイムオペレーティングシステム – スケジューリングとスケジューラ」(PDF) . 2020年5月4日閲覧。
7. 米国 20190266019、フィリップ・D・ハーシュ、「改良された加重ラウンドロビン手法を用いたタスクスケジューリング」、2019年8月29日発行 
8. フォール、ケビン（1999年4月29日）「EECS 122、「通信ネットワーク入門」、講義27、「ベストエフォート型接続と保証型接続のスケジューリング」. 2020年5月4日閲覧。
9. タバタベイ、シード・モハマドホセイン;ル・ブーデック、ジャン＝イヴ。マルク・ボワイエ（2020年9月22～24日）。 「インターリーブ加重ラウンドロビン: ネットワーク微積分分析」。手順第32国際のテレトラフィック会議 (ITC 32)。arXiv : 2003.08372。土井: 10.1109/ITC3249928.2020.00016。

「 https://en.wikipedia.org/w/index.php?title=Weighted_round_robin&oldid=1334561833」より取得