QoS（6）優先制御 マーキング /キューイング/スケジューリングと輻輳回避

マーキング

クラス分類したパケットにキュー番号などのキュー識別コードを割り付ける。マーキングは装置内部処理のため、ユーザはあまり意識する必要はない。

キューイング

マーキングされた識別コードと一致するキューにパケットを格納する。キューイングも装置内部処理のため、ユーザはあまり意識する必要はない。

スケジューリング

優先制御とは、パケットに優先度を付け、優先度に応じて送信機会を変えることだ。優先度が高いパケットは他のパケットよりも先に送信したり送信機会を増やしたりする。パケットを送出したアプリケーションの遅延やジッタなどの品質を改善することが狙いだ。

受信パケットは、「クラス分類」「マーキング」を経て、クラスに応じたキューに格納される。キューから取り出す「スケジューリング」には様々な方法があり、ここで優先制御の方式が決まる（図1 参照）。

優先制御は2つの考え方に分かれる。一つは、優先度の高いキューにパ ケットがあれば必ず優先的に送信する方法で「絶対優先」とも呼ばれる方式だ。幾つかの呼び方があるが、PQ（Priority Queueing）やSPQ（Strict Priority Queueing）と呼ばれる。

もう一つは各キューを巡回し公平に送信する方法だ。キューごとに重み付けをする WRR（Weighted Round Robbin） が一般的で、例えばキューが３つあると「5:3:1」などの割合で重みを付け、順番に送信する。重みを付けない RR（Round Robbin） もあり、キューが3つの場合は「1:1:1」の割合で順番に送信する。送信量は1秒間に送信するビット数で設定し、制御方式は「トークンバケット制御」が一般的に使われる。

制御が全くない「Best Effort」を含め、優先制御の各方式を順次説明したい。ただし、表現を簡素化するため、送信量をビット数ではなく「固定長パケット数」としている。

FIFO（First Input First Output ：ファイフォ）

FIFO は、クラス分類／マーキング機能がなく優先度キューもない。全ての受信パケットは到着順に直接送信キューに格納され、送信キューから溢れたパケットは廃棄される。送信時は、送信キューの先頭から順次取り出すだけだ。パケットの優先度は、緑＞橙＞黒の順だが、優先度の高いパケットをフォワードできるとは限らない。まさに FIFO（先入先出）そのものだ（図2）。

SPQ（Strict Priority Queueing）

SPQ は、優先度ごとにクラス分類／マーキングを行い、それぞれの優先度キューに格納される。優先度キューから溢れたパケットは廃棄される。SPQ では、最も優先度の高いキューにパケットがある限り送信キューに取り込み続ける。最高優先度のキューが空になると次の優先度キューを全て取り込む。優先度の低いパケットは、送信キューに取り込まれず滞留し廃棄される可能性がある。優先度の高いパケットの遅延やジッタを押さえることができるが、優先度の低いパケットは廃棄の可能性が高くなる。SPQ を運用する場合は、優先度の高いパケット量を制限する必要がある。図3 の例では、最優先度の緑を全て取り出し、2番目の優先度橙をとりだす。緑も橙もすべて空になったところで、黒を取り出すことができる。

RR（Round Robbin）

RR は、優先度ごとにクラス分類／マーキングを行い、それぞれの優先度キューに格納する。優先度キューから溢れたパケットは廃棄される。ここまでは SPQ と同じだ。違いは、全てのキューを順次巡回し送信キューに取り込むところだ。公平性はあるが、優先度の高低が特にあるわけではない。遅延やジッタに厳しいパケットを守ることはできない。一見役に立たないように見えるが、優先度に大きな差がない複数キューに公平に帯域を与えるような場合は有効な手法だ。

図4 の例では、 緑→ 橙→ 黒の順で巡回している。3周目で緑は空になったため、次の橙が取り出される。

WRR（Weighted Round Robbin）

WRR は、優先度ごとにクラス分類／マーキングを行い、それぞれの優先度キューに格納する。優先度キューから溢れたパケットは廃棄される。ここまでは SPQ/RR と同じだ。RR との違いは、巡回時に各キューから取り出すデータ量に差があることだ。WRR はキューごとに重み付けをすることで、送信機会に差が生まれる。しかし、RR と同じように遅延やジッタに厳しいパケットを守ることはできない。図5 の例では、緑：橙：黒＝1：1：2 の比率で取り出し、巡回している。

輻輳回避

Store & Forward 方式のスイッチやルータは、パケットを一時的に格納するためにキューを持っている。しかし、キュー容量は有限なため、トラフィック集中や帯域超過でバッファが溢れ、パケット廃棄が起きる（図6）。幾つかの廃棄方法があるが、最も一般的な廃棄方法はテールドロップ（Tail Drop）だ。

パケット廃棄は致し方ないが、問題はパケット廃棄の副作用だ。TCP パケットが廃棄されると、数秒後に送信ノードはパケット廃棄を検出し再送を始める。受信ノードからの応答（ACK）が、一定時間受信できずタイムアウトするためだ。TCP の再送がトラフィック増を招き、新たな輻輳を引き起こす。

テールドロップ（Tail Drop）

テールドロップは、キューが一杯になると溢れたパケットは全て廃棄される。複数の TCP アプリケーションのパケットがほぼ同時に廃棄されることになる（図7）。数秒後に、複数の TCP アプリケーションの再送が始まり、トラフィックが急増する。もちろん、図8 の様に TCP の「スロースタート」機能で送信量を押さえて再送を始めるが、再送ノードの数が多いと深刻な影響が出る。テールドロップにより悪循環が始まり、パケット廃棄と再送を繰り返しネットワークは不安定になる。UDP は再送機能がないため、このような問題は起きない。

RED

テールドロップの欠点は、溢れたパケットをほぼ同時に廃棄することで、再送が一斉に始まることだ。ランダムにパケット廃棄が起きれば、再送もランダムに始まりトラフィック集中を避けることができる。RED はこの廃棄タイミングの離散化を目的に作られた。

RED は、キューの空き領域に応じてパケット廃棄確率を変えることで、集中的な廃棄を防ぎかつランダムな廃棄タイミングを作るようになっている。

キューの空き領域に余裕があれば廃棄確率は「0%」で、全てのパケットを受け入れる。空き領域が一定の割合を下回ると順次廃棄確率を上げ、空き領域がなくなると廃棄確率は「100%」になる。この状態になった後は、空き領域が増えいくらか余裕ができるまで、全廃棄の状態が続く。ヒステリシスを持たせた廃棄アルゴリズムになっている（図9）。

RED の意味は、ランダム早期検出（Random Early Detection）とランダム早期廃棄（Random Early Discard）の２つの説がある。かつては、「早期廃棄」だったような気がするが、最近は「早期検出」が主力のようだ。