トークンバケットとリーキーバケット：レート制御の数理

レート制御が分離すべき2つの量

レート制御の核心は、「長期の平均レート」と「短期のバースト許容量」という独立した2つの量を別々に扱うことです。秒間100パケットに制限したいとき、それは「常に等間隔で100個」なのか「平均100個だが瞬間的に300個までは許す」のか。前者は出力の平滑さを、後者は突発トラフィックへの寛容さを重視します。トークンバケットとリーキーバケットは、この2量をどう束ねるかが正反対の2つのモデルです。

両者を理解する鍵は、レートの制約を「カウンタとしきい値」に翻訳することです。固定窓のカウンタ方式（1秒ごとにカウンタを0に戻す）は実装が単純ですが、窓の境界で問題が出ます。窓の末尾と次窓の先頭に集中すると、ごく短時間に制限の2倍が通ってしまう（境界バースト）。バケットモデルは時間を窓で区切らず、連続時間で「いままで何を許したか」を1つの状態量に畳み込むため、この欠陥がありません。

トークンバケット：平均とバーストの分離

トークンバケットは、容量 b のバケットに毎秒 r 個の割合でトークンを補充し続けます。パケットを送る（または1バイト送る）たびに、その分のトークンを消費します。トークンが足りなければ、そのパケットは適合外（non-conformant）です。状態量はただ一つ、現在のトークン残量だけです。

• 補充レート r: トークンが貯まる速さ。これが長期の平均レートを決める。バケットが空でも r ずつは必ず流せる。
• バケット容量 b: 貯められるトークンの上限。これが最大バーストを決める。長く無送信だった後は最大 b 分を一気に出せる。

なぜこの2つで平均とバーストが分離されるのか。式で見ると明快です。任意の時間区間 [t1, t2]（長さ T = t2 - t1）に通せるトラフィック量 A(T) の上限は、

A(T) ≤ r * T + b

となります。これは**到着曲線（arrival curve）**と呼ばれ、ネットワーク・カルキュラスの基本式です。読み方は「どの長さ T の窓を取っても、流せる総量は『平均ぶん r*T』に『バースト一括ぶん b』を足した値を超えない」。T が大きいほど右辺は r*T が支配的になり、長期平均は r に漸近します。逆に T が小さい瞬間では定数項 b が効き、短時間のバーストを許します。r と b を独立に選べることが、トークンバケットが「平均は抑えつつ突発は通す」を実現できる理由です。

# トークンバケット（到着時に判定）
elapsed = now - last
tokens  = min(b, tokens + r * elapsed)   # 経過分を補充、上限は b
last    = now
if tokens >= size:                       # size = パケット長など
    tokens -= size
    送出（conformant）
else:
    超過扱い（drop / mark / queue）

リーキーバケット：出力の平滑化

リーキーバケットは、底に小さな穴の空いたバケツです。到着したパケットをバケツに入れ、底から一定レート r で漏れ出させる（送出する）。バケツが満杯ならあふれた分は捨てます。トークンバケットがトークンを貯めるのに対し、リーキーバケットはパケットそのもの（またはその仕事量）を貯める点が決定的に違います。

この差が出力特性を変えます。リーキーバケットの出力は、入力がどれほどバースト的でも常に最大 r に均されます。穴の太さが出力レートを物理的に決めるため、出力は完全に平滑化されます。一方トークンバケットは、バケットにトークンが溜まっていれば一気に b 分を放出でき、出力はバースト的になり得ます。

両者はしばしば「双対（dual）」と説明されます。リーキーバケットの動作は、出力を一定レートに保つトークンバケット（容量を小さく取り、必ずキューで遅らせる構成）と等価な制約を与えます。実装の世界では、出力を平滑化したいシェーパーはリーキーバケット的に振る舞い、適合判定だけを高速に行いたいポリサーはトークンバケット的に振る舞う、という棲み分けが定着しています。

シェーピングとポリシング：超過分の扱いが正反対

同じバケット式を使っても、適合外パケットをどう扱うかで2つの運用に分かれます。ここが実務で最も混同されるポイントです。

• シェーピング（shaping）: 超過分をキューに貯めて遅らせ、後でトークンが回復してから送る。出力を契約レートへ整形する。バッファを使うため遅延とジッタが増えるが、ロスは抑えられる。
• ポリシング（policing）: 超過分を**即座にドロップ（または DSCP を下げてマーク）**する。キューを持たないためメモリと遅延のコストが小さいが、適合外は捨てられる。

2レート3カラー：srTCM と trTCM

実運用では1つのレートでは足りず、「保証レートまでは緑、超過バーストは黄、それも超えたら赤」という3段階の色分けが標準です。RFC 2697 の srTCM（Single Rate Three Color Marker） は、committed rate CIR で補充される2つのバケット CBS（committed burst）と EBS（excess burst）を直列に使います。CBS に収まれば緑、あふれて EBS に収まれば黄、両方あふれれば赤。

RFC 2698 の trTCM（Two Rate Three Color Marker） は2つの補充レート CIR と PIR（peak）を使い、PIR 超過を赤、CIR 超過かつ PIR 内を黄とします。srTCM が「バーストの大きさ」で色を分けるのに対し、trTCM は「瞬間レートの高さ」で色を分けるのが本質的な違いです。色（緑／黄／赤）は後段の AQM やドロップ優先度に渡され、輻輳時にどの色から落とすかを決めます。緑を最優先で守り、赤から捨てる設計が一般的です（QoS の優先制御 とつながります）。

# srTCM（Color-Blind モード）の判定要点
refill(Tc, CBS, CIR); refill(Te, EBS, CIR)   # Te は Tc あふれ分を受ける
if size <= Tc:  Tc -= size; color = green
elif size <= Te: Te -= size; color = yellow
else:            color = red                  # トークン消費せず

なぜキューでは遅延が、ポリサーではロスが出るのか

最後に、バケットモデルがネットワークの遅延・ロスに直結する理由を押さえます。シェーパーは超過分をキューに積むので、適合内に整形されるまでの待ち時間がそのままキューイング遅延として乗ります。バースト b を r で吐き出すには最悪 b / r の時間がかかり、これが追加遅延の上界です。バケットを大きくすればロスは減りますが遅延は増える、というトレードオフはバッファ設計と同型で、過大バッファが遅延を肥大させる構図は バッファブロートと AQM と地続きです。

ポリサーはキューを持たないので遅延は増えませんが、適合外は捨てられるためロスが出ます。つまり「遅延を取るか、ロスを取るか」がシェーピングとポリシングの根本的な選択であり、その分岐点を決めるのが補充レート r とバケット容量 b という、たった2つのパラメータなのです。レート制御の設計とは、この2量を回線速度・RTT・許容遅延から逆算する作業にほかなりません（基礎関係は 帯域・レイテンシ・スループット を参照）。