(57)【特許請求の範囲】
【請求項１】
第一のタイプと第二のタイプのコールを受信できるネットワークにおけるコール許可決定法であって、
当該ネットワークは、それに付随した割込み確率とそれに付随した割込み確率閾値を有し、
（ａ）第一のタイプのコールが到着すると、その第一タイプのコールがサービスを許可された場合に割り込みが発生する確率である、ネットワークの割込み確率の近似値を算出するステップと、
（ｂ）割込み確率の近似値がネットワークの割込み確率閾値未満であれば当該コールにサービスを許可するステップと、
を含み、
第一のタイプのコールは即時要求コールであり、第二のタイプのコールは予約コールであることを特徴とする資源共用法。
【請求項２】
請求項１に記載の方法において、
当該ネットワークはさらにそれに付随した予約コールのプロフィールを有しており、割込み確率は、コール到着時点でサービス中の即時要求および予約コールの数と、予約コールのプロフィールの関数であることを特徴とする資源共用法。
【請求項３】
請求項２に記載の方法において、
割込み確率の近似値は、独立ピーク近似法を用いて算出することを特徴とする資源共用法。
【請求項４】
請求項２に記載の方法において、
割込み確率の近似値は、固定時間近似法を用いて算出することを特徴とする資源共用法。
【請求項５】
請求項２に記載の方法において、
割込み確率の近似値は、１ピーク近似法を用いて算出することを特徴とする資源共用法。
【請求項６】
請求項２に記載の方法において、当該ネットワークはさらにそれに付随した予約数の上限を有しており、
（ｃ）予約コールを受信すると同時に、将来サービス予定の予約コールの数がネットワークの予約数の上限以下であれば当該予約コールを将来サービスすることをスケジュールに入れるステップと、
を含むことを特徴とする資源共用法。
【請求項７】
請求項１に記載の方法において、
前記割込み確率の近似値は、第一のタイプのコールの到達確率に基づいて計算されることを特徴とする資源共用法。
【請求項８】
予約ユーザと即時要求ユーザにサービスし得る資源提供エンティティの資源を割り当てる方法であって、
当該エンティティはそれに付随するサービス割込み確率とそれに付随する資源割込み確率閾値を有しており、
（ａ）資源提供エンティティによるサービスを即時要求ユーザが要求すると、その即時要求ユーザが資源提供エンティティによるサービスを受けられるとした場合における、エンティティのサービスの割込み確率の近似値を算出するステップと、
（ｂ）サービスの割込み確率の近似値が、資源提供エンティティの資源割込み確率閾値未満であればユーザにサービスをするステップと、
を含むことを特徴とする資源割当て法を含む資源共用法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般的には通信ネットワークに関し、特に、統合サービスネットワークにおける予約および即時要求コールに資源を割り当てる方法に関する。
【０００２】
【従来の技術】
統合サービスネットワークにおいては、テレビ会議のような帯域幅の大きいコールに、適切な品質のサービスを、ネットワーク利用に悪影響を及ぼすことなく提供するのはむずかしい。この問題を軽減するための一つの方法は、ネットワークのカスタマに、レストランに予約の電話を入れるように、実際のコール開始時間に先立ってコールを予約させることである。
【０００３】
ネットワーク資源を、（予定の保持時間を予告する）予約コールと（予告しない）即時要求コールのそれぞれのクラス専用の２つの別のサブセットに分割することによって、どちらのコールも許可することが可能となる。あるいは、たとえば、クラス間の境界を可動にすることによって、ネットワーク資源を厳密に分割せずに共用し、それによって通信中のどのコールも割り込まれることなく資源を共用できる。
【０００４】
【発明が解決しようとする課題】
しかしながら、コールの割込み（interruption：インタラプション）をさせない厳密な資源分割方式には欠点もある。このような資源共用方式は、ネットワーク資源を十分に活用しきれない。したがって、通信中のコールの中には割り込まれるものがあっても、ネットワーク資源の利用およびそれに伴う収益を増加させるような資源共用を実施することが望ましい。
【０００５】
【課題を解決するための手段】
本発明は、資源を前もって予約する“予約”利用と、前もって予約しない“即時要求”利用の両方ができる環境での資源共用法において、割込みをして資源を利用することを許可し、そのような割込みができない場合よりも全般的な資源利用が大きくなるような方法を提供する。一つの形態では、本発明は、統合サービスネットワークにおける“予約”コール（予定のコール開始時間とコール保持時間を予告する）と、非予約（または“即時要求”）コール（予定のコール保持時間を予告しない）の間で通信ネットワーク資源を共用するための方法を提供する。本発明の本形態によるネットワーク資源共用の基本は許可管理アルゴリズムで、これによって、即時要求コールは、（リアルタイムで計算された）割込み確率の近似値がある閾値未満であれば許可される。シミュレーション実験によれば、本発明の許可管理アルゴリズムは、コール割込みをさせない厳密な資源分割などの別の方式と比べて、優れた資源利用と収益発生を提供する。
【０００６】
本発明のネットワーク資源共用法は、厳密な分割方式とは異なって、コール割込みの可能性を許可している。したがって、この点において、本方式は、非同期転送モード（ＡＴＭ）ネットワークにおけるセルストリームの統計的多重化と類似している。ＡＴＭネットワークでは、資源を確保してピーク時の通信量（トラフィック）に対応する代わりに、小さな確率のセル損失は、許可するストリーム数を増やすためにはあってもよいとしている。本資源共用法といくらか類似した別の通信トラフィック取扱いシステムはワイヤレスネットワークである。このネットワークでは、全般的なネットワーク利用を増加させるために、少しの呼損率（ハンドオフ・ドロッピング・レート：handoff dropping rate）は許されている。
【０００７】
【発明の実施の形態】
本発明は、いくつかの状況で採用可能な資源共用法に関する。以下の説明では、特に通信ネットワークにおける資源共用に言及するが、本発明の適用は、通信ネットワークだけに限られない。
【０００８】
本発明の一つの形態に関する以下の説明では、通信ネットワークにおける資源共用を検討する。以下の説明で、“コール”とは通信ネットワーク資源が利用されるすべての通信セッションを指し、たとえば、音声コール、データ通信などが含まれる。ここで言う“予約コール”とは、予定のコール開始（すなわち予約）時間（期間）とコール保持時間（期間）を予告するコールのことである。“即時要求コール”とは、予約をしない代わりに、（ネットワークに入ることを許可された場合）コール到着後すぐにサービスに入るコールのことである。予定のコール保持時間も予告しない。
【０００９】
予約コールが許可された場合、最初の到着時間（時刻）に予約時間（予約状態にある期間）を加えた時間（時刻）にサービスに入り、コール保持時間（期間）分のサービスを受けた後サービスから離れる。予約コールに関して、ｔ１、ｔ２、ｔ３をそれぞれ到着時間（予約の到着時刻：ｔ１）、予約時間（予約したコールが開始されるまでの予約状態にある期間：ｔ２）、保持時間（予約したコールが継続する期間：ｔ３）とすると、その予約コールは、許可された場合、（ｔ１＋ｔ２）から（ｔ１＋ｔ２＋ｔ３）の間がサービス中ということになる。
【００１０】
本発明の目的のために、予告された予約コールの予定の保持時間は、見積または安全な上限でよい。予約コールに使用されるネットワークのキャパシティは、どちらが先でもよいが、予約カスタマがサービスから離れるか保持時間が終了した後は、別の発信者が使用できる。
【００１１】
本発明の一つの形態では、予約コールは保持時間を延長することができる。これは、たとえば、保持時間の延長の要求を新規の予約コールとして扱うことなどによって達成できる。この新規の要求については、予約時間は、当初の要求のあった時点（時刻ｔ１）と当初の予約コールの終了予定時間（時刻ｔ１＋ｔ２＋ｔ３）との間の時間（時刻ｔ４）である。新規の要求の保持時間は、増加分の保持時間（期間ｔ５）ということになる。したがって、予約コールがｔ４の時刻に、ｔ１＋ｔ２＋ｔ３＋ｔ５の時間に終了すると要求した場合、ここで、ｔ１＜ｔ４＜（ｔ１＋ｔ２＋ｔ３）であるが、新規の要求の予約時間（予約状態にある期間）は、ｔ１＋ｔ２＋ｔ３−ｔ４で、保持時間はｔ５となる。すなわち、予約の到達時刻がｔ４で、予約コールの開始時刻がｔ１＋ｔ２＋ｔ３であるので、予約状態にある時間（予約時間）は、予約到達時刻から当初の終了時刻までの期間ｔ１＋ｔ２＋ｔ３−ｔ４となる。
【００１２】
本発明による資源共用は、許可管理政策に基づいているが、この政策は、到着コールごとの割込み確率の計算に基づいている。本許可管理政策によって、即時要求コールは、計算した割込み確率がある閾値未満であれば許可され、そうでなければ遮断される。予約コールは次のような場合に許可される（すなわち今後のコール開始時間がスケジュールに入れられる）。（１）それまでに予約済みの予約コールのみを考慮して空きがある場合、（２）当該コールを許可した後の割込み確率が第二の割込み確率閾値（即時要求コールに適用される閾値と同じでよいが、そうでなくてもよい）を越えない場合。
【００１３】
本発明によれば、必要がある場合、どのコールに割込みをするかを決定する方法はいくつかある。コール割込みは滅多に起こらないので、どのコールに割込みをするかの選択は、本許可管理政策のパフォーマンスにあまり影響を与えないはずである。一般的には、最も重要でないと考えられるコールに割込みをする。たとえば、成立したコールの価値はコール時間とともに増すと考えられれば、先に到着したコールよりは最後に到着したコールに割り込むのがよい。
【００１４】
したがって、本発明に従って、いくつかの典型的なコール割込み政策が使用できる。その一つは、コールの種類がどうであれ、最後に到着したコールに割込みをすることである。（予約コールについては、要求のなされた時間は、サービス開始時間ではなく到着時間であると考える。）
採用可能な別の割込み政策は、最後に到着した即時要求コールに割込みをすることである。この割込み政策に従うと、予約コールは決して割込みをされないことになる。この政策は、予約コールのほうが価値が高いとみなされれば好ましい。本発明に従って採用し得るさらに別の割込み政策の例は、最後に到着したコールに割込みをするが、ただし、かなり前もって予約された予約コールについては例外的に、即時要求コールやコール開始時間までにあまり間のない予約コールよりも優先される。
【００１５】
本発明では、さまざまな割込み政策を合わせて使用できる。予約コールは、即時要求コールの保持時間と比較してかなり以前に予約されるものであるとすれば（おそらくそうであろうが）、前述の割込み政策には事実上の差はほとんどない。たとえば、標準的な電気通信ネットワークでは、通常の即時要求音声コールの平均の保持時間は約５分であるのに対し、電子会議のコールは数日前に予約される。図２から８に描かれ、以下で説明するシミュレーションの結果は、予約コールがかなり先の予約である場合についてである。
【００１６】
許可管理政策の実施に当たっては、割込み確率の計算を迅速に行い、許可管理の決定をリアルタイムでできるようにすることが重要である。割込み確率を正確に計算することは困難であるので、本発明では、割込み確率の計算にいくつかの近似法を使用する。これらの近似法は以下に説明する。また、さまざまな近似法についてのシミュレーション結果は図２から８に示し、以下で検討する。これらのシミュレーション結果によれば、本発明の近似法は、リアルタイムの計算および期待収益の両方の点から非常に有効であるといえる。特に、シミュレーション結果から、本発明による許可管理政策は、コール割込みを許可しない他の代替法と比べて、資源利用率が高く、ネットワーク資源から得られる収益が大きいということがわかる。
【００１７】
予約コールが比較的かなり先の予約をするとすれば、予約の特徴から予約コールは即時要求コールよりも優先される。したがって、即時要求コールに対して何らかのサービス保証を与えるのが望ましい。ゆえに、本発明の一つの形態では、予約コール用のネットワークキャパシティに上限を設けることが含まれている。つまり、本形態では、ある予約コールによってシステムの予約コール数がある閾値を越えてしまうような場合はいつでも、その予約コールは許可されない。
【００１８】
即時要求カスタマの中には割込みに強く反対する人もいるので、即時要求コールを複数のクラスに分けて、その中の一部だけが割込みを経験するようにするのが望ましい。複数クラスを用いれば、たとえば、存在する最下位のクラスから最後に到着したコールに割込みをするといった割込み法を採用できる。あるいは、クラスの種類とコール到着時間の両方を考慮してどのコールに割込みをするかを決定するといった、より複雑な割込み法を採用することもできる。本発明に関する以下の検討では、即時要求カスタマのクラスは１種類であるが、本発明では即時要求コールのクラスを複数にすることも容易にできる。どのクラスも同じ保持時間分布を有しているとすれば、このことによって複雑さが増すことはない。
【００１９】
以下で検討するシミュレーションでは、当初の要求が合わない到着予約コールは遮断され、失われると仮定した。しかしながら、実際には予約コールは要求を変更する、すなわち、利用可能な別の割り当て時間を受容すると思われる。重要なことは、即時要求コールのための本発明の許可管理政策は、そのような変更にも同様によく対応するということである。
【００２０】
また、シミュレーションでは、各コールが到着すると同時に、サービスプロバイダには、通信中の即時要求コールの数と、今後存在することになる以前に許可された（通信中あるいは予定の）予約コールの数がわかるということも仮定した。通信中および予定の予約コールに関するデータをここでは予約コールのプロフィールと呼ぶ。サービス中のコール、予定に入っている予約コール、新規到着分が与えられたとすると、将来の到着分は無視して、将来のすべての時点における割込み確率が概算される。
【００２１】
予約コールがあまり先の予約でない場合、許可されたコールが結局割込みをされる確率は、そのコールの到着後の事象によって変わり得るということを認識しておくことは重要である。たとえば、即時要求コールだけが割込みをされるとすると、将来的に到着する予約コールによって、即時要求コールが結局は割込みをされる確率が増加することになりかねない。このことは、たとえ到着時に計算された割込み確率が閾値未満であっても、割込みをされるコールの機会は実際には閾値を越え得るということを意味する。しかしながら、この影響はあまり大きくはないはずである。なぜならば、非常に混雑している場合、この問題の原因となるような新規の予約コールは、それ自体が許可されそうもないからである。予約時間のほうが一般的には即時要求コールの保持時間よりもかなり長いというような状況では、このような複雑な問題は起こらない。必要であれば、最小の予約時間を設定することによって、問題を起こりにくくすることもできる。
【００２２】
１．即時要求コールの許可管理法
本発明による即時要求コールの許可管理法は、問題のコールがサービスを許可された場合に割込みをされるおよその確率を算出することに基づいている。この割込み確率の計算は、この新規のコールの保持時間の確率分布と、到着時点におけるシステム内の他のコールに関する情報に基づいている。したがって、即時要求コールのコール保持時間分布を知ることが必要となる。この分布は、標準法によって履歴データから推定される。一つの可能性としては、その平均を特徴とする指数分布を使用することである。ここでの平均はサンプル平均によって概算される。
【００２３】
本許可管理アルゴリズムは、実際の分布が指数分布でなくてもかなりよく機能するが、実際の分布を考慮に入れればパフォーマンスを向上させることができる。この目的のために、一般的な即時要求コールの保持時間分布を用いて割込み確率を計算するアルゴリズムを以下のセクション３で検討する。その場合、さらに、即時要求コールはポアソン過程に従って到着するという仮定をする。この仮定によって、アルゴリズムは指数分布の場合と同じ計算量を有することになる。このアルゴリズムを他の到着過程の近似としても使用することは自然なことである。ポアソン到着過程を使っても使わなくても、基礎になっている保持時間分布が指数分布でない場合、通信中の即時要求コールの経過保持時間（エイジ）は、残りの保持時間分布に影響を及ぼすが、セクション３で検討するアルゴリズムにはエイジを用いない。
【００２４】
割込み確率の計算のためにまず最初に仮定することは、サービス中の即時要求コールは独自の保持時間を有し、各々は指数分布であるということである。さらに、将来の予約コールについては開始時間も終了時間もわかっているということも仮定する。
【００２５】
またさらに、即時要求コールは１ユニットの帯域幅を、予約コールはｂユニットの帯域幅を要求し、リンクしている利用可能な全帯域幅はｓであると仮定する。（本発明のネットワーク資源共用法は、帯域幅要件の異なる異種の予約コールにも拡大できるが、即時要求コールについては共通の帯域幅要件を利用する。ただし１ユニットでなくてもよい。）前述のとおり、割込みにはいくつかの可能な政策があるが、厳密に言えば、以下の検討では、割込みが必要なときは最後に到着した即時要求コールが割り込まれると仮定する。
【００２６】
以下に示すように、上述の仮定のもとで割込み確率を正確に表現式で表すことは可能である（事前にアクセプトされた予約コールだけを考慮して）。しかしながら、実際に計算を実施するのは難しいと思われる。したがって、本発明では割込み確率の近似値を計算することによる許可管理政策を実施する。近似法のいくつかの候補を以下に示す。最も有望なものは、以下のセクション１．２に展開する独立ピーク近似法（ＩＰＡ）と思われる。これは、処理できる程度に低い計算オーバーヘッドで高パフォーマンスを提供する。このセクションでは、即時要求コールの保持時間分布は指数分布であると仮定する。セクション３で一般的な即時要求コールの保持時間分布の場合を検討する。
【００２７】
１．１．正確な割込み確率の計算
本セクションでは、各到着コールの割込み確率を、到着時点で存在する即時要求コールの数と予約コールの将来のプロフィールを用いて、どの様に計算するかを説明する。決定は、割込み確率がある閾値より大きいか小さいかによる。以下の表現式から、割込み確率の正確な計算は、実施が難しいことは明らかである。この困難を回避するために、以下のセクション１．２で検討するような割込み確率の近似法を利用する。
【００２８】
Ｉ（ｔ）とＢ（ｔ）は、それぞれ、時間ｔ1における通信中の即時要求コールと予約コールの数を表すとする。新規の即時要求コールが時間Ｔ0に到着し、このコールを許可するか否かの決定をしなければならないとする。すると、時間Ｔ0に到着したこの即時要求コールの第一の予想割込み時間は、
【数１】
0004448205.tif 000002
ここで、ｓは全帯域幅（キャパシティ）である。次に、時間Ｔ0に到着した即時要求コールのその後の予想割込み時間はＴi、ｉ＝２，３・・・であり、Ｔiは、Ｔ1＜Ｔ2＜・・・、Ｂ（Ｔi）＝Ｂ（Ｔi-1）＋１を満たす。図１に、予約コールのプロフィールと予想割込み時間｛Ｔ0，Ｔ1，・・・｝の一例を示す。
【００２９】
ｎ（Ｔ0）を、Ｔ0に到着した新規のコールが割込みをされないように、Ｔ1までにクリアダウン（サービスを終了）しなければならない即時要求コールの数とする。明らかに、ｎ（Ｔ0）＝Ｉ（Ｔ0）−ｓ＋ｂＢ（Ｔ1）＋１である。予想割込み時間Ｔiの数は、ｓ／ｂ以下である。実際には、ある範囲内の割込み時間の数だけに的を絞ることができる。初めのＬ（式中では筆記体小文字）個の予想割込み時間、すなわち｛Ｔ1，Ｔ2，・・・ＴL｝を考えるとする。Ｎ（ｔ）を、時間Ｔ0にはシステムにあるが、ｔ＞Ｔ0である時間ｔまでにはサービスを終了する即時要求コールの数とする（Ｔ0に新規に到着したコールは含まれない）。Ｘを時間Ｔ0に新規に到着した即時要求コールの保持時間とする。すると、Ｔ0に到着した即時要求コールが後になって割込みをされる確率は、
【数２】
0004448205.tif 000003
となる。
【００３０】
即時要求コールの保持時間が指数分布であると仮定すると、上記式（１．２）を計算することは可能である。たとえば、ゆえに、
【数３】
0004448205.tif 000004
また、Ｎ（ｔ）は、変数Ｉ（Ｔ0）と
【数４】
0004448205.tif 000005
を持つ二項分布を有している。
【００３１】
たとえ式（１．２）についての明白な表現式が与えられても、計算は非常に困難である。
【００３２】
１．２  割込み確率の近似計算法
このセクションでは、式（１．２）の割込み確率を近似するための３種類の近似法を検討するが、近似法は番号順に複雑になる。
【００３３】
１．  固定時間近似法（ＦＴＡ）
ＦＴＡでは、割込み確率は次式で近似される。
【００３４】
【数５】
0004448205.tif 000006
すなわち、ＦＴＡではＴ1以外のすべての割込み時間を無視し、また、時間Ｔ0に存在する即時要求コールの数に関する情報も用いない。
【００３５】
２．  １ピーク近似法（ＯＰＡ）
ＯＰＡでは、式（１．２）の右辺の第１項だけを用いて、ｐ（Ｔ0）の下限を求める。言い換えれば、割込み時間Ｔ1１つだけを用いて計算をする。したがって、割込み確率ｐ（Ｔ0）は次式で近似される。
【００３６】
【数６】
0004448205.tif 000007
３．  独立ピーク近似法（ＩＰＡ）
ＩＰＡでは、Ｔ0に到着するコールが、各予想割込み時間｛Ｔ1，Ｔ2，・・・，ＴL｝に割込みをされる確率は互いに独立であると仮定する。したがって、割込み確率ｐ（Ｔ0）は次式で上限が求められる。
【００３７】
【数７】
0004448205.tif 000008
ＩＰＡは、本発明の好ましい形態で割込み確率を近似するのに用いられる。それは、当該方法が非常に正確でありながら計算が処理しやすいためである。コール割込みが問題であるならば、ＩＰＡでは上限を求めるため、控えめに算出される。ＯＰＡでは下限が求められるので、ＯＰＡとＩＰＡが近接していれば、どちらから求められるものも正確である。
【００３８】
１．３  一定保持時間近似法（ＣＨＴＡ）
本セクションで紹介する許可管理法は、割込み確率の計算とみなす必要のないものである。即時要求コールのためのＣＨＴＡ許可管理法は、各新規の即時要求コールが一定の保持時間Ｈを有すると仮定する。当該コールは、リンク中にＨ時間単位分の十分な空きキャパシティがあれば許可される。空きがなければ拒絶される。予定の終了時間はモニタされる。もし、当該コールがＨ時間単位以前に終了すれば、その分の空きは別のコールに供される。終了していなければ、新規のコールが到着するといつでも、Ｈ時間単位を越えて続いている全即時要求コールは、その時点では存在するが、程なく（無限小の時間間隔後に）終了するとしてカウントされる。
【００３９】
もし、Ｈを非常に大きく、たとえばＨ＝∞にすると、コール割込みは実質的に許されなくなる。即時要求の到着は、将来何らかのコンテンション（回線の争奪）があれば許可されなくなる。同様に、新規の予約コールも、通信中の即時要求コールがそれから割込みをされるのであれば、許可されなくなる。ＣＨＴＡは通信中のコールの終了時間を予定に入れているので、ＦＴＡは、Ｈ＝ＫであるＣＨＴＡとは同じではないことに注意する。
【００４０】
以下で検討するシミュレーションの例によれば、ＣＨＴＡは、即時要求コールの保持時間が実際一定でない場合、割込み確率の計算に基づいた方法に比べてパフォーマンスが悪い。その上、Ｈが有限値の場合、システム中の空きキャパシティの更新に伴う“帳簿づけ”がある。
【００４１】
２．  シミュレーション結果
本セクションでは、本発明によるトラフィックモデルとサービス目標について検討する。ここで検討するトラフィックモデルは、以下で検討する本許可管理法のシミュレーションで用いられるが、許可管理法は、このモデルの使用を必要としない。ここで、（サービスを要求する）予約コールと即時要求コールは、到着率がλBとλIの独立した定常の確率点過程に従って到着すると仮定する。さらに、予約（即時要求）コールの保持時間は、平均がμB-1（μI-1）の共通の分布（同一の分布）を有すると仮定する。またさらに、次の予約時間は、平均がｔbの、独立し同一に分布した確率変数であると仮定する。到着過程、保持時間、予約時間はすべて相互に独立していると仮定する。
【００４２】
許可管理のパフォーマンスの特徴を明らかにするために次のことに着目する。
【００４３】
・ＰI：即時要求コールの遮断確率、すなわち、許可管理アルゴリズムにより、またはリンクが混雑しているために拒絶される即時要求コールの長期間にわたる割合（ロングラン・フラクション）。
【００４４】
・ＰB：予約コールの遮断確率、すなわち予告された保持時間中のキャパシティの不足、または上限などの何らかの許可管理によって拒絶される予約コールの長期間にわたる割合（ロングラン・フラクション）。
【００４５】
・ｐ：即時要求コールの割込み確率、すなわち、リンクの混雑のために通信中に割込みをされる許可された即時要求コールの長期間にわたる割合。
【００４６】
前述のように、ここでは予約コールは割込みをされないと仮定する。許可されたコール間で資源のコンテンションがあるときは、即時要求コールが割込みをされると仮定する。最初に割込みをされるのは最後に到着した即時要求コールである。
【００４７】
サービスを終了する即時要求コールと予約コールのコール当たりの収益をＲIとＲB、即時要求コールに割込みをするためのコール当たりのコストをＣIと仮定する。さらに、サービスを終了する即時要求コールと予約コールの時間当たりの収益率をｒIとｒBと仮定する。次に、即時要求コールと予約コールを許可するための許可管理法は、収益率を最大にするように選ばれる。すなわち、
【数８】
0004448205.tif 000009
ｐ≦Ｐの制約を受け、Ｐは、即時要求コールの割込み確率の上限、１／μ'Iは割込みをされない即時要求コールの平均の保持時間である。μ'IはμIではないことに注意する。割込みに条件をつけると保持時間分布は影響を受ける。割込みをされたコールがそれまでに完了した時間の平均は１／μIより長い傾向にあるが、割込みをされなかったコールの平均の長さは１／μIより短い傾向にある。しかしながら、割込み確率は非常に小さいことを通常所望されているのだが、その場合、μ'IはμIとほぼ同じになる傾向にある。したがって、（２．１）のμ'IはμIに置き換えてよい。
【００４８】
本セクションでは、即時要求コールの割込み確率の近似法がどのようなパフォーマンスを遂行するかを示したシミュレーション結果について検討する。シミュレーションは、前述のトラフィックモデルのフレームワークの中で実施した。ここでは、即時要求コールと予約コールは独立したポアソン過程に従って到着し、すべての保持時間は指数分布であると仮定している。先に指摘したように、すべての予約コールは、即時要求コールの保持時間と比べてかなり先の予約をすると仮定する。
【００４９】
簡単にするために、すべての予約コールは、ｔb＞＞１／μIである一定量のｔbだけ先の予約をすると仮定する。ｔb＞＞１／μIであると仮定すると、一定量の時間だけ先に予約するというのはかなり一般的なことである。なぜならば、予約コールのサービス開始時間は、予約時間がランダムである場合でさえもポアソン過程を形成するからである。この性質は、Ｍ／ＧＩ／∞待ち行列モデルにおけるサービス終了過程（デパーチャープロセス：ｄｅｐａｒｔｕｒｅ  ｐｒｏｃｅｓｓ）がポアソン過程であることに等しい。Ｍ／ＧＩ／∞待ち行列は、ポアソン到着過程、独立し全く同一に分布したサービス時間、無限のサーバを有する。（たとえば、Ｓ．Ｇ．Ｅｉｃｋ，Ｗ．Ａ．Ｍａｓｓｅｙ，Ｗ．Ｗｈｉｔｔ著“Ｔｈｅ  Ｐｈｙｓｉｃｓ  ｏｆ  ｔｈｅ  Ｍt／ＧＩ／∞  Ｑｕｅｕｅ”，Ｏｐｅｒａｔｉｏｎｓ  Ｒｅｓｅａｒｃｈ、４１：７３１−７４２、１９９３参照。）予約時間が一定であることによって、予約コールがすべてかなり先の予約をすることが保証される。このことは、予約時間がランダムであっても、ある最小値を越えるという要件を満たせば達成することができる。
【００５０】
実施例１：使用可能なキャパシティ（サーバ数）をｓ＝１００、帯域幅の大きいコールが各々要求する帯域幅（サーバ数）をｂ＝１０、帯域幅の小さいコールクラスの到着率をλI＝６０、帯域幅の大きいコールクラスの到着率をλB＝２とする。両コールクラスの平均保持時間を１とする。帯域幅の小さいコールクラスの帯域幅は、以前に１と仮定した。シミュレーションは、遮断確率を、即時要求コールの割込み確率閾値ＰTと、予約コールに課せられた上限ｓ−ｒの関数として見積もるために実施された。この最初の実施例については予約コールに上限を課さなかった。したがってｒ＝０であった。
【００５１】
入力制御ＰTが与えられると、ＰB、ＰI、ｐの見積値は各シミュレーションのランから得られた。各曲線は１０個の異なるＰTに基づいている。ＰTの各値について、シミュレーションのランレングスは、トランジエントを除外するために２５時間単位を削除した後、１００，０００時間単位であった。したがって、曲線の各点について、およそ６００万の即時要求コールの到着と２００万の予約コールの到着がシミュレートされた。セクション１．３の３種類の近似法について、ＰI対ｐのプロット図が図２に示されている。定常状態のシミュレーションのランレングスの１００，０００は２０のバッチに分けて信頼区間を計算したが、ここには示されていない。しかしながら、滑らかでないプロットがかなり滑らかに見えるという事実は、データポイントが正確であることを示している。
【００５２】
予約コールの遮断確率ＰBはＰTとは無関係で、この場合０．００００３８であった。ＰIとｐの間にはおもしろい相殺関係があり、ＰTが増加すると、ｐは増加するがＰIは減少する。図２から明らかなように、各固定値のｐに関して、ＩＰＡはＦＴＡやＯＰＡよりもかなり小さいＰIを有する。このことは、必然的に（２．１）の基準下でＩＰＡの収益率が高いことを意味する。セクション１．３のアルゴリズムＣＨＴＡは、他の３つのアルゴリズムよりもかなりパフォーマンスが悪い。あまり悪いので、関連の詳細を曖昧にせずに他の３つのアルゴリズムと同じグラフ上に表すのは難しい。したがって、パフォーマンスデータは表１に示す。
【００５３】
【表１】
0004448205.tif 000010
表１の最後の３行はキーポイントを非常にはっきりと示している。すなわち、小さな割込み確率を許すことで、遮断確率を著しく低下させることができる。この効果は、ＰT＝０に設定すると（つまりｐ＝０になる）、ＩＰＡでも観察できる。ＰT＝０であると、即時要求コールの遮断確率ＰIは０．２６４になった。これは、図２のＩＰＡ曲線に見られる最大値よりかなり大きい。
【００５４】
実施例２：実施例１とは対照的に、ここでは即時要求コールの遮断確率が高い場合について考えた。予約コールの到着率も高くして、到着する即時要求コールからみたときのプロフィール中の“ピーク”数（割込み回数（ｔｉｍｅｓ））を多くする。特に、変数は次のとおりである。ｓ＝４０、λI＝２４、μI＝１、λB＝１６、μB＝４、ｂ＝５。ｐ対ＰIのプロット図を図３に示す。
【００５５】
各曲線は１０個の異なるＰTに基づいている。ＰTの各値について、シミュレーションのランレングスは、トランジエントを除外するために２５時間単位を削除した後、１０，０００時間単位であった。したがって、この場合、曲線上の各点について、およそ２４万の即時要求コールの到着と１６万の予約コールの到着がシミュレートされた。ここでもＩＰＡのパフォーマンスが最も良いが、この場合、ＦＴＡ曲線もＩＰＡ曲線に極めて近い。
【００５６】
実施例３：本実施例では、収益率を向上させるのに上限ｓ−ｒをいかに有効に使用できるかを示す。新しい制御変数ｒ以外は実施例１と同じシステム変数の集合を考える。ｒの各値について、ＩＰＡを使用したｐ対ＰIのプロット図を図４に示す。対応するＰBは表２に示す。実施例１と同様、曲線は１０個の異なるＰTに基づいており、ＰTの各値について、シミュレーションのランレングスは、トランジエントを除外するために２５時間単位を削除した後、１００，０００時間単位であった。
【００５７】
【表２】
0004448205.tif 000011
予想されるとおり、予約変数ｒの値が大きくなると、即時要求コールの遮断および割込みのパフォーマンスが良くなる。いくつかのｒについて、ｐ対平均収益Ｒのプロット図を図５に示す。ｒB＝ｒI＝１、ＲB＝ＲI＝０として、等式（２．１）を使って求めたものである。最良の結果Ｒ＝７６．３は、まずｒ＝５０で達成され、次いでｒ＝６０で達成された。これとは対照的に、ｒ＝０についての最良の収益は７６．０、リンク分割については７４．３である（キャパシティ３０を予約コール専用）。ｒB＝ｒI＝１であるので、本例の収益はキャリードロード（負った負荷）に相当する。オファードロード（与えた負荷）は８０であるので、損失収益はリンク分割の５．７からｒ＝５０を用いた資源共用の３．７へと３５％減少した。
【００５８】
表２から、本例の最適解は比較的高い予約コール遮断確率ＰB＝０．０３７を有することがわかる。予約コールの方の価値が高い、すなわちｒB＞ｒIであれば、ｒの最適値は減少し、その結果ＰBも減少する。
【００５９】
設計の観点から、ｐ対Ｒ曲線上の所定の動作ポイントでネットワークを実行するためにもう一つの関係を特定する必要がある。これは、割込み確率閾値ＰTと実現（リアライズド：realized）割込み確率ｐとの関係である。最適予約変数ｒ＝５０について、この（明らかに直線の）関係を図６に示す。
【００６０】
３．即時要求コールの保持時間が非指数分布の場合
即時要求コールに保持時間が指数分布であるという仮定を当てはめると、即時要求コールの保持時間がメモリレスであるという性質が失われる。（メモリレスの性質は次のように記述できる。すべて正のｓおよびｔに対してＰ（Ｘ＞ｔ＋ｓ｜Ｘ＞ｓ）＝Ｐ（Ｘ＞ｓ）。このことは、経過した保持時間は残りの保持時間分布に何の影響も与えないということを意味する。）メモリレスの性質がなければ割込み確率の計算が複雑になる。保持時間の累積分布関数（ｃｄｆ）をＧ、通信中のいずれかのコールの経過保持時間をＸとすると、当該コールの残りの保持時間は相補的な累積分布関数を有する。
【００６１】
【数９】
0004448205.tif 000012
ここで、Ｇc（Ｘ）＝１−Ｇ（Ｘ）である。したがって、通信中のｎコールについて経過保持時間をＸ1，・・・・，Ｘnとすると、残りの保持時間は、（３．１）で定義された累積分布関数Ｈx1，・・・，Ｈxnを有する独立した確率変数である。これらの累積分布関数の値は異なるので、将来の事象の正確な計算は難しい組合せの問題になる。
【００６２】
幸いなことに次のような単純化がかなり有効のようである。経過した保持時間を無視すると、記憶すべき情報量を削減できる。経過保持時間を無視し、ポアソン到着過程を仮定し、無限サーバの近似をする。次に、平衡状態にある或る時間に、通信中のコールがｎ個あるという条件をつけると、これらのｎコールの残りの保持時間は、累積分布関数Ｇeを有する独立した確率変数として分布する。Ｇeは定常−過剰（stationary-excess）の累積分布関数で、次式によって与えられる。
【００６３】
【数１０】
0004448205.tif 000013
この性質は、到着時間と保持時間のペアが平面上でポアソンランダム測度（メジャー：measure）に従って分布するために維持される。（たとえば、先に引用したＥｉｃｋらの定理１参照）。
【００６４】
経過時間を無視する無限サーバ近似によって、ＦＴＡ、ＯＰＡ、ＩＰＡ許可管理アルゴリズムを、計算量を増加させずに、非指数分布である保持時間分布に直接拡大することができる。たとえば、（１．４）の代わりに、ＩＰＡの割込み確率は次式のようになる。
【００６５】
【数１１】
0004448205.tif 000014
すなわち、前のコールは累積分布関数Ｇeを有するが、新規のコールは累積分布関数Ｇを有する。ＯＰＡ、ＦＴＡについての表現式も同様にして得られる。
【００６６】
実施例４：説明のために、実施例３の変数は、ｒ＝５０、および保持時間分布は平衡平均（バランスド・ミーン）、すなわち総平均（オーバーオール・ミーン）１／μIを２乗した変動係数Ｃa2を有する超指数分布とする。（２乗した変動係数は、その平均の２乗に対する標準偏差の平方の比である。）超指数分布を用いれば、コールが到着すると、ｑの確率で、平均が１／μ1の指数分布から保持時間を選び、１−ｑの確率で、平均が１／μ2の別の指数分布から保持時間を選ぶ。このモデルは、異なる指数分布の保持時間を有する２つのサブクラスの即時要求コールを表すのにふさわしい。平衡平均の仮定は、ｑ／μ1＝１−ｑ／μ2を必要とすることによって１つの変数を特定する。各シミュレーションのランレングスは、トランジエントを除外するために２５時間単位を削除した後、５００，０００時間単位であった。各曲線は１０個のシミュレーションランを基にプロットされている。シミュレーションランは、適当な滑らかな曲線をえるために実施例２より長い。これは、保持時間分布の変動性が増加したためである。
【００６７】
超指数分布に基づいたＩＰＡ（Ｈｙｐｅｒｘで表示）を、指数分布に基づいたＩＰＡ（ＥｘｐＩＰＡで表示）と比較した。すなわち、ＥｘｐＩＰＡは、実際の保持時間が超指数分布のとき、指数分布を仮定しているセクション１．２のＩＰＡアルゴリズムを用いた。比較の目的は、Ｈｙｐｅｒｘのパフォーマンスを調べることと、ＥｘｐＩＰＡが保持時間分布に感応するかどうかをチェックすることである。Ｃa2＝１０について、ＨｙｐｅｒｘとＥｘｐＩＰＡが図７に比較してある。Ｈｙｐｅｒｘのパフォーマンスの方がＥｘｐＩＰＡより明らかに優れている。この例から、即時要求コールの保持時間分布に関する知識を利用すれば、計算量を増やすことなく収益を改善できることがわかる。
【００６８】
実施例５：ここでは、即時要求コールの保持時間が所定の場合について考える。これを考えるのは、結果をＣＨＴＡと比較できるからである。ＣＨＴＡは、ｒが固定値であるこの特例に明らかに最適である。したがって、実施例４と同じ変数をここでは使用する。ただし、唯一の相違点は即時要求コールの保持時間が所定値であるということである。ｔ≦ＴのときＧe（ｔ）＝ｔμIは、ｔ＞Ｔのとき１であることに注意する。各シミュレーションのランレングスは、トランジエントを除外するために２５時間単位を削除した後、１００，０００時間単位であった。各曲線は１０個のシミュレーションランを基にプロットされている。
【００６９】
ＤｅｔＩＰＡとＣＨＴＡが図８に比較してある。図８で、ＣＨＴＡ曲線は一定で、割込みを許可しない。ＣＨＴＡとＤｅｔＩＰＡ間のギャップは、エイジの経過を追わず、利用しなかったために失ったものである。しかしながら、図８の曲線は、このギャップは小さいことを示している。したがって、無限サーバ近似は、最適解がわかっている一例においては確かに優れており、ほぼ最適である。
【００７０】
本発明のいくつかの形態について特に説明をしてきたが、本発明の範囲内で多様な変形が可能であることはいうまでもない。たとえば、本説明では、特に通信ネットワークにおける資源共用を取り上げたが、本発明の資源共用法は、他の多くの状況、たとえば、製造施設における自動化装置類の割り当てなどの状況で容易に実施することができる。
【図面の簡単な説明】
【図１】  本発明による予約コールのプロフィールが与えられた場合の即時要求コールの予想割込み時間を示す図である。
【図２】  本発明による種々の割込み確率近似法を用いた第一のシミュレーション例の割込み確率対遮断確率のプロット図である。
【図３】  本発明による種々の割込み確率近似法を用いた第二のシミュレーション例の割込み確率対遮断確率のプロット図である。
【図４】  本発明による種々の予約変数値を用いた第三のシミュレーション例の割込み確率対遮断確率のプロット図である。
【図５】  本発明による種々の予約変数値を用いた第三のシミュレーション例の割込み確率対収益のプロット図である。
【図６】  本発明による第三のシミュレーション例の割込み確率閾値対実現割込み確率のプロット図である。
【図７】  本発明による異なる指数分布の保持時間を有する２種類のクラスの即時要求コールの割込み確率対収益のプロット図である。
【図８】  本発明による所定の保持時間と一定の保持時間を有する各即時要求コールの割込み確率対収益のプロット図である。
【図１】
0004448205.tif 000015
【図２】
0004448205.tif 000016
【図３】
0004448205.tif 000017
【図４】
0004448205.tif 000018
【図５】
0004448205.tif 000019
【図６】
0004448205.tif 000020
【図７】
0004448205.tif 000021
【図８】
0004448205.tif 000022