---
title: 待ち行列ネットワークとボトルネック
url: https://doc.liz6.com/ja/theory/03-queueing-theory/09-networks-and-bottlenecks
locale: ja
area: theory
tags:
- 待ち行列理論
- 基礎理論
date: 2026-09-10
modified: 2026-09-10
description: 要求はキャッシュ、アプリ、データベースを順に訪れ、戻ったり複数の子要求へ分岐したりします。待ち行列ネットワークは、外部要求数を各資源が処理する仕事量へ変換します。
---
# 待ち行列ネットワークとボトルネック
要求はキャッシュ、アプリ、データベースを順に訪れ、戻ったり複数の子要求へ分岐したりします。待ち行列ネットワークは、外部要求数を各資源が処理する仕事量へ変換します。
## 待ちを求める前に流量を解く
ノード $j$ への外部到着率を $\gamma_j$、ノード $i$ の完了後に $j$ へ進む確率を $p_{ij}$ とすると、定常流量保存は：
$$\lambda_j=\gamma_j+\sum_i\lambda_i p_{ij}.$$
これは経路の記帳で、各ノードのM/M/1分布を保証しません。開放Jacksonネットワークには、独立な外部Poisson到着、指数処理、適切に独立な無記憶経路、無限待機容量、各ノードの安定負荷などが必要です。内部過程も無条件に独立標本とは扱えません。
鍵はJacksonの定常積形式です。本章の単一窓口ノードでは：
$$P(N_1=n_1,\ldots,N_k=n_k)=\prod_{j=1}^k(1-\rho_j)\rho_j^{n_j},\qquad \rho_j=\lambda_j/\mu_j<1.$$
同じ定常時刻の各ノード占有数の独立性であり、経路上の待ち時間の独立性ではありません。戻りがあると内部到着はPoissonでなくてもよく、この周辺分布から平均占有とネットワーク平均時間を求められます。条件と区別は [MITのJackson網講義](https://ocw.mit.edu/courses/6-263j-data-communication-networks-fall-2002/42cb7759de031ae20aae04632773fef4_Lecture7.pdf)を参照してください。
実験ではノード1、2を通り、確率 $p$ で1へ戻り、残りは退出します。各業務の各ノード平均訪問数は $V=1/(1-p)$、内部流量はともに $\lambda_0V$。処理率は100/sと250/sで、安定には $\lambda_0V<100$ が必要です。
$$E[T_{\mathrm{network}}]=V\left(\frac1{100-\lambda_0V}+\frac1{250-\lambda_0V}\right).$$
各ノード平均系内数を足し、ネットワークのLittleの法則を使って導けるため、一要求の経路上の遅延が独立である必要はありません。既定値 $\lambda_0=40$/s、$p=0.2$ では $V=1.25$、内部各50/s、平均31.25 msです。
**待ち行列ネットワークとボトルネック · 実験**
外部Poisson到着はノード1、2の順に進み、2から確率pで1へ戻ります。独立指数処理の単一窓口、μ₁=100/s、μ₂=250/s。ボトルネック以上では定常遅延を表示しません。
外部流量を固定して戻り確率を上げると、内部負荷が増えます。ボトルネック以上では定常条件が「いいえ」となり、平均時間は — です。有限の図から存在しない定常解を出しません。
## サービス需要とボトルネック界
業務一件あたり資源 $j$ の平均サービス需要は $D_j=V_jE[S_j]$。単一容量資源の利用率は $U_j=XD_j$ なので、必要なスループット上界は：
$$X\le\frac1{\max_jD_j}.$$
$D_j$ は占有処理だけで待機を含みません。応答時間を入れると混雑を固有仕事量と誤認します。交換可能な資源が $c_j$ 個なら $c_j/D_j$ にできますが、割当可能性と共有ボトルネックなしが前提です。上界は任意の遅延目標で到達できる性能の保証ではありません。
固定 $N$ ユーザー、平均思考時間 $Z$ の閉鎖系では $N=X(E[T]+Z)$。完了してから次を送るユーザーは応答が遅いと流入を減らします。外部予定で到着し続ける開放系とは違います。
## ファンアウトと裾
$m$ 子要求の全完了を待つと時間に $\max(T_1,\ldots,T_m)$ が含まれます。子時間が独立同分布でCDFが $F$ の場合だけ、最大値のCDFは $F(t)^m$。一子が閾値内に終わる確率0.99でも、独立な100子が全部終わる確率は $0.99^{100}\approx0.366$ です。
共通DB、ネットワーク、障害は依存を作るため、無条件に掛け算できません。直列段の平均は足せますが、各段p99の和は一般に全体p99ではありません。結合測定、適切な確率界、依存モデルが必要です。
## 確認問題
1. 業務一件がDBを平均3回、各5 ms占有します。単一資源の上界はいくつですか。
考え方
$D=3\times0.005=0.015$ s/件なので $X\le66.67$/s。待ち目標、別の資源、変動により実用流量はさらに低くなり得ます。
考え方
定常式では100/sから10/sへ下がります。生成器も対象と一緒に遅くなったのであり、継続的な開放100/sに耐えた証拠ではありません。