《待ち行列ネットワークの近似解析》

【まちぎょうれつねっとわーくのきんじかいせき (approximate analysis of queueing network) 】

　積形式解を持たないような待ち行列ネットワークについては, 現在のところ構造を特定したいくつかの例に関して解析結果があるものの, 網羅的な性能評価手法は確立されていない. また, 数値解やシミュレーションにより厳密な特性値を得ようとする場合, 単一の待ち行列に比べてモデルが非常に大きくなるため, 計算コストは膨大なものとなってしまう.

　一方, 応用面では必ずしも厳密な解を必要としない事例も多く, また厳密解が得られない場合の次善の策としても, 特性値の近似解を与える簡便かつ高速な手法が求められている. 簡単な方法としては, 定常分布などの特性が既に知られているモデルを当てはめることも考えられるが, 得られた近似解の誤差評価が困難であるという問題がある. 待ち行列ネットワークに対する近似解析手法はまだ未開拓の部分も多い.

積形式解を持つ閉鎖型ネットワークにおける近似　積形式解を持つ待ち行列ネットワークでは, 理論上は厳密解が得られることがわかっているが, ネットワークに閉路を含む場合には平均値解析法による反復計算を行う必要があり, 系内客数や客のクラスが多い場合, 反復の回数が多くなって計算コストが増大する. これを回避するため, 反復によって求めるべき値を近似式によって与えてしまうという方法が提案されている. 具体例として, 複数クラスの客がいるBCMP閉鎖型ネットワークでの平均待ち行列長の計算を挙げよう. 今, クラスは$C\,$種類, ノードは $M\,$ 個あるとする. クラス $c\ (1\leq c\leq C)\,$ の客は系内に $n_{c}\,$ 人いると仮定し, ${\boldsymbol {n}}=(n_{1},\ldots ,n_{C})\,$ とおく. このときのノード $j\,$ におけるクラス $c\,$の平均客数を $L_{(c,j)}({\boldsymbol {n}})\,$ と書くとき, この値を平均値解析法で得るにはクラス $c\,$ の客が一人少ないときの平均 $L_{(d,j)}({\boldsymbol {n}}-{\boldsymbol {\delta }}_{c})\,$ の値が必要だが, [4]では

${\begin{array}{lll}L_{(d,j)}({\boldsymbol {n}}-{\boldsymbol {\delta }}_{c})&=&L_{(d,j)}({\boldsymbol {n}})\ \ \ \ (d\neq c)\\L_{(c,j)}({\boldsymbol {n}}-{\boldsymbol {\delta }}_{c})&=&{\frac {(n_{c}-1)}{n_{c}}}L_{(c,j)}({\boldsymbol {n}})\end{array}}\,$

と近似して$L_{(d,j)}({\boldsymbol {n}})\,$に関する方程式をたて反復を避ける方法が提案されている. この近似法は各ノードが単一窓口のとき (一部に無限窓口を含んでよい) にのみ適用可能だが, 実装は簡単で計算量を確実に減らすことができる. またこのアイデアを基に, 複数窓口ノードに適用可能な近似法も提案されている [3].

分解近似法　積形式解を持たない待ち行列ネットワークに対して比較的古くから適用される近似の考え方に, 一つの大きな待ち行列ネットワークを, 比較的依存関係の強いと考えられるいくつかの部分ネットワークに分解して計算する方法がある. これが分解近似法 (decomposition methods)と総称される考え方である. 分解近似法は, 積形式解を持つ待ち行列ネットワークに対するノートンの定理が, 積形式解を持たない場合にも成り立つという仮定に基づいている.

　最も単純な分解の仕方は全てのノードの独立性を仮定するもので, 1ノード分解と呼ぶ. 計算機ネットワークの性能評価ツールなどに使われている. 1ノード分解では, 近似の精度は分解したノードへの客の到着過程の近似度合いに大きく依存する. 例えば単純に積形式分解を仮定すると, 到着過程はポアソン過程となり, 平均到着率によって全てが決まる. この点を改善した近似法として, 到着過程を再生過程で近似する方法などが提案されている. 例えばQNAと名付けられた性能評価ツールでは, 退去過程の特性を使って到着過程を再生過程で近似する. このとき, 各ノードはGI/G-型の待ち行列となるので, 更に拡散近似により近似する方法が採られている.

　ノード間に多少の依存関係を取り入れる場合には, 2ノードあるいはそれ以上を一つの部分ネットワークとして分解する. 1ノード分解に比べ近似精度は通常大幅に向上するが, 分解の方法と近似精度との関連など, まだ未知の部分が多い. この種の分解近似法の具体例には, Kühn [2] の分解法, 高橋 [5] によるクロス縮約法 (cross aggregation method) などがある.

