(57)【特許請求の範囲】
【請求項１】
各々がある容量を持つ伝送リンクとスイッチングノードとを含む複数の制約付き資源を有するパケット通信ネットワークにおいて、与えられたサービス優先度をもつ新しい接続の受付を管理する方法であって、
前記新しい接続に影響するよう選択され得る各制約付き資源と各サービス優先度とについて、以前に受け付けられた各接続の個々の有効バンド幅の和で表わされる全有効バンド幅を生成するステップと、
それぞれが前記与えられたサービス優先度とそれより下位の各サービス優先度とに関連付けられ、損失基準に基づく、前記新しい接続の複数の有効バンド幅を決定するステップと、
前記生成するステップにおいて前記全有効バンド幅が生成された前記制約付き資源の中から、前記新しい接続についての前記与えられたサービス優先度とそれより下位の各サービス優先度について前記全有効バンド幅と前記決定された有効バンド幅との和が前記容量未満である前記制約付き資源を選択できる場合に、前記新しい接続を受け付けるステップと、
を含む方法。
【請求項２】
請求項１に記載の方法において、前記新しい接続についての前記複数の有効バンド幅がネットワーク端間の遅延基準に基づくことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記新しい接続についての前記複数の有効バンド幅が、空バッファ有効バンド幅（ＥＢＥＢ）に応じて決定されることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、有効バンド幅を予め計算してデータベースに登録しておき、前記決定ステップでは、そのデータベースから前記新しい接続についての前記複数の有効バンド幅を検索することを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記決定ステップが前記新しい接続についての前記複数の有効バンド幅を求めるために測定値を得るステップを含むことを特徴とする方法。
【請求項６】
請求項１に記載の方法において、少なくとも一つの前記新しい接続についての複数の前記有効バンド幅が同じ値を持つことを特徴とする方法。
【請求項７】
請求項１に記載の方法において、既に受け付けられている接続及び前記新しい接続は複数のソース型に分類され、同じソース型と同じサービス優先度とを持つ複数の接続は前記複数の有効バンド幅について同じ値を持つことを特徴とする方法。
【請求項８】
請求項１に記載の方法において、前記伝送リンクの少なくとも一つは、前記接続のために専用化された伝送路上でのバンド幅の一部であることを特徴とする方法。
【請求項９】
ある容量を持つ伝送リンクで相互接続された複数のスイッチングノードを含むパケット通信ネットワークにおいて、接続解放時のバンド幅更新を管理する方法であって、
特定のサービス優先度を有する接続を終了させる要求を受けるステップと、
前記特定のサービス優先度とそれより下位の各サービス優先度について、それ以前に受け付けられた接続の有効バンド幅の和で表わされる全有効バンド幅にアクセスするステップと、
終了させるべき接続について、前記特定のサービス優先度とそれより下位の各サービス優先度とにそれぞれ対応する複数の有効バンド幅にアクセスするステップと、
前記特定のサービス優先度とそれより下位のサービス優先度について、与えられたサービス優先度での前記終了させるべき接続についての有効バンド幅を全有効バンド幅から差し引くことにより、全有効バンド幅を更新するステップと、
前記接続を解放し終了させるステップとを含み、
前記新しい接続についての前記複数の有効バンド幅が損失基準に基づくことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、前記新しい接続についての前記複数の有効バンド幅が遅延基準に基づくことを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、前記新しい接続についての前記複数の有効バンド幅が、空バッファ有効バンド幅に応じて決定されることを特徴とする方法。
【請求項１２】
請求項９に記載の方法において、有効バンド幅を予め計算してデータベースに登録しておき、前記アクセスステップでは、そのデータベースから前記新しい接続についての前記複数の有効バンド幅を検索することを特徴とする方法。
【請求項１３】
請求項９に記載の方法において、既に受け付けられている接続及び前記解放された接続は複数のソース型に分類され、同じソース型と同じサービス優先度とを持つ複数の接続は前記複数の有効バンド幅について同じ値を持つことを特徴とする方法。
【請求項１４】
請求項９に記載の方法において、前記伝送リンクの少なくとも一つは、前記接続のために専用化された伝送路上でのバンド幅の一部であることを特徴とする方法。
【請求項１５】
（ｉ）リンクの容量の初期値と、（ｉｉ）与えられた特定のサービス優先度とソース型とに関する可能な接続の分類と、（ｉｉｉ）前記各分類された接続ごとにそれぞれ割り当てられ、当該接続のサービス優先度及びそれより下位の各サービス優先度にそれぞれ対応した複数のサービス優先度と、（ｉｖ）接続の分類に対応して提供された負荷ベクトルと、（ｖ）ブロッキング基準と、が与えられたときに、パケット通信ネットワーク内のリンクのサイズを調整する方法であって、
（ａ）前記リンクの容量と前記分類された各接続についての前記複数の有効バンド幅について、前記接続の受付可能集合を決定するステップと、
（ｂ）前記受付可能集合と負荷ベクトルに基づき、各サービス優先度と各ソース型との組合せごとに、ブロックされる接続の部分を決定するステップと、
（ｃ）前記ステップ（ａ）及び（ｂ）を繰り返し、ブロックされた接続の部分が前記ブロッキング基準を超えれば前記リンク容量を増やし、前記ブロッキング基準が満たされれば前記ブロッキング基準が満たされないようになるまで前記リンク容量を段階的に減らしていくステップと、
を含む方法。
【請求項１６】
請求項１５に記載の方法において、ステップ（ｂ）で決定される前記接続の部分はＦＩＦＯネットワークの中で使用されているアルゴリズムにしたがって決定されることを特徴とする方法。
【請求項１７】
請求項１０に記載の方法において、前記リンクは、前記接続のために専用化された伝送路上でのバンド幅の一部であることを特徴とする方法。
【請求項１８】
ある容量を持つ共有資源についての新しいサービス要求の受付を管理する方法であって、
前記共有資源上での各サービス優先度について、それ以前に受け付けたサービス要求についての個々の有効バンド幅の和に対応する全有効バンド幅を生成するステップと、
特定のサービス優先度を有する新しいサービス要求を受けたときに、その新しい要求について、前記特定のサービス優先度とそれより下位のサービス優先度にそれぞれ対応した複数の有効バンド幅にアクセスするステップと、
前記特定のサービス優先度とそれより下位のサービス優先度について、（ｉ）与えられたサービス優先度についての前記全有効バンド幅と、（ｉｉ）前記新しい要求についての前記与えられたサービス優先度での前記有効バンド幅と、の和が前記共有資源の容量未満であれば、前記新しい要求を受け付けるステップと、
を含み、
前記新しいサービス要求の前記複数の有効バンド幅が、損失基準に基づくことを特徴とする方法。
【請求項１９】
請求項１８に記載の方法において、前記新しいサービス要求についての前記複数の有効バンド幅が遅延基準に基づくことを特徴とする方法。
【請求項２０】
請求項１８に記載の方法において、前記新しいサービス要求についての前記複数の有効バンド幅が、空バッファ有効バンド幅（ＥＢＥＢ）に応じて決定されることを特徴とする方法。
【請求項２１】
請求項１８に記載の方法において、有効バンド幅を予め計算してデータベースに登録しておき、前記アクセスステップでは、そのデータベースから前記新しいサービス要求についての前記複数の有効バンド幅を検索することを特徴とする方法。
【請求項２２】
請求項１８に記載の方法において、前記アクセスステップが前記新しいサービス要求についての前記複数の有効バンド幅を求めるために測定値を得るステップを含むことを特徴とする方法。
【請求項２３】
請求項１８に記載の方法において、前記共有資源がパケット通信ネットワークであることを特徴とする方法。
【請求項２４】
ある容量を持つ共有資源において、特定のサービス優先度を有するサービスの解放時に、前記共有資源の占有度の更新を管理する方法であって、
前記サービスを終了させる要求を受けるステップと、
前記特定のサービス優先度とそれより下位の各サービス優先度について、それ以前に受け付けられたサービスの有効バンド幅の和で表わされる全有効バンド幅にアクセスするステップと、
終了させるべき前記サービスについて、前記特定のサービス優先度とそれより下位の各サービス優先度とにそれぞれ対応する複数の有効バンド幅にアクセスするステップと、
前記アクセスステップにおいてアクセスされた前記複数の有効バンド幅を前記和から差し引くことにより、全有効バンド幅を更新するステップと、
前記サービスを解放し終了させるステップと、を含み、
前記サービスの前記複数の有効バンド幅が、損失基準に基づくことを特徴とする方法。
【請求項２５】
請求項２４に記載の方法において、前記サービスについての前記複数の有効バンド幅が遅延基準に基づくことを特徴とする方法。
【請求項２６】
請求項２４に記載の方法において、前記サービスについての前記複数の有効バンド幅が、空バッファ有効バンド幅に応じて決定されることを特徴とする方法。
【請求項２７】
請求項２４に記載の方法において、有効バンド幅を予め計算してデータベースに登録しておき、前記アクセスステップでは、そのデータベースから前記サービスについての前記複数の有効バンド幅を検索することを特徴とする方法。
【請求項２８】
（ｉ）共有資源の容量の初期値と、（ｉｉ）与えられた特定のサービス優先度とソース型とに関する各サービス要求の分類と、（ｉｉｉ）前記各サービス要求ごとにそれぞれ割り当てられ、当該サービス要求のサービス優先度及びそれより下位の各サービス優先度にそれぞれ対応した複数のサービス優先度と、（ｉｖ）サービス要求の分類に対応して提供された負荷ベクトルと、（ｖ）ブロッキング基準と、が与えられたときに、共有資源のサイズを調整する方法であって、
（ａ）前記容量と前記分類された各サービス要求についての前記複数の有効バンド幅について、前記接続の受付可能集合を決定するステップと、
（ｂ）前記受付可能集合と負荷ベクトルに基づき、各サービス優先度と各ソース型との組合せごとに、ブロックされるサービス要求の部分を決定するステップと、
（ｃ）前記ステップ（ａ）及び（ｂ）を繰り返し、ブロックされたサービス要求の部分が前記ブロッキング基準を超えれば前記容量を増やし、前記ブロッキング基準が満たされれば前記ブロッキング基準が満たされないようになるまで前記容量を段階的に減らしていくステップと、
を含む方法。
【請求項２９】
請求項２８に記載の方法において、ステップ（ｂ）で決定される前記サービス要求の部分はＦＩＦＯネットワークの中で使用されているアルゴリズムにしたがって決定されることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット通信ネットワークなどの共有資源の管理方法、特に共有資源に対するサービス要求の受付処理の管理方法に関する。
【０００２】
【従来の技術】
新しく出現しつつある、たとえばＡＴＭ技術を使用する広帯域ＩＳＤＮのような高速通信ネットワークは、回線交換型よりはパケット型ネットワークとなる傾向にある。これはパケット構造の方がよりよい資源（リソース）の共有が見込まれるからである。パケットネットワークでは、ソースに対し、全接続期間にわたって、専用のバンド幅（たとえば回線）を割り当てる必要はない。しかし不幸にして、パケットネットワークでは、柔軟性が強化されたことが、かえって既存のネットワークに入ろうとする接続（コネクション）に対する効果的な接続受付制御や、将来のネットワークの設計段階での容量計画を難しくしている。
【０００３】
パケットネットワークにおける接続受付制御と容量計画の問題は、接続の「有効バンド幅」あるいは「等価バンド幅」で知られる概念により説明されよう。この概念を用いると、適切な有効バンド幅が各接続に割り当てられ、各接続はアクティブ期間中この有効バンド幅を必要とするかのように取り扱われる。与えられた組み合わせの接続を受け付けられるか否かは、有効バンド幅の和が使用可能な全バンド幅（すなわち容量）を超えないことを保証できるか否かによって決まる。このように有効バンド幅を用いることにより、接続受付制御と容量計画の問題は、回線交換型ネットワークにおいて適用されているのと同様の手法で記述される。有効バンド幅に関しては、例えば米国特許第５，２８９，４６２号や５，５２１，９７１号に詳細に説明されている。
【０００４】
通信ネットワークを利用する異なる階層の顧客に、異なるサービス品質（ＱＯＳ）を保証する（すなわち顧客に、そのクラスに応じた品質のサービスを提供する）ことが望ましいことがよくある。ネットワークノードは、リンク上で確立されている接続群を異なる複数の優先度に区分けし、ある優先度の接続からのキュー内のすべてのパケットが、それより低い優先度の接続からのパケットのどれよりも先に発信されるよう、設計されてきた。これにより、異なる優先度に基づきネットワーク資源を割り当てることは現実的に可能になりつつある。しかしながら、有効バンド幅の概念を用いる既知の接続受付制御方法は、ネットワークノードが到着順処理（ＦＩＦＯ）方式で動作することを仮定している。
【０００５】
【発明が解決しようとする課題】
接続に優先度を設定する場合、パケットの処理順序は優先度に依存するためＦＩＦＯ方式にはならない。このため、ＦＩＦＯ方式を仮定した従来の有効バンド幅利用の接続受付制御方法は、優先度ベースのシステムにはそのまま適用できなかった。
【０００６】
優先度ベースのシステムにおいて適切な接続受付制御と容量計画を実現するためには、ネットワークノード上でのサービスの優先度を表すことができる有効バンド幅を採用するのが望ましい。
【０００７】
この課題は、パケット通信ネットワークに限らず、複数のソースによって資源が共有されるシステム全般に共通する課題である。
【０００８】
【課題を解決するための手段】
本発明は、ある容量を持つ共有の資源（リソース）に対する新しいサービス要求を受け付ける際の制御方法に関する。新しい要求は、サービス優先度を有している。例えば、共有資源はパケット通信ネットワークであり、サービス要求は新しい接続の受付の要求である。本発明に係る方法では、まず共有資源上の各サービス優先度について、それぞれ全有効バンド幅が生成される。全有効バンド幅は、以前に受け付けられたサービス要求の個々の有効バンド幅の和によって表わされる。ある特定のサービス優先度を持った新しいサービス要求を受けると、その新しい要求のために、複数の有効バンド幅がアクセスされる。ここで、それら複数の有効バンド幅は、各々その新たな要求に係る特定のサービス優先度及びそれより下位の各サービス優先度に関連づけられている。新しい要求は、その要求に係る特定のサービス優先度とそれより下位のサービス優先度について、（ｉ）ある与えられたサービス優先度についての前記全有効バンド幅と、（ｉｉ）前記新しい要求についての前記与えられたサービス優先度での有効バンド幅と、の和が前記共有資源の容量より小さければ、受け付けられる。
【０００９】
また、本発明は、サービス要求を解放したり、共有資源の容量を調整したりするための種々の方法を包含するものである。
【００１０】
【発明の実施の形態】
図１は、１〜８まで番号付けられた８個のネットワークノード１１を含むパケット伝送システム１０の一般的なブロック図を示した。各ネットワークノード１１は一つ以上の通信リンクＡ〜Ｌによって他のネットワークノード１１と接続されている。各通信リンクは多様な接続（コネクション）をサポートすることができる。サポートされる接続は、例えば、半固定接続や、選択的に使用可能となる（ダイアルアップされる）接続である。ネットワークノード１１群の一部または全ては、終端ノードに接続される。例えば図では、ネットワークノード２は終端ノード１、２、３に、ネットワークノード７は終端ノード４、５、６に、ネットワークノード８は終端ノード７、８、９に接続されている。ネットワークノード１１は、それぞれデータ処理システムを含む。データ処理システムは、接続された全てのノード（すなわちネットワークノードと終端ノード）と、そのデータ処理システムが所属するノードの中の決定ポイントとに対し、データ通信サービスを提供する。ネットワークノード１１各々は、一つ以上の決定ポイントを含み、そこではデータパケットが選択的に一つ以上の出側通信リンクにルーティングされて他のノードに向けられる。この経路決定はデータパケットのヘッダー部にある情報に応じてなされる。ネットワークノードは、またターミナルノード間の経路、すなわちパス、の計算などの補助的なサービスを行いつつ、そのノードからネットワークに入るパケットにアクセス制御を提供し、経路計算に用いられるネットワークトポロジーデータベースの管理やディレクトリーサービスを行う。
【００１１】
伝送システム１０において二つのノード間の接続を確立する際のステップは、バンド幅割当て、経路選択、接続受付制御、及び発呼準備を含む。バンド幅割当てと接続受付制御は、確立すべき接続の「有効バンド幅」を決定することにより達成される。接続の有効バンド幅は、ソースのトラフィック特性と望まれるサービス品質に基づいて、新しい接続が生み出す負荷を評価する。伝送システムは、その接続の継続期間中、その接続がその有効バンド幅を必要とするものと仮定する。
【００１２】
米国特許第５，２８９，４６２号は、有効バンド幅計算に使用しうる一方法を提示している（その特許の式２を参照）。しかし、先に述べたように、この既知の方法は、接続に異なる優先度が割り当てられることを考慮に入れておらず、むしろ単純にＦＩＦＯ型のサービスを採用している。
【００１３】
図２はネットワークノード２０のブロック図を示す。ネットワークノード２０は、各接続に割り当てられた優先度に基づいて、出側リンク２１へパケットを供給するよう構成されている。ノード２０は、接続を待機させておくためのバッファー２３を含む。バッファー２３の中のキュー１は最高の優先度を持ち、パケットは、このキュー１からリンク２１へＦＩＦＯ形式でキュー１が空になるまで供給される。キュー１が空になると、これが空のままである限り、パケットはキュー２からＦＩＦＯ形式で供給される。この処理は、最下位優先度のキュー（キューＩ）に至るまで続く。最下位優先度のキューに至るのは、それより上位のキューが全て空になったときである。当業者なら分かるように、キュー１〜Ｉは、物理的に単一のバッファーとして構成しても良いし、分離した複数のバッファーとして構成しても良い。現状のパケット交換では、サービス優先度は２つから４つのレベル（Ｉ＝２〜４）で実装するのが典型的である。ただし、本実施形態は、それに限らず任意数レベルの優先度に適用できる。
【００１４】
サービス優先度を説明すると、本実施形態では、各接続（最下位優先度の接続以外）に多重的に有効バンド幅を割り当てる。すなわち、各接続ごとに、その接続のサービス優先度に対し１つの有効バンド幅を、それより下位の各優先度に対しそれぞれ１つの有効バンド幅を割り当てる。個々の有効バンド幅は、ＦＩＦＯ原理を適用する既知の手順に従い計算できる。ここでは、資源が一つであるケースについて記述する。しかしながら、当業者には分かるように、本実施形態は、２以上の資源を含む場合にも適用可能である。
【００１５】
複数のサービス優先度を有するノードについて適用される従来技術では、各接続に対し単一の有効バンド幅を割り当てていた。優先度ｉ（添え字の値が小さいほど高い優先度をもち、１が最高優先度となる）でソース型ｊの特性をもつ接続の有効バンド幅をｅij表わし、優先度ｉかつソース型ｊの接続の数をｎijとする。優先度の総数はＩと表し、優先度ｉをもつソース型（タイプ）の数はＪiと表す。リンクの容量をＣで表わせば、次の不等式拘束条件が従来技術では用いられた。
【００１６】
【数１】
0003949282.tif 000002
この不等式を満たす接続の数ｎijの集合を受付可能集合と呼ぶ。
【００１７】
本案の発明者は、上記不等式（１）は不必要に控えめな拘束条件であると認識している。各優先度に対して個別の不等式拘束条件を用い、異なる不等式拘束条件下で用いられる同じ接続に対し、異なる有効バンド幅を割り当てることにより（すなわち同じ接続でも不等式拘束条件が異なれば異なる有効バンド幅を割り当てることにより）、著しい改善をなしうる。すなわち、単一の不等式拘束条件はＩ個の不等式拘束条件の組で置き換えられる。
【００１８】
【数２】
0003949282.tif 000003
ただし、ｅkijは、優先度ｋから見たときの（ｉ，ｊ）接続（すなわちソース型ｊ、優先度ｉの接続）の有効バンド幅であり、Ｃはリンクの容量である。言い換えれば、与えられた接続には次のような幾つかの有効バンド幅が割り当てられる。すなわち、与えられた接続のサービス優先度に対して一つの有効バンド幅が割り当てられ、その優先度以下の各優先度に対してそれぞれ一つの有効バンド幅が割り当てられる。ここで注意すべきことは、いくつかのサービスタイプについては、より下位の優先度に対し異なる有効バンド幅を適用してもさほど大きな効果を生まない場合があることである。その場合には、複雑さを減らすために、与えられた（ｉ，ｊ）接続に対する有効バンド幅ｅkijの値を優先度ｋによらず同じにしてもよい。式（２）についての受付可能集合は式（２）におけるＩ個のすべての不等式を満たす接続の数ｎijの集合である。一見すると、式（２）のＩ個の不等式拘束条件は式（１）の単一の不等式拘束条件より拘束が強いように見える。しかし、実際にはそうあるべきであるように、ｅkij≦ｅijが全てのｉ、ｊとｋ≦ｉに対して成り立てば（ただし、ｅkijは式（２）に、ｅijは式（１）にある）、式（２）における新しい受付可能集合は、少なくとも式（１）のそれと同等の大きさである。事実、発明者は式（２）に関する受付可能集合が式（１）に関する受付可能集合よりかなり大きくなりうる事を明らかにしている。
【００１９】
先に述べた受付可能集合は単一の資源（たとえばリンク）の場合にあてはまる。しかしながら、接続が複数の資源を必要とすることもある。その場合には、接続は、その必要とする資源全てに関連する不等式拘束条件を満たさねばならない。
【００２０】
先に述べた特許の中で議論されているようなＦＩＦＯ型サービスに関する有効バンド幅は、性能基準が損失、遅延のいずれに関して指定されるかによらない。損失は、無限容量のバッファーの中でキューの長さが一定の閾値を越える確率によってモデル化されるのが代表的である。しかし、優先度の概念が採用されると、有効バンド幅は、性能基準が損失、遅延のいずれに基づいているのかによって変わる。最高優先度以外の優先度に関して、ワークインシステム（work-in-system：一定サイズのパケットに対するキューの長さを表わす）は遅延よりも著しく小さくなりうるが、これは当該優先度よりも高位の優先度の接続からパケットが到着すると作業処理が中断されるからである。本実施形態では、損失に基づいた性能基準を例にとって説明する。しかし、当業者には明らかなように、本実施形態は、性能基準が遅延に基づく場合にも適用しうる。
【００２１】
必要な有効バンド幅ｅkijは種々の方法により決定しうる。以下、ラージバッファ漸近法（large buffer asymptotics）に基づくアプローチについて記述する。以降の議論のために、性能基準は仮説的な無限容量システムの中の作業負荷に基づいてモデル化する。このモデルでは、その作業負荷は、ｐi以下の確率で閾値ｂiを越えるものとする。ただし、ｂiは、ノードの中で優先度ｉについてのバッファ容量を示す。すなわち、損失に基づいた優先度ｉ基準は次式で表わしうる。
【００２２】
【数３】
確率（優先度ｉの作業負荷＞ｂi）＜ｐi、ｉ＝１，．．，Ｉ    （３）
簡略化された仮定に基づくと、この損失基準を満たす有効バンド幅は次のように表わしうる。
【００２３】
【数４】
0003949282.tif 000004
ただし、η*kは、「有効優先度ｋ基準」と呼び、−ｌｏｇ（ｐk）／ｂkに等しい。そして、
【数５】
0003949282.tif 000005
である。Ａij（ｔ）は［０，ｔ］の時間区間中の（ｉ，ｊ）接続の作業入力である。式（４）は、以下、空バッファ有効バンド幅（Ｅｍｐｔｙ  Ｂｕｆｆｅｒ  Ｅｆｆｅｃｔｉｖｅ  Ｂａｎｄｗｉｄｔｈ：ＥＢＥＢと略称）近似と呼ぶ。なお、本実施形態では、別の方法の利用についても考察している。
【００２４】
図３は、異なる複数のサービス優先度について有効バンド幅を決定するための方法の例を示している。この方法の結果（一連のｅkijの数値となる）は、オフラインで計算され、必要に応じて後で検索できるように蓄積してもよい。図示したように、優先度のインデクスｉは１に初期化され（ステップ１００）、インデクスｋはｉに等しくセットされる（ステップ１１０）。有効優先度基準ηは、有効優先度ｋ基準にセットされる（ステップ１２０）。すなわち、η＝η*kとセットされる。そして、接続タイプを表わすインデクスｊは１にセットされる（ステップ１３０）。ここで計算すべき有効バンド幅は、優先度ｋから見た接続（ｉ，ｊ）の有効バンド幅である（ステップ１４０）。有効バンド幅ｅkijは、例えば、米国特許第５，２８９，４６２号の中の式２で示されるようなＦＩＦＯサービスを採用した既知の方法により計算される（ステップ１５０と１６０）。ステップ１１０〜１６０の処理は、ステップ１７０，１７２，１７４，１７６，１７８，１８０により、ｉ，ｊ，ｋのすべての値について有効バンド幅値ｅkijを計算し終わるまで繰り返される。
【００２５】
図４は、ネットワークノードからのリンク上での接続を受け付けるための具体的な方法に関するフローチャートを示している。この方法では、図３の方法によって計算された有効バンド幅を用いている。ここで、値Ｅkを定義する。この値は、優先度ｋで現在ネットワークに受け付けられている接続の有効バンド幅の和に等しい。Ｅkの値は最初０にセットされる（ステップ５００）。優先度ｉ、型ｊの接続の受付要求を受けて（ステップ５１０）、予め決定されているこの接続のための有効バンド幅の値ｅkij，ｋ＝ｉ，．．．，Ｉがデータベースから検索される（ステップ５２０）。接続は、次の（Ｉ−ｉ＋１）個の不等式、すなわち、Ｅk＋ｅkij＜Ｃ（ｋ＝ｉ，．．．，Ｉについて）が満たされれば、ネットワークに受け付けられる（ステップ５３０）。もし不等式群が満たされないと、接続要求は拒否される（ステップ５４０）。不等式群が満たされれば、接続要求は受け入れられ、ｋ＝ｉ，．．．，Ｉの各々についてＥkの値が更新され、その更新結果の値は新しく受け付けられた接続を反映することになる（ステップ５６０）。処理は、新しい接続要求を受けるまで停止する（ステップ５７０）。
【００２６】
図５は、接続終了時に、リンク上に割り当てられていたバンド幅を解放するための方法に関するフローチャートである。接続ｉ，ｊが終了した通知を受けると（ステップ６００）、ｋ＝ｉ，．．．，Ｉの各優先度ごとに、Ｅkの値が更新される。更新処理は、各優先度ｋ＝ｉ，．．．，Ｉについて、解放された接続の各有効バンド幅値ｅkijをＥkの現在値から差し引くことにより行われる（ステップ６１０）。この後、処理は停止し、次の接続が終了したときに再開する（ステップ６２０）。
【００２７】
図３〜５に記述された方法は、有効バンド幅がオフラインで計算され一定であることを仮定している。しかし、この代わりに、有効バンド幅を通話中のシステムの測定に基づいて調整してもよい。その様な有効バンド幅の測定には種々の方法がある。たとえば、式（５）のΨAijの値は、測定値により推定しうる。すなわち、十分大きなｔについて、次式が成り立つ。
【００２８】
【数６】
0003949282.tif 000006
式（４）を適用するには、この推定は、ｉ≦ｋ≦Ｉを満たすすべてのｋについてのθ＝η*kについて、行うことが必要である。
【００２９】
図６は、接続の数ｎijの受付可能集合が与えられたネットワーク中のリンクの容量を調整する方法に関するフローチャートである。処理は、容量の初期値を選ぶことから始まり（ステップ７００）、最終値に到達するまで引き続き繰り返される。より明確にいえば、受付可能集合α（Ｃ）は、選択した容量Ｃについて前述の不等式の組を満足する値ｎijの集合である（ステップ７１０）。α（Ｃ）と、負荷のベクトルρ（すなわち（ｉ，ｊ）番目の負荷ρijは、接続（ｉ，ｊ）に関する要求の到着率とこれらの接続の平均持続時間との積である）とが与えられたとして、接続（ｉ，ｊ）のうち、この容量に基づきブロックされる部分は、既知のたとえばＧ．Ｃｈｏｕｄｈｕｒｙ他による“Ａｄｖａｎｃｅｓ  ｉｎ  Ａｐｐｌｉｅｄ  Ｐｒｏｂａｂｉｌｉｔｙ”，Ｖｏｌ．２７，１９９５，ｐｐ．１１０４−１１４３，で明らかにされている方法により決定される（ステップ７２０）。このブロックされた接続の部分は、予め定められたブロッキング基準と比較される（ステップ７３０）。なお、ブロッキング基準は入力パラメータとして予め提供されるものである。採用される代表的なブロッキング基準は、例えば、各ｉ，ｊについての接続（ｉ，ｊ）のうち、ブロックされるのが１％未満であるという基準である。ブロッキング基準が満たされないと、容量値Ｃは増やされ（ステップ７４０）、新しく選択された容量について不等式（２）を満たす受付可能集合を定義するところから処理を再開する。一方、ブロッキング基準が満たされば、容量が所望の許容範囲にあるかどうかを決定する（ステップ７５０）。容量が許容範囲にあれば、この方法に係る処理は完了である。容量が許容範囲になければ、容量は下げられ（ステップ７６０）、容量の新しい値を求めて処理が繰り返される。
【００３０】
式（２）における単一のリンクに関するＩ個の優先度に基づくＩ個の拘束条件は、ＦＩＦＯ型サービス原理を用いるＩ個のリンクからなるネットワークに関連したＩ個の拘束条件と等価であると理解される。したがって、例えば上記Ｃｈｏｕｄｈｕｒｙの文献に示されるようなＦＩＦＯネットワークの容量を調整する従来の方法は、優先度ネットワークにも適用しうる。優先度ネットワークには、ネットワーク中の各資源（たとえばリンク）について、それぞれＩ個の拘束条件がある。
【００３１】
先述したように、有効バンド幅は、種々の方法、たとえば式（４）のＥＢＥＢ近似の様な方法、により決定しうる。しかしながら、ある環境下では別の方法がより好適である。たとえば、ネットワークが、統計的ビットレート（Ｓｔａｔｉｓｉｔｉｃａｌ  Ｂｉｔ  Ｒａｔｅ：ＳＢＲ）伝送能力を用いる非同期転送モード（ＡＴＭ）技術を採用していれば、有効バンド幅は、通常のトラフィック記述子、たとえばピーク・セル・レート（Ｐｅａｋ  Ｃｅｌｌ  Ｒａｔｅ：ＰＣＲ）、サステイナブル・セル・レート（Ｓｕｓｔａｉｎａｂｌｅ  Ｃｅｌｌ  Ｒａｔｅ：ＳＣＲ）を用いて決定することができる。これらトラフィック記述子については、ＩＴＵ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｉ．３７１  ’Ｂ−ＩＳＤＮ  Ｔｒａｆｆｉｃ  Ｃｏｎｔｒｏｌ  ａｎｄ  Ｃｏｎｇｅｓｔｉｏｎ  Ｃｏｎｔｒｏｌ’，Ｇｅｎｅｖａ，Ｍａｙ，１９９６を参照されたい。この場合、接続（ｉ，ｊ）には、ｋ≧ｉを満たす優先度ｋについての有効バンド幅ｅkijが割り当てられる。この有効バンド幅ｅkijは、既存の接続の全てと優先度ｋ≧ｉを持つ新しい接続候補とに関するＰＣＲとＳＣＲの関数である。たとえば、ｅiijは、接続の優先度ｉに関してＰＣＲ（ＰＣＲijと記述する）に等しくし、ｅkijはｉより低い優先度ｋ＝ｉ＋１，．．．，Ｉについてαkij（ＳＣＲij）に等しくするなどの方法が考えられる。ただし、ここでαijはある正数である。
【００３２】
当業者には明らかなように、本実施形態の適用はパケット通信ネットワークに限定されるものではない。本実施形態は、優先ステータスがデータパケット以外のものに割り当てられる他の資源共有システムにも等しく適用可能である。
【図面の簡単な説明】
【図１】  パケット伝送システムの概要を示すブロック図である。
【図２】  各接続に割り当てられた優先度に基づいて、パケットを出側リンクに供給するために構成されたノードのブロック図である。
【図３】  実施形態における有効バンド幅の計算方法に関するフローチャートである。
【図４】  実施形態における接続受付の方法に関するフローチャートである。
【図５】  実施形態における接続終了時に割り当てられたバンド幅を解放する方法に関するフローチャートである。
【図６】  実施形態におけるネットーワークの容量の調整方法に関するフローチャートである。
【符号の説明】
１０  パケット伝送システム、１１  ネットワークノード、１２  終端ノード。
【図１】
0003949282.tif 000007
【図２】
0003949282.tif 000008
【図３】
0003949282.tif 000009
【図４】
0003949282.tif 000010
【図５】
0003949282.tif 000011
【図６】
0003949282.tif 000012