重み付け公平キューイング

重み付け公平キューイング( WFQ ) は、ネットワークスケジューリングアルゴリズムです。WFQ は、汎用プロセッサ共有(GPS) ポリシーのパケットベースの実装であり、公平キューイング(FQ)の自然な拡張です。FQ ではリンクの容量が均等に分割されますが、WFQ では、スケジューラがフローごとに容量のどの部分を割り当てるかを指定できます。

重み付け公平キューイングは、到着パターンに関係なく、一般化されたプロセッサ共有を「1パケットの送信時間内に」近似するため、パケット単位GPS（PGPSまたはP-GPS）とも呼ばれます。^[1]

パラメータ化と公平性

他の GPS のようなスケジューリングアルゴリズムと同様に、重みの選択はネットワーク管理者に任されています。何が「公平」であるかの一意の定義はありません (詳細については、「公平なキューイング」の「公平性」を参照してください)。

WFQ の重みを動的に調整することにより、WFQ はサービス品質の制御、たとえば保証されたデータレートの実現に利用できます。 ^{[引用が必要]}

比例的に公平な動作は、重みをに設定することによって実現できます。ここで、はデータフローのデータビットあたりのコストです。たとえば、CDMAスペクトラム拡散セルラーネットワークでは、コストは必要なエネルギー (干渉レベル) であり、動的チャネル割り当てシステムでは、コストは、同一チャネル干渉を回避するために同じ周波数チャネルを使用できない近くの基地局サイトの数である可能性があります。 $w_{i}=1/c_{i}$ $c_{i}$ $i$

アルゴリズム

WFQ では、 $N$ 個のフローを処理するスケジューラは、フローごとに 1 つの重みで設定されます。すると、数値のフローは平均データレートを達成します。ここで、はリンクレートです。すべての重みが等しい WFQ スケジューラは FQ スケジューラです。 $w_{i}$ $i$ ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ $R$

すべての公平キューイングスケジューラと同様に、各フローは他のフローから保護されており、データフローがリーキーバケット制約されている場合、エンドツーエンドの遅延境界が保証されることが証明されています。 ^[2]

WFQ のアルゴリズムはFQ のアルゴリズムと非常によく似ています。パケットごとに仮想の理論上の出発日が計算されます。これは、スケジューラが完全な GPS スケジューラである場合の出発日として定義されます。次に、出力リンクがアイドル状態になるたびに、日付が最も小さいパケットが送信用に選択されます。

擬似コードは、仮想出発時刻の計算を次のように置き換えることで、 FQのコードから簡単に得ることができる。

パケット.virFinish = virStart + パケット.size / Ri

と。 $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$

GPS 近似としての WFQ

WFQはPGPSという名前で「GPSの優れた近似値」として設計されており、「到着パターンに関係なく、1パケットの送信時間内で」GPSに近似することが証明されています。^[1]

WFQ の実装は公平なキューイングに似ているため、同じO(log(n)) の複雑さを持ちます。ここで、n はフローの数です。この複雑さは、パケットが送信されるたびに、仮想終了時間が最小のキューを選択する必要があることから生じます。

WFQ の後、GPS の他の実装がいくつか定義されました。

WFQ が理想的な GPS ポリシーに対して最大で「1 パケット」遅れている場合でも、任意に先行する可能性があります。最悪ケースの公平な加重公平キューイング(WF2Q) は、各パケットに仮想サービス開始を追加することでこれを修正し、仮想サービス開始が現在の時間よりも小さくない場合にのみパケットを選択します。^[3]
仮想終了時間が最小となるキューの選択をワイヤスピードで実装するのは難しい場合があります。そこで、デフィシットラウンドロビンなど、複雑さの少ない GPS の近似方法が定義されています。

歴史

^{帯域幅を任意の方法で共有するためのパラメータの導入は、 [4]}の最後でFQの拡張として言及されている。重み付けという用語は^[1]で初めて登場する。

参照

参考文献

^ abc Parekh, AK; Gallager, RG (1993). 「統合サービスネットワークにおけるフロー制御に対する一般化プロセッサ共有アプローチ: 単一ノードの場合」(PDF) . IEEE/ACM Transactions on Networking . 1 (3): 344. doi :10.1109/90.234856. S2CID 52808341.
^ Stiliadis, D.; Varma, A. (1998). 「レイテンシレートサーバー: トラフィックスケジューリングアルゴリズムの分析のための一般的なモデル」(PDF) . IEEE/ACM Transactions on Networking . 6 (5): 611. doi :10.1109/90.731196.
^ Bennett, JCR; Hui Zhang (1996)。「WF/sup 2/Q: 最悪ケースの公平な加重公平キューイング」。IEEE INFOCOM '96 の議事録。コンピュータ通信に関する会議。第 1 巻。p. 120。doi : 10.1109 / INFCOM.1996.497885。ISBN 978-0-8186-7293-4.S2CID 17558577 。
^ Demers, A.; Keshav, S.; Shenker, S. (1989). 「公平なキューイングアルゴリズムの分析とシミュレーション」ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .

[GPS-1] Parekh, AK; Gallager, RG (1993). 「統合サービスネットワークにおけるフロー制御に対する一般化プロセッサ共有アプローチ: 単一ノードの場合」(PDF) . IEEE/ACM Transactions on Networking . 1 (3): 344. doi :10.1109/90.234856. S2CID 52808341.

[2] Stiliadis, D.; Varma, A. (1998). 「レイテンシレートサーバー: トラフィックスケジューリングアルゴリズムの分析のための一般的なモデル」(PDF) . IEEE/ACM Transactions on Networking . 6 (5): 611. doi :10.1109/90.731196.

[WF2Q-3] Bennett, JCR; Hui Zhang (1996)。「WF/sup 2/Q: 最悪ケースの公平な加重公平キューイング」。IEEE INFOCOM '96 の議事録。コンピュータ通信に関する会議。第 1 巻。p. 120。doi : 10.1109 / INFCOM.1996.497885。ISBN 978-0-8186-7293-4.S2CID 17558577 。

[FQ-4] Demers, A.; Keshav, S.; Shenker, S. (1989). 「公平なキューイングアルゴリズムの分析とシミュレーション」ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .