(57)【特許請求の範囲】
【請求項１】
ネットワークの少なくとも一部についての障害の所定の最大数を求めるステップと、
前記ネットワークの前記少なくとも一部のトポロジを求めるステップと、
前記ネットワークの前記少なくとも一部の１つまたは複数のフローを求めるステップと、
障害の前記所定の最大数および前記ネットワークの前記少なくとも一部の前記トポロジに少なくとも部分的に基づき、１つまたは複数のハードウェアプロセッサが、前記ネットワークの前記少なくとも一部についての１つまたは複数の障害の様々な組み合わせのモデルを生成するステップであって、前記モデルは前記ネットワークの前記少なくとも一部についての前記１つまたは複数の障害の前記様々な組み合わせに関連した第１の数の制約を含む、ステップと、
前記モデルにおける前記第１の数の制約を、前記第１の数の制約よりも少ない第２の数の制約に、ソーティングネットワークを使用して削減するステップと、
前記モデルに少なくとも部分的に基づき、前記１つまたは複数のフローのうちの個別のフローについて、１つまたは複数の経路のうちの個別の経路を介して伝達されるトラフィックの量を、前記ネットワークの前記少なくとも一部において発生する実際の障害の数が障害の前記所定の最大数以下である場合に輻輳が回避されるように計算するステップと、
前記１つまたは複数のフローのうちの個別のフローについて、前記ネットワークの前記少なくとも一部において配分されるトラフィックを、前記１つまたは複数の経路のうちの前記個別の経路を介して伝達されるトラフィックの前記量に少なくとも部分的に基づき生じさせるステップと
を含む方法。
【請求項２】
請求項１に記載の方法であって、前記１つまたは複数のフローは、トラフィックを発信元装置から宛先装置まで個別に伝達し、前記１つまたは複数のフローは前記トポロジの少なくとも一部を通過し、前記トポロジは、
前記ネットワークの前記少なくとも一部における複数のデバイスおよび前記複数のデバイス間の複数のリンクの配置と、
前記複数のリンクのうちの個別のリンクについての容量であって、前記計算は、前記複数のリンクのうちの個別のリンクの前記容量が、障害の前記所定の最大数を超過しない限り超過しないことを保証する、前記複数のリンクのうちの個別のリンクについての容量と
を表す、方法。
【請求項３】
請求項２に記載の方法であって、前記１つまたは複数の経路のうちの前記個別の経路を介して伝達されるトラフィックの前記量の前記計算は、前記複数のリンクのうちの個別のリンクに関する帯域幅の利用可能性を、前記容量が、障害の前記所定の最大数未満の発生に応答して追加のトラフィックが到着した場合に超過しないように提供する、方法。
【請求項４】
請求項１に記載の方法であって、障害の前記所定の最大数はコントロール障害に関連付けられ、該コントロール障害において、１つまたは複数のスイッチング装置は、現在の構成を古い構成から新しい構成に更新することに失敗するか、または、前記現在の構成を前記古い構成から前記新しい構成に更新することに遅延する、方法。
【請求項５】
請求項１に記載の方法であって、障害の前記所定の最大数はスイッチ障害に関連付けられ、該スイッチ障害において、１つまたは複数のスイッチング装置はトラフィックを伝達することに失敗しかつ伝達できない、方法。
【請求項６】
請求項１に記載の方法であって、障害の前記所定の最大数はリンク障害に関連付けられ、該リンク障害において、１つまたは複数のリンクはトラフィックを伝達することに失敗しかつ伝達できない、方法。
【請求項７】
請求項１に記載の方法であって、個別のフローについて前記ネットワークの前記少なくとも一部において配分されるトラフィックを生じさせる前記ステップは、配分命令を１つまたは複数のスイッチング装置に発行するステップを含む、方法。
【請求項８】
請求項１に記載の方法であって、前記ネットワークの前記少なくとも一部において配分されるトラフィックを生じさせる前記ステップは、フロー配分重みを１つまたは複数のスイッチング装置に提供するステップを含む、方法。
【請求項９】
１つまたは複数のプロセッサと、
命令を記憶する１つまたは複数のメモリと
を備えたシステムであって、前記命令は、前記１つまたは複数のプロセッサに、
ネットワークの少なくとも一部についての障害の所定の最大数を求めるステップと、
前記ネットワークの前記少なくとも一部のトポロジであって、前記ネットワークの前記少なくとも一部における１つまたは複数のリンクのうちの個別のリンクについての通信容量を含むトポロジを求めるステップと、
前記ネットワークの前記少なくとも一部の前記トポロジおよび障害の前記所定の最大数に少なくとも部分的に基づき、可能性ある障害の様々な組み合わせのモデルを生成するステップであって、前記モデルは可能性ある障害の前記様々な組み合わせに関連した第１の数の制約を含む、ステップと、
前記モデルに含まれる前記第１の数の制約を、前記第１の数の制約よりも少ない第２の数の制約に、ソーティングネットワークを使用して削減するステップと、
前記モデルに少なくとも部分的に基づき、前記ネットワークの前記少なくとも一部についてのトラフィック構成を、前記ネットワークにおいて実際に発生する障害の数が障害の前記所定の最大数以下である限り、個別のリンクが前記通信容量を超過しないように計算するステップと、
前記ネットワークの前記少なくとも一部を、前記トラフィック構成に少なくとも部分的に基づき構成するステップと
を実行させる、システム。
【請求項１０】
請求項９に記載のシステムであって、障害の前記所定の最大数はコントロール障害に関連付けられ、該コントロール障害において、１つまたは複数のスイッチング装置は、現在の構成を古い構成から新しい構成に更新することに失敗するか、または、前記現在の構成を前記古い構成から前記新しい構成に更新することに遅延する、システム。
【請求項１１】
請求項９に記載のシステムであって、障害の前記所定の最大数はスイッチ障害に関連付けられ、該スイッチ障害において、１つまたは複数のスイッチング装置はトラフィックを伝達することに失敗しかつ伝達できない、システム。
【請求項１２】
請求項９に記載のシステムであって、障害の前記所定の最大数はリンク障害に関連付けられ、該リンク障害において、前記１つまたは複数のリンクのうちの少なくとも１つはトラフィックを伝達することに失敗しかつ伝達できない、システム。
【請求項１３】
請求項９に記載のシステムであって、前記命令は、前記１つまたは複数のプロセッサに、前記ネットワークの前記少なくとも一部を、フロー配分重みを１つまたは複数のスイッチング装置に提供することによって構成させる、システム。
【請求項１４】
請求項９に記載のシステムであって、前記トラフィック構成の前記計算は、前記個別のリンクについての帯域幅の利用可能性を、前記個別のリンクが、障害の前記所定の最大数未満の発生に応答して追加のトラフィックが到着した場合に前記通信容量を超過しないように提供する、システム。
【請求項１５】
１つまたは複数のプロセッサと、
命令を記憶する１つまたは複数のメモリと
を備えた１つまたは複数の装置であって、前記命令は、前記１つまたは複数のプロセッサによって実行されると、前記１つまたは複数の装置に、
ネットワークのトポロジにアクセスするステップと、
前記ネットワークのトポロジおよび障害の所定の最大数に少なくとも部分的に基づき、可能性ある障害の様々な組み合わせのモデルを生成するステップであって、前記モデルは可能性ある障害の前記様々な組み合わせに関連した第１の数の制約を含む、ステップと、
前記モデルにおける前記第１の数の制約を、前記第１の数の制約よりも少ない第２の数の制約に、ソーティングネットワークを使用して削減するステップと、
前記ネットワークのトポロジに少なくとも部分的に基づき、ネットワークの少なくとも一部についてのトラフィック構成を、前記ネットワークの前記少なくとも一部において実際に発生する障害の数が障害の前記所定の最大数以下である限り、前記ネットワークの前記少なくとも一部における個別のリンクが通信容量を超過しないように計算するステップと、
前記ネットワークを、計算された前記トラフィック構成に少なくとも部分的に基づき構成するステップと
を実行させる、１つまたは複数の装置。
【請求項１６】
請求項１５に記載の１つまたは複数の装置であって、障害の前記所定の最大数はコントロール障害に関連付けられ、該コントロール障害において、１つまたは複数のスイッチング装置は、現在の構成を古い構成から新しい構成に更新することに失敗するか、または、前記現在の構成を前記古い構成から前記新しい構成に更新することに遅延する、１つまたは複数の装置。
【請求項１７】
請求項１５に記載の１つまたは複数の装置であって、障害の前記所定の最大数はスイッチ障害に関連付けられ、該スイッチ障害において、１つまたは複数のスイッチング装置はトラフィックを伝達することに失敗しかつ伝達できない、１つまたは複数の装置。
【請求項１８】
請求項１５に記載の１つまたは複数の装置であって、障害の前記所定の最大数はリンク障害に関連付けられ、該リンク障害において、１つまたは複数のリンクはトラフィックを伝達することに失敗しかつ伝達できない、１つまたは複数の装置。
【請求項１９】
請求項１５に記載の１つまたは複数の装置であって、前記ネットワークを構成するステップは、フロー配分重みを１つまたは複数のスイッチング装置に提供するステップを含む、１つまたは複数の装置。
【請求項２０】
請求項１５に記載の１つまたは複数の装置であって、前記命令は、前記１つまたは複数の装置を、前記個別のリンクについての帯域幅の利用可能性を、前記個別のリンクが、障害の前記所定の最大数未満の発生に応答して追加のトラフィックが到着した場合に前記通信容量を超過しないように提供するように更に構成する、１つまたは複数の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]電子的サービス（例えば、検索サービス、電子メールサービス、ソーシャルネットワーキングサービス、クラウドコンピューティングサービス、など）は、より多くのユーザーへサービスすることおよびより多くのコンテンツを提供することにより拡大し続けており、電子的サービスのプロバイダーは、拡張された電子的サービスを提供するために装置のネットワークを継続的に維持し、かつ更新しなければならない。しかしながら、装置および装置を相互接続し、かつ個別のネットワーク内のデータを伝達するリンクは、故障する、またはネットワーク輻輳（例えば、リンクが通信容量を超過する）を招く恐れのある障害を引き起こす可能性がある。したがって、ネットワークは、ネットワークの効率性および信頼性に影響を及ぼす恐れがあるパケットの損失を被る可能性がある。
【発明の概要】
【０００２】
[0002]本明細書に記載される技術および／またはシステムは、ネットワークの少なくとも一部が、所定の最大障害数を超過しない限り、輻輳（例えば、リンクが容量を超過する）を回避できることを保証することができる障害処理サービスを実装する。障害処理サービスは、ネットワークトポロジに基づき可能性のある障害の異なる組み合わせをモデル化し、次いで、発生する実際の障害数が所定の最大障害数以下である限り、輻輳が回避されるように個別の経路を介して伝達されるべきトラフィック量を計算する。
【０００３】
[0003]本概要は、詳細な説明の中で以下に詳しく説明される、簡単化された形での選択された概念を紹介するために提供される。本概要は、特許請求の範囲の主題の主要な機能または本質的な特徴を特定することを意図するものでも、特許請求の範囲の主題の範囲を限定するために使用されることを意図するものでもない。
【０００４】
[0004]詳細な説明は添付の図面を参照して表現される。図に於いて、参照番号の最左の数字は参照番号が最初に現れた図を識別する。異なる図での同一の参照番号の使用は、類似のまたは同一の項目を示す。
【図面の簡単な説明】
【０００５】
【図１】[0005]障害処理サービスが、様々な実施形態に従って、所定の最大障害数までを取り扱うようにネットワークを構成する図を例示する。
【図２】[0006]様々な実施形態に従って、所定の最大リンク障害数までを取り扱うように構成されたネットワーク例を示す図である。
【図３】[0007]様々な実施形態に従って、所定の最大のコントロール障害数までを取り扱うように構成されたネットワーク例を示す図を例示する。
【図４】[0008]様々な実施形態に従って、障害処理サービスを実装する環境例を示す図を例示する。
【図５】[0009]様々な実施形態に従って、所定の最大障害数がリンク上に輻輳を引き起こすことなく発生することができるようにネットワークを構成するプロセス例を示す図を例示する。
【図６】[0010]様々な実施形態に従って、障害処理サービスが可能性のある障害の異なる組み合わせに関連した制約を効率的に解決することができるようにソーティングネットワーク手法を使用するプロセス例を示す図を例示する。
【図７】[0011]様々な実施形態に従って、障害処理サービスを実装するために使用されるソーティングネットワーク例を示す図を例示する。
【発明を実施するための形態】
【０００６】
[0012]本明細書に記載された技術および／またはシステムは、ネットワークのための障害処理サービスを実装する。障害処理サービスは、所定の最大障害数までを取り扱うようにネットワークを積極的に構成する。例えば、障害処理サービスは、入力として、特定の許容される障害数（例えば、所定の最大障害数）およびネットワークの少なくとも一部のトポロジを受信することができる。トポロジは、少なくとも、
（ｉ）装置および装置間のリンクなどのネットワーク構成要素の配置、および（ｉｉ）ネットワークまたはネットワークの一部内の１つまたは複数の個別のフローに関連した情報を含むことができる。入力に基づいて、障害処理サービスは、ネットワーク内で実際に発生する障害数が所定の最大障害数以下である限り、ネットワーク輻輳が回避されるように、個別のフローについて、１つまたは複数の経路内で伝達されるトラフィック量を計算するように構成される。次いで、障害処理サービスは、障害が実際にネットワーク内で発生する以前に計算に基づきフローが配分されるように、ネットワークの構成要素を構成する（例えば、命令を発出する）ことができる。したがって、障害処理サービスは、所定の最大障害数に達するまで堅牢であるように積極的にネットワークを構成する（例えば、輻輳が発生しないように保証する）。
【０００７】
[0013]ネットワーク障害は、データプレーン障害またはコントロールプレーン障害を含む可能性がある。データプレーン障害は、リンク（例えば、ネットワーク内の２つの装置間の直接のリンク）が故障する場合、または装置が故障する場合に発生する。本明細書に記載された様々な実装では、ネットワーク障害に関連する装置は、例えば、ネットワーク内でデータパケット（例えば、ネットワーク内で伝達されるトラフィック）を回送する仕事をするスイッチング装置であり得る。したがって、データプレーン障害は、パケットの回送に影響を及ぼすリンク障害またはスイッチ障害を含む可能性がある。コントロールプレーン障害は、ネットワーク内のスイッチング装置が、適時に、再構成すること、または更新を受信することに失敗する場合（例えば、完全な再構成障害、再構成遅延など）に発生する。したがって、スイッチング装置がパケットを回送し続け、かつ故障していないとしても、スイッチング装置が以前のまたは古い構成であり、かつ更新されていないまたは新しくない構成に基づきパケットを回送することから、障害が依然として発生する。コントロールプレーン障害は、リモートプロシージャコール（ＲＰＣ）障害、スイッチング装置ファームウェアまたはソフトウェア内のバグ、スイッチング装置内のメモリ不足などに起因する可能性がある。したがって、本明細書に記載された障害処理サービスは、実際に発生する障害数が所定の最大障害数未満である限り、障害処理サービスが、ネットワーク輻輳が発生することがない（例えば、ネットワーク内のリンク上のトラフィックが容量を超過しない）ことを保証するように、データプレーン障害および／またはコントロールプレーン障害を積極的に処理するようにネットワークを構成する。
【０００８】
[0014]従来、トラフィックエンジニアリング制御装置は、障害の検出に応答してネットワークを再構成する。したがって、従来の手法は、障害が実際に発生した後の、および障害が検出された後のネットワーク輻輳、結果として、既に発生し、かつ修正の必要が生じているネットワーク輻輳を削減する。多くの場合、トラフィックエンジニアリング制御装置は、ネットワーク処理能力を、例えば、パケット損失に起因して、中断または減少させる障害に対して効率的に反応することができない（例えば、再動作または訂正は数十秒を要する可能性がある）。例えば、ネットワーク内のリンクが故障する（例えば、故障が発生する）場合、ネットワーク内のスイッチング装置は、典型的にはトラフィックを他の利用可能な経路に移動する（例えば、トラフィックを再調整する）ように構成される。しかしながら、本動作は、リンク容量制約を考慮しておらず、したがって、本動作は、その後に反応的に訂正されなければならないリンク輻輳を招くことが多い。
【０００９】
[0015]図１は、本明細書に記載された障害処理サービス１０２が所定の最大障害数（例えば、１、２、３、４、１０、２０、１００または任意のその他の数）まで取り扱うようにネットワーク１０４を構成する例図１００を例示する。所定の最大障害数は、障害処理サービス１０２を作動させるエンティティ、あるいはネットワーク１０４またはパケット回送などのネットワーク１０４の特定の機能を管理するエンティティ（例えば、トラフィックエンジニアリングアプリケーションまたは制御装置）により設定され得る。上記のように、障害処理サービス１０２は、ネットワーク１０４内の障害を処理するための積極的な手法を実装する。例えば、障害処理サービス１０２は、輻輳からの開放が所定の最大障害数まで実現されるように、フローに関連した１つまたは複数の経路を介して伝達されるべきトラフィック量を計算することができる。別の言い方をすれば、障害処理サービス１０２は、障害の総数が所定の許容される障害の最大数以下である限り、輻輳が発生しない、例えば、リンクが帯域幅容量を超過しないように、ネットワーク内にトラフィック拡散する。
【００１０】
[0016]ネットワーク１０４は、様々な装置１０６および直結のリンク１０８、例えば、ネットワーク１０４内の２つの装置１０６間のリンクを含むことができる。直結のリンク１０８は、２つの装置を接続する通信経路の少なくとも一部であり得る。例えば、入口スイッチング装置は、トラフィックが発生する発信元装置であり、出口スイッチング装置はトラフィックが終結する宛先装置であり得る。入口スイッチング装置は、１つまたは複数の通信経路を確立し、かつ１つまたは複数の通信経路を介して出口スイッチング装置にフロー（例えば、トラフィック）を伝達するように構成される、または指示され得る。本明細書に記載されるように、通信経路はまた、（例えば、入口スイッチング装置および出口スイッチング装置を含む）２つ以上の装置を通過する、通信トンネルまたはトンネルと呼ばれ得る。
【００１１】
[0017]様々な実施形態では、ネットワーク１０４は、データセンターネットワーク（ＤＣＮ）、インターネットサービスプロバイダー（ＩＳＰ）ネットワーク、企業ネットワーク（例えば、クラウドサービス）またはエンティティの制御下にあり得る任意のその他の管理ドメイン（例えば、障害処理サービス１０２を実行する装置を作動させ、かつ維持するエンティティ）などの、大規模な生産ネットワークであり得る。装置１０６は、スイッチング装置（スイッチ）、ルーティング装置（ルーター）、ゲートウェイ装置（ゲートウェイ）、ブリッジング装置（ネットワークブリッジ）、ハブ装置（ネットワークハブ）、ファイヤーウォール装置、ネットワークアドレス変換装置（ＮＡＴ）、多重化装置（マルチプレクサー）、無線アクセスポイント装置（ＷＡＰ）、プロキシーサーバー装置、ファイルサーバー装置、データベースサーバー装置、記憶装置などのような物理的ネットワーク装置であり得る。装置１０６はまた、ネットワーク１０４に接続する能力のあるエンドユーザー装置であり得る。例えば、エンドユーザー装置は、スマートフォン、携帯電話、パーソナルデジタルアシスタント（ＰＤＡ）、電子ブック装置、ラップトップコンピューティング装置、タブレットコンピューティング装置、パーソナルメディアプレーヤーなどのような、モバイルまたは携帯装置を含むことができる。あるいは、エンドユーザー装置は、デスクトップコンピューティング装置、ゲームコンソール装置、デジタルビデオ録画装置（ＤＶＲ）、セットトップボックス装置などのような、据え置き型装置を含むことができる。したがって、ネットワーク１０４は、ドメインまたは管理ネットワークを構成するために相互に接続された数十、数百、数千の装置を含むことができる。
【００１２】
[0018]本明細書で議論される様々な例では、障害処理サービス１０２はトンネル型フォワーディングに従って実装され得る。トンネル型フォワーディングは、ネットワークのトラフィックエンジニアリングに於いて使用され得る。トンネル型フォワーディングでは、１つまたは複数のトンネル（例えば、通信経路）が入口−出口スイッチング装置対間のトラフィックを伝達するために確立され、かつ伝達されるトラフィックは、フローと呼ばれ得る。上述のように、フローは、複数のトンネルに拡散され、または分散され得る。したがって、障害処理サービス１０２は、フローが複数のトンネルに分割される方法を決定する重み付けを有する入口スイッチング装置を構成することができる。
【００１３】
[0019]障害処理サービス１０２は、ネットワーク１０４のトポロジを受信またはアクセスし、かつモデル、例えば、連立方程式をトポロジおよび所定の許容される最大障害数に基づき生成するように構成される。モデルは、ネットワーク内で潜在的に発生し得る可能性のある障害の異なる組み合わせ表現する（例えば、障害の種類、障害の場所など）。例えば、所定の許容される障害の最大数が１である場合、可能性のある障害の組み合わせは、１つの許容される障害が発生し得るネットワーク内の一箇所（例えば、スイッチ故障に対する各スイッチング装置）に関連している。したがって、可能性のある障害の組み合わせは、単一の障害を含むことができる。別の例では、所定の許容される障害の最大数が２である場合、可能性のある障害の組み合わせは、２つの障害が発生し得るネットワーク内の２箇所に関連している。さらに別の例では、所定の許容される障害の最大数は３、５、１０、２０、５０、１００などの、任意の数であり得る。
【００１４】
[0020]次いで、障害処理サービス１０２は、ネットワーク内の経路を介して伝達されるべきトラフィック量を計算するためにモデルを使用する。計算されたトラフィック量は、発生する障害数が所定の障害の最大数以下である限り、リンクが通信容量を超過することなく、リンクに到着する追加のトラフィック（例えば、障害に応答したトラフィック量の再調整プロセスの一部として）のために部屋、例えば、利用可能な空間を提供する。すなわち、計算は、障害の任意の組み合わせ（例えば、障害の数が所定の最大障害数以下である障害の組み合わせ）の結果としてリンクに到着する可能性がある追加のトラフィックが当該リンクに対する利用可能なまたは予備の容量より少ないことを保証し、したがって、リンク輻輳は回避される。様々な実施形態では、入口スイッチング装置は、入口スイッチング装置が１つまたは複数のトンネル（例えば、障害に影響された）を無効にし、かつ１つまたは複数の障害トンネルを介して伝達されるトラフィックをフローに対して確立された他のトンネル（例えば、残余のトンネル）上に分割するように、障害に応答した比例再調整を実装することができる。
【００１５】
[0021]様々な実装では、ネットワーク１０４は、多数の装置（例えば、数十、数百、数千など）および／または２つの装置間のリンクを含むことができる。したがって、可能性のある障害の異なる組み合わせを決定することおよび異なる組み合わせをモデル化することは、計算上の課題、例えば、多数の制約を提示することができる。したがって、障害処理サービス１０２は、本明細書でさらに議論するように、生起する多数の制約を符号化し、かつ制約を効率的に解決するために（例えば、１つまたは複数のフローに対するトラフィック配分を計算するために）ソーティングネットワーク手法を使用することができる。いくつかの例では、障害処理サービス１０２は、削減された数の制約（例えば、ネットワークトラフィックに最も多くの影響を与える障害に関連した）をソートするためにソーティングネットワーク手法を使用することができる。
【００１６】
[0022]上述のように、ネットワーク障害は、データプレーン障害および／またはコントロールプレーン障害を含み得る。図１は、リンク障害１１０、スイッチ障害１１２およびコントロール障害１１４を例示する。リンク障害１１０およびスイッチ障害１１２はそれぞれ、少なくとも、リンクまたはスイッチング装置がフローまたはフローの一部を処理することができないことから、トンネル型フォワーディングに影響を及ぼす可能性があり、したがって、ネットワーク１０４内のトラフィックを再調整されるべきことが要求されるデータプレーン障害の例である。コントロール障害１１４は、トンネルに沿ったスイッチング装置が、少なくとも、新しいまたは更新された構成に従ってトラフィックを経路付けすることが期待される時点で、古いまたは以前の構成に従ってトラフィックを経路付し続ける可能性があることから、ネットワーク輻輳を引き起こす可能性もあるコントロールプレーン障害の例である。
【００１７】
[0023]積極的に障害を処理するためにネットワーク１０４を構成することに先立って、障害処理サービス１０２は、１つまたは複数の障害保護レベル１１６を決定する（例えば、アクセスまたは受信する）ように構成される。障害保護レベル１１６は、所定の許容されるリンク障害の最大数（例えば、以下の議論におけるｋｅ）、所定の許容されるスイッチ障害の最大数（例えば、以下の議論におけるｋｖ）および／または所定の許容されるコントロール障害の最大数（例えば、以下の議論におけるｋｃ）を示すことができる。
【００１８】
[0024]障害保護レベル１１６に基づき、障害処理サービス１０２は、発生する障害の総数が所定の許容される障害の最大数以下である限り、ネットワーク輻輳が回避されることを保証するトラフィック量を計算するように構成される。次いで、障害処理サービス１０２は、ネットワーク１０４に対して構成設定１１８を提供して、ネットワーク１０４が、計算結果に基づきトラフィックを伝達する（例えば、配分する）ように構成され得る。
【００１９】
[0025]一例として、図２は、障害処理サービス１０２が所定のリンク障害の最大数ｋｅまで処理するようにネットワークを構成する方法を示す図２００を例示しており、図２の例ではｋｅ＝１である。したがって、図２は、データプレーン障害に向けたものであり、リンク障害以前のネットワークのトラフィック配分をモデル化した第１の構成２０２およびリンク障害後の同一のネットワークのトラフィック配分をモデル化した第２の構成２０４を例示する。ネットワークは、第１のスイッチング装置２０６（１）、第２のスイッチング装置２０６（２）、第３のスイッチング装置２０６（３）および第４のスイッチング装置２０６（４）を含む。ネットワーク内の任意の２つの装置間の各リンクは、超過した場合、リンクに輻輳を引き起こさせる可能性のある通信容量または帯域制限（例えば、図２の例では１０ユニット）を有する。
【００２０】
[0026]第１の構成２０２では、第１のトンネル２０８（１）（トンネルは図２内の点線で示される）は、１．５ユニット（例えば、毎秒当たりのギガビット、Ｇｂｐｓ）のトラフィックをスイッチング装置２０６（２）からスイッチング装置２０６（４）にスイッチング装置２０６（１）を介して伝達し、第２のトンネル２０８（２）は、１．５ユニットのトラフィックをスイッチング装置２０６（３）からスイッチング装置２０６（４）にスイッチング装置２０６（１）を介して伝達し、第３のトンネル２０８（３）は、７ユニットのトラフィックをスイッチング装置２０６（３）からスイッチング装置２０６（４）に直接伝達し、第４のトンネル２０８（４）は、７ユニットのトラフィックをスイッチング装置２０６（２）からスイッチング装置２０６（４）に直接伝達する。したがって、トンネル２０８（１）およびトンネル２０８（４）は、スイッチング装置２０６（２）が入口スイッチング装置であり、スイッチング装置２０６（４）が出口スイッチング装置であるフローに関連付けられ得る。さらに、トンネル２０８（２）およびトンネル２０８（３）は、スイッチング装置２０６（３）が入口スイッチング装置であり、スイッチング装置２０６（４）が出口スイッチング装置である別のフローに関連付けられ得る。障害処理サービス１０２は、ｋｅ＝１を指定する、障害保護レベル１１６に基づきトラフィック量（例えば、図２に例示されるユニット）を計算する。
【００２１】
[0027]したがって、リンク障害２１０（例えば、データプレーン障害）が、第２の構成２０４内に示されるように、スイッチング装置２０６（２）とスイッチング装置２０６（４）との間の場所で発生する場合、ネットワークは、第１のトンネル２１２（１）が、８．５ユニットのトラフィックをスイッチング装置２０６（２）からスイッチング装置２０６（４）にスイッチング装置２０６（１）を介して伝達し、第２のトンネル２１２（２）が、１．５ユニットのトラフィックをスイッチング装置２０６（３）からスイッチング装置２０６（４）にスイッチング装置２０６（１）を介して伝達し、かつ第３のトンネル２１２（３）が７ユニットのトラフィックをスイッチング装置２０６（３）からスイッチング装置２０６（４）に直接伝達するようにトラフィックを再調整する。
【００２２】
[0028]図示のように、第１の構成２０２でのトンネル２０８（２）およびトンネル２０８（３）は、再調整プロセスの間変更されないままである。しかしながら、第２の構成２０４内のトンネル２１２（１）は、リンク障害２１０の結果として第１の構成２０２でのトンネル２０８（１）およびトンネル２０８（４）のフローを合わせて処理するように再調整されたトンネルである。第２の構成２０４では、スイッチング装置２０６（１）からスイッチング装置２０６（４）への直接リンク上の負荷は、リンクの最大容量以内である、合計１０ユニット（すなわち、８．５＋１．５）である。
【００２３】
[0029]図２は、リンク障害がスイッチング装置２０６（２）とスイッチング装置２０６（４）との間で発生していることを示しているが、例えば、障害処理サービス１０２により計算されるように、第１の構成２０２内で指定されたユニットは、ネットワーク内のどこであれ単一のリンク障害を積極的に処理することができ、かつ単一のリンク障害（ｋｅ＝１）を越えない限り、輻輳は依然として回避されることになる。例えば、スイッチング装置２０６（２）とスイッチング装置２０６（４）間のリンクの替わりに、スイッチング装置２０６（１）とスイッチング装置２０６（３）間のリンクが故障した場合、トンネル２０８（２）を介して伝達される１．５ユニットは、合計８．５ユニットが再調整された構成に於いてスイッチング装置２０６（３）とスイッチング装置２０６（４）間のリンクを介して伝達されるように（例えば、８．５ユニットはリンクに対する容量１０ユニット未満である）、トンネル２０８（３）を介して伝達される７ユニットに加算され得る。
【００２４】
[0030]さらに、第１の構成２０２はまた、輻輳を引き起こすことなく単一のスイッチ障害（例えば、Ｋｖ＝１）を処理することができる。例えば、スイッチング装置２０６（１）が故障した場合、トンネル２０８（１）を介して伝達される１．５ユニットは、トンネル２０８（４）を介して伝達されるように再調整され（例えば、７＋１．５＜１０ユニット）、かつトンネル２０８（２）を介して伝達される１．５ユニットは、トンネル２０８（３）を介して伝達されるように再調整され得る（例えば、７＋１．５＜１０ユニット）。
【００２５】
[0031]したがって、障害処理サービス１０２は、フローに対するトラフィック量を計算するように構成され、かつ、ネットワークが、例えば第２の構成２０４内に示されたように、障害に対して堅牢であるように構成された後に発生する、リンク障害のためにリンクに到着する可能性がある、再調整されたトラフィック（例えば、比例再調整）を吸収するために十分に利用可能なまたは予備の容量があるように、例えば、第１の構成２０２内で示されたように、計算されたトラフィック量に基づきネットワークを積極的に構成する。
【００２６】
[0032]別の例として、図３は、障害処理サービス１０２がコントロール障害の最大数ｋｃまで処理するようにネットワークを構成する方法を示す図３００を例示する。したがって、図３は、コントロールプレーン障害に向けられ、かつネットワークまたはネットワークの一部のトラフィックをモデル化する第１のトラフィックエンジニアリング（ＴＥ）構成３０２および第２のＴＥ構成３０４を例示する。所定の許容されるコントロールプレーン障害の最大数は１に等しい（例えば、ｋｃ＝１）。第１のＴＥ構成３０２および第２のＴＥ構成３０４に於いて、トラフィックは、図３の例内の、第１のスイッチング装置３０６（１）、第２のスイッチング装置３０６（２）、第３のスイッチング装置３０６（３）および第４のスイッチング装置３０６（４）によりまたは介して伝達される。この例では、リンク容量は１０ユニットである。リンクおよび装置の配置、リンク容量、ならびに第１のＴＥ構成３０２内で伝達されるトラフィックは、障害処理サービス１０２によりアクセス可能なネットワークトポロジにより表され得る。
【００２７】
[0033]第１のＴＥ構成３０２に於いて、第１のトンネル３０８（１）（トンネルは同様に図３内の点線で示される）はスイッチング装置３０６（１）からスイッチング装置３０６（２）に直接１０ユニットのトラフィックを伝達し、第２のトンネル３０８（２）は、スイッチング装置３０６（１）からスイッチング装置３０６（３）に直接１０ユニットのトラフィックを伝達し、第３のトンネル３０８（３）は、スイッチング装置３０６（２）からスイッチング装置３０６（４）に直接７ユニットのトラフィックを伝達し、第４のトンネル３０８（４）は、スイッチング装置３０６（３）からスイッチング装置３０６（４）に直接７ユニットのトラフィックを伝達し、第５のトンネル３０８（５）は、スイッチング装置３０６（２）からスイッチング装置３０６（４）にスイッチング装置３０６（１）を介して３ユニットのトラフィックを伝達し、第６のトンネル３０８（６）は、スイッチング装置３０６（３）からスイッチング装置３０６（４）にスイッチング装置３０６（１）を介して３ユニットのトラフィックを伝達する。
【００２８】
[0034]この例では、障害処理サービス１０２またはトラフィックエンジニアリングコントローラは、第２のＴＥ構成３０４内に示されるように新トンネル３１０を収容するためにスイッチング装置を更新しようとする。したがって、障害処理サービス１０２は、トンネル３１２（１）が第１のＴＥ構成３０２内のトンネル３０８（３）および３０８（５）を介してこれまでに伝達されていたトラフィックを結合して（例えば、７＋３＝１０ユニット）伝達するように、新しい構成（例えば、新しい重み付けの配分）でスイッチング装置３０６（２）を更新することを試みることができる。さらに、障害処理サービス１０２またはトラフィックエンジニアリングコントローラは、トンネル３１２（２）が第１のＴＥ構成３０２内のトンネル３０８（２）および３０８（４）を介してこれまでに伝達されていたトラフィックを結合して（例えば、７＋３＝１０ユニット）伝達するように、新しい構成でスイッチング装置３０６（３）を更新することを試みることができる。第２のＴＥ構成３０４内のトンネル３１２（３）および３１２（４）は、第１のＴＥ構成３０２内のトンネル３０８（１）およびトンネル３０８（２）からは変更されない。
【００２９】
[0035]したがって、コントロール障害３１４（例えば、コントロールプレーン障害）が、第２のＴＥ構成３０４内に示されるように、スイッチング装置３０６（２）（例えば、スイッチング装置障害を更新する、または遅延され、タイムリーに実装されないような試み）に於いて発生した場合、スイッチング装置３０６（２）は、第１のＴＥ構成３０２に従ってトラフィックを経路付し続けることになる。したがって、トンネル３１２（１）は、トンネル３０８（５）からの３ユニットのトラフィックを取り入れるように構成されることに成功しないことになる。しかしながら、障害処理サービス１０２は、最大１つのスイッチング装置が故障した場合であっても、リンク輻輳が発生しないことを保証するトンネル３１０に対する７ユニットのトラフィック量を計算するように構成される。例えば、トンネル３０８（５）および新しいトンネル３１０からの古い構成のトラフィックであっても、スイッチング装置３０６（１）とスイッチング装置３０６（４）間のリンクの容量は、１０ユニットの容量を超過しない（例えば、３＋７≦１０ユニット）。
【００３０】
[0036]図３は、コントロール障害がスイッチング装置３０６（２）に於いて発生し（例えば、可能性のある障害の第１の組み合わせ）、図３におけるＴＥ構成がネットワーク内のどこであれ、例えばスイッチング装置３０６（３）に於いて、コントロール障害（例えば、可能性のある障害の第２の組み合わせ）を積極的に処理することができることを示す。
【００３１】
[0037]図４は、上記の障害処理サービス１０２を実装する環境例４００を示す図である。様々な実施形態に於いて、障害処理サービス１０２は、１つまたは複数の装置４０２により実装され得る。装置４０２は、デスクトップコンピューティング装置、サーバーコンピューティング装置などといった据え置き型装置を含むことができる。装置４０２は、それらの替わりに、ラップトップコンピューティング装置、タブレットコンピューティング装置、スマートフォン装置、携帯電話装置、携帯情報端末（ＰＤＡ）装置、電子ブック装置などといったモバイルまたは携帯型装置を含むことができる。
【００３２】
[0038]装置４０２は、本明細書に記載された技術を実装するように構成された障害処理サービス１０２を含む。装置４０２は、１つまたは複数のプロセッサ４０４およびメモリ４０６を個別にかつ別々に含むことができる。プロセッサ４０４は、単一の処理装置または、それぞれが複数の異なる処理装置を含むことができる、いくつかの装置であり得る。プロセッサ４０４は、マイクロプロセッサ、マイクロコンピュータ、マイクロコントローラ、デジタルシグナルプロセッサ、中央処理装置（ＣＰＵ）、グラフィックスプロセッシングユニット（ＧＰＵ）、セキュリティプロセッサなどを含むことができる。代替として、または加えて、本明細書に記載された技術のいくつかまたはすべては、少なくとも一部を、１つまたは複数のハードウェアロジックコンポーネントにより遂行され得る。例えば、限定するものではなく、使用され得るハードウェアロジックコンポーネントの種類の例には、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、アプリケーション固有標準製品（ＡＳＳＰ）、状態マシーン、コンプレックスプログラマブルロジックデバイス（ＣＰＬＤ）、その他の論理回路、システムオンチップ（ＳｏＣ）、および／または命令に基づき動作を遂行する任意のその他の装置が含まれる。その他の能力の中で、プロセッサ４０４は、メモリ４０６内に記憶されたコンピュータ読み取り可能な命令を読み込みかつ実行するように構成され得る。
【００３３】
[0039]メモリ４０６は、コンピュータ読み取り可能な媒体の１つまたは組み合わせを含むことができる。
本明細書で使用されるように、「コンピュータ読み取り可能な媒体」は、コンピュータ記憶媒体および通信媒体を含む。
【００３４】
[0040]コンピュータ記憶媒体は、コンピュータ読み取り可能な命令、データ構造、プログラムモジュールまたはその他のデータなどの、情報を記憶するための任意の方法または技術で実装された、揮発性および不揮発性、可換型および非可換型媒体を含む。コンピュータ記憶媒体は、相変化メモリ（ＰＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、その他の種類のランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、電気的に消去可能なプログラマブルＲＯＭ（ＥＥＰＲＯＭ）、フラッシュメモリ、またはその他のメモリ技術、コンパクトディスクＲＯＭ（ＣＤ−ＲＯＭ）、デジタル多目的ディスク（ＤＶＤ）またはその他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク装置またはその他の磁気記憶装置、あるいは装置によりアクセスするための情報を記憶するために使用され得る任意のその他の媒体を含むが、限定するものではない。
【００３５】
[0041]一方、通信媒体は、搬送波などの変調されたデータ信号内のコンピュータ読み取り可能な命令、データ構造、プログラムモジュール、またはその他のデータを含む。本明細書で定義されるように、コンピュータ記憶媒体は、通信媒体を含まない。
【００３６】
[0042]メモリ４０６は、その他のモジュール、コンポーネントおよび装置の利便性のために装置内のおよび装置に結合されたハードウェアおよびサービスを管理するように構成されるオペレーティングシステムを含むことができる。幾つかの例では、障害処理サービス１０２の少なくとも一部は、オペレーティングシステム内に、またはオペレーティングシステムにより実装され得る。
【００３７】
[0043]障害処理サービス１０２は、監視モジュール４０８、計算モジュール４１０および構成モジュール４１２の１つまたは複数を含む。本明細書で使用されるように、用語「モジュール」は、議論の目的のために例示的に区分されたソフトウェアを表すことを意図するものであり、何らかの種類の要件あるいは要求された方法、態様または機構を表すことを意図するものではない。したがって、様々な「モジュール」が議論されるが、それらの機能および／または類似の機能は、（例えば、より少ない数のモジュールに結合される、より多くの数のモジュールに分割されるなど）異なる形で配置され得る。さらに、ある機能およびモジュールが、１つまたは複数の装置にまたがる１つまたは複数のプロセッサ上で実行可能なソフトウェアおよび／またはファームウェアにより実装されるように本明細書中に記載されるが、他の実施形態では、モジュールのいずれかまたはすべては、記載した機能を実行するためにハードウェア（例えば、ＡＳＩＣ、特定目的処理装置など）により全体的にまたは一部が実装され得る。他の例では、機能および／またはモジュールは、デバイスドライバー、ファームウェアなどの一部として実装される。
【００３８】
[0044]様々な実施形態に於いて、監視モジュール４０８は、（例えば、ネットワークの少なくとも一部の）ネットワークトポロジを観察し、かつ／またはネットワークトポロジストア４１４内にネットワークトポロジを記憶するように構成される。ネットワークトポロジは、ネットワークの様々なコンポーネントの配置（例えば、装置の場所、装置の種類、装置の機能、装置対間のリンクなど）である。ネットワークトポロジは、ネットワークコンポーネントの配置を表す物理的トポロジおよびネットワーク内のデータフローを表す論理的トポロジを含むことができる。したがって、監視モジュール２０８は、様々な発信元装置（例えば、入口スイッチ）から様々な宛先装置（例えば、出口スイッチ）に伝達されるトラフィックフローを観察し、かつ記憶するように構成される。監視モジュール４０８は、周期的スケジュールに従って、かつ／または特定の事象に応答して、実時間でネットワークトポロジを決定することができる。
【００３９】
[0045]ネットワークトポロジはまた、その他のネットワーク設定、例えば、ネットワーク内の個別のリンクに対する最大リンク容量（例えば、帯域幅）、ネットワーク上のフローの要求する容量を含む。上述のように、障害処理サービス１０２は、実際の障害数が所定の許容される障害の最大数を超過しない限り、リンクが輻輳することがない（例えば、最大リンク容量を超過しない）ことを保証するようにトラフィック量を計算する。
【００４０】
[0046]計算モジュール４１０は、構成設定１１８を計算するように構成される。計算モジュール４１０は、ネットワークトポロジストア４１４から現在のまたは最近のネットワークトポロジを決定する（例えば、受信するまたはアクセスする）ことができる。さらに、計算モジュール４１０は、障害保護レベルストア４１６から１つまたは複数の障害保護レベル１１６を決定する（例えば、受信するまたはアクセスする）ように構成される。障害保護レベル１１６は、ネットワークに対して許容される所定の最大障害数（例えば、リンク障害、スイッチ障害および／またはコントロール障害の１つまたは複数に対する所定の最大数）を指定することができる。障害保護レベルストア４１６は、異なるシナリオにおける計算モジュール４１０によりアクセス可能な変化する障害保護レベルを保存することができる。例えば、障害処理サービス１０２は、異なる時間（例えば、特定の時差帯に対する夜間対昼間）、ネットワーク上の異なる要求などに基づき異なる保護レベルを実装することができる。
【００４１】
[0047]ネットワークトポロジおよび障害保護レベルに基づき、計算モジュール４１０は、ネットワーク内に発生し得る可能性のある障害（例えば、障害の種類、障害箇所など）の異なる組み合わせを表す、モデル、例えば、連立方程式、を生成する。次いで、計算モジュール４１０は、例えば構成設定１１８のような、トラフィック量を計算するためにモデルを使用することができる。上述のように、計算されたトラフィック量は、発生する障害数が（例えば、障害の種類に応じて定義されるような）所定の最大障害数以下である限り、リンクが通信容量を超過することなく、（例えば、１つまたは複数の障害に応答したトラフィック再調整プロセスの一部として）追加のトラフィックがリンクに到着することを可能とする。様々な実施形態の於いて、本明細書でさらに議論するように、保護モジュール４１０は、可能性のある障害の異なる組み合わせに基づき制約を符号化し、次いで、効率的に制約を解決するためにソーティングネットワーク手法を使用することができる。
【００４２】
[0048]構成モジュール４１２は、障害に起因する輻輳およびパケット損失（例えば、まだ発生してはいない未知の障害）が回避され得るように、ネットワーク１０４を構成する命令を発出するように構成される。例えば、構成モジュール４１２は、トラフィックが計算モジュール４１０により計算されたトラフィック量に基づき伝達される、かつ／または配分されるように、ネットワーク内のスイッチング装置に適用するための特定のコマンド（例えば、装置特有コマンド）を生成することができる。
【００４３】
[0049]様々な実施形態の於いて、障害処理サービス１０２は、トラフィックエンジニアリングコントローラの一部として実装され得る。代替として、障害処理サービス１０２は、トラフィックエンジニアリングコントローラとインターフェイスを取るように構成され得る。したがって、装置４０２は、１つまたは複数の通信装置４１８を含むことができる。通信装置４１８は、１つまたは複数のネットワーク（例えば、ネットワーク１０４）、様々なサービスまたはコンテンツプロバイダーにより運用されるアプリケーション、および／またはその他の装置への有線および／または無線接続を容易にするように構成され得る。したがって、通信装置４１８は、様々な通信またはネットワーク接続プロトコルの１つまたは複数を実装することができる。
【００４４】
[0050]図５および図６は、ハードウェア、ソフトウェア、ファームウェアまたはそれらの組み合わせ内に実装され得る一連の動作を表す論理的流れ図として示されるプロセス例を例示する。ソフトウェアの文脈に於いて、動作は、１つまたは複数のプロセッサにより実行される場合、列挙された動作を遂行するようにコンピューティング装置を構成する、コンピュータ実行可能な命令を表す。一般的に、コンピュータ実行可能な命令は、特定の機能を遂行する、または特定の抽象データ型を実装するコンピューティング装置を構成する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。いくつかの実装形態では、動作のいずれかまたはすべては、記載された機能を実行するために、ハードウェア（例えば、ＡＳＩＣ、特定目的処理装置などとして）により全体または一部に実装され得る。いくつかの例では、機能および／またはモジュールは、オペレーティングシステムの一部として実装される。その他の例では、機能および／またはモジュールは、デバイスドライバー、ファームウェアなどの一部として実装される。
【００４５】
[0051]動作が記載されている順序は、限定として制約されることを意図するものではなく、任意の数の記載された動作は、プロセスを実装するために任意の順序で、かつ／または並列に結合され得る。
【００４６】
[0052]図５は、所定の最大障害数まで堅牢である（例えば、リンクが輻輳することがないことを保証する）ようにネットワークを構成するプロセス例５００を例示する。図５に於ける動作例は、図１から図４のいずれか１つに例示されるモジュール、コンポーネントおよび／または要素により説明され得る。
【００４７】
[0053]５０２に於いて、観察モジュール４０８は、ネットワークトポロジを観察し、かつ（例えば、ネットワークトポロジストア４１４内に）記憶することができる。例えば、ネットワークトポロジは、ネットワークの様々な構成要素の配置に関連した情報（例えば、装置の所在、装置の種類、装置の機能、装置対間のリンクなど）を提供することができる。様々な実装に於いて、観察され、かつ記憶されたネットワークトポロジは、ネットワークのフローを記述するトラフィック需要マトリックス（例えば、フローに対する発信元または入口装置、フローに対する宛先または出口装置、フローに対するトラフィックの総量、フローに対するトラフィックのトンネル配分など）を含むことができる。
【００４８】
[0054]５０４に於いて、計算モジュール４１０は、所定の最大障害数を指定した１つまたは複数の障害処理レベルを決定することができる。例えば、計算モジュール４１０は、障害保護レベルストア４１６にアクセスする、またはネットワークを管理するエンティティから障害保護レベルを受信することができる。様々な実施形態に於いて、障害保護レベルは、特定の種類（例えば、リンク障害、スイッチ障害またはコントロール障害）の所定の最大障害数を示すことができる。したがって、計算モジュール４１０は、ネットワークがリンク障害（ｋｅ）、スイッチング装置障害（ｋｖ）、コントロール障害（ｋｃ）、２種類の障害の組み合わせ、またはすべての３種類の障害の組み合わせに対して堅牢であるべきか否かに応じてトラフィック量を計算することによりネットワーク保護のレベルを変化させることができる。
【００４９】
[0055]５０６に於いて、計算モジュール４１０は、ネットワークトポロジおよび障害保護レベルに基づき可能性のある障害の異なる組み合わせを捕捉するモデルを生成することができる。例えば、計算モジュール４１０は、ネットワークトポロジストア４１４および障害保護レベルストア４１６内の情報にアクセスすることができる。様々な実施形態に於いて、モデルは、可能性のある障害に関連した変数（例えば、トポロジにより記述されるネットワーク配置内の障害の場所）を含む連立方程式である。
【００５０】
[0056]５０８に於いて、計算モジュール４１０は、ネットワーク内のリンク上で伝達されるべき、個々のフローに対するトラフィック量を計算することができる。例えば、計算モジュール４１０は、発生する障害数が（例えば、障害の種類に対して定義されるような）所定の最大障害数以下である限り、計算されたトラフィック量が、リンクが通信容量を超過することなく、（例えば、１つまたは複数の障害に応答して比例トラフィック再調整プロセスの一部として）追加のトラフィックがリンクに到着することを可能とするように連立方程式を解くことができる。
【００５１】
[0057]５１０に於いて、構成モジュール４１２は、計算されたトラフィック量に基づき構成設定を生成し、かつ構成設定（例えば、命令、コマンドなど）をネットワークに提供することができる。
【００５２】
[0058]図６は、障害処理サービスが可能性のある障害の異なる組み合わせに関連した制約を効率的に解決することができるように、ソーティングネットワーク手法を使用する処理例６００を例示する。図６に於ける、動作例は、図１から図５のいずれか１つに例示されたモジュール、コンポーネント、要素および／または動作を参照して記述され得る。例えば、処理例６００は、図５内の動作５０６および／または動作５０８に従って実装され得る。
【００５３】
[0059]６０２に於いて、計算モジュール４１０は、モデル（例えば、連立方程式）により捕捉された可能性のある障害の異なる組み合わせに基づき解決されるべき第１の数の制約を決定する。上述のように、障害処理サービス１０２が制約の解決に於ける計算上の課題で提示されるような、制約の第１の数が十分に大きいシナリオが存在し得る。
【００５４】
[0060]６０４に於いて、計算モジュール４１０は、ソーティングネットワークを使用して制約の第１の数を制約の第２の数に削減することができる。このことは、より少ない計算上のオーバーヘッドで計算を遂行可能とする。
【００５５】
[0061]６０６に於いて、計算モジュール４１０は、第２の数の制約を解決し、かつネットワーク内で伝達されるべきトラフィック量を計算する。
[0062]ネットワークが所定の最大障害数まで堅牢であるようにフローのトラフィック配分を決定するために遂行される計算例が本明細書で提供される。上述のように、ネットワーク１０４は、多数の装置（例えば、数十、数百、数千など）を含むことができる。したがって、可能性のある障害の異なる組み合わせ（例えば、所定の最大数までの障害数の所在）を決定することは、可能性のある障害の異なる組み合わせに関連した大きな数の制約を計算し、かつ解決することが必要となる大きなオーバーヘッド量に起因する計算上の課題を提示している。最大ｋ個の障害（例えば、所定の最大数）が許容される場合、ｎ個の可能性のある障害（例えば、ネットワーク１０４内の様々なスイッチに１つに位置するスイッチ障害１１０、ネットワーク１０４内の様々なリンクの１つに位置するリンク障害１１２、ネットワーク１０４内の様々なスイッチの１つにおけるコントロール障害１１４）を被る余地のあるネットワークに対する計算上の課題は、以下の式のように表現され得る。
【００５６】
【数１】
0006527584.tif 000002
【００５７】
[0063]式（１）を用いると、ｎ＝１０００（例えば、大規模なネットワーク内の妥当なリンク数）かつｋ＝３の場合、最大で３個の障害がネットワークコンポーネントにわたって発生する、異なる組み合わせの数は１０９より多い。このことは解決するために大量の計算上のオーバーヘッドを必要とする。
【００５８】
[0064]計算モジュール４１０は、可能性のある障害の異なる組み合わせに関連した多数の制約を「有界Ｍ和」問題（例えば、Ｎ個の変数の内任意のＭ個の合計が有界である）に変換することにより計算上のオーバーヘッドを削減するように構成される。したがって、問題中の多数の制約は、最大、または最小のＭ個の変数上の単一の制約に削減され得る。計算モジュール４１０は、本明細書でさらに議論されるように、Ο（ｋｎ）線形束縛条件として有界Ｍ和問題を効率的に符号化するためにソーティングネットワーク手法を使用することができる。計算モジュール４１０は、以下に基づき可能性のある障害の異なる組み合わせをモデル化する。
（ｉ）スイッチング装置が新しい構成で更新することに失敗した場合（例えば、コントロール障害）、スイッチング装置は古い構成を使用し、（ｉｉ）リンクが故障した場合（例えば、リンク障害）、入口スイッチング装置は決定論的にトラフィックを再調整する（例えば、比例再調整）。
【００５９】
[0065]本明細書で提供される説明は、トラフィックエンジニアリング（ＴＥ）に関連した実装例に於いて障害からネットワークを保護するために障害処理サービス１０２を使用する。
表１は、ネットワークのトラフィックエンジニアリングに関連して使用される表記法を提供する。
【００６０】
【表１】
0006527584.tif 000003
【００６１】
【表２】
0006527584.tif 000004
【００６２】
[0066]このように、トラフィックエンジニアリング実装に於ける障害処理サービス１０２への入力は、グラフＧ＝（Ｖ，Ｅ）であり、ここで、Ｖはスイッチング装置の集合であり、Ｅは、それぞれの直接リンクが２つのスイッチング装置間に確立される直接リンクの集合である。グラフＧは、監視モジュール４０８により決定され、かつ記憶されるネットワークトポロジの少なくとも一部を表す。Ｅ内の各リンクｅは、容量ｃｅ（例えば、図２および図３の例の中で提供されるように所定の容量、例えば１０ユニット）を有することができる。計算モジュール４１０は、各フローｆが、入口スイッチング装置から出口スイッチング装置に伝達されるトラフィックの集合であるフローの集合としてネットワーク上のトラフィック要求を表す。トラフィックエンジニアリング（ＴＥ）間隔内の帯域幅要求ｆは、ｄｆであり、かつトラフィックは、事前に確立されたトンネル集合Ｔｆに分散させられ得る。
【００６３】
[0067]この実装例では、計算モジュール４１０は、各フローの出力帯域幅割当｛ｂｆ｜∀ｆ｝および各トンネルを通過するできるフロー量｛ａｆ，ｔ｜∀ｆ，ｔ∈Ｔｆ｝を計算するように構成される。計算モジュール４１０は、帯域幅割当、例えば、ＤＣＮまたはＷＡＮに対して、以下のような経路制約のある多品種フロー問題に基づき解決する（例えば、計算する）ことができる。
【００６４】
ｍａｘ  Σｆ∈Ｆｂｆ      式（２）
【００６５】
【数２】
0006527584.tif 000005
【００６６】
【数３】
0006527584.tif 000006
【００６７】
∀ｆ∈Ｆ、ｔ∈Ｔｆ：  ０≦ｂｆ≦ｄｆ；０≦ａｆ，ｔ      式（５）
[0068]式（２）は、ネットワークスループットを最大化するように定式化される。式（３）は、ネットワーク内のリンクが過負荷になるべきでないことを示す。式（３）に於いて、ｌ［ｔ，ｅ］は、トンネルｔがリンクｅを通過するか否かを示すバイナリ変数である。式（３）は、トンネルにまたがったフローの割当の合計が、フローに割り当てられたレート未満とならないことを示す。式（４）は、フローに許可された帯域幅がフローの要求を超えることがないこと、および変数が負ではないことを示す。幾つかの実装では、計算モジュール４１０は、フローおよび入口スイッチが式（６）で提供されるトラフィック配分重み付けを使用するように、それらのレートリミッター｛ｂｆ｝を更新することができる。
【００６８】
【数４】
0006527584.tif 000007
【００６９】
[0069]様々な実施形態に於いて、コントロールプレーン障害（例えば、コントロール障害１１４）をモデル化するために、計算モジュール４１０は、ｋｃまたはより少ないスイッチング装置が古い構成（｛ｂ’ｆ｝，｛ａ’ｆ，ｔ｝）を更新することに失敗しない限り、例えば、リンクに於いて、輻輳が発生しないように、新しい構成（｛ｂｆ｝，｛ａｆ，ｔ｝）を計算する。本明細書で使用されるように、（ｉ）λｖ＝１は入口スイッチｖでフローの少なくとも１つに対する構成失敗を示し、（ｉｉ）λｖ＝０は入口スイッチに於いて開始されるすべてのフローに対する構成が成功していることを示す。計算モジュール４１０は、各スイッチング装置の状態を示すベクトルλ＝［λｖ│ｖ∈Ｖ］によりネットワーク内のコントロールプレーン障害を表すことができる。したがって、計算されたネットワーク構成が、ｋｃ障害に対して堅牢であることを保証するために、ネットワークは、式（７）により表わされる一群の状況下で過負荷リンクを有することはできない。
【００７０】
【数５】
0006527584.tif 000008
【００７１】
[0070]計算モジュール４１０は、式（８）に示すように、式（７）の必要条件を捕捉することができる。
【００７２】
【数６】
0006527584.tif 000009
【００７３】
[0071]式（８）に於いて、
【００７４】
【数７】
0006527584.tif 000010
【００７５】
は、式（９）に表されるようになんらの構成の障害もない場合に、スイッチング装置ｖに於いて開始されるフローから、リンクｅに到着し得る総トラフィックである。
【００７６】
【数８】
0006527584.tif 000011
【００７７】
[0072]式（９）に於いて、ｓ［ｔ，ｖ］はトンネルｔに対する発信元スイッチング装置がｖであるか否かを示すバイナリ変数である。
[0073]式（８）に於いて、
【００７８】
【数９】
0006527584.tif 000012
【００７９】
は、障害発生（例えば、λｖ＝１）時の、ｖに於いて開始されるフローからのリンクｅのトラフィックの上界であり、以下の式（１０）のように表され得る。
【００８０】
【数１０】
0006527584.tif 000013
【００８１】
[0074]式（１０）に於いて、βｆ，ｔは、障害がｆに対して発生する場合のトンネルｔ上のフローのトラフィックの上界である。レートリミッター内の更新が成功した場合の例では、βｆ，ｔは以下の式（１１）のようにモデル化され得る。
【００８２】
∀ｆ∈Ｆ，ｔ∈Ｔｆ：βｆ，ｔ＝ｍａｘ｛ｗ’ｆ，ｔｂｆ，ａｆ，ｔ｝      式（１１）
[0075]式（１１）に於いて、ｗ’ｆ，ｔは、（例えば、監視モジュール４０８により知られるまたは観察され得る）古い構成に於けるトンネルｔに対するフローの配分の重み付けである。
【００８３】
[0076]したがって、式（８〜１１）を使用して、計算モジュール４１０は、ｋｃコントロールプレーン障害に対して堅牢であるＴＥ構成を見出すことができる。別な言い方をすれば、ネットワークは、ネットワーク輻輳（例えば、リンクがその容量を超過する）を引き起こすことなくｋｃ個のコントロールプレーン障害までを処理することができる。
【００８４】
[0077]様々な実施形態に於いて、データプレーン障害（例えば、スイッチ障害１１０またはリンク障害１１２）をモデル化するために、計算モジュール４１０は、（ｉ）故障したリンク数がｋｅ以下であり、（ｉｉ）故障したスイッチング装置がｋｖ以下である限り、輻輳が発生しないようにフロー割当を計算する。これは、故障したスイッチング装置に付随しないリンク障害に対して適用することができる。計算モジュール４１０は、スイッチング装置が多数の付随するリンクを有することから、スイッチング装置障害およびリンク障害を別個に考慮することができる。故障しているリンクｅは、μｅ＝１として示され、また、スイッチ障害はηｖ＝１として示され得る。前記の文章中の変数は、リンクまたはスイッチが故障していない場合ゼロとなろう。次いで、計算モジュール４１０は、ベクトル（μ，η）としてデータプレーン障害を表すことができ、ここで、ベクトルμ＝［μｅ│ｅ∈Ｅ］、またベクトルη＝［ηｖ│ｖ∈Ｖ］である。トラフィックエンジニアリング構成がｋｅ個のリンク障害およびｋｖ個のスイッチ障害に対して堅牢であることを保証するためには、式（１２）により指定されるようなハードウェア障害の場合の集合のもとで過負荷リンクがないことが必要である。
【００８５】
【数１１】
0006527584.tif 000014
【００８６】
[0078]データプレーン障害は、入口スイッチング装置がトラフィックを再調整する（例えば、影響を受けたトンネルから残余のトンネルへトラフィックを移動する）場合、それらの障害が、ネットワーク上のトラフィック配分を変更することから輻輳を引き起こす可能性がある。したがって、障害のケース（μ，η）が与えられると、計算モジュール４１０は、故障したリンクおよび／または故障したスイッチを通過しない各フローｆの残余のトンネル
【００８７】
【数１２】
0006527584.tif 000015
【００８８】
を知り、かつフローｆの残余のトンネルは、式（１３）により表されるように割り当てられたレートを保持することを可能としなければならない。
【００８９】
【数１３】
0006527584.tif 000016
【００９０】
[0079]フローｆが故障ケース（μ，η）のもとで残余のトンネルを有しない状況、例えば、
【００９１】
【数１４】
0006527584.tif 000017
【００９２】
、では、フローの大きさｂｆはゼロに固定され得る。したがって、式（１３）はいずれのリンクも過負荷ではないことを保証する。
[0080]式（１３）を見ると、残余のトンネルの数が増加すると、ネットワークスループットもまた増加する。このように、様々な実施形態では、ネットワークトポロジは、（例えば、障害処理サービス、別のトラフィックエンジニアリングコントローラなどにより）、障害が発生した場合に、フローに対するトンネルの喪失（例えば、トンネル喪失の数）が最小化されるように、トンネルを割付することによりネットワークスループットを改善するように構成され得る。例えば、ネットワークは、個別のフローに対して、最大でｐ本のトンネルがリンクを通過し、かつ最大でｑ本のトンネルがスイッチング装置を通過することができるように、（ｐ，ｑ）リンク−スイッチの互いに素なトンネルに基づき構成され得る。パラメータｐおよびｑは、障害処理サービス１０２および／またはトラフィックエンジニアリングコントローラにより定義され、かつフロー固有であり得る。
【００９３】
[0081]上述のように、ネットワークに対する可能性のある障害の異なる組み合わせをモデル化する結果生じる多数の制約を解決するために、計算モジュール４１０は、有界Ｍ和問題に制約を変換し、次いでソーティングネットワークを使用して、有界Ｍ和問題を符号化するように構成される。有界Ｍ和問題は、Ｎ個の変数集合が与えられると、それらの変数の任意のＭ個の総計が境界Ｂより少ないか、または境界Ｂより大きくなければならないというように定義され得る。したがって、ＮＭが、濃度Ｍ以下であるすべての変数サブセットの集合である場合、有界Ｍ和問題は、以下の式（１４）で表され得る。
【００９４】
【数１５】
0006527584.tif 000018
【００９５】
[0082]式（１４）に於いて、Ｓは、異なる可能性のある障害の組み合わせを表す。ｎｊがＮ個の中でｊ番目に大きい変数に対する式である場合、すべての上記の制約は、次式の場合に保持される。
【００９６】
【数１６】
0006527584.tif 000019
【００９７】
[0083]したがって、計算モジュール４１０は、Ｎ個中の最大のＭ個の変数に対する効率的な（一次）式を発見することができ、したがって、計算モジュール４１０は、元の制約（例えば、多数の制約）をより効率的に解決され得る削減された数の制約（例えば、１つの制約）で置き換えることができる。
【００９８】
[0084]コントロールプレーン障害の場合には、式（８）は、制約を有界Ｍ和問題に変換するために式（１６）のように書き換えられ得る。
【００９９】
【数１７】
0006527584.tif 000020
【０１００】
[0085]
【０１０１】
【数１８】
0006527584.tif 000021
【０１０２】
、Ｄ中でｊ番目に大きい要素であるｄｊを用いて、かつ
【０１０３】
【数１９】
0006527584.tif 000022
【０１０４】
であることから、式（１６）は、以下の式（１７）と等価である。
【０１０５】
【数２０】
0006527584.tif 000023
【０１０６】
[0086]したがって、計算モジュール４１０は、元の
【０１０７】
【数２１】
0006527584.tif 000024
【０１０８】
の制約を│Ｅ│の制約（例えば、各リンクごとに１つ）に変換するために式（１６）および式（１７）を使用することができる。
[0087]データプレーン障害の場合には、フローｆのトンネルは、（ｐｆ，ｑｆ）互いに素なリンク−スイッチとして表され得る。したがって、データプレーン障害のケース
【０１０９】
【数２２】
0006527584.tif 000025
【０１１０】
に対して、残余のトンネルの数は、τｆ＝│Ｔｆ│−ｋｅｐｆ−ｋｖｑｆ未満ではない。
【０１１１】
【数２３】
0006527584.tif 000026
【０１１２】
がＡｆ＝｛ａｆ，ｔ│ｔ∈Ｔｆ｝内のｊ番目の最小要素である場合、式（１８）は式（１３）内のすべての制約が満足されることを保証する。
【０１１３】
【数２４】
0006527584.tif 000027
【０１１４】
[0088]計算モジュール４１０は、式（１８）内の左辺が、フローｆが
【０１１５】
【数２５】
0006527584.tif 000028
【０１１６】
内の任意のケースのもとでフローの残余のトンネルから得ることができる、最悪の場合の帯域幅割当であることから、すべての制約が満足されることを保証することができる。
[0089]次いで、計算モジュール４１０は、ソーティングネットワークに基づき一次制約として最大のＭ個の変数を表す。ソーティングネットワークは、任意のＮ値の配列をソートすることができる比較−入替え演算子のネットワークである。４つの入力値７０２（例えば、ｘ１＝６、ｘ２＝８、ｘ３＝４、ｘ４＝９）をソートするソーティングネットワーク例７００が、図７に示される。このネットワーク例７００は、各比較−入替え演算子が左から２つの入力を取り、２つの入力を比較し、かつ２つの入力の内の大きいものを上方に、２つの入力の内の小さいものを下方に移動するソート・マージアルゴリズムに基づいている。ソーティングネットワークの特性は、比較−入替え演算子のシーケンスが、入力と独立に実装されることである。この特性は、計算モジュール４１０が最大の変数から最小の変数までのそれぞれに対して一次式として計算を符号化することを可能とする。したがって、ネットワーク例７００の出力７０４（例えば、ｙ１、ｙ２、ｙ３、ｙ４）はソートされた順番（例えば、９＞８＞６＞４）となる。
【０１１７】
[0090]最大のＭ個の変数はソートされるべきであることから、計算モジュール４１０は、Ο（ＮＭ）演算子を有する部分ネットワークを使用することができる。様々な実施形態に於いて、計算モジュール４１０は、最大のＭ個の値を生み出すステージ数の後終了するバブルソートを使用してソーティングネットワークを実装することができる。
実装例
[0091]実装Ａ、ネットワークの少なくとも一部に対する所定の最大障害数を決定するステップと、ネットワークの少なくとも一部の１つまたは複数のフローを決定するステップと、１つまたは複数のハードウェアプロセッサにより、少なくとも部分的には所定の最大障害数に基づき、ネットワークの少なくとも一部に対する１つまたは複数の障害の異なる組み合わせのモデルを生成するステップと、少なくとも部分的には、モデルに基づき、１つまたは複数のフロー中の個別のフローに対して、少なくともネットワークの一部内に発生する実際の障害数が所定の最大障害数以下である場合、輻輳が回避されるように、１つまたは複数の個別の経路を介して伝達されるべきトラフィック量を計算するステップと、１つまたは複数のフロー中の個別のフローに対して、少なくとも部分的には、１つまたは複数の個別の経路上で伝達されるべきトラフィック量に基づきネットワークの少なくとも一部内にトラフィックを配分させるステップと、を含む方法。
【０１１８】
[0092]実装Ｂ、１つまたは複数のフローが個別に発信元装置から宛先装置へトラフィックを伝達し、かつ１つまたは複数のフローがネットワークトポロジを通過する実装Ａの方法であって、ネットワークトポロジが、ネットワークの少なくとも一部内の複数の装置および複数の装置間の複数のリンクの配置と、所定の最大障害数が超過しない限り、複数のリンク中の個別のリンクの容量が超過しないことを計算が保証する、複数のリンク中の個別のリンクに対する容量と、を表す実装Ａの方法。
【０１１９】
[0093]実装Ｃ、追加のトラフィックが最大障害数以下の発生に応答して到着する場合、容量が超過することがないように、１つまたは複数の個別の経路を介して伝達されるべきトラフィック量を計算するステップが、複数のリンク中の個別のリンク上で利用可能な帯域幅を提供する、実装Ｂの方法。
【０１２０】
[0094]実装Ｄ、さらに、１つまたは複数の障害の異なる組み合わせをモデル化するためにネットワークの少なくとも一部のネットワークトポロジを観察するステップを含む、実装Ａまたは実装Ｂの方法。
【０１２１】
[0095]実装Ｅ、モデルがネットワークの少なくとも一部に対する１つまたは複数の障害の異なる組み合わせに関連した第１の数の制約を含み、方法がさらに、１つまたは複数の個別の経路を介して伝達されるべきトラフィック量を計算するステップに先立ってソーティングネットワークを使用して制約の第１の数より少ない制約の第２の数に制約の第１の数を削減するステップを含む、実装Ａから実装Ｄのいずれか１つの方法。
【０１２２】
[0096]実装Ｆ、所定の最大障害数が、１つまたは複数のスイッチング装置が現在の構成を古い構成から新しい構成に更新することに失敗する、または現在の構成を古い構成から新しい構成に更新することに遅延するコントロール障害に関連付けられる、実装Ａから実装Ｅのいずれか１つの方法。
【０１２３】
[0097]実装Ｇ、所定の最大障害数が、１つまたは複数のスイッチング装置がトラフィックを伝達することに失敗し、かつ伝達できないスイッチ障害に関連付けられる、実装Ａから実装Ｅのいずれか１つの方法。
【０１２４】
[0098]実装Ｈ、所定の最大障害数が、１つまたは複数のリンクがトラフィックを伝達することに失敗し、かつ伝達できないリンク障害に関連付けられる、実装Ａから実装Ｅのいずれか１つの方法。
【０１２５】
[0099]実装Ｉ、トラフィックを個別のフローに対するネットワークの少なくとも一部に配分させるステップが、１つまたは複数のスイッチング装置に配分命令を発出するステップを含む、実装Ａから実装Ｈのいずれか１つの方法。
【０１２６】
[00100]実装Ｊ、１つまたは複数のプロセッサにより実行される時、ネットワークの少なくとも一部に対する所定の最大障害数を決定するステップと、１つまたは複数の個別のリンクに対して、ネットワークの少なくとも一部内の１つまたは複数のリンクに対する通信容量を決定し、ネットワーク内で実際に発生する障害数が所定の最大障害数以下である限り、個別のリンクが通信容量を超過することがないように、ネットワークの少なくとも一部に対するトラフィック構成を計算するステップと、少なくとも部分的にはトラフィック構成に基づきネットワークの少なくとも一部を構成するステップとを行うために、１つまたは複数のプロセッサをプログラミングする、コンピュータ実行可能な命令を記憶する１つまたは複数のコンピュータ記憶媒体。
【０１２７】
[00101]実装Ｋ、実行可能な命令がさらに、少なくとも部分的には、ネットワークの少なくとも一部のトポロジおよび所定の最大障害数に基づき可能性のある障害の異なる組み合わせのモデルを生成するステップであって、該モデルがネットワークの少なくとも一部に対する可能性のある障害の異なる組み合わせに関連付けられた第１の数の制約を含む、ステップと、ネットワークの少なくとも一部に対するトラフィック構成を計算するステップに先立ち、ソーティングネットワークを使用して制約の第１の数未満の制約の第２の数に制約の第１の数を削減するステップとを行うために、１つまたは複数のプロセッサをプログラミングする、実装Ｊの１つまたは複数のコンピュータ記憶媒体。
【０１２８】
[00102]実装Ｌ、所定の最大障害数が、１つまたは複数のスイッチング装置が現在の構成を古い構成から新しい構成に更新することに失敗する、または現在の構成を古い構成から新しい構成に更新することに遅延する、コントロール障害に関連付けられる、実装Ｊまたは実装Ｋの１つまたは複数のコンピュータ記憶媒体。
【０１２９】
[00103]実装Ｍ、所定の最大障害数が、１つまたは複数のスイッチング装置がトラフィックを伝達することに失敗し、かつ伝達できないスイッチ障害に関連付けられる、実装Ｊまたは実装Ｋの１つまたは複数のコンピュータ記憶媒体。
【０１３０】
[00104]実装Ｎ、所定の最大障害数が、１つまたは複数のリンクがトラフィックを伝達することに失敗し、かつ伝達できないリンク障害に関連付けられる、実装Ｊまたは実装Ｋの１つまたは複数のコンピュータ記憶媒体。
【０１３１】
[00105]実装Ｏ、１つまたは複数のプロセッサと、１つまたは複数のメモリと、１つまたは複数のメモリ上に記憶される計算モジュールであって、ネットワークトポロジにアクセスするステップと、ネットワークの少なくとも一部で実際に発生する障害数が所定の許容される障害の最大数以下である限り、ネットワークの少なくとも一部内の個別のリンクが通信容量を超過することがないように、少なくとも部分的には、ネットワークトポロジに基づき、ネットワークの少なくとも一部に対するトラフィック構成を計算するステップとを行うために、１つまたは複数のプロセッサにより実行される計算モジュールと、１つまたは複数のメモリ上に記憶される構成モジュールであって、少なくとも部分的には、計算されたトラフィック構成に基づきネットワークを構成するステップを行うために、１つまたは複数のプロセッサにより実行される構成モジュールと、を含む１つまたは複数の装置。
【０１３２】
[00106]実装Ｐ、所定の最大障害数が、１つまたは複数のスイッチング装置が現在の構成を古い構成から新しい構成に更新することに失敗する、または現在の構成を古い構成から新しい構成に更新することに遅れるコントロール障害に関連付けられる、実装Ｏの１つまたは複数の装置。
【０１３３】
[00107]実装Ｑ、所定の最大障害数が、１つまたは複数のスイッチング装置がトラフィックを伝達することに失敗し、かつ伝達できないスイッチ障害に関連付けられる、実装Ｏの１つまたは複数の装置。
【０１３４】
[00108]実装Ｒ、所定の最大障害数が、１つまたは複数のリンクがトラフィックを伝達することに失敗し、かつ伝達できないリンク障害に関連付けられる、実装Ｏの１つまたは複数の装置。
【０１３５】
[00109]実装Ｓ、計算モジュールが、少なくとも部分的には、ネットワークトポロジおよび所定の最大障害数に基づき可能性のある障害の異なる組み合わせのモデルを生成するステップであって、モデルが、ネットワークの少なくとも一部に対する可能性のある障害の異なる組み合わせに関連した第１の数の制約を含む、ステップと、トラフィック構成を計算するステップに先立ちソーティングネットワークを使用して制約の第１の数未満である制約の第２の数に制約の第１の数を削減するステップとをさらに行う、実装ＯからＲのいずれか１つの中の１つまたは複数の装置。
【０１３６】
[00110]実装Ｔ、構成モジュールが、１つまたは複数のスイッチング装置にフロー配分の重み付けを提供することによりネットワークを構成する、実装ＯからＳのいずれか１つの中の１つまたは複数の装置。
【０１３７】
結論
[00111]本開示は、構造的特徴および／または方法論的動作に固有の言語を使用することができるが、本発明は、本明細書に記載された特定の特徴または動作に限定されるものではない。むしろ、特定の特徴および動作は、本発明の例示的な形態として開示されるものである。
【図１】
0006527584.tif 000029
【図２】
0006527584.tif 000030
【図３】
0006527584.tif 000031
【図４】
0006527584.tif 000032
【図５】
0006527584.tif 000033
【図６】
0006527584.tif 000034
【図７】
0006527584.tif 000035