《積形式解ネットワークとなるための条件》

【せきけいしきねっとわーくとなるためのじょうけん (product form solution of queueing network and Markov process) 】

　待ち行列ネットワークの特性を調べる上で, 定常分布を求めることは重要であるが一般には難しい. しかし, ジャクソンやBCMPネットワークのように定常分布が解析的に得られる場合がある. 特に, これらのネットワークは積形式の定常分布を持つ. このようなネットワークを一般に積形式ネットワーク (product form network) と呼ぶ. この他, 集団移動型ネットワーク (batch movement network) などで, 特殊なサービス規律を適用すると定常分布が解析的に得られる場合がある. なぜこれらのネットワークでは定常分布が解析的に得られるのであろうか？ 一般的なモデルを対象にその理由を説明する.

マルコフ連鎖によるモデル化

待ち行列ネットワークはマルコフ過程によりモデル化することができる．このマルコフ過程には次の２つのタイプがある． 1. 各ノードの客数を主な状態とし，サービス中の客のサービス経過時間などを補助変数とするマルコフ過程で，代表的なものに一般化セミマルコフ過程 (generalized semi-Markov process, GSMP と略称化される)がある．

2. サービス時間と到着間隔の分布を指数分布と仮定したり，1の補助変数の部分を相型分布などを使って離散化することにより，離散的状態を持つマルコフ過程，すなわち，マルコフ連鎖としてモデル化する．

　1のモデルは2のモデルで十分に近似することができるので, 以下では2のモデルを使う. 一般に待ち行列ネットワークをマルコフ連鎖で表すには, その推移率関数を次の要素に分けると見通しがよい.

• 内部推移率：ノードの内部的な変化 (サービスの進行など) を表す部分

• 退去推移率：退去とそのときの状態変化を表す部分

• 経路選択確率：退去から次のノードへの到着を表す部分

• 到着推移確率：到着による状態変化を条件付き確率で表す部分

独立サービス・確率的経路選択ネットワーク $1\,$から$N\,$までの番号がついた$N\,$個のノードを持つ開放型ネットワークをマルコフ連鎖によりモデル化する．ただし，複数のクラスの客があり，各客はサービス完了後のクラスとノードにのみ依存した確率で次のノードとクラスを選択するとする．なお，各ノードには，$1,2,\ldots \,$と番号のついたサービス位置があり，$n\,$人の客がいるときには，，$1,2,\ldots \,$のサービス位置を占める．ノード$j\,$での各サービス位置の客のクラスとサービスの経過時間を表す状態からなるベクトルを${\boldsymbol {x}}_{j}\,$とする．このとき，ネットワークの状態を${\boldsymbol {x}}=({\boldsymbol {x}}_{1},{\boldsymbol {x}}_{2},\ldots ,{\boldsymbol {x}}_{M})\,$により表す．

このネットワークで, ノード$j\,$にいるクラス$u\,$の客の退去推移率を $q_{ju}^{\rm {D}}\,$, その客が退去後ノード$k\,$へクラス$v\,$の客として到着する経路選択確率を $r_{ju,kv}\,$, ノード$k\,$での到着推移確率を $p_{kv}^{\rm {A}}\,$ とする. この場合のサービス完了から到着までを表す推移は, ノード$j,k\,$の状態が${\boldsymbol {x}}_{j},{\boldsymbol {x}}_{k}\,$ から ${\boldsymbol {x}}_{j}',{\boldsymbol {x}}_{k}'\,$ へ変わったとすると,

$q_{ju}^{\rm {D}}({\boldsymbol {x}}_{j},{\boldsymbol {x}}_{j}')\,r_{ju,kv}\,p_{kv}^{\rm {A}}({\boldsymbol {x}}_{k},{\boldsymbol {x}}_{k}')\,$

である．なお，開放型の場合には，外部をノード$0$とみなし，ネットワーク状態に取り入れる．ただし，外部からの到着がポアソン過程に従うならば，ノード$0$からの退去率$q_{0u}^{\mbox{\scriptsize \sc d}}(\vc{ x}_0,\vc{ x}_0')$は各$u\,$に対して定数であり，ノード$0\,$の状態をネットワーク状態に取り入れる必要はない．このような退去・到着による推移率と内部推移率の総和をネットワーク全体の推移率$q\,$とすると，$q\,$はネットワークモデルを表すマルコフ連鎖の推移率である(\cite{B04+MIYAZAWA5}参照)．

このネットワークモデルでは，サービスが各ノードごとに独立に行われ，経路選択もネットワークの状態とは独立に確率的に行われるので，独立サービス・確率的経路選択ネットワークと呼ぶ．このモデルは，ジャクソン，BCMPやケリーネットワークにおいて，到着過程，サービス方法，サービス時間分布などを一般化したものである．この一般モデルにおいて定常分布が積形式となる条件が得られている（\cite{B04+MIYAZAWA1}参照）．

準可逆性

独立サービス・確率的経路選択ネットワークにおいて，各ノードを切り離し客をポアソン到着させると定常分布が存在し，この定常分布に従う状態の下で退去もまたポアソン過程となるならば，準可逆 (quasi-reversibility)であるという．例えば，ノード$j\,$の準可逆性は，切り離してポアソン入力した場合の定常分布を$\pi _{j}\,$とすれば，各クラス構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \u\, } に対して，

