JPH08293876A - 共有リソースへのオーバーロードに対する保護機構を有する効率的な複数のサービスのグレードの供給 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】 リソースの共有利用者に異なったグレードの
サービスを提供し、かつオーバーロードに対して利用者
を保護する。 【解決手段】 共有リソース２０１への加入許可を制御
し２０３、２０６、新規利用者に見合うリソース容量の
調整を行い、障害の起きたリソースから代替リソースへ
振替を行う。それぞれ、積行列定常状態分布を有するリ
ソース共有モデルを解くため、ブロッキング確率コンピ
ュータＢＰＣ２０４使用する。各利用者２０２は、要求
のソースであり、上限及び保証された最低の限界がサー
ビス要求に対して割り当てられる。所望のブロッキング
確立は、積行列定常状態に現われる規格化定数によって
直接表現される。ＢＰＣでは、まず規格化定数の母数
（Ｚ変換）を作り、母数を数値反転して規格化定数を計
算する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数の利用者（cu
stomer）が共有する有限リソースのために、オーバーロ
ードに対する保護機構を有することを特徴として効率的
に複数のサービスのグレードを供給することに関し、特
に、（ｉ）いつ新たな見込み利用者に、望まれたグレー
ドのサービスでリソースを使用することを認めるまたは
許容するかを制御すること、（ｉｉ）利用者需要の変化
に即応してリソースの容量を調整すること、（ｉｉｉ）
リソースの障害に応答することとに関する。

【０００２】

【従来の技術】一般に、リソース共用の問題では、複数
の利用者にサービスを供給する複数のリソース「装置」
からなる「リソース」を１つ以上含んでいる。各々の利
用者は一連の、あるいは一続きの「要求」の発生源であ
る。各々の利用者要求は、各々のリソースからいくつか
の装置を必要とする。そのリソースは、０あるいは１以
上であってもよいし、異なる利用者に対して異なっても
よいが、同じ利用者の異なる要求に対しては同じであ
る。新たな要求の到着にすべての要求物を満たすことが
できる場合は、その新たな要求は認められ、すべての要
求されたリソースユニットは要求保留時間の間ずっと予
約、あるいは保留される。満たせなければ、その要求は
認められず、「ブロック」されたとされる。

【０００３】上記のリソース共用は、通信ネットワーク
やコンピューターシステムなど多くの物理的な設定で発
生する。回線交換通信ネットワークでは、利用者が異な
る「サービス」（つまり、音声、データ、映像やファッ
クス）と結び付けられ、要求が「コール」となる一方、
リソースが「リンク」で、リソースユニットがこれらの
リンク上の「回線」となるかもしれない。コールは、コ
ールの起点と目的地に依存した固有のリンクと共に、い
くつかの異なるリンク上で回線を同時に要求することが
しばしばある。いくつかのサービスでは、コールはそれ
ぞれのリンク上に複数の回線を要求する。

【０００４】回線交換ネットワークの一例は、図１に示
されている。この図では、５個のノード１０１−１０５
があり、リンクｉにＫｉ個の回線を持って、５個のリン
ク１１１−１１５がある。（このケースではノードは何
の役割もしない。）このネットワークは、複数の利用者
にサービスする。その利用者は、要求するリンクの組あ
るいは「ルート」によって部分的に特徴付けられる。例
えば、図１の設定では、以下のリンクのサブセットを要
求する６本のルートが考えられる。 ルート リンク １ １１１ ２ １１２ ３ １１１、１１２ ４ １１３、１１５ ５ １１４、１１５ ６ １１１、１１３、１１５

【０００５】同じルートに複数の利用者が存在できるの
で、利用者は、それよりずっと多くいると思われる。例
えば、ある利用者達はそれぞれのリンク上に一本だけの
回線を要求するかもしれないし、一方、別の利用者たち
はそれぞれのリンク上に複数本の回線を要求するかもし
れない。より具体的には、ある種のデータサービスコー
ルは、それぞれのリンク上に６本の回線を必要とする
が、一方、一般の音声コールではそれぞれのリンク上に
一本だけの回線しか必要としない。この設定では、一人
の利用者が、ある特定のルート上のコールのクラス（音
声かデータのいずれか）を代表する。このように、６本
のルートそれぞれに、一人の音声利用者と一人のデータ
利用者がいて、合計１２人の利用者ということになるだ
ろう。ルート１、３および６上の６人の利用者は、全て
リンク１１１を使用し、そこにあるk1の利用可能な回線
を共用する。ルート６上でデータコールを試みた場合、
リンク１１１、１１３および１１５それぞれに６本の回
線を必要とする。仮に、これを試みた時に、これらのリ
ンクのどれかで十分な未使用回線が利用可能でなかった
ら、コールはブロックされる。反対に、ルート１上の音
声コールは、リンク１１１上に一本だけの回線を必要と
する。本発明で提供されるような特別な対策が講じられ
ないかぎり、ルート６上のデータコールは明らかにルー
ト１上の音声コールよりもかなり高い確率でブロックさ
れるだろう。さらに、この設定ではネットワークの提供
者は、異なる利用者に、他の利用者からのオーバーロー
ドに対する保護を含んで、適切なグレードのサービスを
提供出来ることを望んでいる。

【０００６】非同期転送モード（ＡＴＭ）技術により支
持された広帯域総合デジタル通信網（Ｂ−ＩＳＤＮ）に
おいて、リソースは、「開閉器」および他のネットワー
クの機能であり、リソース能力は、これらのネットワー
ク機能で可能な「帯域」であり、一方利用者は接続した
いとするネットワークの見込み「ユーザ」であり、利用
者の要求は、ＡＴＭセル、ＡＴＭセルのバースト、確立
された接続内のＡＴＭセルのバーストと関連した所望の
「有効な帯域」である。図１は、このＢ−ＩＳＤＮの例
に適用することもできる。臨界リソースが開閉器である
場合、ノード１０１〜１０５はリソースである。さらに
一般的には、ノード１０１〜１０５およびリンク１１１
〜１１５の両方が重要なリソースとなる。Ｂ−ＩＳＤＮ
ネットワークが広い範囲のサービス向きであるので、利
用者がかなり異なるトラヒック特性およびかなり異なる
必要条件を有することを許容することが重要である。特
に、異なる利用者からの要求は、異なる数のリソースを
使用するであろう。この状況では、加入許可制御（admi
ssion control）は、現在取り上げている問題を解決し
ようとする以外は公知のものである（Ｊ．Ｗ．ロバート
氏の「マルチサービスネットワークのパフォーマンス評
価および設計（Perfomance Evaluation andDesign of M
ultiservice Networks）」ＣＯＳＴ２２４ファイナルレ
ポート、ヨーロッパ共同体委員会、ルクセンブルグ１９
９２年、参照）。

【０００７】リソース提供者は、２つの根本的な問題に
直面している：第１の問題は、リソースユニットが供給
するのに費用がかかるため、必要以上の容量を持たない
ことが重要であるという明白な事実である。第２の問題
は、問題の確率的性質である。利用者要求のサブミッシ
ョンおよびこれら要求の保持時間は、使用時間上で変化
する不確実な事である。それ故に、利用者の実際の条件
を前もって知ることはできない。しかしながら、利用者
要求と要求保持時間とのパターンは、確率的に予知でき
る。確かに、確率的または推計的なモデルが利用者条件
を示すために使われることは周知である。この限定され
たリソースを有する不確実な環境において、リソース容
量がかなり需要を超えない限り利用者要求をブロックす
ることは避けられなくなる。利用者の「要求ブロッキン
グ確率」、即ち、特定の運転レジームにおいてブロック
される要求の長期の比例に換算して受け取られるサービ
スのグレードを特徴づけるのが普通である。利用者はそ
れぞれ、その要求ブロッキング確率が適切に低いことを
望む。要求ブロッキング確率があまりにも高いと、利用
者条件が満足されない。一方、要求ブロッキング確率が
あまりにも低いと、必要とされるより多くの容量が供給
された。

【０００８】この確率的な設定において、リソース提供
者は：（ｉ）既定のリソース容量のための既定の組み合
わせの利用者の許容性を決定し、（ｉｉ）既定の組み合
わせの利用者ための適切なリソース容量を決定し、（ｉ
ｉｉ）リソース障害のために１つのあるいはもっと多く
のリソースの一時的な有効性にいかにして返答するかを
決定することを必要とする。これらの問題は、それぞれ
の利用者の要求トラフィックが（確立的に）特徴づけら
れ、それぞれの利用者のブロッキングの確率条件が得ら
れる時に考慮される。すべての利用者がリソースに対す
るフルアクセスを持っている時、即ち、「完全共有手
段」が用いられる時、考慮中のシステムのモデルにおけ
る各クラスについてのブロッキング確率を計算する周知
の方法がある。リソース提供者は、一般的な利用者の要
求ブロッキング確率が条件と合致するするか否かををチ
ェックできる。リソース提供者は新しい利用者を入れる
か否か決定して、適切な容量を決定し、リソース不足に
いかにして返答するかを決定するためにこれらの計算を
用いることができる。しかしながら、現在の方法が、モ
デルが大きくなるにつれて、これらのブロッキング確率
を計算することが困難になる。そこで、今までよりもか
なり大きな標準モデルを解ける必要性が残されたままで
あった。

【０００９】モデルが大きくなった場合の困難に加え
て、現在の方法は、要求の到着プロセスが例外的に高い
または低い変異性を有する場合、ブロッキング確率を計
算するのが困難である。リソース共有モデルにおける到
着プロセスの標準的表示は、「ポアソン」過程である。
しかしながら、多くの適用において、利用者要求の到着
プロセスは、ポアソン過程よりもさらにもしくはよりも
少なく変化しやすく、これらの別の形式の到着プロセス
変異性は、利用者要求ブロッキング確率にかなり影響す
る。例えば、高い変異性の到着プロセスは、通信ネット
ワークに別の経路指定が存在する場合に起こるように、
オーバーフロートラフィックに定期的に起こる。このよ
うにして、非ポアソンの到着プロセス変異性を特徴づ
け、正確に利用者要求ブロッキング確率を決定する効果
的な方法が必要である。

【００１０】さらに、リソース提供者は、実際には、周
知の方法がしばしば適用される完全共有手段を用いたく
『ない』と強く動機づけされている。多くの出現するリ
ソースの重要な特徴は、さまざまな利用者の存在であ
る。この設定において、利用者を互いから守ることが非
常に重要である。すべての利用者にリソースへのフルア
クセスを許容した場合、１人あるいはもっと多くの利用
者が交渉された率よりもかなり高い率で要求を提出する
であろう、それは他のクラスにおける他の利用者が利用
不可能なほどの高いブロッキング確率を経験させる。そ
こで、「他の利用者によるオーバーロードから利用者を
守る」ためにいくつかの方法が必要とされる。これを行
う１つの方法は、リソースをそれぞれの利用者に提供さ
れた部分へ「分割する」ことであるが、これは、共同使
用の長所が失われるので非能率的傾向にある。それぞれ
のリソースで必要とされた全体の容量は、完全分割で許
容できないほど大きくなる傾向がある。

【００１１】いくらかの分割を許容する別の利用可能な
制御方式は、１９９３年１２月２８日にバージャ（Berg
er）、ミリト（Milito）およびホイット（Whitt）に発
行された米国特許第５２７４,６４４号に記述されたよ
うな、レート・ベースの多数クラスのアクセス制御方式
である。この方式は、異なった利用者からの認められた
要求を規定するものであるが、それは要求のパターンの
みに基づいている。それは、要求の保持時間を考慮に入
れない。さらに全体的には、それはリソースのカレント
ステートを用いない。特に、そのレート・ベースの制御
は、現在サービスを受けている各利用者からの要求の数
に依存しない。ここで、この追加の情報がリソース提供
者に利用可能である状況を考える。したがって、それが
利用可能である場合、この補足情報を活用する制御装置
を探すことは可能である。さらに、上で引用したバージ
ャーらの特許のレート・ベースの多数クラスのアクセス
制御方式のような方式は、ただ利用者要求の流れを調節
するだけである。リソース提供者はまた、利用者が要求
を送るれるようにするか否か知る必要がある。利用者加
入許可の問題はもまた、主要な問題である。

【００１２】完全共有使用あるいは完全分割の代わり
に、いくらかの共同使用を許容するリソースにおける許
容可能状態におけるさまざまな「制約条件」を考慮する
ことは当然である。１つのそのような方式は、「トラン
クリザベーション」である。例えば、２つのクラスで、
トランクリザベーションが、完全なただの容量が指定さ
れたしきい値以下に降下する際は常に２つのクラスうち
の一方をブロックする。この方式は、一方のクラスから
のオーバーロードに対してもう一方のクラスを保護する
が、両方のクラスを保護するものではない。さらに全体
的には、ｎ個のクラスで、トランクリザベーションの自
然な概括は、ｎ−１個のしきい値が存在する指定された
ｋ^thのしきい値以下に降下する場合にブロックされる第
１のｋ個のクラスを有する。しかしながら、２つのクラ
スのケースのように、すべてのクラスはこの方式で保護
されない。

【００１３】さらに、既知の技法を用いて、「トランク
リザベーション」方式で利用者ブロッキング確率を算出
するのは比較的難しい。トランクリザベーション方式
は、標準モデルを完全供給および完全分割手段を解析で
きるようにするその良好な積行列構造を失わせてしま
う。その他の制約は、ブロッキング確率を算出するのに
深刻な問題を起こす傾向にある。いわゆる「コーディネ
ートコンベックス（coordinate-convex）」共有手段を
もたらす多量の制約は、積行列定常状態分布を有する。
例えば、Ｊ．Ｓ．カフマンの「分割されたリソースの環
境におけるブロッキング（Blocking in a Shared Resou
rce Emvironment）」通信についてのＩＥＥＥトランザ
クション（IEEE Transactions on Communications）１
９８１年、第ＣＯＭ−２９巻１４７４〜１４８１ペー
ジ、しかし、一般的なコーディネートコンベックス方式
のための良好なアルゴリズムは、開発されていない。制
約を有する利用者の要求ブロッキング確率を算出するた
めのアルゴリズムは、２、３の非常に特別なケースです
でに開発されている。

【００１４】異なる利用者で、他からのオーバーロード
に対して保護することばかりでなく、「異なるグレード
のサービス」を提供することができることも重要であ
る。低いブロッキング確率を有し、他からのオーバーロ
ードに対する強い保護を欲する利用者もいる一方、低い
値段で、高いブロッキング確率を有し他からのオーバー
ロードに対して弱い保護の方を好む利用者もいるだろ
う。異なった利用者が各要求ごとに異なる数のリソース
ユニットを要求すると思われるため、同様のブロッキン
グ確率に達することでさえも難しい。他の利用者よりも
多くのリソースユニットを要求する利用者ほど、高いブ
ロッキング確率有する傾向にある。サービスの異なった
グレードは、完全分割により成し遂げられるが、必要と
されるものは、共有を許容する異なるグレードのサービ
スを提供するための「最も有効な」方法である。

【００１５】オーバーロードに対する保護機能を有する
多数のグレードのサービスを提供するための可能な方式
を考慮した場合、他の関連する問題が起こる。まず、リ
ソース提供者は、効果的な「価格決定スキーム」が開発
されるように、「サービスの得られたグレードを供給す
るコストを評価する」ことを望む。このようなコストを
示す異なった方法がいくつかある。重要な方法のひとつ
は、それぞれの利用者によって使われるリソースにおけ
る平均の容量を決定することである。しかしながら、非
常に異なった条件とサービスのグレードとを持つ利用者
がいる場合、それぞれの利用者によって使われる平均の
容量を決定するのに注意深い解析が要求されるであろ
う。普通の使用にだけ基づいただけの推定量では、真の
コストを正確に示すことができないであろう。異なるグ
レードのサービスを提供するために用いられたいかなる
共同使用でも、サービス提供者は、各利用者により使用
される平均容量を計算できるようにしたいであろう。

【００１６】多数のグレードのサービスを効果的に提供
する有効な方式は、「リアルタイムの利用者加入許可制
御」の問題を処理すべきである。規定の限定されたリソ
ースについて、リソース提供者は、各新しい見込み利用
者を加入許可することができるか否かを決定できる必要
がある。多数のグレードのサービスで、リソース提供者
は、すべての既に加入していた利用者が彼等の既に決定
されたグレードのサービスが受けられる状態で、新しい
利用者が加入きるか否かを決定する必要がある。異なる
グレードのサービスを提供するいかなる技法も、加入し
た利用者によって提出された要求における限界をおそら
く設定する（imposes）。限界を「実施する」有効な方
式が必要とされる。チェックが利用者要求それぞれにつ
いてされなければならないので、計算の効率が重大な問
題である。

【００１７】使用時間中、利用者需要のレベルはしばし
ば変化する。サービスのための需要は、増えたり減った
りする。「リソース障害」に直面した需要の一時的移転
も存在する。いくつかのリソース障害の状況では、利用
者は、それらを代替リソースに割り当てることによりサ
ービスを受けることができるが、これは、これらの代替
リソース上の利用者要求を増加させる。これに応じて、
リソース提供者は、これらの他のリソースに容量を加え
る機会を持ってもよい。このような変化している利用者
要求に直面し、リソース提供者は、この需要に合うため
に必要とされる容量の合計を決定するための方法を必要
とする。これは「容量調整プロブレム」である。

【００１８】リソース提供者は、しばしばリソース障害
に応答するために一層複雑な選択肢の組を持つであろ
う。上述したように、利用者は、リソースの代替の組合
せからサービスを受け取ることが可能であるかも知れな
い。いくつかのケースでは、おそらく追加の費用で、他
のリソースですぐに供給してもらえる追加の容量を要求
するであろう。しかしながら、他のケースでは、追加の
容量は十分に速く供給されない。よって、リソース提供
者は、制御できないリソース障害に直面した場合の最良
の可能なサービスを提供することを必要とする。障害の
起きたリソースを用いる利用者が代替リソースに割り当
てられる場合、転送された（diverted）需要からそれら
の他のリソースにおける元の利用者を保護する方法が必
要である。同時に、リソース提供者は、転送された利用
者もまた保護したいであろう。

【００１９】障害の起きたリソースを用いる利用者を応
対するために利用可能な代替リソースを識別するための
方法は数多くある。いくつかの設定では、代替リソース
は明白になる。例えば、システムは、互いのバックアッ
プとしてそれぞれ機能する状態で、単に２つのリソース
のみを含んでいてもよい。他の設定では、通信ネットワ
ークでふさがれたコールの代替経路指定のための方式を
有するケースであるように、新しいリソースに動的に需
要を再配分する適切な自動的なプロシージャであっても
よい。別の可能性は、マンサー（Mansour）およびニュ
ーエン（Nguyen）（米国特許第５，０５８，１０５号）
により開発された代替の経路指定装置のためのアルゴリ
ズムにおけるように、特別な手続きがリソース障害の場
合中央制御装置により実施される必要があることであ
る。集中制御がないところで、分散アルゴリズムは、ま
ずすべてのリソースに障害が起きたことを知らせるこ
と、そして次に適切な代替ルート（リソース割当て）を
設立することを必要とするであろう。

【００２０】代替リソース割当てを生成するために使わ
れた方法にかかわらず、残留しているリソースに元のお
よび転送された利用者両方に保護を提供する必要があ
る。つまり、リソース提供者は、次の多くの問題に直面
している：いかにしてリソースへアクセスを管理および
制御し、そしてオーバーロードに対し効果的に多数のグ
レードのサービスに保護を提供すべきか？いかにして、
異なったグレードのサービスを規定の容量でリソースを
使用する規定の組の利用者に提供すべきか？いかにし
て、規定のグレードを提供する「コスト」（リソースの
使用、容量などに関して）を査定すべきか？いかにし
て、リアルタイムで、それぞれの望ましいグレードのサ
ービスで見込み利用者が加入許可される（べき）か否か
を決定するか？いかにして、新しい組の利用者需要を満
たすために必要とされるリソースの新しい容量を決定す
るか？いかにして、リソース障害に返答するか？

【００２１】

【発明が解決しようとする課題】本発明の目的は、リソ
ースを共有している利用者に異なったグレードのサービ
スを供給し、且つオーバーロードに対して利用者の保護
を供給することである。

【００２２】

【課題を解決するための手段】利用者はそれぞれ、「上
限の」（ＵＬ）および「保証された−最小の」（ＧＭ）
「限界」がその要求に割り当てられる。上限限界は、い
つでもサービスを受けられる利用者からの要求の数に上
限を置く。保証された最小限界は、利用者からの特定数
の要求を守るためにリソース内の利用可能なリソースで
あることを保証する。プロセスは、共同を伴う重要な分
離と呼ばれるものを提供し、完全分割および完全共有に
優れている。

【００２３】ＵＬおよびＧＭ限界における変化も許容さ
れる。代替の限界は、異なった利用者の作動中の要求数
における線形制約に基づくことができる。これらの代替
の限界は、利用者のサブセット（クラス）ごとにＵＬ限
界を含む。「一般的トラフィック条件下でコンピュータ
ネットワークノード環境における共有された有限の記憶
の分析（Analysis of Shared Finite Storge in a Comp
uter Network Node Emvironment Under General Traffi
c Condition）」通信についてのＩＥＥＥトランザクシ
ョン１９８０年、第ＣＯＭ−２８巻、９９２〜１００３
ページにおけるカマン（Kamoun）およびクレインロッッ
ク（Kleinrock）による特定の限定された文脈内に記述
されたＵＬおよびＧＭ限界を用いることにより、コーデ
ィネートコンベックス共有方式が導かれ、その結果得ら
れたリソース共有モデルは、積行列定常状態分布を有す
る。本発明によれば、我々は、このモデルでブロッキン
グ確率を決定するための効果的な方法を見いだし、リソ
ース提供者に直面した種々の問題を解決し、且つＵＬ／
ＧＭ限界はずっとより広い環境に適用された。

