到着過程とモデルの仮定

6 分で読了 #待ち行列理論 #基礎理論

このページの目次

平均100要求/sでも、等間隔の場合と毎秒一斉に来る場合では待ち時間が変わります。Poisson到着は解析しやすい基準であり、「要求が多い」だけで成立する仮定ではありません。

Poisson到着の仮定

一様Poisson過程は独立増分と一定強度 $λ$ を持ちます。長さ $Δ$ の区間の到着数は：

$P {A (Δ) = n} = e^{- λ Δ} \frac{( λ Δ ) ^{n}}{n !}, E [A (Δ)] = Var (A (Δ)) = λ Δ.$

隣接到着間隔 $I$ は独立同分布の指数変数で、 $P (I > t) = e^{- λ t}$ 、 $E [I] = 1/ λ$ 。 $λ = 2$ /sなら1 s内に到着がない確率は約13.5%です。平均間隔0.5 sは、必ず0.5 sごとに来るという意味ではありません。

指数分布の無記憶性は：

$P (I > s + t ∣ I > s) = e^{- λ t} .$

既に待った時間が長くても、このモデルでは次の到着が近づくわけではありません。一定間隔なら、経過時間から残り時間を推測できます。

図を準備しています

到着過程とモデルの仮定 · 実験

一様Poisson到着の解析分布であり、待ち行列のシミュレーションではありません。個数の極小右尾を省略し、下図は到着間隔の生存確率を示します。

$λ$ を固定して計数窓を広げると、個数の平均と分散は増えますが、到着間隔の曲線は変わりません。個数は離散、間隔は連続で、別の確率変数を示しています。

$C_{a}^{2} = \frac{Var ( I )}{E [ I ] ^{2}}, C_{s}^{2} = \frac{Var ( S )}{E [ S ] ^{2}} .$

一定間隔は $C_{a}^{2} = 0$ 、指数間隔は1です。1より大きいと平均に対する散らばりが大きくなります。ただし周辺分布の二つのモーメントでは、自己相関、同期周期、長いバーストを表せません。同じ短い間隔と長い間隔でも、並べ方によって待ち時間は変わります。

ログでは時間帯別の流量、複数時間幅での個数分散、間隔分布、相関を確認します。定期バッチ、日周期、キャッシュ失効、一斉再試行は一様性や独立性を破り得ます。独立で疎な多数の発生源の重ね合わせはPoissonに近づく場合がありますが、共通トリガーがあるとその根拠が崩れます。

$A / S / c / K$ は到着間隔、処理時間、窓口数、総容量の順です。 $M$ は無記憶の指数分布、 $D$ は一定値、 $G$ は一般分布。 $G I$ は独立同分布の一般間隔を明示します。本シリーズでは省略した $K$ を無限とし、FCFSや放棄なしなどは別に記載します。

PASTAは、外生Poisson到着が直前に見る状態分布が時間定常分布と一致する性質です。到着が未来のシステム変化を予知しないなど、適切な条件が必要です。これにより稼働時間の割合を「到着者が待つ確率」に変換できます。一般到着には保証されず、要求間の待ち時間の独立性も意味しません。

考え方

違います。同期バッチと一定周期があり、短い窓の個数は位相に依存します。バッチ・周期モデルかタイムスタンプの再生を使います。長期平均だけでは到着過程を特定できません。

考え方

できません。二つのモーメントは分布や依存関係を決定しません。経験分布、区間別流量、相関を調べます。有限データによる適合は証拠であり、厳密な仮定の証明ではありません。

CMUのモデル化講義は実システムを適切なモデルへ翻訳する手順を扱います。記法は MIT講義も参照できます。以後の計算でも仮定を省略しません。