(57)【特許請求の範囲】
【請求項１】
異なる処理速度の複数の異なるアプリケーションプロセッサ間の分散システムにおいて、新たに入着する呼要求の処理を割り当てる方法であって、
各呼プロセッサの利用度を判定するステップであって、該利用度は各呼プロセッサに対する最大可能負荷に関連する現在の負荷の程度であるステップ、
各呼プロセッサの応答時間を判定するステップであって、該応答時間は呼プロセッサが単位時間当たりに処理できるタスク数の程度であるステップ、
各新着呼要求に対応する該新着呼の処理が完了されるべき最大カットオフ時間を判定するステップ、
最初の入着呼要求を受け取った後、該最初の入着呼要求に関連して増加した負荷に適応する利用度を有する最短の応答時間を持つ第１のプロセッサを判定するステップ、
該第１のプロセッサが該最初の入着呼要求が該最初の入着呼要求に関連した該最大カットオフ時間内に処理されることを可能とする利用度を有する場合に、最初の入着呼要求の処理を該第１のプロセッサに割り当てるステップ、及び、
該第１のプロセッサが、該最初の入着呼要求が該最初の入着呼要求に関連した該最大カットオフ時間内に処理されることができない利用度を有する場合に、該最初の入着呼要求を廃棄するステップからなる方法。
【請求項２】
異なる処理速度の複数の異なるアプリケーションプロセッサ間の分散システムにおいて、新たに入着する呼要求の処理を割り当てる装置であって、
各呼プロセッサの利用度を判定する手段であって、該利用度は各呼プロセッサに対する最大可能負荷に関連する現在の負荷の程度である手段、
各呼プロセッサの応答時間を判定する手段であって、該応答時間は呼プロセッサが単位時間当たりに処理できるタスク数の程度である手段、
各新着呼要求に対応する該新着呼の処理が完了されるべき最大カットオフ時間を判定する手段、
最初の入着呼要求を受け取った後、該最初の入着呼要求に関連して増加した負荷に適応する利用度を有する最短の応答時間を有する第１のプロセッサを判定する手段、
該第１のプロセッサが該最初の入着呼要求が該最初の入着呼要求に関連した該最大カットオフ時間内に処理されることを可能とする利用度を有する場合に、最初の入着呼要求の処理を該第１のプロセッサに割り当てる手段、及び、
該第１のプロセッサが、該最初の入着呼要求が該最初の入着呼要求に関連した該最大カットオフ時間内に処理されることができない利用度を有する場合に、該最初の入着呼要求を廃棄する手段からなる装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信交換システムにおいて通信を制御する装置および方法に関し、特に、異なる呼プロセッサを有する通信交換システムの分散処理制御の装置および方法に関する。
【０００２】
【従来の技術】
一般にネットワークはアプリケーションプロセッサ（ＡＰ）を有するが、それらのプロセッサがすべて同じ性能特性を有するわけではなく、しかも、独立のアプリケーションを処理する各プロセッサが、１つの限定された最大時間限界内に応答することを要求される。このようなシステムで重大な関心のある１つの問題は、次の呼要求サービスを処理するのにどのＡＰを割り当てなければならないかを決定する問題である。このような状況は、ネットワーク所有者が、ディジタル処理および呼処理（ＣＰ）に対する増大し続ける顧客の需要を満たすために新たな高性能のＡＰを追加することによって費用効率よくシステムを拡張しながら既存のシステムにおける投資を保護するという、コンピュータおよび通信の領域で生じる。増大し続ける顧客のＣＰ需要を費用効率よく満たすためには、高速なハードウェア、新しいソフトウェア、新しいミドルウェアおよび最新の標準を特徴とする安価なＡＰが、進歩し続けるテクノロジーによってこれまで提供されてきている。例えば、ＣＰは、図１および図２にそれぞれ示したシステム１００およびシステム２００のような次世代の呼制御システムにおける中心的機能である。図１のシステム１００では、ＡＰ１０２１〜１０２ｎは高速なトークンリング１０４によって相互接続される。図２のシステム２００では、ＡＰ２０２１〜２０２ｍはＡＴＭ２０４１〜２０４ｋによって接続される。さらに、ＡＰ１０２１〜１０２ｎあるいは２０２１〜２０２ｍはそれぞれ、複製されたデータベースを有し、任意の呼を処理するように機能的に装備されている。ＡＰは、指定された期間内にＣＰ要求に応答して、次の問題を回避しなければならない。すなわち、呼が、顧客によって期待されるように設定あるいは破棄されないことにより顧客の不満を引き起こす問題、および、混雑時間中の呼が確立されないことによりサービスプロバイダの収入が損失する問題である。
【０００３】
また、分散コールセンタアプリケーションにおける自動呼分配においても、次の呼が、（複製された、あるいは、ネットワーク接続された）データベースを共有する複数の呼プロセッサのうちの１つに割り当てられる必要がある場合に問題が生じることがある。
【０００４】
【発明が解決しようとする課題】
この問題を解決するための従来の試みは発見法に基づいている。例えば、米国特許第４，８２７，４９９号（発明者：Ｗａｒｔｙ  ｅｔ  ａｌ．）による方法では、各プロセッサに配分される新たな負荷の割合は、まず、ＡＰが過負荷になったときに変更される初期化パラメータによって決定される。過負荷プロセッサ数の割合があるしきい値を超過したときにシステム過負荷であると認識される。その場合、拒絶される新たな呼の割合は、システムがもはや過負荷でなくなるまで徐々に増大し、そうでない場合には同様に減少する。米国特許第４，９７４，２５６号（発明者：Ｃｙｒ  ｅｔ  ａｌ．）は、システム過負荷に対する応答時間はこの方法における最適値より短いことを示し、改良を提案している。この方法では、各ＡＰの平均利用度を周期的に測定することによって、次の期間の各ＡＰに配分される新たな呼の割合は、その期間中のすべてのＡＰの占有度を等しくするように発見的に調節される。スケジューラは、占有度が平均値を超えるＡＰの割合を減少させ、占有度が平均値を下回るＡＰの割合を増加させる。スケジューラは、ある期間におけるすべてのＡＰの平均利用度またはシステム全体の呼損数を用いてシステム過負荷を認識し、すべてのＡＰが次の期間中に一定の割合の呼を捨てる（すなわちキャンセルする）ように指示して、認識された過負荷を取り除く。選択されたパラメータ値に依存して、この方法は、悲観的（最適なシステムスループットより少なくしかサポートしない）であるか、あるいは、混雑時間中に回避可能な呼損を引き起こす。しかし、以上の方法は、実時間ベースで各呼要求に対処しておらず、また、さまざまなＡＰの応答時間パフォーマンス能力に対処しておらず、既存の呼の中断を防ぐ予測可能な能力は制限されている。すなわち、遅いＡＰが過負荷になると、次の期間にシステムのすべてのＡＰからある割合の呼を廃棄することを引き起こすことがある。混雑時間中には、このような方法では呼が損失する。
【０００５】
従って、異なるＡＰを有するシステムの各ＡＰを最大限に利用する方法が必要とされている。
【０００６】
【課題を解決するための手段】
本発明の方法は、相異なるパフォーマンス特性のＡＰを有するシステムに対して、ＡＰ利用度等化法よりも混雑時間中に多くの呼を処理することを可能にする。顧客の投資を保護するために、実際にさまざまなＡＰに対処しなければならない。プロセッサ占有度等化に注目する既存の方法では、高速なプロセッサほど十分に利用されず、システム容量がむだになる。それは、最低速度のＡＰのハンディキャップにより高速のＡＰが十分に利用されず、高速のＡＰの負荷を捨てることが強制される可能性があるためである。
【０００７】
本発明の１つの特徴によれば、複数のアプリケーション呼プロセッサを有する分散システムで呼制御スケジューリングを行う方法において、
呼要求が存在するかどうかを判定する呼要求判定ステップと、
呼要求が存在しない場合、短い遅延の後にこの呼要求判定ステップを繰り返し、呼要求が存在する場合、続けて以下のステップを実行するステップと、
前記複数のアプリケーションプロセッサのうちの１つのアプリケーションプロセッサが呼要求に割り当てられているかどうかを判定するステップと、
１つのアプリケーションプロセッサが呼要求に割り当てられている場合、呼を終端し、データテーブルエントリを更新し、前記呼要求判定ステップに復帰し、１つのアプリケーションプロセッサが呼要求に割り当てられていない場合、続けて以下のステップを実行する。
次のステップは、Ｓ（ｉ）およびＵ（ｉ）のデータとともに、計算された応答時間データＴ（ｉ）を用いて、前記複数のアプリケーションプロセッサのうちから、判定された呼要求を実行するための最小応答時間Ｔ（ｊ）を有する１つのアプリケーションプロセッサを求めるステップである。
次のステップは、アプリケーションプロセッサの最小応答時間Ｔ（ｊ）がτより大きいかどうかを判定し、Ｔ（ｊ）がτより大きい場合、前記呼要求を捨てて前記呼要求判定ステップに復帰し、Ｔ（ｊ）がτ以下の場合、続けて以下のステップを実行するステップである。
次のステップは、期待される利用度Ｕ（ｊ）を更新し、前記呼要求を呼処理するためにｊ番目のアプリケーションプロセッサに割り当て、更新された期待利用度とともに前記呼要求判定ステップに復帰するステップである。
【０００８】
【発明の実施の形態】
図３に、複数のＡＰ３０２１〜３０２ｎを有するリングシステム３００をブロック図形式で示す。図３のシステム３００は、ＣＰの方法ＱＲ（ＱＲ法、ＱＲアルゴリズム）が異なることを除いては図１のシステム１００と本質的に同じである。ＱＲは急速応答（ｑｕｉｃｋ  ｒｅｓｐｏｎｓｅ）の略であり、急速応答に注目する理由は以下で明らかとなろう。実行時にＣＰに対して方法ＱＲを提供するプログラムは、管理アプリケーションプロセッサ（ＡＡＰ）３０８に接続されたメモリ３１０に格納される。
【０００９】
ＡＡＰ３０８は、システム３００のＣＰに対して方法ＱＲを提供するプログラムを実行する。代替実施例は、実行時に、ＣＰのための複数のメモリ３１１１〜３１１ｎに格納された方法ＱＲを提供するプログラムを有する。メモリ３１１１〜３１１ｎはそれぞれ、対応するアプリケーションプロセッサＡＰ１〜ＡＰｎに接続される。この代替実施例は、アプリケーションプロセッサＡＰ１〜ＡＰｎ間の分散処理を用いて方法ＱＲを提供する。メモリ３１１１〜３１１ｎは、システム３００の代替実施例であることを表すために、破線で囲まれたブロックとして図示されている。これらの実施例はいずれも、システム３００に、図１のリングシステム１００で用いられたＣＰに対する等利用度法を超える、ＣＰに対する方法ＱＲの利点を提供する。
【００１０】
同様に、図４に、システム４００のＣＰに対して使用される複数のＡＰ４０２１〜４０２ｍを有するＡＴＭ接続されたシステムをブロック図形式で示す。図４のシステム４００は、ＣＰに対して方法ＱＲを使用することを除いては図２のシステム２００と本質的に同じである。実行時にＣＰに対して方法ＱＲを提供するプログラムは、ＣＰのための複数のメモリ４１１１〜４１１ｍに格納される。メモリ４１１１〜４１１ｍはそれぞれ、対応するアプリケーションプロセッサＡＰ１〜ＡＰｍに接続される。この実施例は、アプリケーションプロセッサＡＰ１〜ＡＰｍ間の分散処理を用いて方法ＱＲをシステム４００に対して提供する。この実施例は、システム４００に、図２のＡＴＭシステム２００で用いられたＣＰに対する等利用度法を超える、ＣＰに対する方法ＱＲの利点を提供する。
【００１１】
方法ＱＲ自体は、システム３００あるいは４００への各呼処理要求に対する急速応答を使用することによって優れた効果を奏する。方法ＱＲの動作の説明として、｛Ｐｉ｜ｉ＝１，２，３，．．．，ｑ｝が、分散処理システムを構成するｑ個のＡＰの集合である場合を考える。ただし、Ｐｉはｉ番目のＡＰを表す。Ｐｉは、特定のＣＰ要求Ｒに対して全処理サービス時間Ｓｉ（秒）を有する。パラメータｑは、システム３００ではｎに等しく、システム４００ではｍに等しい。Ｐｉの利用度（あるいは占有度）は、それが１秒間に処理する同時ＣＰ制御タスクの数に正比例する。要求Ｒに関して、顧客の好みを含む外的条件によって課される応答時間カットオフＴｒ（秒）がある。ＰｉがＴｑ以内に要求の処理を完了することができない場合、呼接続は失敗すると仮定される。呼の平均長をｐ秒とする。一般に、通常動作の下では、特定のＡＰに割り当てられる呼制御は、呼のｐ秒間の全体にわたってそのＡＰによって処理される。ＡＰが失敗した場合、システムはその責任を別のＡＰに割り当てる。方法ＱＲの目的は、到着した呼処理要求を、（実現可能な場合に）最小の遅延でタスクを完了する見込みの最も高いＡＰに割り当てることである。
【００１２】
Ｕｉは、毎秒Ｃｉ個の呼を処理するＰｉの現在の利用度を表すとする。注意すべき点であるが、ＡＰ  Ｐｉは蓄積プログラムコンピュータであり、その応答時間（レイテンシ）Ｌｉ（秒）が次のようなＭ／Ｍ／１待ち行列モデルでモデル化される。
Ｌｉ＝Ｓｉ／（１−Ｕｉ）
ただし、
Ｕｉ＝ＣｉＳｉ
である。
【００１３】
ＡＰの応答時間は短いほど良く、これはこの方法では所与量である。注意すべき点であるが、あるＡＰでの呼に対するサービス時間は、そのＡＰのパフォーマンス能力の良い指標である。ＡＰの応答時間は、そのジョブに関するＡＰの実際のパフォーマンスの正しい指標である。上記のレイテンシ表式で与えられるように、応答時間は、サービス時間および利用度の両方に依存する。他のことが同じままである場合、注意すべき点であるが、（同じプロセッサ利用度を仮定すれば）ＡＰのクロックレートが速いほど、１つの要求に対するサービス時間は短くなり、呼要求に対する応答時間も短くなる。この方法で所与量でないのは以下のものである。
【００１４】
他の条件が同じままである場合、
Ｓｌ／（１−Ｕｌ）＞Ｓｆ／（１−Ｕｆ）
すなわち
Ｓｌ／Ｓｆ＞（１−Ｕｌ）／（１−Ｕｆ）
である場合、高速のプロセッサを有する利用度ＵｆのＡＰは、低速のプロセッサを有する利用度Ｕｌ（Ｕｌ＜Ｕｆ）のＡＰよりも良好な応答時間を有する。
【００１５】
ここで、（高速プロセッサのクロックレートが低速プロセッサのクロックレートの１０倍であるために）Ｓｌ／Ｓｆが１０であるとすると、高速ＡＰが９０％利用されるのに対して低速プロセッサが１０％しか利用されなくても、高速ＡＰは低速ＡＰよりも良好な要求応答時間を与える。
【００１６】
換言すれば、このことは、すべてのＡＰの利用度を等しくしようとする従来の呼分配方法は、低速のＡＰによって処理される呼要求に対して低速の応答をする可能性があるということを意味する。最悪の場合、混雑時間中に低速ＡＰにおいて許容できない遅延および呼損を引き起こす可能性がある。方法ＱＲでは、新たな呼要求はシステム３００または４００の他のＡＰよりも急速に応答するパフォーマンス能力を有するＡＰ（あるいは、同等に動作可能な複数のＡＰがあればその同等のＡＰのうちの１つ）に割り当てられ、高速プロセッサを有するその割り当てられたＡＰが過度に利用されても制限時間内にタスクを完了する。従来の方法に比べて方法ＱＲの利点には次のようなものがある。
【００１７】
１．低負荷および中程度の負荷（非混雑時間）の間、従来の方法に比べておそらく高速に応答する。
【００１８】
２．混雑時間中、方法ＱＲは、利用度等化法に基づく方法よりも多くの呼を処理する。本発明による方法のためにさらにサポート可能となる追加の呼数はシステムパラメータに依存する。
【００１９】
本発明の一実施例による方法ＱＲは、システム３００内の各ＡＰ３０２１〜３０２ｎ上で関連するパフォーマンス情報を有するデータ構造体を管理するＡＡＰ３０８上で実行される。各ＡＰに関する情報には、そのＡＰの現在の利用度および代表的なＣＰ要求を処理するためのサービス時間（秒）が含まれる。ＡＰの現在の利用度は、すべてのＡＰから周期的にモニタされて収集されるか、あるいは、パフォーマンスモデルに基づいて予測される。特定のＡＰｉに対するＣＰ要求のサービス時間は、メッセージを処理し、データベースにアクセスし、呼設定、破棄などの機能のようなその他のタスクを実行するために使用されるすべての時間の総和を含む定数である。特定のＡＰｉに対する平均ＣＰサービス時間は、軽負荷のＡＰに対する１回の実験室測定によってあらかじめ決定され、システムの起動時に初期化される。これらおよびＣＰパフォーマンスモデルから、ＡＡＰ３０８は、あたかも要求を処理してＣＰ要求に対する最短の応答時間の見込みのあるＡＰを識別するかのように、ＡＰ３０２１〜３０２ｎのそれぞれの応答時間を予測する。選択されたＡＰの応答時間が許容されるしきい値τ（秒）を超える場合、呼は捨てられる（すなわちキャンセルされる）。システム３００の残りのＡＰのいずれもさらに良好に実行することはできないからである。そうでない場合、呼は選択されたＡＰに割り当てられ、その予測される利用度が更新される。また、ＡＡＰ３０８は、システム３００全体によって処理される、順序対（ｃａｌｌ＿ｉｄ，ｃａｌｌ＿ｉｄによって定義される呼を処理するように割り当たられたＡＰ）によって与えられる現在のすべての割当てのリストＬｓｔを管理する。ＡＡＰ３０８はこのリストを用いて、要求が新たなｃａｌｌ＿ｉｄからのものであるかそれとも既存の呼からのものであるかを調べる。
【００２０】
システム３００およびシステム４００の別の実施例は、ＡＡＰ３０８の呼処理管理および割当て機能がシステム３００の別の実施例ではＡＰ３０２１〜３０２ｎの間に分散されシステム４００の場合にはＡＰ４０２１〜４０２ｍの間に分散されて含まれることを除いては、ＡＡＰ３０８を有するシステム３００の実施例と同様に動作する。
【００２１】
以下で、方法ＱＲ５００の形式的記述をする。（方法ＱＲは図５の流れ図にも図示される。）ここで、ｉ、ｊ、ｋ、およびＮはすべて整数であり、Ｔ（ｉ）、Ｕ（ｉ）、Ｓ（ｉ）はそれぞれ、ＡＡＰによって管理されるＮベクトルの第ｉ成分である。
【００２２】
Ｍｅｔｈｏｄ  ＱＲ
Ｐｒｏｃｅｄｕｒｅ  Ｗａｉｔ（）  ／／  ＡＡＰプロセスは次のＣＰ要求を待機する
Ｄｏ  ｗｈｉｌｅ  （ｔｒｕｅ）
Ｉｆ  要求がある  ｔｈｅｎ  ｄｏ  ｂｅｇｉｎ
Ｉｆ  それはｋ番目のＡＰに割り当てられた呼に対する要求である  ｔｈｅｎ
ｄｏ  ｔａｓｋ（ｋ）  ／／  呼の所有者に送る
Ｅｌｓｅ  ｄｏ  Ｓｃｈｅｄｕｌｅ（）
Ｅｎｄ
Ｅｎｄ
Ｅｎｄ
Ｐｒｏｃｅｄｕｒｅ  Ｓｃｈｅｄｕｌｅ（）
ｊ＝１；
Ｆｏｒ  ｉ  ＝  １，  ２，  ．．，  Ｎ  ｄｏ  ｂｅｇｉｎ
／／  要求タイプごとに最短応答時間のＡＰを決定する
Ｔ（ｉ）  ＝  Ｓ（ｉ）／（１−Ｕ（ｉ）−Ｓ（ｉ）／ｐ）
／／  Ｔ（ｊ）が｛Ｔ（ｉ）｜ｉ＝１，２，．．，Ｎ｝の最小値となるｊを求める
Ｉｆ  Ｔ（ｉ）  ＜  Ｔ（ｊ）  ｔｈｅｎ  ｄｏ  ｊ  ＝  ｉ；
Ｅｎｄ
Ｉｆ  Ｔ（ｊ）  ＞  τ  ｔｈｅｎ  ｄｏ  ｂｅｇｉｎ
話中音を送出；  ／／  許容できない遅延なので呼を捨てる
Ｗａｉｔ（）
Ｅｎｄ
Ｅｌｓｅ  ｄｏ  ｂｅｇｉｎ
Ｕ（ｊ）  ＝  Ｕ（ｊ）  ＋  Ｓ（ｊ）／ｐ；  ／／  ｊ番目のＡＰの利用度を更新
割当てのリストに（ｃａｌｌ＿ｉｄ，  ｊ）の対を含める
ＣＰに対してｊ番目のＡＰに要求を送る；
Ｅｎｄ
Ｅｎｄ
Ｐｒｏｃｅｄｕｒｅ  ｔａｓｋ（ｋ）
Ｉｆ  呼が確立または失敗  ｔｈｅｎ  ｄｏ  Ｕ（ｋ）  ＝  Ｕ（ｋ）  −  Ｓ（ｋ）／ｐ；
／／  呼確立に対して利用度を縮小
Ｌｓｔから（ｃａｌｌ＿ｉｄ，  ｋ）エントリを除去；
Ｅｎｄ
Ｅｎｄ
【００２３】
方法ＱＲ５００は正しく効率的に動作する。方法ＱＲ５００は、ベクトルＵにおいて各プロセッサの利用度を更新し追跡し、ベクトルＳにおいてすべてのプロセッサのサービス時間を更新し追跡する。注意すべき点であるが、呼の確立によってｋ番目のＡＰの利用度Ｕ（ｋ）の期待される減少はＳ（ｋ）／ｐである。ただしｐは秒単位の平均呼長である。同様に、新たな呼要求によってｊ番目のＡＰの利用度Ｕ（ｊ）の期待される増大はＳ（ｊ）／ｐである。ただしｐは秒単位の平均呼長である。新たな呼要求が到着すると（あるいは呼が確立すると）、毎秒の呼数はちょうど１／ｐだけ増大（あるいは減少）する。こうして、方法ＱＲは、呼単位で動的に、レイテンシＬｉおよび利用度Ｕｉに対する前記の表式で与えられるモデルを正しく実装する。
【００２４】
これらの情報が利用可能になると、応答時間の予測に必要なのは、サービス時間の分割のみであり、これは起動時に（１−利用度）によって初期化される既知定数である。必要なのは、次元Ｎの２つのベクトルのみであり、一方は利用度のベクトルであり、他方はサービス時間のベクトルである。リストＬｓｔは、毎秒の呼数のオーダである必要がある。呼が新しいかどうかの検査は、リストＬｓｔのスキャンを必要とし、これは一定時間で行うことが可能である。本発明の計算量はＯ（Ｎ）であり、ＡＰの数に関して線形であり、従って効率的である。
【００２５】
方法ＱＲの利点をさらに説明するため、以下の記法および定義を考える。システム内のプロセッサの集合は、各クラスが同じプロセッサ速度およびパフォーマンス特性を有するように分割されていると仮定する。さらに、これらのクラスは１からｋまで順序づけられ、第１クラスのプロセッサは最低速で、第ｋクラスのプロセッサは最高速であり、すべての０＜ｉ＜ｋに対して、クラスｉ＋１のプロセッサはクラスｉのプロセッサより速いと仮定する。使用される主な記号は表１の通りである。
【００２６】
【表１】
0003545931.tif 000002
【００２７】
利用度等化法および方法ＱＲの両方におけるＡＰの目的は呼処理を提供することをである。解析のため、すべての呼はほぼ同じ呼制御手順を有すると仮定する。これに基づいて、呼分配ツリーを用いてモデルおよび方法ＱＲを修正してさらに結果を改善することが可能である。ＡＰが他の処理機能も行う場合、そのＡＰのパフォーマンスはそれらの機能を処理するために低下する可能性がある。ＡＰが与えられた制限時間内に処理を完了することができない場合に、ＣＰスケジューリング法は失敗したという。注意すべき点であるが、呼制御を行うプロセッサが（あらかじめ定められた）適当な時間内に正しい情報あるいは信号で応答することに失敗した場合、それによって処理されている呼は時間内に設定されたり破棄されたりしないこともあり、あるいは考慮されずに破棄されることもある。これに関して、以下の結論を出すことができる。
【００２８】
１．利用度等化法は、すべてのプロセッサのすべての利用度がＶであり最低速プロセッサの応答時間がＴを超えるときに失敗する。
【００２９】
２．方法ＱＲは、任意のプロセッサの応答時間がτを超える（そして高速なプロセッサの利用度が常に低速のプロセッサの利用度より大きい）ときに失敗する。
【００３０】
ＡＰの呼容量は、そのＡＰが呼を破棄せずに同時に処理することができる毎秒の最大呼数によって与えられる。従って、その呼容量より少ない毎秒の呼数を処理しているＡＰは、許容されるカットオフ以内にその応答時間が収まることを保証することができる。
【００３１】
［利用度等化法における１秒あたり処理される呼数］
利用度等化法では、プロセッサ利用度はＶに等しく、次式が成り立つときに、最低速のＡＰにおいて最大呼数Ｃ１を処理する。
【数１】
0003545931.tif 000003
ただし、Ｕ＝Ｃ１・ｔ・ｓｋ／ｓ１であり、ｔは最高速プロセッサで呼を処理するためのサービス時間である。従って、
【数２】
0003545931.tif 000004
である。この方法ではすべてのＡＰの利用度はＵであるため、１≦ｉ≦ｋに対して次式が成り立つことが示される。
【数３】
0003545931.tif 000005
従って、いずれかの呼の失敗の前に従来法によって処理される総呼数は次式で与えられる。
【数４】
0003545931.tif 000006
【００３２】
［方法ＱＲにより１秒あたり処理される呼数］
クラスｋのＡＰによって処理される呼数は次式によって決定される。
τ＝ｔ／（１−Ｃ′ｋ・ｔ）
ただし、Ｃ′ｋ＝（１／ｔ）−（１／τ）である。
【００３３】
クラスｉのＡＰによって処理される呼数は次式で与えられる。
【数５】
0003545931.tif 000007
従って、呼失敗が起こる前に方法ＱＲによって処理される総呼数は次式で与えられる。
【数６】
0003545931.tif 000008
同じシステムが方法ＱＲを用いて失敗なしにさらに処理することができる１秒あたりの追加の呼数は次式で与えられる。
【数７】
0003545931.tif 000009
注意すべき点であるが、Ｔ１＝τである。その理由は、この遅延では、最低速ＡＰはＡＰ利用度等化法において可能な最大の許容可能な遅延を有するためである。しかし、同じ利用度に対して、利用度等化法では、１≦ｉ≦ｋに対して、次のようになる。
Ｔｉ＝Ｔ１・ｓ１／ｓｉ＝τ・ｓ１／ｓｉ
従って、
【数８】
0003545931.tif 000010
となる。明らかに、Ｃｘは、複数のクラスのＡＰがある場合には常に正の数となる。
【００３４】
次に、上記の表式に関して以下の例を考える。
【００３５】
［例１］
それぞれ８ＭＩＰＳの４個のＡＰと、３２ＭＩＰＳのもう１つのＡＰがある場合を考える。プロセッサ利用率は８０％（これは妥当な数である）、カットオフ時間は０．８５秒で、８ＭＩＰＳのＡＰあたり１７ＫＢＨＣＡ（混雑時の１０００回の呼試行（ｔｈｏｕｓａｎｄｓ  ｏｆ  ｂｕｓｙ  ｈｏｕｒ  ｃａｌｌ  ａｔｔｅｍｐｔｓ））を仮定する。この場合、Ｃｘは３／０．８５＝３．５３呼／秒すなわち１２．７１ＫＢＨＣＡとなる。この数は、全容量（４×１７＋４×１７）＝８５ＫＢＨＣＡに対する割合としては約１５％である。
【００３６】
［例２］
それぞれ８ＭＩＰＳの２個のＡＰと、１６ＭＩＰＳのもう１つのＡＰがある場合を考える。プロセッサ利用率は８０％、カットオフ時間は約１秒で、８ＭＩＰＳのＡＰあたり１７ＫＢＨＣＡを仮定する。この場合、Ｃｘは１×１／１＝１呼／秒すなわち３．６ＫＢＨＣＡとなる。割合としてはこれは約３６０／６８＝５．３％となる。注意すべき点であるが、この場合、高速のＣＰＵは低速のものと同じ世代に属しているにもかかわらず、方法ＱＲの有用性を示している。
【００３７】
［例３］
８ＭＩＰＳの１個のＡＰと、３２ＭＩＰＳのもう１つのＡＰがある場合を考える。プロセッサ利用率は８０％、カットオフ時間は１秒で、８ＭＩＰＳのＡＰあたり１７ＫＢＨＣＡの場合、Ｃｘは３／１＝３呼／秒すなわち１０．８ＫＢＨＣＡとなる。割合としてはこれは約１０８０／８５＝１３％となる。
【００３８】
［例４］
８ＭＩＰＳの１個のＡＰと、８０ＭＩＰＳのもう１つのＡＰがある場合を考える。プロセッサ利用率は８０％、カットオフ時間は１秒で、８ＭＩＰＳのＡＰあたり１７ＫＢＨＣＡの場合、Ｃｘは９／１＝９呼／秒すなわち３２．４ＫＢＨＣＡとなる。割合としてはこれは約３２４０／１８７＝１７％となる。
【００３９】
観察されるように、利用度等化法によって達成可能なものを超えて方法ＱＲが処理することができる呼の割合は、応答時間カットオフに依存する。応答時間カットオフが小さいほど、方法ＱＲがさまざまなパフォーマンスのＡＰ３０２を有するシステム３００によって処理することができる追加の呼の割合は大きくなる。このように処理される追加の呼は、低速プロセッサよりもずっと高い利用度で許容可能な応答をすることができる高速プロセッサに由来する。
【００４０】
図６に、一方は８ＭＩＰＳで他方は８０ＭＩＰＳの２個のＡＰからなるシステム上での２つの方法の比較を示す。ここで、ｘ軸は秒単位の遅延カットオフであり、ｙ軸は２つの方法によって処理される呼数を表す。図から分かるように、本発明の方法は、要求される遅延が小さい（これは顧客が望むところである）場合特に、利用度等化法に比べて優れた効果を奏する。
【００４１】
まとめると、方法ＱＲは、相異なるパフォーマンス特性のＡＰを有するシステムに対して、ＡＰ利用度等化法よりも混雑時間中に多くの呼を処理することを可能にする。さらに、さまざまなＡＰを有するシステムは、従来の設備投資を保護するために、現代のネットワークが実際に対処しなければならないものである。プロセッサ占有度等化に注目する従来の方法では、高速なプロセッサほど十分に利用されず、システム容量がむだになる。それは、最低速度のＡＰのハンディキャップにより高速のＡＰが十分に利用されず、高速のＡＰの負荷を捨てることが強制される可能性があるためである。
【００４２】
方法ＱＲの実装は直接的である。すべてのＡＰの利用度を計算する代わりに、新たな呼が到着したときに、ＡＰの期待される応答時間を計算する必要がある。方法ＱＲでは、高速ＡＰがまとまった呼を分け合うため、軽負荷および中程度の負荷ではＣＰに対する応答が多少速くなる。方法ＱＲは実時間で各呼要求に注目し、呼の確立に成功する見込みのある場合にはその呼要求を処理するための最高速応答のＡＰを探索し、最高速応答ＡＰが必要な応答時間内にその呼要求に応答することができない場合にはその呼要求を拒絶する。後者の場合、システム３００あるいは４００は真に過負荷状態にあり、呼の拒絶は不可避である。
【００４３】
【発明の効果】
このように、本発明によれば、複数の異なるアプリケーションプロセッサのうちの１つを呼要求の処理に割り当てる新たな装置および方法が実現される。当業者には明らかなように、本発明のさまざまな変更あるいは変形が可能である。例えば、統計的に計算された利用度の代わりに、ＡＰからの実際の測定値によってＣＰＵ利用度ベクトルを周期的に更新することが可能である。このような変形例では、応答時間の更新を各ＡＰで独立かつ周期的に行い、更新された応答時間をＡＡＰと共有することが必要となる。このような更新値は、モデルを定期的に検査し更新するために使用可能であるとともに、呼割当てにも使用可能である。しかし、このアプローチは、ＡＡＰおよびＡＰにおける通信および処理の追加のオーバヘッドを引き起こす。ＯＣ−３  ＡＴＭ相互接続や高速トークンリングのようなブロードキャスト能力を有する高速相互接続を有するＡＰでは、これは達成可能である。
【図面の簡単な説明】
【図１】複数の異種のＡＰを含むトークンリングを有する従来のシステムのブロック図である。
【図２】ＡＴＭネットワークによって接続された複数の呼処理ＡＰを有する従来のシステムのブロック図である。
【図３】複数の異種のＡＰを含むトークンリングを有する本発明によるシステムのブロック図である。
【図４】ＡＴＭネットワークによって接続された複数の呼処理ＡＰを有する従来のシステムのブロック図である。
【図５】呼制御スケジューリングのＱＲ法の流れ図である。
【図６】簡単なシステムに対する利用度等化法とＱＲ法の比較の棒グラフの図である。
【符号の説明】
１００  システム
１０２  アプリケーションプロセッサ（ＡＰ）
１０４  トークンリング
２００  システム
２０２  アプリケーションプロセッサ（ＡＰ）
２０４  ＡＴＭ
３００  リングシステム
３０２  アプリケーションプロセッサ（ＡＰ）
３０８  管理アプリケーションプロセッサ（ＡＡＰ）
３１０  メモリ
３１１  メモリ
４００  システム
４０２  アプリケーションプロセッサ（ＡＰ）
４１１  メモリ
５００  方法ＱＲ
【図１】
0003545931.tif 000011
【図２】
0003545931.tif 000012
【図３】
0003545931.tif 000013
【図４】
0003545931.tif 000014
【図５】
0003545931.tif 000015
【図６】
0003545931.tif 000016