「待ち行列ネットワーク」の版間の差分

2008年11月13日 (木) 22:00時点における最新版

【まちぎょうれつねっとわーく (queueing network)】

概要

複数の待ち行列システムが，直列，リング状あるいはネットワーク状に組み合わされた数学モデル．情報ネットワーク，コンピュータシステム，FMS（flexible manufacturing system）を始めとする生産システム，交通システムなどの複合システムにおける「待ち」現象の確率的振る舞いを取り扱う．待ち時間，待ち行列長，スループットなどの性能評価量を算出するのに用いられる．

詳説

　複数の待ち行列システム(以下ノードと表記)が, 図1のようにネットワーク上に結合された数学モデルを待ち行列ネットワーク (queueing network あるいは network of queues) と呼ぶ.

図１：待ち行列ネットワーク

　各ノード間の移動は通常確率的に選択される. 例えばノード $i$ から $j$ は確率 $r_{ij}$ で移動する. 経路選択確率 (routing probability) あるいは分岐確率 (branching probability) と呼ぶ. 特にネットワーク外を表現するのにノード0と記す．このモデルの確率的な振る舞いを解析し, 待ち時間・待ち行列長・スループットなどに関する性能評価量を算出が可能となる. 特に図2のように直列につながったモデルを直列型待ち行列(queueing networkあるいはnetwork of queues)と呼ぶ．

図２：直列型待ち行列

　これらのモデルにおいては，あるノードからの退去過程は他のノードへの到着過程になることからノード間の従属性が生じる．さらにはネットワークにフィードバック・ループがある場合には，退去した客が再度到着する可能性もあり，到着客間にも従属性が生じる．これらのことから個別のノードを取り出し，解析するのは不可能であり，ネットワーク全体を捉えた解析が必要である．これまでに解析的にはマルコフ性を保持しながら，積形式解が得られる範囲内で，現実のシステムにより近いモデルが次々と発表されて来た．　待ち行列ネットワークは，外部との関わり方で開放型ネットワーク(open network)と閉鎖型ネットワーク(closed network)に分類が可能である．開放型ネットワークにおいてはネットワーク外からの客の到着があり，またネットワーク外への退去もある．従ってネットワーク内の総客数は可変であり，一定ではない．これは例えば蓄積交換型のパケット交換網においては，パケット送信要求の発生が客のネットワークへの流入に相当し，各交換機およびそれに付随するバッファが各ノードに対応する．従って目的局に受信されることが，ネットワークからの退去に当たる．一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着，外への退去はない．従って総客数が常に一定に保たれる．これは例えば一定台数の機械から構成されるシステムにおいて機械の故障・修理を考慮した性能評価を行なう際に用いられる．あるいはマルチプログラミング環境下で動作する計算機システムのように，内部にCPU，I/O機器などのサーバおよびそれに付随した待ち行列があり，総客数は一定に保たれている場合に相当する．計算が完了したジョブ／トランザクションはネットワークから消滅するが，それと同時にネットワーク外のバッファに貯えられていたジョブ・トランザクションが投入され，結果として総数が変わらないような場合にも適用が可能であり，計算機アーキテクチュアなどの評価に用いられた．閉鎖型ネットワークで，機械修理問題に見られるように，稼動状態，修理待ち状態，検査待ち状態のそれぞれに対応するノードを順番に訪問し，客の流れが同一方向で，訪問する待ち行列の順番が一定な直列型待ち行列を特に循環型待ち行列(図3参照)と呼ぶ．

図３：循環型待ち行列

　また図4に示すように, 計算機システムをモデル化した閉鎖型ネットワークで, 中央に位置するサーバ (CPU に相当) と複数の他のサーバおよびそれに付随する待ち行列 (入出力機器などの周辺機器に相当) からなり, 客がこれらの間を交互に行き来するモデルをセントラルサーバモデルと呼ぶ.

図４：セントラルサーバモデル