【００２４】リソース提供者が利用中の各利用者からの
要求の数を記録する場合ＵＬ限界は容易に実施される一
方、ＧＭ限界は、実施することが一層難しい。本発明
は、ＧＭおよびＵＬ限界両方を実施する「有効な方式」
を含んでいる。ＵＬおよびＧＭ限界は、（ａ）が利用者
によって直接供給される、あるいは（ｂ）他の必要条件
を満たすためリソース提供者によって決定されるかのい
ずれかである。利用者は、そのブロッキング条件および
その所望のトラフィックの特性を供給すると仮定され
る。要求ブロッキング条件は、それらの交渉されたトラ
フィックパラメータによって要求を提出できると仮定し
て、最大の許容されたリクエストブロッキング確率であ
る。利用者のトラフィックは、要求到着率と、平均要求
保持時間と、各リソースに必要とされるユニットの数と
により特徴づけられる。加えて、利用者の要求の流れの
変異性を記述する「バーストパラメータ」もまた、許容
される。標準の想定は、ポアソン到着過程である。バー
ストパラメータは、ポアソン過程より実質的に多いまた
は少ないバーストで到着過程を説明する。加えて、利用
者要求は、状態依存の到着率あるいはバッチ到着を有す
ることができる。状態依存の到着率は、有限ソースの入
力、即ち一定の有限の人工から提出された要求、の重要
なケースを含む。

【００２５】サービスの利用者グレードはまた、別の方
法、特に、いくらかオーバーロードのパターンにある他
の利用者次第のブロッキング条件である「条件付きのブ
ロッキング条件」によって指定される。一例では、一人
の他の利用者のだれであっても任意のオーバーロードに
あるということが与えられた条件付きのブロッキング条
件となる。別の例では、すべての他の利用者がオーバー
ロードにあるということが与えられた、即ち他の利用者
がそれぞれその交渉されたレートより上のレートでトラ
フィックを提出しているということが与えられた条件付
きのブロッキング条件となる。ＵＬおよびＧＭ限界は、
条件付きのブロッキング条件が適合されることを保証す
るために使われる。

【００２６】提案されたグレードのサービスで共用リソ
ースを効率よく管理するために、本発明は、「ブロッキ
ング確率コンピュータ」プロセスを用いて、有効なそれ
らのグレードのサービスでリソース共有モデルを適切且
つ正確に解く。上述したように、ＵＬおよびＧＭ限界を
有するリソース共有モデルは、積行列定常状態分布を有
する。追加の制約による困難を打破するためにに、本発
明は、所望のブロッキング確率が積行列定常状態の分布
に現われる規格化定数（あるいは分割関数値）により直
接表現されるということを利用する。プロセスは、まず
規格化定数の母関数（あるいはｚ変換）を用いて、次に
母関数を数値的に反転することによって規格化定数を算
出する。

【００２７】母関数の数値の反転が困難なため、本発明
は、発明を容易にするためのプロセスを含む。主な困難
は、必要とされた計算が母関数の次数で急速に増加する
ということである。母関数のディメンションは、リソー
スの数に線形制約条件の数をたした数と等しくなる。Ｕ
ＬとＧＭ限界が一般に非常に多くの線形制約条件に対応
するので、単一リソースについてでさえも問題を単純化
する必要がある。我々のプロセスによれば、第１のステ
ップは、各リソース上のロードをおおよそ決定するため
に「正規近似式」を用いる。この予備の近似解析は、そ
れらを考慮からはずすせるように、本質的に制約条件を
供給しないほど軽い負荷のリソースがいくつかあるか否
かを決定する。これらの非常に軽い負荷のリソースは、
母関数を形成する前にモデルから省略される。

【００２８】正規近似式で事前の解析を行った後で、す
べての残留リソースを伴うモデルのための母関数が形成
される。この母関数のための明確な式は、利用者パラメ
ータの関数として決定された。次に母関数の効果的な次
数は、減少される。「条件付きの分解スキーム」は、多
数次数の母関数の変数を反転するための良好な次数（シ
ーケンス）を決定するために使われる。条件付きの分解
スキームは、しばしば母関数の効果的な次数を極端に減
らすことができる。確かに、この条件付きの分解ステッ
プは、完全共有方を有するディメンションより寸法をせ
いぜいもう２つ多い次数に次数を減少するために常にＵ
ＬおよびＧＭ限界と共働する。単に単一リソースのみが
存在する場合、結果として生じるモデルは、ほとんど常
に解くことができる。

【００２９】実質的な数のリソースがある場合、モデル
は、正規近似および条件付きの分解のステップの後でも
解かれていないであろう。モデルがまだ解かれていない
場合は、「減少したロードの固定小数点近似式プロセ
ス」がモデルを解くために用いられてもよい。減少した
ロードの固定小数点近似式プロセスの概念は周知である
が、我々の発明は、ＵＬおよびＧＭ限界を有する単一リ
ソースのサブモデルを正確に解くためにブロッキング確
率コンピュータプロセスに基づいて新しいサブルーチン
を用いる。新しいサブルーチンは、正確に１以上の単一
リソースのサブセットを含むモデルを解くためにも用い
られる。

【００３０】３つの問題リダクションステップが完了さ
れた後、ブロッキング確率を計算するために数値反転が
行われる。モデルが直接解決可能である場合直接的に、
あるいは減少したロードの固定小数点近似スキーム中の
サブルーチンのパートとして間接的にのいずれかで実行
される。我々の発明によれば、反転は（ａ）フーリエ級
数方法と、（ｂ）特にリソース共有モデルに適合した効
果的なスケーリング算法と、（ｃ）切り捨てと、（ｄ）
乗法の効果的な処置と、（ｅ）数多くのクラスおよび大
きなリソース容量が存在する場合、重要な計算の能率ア
ップを得るための規格化定数の共有計算とを用いる。今
記述した手順で、ブロッキング確率コンピュータは、規
定の容量でリソースを使用する既定の組の利用者にサー
ビスに提案されたグレードを提供できるか否かを決定す
る。

【００３１】リアルタイム加入許可制御に関する本発明
の特定の一実施例では、ブロッキング確率コンピュータ
は、新しい見込み利用者が所望のグレードのサービスで
リソースに加入できるか否かをリアルタイムで決定する
ために用いられる。プロセスにおける第１のステップ
は、提案された利用者トラフィックパラメータとＵＬお
よびＧＭ限界とを確保して、見込み利用者のためのサー
ビスの望ましいグレードを決定することである。ブロッ
キング確率コンピュータは、その後すべての（条件付き
および無条件の）ブロッキング条件が見込み利用者とす
べての現在の利用者の両方を考慮して満たされるか否か
決定する。すべてのブロッキング条件が満たされる場
合、リソース提供者はサービスの望ましいグレードで新
たな利用者を加入させる。すべてのブロッキングの条件
が満たされない場合、ブロッキング確率コンピュータ
は、より低いグレードのサービスが実行可能であるか否
かを決定するために使われる。

【００３２】本発明は、利用者需要における変化に適合
するために適切な容量修正を行うためにもブロッキング
確率コンピュータを用いる。指定されたリソースおよび
サービスのグレードを有する新たな組の見込み利用者と
いう条件のもとで、ブロッキング確率コンピュータは、
適切なリソース容量を見いだす。正規近似スキームは、
まず実行可能な容量上の上位限界を見いだすために使わ
れる。そして容量は、必要に応じて変えられたＵＬおよ
びＧＭ限界とともに着実に減少される。ブロッキング確
率コンピュータは、各対象を評価するために使われる。
プロセスは、この方法によって見いだされる最小の実行
可能な容量を生じる。

【００３３】本発明は、障害が起きたリソースの１つを
使用していた利用者が残留しているリソース上で彼等の
需要を満たすことができるように、リソース障害に対す
る効果的な応答を決定するためにもまたブロッキング確
率コンピュータを用いる。ブロッキング確率コンピュー
タは、新たな割り当てが実行可能であるか否かを決定す
る。実行可能でない場合、リソース提供者は容量拡張を
考慮する。もし容量拡大ができない場合は、連続したセ
ットの代替リソース上のトラフィックの比率を変える試
みが行われる。ブロッキング確率コンピュータは、実行
可能な比例を決定するために用いられる。ＵＬおよびＧ
Ｍ限界は、元のおよび変更された利用者に適切な保護を
提供するために用いられる。

【００３４】

【発明の実施の形態】共用リソースにおけるオーバーロ
ードに対する保護機能とともに多数のグレードのサービ
スを提供するための我々の技法には３つの主要な局面が
ある：（Ａ）リアルタイムの利用者加入許可制御と、
（Ｂ）リソース容量および制御限界との調整と、（Ｃ）
リソース障害への応答。上記３つの局面は、上限（Ｕ
Ｌ）および保証された制定（ＧＭ）限界とブロッキング
確率コンピュータとを用いる。３つの局面は、それぞれ
以下に順に論じられる。ブロッキング確率コンピュータ
はセクションＡで加入許可制御と関連して論じられる。

【００３５】Ａ． リアルタイム利用者加入許可制御 本発明に従って配された加入許可制御システムのブロッ
ク図が図２に示されている。リソース２０１（それぞれ
多数の部品を持つ多数のユニットを有する）は、利用者
プール２０２と呼ばれた利用者のソースからの到着を処
理する。時々、利用者プール２０２からの利用者は、リ
ソース２０１（からサービスを受ける）ことを許可され
たいと望む。利用者に加入の許可をするか否かについて
の決定は、開閉器２０６に閉じるか、開けるかを信号で
知らせ、リソース２０１に利用者プール２０２からの利
用者到着を接続するか、もしくはリソース２０１に利用
者に到着アクセスを与えることを拒否する加入許可コン
トローラ２０３によって行われる。加入許可コントロー
ラ２０３はまた、上限（ＵＬ）および保証された制定
（ＧＭ）限界を含んで、サービスのグレードを決定す
る。利用者がリソース２０１への加入を望む場合、利用
者は加入許可コントローラ２０３に加入許可の要求をす
る。この時、利用者は、ブロッキング条件を含んで、彼
の望むトラフィックパラメータとサービスのグレードを
示す。加入許可コントローラ２０３は、新たな利用者を
どのＵＬおよびＧＭ限界で且ついくらで加入許可すべき
か否かを決定するためにブロッキング確率コンピュータ
２０４を始動する。この目的のために、リソース共有シ
ステムの数学モデルが形成され、それは、新たな利用者
と同様にすべての現在の利用者を含む。現在の利用者に
ついての適切なデータは、利用者データベース２０５か
ら加入許可コントローラ２０３によって得られる。ブロ
ッキング確率コンピュータ２０４による計算の結果がす
べてのブロッキング確率がブロッキング条件よ少ないこ
とを示す場合、新たな利用者は加入許可される。この決
定は、加入許可コントローラ２０３によって実行され、
利用者に伝達される。

【００３６】本発明による加入許可制御プロセスの概観
を示す流れ図が図３に図示されている。プロセスは、ス
テップ３０１でリソースとそれらの容量を指定すること
から始まる。ｐリソースが存在する。（ケースｐ＝１で
さえも重要である。）リソースｉは、容量Ｋｉ、１≦ｉ
≦ｐを有する。即ち、リソースｉがＫｉ個のリソースユ
ニットを持っている。（ｐ、K1 、・・・、Kｐが正の整
数であると仮定する。） 次に、ステップ３０２で、現在サービスを受けているす
べての利用者の条件が決定される。特定の条件は、以下
のステップ３０６の説明と関連して記述される。現在サ
ービスを受けているすべての利用者の条件を決定するた
め、リソース提供者は、新たな利用者到着あるいは離脱
に基づいて利用者データベースを更新してもよい。利用
者データベースは、サービスのグレードのパラメータを
含むサービスを受けているすべての利用者のレコードを
含む。

【００３７】サービスのグレードがＵＬおよびＧＭ限界
を用いることによって供給されるとすれば、サービスを
受けている利用者ごとの継続中の基準でこれらのトラフ
ィック限界を実施する必要がある。この機能は、ステッ
プ３０３で行われ、これについては以下でさらに詳細に
記述する。このステップは、ここでは利用者を加入許可
するか否かについての決定を考慮するため、主要なプロ
セスの流れの一部ではない。逆に、トラフィック限界を
実施することは、既に加入許可され要求を提出すること
が許された利用者によって提出された要求を受け入れる
ことを許可するか否かについての決定にかかわる。

【００３８】新たな利用者の事件が発生する場合、「進
め」信号がステップ３０４で生成され、プロセスをステ
ップ３０５に移動させる。新たな事件が現在の利用者の
サービスの完了である場合、その利用者データは利用者
データベースから離され、プロセスはステップ３０２に
戻る。図３に特に示されないが、利用者が彼等のサービ
スのグレードを再度交渉したいとする場合、これはサー
ビス要求の完了として取り扱われる。なお、利用者また
はシステムは、利用者の実際の要求トラフィックをモニ
ターし、利用者が異なったトラフィックパラメータ、例
えば、より高いまたはより低い要求到着率を必要とする
と決定してもよい。サービスのグレードを変えたいとす
る利用者は、すぐに新たな到着が引き続くサービスの完
了としてみなされてもよい。

【００３９】ステップ３０５の結果が新たな到着を示す
なら、ステップ３０６で、サービスの望ましいグレード
と結果として生じる条件とトラフィックバウンドとが決
定される。サービスのグレードは、要求トラフィックの
特性評価を含む。利用者の要求トラフィックの規格特性
評価は、要求到着率と平均要求保持時間によるものであ
る。実際に、提供されたロードと呼ばれるこれらのパラ
メータの積を求めることのみが必要である。

【００４０】しかしながら、一層手が込んだトラフィッ
ク特性評価を有することも可能である。上記の特性評価
に加えて、「尖度（peakedness）」と呼ばれるトラフィ
ック変異性パラメータがあり得る。尖度は、要求ストリ
ームの変異性を記述する。尖度は、代替経路指定で起こ
るように、オーバフロープロセスを処理するために重要
である。（尖度と共に働く方法は下に記述される。） あるいは、利用者ｊのためのトラフィックは、到着率と
サービスレート関数λ_j （ｋ）およびμ_j （ｋ）によっ
て特徴づけられる。そしてλ_j （ｋ）は、利用者ｊから
のｋ個の要求が作動中である時、要求の到着率であり、
μ_j （ｋ）は、利用者ｊからのｋ個の要求が作動中であ
る時、要求の到着率である。標準のケースは、利用者の
ための一定到着率と作動中の要求ごとの一定サービスレ
ートに対応するλ_j （ｋ）＝λ_j およびμ_j （ｋ）＝ｋ
μ_j である。式λ_j （ｋ）＝α_j−ｋβ_j の到着率は、
有限のソースからの入力のケースをカバーする。ブロッ
キング確率コンピュータは、標準のケースと同様に一般
の状態依存到着およびサービスレートが適用される。

【００４１】標準ケースは、尖度１を有することに対応
する。他の尖度パラメータは、適切な状態依存到着率を
形成することによりおおよそ処理される。尖度入力を状
態依存到着率に変換し、次にブロッキング確率を計算す
る効果的な方法が以下に記述される。ステップ３０６
で、利用者はまた、要求事項ベクトル，バーｂ_j ＝（ｂ
_1j、・・・、ｂ_pj）を指定する。パラメータB_ijは、利
用者ｊからの各要求がリソースｉのｂ_ij 個のユニット
を必要とすることを示す。（ｂ_ijがｉとｊそれぞれの負
以外の整数であると仮定される。ブロッキング確率コン
ピュータを保証された制定限度で効果的に実行させるた
めには、ｂ_ijがｂ_j あるいは０のいずれかであると、即
ち、バーｂ_j の正のエントリが一定値をとると仮定され
る。）

【００４２】サービスのグレードはまた、ブロッキング
条件も含む。まず、すべての利用者が彼らの基準レート
で要求を提出すると想定して、利用者ｊからの要求のた
めの望ましいブロッキング確率である基準ブロッキング
条件が存在する。第２に、一人もしくはそれ以上のその
他の利用者が彼等の指定のレートを超えて要求を送てい
ると仮定するブロッキング確率仕様である条件ブロッキ
ング要求も存在する。利用者は、ＵＬおよびＧＭ限界に
よって直接サービスのグレードを指定してもよい。そう
であれば、それらの限界は、まだブロッキングの条件に
適合するために変更される必要があるだろう。利用者が
ＵＬまたはＧＭバウンドを指定する場合、ネットワーク
提供者は、利用者により指定された限界に等しいかそれ
以上のこれらの限界のための値を自由に選べる。

【００４３】ステップ３０６が完了した後、ブロッキン
グ確率コンピュータは、ステップ３０７で、すべての古
いおよび新たな利用者のブロッキング確率を算出し、ブ
ロッキング条件が満たされるか否かを決定するために用
いられる。ブロッキング確率コンピュータについては、
以下にさらに詳細に記述する。リソース提供者が新たな
利用者および現存の利用者の基準および条件付ブロッキ
ング条件を満たす目的でこの新たな利用者のための新た
なＵＬおよびＧＭ限界を紹介することも必要である。新
たな限界割り当ては、ＵＬおよびＧＭ限界が容量調整プ
ロセスで調整されるのと同様の方法で行うことができ、
これは後述のセクションＢで詳細に記述される。

【００４４】次に、ステップ３０８でブロッキング条件
が満たされるか否かを決定するためにテストが行われ
る。「イエス」の結果出た場合は、新たな利用者は、ス
テップ３０９で受け入れられる、プロセスはステップ３
０２に戻る。一方、いずれかの計算されたブロッキング
確率がその条件より大きい場合は、加入許可のための条
件は満たされず、ステップ３０８の結果は「ノー」であ
る。その時、ステップ３１０で示されるように、ブロッ
キング確率コンピュータは、ひとつもしくはそれ以上の
代替グレードのサービスが提供されるか否かを決定する
ために用いられる。修正された条件は、例えば、より低
い到着率関数、より低い上限限界あるいはより低い保証
された最低限界を有してもよい。

【００４５】サービスの代替のグレードがステップ３１
０で提案された後、それらの代替のひとつが利用者にと
って満足がいくかどうかについてステップ３１１で決定
される。イエスであれば、プロセスはステップ３０６に
戻り、サービスのグレードを決定するために新たなパラ
メータが用いられる。他方、もしステップ３１１におけ
る結果が「ノー」であるなら、新たな利用者はステップ
３１２で拒絶される、そしてプロセスは新しい利用者事
件を待ち受けるためにステップ３０４に戻る。図３のス
テップ３０６で行われたサービスのグレード決定につい
ては、図４でさらに詳細に記述する。プロセスは、利用
可能なサービスの選択肢が利用者通信される場合、ステ
ップ４０１から開始する。システムは前もって指定され
た価格における前もって指定されたグレードのサービス
の一定の有限の組を供給するか、利用者それぞれに特別
に適した新たなグレードのサービスを設計してもよい。
方法を利用者に知らせる。次に、ステップ４０２で、シ
ステムは利用者から入力を受け取る。提案されたグレー
ドのサービスの仕様という条件のもとで、リソース提供
者はコストの見積もりをし、ステップ４０５で利用者に
価格を知らせる。コストを推測する方法は後述する。そ
の後、ステップ４０６において、リソース提供者は価格
が利用者にとって満足がいくか否かを決定する。

【００４６】図３のステップ３１０において代替グレー
ドのサービスを提案するために用いられた条件修正プロ
シージャについては、図５でさらに詳細に記述する。こ
のプロセスは、新たな利用者の条件が実行不可能である
と分かった場合、ステップ４０６から開始する。まず、
プロセスは、ステップ５０２で、実行可能な見込み利用
者ｊのための減少した要求サブミッションレートを見つ
ける。元の要求レートがλ_j である場合、新しい要求レ
ートは、いくらかのα、０＜α＜１、のためαλ_j とな
る。新たな到着率で同様の制約を制限する関連する新た
なＵＬおよびＧＭ限界有するために、ＵＬおよびＧＭ限
界はαλ_j ＋ｃ√λ_j 定数を保持するように変更さえ
る。前記式におけるｃはケースα＝１と関連する値であ
る。尖度パラメータは、あれば、変化しないままであ
る。到着率だけについて検索されるので、それは比較的
初等である。即ち２等分探索が用いられる。各候補レー
トαλ_jについて、ブロッキング確率コンピュータはフ
ィージビリティ（実行の可能性）をチェックするために
用いられる。単に有限のレートの組が利用可能であるな
ら、検索はこの組上に行われる。

【００４７】次に、ステップ５０３において、実行可能
な代替物が、一定のしかしグラムとＵＬ限界を変更する
最初のレートを保持することにより生成される。まず、
ＧＭ限界を減少させて、実行可能な解答が得られるか否
かを確認する。もし可能であるなら、検索により最大の
実行可能なＧＭ限界を見いだす。もしＧＭ限界を削除す
ることにより実行可能な解答をえることができないので
あれば、ＧＭ限界を０と等しくし、ＵＬ限界を減少す
る。その後、最大の実行可能なＵＬ限界を見いだすため
の検索を行う。ＧＭ限界を前の最小値とフィージビリテ
ィに影響しない最も高い値にＧＭ限界を上げる。この方
式は、実行可能な同じ到着率を有する新しい１対のＵＬ
およびＧＭ限界を作り出す。代替のグレードのサービス
のを形成するプロシージャは、ステップ５０５でストッ
プする。ステップ５０２および５０３で生成された２つ
の代替物は、ステップ３１０で、利用者に提供される。
利用者およびリソース提供者はまた、同様にフィジビリ
ティについてチェックされる他の代替物を考慮してもよ
い。実行可能な代替物が利用者にとって満足がいくもの
であれば、利用者は加入許可される（図３のステップ３
０９）。

【００４８】図３のステップ３０３で示されるように、
ＵＬおよびＧＭ限界を有する多数のグレードのサービス
を提供することは、これらの限界が継続中の基準で実施
されることを必要とする。能率的にトラフィック限界を
実施するための全体のプロシージャは、図６に示されて
いる。好都合なことに、このプロセスは、保証された最
低限界を効果的方法でチェックする。特に、要求事件ご
との計算量は、その要求をする利用者によって用いられ
るリソースの数と同じ次数である。これは、リソースの
合計と利用中のクラスの合計の積に等しい次数の計算量
を必要とするスキームよりもずっと複雑でない。

