クローズド待ち行列ネットワークにおけるノートンの定理（１）

これは、Sanjay Kumar Boseという方の本「An Introduction to Queueing Systems」の一部を翻訳したものです。
この翻訳した部分http://www.iitg.ac.in/skbose/qbook/ch5_sample.pdfは英語でウェブに公開されているので、日本語に訳しても著作権の侵害に当たらないと判断しました。問題があれば削除しますので、問題を発見された方はご連絡下さい。

クローズド待ち行列ネットワークにおけるノートンの定理

　クローズド待ち行列ネットワークの解析のためのノートンの定理は、電気回路の解析におけるノートンの定理のアナロジーからひらめきを得ている。電気回路の解析におけるノートンの定理では、複雑な回路が負荷インピーダンスを駆動する並行インピーダンスを持つ電流源としてコンパクトに表現される。その電流源とその並行インピーダンスは次にその効果が研究される必要がある、負荷インピーダンス以外の回路の残りを、つまり負荷にかかる電圧とそれを通る電流を、表す。
　クローズド・ネットワークについてのノートンの定理は本質的に類似の機能を遂行する。それは基本的に個のFCFS指数処理待ち行列とそのネットワークを巡回する個のジョブ／客を持つクローズド待ち行列ネットワークを待ち行列の一つ（ネットワーク内の任意の待ち行列）の性能や待ち行列のサブネットワークの性能が容易に研究出来るように簡約するテクニックである。この方法に従うと、指定されたサブネットワーク内の待ち行列以内の全ての待ち行列を単一のフロー等価サーバ（ＦＥＳ）で置き換えることにより、より小さな等価ネットワークを得ることが出来る。この方法[CHW75]の著者ら（ChandyとHerzogとWoo）は若干のタイプのシステム・パラメータについて、等価ネットワークの動作が元々のネットワークの動作と厳密に同じになることを示した。これはChandy-Herzog-Wooの理論として知られており、次に示す。この方法はまた一般処理時間を持つFCFS待ち行列のクローズド・ネットワークについての近似として拡張することも出来る。それは他の処理規律を持つネットワークにも拡張出来、複数の客クラスを持つネットワークにも使用出来る。しかし、このセクションで我々は単一ジョブ・クラスを持ち、指数分布の処理時間と確率的ルーティングを持つ、単純な、クローズド待ち行列ネットワークに我々の議論を制限する。
　そのようなクローズド待ち行列ネットワークへのノートンの定理の適用を示すために、図5.13の例のネットワークを考察しよう。そこで我々は待ち行列を、その性能を研究する必要がある待ち行列であると指定した。（たった１つの待ち行列の代わりに研究すべき待ち行列のサブネットワークを考察することも可能であることに注意。）

• 
• 図5.13. 簡約前の元々の待ち行列ネットワーク

　我々が待ち行列を様々な仕方で特徴づけ、これが待ち行列の性能とネットワーク全体のスループットにどのように影響を与えるかを見たいという状況を考察しよう。例えばこれはにおける処理レートを変えることによってなされるだろう。のさまざまな特徴づけについてその待ちの統計を得ることは、もしクローズド待ち行列ネットワークの残りによりコンパクトな表現を、望ましくは単一待ち行列として、与えることが出来るならば簡略化されるだろう。待ち行列以外の待ち行列ネットワークの残りのそのようなコンパクトな表現を得るためにノートン簡約化のテクニックがこのネットワークに適用出来る。この簡約化のこの目的の最終目標は図5.14で与えられるネットワークを得ることであり、その図では以外のサブネットワークは状態依存処理レートを持つ単一待ち行列で置き換えられている。ただしはその待ち行列内のジョブ数である。この待ち行列は（以外の）ネットワークの残りと置き換えられる等価な待ち行列のフロー等価サーバ（ＦＥＳ）とも呼ばれる。それがフロー等価サーバと呼ばれる理由はそれが単一待ち行列によって待ち行列のそのサブネットワークを表しており、そのサブネットワークからの総フローについてそれは等価であるからである。しかしながら、クローズド・ネットワークが持っていると思われるジョブ数に等価の実際の性質は依存していることに注意すべきである。つまり、フロー等価サーバの等価処理レートはネットワーク内を巡回するジョブの数に依存して変化する。

• 
• 図5.14.フロー等価サーバがある等価ネットワーク