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

重み付き公平キューイング、Weighted Fair Queueing （ WFQ ）は、帯域幅の割り当てと遅延範囲をサポートするスケジューリングアルゴリズムである。元のWFQが10年以上前に提案されて以来、複雑さと正確さの間のさまざまなトレードオフで多くのさまざまなバリエーションが開発されてきた。WFQは、QoSをサポートするためにルーターに広く実装されている。最初にWFQの主要なプロパティを確認してから、高速実装用に設計されたいくつかのバリアントについて説明する。 
WFQは、一般化されたプロセッサ共有（GPS）ポリシーのパケットベースの実装であり、フェアキューイング（FQ）の自然な拡張である。FQはリンクの容量を等しいサブパートで共有するが、WFQでは、スケジューラが各フローに対して、容量のどの割合を与えるかを指定できる。 
重み付けされた均等化キューイングは、「到着パターンに関係なく、1つのパケット送信時間内に」一般化されたプロセッサ共有を概算するため、パケットごとのGPS（PGPSまたはP-GPS）とも呼ばれる。 
パラメータ化と公平性.
他のGPSに似たスケジューリングアルゴリズムと同様に、重みの選択はネットワーク管理者に任されている。「フェア」とは何かの一意の定義はない（ 参照） さらなる議論のための ）。 
WFQの重みを動的に調整することにより、WFQを利用してサービス品質を制御し、たとえば保証されたデータレートを実現できる。 
重みを次のように設定することで、比例して公平な動作を実現できる。formula_1 、ここでformula_2はデータフローformula_3のデータビットあたりのコスト。たとえば、CDMAスペクトラム拡散セルラーネットワークでは、コストは必要なエネルギー（干渉レベル）である可能性があり、動的チャネル割り当てシステムでは、コストは、同じ周波数チャネルを使用できない近くの基地局サイトの数である可能性がある。同一チャネル干渉を回避するためのビュー。 
アルゴリズム.
WFQでは、 フローを処理するスケジューラが1つの重みで構成される。 formula_4フローごとに。 次に、数の流れformula_3の平均データレートを達成するformula_6 、ここでformula_7はリンク速度である。すべての重みが等しいWFQスケジューラはFQスケジューラである。 
すべてのフェアキュースケジューラと同様に、各フローは他のフローから保護されており、データフローがリーキーバケットに制約されている場合は、エンドツーエンドの遅延範囲が保証されることが証明できる。 
WFQのアルゴリズムはFQのアルゴリズムと非常によく似ている。各パケットについて、仮想の理論上の出発日が計算され、スケジューラが完全なGPSスケジューラであった場合の出発日として定義される。次に、出力リンクがアイドル状態になるたびに、日付が最も小さいパケットが送信用に選択される。 
仮想出発時間の計算を次のように置き換えることにより、FQの1つから疑似コードを簡単に取得できる。 
 packet.virFinish = virStart + packet.size / Ri 
とformula_8 。 
GPS近似としてのWFQ.
WFQは、PGPSという名前で「GPSの優れた近似値」として設計されており、「到着パターンに関係なく、1パケットの送信時間内に」GPSを近似することが証明されている。 
WFQの実装はフェアキューイングに似ているため、 "O（log（n））の"複雑さは同じである。ここで、 "n"はフローの数である。 この複雑さは、パケットが送信されるたびに仮想終了時間が最も短いキューを選択する必要があるために生じる。 
WFQの後、GPSの他のいくつかの実装が定義されている。 
歴史.
FQへの可能な拡張として、 最後に記載されている任意の方法で帯域幅を共有するためのパラメーターの導入。"加重"という用語が最初に表示される。