【００４９】図６において、トラフィック限界を実施す
る第１のステップ６０１は、システムのスタートアップ
において、および利用者が到着したり離脱する時に制御
変数を初期化している。利用者およびシステムのパラメ
ータは以下の通りである： Ｐ − リソースの数 ｒ − 利用者の数 Ｋ_i − リソースの容量、ｉ、 Ｌ_j − 利用者ｊからの要求上の保証された最低限界 Ｕ_j − 利用者ｊからの要求上の上限限界 ｂ_ij − 利用者ｊの各要求によって要求されたリソー
スｉにおけるユニットの数。 かぎ変数は、利用者ｊの使用中の要請の数ｎ_j である。
要求が到着する前は、値はｎ_j ＝０である。また、有効
な更新のために、もう１つのかぎ変数は、ｉごとのリソ
ースｉないの自由なユニットの数Ｆ_i である。Ｆ₁ のイ
ニシャルバリューは、保証された最低限界によって必要
とされた数を差し引いたユニットの合計の数である。即
ち、

【数１】

【００５０】図６のプロセスは、新しい要求イベントが
起こまでステップ６０２で待機し、その後ステップ６０
３に進む。ステップ６０３で、利用者ｊの要求がサービ
スを完了して、そして離れること決定された場合、計量
値ｎ_j およびＦ_i が次のように更新される： （ｉ） ｎ_j＝ｎ_j−１ （ｉｉ） すべてのｉについてｂ_ij＞０となるよう
に、ｎ_j ≧Ｌ_j の場合、Ｆ_i ＝Ｆ_i ＋ｂ_ijとなる。さも
なければＦｉは変えない。

【００５１】新しい利用者ｊの要求が到着したとステッ
プ６０３で決定された場合、新しい利用者ｊの要求は、
新しい要求がＵＬおよびＧＭ限界を満足させたとステッ
プ６０５で決定された場合に受け入れられる。 （ｉ） ｎ_j≦Ｕ_j−１、および （ｉｉ） ｉごとに、ｂ_ij＞０となるように、 ｎ_jｂ_ij≦Ｆ_i＋Ｌ_jｂ_ij−ｂ_ij ステップ６０５で結果が得られなければ、利用者ｊの要
求は受け入れられない。利用者ｊの要求がステップ６０
５で受け入れられる場合、計量値は次のようにステップ
６０６で更新される： （ｉ） ｎ_j＝ｎ_j＋１ （ｉｉ） ｉごとに、ｂ_ij＞０となるように、ｎ_j＞Ｌ_j
の場合、Ｆｉ＝Ｆｉ−ｂ_ijとなる

【００５２】初期数の要求でシステムがスタートした場
合、Ｆｉは次の式を用いてｉごとに計算されなければな
らない。

【数２】 全体の計算量は、Ｏ（rp）である。利用者ｊの引き続く
要求の到着／離脱事件ごとに、計算量Ｏ（ｑ）を有する
計算が行われる。このｑは、利用者により使用されたリ
ソースの数である。いくつかの適用では、ｒとｐは両方
とも大きくなが、ｑは小さいままでであろう。従って、
一度大きいスタートアップ計算（one-timelarge start-
up computation）が存在してもよいが、各要求到着／離
脱時点において、計算量は低いままで、完全共有および
トランクリザベーションなどの他の単純要求受け入れ許
可方法と同じ順番である。

【００５３】新しい利用者にサービスを供給するための
コストを決定するための方法を以下に論じる。たとえ各
リソースに使われた容量にだけ焦点を合わせたとして
も、新しい利用者にサービスを供給するためのコストに
ついていくつかの可能な解釈が存在する。明らかに、使
用された最小容量は、最低限界ＧＭであり、使用された
最大容量は、上限限界ＵＬである。これら２つの限界の
間にあるべき「使用される予想容量」の知らせを探すこ
とは当然である。

【００５４】ひとつの予想コストの表現は、ぎりぎりの
予想コストであって、すべての利用者が指定されたパラ
メータに従って要求を提出すると仮定してそのリソース
を使用するすべての他の利用者について必要な分を超え
るリソースで要求される割り増しの容量である。ぎりぎ
りの予想コストは、まず、すべての現在の利用者条件が
満たされるようにリソースの最小容量を見い出し、次に
すべての現在の利用者と新たな利用者との条件が満たさ
れるようにリソースの最小容量を見い出すことにより決
定される。このリソースにおいて利用者にサービスを供
給することについてのぎりぎりの予想コストは、これら
の２つの容量レベル間の差である。ブロッキング確率コ
ンピュータは、ちょうど容量修正プロシージャにおける
場合のように、２つの重大な容量レベルを決定するため
に用いられる。

【００５５】別つの予想コストの表現は、第１の利用者
の予想コストであって、その利用者がそのリソースを使
う利用者のみであった場合は使用された平均容量であ
る。このコストは、他の利用者が存在せず、この利用者
はその承認されたトラフィックパラメータに従って要求
を提出する仮定して利用者の条件が満足し得るように、
リソースの最小容量を見いだすことにより決定される。
第１の利用者の予想コストは、一般に、より少ない共有
のために、ぎりぎりの予想コストより高いはずである。
この第１の利用者の予想コストはまた、ぎりぎりの予想
コストの場合と同様に、ブロッキング確率コンピュータ
を使用することにより決定される。計算は、単一利用者
だけにより、より容易である。

【００５６】上述の２つの予想コストを評価するための
非常に早い容量条件予測を得るために正規近似を使用す
ることも可能である。正規近似は、数値反転を行う前
に、モデルから非常に軽いロードのリソースを取り除く
目的で必要とされる容量を見積もるために、以下に記述
されるように用いられる。以下、さまざまな到着プロセ
ス変異性の処理について論じる。各利用者の要求到着プ
ロセスがポワソン過程として合理的にモデル化されると
いうのが通常の前提である。各要求到着プロセスは、単
に到着率を与えることによって指定される。ポワソン過
程は適切なモデルであが、時々要求到着はポワソン過程
におけるよもりも実際はかなり変化しやすい又はしにく
いあるいは「バースト的」である。例えば、要求が別の
リソースに対して実際に満たされない要求のオーバフロ
ーである場合、それらはポアソン過程よりさらにバース
ト的なプロセスに到達する傾向がある。非ポアソン過程
を特徴付ける方法は、Ａ・Ｅ・エクベルグ（A. E. Eckb
erg）「テレトラフィックプロセスの一般化された尖度
（Generalized Peakedness of Teletraffic Processe
s）」、第１０回国際テレトラフィック会議の議事録、
モントリオール、カナダ、書類４．４ｂ．３およびＬ・
Ｅ・Ｎ・ベルブルク（L. E. N. Delbrouck）の「スムー
ズな最高性能のトラフィック（Peaky Traffic）のため
の混雑関数の統一概算評価」コミュニケーションについ
てのＩＥＥＥ会報、通信についてのＩＥＥＥトランザク
ション、１９８１年、第２９巻、８５〜９１ページによ
って記述された尖度パラメータによるものである。「尖
度」は、関連する無限容量リソースにおける使用中の要
求の平均数に対する変異（variance）比率として定義さ
れる。ポワソン到着のケースのために、サービス中の要
求の数は、容量限界がない場合、ポアソン分布を有す
る。変異がポアソン分布の平均に匹敵するため、尖度は
ポワソン到着過程のため１である。さらにバースト的な
到着過程では、尖度は１より大きく、一方バースト的で
ない到着過程では、尖度は１以下である。

【００５７】ベルシステム技術ジャーナル（Bell Syste
m Technica Jurnal）第３５巻Ｎｏ２「米国における長
距離通信トラフィック工学のための理論（Theories fo
TallTraffic Engineering in the U.S.A.」１９５６年
４２１〜５１４ページにおけるＲ・Ｉ・ウィルキンソン
（Wilkinson）を始めとして、数人の研究員は、有限容
量リソースにおける使用中の要求の数がいかなるリソー
ス容量についても、ポワソンよりもバースト的な切り捨
てを行ったパスカル（または負の二項式）分布およびポ
ワソンよりもスムーズなソースのための二項分布を有す
る傾向にあるという観測結果を見い出した。この観測結
果を用いて、前記で引用した参考文献においてＬ．Ｅ．
Ｎ．デルブロック（L. E. N. Delbrouck）は、完全供給
手段を有する単一レート、単一リソースの環境における
ブロッキング計算のための正確な近似を開発した。我々
は、より一般的な設定でその方法を引出す。

【００５８】基本観念は、線形状態依存到着比率関数λ
_j （ｋ）＝α_j ＋β_j を用いることである、ＢＰＰ過程
として知られたこの到着過程が、β_j ＞０のためのパス
カルとしておよびβ_j ＜０のための二項式として無限容
量リソースに多くのビジーなサービスを生成する。（さ
らにＢＰＰモデルは、ブロッキング確率コンピュータの
範囲内となる。）ＢＰＰ過程のパラメータα_j およびβ
_j は、無限容量リソース、すなわちいかなる容量制約条
件もないシステム、における任意の時点で使用中のクラ
スｊ要求の数の平均および分散（variance）を適合する
ことにより決定される。特に、Ｍ_j およびＶ_j が利用者
ｊに対応する実際の到着過程について上述した平均およ
び分散量を示すようにする。概算ＢＰＰ過程のためのこ
れらの量は、

【数３】 と

【数４】 であることが示される。上記のことから、２つのＢＰＰ
パラメータは、

【数５】 と

【数６】 であり、ここでは、

【数７】 である。数量Ｍ_j は、与えられたロードであり、到着過
程のほとんどについては容易に計算可能である。また、
ほとんどの共通の到着過程について、尖度パラメータ
は、（上に引用された）Ａ．Ｅ．エクベルグによって示
されたのと、同様に容易に計算可能である。

【００５９】α_j とβ_j を得て、我々はブロッキング確
率を計算することを望む。これはブロッキング確率コン
ピュータを応用することによって直接されることができ
た、しかし（以前に引用された）ベルブロクによって分
かるように、もし我々がＢＰＰ到着過程を有する有限容
量システム内の活用中の要求の平均数によって間接的に
ブロッキング確率を計算する場合、もっと良い近似式が
得られる。したがって、次のステップは、容積制約を有
する実際のシステムにおけるサービス中のクラスｊ要求
の平均数、ｍ_j 、を計算することである。ｍ_j は、

【数８】 により得られることが示される。ｅ_j は、ｊ番目の一に
おける１と０の他の場所を有するベクトルであり、式８
の分子における記号ｇは、我々がα_j ＋β_j で置換され
るα_j を有するシステムを考慮すべきであることを意味
する。尚、この置換は分子の規格化定数を算出するため
のだけのものであり分母のためのものではない。

【００６０】故に、ｍ_j はブロッキング確率コンピュー
タによって容易に計算される。最後に、コールブロック
のための式は、

【数９】 である。図２に示され、また図３の加入許可制御プロセ
スのステップ３０７に援用されるブロッキング確率コン
ピュータについて説明する。（以下のセクションＢおよ
びＣで儒様な役割を果たす。）図３のステップ３０７二
示されたブロッキング確率コンピュータプロセスについ
ては、図７に関してより詳細に記述する。

【００６１】ブロッキング確率コンピュータで実行され
るプロセスは、ステップ７０１で得られた次のリソース
供給入力必要とする： ｐ − リソースの数 ｒ − 利用者の数 ｋ_i − リソースｉの容量，ｉ≦ｉ≦ｐ ｂ_j − 利用者ｊにより使用される各リソースに必要
とされるユニットの数 δ_ij＝ １ 利用者ｊがリソースｉを使用する場合 ０ それ以外 Ｂ − ｂ_ij＝δ_ijｂ_ijを伴うマトリクス Ｕ_j − 利用者ｊからの要求におけるＵＬ限界、１≦
ｊ≦ｒ、 Ｌ_j − 利用者ｊからの要求におけるＧＭ限界、 Ｎ_j − 利用者ｊのために保証されたユニットの数、
Ｎ_j＝Ｌ_jｂ_j Ｋ ＝（Ｋ₁，・・・，Ｋ_p）− 容量ベクトル Ｕ ＝（Ｕ₁，・・・，Ｕ_r）− ＵＬ限界ベクトル Ｎ ＝（Ｎ₁，・・・，Ｎ_r）− ＧＭ限界ベクトル モデルが効果的に直接解答するには大きすぎる場合、基
本的に等しいより小さなモデルを生成するためにステッ
プ７０２において、基準近似プロセスが実施される。近
似解析は、あまり制約条件をかけないほどの軽いロード
のリソースを検索し、より小さいモデルはこれらのリソ
ースを削除することにより得られる。軽いロードのリソ
ースを削除するためのこの正規近似スキームは、以下に
より詳しく記述される。

【００６２】次に、ステップ７０３において、積行列の
定常状態分布と関連する規格化定数の母関数が形成され
る。まず、許可可能な状態のセットは、

【数１０】 である。ｇ（Ｋ、Ｕ、Ｎ）は、規格化定数であり、

【数１１】 であり、λ_j （ｋ）到着比率関数およびμ_j （ｋ）サー
ビスレート関数である。規格化定数は、

【数１２】 である。

【００６３】規格化定数ｇ（Ｋ、Ｕ、Ｎ）の母関数は

【数１３】 である。ｚ＝（ｚ₁ ，・・・，ｚ_p ）、ｙ＝（ｙ₁ ，・
・・，ｙ_r ）およびｘ＝（ｘ₁ ，・・・，ｘ_r ）は、複
素数変数のベクトルである。式４の母関数は、式

【数１４】 を有し、ここでは、

【数１５】 および

【数１６】 であり、式１６におけるｘは、単一複素数変数である。

【００６４】λ_j （ｋ）＝λ_j 、μ_j （ｋ）＝ｋμ_j お
よびρ_j ＝λ_j ／μ_j を伴う標準（ポワソン）ケースで
は、母関数Ｆ_j （ｘ）は、次の式：

【数１７】 によって得られる。λ_j （ｋ）＝α_j ＋β_j ｋ（β_j ≠
０およびｒ_j ＝α_j ／β_j ）およびμ_j （ｋ）＝ｋμ_j
を伴ういわゆる二項式およびパスカルケースにおいて、
式１６における母関数Ｆ_j （ｘ）は、次の式：

【数１８】 によって得られる。λ_j （ｋ）＝でλ_j およびμ_j
（ｋ）＝μ_j 、ｆ_i （ｎ_j ）＝ρⁿ _j ^j である特別なケー
スについては、式１６において、次の式：

【数１９】 によって得られる。

【００６５】式１７から１９におけるＦ_j （ｘ）のため
の閉じた形式の式は、式１５および故に式１４における
母関数値を計算しやすくする。しかしながら、一般的ケ
ースでさえ、式１６における無限和は、常にほとんど損
失なしで（loss of generality）切り捨てられる。有限
の容量限度により、すべてのｋ≧ｎ_j ＋１についてｆ_j
（ｋ）＝０とするように、ふさわしく大きいｎ_j につい
てλ_j （ｎ_j ）＝０と仮定するに足りる。

【００６６】たとえいくつかのリソースが図７のステッ
プ７０２においてプロセスから削除されたとしても、そ
の結果生じるプロセスは依然、直接解くにはあまりにも
複雑であろう。この困難は主に、ステップ７０３におい
て形成された母関数のディメンションがあまりにも大き
いためである。ディメンションがあまりにも大きい場
合、良好な条件付きの分解が母関数の効果的な次元を減
らすために求められる。ディメンションリダクションを
成し遂げる良好な条件付きの分解を見いだすためのプロ
シージャを以下に記述する。ステップ７０２および７０
４を応用して、ステップで７０５において、ブロッキン
グ確率が計算されるか否かについての決定が行われる。
その結果が「ノー」である場合、減少したロードの固定
小数点近似がステップ７０６で行われる。ブロッキング
確率コンピュータは、以下により詳しく記述されるよう
に、このステップにも実際に使われる。

【００６７】ステップ７０５における結果が「イエス」
である場合、母関数は、ステップ７０７において反転さ
れる。反転はさまざまな方法で行うことが可能である。
フーリエ級数方法を用いる効果的な反転技術のひとつ
は、Ｊ・アベート（J. Abate)）およびＷ．ホイット
（W.Whitt） の「確率分布のトランスフォームを反転す
るためのフーリエ級数方法The Fourier-Series Method
for Inverting Transformsof Probability ）」キュー
イングシステム（Queueing Systems）１９９２年、第１
０巻、５〜８８ページと、Ｇ．Ｌ．チュードリー（G.L.
Choudhury）におけるＤ．Ｍ．ルーカントニ（D.M. Luc
antoni）およびＷ・ ホイット (W. Whitt)の「過渡Ｍ／
Ｇ１キューへのアプリケーションとともに多次元のトラ
ンスフォーム反転（Mulitidimensional Transform Inve
rsion With Applications to the Transient M/G1 queu
e）」応用の確率の年報（Annals of Applied probabili
ty）、１９９４年、第４巻、７１９〜７４０ページとに
記載されている。

【００６８】ｐ次元の母関数

【数２０】 が反転されるコトヲ考える。変数を反転すべき良好な次
数を決定するために条件付きの分解がすでに行われたと
仮定する。その後、プロシージャは、ｐまで繰り返し１
次元反転を行う。

【００６９】反復反転を示すために、部分的な母関数を

【数２１】 とする。上記式において、１≦ｊ≦ｐの場合、ｚ_j＝
（ｚ₁，ｚ２，．．．，ｚ_j）およびＫ_j ＝（Ｋ_j，Ｋ_j+1
，．．．Ｋ_p ）である。ｚ₀ およびＫ_p+1 をヌルベク
トルとする。明らかに、Ｋ＝ｋ，ｚ＝ｚ_p，ｇ^(p) （ｚ_p
，Ｋ_p+1 ）＝Ｇ（ｚ）およびｇ⁽⁰⁾ （ｚ₀ ，Ｋ₁ ）＝
ｇ（Ｋ）である

【００７０】Ｉ_j をＺ_j について反転を示すものとす
る。すると、ステップバイステップのはめ込み反転アプ
ローチは、

【数２２】 であり、ｊ＝ｐから始めて、ステップごとに１ずつｊを
減少させる。実際のプログラムインプリメンテーション
では、式２２における反転は、ｊ＝１として試まれる。
右側部分を算出するには、ｊ＝２を有するもう一方の反
転が必要である。このプロセスは、ステップｐにおいて
右側の関数がｐ次元の母関数になり、確実に計算可能に
なるまで、続く。

【００７１】ｊ番目のステップにおける反転式を下に示
す。単純にするために、この反転の間に一定のままのこ
れらの引数は、ｇ_j （Ｋ_j ）＝ｇ^(j-1) （ｚ_j-1 ，Ｋ
_j ）およびＧ_j （ｚ_j ）＝ｇ^(j) （ｚ_j ，Ｋ_j+1 ）とし
て抑制される。この定義を用いて、反転式（式２２）
は、

【数２３】 であり、ｉ＝√−１であり、１_jは正の整数であり、ｒ_j
は正の実数であり、またｅｊは、次式：

【数２４】 によって得られるエイリアシング誤りを示す。

【外１】

【００７２】（２４）におけるエイリアシング誤差を制
御するために、α_j ＝γ_j ／（２１_jＫ_j）の場合、ｒ_j
＝１０^-aj とする。よって、式２４は、

【数２５】 となる 。

【００７３】式２５におけるより大きいγ_jは、エイリ
アシング誤差を減少させる。パラメータ１ｊは、より大
きい数値がより少ない丸め誤差を起こすという状態で、
丸め誤差を制御する。内部和における反転された値が外
部和におけるトランスフォーム値として用いられるの
で、反転の内部和は外部和よりも多くの精度を必要とす
る。およそ８つの有効桁精度を目的とし、次の１_jとγ_j
のセットは、計算が２倍精度算出法を使って行われると
仮定して、一般的に妥当：ｉ）１₁ ＝１，γ₁ ＝１１、
ｉｉ）１₂ ＝１₃ ＝２，γ₂ ＝γ₃ ＝１₃ 、ｉｉｉ）１
₄ ＝１₅ ＝１₆ ＝３，γ₄ ＝γ₅ ＝γ₆ ＝１５である。
同様の精度に達成するようにさらに計算が行われるの
で、通常はすべてのｊについて同じ１_jを使うことは良
い考えではない。

【００７４】反転関数が確率である場合、式２５におけ
るエイリアシング誤差ｅ_j は、ｇ_j（Ｋ_j ）≦１である
ので容易に境界がつけられる。逆に、ここで規格化定数
は任意の大きさであるので、エイリアシング誤差ｅ_j も
同様に任意の大きさであろう。したがって、母関数は、
スケーリングされた母関数を

【数２６】 と定義することによって各ステップでスケーリングされ
る。上記式におけるα_0jとα_j は、正の実数である。こ
のスケーリングされた母関数は、誤差がふさわしく制御
されるように、α_0jとα_j を選択した後で反転される。
式２６におけるＧ_j （ｚ_j ）の反転により、スケーリン
グされた規格化定数：

【数２７】 が形成される。効果的なスケーリングプロシージャにつ
いてはは、以下により詳しく記述する。大きなモデルに
ついて、計算は、多様性（multiplicities）を利用し、
大きな有限合計を賢明に切り捨て、共有された多量の計
算で、多くの密接に関係する規格化定数を同時に計算す
ることによって、スピードアップすることができる。こ
れらの技術については、以下にさらに詳しく記述する。
最後に、ブロッキング確率自身を計算することが残る。
このステップはまた、ステップ７０７で実行され、以下
により詳しく記述される。

