《待ち行列ネットワークの安定性》

【まちぎょうれつねっとわーくのあんていせい (stability of queueing network) 】

　待ち行列や待ち行列ネットワークが長時間に渡って稼働するとき, システム内の客数が発散することがない場合に待ち行列の安定であるという. 安定でなければ, サービスを受けられない客が正の確率で増大する. 安定性はシステムを安全に稼働するための最低限の条件といえる. 待ち行列システムをマルコフ過程などの確率過程でモデル化すると, 安定性は状態の確率分布が全ての時間にわたって確率過程のタイト (tight)であることに等しい.

　一般に確率過程が定常分布を持つならば, 安定である. しかし, 逆は周期性などのため必ずしもいえない. このように正確には安定性は定常分布の存在とは少し異なるが, 待ち行列システムの状態推移が, 特定の時刻に依存して変化しない時には, 安定性は定常分布の存在と同じであると考えてよい. 本稿では客の到着過程が時間的に定常であり, サービス規律なども特定の時刻に依存しない待ち行列システムの安定性について説明する. したがって, 安定性は定常分布の存在と同じ意味を持つ.

　待ち行列ネットワークの安定性を論ずるために, 初めにネットワークを構成するノードの安定性を調べる. システムは窓口が1つで, 定常な入力過程を持つとする. このシステムでは, サービスを受けることができない客は待ち行列を作って待つ. サービス規律としては, 客がいれば必ずサービスを行い, サービス要求量に変化がない仕事量保存型サービス (work conserving service)を仮定する. このシステムでは, 直感的にも分かるように,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \ (\, } 単位時間当たりの到着仕事量の平均 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \ ) < 1 \, }

ならば, 待ち行列は安定である. 単位時間当たりの到着仕事量の平均は, システムに対する負荷を表す基本的な量で, 入力密度という. 待ち行列ではこれを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho\, } で表すことが多い. 例えば, 単位時間当たりの平均到着人数を$\lambda \,$, 1人当たりの平均サービス時間を${\overline {S}}\,$とすると, $\rho =\lambda {\overline {S}}\,$である. $\rho >1\,$のときは, 待ち行列は確率1で無限に大きくなり安定ではない. $\rho =1\,$の場合も, 一般には安定でないが, 特殊な場合には安定となることがある.

　これらの安定性の数学的な証明は, 定常な入力を表す確率過程が必要であり, 通常マーク付き点過程が用いられる. 基本的には, 大数の法則を適用して, $\rho <1\,$ならば, 確率1で系内総仕事量がいつか$0\,$となることを示す. ただし, 系内総仕事量の標本関数の変化を単純に追っていくと複雑で難しい. そこで, 定常な系内仕事量過程をうまく構成し, この定常過程が元の仕事量過程とある時間以後一致することを証明する [5]. このように, 2つ確率過程がある時間以後一致することをカップリング (coupling) と呼ぶ. カップリングは吸収 [6] ともいい安定性を証明する有力な方法の1つである. 待ち行列システムがマルコフ過程でモデル化できる場合には, マルコフ過程が定常分布を持つための条件を使って安定性を論じることができる. このとき, 一般に状態空間はベクトル値であり扱いにくいので, 状態空間から実数の集合への関数を使って安定性を調べることもよく行われる. この関数をリヤプノフ関数と呼ぶ.

　定常な入力を持つ単一システムの安定性は, 複数の客のクラスがあったり, 優先権付きのようにクラスによってサービス順序が異なる場合でも, 仕事量保存型サービスである限り, システム全体としての安定性の条件は変わらない. ただし, 入力密度$\rho \,$は客の種類ごとの入力密度の和となる.

　単一ノード待ち行列では, 窓口数(サーバの数)が複数の場合でも, 客が待っている限り窓口に空きがなければ基本的に単一窓口の場合と同じである. 例えば, 窓口数を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c\, } 個とすると, 入力密度$\rho \,$に対して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho < c\, } ならばシステムは安定である. 単一ノード待ち行列であっても, サーバが休止したり, 客が途中で退去する場合には, 安定性の条件は複雑になる. ただし, サーバが休止するバケーションモデルでは, サーバの休止する条件が, システムが空になったり, 系内人数が与えられた一定の数より小さくなる場合のときには, 安定性の条件はサーバの休止がない場合と同じである.

