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

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

2007-08-09T02:25:07Z

2007年8月8日 (水) 06:37にYutaによる

2007-08-08T06:37:24Z

2007年8月8日 (水) 06:37にYutaによる

2007-08-08T06:37:08Z

2007年8月8日 (水) 06:34にYutaによる

2007-08-08T06:34:14Z

2007年8月7日 (火) 10:31にYutaによる

2007-08-07T10:31:29Z

2007年8月7日 (火) 10:20にYutaによる

2007-08-07T10:20:33Z

2007年8月7日 (火) 07:17にKuwashimaによる

2007-08-07T07:17:25Z

Orsjwiki: ページ《待ち行列ネットワーク(BCMP型)》を《待ち行列ネットワーク(BCMP型とその応用)》へ移動

2007-08-06T04:06:52Z

ページ《待ち行列ネットワーク(BCMP型)》を《待ち行列ネットワーク(BCMP型とその応用)》へ移動

Orsjwiki: "《待ち行列ネットワーク(BCMP型)》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:53:37Z

"《待ち行列ネットワーク(BCMP型)》" を保護しました。 [edit=sysop:move=sysop]

2007年7月19日 (木) 04:45に122.17.2.240による

2007-07-19T04:45:07Z

@@ 15行目: / 15行目: @@
 :*各ノードのサービス規律は先着順, プロセッサ・シェアリング, 無限サーバ, 後着順割込継続型のいずれかにしたがう. 各クラスの客のサービス要求量の分布は, 先着順の場合はクラス共通の指数分布のみであるが, その他の場合はクラスに依存してもよく, 任意の分布が許される.
-いま, ノード<math>i\, </math>への客の到着を[[トラヒック方程式]] (traffic equation)
+いま, ノード<math>i\, </math>への客の到着を[[トラフィック方程式]] (traffic equation)
@@ 27行目: / 27行目: @@
 の解<math>\lambda_{(i, c)}\, </math>に等しい率のポアソン到着としてノードの状態の周辺分布を求めると, BCPM型ネットワークの定常分布はこの周辺分布の積で表現できる.
 '''ケリー型''' BCMPネットワークとケリーネットワークの2つの研究は，ほぼ同時期に独立に行われたが，本質的には同種類のモデルである．しかしKellyの研究は，積形式解をもつネットワークの範囲がBCMP型のプロセッサ・シェアリング，無限サーバ，後着順割込継続型を含む，より一般的な[[対称型サービス規律]](symmetric service discipline)に拡張されている点と，客のクラスを経路情報を含めた形で設定するれば客の経路を決定論的に定めることができることを明示した点で重要である．以下，対称型サービス規律について説明する．
 '''対称型サービス'''　対称型サービス規律ではノード内の客の位置を区別し, ノード<math>i\, </math>に客が<math>m\, </math>人いるときのノード<math>i\, </math>の状態 <math>\boldsymbol {x_i} \, </math> を, 位置<math>k\, </math>の客のクラス<math>c_k\, </math>とその客の残余サービス必要量 (サービス必要量の分布が[[相型分布]](phase distribution)の場合は客のいる相番号))<math>\phi_k\, </math>を用いて，<math>\boldsymbol{x_i} = (c_1, \phi_1, c_2, \phi_2, \cdots, c_m, \phi_m)\, </math>と表現する．
 ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるときこのノードに客が到着すると, 客は確率 <math>\gamma(m+1, k)\, </math> で位置<math>k\, </math>を選択し, このとき位置 <math>l>k\, </math> にいた客は位置<math>l+1\, </math>に移る. また, 状態 <math>\boldsymbol{x_i}\, </math>において位置<math>k\, </math>の客が退去すると, 位置 <math>l>k\, </math> にいた客は位置 <math>l-1 \, </math> に移る. さらに, ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるとき, このノードの総サービス率は <math>\varphi(m)\, </math> で与えられ, 総サービス率は位置kの客に <math>\gamma(m, k)\, </math> の割合で配分される. すなわち, 位置<math>k\, </math>の客のサービス率は <math>\varphi(m) \gamma(m, k)\, </math> となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する.
 '''平均応答時間''' ケリーネットワークでは，客を種類に分け，種類ごとに客がサービスを受けるノードの列を前もって決めることができる．この経路選択は客の種類を適切に与えると通常のマルコフ的経路選択と等価であることが証明できる．このように客がサービスを受けるノードの列<math>i_{1}, i_{2}, \ldots, i_{n}</math>が前もって与えられ，各ノードでのサービス必要量が<math>x_{1}, x_{2}, \ldots, x_{n}</math>である客が到着したという条件の下で，その客の到着から退去までの時間の条件付き期待値を平均ネットワーク[[応答時間]]と呼ぶ．対称型サービスでは，上記の客が<math>k\, </math>番目のノードに到着してから退去するまでの平均応答時間が客のサービス必要量<math>x_{k}</math>に比例し，平均ネットワーク応答時間は<math>x_{1}, x_{2}, \ldots, x_{n}</math>の線形和となることが知られている（[3]参照）．
 '''不感性''' 対称型サービス規律では，各ノードの状態確率がサービス時間分布の形とは無関係に，その平均値のみによって定まる．この性質は[[不感性]](insensitivity)と呼ばれている．また，局所平衡が成り立つネットワークは不感性であることもわかる．
 不感性をもつ代表的なシステムの例としては，呼がポアソン過程に従って発生する[[回線交換網]](circuit switching network)が挙げられ，呼損率は保留時間の分布形に関係なく平均値によってのみ定まる．
 '''局所平衡''' BCMPやケリーネットワークの特徴は，[[局所平衡方程式|局所平衡]](local balance)方程式を満たすことにある．
 これによって，積形式解が直接導かれ，また積形式解が[[大域平衡方程式|大域平衡]] (global balance)方程式を満足すること(定常分布であること)も容易に証明できる．

