8.5.1.大域バランス（３）：Quantitative System Performance

待ち行列ネットワークへの助走

「8.5.1.大域バランス（２）」の続きです。（目次はこちら）

大域バランスの詳細
　大域バランス解法は待ち行列のかなり一般的なネットワークの解を計算するために用いることが出来る。この手法はある「状態」から別の状態へのシステムの遷移を解析することに基づいている。
　待ち行列ネットワーク・モデルのサービスセンターの状態をそのキューでの客の順番であると定義する。例えば、２つのクラスA客と１つのクラスB客を持つネットワーク内にあるサービスセンターの実現可能な状態は

  • (AAB)、(ABA)、(BAA)、(AA)、(AB)、(BA)、(A)、(B)、()

である。サービスセンターの状態はどの客が処理中でありどの客が待っているかの情報を提供する。若干の場合、状態記述はキュー内の客の順序に関する情報を含む必要はない。例えば、上記のキューがクラスAがクラスBに優先するようにスケジュールされているのであれば、クラスAが最初に処理されるのは確かなので客の順序を挙げる必要はない。
　待ち行列ネットワークの状態をその全てのサービスセンターの状態の組合せであると定義する。直感的には、待ち行列ネットワークの状態は、その時のモデルの振る舞いを決定するのに必要な全ての情報を含んでいる。
　待ち行列ネットワークの状態空間を実現可能な状態の集合であると定義する。例えば、２つのサービスセンターと３つの客を持つ１つの客クラスを持つモデルの状態空間は

  • (3;0) (2;1) (1;2) (0;3)

である。ここで個々のペアの最初の数字はセンター１での客の数を表し、２番目はセンター２での数を表す。一般に、待ち行列モデルの実現可能な状態の集合は、ネットワーク内の個々のクラスの客の数と、個々のクラスが訪問するサービスセンターと、さまざまなセンターのスケジューリング規律によって決定される。
　状態遷移を、モデル内部の客の動きによって引き起こされた、状態の１つから別のものへのモデルの動きであると定義する。例えば、上のモデルが状態(3;0)に仮にいたとして、その客のうちの１つがセンター１で処理を完了してセンター２に進んだ場合に、それは状態(2;1)に移る。待ち行列ネットワークを解析する際になされる普通の仮定はそれらが１ステップ動作を示す、つまり個々の状態遷移は厳密に１つの客の動きを伴っている、ということである。よって、ネットワークは状態(3;0)から状態(2;1)へは進むことが出来るが、状態(1;2)へは（直接には）出来ない。コンピュータ・システムのどんな２つのジョブであっても正確に同じ時刻に場所を変わるというのは非常にありそうにないことなので、１ステップ動作は理にかなった仮定である。
　特定の状態遷移に関連した状態遷移レートを、ネットワークが開始状態にあるとした時に遷移が起きる瞬間的なレートであると定義する。例えば、もし上のモデル内のセンター１が２の処理時間（０．５の処理レート）を持ち、客は常にセンター１と２の間を行ったり来たりするならば、(3;0)から(2;1)への遷移に関連するレートは０．５である。一般に、状態遷移レートは動く客が出発するセンターでのその客の処理時間と、このセンターを離れる客が即座に別の特定のセンターに進む確率に依存する。単一クラス・モデルについて我々はレート\mu_ip_{i,j}で

  • (n_1;...;n_i+1;...;n_j-1;...;n_K)\rightar(n_1;...;n_i;...;n_j;...;n_K)

を持つ。ただし\mu_iはセンターiの処理レートでありp_{i,j}はセンターiを離れる客が直接センターjに進む回数の割合である。
　任意の待ち行列ネットワーク・モデルを与えられた時、モデル入力から、その状態と、関連する状態遷移と、状態遷移レートを計算することが出来る。そのように記述されたモデルの解は、任意の状態へのネットワークのフローのレートはその状態からのネットワークのフローのレートに等しくなければならないという状態空間フロー・バランス仮定を設定することにより、得ることが出来る。（この仮定は、状態空間レベルでネットワークに適用した、第３章のフロー・バランス仮定によく似ている。）　状態SからのフローのレートはSで費やした時間の割合にSからの状態遷移レートの合計をかけたものである。状態Sへのフローのレートは、ネットワークの全ての状態に渡っての、その状態で費やした時間の割合かけるその状態からSへの状態遷移レートの、合計である。

「8.5.1.大域バランス（４）」に続きます。