　待ち行列ネットワークの安定性は, 単一ノードの安定性とは様相が異なる. 1つには, 一部のノードは安定であるが, 残りのノードは安定でない場合が起こりうる. これを待ち行列ネットワークの部分的安定性と呼ぶ. 定常分布の言葉でいえば, ネットワーク状態の定常分布は存在しないが, 周辺分布に関する定常分布は存在することに等しい. 別の問題点は, 次のようなネットワーク特有の問題が生じることである.

(i)　各ノードへの到着過程が前もってわからない. サーバが移動するモデルでは, サーバが窓口にいる時間が前もってわからない.

(ii)　ノード間の干渉により, 各ノードを個別に見たときには平均的には安定に見える場合でも安定とならない場合がある.

(i)の例に1人のサーバが各ノードに移動してサービスを行う巡回型のモデルがある. 巡回型ではサーバの移動時間があることと, サーバの到着したノードに客がいないときには待たずに次のノードに移動するために, 各ノードの窓口稼働時間がわからない. Borovkov [2] は1回のサービスを1人に制限したモデルで, 各ノードへの到着がポアソン過程に従い, サーバが推移確率$p_{ij}\,$でノード$i\,$から$j\,$へ移動する場合について, 以下の安定性条件を得ている. $\{\pi _{j}\}\,$を$P=\left(p_{ij}\right)\,$の定常分布とする. ノード数$M\,$は有限と仮定するので, 必ず構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \pi_i\, } が存在する. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_i\, } をノード構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } への客の到着率とするとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho_i = \lambda_i/\pi_i\, } が小さいものから大きいものへとノードのラベルを$1,2,\ldots ,M\,$と付け替える. ネットワーク全体での平均歩行時間を${\overline {U}}\,$, ノード構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } での平均サービス時間を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{S}_i\, } とし,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_k = \overline{U} + \sum_{i=k+1}^M \overline{S}_i \pi_i, \qquad \nu_k = 1 - \sum_{i=1}^k \lambda_i \overline{S}_i, \qquad k=1, 2, \ldots, M, \, }

とすれば, $\rho _{k}<\nu _{k}/u_{k}\,$ $(k=1,\ldots ,M)\,$が安定であるための必要十分条件である.

　ジャクソンネットワーク}やBCMPネットワークでは, トラヒック方程式を解いて各ノードへの到着率を計算すれば, ネットワーク全体の安定性を調べることができる. ただし, 部分的安定性を調べるためには, 安定でないノードの退去率はサービス率に等しくしてトラヒック方程式をたて直す必要がある. 客にクラスがない場合には, 同様な結果が一般化ジャクソンネットワーク (generalized Jackson network, ジャクソンネットワークにおいて, 各ノードでのサービスは先着順とし, 到着過程の時間間隔やサービス時間を一般分布に拡張したもの)に対しても成り立つ [1].

　複数の客のクラスがある場合には, 対称型のサービス規律以外では(ii)が起る場合がある. 例えば, 各ノードは単一窓口で, 先着順サービスまたはクラス別に優先権を付けたサービスを行うとする. この場合に, 2つのノード間で退去した客が戻ってくる経路があるとき, 各ノードの総入力密度が1より小さくても, 安定とならない場合がある. これは, 2つのノードが交互にサービスができないような状況が生じているためである [3].

　一般に複数の客のクラスがある場合に安定性を調べることは難しい. そこで直接調べるのではなく, 流体近似過程を使って安定性を調べる研究が進められている. 例えば, 複数のクラスを持つ一般化ジャクソンネットワークにおいては, どのような初期条件に対してもこの流体近似過程がネットワークが空になる状態に到達するときにのみ安定性が成り立つ [4].

---

参考文献

[1] F. Baccelli and S. Foss, "Stability of Jackson-type Queueing Networks, I", Queueing Systems, 17 (1994), 5-72,

[2] A. A. Borovkov, Ergodicity and Stability of Stochastic Processes, translated by V. Yurinsky, John Wiley & Sons, 1998.

[3] M. Bramson, "Instability of FIFO Queueing Networks" Annals of Applied Probability, 4 (1994), 414-427.

[4] H. Chen, "Fluid Approximations and Stability of Multiclass Queueing Networks: Work-conserving Disciplines" Annals of Applied Probability, 4 (1995), 637-665.

[5] R. M. Loynes, "The Stability of a Queue with Non-independent Inter-arrival and Service Times", Proceedings of the Cambridge Philosophical Society, 58 (1962), 497-520.

[6] T. Nakatsuka, "Absorbing Process in Recursive Stochastic Equations", Journal of Applied Probability, 35 (1998), 418-426.