待ち行列：BCMP Network(2) 文献調査

トラフィック方程式から各ノードへのクラス別の到着率が求まったので、特性量を求めていきます。今回は平均値解析法で、平均滞在時間、スループット、平均系内人数を求めていきます。そのための文献を書いておきます。

(1) 平均値解析法のアルゴリズム(複数クラス)
平均値解析法について、わかりやすい文献をあげておきます。

1. 笠原正治、5 章 待ち行列ネットワークモデル
http://www.ieice-hbkb.org/files/05/05gun_01hen_05.pdf
日本語なので、全体の概略を掴むのにいいかも。P13から畳み込み法と平均値解析法に触れているが、複数クラスには触れていない。

2.  著者不明、BCMP Networks
http://www.cas.mcmaster.ca/~downd/BCMP.pdf
英語だが、BCMPの分類がわかりやすい。定常分布などあるが、平均値解析法などアルゴリズムには触れていない。

3. Simonetta Balsamo, Andrea Marin, Queueing Networks
http://www.sti.uniurb.it/events/sfm07pe/slides/Balsamo.pdf
詳しく書いてあって良い資料。残念ながら、畳み込み法と平均値解析法の部分で複数クラスでの取り扱いがよくわからなかった。

4. Kumar, Jitendra, and Vikas Shinde. "A Comparative Study of Mean Value Analysis and Convolution Algorithm for Queueing Networks."
https://pdfs.semanticscholar.org/0e61/2030cdebbb13dc59055ea4a8c9ea285056ad.pdf
非常によくまとまっていて、すごく参考になった。アルゴリズムも明確に書かれていて、今回はこれを一番参考にした。具体例も載っていたので、数値計算の確認もしてみたい。ただ一つ、P15, Step2.2の式でKr(人数)の扱いが書いてなかったので困った。

5. 著者不明、Mean Value Analysis
http://www.cs.ucr.edu/~mart/204/MVA.pdf
4でのKrの取り扱いがわからなかったので、これも参考にした。表現は違うが、これも非常にわかりやすく書いてある。P8の下から複数クラスの閉鎖型モデルの説明が始まる。これも表現は同様であったが、アルゴリズムがさらに詳細に書かれてあった。P10のアルゴリズムでは、n=(n1,...,nc)でnが現在人数を超えない(アルゴリズムでは1からNまで増やすので)値で総組み合わせでやるということになります。クラスが2つなら、クラス1とクラス2の人数の和が現在人数nと言うことです。

6. Chereddi, Chandrakanth. Mean Value Analysis for Closed, Separable, Multi Class Queueing Networks with Single Server & Delay Queues. Technical report, University of Illinois at Urbana-Champaign.
https://pdfs.semanticscholar.org/e66b/edb8ad6548e45fe9da56d188dde7da7cbcaa.pdf
これもアルゴリズムの確認で使いました。３章にあるアルゴリズムで同様に確認しました。

文献では、1,2,3で概要を把握、４を中心にアルゴリズムを確認し、5,6で細かい部分を補った形です。