待ち行列：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で細かい部分を補った形です。

待ち行列：BCMP Network(1)

BCMPネットワークについて考えていきます。
BCMP ネットワークでは待ち行列ネットワークが拡張されています。開放型、閉鎖型の両方が表現でき、複数の客クラスを持てます。またサービスについても、FCFS(First Come First Served)、プロセッサーシェアリング、LCFS-PR(Last Come First Served with Preemption)、無限サーバがありますが、ここではFCFSを扱います。

(1) 今回のモデルの特徴をまとめると下記になります。

• 閉鎖型待ち行列ネットワーク。ノード数：m、ネットワーク内客数：N
• 複数の客クラスを持つ。クラス数：J
• 各ノードでのサービスはFCFS。サービス時間はμi(ni)の指数分布に従う(全ての客クラスで共通)

(2) 推移確率の定義
ノード：i、クラス：μから、ノード：j、クラス：νに移動する確率を次のようにする。

クラスの集合Tを次のように定義しておく。

推移確率は次を満たす。

推移確率行列Rは上記になります。ノードへの移動の推移確率行列のブロックが、クラス推移に対してそれぞれ存在します。

(2) ノードiへのクラスμの客の総到着率：トラフィック方程式を解く(閉鎖型)
ノードiへのクラスμの客の総到着率を求めるために、トラフィック方程式 α = α R (閉鎖型)を解いていきます。ここでαはクラス別にm個のノードを並べたm * J 個のベクトルです。

トラフィック方程式の右辺は下の式になります。

これを計算すると、m * J個のベクトルができますが、それぞれの成分はαとRの列(To Class)の内積になります。簡単に書くと、次のようになります。

最初の第1成分だけ取り出して見ると(上の図の一番左側)、m個のベクトルができます。この時、(1) クラスを固定、(2) ノードkを動かして計算していきます。

To Class 1だけで考えると、上記のm個のベクトルができるので、これをTo Class 全てで考えると、m * J 個のベクトルができます。

つまり、ノードi、クラスμにおけるトラフィック方程式を成分で書くと、

この m * J 個の連立方程式を解くことになります。この場合、解は相対値で出てきますが、解を固定するために、α11 = 1とおきます。

を式変形すると、Rの転置行列を使って、次のように変形できます。

さらに、α11 = 1とすると、式変形ができますが、簡単に４行４列でやった場合が次になります。

つまり、転置した行列の第１行と第１列要素を取り除いた行列を作成し、右辺に転置行列の第１列の第２成分から全てを書きます。転置前の行列では赤の部分になります。

(3) トラフィック方程式を実際に求める
簡単に考えるために、客は２クラスで同じ推移確率で動くとします。ノード数は12です。クラス間の移動は無いものとします。
例えば推移確率行列を図のように作ってみました。

緑の部分はクラス1からクラス１へのノード間推移確率行列です。右上と左下のグレーの部分はそれぞれ、クラス1 -> クラス2、クラス2 -> クラス1へ移動する場合のノード間推移確率です。クラス間の移動が無いため、全て0となります。右下の黄色の部分はクラス2でのノード間推移確率になります。ノード数が12、クラス数が2のため12*2=24、24*24の推移確率行列になります。

次にトラフィック方程式用の行列を用意します。上でも書いた通り、Rを転置して、１行、１列の要素を全て取り除き、対角要素は-1したものです。(m * J -1) × (m * J -1)の大きさになります。

実は、このようにクラス間移動が無い場合、閉鎖型待ち行列ネットワークのモデルとして、うまくないです。このようにクラス間移動がない場合、閉鎖型待ち行列ネットワークが２個あるのと同じになります。ノードの平均系内人数は足し合わせたものになります。（これは今の僕の考え。変わるかも）
実際これをα11=1として解いてみてもクラス1は数値が求められますが、クラス2は全て0となってしまいます。クラス2のα12=1としないと求められないです。
エクセルファイル
[確認事項]
・クラス間の移動が無くても、大丈夫なはずなので、トラフィック方程式を確認(クラス間の移動がない場合、クラス2でもα12=1としないといけないか？式変形の問題なので計算してみる)

BCMPモデルとしてクラス間の移動があった場合の方がモデルとして適していると考えます。そこで次のような推移確率行列を定義します。

クラス1でノード5,10に来た客は退去するとクラス2に移動します(右上の赤い部分)。またクラス2でノード1,6,11に来た客はクラス1に移動します(左下の青い部分)。
推移確率行列csvファイル
これを転置して、対角要素から-1をしておきます。

試しにエクセルのソルバーで解いてみます。今回はα11-α122までの24個のベクトルがあり、次のようになります。
・初期値は全て1
・αベクトルと転置して-1した行列の行との内積をとります。

目的関数は|α11-1|としておきます。変数はαのベクトルです。
・α11=1
・各内積=0

プログラム(Java)で解いた解とほぼ同じになりました。Javaで解いた解は下記

ソルバー付きエクセルファイル
これでトラフィック方程式の解αが求められ、各ノードの到着率がわかりました。