(57)【特許請求の範囲】
【請求項１】
回線交換通信ネットワーク（１）に接続される少なくとも１つのプログラム可能な装置（１０）上で、またはそれの助けで実行される方法において、
Ｂブロッキング・アイランド（Ｎi）に基づいて、ネットワークの表示を、計算し（２０２）且つ電子メモリー（１０１８，１０２０）に蓄積する（２０３）ステップを有し、
各Ｂブロッキング・アイランドが、ノード（Ａ−Ｇ）の最大限の集合であって、凹形のリソースの少なくとも量Ｂをもつ少なくとも１つの経路が、時間ｔでのその集合のどのノードの組の間にも存在するようにリンクされるものからなる
ことにより特徴付けられている方法。
【請求項２】
前記Ｂiブロッキング・アイランド（Ｎi）をヒエラルキーに組織化するステップをさらに具備し、
それぞれのＢiブロッキング・アイランドのヒエラルキー的位置は、前記ブロッキング・アイランドを定義するのに使用される値Ｂiの選択に依存するものである
請求項１に記載の方法。
【請求項３】
ブロッキング・アイランドのヒエラルキーを定義するのに使用される前記値Ｂiは、共通のリソース要請にしたがって前もって定義されている
請求項２に記載の方法。
【請求項４】
ブロッキング・アイランドのヒエラルキーを定義するのに使用される前記値Ｂiを動的に変更するステップを、さらに具備する
請求項３に記載の方法。
【請求項５】
前記ネットワーク（１）において確立された回線の割り振り解除が、２つのＢブロッキング・アイランド（Ｎi）の間のリンク（Ｉi）での十分なリソースを、前記リンク（Ｉi）でリソースの少なくとも量Ｂが利用できるように開放するとき、少なくとも１つのヒエラルキー的レベルで、前記２つのＢブロッキング・アイランドを動的に合体するステップを、さらに具備する
請求項２乃至４の１つに記載の方法。
【請求項６】
Ｂブロッキング・アイランドの内側の２つのノードの間の少なくとも１つのリンクを使用しての新しい回線の確立が、前記Ｂブロッキング・アイランドの内側のどのノードの組の間にもリソースの少なくとも量Ｂをもつ経路を可能とすることができないほど多くのリソースを使用するとき、少なくとも１つのヒエラルキー的レベルで、前記Ｂブロッキング・アイランド（Ｎi）を動的に分割するステップを、さらに具備する
請求項２乃至５の１つに記載の方法。
【請求項７】
ディマンドの再経路付け、リンクの不存在またはリンクの取り除き、リンクの特性の変更、リンクの追加、ノードの不存在、ノードの取り除きまたはノードの追加の場合に、前記Ｂブロッキング・アイランドのヒエラルキーを更新するステップを、さらに具備する
請求項２乃至６の１つに記載の方法。
【請求項８】
前記方法は、利用できるリソースの少なくとも量ｂをもつ回線交換通信ネットワーク（１）において、少なくとも２つのノード（Ａ−Ｇ）の間に道筋を見出すために使用される方法であって、前記道筋の検索は、少なくとも２つの前記ノードを具備するＢブロッキング・アイランドに限定され、Ｂはｂよりも大きい、
請求項１乃至７の１つに記載の方法。
【請求項９】
それぞれの道筋が、ブロッキング・アイランドのヒエラルキーの構造について有する影響を分析することによって、最も適切な道筋を選択するステップを、さらに具備する
請求項８に記載の方法。
【請求項１０】
前記Ｂブロッキング・アイランドのヒエラルキーのどのレベルでそれぞれの経路が現れるか比較することによって、最も適切な道筋を選択するステップを、さらに具備する
請求項８または９に記載の方法。
【請求項１１】
経路付けアルゴリズムのディマンドのための検索スペースが、前記ディマンドの終点を収容する、最も大きな、前もって定義されるＢをもつＢブロッキング・アイランドによって要約されるサブネットワークに低減される
請求項８または９に記載の方法。
【請求項１２】
前記方法が、必要である（ジグザグ接続）よりもより重大なリンクをヒエラルキーのレベルＢiで使用する、再経路付け接続のために使用される方法である
請求項２乃至７の１つに記載の方法。
【請求項１３】
前記方法が、通信の価格を決定するのに使用される方法であり、ここで前記価格は、少なくとも部分的には、前記Ｂブロッキング・アイランドのヒエラルキーにおける通信のために確立された回線によって使用されるリンク（Ｉi）のヒエラルキー的レベルに依存する
請求項２乃至７の１つに記載の方法。
【請求項１４】
前記方法が、現存の回線交換通信ネットワークの振る舞いを分析する、もしくは新しい回線交換通信ネットワークの構築または現存する回線交換通信ネットワークの変更を企画するのに使用する方法である
請求項２乃至７の１つに記載の方法。
【請求項１５】
独立したインテリジェント・エージェントのヒエラルキーに基づく方法であって、各々のエージェントは、前記回線交換通信ネットワークにおけるノードの集合に責任を負い、より高いレベルのエージェントは、同僚（ｐｅｅｒ）のエージェントの間での紛争を仲裁するものにおいて、
各々のエージェントが、ノード（Ｎi）の動的に定義される集合（ｓｅｔ）に対して責任を負うものであって、
そのノードの集合が、凹形のリソースの少なくとも量Ｂをもつ少なくとも１つの経路が時間ｔでのその集合におけるいずれのノードの対の間にも存在するようなやり方でリンクされたノードからなり、
かつ前記ヒエラルキーにおけるエージェントのレベルは、前記ノードの集合を定義するために使用される値Ｂの選択に依存する
請求項１乃至７の１つに記載の方法。
【請求項１６】
回線交換通信ネットワーク（１）における少なくとも２つのノードの間の経路付けディマンドのために使用される方法であり、そして
前記方法が、少なくとも１つの他のノードｙと通信する必要のあるネットワーク・ノードｘによって発せられ、新しいディマンドが発生するとき、着手される下記のステップを具備し、但しその通信のためにある量Ｂのリソースが要請されるものであり：
第１に前記ノードｘが、エージェントのヒエラルキーにおいて最も低いレベルをもつ前記ノードｘに責任を負う前記エージェントに、前記新しいディマンドのための回線を確立するように依頼するステップ、
前記エージェントは、このディマンドを前記ヒエラルキーにおける次のレベルのエージェントに送り渡すステップ、
最後にレベルＢでのエージェントに達して、その時ｘおよびｙの間に経路を見出し回線を確立するステップ、
を有する請求項１５に記載の方法。
【請求項１７】
前記方法が、通信のための価格を決定するのに使用される方法であり、前記価格は、少なくとも部分的には、前記ブロッキング・アイランドのヒエラルキーにおいて、通信のために確立される回線によって使用されるリンク（Ｉi）のヒエラルキー的レベルに依存している
請求項１５に記載の方法。
【請求項１８】
同じＢブロッキング・アイランドに属するノードを決定するのに使用される前記リソースが、帯域幅である
請求項１乃至１７の１つに記載の方法。
【請求項１９】
中央のハードウェアおよびソフトウェアのマネージメント・プラットフォーム（１０）で実行される
請求項１乃至１８の１つに記載の方法。
【請求項２０】
ネットワークにおいて分配される通信および・または端子ノードによって実行される
請求項１乃至１８の１つに記載の方法。
【請求項２１】
前記回線交換通信ネットワーク（１）が、ＡＴＭネットワークである
請求項１乃至２０の１つに記載の方法。
【請求項２２】
ＡＴＭスイッチ（１０）における接続許可制御機能（ｃｏｎｎｅｃｔｉｏｎ  ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ  ｆｕｎｃｔｉｏｎ）（ＣＡＣ）のために使用される方法であって、その接続許可制御の経路付けモジュールがブロッキング・アイランドのヒエラルキーを使用する
請求項２１に記載の方法。
【請求項２３】
前記回線交換通信ネットワーク（１）が、ＳＤＨネットワークである
請求項１乃至２０の１つに記載の方法。
【請求項２４】
前記回線交換通信ネットワーク（１）が、ＲＳＶＰおよびＴＣＰ／ＩＰネットワークである
請求項１乃至２０の１つに記載の方法。
【請求項２５】
前記回線交換通信ネットワーク（１）が、ＴＤＭネットワークである
請求項１乃至２０の１つに記載の方法。
【請求項２６】
回線交換通信ネットワーク（１）において端子ノードとしてまたは通信ノードとして使用することができる装置（１０）において、Ｂブロッキング・アイランド（Ｎi）に基づくネットワークの表示を計算する手段（１０１６，１０１８，１０２０）であって、それぞれのＢブロッキング・アイランドは、少なくともリソースの量Ｂをもつ少なくとも１つの経路が、時間ｔでの前記集合におけるいずれのノードの組の間にも存在するようなやり方でリンクされる凹形のノードの最大限の集合からなるもの、および前記表示を蓄積（記憶）するための蓄積手段（記憶手段）（１０１８，１０２０）
によって特徴付けられる装置（１０）。
【請求項２７】
ヒエラルキーにおいて前記Ｂブロッキング・アイランド（Ｎi）を組織化する手段をさらに具備し、それぞれのＢiブロッキング・アイランドのヒエラルキー的位置は、前記ブロッキング・アイランドを定義するのに使用される値Ｂiの選択に依存する
請求項２６に記載の装置。
【請求項２８】
ブロッキング・アイランドのヒエラルキーを定義するのに使用される前記値Ｂｉが、共通のリソース要請にしたがって前もって定義される
請求項２７に記載の装置。
【請求項２９】
ブロッキング・アイランドのヒエラルキーを定義するのに使用される前記値Ｂiを動的に変更する手段を、さらに具備する
請求項２８に記載の装置。
【請求項３０】
前記ネットワークにおいて確立された回線の割り振り解除は、少なくともリソースの量Ｂが前記リンク（Ｉi）で利用できるように、２つのＢブロッキング・アイランドの間の前記リンク（Ｉi）での十分なリソースを開放するとき、前記２つのＢブロッキング・アイランド（Ｎi）を少なくとも１つのヒエラルキー的レベルで動的に合体する手段を、さらに具備する
請求項２６乃至２９の１つに記載の装置。
【請求項３１】
Ｂブロッキング・アイランドの内側の２つのノードの間の少なくとも１つのリンクを使用して、新しい回線の確立が余りにも多くのリソースを使用しすぎて、前記Ｂブロッキング・アイランドの内側のどのノードの組の間のリソースの少なくとも量Ｂをもつ経路が可能ではなくなるとき、前記Ｂブロッキング・アイランドを少なくとも１つのヒエラルキー的レベルで動的に分割する手段をさらに具備する
請求項２６乃至２９の１つに記載の装置。
【請求項３２】
ディマンドの再経路付け、リンクの不存在またはリンクの取り除き、リンクの特性の変更、リンクの追加、ノードの不存在、ノードの取り除きまたはノードの追加の場合において、前記Ｂブロッキング・アイランドのヒエラルキーを更新する手段をさらに具備する
請求項２６乃至３１の１つに記載の装置。
【請求項３３】
利用できるリソースの少なくとも量ｂをもつ前記回線交換ネットワーク（１）において、少なくとも２つのノード（Ａ−Ｇ）の間に道筋を見出す経路付け手段をさらに具備し、ここで前記経路付け手段は、前記道筋の検索を、少なくとも２つの前記ノードを具備するＢブロッキングアイランドに限定するために、前記蓄積手段を使用し、Ｂはｂよりも大きい、
請求項２６乃至３２の１つに記載の装置。
【請求項３４】
それぞれの道筋がブロッキング・アイランドのヒエラルキーの構造について有する影響を分析することによって最も適切な道筋を選択する手段、をさらに具備する
請求項３３に記載の装置。
【請求項３５】
Ｂブロッキング・アイランドのヒエラルキーの、どのレベルでそれぞれの道筋が現れるかを比較することにより最も適切な道筋を選択する手段、をさらに具備する
請求項３３または３４の１つに記載の装置。
【請求項３６】
経路付けアルゴリズムのディマンドのための検索スペースを、前記ディマンドの両終点が入っている、最大の所定のＢをもつＢブロッキング・アイランドによって要約されるサブネットワークへと低減する手段を、さらに具備する
請求項３３乃至３５の１つに記載の装置。
【請求項３７】
前記装置は、通信の価格を決定するのに使用される価格決定装置であり、ここで前記価格は、少なくとも部分的には、前記ブロッキング・アイランドのヒエラルキーにおける通信のために確立される回線によって使用されるリンク（Ｉi）のヒエラルキー的レベルに依存する
請求項２６乃至３２の１つに記載の装置。
【請求項３８】
前記装置が、現存する回線交換通信ネットワークの振る舞いを分析する、または新しい回線交換通信ネットワークの構築および現存する回線交換通信ネットワークの変更を企画するために使用することのできるネットワーク企画ツールである
請求項２６乃至３２の１つに記載の装置。
【請求項３９】
前記装置を前記回線交換通信ネットワーク（１）に接続する手段（１０２１）をさらに具備する
請求項２６乃至３８の１つに記載の装置。
【請求項４０】
回線交換通信ネットワーク（１）における、中央のハードウェアおよびソフトウェアのマネージメント・プラットフォームである
請求項３９に記載の装置。
【請求項４１】
分配されるマネージメントをもつ回線交換通信ネットワーク（１）における、ローカルの端子または通信ノードである
請求項３９に記載の装置。
【請求項４２】
前記分配されるマネージメントは、独立したインテリジェント・エージェントのヒエラルキーに基づいており、各々のエージェントは、前記回線交換通信ネットワークにおけるノードの動的に定義された集合に責任を負うローカルのマスター・ノードにおいて実行され、ここでより高いレベルのエージェントは、同僚のエージェントの間での紛争を仲裁し、各々のエージェントは、動的に定義されるノード（Ｎi）の集合であって、凹形のリソースの少なくとも量Ｂをもつ経路が少なくとも、時間ｔで前記集合におけるいずれのノードの組の間にも存在するようなやり方でリンクされるノードからなるものに責任を負い、前記ヒエラルキーにおける各々のエージェントのレベルは、前記ノードの集合を定義するのに使用される値Ｂの選択に依存する
請求項４１に記載の装置。
【請求項４３】
前記回線交換通信ネットワーク（１）が、ＡＴＭネットワークである
請求項２６乃至４２の１つに記載の装置。
【請求項４４】
前記回線交換通信ネットワーク（１）が、ＳＤＨネットワークである
請求項２６乃至４２の１つに記載の装置。
【請求項４５】
前記回線交換通信ネットワーク（１）が、ＲＳＶＰおよびＴＣＰ／ＩＰネットワークである
請求項２６乃至４２の１つに記載の装置。
【請求項４６】
前記回線交換通信ネットワーク（１）が、ＴＤＭネットワークである
請求項２６乃至４２の１つに記載の装置。
【請求項４７】
同じＢブロッキング・アイランドに属するノードを決定するのに使用される前記リソースが帯域幅である
請求項２６乃至４６の１つに記載の装置。
【請求項４８】
回線交換通信ネットワーク（１）の表示を蓄積する少なくともプログラム可能な装置（１０１）で、またはその助けにより実行される方法において、
Ｂブロッキング・アイランド（Ｎｉ）に基づいてネットワーク（１）の表示を電子メモリー（１０１８，１０２０）において計算しかつ蓄積するステップを有し、
それぞれのＢブロッキング・アイランドが、ノードの最大限の集合であって、凹形のリソースの少なくとも量Ｂをもつ経路が少なくとも、前記集合におけるいずれのノードの組の間にも存在するようなやり方でリンクされるものからなる
ことにより特徴付けられる方法。
【請求項４９】
前記Ｂブロッキング・アイランドをヒエラルキーにおいて組織化するステップをさらに具備し、
ここでそれぞれのＢブロッキング・アイランドのヒエラルキー的位置は、前記Ｂブロッキング・アイランドを定義するのに使用される値Ｂの選択に依存する
請求項４８に記載の方法。
【請求項５０】
前記ネットワークの要約される表示を、前記プログラム可能な装置（１０１）に接続されるディスプレイ（１０１４）上に図形的に表示するステップをさらに具備する
請求項４８または４９の１つに記載の方法。
【請求項５１】
前記ブロッキング・アイランドの間の重大なリンクを、前記ディスプレイ（１０１４）上で図形的に強調するステップをさらに具備する
請求項５０に記載の方法。
【請求項５２】
現存する回線交換通信ネットワーク（１）の振る舞いを分析し、および／または現存するネットワークの変更を企画するために使用することのできるネットワーク企画ツール（１０１）であって：
処理手段（１０１６）、
蓄積手段（１０１８，１０２０）、
表示手段（１０１４）、
前記処理手段（１０１６）に、ネットワークのトポロジーの表示から、かつディマンドの集合から、時間ｔでの前記ネットワークの状態の要約される表示を計算させるプログラム・コード手段であって、ここで前記要約される表示は、前記ネットワークのノードの少なくともいくつかを、複数のＢブロッキング・アイランド（Ｎi）へとグループ分けすることによって利用できるリソースを要約するもので、各々のＢブロッキング・アイランドは、ノードの集合であって、少なくともリソースの量Ｂをもつ少なくとも１つの経路が、時間ｔで前記集合のいずれのノードの組の間にも存在するようなやり方でリンクされるものからなっている前記プログラム・コード手段、及び
前記処理手段（１０１６）に、前記要約される表示を、前記蓄積手段（１０１８，１０２０）に蓄積させかつ前記表示手段（１０１４）上に表示させるプログラム・コード手段（１０１１）、を具備する
ネットワーク企画ツール（１０１）。
【請求項５３】
回線交換通信ネットワーク（１）において、端子ノードとしてまたは通信ノードとして使用することのできる装置（１０）であって、
Ｂブロッキング・アイランドのヒエラルキーの少なくとも一部を計算し、蓄積しかつ更新する手段で、前記Ｂブロッキング・アイランドが少なくともリソースの量Ｂをもつ少なくとも１つの経路が、時間ｔでの前記集合におけるいずれのノードの対の間にも存在するようなやり方でリンクされる凹形のノードの最大限の集合からなるもの、また前記Ｂブロッキング・アイランドのヒエラルキーにおける各Ｂiブロッキング・アイランドの位置は前記ブロッキング・アイランドを定義するために使用される値Ｂiの選択に依存するもの、によって特徴付けられる前記装置（１０）。
【請求項５４】
プログラム可能な機器（１０１）によって読み取り可能なプログラム蓄積装置（１０１１）であって、そして前記プログラム可能な機器（１０１）に請求項１乃至２５の１つの方法を実行させるように構成された
プログラム蓄積装置（１０１１）。
【請求項５５】
前記プログラム可能な機器（１０１）が請求項２６乃至４７の１つに記載の装置である
請求項５４に記載のプログラム蓄積装置（１０１１）。
【請求項５６】
請求項２６乃至４７の１つまたは５５による少なくとも１つの装置（１０）を具備する
回線交換通信ネットワーク（１）。
【請求項５７】
コンピュータによって読み取り可能なプログラム蓄積装置（１０１１）であって、前記コンピュータに請求項４８乃至５１の１つの方法を実行させるように構成された前記プログラム蓄積装置（１０１１）。
【請求項５８】
プログラム可能装置（プログラマブルデバイス）（１０）に、ブロッキング・アイランドのヒエラルキーの少なくとも一部を計算させ、蓄積させかつ更新させるように構成されたプログラム・コードを蓄積するプロセッサー読み取り可能な記録媒体（１０１１）であって、前記Ｂブロッキング・アイランドが少なくともリソースの量Ｂをもつ少なくとも１つの経路が、時間ｔでの前記集合におけるいずれのノードの組合せにも存在するようなやり方でリンクされる凹形のノードの最大限の集合からなり、また前記Ｂブロッキング・アイランドのヒエラルキーにおける各々のＢiブロッキング・アイランドの位置は前記ブロッキング・アイランドを定義するために使用される値Ｂiの選択に依存する、
プロセッサー読み取り可能な記録媒体（１０１１）。
【請求項５９】
請求項１乃至２５のうちのいずれか１つに記載の方法の各ステップを含むプログラムを蓄積したコンピュータ読み取り可能な記録媒体。
【請求項６０】
請求項４８乃至５１のうちのいずれか１つに記載の方法の各ステップを含むプログラムを蓄積したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
本発明は、ネットワークの改良されて要約された表示を用いる、回線交換通信ネットワークにおけるマネージメント（管理）方法および装置に関する。さらには、本発明は、回線交換通信ネットワークにおける経路付け方法および装置、価格付け方法および装置、ならびに企画方法および装置に関する。
通信ネットワークは、音声、音波、グラフィクス、絵画、ビデオ、テキストまたはデータであるであろう情報の交換を可能とするため、リンク（ｌｉｎｋｓ）と相互接続されるノード（ｎｏｄｅｓ）の集合を具備する。そのノードは、端子ノードと通信ノードの２つの種類に分けられる。電話機、コンピュータ、プリンタ、ファイル・サーバー（ｆｉｌｅ  ｓｅｒｖｅｒｓ）またはビデオ・モニターのような端子ノードは、ネットワークを介して送信される情報を発生するか使用するかする。スイッチやゲートウェイ（ｇａｔｅｗａｙｓ）のような通信ノードは、情報を中継するがそれを発生したり使用したりはしない。ある端子ノードＡから端子ノードＢへの通信は、１つ以上の通信リンクを介して起こる。この通信を支援する物理的な媒体は、例えば、ケーブル、導線、光ファイバーまたは無線リンクであって良い。
２つのノード間で情報を交換する必要性は、ディマンド（要求）と呼ばれる。ディマンドは、一方向あるいは双方向かのいずれかであり得、あるいは同じ量の帯域幅（ｂａｎｄｗｉｄｔｈ）が双方向において送信されることを要請（ｒｅｑｕｉｒｅ）しない。しかしながら、リンクは双方向的である。ノード間で情報が転送されることのできる前に接続を確立することを要請するネットワークは、回線交換通信ネットワークと呼ばれる。これらのネットワークにおいて、回線は、ディマンド（要求）に応じてのみ確立され、かつもはや必要とされないときには割り振り解除（割り当て解除）（ｄｅａｌｌｏｃａｔｅ）される。回線交換通信ネットワークは、例えば、非同期転送モード（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）（ＡＴＭ）、時分割マルチプレクシング（Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）（ＴＤＭ）、供給源予約プロトコール（Ｒｅｓｏｕｒｃｅ  Ｒｅｓｅｒｖａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）（ＲＳＶＰ）、送信制御プロトコール（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）（ＴＣＰ）および同期デジタル・ヒエラルキー（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｉｇｉｔａｌ  Ｈｉｅｒａｒｃｈｙ）（ＳＤＨ）のようなさまざまなプロトコールを用いることができる。共通の回線交換通信ネットワークは、ネットワークにおいて発生するリソース（供給源）およびディマンドのマネージメントを少なくともある形で必要とする。大抵の回線交換ネットワークは、中央で管理される（しかしながらＴＣＰではそうではない）。中央のハードウェアおよびソフトウェアのマネージメント・プラットフォーム（ｍａｎａｇｅｍｅｎｔ  ｐｌａｔｆｏｒｍ）は、通常「実時間（リアルタイム）」でネットワークを通しての全ての新しいディマンドを管理して経路付けする。中央のマネージメント・プラットフォームは、ネットワーク・ロード（ｎｅｔｗｏｒｋ  ｌｏａｄ）を調べ、ボトルネック（ｂｏｔｔｌｅｎｅｃｋｓ：隘路）を特定するなどする価格付けおよび分析機能のような他のタスク（ｔａｓｋｓ）を実行する。
ネットワークにおける各々のリンクは、そのリンクにおいて利用できる帯域幅のような少なくとも１つのメトリック（ｍｅｔｒｉｃ）によって特徴付けられるであろう。例えばＡＴＭのようないくつかの回線交換通信ネットワークは、サービスの質（ｑｕａｌｉｔｙ  ｏｆ  ｓｅｒｖｉｃｅ）（ＱｏＳ）要件に基づいてマネージメントを可能とする。各新しいディマンドは、呼び出しを行っているユーザーが、自分が確立したいと望む通信のために要請するリソースの量を指示するところの、サービスの質のパラメーターを収容するであろう。要請されるかもしれない典型的なリソースは、例えば帯域幅であろう；ＡＴＭネットワークにおいて呼び出しを行う者は、例えば少なくとも６４Ｋビット／秒での接続の確立を要請することができる。しかしながら、広範囲にわたっての適用を支援するためには、新しい経路付けプロトコールは、帯域幅、遅延および損失の可能性などの複数のメトリックで定義されるサービスの質のパラメーターを用いて良い。ツェン・ワン（Ｚｈｅｎｇ  Ｗａｎｇ）およびジョン・クロウクロフト（Ｊｏｎ  Ｃｒｏｗｃｒｏｆｔ）は、１９９６年９月のＩＥＥＥジャーナル・オン・セレクティッド・エアリアズ・イン・コミュニケーションズ（ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）第１４巻７号１２２８頁の「マルチメディアへの応用を支援するためのサービスの質の経路付け（Ｑｕａｌｉｔｙ−ｏｆ−Ｓｅｒｖｉｃｅ  Ｒｏｕｔｉｎｇ  ｆｏｒ  Ｓｕｐｐｏｒｔｉｎｇ  Ｍｕｌｔｉｍｅｄｉａ  Ａｐｐｌｉｃａｔｉｏｎｓ）」において、いくつかの要件を満たす道筋を見つける戦略を記述している。例えば、この方法によれば、最大のボトルネック帯域幅（最も広い道筋）をもつ道筋を、また最も広い道筋が２つ以上ある時は、伝搬遅延の最も短いものを見つけることが可能となる。
中央のプラットフォームは通常、考慮されている時点でネットワークの状態の表示をある形で蓄積する電子メモリーを具備する。この表示には通常、ネットワークのトポロジー（位相幾何学）についての情報、すなわちノードおよびこれらのノードを相互接続するリンクの一覧が含まれる。前記メモリーに蓄積される表示はまた通常、ネットワークじゅうで既に確立された回線についての、かつある場合には、ネットワークじゅうで新しい回線を確立するためのディマンドについての情報を収容する。
中央で管理されるネットワークにおいて、中央のマネージメント・プラットフォームは通常、ディマンドの経路付けに、すなわち各々の新しいディマンドのためにネットワークじゅうで経路を決定することに責任がある。経路付け手段の効率、すなわち大抵の新しいディマンドのために「良い」経路を見つけるそれの能力は、使用される経路付けアルゴリズムのみではなく、ネットワークの状態の、蓄積（記憶）される表示にも依存する。非常に大きなネットワークでは、マネージメント・プラットフォームのＲＡＭにおいて、ネットワークの完全な表示を蓄積しかつ更新すること、また実時間でそれに働きかけることは、もはや不可能となる。少なくともいくつかのサブネットワークを単一のノードに集めることによって、前記表示のサイズを低減することは可能であるかもしれない。しかしながら、もし前記表示が不完全であるなら、経路付け手段は、良い経路を見つけ出すことができないように思われる。たとえネットワークの完全な表示に働きかけることが可能であるとしても、膨大な量のノードを通る回線を見つけ出すために、経路付け（ルーティング）手段によって必要とされる時間は、もはや容認できないものとなるかもしれない。換言すれば、ネットワークのサイズと新しいディマンドのための経路を見つけ出すのに許される時間との間には、トレードオフ（条件の取捨）がある。
大抵の通信ネットワークにおいて、通信の価格は、接続期間のみに（インターネットの場合）、接続および帯域幅に（あるインターネットのプロバイダーの場合）、または期間、その日の時間および距離（電話ネットワークの場合）に基づいて計算される。動的な価格付けポリシーを持つネットワークはまた、この場合は、リンクを通しての接続の価格がそのリンクで利用できるリソースに依存するということで、実験されてもいる。中央で管理されるネットワークにおいては、新しい通信のための価格は、中央のマネージメント・プラットフォームによって、時間ｔでのネットワークの状態についてそれが分かっていることに基づいて計算されるであろう。したがって動的価格手順（ダイナミック・プライス・プロシーデュア）はまた、中央のプラットフォームがネットワークの状態またはトポロジーの表示を少なくとも何らかの形で蓄積することを要請する。
ネットワーク企画ツール（ｐｌａｎｎｉｎｇ  ｔｏｏｌ）が、現存するネットワークの振る舞いを分析するのに、および／または新しいネットワークの構築または現存するネットワークの変更（拡張）を企画するのに使用される。それらは、企画するディマンドを発生させるのにネットワーク・シュミレーター（ｓｉｍｕｌａｔｏｒ）を使用し、またはそれらを例えば測定ツールから持ち込んでも良い。それらは独立型装置として用いることができ、または現存するネットワークに接続されても良い。ネットワーク企画ツールは通常、ネットワークのトポロジーの表示を蓄積するためにメモリーを用いる。そしてオペレーターは、ネットワークへの改良を企画するためにネットワークの振る舞いを観察することができる。しかしながら、非常に大きいネットワークの完全な表示に働きかけるには、適当な時間で実行されるように巨大なメモリーと非常に高価なコンピュータが必要である。したがって、ネットワーク企画ツールは時々、単一のノードに集められるサブネットワークを有するネットワークの要約された表示を使用する。しかしながら、この要約された表示は、集められたサブネットワークの内側にボトルネックを隠してしまうかもしれない。さらには、経験を積んだオペレーターでさえ、ネットワークにおいて、とりわけ何千もまたは何百万もありさえするノードを収容するネットワークにおいて、発生するかもしれない問題を指摘するのは困難であろう。
したがって、経路付け手段、価格手順決定手段およびネットワーク企画ツールは全て、ネットワークの状態の動的な表示を何らかの形で蓄積しおよび／またはそれらに働きかける必要がある。ネットワークのサイズが大きくなるとき、その表示のサイズもそれにしたがって大きくなり、そしてそのような大きな表示に働きかけることは困難となる。
本発明が解決したいと望む１つの技術上の問題は、ネットワークの状態の改良された表示を使用するところの、中央で管理される回線交換通信ネットワークにおいて、ディマンドおよびリソースのマネージメントの改良された方法を見出すことである。とりわけ、本発明が解決することを目標とする１つの技術上の問題は、改良された経路付け方法および改良された価格付け方法を見出すことである。本発明が解決することを目標とするもう１つの他の技術上の問題は、中央で管理される回線交換通信における中央のマネージメント・プラットフォームでおよび／または独立型の汎用コンピュータ（ｓｔａｎｄ−ａｌｏｎｅ  ｇｅｎｅｒａｌ  ｐｕｒｐｏｓｅ  ｃｏｍｐｕｔｅｒ）で、分配されるかまたは実行されることのできる改良されたネットワーク企画方法を見出すことであり、そこでは、その改良されたネットワーク企画方法は、ネットワークの状態の改良された表示を使用する。
大きなネットワークを管理するために、ネットワーク・マネージメント機能がローカル（局地、局所）のエージェント（ａｇｅｎｔｓ：仲介者）に分配され、各々のローカルのエージェントは、ネットワークにおけるノードの限られた部分集合に責任を負うものとすることが提案されている。新しい接続の確立を要請するノードは、そのローカルのマスター（ｍａｓｔｅｒ）に、経路を見出しかつ接続の価格を決定するよう依頼することができる。エージェントは、全体のネットワークを通して確実に経路付けされるよう協力し合う。エージェントの構造はヒエラルキー的である：より高いレベルのエージェントは、さもなくば解決することのできない同僚のエージェントの紛争を仲裁する。ローカルのエージェントは、例えば要求されたサービスの質およびネットワークの状態について知っていることに基づいて、ネットワークじゅうで道筋を見出すよう試みるであろう；もしそれが不存在となれば、または目的地のノードがそれが支配する部分集合に属さないならば、ローカルのエージェントは、より高いレベルのエージェントに問題を解決するよう依頼するであろう。新しい接続のこの確立は、そのローカルのマスターに経路を見出してかつ接続の価格を決定するよう依頼するであろう。エージェントは、ネットワーク全体を通して確実に経路付けするよう協力し合う。エージェントの構造はヒエラルキー的である：より高いレベルのエージェントは、さもなくば解決することができない同僚のエージェントの間での紛争を仲裁する。ローカルのエージェントは、例えば要求されるサービスの質およびネットワーク状態についてのそれの持つ知識に基づいて、ネットワークじゅうから道筋を見出そうと試みるであろう；もしそれが見つからないか、または目的地（ｄｅｓｔｉｎａｔｉｏｎ）のノードがそれが支配する部分集合に属さないならば、ローカルのエージェントは、より高いレベルのエージェントに問題を解決するよう依頼するであろう。この分配されるマネージメントでは、少なくともいくつかの信号送信プロトコールがローカルのエージェントの間で確立されることが必要である。例えば、リンクのメトリックについてのおよび特定のノードの状態についての情報は、ローカルのエージェントの間で共有されなければならない。
そのような分配されるマネージメントは、シスコ・システムズ，インコーポレイテッド（Ｃｉｓｃｏ  Ｓｙｓｔｅｍｓ，Ｉｎｃ，）のアンソニー・アレス（Ａｎｔｈｏｎｙ  Ａｌｌｅｓ）によって、１９９５年５月に「ＡＴＭインターネットワーキング（Ｉｎｔｅｒｎｅｔｗｏｒｋｉｎｇ）」において記述されている。ＡＴＭネットワークにおけるディマンドおよびリソースのマネージメントについての一般的な情報は、１９９４年にマクグローヒル・シリーズ・オン・コンピュータ・コミュニケーションズ（ＭｃＧｒａｗ−Ｈｉｌｌ  Ｓｅｒｉｅｓ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）の「ＡＴＭ−理論と応用（Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ）」ＩＳＢＮ０−０７−０６０３６２−６において、デービッドＥ．マクダイサン（Ｄａｖｉｄ  Ｅ．ＭｃＤｙｓａｎ）およびダレンＬ．スポーン（Ｄａｒｒｅｎ  Ｌ．Ｓｐｏｈｎ）によって与えられている。ネットワーク・マネージメントのエリクソン・アプライド・ラボラトリー（Ｅｒｉｃｓｓｏｎ  Ａｐｐｌｉｅｄ  Ｌａｂｏｒａｔｏｒｙ  ｉｎ  Ｎｅｔｗｏｒｋ  Ｍａｎａｇｅｍｅｎｔ）のファーガル・ソマーズ（Ｆｅｒｇａｌ  Ｓｏｍｅｒｓ）は、「ハイブリッド：分配されるＡＴＭネットワーク・マネージメントのためのインテリジェント・エージェント（ＨＹＢＲＩＤ：Ｉｎｔｅｌｌｉｇｅｎｔ  Ａｇｅｎｔｓ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  ＡＴＭ  Ｎｅｔｗｏｒｋ  Ｍａｎａｇｅｍｅｎｔ）」において、分配されるエージェントのヒエラルキーによって管理されるＡＴＭネットワークについて記述している。各々のエージェントは、任意にかつ静的に定義されたサブネットワークにおいて、多くの場合ある種の行政範囲において、リソースおよびディマンドを管理する。例えば、大学は次のように管理することができるであろう：各研究室で１人のエージェントが責任者となり、一方他の各々のエージェントはそれぞれ学部を監督し、そしてある１人だけがその大学を支配する。
分配されるマネージメントをもつ非常に大きなネットワークにおける全てのローカルのエージェントが、完全なネットワークの状態の完全な表示を蓄積することは不可能であろう。この理由のために、各々のローカルのエージェントにおいてのおよびローカルのエージェント間で送信される信号送信メッセージにおいてのネットワークの状態の表示は、時には集められたノードの集合を単一のノードで置き換えることにより要約される。
したがって、本発明が解決しようと望む１つの技術上の問題は、ネットワークの状態の改良された表示を使用する、回線交換通信ネットワークにおいて、ディマンドおよびリソースのマネージメントの改良された分配され方を見つけ出すことである。
本発明が解決しようと望むもう１つの他の問題は、回線交換通信ネットワークを管理するために分配されるエージェントの改良されたヒエラルキーを見つけ出すことである。
本発明は、一般には、回線交換通信ネットワークにおけるディマンドおよびリソースのマネージメントの改良された方法を提供することを求めるものである。本発明はまた、中央のまたは分配されるマネージメントをもつ回線交換通信ネットワークにおいて、改良された経路付け方法、改良された価格付け方法および改良されたネットワーク企画方法を提供することを求めるものである。さらに本発明は、ＡＴＭネットワークのような回線交換通信ネットワークにおいて、（端子または通信）ノードとして使用することのできる改良された装置を提供することを求めるものである。本発明はまた、ハードウェア構成部品、適当なソフトウェアによってプログラムされたコンピュータであるとしても、またはそれら２つの何らかの組み合わせによるかまたはその他のやり方であるにしても、それぞれ記述される方法のステップを実行するための機器部品を含めて、開示される方法を実行するための機器にも向けられている。
本発明のさまざまな観点によれば、これらの改良は、独立請求項の特徴部分の特徴から分かる。
当業者が認めるであろうように、これらの改良は結果として、回線交換通信ネットワークの技術的に改良された機能性、とりわけ新しいディマンドのより早くより良い経路付け、リソースの改良された使用およびより良い価格付けになる。
さらに詳しく言うと、これらの改良は、ネットワークで利用できるリソースを要約するための新しい方法から生じる。その方法は、前記ネットワークの端子ノードおよび通信ノードの少なくともいくつかを、複数のＢブロッキング・アイランド（Ｂ−ｂｌｏｃｋｉｎｇ  ｉｓｌａｎｄｓ）にグループ分けすることにあり、各々のＢブロッキング・アイランドは、１つの凹形のリソース（ｃｏｎｃａｖｅ  ｒｅｓｏｕｒｃｅ）の少なくとも量Ｂをもつ経路が、時間ｔにおける集合の中でどの一組のノード間にも少なくとも存在するようなやり方でリンクされるノードの最大限の集合からなる。
本発明を、図面を参照して実例でもってより詳細に説明する。それらにおいて：
図１は、簡単なＡＴＭネットワークの例である。
図２は、時間ｔでの図１のネットワークにおける全てのディマンドを要約するディマンド・グラフである。
図３ａは、考慮される時点で各々のリンクで利用できる帯域幅、および破線で描かれる楕円で示される１２８Ｋブロッキング・アイランドを示す図１のネットワークの表示である。
図３ｂは、図３ａのネットワークの要約される表示であり、各々の１２８Ｋブロッキング・アイランドにおけるノードの集合は、単一のノードに集められている。
図４ａ−４ｄは、通信ネットワークのヒエラルキー的表示の４つのレベルである。
図５は、本発明の方法を実行するための装置によって実施されるステップを例示するフローチャートである。
図６は、本発明による、中央に集められたマネージメント方法を実行するのに使用される装置の遠近図である。
図７は、図６の装置のハードウェアのブロック図である。
図１は、スイッチまたはゲートウェイのような通信ノード１０、およびコンピューター２０１、電話機２０２、ファイル・サーバー２０３、ビデオカメラ２０４などの端子ノードからなる通信ネットワークを示す。通信ノードおよび端子ノードは、通信リンクＩｉで相互接続される。リンクＩｉは、双方向の通信メディアに対応する。各々のリンクＩｉは、典型的にはビット／秒で測定されるその帯域幅Ｂ、ならびに遅延（［ｍｓ］）、遅延ジッター（ｄｅｌａｙ  ｊｉｔｔｅｒ）およびセル損失速度（ｃｅｌｌ  ｌｏｓｓ  ｒａｔｅ）のようなその他の特性によって特徴付けられれる。リンク帯域幅は、図１で各々のリンク近くの括弧内に与えられている。
簡略化の目的で、以下のバックボーン・ネットワーク（ｂａｃｋｂｏｎｅ  ｎｅｔｗｏｒｋ）１（通信ノードとそれらの間のリンクのみからなる）のみを考察し、また他の形状からおよびネットワークの要約された表示からアクセス・ネットワーク（端子ノードおよびそれらの通信ノードヘのリンクからなる）は除外する。しかしながら、本発明の方法は、いかなる困難性もなく、端子ノード、通信ノードおよびそれらの間のリンクを含んで、完全なネットワークの表示にまで拡張されることができる。そのような完全な表示は、とりわけ、端子ノードが複数のネットワーク（例えば、会社のローカルネットワークおよびインターネットに同時に接続されるコンピュータ）に接続されかつ、それ故に（異なるネットワーク層に於いてではあるが）通信ノードとしてもまた働くことができるならば有用であるであろう。
以下では、よりはっきりとＡＴＭネットワークの特別な場合に関して記述がなされる。しかしながら、本発明は、いかなる種類の回線交換通信ネットワークにも応用できる。
図６は、特許請求項の方法を実行するよう、特別に設計されることができるＡＴＭネットワークのいくつかの要素の透視図である。スイッチ１０は、ＡＴＭスイッチング・ボード（ｓｗｉｔｃｈｉｎｇ  ｂｏａｒｄ）１００およびそのスイッチング・ボード１００の操作を制御するためのコンピュータ１０１を含む。コンピュータ１０１はまた、図７にも示されており、キーボード１０１０、メインユニット１０１２、ＣＤ−ＲＯＭドライブ１０１３のような蓄積装置読み取り機、およびディスプレイ１０１４を含む。メインユニット１０１２は、ＣＰＵ１０１６、ＲＯＭ１０１７、ＲＡＭ１０１８、ハードディスク１０２０、およびプログラム可能な装置１０１をＡＴＭスイッチング・ボード１００にまたはＡＴＭネットワーク１に直接に、接続するよう特別に適合されているインターフェイス１０２１を具備する。コンピュータ１０１は、ＣＤ−ＲＯＭ１０１１またはハードディスク１０２０に蓄積されるソフトウェアを実行することによって、特許請求の範囲のようなやり方でＡＴＭスイッチング・ボード１００を制御するよう特別に設計されている。ＡＴＭスイッチ１０は、リンクＩｉによって、例えば低速の銅線１２０によって、サテライト１３０またはその他のワイヤレス送信システムによって、光ファイバー（図示されていない）によってまたは仮想のリンク（図示されていない）によって、他のスイッチおよび／またはＡＴＭネットワークにおける他のコンピュータまたは端子ノードに接続される。
ネットワーク１は、ノード間での通信、例えば、電話通話、ビデオ会議、要求次第のビデオ（ｖｉｄｅｏ  ｏｎ  ｄｅｍａｎｄ）などのためのディマンドを満たさなければならない。ディマンドｄｋは、間で通信が起こることが要請されるノードｘｋおよびｙｋ（ディマンドの終点）によって、かつサービスの質の要請（ＱｏＳ）を記述するパラメーターＢｋによって定義されることができる。以下の部分の記述においては、Ｂｋが、要請される帯域幅の量のみに依存する場合を考える。パラメーターＢｋは、一定のビット速度接続（ｃｏｎｓｔａｎｔ  ｂｉｔ  ｒａｔｅ  ｃｏｎｎｅｃｔｉｏｎｓ）（ＣＢＲ）のためには定数であり、または可変ビット速度接続（ｖａｒｉａｂｌｅ  ｂｉｔ  ｒａｔｅ  ｃｏｎｎｅｃｔｉｏｎｓ）（ＶＢＲ）または一時的（Ｔｅｍｐｏｒａｌ）ＣＢＲ（ＴＣＢＲ）のためには時間の関数であり得る。さしあたってＢｋが定数である場合のみを考慮する。
図２は、任意の時間ｔでネットワーク１において生じる全てのディマンドｄｋを示す。例えば図２は、最小の６４ｋビット／秒の帯域幅でノードＦとＧとの間の接続を確立するためにディマンドｄ６があるということを示す。
ディマンドｄｋを満たすためには、そのディマンドの終点ｘｋおよびｙｋの間に回線が割り当てられなければならない。この回線は、そのディマンドのサービスの質の要請を満たすような経路を取らなければならない。経路は、ネットワークを横切る簡単な道筋であり、またしたがってリンクの集合である。経路計算は、中央に集められたまたは分配される経路決め手段によって実行される経路決めアルゴリズムにより確実なものとされる。経路決めの問題は１つで、しかも、要請されたサービスの質（帯域幅）を満たす各々のディマンドのために１つだけの、経路を見出すことであり、またリソースの使用を最小限化することを含む。そして経路決めアルゴリズムは、この経路の各リンクおよび各ノードがそのディマンドを支援するのに十分な帯域幅をもつように、ネットワークにおいて発生する各ディマンドのために経路を見出さなければならない。
ネットワークを通じての接続を経路決めするのにはさまざまなアプローチが可能である。ホップ・バイ・ホップ経路付け（ｈｏｐ−ｂｙ−ｈｏｐ  ｒｏｕｔｉｎｇ）は、インターネット・プロトコールのような最新のネットワーク層プロトコールによって使用されており、そこではどの任意のノードででも最終の目的地により近い別のノードのみにパケット（ｐａｃｋｅｔ）が経路付けられる。ソース経路付け（ｓｏｕｒｃｅ  ｒｏｕｔｉｎｇ）において、道筋における最初のノードが、最後の目的地への全体の経路を決定する。Ｐ−ＮＮＩプロトコールは、経路付けに責任を負う、エージェントのヒエラルキーを使用する。しかしながら、本発明のネットワーク表示方法は、経路付け方法から独立しており、大抵の経路付けアルゴリズムに利益を提供することができる。
一旦経路が見出されると、この経路に沿って必要なリソースが指定される。このプロセスが回線の確立と呼ばれる。ネットワーク技術により、要請される帯域幅が正確に指定されなければならないか、または（例えば、時分割マルチプレクシング・ネットワークにおいては）少なくとも要請されるだけの数のリソースが割り当てられなければならない。
一般に通信ネットワークにおいて、ディマンドが全て同時に発生することはない。さらには、ディマンドの到着時間は通常前もって知らされない。したがってディマンドは、それらが到着するにつれ経路付けされなければならない。最初のディマンドのために経路を割り当てることは、後に続くディマンドの経路付けを行うのに影響がある、というのは、前者はいくつかのリソースを使い切ってしまい、それ故にそれらは、後者にはもう利用できないものであるからである。そして最初に確立される回線は、追加のディマンドの経路付けを不可能なものにしてしまうかもしれない。将来入ってくるディマンドの数および要請は、一般には知られておらず、そしてそれ故、確実に全てのディマンドが経路付けされ得るようにするために割り当てを最適化する方法はない。ディマンドの再経路付けおよびロード（ｌｏａｄ）のバランス取りは、そのように考慮されなければならない。
本発明の、ネットワーク・マネージメント方法は、Ｂブロッキング・アイランド（Ｂ−ｂｌｏｃｋｉｎｇ  ｉｓｌａｎｄｓ）と呼ばれる動的に定義される部分集合におけるネットワークのノードを集めて一団にする（ｃｌｕｓｔｅｒｉｎｇ）ステップを具備する。このグループ化は、例えば、ＲＡＭ１０１８におけるネットワークの表示において、またはネットワークの通信ノード１０のハードディスク１０２０でなされ得る。例えば、蓄積手段１０１８，１０２０は、ネットワークの各々のノードのために、それがどのＢブロッキング・アイランドに属するかを指示するパラメーターを蓄積することができる。電子メモリーにおいて部分集合におけるノードの集合を組織化する他の方法は、プログラミング技術の当業者が容易に想定することができる。後に記述されるさまざまな実施例において、各ブロッキング・アイランドは、分配されるマネージメントをもつネットワークにおいて１つの分配されるエージェントに割り当てられるネットワークにおけるノードの部分集合に対応する。ノードをグループ化するこの方法は、理解されるとおり、回線交換通信ネットワークにおいて、ディマンドの経路付け、価格付け、分析およびさまざまなその他のマネージメント・タスク（ｔａｓｋｓ）を簡略化し、改良するために使用される。
本発明によると、ネットワークにおけるノードは、Ｂブロッキング・アイランドと呼ばれるノードの集合に集めて一団とされ、利用できる凹形のリソースの少なくとも量Ｂをもつ少なくとも１つの経路が、時間ｔでその集合のいずれのノードの組の間にも存在するようなやり方でリンクされる。Ｂブロッキング・アイランドはノードについては最大限である、すなわち、どのブロッキング・アイランドの外側にも、凹形のリソースの量Ｂをもつ前記Ｂブロッキング・アイランドから到達されることのできるノードは存在しない。
図３ａは、図１のネットワークの各々のノードのための、時間ｔでの１２８Ｋブロッキング・アイランドを示す。図３ａでの各リンク近くの括弧の中の数字は、時間ｔでそのリンクにて利用できる帯域幅を与える。例えば、ノードＡとＢとの間のリンクＩ１では、２７３Ｋビット／秒が利用できる。各ブロッキング・アイランドＮ１，Ｎ２，Ｎ３が破線で描かれた楕円で示される。少なくとも１２８Ｋの利用できる帯域幅をもつ各１２８Ｋブロッキング・アイランドの内側の各ノードの間に、時間ｔで少なくとも１つの利用できる経路がある。しかしながら、Ｂブロッキング・アイランドの内側には、Ｂより少ない利用できるリソースをもつリンクＩｉがあるであろう。そのような場合、それは単にＩｉの終点間にＢの利用できるリソースをもつ別の経路があることを意味する。実際、図３ａにおいて、ノードＡとＧとの間のリンクＩ９は、同じ１２８Ｋブロッキング・アイランドＮ１において双方の終点を有するが、１２８Ｋビット／秒より少ないものしか利用できない。しかしながら、１３３Ｋビット／秒が利用できるＡからＢを経てＧへの経路がある。
Ｂブロッキング・アイランドの定義から直ちに、１つの、そしてネットワークにおける各ノードｘについて１つだけの、Ｂブロッキング・アイランドがあるということが理解できる（ある場合には、このＢブロッキング・アイランドはノードｘのみをもつ）。さらには、２つの終点ｘおよびｙが同じＢブロッキング・アイランドの中にあるならば、そしてありさえすれば、割り当てられないディマンドのＢリソース要請を満たす１つの経路が２つのノードｘおよびｙの間にあるということを示すことが可能である。Ｂの利用できるリソースをもつｘとｙとの間のいかなる経路のリンクも、全てその終端ｘおよびｙのＢブロッキング・アイランドの中にある。
ブロッキング・アイランドのこれらの有利な特性が、回線交換通信ネットワークにおいてさまざまなマネージメント・タスクを簡略化し改良するためにどのように用いられるかが以下で分かるであろう。
図３ｂは、時間ｔでの図１の（バックボーン）ネットワークの概要表示を示し、そこでは、各々の１２８Ｋブロッキング・アイランドが単一のノードに集められて一団となっている。例えば、ブロッキング・アイランドＮｌに全て属するノードＡ，ＢおよびＧは、図３ｂの要約された表示において単一のノードＮ１により置き換えられる。図３ｂの表示におけるノードは、ＢリンクＬ１，Ｌ２，Ｌ３によってリンクされている。ある回線交換通信ネットワークにおいて、各々の通信は１つの経路だけを取るので、２つのＢブロッキング・アイランド間でＢリンクの利用可能帯域幅は、図３ａの表示におけるこれらのＢブロッキング・アイランド間の全てのリンクの利用可能な帯域幅の最大のものである。例えば、１２８Ｋブロッキング・アイランドＮ１およびＮ３の間のＢリンクＬ３の利用可能帯域幅は、５６Ｋビット／秒で、図３ａにおいてブロッキング・アイランドＮ１およびＮ３の間のリンクＩ６，Ｉ８で最大利用可能帯域幅である。
図３ｂにおいて使用されるネットワークの表示の要約は、ノードを集めて一団とすることに限られない：同じＢブロッキング・アイランドにおいて双方の終点を有するネットワーク・リンクは示されておらず、またＢブロッキング・アイランドの間で唯一（重大な）Ｂリンクのみが表示されている。この表示は、このように非常に簡略化されていて、図３ａに用いられる完全なグラフの表示に比べてメモリーのほんの小さなスペースしか、または送信するためのほんの少しの時間しか費やさない。さらに図３ａの表示は、ノードの間でＢリソースを要請するディマンドが割り当てられることのできる全ての組をそれが特定するので、直ちに非常に有用な情報を与える：同じＢブロッキング・アイランドの中にあるどんなノードの組でも。反対に、もし２つのネットワーク・ノードが同じＢブロッキング・アイランドの中にないならば、Ｂの利用できるリソースを有する経路はそれらの間にはない。
しかしながら、多くの場合において、中央のネットワーク・マネージメント・プラットフォームは、なおもさまざまなタスクのためにネットワークの完全な表示を蓄積する必要がある。この完全な表示は、大抵の操作のためには、ハードディスクのような遅くて費用のかからないメモリーに蓄積することができ、一方マネージメント・プラットフォームは、ＲＡＭにロードされるネットワークの要約された表示のみを用いて大抵のタスクを実行する。この場合、本発明の方法は、実行時間に対して、（全ての）メモリー・スペースを交換することを可能とする。
ネットワークの任意のノードｘのためのＢブロッキング・アイランドＮは、Ｂブロッキング検索（Ｂ−ｂｌｏｃｋｉｎｇ  ｉｓｌａｎｄ  ｓｅａｒｃｈ）ＢＩＳと呼ばれる簡単でどん欲なアルゴリズムで得ることができる。最初のノードの集合Ｎ＝｛ｘ｝で開始して、少なくともＢの利用できるリソースを有するリンクによって到達することのできるＮに全てのノードを繰り返し加える。さらなるノードを加えることができなくなったとき、Ｎは求められるＢブロッキング・アイランドである。
完全なネットワークのＢブロッキング・アイランドの表示は、各々のノードが１つのＢブロッキング・アイランドに属するまで、全てのＢブロッキング・アイランドを最初に計算することによって構築されることができる。そして、Ｂブロッキング・アイランド間のＢリンクが、２つの別個のＢブロッキング・アイランドを接合する全てのリンクにわたって、反復によって得られる：リンクＩの終端のＢブロッキング・アイランドの間に既にＢリンクＬがあるならば、最大の利用できる帯域幅は、Ｉの上で利用できる帯域幅がＬのために利用できる最大の帯域幅よりも大きいならば、再計算される。そうではなくて、Ｂリンクが２つのＢブロッキング・アイランドの間に存在しないならば、新しいＢリンクが作り出され、そしてその利用できる最大の帯域幅はＩの上で利用できる帯域幅である。
前記のことから、もし２つのポイントｘおよびｙが、同じＢブロッキング・アイランドの中にあるならば、ｘとｙとの間にＢの利用できるリソースをもつ少なくとも１つの経路があることが分かる。それからの推論（ｃｏｒｏｌｌａｒｙ）は、１つの、そして唯１つの終端ｘがＢブロッキング・アイランドの中にあるときは、ｘとｙとの間のＢリソースを要請するディマンドを満たすことはできない：ｘとｙとの間にＢの利用できるリソースをもつ経路が無く、そうでなければｘとｙとは同じＢブロッキング・アイランドの中にあるだろうということになろう。割り当てられないディマンドｄのために１つの、かつ１つだけの終端ｘを収容するＢブロッキング・アイランドを一次（ｐｒｉｍａｒｙ）Ｂブロッキング・アイランドと呼ぶ。一次ブロッキング・アイランドは、例えばネットワーク企画ツールにおいての割り当ての不存在を説明するのに非常に有用であるということが後で分かるであろう。ディマンドｄのための一次ブロッキング・アイランドは正しい推論（ａｒｇｕｍｅｎｔｓ）をもつ、すなわちネットワーク・グラフ、確立された回線、ｄの帯域幅要請およびｄの終端の１つをもつＢブロッキング・アイランド検索アルゴリズムを実行することにより容易に見出すことができる。
図３の例のようなＢブロッキング・アイランドの表示は、任意のＢについて、ＢリンクＬ１，Ｌ２，Ｌ３のみを提示する。これらのＢリンクは、Ｂまたはそれ以上の帯域幅を要請するディマンドを支援することができない。しかしながら、異なるＢについての、例えば典型的な可能な帯域幅要請についてのボトルネックを知ることは有用であろう。可能ではあるが費用のかかる解決法は、各々の要請Ｂについて別々のブロッキング・アイランド表示を計算して蓄積することである。本発明の好ましい実施例によると、Ｂｉの下る順にＢｉブロッキング・アイランドの繰り返し分解（ｒｅｃｕｒｓｉｖｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）：Ｂｉ＞Ｂ２＞．．＞Ｂｂ＝０が構築される。この方法が図４において、帯域幅要請Ｂｉ＝｛「最大限のスピード」６４Ｋ、１９．２Ｋ、ＯＫ｝に関して説明されている。図４ａは、完全な回線交換通信ネットワーク１の表示を示す。各々のリンク近くの括弧の中の数字は、考慮される時間ｔでの利用できる帯域幅を示す。図４ｂは、ヒエラルキーのＢｉブロッキング・アイランド表示の次の（より高い）レベルを示す：少なくとも量Ｂｉ＝６４Ｋビット／秒をもつ少なくとも１つの経路が時間ｔでの集合におけるどのノードの組の間にも存在するようなやり方でリンクされるネットワークの全てのノードが、６４Ｋブロッキング・アイランドＮ１乃至Ｎ５に集められて一団とされている。図４ｃは、図４ｂの６４Ｋ表示から直接計算される表示を示す：６４Ｋブロッキング・アイランドは、それら自体１９．２Ｋブロッキング・アイランドに集められて一団とされる。例えば、図４ｂの表示における６４Ｋブロッキング・アイランドＮ１およびＮ５は、３２Ｋの利用できる帯域幅をもつリンクによって接合される：図４Ｃの１９．２Ｋ表示において、それ故それらは、１つの１９．２Ｋブロッキング・アイランドＮ６に集められて一団とされる。図４ｄは、ネットワークのゼロＫ表示を示す：このネットワークにおける全てのノードは接続されているので、少なくともゼロＫの利用できる帯域幅をもつネットワークの各々のノードの間に少なくとも１つの経路がある。したがって、この最も高いレベルの表示は、ネットワーク全体を集めて１つのノードＮ９へ一団とする。各々のレベルのブロッキング・アイランドのヒエラルキーは、ネットワークのノードから第１のレベルのヒエラルキーを構築するのに使用される同じアルゴリズムで、最も低いレベルから計算される。
大抵のネットワークにおいて、所定の帯域幅要請の限られた量のみが、例えば電話通話のためには９．６Ｋビット／秒が、使用される。ブロッキング・アイランドのヒエラルキーは、好ましくは、これらの最も共通する所定の帯域幅要請、例えばＢｌ＝１２８Ｋ、Ｂ２＝６４Ｋ、Ｂ３＝２８．８Ｋ、Ｂ４＝１４．４Ｋ、Ｂ５＝９．６Ｋ、Ｂ６＝２．４ＫおよびＢ７＝０Ｋで構築される。Ｂｉ値の集合および／またはブロッキング・アイランドのヒエラルキーにおけるレベルの数はまた、新しい帯域幅要請にしたがって動的に変化し得るものである。
図５は、本発明の経路付け方法を実行する中央のマネージメント・プラットフォームによって実行されるメインステップを指示するフローチャートである（それは、図６に例示される装置１０によって実行されるであろう）。その方法は、ステップ２００で開始する（ネットワーク・ブート（ｂｏｏｔ）での初期化）。そして経路付け装置は、それが責任を負うネットワークの少なくとも一部のトポロジーについての情報を得（ステップ２０１）、すなわちこれらのノードを相互接続するノードおよびリンクの一覧を受け取って蓄積する。この情報は、オペレーターによってキーボード１０１０で入力され、他の接続された装置からネットワークおよびインターフェイス１０２１を介して送信され、または図形ネットワーク・エディター（ｇｒａｐｈｉｃａｌ  ｎｅｔｗｏｒｋ  ｅｄｉｔｏｒ）からまたはネットワーク発見ツール（ｎｅｔｗｏｒｋ  ｄｉｓｃｏｖｅｒｙ  ｔｏｏｌ）から入力されることができる。続いて処理ユニット１０１２は、Ｂブロッキング・アイランドの１つ以上のレベルでネットワークの要約された表示を計算し（ステップ２０２）、そしてこのブロッキング・アイランドのヒエラルキー表示をメモリーまたはハードディスクのような蓄積デバイスに蓄積する（ステップ２０３）。
続いて経路付け装置は、要請されたサービスの質Ｂｒをもつネットワーク１における２つのノードｘおよびｙを相互接続するための新しいディマンドｄを受け取る（ステップ２０４）。ステップ２０５では、経路付け装置は、ネットワークにおけるｄのために経路が存在するかどうかチェックする。このチェックは非常に容易に実行される：もし２つの終点ｘおよびｙがＢ＞＝Ｂｒで蓄積される表示のレベルＢで同じＢブロッキング・アイランドの中にあるならば、そしてありさえすれば、経路は存在する。例えば、図４の例において、経路付け装置は、これらのノードは双方とも、ネットワークのＢ＝６４Ｋ表示に蓄積される同じ６４Ｋブロッキング・アイランドＮ１に属するので、要請される帯域幅Ｂｒ＝６４Ｋビット／秒をもつ経路は、終点ＡおよびＣの間に存在するということを直ちに判断することができる。もし経路が存在しないならば、そのディマンドは、ステップ２０６で拒絶される（本発明の方法は、これらの割り当ての不存在の簡単な説明を提供するということが後で理解されるだろう）。もし経路が存在するならば、経路付け装置は、経路を見つけるために他のＱｏＳパラメーター（例えば、遅延）をもまた考慮に入れるために、知られているどのＱｏＳ経路付けアルゴリズムを使用することもできる（ステップ２０７）。
上記の通り、帯域幅Ｂｒを要請するディマンドのために経路が存在するならば、その経路の全てのリンクは、そのディマンドの終点をＢ≧Ｂｒで収容するＢブロッキング・アイランドに属する。したがって、ステップ２０７で使用される経路付けアルゴリズムのための検索スペース（ｓｅａｒｃｈ  ｓｐａｃｅ）は、ディマンドの２つの終点が入っているＢブロッキング・アイランドで要約されるサブネットワークへと低減することができる。さらに良いことには、経路付けアルゴリズムの検索スペースは、それをさらにもっと制限するために、ブロック・アイランドのヒエラルキーにおいて最大のＢ（Ｂ≧Ｂｒ）をもつディマンドのため２つの終点が入っているＢブロッキング・アイランドに設定されなければならない。例えば、図４において、ａおよびｃの間の帯域幅Ｂｒ＝１９．２Ｋビット／秒を要請するディマンドのための検索スペースは、ａおよびｃが同じ６４Ｋブロッキング・アイランドＮ１に属するので、６４Ｋブロッキング・アイランドＮ１に（１９．２Ｋブロッキング・アイランドＮ６ではなく）限定されなければならない。この選択は２つの有益な副次的作用を有する：より多くの検索スペースが低減されるほど、利用可能な代替経路の数が少なくなり、したがって経路の選択を容易にする；それはまた、ヒエラルキーにおいてＢｉブロッキング・アイランドのレベルが低ければ低いほど（すなわちＢｉが高ければ高いほど）それが集まって一団となるリンクでより多く利用可能帯域幅が増え、良いバランス取りの効果を達成する。
低レベルのＢｉブロッキング・アイランドにおいてでさえ、２つ以上の経路が２つのノードｘおよびｙの間に存在するということが起こりうる。ステップ２０７での経路付けアルゴリズムによって見出されるこれらのものの間で「最善の」経路は、ステップ２０８の間に選択される（この選択は、経路付けを行う者（ｒｏｕｔｅｒ）が将来のディマンドを予測することはできないので、単に一つの最善の推測にすぎないことに留意のこと）。可能なもののうちで最善の経路は、長さの基準（経路においてリンクが数少ないほど、使用されるリソースはより数少ないということ）で、およびサービスの質のために要請される（遅延、遅延ジッターなどの）他の特性で選択することができる。しかしながら、蓄積手段においてブロッキング・アイランドにおいて要約されるネットワークの表示は、「最善の」経路を決定するための新しい手段を与える。表示のヒエラルキーにおいてリンクが高く現れるほど、それは帯域幅でより重大（クリティカル）なものとなる。そして２つの経路の比較は、それらのリンクのクリティカル性か、またはヒエラルキーのどのレベルで各々の経路が現れるかに基づくことができる。ステップ２０８の間に経路を比較する別のやり方は、ブロッキング・アイランドのヒエラルキー的な表示で、各々の経路が有する結果を分析することである。最善の経路は、ブロッキング・アイランドのより数の少ない分割を引き起こす経路である。２つの経路の比較はまた別のＱｏＳパラメーターに基づき得るものである：この場合、ブロッキング・アイランドのヒエラルキーは、第１のフィルターとして働く。帯域幅のためにブロッキング・アイランドのヒエラルキーを、また別のサービス特性、例えばセル損失速度（ｃｅｌｌ  ｌｏｓｓ  ｒａｔｅ）のために別のものを構築することもでき得る。そして双方が並行してフィルターを通ることができる。
「最善の」経路が選択されたとき、そのディマンドのために回線を確立することができ、すなわち要請されるリソースが選択される経路に沿ってｘとｙとの間で各々のリンクで指定される（ステップ２０９）。
ディマンドのために回線が一旦確立されると、ステップ２０３の間にメモリーに蓄積されたブロッキング・アイランドのヒエラルキーが適合される必要がある。とりわけ、経路を構成するリンクで利用できるリソースはより数少なくなければならない。この適合は、ステップ２１０の間になされる。ブロッキング・アイランドのヒエラルキーはまた、さまざまな他の機会に、特に回線の割り振りが解除（ｄｅａｌｌｏｃａｔｅ）されるときに、適合されまたは維持される必要もあることが理解される。
リンクＩでの利用できるリソースの減少は、Ｉが入っているＢブロッキング・アイランドの２つの別々のＢブロッキング・アイランドへの分割を引き起こすかもしれない。ディマンドが経路付けられる各々のリンクＩについて、装置は、追加のロードがブロッキング・アイランドを分割させるかどうか、すなわち少なくともリソースの量Ｂをもつ経路が、リソースの割り当ての後、ブロッキング・アイランドにおいてどのノードの組の間にももうこれ以上存在しないかどうかチェックする。ブロッキング・アイランドのヒエラルキーのレベルＢ１で分割が要請されるならば、各々の以前のレベルＢ２＞Ｂ１でもまた分割が、もしまだそうなっていないならば、要請されるであろう。
したがって、新しい回線の確立の後、ブロッキング・アイランドのヒエラルキーを更新するために使用される方法は以下のとおりである：
装置はまず、ディマンドが経路付けられる各々のリンクＩについて、リンクＩがブロッキング・アイランドに隠される最も低いレベルＢｉを計算する。先のレベルＢｉ−１では、要約された表示においてリンクが現れる。したがって、もし分割がなされなければならないならば、最初のものはＢｉで生じるであろう。そして装置は、分割が要請されるかどうかチェックする。新しい割り当ての後、利用できるＢｉより数少ないリソースをリンクＩが有するならば、かつそうでありさえすれば、また少なくともＢｉの利用できるリソースを有するＩの両終点の間に他の経路がないならば、そのようになる。分割がなされなければならない場合、装置はＢｉブロッキング・アイランドを２つのＢｉブロッキング・アイランドへと分割し、またその２つの新しいＢｉブロッキング・アイランドの間の新しいリンクを計算する。要請があるならば次のヒエラルキー的レベルでの分割が、行われる。
ネットワークの状態の表示が適合されなければならない他の状況がある。それは通信の必要性が発生しそして消滅し、そしてそれ故新しい回線が確立されなければならず、かつ現存するものが割り振り解除されることがある。さらには、リンクは崩壊するかもしれず、またはリンクの特性が向上し得、より多くの利用できるリソースへと導き、またはネットワークのトポロジーさえも、例えば新しいリンクを加えるときに変化し得る。リソースの利用性におけるこれらの変化は、蓄積されるブロッキング・アイランドの表示を適合することによって考慮されなければならない。本発明によると、ブロッキング・アイランドのヒエラルキーは、最初からそれを再計算することでなく、動的に適合させることができる。
接続がもはや必要とされないので、確立された回線が割り振り解除されなければならないときは、回線が経路付けられるリンクでリソースが開放される。もしＢ帯域幅要請をもつ新しいディマンドがＩの上で経路付けされることを可能とするため、２つのＢブロッキング・アイランドを結合するリンクＩで十分なリソースが開放されているなら、その２つのＢブロッキング・アイランドは合体されなければならない。したがって、回線の割り振り解除は、ブロッキング・アイランドのヒエラルキーの各々のレベルで、またディマンドが経路付けられる各々のリンクについて、２つのブロッキング・アイランドを合体するということになり得る。
確立された回線の割り振り解除の後、ブロッキング・アイランドのヒエラルキーを更新する方法は、例えば以下のようなものである：
第１のステップの間に、装置は、ディマンドが経路付けられる各々のリンクのために、２つのブロッキング・アイランドが合体されなければならないブロッキング・アイランドのヒエラルキーにおける最も低いレベルを計算する。これは、残りの確立された回線が与えられているとして、Ｉが満たすことのできる最大の帯域幅要請である。そしてリンクＩの各々の終点が入っている２つのＢブロッキング・アイランドの合体は、もしＢがゼロではないもので、かつそうでありさえすれば、またもしリンクＩが既に集められてＢブロッキング・アイランドに一団とされていないならば、行われる。そして合体は、各々の次のレベルで（もし既に達成されているのでなければ）繰り返して行われる。
通信ネットワークにおいて起こるかもしれず、かつブロッキング・アイランドのヒエラルキーに影響を及ぼす他の特別な事象には以下のことがある：
・ディマンドの再経路付け。その場合に適用する手順は、古い回線を割り振りを解除し、かつ新しいものを追加するというものである。その場合に、装置に蓄積されるブロッキング・アイランドのヒエラルキーは、ディマンドの再経路付けの問題を解決するのに役立つ；それは、検索スペースをディマンドの終点のＢブロッキング・アイランドに低減する。加えて、説明した通り、それは選び得る経路の間から選択を行うための価値ある評価基準を提供する。
・リンクの不存在またはリンクの取り除きは、回線の追加と同様に処理することができる：リンクにて利用されるリソースがない。そのリンクを使用する全ての確立された回線が、ダウンし、取り除かれなければならない。
・リンクの特性を変更するとき、２つの場合が考慮されなければならない：リンクの帯域幅リソースが増大されるか減少されるかする。前者は接続が取り除かれる場合と同じであり、また後者は新しいものが確立される場合と同じである。
・リンクを追加するとき、回線の取り除きのような手順が適用される：それは、以前に利用できるリソースを有していなかったリンクで回線が取り除かれる場合と同じである。
・ノードの不存在またはノードの取り除きはまた、そのノードが接続される全てのリンクの取り除きをも意味する。ノードはそれが属する全てのブロッキング・アイランドから取り除かれなければならず、またリンクの取り除きは、上記に指定したとおりに取り扱われる。
・ノードの追加は、それを他のノードに接続する少なくとも１つのリンクが追加されるときのみ意味がある。新しいブロッキング・アイランドが、ヒエラルキーの各々のレベルで作り出されなければならず、そして続いて上述の通りリンクの追加を行うことができる。
既に示唆されたとおり、ブロッキング・アイランドをもつネットワークの要約された表示の計算および蓄積は、ネットワークの重大なリンクを簡単に見出すことを許すものである。この特性は、接続を再経路付けするために使用することもできる。既に説明したとおり、ブロッキング・アイランドを接合するリンクは、ブロッキング・アイランドの内側のリンクよりも、特にブロッキング・アイランドのヒエラルキーにおけるより高いレベルでよりクリティカルである。したがって、ヒエラルキーのレベルＢｉで必要である（ジグザグ接続）よりもっとクリティカルなリンクを使用する２つの終点の間の接続は、再経路付けされるべきである。例えば、図３ａでは、ノードＦおよびＥを介してのＧとＢとの間の接続は、ブロッキング・アイランドＮｌとＮ３との間の２つのクリティカルなリンクＩ６およびＩ８を使用する；この接続は、クリティカルではないリンクＩ７のみを用いるように、またはクリティカルなリンクでのリソースを開放するためにクリティカルでないリンクＩ１およびＩ９を可能ならば介するように、再経路付けされるべきである。この「ジグザグ低減」再経路付け方法は、例えば中央のマネージメント・プラットフォームにおいてまたは独立型ネットワーク企画ツールにおいて用いることができる。
ヒエラルキーにおいて２つのブロッキング・アイランドを接合するリンクとしてより高くリンクが現れるほど、それはよりクリティカルなのであり、かつ使用するためにそれはより費用がかかるのである。本発明の別の観点によると、この情報は、そのリンクを用いる通信の価格を決定するために、可能ならば、期間、時間、帯域幅、距離およびサービスの質の要請のような他のパラメーターと関連して使用される。そして価格付けは、需要と供給のような法則に従う。
この方法は、価格が実際には、利用される帯域幅にではなくリンクのクリティカル性に基づくものであるという利点を有する：低度に利用される帯域幅（０でさえある）をもつリンクＩは、Ｉの終点の間の他の経路で多くの利用できるリソースをもつ経路があるならば、クリティカルなリンクではない。
本発明のさらにまた別の観点によると、ブロッキング・アイランドのヒエラルキーが、新しい通信ネットワークを設計するかまたは現存するものを分析して変更するかするために、ネットワーク企画ツールにおいて使用されおよび／または確立される。ネットワーク企画ツールは、図５に例示されるコンピュータ１０１のような汎用コンピュータによって実行され、特にはコンピュータで使用可能な媒体に蓄積されるソフトウェアを実行することによって構成され得る。フロッピーディスクに、ハードディスクにまたはＣＤ−ＲＯＭ１０１１に蓄積されるプログラム・コード・インストラクション（ｐｒｏｇｒａｍ  ｃｏｄｅ  ｉｎｓｔｒｕｃｔｉｏｎｓ）は、適当なドライバー１０１３によって読み取られる。そのインストラクションは、ＲＡＭに転送されそしてコンピュータのＣＰＵによって実行される。
プログラム・コード・インストラクションは、ＣＰＵに、ネットワークのトポロジーの記述に入るようユーザーを促させる。その記述は、キーボード１０１０を介しておよび／またはマウスおよび図形インターフェースで入ることができる。図６に例示されるさまざまな実施例において、コンピュータは回線交換通信ネットワークに接続され、また例えばネットワークのトポロジーについてそれ自体で情報を集めることができる。
続いてプログラム・コード・インストラクションは、ＣＰＵにネットワークを介して予測されるディマンドを発生させたりまたは測定させたりし、かつ使用されるべき経路付けアルゴリズムをシミュレートすることによってこれらのディマンドのための経路を見つけ出させるものとする。プログラム・コード・インストラクションは同時に、ＣＰＵに、各々の回線の確立を考慮に入れ、かつブロッキング・アイランドのヒエラルキーを使用してシミュレートされるネットワークの状態の表示を構築しかつ維持させる。ブロッキング・アイランドは、回線の確立および割り振り解除によって、合体されたり分割されたりする。この表示は、ダイナミック・メモリにおよび／またはハードディスクに蓄積され、かつコンピュータのディスプレイ１０１４で表示されるであろう。好ましくは、ソフトウェアは、ユーザーに、ネットワークのさまざまな部分でズームインおよびズームアウトを行ってヒエラルキーの異なるレベルを探索する可能性を与える。
割り当て不存在の場合には、すなわちもし利用できるリソースが新しいディマンドを経路付けするのに十分ではないならば、ブロッキング・アイランドを使用してのネットワークの表示は、何故割り当てが不存在であるかを説明するのに非常に効果的である。例えば、ディスプレイ１０１４に示される表示は、割り当てられていないディマンドのために２つの解体された一次ブロッキング・アイランド（ディマンドの各々の終端について１つ）かつこれらの２つの一次ブロッキング・アイランドの間のボトルネック・リンクを強調する（ｈｉｇｈｌｉｇｈｔ）ことができる。この情報は、使用されることが意図されている経路付けアルゴリズムおよびネットワークのトポロジーを評価するためにネットワークのオペレーターによって使用されるであろう：ボトルネックが特定されるとき、ブロッキング・アイランドのヒエラルキーは、割り当ての不存在を解決しかつ防止するためにどこに新しいリンクを加えるべきか、またはどのリンクのリソースが増加されなければならないかについて、ネットワークのマネージャーにとって価値のある情報を提供する。ブロッキング・アイランドのヒエラルキーにおいて、いくつかのレベルを考慮することは、追加すべきリンクの最小限の数およびそれらを追加すべきところ、すなわちブロッキング・アイランドの間を決定するのに役立つ。ブロッキング・アイランドをもつ要約される表示はまた、拒絶される接続の最大限のしきい値が与えられるならば、現存するネットワークが予測される追加のロードを支援するかどうかチェックするのに使用することもできる。
当業者は、ネットワーク企画ツールに応用される本発明の方法は、ネットワークの徹底的な表示から抽出されるずっと少ないメモリースペースを用いて要約される表示を可能とする、ということを認識するであろう。オペレーターは、自分が現在見ているブロッキング・アイランドのヒエラルキーのレベルを変えることによって、ネットワーク企画ツールが表示しなければならないノードの数を選択することができる。したがって、オペレーターは、ネットワークのシミュレーションの作業速度で直接働くことができる：ネットワークの状態のあらましの表示は、ブロッキング・アイランドのヒエラルキーの最も高いレベルのみを表示することによって素早く得ることができる。さらには、既に説明されたとおり、ネットワーク企画ツールによってシミュレートされる経路付けは、使用される経路付けアルゴリズムのための検索スペースをシミュレートされるディマンドの２つの終点が入っているＢブロッキング・アイランドに属する全てのノードに制限することにより、ずっと素早いものとすることができる。
本発明のさらにまた別の観点によると、ブロッキング・アイランドのヒエラルキーは、確立されなければならない接続、およびディマンドの要請および到着時間が双方とも前もって知られているときに異なるリンクで指定されなければならないリソース、を企画するためのネットワーク企画ツールにおいて確立されかつ使用される。例えば、電気通信のユーザーが、所定時間に自分が生成するディマンドについて前もって自分のネットワークのオペレーターに知らせるとき、これが事例となるであろう。そしてネットワークのオペレーターは、最小限のリソースの量を用いて、要請されるディマンドを転送するための戦略を見出すために、独立型ネットワーク企画ツールを使用する。ネットワーク企画ツールは、期待されるディマンドを発生する、使用されるべき経路付けアルゴリズムをシミュレートすることにより経路を見出しかつ回線を確立するために、実際のネットワークと同じ振る舞いをするネットワーク・シミュレータを使用する。ブロッキング・アイランドのヒエラルキーを表示することは、全ての要請されるディマンドをリソースの最小限の量で転送するために、割り当て不存在の場合の説明およびリソースをどこで増大させるべきかまたは接続を何時経路付けするべきかについての情報を提供するのに役立つ。ブロッキング・アイランドのヒエラルキーにおいていくつかの層を考慮することは、追加するべきリンクのリソースの最小限の数およびそれらをどこに追加するか：ブロッキング・アイランドの間で、を決定するのに役立つ。
前記記載は、より詳細には、中央で管理されるネットワークの場合に関する。ネットワークのサイズのためにマネージメントおよび企画がますます困難になるのを克服するために、それをエージェントに分配するのがより有益であるであろう。各々のブロッキング・アイランドは、自分の領域、ブロッキング・アイランドにおけるリソースの割り当ておよびマネージメントに責任のある、独立したエージェント、つまりブロッキング・アイランド・リーダー、によって支配される。エージェントは、好ましくは、支配されるブロッキング・アイランドの内側のノードの１つに埋め込まれるプログラム可能な装置によって実行される、ソフトウェア・モジュールまたはプログラム・コードによって実行される。各々のエージェントは、ブロッキング・アイランドのヒエラルキーの次の層でブロッキング・アイランドを支配する１つ高いレベルのエージェント（その人の「父親（ｆａｔｈｅｒ）」）によって支配される。最高位（トップ）レベルのリーダーは、ゼロＫブロッキング・アイランドの責任を負い、そして最も高い責任を負うエージェントである。
ネットワーク・ブートでのブロッキング・アイランドのヒエラルキーの構造は、分配されているものであり得る。最高位のリーダーはまず、最も小さな帯域幅要請のためのブロッキング・アイランドの表示を計算し、そして続いて、作り出される各々のブロッキング・アイランドを支配する子供（ｃｈｉｌｄ）エージェントを作り出す。これらの子供エージェントは、例えば周知の技術によって作り出され、また分配されることができる。各々の子供エージェントは続いて、次ぎに最も小さな帯域幅要請にしたがって、自分の領域を分割する。これは、最も大きな帯域幅要請のためのエージェントが確立されるまで繰り返して行われる。
回線の確立は、エージェントによって効率的に管理される。Ｂビット／秒で別のノードｙと通信する必要のあるネットワークノードｘにより発せられた、新しいディマンドが、発生したとき、ｘは自分の直接のリーダーにその接続を確立するよう依頼する。そのリーダーはその要請をその人自身のリーダーに送り渡し、それは遂にＢレベルでのリーダー（Ｂリーダー）に達する。そして後者は新しいディマンドのための回線を確立する、すなわち、要請されたサービスの質の制約を満たす経路を見出すこと、と選択された経路に沿って要請されるリソースを指定することとに責任がある。Ｂリーダーは、リソースを交渉するために同僚のエージェントと通信する必要はない、というのは、新しいディマンドを満たすどの経路もその人が責任あるリソースのみを使用するからである。しかしながらＢリーダーは、経路を見出すとき部下のエージェントと通信するであろう。回線の割り振り解除および再経路付けは同様のやり方で行われるであろう。
当業者は、分配されるエージェントによって支配される領域が現在のリソースの能力を反映するということを認識するであろう：Ｂブロッキング・アイランドを指揮するエージェントは、そのブロッキング・アイランドにおけるいずれの２つのノードの間の帯域幅をも割り当てることができる。結果として、エージェントの間での協力および交渉はほとんど要請されない。
本発明の別の観点によると、価格付けもまた分配されるエージェントのヒエラルキーによって管理される。この場合には、通信の価格は、通信を確立するために動員されるエージェントのヒエラルキー的レベルに依存するであろう。
先の記述は、より詳しくはポイント・ツー・ポイント・ディマンズ（ｐｏｉｎｔ−ｔｏ−ｐｏｉｎｔ  ｄｅｍａｎｄｓ）の特別な場合に関する。しかしながら、本発明はまた、マルチポイント・ディマンズ（ｍｕｌｔｉｐｏｉｎｔ  ｄｅｍａｎｄｓ）、すなわちテレビまたは３人以上の人のビデオ会議のような３つ以上のノードの間のデータ交換を要請するディマンド、の経路付け、価格付けおよび企画にも用いることができる。あるマルチポイント・ディマンズは、もしその終端の全てがリソースの要請される量のための同じブロッキング・アイランドの中に全てあるならば、そしてありさえすれば、経路付けすることができる。
今までのところディマンドは、時間にわたって帯域幅の一定量を要請するものとされていた。しかしながら本発明の方法はまた、他のリソースを管理しまた割り当てるのにも応用される。実際、その方法はどのような凹形のメトリックμを管理するのにも用いることができ、ここでリンク｛Ｉ１，．．．Ｉｉ，．．．，Ｉｐ｝にわたるどの道筋ｐについても、μ（ｐ）＝ｍｉｎ  μ（Ｉｉ）であるなら、リンクＩのためのメトリックμは、凹形であると云える。
さらには、本発明は、時間にわたって変化する（可変ビット速度、ＶＢＲ接続、または一時的ＣＢＲ、ＴＢＣＲ）帯域幅要請Ｂ（ｔ）をもつディマンドにもあてはまる。これは典型的には、例えばインターネット・サーフィンの時の場合である：ワールド・ワイド・ウェブ（ｗｏｒｌｄ  ｗｉｄｅ  ｗｅｂ）上のページをローディングしているとき、データが最大限のスピードで転送されなければならない；しかしながら、そのページを読んでいるとき、接続は使用されていない（ｉｄｌｅ）。そのような可変ビット速度接続は、一定のビット速度接続で近似される（に近づけられる）であろうが、ここで一定の帯域幅要請が最高のピークであって、またその帯域幅で回線を確立することができる。しかしながら、そのやり方ではたくさんのリソースが浪費される。したがって、より複雑な接続許可制御（ｃｏｎｎｅｃｔｉｏｎ  ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌｓ）（ＣＡＣｓ）という代価で可変ビット速度接続を確立する方がずっと良い。マーティン・デ・プリッカー（Ｍａｒｔｉｎ  ｄｅ  Ｐｒｙｃｋｅｒ）は、１９９５年のプリンティス・ホール（Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ）第３版の非同期転送モード：広帯域ＩＳＤＮのための解決法（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ：  Ｓｏｌｕｔｉｏｎ  ｆｏｒ  Ｂｒｏａｄｂａｎｄ  ＩＳＤＮ）の中で、ＡＴＭネットワークにおける可変ビット速度接続を確立する方法を記述している。
どんなＢｉ（ｔ）、Ｂｊ（ｔ）についても、関係Ｂｉ（ｔ）＜＝Ｂｊ（ｔ）または関係Ｂｊ（ｔ）＜＝Ｂｉ（ｔ）のいずれかがあり、但しＢｉ（ｔ）＜＝Ｂｊ（ｔ）が、もしリンクＩが、Ｂｊ（ｔ）を要請するディマンドのために十分利用されるリソースを有しているなら、ＩがＢｉ（ｔ）を要請するディマンドを支援することができると云うことを意味するならば、リソース要請Ｂｉ（ｔ）は完全にオーダーされると云える。これは、例えばネットワークにおいて発生するディマンドの各々の組についておよび各々の時間ｔについて、１つのディマンドが、他のものよりも少ないか同じだけの量のリソースを要請するときの場合である。この特別な場合においては、ブロッキング・アイランドのヒエラルキーは、一定の帯域幅のためのブロッキング・アイランドのヒエラルキーと同じ特性を有しており、また同じやり方で構築、管理、維持されることができる。
しかしながら、もし２つの帯域幅要請が、リンクで確立された回線から独立していつもは比較することができないならば、帯域幅要請は、部分的にのみオーダーされると云えよう。この場合には、ブロッキング・アイランドは、１人以上の父親をもち、かつ１つ以上の他のブロッキング・アイランドの子供であるかもしれないということを示すのは容易である。それでブロッキング・アイランドのヒエラルキーは、構築し、訪問しそして探索するのがより複雑である。実際、部分的に注文されたりソース要請のためのブロッキング・アイランドのヒエラルキーは、もはや木（ｔｒｅｅ）状ではなく格子（ｌａｔｔｉｃｅ）状である。このブロッキング・アイランドのヒエラルキーを分配するには、エージェントの間でのもっと凝った（複雑な）協力および交渉プロトコールが要請されるであろう、というのは、各々のエージェントはいく人かの父親をもつかもしれず：エージェントは、純粋にヒエラルキー的なシステムにおいて配置されていないからである。紛争解決は、対立するエージェントを監督する最も低いエージェントによって行われ；そしてその最も低いエージェントは、対立するエージェントの直接のリーダーではないこともある。
【図１】
0003856837.tif 000002
【図２】
0003856837.tif 000003
【図３ａ】
0003856837.tif 000004
【図３ｂ】
0003856837.tif 000005
【図４ａ】
0003856837.tif 000006
【図４ｂ】
0003856837.tif 000007
【図４ｃ】
0003856837.tif 000008
【図４ｄ】
0003856837.tif 000009
【図５】
0003856837.tif 000010
【図６】
0003856837.tif 000011
【図７】
0003856837.tif 000012