「《待ち行列ネットワーク》」の版間の差分
ナビゲーションに移動
検索に移動
Sakasegawa (トーク | 投稿記録) |
Sakasegawa (トーク | 投稿記録) |
||
| 1行目: | 1行目: | ||
'''【まちぎょうれつねっとわーく (queueing network) 】''' | '''【まちぎょうれつねっとわーく (queueing network) 】''' | ||
| + | |||
| + | [[待ち行列ネットワーク|ここをクリックしてください]] | ||
| + | <!-- | ||
複数の待ち行列システム(以下ノードと表記)が, 図1のようにネットワーク上に結合された数学モデルを[[待ち行列ネットワーク]] (queueing network あるいは network of queues) と呼ぶ. | 複数の待ち行列システム(以下ノードと表記)が, 図1のようにネットワーク上に結合された数学モデルを[[待ち行列ネットワーク]] (queueing network あるいは network of queues) と呼ぶ. | ||
| 9行目: | 12行目: | ||
各ノード間の移動は通常確率的に選択される. 例えばノード <math>i</math> から <math>j</math> は確率 <math>r_{ij}</math> で移動する. [[経路選択確率]] (routing probability) あるいは分岐確率 (branching probability) と呼ぶ. 特にネットワーク外を表現するのにノード0と記す．このモデルの確率的な振る舞いを解析し, 待ち時間・待ち行列長・スループットなどに関する性能評価量を算出が可能となる. 特に図2のように直列につながったモデルを[[直列型待ち行列]](queueing networkあるいはnetwork of queues)と呼ぶ． | 各ノード間の移動は通常確率的に選択される. 例えばノード <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> | <center><table><tr><td align=center>[[画像:sk-0123-b-b-01-1.png]]</td></tr> | ||
<td align=center>図２：直列型待ち行列<br></td></table></center> | <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} | \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} | ||
--> | --> | ||
| + | <!-- | ||
これらのモデルにおいては，あるノードからの退去過程は他のノードへの到着過程になることからノード間の従属性が生じる．さらにはネットワークにフィー | これらのモデルにおいては，あるノードからの退去過程は他のノードへの到着過程になることからノード間の従属性が生じる．さらにはネットワークにフィー | ||
| 21行目: | 26行目: | ||
析するのは不可能であり，ネットワーク全体を捉えた解析が必要である．これまでに解析的にはマルコフ性を保持しながら，[[積形式解]]が得られる範囲内で，現実のシステムにより近いモデルが次々と発表されて来た． | 析するのは不可能であり，ネットワーク全体を捉えた解析が必要である．これまでに解析的にはマルコフ性を保持しながら，[[積形式解]]が得られる範囲内で，現実のシステムにより近いモデルが次々と発表されて来た． | ||
待ち行列ネットワークは，外部との関わり方で[[開放型ネットワーク]](open network)と[[閉鎖型ネットワーク]](closed network)に分類が可能である．開放型ネットワークにおいてはネットワーク外からの客の到着があり，またネットワーク外への退去もある．従ってネットワーク内の総客数は可変であり，一定ではない．これは例えば蓄積交換型のパケット交換網においては，パケット送信要求の発生が客のネットワークへの流入に相当し，各交換機およびそれに付随するバッファが各ノードに対応する．従って目的局に受信されることが，ネットワークからの退去に当たる．一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着，外への退去はない．従って総客数が常に一定に保たれる．これは例えば一定台数の機械から構成されるシステムにおいて機械の故障・修理を考慮した性能評価を行なう際に用いられる．あるいはマルチプログラミング環境下で動作する計算機システムのように，内部にCPU，I/O機器などのサーバおよびそれに付随した待ち行列があり，総客数は一定に保たれている場合に相当する．計算が完了したジョブ／トランザクションはネットワークから消滅するが，それと同時にネットワーク外のバッファに貯えられていたジョブ・トランザクションが投入され，結果として総数が変わらないような場合にも適用が可能であり，計算機アーキテクチュアなどの評価に用いられた．閉鎖型ネットワークで，機械修理問題に見られるように，稼動状態，修理待ち状態，検査待ち状態のそれぞれに対応するノードを順番に訪問し，客の流れが同一方向で，訪問する待ち行列の順番が一定な直列型待ち行列を特に循環型待ち行列(図3参照)と呼ぶ． | 待ち行列ネットワークは，外部との関わり方で[[開放型ネットワーク]](open network)と[[閉鎖型ネットワーク]](closed network)に分類が可能である．開放型ネットワークにおいてはネットワーク外からの客の到着があり，またネットワーク外への退去もある．従ってネットワーク内の総客数は可変であり，一定ではない．これは例えば蓄積交換型のパケット交換網においては，パケット送信要求の発生が客のネットワークへの流入に相当し，各交換機およびそれに付随するバッファが各ノードに対応する．従って目的局に受信されることが，ネットワークからの退去に当たる．一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着，外への退去はない．従って総客数が常に一定に保たれる．これは例えば一定台数の機械から構成されるシステムにおいて機械の故障・修理を考慮した性能評価を行なう際に用いられる．あるいはマルチプログラミング環境下で動作する計算機システムのように，内部にCPU，I/O機器などのサーバおよびそれに付随した待ち行列があり，総客数は一定に保たれている場合に相当する．計算が完了したジョブ／トランザクションはネットワークから消滅するが，それと同時にネットワーク外のバッファに貯えられていたジョブ・トランザクションが投入され，結果として総数が変わらないような場合にも適用が可能であり，計算機アーキテクチュアなどの評価に用いられた．閉鎖型ネットワークで，機械修理問題に見られるように，稼動状態，修理待ち状態，検査待ち状態のそれぞれに対応するノードを順番に訪問し，客の流れが同一方向で，訪問する待ち行列の順番が一定な直列型待ち行列を特に循環型待ち行列(図3参照)と呼ぶ． | ||
| − | |||
| 36行目: | 40行目: | ||
</td></table></center> | </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} | \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} | ||
--> | --> | ||
| + | <!-- | ||
また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である. | また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である. | ||
| 53行目: | 59行目: | ||
[[category:待ち行列ネットワーク|まちぎょうれつねっとわーく]] | [[category:待ち行列ネットワーク|まちぎょうれつねっとわーく]] | ||
| + | --> | ||