GPS近似としてのWFQ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/02/23 02:42 UTC 版)
「重み付き公平キューイング」の記事における「GPS近似としてのWFQ」の解説
WFQは、PGPSという名前で「GPSの優れた近似値」として設計されており、「到着パターンに関係なく、1パケットの送信時間内に」GPSを近似することが証明されている。 WFQの実装はフェアキューイングに似ているため、 O(log(n))の複雑さは同じである。ここで、 nはフローの数である。 この複雑さは、パケットが送信されるたびに仮想終了時間が最も短いキューを選択する必要があるために生じる。 WFQの後、GPSの他のいくつかの実装が定義されている。 WFQが理想的なGPSポリシーに対してせいぜい「1パケット」遅れたとしても、勝手に進む可能性がある。ワーストケースフェアウェイトフェアキューイング (WF2Q)は、各パケットに仮想サービスの開始を追加することで修正し、仮想サービスの開始が現在の時間以上の場合にのみパケットを選択する。 最小限の仮想終了時間でキューを選択することは、ワイヤスピードで実装するのが難しい場合がある。次に、 不足ラウンドロビンのように、複雑さの少ないGPSの他の近似が定義された。
※この「GPS近似としてのWFQ」の解説は、「重み付き公平キューイング」の解説の一部です。
「GPS近似としてのWFQ」を含む「重み付き公平キューイング」の記事については、「重み付き公平キューイング」の概要を参照ください。
- GPS近似としてのWFQのページへのリンク