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

重み付き公平キューイング、Weighted Fair Queueing （ WFQ ）は、帯域幅の割り当てと遅延範囲をサポートするスケジューリングアルゴリズムである。元のWFQが10年以上前に提案されて以来、複雑さと正確さの間のさまざまなトレードオフで多くのさまざまなバリエーションが開発されてきた。WFQは、QoSをサポートするためにルーターに広く実装されている。最初にWFQの主要なプロパティを確認してから、高速実装用に設計されたいくつかのバリアントについて説明する^[1]。

WFQは、一般化されたプロセッサ共有（GPS）ポリシーのパケットベースの実装であり、フェアキューイング（FQ）の自然な拡張である。FQはリンクの容量を等しいサブパートで共有するが、WFQでは、スケジューラが各フローに対して、容量のどの割合を与えるかを指定できる。

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

パラメータ化と公平性

他のGPSに似たスケジューリングアルゴリズムと同様に、重みの選択はネットワーク管理者に任されている。「フェア」とは何かの一意の定義はない（ Fair queuing § Fairness参照） Fair queuing § Fairnessさらなる議論のためのFair queuing § Fairness ）。

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

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

アルゴリズム

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

すべてのフェアキュースケジューラと同様に、各フローは他のフローから保護されており、データフローがリーキーバケットに制約されている場合は、エンドツーエンドの遅延範囲が保証されることが証明できる。 ^[3]

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

仮想出発時間の計算を次のように置き換えることにより、FQの1つから疑似コードを簡単に取得できる。

 packet.virFinish = virStart + packet.size / Ri

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

GPS近似としてのWFQ

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

WFQの実装はフェアキューイングに似ているため、 O（log（n））の複雑さは同じである。ここで、 nはフローの数である。この複雑さは、パケットが送信されるたびに仮想終了時間が最も短いキューを選択する必要があるために生じる。

WFQの後、GPSの他のいくつかの実装が定義されている。

WFQが理想的なGPSポリシーに対してせいぜい「1パケット」遅れたとしても、勝手に進む可能性がある。ワーストケースフェアウェイトフェアキューイング （WF2Q）は、各パケットに仮想サービスの開始を追加することで修正し、仮想サービスの開始が現在の時間以上の場合にのみパケットを選択する。 ^[4]
最小限の仮想終了時間でキューを選択することは、ワイヤスピードで実装するのが難しい場合がある。次に、不足ラウンドロビンのように、複雑さの少ないGPSの他の近似が定義された。

歴史

FQへの可能な拡張として、 ^[5]最後に記載されている任意の方法で帯域幅を共有するためのパラメーターの導入。加重という用語が最初に表示される。 ^[2]

参考文献

^ Wang, Zheng. (2001). Internet QoS : architectures and mechanisms for quality of service. San Francisco: Morgan Kaufmann. ISBN 978-1-55860-608-1. OCLC 162595674
^ ^a ^b ^c Parekh, A. K.; Gallager, R. G. (1993). “A generalized processor sharing approach to flow control in integrated services networks: The single-node case”. IEEE/ACM Transactions on Networking 1 (3): 344. doi:10.1109/90.234856.
^ Stiliadis, D.; Varma, A. (1998). “Latency-rate servers: A general model for analysis of traffic scheduling algorithms”. IEEE/ACM Transactions on Networking 6 (5): 611. doi:10.1109/90.731196.
^ Bennett, J. C. R.; Hui Zhang (1996). “WF/sup 2/Q: Worst-case fair weighted fair queueing”. Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. 1. pp. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4
^ Demers, A.; Keshav, S.; Shenker, S. (1989). “Analysis and simulation of a fair queueing algorithm”. ACM SIGCOMM Computer Communication Review 19 (4): 1. doi:10.1145/75247.75248.

[1] Wang, Zheng. (2001). Internet QoS : architectures and mechanisms for quality of service. San Francisco: Morgan Kaufmann. ISBN 978-1-55860-608-1. OCLC 162595674

[GPS-2] Parekh, A. K.; Gallager, R. G. (1993). “A generalized processor sharing approach to flow control in integrated services networks: The single-node case”. IEEE/ACM Transactions on Networking 1 (3): 344. doi:10.1109/90.234856.

[3] Stiliadis, D.; Varma, A. (1998). “Latency-rate servers: A general model for analysis of traffic scheduling algorithms”. IEEE/ACM Transactions on Networking 6 (5): 611. doi:10.1109/90.731196.

[WF2Q-4] Bennett, J. C. R.; Hui Zhang (1996). “WF/sup 2/Q: Worst-case fair weighted fair queueing”. Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. 1. pp. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4

[FQ-5] Demers, A.; Keshav, S.; Shenker, S. (1989). “Analysis and simulation of a fair queueing algorithm”. ACM SIGCOMM Computer Communication Review 19 (4): 1. doi:10.1145/75247.75248.

[1]

[2]

[3]

[4]

[5]

パラメータ化と公平性

アルゴリズム

GPS近似としてのWFQ

歴史

関連項目

参考文献