sharin

Appearance

輻輳制御(AIMD) ​

実装: network/congestion/ / 実行: go test ./network/congestion/

帯域は共有資源だ。送り手が一斉に全力で送れば経路が詰まり、パケットが溢れ、再送でさらに詰まる。だが誰も空き帯域を知らない。そこでTCPは各接続が自分で探る。一度に送ってよい量を最初は倍々に増やして空きを探り、閾値からは1往復に1ずつ慎重に増やし、パケットが落ちたら詰まった合図とみなして半分に切る。この制御を実装し、増やしては半減する単純な規則が、中央の調整役なしに効率と公平を両立する仕組みを見る。

この章で作るもの ​

TCPは、失われたパケットを再送して信頼性のある通信を作った。だが「どれだけの速さで送るか」という問題が残っている。ネットワークの帯域は、多数の接続が共有する資源だ。もし各接続が思うままに全力で送れば、経路上のルータのバッファが溢れ、パケットが捨てられる。捨てられれば再送する。再送がさらに経路を詰まらせ、また捨てられる。この悪循環が輻輳崩壊(congestion collapse)で、1980 年代に実際にインターネットを何度も麻痺させた。

厄介なのは、誰も「今どれだけ空いているか」を知らないことだ。経路の途中のルータは送り手に空き容量を教えてくれない。そこで TCP は、各接続が自分で探ることにした。輻輳ウィンドウ(cwnd)という「一度に送ってよい量」を持ち、それを少しずつ増やして空きを試し、パケットが落ちたら「詰まった」合図とみなして減らす。増やし方と減らし方の設計が輻輳制御だ。この章では、スロースタートと AIMD による古典的な制御を実装し、それが中央の調整役なしに効率と公平を両立させる仕組みを見る。

cwnd
 │        損失→半減      損失→半減
 │        /|      /|      /
 │       / |     / |     /     容量ライン
 │──────/──┼────/──┼────/──────────────
 │  ╱     └   ╱    └   ╱  ← 輻輳回避(1ずつ加算増加)
 │ ╱ ← スロースタート(倍々)
 └────────────────────────────▶ 往復
cwnd(一度に送ってよい量)の推移。最初は倍々に増え、閾値(ssthresh)からは 1 ずつの増加に切り替わる。損失で半減し、また増やす。容量を探るのこぎり波

順に作る。

  1. スロースタートで手早く探る: cwnd=1 から倍々に増やし、空き帯域を素早く見つける。閾値(ssthresh)で切り替え
  2. 輻輳回避で慎重に探る: 閾値からは 1 往復に 1 だけ増やす(加算増加)。容量の近くをそっと押す
  3. 損失で半分に切る(AIMD): 詰まったら cwnd を半減(乗算減少)。これが効率と、接続間の公平をもたらす

① スロースタートと輻輳回避 ​

まず cwnd の増やし方を作る。始めは空きがどれだけあるか見当もつかないので、倍々に増やして素早く探る(スロースタート)。だが増やしすぎると一気に溢れるので、閾値 ssthresh に達したら、1 往復に 1 だけ増やす慎重な増やし方(輻輳回避)に切り替える:

go

// State は輻輳制御の局面。
type State int

const (
	SlowStart           State = iota // 指数的に増やして空きを素早く探る
	CongestionAvoidance              // 1 往復に 1 ずつ慎重に増やす
)

func (s State) String() string {
	if s == SlowStart {
		return "slow-start"
	}
	return "congestion-avoidance"
}

// Controller は 1 接続の輻輳ウィンドウを管理する。単位は MSS(最大セグメント長)。
type Controller struct {
	Cwnd     float64 // 輻輳ウィンドウ(一度に送ってよい量)
	Ssthresh float64 // スロースタートから輻輳回避へ移る閾値
	State    State
}

// New は cwnd=1 のスロースタートで始める。
func New(ssthresh float64) *Controller {
	if ssthresh < 1 {
		ssthresh = 1
	}
	return &Controller{Cwnd: 1, Ssthresh: ssthresh, State: SlowStart}
}

// OnRoundACKed は 1 往復ぶんの ACK が返ったときの増やし方。
//   - スロースタート: cwnd を倍にする(各パケットの ACK で +1 = 1 往復で倍)
//   - 輻輳回避: cwnd を 1 だけ増やす(加算増加)
func (c *Controller) OnRoundACKed() {
	if c.State == SlowStart {
		c.Cwnd *= 2
		if c.Cwnd >= c.Ssthresh {
			c.Cwnd = c.Ssthresh
			c.State = CongestionAvoidance
		}
	} else {
		c.Cwnd += 1 // 加算増加(additive increase)
	}
}