← 古い版		2007年8月8日 (水) 06:37時点における版
54行目:		54行目:

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

	[3] M. Miyazawa, R. Schassberger and V. Schmidt, "On the structure of an insensitive generalized semi-Markov process with reallocation and with point-process input," ''Advances in Applied Probability'' (1995), 203-225.		[3] M. Miyazawa, R. Schassberger and V. Schmidt, "On the structure of an insensitive generalized semi-Markov process with reallocation and with point-process input," ''Advances in Applied Probability'' (1995), 203-225.

@@ 53行目: / 53行目: @@
 [1] F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers," ''Journal of Association for Computing Machinery'', '''22''' (1975), 248-260.
 [2] F. P. Kelly, ''Reversibility and Stochastic Networks'', John Wiley & Sons, 1979.
-[3] 橋田温, 「最近のネットワーク手法」, 『オペレーションズ・リサーチ』, '''26''' (1981), 205-212.
 [4] J. Walrand, ''An Introduction to Queueing Networks'', Prentice-Hall, 1988.
 [[category:待ち行列ネットワーク|まちぎょうれつねっとわーく（BCMPがたとそのおうよう）]]

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつねっとわーく (びーしーえむぴーがた) (BCMP network) 】'''
-　[[待ち行列ネットワーク]] (queueing network) において, ネットワーク全体の定常分布が各ノードの状態の周辺分布の積として表されるとき, このようなネットワークは一般に[[積形式解]] (product form solution) を持つといわれる. 最初に研究された一連の積形式ネットワークは, [[ジャクソンネットワーク]] (Jackson network) と呼ばれている. ジャクソンネットワークは, 定常分布の表現が簡単であるので広く応用されてきたが, 経路をあらかじめ選択できない, 指数サービスに限定される, などモデルの制約が強い. これに対して, ジャクソンネットワークを拡張して, 客に客の[[客のクラス|クラス]]を設け, かつより一般的なサービス機構にしても積形式解をもつことが, Baskettら [1] やKelly [2] の研究によって明らかにされた. ここでは, 前者を[[BCMPネットワーク]] (BCMP network) [3], 後者を[[ケリーネットワーク]] (Kelly network) と呼ぶ.
+　[[待ち行列ネットワーク]] (queueing network) において, ネットワーク全体の定常分布が各ノードの状態の周辺分布の積として表されるとき, このようなネットワークは一般に[[積形式解]] (product form solution) を持つといわれる. 最初に研究された一連の積形式ネットワークは, [[ジャクソンネットワーク]] (Jackson network) と呼ばれている. ジャクソンネットワークは, 定常分布の表現が簡単であるので広く応用されてきたが, 経路をあらかじめ選択できない, 指数サービスに限定される, などモデルの制約が強い. これに対して, ジャクソンネットワークを拡張して, 客に客の[[客のクラス|クラス]]を設け, かつより一般的なサービス機構にしても積形式解をもつことが, Baskettら [1] やKelly [2] の研究によって明らかにされた. ここでは, 前者を[[BCMPネットワーク]] (BCMP network) [4], 後者を[[ケリーネットワーク]] (Kelly network) と呼ぶ.
@@ 9行目: / 9行目: @@
 :*外部から到着した客は, 確率<math>r_{0, (i, c)}\, </math>でノード<math>i\, </math>に行き, クラス<math>c\, </math>の客となる. ノード<math>i\, </math>のクラス<math>c\, </math>の客は, サービス終了後確率<math>r_{(i, c), (j, d)}\, </math>でノード<math>j\, </math>のクラス<math>d\, </math>の客となり, 確率<math>r_{(i, c), 0}\, </math>でネットワークから退去する. これらの確率はネットワークの状態とは独立であるので、このような経路選択をマルコフ的という．マルコフ的経路選択では，すべてのクラスに対して<math>r_{0, (i, c)}\,>0 </math>，<math>r_{(i,c),0}\,>0 </math>とおけば[[開放型ネットワーク|開放型]](open network)，<math>r_{0, (i, c)}\,=0 </math>，<math>r_{(i,c),0}\,=0 </math>とおけば[[閉鎖型ネットワーク|閉鎖型]](closed network)となる．
 :*各ノードのサービス規律は先着順, プロセッサ・シェアリング, 無限サーバ, 後着順割込継続型のいずれかにしたがう. 各クラスの客のサービス要求量の分布は, 先着順の場合はクラス共通の指数分布のみであるが, その他の場合はクラスに依存してもよく, 任意の分布が許される.
@@ 18行目: / 21行目: @@
 <math>
 \lambda_{(i, c)} = \lambda r_{0, (i, c)} +
-\sum_{j=1}^M \sum_{d=1}^C \lambda_{(j, d)} r_{(j, d), (i, c)}
+\sum_{j=1}^N \sum_{d=1}^C \lambda_{(j, d)} r_{(j, d), (i, c)}
 \, </math>
 </center>
@@ 25行目: / 28行目: @@
 の解<math>\lambda_{(i, c)}\, </math>に等しい率のポアソン到着としてノードの状態の周辺分布を求めると, BCPM型ネットワークの定常分布はこの周辺分布の積で表現できる.
-'''ケリー型'''
+'''対称型サービス'''　対称型サービス規律ではノード内の客の位置を区別し, ノード<math>i\, </math>に客が<math>m\, </math>人いるときのノード<math>i\, </math>の状態 <math>\boldsymbol {x_i} \, </math> を, 位置<math>k\, </math>の客のクラス<math>c_k\, </math>とその客の残余サービス必要量 (サービス必要量の分布が[[相型分布]](phase distribution)の場合は客のいる相番号))<math>\phi_k\, </math>を用いて，<math>\boldsymbol{x_i} = (c_1, \phi_1, c_2, \phi_2, \cdots, c_m, \phi_m)\, </math>と表現する．
 ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるときこのノードに客が到着すると, 客は確率 <math>\gamma(m+1, k)\, </math> で位置<math>k\, </math>を選択し, このとき位置 <math>l>k\, </math> にいた客は位置<math>l+1\, </math>に移る. また, 状態 <math>\boldsymbol{x_i}\, </math>において位置<math>k\, </math>の客が退去すると, 位置 <math>l>k\, </math> にいた客は位置 <math>l-1 \, </math> に移る. さらに, ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるとき, このノードの総サービス率は <math>\varphi(m)\, </math> で与えられ, 総サービス率は位置kの客に <math>\gamma(m, k)\, </math> の割合で配分される. すなわち, 位置<math>k\, </math>の客のサービス率は <math>\varphi(m) \gamma(m, k)\, </math> となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する.
-'''平均応答時間'''
+'''平均応答時間''' ケリーネットワークでは，客を種類に分け，種類ごとに客がサービスを受けるノードの列を前もって決めることができる．この経路選択は客の種類を適切に与えると通常のマルコフ的経路選択と等価であることが証明できる．このように客がサービスを受けるノードの列<math>i_{1}, i_{2}, \ldots, i_{n}</math>が前もって与えられ，各ノードでのサービス必要量が<math>x_{1}, x_{2}, \ldots, x_{n}</math>である客が到着したという条件の下で，その客の到着から退去までの時間の条件付き期待値を平均ネットワーク[[応答時間]]と呼ぶ．対称型サービスでは，上記の客が<math>k\, </math>番目のノードに到着してから退去するまでの平均応答時間が客のサービス必要量<math>x_{k}</math>に比例し，平均ネットワーク応答時間は<math>x_{1}, x_{2}, \ldots, x_{n}</math>の線形和となることが知られている（[3]参照）．
-対称型サービス規律では，各ノードの状態確率がサービス時間分布の形とは無関係に，その平均値のみによって定まる．この性質は[[不感性]](insensitivity)と呼ばれている．また，局所平衡が成り立つネットワークは不感性であることもわかる．
+'''不感性''' 対称型サービス規律では，各ノードの状態確率がサービス時間分布の形とは無関係に，その平均値のみによって定まる．この性質は[[不感性]](insensitivity)と呼ばれている．また，局所平衡が成り立つネットワークは不感性であることもわかる．
 不感性をもつ代表的なシステムの例としては，呼がポアソン過程に従って発生する[[回線交換網]](circuit switching network)が挙げられ，呼損率は保留時間の分布形に関係なく平均値によってのみ定まる．
-'''局所平衡'''
+'''局所平衡''' BCMPやケリーネットワークの特徴は，[[局所平衡方程式|局所平衡]](local balance)方程式を満たすことにある．
 これによって，積形式解が直接導かれ，また積形式解が[[大域平衡方程式|大域平衡]] (global balance)方程式を満足すること(定常分布であること)も容易に証明できる．
 また，サービス時間分布が一般の場合は，対称型サービス規律はサービス位置を区別した最も詳細な局所平衡方程式が成り立つための必要十分条件となる．対称型サービス規律はこの局所平衡方式から自然に導かれたと考えられる．

@@ 26行目: / 26行目: @@
-'''対称型サービス規律'''　BCMPネットワークとケリーネットワークの2つの研究は, ほぼ同時期に独立に行われたが, 本質的には同種類のモデルである. しかしKellyの研究は, 積形式解をもつネットワークの範囲がBCMP型のプロセッサ・シェアリング, 無限サーバ, 後着順割込継続型を含む, より一般的な[[対称型サービス規律]] (symmetric service discipline) に拡張されている点と, 客のクラスを経路情報を含めた形で設定すれば客の経路を決定論的に定めることができることを明示した点で重要である. 以下, 対称型サービス規律について説明する.
+'''平均応答時間'''
-　対称型サービス規律ではノード内の客の位置を区別し, ノード<math>i\, </math>に客が<math>m\, </math>人いるときのノード<math>i\, </math>の状態 <math>\boldsymbol {x_i} \, </math> を, 位置<math>k\, </math>の客のクラス<math>c_k\, </math>とその客の残余サービス要求量 (サービス要求量の分布が相型分布の場合は客のいる相番号)<math>\phi_k\, </math>を用いて, <math>\boldsymbol{x_i} = (c_1, \phi_1, c_2, \phi_2, \cdots, c_m, \phi_m)\, </math> と表現する. ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるときこのノードに客が到着すると, 客は確率 <math>\gamma(m+1, k)\, </math> で位置<math>k\, </math>を選択し, このとき位置 <math>l>k\, </math> にいた客は位置<math>l+1\, </math>に移る. また, 状態 <math>\boldsymbol{x_i}\, </math>において位置<math>k\, </math>の客が退去すると, 位置 <math>l>k\, </math> にいた客は位置 <math>l-1 \, </math> に移る. さらに, ノード<math>i\, </math>の状態が <math>\boldsymbol{x_i}\, </math> であるとき, このノードの総サービス率は <math>\varphi(m)\, </math> で与えられ, 総サービス率は位置kの客に <math>\gamma(m, k)\, </math> の割合で配分される. すなわち, 位置<math>k\, </math>の客のサービス率は <math>\varphi(m) \gamma(m, k)\, </math> となる. 対称型という言葉は, 到着した客が各位置へ割り付けられる確率とその位置で客が受けるサービスの割合が比例する点に由来する. また, 対称型サービスでは, 客がノードに到着してから退去するまでの平均応答時間が, その客のサービス要求量に比例することが知られている.
+ケリーネットワークでは，客を種類に分け，種類ごとに客がサービスを受けるノードの列を前もって決めることができる．この経路選択は客の種類を適切に与えると通常のマルコフ的経路選択と等価であることが証明できる．このように客がサービスを受けるノードの列$i_{1}, i_{2}, \ldots, i_{n}$が前もって与えられ，各ノードでのサービス必要量が$x_{1}, x_{2}, \ldots, x_{n}$である客が到着したという条件の下で，その客の到着から退去までの時間の条件付き期待値を平均ネットワーク\yougolink{B-B-03}{応答時間}{応答時間}(response time)と呼ぶ．対称型サービスでは，上記の客が$k$番目のノードに到着してから退去するまでの平均応答時間が客のサービス必要量$x_{k}$に比例し，平均ネットワーク応答時間は$x_{1}, x_{2}, \ldots, x_{n}$の線形和となることが知られている（[3]参照）．
-　BCMPやケリーネットワークの特徴は, [[局所平衡方程式|局所平衡]] (local balance) 方程式を満たすことにある. これによって, 積形式解が直接導かれ, また積形式解が[[大域平衡方程式|大域平衡]] (global balance) 方程式を満足すること (定常分布であること)も容易に証明できる. また, サービス時間分布が一般の場合は, 対称型サービス規律はサービス位置を区別した最も詳細な局所平衡方程式が成り立つための必要十分条件となる. 対称型サービス規律はこの局所平衡方式から自然に導かれたと考えられる.
+'''不感性'''
-　対称型サービス規律では, 各ノードの状態確率がサービス時間分布の形とは無関係に, その平均値のみによって定まる. この性質は[[不感性]] (insensitivity)と呼ばれている. また, 局所平衡が成り立つネットワークは不感性をもつこともわかる. 不感性をもつ代表的なシステムの例としては, 呼がポアソン過程に従って発生する[[回線交換網]] (circuit switching network) が挙げられ, 呼損率は保留時間の分布形に関係なく平均値によってのみ定まる.
+対称型サービス規律では，各ノードの状態確率がサービス時間分布の形とは無関係に，その平均値のみによって定まる．この性質は[[不感性]](insensitivity)と呼ばれている．また，局所平衡が成り立つネットワークは不感性であることもわかる．
-　ネットワークが積形式解をもつ証明の別法として, 元の確率過程の時間を逆転した[[逆過程]] (reversed process) を用いる方法が提案されている [2], [4]. 関連した方法に[[準可逆性]](quasi-reversibility) という性質を使う証明がある. この場合には, 各ノードが準可逆性を持つことを示し, 準可逆性を持つノードをマルコフ的経路選択で結合すると積形式ネットワークとなることを利用する. この方法は, 積形式を持つネットワークを構成するためにも有効な方法である.
+BCMPやケリーネットワークの特徴は，[[局所平衡方程式|局所平衡]](local balance)方程式を満たすことにある．

← 古い版		2007年8月7日 (火) 07:17時点における版
55行目:		55行目:

	[4] J. Walrand, ''An Introduction to Queueing Networks'', Prentice-Hall, 1988.		[4] J. Walrand, ''An Introduction to Queueing Networks'', Prentice-Hall, 1988.
		+
		+	[[category:待ち行列ネットワーク\|まちぎょうれつねっとわーく（BCMPがたとそのおうよう）]]

← 古い版	2007年8月6日 (月) 04:06時点における版
(相違点なし)

← 古い版	2007年7月19日 (木) 13:53時点における版
(相違点なし)

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

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

2007年8月8日 (水) 06:37にYutaによる

2007年8月8日 (水) 06:37にYutaによる

2007年8月8日 (水) 06:34にYutaによる

2007年8月7日 (火) 10:31にYutaによる

2007年8月7日 (火) 10:20にYutaによる

2007年8月7日 (火) 07:17にKuwashimaによる

Orsjwiki: ページ 《待ち行列ネットワーク(BCMP型)》 を 《待ち行列ネットワーク(BCMP型とその応用)》 へ移動

Orsjwiki: "《待ち行列ネットワーク(BCMP型)》" を保護しました。 [edit=sysop:move=sysop]

2007年7月19日 (木) 04:45に122.17.2.240による

Orsjwiki: ページ《待ち行列ネットワーク(BCMP型)》を《待ち行列ネットワーク(BCMP型とその応用)》へ移動