公平な待ち行列

公平なキューイングは、一部のプロセスおよびネットワーク スケジューラで使用されるスケジューリング アルゴリズムのファミリです。このアルゴリズムは、限られたリソースを共有する場合に公平性を実現するように設計されています。たとえば、大きなパケットを持つフローや小さなジョブを生成するプロセスが、他のフローやプロセスよりも多くのスループットや CPU 時間を消費するのを防ぎます。

公平なキューイングは、一部の高度なネットワーク スイッチおよびルーターに実装されています。

フェアキューイングという用語は、1985年にジョン・ネーグルが、不正な動作をするホストによるネットワークの混乱を減らすために、ローカルエリアネットワークとインターネット間のゲートウェイでラウンドロビンスケジューリングを提案したときに造られました。^{[1] [2] [3]}

バイト重み付けバージョンは、1989年にアラン・デマーズ、スリニヴァサン・ケシャフ、スコット・シェンカーによって提案され、以前のナグル公平キューイングアルゴリズムに基づいていました。^{[4] [5]}バイト重み付け公平キューイングアルゴリズムは、各パケットの理論的な出発日を計算することで、ビットごとの多重化を模倣することを目的としています。

この概念は、重み付け公平キューイングや、より一般的なトラフィックシェーピングの概念へとさらに発展しました。トラフィック シェーピングでは、キューイングの優先順位が動的に制御され、望ましいフローのサービス品質目標を達成したり、一部のフローを加速したりします。

公平なキューイングでは、パケットフローごとに1つのキューを使用し、各フローが「リソースの均等な割合を取得」できるように順番に処理します。^{[1] [2]}

従来の先入れ先出し(FIFO) または優先キューイングと比較した利点は、大きなパケットまたは多数のデータ パケットで構成される高データ レート フローが、リンク容量の公平な割り当てを超えて占有できないことです。

公平なキューイングは、バッファからパケットを転送するルータ、スイッチ、統計マルチプレクサで使用されます。バッファはキューイング システムとして機能し、データ パケットは送信されるまで一時的に保存されます。

リンク データ レートがRの場合、任意の時点でN 個のアクティブ データ フロー (キューが空でないフロー) がそれぞれ平均データ レートR/Nで処理されます。パケットは順番に配信されるため、短時間でデータ レートはこの値付近で変動する場合があります。

ネットワークスケジューリングの文脈では、公平性には複数の定義があります。Nagel の論文では、パケットのラウンドロビンスケジューリングが使用されています^[2]。これはパケット数に関しては公平ですが、パケットのサイズが変化するときの帯域幅の使用に関しては公平ではありません。公平性の尺度には、最大最小公平性、最悪ケース公平性、^[6]、公平性指数など、いくつかの正式な概念が定義されています。^[7]

最初のアイデアでは、各フローに同じレートが与えられます。自然な拡張では、各フローに割り当てられる帯域幅の部分をユーザーが指定できるようにすることで、重み付け公平なキューイングと一般化されたプロセッサ共有が可能になります。

このアルゴリズムは、競合するフロー間でリンク リソースをビット単位のラウンドロビン方式で共有する公平性をエミュレートしようとします。ただし、パケット ベースのフローは、パケット単位で順番に送信する必要があります。バイト重み付け公平キューイング アルゴリズムは、各パケットの終了時間をビット単位のラウンドロビン方式で送信できるかのようにモデル化することで、パケットの送信順序を選択します。このモデル化に従って終了時間が最も早いパケットが、次に送信用に選択されます。

アルゴリズムの複雑さはO(log(n))です。ここで、nはキュー/フローの数です。

実際の終了時間のモデル化は実行可能ですが、計算量が多くなります。パケットが送信用に選択されるたび、および新しいパケットがキューに到着するたびに、モデルを大幅に再計算する必要があります。

計算負荷を軽減するために、仮想時間の概念が導入されました。各パケットの終了時間は、この単調に増加する代替仮想時間スケールで計算されます。仮想時間は、パケットが送信を完了する時間を正確にモデル化しませんが、フル機能モデルの目的を満たすために送信が発生する必要がある順序を正確にモデル化します。仮想時間を使用すると、以前にキューに入れられたパケットの終了時間を再計算する必要がありません。絶対的な意味での既存パケットの終了時間は、新しい到着によって影響を受ける可能性がありますが、仮想タイムラインの終了時間は変更されません。仮想タイムラインは、新しい送信に対応するために実時間に対して歪みます。

新しくキューに入れられたパケットの仮想終了時間は、仮想開始時間とパケットのサイズの合計で決まります。仮想開始時間は、同じキューの以前の仮想終了時間と現在の瞬間との間の最大値です。

すべての候補パケット（つまり、すべての空でないフロー キューの先頭にあるパケット）の仮想終了時間が計算され、公平なキューイングによって仮想終了時間を比較して最小のものが選択されます。仮想終了時間が最小のパケットが送信されます。

関数receive ()はパケットを受信するたびに実行され、関数send ()は送信するパケットを選択する必要があるとき、つまりリンクがアイドル状態でキューが空でないときに実行されます。この疑似コードでは、現在の仮想時間を返す関数now ()と、パケットがエンキューされるキューを選択する関数chooseQueue ()があることを前提としています。

selectQueue ()関数は、 仮想終了時間が最小のキューを選択します。読みやすさを考慮して、ここで示す擬似コードでは線形検索を行っています。ただし、ソートされたリストの維持は対数時間で実装でき、複雑さはO(log(n))になりますが、コードはより複雑になります。