【００７５】スケーリングについて述べると、数値反転
におけるエイリアシング誤差は、各ステップにおいて母
関数をスケーリングすることによって制御されることを
述べておく。ｐ次元の反転のｊ番目のステップにおい
て、スケーリングされた母関数が式２６に定義される。
このスケーリングされた母関数は、誤差が適切に制御さ
れるように、α_0jとα_j を選択した後で反転される。式
２６におけるα_0jおよびα_j は、スケーリング

【数２８】 でエイリアシング誤差を制御するように選択される。

【００７６】ブロッキング確率は、規格化定数の比を伴
うから、次式

【数２９】 で制限される相対誤差ｅ^' _j＝バーｅ_j ／バーｇ_j （Ｋ
_j ）に集中するのに適している。

【数３０】 とすると

【数３１】 となる。なお、式３０におけるＣ_jは、α_0jとは無関係
である。第２のパラメータα_0jは、数値のアンダフロー
あるいはオーバフローを避けるように、バーｇ_j（Ｋ
_j ）を１に近い状態に保つために主に使われる。（この
数値問題はまた、対数と共働することにより解決でき
る。）

【００７７】したがって、主たる目的は、Ｃ_j ＜＜１０
γⁱ となるようにα_j を選択することである。この＜＜
は、「よりもかなり少ない」という意味である。もちろ
ん、一般的には、ｇ_j （Ｋ_j ）は知られていないので、
Ｃ_jも同様に知られていない。しかしながら、Ｃ_j ＜＜
１０γⁱ は、母関数の構造を利用して、バーｇ_j （Ｋ
_j ）の成長率、またはその最も早い成長期間、を大ざっ
ぱに制御することにより成し遂げられる。ポワソン到着
を伴う完全共有（ＣＳ）手段のケースについて、スケー
リングされた母関数は、

【数３２】

【００７８】およびスケーリングされた規格化定数は、

【数３３】 である。この設定において、効果的スケーリングは、ス
ケーリングパラメータα _i （１≦ｉ≦ｐ）を選択するこ
とによって得られるので、差０＜αｉ≦１および

【数３４】 が満たされる。上記式において、ｊ／（２１_j Ｋ_j ）
の場合ｒｋ＝１０^-aj である。スケーリング変数α_i が
得られると、変数α_0iは、次式

【数３５】 によってｉ＝ｐから開始して反復的に得られる。

【００７９】式３４を満たす最大ベクトル（α
₁ ，．．．α_p ）は、ｉ＝ｐから開始し、ｉを準々に減
らすことによって見い出される。式３４の左側がα_i に
おいて単調であるということを用いる。ｉ＝１である場
合、ｉ≧１＝１の場合α_i の値は知られている。まるで
ｉ≦１＋１の場合α_i ＝１であるかのように行うことに
より近似化させ、式３４におけるｉ＝１についての制約
を満たすα１を見い出す。これにより、最大ベクトルが
生成される。即ち、いずれのα_i も１以下である場合、
式３４における少なくともひとつの制約は均等として必
ず満たされる。それ故、ベクトルは、制約条件を破らず
に増加されることはない。しかしながら、一般に数多く
の最大のベクトルがあるだろう。

【００８０】以下、他の到着率とサービスレート関数の
ためのスケーリングについて記述する。単に１次元のケ
ースについてのみ詳細に記述する。多次元拡張（extens
ions）は、上記の式３４および３５に類似する。

【００８１】まず、β_j ≠０の場合λ_j （Ｋ）＝α_j ＋
ｋβ_j およびμ_j （ｋ）＝ｋμ_j であるケースを考慮す
る。（完全共有手段はこの時点でもまだ仮定される。）
１次元のケースにおいて、

【数３６】 である。式３６から、このケースが無限に多くのクラス
を伴うポワソンケースと見すことができる。クラスは、
１≦ｊ≦ｒおよび１≦１≦∞である（ｊ，１）として示
される。クラス（ｊ，１）のためのトラフィック密度パ
ラメータは、（β_j ／μ_j ）¹ （ｒ_j ／１）および1ｂ_j
におけるこのクラスの数により必要とされるリソースユ
ニットである。したがって、ポワソンケースで使用され
たものと同じスケーリングが使用できる。

【００８２】式３４の１次元バージョンは、

【数３７】 となる。よって、αは、式３７を満たす（０,１］ にお
いて最大数である。式３７を解く場合、左側は、分母項
のいずれかが負の数である場合無限とされる。

【００８３】次に

【数３８】 であり、簡単化後は、

【数３９】 である。

【００８４】次に、λ_j （ｋ）＝λ_j およびμ_j （ｋ）
＝μ_j を伴うケースを考える。これは、Ｆ．カモン（F.
Kamoun） およびＬ．クレインロック（L. Kleinrock）
の「一般的トラフィック条件下でコンピュータネットワ
ークノード環境における共有された有限の記憶の分析
（Analysis of Shared Finite Storge in a Computer N
etwork Node Emvironment Under General Traffic Cond
ition）」 通信についてのＩＥＥＥトランザクション、
１９８０年第ＣＯＭ−２８、９９２〜１００３ページに
示されたように、単一サーバを有する緩衝された（buff
ered）モデルに対応している。このケースは、ちょうど
ｒ_j を１で置換し、（β_j ／μ_j ）をρで置換すること
により考慮されたケースに還元されるる。それにより、
スケーリングパラメータが生成される。特に、αは、式

【数４０】 の範囲（０,１］ における最大解である。上述したよう
に、若干のｊについて１−ρ_j α^bj＜０である場合、左
側全部は、無限として解釈される。すると、

【数４１】 となる。

【００８５】今まで、完全共有の（ＣＳ）手段は、仮定
されてきた。ＵＬケースにおいて、母関数の形式は、よ
り多くのリソースを伴うＣＳ母関数と同様である。この
場合、ＣＳスケーリングは、簡単な方法で拡張される。
ＧＭケースは、他のすべてのクラスの保証された最小値
の合計を差し引いた容量に等しい上限を有するＵＬ手段
にそれを等しいと置くことにより（スケーリングだけの
ために）ヒューリスティックに扱われる。結合したＵＬ
およびＧＭケースについて、近似として、各クラスごと
の与えられた上限最小値および他のすべてのクラスの保
証された最小値に基づいたヒューリスティックである新
しい上限を使用する。

【００８６】いかなる形式の母関数にも適用し、一般的
な状態依存の到着とサービスレートに適用可能な別のヒ
ューリスティックが存在する。

【数４２】 を伴う

【数４３】 とすると、αは、

【数４４】 となるような間隔インタバル（０,１］における最大数
である。

【００８７】上記式において、Ｇ^' _j（ｚ）＝ｄ／ｄｚ．
Ｇ_j （ｚ）、すなわち、導関数である。すると、

【数４５】 となる。このスケーリングは、詳細に扱われた特別なケ
ースにおける事前のスケーリングと一致する。式４２の
ｐ次元の拡張は、

【数４６】 であり、上記式において、

【数４７】 である。

【００８８】反転の最も内部のレベルはｚ１に関し、最
も外部のレベルはｚｐに関すると仮定される。スケーリ
ングパラメータをα＝（α₁ ，α₂ ，．．．，α_p ）お
よびα０＝（α₀₁，α₀₂，．．．，α_0p）とする。よっ
て、スケールベクトルαは、ｉ＝１，２，．．．，ｐの
場合０＜α≦１、およびｉ＝１，２，．．．，ｐの場合

【数４８】 を満たす最大ベクトルである。上記式において、

【数４９】 である。「最大」は、式４８が少なくともｉにおいて、
α＝（１，１，・・・，１）でない限り均一性（equali
ty）で満たされるべきであることを意味している。残り
のスケールパラメータα_0i、１≦ｉ≦ｐ、は、

【数５０】 によりｉ＝ｐから開始して反復的に得られる。

【００８９】次に、本発明に係る選択肢として有効に使
用できるいくつかの技術を考えると、まず、２つ以上の
クラスが同じパラメータ（トラフィックパラメータ、リ
ソース条件、ＵＬおよびＧＭパラメータ）を有している
場合、この重複度は、要求される計算を著しく減らすた
めに用いることができる。ｒを異なるタイプの利用者の
数とし、ｊ^thタイプは重複度ｍ_jを有するとすると、利
用者クラスの合計数は、

【数５１】 であり、関心のｐ次元母関数が、次式

【数５２】 で表わされる場合、それは、

【数５３】 で表わすことができる。式５２の評価における計算の複
雑性は、Ｏ（ｒ）であり、一方、式５３の評価における
計算の複雑性は、Ｏ（バーｒ）である。第２に、式２３
から分かるように、各次数における反転式は、２１_i Ｋ
_i 項の合計である。Ｋ_i が大きい場合、有限合計の賢明
な切り捨てを含む有限合計のコンバージェンスを加速す
る方法が存在する。

【００９０】各次数における反転式は、円周に沿って等
距離のポイントにわたって評価された母関数値の重みづ
け合計である。重みづけは、複雑な数であるが、それら
は、一定の振幅を有する。容量Ｋ_iが大きくなるにつれ
母関数の振幅は、一般に、円周沿って不揃いに分布され
る。最大ローカルポイントおよび、これらのポイントか
らはっきりと離れた振幅降下が存在する。重みづけが一
定の振幅を有するので、母関数値の相対振幅を考慮する
ことのみが必要である。）すべての相対最大ポイントが
認識され、比相対振幅を有するそれらの周りのポイント
のみが考慮される場合、計算における著しいリダクショ
ンを得ることが可能である。まず、切り捨てプロシージ
ャは、単一リソースについて開発され、その後拡張され
る。ポワソン到着を有する完全共有の場合におけるスケ
ーリングされた母関数、即ち、

【数５４】 を考える。外側次数において、計算は半分にカットされ
る；よって、半径ｒ₁ ＝１０−γ₁ ／２１₁ Ｋ₁ を有す
る上方半円にわたる合計を考える。

【００９１】総和ポイントにおいて、ｚ₁ ＝ｒ₁ ｅⁱ θ
であり、θは、０≦ｋ≦１₁ Ｋ₁ の場合値πｋ／（１₁
Ｋ₁ ）を仮定する。バーＧ^* （θ）をθの関数として表
わされたバーＧ（ｚ₁ ）とする、すなわち、

【数５５】 とする。式５５におけるＧ^*（θ）の振幅は、

【数５６】 である。

【００９２】ｊ＝１，２，．．．，ｒの場合、分子は、
１ｊ＝０，１，．．．，［ｂｊ／２］におけるθ＝２１
_jπ／ｂ_jにおいて相対最大値と、分母は、θ＝０におい
て単一の最小値を有する。故に、｜Ｇ^*（θ）｜は、θ
＝０において大域の最大値を有し、１_j ＝１，
２，．．．，［ｂ_j ／２］および１，２，．．．，ｒの
場合のθ＝２１_j π／ｂ_j における潜在ローカル最大値
とを有する。なお、通常は、これら^rΣ_j=1［ｂ_j ／２］
ローカル最大値のほとんどは一致する。

【００９３】要約すると、｜Ｇ^* （０）｜を算出するこ
とによって開始し、１_j ＝１，２，．．．，［ｂ_j ／
２］および１，２，．．．，ｒの場合の独特のローカル
最大ポイントθ＝２１_j π／ｂ_j を見い出し、増加する
次数にそれらを分類する。それらのポイントをｉ＝１，
２，．．．，Ｌの場合のθⁱ _mとする。一般にθⁱ _mは、反
転アルゴリズムにおける総和ポイントとは一致されな
い。その場合、反転アルゴリズムに用いられた最も近い
総和ポイントにθⁱ _mを移動する。次に、｜バーＧ^*（θⁱ
_m）／バーＧ^* （０）｜≧εとなるようにすべてのｉを
見い出す。εは、若干の許容誤差である。よって、

【数５７】 となる。すべてのｉについて、｜バーＧ^* （θⁱ _m）／バ
ーＧ^* （０）｜≧εとなるまでのθⁱ _m以上のおよび以下
のすべての総和ポイントを合計する。どんな総和ポイン
トも２度（１度以上に）合計してはいけない。

【００９４】大きなρ_j およびK₁について、一般に、単
にθ＝０周辺のポイントおよび２、３の他のローカル最
大値は有用である。計算上の節約がどれほど生じるか
は、（０，π）におけるθのすべての値について計算
し、｜バーＧ^* （θⁱ _m）／バーＧ^* （０）｜≧εである
範囲の割合を見い出すことにより分かる。節約は、√Ｋ
₁にほぼ比例して見られた。切り捨ては、多数のリソー
スでも実行されるが、状況はさらに複雑化される。スケ
ーリングされた母数は、

【数５８】 によって得られ、スケーリングされた規格化定数は、

【数５９】 である。ｚ_p に関する反転の場合、単一のリソースの場
合と同様の計算上の節約が達成されるが、２つの差が存
在する。ひとつは、反転式は、ちょうど半円の代わりに
完全な円にわたる総和を含み、従ってより大きな最大ポ
イントを考慮する必要があるということである。

【外２】 後者の定数が複雑な数であるので、定数フェーズ変化を
θに故にすべての最大ポイントに導くであろう。