// OnLoss は重複 ACK による損失(fast retransmit)。ssthresh を今の半分にし、
// cwnd もそこまで落として輻輳回避を続ける(乗算減少)。
func (c *Controller) OnLoss() {
	c.Ssthresh = c.Cwnd / 2 // 乗算減少(multiplicative decrease)
	if c.Ssthresh < 1 {
		c.Ssthresh = 1
	}
	c.Cwnd = c.Ssthresh
	c.State = CongestionAvoidance
}

// OnTimeout はタイムアウト(より深刻な損失)。cwnd を 1 に戻し、スロースタートから
// やり直す。ssthresh は半分に。
func (c *Controller) OnTimeout() {
	c.Ssthresh = c.Cwnd / 2
	if c.Ssthresh < 1 {
		c.Ssthresh = 1
	}
	c.Cwnd = 1
	c.State = SlowStart
}

スロースタートは名前に反して、増え方はむしろ速い。cwnd の全パケットが ACK されるたびに、1 往復で cwnd が倍になる。1, 2, 4, 8… と指数的だ。空き帯域が大きいとき、これを線形に埋めていたら時間がかかりすぎる。だから最初は倍々で駆け上がる。ただし、いつまでも倍々では必ず溢れる。そこで閾値からは加算増加に落とす。損失が起きたときの反応が 2 通りある。重複 ACK による軽い損失(fast retransmit)なら、cwnd を半分にして輻輳回避を続ける。タイムアウトという重い損失なら、cwnd を 1 に戻してスロースタートからやり直す。テストで、倍々に増えて ssthresh で切り替わること、損失で半減すること、タイムアウトで 1 に戻ることを固定した。

② のこぎり波: 容量を探り続ける ​

この増減を経路上で繰り返すと何が起きるか。cwnd を増やしていくと、いつか経路の容量を超え、パケットが落ちる。すると cwnd は半分に切られる。また増やす。また超えて落ちる。また半減する。cwnd は容量の周りを、増やしては切られる、のこぎり波(sawtooth)を描き続ける:

go

// Simulate は容量 capacity の経路で rounds 往復ぶん送ったときの cwnd の推移を返す。
// cwnd が容量を超えると損失が起き(OnLoss)、半分に切られる。増やしては切られる
// のこぎり波(sawtooth)になり、cwnd が容量の周りを探り続ける。
func Simulate(ssthresh, capacity float64, rounds int) []float64 {
	c := New(ssthresh)
	history := make([]float64, 0, rounds)
	for i := 0; i < rounds; i++ {
		if c.Cwnd > capacity {
			c.OnLoss() // 経路が溢れた
		} else {
			c.OnRoundACKed()
		}
		history = append(history, c.Cwnd)
	}
	return history
}

こののこぎり波こそが輻輳制御の姿だ。cwnd は容量ちょうどに落ち着くのではなく、その少し上まで押しては半分に下がる、を繰り返す。一見無駄に見えるが、これには意味がある。ネットワークの空き容量は、他の接続の増減で刻々と変わる。固定値に落ち着いてしまうと、空きが増えても気づけない。常に少し押し続けることで、増えた空きをすぐ使え、詰まればすぐ引く。テストで、cwnd が増減を繰り返すのこぎり波になり、容量を大きく超え続けないことを固定した。損失を「悪いこと」でなく「容量を教えてくれる信号」として使うのが、この設計の賢さだ。

③ AIMD: なぜ公平になるのか ​

もう一つ、AIMD には見事な性質がある。複数の接続が 1 本の経路を分け合うとき、取り分が自然に等しくなる方へ収束する。中央で「君は 30%、君は 40%」と割り振る調整役はいないのに、だ:

go

// SimulateFairness は容量 capacity を 2 接続で分け合うときの各ウィンドウの推移を返す。
// 両者とも毎往復 1 ずつ増やし(加算増加)、合計が容量を超えたら両者とも半分に切る
// (乗算減少)。加算増加は差を保ち、乗算減少は差を半分にするので、取り分は
// 等しい方へ収束する。これが AIMD が公平をもたらす仕組み。
func SimulateFairness(capacity, a, b float64, rounds int) (histA, histB []float64) {
	histA = make([]float64, 0, rounds)
	histB = make([]float64, 0, rounds)
	for i := 0; i < rounds; i++ {
		a += 1 // 加算増加(両者同じだけ増える)
		b += 1
		if a+b > capacity {
			a /= 2 // 乗算減少(両者とも半分)
			b /= 2
		}
		histA = append(histA, a)
		histB = append(histB, b)
	}
	return histA, histB
}

