《待ち行列ネットワーク(ジャクソン型とその応用)》のソースを表示

'''【まちぎょうれつねっとわーく (じゃくそんがた) (Jackson network) 】'''

　ジャクソンネットワークの名は J.R.Jackson[5]に因る．1970年代後半から, 計算機システムの評価に応用されはじめた．待ち行列網の状態変化がマルコフ過程として記述され, 平衡方程式の解である定常確率分布が[[積形式解|積形式]]として陽に表される基本的なモデルとして重要なものとなっている．

　この待ち行列網の各ノードは指数分布に従うサービス時間をもつ窓口からなり, １つのノードのサービスを終えた客が，その客の履歴によらず，[[経路選択確率]]と呼ぶ一定の確率で次のノードを選ぶモデルである．すなわち，<math>M\, </math>個のノード<math>1, 2, \ldots, M\, </math>からなり，ノード<math>i\, </math>のサービス率はそのノードにいる客数<math>n\, </math>の関数で，<math>C_{i}\,(n) </math>と表すことができる．例えば，ノード<math>i\, </math>のサーバー数が<math>c_{i}\, </math>，サービス時間分布がサービス率<math>\mu_{i}\, </math>の[[指数分布]]ならば，<math>C_i(n)=\min(n, c_{i})\mu_{i}\, </math>である．ノード<math>i\, </math>のサービスを終えた客は経路選択確率<math>r_{ij}\, </math>でノード<math>j\, </math>に移動する．

　この網は，外部からの客の到着を仮定する[[開放型ネットワーク|開放型]]と，外部からの到着はなく，常に一定数<math>N\, </math>の客が網内を移動する[[閉鎖型ネットワーク|閉鎖型]]に大別される．開放型の場合，外部からの到着過程は到着率<math>\lambda\, </math>の[[ポアソン到着|ポアソン過程]]とする．外部から到着した客は確率<math>r_{0i}\, </math>でノード<math>i\, </math>に進み，ノード<math>i\, </math>のサービスが終了した客は確率<math>r_{i0}\, </math>で網から退去する．少なくとも一つの<math>i\, </math>について，<math>r_{i0}\,>0 </math>とならなければならない．閉鎖型の場合はすべての<math>i\, </math>について，<math>\textstyle \sum_{j=1}^Mp_{ij} =1\, </math> とする．
経路選択確率<math>r_{ij}\, </math> からなる正方行列を<math>P\, </math>とする．開放型の場合，状態<math>0\, </math>があるため，<math>P\, </math>は<math>M+1\, </math>次となり，閉鎖型の場合<math>M\, </math>次となる．
<math>P\, </math>をマルコフ連鎖の推移確率行列とみたとき，既約であると仮定する．客のクラスが複数の場合の[[混合型待ち行列ネットワーク|混合型]]
については，発展した型である[[BCMPネットワーク|BCMP型]]や[[ケリーネットワーク|ケリー型]]などのネットワークに分類される．また，外部からの到着があるが，系内に入ることができる客数に制限がある[[有限呼源待ち行列|有限呼源]](もしくは損失型)の場合，外部を一つのノードとみなすことにより，閉鎖型に帰着できる（[5]参照）．

'''積形式解'''　この待ち行列網の状態を <math>(n_1, n_2, \ldots, n_M)\, </math> で表す. ここで <math>n_i\, </math> はノード <math>i\, </math> にいる客の数である. 定常状態確率を <math>p_{(n_1, n_2, \ldots, n_M)}\, </math> とすれば, これは次のような積形式になる. 


<center>
<math>
p_{(n_1, n_2, \ldots, n_M)}=G^{-1}  \prod_{i=1}^M
\, \frac{\alpha_i^{n_i}}{\prod_{n=1}^{n_i} C_i(n)} 
      </math>
</center>


上記の積で <math>n_i=0\, </math> となる項は1とする. <math>G\, </math> は[[ネットワーク状態分布の正規化定数|正規化定数]]であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラフィック方程式]]と呼ばれるつぎの方程式の解である.

<center>
<math>
\alpha_i = p_{0i}\lambda + \sum_{i=1}^M \alpha_j p_{ji}, 
          \quad i=1, 2, \ldots, M,  \qquad 
\, </math>　開放型
</center>

<center>
<math> 
\alpha_i = \sum_{i=1}^M \alpha_j p_{ji}, 
       \quad i=1, 2, \ldots, M, \qquad
\, </math>　開放型
</center>


この方程式は，各ノード毎に到着率が退去率に等しいとして得られる1次の連立方程式である．開放型の場合，解<math>\alpha_i\, </math>は一人の客が網に到着してから退去するまでにノード<math>i\, </math>を訪問する平均回数にネットワークへの総到着率<math>\lambda\, </math>を乗じたものである．閉鎖型の場合は，トラヒック方程式は<math>P\, </math>の定常確率を求める方程式と同一であり，さらに，例えば<math>\alpha_1=1\, </math>とすれば，<math>\alpha_{i}\, </math>はノード1に到着してからまた次にそこに到着するまでの間にノード<math>i\, </math>を訪問する期待回数という意味をもつ．

