アクティブキュー管理の系譜：RED から PIE まで

テールドロップとグローバル同期

最も素朴なキュー管理はテールドロップです。バッファが満杯になるまで何もせず、溢れた到着パケットだけを末尾で捨てます。一見合理的ですが、二つの病理を抱えます。

第一はロックアウトです。少数のフローがバッファを占有すると、後発フローが入り込む隙がなくなり、不公平が固定化します。第二が本質的に厄介な**グローバル同期（global synchronization）**です。バッファが満杯になる瞬間、複数フローのパケットがまとめて落ちます。落とされた各 TCP は損失を輻輳シグナルとして cwnd を半減させ（AIMD と輻輳制御の数理 参照）、ほぼ同じタイミングで一斉に減速します。すると一気にキューが空き、各フローが揃って加法増加を始め、再び同時に満杯へ向かう。送信レートの総和がノコギリ波のように脈動し、谷ではリンクが遊び、山では遅延が肥大します。位相が揃っているため、本来は互いに打ち消し合うはずの揺らぎが増幅されてしまうのです。

RED：確率的早期廃棄という発明

RED（Random Early Detection, 1993）の核心は二つあります。早期（early）＝満杯を待たず平均キュー長がしきい値を超えた段階でシグナルを返す。確率的（random）＝落とすパケットを確率で散らし、特定フローへの集中と同期を防ぐ。

RED は瞬間キュー長ではなく**指数移動平均（EWMA）**でキュー長 avg を平滑化します。バーストで瞬間的に深くなっても、平滑値が min_th（最小しきい値）未満なら何もしません。avg が min_th と max_th の間にあるとき、超過の度合いに比例してドロップ確率を 0 から max_p まで線形に上げ、その確率で到着パケットを廃棄します。max_th を超えたら確率 1、つまり強制ドロップに切り替えます。

# RED エンキュー時の判定（要点）
avg = (1 - w) * avg + w * queue_len      # EWMA で平滑化
if avg < min_th:
    enqueue(packet)                       # 健全。何もしない
elif avg < max_th:
    pb = max_p * (avg - min_th) / (max_th - min_th)   # 線形に上昇
    pa = pb / (1 - count * pb)             # 連続非ドロップ数で補正し均一化
    if random() < pa:
        drop(packet); count = 0
    else:
        enqueue(packet); count += 1
else:
    drop(packet)                           # max_th 超過は強制ドロップ

確率を count（前回ドロップからの非ドロップ数）で補正するのは、ドロップ間隔を時間的に均一化し、特定フローが連続して被弾するのを防ぐためです。フローごとのドロップ期待値がそのフローの占有帯域に比例するので、帯域を多く食うフローほど多く落ち、近似的な公平性が生まれます。確率で散らすことでグローバル同期の位相揃いも崩れ、ノコギリ波が均されます。

ECN マーキング：落とさずに伝える

RED が用意したもう一つの拡張が ECN（明示的輻輳通知）との連携です。RED の「早期に確率的にシグナルを返す」という枠組みは、シグナルの手段が廃棄である必然性を持ちません。対応フローには、落とす代わりに IP ヘッダの CE（Congestion Experienced）ビットを立ててマークすれば、同じ早期シグナルを再送遅延ゼロで届けられます。送信側はマークを損失と同等に扱い減速します。

これは大きな前進でした。テールドロップでは「シグナル＝損失」が不可分で、輻輳を伝えるたびに必ず再送が発生していました。ECN はシグナルと損失を分離し、AQM が「捨てるか、合図するか」を選べるようにします。ただし RFC 3168 の古典 ECN はマークを損失と等価に扱う設計で、1 マーク＝半減と減速が荒く、キューを 1ms 級まで浅くは保てません。この限界を、CE を**マーク率（確率的シグナル）**として再解釈し DualQ でフローを分離して乗り越えたのが L4S です（ECN と L4S 参照）。AQM の系譜では、ECN はシグナル手段の自由度を開いた節目に当たります。

RED の限界と「遅延を直接見る」転回

RED 以降の二世代は、設計目標をキュー長からキュー遅延へ移します。発想は「困るのはキューが長いことではなく、掃けない遅延が居座ること」であり、しかも遅延は時間の量なのでリンク速度に依存しません。この系統の代表が、デキュー時の滞留時間を直接測る CoDel（CoDel と FQ-CoDel 参照）と、制御理論でアプローチする PIE です。

PIE：比例積分制御による遅延制御

PIE（Proportional Integral controller Enhanced, RFC 8033）は、RED と同じくエンキュー時に確率 p で落とす枠組みを残しつつ、p の決め方を制御理論で刷新しました。制御目標は平均キュー長ではなくキュー遅延そのものです。

PIE は周期的（既定 15ms ごと）に現在のキュー遅延 cur_delay を推定し、目標遅延 target（既定 15ms）との誤差からドロップ確率を更新します。

# PIE のドロップ確率更新（周期 Tupdate ごと）
err = cur_delay - target
p  += alpha * err + beta * (cur_delay - old_delay)
#        └比例項(P): 今ずれているか    └積分/傾向項(I): 増えているか
old_delay = cur_delay

alpha は現在の遅延誤差に比例して p を動かす比例項（P）、beta は遅延の変化の向きを見る項で、定常偏差を消し増加トレンドを先取りする**積分的（I）**な役割を担います。遅延が目標より大きく、しかも増え続けているなら p を強めに上げ、目標へ近づき減少傾向なら緩める。これにより遅延を target 付近へ滑らかに収束させます。キュー遅延の推定は、現在のキュー長 Q をデキュー実測レート drain_rate で割る Q / drain_rate、すなわちリトルの法則的な近似で行います。

PIE が RED に対して優れる点は明確です。第一に、制御目標が時間（遅延）なのでリンク速度に依存せず、RED の min_th/max_th のような速度依存の手調整が要りません。第二に、PI 制御は定常偏差を残さないため、フロー数が変動しても目標遅延付近に居続けます。第三に、廃棄はエンキュー時に確率 p で行うため、デキュー経路（パケットを送り出す高速経路）の計算負荷が軽く、ハードウェア実装に向きます。実際 PIE は DOCSIS ケーブルモデムの低遅延規格に採用されました。

系譜の総括と設計判断

四世代を貫く軸は二つです。一つはシグナルを返すタイミングで、満杯（テールドロップ）→ 平均キュー長のしきい値（RED）→ 遅延の継続超過や遅延誤差（CoDel/PIE）と、より早く・より遅延に直結した点へ移りました。もう一つはシグナルの手段で、損失一択から、ECN による損失なしマークへと自由度が広がりました。

注意すべきは、これは「新しい方式が常に正解」という単純な置換ではないことです。RED 系の WRED は DiffServ の優先制御と組み合わせる用途で今も使われ、CoDel は滞留時間の直接計測ゆえデキュー時計算が要り、PIE はエンキュー時廃棄ゆえハードウェア親和性が高い、と適材適所があります。