《待ち行列ネットワーク》

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

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

\begin{figure}[htbp] \begin{center} \includegraphics[bbllx=0, bblly=185mm, bburx=180mm, bbury=280mm, height=50mm]{0123-Network.eps} \caption{待ち行列ネットワーク}\label{B-B-01+queueing-network} \end{center} \end{figure}

　各ノード間の移動は通常確率的に選択される. 例えばノード $i$ から $j$ は確率 $r_{ij}$ で移動する. 経路選択確率 (routing probability) あるいは分岐確率 (branching probability) と呼ぶ. このモデルの確率的な振る舞いを解析し, 待ち時間・待ち行列長・スループットなどに関する性能評価量を算出することが目的である.

　これらのモデルにおいては, あるノードからの退去過程は他のノードへの到着過程になることから, ノード間の従属性が生じる. さらにはネットワークにフィードバック・ループがある場合には, 退去した客が再度到着する可能性もあり, 到着客間にも従属性が生じる. これらのことから個別のノードを取り出し, 解析するのは不可能であり, ネットワーク全体を捉えた解析が必要である. これまでに解析的にはマルコフ性を保持しながら, 積形式解が得られる範囲内で, 現実のシステムにより近いモデルが次々と発表されて来た. 待ち行列ネットワークは, 外部との関わり方で開放型ネットワーク (open network) と閉鎖型ネットワーク (closed network) に分類が可能である.

開放型ネットワーク　開放型ネットワークにおいてはネットワーク外からの客の到着があり, またネットワーク外への退去もある. 従ってネットワーク内の総客数は可変であり, 一定ではない. 例えば蓄積交換型のパケット交換網では, パケット送信要求の発生が客のネットワークへの流入に相当し, 各交換機およびそれに付随するバッファが各ノードに対応する. 従って目的局に受信されることが, ネットワークからの退去に当たる.

　図2のように直列に繋がったモデルを直列型待ち行列 (tandem queue あるいは series queue) と呼ぶが, これは代表的な開放型ネットワークである. 直列型待ち行列は生産ラインの性能評価などに多用される.

\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}

閉鎖型ネットワーク　一方閉鎖型ネットワークにおいてはネットワーク外からの客の到着, 外への退去はない. 従って総客数が常に一定に保たれる. これは例えば一定台数の機械から構成されるシステムにおいて, 機械の故障・修理を考慮した性能評価を行なう際に用いられる. あるいはマルチプログラミング環境下で動作する計算機システムのように, 内部にCPU, I/O機器などのサーバおよびそれに付随した待ち行列があり, 総客数は一定に保たれている場合に相当する. 計算が完了したジョブ/トランザクションはネットワークから消滅するが, それと同時にネットワーク外のバッファに貯えられていたジョブ/トランザクションが投入され, 結果として総数が変わらないような場合にも適用が可能であり, 計算機アーキテクチュアなどの評価に用いられている.

　閉鎖型ネットワークで, 機械修理問題に見られるように, 稼動状態, 修理待ち状態, 検査待ち状態のそれぞれに対応するノードを順番に訪問し, 客の流れが同一方向で, 訪問する待ち行列の順番が一定な直列型待ち行列を, 特に循環型待ち行列 (図3参照) と呼ぶ.

\begin{figure}[htbp] \begin{center} \includegraphics[bbllx=0, bblly=190mm, bburx=130mm, bbury=270mm, height=60mm]{0123-Cyclic.eps} \caption{循環型待ち行列} \label{B-B-01+cyclic-queue} \end{center} \end{figure}

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

\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}

　また単一待ち行列モデルで客の母集団が有限である場合も, 閉鎖型ネットワークの一例と見ることも可能である.

混合型ネットワーク　さらに客が優先権, 待ち行列ネットワーク内の移動経路などの属性により複数クラスに分類され, 一部のクラスに属する客に関しては開放型で, 他のクラスの客に関しては閉鎖型のネットワークを混合型ネットワークと呼ぶ.

ブロッキング　待ち行列ネットワークの別の分類として, 各ノードで許容される待ち行列長に関する制限の有無に依るものがある. 制限が無い場合には適当なモデル化の仮定を設ければ積形式解を用いた実用的な計算が可能であるが, 制限がある場合には, ブロッキングが発生し, ノード間のより一層複雑な従属性が生じ, 有効な解析法は存在しない. このような場合には近似的なアプローチを取らざるを得ない. ブロッキングとは, 次に訪問するノードの待合室が一杯のときに移動が妨げられることを言う. この結果, 元のサーバが次の客へのサービスを行なえない, 客がいるにも拘わらずサービスが開始されない, というようなことが起こる. 例えば多段工程からなる生産ラインでは, 各工程における仕掛品置き場が十分でないと, ブロッキングによってラインの流れが滞る. また, 通信網では, ブロッキングによって, 客であるパケット/メッセージなどが消滅したり, もう一度はじめから送信し直さなければならなくなったりする.

待ち行列ネットワークの応用　待ち行列ネットワークは, 従来単一待ち行列システムでモデル化されていた生産・通信・コンピュータ・輸送・交通システムのネットワーク化に伴い, その重要性が増しており, 積形式解を持つモデルの数値計算を支援するソフトウェア・パッケージなども提供されている.