8.5.1.大域バランス(1):Quantitative System Performance

8.5.階層的モデル化の適用」の続きです。(目次はこちら

8.5.1.大域バランス


 クローズド非分離可能ネットワークを評価するのに用いられる一般的な解析的手法は大域バランスと呼ばれる。大域バランス解法はこれらのモデルの振る舞いを記述する線形方程式の多くの組を作成して解くことを含む。この手法は膨大な数の方程式と未知数が含まれるため、だいたいの場合実行できないくらい高価である。大域バランスはネットワークの状態ごとに1つの方程式を要求し、ここに状態は(だいたい)サービスセンターでの客の配置である。よって、K個のセンターとC種類のクラスを持つモデルは少なくとも

  • \prod_{c=1}^C\left[\begin{array}{c}N_c+K-1\\K-1\end{array}\right]

個の方程式と未知数を持つ。ただし\left[\begin{array}{c}n\\p\end{array}\right]n個のものからp個を選ぶ仕方の数を示している。このサイズの連立方程式は一見控えめなKC\vec{N}についてであってさえも管理しがたいものである。例えば、6個のサービスセンターと5つのクラスと、個々のクラスにそれぞれ5個の客を持つネットワークは10^{12}以上の状態を持ち、よって大域バランスを用いて直接解くことは出来ない。
 モデルの規模とともに状態空間の規模が迅速に増加することの意味は、大域バランスは非常に小さなモデルにのみ適用可能であるということである。しかしながら、大規模の一般のモデルの近似解は、大域バランスと階層的分解の組合せによって得ることが出来る。大きなモデルは部分に分解され、それらの各々が独立に解析出来る。これらの個々の解は次にFESCを用いた単一のモデルに組み合わされ、このずっと小さなモデルの解は大域的バランスによって得られる。
 例として、図8.4は3つのサービスセンター(1つのCPUと2つのI/Oデバイス)と2つの客クラスを持つモデルを示す。両方のI/Oデバイスはキューイング・デバイスであるが、CPUはクラスAがクラスBに優先するようにスケジュールされる。(到着したクラスA客は、もしセンターにクラスAの客がいないならば即座に処理に入り、さもなければそれらのクラスA客の後で待つ。) 優先スケジューリングのために、モデルは分離可能ではなく、よって第7章のMVA手法を用いて評価することが出来ない。

  • V_{A,CPU}=17V_{A,Disk1}=15V_{A,Disk2}=0
  • N_A=1S_{A,CPU}=15S_{A,Disk1}=20S_{A,Disk2}=
  • D_{A,CPU}=240D_{A,Disk1}=300D_{A,Disk2}=0
  • V_{B,CPU}=11V_{B,Disk1}=4V_{B,Disk2}=6
  • N_B=2S_{B,CPU}=13S_{B,Disk1}=20S_{B,Disk2}=50
  • D_{B,CPU}=143D_{B,Disk1}=80D_{B,Disk2}=300
  • 図8.4 大域バランス・モデル


 クラスcのセンターkでの処理要求時間、D_{c,k}は訪問回数、V_{c,k}と1訪問あたりの処理要求時間、S_{c,k}の積であることを思い出そう。分離可能モデルでは、同じ積D_{c,k}を持つV_{c,k}S_{c,k}の全ての組合せについて性能尺度は同じなので、我々はD_{c,k}のみを話す。非分離可能モデルでは、同じ積D_{c,k}を持つV_{c,k}S_{c,k}の異なる組合せでは一般に、異なる結果を生みだす。よって、図8.4の非分離可能モデルを指定するためにはV_{c,k}S_{c,k}を提供しなければならなかった。個々のジョブはCPUで始まり、終わると我々は仮定するので、個々のクラスについてCPU訪問回数はディスク訪問回数の和より1多い。この情報はモデルの厳密解を得る際にのみ使用される。つまり我々の階層的近似は処理要求時間のレベルでモデルを考察する。

8.5.1.大域バランス(2)」に続きます。