(57)【特許請求の範囲】
【請求項１】
通信ネットワークのリンク（２０．１、２０．２等）に帯域容量を割り当てるための方法であって、
前記通信ネットワークは複数のサブネットワークおよび複数の通信サービスをサポートし、前記通信ネットワークの内部において、前記各サブネットワークおよびサービスに対する各ソース−宛先の組の間で許容ルートの組が定義され、前記通信ネットワークは、ルート・コントローラを具備する少なくとも一つの交換機に接続され、本方法は前記ルート・コントローラにより実行され、本方法が、二度又はそれ以上の反復において、
（ａ）前記ネットワークの少なくとも幾つかのリンクの各々の帯域容量を、前記少なくとも幾つかのリンクの各々を共有するサブネットワーク間で分割するステップ（１１０）と、
（ｂ）二つ又はそれ以上のサブネットワークにおいて、各サービスおよび各サービスによりサービスを受けるソース−宛先の各組に対して、前記ソース−宛先の組の間の各許容ルートに提供されるトラヒック速度を決定するステップ（１５）とを含み、
ステップ（ａ）の少なくとも一つの場合（１４５）が、ステップ（ｂ）についての以前の場合（１３１）に起因するトラヒック速度の割り当てに基き、分割されたリンク容量の組を更新するステップを含み、
ステップ（ｂ）の少なくとも一つの場合（１３１）が、ステップ（ａ）についての以前の場合（１４５）に起因するサブネットワーク間でのリンク容量の更新された分割に基き、
前記分割されたリンク容量の組は、分割されたリンク容量の現在の組と現在のトラヒック速度とから各サブネットワークのリンク容量に対するネットワーク収益関数の依存性を計算（１３２）し、前記計算された依存性と分割されたリンク容量の現在の組とを、分割されたリンク容量の更新された組を生成するための入力として使用することにより、更新される、
通信ネットワークのリンクに帯域容量を割り当てるための方法。
【請求項２】
請求項１に記載の方法において、前記ネットワーク収益関数は、各サブネットワークについての帯域幅の大きさの加重総計であり、前記ネットワーク収益関数を最大にするために、ステップ（ａ）とステップ（ｂ）とが実行される方法。
【請求項３】
請求項２に記載の方法において、少なくとも一つのサブネットワークにおけるサービスの最低品質を指定する制限に従って、前記ネットワーク収益関数が最大化される方法。
【請求項４】
請求項２に記載の方法において、各反復中に、各サブネットワークに対してステップ（ｂ）が独立して実行され、ステップ（ａ）が、各リンクに割り当てられた帯域幅がサブネットワーク間で完全に分割され且つ帯域幅が各リンクに別々に再割り当てされるように実行される方法。
【請求項５】
請求項１に記載の方法において、各サブネットワークからの各サブネットワーク収益を合計する（１３５）ことによって、前記ネットワーク収益関数を評価し、
リンク容量に対するネットワーク収益関数の依存性についての前記計算は、各サブネットワークの各リンクに対して、前記サブネットワークについて前記リンクへ割り当てられた帯域幅に対する、関連サブネットワーク収益の感度を表す容量コストを計算するステップ（１３２）を含み、前記方法はさらに、
各反復中に、前記帯域幅の再割当に基づいて、新しいサブネットワークに対する前記帯域幅の割当の現在の組に基づいて、現在のサブネットワーク収益から外挿するために、前記容量コストを使用するステップ（１４５）とを含む方法。
【請求項６】
請求項５に記載の方法において、
推定コストと呼ばれる各ペナルティが、それぞれのサービスに対する各サブネットワークの各リンクに関連していて、
各推定コストが、関連サブネットワークの呼毎の有効収益、および前記関連リンクにおいて経路選択されるサービスを少なくする働きをし、
前記推定コストは、各サブネットワークの種々のリンク上の帯域幅が不十分なために呼が失われる確率を反映し、
容量コストを計算する前記ステップが推定コストを評価するステップを含む方法。
【請求項７】
請求項１に記載の方法において、さらに、ステップ（ａ）の最後の反復の後で、少なくとも一つのリンクにおいて、帯域幅を、少なくとも一つのサブネットワークから少なくとも一つの他のサブネットワークに一時的に再割り当てするステップを含む方法。
【請求項８】
請求項１に記載の方法において、前記方法が、さらに、少なくとも一つのサブネットワーク内の、少なくとも一つのソース−宛先の組に提供される少なくとも一つの種類のサービスにおいて、トラヒック密度を測定するステップを含み、
ステップ（ａ）および（ｂ）が前記測定するステップに応じて実行され、
前記方法が、さらに、ステップ（ａ）および（ｂ）に応じて、ネットワーク構成要素の少なくとも一つの動作パラメータを設定するステップを含む方法。
【請求項９】
請求項８に記載の方法において、ネットワーク構成要素の少なくとも一つの動作パラメータを設定する前記ステップが、スケジューリング加重を設定するステップを含む方法。
【請求項１０】
請求項１に記載の方法において、前記方法が、さらに、少なくとも一つのサブネットワーク内の、少なくとも一つのソース−宛先の組に提供される、少なくとも一つの種類のサービスにおいて、トラヒック密度を測定するステップを含み、
ステップ（ａ）および（ｂ）が、前記測定するステップに応じて実行され、
前記方法が、さらに、ステップ（ａ）および（ｂ）の後で、少なくとももう一度トラヒック密度を測定するステップを含み、
前記方法が、さらに、トラヒック密度の少なくとももう一度の前記測定に応じて、少なくとも一つのサブネットワークから少なくとも一つの他のサブネットワークへ、少なくとも一つのリンクにおいて帯域幅を一時的に再割り当てするステップを含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一種類以上のサービスに対応するトラヒックを運ぶ種類の通信ネットワークの設計および管理に関し、特に利用することができるルートの間でトラヒックを分配し、上記種類の通信ネットワークの上記ルートに帯域幅資源を割り当てるための方法に関する。
【０００２】
【従来の技術、及び、発明が解決しようとする課題】
ネットワークは、通常、コンピュータ・ターミナル、電話、ファクシミリおよびコンピュータ・ファイル・サーバのようなターミナル通信装置の間で情報を交換し、伝達するために使用される。図１は、例示としてのネットワークである。通常のネットワークは、この図のリンク２０．１−２０．１０のようなリンクで相互に接続している、この図のノード１０．１−１０．８のような交換ノードを含む。各ターミナル通信装置（図示せず）は、一般に、上記ノードの一つに関連している。
【０００３】
各リンクは、通常、そのリンクに対する帯域幅として特徴づけられるある容量を持つ。ネットワークは、種々の形で情報を運ぶことができる。しかし、上記情報は、多くの場合、適当なネットワーク形成プロトコルにより、パケットまたはセルの形にフォーマットされる。
【０００４】
ネットワーク形成プロトコルの一つに非同期転送モード（ＡＴＭ）がある。ＡＴＭは、高速デジタル音声およびデータ通信を効率的にサポートするように設計されたネットワーク形成プロトコルである。
【０００５】
一組のターミナル通信装置間で情報が交換される場合には、ネットワークは、上記装置に関連する上記ノードの間に経路を確立する。以下の説明において、発呼ノードは、多くの場合「ソース」と呼ばれ、宛先ノードは、多くの場合「宛先」と呼ばれる。上記確立した経路を通しての、所与のサービス・タイプの情報の流れは、多くの場合、ソースから宛先への通信「ストリーム」と呼ばれる。
【０００６】
（もし、存在する場合には）中間ノード、およびそれらを接続しているリンクも含めて、所与の通信ストリームに対するソースおよび宛先を、「物理的経路」という用語で呼ぶことにする。実際の大きさと複雑な構成を持つネットワークにおいては、多くの場合、一組の多重物理的経路が存在するが、各物理的経路は所与のストリームを運ぶことができる。
【０００７】
物理的経路は、ソースＳと宛先Ｄとの間に存在するが、この物理的経路に沿ったリンクの全帯域幅は、ＳとＤとの間で通信ストリームを運ぶのに使用することはできないことに留意されたい。すなわち、ネットワーク・マネージャは、可能な各物理的経路に沿って、ＳとＤとの間に、ストリームに対して所定の帯域幅を指定するすることができる。この指定された帯域幅は、全帯域幅に等しいか、または全帯域幅より少し狭いか、または帯域幅を全然持たない。もちろん、最後のケースは、ＳとＤとの間に物理的経路が存在しないのと同じことである。
【０００８】
帯域幅の指定により定義された、所与のソースと所与の宛先との間の経路を、「論理的経路」または「仮想経路」という用語で呼ぶことにする。これらの用語を使用する場合には、これら経路が、物理的考慮だけでは決定できず、指定でき、また変更できるパラメータにより一部定義されることを意味する。
【０００９】
上記説明から、個々の仮想経路は、多くの場合、それらが占めるリンク上で物理的に使用することができる全帯域幅より狭いことを理解することができるだろう。それ故、多くの場合、いくつかの仮想経路が、物理的経路の一部または全部に沿って共存することになる。すなわち、ネットワークの各リンクは、いくつかの仮想経路を同時にサポートすることができる。
【００１０】
仮想経路の重要な利点は、ネットワークの種々のユーザにサービスを提供するために、この仮想経路をサブネットワークに分割することができることであり、またこれらサブネットワークを変動するトラヒック要件に対応するために、その時々で、そのサイズを変更することができることである。（すなわち、種々の仮想経路に沿った帯域幅の指定を変更することができることである。）
【００１１】
ソース−宛先の組、サブネットワーク、およびサービスの種類に従って、ネットワークのすべての仮想経路へ帯域幅を割り当てる問題は、論理的ネットワーク設計と呼ばれる。論理的ネットワーク設計の一つの重要な要素は、通信ストリームの推定トラヒックを伝達するのに十分な容量を持つネットワークを通して、一組の物理的経路を選択する問題である。この問題を解決するこのプロセスは、ネットワーク・トポロジー、ノードのところで現在使用することができるバッファ空間、および現在使用することができるリンク容量のような要素を考慮に入れることができる。
【００１２】
重要なことは、ネットワーク・オペレータが、保証帯域幅または最大セル呼損率のようなその顧客に関するサービスの質に責任を持つことができることである。経路選択プロセスは、上記責任を考慮に入れることができる。
【００１３】
すでに説明したように、ある種のネットワーク、特に高速ネットワークは、ＡＴＭと呼ばれる、ネットワーク形成プロトコルをサポートすることができる。高速ネットワークは、通常、一定のビット速度トラヒックおよび可変ビット速度トラヒックの両方を含む、異なるトラヒック特性を持つ多重サービスを行う。ＡＴＭネットワークで可変ビット速度トラヒックを処理する際の重要な単純化は、「ネットワーク・ノードで、ネットワーク資源を割り当てることによる、受け入れ制御および経路選択のための方法」という名称の、米国特許出願第０８／５０６，１６０号に詳細な記載がある「効果的帯域幅」というコンセプトにより行われる。
【００１４】
バッファ処理容量は、帯域幅を補足するものとしてＡＴＭネットワークで重要な役割を演じるが、このモデルは、有効な帯域幅へのバッファ処理に関連する考慮を有効帯域幅に導入する。従って、可変ビット速度トラヒックが、その有効帯域幅により特徴づけられる場合には、任意のＡＴＭネットワークを、（呼出処理目的のために）その内部において、各サービスの説明がサービスを行う各リンクに対して特徴を持つ帯域幅要件を含む、多重速度、回線交換、損失ネットワークと見なすことができる。
【００１５】
我々の目的にとって役に立つ単一の回線交換損失ネットワークのモデルにおいては、各サービス・ルート（または「仮想経路」）は、比較的大きな帯域幅にまたがっていて、多くのより狭い帯域幅のサブチャネルに分割することができる、通信チャネルとして処理される。多くの呼出は、仮想経路上で多重化される。各呼出は、一つまたはそれ以上のサブチャネルを占有する。我々のモデルの場合には、この占有は、呼出が行われている間中、独占的なものであると仮定した方が便利である。一つの呼出を運ぶサブチャネルは、「交換仮想回線」または「交換仮想接続」と呼ばれる。ビットは、各ソースにより、（関連サービスに対する有効帯域幅に対応する）一定の速度で送信されるものと仮定する。インターネット・プロトコル（ＩＰ）通信をよく知っている人なら、「流れ」または「接続」と呼ばれるトラヒック構成要素が、交換仮想回線のＩＰ相対物を指すことを理解することができるだろう。（ＩＰに関連して、ＲＳＶＰと呼ばれるプロトコルが、ソース−宛先経路の資源を予約するために呼び出され、このプロトコルが、「流れ」のＩＰコンセプトを交換仮想回線のＡＴＭコンセプトにより近いものにする。）
【００１６】
有効帯域幅モデルによる便利な機能が、ネットワーク分析に適用された場合でも、帯域幅割当および経路選択の問題が、非常に困難なものになる場合がある。この困難の一つの原因は、永久的な仮想回線とは異なり、仮想回線は形成され、暫くの間ネットワーク資源を保持するが、その後で消滅するからである。そのため、呼出の到着および呼出の保持時間がランダムであることを考慮に入れる必要がある。上記困難の第二の原因は、これらネットワークの潜在的リンク容量が大きいことである。そのため、近い将来、数千または数万もの回線になる恐れがある。さらに、上記困難の第三の原因は、これらネットワークが運ぶことができる、異なるサービスの潜在的数が大きいことである。この数は、近い将来数百のサービスになり、その後ではさらに増大するものと考えられている。
【００１７】
単一速度回線交換ネットワークを分析するための周知の技術がいくつか存在する。少なくともより簡単なネットワークにおいては、このような技術の力を借りて、帯域幅割当および経路選択を有益に行うことができる。しかし、多重速度が導入されると、とりわけ、実際の問題の計算上の使いやすさが低下が上記困難の原因になる。
【００１８】
本明細書に記載した共同発明者は、多重速度回線交換ネットワークの設計問題に有意に貢献をしてきた。その貢献の中には、経路選択方法が含まれる。以後ミトラ他と呼ぶ（１９９６年８月の）ネットワーク形成４に関するＩＥＥＥ／ＡＣＭ会報の、５３１〜５４３ページ掲載の、Ｄ．ミトラ他の「ＡＴＭネットワーク設計および最適化；多重速度損失ネットワーク・フレームワーク」に、上記方法が記載されている。１９９５年１１月７日付の本出願と一緒に共通に譲渡された、「多重サービス・ネットワークの論理的ネットワーク設計を行うための方法」という名称の米国特許出願０８／５５４，５０２も、上記方法を記載している。
【００１９】
図２を参照しながら、ミトラ他の経路選択方法を簡単に説明する。
上記経路選択方法の目的は、ネットワークの性能を最適化する一組のソース−宛先の間の各ルートに提供されたトラヒックの速度を発見することである。ネットワークの性能は、種々の方法で特徴づけることができる。ある例示としての分析の場合には、ネットワークの性能は、長期ネットワーク収益Ｗにより特徴づけられる。Ｗは、単位時間当たりに行われた呼出毎の収益ｅsr、トラヒック密度（トラヒック速度とも呼ばれる）ρsr、および呼損率Ｌsrにより決まる。下付き文字ｓは、各サービス・タイプにより異なる数値を取り、各サービス・タイプが、これらのパラメータに対して、それ自身の特殊な一組の数値を持つことを意味する。（ネットワーク設計および管理の分野においては、トラヒック特性およびサービスの品質の基準は、場合によっては、関連「用途」により決定され、「サービス」という用語は、幾分より狭い意味で使用されるといわれる。本明細書においては、「サービス」という用語は、一般的な意味で使用され、「用途」と同義語である。）
【００２０】
下付き文字ｒは、所与のソースと所与の宛先との間の一組の許容ルートの各ルートに対して異なる数値をとり、所与のサービス・タイプにおいてすら、各ルートがそれ自身の特殊な数値の組を持つことを意味する。トラヒック密度は、所与のルートに提供された呼出の平均到着速度に一つの呼出の平均保持時間を掛けたものとして定義される。（モデル化するために、呼出到着はポアソン分布を持つものと仮定する。）呼損率は、阻止される呼出分と定義される。上記ルートの何等かのリンクが、（そのリンク上の呼出を実行するのに十分な資源を持っていないために）その呼出を拒否した場合に呼出の阻止が発生する。
【００２１】
呼損率は、提供されたトラヒック速度に対して複雑な依存性を持つ。より詳しく説明すると、ネットワークの一部でのトラヒック・ローディングの小さな変化は、ネットワークのより大きな部分上で反動を起こす場合がある。そのため、逐次比較法により提供されたトラヒック速度の最適な組にアプローチするために、反復方法を使用しなければならない。ミトラ他は、最も急峻な上昇方法のような最適化の周知の技術に基づく方法を採用する。この方法によれば、種々の各パラメータρsrに対するＷの感度の知識は、現在の各近似から次の近似へのステップを形成するために使用される。上記感度は、「ネットワーク感度」と呼ばれる。
【００２２】
【外１】
0003789681.tif 000002
【００２３】
ρsrに対する最初の数値の組が供給される（ブロック４５）。
その後、上記ルートパケット帯域幅割当データは、呼損率およびネットワーク感度を決定するために使用される（ブロック５０）。
【００２４】
その後、ρsrの数値は、例えば、Ｗの改善された数値を与えるために、最も急峻な上昇法に従って増分だけ増大する（ブロック５５）。
【００２５】
その後、ローカル最適値へのアプローチを測定するための例示としての方法において、Ｗの現在および前の数値を比較することにより、収束に対する試験が行われる（ブロック６０）。Ｗの変化が十分小さな場合には、この手順は収束したと宣言され、Ｗの現在の数値およびパラメータρsrが、最適値として出力される。そうでない場合には、ρsrの現在の数値を使用して、上記手順が反復して行われる。
【００２６】
所与のストリームの到着呼出は、そのストリームに対する一組の許容ルートの任意のルートに提供することができる。上記提供は、所定の各確率値に従って、上記一組のルート中のルート上に分配される。すなわち、各ルートに対して、ランダムに選択した呼出が、そのルートに提供される確率は、所定の数値を持つ。上記パラメータρsrの最適化された数値が、上記確率を決定するために使用される。
【００２７】
ミトラ他の手順からの出力も、各リンクｌ上のサービス・タイプｓの呼損率Ｂslを含む。この情報から、各サービス・ルートの各リンクに対する必要な帯域幅の使用の基準を入手するために、また、上記情報から、各サービス・ルートの各リンクへの、各ストリームに対する帯域幅の名目上の割当を行うために複数の手順を使用することができる。
【００２８】
ネットワーク・オペレータにとって、その顧客に、（例えば、サービス・レベルの契約を通して）保証した品質のサービス、特に異なるタイプのサービスに対して（それ故、異なるデータ速度）を提供することが、ますます重要になってきている。この問題に対する一つの非常に魅力的なアプローチは、ネットワークを仮想私的ネットワーク（ＶＰＮ）に編成することである。折り合いのついたサービスの質を供給するために、それらが占有しているリンク上の種々のＶＰＮに対して、十分な帯域幅が割り当てられる。顧客の収益を最大にするために、ネットワーク・オペレータは、すべての顧客にトラヒックが、その各ＶＰＮを通して最適に経路選択された場合、ネットワーク収益Ｗのような、そのネットワークを通して行われた帯域幅の加重総合基準が最大になるような方法で、帯域幅の割当を行う必要がある。
【００２９】
これによる問題は、複雑な内容を抱えていて、それは初期の研究ではほとんど正しく研究されなかった。すなわち、異なるＶＰＮ間でリンクを分割すると、ＶＰＮの最適な経路選択の問題と、各ＶＰＮへの最適な帯域幅の割当の問題との間にどうしても関連ができてくる。
【００３０】
すでに説明したように、ミトラ他の方法は、孤立しているＶＰＮの経路選択問題に有利に適用することができる。しかし、この方法だけでは、ネットワーク資源が複数のＶＰＮに割り当てられる場合には、ネットワーク設計のより大きな問題を解決することはできない。
【００３１】
【課題を解決するための手段】
本発明は、複数のサブネットワークおよび複数の通信サービスをサポートするネットワークで最適な経路選択および最適な帯域幅割当の複合問題を解決するためのものである。広い意味でいうと、本発明は、所与のサブネットワーク、および所与のサービスの種類を通して通信する、各ソース−宛先の組に対して、所与のサブネットワークおよびサービスの種類で、上記ソースと上記宛先の間の一組の各許容ルートに提供されるトラヒック速度の決定を含む。本発明は、さらに、各サブネットワークの各リンクへの、各帯域幅の割当を含む。重要なことは、提供するトラヒック速度の決定、およびサブネットワークの各リンクへの帯域幅の割当が、相互に反応する方法で行われることである。
【００３２】
【発明の実施の形態】
Ｉ．ミトラ他の最適経路選択問題
本発明を理解するには、上記のミトラ他の特許に記載されている手順の概略を最初に概観することが望ましい。本明細書においては、ミトラ他の手順により解決しようとした問題を最適経路選択問題と呼ぶことにする。
【００３３】
図２のブロック５０のところですでに説明したように、（反復）手順の一つのステップは、呼損率Ｌsrおよびネットワーク感度∂Ｗ／∂ρsrを決定することである。上記呼損率およびネットワーク感度は、ルートｒ上のサービス・タイプｓの、提供された負荷に関するネットワーク収益の各派生物と考えると、最もよく理解することができる。
【００３４】
図３は、図２にブロック５０として示したステップである。このステップは、それぞれ、ブロック６５、７０および７５で示す三つのより小さいステップからなる。ブロック６５は、予め定義した有効帯域幅ｄsl、予め定義したリンク容量Ｃl 、および提供された負荷ρsrの現在の推定値を入力として取り入れる。ブロック６５で実行される手順は、（各サービスの種類およびリンクｌに対する）連結式の、二つのシステムの自己矛盾しない回答を反復して発見するステップを含む。固定点方程式と呼ばれる、上記式については、以下にさらに詳細に説明する。この式の一つのシステムは、以下に説明するリンク呼損率Ｂslに対するものである。正確な技術を使用して計算を行う場合には、Ｂslの計算は、複合項Ｏ（Ｃ）を持つ。この場合、Ｃはリンク容量の特徴を示す。（以下に説明するように、漸近技術を使用すると、この複合項をＯ（１）という簡単な形にすることができる。
【００３５】
ブロック６５の結果として計算することができる数値は、リンクｌ上のサービスｓの呼出のリンク呼損率Ｂsl、所与のルートのすべての他のリンクにより、独立して間引いた（すなわち、呼出をドロップした）後で、ルートｌによりリンクに追加されたサービスｓの負荷νsl:r、およびすべての間引いた各負荷に関するリンク呼損率の派生物を含む。単位時間毎に行われた呼出毎に入手した、予め定義したネットワーク収益ｅsrと共に、上記数値がこの図のブロック７０に入力される。ブロック６５の出力は、ネットワークへの参加が行われた後の均衡確率である、ルート呼損率Ｌsrである。サービスの種類ｓの呼出は、ルートｒにより放棄される。（そのリンクのいずれかが、その呼出を拒否した場合には、ルートは呼出を放棄する。）
【００３６】
ブロック７０においては、各サービスの種類に対して、一組のパラメータｃslの計算が行われる。この場合、ｌは数値ｌ＝１、２、．．．、Ｌをカバーし、Ｌは、そのネットワークのリンクの総数である。推定コストと呼ばれる上記パラメータは、所与のリンク上の、所与のサービスの種類の呼出を行う際に発生する、収益の有効な損失を反映し、残りの容量を減少させ、その結果、将来提供される呼出の阻止が行われる際に、増分だけの増大を起こす。正確な技術を使用するこの計算の複合項は、Ｏ（Ｓ3Ｌ3）である。
【００３７】
ネットワーク感度は、この図のボックス７５に示すように、ルート呼損率、収益パラメータ、および推定コストから容易に知ることができる。
【００３８】
図４について説明すると、この図は、それぞれ、ブロック８０および８５により表される二つの固定点方程式を示す。ブロック８０においては、各リンク呼損率は、対応するリンク容量により表され、各サービスの種類ｓに対して、ｓ＝１、２、．．．、Ｓ（Ｓは、サービスの種類の全数である）の場合には、対応する全間引きリンク負荷、およびリンク帯域幅により表される。ブロック８５においては、各全間引きリンク負荷は、すべてのリンクおよびすべてのサービスの種類に対して、各リンク呼損率により表される。すでに説明したように、自己矛盾のないように、連結式のこれら二つのシステムを解くために、反復技術が使用される。
実用上重要な多くのケースの場合、上記固定点方程式を解き、正確な技術により推定コストを知るために、経済の上でも、数字の上でも、実際に使用できないほど、リンク容量が大きくなりすぎる場合がでてくる。そのような場合には、ミトラ他の特許に記載されているように、計算の複雑さを軽減するために、均一漸近近似法（ＵＡＡ）と呼ばれる漸近近似法を使用することができる。実際には、小さなリンクは正確な技術で処理することができ、一方、同時に、より大きなリンクは、ＵＡＡで処理することができる。上記アプローチを「ハイブリッド」アプローチと呼ぶことにする。
【００３９】
図５は、リンク容量、全間引きリンク負荷、およびリンク帯域幅により表される、リンク呼損率Ｂslに対するＵＡＡのステートメントを示す。この図の関数ＢslおよびＢl は、ミトラ他の特許に定義されていて、Ｂl はサービスの種類ｓとは無関係であることを説明するだけにとどめ、詳細な説明は省略する。このことは、以下に説明するように、損失および推定コストの計算の複雑さを軽減するために重要である。
【００４０】
図５の第二の式は、ＵＡＡの結果である。これは、推定コストを入手するためのスタート点である。これも、損失および推定コストの計算の複雑さを軽減するために重要なことである。記号ｓおよびｔの両方は、サービスの種類の指数である。関数ａtlは、ミトラ他の特許に定義されているので、ここでは詳細な説明は省略する。
【００４１】
この点について、ミトラ他が解決しようとした最適経路選択問題に対して、ＵＡＡが役に立つことは分かっているが、本発明の最適経路選択問題を解く場合、異なる漸近近似法を使用するのが好ましいことが分かったことに留意されたい。本発明の好適な近似は、改良形均一漸近近似法（ＲＵＡＡ）と呼ぶことにする。ＲＵＡＡは、好適な近似法である。何故なら、リンク呼損率に対する、推定コストおよび感度を計算するための、より正確な方法であるからである。本発明の特徴を説明した後で、以下にＲＵＡＡについて詳細に説明する。
【００４２】
図６に示すように、ＵＡＡ（ボックス９０）を計算に導入すれば、固定点方程式（ボックス９５）を解く際に、コストを削減することができる。何故なら、リンク呼損率の計算の複雑さをＯ（１）まで軽減することができるからであり、（すなわち、Ｃが無制限に増大した場合、限界内に留まるからであり、）推定コスト（ボックス１００）を計算する際の複雑さをＯ（Ｌ3）まで軽減することができる。それ故、推定コストを計算する際の複雑さが、サービスの種類の数とは無関係になる。顧客に異なるニーズを供給し、そのため、多くの異なるサービスの種類でトラヒックを行う、大型の多重速度ネットワークの場合には、特に重要である。
【００４３】
II．最適経路選択および資源割当導入の複合問題
ここで、例示としての実施形態における、本発明の特徴について説明する。物理的下部構造ネットワークは、複数のサブネットワークをサポートする。これらサブネットワークを呼ぶのに、多くの場合、仮想専用網（ＶＰＮ）という用語を使用することにする。例えば、図１のネットワークにより、四人の顧客、すなわち、イースト・コーポレーション、ミッドウェスト・コーポレーション、ウェスト・コーポレーションおよびサウス・コーポレーションにサービスを提供すると仮定しよう。これら各コーポレーションは、それ自身のＶＰＮを持っているが、下支えしているネットワークは、種々のＶＰＮの間で共有される。各コーポレーションは、これら種々のリンクのそれ自身の使用パターンを持つ。例えば、各ＶＰＮにおいては、ノードの他の組の間より、上記コーポレーションの本店に対応するノードの間の方がトラヒック量が多い。以下に説明する例示としての実施形態の目的のために、ウェスト・コーポレーションは、図１のノード１０．１および１０．２のところに本社を持ち、ミッドウェスト・コーポレーションは、ノード１０．３のところに本社を持ち、イースト・コーポレーションはノード１０．４、１０．５および１０．６のところに本社を持ち、サウス・コーポレーションはノード１０．７および１０．８のところに本社を持つ。（同じ例示としての目的のために、一つのコーポレーションの本社のない任意のノードは支店となる。）
【００４４】
【外２】
0003789681.tif 000003
以下の説明においては、この加重総計基準をネットワーク収益と呼ぶ。通常、本明細書においては、そのそれぞれ、を記号ｓで示す、複数のサービスの種類のトラヒックを、各ＶＰＮが、サポートしていることに留意することが重要である。
【００４５】
以下の説明においては、ミトラ他の特許の最適経路選択問題の説明で使用している記号を使用することにする。しかし、特定のＶＰＮに特有の上記数値は、上記のリンク容量の場合のように、ＶＰＮ指数が上付き文字で表示されている。
【００４６】
【外３】
0003789681.tif 000004
【００４７】
以下の説明においては、全部でＳのサービスの種類があり、種類ｓの各呼出は、リンクｌ上で帯域幅ｄslを必要とするものと仮定する。
【００４８】
本発明の技術は、実際のネットワークにおいて、広い用途を持つものと考えるが、以下に説明する実施形態は、ある理想化した特性を持つモデル・ネットワークを参照して、作成したものであることに留意されたい。すでに説明したように、パケット化したネットワークは、回線交換損失ネットワークとしてモデル化することができること、バッファ処理に関するすべての考慮は、有効帯域幅に導入することができるものと仮定する。
【外４】
0003789681.tif 000005
【００４９】
【外５】
0003789681.tif 000006
【００５０】
【外６】
0003789681.tif 000007
【００５１】
III．最適経路選択および資源割当の複合問題の概観
【外７】
0003789681.tif 000008
この式に関連所得パラメータを掛けることにより、サービス・ルートに対する長期平均収益が得られる。サブネットワークに対する長期平均収益は、サブネットワークのすべてのストリーム（ｓ、σ）上、および各ストリームに対する一組のルートの、すべてのルート上の上記式を合計することによって得られる。
【００５２】
【外８】
0003789681.tif 000009
【００５３】
少なくともいくつかのケースの場合、サブネットワークのいくつかのそれぞれ、または全部に対して確実に約束の品質を提供するために、もっと多くの制約を課することが望ましい場合がある。そのようなアプローチの一つとしては、指定の数値以下に下がらないように、影響を受けた各サブネットワークの収益Ｗ(Ω)を制限する方法がある。
【００５４】
図７に示すように、本発明の計算上の手順は、親のプロセス１１０と、各ＶＰＮに対して一つずつある、子のプロセス１１５との間の相互作用により、有利に実行することができる。上記親のプロセスは、一組のサービス−ルート・トラヒック密度が、サブネットワーク・リンク容量に対する最適経路選択に対応する場合に、資源割当問題を解決するプロセスを含む。子の各プロセスは、その各サブネットワークに対する、リンク容量の現在の組の場合の、最適経路選択問題を解くプロセスを含む。全手順は、リンクの各再割当を行い、その後で、各サブネットワークに対する最適経路選択問題の、新しい解を見つけるという方法で、反復して行われる。全ネットワーク収益が収束することが分かった場合に、上記反復はストップする。
【００５５】
適当なコンピュータ・プログラムの制御の下で、デジタル・コンピュータにより、上記計算のすべての手順を容易に実行することができる。重要なことは、子の各プロセスは、他の子のプロセスとは独立して（各反復の際に）実行されることである。それ故、子のプロセスは、並列プロセサにより、都合よく有利に実行することができる。
【００５６】
リアルタイムのネットワーク管理のために、実際に使用する場合には、ネットワーク１２０のトラヒック特性が測定され、例えば、マトリックスの形をしている親のプロセサ１１０に送られる。（実際のネットワークにおいては、上記測定は、通常、周期的に行われる。例えば、１５分に一回の割当で行われる。
【外９】
0003789681.tif 000010
【００５７】
関連トラヒック測定は、例えば、先行する周期中に測定を行い、それを現在の周期に外挿するプロセスである。別の方法としては、トラヒック特性の関連記述を、例えば、過去のデータに基づいて行うことができる。
【００５８】
関連測定は、通常、ネットワークの種々のノードのところに位置する、交換機により行われ、中央ネットワーク管理プラットホームにより集められる。
【００５９】
例えば、図８に示すように、交換機１２１は、通常、多くの場合、ルート・コントローラと呼ばれる中央処理装置（ＣＰＵ）１２２と、高速エサネット・リンク上の相互通信のルータ１２３を含む。ルート・コントローラ１２２は、特に、ルートの選択を行い、素子マネージャと呼ばれる、ソフトウエア・モジュール１２４を通して素子管理機能を行う。ルータは、各入口リンク１２６．１に対する各インターフェース・カード１２５．１、および各入口リンク１２６．２に対する各インターフェース・カード１２５．２を含む。各入口インターフェース・カード１２５．２は、パケットのスケジュールの作成をする、メモリ１２７を持つＣＰＵを含む。メモリ１２７は、ルート・コントローラ１２２と共有することができる。（ある場合には、各インターフェース・カードは、それ自身の各メモリを持つ。）
【００６０】
素子マネージャ１２４は、周期的に、入力パケット（またはセル）上のヘッダを読み出し、それにより、ソース−宛先トラヒック、および出力リンクの使用状態についての情報を収集する。重要なことは、ヘッダは、また、サービスの種類およびＶＰＮを識別する情報を含むことである。管理情報ベース（ＭＩＢ）と呼ばれるデータベース（図示せず）は、通常、素子マネージャ、および中央ネットワーク管理プラットホーム１２８のところに、常駐している。（場合によって、ローカルまたはグローバルな）関連データが、ＭＩＢに記憶される。各（ローカル）素子マネージャ１２４と、中央ネットワーク管理プラットホーム１２８との間の通信は、簡単ネットワーク管理プロトコル（ＳＮＭＰ）と呼ばれる、プロトコルにより調停される。中央ネットワーク−管理プラットホームへ情報を送信する他に、各素子マネージャは、また周期的に、そこからグローバルなネットワーク・トラヒック情報をダウンロードする。この情報により、本明細書に記載する計算上の手順を、例えば、ルート・コントローラ１２２により実行することができる。
【００６１】
計算手順の出力、すなわち、一緒に最適化されたサービス−ルート・トラヒック密度およびリンク容量は、例えば、スケジューラおよび待ち行列エンジンの、パラメータおよび加重を決定することにより、ネットワークの動作特性を更新するために、ルート・コントローラにより、容易に適用することができる。
【００６２】
例えば、交換機１２１からの各入口リンクは、通常、対応するインターフェース・カード１２５．２上でＣＰＵにより実行される、それ自身のスケジューラを持つ。スケジュール作成（スケジューリング）機能を実行するために、種々のスケジュール作成方法を使用することができる。加重ラウンド・ロビン・スケジュール作成のような、加重スケジュール作成は、サービス・レベルの協定を強制的に実行する際に特に役に立つ。加重は、特定の待ち行列に与えられる、帯域幅の一部として記載することができる。それ故、上記加重は、ＶＰＮ間、ＶＰＮのサービス間、およびこれらサービスの種類のソース−宛先の各組間の、サービスの品質および資源割当を制御する。加重は、ルート・コントローラ１２２により計算され、各スケジューラで実行するために、ルータ１２３にダウンロードされる。
【００６３】
この点に関して、図７の計算手順を使用すれば、サブネットワークを完全に分割することができることに留意されたい。すなわち、たまたま同じリンクを共有している、任意の二つのサブネットワークの間に割り当てられた容量を、元来共有していない状態で、リンク容量をサブネットワークにより厳格に割り当てることができる。非常に驚くべきことに、完全に分割するための（損失容量における）コストは、比較的安いことが分かった。例えば、（そのいくつかのを以下に説明する）我々の実験シミュレーションにより、モデル・ネットワークの場合には、（サブネットワーク間のネットワーク資源の完全な共有に基づく、ネットワーク設計と比較することにより）呼出阻止の約２％の原因は、完全な分割によるものであることが証明された。実際の状況下では、コストは、各ＶＰＮを分離し、これらＶＰＮを他のＶＰＮによる資源の無拘束の借用から保護することにより、大きく変わる場合がある。それ故、各ＶＰＮ上のサービスの約束した品質の実際の供給がさらに保証される。
【００６４】
しかし、完全な分割を行った後で、例えば、呼出毎の現在の需要に従って、資源の一時的な借用を認めた方が、有利である場合も出てくるかも知れない。（上記借用は、例えば、幹線留保パラメータと呼ばれる、スケジュール作成（スケジューリング）加重を設定することによって実行される。）上記借用に対する種々の手順は、当業者にとっては周知のものである。例えば、１９９７年のＩＥＥＥ  ＧＬＯＢＥＣＯＭ議事録の１７８４〜１７９１ページ掲載のＤ．ミトラおよびＩ．ジーディンスの「階層的仮想分割：仮想専用網形成」およびＤ．ミトラおよびＥ．ジーディンスの「仮想分割によるネットワーク資源の共有方法」という名称の、本出願の共通譲渡の米国特許出願第０８／６４９，５０２号は、特定の例を開示している。通常、ネットワーク・ノードのところの制御素子は、要求された再割当を、あるＶＰＮから他のＶＰＮに行うことができるかどうかを判断するために、ある基準を適用する。上記基準は、例えば、影響を受けたサービスの種類、ネットワーク・リンク（または、他の物理的資源）上の現在の負荷、および借用ＶＰＮ上の現在の負荷に基づくことができる。（再割当をする決定は、資源交換機と一つまたはそれ以上の遷移交換機との間の共同作業を含むことができることに留意されたい。）
【００６５】
それ故、本発明は、最終的な目的として完全な分割を行う資源割当および経路選択手順に限定されない。それどころか、本発明の目的とする範囲は、完全な分割は中間段階であって、その後でさらに他の適応を行う手順を含む。
【００６６】
すでに説明したように、ミトラ他の文献は、呼損率および推定コストを決定するために、ＵＡＡと呼ばれる近似法の使用を記載している。本発明も、同様に、以下に説明する例示としての実施形態にＲＵＡＡと呼ぶ近似を使用している。ＵＡＡもＲＵＡＡも両方とも、ネットワーク・トラヒックの確率論的モデルに基づく、漸近近似技術の例である。当業者であれば、他のモデルも同様に使用することができ、またネットワークの複雑さ、ネットワークの容量およびトラヒック密度のある制度において、適していることを理解することができるだろう。
【００６７】
モデルの上記の一つの種類は、ある意味では、連続している流体として、ネットワーク・トラヒックを処理する決定論的流れモデルである。決定論的流れモデルは、本明細書に記載する確率論的モデルと比較すると、遙かに簡単であるが、本明細書に記載する目的を達成するために使用する場合、比較的大きな線形プログラミング問題を発生する傾向がある。これらモデルは、ノードが５００またはそれ以上の、ルータをベースとするネットワークのような、大型のネットワークを処理するのに特に有利である場合がある。決定論的流れモデルは、ソース割当手順または経路選択手順、または両方に適用することができる。
【００６８】
実際、種々のハイブリッド・アプローチが可能であり、事実、ある問題に適用した場合有利な場合がある。上記の一つのハイブリッド・アプローチの場合、最適経路選択問題の解決手段は、確率論的モデルを適用するが、提供されたトラヒックに関するリンク呼損率、およびその部分的派生物を推定するには、上記解決手段は、容量の小さいリンクを正確な技術で処理し、容量の大きいリンクを漸近近似技術により処理する。他のハイブリッド・アプローチの場合、最適経路選択問題の解決手段は、漸近近似技術を適用するが、上記解決手段は、初期の反復中にはＵＡＡを使用し、最大のネットワーク収益Ｗに収束する最終段階に対しては、ＲＵＡＡへ切り替える。それ故、ほとんどの反復に対しては、計算の複雑さが軽減するが、最後の数回の反復中にはもっと正確な収束が行われる。より高いレベルで、ハイブリッド化が行われたアプローチの場合には、最適経路選択問題を解くのに決定論的流れモデルが使用されるが、資源割当問題を解くには確率論的モデルに基づく技術が使用され、またはその逆が行われる。
【００６９】
これらの種々の代わりのアプローチおよびハイブリッド・アプローチのすべては、本発明の範囲および精神の中に含まれる。
【００７０】
本発明の例示としての実施形態の場合には、リンク容量へのサブネットワーク収益の依存性を線形化することによって、計算問題がかなり簡単になる。
【外１０】
0003789681.tif 000011
この線形化したアプローチの予想しなかった特徴は、各リンクに対するＶＰＮへの再割当を独立して行うことができるように、資源割当問題が簡単になることである。さらに、結果として得られる線形プログラミング問題へ、閉じた形の解を与えることができる。
【００７１】
もっと一般的にいうと、本発明で、非線形容量コストを線形コストの代わりに使用することができる。
非線形容量コストを使用するアプローチも、また本発明の範囲および精神に含まれる。
【００７２】
IV．本発明の例示としての実施形態
【外１１】
0003789681.tif 000012
【００７３】
図９のボックス１３０示すように、最適経路選択問題が解かれ（ボックス１３１）、リンク容量の現在値を使用して、各サブネットワークΩに対する、線形化した容量コストの計算が行われる（ボックス１３２）。この点に関して、ボックス１３０に示すプロセスの各反復において、最適経路選択の解が収束した後でだけ、線形化した容量コストの計算が行われることに留意されたい。
【外１２】
0003789681.tif 000013
【００７４】
【外１３】
0003789681.tif 000014
本発明のこの実施形態の場合には、図９に示すように、各リンクに対してプロセス１４５の別の反復が行われる。この各リンクを分解することができる能力は、部分的には、収益−最大化問題に課せられる制約により異なる。現在、本発明の制約は、全リンク容量が節約して使用されること、および各新しい容量割当は負の数値であってはならないこと、また個々に任意のリンク容量を超えてはならないことだけである。すでに説明したように、例えば、一つまたはそれ以上のサブネットワークで、指定の最低の品質のサービスを確実に行うために、他の拘束を追加することができる。例えば、拘束は、サービスの一つまたはそれ以上の種類に、一つまたはそれ以上のサブネットワークにより実行される各帯域幅が、（サービスの一つのまたは複数の種類の、関連サブネットワークに提供された、全トラヒックの指定の一部のような）指定のレベル以下にならないように指定することができる。この指定のレベルは、関連サービスの、一つまたは複数の種類で実行される、全サブネットワーク帯域幅に適用することもできるし、または指定レベルを、一つまたはそれ以上の、指定の幾組かのソース−宛先の間で実行される、帯域幅に適用することもできる。そのような場合、通常、分解は使用することができない。それ故、各リンクに対してプロセス１４５を反復する代わりに、プロセス１４５は、線形プログラミング問題、または非線形結合最適化問題のような、同時にすべてのリンクを含む問題を解く。
【００７５】
【外１４】
0003789681.tif 000015
【００７６】
【外１５】
0003789681.tif 000016
【００７７】
図１０は、最適経路選択問題を解くためのプロセスを示す、図９のボックス１３１の拡大図である。図１０に示すように、このプロセスに対して、外部から供給されたもう一つの入力は、現在のサブネットワークの各サービスの種類およびリンクの、一組の有効帯域幅ｄsl(Ω)である。図に示すように、下記の拘束を受ける現在のサブネットワークの収益を最大にするために、最適サービス−ルート・トラヒック密度が入手される。拘束とは、（ｉ）すべての許容ルートに提供された、所与のストリームの全トラヒックは、ネットワークに到着するそのストリームの全トラヒックを超えてはならない。（ii）任意の所与のルートｒに提供されるトラヒック密度ρsr(Ω)は、負の数値であってはならないという内容のものである。
【００７８】
図１１は、（本明細書においては、リンク容量に対する、ネットワーク感度とも呼ばれる）、線形化した容量コストｗl(Ω)を計算するためのプロセスを示す、図９のボックス１３２の拡大図である。図１１に示すように、第一の段階は、固定点方程式を解くための段階である（ボックス１６０）。この段階の出力は、、（現在のネットワークΩに対する）、リンクｌ提供されたサービスｓの間引きした全負荷である、ｖsl(Ω)を含む。この段階の出力は、それぞれが、（現在のネットワークΩに対する）各リンクｌ上の各サービスｓの呼損率を示す、（呼出阻止関数とも呼ばれる）リンク呼損率を含む。この段階の出力は、次の段階で、推定コストを計算するために使用され（ボックス１６５）、この推定コストは、線形化容量コストを計算するために使用される（ボックス１７０）。
【００７９】
すでに説明したように、ＲＵＡＡは、多くの場合、リンク呼損率を入手するために有利に使用される。図１２は、ボックス１７５での、この近似法のステートメントである。図１２の第二の式は、ＲＵＡＡの結果である。これは推定コストを入手するためのスタート点である。これは、損失および推定コストの計算を簡単にするためにも重要である。関数Ｂ(i) およびθ(i) および係数Ａsl(i) の定義を以下に示す。
【００８０】
リンク呼損率に対する関数Ｌs（ｄl、ｖl、Ｃl）は、当業者なら周知のものである。ＩＥＥＥトランス・コミュニケーションのＣＯＭ２９巻（１９８１）の１４７４−１４８１ページ掲載のＪ．Ｓ  カウフマン．の「共有資源環境の呼出阻止」、および国際テレトラヒック会議議事録−１０、セッション１．１、論文＃２の、Ｊ．Ｗ．ロバートの「テレコム１総合サービス・ネットワーク用のテレトラヒック・モデル」にその評価方法が記載されている。機能Ｌs のアーギュメントとしての記号ｄl は、（ｄ1l，ｄ2l、．．．、ｄsl）を表す。機能Ｌs のアーギュメントとしての記号ｖl は、（ｖ1l、ｖ2l、．．．、ｖsl）を表す。
【００８１】
図１３は、ＲＵＡＡを内蔵するように修正した、図１１のプロセスと同じプロセスである。ボックス１８０に示すように、固定点方程式を解くためのプロセスは、この場合、出力として、現在のサブネットワークに対する（以下に定義する）Ａsl(i)およびａsl(i)を含む。これら係数は、プロセス１８５中に、推定コストを計算するために使用される。プロセス１８０の出力も、また（現在のサブネットワークに対する）各リンク、およびサービス・ルート、ルートｒのすべての他のリンクにより、独立して間引きを行った後の、リンクｌに加算したサービスｓの負荷ｖsl;r(Ω)を含む。この数値は、また推定コストを計算するために使用される。
【００８２】
この図に示すように、ＲＵＡＡは、プロセス１８０とプロセス１８５の両方に含まれる。プロセス１８５の出力は、現在のサブネットワークに対する（以下に定義する）関数ξl(i)を含む。これら関数は、プロセス１９０において、線形化した容量コストを計算するために使用される。重要なことは、プロセス１８５の複雑さは、ＲＵＡＡを使用すると、サービスの種類の全数Ｓとは無関係なものにすることができるということである。このプロセスの実際の複雑さは、使用する数学的な技術による異なるけれども、ＲＵＡＡを使用する場合、推定コストを入手するための通常の複雑さのレベルはＯ（２７Ｌ3 ）である。
【００８３】
＜数学的詳細＞
１．固定点の式
ＶＰＮ指数Ωは、この節で抑制される。
サブネットワークに対する固定点方程式（ＦＰＥ）は、リンクの独立性の周知の仮定に基づいて作成される。サービスのタイプｓのトラヒックを運び、リンクｌを使用する各ルートｒは、リンクｌに負荷νsl;rを追加する。この負荷は、そのルートのすべての他のリンクによる個々の間引きにより低下する速度を持つ、ポワソンであると仮定される。リンクｌを使用するすべてのルートｒ上のνsl;rを合計することにより、リンクｌに提供された、サービスｓの間引きしたすべての負荷νslを入手することができる。Ｂslがリンクｌ上のサービスｓの呼損率を示し、ｄl＝｛ｄsl｝sであり、νl＝｛νsl｝であるとすると、Ｂsl＝Ｌs（ｄl、νl 、Ｃl ）である。この式は、複合項Ｏ（Ｃl ）により、上記のカウフマン−ロバーツ回帰法により計算することができる。別の方法としては、Ｃl ＞＞１およびνl ＝Ｏ（Ｃl ）である場合には、複合項Ｏ（１）により、またＲＵＡＡにより、Ｂslへの近似を計算することができる。いずれの場合でも、φslはこのマッピングを示す。ＦＰＥの補足的な部分は、リンク呼損率の関数としての、各リンクのところでの間引きし、提供された負荷を示す。このマッピングは、Ψで示す。完全なネットワークのＦＰＥは下記式により表される。
Ｂsl＝φsl（νl）（ｓ＝１、２、．．．、Ｓ：ｌ＝１、２、．．．、Ｌ）
ν＝Ψ（Ｂ）                              （１）
ここで、ｖは下記式により表される。
ν＝｛νl｝およびＢ＝｛Ｂsl｝
【００８４】
ＦＰＥを解くための数値技術は、多くの場合、ダンプされた逐次比較法である。最後に、ＦＰＥを解くことにより、ルートｒ上のサービスｓの呼損率Ｌsrが得られる。それ故、下記式のようになる。
【数１】
0003789681.tif 000017
【００８５】
２．ネットワーク推定コスト
ＶＰＮ指数Ωはこの節で抑制される。
下記式で示す推定コスト｛Ｃsl｝の役割の一つは、提供された負荷へのサブネットワークの感度を決定することである。
【数２】
0003789681.tif 000018
【００８６】
この式は、決定変数が｛ρsr｝の場合に、トラヒック経路選択に対する推定コストの重要性を強調している。ここで、容量コストに焦点を当てる。この場合、推定コストは、また重要な役割を演じているが、それは後で説明するが全然異なる方法で行われる。
【００８７】
｛Ｃsl｝を計算するには、ＳＬ一次方程式の一つのシステムの解を求めなければならない。
【数３】
0003789681.tif 000019
ここで、｛νl｝は、ＦＰＥ（１）を解くことにより得られる。
【数４】
0003789681.tif 000020
【００８８】
３．単一リンクの漸近近似法
ＶＰＮ指数Ωはこの節で抑制される。この節で導入される記号については、表Ａに定義する。
【００８９】
サブネットワークへ進む前に、単一リンクに対するＲＵＡＡの使用に焦点を当てる。またこの小節でリンク指数ｌを抑制する。リンク容量Ｃは大きく、トラヒック密度｛Ｖs ｝も大きく、Ｏ（Ｃ）であると仮定する。リンク上のサービスｓに対する呼損率Ｂs へのＲＵＡＡは、下記式で表される。
【数５】
0003789681.tif 000021
【００９０】
ここで、Ｂ(i)（ｉ＝１、２、３）は、ｓに依存しない。以下の二つの小節で、容量の変化による呼損率の変化を近似する必要がある。ｎ＝Ｏ（１）が正または負の整数である場合には、ＲＵＡＡは下記式で表される。
【数６】
0003789681.tif 000022
【００９１】
Θ(i)（ｎ）は、ｎの分析関数であり、Θ(i)（０）＝０、ｉ＝１、２、３である。Ｃが整数でない場合には、Ｌs （ｄ、ｖ、「Ｃ」）＝Ｌs （ｄ、ν、「Ｃ」）であるが、ｎが整数でない場合、近似法（７）を使用する。特に、式（７）をｎで割った場合で、ｎ−＞０の場合には、下記式の容量勾配が得られる。
【数７】
0003789681.tif 000023
【００９２】
ここで、σ(i)＝ｌｉｍn→0Θ(i)（ｎ）／ｎである。これらの数値は、厳密な凹関数を最小値にする一意の整数ｚ*によりはっきりと表すことができる。
【数８】
0003789681.tif 000024
【００９３】
関数Ｆ（ｚ）およびｚ*は、ＵＡＡおよびＲＵＡＡに共通のものである。式（９）のミニマイザｚ*は、二等分することにより容易に計算することができる。下記式は、後で必要になるΘ(i)に対するものである。
【数９】
0003789681.tif 000025
【００９４】
４．推定コストのＲＵＡＡ
ＶＰＮ指数Ωはこの節で抑制される。
ＦＰＥ（１）および推定コストの式（４）に対するＲＵＡＡの内容について検討する。ＲＵＡＡは、すでに説明したように、式（１）の関数φslを評価する際に使用することができる。また、式（７）から、リンク指数ｌを再度導入して、下記式が得られる。
【数１０】
0003789681.tif 000026
【００９５】
ここで、式（６）から、ａtl(i)＝Θl(i)（ｄtl）／（１−Ｂtl）。式（４）から、ＲＵＡＡ（１２）がそのサブネットワークのすべてのリンクに適用することができる場合には、推定コストは下記式に従って漸近近似法により求められる。
【数１１】
0003789681.tif 000027
【００９６】
ここで、ξl(i)は、下記式で表される。
【数１２】
0003789681.tif 000028
【００９７】
式（１４）は、｛ξl(i)｝の式の完全なシステムである。パラメータ｛Ａsl(i)｝、｛νsl;r｝および｛ａsk(j)｝は、すべてのＦＰＥ（１）を解くことにより求められる。３Ｌ一次方程式（１４）のシステムの解を求める複雑のレベルはＯ（２７Ｌ3 ）であり、一方、推定コストに対して、直接ＳＬ一次方程式（４）のシステムの解を求める複雑のレベルは、Ｏ（Ｓ3 Ｌ3 ）である。Ｓが大きい場合の、大きな利点は、サービスＳの数からの独立性性である。いずれの場合でも、リンクｌに対して適用できる場合には、式（１２）の近似法は、式（４）で使用することができる。
【００９８】
５．リンク容量に対する収益感度
ＶＰＮ指数Ωはこの節で抑制される。
リンク容量に対するサブネットワーク収益の感度に対する、ＲＵＡＡの内容について検討する。すでに説明したように、Ｃの非整数値に対するＬs（ｄ、ｖ、Ｃ）の滑らかな連続性を使用して、リンクｌの容量に関するサブネットワーク収益の対応する勾配が、下記式により表されることを証明することができた。
【数１３】
0003789681.tif 000029
【００９９】
それ故、式（８）、（１３）および（１４）から、下記式を得ることができる。
【数１４】
0003789681.tif 000030
【０１００】
要するに、大きなリンク容量Ｃlおよび同じ程度のトラヒック密度に対しては、下記式が適用される。
【数１５】
0003789681.tif 000031
【０１０１】
ここで、ｗl は、下記式により表すことができる。
【数１６】
0003789681.tif 000032
【０１０２】
この場合、σl(i)、ｉ＝１、２、３、は、ｚ*の代わりにｚl*を使用することにより、式（１０）および（１１）で表される。また、ξl(i)は、式（１４）の３Ｌ一次方程式のシステムの解を求めることにより、得ることができる。
数値ｗlを線形化容量コストと呼ぶことにする。
【０１０３】
６．アルゴリズムの数学的基礎
式（１７）に注目して、それを各リンクｌ上のそれに割り当てられた帯域幅Ｃl(Ω)を持つサブネットワークΩに適用することにより、サブネットワークに対する収益の線形化外挿は下記式で表される。
【数１７】
0003789681.tif 000033
【０１０４】
この場合、Ｗl(Ω)（ｌ＝１、２、．．．、Ｌ）は、式（１８）により得られる線形化容量コストであり、整数ｎl(Ω)は、現在の容量割当を修正するための候補である。後者の数値は、適応する式（１９）に対してＯ（１）でなければならない。
【０１０５】
Ｃ(Ω)は、（Ｃl(Ω)、．．．、ＣL(Ω)）として定義され、ｎ(Ω)は、（ｎl(Ω)、．．．、ｎL(Ω)）として定義される。また、Ｃは、｛Ｃl(Ω)｝として定義される。
【０１０６】
ネットワーク収益がサブネットワーク収益の合計であるために、下記式のようになることに留意されたい。
【数１８】
0003789681.tif 000034
【０１０７】
Ｗ（Ｃ−ｎ）を最大にするようなｎの選択に進む。すなわち、下記式を参照されたい。
【数１９】
0003789681.tif 000035
【０１０８】
第二の拘束は、新しい容量割当は負の数値であってはならず、それぞれ、任意のリンク容量を超えることができないという要件を単に反映しているに過ぎない。
二つのステップが行われる。これは全く個人的な見解だが、コスト関数の線形構造が与えられ、リンクによる拘束が分離できる場合には、第一のステップは、式（２１）は、各リンクに対する一つずつという形で、Ｌ個の問題に分解されるようにする。すなわち、下記式を使用した場合、
【数２０】
0003789681.tif 000036
【０１０９】
ｌ（ｌ＝１、２、．．．、Ｌ）で表される問題は、下記式で表される。
【数２１】
0003789681.tif 000037
【０１１０】
式（２３）においては、式（１９）の近似が無効になるほど決定変数が、さらに、決して大きくならないように、第二の拘束（２１）は厳しいものになっている。
【数２２】
0003789681.tif 000038
【０１１１】
ここで、定数（ｃｏｎｓｔ）の合理的な数値は、約０．５である。以下に説明するステップにおいて、最適な解、すなわち、新しい容量割当が整数値になるように、上記境界を確実に整数値になるようにすることが重要である。下記式に留意されたい。
【０１１２】
Ｃl(Ω)＞０の場合には、下記式のようになる。
【数２３】
0003789681.tif 000039
【０１１３】
式（２３）のプログラミング問題の検討へ進み、明らかな解を示す。この場合、下付き文字ｌは、余分なものなので、表記を簡単にするためにｌを削除する。また、下記式の一般的な損失はないものと仮定する。
【数２４】
0003789681.tif 000040
【０１１４】
すなわち、サブネットワークｌは「最も安いもので」で、サブネットワーク−Ωは「最も高いもの」である。以下同じ。それ故、Ω1＜Ω2の場合には、同じ量だけｎ(Ω2)が減少し、ｎ(Ω1)が増大すると、何時でも目的関数は減少する。それ故、式（２３）の解は、グローバルな拘束Σｎ(Ω)＝０が満足するように、ｉの小さな数値をもつ最大化するｎ(i)と、ｉの大きな数値を持つ最小化ｎ(i)からなる。
【０１１５】
すこし考えれば、式（２６）および（２７）により、下記式のような一意のサブネットワーク指数Ｉが存在することが分かる。
【数２５】
0003789681.tif 000041
【０１１６】
【外１６】
0003789681.tif 000042
【数２６】
0003789681.tif 000043
【表１】
0003789681.tif 000044
【０１１７】
＜例＞
上記方法に基づく計算上の実験の結果について簡単に説明する。図１の下部構造ネットワークは、八つのノードと、両方向に１０組のノードを接続している、２４のＯＣ３リンクを含む。六種類のサービスがあり、個々の呼出の有効帯域幅は、すべてのリンク上において、それぞれ、１６、４８、６４、９６、３８４および６４０Ｋｂｐｓである。
【０１１８】
ウェスト・コーポレーション、ミッドウェスト・コーポレーション、イースト・コーポレーションおよびサウス・コーポレーションに対して四つのＶＰＮが存在する。これらコーポレーションは、各サービスに対して各ノードから各ノードへのトラヒックを含み、その名称に対応する地理上の地域内の、ノードへまたノードからのある程度の重要性を示す、個々のコーポレーションに対するトラヒック・パターンを持つ、国内の顧客である。許容ルートは、そのルートに最大四つのホップを持つようなルートである。
【０１１９】
表Ｉは、最適化した設計に対するＶＰＮ上の提供され、実行された帯域幅の要約である。特に重要なことは、ＶＰＮに対する呼出阻止に有意な変動がないことである。
【表２】
0003789681.tif 000045
【０１２０】
上記結果を、ＶＰＮ構造が除去され、総計トラヒックが最適に経路選択される、完全共有設計により得られる結果と比較する。完全共有の解の実行された帯域幅の合計は、７３，７９５である。これは１．２％の呼出阻止を示す。それ故、ＶＰＮの間での資源分割により、呼出阻止は約１８．５％増大する。
【０１２１】
表IIの場合には、リンク２０．２（図１参照）を考慮の対象とし、最適化した設計でＶＰＮに容量の割当を行う。
【表３】
0003789681.tif 000046
【０１２２】
１０-3の収束域値にＤ適合するために必要な外部反復は、１０回だけであった。表IIIは、偶数回の反復の後での、実行帯域幅の合計を示す。完全な共有解に基づく、ＶＰＮ設計である、初期設計の適合度に特に注目されたい。
【表４】
0003789681.tif 000047
【図面の簡単な説明】
【図１】例示としての通信ネットワークの略図である。
【図２】多重サービス・ネットワークの最適経路選択問題を解決するためのミトラ他の方法のフローチャートである。
【図３】呼損率およびネットワーク感度を決定する際に含まれる他のステップを示す図２のフローチャートの拡大詳細図である。
【図４】固定点の式を示す図３の拡大詳細図である。
【図５】図３の手順と一緒に使用することができる均一漸近近似法（ＵＡＡ）の図である。
【図６】ＵＡＡおよび図３の手順との間の相互作用を示す略図である。
【図７】本発明のある実施形態の最適経路選択および最適帯域幅割当の複合問題を解決するためのプロセスのフローチャートである。
【図８】本発明を実行する際に役に立つ、通常のネットワーク交換機の簡単なブロック図である。
【図９】図７のプロセスの詳細なフローチャートである。
【図１０】複数のサブネットワークをサポートする多重サービス・ネットワークの最適経路選択問題を示す図９のフローチャートの拡大詳細図である。
【図１１】線形化した容量コストを計算するためのプロセスを示す図１０のフローチャートの拡大詳細図である。
【図１２】図１１の手順と一緒に使用することができる改良形均一漸近近似法（ＲＵＡＡ）の図である。
【図１３】ＲＵＡＡを内蔵するように修正した図１１のプロセスのフローチャートである。
【図１】
0003789681.tif 000048
【図２】
0003789681.tif 000049
【図３】
0003789681.tif 000050
【図４】
0003789681.tif 000051
【図５】
0003789681.tif 000052
【図６】
0003789681.tif 000053
【図７】
0003789681.tif 000054
【図８】
0003789681.tif 000055
【図９】
0003789681.tif 000056
【図１０】
0003789681.tif 000057
【図１１】
0003789681.tif 000058
【図１２】
0003789681.tif 000059
【図１３】
0003789681.tif 000060