　また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である. 　さらに客が優先権，待ち行列ネットワーク内の移動経路などの属性により複数クラスに分類され，一部のクラスに属する客に関しては開放型で，他のクラスの客に関しては閉鎖型のネットワークを混合型待ち行列ネットワークと呼ぶ．　待ち行列ネットワークの別の分類として，各ノードで許容される待ち行列長に関する制限の有無に依るものがある．制限が無い場合には適当なモデル化の仮定を設ければ積形式解を用いた実用的な計算が可能であるが，制限がある場合には，ブロッキングが発生し，ノード間のより一層複雑な従属性が生じ，有効な解析法は存在しない．このような場合には近似的なアプローチを取らざるを得ない．ブロッキングとは，次に訪問するノードの待合室が一杯のときに移動が妨げられることを言う．この結果，モデルによっては元のサーバが次の客へのサービスを行なえない．客がいるにも拘わらずサービスが開始されない．これは例えば多段工程からなる生産ラインにおける，各工程における仕掛品置き場のように大容量のバッファがないシステムに相当する．一方通信網においては，ブロッキングが発生すると客であるパケット・メッセージなどは消滅する．　待ち行列ネットワークは，従来単一待ち行列システムでモデル化されていた生産・通信・コンピュータ・輸送・交通システムのネットワーク化に伴い，その重要性が増しており，特に積形式解を持つモデルの数値計算を支援するソフトウェア・パッケージなども提供されている．

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつねっとわーく (queueing network)】'''
+=== 概要 ===
-複数の待ち行列システムが, 直列, リング状あるいはネットワーク状に組み合わされた数学モデル. 情報ネットワーク, コンピュータシステム, FMS (flexible manufacturing system) を始めとする生産システム, 交通システムなどの複合システムにおける「待ち」現象の確率的振る舞いを取り扱う. 待ち時間, 待ち行列長, スループットなどの性能評価量を算出するのに用いられる.
+複数の待ち行列システムが，直列，リング状あるいはネットワーク状に組み合わされた数学モデル．情報ネットワーク，コンピュータシステム，FMS（flexible manufacturing system）を始めとする生産システム，交通システムなどの複合システムにおける「待ち」現象の確率的振る舞いを取り扱う．[[待ち時間]]，[[待ち行列長]]，スループットなどの性能評価量を算出するのに用いられる．
+=== 詳説 ===
+　複数の待ち行列システム(以下ノードと表記)が, 図1のようにネットワーク上に結合された数学モデルを[[待ち行列ネットワーク]] (queueing network あるいは network of queues) と呼ぶ.
+<center><table><tr><td align=center>[[画像:0123-Network.png|center|図１：待ち行列ネットワーク]]</td></tr>
+<td align=center>図１：待ち行列ネットワーク</td></table></center>
+　各ノード間の移動は通常確率的に選択される. 例えばノード <math>i</math> から <math>j</math> は確率 <math>r_{ij}</math> で移動する. [[経路選択確率]] (routing probability) あるいは分岐確率 (branching probability) と呼ぶ. 特にネットワーク外を表現するのにノード0と記す．このモデルの確率的な振る舞いを解析し, 待ち時間・待ち行列長・スループットなどに関する性能評価量を算出が可能となる. 特に図2のように直列につながったモデルを[[直列型待ち行列]](queueing networkあるいはnetwork of queues)と呼ぶ．
+<center><table><tr><td align=center>[[画像:sk-0123-b-b-01-1.png]]</td></tr>
+<td align=center>図２：直列型待ち行列<br></td></table></center>
+<!--
+\begin{figure}[htbp] \begin{center} %\includegraphics[bbllx=0, bblly=210mm, bburx=230mm, bbury=260mm, %height=40mm]{. . /b-b/tandem.eps} \setlength{\unitlength}{1mm} \begin{picture}(108, 20)(0, -10) \thicklines \put(0, 0){\vector(1, 0){8}} \multiput(9, -2.5)(0, 5){2}{\line(1, 0){7}} \put(16, -2.5){\line(0, 1){5}} \put(16, 0){\line(1, 0){2}} \put(21, 0){\circle{6}} \put(24, 0){\vector(1, 0){8}} \multiput(33, -2.5)(0, 5){2}{\line(1, 0){7}} \put(40, -2.5){\line(0, 1){5}} \put(40, 0){\vector(2, 3){4}} \put(40, 0){\vector(2, -3){4}} \put(47, 7.5){\circle{6}} \put(47, -7.5){\circle{6}} \put(47, 0){\makebox(0, 1.2){$\vdots$}} \put(50, 6){\vector(2, -3){4}} \put(50, -6){\vector(2, 3){4}} \multiput(55, -2.5)(0, 5){2}{\line(1, 0){7}} \put(62, -2.5){\line(0, 1){5}} \put(62, 0){\line(1, 0){2}} \put(67, 0){\circle{6}} \put(70, 0){\vector(1, 0){5}} \put(80, 0){\makebox(0, 0){$\cdots$}} \multiput(84, -2.5)(0, 5){2}{\line(1, 0){7}} \put(91, -2.5){\line(0, 1){5}} \put(91, 0){\line(1, 0){2}} \put(96, 0){\circle{6}} \put(99, 0){\vector(1, 0){9}} \end{picture} \end{center} \caption{直列型待ち行列} \label{B-B-01+tandem-model} \end{figure}
+-->
+　これらのモデルにおいては，あるノードからの退去過程は他のノードへの到着過程になることからノード間の従属性が生じる．さらにはネットワークにフィー
+ドバック・ループがある場合には，退去した客が再度到着する可能性もあり，到着客間にも従属性が生じる．これらのことから個別のノードを取り出し，解
+析するのは不可能であり，ネットワーク全体を捉えた解析が必要である．これまでに解析的にはマルコフ性を保持しながら，[[積形式解]]が得られる範囲内で，現実のシステムにより近いモデルが次々と発表されて来た．
+　待ち行列ネットワークは，外部との関わり方で[[開放型ネットワーク]](open network)と[[閉鎖型ネットワーク]](closed network)に分類が可能である．開放型ネットワークにおいてはネットワーク外からの客の到着があり，またネットワーク外への退去もある．従ってネットワーク内の総客数は可変であり，一定ではない．これは例えば蓄積交換型のパケット交換網においては，パケット送信要求の発生が客のネットワークへの流入に相当し，各交換機およびそれに付随するバッファが各ノードに対応する．従って目的局に受信されることが，ネットワークからの退去に当たる．一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着，外への退去はない．従って総客数が常に一定に保たれる．これは例えば一定台数の機械から構成されるシステムにおいて機械の故障・修理を考慮した性能評価を行なう際に用いられる．あるいはマルチプログラミング環境下で動作する計算機システムのように，内部にCPU，I/O機器などのサーバおよびそれに付随した待ち行列があり，総客数は一定に保たれている場合に相当する．計算が完了したジョブ／トランザクションはネットワークから消滅するが，それと同時にネットワーク外のバッファに貯えられていたジョブ・トランザクションが投入され，結果として総数が変わらないような場合にも適用が可能であり，計算機アーキテクチュアなどの評価に用いられた．閉鎖型ネットワークで，機械修理問題に見られるように，稼動状態，修理待ち状態，検査待ち状態のそれぞれに対応するノードを順番に訪問し，客の流れが同一方向で，訪問する待ち行列の順番が一定な直列型待ち行列を特に循環型待ち行列(図3参照)と呼ぶ．
+<center><table><tr><td align=center>[[画像:0123-Cyclic.png|center|図３：循環型待ち行列]]</td></tr>
+<td align=center><br>図３：循環型待ち行列</td></table></center>
+　また図4に示すように, 計算機システムをモデル化した閉鎖型ネットワークで, 中央に位置するサーバ (CPU に相当) と複数の他のサーバおよびそれに付随する待ち行列 (入出力機器などの周辺機器に相当) からなり, 客がこれらの間を交互に行き来するモデルを[[セントラルサーバモデル]]と呼ぶ.
+<center><table><tr><td align=center>[[画像:sk-0123-b-b-01-2.png]]</td></tr>
+<td align=center>図４：セントラルサーバモデル<br>
+</td></table></center>
+<!--
+\begin{figure}[htbp] \begin{center} %\includegraphics[bbllx=0, bblly=210mm, bburx=230mm, bbury=260mm, %height=40mm]{. . /b-b/central.eps} \setlength{\unitlength}{1mm} \begin{picture}(72, 33)(0, -13) \thicklines \put(0, -1){\vector(1, 0){10}} \put(0, -1){\line(0, 1){21}} \put(0, 20){\line(1, 0){72}} \put(72, 0){\line(0, 1){20}} \put(62, 0){\line(1, 0){10}} \put(6, 1){\vector(1, 0){4}} \put(6, 1){\line(0, 1){7}} \put(6, 8){\line(1, 0){23}} \put(29, 0){\vector(0, 1){8}} \multiput(11, -2.5)(0, 5){2}{\line(1, 0){7}} \put(18, -2.5){\line(0, 1){5}} \put(18, 0){\line(1, 0){2}} \put(23, 0){\circle{6}} \put(26, 0){\line(1, 0){12}} \put(38, -10){\line(0, 1){20}} \put(38, 10){\vector(1, 0){5}} \multiput(44, 7.5)(0, 5){2}{\line(1, 0){7}} \put(51, 7.5){\line(0, 1){5}} \put(51, 10){\line(1, 0){2}} \put(56, 10){\circle{6}} \put(59, 10){\line(1, 0){3}} \put(38, -10){\vector(1, 0){5}} \multiput(44, -7.5)(0, -5){2}{\line(1, 0){7}} \put(51, -7.5){\line(0, -1){5}} \put(51, -10){\line(1, 0){2}} \put(56, -10){\circle{6}} \put(59, -10){\line(1, 0){3}} \put(62, -10){\line(0, 1){20}} \put(48, 0){\makebox(0, 1.2){\Huge $\vdots$}} \end{picture} \caption{セントラルサーバモデル}\label{B-B-01+central-server-model} \end{center} \end{figure}
+-->
+　また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である.
+　さらに客が優先権，待ち行列ネットワーク内の移動経路などの属性により複数クラスに分類され，一部のクラスに属する客に関しては開放型で，他のクラス
+の客に関しては閉鎖型のネットワークを[[混合型待ち行列ネットワーク]]と呼ぶ．
+　待ち行列ネットワークの別の分類として，各ノードで許容される待ち行列長に関する制限の有無に依るものがある．制限が無い場合には適当なモデル化の仮
+定を設ければ積形式解を用いた実用的な計算が可能であるが，制限がある場合には，ブロッキングが発生し，ノード間のより一層複雑な従属性が生じ，有効な解析法は存在しない．このような場合には近似的なアプローチを取らざるを得ない．ブロッキングとは，次に訪問するノードの待合室が一杯のときに移動が妨げられることを言う．この結果，モデルによっては元のサーバが次の客へのサービスを行なえない．客がいるにも拘わらずサービスが開始されない．これは例えば多段工程からなる生産ラインにおける，各工程における仕掛品置き場のように大容量のバッファがないシステムに相当する．一方通信網においては，ブロッキングが発生すると客であるパケット・メッセージなどは消滅する．
+　待ち行列ネットワークは，従来単一待ち行列システムでモデル化されていた生産・通信・コンピュータ・輸送・交通システムのネットワーク化に伴い，その
+重要性が増しており，特に積形式解を持つモデルの数値計算を支援するソフトウェア・パッケージなども提供されている．
+[[category:待ち行列|まちぎょうれつもでるえむえむしー]]
+[[category:待ち行列ネットワーク|まちぎょうれつねっとわーく]]
+[[category:待ち行列の応用|まちぎょうれつのつうしんへのおうよう]]

「待ち行列ネットワーク」の版間の差分

2008年11月13日 (木) 22:00時点における最新版

概要

詳説

案内メニュー

検索