【００９５】ｉ＜ｐの場合のｚ_pに関する反転の場合、
関数形式が知られていない部分的に反転された母関数ｇ
^(j-1 ）（ｚ_j-1 ，Ｋ_j ）に対処する必要がある。故
に、最大ポイントは知られておらず、よって、ヒューリ
スティックへ再分類する必要がある。最大ポイントの一
を部分的に反転された母関数が式５５におけるものと同
じ関数形式を有する場合、通常良好な計算節約を作動
し、与えるのと同じであると仮定する。ステップ７０６
および７０７におけるｒクラス語とのブロッキング確率
を算出するために、ｒ＋１規格化定数値はステップ７０
２で算出されるべきであり、それぞれに求められた計算
はＯ（ｒ）であるので、計算上の複雑性はＯ（ｒ²）で
ある。しかしながら、大きな容量のベクトルＫの場合、
共有された多量の計算と同時にｒ＋１規格化定数を計算
できるので、すべての規格化定数のために要求された計
算は、一つの場合よりもわずかに多いだけである。これ
により、Ｏ（ｒ²）からＯ（ｒ）までの全体の計算上の
複雑性が減少される。

【００９６】方法を説明するために、ポワソン到着と完
全共有手段を有する単一のリソースについて考えてみ
る。クラスｊのブロッキング確率は、Ｂ_j＝１−ｇ（Ｋ₁
−ｂ_j）／ｇ（Ｋ₁ ）である。ｂ₀≡０とすると、０≦
ｊ≦ｒの場合のｇ（Ｋ₁ −ｂ_j）を計算する必要があ
る。上述したスケーリングと反転プロシージャとを組合
せて、この計算のための標準式は、

【数６０】 である。上記式において、α_o1j およびα_1jは、スケー
リングパラメータであり、

【数６１】 である。関連するエイリアシング誤差は、

【数６２】 である。なお、数量α_o1j およびα_1j、ｍ_j がｊの異な
る値ごとに異なるため、ｊの異なる値のための式６０に
おける計算は共有されない。

【００９７】ｊの異なる値のための計算を共有する目的
で、Ｋ₁＞＞ｂ_j（０≦ｊ≦ｒ）の場合、数量α_o1j 、α
_1jおよびｍ_j がｊをすべてのｊについてｊ＝０における
それらの値で置換する。Ｋ₁＞＞ｂ_jの場合、数量α
_o1j 、α_1jおよびｍ_j は、ｊ＝０におけるそれらの値に
非常に近いため、これは、式６０におけるエラー表現に
おいて適切な差をもたらさない。α_o1j 、α_1jおよびｍ
_j についてのサブスクリプトｊを減少させ、式６０は、

【数６３】 で書き直せる。上記式において、

【数６４】 である。なお、式６３における多量の計算は、共有され
得るＴ_k を計算することである。Ｃ_j が各ｊごとに一度
だけ計算される必要があるので、数量Ｃ^k _jは素早く算出
される。すべてのｊの部分和で同時に働くことによっ
て、全体の計算は、記憶条件Ｏ（ｒ）で行われてもよ
い。さらに、切り捨て（上述した）が適用する場合、｜
Ｃ^k _j｜＝１であるので、すべてのｊにとって均一に適用
する。多数のリソースおよび他の共有手段について、同
様のアプローチが機能する。

【００９８】以下、ブロッキング確率を算出することに
ついて記述する。ブロッキング確率は、上述した規格化
定数の比較的単純な数式として得られる。それにもかか
わらず、ブロッキング確率を算出するにはいくらかの注
意が必要である。「コールブロッキング」と「タイムブ
ロッキング」とを識別することが重要である。「コール
ブロッキング」は、到着（到着時期における状態によ
る）によって起こったブロッキングを指し、一方「タイ
ムブロッキング」は、任意の時間に到着があった場合そ
の時間におこったであろうブロッキングを指す。式１０
における定常状態分布πが任意の時間を指すので、それ
から直接算出されたブロッキング確率は、タイムブロッ
キングにかかわるが、タイムブロッキングと同様コール
ブロッキングを算出することが可能である。ポワソン到
着では、到着時期および任意の時間における２つの確率
分布は一致するが、一般的でない。

【００９９】まず、レートおよび尖度により部分的に特
定された到着仮定に対する近似としてＢＰＰ状態依存到
着仮定を得る場合、（上記で、尖度の処理において記述
したように）通常、ＢＰＰコールブロッキングを計算す
る代わりに式９を用いてコールブロッキング確率を算出
する方がよい。したがって、以下のコールブロッキング
についての説明は、（尖度の近似式とは逆に）状態依存
到着仮定が自然にモデルで持ち上がるケースについて向
けられている。重要な例は、有限ソース入力のケースで
ある。完全共有手段で、利用者ｊ要求が任意の時間（タ
イムブロッキング）に受け入れられない確率は、

【数６５】 である。上記式において、ｂ_j≡（ｂ_1j，．．．，
ｂ_pj）は、クラスｊについての条件ベクトルである。

【０１００】上述したように、利用者ｊ要求がポワソン
過程に到着した場合、式６５はまた、コールブロッキン
グを得るが、一般的でない。しかしながら、到着レート
が状態依存である場合、コールブロッキングは常に、修
正されたモデルにおいてタイムブロッキングを計算する
ことにより得られる。Ｂ_jを利用者ｊブロッキング確率
（コールブロッキング）とする。Ｂ≡（ｂ_ij）を条件マ
トリックスとする。一般に、

【数６６】 である。

【０１０１】しかしながら、λ_j（ｎ_j）ｆ（ｎ）は、λ
_j（０）ｆ（ｎ）として書き直すことができるので、式
６５は、

【数６７】 として書き直すことができる。上記式において、バーｆ
（ｎ）は、λ_j （ｍ）≡λ_j （ｍ＋１）で置換されたバ
ーλ_j （ｍ）を伴うｆ（ｎ）のアナログであり、バーｇ
（Ｋ）は、バーλ_j （ｍ）で置換されたｆ（ｎ）を伴う
ｇ（Ｋ）のアナログである。このようにして、式６７に
おける利用者ｊブロッキング確率Ｂｊは、クラスｊ到着
レート関数がλ_j （ｍ）からバーλ_j （ｍ）へ変更され
る修正されたモデルのための式６５におけるタイムブロ
ッキング数量Ｂ^t _jと一致する。

【０１０２】λ_j （ｍ）＝α_j ＋β_j ｍである特別なケ
ースの場合、

【数６８】 であり、よって修正されたモデルは、同様の一般形式の
モデルである。線形到着レート関数を有するモデルの場
合、コールブロッキングを計算するためのアプローチ
は、性能評価（Performance Evaluations） １９８７
年、第７巻、２６７〜２８４ページ「回路切り換え集積
サービスネットワークにおける混雑確率（Congestion P
robabilities in a Circuit-Switched Integrated Serv
ices Network）」の２７３ページでＺ．デュジオン（Z.
Dzion）およびＪ．Ｗ．ロバーツ（J.W.Roverts）によ
って指摘された。

【０１０３】ＵＬおよびＧＭ境界を有するモデルには、
異なった式が必要出有る。式６５と平行して、ＵＬおよ
びＧＭ境界を伴うタイムブロッキングは、

【数６９】 であり、上記式におけるｇ（Ｋ，Ｕ，Ｎ）は規格化定数
である。コールブロッキングはまた、修正されたパラメ
ータを伴うタイムブロッキングＢ^t _jである。以下、図７
に示されたブロッキング確率コンピュータにおける他の
キーとなるステップに戻って説明をする。図７に示され
たように、ブロッキング確率コンピュータプロセスのス
テップ７０２は、認識のため正規近似アルゴリズムを適
用し、リソースモデルから非常に軽いロードのリソース
を取り除くことである。このステップは、反転を容易に
するためステップ７０７における反転を行う前に行われ
る。

【０１０４】正規近似方法の詳細は、図８に図示されて
いる。まず、ステップ８０１において、各リソース上の
各利用者により用いられる容量の平均と分散が決定され
る。さらに詳しくは、リソースおよび利用者が一定であ
るとし、ｉとｊのサブスクリプトは省く。到着レート関
数が線形、即ちλ（ｋ）＝α＋ｋβであると仮定する。
上述したように、これは、ポワソン到着の標準ケースと
尖度パラメータがあるケースとを含む。容量制約がない
場合、サービス中の要求の数の平均および分散量は、

【数７０】 となる。各要求がｂのリソースユニットを使用するた
め、リソースユニットの数の関連する平均および分散量
は、式７０におけるｍおよびｖについて、

【数７１】 である。

【０１０５】しかしながら、ＵＬ限界ＵおよびＧＭ限界
Ｌをまだ考えなければならい。この目的のため、条件付
正規近似が用いられる。概念は、常に使用中の要求の数
が通常式７０の平均ｍおよび分散量ｖで無秩序で変化し
て分布されるが、条件はＵを決して超えない。これは、
バーＮ≡（Ｎ（ｍ，ｖ）｜Ｎ（ｍ，ｖ）≦Ｕで表わされ
る。使用された容量（リソースユニットの数）がＣ
（Ｌ，Ｕ）で示されるとする。Ｃ（Ｌ，Ｕ）は、Ｎ≦Ｌ
およびｂＮである場合、ｂＬである。従って、正規分布
の特性を用いて、Ｃ（Ｌ，Ｕ）の平均および分散量は計
算される。この目的ために、φ（ｘ）を標準（平均０、
分散量１）正規密度関数とし、Φ（ｘ）wp累積分散関数
とする。

【０１０６】利用者の占有度は、条件付正規分散量（Ｎ
（ｍ，σ２）｜Ｎ（ｍ，σ２）≦Ｕ）により近似化され
ると仮定し、いつでも使用される容量の最初の２つのモ
ーメントは、

【数７２】 であり、上記式において、

【数７３】 であり、また

【数７４】 であり、

【０１０７】上記式において、

【数７５】 である。通常、分散量は、

【数７６】 である。加えて、

【数７７】 であり、

【数７８】 である。

【０１０８】これまでの説明は、所定の利用者により使
用されるリソースユニットの平均と分散量を概算する方
法を示してきた。多くの利用客の場合、ＭｊおよびＶｊ
は、利用者ｊについてのＣ（Ｌ，Ｕ）の平均と分散量を
示すものとする。次のステップは、ステップ８０２であ
り、すべての利用者についての合計平均と分散量を見い
出すためにすべての利用者における平均および分散量を
加えることである。次に、正規近似は、実際に必要な容
量を見積もるためにステップ８０３で用いられる。解く
に、常に必要な合計容量がほぼ正規に分布されたと、即
ち、Ｎ（Ｍ，Ｖ）とみなされる。Ｘが必要な容量である
ならば、（Ｘ−Ｍ）／√Ｖは、Ｎ（０、１）として分散
される。このリソース上の利用可能な容量Ｋが深刻な制
約を与えるかどうかが決定される。

【０１０９】この目的のため、「結合パラメータ」

【数７９】 を形成する。なお、

【数８０】 である。故に、式７８における「結合パラメータ」γが
適切な大きさである場合、たとえばγ≧５である場合、
容量Ｋを上回ることはないあろう。前述したばかりの計
算はすべてのリソースにおいて行われる。式７９におけ
る適切な大きさの結合パラメータを有するすべてのリソ
ースは、ステップ８０４でモデルから削除される。

【０１１０】図７に示されるように、ブロック率計算機
能（コンピュータ−）のステップ７０４には、「変換の
有効次数を下げる条件つき分解手続き」を含んでいる。
今議論した正規近似アルゴリズムによって、このステッ
プは、反転処理を容易にするために、ステップ７０７で
の反転手続きを実行する前に処理される。条件つき分解
の背景にあるアイデアは、特別な構造を利用して、数値
反転の有効次数を減らすことができることがかなりある
ことである。この概念を理解するために、Ｇ（ｚ）が、
どの２つの因子も共通の変数を持たない因子の積として
書けるとき、Ｇ（ｚ）の反転は、因子を別々に反転する
ことによって達成され、反転の次数が因子のどれか最大
の次数までへらされることに注目しよう。因子が反転公
式中の計算を通じての積分パスに変数を含んでいないの
で、因数は別々に扱える。

【０１１１】しかしながら、生成関数が共通の変数を持
たない別々の構成要素に因数分解されることは、２つの
関係しない問題を持っていることに対応するので、事実
上は起こらない。アイデアは、「条件付き分解」と呼ば
れるより弱い特性を見つける事である。最初に、反転し
ようとするｄ変数を選択し、残っているｐ−ｄ変数の関
数がどの２つの因子も残っているｐ−ｄ変数において共
通の変数を持たない因子の積として書けるかどうかを見
る。すると反転の最大の次数は、ｄに、因子のどれかに
現れるｐ−ｄ変数の最大個数ｍを加えたものである。全
体の反転は、ｄ＋ｍの次数であるとみなせる。アイデア
は、結果の次数ｄ＋ｍが小さくなるように適切なｄを選
択することである。小さな問題では、エミュレーション
ですることができる。

【０１１２】条件付き分解が、ＵＬおよびＧＭ方針が有
効次数を徹底的に減らすのにシステム的に常に利用でき
ることは重要である。方程式１４に示される生成関数を
考えよう。そこでの生成関数は、直接、因子によって表
現されている。方程式１５の関数Ｇ_j（ｚ，ｙ，ｘ）
は、ｚ，ｙ_j およびｘ_j だけを含んでいるので、方程式
１４の有効次数は常にｐ＋２ｒからｐ＋２に減らすこと
ができる。しかしながら、陽（explicit）反転によっ
て、さらに良く実行できる。ｘ_jに関する陽反転は、

【数８１】 となる。ｙ_jに関して式８１の陽反転を実行し、Ｕｊ≧
［Ｎ_j／ｂ_j］が

【数８２】 であることを思い起こす。

【０１１３】なお、式８２からかなり単純になる。Ｎ_j
をｂ_jの多数の整数であると仮定すると、式８２は、

【数８３】 として書き直せる。残りの母関数全体は、

【数８４】

【外３】

【０１１４】式８２および８３は、

【数８５】 として正規化定数のための明確な式を与える。式８４と
８１または式８３を用いることにより、反転の有効次数
は効果的にｐ＋２ｒからｐに減らされた。しかしなが
ら、式８２と８３には項Ｕｊがあるので、計算の複雑さ
は、約Ｕ_j 回で閉じた形式のｐ次元反転のものである。
一般的には、ＵｊはＫｉにつれて増加し得る、しかし多
くのクラスがあれば、大きなＫｉでもＵｊは小さいまま
であり得る。しかしながら、Ｕ_j が非常に大きければ、
このことは、Ｇ_j （ｚ，ｙ_j ，Ｎ_j ）を使いもう１つの
反転レベルを実行するのに有利である。Ｎ_j ／ｂ_j が大
きければ、今度はＧ_j （ｚ，ｙ，ｘ）を使うのに有利と
なるだろう。

【０１１５】特別なケースは、ｆ_j （ｎ_j ）に対応する
式を挿入することにより容易に得られる。λ_j （ｋ）＝
λ_j でμ_j （ｋ）＝μ_j である場合、式８２と８３の計
算は閉じた形式で表現することもできる。特に、式８３
は、

【数８６】 となる。従って、この場合、結合されたＵＬおよびＧＭ
モデルのための計算は、単一のＣＳモデルの場合と同様
の早さである。

【０１１６】図７のステップ７０６で実行された「軽減
負荷不動点近似」は、正確に解くには大きすぎるリソー
ス供用モデルやロスネットワークを近似的に分析するの
に効果的なアプローチである。このアプローチは、ブロ
ックされた要求に対して「交代ルーティング」がある近
似分析システムについても重要である。このアプローチ
で我々は、異なるリソースが確率的に独立したものであ
り、異なるリソースへの利用者の要求の到着プロセスは
互いに独立しているかのように行動するが、どこかの利
用者が被ったブロッキングによって、それぞれのリソー
スでそれぞれの利用者に提示された負荷を減らす。この
近似戦略は、単独のリソースを解決するプロセスと一緒
になって、各々の利用者のブロッキング率を近似する不
動点式の非線形システムを導き、それは反復的に解くこ
とができる。Ｓ．Ｐ．チャン（S.P.Chung） とＫ．ロス
（K.Ross）の「マルチレートロスネットワークのための
軽減された負荷近似（Reduced Load Approximations fo
r Multi-Rate Loss Networks）」、１９９３年、通信に
おけるＩＥＥＥトランザクション、第４１巻、１２２２
〜１２３１ページと、Ｆ．Ｐケリー（F.P.Kelly） の
「ロスネットワーク」１９９１年適用される確率（Appl
ied Probabilty）の年刊の第１巻３１９〜３７８ページ
と、およびＷ．ホイット（W.Whitt） の「サービスがい
くつかの設備から同時に要求されたときのブロッキング
（Blocking When Service is Requiredfrom Several Fa
cilities Simaltaneously）」１９８５年ＡＴ＆Ｔ専門
紙、第６４巻、１８０７〜１８５６ページを参照のこ
と。

【０１１７】この軽減負荷不動点近似スキーマは、ブロ
ック率計算機を使用することによってＵＬおよびＧＭ境
界を持つ大きなリソース共用モデルに適用し、それぞれ
のリソース上のそれぞれの利用者がブロックされる正確
な確率を計算できる。さらに、２つ以上のリソースを持
つモデルを正確に解くことへの本発明の手続きを利用す
ることによって、これらの軽減負荷不動点近似の質を向
上することが時にはできる。そこで我々は最初の大きな
リソース共用モデルを効率的に正確に解けるより小さい
サブモデル（ここで一般的には２つ以上のリソースを持
つ）に分解できる。我々はまた、これらのサブモデルが
独立したものであるかのように行動でき、別のサブモデ
ルの利用者が被ったブロッキングによって、それぞれの
リソースでそれぞれの利用者に提示された負荷を減らせ
る。（交代ルーチングが存在するとき、２つ以上のリソ
ースを持つモデルをブロック率計算機を使用することに
よって正確に解くことはできない。従って、サブモデル
は他のアプリケーションに用いるつもりである。）

【０１１８】２つ以上のリソースがサブモデルで使われ
るときには、どちらのリソースをサブモデルの中で一緒
にグループ化すべきかを決定することが必要である。こ
の目的のため、我々はこれらの新しい軽減負荷近似のた
めの良い分解を確認することが有利であることを発見し
た。我々は、関連づけられた無制限容量のモデルで資源
占有の間の相互関係を計算することによって、それぞれ
の１対の資源がどれぐらいきつくつながれたか見積も
る。無制限容量のモデルは、トラフィック理論におい
て、たとえば尖度や正規近似の概念と関連して、長い伝
統を持っている。Ｗ．ホイットの「ブロッキングを伴う
サービスシステムのためのヘビィトラフィック近似（He
avy-Traffic Approximation for Service Systems with
Blocking ）」ＡＴ＆Ｔ研究所専門紙、第６３巻、６８
９〜７０８ページ、および、Ｚ．デュジオンおよびＪ．
Ｗ．ロバーツの（上記で引用した）文献を参照のこと。
このように我々は、２つのリソースを、それらが相対的
にきつくつながれた、すなわち高い相互関係であると
き、同じサブモデルに置こうと試みる。 本質的に制約
を供給しない非常に軽く負荷のかかった資源（負荷が非
常に軽い資源）は、既にモデルから排除されたと想定さ
れる。Ｋによって部分集合にインデックスを付けて、ｐ
資源をｓ個の部分集合に分割しよう。（それぞれのリソ
ースは、１個１つだけの部分集合に現れる。）リソース
(k、i) を部分集合ｋのｉ番目のリソースとする。ｐ_k を
ｉ番目の部分集合のサイズとする。すると、リソース
は、１＜ｉ＜ｐ_k で１＜ｋ＜ｓである（k、i） の組みで
インデックス付けされる。近似の最初のステップは、ｓ
の部分集合が確率的に独立したものであるとみなすこと
である。それらは別々に解かれる。最初に提示されたそ
れぞれのサブモデルへのトラフィックは、サブモデルを
使うオリジナルのモデルの提示されたトラフィックであ
る。利用者ｊへのブロッキング率への大まかな最初の近
似は、

【数８７】 であり、ここでＢ_kjはサブモデルｋでの利用者ｊへのブ
ロッキング率であり、直接オリジナルのモデルデータに
基づいていると考えられる。式８７は、全体がブロック
されない利用者ｊの確率が各サブモデルにおいてブロッ
クされないその確率の積と等しいと仮定することにより
生じるので、独立した近似を利用する。

【０１１９】サブモデルブロッキング確率Ｂ_kjが比較的
小さい場合、式８７自身が優れた近似となりうる。でな
ければ、他のサブモデルにおいて起きたブロッキングを
考慮するため各サブモデルにおいて到着率を減少させる
のが最も良いと思われる。一般的に、状態依存到着レー
トが存在するので、サブモデルｋにおける利用者ｊのた
めの新たな軽減状態依存到着率関数λ^* _kjが、

【数８８】 とすることにより形成される。

【０１２０】軽減到着率関数λ^* _kj は、サブモデルブロ
ッキング確率Ｂ_ijに依存し、サブモデルブロッキング確
率は、サブモデルで使用された到着率関数に依存する。
したがって、式８７および８８の固定ポイント解答を見
い出すことが必要である。まず、λ^* _kj （ｍ）＝λ_j
（ｍ）とする。サブモデルブロッキング確率Ｂ_kjを得る
ためにサブモデルを解き、式８７を用いて最初の候補の
全体のブロッキング確率Ｂ_j を得る。繰り返し、わずか
な変化が存在するまで、式８７および８８を解く。必要
であれば、反復は、例えば緩和方法により、コンバージ
ェンスを得るために修正されてもよい。たとえば、λ^*
_kj （ｍ）の新しい値は、候補の新しい値の代わりに前
の値と候補の新しい値とのコンベックスな組合せでもよ
い。

【０１２１】軽減負荷近似において個々のリソースの代
わりにサブモデルを活用する利点は、きつく組合わさっ
たリソースが一緒に処理されることが可能なことであ
る。リソースが比較的きつく組合わさっている場合は同
じサブセットにそれらのリソースを入れ、ゆるく組合せ
っている場合には異なるサブセットに入れることは当然
である。

【０１２２】良好な分解を選択するためのキーとなるも
のは、どれほどきつくそれらのリソースが実際に組合さ
わっているかについての有効な概算をＬことである。こ
れを行うひとつの方法は、関連する無限容量モデルにお
ける定常状態占有間の相関関係を算出することである。
リソースｉ₁ とｉ₂ との間の相関関係は、

【数８９】 上記式において、Ｖ（ｉ）は分散量であり、Ｃ（ｉ₁ ，
ｉ₂ ）は共分散である。これらは、利用者の分散量およ
び条件から決定できる。ｂ_ijをリソースｉにおける利用
者ｊ要求によって要求されたリソースユニットの数と
し、ｖ_j を利用者ｊからの使用中の要求の数の分散量で
あるとすると、

【数９０】 および

【数９１】 である。個々のクラスの平均および分散量を算出する方
法は、軽いロードのリソースを取り除くための正規近似
アルゴリズムに関して記述された。最後に、最も強く関
係したリソースは同じサブモデルで一緒にされる。

【０１２３】Ｂ．リソース容量と通信限界の調整 本発明の他の局面に従って、前述したブロッキング確率
コンピュ−タはひとつのリソースの容量を調整し、予想
されるトラフィックロードの変更に応じて、関連するＵ
ＬとＧＭパラメータを調節するために用いられる。（似
たようなプロシージャが複数のリソースのときに用いら
れる。）トラフィック需要が増えたり減ったりすると、
現存するリソース容量は不十分または超過になり、ＵＬ
とＧＭパラメータもまた適正なものでなくなる。リソー
スが限られていることから、最小限のリソースユニット
を新たな需要に合わせて用いることが望ましい。新たな
トラフィックロードに対して、特定のパフォーマンス要
求事項を満たすために、このような最小限の実行可能な
リソース容量をよいＵＬとＧＭトラフィック限界と共に
特定することが目的である。つまり、現在考慮されてい
る最適化における問題とは、ブロッキング確率要求事項
に合っている間に適当なＵＬとＧＭパラメータを選ぶこ
とによってリソース容量を小さくすることである。

【０１２４】本発明はサーチプロシージャを用いて組織
的に様々な候補となるパラメータセッテイングをサーチ
し、それらのなかで最良のものを特定する。サーチプロ
シージャの大きな要素は、ブロッキング確率コンピュー
タを用いて、与えられたパラメータセットに対するブロ
ッキング確率を決定することである。コントロール変数
の数が大きく、最適化問題が確立された数学的性質
（例：単調性とか、コンベックスのような）をもたない
場合、最善の解決法を見つけ出すのに効果的なアルゴリ
ズムを考案するのは難しい。従って、ブロッキング確率
コンピュータを利用して、新たなトラフィックロードに
対する実行可能なよいリソース容量とよいＵＬとＧＭパ
ラメータを確立する発見的サーチ法が用いられる。下記
に詳述される特定のサーチ手法は、たくさんの代替的手
段のひとつとして見なされるべきである。他のサーチプ
ロシージャは、ブロッキング確率コンピュータを主要な
構成要素として用いるそれらの手法によって開発され
る。

【０１２５】サーチプロシージャはリソース容量とＵＬ
とＧＭパラメータを、リアルタイム・レスポンスとして
調整するために実施され、トラフィックロードを変更す
る。リアルタイム・レスポンスにおける時間の幅は異な
るアプリケーションによって異なる。システムのブロッ
ク図は本発明に従って配されされ、図９に示されるリソ
ース共有システム内で容量の調整を行う。容量調整コン
トローラ９０３は容量の調整プロセスを管理する。容量
調整プロセスは利用者プール９０１にいる利用者からま
たはトラフィックロードモニタ９０２からの直接入力の
どちらかで始めることができる。利用者は彼らのサービ
スのグレードを増やしたい、減らしたいといった要求を
示すことができる。トラフィックロードモニタ９０２は
現在の容量が増やされるべき、または減らされるべきと
いうことを示すことができる。容量調整が適正であると
思われるとき、容量調整コントローラ９０３はブロッキ
ング確率コンピュ−タ９０４を用いてサーチプロシージ
ャを行い、新しい要求に見合う適正で新しいリソース容
量を見つける。このことは利用者ＵＬとＧＬ限界の調整
も同様に必要とする。新しい容量と限界が決定される
と、リソース９０５にも変更が施され、新しいパラメー
タが利用者データベース９０６に送られ、ここにおいて
それらは進行中のシステム管理のために用いられる。

【０１２６】１からｒで示されたｒの利用者へサービス
するリソースは、それぞれの利用者ｊはリソースのユニ
ットに要求ｂ_j を要求する。全てのｂ_j が全てのｂ_j の
最大共通分母によって適正に計測されていることと仮定
する。この計測において、全てのｂ_j の最大共通因数は
１である。それぞれの利用者ｊは基準のおよび条件付、
Ｂ^* _jおよびバーＢ^* _jとおのおの表示されるブロッキング
確率条件をもつ。基準の条件Ｂ^* _jは通常のトラフィック
ロードに特定され、それは、各利用者があらかじめ特定
された負荷レベル（利用者とシステムとの間で既に合意
されている）においてリソースに対し要求を提出すると
いうことである。これに対して、条件付条件バーＢ^* _jは
オーバーロードコンディションのいくつかの形に特定さ
れる。ここでは利用者ｊを除く全ての利用者に申込負荷
があらかじめ特定された負荷レベルよりＸパーセント
（例：１０％）上であったと仮定する。他の条件付きブ
ロッキング条件は似たような方法によって扱われるが、
いくつかはさらなる計算に導かれる。

【０１２７】利用者ｊのＵＬとＧＭパラメータがＵｊと
Ｌｊと各々表示されるとする。これらは要求の数の限界
であってリソースユニットの数ではない。他の全ての利
用者が極度のオーバーロードの状態にあるときに最低限
のサービスのグレードを保証するために、利用者ｊは低
位限界Ｌ^* _jをＧＭパラメータにもち、そのために少なく
とも利用者ｊのＬ^* _j要求はシステムによっていかなる時
でも送達される。つまり、Ｌｊ≧Ｌ^* _jということであ
る。加えて、利用者ｊは低位限界Ｕ^* _jをＵＬパラメータ
にもち、ゆえにＵｊ≧Ｕ^* _jとなる。

【０１２８】Ｋをリソースユニットの数（つまりリソー
ス容量）であるとする。また、Ｂ_jとＢ_j を各々基準の
かつ条件付きブロッキング確率とする。ここで、最適化
問題は次のように形式化される：

【数９２】 容量調整プロセスは図１０に説明されている。このプロ
セスはリソースの利用と利用者の需要をステップ１００
１において絶えずモニターすることによって開始する。
システムは周期的にいつリソース容量がステップ１００
２において調整を必要とするかを決定する。調整が必要
とされるとき、ステップ１００３は利用可能なリソース
と利用者条件を決定する。

【０１２９】これらのデータに基づき、サーチプロシ−
ジャは次の４つの大きなステップに従うことによってよ
いリソース容量を見つけ出そうと試みる。 ａ．ステップ１００４においてリソース容量に対する上
限限界Ｋ_uを見つける。 ｂ．ステップ１００５において各利用者ｊのＵＬパラメ
ータに対する上限限界Ｕ_j を見つける。 ｃ．ステップ１００６において各利用者ｊのＧＭパラメ
ータに対する低位限界Ｌ_j を見つけ、そして ｄ．ローカルサーチテクニックを適用し、ステップ１０
０７において上記ａからｃにおいて見つけられた”悲観
的解答”に基づく最も良いローカル最適解答を特定す
る。 これらのステップは下記に順を追って説明される。各ス
テップにおいて、ブロッキング確率コンピュ−タは繰り
返し実施され、候補となるパラメータセッティングのブ
ロッキング確率を計算する。

【０１３０】（１）リソース容量のための上限限界Ｋ_u 基準の申込負荷、ＧＭパラメータの低位限界Ｌ^* _j、各利
用者ｊの無限のＵＬパラメータとリソース条件ｂ_j に基
づき、方程式３１〜３５の通常の概算は、Ｍ_jとＶ_j に
よって各々表示される、各利用者ｊによって占有された
リソースユニット数の意味と差を計算するために用いら
れる。全ての利用者によって占有されたリソースユニッ
ト数の平均と差をＭとＶとし、これらはそれぞれ

【数９３】 によって順々に得られる。基準のトラフィックロードの
上限限界の容量Ｋ_n は以下のステップにより決定され
る。

【０１３１】（ａ）サーチパラメータγを４に設定す
る。 （ｂ）Ｋ＝Ｍ＋γ√Ｖを設定する。基準の申込負荷、リ
ソース容量ＫとＧＭパラメータＬ^* _j、そして各利用者ｊ
の無限のＵＬパラメ−タを用いてブロッキング確率コン
ピュ−タを実施し、各利用者ｊのブロッキング確率Ｂ_j
を計算する。 （ｃ）もし少なくともひとつのｊが、１からＢ_j ＞Ｂ^* _j
であるところのｒまでの間に存在するとき、γを１つづ
つ増やし、ステップｂを続行する。または、Ｋ^*＝Ｍ＋
γ√Ｖを設定し、ステップｄを続行する。 （ｄ）γを１にリセットする。 （ｅ）Ｋ＝Ｍ＋γ√Ｖを設定する。名目的に申込負荷、
リソース容量ＫとＧＭパラメータＬ^* _j、そして各利用者
ｊの無限のＵＬパラメータを用いてブロッキング確率コ
ンピュータを実施し、各利用者ｊのブロッキング確率Ｂ
_jを計算する。 （ｆ）もし少なくともひとつのｊが、１からＢ_j ≧Ｂ^* _j
であるところのｒまでの間に存在するとき、γを１つづ
つ増やし、ステップｅを続行する。または、Ｋ＝Ｍ＋γ
√Ｖを設定すし、ステップｇを続行する。 （ｇ）ブロッキング確率コンピュ−タを繰り返し続行す
ることにより、１からｒまでの全てのｊのためのＢ_j ≦
Ｂ^* _jや全てのＫ^* ≧Ｋ≧Ｋ_u であるときのＫからＫ＊の
間のＫｕを探すための二等分サーチを実行するが、Ｋ＝
Ｋ_u −１であるとき、１からＢ_j ＞Ｂ^* _jであるところの
ｒまでの間に少なくともひとつのｊが存在する。

【０１３２】リソース占有率ＭとＶの計算と、上記のス
テップ（ａ）から（ｇ）までは条件付き（オーバーロー
ド）トラフィックロードのためにくり返され、オーバー
ロードコンディションに対する上限限界容量Ｋｃを見つ
けようとする。単純には、これは全ての利用者がＸ％の
オーバーロードを持っていると仮定することによって行
われる。その後、各利用者のために別々の計算をするこ
とは不要である。最後に、上限限界リソース容量Ｋ_u は
Ｋ_n とＫｃの最大値として選ばれる。

【０１３３】（２）各利用者のＵＬパラメータのための
上限限界 ここに説明するアイデアは、リソースが上記によって得
られた上限容量Ｋ_u を持つという仮定に基づいて、各利
用者ｊのＵＬパラメータＵｊに上限限界Ｕ_j を見つける
ためのものである。これらの上限限界はまず基準の申込
負荷と基準のブロッキング確率条件を考慮することによ
って決定される。そして、同様のプロシ−ジャがオーバ
ーロードと条件付きブロッキング確率条件のためにくり
返される。利用者ｊの最後の上限限界Ｕ_j は基準のそし
てオーバーロードコンディションと、あらかじめ利用者
によって特定された低位限界Ｕ^* _jに対する限界の最大値
に設定される。ＵＬパラメータが基準のトラフィックコ
ンディションであるときの上限限界は次のステップによ
って決定される。

【０１３４】（ａ）基準の申込負荷に基づき、容量の上
限限界Ｋｕ、ＧＭパラメータの低位限界Ｌ^* _j、Ｋｕに等
しいＵＬパラメータ、そして全ての利用者ｊのリソース
条件ｂｊはブロッキング確率コンピュ−タを実施して全
ての利用者のブロッキング確率を決定する。これらの計
算されたブロッキング確率は参考ブロッキング確率とし
てここに続く詳述のなかで参照される。 （ｂ）各利用者ｊのＧＭとＵＬパラメータが各々Ｌ^* _jと
Ｋ_u であると仮定し、各利用者ｊからのサービスにおけ
る要求の数の平均ｍ_jと差ｖ_j を計算する。 （ｃ）セットＣを｛１，２，．．．．ｒ｝と定義する。
γをひとつの上限限界値（例：６）に設定する。この上
限限界値はブロッキング確率コンピュ−タを用いること
によって変えることができ、利用者ｊのブロッキング確
率はブロッキング確率の条件のＹ％（例えば１０％）プ
ラス１からｒまでの各利用者ｊの参考ブロッキング確率
より小さいまたは等しいことを確かめることができる。 （ｄ）それぞれのｊ∈Ｃにおいて、Ｕ_j ＝ｍ_j ＋γ√ｖ
_j を設定する。 （ｅ）リソース容量Ｋ_u 、各利用者ｊのＧＭとＵＬのパ
ラメータＬ^* _jとＵ_j を用いて、ブロッキング確率コンピ
ュ−タを実施して全ての利用者に対するブロッキング確
率を求める。

【０１３５】（ｆ）もし各利用者ｊのブロッキング確率
がブロッキング確率のＹ％プラス１からｒまでの各利用
者ｊの参考ブロッキング確率より小さいまたは等しいと
き、γを１つづつ減らしてステップｄを続行する。もし
そうでない場合はステップｇに進む。 （ｇ）γがブロッキング確率条件のＹ％プラス利用者の
参考ブロッキング確率よりも大きいがγ＋１より小さい
ことに基づいて計算されたブロッキング確率に利用者ｊ
を特定する。Ｓを全てのこのような利用者のセットとす
る。（明確には、Ｓ⊆Ｃ。） （ｈ）ひとつのｊ∈Ｓを選び、Ｕ_j ^*＝ｍ_j ＋γ√ｖ_j と
Ｕ^* _j＝ｍ_j ＋（γ＋１）√ｖ_j を設定する。加えて、そ
れぞれのｋ≠ｊであるｋ∈Ｓに、Ｕ_k ＝ｍ_k ＋γ√ｖ_k
を設定する。

【０１３６】（ｉ）Ｕ_j ^*からＵ^* _jの間のＵｊに二等分サ
ーチを行う。このとき、利用者ｊのいかなるＵＬパラメ
ータもＵｊ＊より小さく、利用者ｊのブロッキング確率
はブロッキング確率条件のＹ％プラス利用者の参考ブロ
ッキング確率よりも大きい。二等分サーチのそれぞれの
ステップにおいて、ブロッキング確率コンピュ−タが実
施され、全ての他のＵＬパラメータであるｋ≠ｊのとき
のＵｋ、ＧＭのパラメータＬｊと変わらない申込負荷を
要求する利用者ｊのブロッキング確率を決定する。 （ｊ）全ての他のｊ∈Ｓのそれぞれにｈ）とｉ）のステ
ップをくり返す。 （ｋ）Ｃ＝Ｃ−Ｓと設定する。もしＣが空でない場合、
γを１つづつ減らしていき、ステップｄを続行する。ま
たは、符合するＵＬパラメータの上限限界（Ｕｊ：ｊ＝
１，２，．．．，ｒ）はこのようにして得られる。 先に指摘したように、このステップａからｋまでのプロ
シ−ジャはオーバーロード通信と条件付きブロッキング
確率条件に対してくり返される。計算を減らすには、全
ての利用者がＸ％のオーバーロードを持つと仮定するこ
とによって実行できる。そして、利用者ｊのＵＬパラメ
ータの最後の上限限界Ｕ_j が名目、オーバーロードコン
ディション、そして利用者によってあらかじめ特定され
た低位限界Ｕ^* _jの各々の限界の最大値をとることによっ
て得られる。

【０１３７】（３）各利用者のＧＭパラメータの低位限
界 各利用者のＧＭパラメータの低位限界を特定する基本的
発想は、ＵＬパラメータの上限限界に関して上記に説明
したものと類似する。 ＵＬパラメータＵｊの上限限界
が決定されていることから、それらはここでＧＭパラメ
ータの低位限界を決定するのに用いられる。完成するた
めに、基準のトラフィックロードのＧＭ限界のためのス
テップが次に与えられる：

【０１３８】（ａ）基準の申込負荷のリソース容量Ｋｕ
に基づき、各利用者ｊのリソース条件ｂｊ、 ＧＭパラ
メータの低位限界Ｌ＊ｊ、 ＵＬパラメータＵｊはブロ
ッキング確率コンピュータを実施し、各利用者のブロッ
キング確率を決定する。これらのブロッキング確率は参
考ブロッキング確率として次に参照される。 （ｂ）各利用者ｊのＧＭとＵＬパラメータを各々Ｌ^* _jと
Ｕ_j と仮定する。（２９）によって、各利用者ｊからの
業務における要求数の平均ｍｊと差ｖｊを計算する。 （ｃ）セットＣを｛１，２，．．．，ｒ｝と定義する。
(を低位限界値（例：６）に設定する。この低位限界値
はブロッキング確率コンピュータを用いることによって
変えることができ、各利用者ｊのブロッキング確率がブ
ロッキング確率条件のＹ％（例：１％）プラス１からｒ
までの各利用者ｊ参考ブロッキング確率より低い又は等
しいことを確かにする。 （ｄ）ｊ∈Ｃのそれぞれにおいて、Ｌ_j ＝ｍａｘ｛０，
ｍ_j ＋β√ｖ_j ｝を設定する。

【０１３９】（ｅ）リソース容量Ｋ_u 、各利用者ｊのＧ
ＭとＵＬパラメータを各々Ｌ^* _jとＵｊを用いて、ブロッ
キング確率コンピュータを実施して各利用者のブロッキ
ング確率を求める。 （ｆ）各利用者ｊのブロッキング確率が各利用者ｊのブ
ロッキング確率がブロッキング確率条件のＹ％（例：１
％）プラス１からｒまでの各利用者ｊ参考ブロッキング
確率より低い又は等しいとき、(を１つづつ増やしステ
ップｄを続行する。または、下に示すステップｇに進
む。 （ｇ）(がブロッキング確率条件のＹ％プラス利用者の
参考ブロッキング確率よりも大きいが、(−１より小さ
いことに基づいて計算されたブロッキング確率に利用者
ｊを特定する。Ｓを全てのこのような利用者のセットと
する。（明確には、Ｓ⊆Ｃ。） （ｈ）ひとつのｊ∈Ｓを選び、Ｌ_j ^*＝ｍａｘ｛０，ｍ_j
＋β√ｖ_j ｝とＬ^* _j＝ｍａｘ｛０，ｍ_j ＋β√ｖ_j ｝を
設定する。加えて、それぞれのｋ≠ｊであるｋ∈Ｓに、
Ｌ_k ＝ｍａｘ｛０，ｍ_k ＋β√ｖ_k ｝を設定する。

【０１４０】（ｉ）Ｌ_j ^*からＬ^* _jの間のＵｊに二等分サ
ーチを行う。このとき、利用者ｊのいかなるＧＭパラメ
ータもＬｊより大きく、利用者ｊのブロッキング確率は
ブロッキング確率条件のＹ％プラス利用者の参考ブロッ
キング確率よりも大きい。二等分サーチのそれぞれのス
テップにおいてブロッキング確率コンピュ−タが実施さ
れ、全ての他のＵＬパラメータであるｋ≠ｊのときのＵ
ｋ、ＧＭのパラメータＬｊと変わらない申込負荷を要求
する利用者ｊのブロッキング確率を決定する。 （ｊ）全ての他のｊ∈Ｓのそれぞれにｈ）とｉ）のステ
ップをくり返す。 （ｋ）Ｃ＝Ｃ−Ｓと設定する。もしＣが空でない場合、
(を１つづつ増やしていき、ステップｄを続行する。ま
たは、全てのＧＭパラメータの低位限界（Ｌｊ：ｊ＝
１，２，．．．，ｒ）はこのようにして得られる。

【０１４１】ＵＬパラメータの上限限界に類似して、こ
のステップａ）からｋ）までのプロシージャはオーバー
ロード通信と条件付き確率条件のために繰り返される。
計算を単純にするために、これは全ての利用者がＸ％の
オーバーロードを持つと仮定することによって得られ
る。そして、各利用者ｊのＧＭパラメータの最後の低位
限界Ｌ_j が名目、オーバーロードコンディション、そし
て利用者によってあらかじめ特定された低位限界Ｌ^* _jの
各々の限界の最大値をとることによって得られる。

【０１４２】（４）ローカル最適化解答をサーチする リソース容量Ｋｕ、ＵＬ限界｛Ｕ_j ｝、ＧＭ限界｛Ｌ
_j ｝によって今のところ得られる解答は、「悲観的」解
答である。すべての基準のそして条件付きブロッキング
確率条件が満たされるので適当ではあるが、さらに改善
できるかどうかを見るべき余地は残される。このローカ
ルサーチプロシージャはローカル最適を探すための出発
点として適当な解答を用いることである。高いレベルに
おいて、サーチプロシージャの主要なアイデアは上限限
界Ｋｕのリソース容量をそこに適当なＵＬまたはＧＭパ
ラメータで基準のそして条件付きブロッキング確率条件
を満たすものが存在するかどうかをチェックすることに
よって減らすことを試みることである。もしそのような
パラメータセッティングが存在するなら、より良い解答
が見つけられ、プロシージャはそれ自身がリソース容量
の更なる減数を繰り返す。または、それ以上容量の減数
をすることができなくなった時にプロシージャはストッ
プし、「最善の」適当な解答が得られる。Ｋ、Ｕ_j そし
てＬ_j をリソース容量とし、各利用者ｊのＵＬとＧＭパ
ラメータをローカルサーチアルゴリズムによって検討中
の候補解答とする。サーチプロシージャは次のように与
えられる。

【０１４３】（ａ）これまでの最善の解答を記録する：
ｊ＝１からｒごとにＫ＝Ｋ_u ，Ｕ_j ＝Ｕ_j およびＬ_j ＝
Ｌ_j （ｂ）２の倍数のリストを空にして、ＵＬとＧＭパラメ
ータ（Ｕ₁ ，．．．Ｕ_r，Ｌ₁ ，．．．，Ｌ_r ）におけ
る２の倍数をリストへの最初のエントリーとして入力す
る。Ｋ＝Ｋ−１と設定する。 （ｃ）候補解答を検討する：各利用者ｊのリソース容量
Ｋ_u 、ＵＬとＧＭパラメータＵ_j そしてＬ_j 。 （ｄ）新たな候補容量とトラフィックパラメータのため
に、ブロッキング確率コンピュータを実施して基準のそ
して条件付きブロッキング確率（各々Ｂ_j 及びバーＢ_j
として示される）を求める。 （ｅ）もし全てのブロッキング確率条件が合致し、例え
ば、もし全てのｊ＝１からｒであるときに（式）であっ
て（式）だとすれば、試された容量Ｋは適当である。こ
の場合、試された解答を新たな最善の解答として記録
し、ステップｂを続行する。もしくは、ステップｆを続
行する。

【０１４４】（ｆ） (ｊを各利用者ｊのＢ_j ／Ｂ^* _jとバ
ーＢ_j ／バーＢ^* _jの最大に設定する。η* とη^* をｊ＝
１からｒであるときのすべての(ｊ の最大と最小にそれ
ぞれ設定する。もしη^* ≧１／η* であれば、ステップ
ｇ）を続行する。もしくは、ステップｈ）を続行する。 （ｇ）η^* ≧１／η* という事実は利用者が例外的に高
いブロッキング確率（基準のまたは条件付きのいずれ
か）を持つことを暗示する。ｊを全ての利用者間の最大
(ｊを生じる利用者インデックスであるとする。もしＵ_j
＜Ｕ_j であれば、Ｕ_j を１つづつ増やす。もしＵ_j ＝
Ｕ_j であれば、Ｌ_j を１つづつ増やす。ステップｉ）を
続行する。 （ｈ）η^*≧１／η*という事実は利用者が例外的に低い
ブロッキング確率（基準のあるいは条件付きのいずれ
か）を持つことを暗示する。 ｊを全ての利用者間の最
小(ｊを生じる利用者インデックスであるとする。もし
Ｌ_j ＞Ｌ_j であれば、Ｌｊを１つづつ減らす。もしＬ_j
＝Ｌ_j であれば、Ｕ_j を１つづつ減らす。

【０１４５】（ｉ）ＵＬとＧＭパラメータ（Ｕ
１，．．．，Ｕｒ，Ｌ１，．．．，Ｌｒ）の２の倍数が
すでにリストに含まれているかどうかをチェックする。
もし含まれていない場合、新たなエントリーとして倍数
をリストに追加してステップｃを続行する。もしくは、
プロシージャは更なる容量の減算をできず、既にステッ
プ（ａ）又は（ｅ）によって記録されたようにローカル
最適化解答が見つけられる。

【０１４６】Ｃ．リソース障害に対するレスポンス リソース共有システムにおけるリソース障害に従ってト
ラフィック迂回を実行するため、本発明にしたがって調
整されたシステムのブロックダイアグラムは図１１に示
される。図には２つの主要な構成要素があり：（１）リ
ソースのセット１１００と、（２）１１１０として示さ
れる中央集権オペレーションセンター（ＣＯＣ）であ
る。リソースステイタスモニタ１１０１は、１つあるい
はより多くのリソースが不良のときは常に不良を探知す
る。リンクをリソースとして持つような遠距離通信シス
テムでは、リンクステイタスはネットワーク内のスイッ
チで典型的にモニターされる。リンク障害はここで、例
えばシグナルの損失によって探知される。

【０１４７】リソース障害が探知されると、リソースス
テイタスモニタ１１０１はＣＯＣ１１０１内のトラフィ
ック迂回コントローラ１１０５にシグナルを送り、ＣＯ
Ｃは不良となったリソースから代替リソースまでの迂回
需要のプロセスを制御する。リソース障害がひとつの一
時的状況として見なされることから、それはリソース上
の最近の利用者負荷のトラフィック迂回の基礎をなすた
めに、ｎｅｇｏｔｉａｔｅされたパラメータよりも（も
しくはそれに加えて）望ましいと推量される。こういう
訳で、システム上の最近の負荷を知ることが必要であ
る。このために、トラフィックロード計測システム１１
０２は利用者利用状況を始終記録する。このようなシス
テムは通常、例えば請求書とリソース管理（前のセクシ
ョンＢで説明したような容量修正）といったどのような
方法によっても得ることができる。

【０１４８】トラフィックロード計測システム１１０２
は、トラフィックロードデータをＣＯＣ１１０１内のト
ラフィックロードデータベース１１０４に周期的に送
る。このため、リソース障害の時点で、トラフィック迂
回コントローラ１１０５は最近のトラフィックロードか
らトラフィックロードデータベース１１０４へのアクセ
スを持つ。不良が発生したとき、トラフィック迂回コン
トローラ１１０５は代替リソース（例：それに代わるル
ート）の可能なセットで、不良となったリソースによっ
て合致している需要に見合うために用いられることので
きるものを決定する。このために、トラフィック迂回コ
ントローラ１１０５は代替リソースの有効性について必
要なデータを迂回データベース１１０６から求める。そ
して、トラフィック迂回コントローラ１１０５はブロッ
キング確率コンピュータ１１０７を実施してどれだけの
負荷がリソースの代替セットのそれぞれに迂回され得る
かを決定する。ブロッキング確率コンピュータ１１０７
は全ての利用者のオリジナルのそして迂回したブロッキ
ング確率が適切なものかどうかを迂回後に決定するため
に必要とされる。迂回するために適切な量を見つけるこ
とは更なる分析を必要とし、それは以下に示される。ト
ラフィック迂回コントローラ１１０５はまた適切な上限
（ＵＬ）と保証された最小（ＧＭ）の限界をも決定し、
これらの代替リソース上のオリジナルのトラフィックと
迂回したトラフィックを保護する。トラフィックコント
ローラ１１０５が適切な迂回プロセスを決定すると、こ
の迂回プロセスは実行のために迂回トラフィック限界強
制システム１１０３に通信される。例えば、遠距離通信
ネットワークにおいて、迂回限界強制はネットワーク内
のスイッチによって実行可能である。トラフィック限界
強制システム１１０３はこのように制御が実行されるこ
とを確実にする。

【０１４９】本発明の他の局面に従うと、ブロッキング
確率コンピュータ１１０７は不良となったリソースから
の利用者の要求を迂回するのに用いられるので、少なく
とも需要の一部は残るリソースによって見合うことがで
きる。リソース共有システムでは、各利用者の要求は一
定の期間異なるリソースのあるユニットを占有する。ひ
とつのリソースが不良となると、不良となったリソース
を求める利用者の要求はブロックされる。

【０１５０】利用者の要求に応えるこのような代替リソ
ースの使用は共通である。図１に示された迂回スイッチ
遠距離通信ネットワークの例では、リンク（例えばリソ
ース）がファイバー切断のような何らかの理由によって
不良となったとき、通話は他のリンクを通って、不良と
なったリンクをバイパスして迂回されることができる。
多くの場合、リソース障害であるときの特定の利用者の
要求を満たすために必要なリソースユニットの合計数
は、平常の状態にあるときよりも高い；例えば、代替ル
ートがしばしばより多くのリンクを持っているなど。そ
れにもかかわらず、代替リソースの利用は、不良が発生
したときに利用者間でリソースを効率的に共有するのに
多大な柔軟性を与えるものである。

【０１５１】本発明のこの局面によって提示された問題
とは：リソース障害を与えられて、システムはいかに効
率的に、他の利用者に与えられるサービスの質に逆作用
することなく、元々不良となったリソースを要求してい
た将来の利用者要求を残りのリソースに迂回することが
できるかということである。（不良となった段階で、リ
ソースからサービスを受け取るというそれらの利用者要
求はなくなるが、これらの要求は将来の需要の一部とし
て再出現するものと予想される。）この問題に対する明
白な解決法は、不良となったリソースからの利用者要求
を十分な容量の空きを持つ他の適用可能なリソースに迂
回することである。しかしながら、これを行う方法は明
らかではない。まず、トラフィックと実行要求が蓋然的
に特徴づけられていることから、可能な容量の空きは実
のところ事前には知られていない。加えて、リソース障
害はリソースに対する利用者要求の到達度の増加と共に
発生する。例えば、電話リンクに損害を及ぼす地震、洪
水、台風のような出来事は、災害地への多数の通話を発
生させる原因ともなり、このため不良となったリンクへ
のより多くの需要を向けることになる。不良となったリ
ソースへの利用者要求の、それはここで残るリソースに
迂回されているが、このように潜在的に多大な増加は、
当初の利用者へのサービスの質を深刻に低下させること
となる。さらに、迂回した利用者への最低保証されたグ
レードのサービスも行われない。

【０１５２】本発明のこの局面の中心となるアイデア
は、不良となったリソースから代替リソースまでの利用
者要求の予想されるトラフィックロードの適正な比率を
迂回させることである。公平基準を用いて、全ての迂回
した利用者への通信の同じ比率を迂回するよう試みる。
しかしながら、代替スキームが考えられ、それは異なる
利用者に異なる優先順位を与えるものである。ここに挙
げる方法はこれらの他のスキームに適正な修正を適用す
るものでもある。負荷の適正な比率を迂回するのに加
え、プロシージャはＵＬとＧＭパラメータを各利用者の
迂回したトラフィックへのサービスと同級のものを保証
しようと試みるように調節する。最後に、ＵＬ限界の２
つの新たなセットがそれぞれのオーバーロードに対する
オリジナルのそして迂回したトラフィック全体の保護を
確実にするために確立される。

【０１５３】迂回プロセスは迂回トラフィックを送達す
ることができる代替リソースの１セットを考えることに
よって始まる。プロシージャはこのリソースの第一セッ
トにどれだけ迂回されることができるかを決定する。も
しまだより多くの迂回されるべきトラフィックがある場
合、プロシージャは迂回トラフィックを送達できる代替
リソースの他のセットを考える。迂回プロセスは全ての
適用可能な代替リソースが検討されるか、影響を受けた
利用者が全て代替リソースに迂回されるまでの間続行す
る。本発明の他の局面を伴って、本迂回プロシージャの
主要な構成要素はブロッキング確率コンピュータであ
る。それは代替リソースに迂回するための通信量と関連
するＵＬとＧＭトラフィックパラメータを決定するのに
用いられる。不良に従ったこの迂回プロシージャのステ
ップを実証するために、一般的なリソース共有システム
と遠距離通信ネットワークが次の説明において別々に考
えられる。一般的システムの主な目的は比較的単純なセ
ッティングでのトラフィック迂回の一般的コンセプトを
説明することなので、主なアイデアは簡単に把握でき
る。遠距離通信ネットワークの例はひとつの大切なアプ
リケーションクラスの実行可能性を実証するためであ
る。

【０１５４】二つのリソースを持つ一般的リソース共有
システムを考えると、一方は平方形を含みもう一方は１
と２により指示される円を含む。ここに４人の利用者が
いるとする。通常の状況では、利用者１と２はそれぞれ
の必要するひとつの平方形を要求し、利用者３と４はそ
れぞれの必要とするひとつの円を要求する。適正なＵＬ
とＧＭ限界が各利用者に与えられていると想定する。こ
れらがＵｊとＬｊとして利用者に指示されているとす
る。残る詳細説明とは異なり、セクションＣ全体を通し
て、 ＵＬとＧＭ限界は要求の代わりにリソースユニッ
トの点から特定される。このため、 Ｕｊは他のセクシ
ョンでいうところのｂｊ時間である。平方形リソースが
不良となったとき、円リソースは代替案として用いられ
ることができるが、利用者１と２からのそれぞれの要求
は二つの円を必要とすると考えられる。もしこのような
不良のとき、迂回したトラフィックである利用者１と２
の要求するような円のために適正なＵＬとＧＭトラフィ
ック限界を特定し強制することを、元々のトラフィック
である利用者３と４の要求するような質のサービスの質
を満足するべく保護している間に可能な限り早く実行さ
れることが望ましい。利用者１と２の迂回は、平方形リ
ソースの不良に応じた円リソースへの二つの新しい利用
者の割り当てとして円リソースを要求すると見ることが
できる。

【０１５５】この一般的リソース共有システムでは、ト
ラフィック迂回プロシージャが絶えず各利用者の要求の
申込負荷をモニターしている。平方形リソースの不良の
おこるすぐ前に利用者ｊの要求した見積り申込負荷をρ
ｊとする。（この見積もり申込負荷は利用者による当初
の負荷と不良に先立って最近のヒストリー上で実際に観
測された負荷の両方を繁栄する。）平方形リソースが不
良となると、円リソースを要求する利用者１から４に対
して関連するリソース条件はｂ２１＝２，ｂ２２＝２，
ｂ２３＝１，ｂ２４＝１である。そして、プロシージャ
は円リソースを要求する利用者１と２の申込された負荷
の０≦α≦１という端数を迂回しようと試みる。

【０１５６】新たな候補申込負荷が迂回したトラフィッ
クのために当初の申込負荷とは異なることから、ＵＬと
ＧＭ限界を修正することは自然である。単純な方法はこ
れらの限界の比率を、対比された申込負荷と比べて新た
な申込負荷αρｊという比率によって古い限界に直すこ
とである。しかしながら、ブロッキング条件のより良い
合致のために、通常の概算が用いられる。通常の概算は
申込負荷が変わるときに容量が変わらなければならない
という方法を説明するので、ブロッキング確率は（ほ
ぼ）固定されたままである。こういう訳で、円リソース
に対してこのように迂回したトラフィック（ｊ＝１と２
であるときにＵ_j とＬ_j で指示される）に対する新たな
ＵＬとＧＭ限界は、通常の概算によって決定されること
ができる。すなわち、ｊ＝１と２であるときに、迂回し
た利用者ｊ要求によって必要とされた円の数が普通に与
えられたランダムの変数Ｎ（ｍ_j ，σ_j ²）、このときｍ
ｊ＝αρｊｂ２ｊであるが、によって概算されたとし、
ｚｊが利用者ｊ要求の到着尖度であるときの差σｊ２
が、αρ_j ｚ_j ｂ² _2j とする。ｃとｂをブロッキング確
率条件と他の技術上の考慮によって正しく選ばれたとこ
ろの実際に値付けられた二つのパラメータとする。（ｃ
とｄの典型的な値は２から４、そして−４から−２の間
に各々おかれている。）もしρｊがＵＬとＧＭ限界のＵ
ｊとＬｊが当初割り当てられたところの当初契約された
申込負荷であれば、ｃとｄが選ばれてすなわちα＝１の
ときＵ_j ＝ｍ_j ＋ｃσ_j とＬ_j ＝ｍ_j ＋ｄσ_j になる。
そして、利用者ｊ＝１と２のとき、新たなＵＬパラメー
タＵｊ’が、ｍｊ＋ｃσｊと（Ｋ２−Ｌ３−Ｌ４）に最
も近い正の整数の最小となるべく選ばれ、そのときＫ２
は可能な円の総数である。さらに、新たなＧＭパラメー
タＬｊ’はｍｊ＋ｄσｊと（ｋ２−Ｌ３−Ｌ４）に最も
近い整数の最小値となるべくセットされる。

【０１５７】オリジナルと迂回したトラフィックを結合
し、円リソースに対する新たな候補申込負荷がベクトル
ρ＝（αρ１、αρ２、ρ３、ρ４）と、上記によって
得られた関連するＵＬとＧＭ限界によって与えられる。
ここでプロシージャはブロッキング確率コンピュータを
実施し円リソースを共有するにあたって各利用者の要求
に対するブロッキング確率を決定する。これらの確率は
ブロッキング確率条件と比較される。全ての条件が満足
するかしないかによって、プロシージャは、より多くの
又はより少ない利用者１と２の要求をαへの単純な二進
的サーチによって円リソースに迂回するような試みを繰
り返すことができる。（候補となるＵＬとＧＭ限界はそ
れぞれの新しいαに調整される。）最後に、プロシージ
ャは利用者１と２の要求の適正な端数を関連する特定さ
れたＵＬとＧＭパラメータにより円リソースに迂回した
後ストップする。迂回したトラフィックに対するＵＬと
ＧＭ限界をブロッキング確率コンピュータを用いてさら
に調整し、純化することが望ましい。

【０１５８】各利用者からの迂回したトラフィックに対
する個々のＵＬ限界に加えて、プロシージャはオリジナ
ルトラフィック（利用者３と４の要求）と迂回したトラ
フィック（利用者１と２の要求）に対するふたつのＵＬ
限界（ＵｏとＵｄによって示される）を求めることによ
ってさらなるオーバーロード保護を提供する。恐らく大
きく異なるリソース条件を持つ異なる利用者がこれらの
新たなＵＬ限界のために結合されることから、これらの
限界は要求よりはリソースユニットにおいて表現される
ことが大切である。オリジナルトラフィックによって占
有された円の数をΣ⁴ _j=3ρ_jｂ_jに等しい普通に与えられ
たランダムの変数であるＮ（ｍ_o 、σ_o ²）によって概算
させる。このとき平均ｍ_o とΣ⁴ _j=3ρ_j ｚ² _jである差σ
_o ²を持つ。そして、ｃが典型的に２から４までの幅にあ
る適正なパラメータであって、必ずしも上記のパラメー
タｃに等しい必要がないときに、Ｕ_o がｍ_o ＋ｃσ_o と
（Ｋ₂ −Ｌ₃ −Ｌ₄ ）に最も近い正の整数の最小として
選ばれる。これに似て、迂回した利用者１と２の要求に
対するＵｄを求めることができる。新たなパラメータｃ
はこれもまた前のパラメータとは異なる。例えば、迂回
したトラフィックよりもオリジナルトラフィックに対し
てより大きい保護を与えることが望ましいと思われる。
これらのＵＬ限界はブロッキング確率コンピュータを用
いることによってチェックされ純化される。

【０１５９】平方形リソースが役割に戻るまでの間、シ
ステムはそれぞれ新しい利用者１と２の要求を円リソー
スの役割に迂回する。その間に各利用者のＵＬとＧＭト
ラフィック限界は、全体のオリジナルと迂回したトラフ
ィックのための新たなＵＬ限界と同様、続けて強制され
る（前述の通り）。この方法は、利用者１と２の要求が
必要とされる平方形リソースが不良となった場合に役立
てられるだけでなく、全ての利用者に対するサービスの
グレードもまたＵＬとＧＭ限界によって保証され、保護
される。リソース障害に直面する迂回したトラフィック
とオリジナルのトラフィックの両方を保護する基本原則
は、前述した一般的な例のように本質的に同じ方法によ
って、たくさんのシステムにおいて機能できる。しかし
ながら、不良リソースのための代替リソースの特定は、
一般例よりもっと踏み込んだものになる。さらに、新た
に設定されたＵＬとＧＭ限界はより複雑になりがちでも
ある。ある特定のシステムへの提案されたアプローチの
適応性を示すためには、遠距離通信ネットワークが考え
られる。このネットワークは現在の回路スイッチネット
ワークまたは将来のＡＴＭ技術に基づくＢ−ＩＳＤＮネ
ットワークとなりうる。ネットワーク内のリンク障害に
応えるトラフィック迂回のための高レベルのフローチャ
ートは図１２に示され、迂回プロシージャは次に詳細に
渡り説明される。

【０１６０】図１に示されたような、多数の通信リンク
を持つ遠距離通信ネットワーク、それらが問題のリソー
スであると考える。高い信頼性を確実にするために、そ
こにはしばしば、ネットワーク内のひとつのスイッチ
（ノード）から他のスイッチへの複数のルート（つまり
複数のリンクによるパス）がある。このように、それぞ
れの通話はおそらくいくつかのルートのうちのひとつを
経由され、その選択はひとつの”ルーチンアルゴリズ
ム”によって通話がセットアップされた時点で行われ
る。１９９２年３月３１日発行、米国特許５，１０１，
４５１号、アッシュによるリアルタイムネットワークル
ーチンアルゴリズムのような、遠距離通信ネットワーク
において共通に利用されるルーチンアルゴリズムのいく
つかは、それらが現在のネットワーク状況を用いて各通
話に最も適当なルートを選択することから、”動的”ア
ルゴリズムと呼ばれる。特定のルーチンアルゴリズムは
ここでは重大ではない；それは静的または動的と言え
る。

【０１６１】本発明の適応性を実証するために、ルーチ
ンアルゴリズムは障害への応答のなかで適応できないも
のと適応できるものに次のように分類される。非適応ル
ーチンでは、ひとつのスイッチから他へのルートのある
リンクが障害となったとき、全部のルートが交換されな
ければならない。発信元−発信先スイッチペアへの通話
は他のあらかじめ設定された代替ルートを経由される。
対して、適応ルーチンアルゴリズムは、障害の起こった
リンクのふたつのエンドスイッチ（障害エンドスイッチ
として参照される）間で自動的に新たなルートを探し出
す。そして、通話は不良となったリンクから他の障害エ
ンドスイッチを素通りして新たな代替ルートに送られ
る。最後に、通話ルーチンはそこから発信先に達するま
でのオリジナルルートの残り部分へと進む。そこには障
害エンドスイッチをつなぐ複数の新たなルートがある可
能性がある。この場合、問題となっている各通話は、用
いられているルーチンアルゴリズムに従って、もし可能
であればこれらのルートのひとつを取ることができる。
又は、ラウンドロビンスキーム、シークエンシャルオー
バーフロースキーム（新たなルートが優先順位に従って
調整される場合、優先順位の高いルートが使用中のと
き、優先順位の低いルートが通話を通すために試みられ
る。）または他の状況に応じた動的スキームが本目的の
ために用いられる。

【０１６２】もし考え中のネットワークが非適応ルーチ
ンアルゴリズムを用いるとき、ソーススイッチがその通
話を不良となったルートから他の代替ルートに迂回し、
パフォーマンスを保証・保護するためにＵＬとＧＭ限界
を強制することが効率的であろう。この場合、トラフィ
ック変換は発信元−発信先スイッチペアを基本に実行さ
れるべきである。その一方で、適応ルーチンアルゴリズ
ムでは、障害エンドスイッチにとって障害リンクからス
イッチにつながる代替ルートへのトラフィックを迂回す
ることと、迂回した通話に対して関連するＵＬとＧＭ限
界を強制することがより効率的である。そして、トラフ
ィックはソースと通話の行き先を考えることなく、単純
に通話クラス毎を基本に迂回される。同じ原則が非適応
ルーチンアルゴリズムに適用できるが、通信モニタリン
グ、迂回、そして発信元−発信先を基本とした強制にお
いて複雑さを増している。

【０１６３】遠距離ネットワークは図１１のブロックの
ような中央集権オペレーションセンター（ＣＯＣ）を持
ち、通信モニタリング、迂回そして他の保守機能を行う
と仮定する。また、トラフィック迂回のために重要な情
報がＣＯＣにおいて得られると仮定する。この情報は、
ａ）ネットワーク内の各発信元−発信先スイッチペアに
対して予測される通話負荷、ｂ）各スイッチペアに対す
る通話に好ましいルート、ｃ）ブロッキング確率、契約
（申込）負荷、それぞれのリンク上の各通話クラスに対
するＵＬとＧＭ限界におけるサービスのグレードを含
む。ネットワーク内の契約負荷により、これらのＵｌと
ＧＭパラメータは特定及び強制され、最低限のグレード
のサービスを保証し、通話の各クラスのオーバーロード
に対する保護をおこなう。

【０１６４】リンクがｉ通話のｒクラスを運ぶと仮定
し、リンクに対する契約負荷が

【外４】 と各リンクｉのＬｏに基づき、ＣＯＣはビンディングパ
ラメータｃｊとｄｊを

【数９４】 として再計算し、そのときｚｊはクラスｊ通話の到達尖
度、ｂｊはリンクｉ上のクラスｊ通話によって占有され
た回路の数である。トラフィック迂回プロセスは図１２
のフローチャートのステップ１２０１から始まり、ここ
でネットワーク内の各スイッチは絶えずブロックされた
通話の端数（ブロッキング確率のような）とスイッチか
ら現れる各リンク上の異なる通話クラス（運ばれた負荷
のような）のトラフィックロードの量をモニタする。各
スイッチはそれぞれのリンクに対して運ばれた負荷とブ
ロッキング確率をＣＯＣに周期的に伝え、ＣＯＣはデー
タを将来の参考のためにセーブする。

【０１６５】スイッチがステップ１２０２においてリン
クからの信号の損失によってリンク障害を探知すると、
ＣＯＣに障害を伝える。スイッチＡとＢを障害となった
リンクに対する障害エンドスイッチとする。障害に関す
る通知を受け取った後、ＣＯＣはステップ１２０３にお
いて、最も障害となったリンクに対して実行された負荷
とブロッキング確率の最も間近のデータをサーチする。
ＣＯＣは各トラフィッククラスに対する申込負荷のよい
見積もりを、オリジナル契約申込負荷と実行負荷の最近
のヒストリーに基づいて開発できると推定される。見積
もられた負荷は単純にオリジナル契約申込負荷（そのた
めのデータが必要とされない）もしくは最も間近の実行
負荷の見積もりであるが、これらと他の歴史的データの
より複雑な組み合わせであるといえる。簡単にするため
に、ここでは最も間近な実行負荷見積もりだけが用いら
れていると推定する。

【０１６６】ここにスイッチＡとＢから障害リンクを経
由して送られた通話のｒクラスがあり、通話クラスが
１、２、．．．ｒによって指示されるとする。さらに、
障害リンクに対する各通話クラスｊに対する実行負荷と
ブロッキング確率が、ｊ＝１、２、．．．，ｒのときに
各々ФｊとＰｊとして指示されるとする。データのサー
チに伴い、ＣＯＣはスイッチＡとＢからの障害リンク上
のクラスｉ通話の申込負荷の量をステップ１２０３にも
ある１−Ｐｊによって得られたρｉ／ｉと見積もる。ト
ラフィック変動のために、この申込負荷はリンクに対す
る契約負荷とは異なると予測されていることに注意。Ｃ
ＯＣはこのためρｉ／ｉの場合、例えば最小のまたは観
察された（実行された）負荷とそのクラスに対する契約
負荷別の他なる機能によってρｉ／ｉを交換することに
よって修正することを選択する。_f （ρ¹ _f，
ρ² _f，．．．，ρ^r _f）を迂回されるべき通信の量とす
る。

【０１６７】次に、ステップ１２０４では、迂回される
べく残っている通信の量であるＰｆがゼロに到達したか
どうかで決定が下される。もしそうであれば、迂回プロ
シージャはうまく完了し、プロセスはまたは、ＣＯＣは
ステップ１２０５に進み、スイッチＡとＢからの次に最
も短い代替ルートでまだこのトラフィック迂回において
使用されていないものを確定するために、ステップ１２
０７で止まる。ルートが通らなければならない中間スイ
ッチの数から、最短の代替ルートを特定することが望ま
しいと思われる。そして、マンスールとギュエンによる
米国特許番号第５，０５８，１０５号によって発明され
たような技術を適用し、最短の代替ルートを見つけるこ
とができる。もしステップ１２０６において新たな代替
ルートが存在しないことが決定されると、障害リンクを
素通りするスイッチＡとＢからの全ての代替ルートは、
迂回したトラフィックの一部分によって考慮され負荷が
付けられる。この場合、図１２のプロセスは、障害リン
クからの全てのトラフィックをネットワーク内のオリジ
ナルトラフィックに対するサービスのグレードを下げる
ことなく完全に迂回することができないとしても、ステ
ップ１２０７においてストップする。

【０１６８】新たな代替ルートが存在すると、ＹＥＳと
いう結果がステップ１２０６で発生し、ＣＯＣはブロッ
キング確率コンピュータをステップ１２０８において実
施し、（式）によって指示されるクラス１からｒまでの
クラスの、代替ルートが障害リンクから受けることので
きるトラフィックロードの量を決定する。特に、この方
法は全てのクラスのトラフィックを迂回するために比率
的手段を用いる；つまり、全クラスからの同じ比率の通
話が障害リンクから代替ルートへ迂回される。更に、本
分析におけるひとつの概算ステップとして、ここでは試
されたルートの全リンク上の全クラスに対するオリジナ
ルトラフィックは相互に独立している。このように、モ
デル内で、迂回した通話のみが代替ルートの全リンクの
同時保有を要求する。別のアプローチは、代替ルートに
焦点を合わせる代わりに全通話クラスによるネットワー
ク全体を考慮するものである。しかしながら、大きなネ
ットワークを分析するにあたって、ブロッキング確率コ
ンピュータは減算した負荷概算に適用しがちであり、こ
れはまたリソース依存のある度合を無視するものであ
る。代替ルートに迂回されるべきトラフィックの比率は
次のステップによって決定される。

【０１６９】（ａ）選ばれた代替ルートを１、
２、．．．、ｊによって指示されたＪリンクによって成
るものとする。ＣＯＣはこれらのリンクのそれぞれの上
の各通話クラスに対する申込負荷を、実行ロードを１マ
イナスリンク上の通話クラスに対するブロッキング確率
で割ることによって見積もる。（実行負荷と各リンク上
のブロッキング確率は周期的にＣＯＣで更新され、記録
される。）迂回したトラフィックにより、これはリンク
に対して契約され計測された申込負荷の最小のもしくは
他のいくつかの機能であるといえる。簡単に説明するた
めに、各リンクが通話クラスの同じ数ｒを持つと仮定す
る。Ｊリンクのひとつに対する申込負荷がρ _o≡
（ρ¹ _o，ρ² _o，．．．，ρ^r _o）によって指示されるとす
る。

【０１７０】（ｂ）選択された代替ルートに対して、Ｊ
リソースと通話（利用者）の（Ｊ＋１）ｒクラスを持つ
リソース共有モデルを組み立て、そこで各リソースは代
替ルートのＪリンクのひとつを表わし、ｊｔｈと要求の
ｒクラスの（ｊ＋１）ｓｔセットはルートのｊｔｈリン
ク上のオリジナルと迂回したトラフィックにそれぞれ応
える。上述のように、全リンク上のオリジナルトラフィ
ッククラスは相互に独立しており迂回した通話のみが全
Ｊリンクの同時保有を要求すると思われる。αＵとαＬ
が、障害リンクから迂回されるべきトラフィックの比率
に対するそれぞれ上限と低位限界を指示するとする。始
めに、αＬ＝０、αＵ＝１と設定する。 （ｃ）α＝（α_U −α_L ）と迂回したトラフィックの量
をαρ _f ≡（αρ¹ _f，αρ² _f，．．．，αρ^r _f）となる
代替ルートのρ _dに設定する。 （ｄ）αＵとαＬの差があらかじめ特定された許容度よ
り小さいとき、αは代替ルートに迂回されるべきトラフ
ィックの残りである。つまり、ρｄは（αρ¹ _f，α
ρ² _f，．．．，αρ^r _f）になるべく解決される。加え
て、１からｒに等しく通話クラスｊ に対する通話クラ
ス毎ＵＬとＧＭパラメータであるＵｊｄとＬｊｄと、各
リンクｉ上のオリジナルと迂回したトラフィックに対す
る新たなＵＬ限界Ｕｏ、ｉとＵｄ、ｉが見つけられる。
プロシージャは止まる、もしくは下記のステップｅを続
行する。

【０１７１】（ｅ）代替ルートの各リンクｉに対して、
γを、迂回トラフィックの予測される回路占有率の割合
からリンクｉ上で契約したトラフィックの割合へ設定す
る。つまり、

【数９５】 を設定する。 リンクｉ上の迂回したトラフィックに対
するＵＬとＧＭ限界をＵ _d＝（Ｕ¹ _d，Ｕ² _d，．．．，Ｕ^r
_d）とＬ _d＝（Ｌ¹ _d，Ｌ² _d，．．．，Ｌ^r _d）とする。ｃ_j
とｄ_j を、上述のリンクｉに対して予め決定されたＵＬ
とＧＭ限界に対する通話クラス毎ビンディングパラメー
タとする。各通話クラスに対して、Ｕ^j _dを

【外５】 に最も近い正の整数の最小数に設定する。

【０１７２】（ｆ）各通話クラスｊに対し、代替ルート
の全リンクｉに対する全てのＵ^j _dにおける最小数を選
ぶ。付加的な表記法（ｎｏｔａｔｉｏｎ）を取り入れる
ことなく、 Ｕ^j _dにこのような最小数を指示させる。こ
れに似て、各クラスｊに対して、全リンクｉに対するＬ
^j _dのなかで最小のＬ^j _dを求める。（ＵＬとＧＭトラフィ
ック限界 Ｕ^j _d とＬ^j _dは代替ルートのあらゆるリンク上
のクラスｊ通話に対して強制される。） （ｇ）オーバーロードに対する更なる保護を行うため
に、オリジナルトラフィックと迂回したトラフィックに
対する新たなＵＬ限界（あらゆるリンクｉに対しＵｏｉ
とＵｄｉにより指示される）の２セットを次に示す通常
概算によって求める。代替ルートの各リンクｉに対し、
リンクｉ上のオリジナル（契約された）トラフィックに
よって占有された回路の数を通常の方法で与えられたラ
ンダムの変数でＮ（ｍｏ，σ２ｏ）、によって概算させ
る。このとき平均ｍｏは

【数９６】

【０１７３】正しく選ばれたビンディングパラメータｃ
とｄを用いて、 Ｕｏｉはｍｏ＋ｃσｏとＫ_i−Σ
^r _i=j（Ｌ^j _o＋Ｌ^j _o）に最も近い整数の最小数となるべく
選ばれる。限界ＵｏｉとＵｄｉはブロッキング確率コン
ピュータを用いることによってチェックされ、整調され
ることができる。

【０１７４】（ｈ）組み合わされた申込負荷ρｏとρ
ｄ、そして通話クラス毎 ＵＬとＧＭパラメータ、そし
てオリジナルと迂回したトラフィックに対する全体ＵＬ
限界を用いて、ブロッキング確率コンピュータを実施
し、リソース共有モデル内のオリジナルと迂回した各通
話クラスに対するブロッキング確率を求める。各通話ク
ラスに対するブロッキング確率と、予め特定したブロッ
キング要求事項（ＣＯＣとして知られる）を比較する。
この比較において、同じブロッキング要求事項がオリジ
ナルと迂回した通話の両方に適用されることができると
すれば、それらは同じクラスのものである。もし、ブロ
ッキング確率を持つ通話クラスのどれかで要求事項を越
えているものがあれば、α_U＝αと設定する。（ひとつ
のオプションとして、プロシージャが迂回したトラフィ
ックに対するＵＬとＧＭ限界を調整しようと試みた後
で、他のパラメータが変えられておらず、少なくとも通
話クラスに対するブロッキング確率が要求事項を妨害す
るのが見つかった場合にのみαＵはαに設定される。こ
のオプションは、通常の概算によって見積もられたＵＬ
とＧＭ限界が、問題の迂回したトラフィックの量に対し
て適正ではないことから、いくつかのパラメータセッテ
ィングに対する迂回の効率性を上昇させる。）または、
α_L ＝αと設定する。そして、αについてステップｃの
二等分サーチを続行する。

【０１７５】ステップ１２０８とＵＬとＧＭパラメータ
において選択された代替ルートに迂回されるべきトラフ
ィックの量を特定した後、ＣＯＣは失敗エンドスイッチ
Ａと関連するトラフィック限界を持つ代替ルート上の他
のスイッチに通知する。そして、ＣＯＣは残るトラフィ
ックをステップ１２０９の障害リンクから迂回されるよ
うに計算し、プロセスはステップ１２０４に戻り、もし
あれば残りのトラフィックを迂回する。このプロシージ
ャは全トラフィックがうまく障害リンクから迂回される
まで、または全代替ルートが検討され、迂回したトラフ
ィックのある量によって負荷付けられるまで続けられ
る。

【０１７６】通話クラス毎ＵＬとＧＭ限界とオリジナル
通話に対する新たなＵＬ限界は代替ルート上のスイッチ
によって強制される。より精密に述べると、リンクと結
び付けられた限界は、リンクの上にトラフィックを送る
スイッチによって観察される。これに対して、通話クラ
ス毎ＵＬとＧＭ限界と迂回した通話に対する新たなＵＬ
限界は失敗エンドスイッチＡによってのみ強制される。
このように、スイッチＡは、迂回した通話に対して正し
いトラフィック強制をするために、様々な通話クラスま
たはリンクに対するＵＬとＧＭ限界に反応する最小数を
知ることだけを必要とする。

【０１７８】効果的なトラフィック強制を可能にするひ
とつの方法は、障害エンドスイッチとＣＯＣだけに分か
るリンク障害を保持することである。結果として、ネッ
トワーク内の他のスイッチはあたかもリンク障害が起こ
らなかったかのようにトラフィックを通り続けることが
できる。通話がスイッチＡからＢへと経由する必要があ
るとき（スイッチＡが発信元あるいは通話の経由スイッ
チであるとき）、スイッチＡはもし通話が迂回した通話
（例えば障害リンクを要求したもの）であるかどうかを
特定することができる。もしそうであれば、スイッチＡ
は、上述のように、確立された代替ルートのひとつへの
通話を受け取るあるいは迂回する前に、もし適用できる
とすればネットワーク内で用いられる通話迂回アルゴリ
ズムに従い、ＵＬとＧＭトラフィック限界がトラフィッ
ク強制のためのステップに従って満足であることを確か
める。もしくは、ラウンドロビンスキーム、順次オーバ
ーフロースキーム、もしくは状況に応じた動的スキーム
が選択を行うために用いられる。迂回スキームは代替ル
ートへの通話到着の尖度を変えることができることに注
意。このように、与えられた迂回スキームに対して、ブ
ロッキング確率を正確に決定するためには、ブロッキン
グ確率コンピュータへのインプットに対する様々な代替
ルートへの尖度パラメータを調整することが望ましい。

【０１７９】もしネットワークの通話迂回アルゴリズム
が障害リンクの負荷状況の使用を求め、迂回したトラフ
ィックに対して直接適用することができないとすれば、
確立された代替ルート間の迂回したトラフィックの負荷
状況の記録を追うことにより、このような情報は失敗エ
ンドスイッチによって集められることができる。ＧＭパ
ラメータがそれぞれに可能なオーバーロードからの代替
ルートに沿って迂回したトラフィックに対する最小級の
サービスを保証し、新たなＵＬパラメータがオリジナル
と迂回したトラフィックを保護することから、障害リン
クはトラフィック迂回メソッドにより、確立された代替
ルートによって部分的にまたは完全にも「取り替えられ
た」と見なすことができる。事実、このトラフィック迂
回プロシージャは複数のリンク障害とスイッチ障害を取
り扱うことができる。スイッチ障害は、スイッチから発
生する全リンクに対する複数の（同時的な）リンク障害
のひとつのケースとして見なされることに注意。同時発
生しない複数のリンク障害の場合、トラフィックが先着
順ベースによって一時にひとつの障害の起こったリンク
から迂回されるので、迂回プロシージャはうまく機能す
ることができる。もし特殊なリンクが異なる障害の起こ
ったリンクに対するいくつかの代替ルートに関連する場
合、そのリンクは複数の障害の起こったリンクから迂回
したトラフィックに負荷付けられる。結果として、リン
クは各障害の起こったリンクから迂回した通話クラスの
付加的なセットを運ぶ。この場面において、様々な障害
の起こったリンクから迂回したトラフィックはそれらの
関連するＵＬとＧＭトラフィック限界を持ち、これは上
記説明と同じ方法で、反応するスイッチによって別々に
強制される。

【０１８０】スイッチ障害に反応するトラフィックを迂
回するために、プロシージャは上に示したような各スイ
ッチに隣り合うスイッチ（例：スイッチから発生する各
リンク上のトラフィックロード）へのトラフィックロー
ドだけでなく、隣り合うスイッチの、隣への迂回ルート
の量もモニターすることを要求する。トラフィックロー
ドは周期的にＣＯＣに伝えられる。結果として、スイッ
チが不良のとき、隣り合うスイッチの各ペア間のトラフ
ィック量はＣＯＣに解る。そして、不良スイッチを素通
りして一方の隣り合うスイッチからもう片方の隣り合う
スイッチまでのトラフィックの量を迂回するために、同
じ迂回プロシージャが用いられる。ここで、不良エンド
スイッチは隣り合うスイッチである。加えて、迂回した
トラフィックを受ける代替ルートは、不良スイッチの隣
にあった一方のスイッチからもう一方へのルートであ
る。プロシージャは迂回したトラフィックの量と各代替
ルートに対する関連するＵＬとＧＭ限界を決定する。こ
れまでと同様、ＵＬとＧＭトラフィック限界は代替ルー
トに沿ったスイッチによって強制される。

【０１８１】更に、同じプロシージャの少数のバリエー
ションがＣＯＣをもたない遠距離通信ネットワークにも
適用できる。この場合、各スイッチはローカルにトラフ
ィックロードをモニターし、保持する。リンク障害が発
生すると、割り当てられた非同時性ベルマン−フォード
アルゴリズム（１９９２年プレンティス−ホール社刊Ｄ
ａｔａ Ｎｅｔｗｏｒｋ誌４０４〜４１０ページ、Ｂｅ
ｒｔｓｅｋａｓ ａｎｄ Ｇａｌｌａｇｅｒ参照）のよ
うな割り当てられたアルゴリズムが用いられ、最短の代
替ルートを特定する。代替ルートが見つけられると、不
良エンドスイッチＡは代替ルート上のスイッチから迂回
するために必要な通信データを収集する責任がある。通
信データにより、スイッチＡはＣＯＣが行うのと同じ方
法でトラフィック迂回を実施する。結果として、迂回し
たトラフィックの量と関連するＵＬとＧＭ限界は代替ル
ートに対して決定される。そして、スイッチＡがルート
上のスイッチにトラフィック強制に対する限界を通知す
る。もしスイッチＡが障害の起こったリンクから迂回さ
れるべき残りのトラフィックがあることを見つけると、
次ぎなる代替ルート上の更なるトラフィック迂回を開始
する。オリジナルトラフィックに対するＵＬとＧＭ限界
によるトラフィック強制はリンク上に送られたスイッチ
によって終わるまで続行される。加えて、迂回したトラ
フィックに対するトラフィック限界は不良エンドスイッ
チＡによって強制される。本発明の様々な修正や変更
は、当業者とっては明らかであろう。従って、本発明は
請求の範囲によってのみ限定される。

【図面の簡単な説明】

【図１】本発明が実行される従来の回線切り換え通信ネ
ットワークの説明図である。

【図２】本発明の原理に従って配された加入許可制御シ
ステムのブロック図である。

【図３】図２の加入許可制御システムによって実行され
た加入許可制御プロセスを示す流れ図である。

【図４】新たな利用者条件を決定するためのプロセスを
示す流れ図である。

【図５】求められたグレードのサービスが実行可能でな
い場合の代替グレードのサービスのためのプロセスを示
す流れ図である。

【図６】トラフィック限界が実施されるプロセスを示す
流れ図である。

【図７】図２のブロッキング確率コンピュータ２０４が
作動するプロセスを示す流れ図である。

【図８】正規近似式技術を用いて軽いロードのリソース
を確認するための本発明によるプロセスを示す流れ図で
ある。

【図９】リソース共有システムにおける容量調整を行う
ための本発明に従って配されたシステムのブロック図で
ある。

【図１０】図９のシステムで実行された容量調整プロセ
スを示す流れ図である。

【図１１】リソース共有システムにおけるリソース障害
に応答してトラフィックディバージョンを実行するため
の本発明に従って配されたシステムのブロック図であ
る。

【図１２】図１１のシステムで実行されるトラフィック
ディバージョンを示す流れ図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 キン ケー．レウン アメリカ合衆国 08820 ニュージャーシ ィ，エディソン，レインフォード ロード 10 (72)発明者 ワード ホイット アメリカ合衆国 07920 ニュージャーシ ィ，バスキング リッジ，ヒル トップ ロード 86

Claims (11)

【特許請求の範囲】
1. 【請求項１】 現存の利用者にサービスをしている共有
   リソースへの新たな利用者の加入許可を制御する方法に
   おいて、前記方法は、 前記現存の利用者のブロッキング確率条件を決定する工
   程と、 前記新たな利用者それぞれにより望まれるブロッキング
   確率条件およびサービスのグレードとを決定する工程
   と、 前記現存の利用者の前記条件を侵害することなく前記新
   たな利用者の条件が満たされるか否かを決定する工程
   と、前記決定は、規格化定数を有する積行列のリソース
   共有モデルに従って行われ、 前記新たな利用者条件が満たされる場合、前記新たな利
   用者が前記共有リソースに加入許可されることを許容す
   る工程とからなり、 最後に述べた決定する工程は、前記リソース共有モデル
   の前記規格化定数の母関数を数値反転することにより、
   前記新たな利用者および前記現存の利用者による前記共
   有リソースの使用のためのブロッキング確率を算出する
   工程を含むことを特徴とする方法。
2. 【請求項２】 現存の利用者にサービスをしている共有
   リソースへの新たな利用者の加入許可を制御する方法に
   おいて、前記利用者はそれぞれ所定のトラフィックロー
   ドを有し、前記方法は、 各前記現存の利用者および前記新たな利用者のための基
   準および条件付ブロッキング確率条件を決定する工程
   と、前記基準ブロッキング確率条件は前記所定のトラフ
   ィックロードで前記利用者すべてによるコンプライアン
   スに従ったものであり、前記条件付プロッキング条件は
   前記所定のトラフィックロードからひとりまたはそれ以
   上の前記利用者による逸脱に基づいたものであり、 前記新たな利用者の基準および条件付ブロッキング確率
   条件両方が前記現存の利用者の基準および条件付ブロッ
   キング確率条件の両方を侵害することなく満たされるか
   否かを決定する工程と、 前記新たな利用者の基準および条件付ブロッキング確率
   条件両方が満たされる場合、前記新たな利用者が前記共
   有リソースに加入許可されることを許容する工程とから
   なることを特徴とする方法。
3. 【請求項３】 共有リソースへの新たな利用者の加入許
   可を制御する方法において、前記新たな利用者は多数の
   サービスのグレードで提供されることが可能であり、 前記現存の利用者の条件を定義する記憶された情報を検
   索し、前記新たな利用者それぞれによって要求される条
   件およびサービスのグレードを得る工程と、 前記検索された情報に応じて、前記現存の利用者の前記
   条件を侵害することなく前記新たな利用者の条件が満た
   されるか否かを決定する工程と、前記決定は、規格化定
   数を有する積行列のリソース共有モデルに従って行わ
   れ、 前記新たな利用者条件が満たされる場合のみ、前記新た
   な利用者が前記所望のサービスのグレードで前記共有リ
   ソースに加入許可されることを許容する工程とからなる
   前記方法であって、 最後に述べた決定する工程は、 前記リソース共有モデルの前記規格化定数の母関数を数
   値反転することにより、前記新たな利用者および前記現
   存の利用者による前記共有リソースの使用のためのブロ
   ッキング確率を算出する工程を含むことを特徴とする方
   法。
4. 【請求項４】 現存の利用者にサービスをしている共有
   リソースへの新たな利用者の加入許可を制御する方法に
   おいて、前記現存の利用者および前記新たな利用者は多
   数のサービスのグレードで提供されることが可能あり、
   各前記サービスのグレードは、トラフィック条件および
   ブロッキング条件により定義され、 （ａ）前記現存の利用者のサービスのグレードと、
   （ｂ）前記新たな利用者により望まれるサービスのグレ
   ードとを含む情報を得る工程と、 新たな利用者により望まれる前記サービスのグレードに
   応答して、前記新たな利用者への前記共有リソースの使
   用におけるＵＬおよびＧＭ限界を指定する工程と、 前記新たな利用者のサービスのグレードが前記現存の利
   用者の条件を侵害することなく得られるか否かを決定す
   る工程と、 前記あらたな利用者のサービスのグレードが得られる場
   合、前記新たな利用者が前記所望のサービスのグレード
   で前記共有リソースに加入許可されることを許容する工
   程とからなる前記方法であって、 前記決定する工程は、前記新たな利用者のためのブロッ
   キング確率を算出し、前記ブロッキング確率が前記新た
   な利用者に割り当てられたＵＬおよびＧＭ限界を満たす
   か否かを決定する工程を含むことを特徴とする方法。
5. 【請求項５】 新たな見込み利用者が所望のサービスの
   グレードでリソースに加入を許可されるか否かをリアル
   タイムで決定するためのリアルタイム加入許可制御のた
   めの方法において、 見込み利用者のための所望のサービスのグレードを決定
   する工程と、 所望のサービスのグレードが見込み利用者とすべての現
   存の利用者両方を考慮して合致されるか否かを決定する
   工程と、 所望のサービスのグレードが提供される場合、所望のサ
   ービスのグレードで新たな利用者の加入を許可する工程
   と、 所望のサービスのグレードが提供されない場合、より低
   いサービスのグレード実行可能であるか否かを決定する
   工程とからなることを特徴とする方法。
6. 【請求項６】 新たなレベルの利用者要求を満たすよう
   に共有リソースの容量を調整する方法において、 利用者要求の変更に応じて、前記リソースのための新た
   な要求レベルを決定する工程と、 すべての利用者のブロッキング条件を満たすように容量
   を調整する工程とからなり、 前記調整する工程は、前記リソース共有モデルの前記規
   格化定数の母関数を数値反転することにより前記利用者
   による前記共有リソースの使用のためのブロッキング確
   率を算出する工程を含むことを特徴とする方法。
7. 【請求項７】 共有リソースシステムにおいて障害の起
   きたリソースから代替リソースへ利用者の使用を転送す
   る方法において、 リソースの障害を決定するためにシステムをモニタする
   工程と、 適切な代替リソースを確認する工程と、 前記代替リソース上の現存および転送された利用者のブ
   ロッキング確率条件に適合するために使用を調整する工
   程とからなり、 前記調整する工程は、規格化定数を有する積行列のリソ
   ース共有モデルに従って行われ、 前記転送された利用者および前記現存の利用者による前
   記共有リソースの使用のためのブロッキング確率は、前
   記共有モデルの前記規格化定数の母関数を数値反転する
   ことにより算出されることを特徴とする方法。
8. 【請求項８】 異なるグレードのサービスを提供し、且
   つリソースを共有する利用者へのオーバーロードに対す
   る保護機能を提供する技法において、 その要求上に各利用者の上限（ＵＬ）および保証された
   最小（ＧＭ）限界を割り当てる工程と、前記上限限界
   は、いつでもサービスを受けることのできる利用者から
   のリクエストの数上の上限を置き、前記保証された最小
   限界は、利用者からの特定数の要求を受けるリソース内
   の常に利用可能なリソースユニットが存在することを保
   証し、これにより、積行列定常状態分布を有するリソー
   ス共有モデルを形成でき、 （ａ）積行列定常状態分布を表わす規格化定数（または
   分割関数値）の項における前記モデルを直接表現し、 （ｂ）規格化定数の母関数を形成することにより規格化
   定数を直接表現し、 （ｃ）母関数を数値反転することにより機能するブロッ
   キング確率コンピュータ（ＢＰＣ）を使用してリソース
   共有モデルを解く工程とからなることを特徴とする技
   法。
9. 【請求項９】 前記数値反転する工程は、 リソース共有モデルに対して調整されたスケーリングア
   ルゴリズムを有するフーリエ級数方法を使用する工程を
   含むことを特徴とする請求項８の方法。
10. 【請求項１０】 （ａ）正規近似スキームを用いて各リ
    ソース上のトラフィックロードをおよそ決定し、 （ｂ）基本的に制約を与えない軽くロードされたリソー
    スがいくつか存在するか否かを決定し、 （ｃ）前記最後の工程に応じて、前記母関数を形成する
    前に前記モデルから軽くロードされたリソースを削除す
    るために前記（ＢＰＣ）が設けられたことを特徴とする
    請求項８もしくは９に記載の発明。
11. 【請求項１１】 前記正規近似および条件付分解工程後
    に、モデルが解決可能であるかを決定し、解決可能であ
    る場合、モデルをほぼ解くための減少ロード固定ポイン
    ト近似（reduced-load fixed-point approximation）を
    実行する工程をさらに含むことを特徴とする請求項１１
    の方法。