《待ち行列ネットワーク(ジャクソン型とその応用)》
【まちぎょうれつねっとわーく (じゃくそんがた) (Jackson network) 】
ジャクソン型待ち行列ネットワークは, J. R. Jackson [3] によって導入された最も基本的な待ち行列ネットワークモデルである. このモデルではシステムの状態変化がマルコフ連鎖で記述され, 定常状態確率が積形式で陽に表現される. 計算機システムの性能評価をはじめ実際問題の解析にも頻繁に応用されている.
ジャクソンネットワーク ジャクソン型待ち行列ネットワークでは, 各ノードは指数サービスを行う1つもしくは複数の窓口と1つの容量無限の待ち合室 (バッファ) からなり, あるノードでサービスを終えた客は経路選択確率と呼ばれる一定の確率で次のノードを選ぶ. ネットワークのノード数を $M$ とし, 各ノードをノード $1, 2, \ldots, M$ で表す. ノード $i$ におけるサービス率はそのノードにいる客数 $n$ の関数として $C_i(n)$ で与えられる. 例えばノード $i$ の窓口数が $c$, 各窓口のサービス率が $\mu$ ならば, $C_i(n)=\min(n, c)\mu$ である. ノード $i$ でサービスを終えた客は経路選択確率 $p_{ij}$ でノード $j$ に移動する.
ジャクソンネットワークは, 外部からの客の到着を仮定する開放型と, 外部からの到着はなく, 常に一定数 $N$ の客がネットワーク内を移動する閉鎖型に大別される. 開放型の場合, 客は外部から到着率 $\lambda$ のポアソン過程にしたがって到着する. 外部から到着した客は確率 $p_{0i}$ でノード $i$ に進み, ノード $i$ のサービスが終了した客は確率 $p_{i0}$ で網から退去する. $0$ を含むすべての $i$ について $\sum_{j=0}^M p_{ij} =1$ である. ただし $p_{00}$ は $0$ とする. 閉鎖型の場合は, すべての $i$ について $\sum_{j=1}^Mp_{ij} =1$ である. 経路選択確率 $p_{ij}$ からなる正方行列を $P$ とする. 開放型の場合 $P$ は $M+1$次であり, 閉鎖型の場合 $M$次である. 小さなモデルに分割されるケースを除外するため, $P$ をマルコフ連鎖の推移確率行列とみたとき, 既約であると仮定する.
定常状態確率 この待ち行列網の状態を $(n_1, n_2, \ldots, n_M)$ で表す. ここで $n_i$ はノード $i$ にいる客の数である. 定常状態確率を $p_{(n_1, n_2, \ldots, n_M)}$ とすれば, これは次のような積形式になる.
p_{(n_1, n_2, \ldots, n_M)}=G^{-1} \prod_{i=1}^M
\prod_{n=1}^{n_i} \frac{\alpha_i}{C_i(n)}
ここで $n_i=0$ のときは上記の積は1とみなす. $G$ は正規化定数であり, $\alpha_i$ $(i=1, 2, \ldots, M)$ はトラヒック方程式と呼ばれるつぎの方程式の解である.
\begin{eqnarray*}
&& \alpha_i = p_{0i}\lambda + \sum_{i=1}^M \alpha_j p_{ji},
\quad i=1, 2, \ldots, M, \qquad \mbox{ 開放型 }
\\
&& \alpha_i = \sum_{i=1}^M \alpha_j p_{ji},
\quad i=1, 2, \ldots, M, %\qquad \alpha_1=1
\qquad \mbox{ 閉鎖型 }
\end{eqnarray*}
これらの式は, 各ノード毎に $\alpha_i$ を到着率とみなし, これが退去率に等しいとして得られる1次の連立方程式と解釈できる. 開放型の場合, $\alpha_i$ は一人の客がネットワークに到着してから退去するまでにノード $i$ を訪問する平均回数に$\lambda$を乗じたものとなっている. 閉鎖型の場合, トラヒック方程式は $P$ の定常状態確率を求める方程式と同一であり, さらに例えば $\alpha_1=1$ という条件をおけば, $\alpha_i$ はノード1に到着してからまた再びノード1に戻ってくるまでにノード $i$ を訪問する平均回数という意味をもつ.
いろいろな性質 定常分布が積形式となることから, ジャクソンネットワークではいろいろ好ましい性質が成り立つことが証明されている. まず開放型の場合, 任意時点での各ノードの客の数は互いに独立になる. ただし, 閉鎖型の場合は可能な状態が $\sum_{i=1}^M n_i =N$ を満たすものに限られるので, 客の数は独立とはならない. また, 閉鎖型も含め, 各ノードからの退去過程はポアソン過程になる. したがって, どんな部分ネットワークに対しても, 部分ネットワーク全体を1つのノードで置き換えて, 他の部分の定常分布が変わらないようにすることができる. すなわちノートンの定理が任意の部分ネットワークに対して成り立つ [8]. さらに, 1つのノードへの到着時点で, 到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する. これを到着定理という. ただし, ネットワークが閉鎖型の場合には, 任意時点の分布として (到着した客を除いたことに対応する) システム内客数が $N-1$ のネットワークにおける定常分布を使う. さらに客の退去時点での分布も同様であり [4], この分布のもとで, ノード $i$ に到着してから次にそこに戻るまでの平均周期は, ノードごとの平均訪問回数と平均待ち時間の積の総和で与えられる.
正規化定数, スループット, 各ノードの平均客数などを求めることは, 開放型ネットワークの場合は容易である. 各ノードの客数が互いに独立になるためである. しかし, 閉鎖型の場合には, 可能な状態が $\sum_{i=1}^M n_i =N$ を満たすものに限られるという制約のため, 工夫が必要である. 例えば, 正規化定数を計算する方法として, たたみ込み法}や平均値解析法が知られている[2]. たたみ込み法では, ノード $i$ に対し, $N+1$ 次元のベクトルを
X_i=(X_i(0), X_i(1), \ldots, X_i(N)),
\quad X_i(0)=1, \quad X_i(n)=\prod_{j=1}^n \alpha_i/C_i(j),
\ n>0
とし, これらのベクトルを客数の和が $N$ 以下の範囲でたたみこみ演算して $G$ を求める. 平均値解析法は到着定理とリトルの公式を応用し, 各ノードの平均客数, 1回あたりの平均滞在時間, スループットなどを, システム内客数 $N$ について $0$ から繰り返し計算する方法である. 各ノードでの規律は, 平均待ち時間が到着時点での平均客数と平均サービス時間から求まるもの, 例えば先着順であること, が本質的である.
待ち時間の分布については, 特殊なネットワークについてのみ考察されている. 開放型で, サーバー数が1のノード (規律は先着順) が直列に並んでいるネットワークもJackson型の一つであるが, このネットワークで一人の客の各ノードでの滞在時間は互いに独立であることがバークの定理として知られている [1],[6]. これを閉鎖型にした場合, すなわち最後のノードを退去した客は必ず最初のノードに戻る循環型のネットワークでも, 一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる [7]. これはどの客も他の客に追い越されることがない (overtake free) という性質が本質的であり, バークの定理はこの影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ. 特に最後のノードのサービス時間分布は任意でよい. その他, セントラルサーバモデルで規律がプロセッサーシェアリングである場合の研究もある [5].
履歴により経路選択確率が変化する場合も含め, 客のクラスが複数の場合の混合型については, 発展型であるBCMP型, ケリー型などのネットワークで扱われる. また, 外部からの到着があるが, 系内に入ることができる客数に制限がある有限呼源 (もしくは損失型) の場合, 外部を一つのノードとみなすことにより, 閉鎖型に帰着できる [3].
参考文献
[1] P. J. Burke, "The Output Process of a Stationary M/M/$s$ Queuing System, The Annals of Mathematical Statistics, 39 (1968), 1144-1152.
[2] K. M. Chandy and C. H. Sauer, "Computational Algorithms for Product Form Queueing Networks," Communications of the Association for Computing Machinery, 23 (1980), 573-583.
[3] J. R. Jackson, "Jobshop-like Queueing Systems," Management Science, 10 (1963), 131-142.
[4] T. Kawashima, "A Property of Two Palm Measures in Queueing Networks and Its Applications," Journal of the Operations Research Society of Japan, 25 (1982), 16-28.
[5] J. A. Morrison and D. Mittra, "Heavy-usage Asymptotic Expansions for the Waiting Time in Closed Processor-sharing Systems with Multiple Casese," Advances in Applied Probability, 17 (1985), 163-185.
[6] E. Reich "Note on Queues in Tandem," The Annals of Mathematical Statistics, 34 (1963), 338-341.
[7] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," Journal of Applied Probability, 24 (1987), 511-521.
[8] J. Walrand, An Introduction to Queueing Networks, Prentice Hall, 1988.