Loading article…
フェアキューイングは、一部のプロセススケジューラやネットワークスケジューラで使用されるスケジューリングアルゴリズムの一種です。このアルゴリズムは、限られたリソースが共有される場合に公平性を実現するように設計されており、例えば、大きなパケットを含むフローや小さなジョブを生成するプロセスが、他のフローやプロセスよりも多くのスループットやCPU時間を消費することを防ぎます。
公平なキューイングは、一部の高度なネットワークスイッチやルーターに実装されています。
フェアキューイングという用語は、1985 年にジョン・ネーグルが、ローカルエリアネットワークとインターネット間のゲートウェイでラウンドロビンスケジューリングを提案し、悪質なホストによるネットワークの中断を減らすために考案したものです。[ 1 ] [ 2 ] [ 3 ]
バイト重み付けバージョンは、1989 年に Alan Demers、Srinivasan Keshav、Scott Shenkerによって提案され、以前の Nagle の公平キューイングアルゴリズムに基づいています。[ 4 ] [ 5 ]バイト重み付け公平キューイングアルゴリズムは、各パケットの理論上の出発日を計算することによって、ビットごとの多重化を模倣することを目的としています。
この概念はさらに発展し、重み付き公平キューイング、そしてより一般的なトラフィックシェーピングという概念へと発展しました。トラフィックシェーピングでは、キューイングの優先順位を動的に制御することで、望ましいフロー品質のサービス目標を達成したり、特定のフローを加速させたりします。
フェアキューイングはパケットフローごとに1つのキューを使用し、それらをローテーションで処理することで、各フローが「リソースの均等な割合を取得」できるようにします。[ 1 ] [ 2 ]
従来の先入れ先出し（FIFO）方式や優先度キューイング方式と比較した場合の利点は、大きなパケットや多数のデータパケットで構成される高データレートの流れが、リンク容量の適正な割り当て量を超えて消費することがない点です。
フェアキューイングは、バッファからパケットを転送するルーター、スイッチ、統計的多重化装置で使用されます。バッファはキューイングシステムとして機能し、データパケットは送信されるまで一時的にそこに格納されます。
リンクデータレートがRの場合、任意の時点でN個のアクティブなデータフロー（キューが空でないフロー）は、それぞれ平均データレートR/Nで処理されます。パケットは順番に配信されるため、短い時間間隔ではデータレートはこの値付近で変動する可能性があります。
ネットワークスケジューリングの文脈では、公平性には複数の定義があります。Nagle の論文ではパケットのラウンドロビンスケジューリングを使用していますが、 [ 2 ]パケット数に関しては公平ですが、パケットのサイズが異なる場合の帯域幅の使用に関しては公平ではありません。公平性の尺度に関するいくつかの正式な概念が定義されており、最大最小公平性、最悪ケース公平性、[ 6 ]および公平性インデックス[ 7 ]などがあります。
当初の構想では、各フローに同じレートを割り当てます。自然な拡張として、ユーザーが各フローに割り当てる帯域幅の割合を指定できるようにすることで、重み付けされた公平なキューイングと汎用的なプロセッサ共有を実現できます。
このアルゴリズムは、競合するフロー間でリンクリソースをビット単位のラウンドロビン方式で共有する際の公平性を模倣しようと試みます。ただし、パケットベースのフローは、パケット単位で順番に送信する必要があります。バイト重み付け公平キューイングアルゴリズムは、各パケットの完了時間をビット単位のラウンドロビン方式で送信できるものとしてモデル化することで、パケットの送信順序を選択します。このモデル化に基づいて完了時間が最も早いパケットが、次に送信されるパケットとして選択されます。
このアルゴリズムの計算量はO(log(n))であり、nはキュー/フローの数である。
実際の処理完了時間をモデル化することは可能ではあるものの、計算負荷が非常に高い。パケットが送信対象として選択されるたび、また新しいパケットがキューに到着するたびに、モデルを大幅に再計算する必要がある。
計算負荷を軽減するために、仮想時間の概念が導入されます。各パケットの終了時刻は、この単調増加する仮想時間スケール上で計算されます。仮想時間はパケットの送信完了時刻を正確にモデル化するものではありませんが、フル機能モデルの目的を達成するために送信が行われるべき順序を正確にモデル化します。仮想時間を使用することで、以前にキューに入れられたパケットの終了時刻を再計算する必要がなくなります。既存のパケットの終了時刻は、絶対値で見ると新しいパケットの到着によって影響を受ける可能性がありますが、仮想時間軸上の終了時刻は変わりません。仮想時間軸は、新しい送信に対応するために、実時間に対して歪みます。
新たにキューに追加されたパケットの仮想終了時刻は、仮想開始時刻とパケットサイズの合計によって決まります。仮想開始時刻は、同じキューの前回の仮想終了時刻と現在の時刻のうち、大きい方の値です。
すべての候補パケット（つまり、空でないすべてのフローキューの先頭にあるパケット）の仮想完了時間が計算されると、フェアキューイングはそれらの仮想完了時間を比較し、最小値を選択します。そして、仮想完了時間が最小のパケットが送信されます。
関数receive () はパケットを受信するたびに実行され、send () は送信するパケットを選択する必要があるとき、つまりリンクがアイドル状態でキューが空でないときに実行されます。この擬似コードでは、現在の仮想時刻を返す関数now () と、パケットがキューに追加されるキューを選択する関数chooseQueue () が存在することを前提としています。
関数 selectQueue () は、仮想終了時間が最小のキューを選択します。読みやすさを考慮して、ここで示す擬似コードでは線形探索を行っています。しかし、ソート済みリストの維持は対数時間で実装でき、O(log(n)) の計算量になりますが、コードはより複雑になります。
Nagle は、ゲートウェイが送信ホストごとに個別のキューを維持する「フェアキューイング」方式を発表しました。この方式では、病的な実装を持つホストがゲートウェイのリソースの公平な割り当てを超えて占有することはできません。これは活発で興味深い議論を引き起こしました。