待ち行列理論で見るネットワーク遅延（M/M/1）

なぜ待ち行列理論がネットワークに効くのか

ルータやスイッチ、ロードバランサ、サーバのどれも、本質は「到着したジョブを 1 つの処理装置で順にさばく窓口」です。パケットが来る速さ（到着率）が、装置がさばける速さ（処理率）に近づくほどキューが伸び、遅延が増えます。この関係を最小限の仮定で式にしたのが M/M/1 で、ネットワーク遅延の直感を数式で裏付けてくれます。

記号の意味をまず固定します。到着率を λ（ラムダ、1 秒あたり何パケット来るか）、サービス率を μ（ミュー、1 秒あたり何パケットさばけるか）とします。1 パケットの平均処理時間は 1/μ です。両者の比が利用率（使用率） ρ = λ / μ で、装置がどれだけ忙しいかを表します。

安定条件と平均量の閉じた式

M/M/1 が定常状態を持つ条件は ρ < 1、つまり λ が μ 未満であることです。到着が処理を上回ればキューは際限なく伸び、定常解は存在しません。

ρ が 1 未満なら、系内にちょうど n 個いる確率は P(n) = (1 − ρ) · ρ^n という幾何分布になります。ここから平均量が次のように閉じた形で出ます。

利用率              ρ = λ / μ
系内の平均パケット数  L  = ρ / (1 − ρ)
平均滞留時間（系内）  W  = 1 / (μ − λ)
平均待ち行列長（窓口除く） Lq = ρ^2 / (1 − ρ)
平均待ち時間（待ち行列のみ） Wq = ρ / (μ − λ)

W は窓口での処理時間 1/μ も含む「系に入ってから出るまで」の全所要時間で、ネットワークでいえばその装置 1 段の遅延に相当します。Wq はそこから自分の処理時間を引いた、純粋に列で待つ時間です。両者は W = Wq + 1/μ の関係にあります。

遅延が発散する非線形性

ここが M/M/1 の核心です。滞留時間を利用率で書き直すと、W = (1/μ) / (1 − ρ) となります。窓口が空いていれば遅延は最小値 1/μ（自分の処理時間だけ）ですが、ρ が 1 に近づくと 1/(1 − ρ) の係数が発散します。

具体的な倍率で見ると非線形性は明白です。

利用率を 50% から 80% に上げても遅延は 2 倍から 5 倍ですが、90% から 99% へのわずか 9 ポイントの上昇で 10 倍が 100 倍へ跳ねます。「回線やサーバを 100% 近くまで詰めて使う」のが危険なのはこのためです。平均では空きがあるように見えても、ポアソン到着のゆらぎが瞬間的にキューを積み上げ、ρ が高いほど積み上がったキューが掃ける前に次のバーストが来ます。容量計画で利用率に上限（たとえば 70〜80%）を設けるのは、この発散域に入る前で止めるための安全余裕です。

リトルの法則：分布に依存しない普遍則

上の L と W は別々に導いたように見えますが、両者は リトルの法則（Little's Law） で必然的に結ばれています。

L = λ · W
（系内の平均数 = 到着率 × 平均滞留時間）

この式の強さは、到着やサービスの分布をいっさい仮定しない点にあります。系が定常で「入った分だけ出ていく」状態なら、M/M/1 でも、複数窓口でも、サービス時間がどんな分布でも常に成り立ちます。実際、待ち行列だけに限った Lq = λ · Wq も同時に成り立ちます。M/M/1 の L = ρ/(1−ρ) と W = 1/(μ−λ) を掛け算で確かめると、λ · W = λ/(μ−λ) = ρ/(1−ρ) = L ときれいに一致します。

ネットワークでの使いどころは広く、3 つの量のうち 2 つが測れれば残り 1 つが出ます。

たとえば飛行中のデータ量がリンクの帯域遅延積です。L（窓に入れるべきバイト数）を λ（スループット）と W（RTT）から L = λ·W で求める発想は、TCP の送信ウィンドウ設計そのものです（TCPフロー制御とウィンドウ 参照）。同じ法則で、AQM がキュー遅延を「キュー長 ÷ 排出レート」で推定するのも W = L/λ の言い換えにすぎません。

モデルの限界と実務での扱い

M/M/1 は強力ですが、仮定が現実と食い違う場面を知っておく必要があります。

• 到着はポアソンとは限らない：実トラフィックはバースト性が強く自己相似的で、独立なポアソン過程より裾が重い。M/M/1 はしばしば楽観的な見積りになります。
• サービス時間は指数分布とは限らない：パケット長が固定に近いなら分散が小さく、より一般の M/G/1 が適切です。サービス時間の分散が大きいほど待ち時間は悪化します（ポラチェック=ヒンチンの公式）。
• バッファは有限：実機のキューは有限長で、溢れればパケットを落とします（M/M/1/K モデル）。深すぎるバッファはむしろ遅延を肥大させます（バッファブロートと AQM 参照）。

それでも M/M/1 が価値を失わないのは、定性的な振る舞いが正確だからです。「利用率を上げると遅延は線形でなく 1/(1−ρ) で跳ね、テールはさらに急」という性質は、より複雑なモデルでも崩れません。容量計画でまず把握すべきは正確な絶対値より、この発散の形です。レート制御で平均到着率 λ を抑えてゆらぎを平滑化する手法は トークンバケットとリーキーバケット、遅延とスループットと帯域の基礎関係は 帯域・レイテンシ・スループット を参照してください。