《待ち行列ネットワーク(ジャクソン型とその応用)》 - 版の履歴

2008年8月5日 (火) 13:33にSakasegawaによる

2008-08-05T13:33:32Z

2008年8月5日 (火) 13:32にSakasegawaによる

2008-08-05T13:32:16Z

2008年8月5日 (火) 02:57にSakasegawaによる

2008-08-05T02:57:55Z

2008年4月14日 (月) 14:09にSakasegawaによる

2008-04-14T14:09:52Z

2007年8月9日 (木) 02:22にSakasegawaによる

2007-08-09T02:22:36Z

2007年8月9日 (木) 01:36にSakasegawaによる

2007-08-09T01:36:07Z

2007年8月9日 (木) 01:34にSakasegawaによる

2007-08-09T01:34:25Z

2007年8月8日 (水) 10:08にSakasegawaによる

2007-08-08T10:08:38Z

2007年8月8日 (水) 10:07にSakasegawaによる

2007-08-08T10:07:16Z

2007年8月8日 (水) 10:02にSakasegawaによる

2007-08-08T10:02:32Z

@@ 56行目: / 56行目: @@
 とし，<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])．
+'''待ち時間''' 待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理|バークの定理]]として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，[[セントラルサーバモデル]]で規律が[[プロセッサシェアリング]]である場合の研究もある．(例えば[8])．
 '''負の客とシグナル''' ジャクソンネットワークの特徴は，ネットワーク内の各ノードに滞在する客数を要素とするベクトルを状態に取ると連続時間マルコフ連鎖により表されることにある．1990年代に[4]は，到着すると客数を減らす[[負の客]]という概念を導入し，同様なマルコフ連鎖によるモデル化を行い，ジャクソンネットワークと同様な積形式の定常分布をもつことを証明した．到着客が待ち行列に並んだ後にサービスを受けずに退去することがあるので，各ノードへの通常の客の総到着率は減少し，客の強制退去を考慮した非線形なトラヒック方程式の解として求められる．定常分布はこの変更された総到着率を使って表すことができる．その後，このモデルは，負の客が複数のノードを瞬間的に動き回る[[シグナル到着ネットワーク]]へ拡張され，積形式の定常分布をもつことが証明されている（[3]参照）．例えば，各ノードで集団サービスが行われるジャクソン型と同様なネットワークで，予定された大きさの集団がサービスされた集団のみ1つの客となり経路を選択するモデルは，シグナル到着ジャクソンネットワークの例である．

@@ 3行目: / 3行目: @@
 　ジャクソンネットワークの名は 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>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> とする．

@@ 21行目: / 21行目: @@
-上記の積で <math>n_i=0\, </math> となる項は1とする. <math>G\, </math> は[[正規化定数]]であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラフィック方程式]]と呼ばれるつぎの方程式の解である.
+上記の積で <math>n_i=0\, </math> となる項は1とする. <math>G\, </math> は[[ネットワーク状態分布の正規化定数|正規化定数]]であり, <math>\alpha_i\, </math> <math>(i=1, 2, \ldots, M)\, </math> は[[トラフィック方程式]]と呼ばれるつぎの方程式の解である.
 <center>
@@ 36行目: / 36行目: @@
 \, </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>を訪問する期待回数という意味をもつ．

@@ 3行目: / 3行目: @@
 　ジャクソンネットワークの名は 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>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> とする．

← 古い版		2007年8月9日 (木) 02:22時点における版
21行目:		21行目:


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

	<center>		<center>

@@ 42行目: / 42行目: @@
 長さは互いに独立になる．また，閉鎖型も含め，各ノードからの退去過程がポアソン過程になる．したがって，どんな部分ネットワークに対しても，部分ネットワー%ク全体を１つのノードで置き換えて，他の部分の定常分布が変えないようにすることができ, すなわち，[[ノートンの定理|ノートンの定理]]が任意の部分ネットワークに対して成り立つ[11]．さらに，１つのノードへの各到着時点で，到着した客が見るネットワークの状態の分布は任意時点の状態分布と一致する．これを[[到着定理|到着定理]]という．ただし，網が閉鎖型の場合には，任意時点の分布として，到着した客を除いた網を使う．さらにその客の退去時点での分布も同様であり[6]，この分布でのもとで，ノード<math>i\, </math>に到着してから，次にそこに戻るまでの平均周期時間はノードごとの平均訪問回数と平均待ち時間の積の総和となること等が求まる．
-'''正規化定数と性能評価量の計算'''　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみこみ法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを
+'''正規化定数と性能評価量の計算'''　積形式解から定常分布を求めるためには正規化定数の計算が必要である．開放型の場合は容易であるが，閉鎖型の場合には，可能な状態が<math>\textstyle \sum_{i=1}^M n_i =N\, </math>を満たすもに限られるので，工夫が必要である．例えば，閉鎖型正規化定数を計算する方法として，[[たたみ込み法]]や[[平均値解析法]]が知られている．[2]．たたみこみ法では, ノード <math>i\, </math> に対し, <math>N+1\, </math> 次元のベクトルを
 <center>

← 古い版		2007年8月9日 (木) 01:34時点における版
53行目:		53行目:


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

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

@@ 8行目: / 8行目: @@
 経路選択確率<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]参照）．
+については，発展した型である[[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> とすれば, これは次のような積形式になる.

@@ 15行目: / 15行目: @@
 <center>
 <math>
-p_{(n_1, n_2, \ldots, n_M)}=G^{-1}
+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)} \prod_{i=1}^M
+\, \frac{\alpha_i^{n_i}}{\prod_{n=1}^{n_i} C_i(n)}
-\, </math>
+      </math>
 </center>
@@ 53行目: / 53行目: @@
-とし，<math>G=(X_1*X_2*...*X_M){\bf 1}\, </math>で与える．<math>*\, </math>はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理と[[リトルの公式|Littleの公式]]を応用し，平均列長などを系内客数<math>N\, </math>について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．
+とし，<math>G=(X_1*X_2*...*X_M){\bf I}\, </math>で与える．<math>*\, </math>はベクトルのたたみ込み演算である．定常分布が求まれば，スループットや平均待ち行列長の計算は比較的簡単である．しかし，正規化定数を計算することなく直接平均待ち行列長を計算する方法もある．例えば，平均値解析法は到着定理と[[リトルの公式|Littleの公式]]を応用し，平均列長などを系内客数<math>N\, </math>について0から繰り返し計算する方法である．各ノードでの平均待ち時間は到着時点での平均列長と平均サービス時間から求まる規律，例えば先着順であることが本質的である．
 '''待ち時間''' 待ち時間の分布については，特殊な網について考察されている．開放型で，サーバー数が1のノード(規律は先着順)が直列に並んでいる網もJackson型の一つであるが，この網で一人の客の各ノードでの滞在時間は互いに独立であることが[[バークの定理|バークの定理]]として知られている[1],[9]．これを閉鎖型にした場合，すなわち，最後のノードを退去した客は必ず最初のノードに戻る周期的な網でも，一周する間の一人の客の各ノードでの滞在時間の同時分布も一種の積の形となる[10]．一人の客が他の客に追い越されることがない(overtake free)という性質が本質的であり，バークの定理は，この影響がない最初と最後のノードでのサーバー数が複数の場合でも成り立つ．特に最後のノードのサービス時間分布は任意でよい．その他，[[セントラルサーバモデル]]で規律が[[プロセッサーシェアリング]]である場合の研究もある．(例えば[8])．