仕組みは、増やし方と減らし方の非対称にある。加算増加(additive increase)は、全接続が同じだけ(1 ずつ)増える。だから接続間のウィンドウの差は変わらない。一方、乗算減少(multiplicative decrease)は、全接続が同じ割合(半分)で減る。片方が 30、片方が 10 なら、半減後は 15 と 5 で、差は 20 から 10 に縮む。増やすときは差を保ち、減らすときは差を縮める。これを繰り返すと、差は往復ごとに縮んでいき、取り分が等しい方へ収束する。テストで、30 対 2 という大きく偏った初期状態から始めても、200 往復後にはほぼ等しい取り分に収束することを固定した。加算増加・乗算減少という単純な規則が、公平という大域的な性質を生む。

動かす ​

下のデモは 2 つの見方を用意した。1 つは単一接続の cwnd が容量を探るのこぎり波。もう 1 つは 2 接続が同じ経路を分け合い、偏った初期状態から公平な取り分へ収束していく様子だ。

デモ輻輳制御(AIMD)容量を探る
のこぎり波(1接続)公平収束(2接続)
cwnd容量 32

cwnd はスロースタートで倍々に立ち上がり、輻輳回避では 1 ずつ増える。容量(点線)を超えると損失で半減し、また増やす。容量ちょうどに留まらず、その周りを探り続けるのこぎり波になる

輻輳ウィンドウ cwnd は「一度に送ってよい量」。誰も空き帯域を知らないので、各接続が増やしては 損失で減らして探る。スロースタートで手早く立ち上げ、輻輳回避で慎重に押し、損失で半減する(AIMD)。 加算増加は接続間の差を保ち、乗算減少は差を縮めるので、中央の調整役なしに取り分が公平へ収束する。

設計の観点 ​

  • 損失は信号: パケットロスを「容量に達した」合図として使う。だから輻輳制御は損失ベースと呼ばれる。無線のように損失が輻輳以外でも起きる経路では、これが誤作動する
  • AIMD が公平を生む: 加算増加・乗算減少の組み合わせが、公平点への収束を生む。加算増加・加算減少や乗算増加では収束しない。この非対称が本質
  • のこぎり波の代償: 常に押しては引くので、リンクを完全には使い切れず、遅延も上下する。これを嫌う新しい方式(BBR)は、損失でなく帯域と RTT を直接測る
  • バッファブロート: ルータのバッファが大きすぎると、cwnd が容量を超えてもすぐには損失が出ず、バッファに溜まって遅延だけが増える。損失ベースの弱点
  • 公平性の前提: AIMD の公平は「みなが同じ規則に従う」前提。規則を破って攻撃的に送る接続がいると、正直な接続が損をする

対照と実例 ​

方式合図特徴
Tahoe / Reno損失(重複 ACK・タイムアウト)古典的 AIMD。この章の対象
Cubic損失Linux の既定。増加を三次関数にして高速リンクに強い
BBR (Google)帯域 + RTT の推定損失に頼らず、バッファブロートを避ける
ECNルータの明示通知損失前に「混み始めた」を伝える拡張

裏どり:

  • Van Jacobson, Congestion Avoidance and Control (1988): 輻輳崩壊への対策としてスロースタートと AIMD を導入した原典
  • Chiu & Jain (1989): AIMD が効率と公平の点に収束することを解析で示した。公平性の理論的根拠
  • TCP Cubic (RFC 8312): 現代の Linux 既定。高帯域・高遅延リンク向けの増加関数
  • BBR (Google): 損失ベースを離れ、帯域と往復遅延を測る新世代。YouTube などで運用

簡略化したこと ​

  • TCP Reno 相当: 実物は Cubic や BBR など多様。ここは古典的 AIMD
  • 1 往復単位: 個々の ACK でなく往復ごとにまとめて増やす。RTT やパケット単位は抽象化
  • 損失は容量超過で判定: 実物は重複 ACK やタイムアウトで検知。ここは cwnd>容量を損失とみなす
  • 公平性は理想化: 両接続が同時に損失を見る前提。実際の同期はもっと不完全

参考資料 ​