$\ (\,$クラス $u\,$ の退去が起こり状態が ${\boldsymbol {x}}_{j}\,$ となる率 $\ )=\beta _{ju}\ \pi _{j}({\boldsymbol {x}}_{j})\,$

となる定数$\beta _{ju}\,$が存在することに等しい. 独立サービス・独立経路選択ネットワークにおいて，終端ノードを除きすべてのノードが準可逆であり，外部からの到着がポアソン過程に従うならば，定常分布は積形式となる．ここに，終端ノードとは退去客が外部へのみ退去するノードである．この結果の逆は必ずしも言えないが，客の種類が１つでサービス中や待っている客が途中で退去しないならば，準可逆性は必要条件でもある\cite{B04+MIYAZAWA1})．

局所平衡式

BCMPやケリーネットワークの特徴は, この推移率$q\,$の定常分布$\pi \,$が次の局所平衡方程式 (local balance equation)を満たすことにある [4]. サービスを受ける位置に番号をつけ, 位置$\ell \,$にいるクラス$u\,$の客を$(\ell ,u)\,$とするとき, 

\begin{eqnarray*}

&& \pi(\vc{ x}) (\mbox{状態 $\vc{x}$ で } (\ell,u) \mbox{の客がノード$j$でサービスを完了する率}) \\
&& \qquad = \sum_{\vc{ x}'} \pi(\vc{ x}') (\mbox{状態 $\vc{x}'$ でサービスの完了または到着があり，}\\
&& \hspace{20ex} (\ell,u) \mbox{の客がノード$j$に到着し状態が$\vc{ x}$となる率})

\end{eqnarray*}

逆に, サービス時間分布が一般の場合にこの方程式が成り立つならば, サービス規律は対称型 である [1]. さらに, 内部推移についても同様な局所平衡方程式が成り立ち, すべての局所平衡方程式を加えると大域平衡方程式 (global balance equation)が得られる. これより, $\pi \,$が局所平衡方程式を満たせば, 定常分布であることが確認できる. この局所平衡方程式は, 客の残りサービス時間や経過サービス時間が客の配置と独立であることと同値である. 積形式に加えこの独立性が成り立つとき2重積形式 (double product form)を持つという.

逆時間過程

局所平衡方程式は一般の積形式ネットワークでは必ずしも成立しない．例えば，到着により客が減る[[負の客}{負の客]](negative customer) や負の客が瞬間的に複数のノードを通過するシグナルネットワークも積形式解を持つが局所平衡は成立しない\cite{B04+MIYAZAWA1}．この種のネットワークの解析には，時間を逆転した確率過程すなわち逆過程(reversed process)が有効である．一般に定常なマルコフ連鎖の逆過程もまた定常なマルコフ連鎖となることから，逆過程の推移率を推測できれば，定常分布$\pi \,$が求められる(\cite{B04+MIYAZAWA5}参照)．逆時間過程は積形式解をもつネットワークを探したり，積形式となることの証明を行う際にも役立つ．

集団移動型ネットワーク 複数のノードで同時に到着やサービスがあるネットワークを集団移動型ネットワークモデルと呼ぶ．集団移動型では，一般に状態推移がネットワークの状態全体$\vc{x}$に依存する．ただし，サービス時間は考えずにネットワークの状態に依存した率で退去が発生するとする．すなわち，集団をベクトル$\vc{u} = (u_1,u_2,\ldots, u_N)$で表すとき，$\vc{u}$の退去がネットワーク状態に依存した率で起こる．この集団$\vc{u}$が集団$\vc{ v}$となって到着する確率を$r_{\vc{u}\vc{v}}(\vc{x})$とする．

一般に，集団移動型ネットワークの定常分布を求めることは困難である．そこで，理想的な条件を仮定して定常分布が得られるモデルを探す．例えば，局所平衡方程式 \begin{eqnarray*}

&& \pi(\vc{ x}) (\mbox{状態 $\vc{x}$ で}\vc{u} \mbox{が退去する率}) \\
&& \quad = \sum_{\vc{ x}',\vc{v}} \pi(\vc{ x}') (\mbox{状態$\vc{x'}$で$\vc{v}$が退去し，$\vc{u}$が到着し状態が$\vc{ x}$となる率})

\end{eqnarray*} が任意の状態$\vc{ x}$とすべて集団$\vc{u}$について成り立つならば．定常分布$\pi$を求めることができる\cite{B04+MIYAZAWA1}．特に推移行列$\{r_{\vc{u}\vc{v}}(\vc{x})\}$が$\vc{x}$に依存しない定常分布$\nu$を持ち，任意に与えた正値関数$\Phi$と非負値関数$\Psi$に対して，状態$\vc{x}$での$\vc{u}$の退去率が \begin{eqnarray*}

\frac {\Psi(\vc{x}-\vc{u})}{\Phi(\vc{x})} \nu(\vc{u})

\end{eqnarray*} であるならば，局所平衡方程式が成り立ち，定常確率$\pi(\vc{x})$は$\Phi(\vc{x})$に比例する\cite{B04+MIYAZAWA3}．このネットワークはWalrand\cite{B04+MIYAZAWA4}の離散時間同期型ネットワークや回線交換網などを特別な場合として含む\cite{B04+MIYAZAWA1}．

　

　

　

$q_{ju}^{\rm {D}}({\boldsymbol {x}}_{j},{\boldsymbol {x}}_{j}')\,r_{ju,kv}\,p_{kv}^{\rm {A}}({\boldsymbol {x}}_{k},{\boldsymbol {x}}_{k}')\,$

である. なお, 開放型の場合は, 外部をノード$0\,$とみなし, ネットワーク状態に取り入れる. ただし, 外部からの到着がポアソン過程に従うならば, ノード$0\,$からの退去率$q_{0u}^{\rm {D}}({\boldsymbol {x}}_{0},{\boldsymbol {x}}_{0}')\,$は各$u\,$に対して定数であり, ノード$0\,$の状態をネットワーク状態に取り入れる必要はない. ネットワーク全体の推移率$q\,$は, このような退去・到着による推移率と内部推移率の総和である([6]参照).

$\pi ({\boldsymbol {x}})(\,$ 状態 ${\boldsymbol {x}}\,$ で $(\ell ,u)\,$の客がノード $j\,$ でサービスを完了する率 $\ )\,$

$\qquad =\sum _{{\boldsymbol {x}}'}\pi ({\boldsymbol {x}}')(\,$ 状態 ${\boldsymbol {x}}'\,$でサービスの完了または到着があり,

$\ \ \ (\ell ,u)\,$ の客がノード $j\,$に到着し状態が ${\boldsymbol {x}}\,$ となる率 $\ )\,$

　局所平衡方程式は, 複数のノードで同時に退去や到着が起こる集団移動型のモデルの解析においても役立つ. このネットワークの状態${\boldsymbol {x}}\,$は各ノードの客数を要素とするベクトルであり, 集団をベクトル${\boldsymbol {u}}=(u_{1},u_{2},\ldots ,u_{M})\,$で表すとき, ${\boldsymbol {u}}\,$の退去がネットワーク状態に依存した率で起こる. この集団${\boldsymbol {u}}\,$が集団${\boldsymbol {v}}\,$となって到着する確率を$r_{\boldsymbol {uv}}\,$とする. このモデルで, 局所平衡方程式

$\pi ({\boldsymbol {x}})(\,$ 状態 ${\boldsymbol {x}}\,$ で ${\boldsymbol {u}}\,$ が退去する率 $\ )\,$

$\quad =\sum _{{\boldsymbol {x}}',{\boldsymbol {v}}}\pi ({\boldsymbol {x}}')(\,$ 状態 ${\boldsymbol {x}}'\,$ で ${\boldsymbol {v}}\,$ が退去し, ${\boldsymbol {u}}\,$ が到着し状態が ${\boldsymbol {x}}\,$ となる率 $\ )\,$

が, 任意の状態${\boldsymbol {x}}\,$とすべて集団${\boldsymbol {u}}\,$について成り立つならば. 定常分布$\pi \,$を求めることができる [1]. 例えば, 推移行列{$r_{\boldsymbol {uv}}\,$}が定常分布$\nu \,$を持ち, 任意に与えた正値関数$\Phi \,$と非負値関数$\Psi \,$に対して, 状態${\boldsymbol {x}}\,$での${\boldsymbol {u}}\,$の退去率が

${\frac {\Psi ({\boldsymbol {x}}-{\boldsymbol {u}})}{\Phi ({\boldsymbol {x}})}}\nu ({\boldsymbol {u}})\,$

であるならば, 局所平衡方程式が成り立ち, 定常確率$\pi ({\boldsymbol {x}})\,$は$\Phi ({\boldsymbol {x}})\,$に比例する [3]. このネットワークはWalrand [5] の離散時間同期型ネットワークや回線交換網などを特別な場合として含む. この種のネットワークは, 転送確率$r_{\boldsymbol {uv}}\,$がネットワークの状態に依存する場合にも拡張されている [1].

---

参考文献

[1] X. Chao, M. Miyazawa and M. Pinedo, Queueing Networks, Customers, Signals and Product form, John Wiley & Sons, 1999.

[2] W. Henderson and P. G. Taylor, "Product Form in Networks of Queues with Batch Arrivals and Batch Services," Queueing Systems, 6 (1990), 71-88.

[3] F. P. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, 1979.

[4] J. Walrand, "A Discrete-time Queueing Network," Journal of Applied Probability, 20 (1983), 903-909.

[5] 宮沢政清, 「待ち行列ネットワークと積形式解」, 『オペレーションズ・リサーチ』, 43 (1998), 442-448.