(57)【特許請求の範囲】
【請求項１】
トラフィックに関するＵＢＲサービスカテゴリの仮想回路を含むコネクションを支援するＡＴＭ通信ネットワークで通信する方法において、
仮想回路に、送信に関する推定帯域幅を割り当てる工程と、
ＡＴＭ通信ネットワークに仮想回路を、その仮想回路のＵＢＲサービスカテゴリ及びその仮想回路の推定帯域幅に基づいて形成する工程であって、任意の所定のリンクについて、その仮想回路の推定帯域幅を、ＵＢＲサービスカテゴリのトラフィックを有する仮想回路で使用可能な全体の帯域幅と累積帯域幅の差と比較して、そのリンクがその仮想回路を支援出来るか否かを決定することで、その仮想回路が、ＡＴＭ通信ネットワークにあるその他の仮想回路とロード平衡されるように、ＡＴＭ通信ネットワークに仮想回路を形成する工程と、
仮想回路について、複数のリンクで構成されると共に、その仮想回路の推定帯域幅を支援出来る経路を見つける工程と、
仮想回路の推定帯域幅を支援出来る経路がない場合、その仮想回路の推定帯域幅を緩和する工程とを含むことを特徴とする方法。
【請求項２】
仮想回路を形成する工程は、その仮想回路のＵＢＲサービスカテゴリ及びその仮想回路の推定帯域幅に基づいて、その仮想回路が、ＡＴＭ通信ネットワーク上のその他の仮想回路と最短の経路の間でロード平衡されるように、ＡＴＭ通信ネットワーク上に仮想回路を形成する、請求項１に記載の方法。
【請求項３】
仮想回路を形成する工程は、その仮想回路のＵＢＲサービスカテゴリ及びその仮想回路の推定帯域幅に基づいて、その仮想回路が、ＡＴＭ通信ネットワーク上のその他の仮想回路と最短の経路の間でロード平衡されるように、ＡＴＭ通信ネットワーク上に仮想回路を形成し、ＡＴＭ通信ネットワークの全リンク中に最大割合の未使用の帯域幅が達成される、請求項２に記載の方法。
【請求項４】
仮想回路を形成する工程は、その仮想回路が、その他の仮想回路とロード平衡されるように、ＡＴＭ通信ネットワーク上に形成されて、その仮想回路の経路指定は、それぞれ異なる大きさの送信経路中にて平衡される、請求項３に記載の方法。
【請求項５】
仮想回路を形成する工程の前に、ＡＴＭ通信ネットワーク上の任意のリンクが、仮想回路を支援するために使用可能な帯域幅を有しているか否かを決定する工程がある、請求項４に記載の方法。
【請求項６】
仮想回路を形成する工程は、ＡＴＭ通信ネットワーク中の仮想回路の合計が、ＡＴＭ通信ネットワークが実際に支援出来る、ＵＢＲサービスカテゴリのトラフィックに使用可能な帯域幅の合計より大きい場合でも仮想回路を形成する、請求項５に記載の方法。
【請求項７】
仮想回路を形成する工程は、全経路が１００パーセントより大きい利用度を有しているときに、最小割合の利用度を有する経路に仮想回路を形成することを含む、請求項６に記載の方法。
【請求項８】
仮想回路を形成する工程は、全経路が１００パーセント未満の利用度を有する場合に、仮想回路が加えられるならば、全経路内に未使用の帯域幅の割合を最大化するであろう経路を見つける工程と、全リンク内に未使用の帯域幅の割合を最大化するであろう経路に仮想回路を形成する工程とを含んでいる、請求項７に記載の方法。
【請求項９】
トラフィックに関するＵＢＲサービスカテゴリの仮想回路を含む各コネクションを支援し、複数のスイッチを含むＡＴＭ通信ネットワークと、それらスイッチと接続する複数のリンクとを具えた通信システムにおいて、
複数のスイッチには、ルーティングモジュールが接続されており、
ルーティングモジュールは、送信に関する推定帯域幅を、各仮想回路に割り当てる機構を有しており、
ルーティングモジュールは、仮想回路が、ＡＴＭ通信ネットワーク上にあるその他の仮想回路とロード平衡されるように、その仮想回路のＵＢＲサービスカテゴリ及びその仮想回路の推定帯域幅に基づいて、ＡＴＭ通信ネットワーク上に仮想回路を形成するように構成されており、
ルーティングモジュールは、任意の所定のリンクについて、仮想回路の推定帯域幅と、ＵＢＲサービスカテゴリのトラフィックを有する仮想回路で使用可能な全体の帯域幅と累積帯域幅の差とを比較して、そのリンクがその仮想回路を支援出来るか否かを決定することで、ＡＴＭ通信ネットワーク上に仮想回路を形成し、
仮想回路について、複数のリンクで構成されると共に、その仮想回路の推定帯域幅を支援出来る経路を見つけ、
仮想回路の推定帯域幅を支援出来る経路がない場合、その仮想回路の推定帯域幅を緩和することを特徴とする通信システム。
【請求項１０】
ルーティングモジュールは、仮想回路のＵＢＲサービスカテゴリ及びその仮想回路の推定帯域幅に基づいて、その仮想回路がロード平衡されるようにＡＴＭ通信ネットワーク上に形成し、ＡＴＭ通信ネットワークの全リンク中に最大割合の未使用の帯域幅が達成される、請求項９に記載のシステム。
【請求項１１】
リンクは、トラフィック運搬容量に関して、それぞれ大きさが異なる経路を有する、請求項１０に記載のシステム。
【請求項１２】
ルーティングモジュールは、如何なる仮想回路も確立されることが出来るようにオーバーブッキングを許容する、請求項１１に記載のシステム。
【請求項１３】
ＡＴＭ通信ネットワーク及びルーティングモジュールはまた、ビットレートが特定されたカテゴリのトラフィックを有している仮想回路を支援する、請求項１２に記載のシステム。
【請求項１４】
マルチメディア、オーディオ、ビデオ又はデータが送信される、請求項１３に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、ＡＴＭネットワーク中のＵＢＲルーティングに関する。特に、本発明は、仮想回路の帯域幅に基づいた、ＡＴＭネットワーク中の仮想回路のロード平衡したＵＢＲルーティング（load balanced UBR routing）に関する。
【０００２】
【発明の背景】
非同期転送モード（ＡＴＭ）ネットワークは、固定ビットレート（ＣＢＲ）、可変ビットレート（ＶＢＲ）及び無規定ビットレート（ＵＢＲ）のような、様々なサービスカテゴリのトラフィックの仮想回路（ＶＣｓ）を支援するネットワークである。これらの種々のサービスカテゴリは、様々なトラフィック特性（traffic characteristics）を有しており、種々な目的のために使用される。ＡＴＭネットワークは、ＶＣｓを経路指定するためにリンク状態のルーティング（link state routing）を使用する。リンク状態のルーティングプロトコルの望ましい機能（features）の一つは、ロード平衡(Load Balancing)させることである。リンク状態のルーティングプロトコルがＡＴＭネットワーク中のＶＣｓをロード平衡させる効率は、ネットワークが激しいトラフィックのもとでどの様に混雑するかを決定する。ＶＣｓを効率的にロード平衡させるルーティングプロトコルは、ネットワークに於ける輻輳(congestion)を最小化する。
【０００３】
ＵＢＲ用のロード平衡の問題（Load Balancing issues）は、ＶＢＲ及びＣＢＲのものとは異なる。ＶＢＲ及びＣＢＲ  ＶＣｓが、ＡＴＭネットワーク中で信号表示される場合、このような各ＶＣのための帯域幅必要事項(requirement)で特定される。この必要事項の明細事項は次に、帯域幅を各ＶＣ用にネットワーク中へ確保することに使用される。ＵＢＲ  ＶＣｓに関しては、帯域幅必要事項は特定されず、それぞれのＵＢＲ  ＶＣｓを支援するために、ネットワーク中に帯域幅の確保が行われることはない。ＵＢＲ  ＶＣｓが特定された帯域幅を持たないという事実によって、ＵＢＲコネクションをＡＴＭネットワーク中にはっきりとロード平衡させることが困難になる。
【０００４】
コネクションはＵＢＲコネクションとして信号表示されるのは、帯域幅必要事項が未知である、若しくは帯域幅必要事項が確かに既知である場合に、コネクションが、他のサービスカテゴリに属するセルの到着時間中（cell inter-arrival times）の分布のような、他のトラフィック特性に適していないからである。ＵＢＲ  ＶＣｓの推定帯域幅必要事項が既知である場合、この推定帯域幅値は次に、ＵＢＲコネクションを効率的にロード平衡させるために用いられる。本発明は、推定帯域幅値を用いてＵＢＲ  ＶＣｓをロード平衡させる装置及び方法に関するものである。
【０００５】
【発明の要旨】
本発明は、データを送信するシステムに関する。該システムは、コネクションを支援する通信ネットワーク（telecommunications network）に関しており、各コネクションは、第一の属性(attribute)を含んでいる。第一の属性は、コネクションが特定されていないトラフィックを有することである。ネットワークは、スイッチ及び、スイッチを接続するリンクを具えている。システムは、スイッチへ接続されたルーティングモジュールを具えている。ルーティングモジュールは、送信と関係した第二の属性を、ネットワーク上の各コネクションに割り当てる機構を有している。第二の属性は、第一の属性とは異なっている。ルーティングモジュールは、第一の属性及び第二の属性に基づいて、ネットワークにコネクションを形成する。
【０００６】
本発明は、データを送信する方法に関する。該方法は、第一の属性を含むコネクションを支援する通信ネットワークを明確にする工程を具えている。第一の属性は、コネクションが、コネクション上を伝わる特定されていないトラフィックを有していることである。次に、送信と関係した第二の属性を、ネットワーク上のコネクションに割り当てる工程がある。第二の属性は、第一の属性とは異なっている。更に、第一の属性及び第二の属性に基づいて、ネットワークにコネクションを形成する工程がある。
【０００７】
添付図面において、本発明の望ましい実施例及び本発明を実践する望ましい方法が、各図に示されている。
【０００８】
【詳細な説明】
図面に於いて、各図を通じて同種又は同じ部分には、同じ参照番号を付している。より具体的には図１を参照すると、データを送信するシステム(10)が示されている。システム(10)は、コネクションを支援する通信ネットワーク(12)を具えており、各コネクションは第一の属性を含んでいる。第一の属性は、コネクションが特定されていないトラフィックを有することである。ネットワーク(12)は、スイッチ(14)及び、スイッチ(14)を接続するリンク(16)を具えている。該システム(10)は、スイッチ(14)へ接続されたルーティングモジュール(18)を具えている。ルーティングモジュール(18)は、送信と関係した第二の属性を、ネットワーク(12)上の各コネクションに割り当てる機構(20)を有している。第二の属性は、第一の属性とは異なっている。ルーティングモジュールは、第一の属性及び第二の属性に基づいて、ネットワーク(12)にコネクションを形成する。
【０００９】
望ましくは、ネットワーク(12)はＡＴＭネットワーク(12)を含み、コネクションは仮想回路を含んでいる。望ましくは、仮想回路の第一の属性は、仮想回路がトラフィックに関するＵＢＲサービスカテゴリに属することである。望ましくは、ルーティングモジュール(18)は、ネットワーク(12)に仮想回路を形成し、それらがロード平衡されるようになす。
【００１０】
望ましくは、第二の属性は、帯域幅に対応しており、該帯域幅はそれぞれの仮想回路と関係している。ルーティングモジュール(18)は、ネットワーク(12)に仮想回路を形成して、仮想回路のＵＢＲトラフィックカテゴリ及び仮想回路の帯域幅に基づいて、ネットワークはロード平衡される。望ましくは、該ルーティングモジュールは、ネットワーク(12)に仮想回路を形成して、仮想回路のＵＢＲトラフィックカテゴリ及び仮想回路の帯域幅に基づいてロード平衡されるようになし、ネットワーク(12)の全リンク(16)内に最大割合の未使用の帯域幅が達成される。リンク(16)は、トラフィック送信能力について、それぞれ異なる大きさの経路（paths）を有していることが望ましい。望ましくは、ルーティングモジュールは、全ての仮想回路が確立出来るようにオーバーブッキングを許容する。望ましくは、ネットワーク(12)及びルーティングモジュール(18)はまた、トラフィックの特定したビットレートカテゴリを有する仮想回路を支援する。
【００１１】
本発明は、図３に示されるように、データを送信する方法に関する。該方法は、第一の属性を含むコネクションを支援する通信ネットワーク(12)を明確にする工程を具えている。第一の属性は、コネクションが、コネクション上を伝わる特定されていないトラフィックを有していることである。次に、送信と関係した第二の属性を、ネットワーク(12)上のコネクションに割り当てる工程がある。第二の属性は、第一の属性とは異なっている。更に、第一の属性及び第二の属性に基づいて、ネットワーク(12)にコネクションを形成する工程がある。
【００１２】
望ましくは、明確にする工程は、コネクションを支援するＡＴＭネットワーク(12)を明確にする工程を含んでおり、そこでコネクションは、仮想回路を有している。ＡＴＭネットワーク(12)を明確にする工程は、望ましくは、第一の属性を有するような仮想回路を明確にする工程を含み、そこで第一の属性は、第一の回路は仮想回路によって支援されているトラフィックのＵＢＲサービスカテゴリに属する。望ましくは、形成工程は、仮想回路をＡＴＭネットワーク(12)へ形成する工程を含むので、仮想回路はネットワーク(12)上で他の回路とロード平衡されるようになる。
【００１３】
第二の属性は、望ましくは、仮想回路の帯域幅に対応し、そこで形成工程はネットワーク(12)に仮想回路を形成する工程を含んでおり、仮想回路は、仮想回路のＵＢＲトラフィックカテゴリ及び仮想回路の帯域幅に基づいて、他の仮想回路とネットワーク(12)上でロード平衡される。望ましくは、形成工程は、仮想回路をネットワーク(12)へ形成する工程を含んでおり、このため仮想回路は、仮想回路のＵＢＲトラフィックカテゴリ及び仮想回路の帯域幅に基づいて、ネットワーク(12)上で他の仮想回路とロード平衡されて、ネットワーク(12)の全リンク(16)中に最大割合の未使用の帯域幅が達成される。望ましくは、形成工程は、仮想回路をネットワーク(12)へ形成する工程を含んでいるので、仮想回路は、他の仮想回路とロード平衡されて、仮想回路のルーティングは、それぞれ異なる大きさの送信経路内に平衡される。
【００１４】
望ましくは、形成工程に先立って、ネットワーク(12)中の任意のリンク(16)が、仮想回路を支援するために使用可能な帯域幅を有しているかどうかを決定する工程が存在する。たとえネットワーク(12)中の全仮想回路の合計が、ネットワーク(12)が実際に支援出来る、ＵＢＲトラフィックに使用可能な帯域幅の合計より大きくても、形成工程は、仮想回路を形成する工程を含んでいることが望ましい。望ましくは、全経路が１００パーセントより大きい利用度（utilization）を有しているとき、形成工程は、最小割合の利用度を有する経路に仮想回路を形成することを含む。望ましくは、形成工程は、経路を見つける工程を含んでおり、仮想回路がそれに加えられるならば、全経路が１００パーセント未満の利用度を有する場合に、全リンク(16)内に未使用の帯域幅の割合を最大化するであろう。また、該形成工程は、全リンク(16)内に未使用の帯域幅の割合を最大化するであろう経路に仮想回路を形成する。
【００１５】
本発明の操作において、ロード平衡したＵＢＲは、大規模ＡＴＭネットワーク(12)内で、任意の大きさの、使用可能な経路中にＵＢＲトラフィックを平衡することを、ユーザに許容する機能である。この能力が無ければ、ＵＢＲトラフィックは、最高の帯域幅、最低コストの経路を通じてしか経路指定されない。ＵＢＲだけのネットワーク(12)における結果は、代わりのルートは未使用であるのに、特定の経路はトラフィックで飽和状態になることである。
【００１６】
上記機能によって、「１秒当たりのセル数（Cells Per Second）」に於けるそれぞれの呼出しの推定帯域幅及び、すべての使用可能なリンク(16)にわたった使用の割合に基づいて、ネットワーク(12)内にＵＢＲ呼出しをロード平衡する新たな方法が提供される。重み付けしたＵＢＲは、推定帯域幅（セルレート）値を各ＵＢＲ  ＶＣと関係させるために、アドミニストレータへ該能力を供給する。上記の推定は、セル／秒の単位で特定されなければならない。帯域幅推定は、次の二つの方法のように使用される：１．特定のリンク(16)の何れかがコネクションを支援するために使用可能な帯域幅を有しているかどうかを決定するためのルーティングモジュールによって、及び；２．ネットワーク(12)中の任意のリンク(16)を通じて推定トラフィック量を提供することである。この情報は、経路計算によって使用されて、ネットワーク(12)を通じてＵＢＲトラフィックを効率的に平衡するルートを計算する。
【００１７】
要約すると、ロード平衡したＵＢＲは：
１．全リンク(16)にわたる最大割合の未使用の帯域幅を許容する。
２．それぞれ異なる大きさのパイプ中に、ＵＢＲトラフィックの経路指定を平衡する。
３．如何なる場合においても回路は確立されるように、オーバーブッキングを許容する。
【００１８】
一実施例として、図２に示されているネットワーク(12)及びその状態を検討する。ネットワーク(12)は、４つのスイッチ(14)及び、それらに接続された４つのリンク(16)を有している。各リンク(16)に対する使用可能なセルレート（ＡＣＲ）、ＬＢ−ＵＢＲ累積帯域幅（ＡＢ）及びＬＢ−ＵＢＲコンジェスション（輻輳）（ＬＣ）が、図中に示されている。
【００１９】
Ｓ１が、３ＭＢの推定ＵＢＲ帯域幅を有する新たなＶＣの送信源であり、Ｓ４が受信先である場合、そのときＬＢ−ＵＢＲロード平衡アルゴリズムは、後述する理由によって、Ｓ１−Ｓ２−Ｓ４について経路Ｓ１−Ｓ３−Ｓ４を選ぶであろう。新たなコネクションの推定帯域幅が計算に入れられる場合、そのときリンク(16)Ｓ１−Ｓ２及びＳ２−Ｓ４用の新たなＡＢは３３ＭＢであり、対応するＬＣは２１％であろう。リンク(16)Ｓ１−Ｓ３及びＳ３−Ｓ４に関して、新たなＡＢは８ＭＢであり、対応するＬＣは１７％であろう。これらの数は、経路Ｓ１−Ｓ３−Ｓ４を好む。
【００２０】
一旦ルーティングの決定が行われると、ＶＣのセットアップは、Ｓ１によってＳ３へ送られて、その後Ｓ３によってＳ４へ送られるであろう。各スイッチ(14)は、各リンク用の新たなコネクションのＵＢＲ帯域幅を、両方の方向へ累積する。一旦コネクションがセットアップされると、次に８ＭＢの新しいＡＢは、リンク(16)Ｓ１−Ｓ３及びＳ３−Ｓ４のために知らされるであろう。任意の新たなＶＣセットアップについてのルーティングの決定は、これらの新たな値に基づいているであろう。
【００２１】
一般的に、各ＵＢＲ仮想回路が識別されるとき、アドミニストレータは、推定帯域幅を、ルーティングモジュール(18)に格納されている仮想回路へ関係させる。ルーティングモジュール(18)は、ネットワーク(12)の状態を認識しており、従って、リンク(16)及びその上にあるスイッチ(14)は、当該分野で周知であるように、使用可能な経路のすべてが１００パーセントより大きい利用度を有するか、或いは１００パーセント未満の利用度を有しているかを決定する。リンク(16)上のすべての使用可能な経路の利用度が１００パーセントより大きい場合、ルーティングモジュール(18)は、仮想回路を、１００パーセントを超えている最低利用度を有する経路へ向ける。利用度が１００パーセント未満の場合、その時ルーティングモジュール(18)は、上記に説明したように、未使用の帯域幅が最大の割合になる仮想回路のための経路を選ぶ。次に、セルを実際に送出又は廃棄することは、当該分野で周知のように行われる。
【００２２】
実際に帯域幅を決定する必要が無く（これは、改善した結果を得るために行うことも出来るが）、単に仮想回路の帯域幅を推定することによって、セルのＵＢＲクラスがより効率的に送出され、従って全体のネットワークがより体系化されることが出来る。ＡＢＲ、ＣＢＲ又はＶＢＲのような、その他のクラスのセルに対して、変更を行なうことは不要である。ここに説明されているシステム及び方法は、トラフィックのＵＢＲクラスに関する割当ての範囲内で機能する。
【００２３】
所定の回路が経路指定される場合、ロード平衡は、回路の送信源から受信先への最短の経路の間でしか起こらない。このことは、下記のように説明される。ネットワークの各リンクは、それと関係させられた管理「コスト」(administrative "cost"）を有している。１つの経路のコストは、経路を作り上げるリンクのコストの合計である。例えば、コスト５００の二経路とコスト６００の一経路がある場合、その際、最も短い経路（即ち、コスト５００を有する経路）が、ＶＣを支援するために十分な帯域幅を有するならば、ロード平衡のために考慮に入れられる。６００コストの経路は、たとえより大きな割合の未使用帯域幅を有しているかもしれないが、無視される。
【００２４】
最短経路の間でロード平衡が起る場合、最大の割合の未使用帯域幅を有する経路が選ばれる。このことは、経路の未使用の帯域幅の割合は、リンクにおける最少の割合の未使用帯域幅であることを意味しており、該リンクは、前記経路を作り上げるすべてのリンク（経路に沿った、最も混雑したリンク）の間に最少の割合の未使用帯域幅を有している。
【００２５】
ロード平衡したＵＢＲの機能を実行することによって、下記の仮定が生じる。
１．ＡＴＭ  ＦｏｒｕｍのＰＮＮＩ [Private Network-Network Interface Specification vl.0, The ATM Forum, af-pnni-0055.000, March 1996 は、引用を以て本願の一部とする] のようなＡＴＭリンク状態ルーティングプロトコルは、この機能によって改良されるために使用可能であると想定される。このようなルーティングプロトコルの実行の詳細は、本明細書の範囲外である。
２．リンク状態ルーティングプロトコルは、個々のリンク(16)へＡＣＲ及びＡＢ値を、それらのリンク状態の一部として伝達する機構を有していると想定される。任意の所定リンク(16)についてＡＣＲ値とＡＢ値が与えられると、該リンク(16)についてＬＣパラメータは計算できる。
３．リンク(16)の状態ルーティングプロトコルは、最短経路ツリー（Shortest Path Trees)(ＳＰＴｓ）の計算に Djikstraのアルゴリズムを使用すると想定され、これの引用をもって本願の一部とする。下記の段落にて説明されるアルゴリズムは、Djikstraのアルゴリズムにとって改良（enhancement）として提供されている。
４．リンク状態ルーティングプロトコルは、呼出し許容基本制御（Generic Call Admission Control)(ＧＣＡＣ）のアルゴリズムを使用すると想定され、これは、ＡＴＭ  ＦｏｒｕｍのＰＮＮＩの仕様書において説明された、単純なＧＣＡＣと同様なものである [Private Network-Network Interface Specification vl.0, The ATM Forum, af-pnni-0055.000, March 1996 は、引用を以て本願の一部とする]。
【００２６】
ＡＴＭネットワークを通じて行われるＶＣの経路計算（ＰＣ）は、一般的に二つの段階で起る。下記に、この二つの段階が示される。
ｉ）ＶＣのＰＣ制約条件（PC constraints）（帯域幅必要事項やセル損失率のような）を、ＳＰＴのルートとしてＶＣのソースで満たす、ネットワーク(12)中の全リンク(16)のＳＰＴの計算。
ii）ＶＣの送信源からＶＣの受信先へのソースルートである指定通過リスト（Designated Transit List)(ＤＴＬ）の作成 [Private Network-Network Interface Specification vl.0, The ATM Forum, af-pnni-0055.000, March 1996 は、引用を以て本願の一部とする]。これは、逆の順序で行われる、即ちＶＣの受信先で開始し、ソースが、横断された各ノードを加えながらリストへ到着するまで、ＳＰＴをツリーのソースへ向かって辿る。次にリストを逆向きにして、ＤＴＬを得る。
【００２７】
呼出し許容基本制御（ＧＣＡＣ）は、ルーティングプロトコルによって知らされたリンク(16)が、帯域幅必要事項やセル損失率必要事項のような、所定のトラフィック特性を有する所定のＶＣを支援する出来るか、を決定するために使われるアルゴリズムである。ＬＢ−ＵＢＲを支援するために、ＧＣＡＣアルゴリズムにおいて要求される変形を次に示す。
【００２８】
ＧＣＡＣアルゴリズムは、ロード平衡したＵＢＲを支援するために変更が加えられることが必要である。一般的に、ＧＣＡＣアルゴリズムによってＵＢＲ ＶＣｓへ加えられる必要事項は無い。通常のＵＢＲ ＶＣｓに帯域幅又はその他の必要事項は無いので、ネットワーク(12)中のリンク(16)の何れも、経路計算手続のＧＣＡＣ工程の間に消去されない。しかしながら、このことは、ＬＢ−ＵＢＲ機能の下で経路が定められたＵＢＲ ＶＣｓには当てはまらない。個々のＵＢＲＶＣｓに使用された推定帯域幅が目下存在するので、ＵＢＲ ＶＣの推定帯域幅値を、ＵＢＲコネクションに使用可能な帯域幅の値と比較するために、ＧＣＡＣアルゴリズムは変更される。この値は、ＵＢＲ ＶＣｓ（ＡＣＲ）に使用可能な全体の帯域幅と、任意の所定のリンク(16)の累積帯域幅値（ＡＢ）の間の相違である。
【００２９】
経路計算は、ＵＢＲ ＶＣｓの経路を計算するときに、二つの手続を通す。第一の手続に於いて、ＧＣＡＣアルゴリズムを実行するときに、推定帯域幅値は考慮に入れられる。第一の手続にて、推定帯域幅の必要事項を満たす一つの経路も見つけられない場合、次に、帯域幅必要事項を緩和した後に、第二の手続が操作される。上記理由から、ＵＢＲ ＶＣは、帯域幅が不十分であることによって拒否されることは決してない。従って、上記に説明されたＬＢ−ＵＢＲ輻輳値は、１００％を越すことが出来て、オーバーブッキングは起り得る。
【００３０】
添付図（図４〜図６）に記載されているアルゴリズムは、Djikstraのアルゴリズムを使用して、所定のネットワーク(12)のために最短経路ツリーを計算するものである。ネットワーク(12)は、一対のノード及びリンク(16)として表される。ノードは、ＡＴＭネットワーク(12)中のスイッチ(14)を表し、リンク(16)は、スイッチ(14)間の論理的リンク(16)（経路）を表している。ネットワーク(12)中の各リンク(16)は、それと関係したコストを有している。各リンク(16)と各ノードの最短経路コストの合計は、送信源からノード又はリンク(16)への最短経路を含む、全リンクのコストの累積合計として計算される。
【００３１】
本発明を、例示の目的のために、前述の実施例において詳細にわたって説明してきたが、この様な詳細は、単にこの目的のために過ぎず、当該分野の専門家によって、前述の特許請求の範囲に説明するものを除いて、本発明の精神及び範囲から逸脱することなく、種々の変化が加えられることが可能であると理解されるべきである。
【図面の簡単な説明】
【図１】本発明のシステムの概略図である。
【図２】４つのスイッチ及び、スイッチへ接続された４つのリンクを有している、本発明のシステムの概略図である。
【図３】本発明の方法の流れ図である。
【図４】  Djikstraのアルゴリズムを使用して、所定のネットワークのために最短経路ツリーを計算するアルゴリズムを示す図である。
【図５】図４の続きを示す図である。
【図６】図５の続きを示す図である。
【符号の説明】
(12)  ネットワーク
(14)  スイッチ
(16)  リンク
【図１】
0004368981.tif 000002
【図２】
0004368981.tif 000003
【図３】
0004368981.tif 000004
【図４】
0004368981.tif 000005
【図５】
0004368981.tif 000006
【図６】
0004368981.tif 000007