パケットスケジューリング：WFQ・DRR・HTB の原理

公平キューイングが解く問題

リンクが混雑したとき、複数のフロー（あるいはトラフィッククラス）にどんな比率で帯域を割り当てるか。これがパケットスケジューラの仕事です。素朴な FIFO（テールドロップ）では、攻撃的に送るフローほど多くのキューを占有し、帯域を奪います。QoS（通信品質の制御） の「スケジューリング」段にあたる部分を、原理から厳密に詰めるのがこの記事です。

理想は GPS（Generalized Processor Sharing） という流体モデルです。GPS は各フロー i に重み w_i を与え、バックログのある（送るものがある）フローの間で、リンク容量を重み比で無限に細かく分配します。あるフローのバックログが切れれば、その帯域は残りのフローへ重み比で即座に再配分される。問題は、現実のパケットは分割できず、1 個ずつ逐次に送るしかない点です。GPS をパケット単位でどう近似するかが、WFQ・DRR・HTB の分かれ道になります。

WFQ — 仮想終了時刻による近似

WFQ（Weighted Fair Queueing）の発想は、「GPS の世界でこのパケットがいつ送り終わるか」を計算し、その仮想終了時刻（virtual finish time）が早い順に実際のパケットを送る、というものです。鍵は実時間ではなく仮想時間 V(t) を使うことです。

仮想時間はリンクの混雑度に応じて進む速さが変わる時計です。バックログ中のフローの重み総和を Σw とすると、V(t) は実時間あたり C / Σw の速さで進みます（C はリンク容量）。アクティブなフローが少ないほど V は速く進む、という性質がポイントです。各パケット k（フロー i、長さ L）に対し、開始タグ S と終了タグ F を次のように割り当てます。

# パケット到着時のタグ付け（フロー i、長さ L）
S = max(V(now), F_prev_i)     # 直前パケットの終了タグか、現在の仮想時刻の遅い方
F = S + L / w_i               # 仮想時間での所要量。重みが大きいほど F は小さく進む
# 送出は F が最小のパケットから

L / w_i が核心です。重み w_i が大きいフローほど、同じ長さでも F の増分が小さい。つまり仮想時間軸での「進みが遅く」見え、より頻繁に最小 F として選ばれ、結果として帯域を多く得ます。max をとるのは、フローがアイドルから復帰したとき、過去に溜めた「貸し」で帯域を独占させないためです。WFQ はこのタグ順送出により、GPS との遅延差が最大 1 パケット長に収まることが保証されます（厳密な公平性）。

WFQ の弱点は計算量です。V(t) の更新はアクティブフロー数に依存し、各送出で最小 F を選ぶのに優先度キュー（ソート）が要ります。1 パケットあたり最悪 O(log N)、V の正確な追従まで含めると実装が重く、高速リンクのハードウェアでは扱いにくい。ここで O(1) 近似の DRR が登場します。

DRR — Deficit Round Robin の O(1) 近似

DRR（Deficit Round Robin）は仮想時刻計算を完全に捨て、ラウンドロビン＋積み立てだけで重み付き公平を近似します。各キュー i に二つの値を持たせます。

• quantum_i（量子）: 1 巡で送ってよいバイト数の基準。重み比に比例させる（quantum_i = w_i × base）。
• deficit_i（赤字カウンタ）: 前の巡で「送りたかったのに送れなかった分」の繰り越し。

スケジューラはアクティブキューを順に回り、各キューで deficit に quantum を足し、先頭パケットの長さが deficit 以下なら送って deficit から引く、を繰り返します。先頭パケットが大きすぎて送れなければ、deficit を残したまま次のキューへ回ります。残った deficit は次の巡に繰り越されるので、いつか必ず送れます。

# DRR の 1 巡（アクティブキューのリストを順に処理）
for each active queue i:
    deficit_i += quantum_i
    while queue_i not empty and head(queue_i).len <= deficit_i:
        pkt = dequeue(queue_i)
        deficit_i -= pkt.len
        send(pkt)
    if queue_i empty:
        deficit_i = 0          # 空になったら貸しをリセット（独占防止）

繰り越し（deficit）こそが公平性の源泉です。可変長パケットでも、各キューが 1 巡で実際に送れるバイト数は長期的に quantum_i へ収束し、配分比は quantum 比＝重み比に一致します。MTU 未満の端数は次巡へ持ち越されるだけで失われません。

計算量が決定的な利点です。quantum を最大パケット長（MTU）以上に選べば、各キューは 1 巡で必ず最低 1 パケットを送れるため、キューを空回りすることがありません。すると 1 パケットの送出にかかる処理は定数回に収まり、1 パケットあたり O(1) が成立します。ソートも仮想時刻更新も不要なので、高速リンクや Ethernet スイッチの内部処理 のようなハードウェア実装に向きます。代償は遅延境界の緩さで、GPS との差は WFQ の「1 パケット長」より大きく、おおむね quantum のオーダーになります。実用上は十分小さく、Linux の FQ-CoDel はこの DRR をフロー分離に採用しています（バッファブロートと AQM 参照）。

HTB — 階層トークンバケットによる帯域配分

WFQ・DRR がフロー間の公平を扱うのに対し、HTB（Hierarchical Token Bucket）が解くのは別の問題です。「各クラスに最低帯域を保証しつつ、誰かが余らせたら他クラスがそれを借りて使い、ただし上限は超えない」という階層的な配分です。Linux tc の代表的な qdisc で、トラフィックを木構造に組みます。

各クラスは二つのレートを持ちます。rate（保証帯域）と ceil（上限帯域）です。実装はトークンバケットで、rate ぶんのトークンが定期的に補充され、パケット送出でトークンを消費します。HTB の核心は borrow（借用） です。あるクラスが自分の rate を使い切っても ceil に達していなければ、親クラスの余剰トークンを借りて送り続けられます。親に余剰がなければさらにその親へ、と木を上へたどります。

# HTB クラスの送出可否（概念）
自クラスのトークンあり          → green : 自分の rate 内。送る
自クラス枯渇・親に余剰あり       → yellow: borrow して送る（ceil まで）
ceil 到達 / 親もすべて枯渇       → red   : 送れない。整形（待たせる）

この三状態（green/yellow/red）により、HTB は次を同時に満たします。第一に、各クラスは少なくとも自分の rate を保証される(親に貸す前に自分が使えるため)。第二に、回線に余剰があれば ceil まで借りて伸びるので帯域を遊ばせない。第三に、ceil で上限が効くので特定クラスの暴走を防げる。葉クラスの内側ではさらに DRR などで個々のフローを公平化でき、「クラス間は階層保証、クラス内はフロー公平」という二層構成が組めます。

三者の役割分担

同じ「スケジューリング」でも狙いが異なります。WFQ は厳密な公平性と最小遅延境界を、DRR はそれを O(1) で実用化する近似を、HTB は公平ではなく階層的な保証・上限・借用を担います。実務では HTB で帯域の大枠（VoIP に最低保証、バックアップに上限）を切り、その葉で FQ-CoDel／DRR によりフロー間の公平と低遅延を確保する、という組み合わせが定番です。背景の帯域と遅延の関係は 帯域・レイテンシ・スループット を、輻輳制御との役割分担は バッファブロートと AQM を参照してください。