最大エントロピー法　定常分布の近似値を求める問題は, 「与えられた条件を満たす最適な確率分布 $\{p(i)\}\,$ を求める問題」であると言える. この最適という尺度を, 情報理論におけるエントロピーの概念で捉えるのが最大エントロピー法の考え方である. 最大エントロピー法は, 以下のように最適化問題として定式化される.

${\begin{array}{lll}{\mbox{max. }}&\displaystyle H(p)=-\sum _{i\in S}p(i)\log p(i)\\{\mbox{s. t. }}&\displaystyle \sum _{i\in S}p(i)\,f_{j}(i)=C_{j},\ \ \ j=1,\ldots ,J\\&\displaystyle \sum _{i\in S}p(i)=1.\end{array}}\,$

ここで $S\,$ は状態空間, $H(p)\,$ はシャノンのエントロピー関数, $C_{j}\,$ は制約条件を与えるために適当に選ばれた関数 $f_{j}(i)\,$ の期待値である.

　最大エントロピー法は前述の分解近似法と組み合わせて用いられることが多い. 例えば, 各ノードが1本の待ち行列を持つときには, 近似的な平均待ち行列長や利用率などを$C_{j}\,$として与える [1].

流体近似と拡散近似　待ち行列ネットワーク過程は通常ベクトル値をとり, 状態空間は多次元ユークリッド空間の部分集合である. 多くの場合, 自然な状態空間をとり確率的経路選択を仮定すると, 境界付近を除く状態空間の内部の点で状態推移は一様になる. そこで, 各ノードで待ち行列が長くなるという仮定の下に, 時間軸と状態空間を縮小して極限過程を求め, それを使って元の待ち行列過程を近似的に解析する方法が考えられている. これらの方法は基本的に重負荷の場合に近似がよいが, 負荷が軽い場合にも使われる.

　縮小のスケールの取り方によって2つの極限過程が得られる. 時間軸を$\textstyle {\frac {1}{n}}\,$に縮小するとき, 状態空間も$\textstyle {\frac {1}{n}}\,$に縮小すると, 大数の法則により, $n\to \infty \,$の極限過程は確定的な関数となる. これを流体近似と呼ぶ. 時間軸の縮小はしないが, 同様に標本関数を平均で決まる確定的な関数で近似する方法もあり, やはり流体近似と呼ばれている. これは, ラッシュアワーなどのように, 時間に依存した現象を表すのに適している. 一方, 時間軸は同じ縮小で, 状態から平均値を引いた値を$\textstyle {\frac {1}{\sqrt {n}}}\,$に縮小すると, 中心極限定理により$n\to \infty \,$の極限過程は拡散過程となる. この種の拡散過程は, ノードが複数窓口の場合や客に複数のクラスがある場合も含め広く研究されている. ただし, これらは多次元の拡散過程であり, 一般に定常分布などを求めることができない. したがって近似解析として使うためには, 更にシミュレーションやマルコフ連鎖の数値解法を援用する必要がある.

軽負荷近似　流体近似や拡散近似とは逆に, 非常に負荷が軽い場合には, ネットワーク内の客が少ない. 特に数名の客ならば全ての客の状態推移を追っていくことが可能である. したがって, 時間軸を到着に関してのみ拡大すれば, 状態確率を漸近的に求めることが可能である. これを軽負荷近似と呼ぶ. ネットワークモデルでは, 軽負荷近似の精度を上げようとすると, 計算が指数的に複雑化するという欠点がある.

---

参考文献

[1] D. D. Kouvatsos and N. P. Xenios, "MEM for Arbitrary Queueing Networks with Multiple General Servers and Repetitive-Service blocking", Performance Evaluations, 10 (1989), 169-195.

[2] P. Kühn, "Approximate Analysis of General Queuing Networks by Decomposition", IEEE Transactions on Communication, 27 (1979), 113-126.

[3] D. Neuse and K. Chandy, "SCAT: A Heuristic Algorithm for Queueing Network Models of Computing Systems", ACM SIGMETRICS Performance Evaluation Review, 10 (1981), 59-79.

[4] P. Schweitzer, "Approximate Analysis of Multiclass Closed Networks of Queues", International Conference on Stochastic Control and Optimization, Amsterdam, 25-29, 1979.

[5] Y. Takahashi, "Aggregate Approximation for Acyclic Queueing Networks with Communication Blocking", in Queueing Networks with Blocking, H. G. Perros and T. Altiok, eds., Elsevier Science Publishers B. V., 1989.