(57)【要約】【課題】ネットワーク内の第１点とネットワーク内の第２点をつなぐリンクの保護パスウェイのプロビジョニングの方法および装置を提供すること。【解決手段】この方法には、保護グラフ内で第１点と第２点との間の最短パスを判定する工程と、前記最短パスの長さを計算する工程と、前記計算された長さに従って保護グラフに前記リンクを追加しなければならないかどうかを判定する工程と、前記リンクの保護パスとして保護グラフ内の最短パスをセットする工程とが含まれる。判定する第２工程に、既存パスがないまたはホップ限度より長い既存パスがあるかどうかを判定するために保護グラフを評価することが含まれる。この評価に基づいて、この方法は、リンクを追加するか、保護グラフに変更を行わないかのいずれかを行う。【選択図】図２
2006191596.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内の第１点と前記ネットワーク内の第２点とをつなぐリンクのホップ制限された保護パスウェイのプロビジョニングの方法であって、
（ａ）保護グラフ内で前記第１点と前記第２点との間の最短パスを判定する工程と、
（ｂ）前記最短パスの長さを計算する工程と、
（ｃ）前記計算された長さに従って前記保護グラフに前記リンクを追加しなければならないかどうかを判定する工程と、
（ｄ）前記リンクの保護パスとして前記保護グラフ内の前記最短パスをセットする工程と
を含む方法。
【請求項２】
前記保護グラフに前記リンクを追加しなければならないかどうかを判定する前記工程が、既存パス無しおよびホップ限度より長い既存パスからなる群から選択されたパスがあるかどうかを判定するために前記保護グラフを評価することをさらに含む、請求項１に記載の方法。
【請求項３】
既存パスがない場合または前記ホップ限度より長い既存パスがある場合に、前記リンクが既存保護パスウェイの集合に追加される、請求項２に記載の方法。
【請求項４】
前記ホップ限度より短い既存パスがある場合に、前記保護グラフに対する変更が行われない、請求項２に記載の方法。
【請求項５】
複数のリンクによって相互接続された複数のノードを有するネットワーク内でホップ制限された保護パスウェイをプロビジョニングする方法であって、
（ａ）前記複数のノードの間の複数のパスを含むスパナを計算する工程と、
（ｂ）前記スパナ内の前記複数のパスのそれぞれを定義するすべてのリンクを、前記複数のノードの間の保護パスウェイ専用にする工程と、
（ｃ）残りのすべてのリンクを、前記複数のノードの間の作業パスウェイ専用にする工程と
を含む方法。
【請求項６】
前記スパナが、ノードのすべての対の間の最短パスの長さが多くともグラフＧの最短パスの長さのｔ倍である前記グラフＧの部分グラフである、請求項５に記載の方法。
【請求項７】
前記第１点と前記第２点の間の前記最短パスを計算する前に複数のサブネットワークを作成するために前記第１点と前記第２点とをつなぐ前記リンクを複数の平行サブリンクに分割する工程をさらに含む、請求項１に記載の方法。
【請求項８】
ネットワーク内の第１点と前記ネットワーク内の第２点とをつなぐリンクの保護パスウェイのプロビジョニングの装置であって、
保護グラフ内で前記第１点と前記第２点との間の最短パスを判定する手段と、
前記最短パスの長さを計算する手段と、
前記保護グラフに前記リンクを追加しなければならないかどうかを判定する手段と、
前記リンクの保護パスとして前記保護グラフ内の前記最短パスを設定する手段と
を含む装置。
【請求項９】
前記保護グラフに前記リンクを追加しなければならないかどうかを判定する前記手段が、既存パス無しおよび前記第１点と前記第２点との間の前記リンクより長い既存パスからなる群から選択されたパスがあるかどうかを判定するために前記保護グラフを評価する、請求項８に記載の装置。
【請求項１０】
前記第１点と前記第２点の間の前記最短パスを計算する前に複数のサブネットワークを作成するために前記第１点と前記第２点とをつなぐ前記リンクを複数の平行サブリンクに分割する手段をさらに含む、請求項８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークのプロビジョニング（ｐｒｏｖｉｓｉｏｎｉｎｇ）の方法および装置に関し、具体的には、２つのネットワーク位置の間のリンクを保護するのに必要な帯域幅の量を判定する方法および装置に関する。
【背景技術】
【０００２】
サービス・プロバイダは、音声アプリケーションおよびビデオ・アプリケーションを単一のパケット・ベース・ネットワークに統一することがますますコスト効率的であることに気付きつつある。この統一の成功は、そのようなタイプのトラフィックを搬送するのに従来使用されてきたネットワークの代わりに個々のアプリケーションに必要なサービス品質（ＱｏＳ）保証を提供する能力を条件とする。リアル・タイム・アプリケーションについて、これは、厳密な帯域幅保証、エンド・ツー・エンド遅延保証、ジッタ保証、およびロス・レート（ｌｏｓｓ  ｒａｔｅ）保証に置き換えられる。たとえば、Ｖｏｉｃｅ  ｏｖｅｒ  ＩＰ（ＶｏＩＰ）およびビデオ会議などのアプリケーションは、エンド・ツー・エンド遅延、ジッタ、およびパケット・ロス・レートを最小限に保ちながら最大の可能な帯域幅を必要とする。より短いエンド・ツー・エンド遅延は、より満足で自然な感じの会議経験をもたらし、逆に、長い遅延値は、句または文の間の長い一時停止を伴う不自然な会話をもたらす。大きいジッタ値（遅延変動）は、がくがくしたビデオまたはどもり、急に動くオーディオをもたらす可能性がある。大きいジッタ値は、遅延場ジェットを超えたのでパケットが捨てられることももたらす可能性がある。許容可能な限度を超えるパケット・ロスは、さらに、クリッピングおよびスキップに起因する音声およびビデオの低い品質をもたらす。現在の「ベスト・エフォート」データ・ネットワークでは、ルータおよびスイッチ・バッファが、すばやく満杯になり、遅延およびパケット・ロスをもたらす傾向がある。パケットに関するこれらの遅延、遅延ジッタ、およびロスの確率値は、ネットワーク内でトラバースされるホップごとに累算される。
【０００３】
ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  ｓｅｒｖｉｃｅの枠組みでは、これらの影響が、リアルタイム・セッションに属するパケットをマークして、各ネットワーク・ノードで優先的な転送の扱い、またはホップごとの挙動を受けることによって軽減される。しかし、ある種の優先順位キューイングおよびスケジューリング（たとえば、Ｄｉｆｆｓｅｒｖの）がリアル・タイム・トラフィックに使用される時であっても、ＱｏＳ要件はキー・パラメータに依存する。そのようなパラメータに、そのようなトラフィックがルーティングされるネットワーク・ホップ数が含まれる。優先順位キューイングがビデオ・トラフィックに使用される時であっても、低帯域幅リンク（サブ１０Ｍｂｐｓリンク）での非音声パケットの伝送遅延に起因して、キューイング遅延が、５ホップ長パスであってもかなり大きくなる可能性がある。
【非特許文献１】「Constructing Maximal Dynamic fbws from Static fbws」、Ford and Fulkerson、Operations Research 6:419-433、1958年
【発明の開示】
【発明が解決しようとする課題】
【０００４】
データ・トラフィックのルーティングに使用されるパスのホップ数の最小化は、光ネットワークの信号品質劣化の最小化など、他の文脈でも重要である。信号は、複数のホップを移動する際に、弱くなり、ホップ数が多すぎる場合には再生成が必要になる可能性がある。これは、高コストの光−電気−光（ＯＥＯ）コンバータを必要とする場合がある。さらに、ＭＰＬＳおよび光ネットワークで、高速復元を、事前にセットアップされた迂回パスを使用してローカルに故障の回りでルーティングすることによって達成することができる。たとえば、ｆａｓｔ  ｒｅｒｏｕｔｅサポートまたはｌｏｃａｌ  ｒｅｒｏｕｔｅサポートと称するＭＰＬＳ高速復元機構は、ｌｏｃａｌ  ｒｅｐａｉｒ機能性をサポートする。ノード故障またはリンク故障の際に、故障の上流の第１ノードが、もたらされたＬａｂｅｌ  Ｓｗｉｔｃｈ  Ｐａｔｈ（ＬＳＰ）を同等の保証された帯域幅を有するバイパス（バックアップ）トンネルに再ルーティングして、故障点をバイパスする。したがって、ＬＳＰの新しいパスのホップ数は、オリジナル・パスの長さと故障したリンクまたはノードのバイパス・トンネルの長さに直接に関係する。再ルーティングされたパスのホップ数は、悪い設計のネットワークではすぐに多くなる可能性がある。したがって、故障からのすばやい復元を保証するだけではなく、再ルーティングされたパスのホップ・カウントの著しい増加がないことも保証する効果的な復元方式が必要である。
【課題を解決するための手段】
【０００５】
従来技術のさまざまな欠陥は、ネットワーク内の第１点とネットワーク内の第２点をつなぐリンクの保護パスウェイのプロビジョニングの方法という本発明によって対処される。この方法には、保護グラフ（ｐｒｏｔｅｃｔｉｏｎ  ｇｒａｐｈ）内で第１点と第２点との間の最短パスを判定する工程と、前記最短パスの長さを計算する工程と、前記計算された長さに従って保護グラフにリンクを追加しなければならないかどうかを判定する工程と、前記リンクの保護パス（ｐｒｏｔｅｃｔｉｏｎ  ｐａｔｈ）として保護グラフ内の最短パスをセットする工程とが含まれる。
【０００６】
保護パスウェイを作成するために複数の迂回パスを有するシナリオでは、この方法に、第１点と第２点の間の最短パスを計算する前に複数のサブネットワークを作成するために第１点と第２点とをつなぐリンクを複数の平行サブリンクに分割する工程が含まれる。そのようなサブリンクは、リンク容量と、プロビジョニング処理中に前に検討された総作業容量に対する前に検討されたリンクの総容量を表す比とに従ってソートされる。
【０００７】
さらに、本発明には、ネットワーク内の第１点とネットワーク内の第２点をつなぐリンクの保護パスウェイのプロビジョニングの動作を実行する装置であって、保護グラフ内で第１点と第２点との間の最短パスを判定する手段と、最短パスの長さを計算する手段と、保護グラフにリンクを追加しなければならないかどうかを判定する手段と、前記リンクの保護パスとして保護グラフ内の最短パスをセットする手段とを含む装置が含まれる。
【０００８】
本発明の教示は、添付図面と共に次の詳細な説明を検討することによってたやすく理解することができる。
理解を容易にするために、可能な場合には、複数の図面に共通する同一の要素を指すのに同一の符号を使用した。
【発明を実施するための最良の形態】
【０００９】
図１に、本発明が動作し、存在する例示的なデータ・ネットワーク１００を示す。データ・ネットワーク１００に（とりわけ）、複数のリンク１０４ｍによって相互接続された複数のノード１０２ｎが含まれる。図からわかるように、開始ノード１０２１から終了ノード１０２２にデータを転送する、複数の定義されたパスウェイ（１つまたは複数のリンク１０４１および１０４２によって定義される）が存在し得る。しかし、そのようなデータ・ネットワーク１００は、リンク故障およびルータ故障（たとえば、アンダーバッファリング（ｕｎｄｅｒｂｕｆｆｅｒｉｎｇ）、一般的な故障、および類似物）をこうむりやすく、これらの故障は、サポートされる音声アプリケーションおよびビデオ・アプリケーションの品質に悪影響を及ぼす。そのような故障は、データ・セッションが長いパスで再ルーティングされる場合に複合する可能性があり、これは、再ルーティング中の遅延ジッタに影響するだけではなく、再ルーティング後のエンド・ツー・エンド遅延および遅延ジッタにも悪影響を及ぼす可能性がある。本発明は、これらのネットワークでリアル・タイム・トラフィックをサポートするために、ネットワーク故障が発生した時にホップ長が制限されることを保証する方法および装置を提供する。
【００１０】
具体的にいうと、例示的ネットワーク１００は、バイパス・トンネルのホップ・カウントに対するユーザ指定の限度をすべての可能なリンク故障について保証するのに必要な保護容量の量を判定するために分析される。設計問題を、ＭＰＬＳおよび光ネットワークの高速のまたはローカルな再ルーティング機構の文脈で提示するが、この解決策は、他のタイプのネットワークに適用することができる。そのようなネットワークは、異なるリンクの保護に使用されるバイパス・トンネルの間で保護容量を共用することによって、保護容量を効率的に利用する。計算的に高速であり、将来のトラフィック需要と独立であるという追加の利益を有し、リンクごとの基礎での作業容量および保護容量へのネットワーク容量の先験的区分をもたらす事前区分モデル（保護容量およびバイパス・トンネルを事前に予約して、動的方式の複雑さおよびシグナリング・オーバーヘッドの多くを減らす）を提示する。その結果、ネットワークでのＱｏＳ保証されたトラフィックのオンライン・ルーティングは、すべてのデータ・セッションを、ネットワークの作業容量部分で、復元考慮事項に完全に明白に、保護されない形で最適にルーティングすることができる（たとえば、最小ホップ長のパスを介して）という点で非常に単純化される。故障の場合に、十分な保護容量が判定され、事前に計算されたバイパス・トンネルが、再ルーティングされたトラフィックを搬送するのに使用可能である。使用されてない時に、予約された保護容量を使用して、リアル・タイム・トラフィックによって先取りできる低優先順位非リアルタイム・トラフィックを搬送することができる。
【００１１】
さらなる分析では、ネットワーク１００を、能力を与えられたネットワークＧ＝（Ｖ；Ｅ）と考え、Ｖは、ｎ個のノードの集合であり、Ｅはｍ個のリンクの集合である。リンクは、能力を与えられ、リンクｅ∈Ｅは、容量ｕ（ｅ）を有する。提示を簡単にするために、ネットワーク１００が、無向であり、平行リンクがなく、リンク容量が整数であると仮定する。ホップ制約ｒ≧２が、バイパス・トンネルの長さに課せられ、分割係数ｋ≧１である。問題は、各リンクｅ∈Ｅの容量ｕ（ｅ）を作業容量ｗ（ｅ）≦ｕ（ｅ）および保護容量ｐ（ｅ）＝ｕ（ｅ）−ｗ（ｅ）に区分して、リンクの保護容量だけを使用することと、それぞれが多くともｒホップの長さの多くともｋ個のバイパス・トンネル（故障したリンクをバイパスするため）だけを使用することによって、保護に使用される帯域幅の総量（Σｅｐ（ｅ））を最小にするという目標の下で、リンク復元（単一のリンク故障に対する）を保証することである。さらに、保護容量を、異なるリンクに関連するバイパス・トンネルの間で共用できると仮定する。
【００１２】
Ｂ（ｅ）が、リンクｅのバイパス・トンネルの集合を表すものとする。上で提示された問題に対する実現可能な解は、次の条件を満足する。
１）リンクｅの故障の際に、その最大サービス・トラフィック（ｗ（ｅ）＝ｕ（ｅ）−ｐ（ｅ）である）を、そのバイパス・トンネルＢ（ｅ）のリンクで予約された保護容量だけを使用することによって、リンクｅから外して再ルーティングすることができる。このトラフィックのパスに、リンクｅを有しないオリジナル・パスをＢ（ｅ）に含まれるバイパス・トンネルのそれぞれに連結することによって得られる｜Ｂ（ｅ）｜個のパスの集合が含まれる。したがって、トラフィックは、そのオリジナル・パスのリンク（リンクｅを除く）の作業容量を使用し、Ｂ（ｅ）に含まれるリンクの保護容量を使用する。
２）すべてのリンクｅについて｜Ｂ（ｅ）｜≦ｋであり、Ｂ（ｅ）の各トンネルは、長さがｒホップを超えない。
３）総保護容量Σｅｐ（ｅ）が最小化される。
【００１３】
本発明の１つの方法（第１方法）は、ネットワークが最小限のホップ長を有して完全にリンク保護されることを保証するために、事前にプロビジョニングされる保護容量の総量を最小にし、事前にインストールされるバイパス・トンネルの集合を計算するという問題に関する高速近似アルゴリズムを提供する。具体的にいうと、より大きいグラフＧのｔ−スパナ（ｓｐａｎｎｅｒ）Ｇ’（または保護グラフ）は、ノードの任意の対の間の最短パスの長さが、多くともＧの最短パスの長さのｔ倍である、Ｇの部分グラフである。このアルゴリズムは、ｒ−スパナ・グラフＧ’を見つけ、全保護容量をＧ’のリンクに割り当てる。残りのリンクのすべてが、全作業容量を有する。このアルゴリズムは、正の作業容量を有するすべてのリンクが、多くともｒホップの保護パスを有することを保証する。
【００１４】
次では、距離メトリックが、リンクｅ＝（ｕ，ｖ）のホップ・カウントであり、ｕが開始ノード１０２１、ｖが終端ノード１０２４であると仮定する。関数Ｐ（ｕ，ｖ）は、ｕからｖへの最短パスを表し、関数ｌｅｎｇｔｈ（Ｐ（ｕ，ｖ））は、Ｐ（ｕ，ｖ）のリンクの個数を表す。ｕとｖの間にパスがない場合には、ｌｅｎｇｔｈ（Ｐ（ｕ，ｖ））は∞である。本発明の一実施形態では、この第１方法が、ＭＡＸＨＯＰと識別され、そのように記述され、次のように説明される。
入力：グラフＧ＝（Ｖ，Ｅ）およびｒ−保護パスの最大ホップ数。｛ｅ１，ｅ２，…，ｅｍ｝が、リンク容量（ｕ（ｅ））の非昇順でソートされたリンクであるものとする。
Ｇ’＝φ
ｆｏｒ  ｉ＝１，…，ｍ  ｛
ｅｉ＝（ｕ，ｖ）であるものとする。
Ｇ’でのｕからｖへの最短パスＰ（ｕ，ｖ）を計算する。
ｉｆ  （ｌｅｎｇｔｈ（Ｐ（ｕ，ｖ））＞ｒ）  ｛
Ｇ’＝Ｇ’∪｛ｅｉ｝
ｐ（ｅｉ）＝ｕ（ｅｉ），  ｗ（ｅｉ）＝０
｝  ｅｌｓｅ  ｛
ｐ（ｅｉ）＝０，  ｗ（ｅｉ）＝ｕ（ｅｉ）
｝
｝
ｒｅｔｕｒｎ  Ｇ’
このアルゴリズムの近似比率が、バイパス・トンネルがとることのできる最大ホップ長に依存することに留意されたい。許容可能なホップ長が長いほど、このアルゴリズムの効率が高くなる。
【００１５】
図２に、一連のステップ２００として、保護パスウェイを計算する第１方法（ＭＡＸＨＯＰ）を示す。具体的にいうと、この方法は、ステップ２０２で開始され、ステップ２０４に進み、ここで、ネットワーク内の第１点または第１ノードｕとネットワーク内の第２点または第２ノードｖの間のリンクを、容量の非昇順でソートし、最短パスＰを保護グラフ内で検索する。リンクｎは、第１点ｕおよび第２点ｖによって定義される。第１点と第２点の間の最短パスを検索したならば、この方法は、ステップ２０６に移動し、ここで、第１点ｕと第２点ｖの間のこの最短パスＰの長さＬを計算する。この長さ計算を完了したならば、この方法は、ステップ２０８に移動して判断を行う。具体的にいうと、保護グラフにパスがないか、識別されたリンクｎの長さｒ（ホップ限度）より長い既存パスが保護グラフにあるかどうかに関する質問を行う。パスがないまたは既存パスがｒより長い場合には、ステップ２０４で検索した最短パスＰを、ステップ２１２で保護グラフに追加する。ステップ２０８の回答が否定の場合には、この方法はステップ２１０に移動し、保護グラフに対する変更を行わない。
【００１６】
保護グラフにパスを追加するか否かの判断（ステップ２１０または２１２のいずれか）を行ったならば、この方法はステップ２１４に移動し、ここで、評価すべきリンクｎがまだあるかどうかに関する判断を行う。評価すべきリンクがまだある場合には、この方法は、ステップ２０４にループ・バックして、新しいリンクｎの新しい最短パスＰを検索する。評価すべきリンクがもうない場合には、この方法はステップ２１６に移動し、ここで、保護グラフの最短パスを、所与のリンクの保護パスウェイとしてセットするか、それ専用にする。
【００１７】
アルゴリズムＭＡＸＨＯＰは、再ルーティングされるサービス・トラフィックを複数の迂回パスに分割することを許容しない。アルゴリズムＭＡＸＨＯＰは、保護にリンク容量のすべてを割り振るか、全く割り振らないかのいずれかである。したがって、使用可能なリンク容量の一部を保護のために予約することを可能にし、ユーザ指定パラメータｋについて、リンクごとに多くともｋ個の迂回パスを可能にする第２アルゴリズムを提供する。本質的に、第２アルゴリズムは、ネットワークをｋ個のサブネットワークに分割し、各個々のネットワークで第１アルゴリズムを実行する。各実行の出力を組み合わせることによって、リンクごとにｋ個までの保護パスがもたらされる。ネットワーク分割には、各リンクをより小さい容量の複数の平行リンクに置換（分割）することが用いられる。
【００１８】
具体的にいうと、Ｕ＝ｍａｘｅ∈Ｅｕ（ｅ）／ｋであるものとする。各リンクは、その総容量が合計でｕ（ｅ）になるように、多くとも１つのリンクがＵ未満の容量であることを除いて、容量Ｕの複数のリンクに分割される。たとえば、リンクｅｉについて、（ｓ−１）Ｕ＜ｕ（ｅｉ）≦ｓＵである場合に、ｅｉは、ｓ個のリンクｅｉ１，ｅｉ２，…，ｅｉｓに分割される。最初のｓ−１個のリンクの容量はＵであり、リンクｅｉｓは、容量ｕ（ｅｉ）−（ｓ−１）Ｕを有する。したがって、ｋ個のサブネットワークが作成される。サブネットワークｊに、すべてのリンクｅｉが含まれ、ｕ（ｅｉ）≧（ｊ−１）Ｕである。具体的にいうと、そのようなリンクｅｉについて、リンクｅｉｊがサブネットワークｊに追加される。第２アルゴリズムは、すべてのサブネットワークについて、サブネットワークｋからサブネットワーク１まで反復する。ｐ’（ｅｉ）が、これまでにこのアルゴリズムによって検討されたリンクｅｉ１，ｅｉ２，…に割り当てられた保護の総量であるものとする。同様に、ｕ’（ｅｉ）が、これまでに検討されたｅｉ１，ｅｉ２，…の間のリンクの総容量であるものとする。次に、ｗ’（ｅｉ）＝ｕ’（ｅｉ）−ｐ’（ｅｉ）と定義し、ｐｒｏｔｅｃｔ（ｅ；ｅ’）が、ｅが故障した時にリンクｅを保護するためにリンクｅ’で予約された保護容量の量であるものと定義する。
【００１９】
本発明の一実施形態で、この第２方法が、ＭＡＸＨＯＰ−ＳＰＬＩＴと識別され、そのように記述され、次のように説明される。
入力：グラフＧ＝（Ｖ，Ｅ）、ｋ−保護パス数の限度、ｒ−保護パス・ホップ限度。
｛ｅ１，ｅ２，…，ｅｍ｝がリンクであるものとし、これらのリンクをｅｉｊに分割する。
すべてのリンクｅｉについて、ｐ’（ｅｉ）；ｕ’（ｅｉ）に０をセットする。
リンクのすべての対（ｅ，ｅ’）について、ｐｒｏｔｅｃｔ（ｅ，ｅ’）に０をセットする。
Ｆｏｒ  ｊ  ＝  ｋ  ｄｏｗｎｔｏ  １  ｛
１）ネットワークｊのすべてのリンクｅｉｊを、主キーとしてｕ（ｅｉｊ）、副キーとして
【数１】
2006191596.tif 000003
を用いて降順でソートする。
２）Ｅ（ｅｉ）が、ｐ’（ｅ’）−ｐｒｏｔｅｃｔ（ｅｉ，ｅ’）≧ｕ（ｅｉｊ）であるリンクｅ’の集合であるものとする。
３）Ｇ（ｅｉ）＝（Ｖ，Ｅ（ｅｉ））であるものとする。
４）ネットワークｊに対してＭＡＸＨＯＰを実行するが、リンクｅｉｊ＝（ｕ，ｖ）のパス計算Ｐ（ｕ，ｖ）は、Ｇ（ｅｉ）のリンクを使用して行われる。
５）Ｆｏｒ  すべてのｅｉｊ＝（ｕ，ｖ）∈ネットワークｊ  ｛
ｕ’（ｅｉ）＝ｕ’（ｅｉ）＋ｕ（ｅｉｊ）
ｐ’（ｅｉ）＝ｐ’（ｅｉ）＋ｐ（ｅｉｊ）  （すなわち、ＭＡＸＨＯＰによって割り当てられた保護容量）
Ｐ（ｕ，ｖ）のすべてのリンクｅ’について、ｐｒｏｔｅｃｔ（ｅｉ，ｅ’）＝ｐｒｏｔｅｃｔ（ｅｉ，ｅ’）＋ｕ（ｅｉｊ）
｝
｝
すべてのｅｉ∈Ｅについて、ｐ（ｅｉ）＝ｐ’（ｅｉ）
【００２０】
この第２アルゴリズムは、同一の容量を有するリンクを（ｕ（ｅｉｊ）＋ｗ’（ｅｉ））／（ｕ（ｅｉｊ）＋ｕ’（ｅｉ））の降順でソートする。これは、全作業容量がこの反復で置かれると仮定するならば、これまでの総容量に対する作業容量の比である。このアルゴリズムは、リンクの間での保護容量の割振りの共用および負荷平衡化のために、この作業容量比のより高い値を有するリンクに保護容量を追加することを優先する。そうでなければ、ＭＡＸＨＯＰ−ＳＰＬＩＴは、すべての反復にまたがって同一の順序でリンク（その分割されたリンク）を検討し、すべてのリンクにまたがる保護容量の割振りの平衡化という目的をくつがえす。
【００２１】
ＭＡＸＨＯＰ−ＳＰＬＩＴが、以前の反復の保護帯域幅を再利用するためのある最適化と共に、サブネットワークごとにＭＡＸＨＯＰを実行することに留意されたい。このアルゴリズムが、これらの最適化なしでも正しいことを示すことができる。最適化ステップは、単に、検討中のリンクｅｉが前のステップでリンクｅ’の保護容量を使用しなかった（すなわちｐ’（ｅ’）−ｐｒｏｔｅｃｔ（ｅｉ；ｅ’）≧ｕ（ｅｉｊ））場合に限って、前のステップのリンクｅ’の保護容量を使用する。したがって、このアルゴリズムは、最適化がある場合であっても実現可能な解を返す。
【００２２】
このアルゴリズムに関して、各リンクｅｉ＝（ｕ，ｖ）のバイパス・トンネルは、ＭＡＸＨＯＰが、リンクｅｉｊを検討する時にネットワークｊのリンクｅｉｊを保護するのに使用できるｒホップのパスＰ（ｕ，ｖ）を見つけたすべてのパスＰ（ｕ，ｖ）の和集合である。ＭＡＸＨＯＰが、ｅｉｊごとにｋ回まで実行されるだけなので、リンクｅｉごとに多くともｋ個のそのようなＰ（ｕ，ｖ）があることに留意されたい。
【００２３】
図３Ａ、Ｂに、一連のステップ３００として、保護リンク・パスウェイの計算および利用の第２方法（ＭＡＸＨＯＰ−ＳＰＬＩＴ）を示す。具体的にいうと、この方法は、ステップ３０２で開始され、ステップ３０４に進み、ここで、ネットワーク内の複数のリンクｅｍをｓ個の平行リンクｅｉｊに分割して、Ｋ個のサブネットワークを作成する。次に、この方法はステップ３０６に進み、ここで、所与のサブネットワーク内のリンクｅｉｊのすべてを、上で説明したように、リンク容量と、そのようなリンク容量および前に検討した容量の比とに従ってソートする。具体的にいうと、本発明の一実施形態で、ソートは、容量の降順で行われ、比は、既に検討された総容量に対する作業容量である。
【００２４】
すべてのリンクｅｉｊをソートし終えたならば、この方法はステップ３０８に進み、そこで、図２の方法ステップ２００として識別された処理ＭＡＸＨＯＰを呼び出し、保護容量値を、平行リンクｅｉｊのそれぞれについて判定する。平行リンクのすべての値を判定し終えたならば（方法２００の呼び出しを介して）、方法３００はステップ３１０に進んで、保護容量の最終計算を実行する。具体的にいうと、すべてのリンクｅｉｊについて、検討された総容量をｅｉの総容量に加算し、検討された総保護容量を、ｅｉの総保護容量に加算する。さらに、ｅｉｊの作業容量を、Ｐ（ｕ，ｖ）の所与のリンクｅ’のリンクｅのために予約された保護容量の量に加算する。
【００２５】
加算を実行したならば、この方法はステップ３１２に移動し、そこで、第１の照会を提示して、サブネットワーク内のすべてのリンクを検討し終えたかどうかを判定する。そうでない場合に、方法３００はステップ３０８にループ・バックして、上で説明した方法２００のステップに従って別のリンクを処理する。サブネットワーク内のすべてのリンクを検討し終えた場合には、この方法はステップ３１４に進み、そこで、第２の照会を提示して、サブネットワーク「ｋ」のすべてを検討したかどうかを判定する。そうでない場合には、この方法はステップ３０６にループ・バックして、新しいサブネットワークのリンクをソートする。すべてのサブネットワーク「ｋ」を検討し終えたならば、この方法はステップ３１６で終了する。
【００２６】
このアルゴリズムの性能を測定するために、ＡＲＰＡＮＥＴ、ＮＪ  ＬＡＴＡ、Ｎａｔｉｏｎａｌ、およびＥｕｒｏｐｅａｎ  Ｃｏｓｔ２３９ネットワークなどの標準的ネットワークを含むさまざまなネットワークを使用したシミュレーションを行った。このアルゴリズムは、均一なリンク容量ｕ（ｅ）＝１および１から２までの範囲内でランダムに選択された不均一リンク容量ｕ（ｅ）の両方を用いて、これらのネットワークに対して実行された。保護パスは、３、４、および５ホップに制限されている。ベンチマークとして、この問題の整数線形計画法（ＩＬＰ）および線形計画法（ＬＰ）の混合定式化について得られた解を使用した。ＬＰは、より少数の制約を用いてこの問題をモデル化するので、その最適解が、この問題に対する最適解の下限であることに留意されたい。ＩＬＰは、ＮＰ完全問題を正確にモデル化し、したがって、最適解を返すのに時間がかかりすぎる可能性がある。
【００２７】
観察を、表１に要約する。「総計」は、不均一の場合の総リンク容量であり、「ＩＬＰ最大」は、得られた最良の実現可能ＩＬＰ解であり、「ＩＬＰ最小」は、返されたＩＬＰからの対応する緩和されたＬＰであり、２−ＭＡＸＨＯＰは、ｋ＝２のＭＡＸＨＯＰ−ＳＰＬＩＴである。２−ＭＡＸＨＯＰでは、「保護」は、総保護容量であり、ＰＢＮ％（Ｐｒｏｔｅｃｔｉｏｎ  ｐｅｒｃｅｎｔａｇｅ  ｏｆ  Ｂａｃｋｕｐ  Ｎｅｔｗｏｒｋ、バックアップ・ネットワークの保護率）は、保護の部分的リンク容量だけを使用する際に２−ＭＡＸＨＯＰがどれほど有効であるかを測定し、非０保護容量を有するリンクの総リンク容量に対する保護容量の比率である。
【表１】
2006191596.tif 000004
【表２】
2006191596.tif 000005
【００２８】
ＬＰは、平均して保護容量として総リンク容量の３７％を割り当てる。したがって、２−ＭＡＸＨＯＰの性能は、平均して保護容量として総リンク容量の４９％を割り当てるので、最適に近い（平均して多くともＬＰの１．３７倍）。２−ＭＡＸＨＯＰは、ネットワークが密であり、ｒが大きい時に特に優秀である。ＭＡＸＨＯＰは、平均して保護容量として総リンク容量の６２％を割り当てる。この値が高いのは、１つの保護パスだけが許容されるからである（平均して多くともＬＰの１．７４倍）。ＮＪ  ＬＡＴＡ、Ｎａｔｉｏｎａｌ、およびＥｕｒｏｐｅａｎ  Ｃｏｓｔ２３９ネットワークが、ＡＲＰＡＮＥＴネットワークより密であることに留意されたい。これらの密ネットワークおよびｒ＝５に関して、２−ＭＡＸＨＯＰは、保護に総リンク容量の４２％だけを予約し、ＭＡＸＨＯＰは、総リンク容量の約５４％を予約する。ＡＲＰＡＮＥＴなどの疎なネットワークで、２−ＭＡＸＨＯＰは、ＬＰ最適解に近い性能を示す。
【００２９】
ＡＲＰＡＮＥＴ、ｒ＝３、均一容量に関して、ＩＬＰは、最適解を返し、これは、ＬＰ  ＯＰＴによって返されるものと同一である。これは、ＡＲＰＡＮＥＴネットワークがかなり疎なので、ホップ制約を満足できる保護パスが１つしかないからである。この解は、ほとんどのリンクに半分の保護、少数のリンクにフル保護をおくことである。一部のリンクのフル保護は、このネットワーク内の多くともｒのサイズのパスがないので必要である。
【００３０】
さらに、表１の列「ＰＢＮ％」から、２−ＭＡＸＨＯＰは、バックアップ・プールとして、非０保護容量を有するリンクの中のリンク容量を８４％を超えて予約しない。この値は、しばしば約６０％であるが、ＭＡＸＨＯＰを使用すると、この比率は必ず１００％である。この比は、ｋが２の時に５０％より小さくすることができないことに留意されたい。これは、リンクの間の保護容量の共用および平衡化において２−ＭＡＸＨＯＰ方式が非常に成功していることを示すものである。
【００３１】
図４に、上で述べたように適当なパス長およびコストを計算し、適当な保護容量値に達するために、説明した形でそれぞれ図２および３の上で識別された方法２００および３００を実行するのに使用される例示的なハードウェアの内部回路の詳細を示す。このハードウェアは、必要なアルゴリズムをリモートに実行するのに必要なプログラミング情報（すなわち、上で識別された図面の擬似コード）を有する、ネットワーク１００の内部のコンピュータまたは他のタイプの処理デバイスあるいは外部コンピューティング・デバイスとしての制御モジュール４２４に含まれる。具体的にいうと、コンピューティング・デバイス４２４に、少なくとも１つの中央処理装置（ＣＰＵ）４３０、サポート回路４３４、およびメモリ４３６が含まれる。ＣＰＵ  ４３０に、１つまたは複数の普通に入手可能なマイクロプロセッサを含めることができる。サポート回路４３４は、電源、クロック、入出力インターフェース回路、および類似物を含む周知の回路である。メモリ４３６に、ランダム・アクセス・メモリ、読取専用メモリ、リムーバブル・ディスク・メモリ、フラッシュ・メモリ、およびこれらのタイプのメモリのさまざまな組合せを含めることができる。メモリ４３６を、時々、メイン・メモリと称し、部分的に、キャッシュ・メモリまたはバッファ・メモリとして使用することができる。メモリ４３６に、上で説明した第１のまたは第２のアルゴリズムに従ってノードおよびパスを処理し、分析し、したがってソフトウェア・パッケージまたは対応するＡＳＩＣを実行する時にこれを行うために特殊目的機械を形成するのに必要なステップを指示するさまざまな前記ソフトウェア・パッケージ（すなわち、パッケージ４３２および４３８）が保管される。
【００３２】
ｔ≧２の場合に最小の個数のリンクのスパナを作成することが非常に困難であることがわかっている。したがって、上で識別された方法は、近似解を判定するために開発された。最適解は、ｋ＝１の場合に混合整数線形計画法（ＩＬＰ）に基づいて入手することもできる。ｋに上限がない時にこの問題を最適に解く（多項式時間で）線形計画法も提示する。主な目的は、提示された問題に関する効率的な多項式サイズのＬＰを定式化することが可能であることを実証することである。これらのＬＰは、近似アルゴリズムの性能を測定するためのシミュレーションにも使用されている。
【００３３】
これらの代替の解に関して一般的にいえば、各リンクを反対方向に向かう２つの有向リンクに置換することによって、無向グラフを有向グラフに変換する。表記ｐａｉｒ（ｅ）を使用して、リンクｅの両方向のグラフを示す。有向リンクの両方が一緒に故障すると仮定し、δｉｎ（ｖ）およびδｏｕｔ（ｖ）を、ノードｖの入るリンクおよび出るリンクを表すのに使用する。
【００３４】
ＩＬＰベースの手法
ＩＬＰ定式化では、すべての整数変数が、２進整数である。このタイプのＩＬＰは、一般的なＩＬＰより解くのが簡単である。２進変数ｕｓｅ（ｅ，ｅ’）を使用して、リンクｅが故障した時のネットワーク内の保護パスを取り込む。ｕｓｅ（ｅ，ｅ’）は、リンクｅの故障の時に保護パスにリンクｅ‘が使用される場合に１がセットされる。ＩＬＰは、
【数２】
2006191596.tif 000006
を最小化することである。
各（無向）辺の保護容量が、方向ごとに１回、合計２回カウントされるので、総保護容量が、目的関数で２で割られることに留意されたい。制約は、すべてのｅ∈Ｅ；ｖ∈Ｖについて
【数３】
2006191596.tif 000007
である。
【００３５】
上の制約は、各ノード（ｅの端点を含む）での「フロー保存（ｆｌｏｗ  ｃｏｎｓｅｒｖａｔｉｏｎ）」制約である。２進変数ｕｓｅが、保護パスのインジケータなので、この制約は、保護パスがノードに入る場合に、そのノードから出なければならないことを述べている。リンクｅについて、ｕｓｅ（ｅ，ｐａｉｒ（ｅ））に１がセットされている場合に、フロー保存制約は、ｅについて正確に１つの保護パスを保証する。次は、作業容量（ｕ（ｅ）−ｐ（ｅ））が非０のリンクについてこれを行うものである。
【００３６】
すべてのｅ∈Ｅについて、
ｕ（ｅ）・ｕｓｅ（ｅ，ｐａｉｒ（ｅ））≧ｕ（ｅ）−ｐ（ｅ）  （３）
ｕｓｅ（ｅ，ｐａｉｒ（ｅ））に直接に１をセットするのではなく上を使用する理由は、後で明らかになる。次の制約は、あるリンクの保護パスがそれ自体を使用しないことを保証する。
すべてのｅ∈Ｅについて
ｕｓｅ（ｅ，ｅ）＝０  （４）
次は、保護パスの長さが多くともｒであることを保証する。
すべてのｅ∈Ｅについて
【数４】
2006191596.tif 000008
ｕｓｅ（ｅ，ｐａｉｒ（ｅ））に１がセットされているので、保護パスの長さは、
【数５】
2006191596.tif 000009
になる。したがって、この不等式ではｒではなくｒ＋１が使用される。
【００３７】
次の制約は、リンクｅがその保護パスにリンクｉを使用する場合に、リンクｉの保護容量がｅの作業容量（すなわち、ｕ（ｅ）−ｐ（ｅ））を超えることを保証する。
すべてのｅ；ｉ∈Ｅ；ｉ≠ｐａｉｒ（ｅ）について、
ｐ（ｉ）＋（１−ｕｓｅ（ｅ，ｉ））ｕ（ｅ）≧ｕ（ｅ）−ｐ（ｅ）  （６）
すべてのｅ∈Ｅについて、
ｐ（ｅ）≦ｕ（ｅ）  （７）
ｐ（ｅ）＝ｐ（ｐａｉｒ（ｅ））  （８）
ｐ（ｅ）≧０  （９）
制約（７）は、保護容量が総容量を超えないことを保証する。制約（８）は、無向グラフについて解を保証するためのものである。制約（９）は、保護容量が負でないことを保証する。
【００３８】
直接割り当てではなく式３が、ｕｓｅ（ｅ，ｐａｉｒ（ｅ））の値に１をセットするのに使用される。直接割り当てが使用される場合に、制約（５）は、フロー保存制約と共に、グラフがすべてのリンクについて長さ≦ｒの保護パス（０容量であっても）を有することを必要とするはずである。その代わりに、式３を使用することによって、全保護容量が、最小サイクルが多くともｒ＋１であるリンクに割り当てられる。
【００３９】
上限のない分割
このセクションでは、バックアップ・フローが、任意に分割される（ｋに上限がない）。保護パスが持つことのできるホップ数に対する制約はまだある。この問題を、多項式時間で最適に解くことができることを示す。
タイムエクスパンデッド・グラフ（ｔｉｍｅ−ｅｘｐａｎｄｅｄ  ｇｒａｐｈ）：タイムエクスパンデッド・グラフという概念は、「Constructing Maximal Dynamic fbws from Static fbws」、Ford and Fulkerson、Operations Research 6:419-433、1958年で導入された。タイム・エクスパンデッド・グラフには、各別個の「時間間隔」（レベル）にノードのコピーが含まれる。ｒ＋１レベルのタイムエクスパンデッド・グラフが、本発明の目的のために構成される。レベルには、０からｒまでの番号が付けられる。レベルｉのノードｕを、ｕｉと表すものとする。オリジナル・グラフに辺（ｕ，ｖ）がある場合に、タイムエクスパンデッド・グラフに、ｕｉ−１からｖｉへの辺が含まれる（ｉ＝１…ｒ）。図５に、オリジナル・グラフ５０２および３つのレベルのタイムエクスパンデッド・グラフ５０４を示す。無向グラフは、タイムエクスパンデッド・グラフを構成する前に、１つの辺を２つの有向辺に置換することによって有向グラフに変換される。
【００４０】
補助定理：レベルｒ＋１のタイムエクスパンデッド・グラフのすべてのパスの最大長は、ｒである。
証明：タイムエクスパンデッド・グラフの辺は、あるレベルから次のレベルに向かうのみである。したがって、このグラフには循環がなく、最長の辺は、一番下のレベルから一番上のレベルに向かう。
【００４１】
ｒ＋１レベルのタイムエクスパンデッド・グラフに対する線形計画法（ＬＰ）を定式化し、上の補助定理を使用して、保護パス長をｒまでに制限する。タイムエクスパンデッド・グラフが、明示的には構成されず、このＬＰを概念的に理解するのに使用されることに留意されたい。
【００４２】
変数ｆｌｏｗ（ｅ，ｅ’，ｉ）が、ｉ＝１…ｒについて、リンクｅの故障時にレベルｉ−１からレベルｉに向かうリンクｅ’で再ルーティングされるフローの量を表すのに使用される。リンクｅの故障時にリンクｅ’で再ルーティングされる総フローは、Σｉ＝１．．．ｒｆｌｏｗ（ｅ，ｅ’，ｉ）である。
ＩＬＰと同様に、目的関数は
【数６】
2006191596.tif 000010
を最小化することである。
【００４３】
リンクｅ＝（ｘ，ｙ）のバックアップ・フローは、タイムエクスパンデッド・グラフで、次のようにルーティングされる。ｕ（ｅ）−ｐ（ｅ）のフローが、ノードｘ０で送られ、これが、ノードｙ１…ｙｒ＋１の間で受け取られる。このフローは、ｙｌ，ｌ＝０…ｒノードのどれにおいても出ることを許可されない。他のすべてのノードでのフロー保存制約は、次の通りである。
すべてのｅ＝（ｘ，ｙ）∈Ｅ；Ｉ＝１…ｒについて、
ｆｌｏｗ（ｅ，ｅ，ｌ）＝０  （１１）
ｆｌｏｗ（ｅ，ｐａｉｒ（ｅ），ｌ）＝０  （１２）
上の制約は、あるリンクのバックアップ・フローが、それ自体またはその逆リンクを使用しないことを保証する。
すべてのｅ＝（ｘ，ｙ）∈Ｅについて、
【数７】
2006191596.tif 000011
上の制約は、レベル０のｘの出るリンク（リンクｅを除く）の間で、リンクｅ＝（ｘ，ｙ）についてｗ（ｅ）＝ｕ（ｅ）−ｐ（ｅ）のフローを送る。
すべてのｅ＝（ｘ，ｙ）∈Ｅ，ｖ∈Ｖ，ｖ≠ｘ，ｖ≠ｙ，ｌ＝２…ｒについて、
【数８】
2006191596.tif 000012
上の制約は、レベル１からｒ−１までの、ｘおよびｙを除くすべてのノードのリンクｅ＝（ｘ，ｙ）の保護パスに関するフロー保存制約である。これは、バックアップ・フローがレベルｌでノードに入る場合に、そのノードから出なければならないことを述べている。これは、レベル０のノードを処理しない。バックアップ・フローは、リンクｅ＝（ｘ，ｙ）について、ｘ０を除いて、レベル０のすべてのノードから、入ることを求められない。次の制約が、これを保証する。
すべてのｅ＝（ｘ，ｙ）∈Ｅ，ｖ∈Ｖ，ｖ≠ｘについて、
【数９】
2006191596.tif 000013
レベルｒのノードについて別々の制約は不要である。というのは、すべてのフローが、その宛先で集められるからである。リンクｅ＝（ｘ，ｙ）について、次の制約は、すべてのレベルでノードｙの間ですべてのバックアップ・フローを集める（正確には、レベル２からｒ＋１までの間）。
すべてのｅ＝（ｘ，ｙ）∈Ｅについて
【数１０】
2006191596.tif 000014
リンクｅ’は、複数のリンク（レベル）に分割されるので、次の制約は、リンクｅの故障時のこれらのすべてのレベルの間のバックアップ・フローが、ｅ’の保護帯域幅未満であることを保証する。
すべてのｅ＝（ｘ，ｙ）∈Ｅ，ｅ’∈Ｅについて
【数１１】
2006191596.tif 000015
ＩＬＰと同様に、次の制約は、保護容量が総容量を超えず（制約１８）、この解が無向グラフについて働き（制約１９）、保護容量が負でない（制約２０）ことを保証する。
すべてのｅ∈Ｅについて
ｐ（ｅ）≦ｕ（ｅ）  （１８）
ｐ（ｅ）＝ｐ（ｐａｉｒ（ｅ））  （１９）
ｐ（ｅ）≧０  （２０）
本発明の教示を組み込んださまざまな実施形態を、図示し、本明細書で詳細に説明したが、当業者は、これらの教示を組み込んだ多数の他のさまざまな実施形態をたやすく考案することができる。
【図面の簡単な説明】
【００４４】
【図１】本発明の方法に従って分析される例示的なネットワークを表す図である。
【図２】本発明によるネットワークのプロビジョニングの第１の方法を示す図である。
【図３Ａ】本発明によるネットワークのプロビジョニングの方法の第２の実施形態を示す図である。
【図３Ｂ】本発明によるネットワークのプロビジョニングの方法の第２の実施形態を示す図である。
【図４】本発明による図２および／または３の方法を実践する装置を示す図である。
【図５】本発明の一実施形態によるオリジナル・グラルおよびタイムエクスパンデッド・グラフを示す図である。
【図１】
2006191596.tif 000016
【図２】
2006191596.tif 000017
【図３Ａ】
2006191596.tif 000018
【図３Ｂ】
2006191596.tif 000019
【図４】
2006191596.tif 000020
【図５】
2006191596.tif 000021