定常分布が積形式となることから，開放型の場合，任意時点での，各ノードの列の長さは互いに独立になり，各ノードからの退去過程がポアソン過程になる．また，閉鎖型も含め，どんな部分ネットワークに対しても，部分ネットワーク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができる．
長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，[[ノートンの定理|ノートンの定理]]が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを[[到着定理|到着定理]]という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード<math>i\, </math>に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．

'''正規化定数と性能評価量の計算'''　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみ込み法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを

<center>
<math>
X_i=(X_i(0), X_i(1), \ldots, X_i(N)), 
  \quad X_i(0)=1, X_i(n)= \frac {\alpha_i^{n}} {\Pi_{j=1}^n C_{i}(j)} \quad (n>0), 
  \  n>0
\, </math>
</center>


とし，<math>G=(X_1*X_2*...*X_M){\mathbf 1}\, </math>で与える．<math>*\, </math>はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理と[[リトルの公式|Littleの公式]]を応用し，平均列長などを系内客数<math>N\, </math>について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．

'''待ち時間''' 待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理|バークの定理]]として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，[[セントラルサーバモデル]]で規律が[[プロセッサーシェアリング]]である場合の研究もある．(例えば[8])．

'''負の客とシグナル''' ジャクソンネットワークの特徴は，ネットワーク内の各ノードに滞在する客数を要素とするベクトルを状態に取ると連続時間マルコフ連鎖により表されることにある．1990年代に[4]は，到着すると客数を減らす[[負の客]]という概念を導入し，同様なマルコフ連鎖によるモデル化を行い，ジャクソンネットワークと同様な積形式の定常分布をもつことを証明した．到着客が待ち行列に並んだ後にサービスを受けずに退去することがあるので，各ノードへの通常の客の総到着率は減少し，客の強制退去を考慮した非線形なトラヒック方程式の解として求められる．定常分布はこの変更された総到着率を使って表すことができる．その後，このモデルは，負の客が複数のノードを瞬間的に動き回る[[シグナル到着ネットワーク]]へ拡張され，積形式の定常分布をもつことが証明されている（[3]参照）．例えば，各ノードで集団サービスが行われるジャクソン型と同様なネットワークで，予定された大きさの集団がサービスされた集団のみ1つの客となり経路を選択するモデルは，シグナル到着ジャクソンネットワークの例である．

'''集団移動型''' ジャクソンネットワークと同様にポアソン到着やサービス時間が指数分布に従うモデルで，集団到着や集団退去があるモデルもあり，[[集団移動型ネットワーク|集団移動型]]と呼ばれる．このモデルは上記で述べた特別な場合を除いて，積形式の定常分布をもたないが，サービス集団の大きさがノードごとに独立であり経路の選択が集団ごとにまとめて行われる場合には，定常分布の補分布の上限を与える積形式分布が知られている（\[7],[12]参照）．また，このモデルは，サービス完了時刻でネットワークの変化を追うと離散時間型のモデルと見なすこともできる．








----

'''参考文献'''

[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]X. Chao, M. Miyazawa and M. Pinedo, ''Queueing Networks; customers, signals and product form solutions,''   Wiley, 1999.

[4]E. Gelenbe, ``Product-form queueing networks with negative and positive customers,'' Journal of Applied Probability}, (1991), 656--663.

[5] J. R. Jackson, "Jobshop-like Queueing Systems," ''Management Science'', '''10''' (1963), 131-142. 

[6]T. Kawashima,
``A Property of two Palm measures in queueing networks and its applications,''Journal of the Operations Research Society of Japan, (1982), 16--28.

[7]M. Miyazawa, P. Taylor,
``A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers,'' Advances in Applied Probability 29, (1997), 523--544.

[8] 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. 

[9] E. Reich "Note on Queues in Tandem," ''The Annals of Mathematical Statistics'', '''34''' (1963), 338-341. 

[10] R. Schassberger and H. Daduna. "Sojourn Times in Queueing Networks with Multiserver Nodes," ''Journal of Applied Probability'', '''24''' (1987), 511-521. 

[11] J. Walrand, ''An Introduction to Queueing Networks'', Prentice Hall, 1988.

[12]H. Yamashita, M. Miyazawa,``Product form queueing networks with concurrent movements,''
. ''Advances in Applied Probability, '' '''30''' (1998), 1111--1129.

[[category:待ち行列ネットワーク|まちぎょうれつねっとわーく（じゃくそんがたとそのおうよう）]]