差異化サービス機能を備えたＭＰＬＳネットワーク用の動的なトラフィックの再配列および復元
複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに少なくとも１つの代替パスが提供される。複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅が決定される。ネットワーク内の使用可能リンクから提案ルートが生成される。提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を、必要な帯域幅に割り振ることができる。提案ルートの帯域幅が必要な帯域幅より小さい場合、少なくとも１つの他のルートが生成され、最低数の他のルートが生成されるように、必要な帯域幅は提案ルートと少なくとも１つの他のルートとの間で分割される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報パケットの転送に使用されるネットワークを対象とし、より具体的に言えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）を組み込んだネットワークを対象とする。
【背景技術】
【０００２】
本出願は、その開示が参照により本明細書に組み込まれた、２００４年５月１９日付け出願の米国特許仮出願第６０／５７２５１２号の利益を主張する。
【０００３】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を使用するネットワークは、パケットがネットワークを介して転送される前に決定されるエンドツーエンド接続パスを介した、ネットワークを通じたパケットの転送を可能にするものである。パケットがＭＰＬＳネットワークに入ると、そのパケットには、ラベルエッジルータ（ＬＥＲ）とも呼ばれる入口（ｉｎｇｒｅｓｓ）ルータによって「ラベル」が割り当てられ、さらにこのルータがパケットにラベルを添付して、そのパケットをラベルスイッチルータ（ＬＳＲ）と呼ばれる一連のルータのうちの第１のルータに転送し、これらのルータが接続パスに沿ってパケットを転送する。ラベルには、第１のルータがパケットを転送する次のルータを決定するために使用する情報が含まれる。次に第１のルータはパケットを受信し、ラベルを除去した後、次のルータがパケットをスイッチする後続のルータを決定するために使用することになる新しいラベルを添付する。このプロセスは、接続パスに沿って配置された各ルータに対して繰り返される。すなわち、パスに沿った各ルータは、直前のルータによって添付されたラベルの付いたパケットを受け取り、ラベルに含まれる情報を使用して次にパケットを受け取る次のルータを決定し、現在のラベルをはがし、後続のルータが使用することになる新しいラベルを貼付した後、パケットをそのルータに転送する。このプロセスは、パケットがパスに沿って、出口ルータまたはＬＥＲとも呼ばれる最後のルータに送達された時点で終了する。
【０００４】
ラベルは、各ルータが転送トラフィックとも呼ばれる接続パスに沿ってパケットを転送する方法を決定するために使用されることから、この接続パスは、ラベルスイッチパス（ＬＳＰ）とも呼ばれる。各ラベルはＬＳＰの一部のみに関する情報を含み、各ルータまたはスイッチに必要なのは、特定ラベルに対応するルートに関する情報を格納すること、およびパケットに貼付されることになる次のラベルを格納することのみである。
【０００５】
ＬＳＰを含む特定のルートは、通常、ある一定レベルの性能を保証すること、ネットワークの輻輳を避けてルーティングすること、または特定用途の要件に準拠することなどの、様々な理由に基づいて決定される。通常、１次ＬＳＰがセットアップされると同時に、１つまたは複数のバックアップＬＳＰも決定される。バックアップパス用のルートは、１次ＬＳＰのセットアップ時に静的に決定するか、または１次ＬＳＰの障害時にのみ動的に決定することができる。バックアップパスは、通常、１次ＬＳＰと同じ帯域幅を有する。
【０００６】
ルータ障害、ルータインターフェース障害、またはリンク障害が発生した場合などの、ネットワーク内に障害が発生した場合、障害のあるＬＳＰを介して搬送されたパケットは、その対応するバックアップＬＳＰのうちの１つにスイッチされる。しかしながら、時には、ネットワーク障害によって１次ＬＳＰおよびそのバックアップＬＳＰに障害が発生する場合もある。現在のＭＰＬＳネットワーク回復スキームは、こうした状況に対処しない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、ネットワークの可用性およびサービスの可用性を増加させるために、こうした状況を処理するトラフィック復元スキームを有することが望ましい。こうしたスキームに、障害のあったＬＳＰによって搬送されたトラフィックと同量程度のトラフィックをできる限り搬送する、１つまたは複数の置換（ｒｅｐｌａｃｅｍｅｎｔ）ＬＳＰを作成させることも望ましい。さらに復元スキームが、ネットワークリソースの効率的な使用を考慮すること、およびトラフィックエンジニアリングポリシーを使用することによって、置換ＬＳＰを作成することも望ましい。
【課題を解決するための手段】
【０００８】
本発明の方法によれば、ネットワークの複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替（ｓｕｂｓｔｉｔｕｔｅ）パスが提供される。この方法は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを含む。
【０００９】
本発明の前述の方法によれば、複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。提案ルートは使用可能な最大帯域幅を有するルートとすることができる。
【００１０】
複数の既存のパスは、複数のサービスクラスのトラフィックを搬送可能であり、前述の決定ステップは、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップを含むことが可能であり、割り振りステップは、提案ルートの帯域幅の一部を、複数の必要な帯域幅内の選択された要素に割り振るステップと、提案ルートの帯域幅が選択された帯域幅要素よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。選択された帯域幅要素は、複数の必要な帯域幅内で最大の非割り振り帯域幅要素とすることができる。この方法は、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅内の、たとえばＸと呼ばれる他の帯域幅要素に割り振るステップと、提案ルートの帯域幅の残りの部分が帯域幅値Ｘよりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むこともできる。帯域幅要素Ｘは、複数の必要な帯域幅内の残りの非割り振り帯域幅要素のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００１１】
この方法は、複数の必要な帯域幅内のたとえばＸと呼ばれる各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分を帯域幅要素Ｘに連続的に割り振るステップと、提案ルートの帯域幅の残りの部分が帯域幅要素Ｘの帯域幅値よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、さらに含むことができる。
【００１２】
この方法は、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、生成されたすべてのルート間で必要な帯域幅を分割するステップとを、含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、決定するステップは、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップを含むことが可能であり、生成するステップは、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の１つよりも少ない場合、少なくとも１つの他のルートを生成するステップと、生成されたすべてのルート間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを生成されたルートに割り当てるステップとを、含むことができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。この方法は、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、さらに含むことができる。他の帯域幅は、選択されたルートの帯域幅の残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。この方法は、複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、含むこともできる。
【００１３】
この方法は、ネットワークの複数のリンクのそれぞれをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとによって、提案ルートの生成に先立って使用可能帯域幅およびリンクを提供するステップを含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、予約帯域幅、最大帯域幅、および使用可能帯域幅を決定するステップは、複数のリンクのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するために、複数のクラスそれぞれについて実行することができる。
【００１４】
本発明の装置は、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する。この装置は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを、実行するように動作可能な、置換ユニットを含む。
【００１５】
この装置によれば、複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）である。提案ルートは使用可能な最大帯域幅を有することができる。
【００１６】
複数の既存のパスは、複数のサービスクラスに対応するこうした複数の必要な帯域幅を決定するステップと、提案ルートの帯域幅の一部を、複数の使用される帯域幅のうちの所与の１つに割り振るステップと、提案ルートの帯域幅が所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能な、置換ユニットを使用して、複数のサービスクラスのトラフィックを搬送することができる。所与の帯域幅は、複数の必要な帯域幅のうちで最大の非割り振り帯域幅とすることができる。
【００１７】
さらにこの置換ユニットは、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、提案ルートの帯域幅の残りの部分が他の帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。他の帯域幅は、複数の必要な帯域幅の残りの非割り振り帯域幅のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００１８】
さらにこの置換ユニットは、複数の必要な帯域幅のうちの各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、提案ルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。
【００１９】
さらにこの置換ユニットは、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で必要な帯域幅を分割するステップとを、実行するように動作可能であるものとすることができる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、置換ユニットは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを実行するように動作可能であり、さらに、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、提案ルートおよび少なくとも１つの他のルートの間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを少なくとも１つの他のルート内の提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。
【００２０】
さらにこの置換ユニットは、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のうちの一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。他の帯域幅は、選択されたルートの帯域幅の残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。
【００２１】
この置換ユニットは、複数の必要な帯域幅の各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、実行するように動作可能であるものとすることもできる。
【００２２】
さらにこの置換ユニットは、提案ルートを生成するように動作可能になるのに先立って、使用可能帯域幅およびリンクを提供するステップを実行するように動作可能であることが可能であり、これには、ネットワークの複数のリンクのそれぞれについてそのリンクをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとを、実行するように動作可能であることも含まれる。複数のクラスのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するように動作可能とすることによって、複数のクラスそれぞれについて、予約帯域幅、最大帯域幅、および使用可能帯域幅を決定するように動作可能な置換ユニットを使用して、複数の既存のパスが複数のサービスクラスのトラフィックを搬送することができる。
【００２３】
本発明の記録媒体には、ネットワークの複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替パスを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録される。この方法は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを含む。
【００２４】
前述の記録媒体によれば、複数のパスのそれぞれが、少なくとも１つの障害リンクをトラバースすることができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。提案ルートは使用可能な最大帯域幅を有することができる。
【００２５】
複数の既存のパスは、複数のサービスクラスのトラフィックを搬送可能であり、コンピュータ読み取り可能プログラムのこの方法の決定ステップは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含むことが可能であり、この方法の割り振りステップは、提案ルートの帯域幅の一部を、複数の必要な帯域幅内の所与の１つに割り振るステップと、提案ルートの帯域幅が所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。
【００２６】
所与の帯域幅は、複数の必要な帯域幅のうちで最大の非割り振り帯域幅とすることができる。さらに前述の方法は、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、提案ルートの帯域幅の残りの部分が他の帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。他の帯域幅は、複数の必要な帯域幅内の残りの非割り振り帯域幅のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００２７】
コンピュータ読み取り可能プログラムのこの方法は、複数の必要な帯域幅のうちの各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、提案ルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、さらに含むことができる。
【００２８】
コンピュータ読み取り可能プログラムのこの方法は、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で必要な帯域幅を分割するステップとを、含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、この記録方法のうちの決定するステップは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含むことが可能であり、この記録方法のうちの少なくとも１つの他のルートを生成するステップは、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の１つよりも少ない場合、少なくとも１つの他のルートを生成するステップと、提案ルートおよび少なくとも１つの他のルートの間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを提案ルートおよび少なくとも１つの他のルートに割り当てるステップとを、含むことができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。
【００２９】
コンピュータ読み取り可能プログラムのこの方法は、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、さらに含むことができる。他の帯域幅は、選択されたルートの残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。
【００３０】
また、コンピュータ読み取り可能プログラムのこの方法は、複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、含むこともできる。
【００３１】
さらに、コンピュータ読み取り可能プログラムのこの方法は、ネットワークの複数のリンクのそれぞれについて、そのリンクをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとによって、提案ルートの生成に先立って使用可能帯域幅およびリンクを提供するステップを含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、前述の方法の予約帯域幅を決定するステップ、最大帯域幅を決定するステップ、および使用可能帯域幅を決定するステップは、複数のリンクのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するために、複数のクラスそれぞれについて実行することができる。
【００３２】
本発明の他の方法によれば、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、ネットワーク内の複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替パスが提供される。この方法は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップと、を含む。
【００３３】
本発明のこの方法によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。
【００３４】
前述の方法は、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、新しい代替パスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、さらに含むことが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上の代替パスに割り振られる合計帯域幅である。
【００３５】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクをトラバースすることが可能であり、この方法は、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、さらに含むことができる。
【００３６】
本発明の他の装置は、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する。この装置は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップとを、実行するように動作可能な置換ユニットを含む。
【００３７】
前述の装置によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。さらにこの置換ユニットは、複数の代替パスのうちの少なくとも１つを生成するように動作可能であって、代替パスの１次パスは提案ルートおよび少なくとも１つの他のルートのうちの１つであり、代替パスによって搬送される各クラスに割り振られる帯域幅は、提案ルートおよび少なくとも１つの他のルートのうちの１つについて各クラスに割り振られる帯域幅である。この置換ユニットは、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、複数の代替パスのうちの新しいパスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、実行するようにも動作可能であるものとすることが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上のパスに割り振られる合計帯域幅である。
【００３８】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことが可能であり、この置換ユニットは、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、実行するようにさらに動作可能であるものとすることができる。
【００３９】
本発明の他の記録媒体には、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する方法を実行するためのコンピュータ読み取り可能プログラムが記録される。この方法は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップとを含む。
【００４０】
前述のコンピュータ読み取り可能プログラムの方法によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。
【００４１】
このコンピュータ読み取り可能プログラムの方法は、複数の代替パスのうちの少なくとも１つを生成するステップをさらに含むことが可能であり、代替パスの１次パスは提案ルートおよび少なくとも１つの他のルートのうちの１つであり、代替パスによって搬送される各クラスに割り振られる帯域幅は、提案ルートおよび少なくとも１つの他のルートのうちの１つについて各クラスに割り振られる帯域幅である。前述の方法は、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、複数の代替パスのうちの新しいパスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、さらに含むことが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上のパスに割り振られる合計帯域幅である。
【００４２】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことが可能であり、このコンピュータ読み取り可能プログラムの方法は、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、さらに含むことが可能である。
【００４３】
本発明のさらに他の方法によれば、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワーク内の複数の既存のパスの代わりに複数の代替パスがネットワーク内に提供される。複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送し、ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することができる。複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとして指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、現在のクラスの提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされた現在のクラスのリンクの使用可能な帯域幅を割り振られた部分だけ削減し、所望の帯域幅リストから少なくとも他のクラスについて、提案ルートの帯域幅が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、少なくとも他のクラスの提案ルートの帯域幅の一部を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最大数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれのリンクの現在のクラスの使用可能帯域幅を割り振られた部分だけ削減し、複数の提案ルートそれぞれについて反復的に、所望の帯域幅リストから少なくとも他のクラスについて、現在の提案ルートの帯域幅が所望の帯域幅リストから少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００４４】
本発明の他の装置は、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワークの複数の既存のパスの代わりに複数の代替パスをネットワーク内に提供し、この複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送する。ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この装置は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、所望の帯域幅リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅リストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、使用可能な帯域幅およびリンクのリストから提案ルートのリンクを除去するステップと、所望の帯域幅リストから、提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、使用可能な帯域幅およびリンクのリストから複数の他のルートそれぞれのリンクを除去し、複数の他のルートのそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストからの少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップとを、実行できるように動作可能な置換ユニットを含む。
【００４５】
本発明の他の記録媒体には、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワーク内の複数の既存のパスの代わりに複数の代替パスをネットワーク内に提供する方法を実行するためのコンピュータ読み取り可能プログラムが記録され、この複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送する。ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、所望の帯域幅リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅リストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅だけ削減し、所望の帯域幅リストから、提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートのそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストからの少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップとを、含む。
【００４６】
本発明の前述の方法、装置、および記録媒体によれば、複数の既存のパスはそれぞれ、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。複数のクラスは複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスとすることができる。
【００４７】
使用可能な帯域幅およびリンクのリストは以下のように提供可能であって、ネットワークの複数のリンクが決定可能であり、複数のリンクそれぞれをトラバースする複数の既存のパスのそれぞれが決定可能であり、複数のリンクそれぞれについて複数のクラスそれぞれに関連付けられた予約帯域幅が決定可能であり、この決定はそのリンクをトラバースする複数の既存のパスそれぞれに基づくものとすることが可能であり、複数のクラスそれぞれに関連付けられた最大帯域幅は複数のリンクそれぞれについて決定可能であり、複数のクラスそれぞれに関連付けられた使用可能帯域幅は、複数のリンクそれぞれについて、そのリンク上のそのクラスに関連付けられた最大帯域幅および予約帯域幅に基づいて決定可能である。
【００４８】
提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、所望の帯域幅のリストのうち現在の第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、提案ルートの帯域幅の残りの部分が現在の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックが提案ルートに割り当てられ、現在のルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振られ、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去され、現在のルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリスト上で次に高位の要素に対応するクラスが現在のクラスとなるように選択可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の帯域幅となるように選択可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容が繰り返される。
【００４９】
複数のルートそれぞれに関連付けられた帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、複数の他のルートのうちの１つが選択可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の帯域幅より大きいかまたは等しいかどうかが決定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックが選択されたルートに割り当て可能であり、選択されたルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の帯域幅よりも小さい場合、所望の帯域幅のリストのうち次に高位の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の帯域幅となるように指定可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容を繰り返すことが可能であり、所望の帯域幅のリストが空でない場合、複数の他のルートのうちの他のルートが選択可能であり、複数の他のルートそれぞれが考慮されるまで前述の内容が繰り返される。
【００５０】
複数の代替パスのうちの１つが生成可能であり、提案ルートをその１次パスとして、また提案ルートの各クラスに関連付けられた帯域幅をその帯域幅として、有することが可能であるか、または複数の他のルートのそれぞれをその１次パスとして、また複数の他のルートのそれぞれの各クラスに関連付けられた帯域幅をその帯域幅として、有することが可能である。複数の代替パスのうちの２つまたはそれ以上のルートによってトラバースされたリンクのすべてが同一である場合、その２つまたはそれ以上の代替パスを組み合わせて、そのルートをその１次パスとして、また、２つまたはそれ以上の代替パスのそれぞれのクラスについて組み合わせた帯域幅をそのクラスについてのその帯域幅として有する、複数の代替パスのうちの新しいパスを生成することができる。
【００５１】
本発明の他の方法によれば、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークの複数の障害ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰが提供される。複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することができる。複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能な帯域幅を割り振られた帯域幅部分だけ削減し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数のルートが生成されるように現在の所望の帯域幅を複数の他のルート間で分割し、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り当て、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００５２】
本発明の他の装置は、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワーク内の複数の障害置換ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰを提供し、複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この装置は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートのリンクを使用可能な帯域幅およびリンクのリストから除去し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれのリンクを使用可能な帯域幅およびリンクのリストから除去し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を実行するように動作可能な置換ユニットを含む。
【００５３】
本発明の他の記録媒体には、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークの複数の障害ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録され、複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能な帯域幅を割り振られた帯域幅部分だけ削減し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００５４】
本発明の前述の方法、装置、および記録媒体によれば、それぞれのリンク上のｄｉｆｆｓｅｒｖクラスごとの使用可能な帯域幅のリストは、以下のように決定可能であって、
ＭＰＬＳネットワークの複数のリンクが決定可能であり、複数のリンクそれぞれをトラバースする複数のＬＳＰのそれぞれが決定可能であり、複数のリンクそれぞれについて、そのリンクをトラバースする複数のＬＳＰそれぞれに基づき、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた予約帯域幅が決定可能であり、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた最大帯域幅は複数のリンクそれぞれについて決定可能であり、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた使用可能帯域幅は、複数のリンクそれぞれについて、そのリンク上のそのｄｉｆｆｓｅｒｖクラスに関連付けられた最大帯域幅および予約帯域幅に基づいて決定可能である。
【００５５】
提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、所望の帯域幅のリストのうち現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックが提案ルートに割り当て可能であり、現在のルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、現在のルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリスト上で次に高位の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように選択可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の所望の帯域幅となるように選択可能であり、所望の帯域幅のリストのそれぞれが考慮されるまで、前述の内容が繰り返される。
【００５６】
複数のルートそれぞれに関連付けられた帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、複数の他のルートのうちの１つが選択可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように選択可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックが選択されたルートに割り当て可能であり、選択されたルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリストのうち次に高位の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容を繰り返すことが可能であり、所望の帯域幅のリストが空でない場合、複数の他のルートのうちの他のルートが選択可能であり、複数の他のルートそれぞれが考慮されるまで前述の内容が繰り返される。
【００５７】
複数の置換ＬＳＰのうちの１つが生成可能であり、提案ルートをその１次パスとして、また提案ルートの各ｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅をその帯域幅として、有することが可能であるか、または複数の他のルートのそれぞれをその１次パスとして、また提案ルートの各ｄｉｆｆｓｅｒｖに関連付けられた帯域幅をその帯域幅として、有することが可能である。複数の置換ＬＳＰのうちの２つまたはそれ以上のルートによってトラバースされたリンクのすべてが同一であるかどうかが判別可能であり、同一である場合、その２つまたはそれ以上の置換ＬＳＰを組み合わせて、そのルートをその１次パスとして、また、２つまたはそれ以上の置換ＬＳＰのそれぞれのｄｉｆｆｓｅｒｖクラスについて組み合わせた帯域幅をそのクラスについてのその帯域幅として有する、複数の置換ＬＳＰのうちの新しい置換ＬＳＰを生成することができる。複数の障害ＬＳＰのうちの少なくとも１つが再度動作可能な場合、複数の置換ＬＳＰのうちの１つまたは複数がもはや必要でないかどうかが判別され、必要でない場合、複数の置換ＬＳＰのうちの１つまたは複数が除去され、１つまたは複数の置換ＬＳＰによってトラバースされたリンク、および含まれるリンクのそれぞれについて各ｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅を含むように、使用可能な帯域幅およびリンクのリストが更新される。
【００５８】
本発明の前述の態様、機能、および利点は、好ましい諸実施形態についての以下の説明および添付の図面を参照しながら考察した場合、さらによく理解されるであろう。
【発明を実施するための最良の形態】
【００５９】
図１は、本発明の態様に従った、システムのオペレーションを実行するために使用されるトラフィックエンジニアリング要素１００の一例を示す。要素１００は、差異化サービス（ｄｉｆｆｓｅｒｖ）機能を有するＭＰＬＳネットワークなどの、ネットワーク１０２と情報をやり取りする。トラフィックエンジニアリング要素は、たとえばネットワークオペレーションセンタに位置するネットワーク管理システム内に配置され、帯域幅マネージャ１０４、復元ユニット１０６、および構成データベース１０８を含むことができる。帯域幅マネージャ１０４はネットワーク１０２を通過するトラフィックを制御し、特定のｄｉｆｆｓｅｒｖクラスに帯域幅を割り振る。復元ユニット１０６は、１つまたは複数のＬＳＰに障害が発生した場合、既存のＬＳＰに関する置換ラベルスイッチパスの代替えを制御する。構成データベース１０８は、ネットワーク１０２のトポロジ、ＬＳＰデータ、およびポリシーを格納する。帯域幅マネージャ１０４および復元ユニット１０６は、好ましくはハードウェアプラットフォーム上で動作するソフトウェアモジュールを備える。モジュール自体は、オブジェクト指向プログラム内のオブジェクトを備えることができる。代替の方法として、モジュールはＤＯＳ、Ｗｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘ、またはＭＡＣオペレーティングシステムにおけるプログラムとして実施可能である。その後プログラムはメモリ内に格納され、プロセッサによって命令として実行される。構成データベースは、好ましくは、帯域幅マネージャ１０４および復元ユニット１０６と同じ場所に配置することが可能なメモリである。別の方法として、構成データベースは復元ユニットからリモートに配置することが可能である。
【００６０】
一般に、要素１００は、たとえばＭＰＬＳネットワーク１０２などの、パケット交換網などを管理するために使用されるオペレーションサポートシステム（ＯＳＳ）を備えることができる。この要素は、スタンドアロン型システムを備えるか、あるいは、既存のまたは現在使用可能なＯＳＳに組み込むことができる。このシステムは、たとえばＷｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘなどの汎用マシンを使用して実施することができる。要素１００とネットワーク１０２との間の通信は、たとえばｔｅｌｎｅｔ、ＳＮＭＰなどを使用して実現することができる。要素１００間の通信は、たとえばＣＯＲＢＡ、ＲＭＩなどを使用して実現することができる。一例として、システムは、Ｊａｖａ（登録商標）を使用して、ネットワーク１０２と通信するためにＴｅｌｎｅｔを使用して、および要素１００間の通信を可能にするためにＣＯＲＢＡを使用して、実施される。
【００６１】
ネットワークトポロジには、ネットワークのルータおよび／またはノードならびにルータのペアを接続するリンクのリストが含まれる。さらに各リンクについて、リンクＩＤ、リンクによって接続された２つのインターフェースのインターネットプロトコル（ＩＰ）アドレス、Ｍｂｐｓ単位でのリンクの最大容量、およびリンクの障害または動作可能状況が格納される。各ルータについて、ルータＩＤおよびルータのインターフェースのＩＰアドレスのリストが格納される。ＬＳＰデータには、ネットワーク用にセットアップされたＬＳＰのリストが含まれ、各ＬＳＰについて、ＬＳＰ ＩＤ、ＡおよびＺエンドのＩＰアドレス、ＬＳＰによってサポートされる各ｄｉｆｆｓｅｒｖクラスについての合計の予約帯域幅、ＬＳＰのパス、すなわちＬＳＰによってトラバースされるリンクの順序付けされたシーケンス、ならびにセットアップおよび保持優先順位が含まれる。ｄｉｆｆｓｅｒｖポリシーは、サポートされるｄｉｆｆｓｅｒｖクラス間でネットワークリソースを区分する働きをし、各ｄｉｆｆｓｅｒｖクラスについてのｄｉｆｆｓｅｒｖクラス名およびネットワーク使用量制限を含む。
【００６２】
図２は、ネットワーク内で１つまたは複数の障害が発生した場合の、本発明の一態様に従った、ＭＰＬＳネットワーク２００の一部およびネットワークトラフィックの復元の例を示す。図示されたネットワークの部分には、ルータＲ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、およびＲ６が含まれ、それぞれ２０Ｍｂｐｓ帯域幅容量を有するリンクＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６、Ｌ７、およびＬ８、ならびに６Ｍｂｐｓ帯域幅容量を有するリンクＬ４が含まれる。初期には、ネットワークトラフィックは、リンクＬ１を介してルータＲ１とルータＲ２との間をルーティングされた２つのＬＳＰ、ＬＳＰ１およびＬＳＰ２に沿って搬送される。パスＬＳＰ１は８Ｍｂｐｓのトラフィックを搬送可能である、すなわち、８Ｍｂｐｓの帯域幅を有するが、実際には３ＭｂｐｓのｄｉｆｆｓｅｒｖクラスのＥＦトラフィックしか搬送しないため、５Ｍｂｐｓの帯域幅が未使用である。パスＬＳＰ２も８Ｍｂｐｓの帯域幅を有するが、１ＭｂｐｓのＡＦ１トラフィックしか搬送しないため、７Ｍｂｐｓの帯域幅が使用される。
【００６３】
リンクＬ１に障害が発生すると、現在のＭＰＬＳネットワーク復元スキームは、同じかまたはそれよりも大きい８Ｍｂｐｓの帯域幅を有するリンクを使用してＬＳＰ１を新しいＬＳＰに置き換えようと試み、さらにＬＳＰ２も同様に、少なくとも８Ｍｂｐｓの帯域幅を有するリンクを使用して新しいＬＳＰに置き換えようと試みる。したがって、各置換ＬＳＰは、置き換えるＬＳＰと同じ未使用の帯域幅を有する。
【００６４】
通常、リンクＬ１に障害が発生した場合、トラフィックはそれぞれが２０Ｍｂｐｓの容量を有するリンクＬ２、Ｌ３、およびＬ７に沿ってルーティングされるため、２つの置換ＬＳＰの組み合わせ帯域幅である１６Ｍｂｐｓを搬送することができる。しかしながら、リンクＬ２およびＬ３にも障害が発生すると、リンクＬ４には６Ｍｂｐｓの容量しかなく、２つの置換ＬＳＰのうちの１つのトラフィックでさえも搬送することができない。帯域幅が不十分であることから、トラフィックはＬ４を介して再ルーティングできないため、復元の試みは失敗する。
【００６５】
これに対して、本発明では、できる限り少ない置換ＬＳＰを生成することによって障害トラフィックを復元する。ここでは、新しいＬＳＰであるＬＳＰ３が生成され、そのパスはリンクＬ４、Ｌ５、Ｌ６、およびＬ７をカバーしている。ＬＳＰ３の帯域幅はＬＳＰ１およびＬＳＰ２によって実際に使用される合計帯域幅のみであるため、ＬＳＰ３には４Ｍｂｐｓの帯域幅しかない。したがって、ＬＳＰ３はリンクＬ４を含むことができる。
【００６６】
図３は、本発明に従って１つまたは複数の障害ＬＳＰの復元を実行するために、図１に示された帯域幅マネージャ１０４、復元ユニット１０６、および構成データベース１０８の間で実行されるメッセージングの一例を示す。第１に、帯域幅マネージャはＭＰＬＳネットワーク１０２の１つまたは複数のＬＳＰの障害を検出する。帯域幅マネージャは、復元スキーム、すなわち障害ＬＳＰの代わりに置換ＬＳＰを生成するプロセスを開始する旨の要求を、復元ユニットに送信する。その後復元ユニットは、ネットワークの構成データを取得するための要求を構成データベースに伝送し、構成データベースはこうしたデータを復元ユニットに送達する。次に、本発明の復元スキームが実行され、新しいＬＳＰが生成される。その後復元ユニットは、構成データを更新するために、新しいＬＳＰに関する情報を構成データベースに送信する。その後、復元ユニットは、ネットワークが首尾良く復元されたかどうかを示す応答を帯域幅マネージャに送信する。
【００６７】
本発明に従ったネットワーク復元の概要が、図４に示される。第１に、復元ユニットが帯域幅マネージャから復元要求を受け取り、復元スキームを開始すると、ステップ４０２に示されるように復元が開始される。復元要求は、各要素が（入口、出口、ｄｉｆｆｓｅｒｖクラス、帯域幅）の形である障害トラフィックのリスト、障害リンクのリスト、および、ＭＰＬＳネットワークが障害に応答して再ルーティングしたそれらの新しいパスを備える再ルーティングＬＳＰと呼ばれるＬＳＰのリストという、属性を含むことが可能である。その後、構成データベースからのネットワーク構成データ、障害リンクのリスト、および再ルーティングされたＬＳＰのリストを獲得した後、ステップ４０４が示すように、復元ユニットは、ＭＰＬＳネットワークの現在の状態を決定し、すなわち、ネットワーク内の各リンク上の各ｄｉｆｆｓｅｒｖクラスに使用可能な帯域幅が決定される。次に、ステップ４０６が示すように、それらの間をトラバースしている１つまたは複数の障害ＬＳＰを有する入口地点および出口地点のペアのリストが、復元要求の障害トラフィック属性のリストを使用して決定される。
【００６８】
次に、ステップ４０８および４１０が示すように、リスト内のすべての入口／出口ペアが考慮されるまで、入口地点および出口地点の各ペアの間で１つまたは複数の置換ＬＳＰが動的に生成される。すべての入口／出口ポートが考慮されると、ステップ４１２が示すように復元は終了する。
【００６９】
図５Ａ〜５Ｆは、入口地点および出口地点の所与のペア間での置換ＬＳＰの動的生成をより詳細に示す流れ図である。動的生成のために実行される計算、ならびに使用される入力、出力、および変数の一例が、表１および２に示される。第１に、ステップ５０２に示されるように、各ｄｉｆｆｓｅｒｖクラスについて各リンク上で使用可能な帯域幅のリストが示される。
【００７０】
図６は、ステップ４０４で言及した使用可能な帯域幅のリストの決定をより詳細に示す流れ図である。第１に、ステップ６０２が示すように、ネットワーク内のすべての障害のないリンクのリストが生成される。次に、ステップ６０４が示すように、各リンクをトラバースするＬＳＰのリストが決定される。次に、ステップ６０６が示すように、それぞれのこうしたＬＳＰによってトラバースされたリンクによって占有される帯域幅を決定するために、ＬＳＰのリストを使用して、障害のない各リンクについて、各ｄｉｆｆｓｅｒｖクラスに関連付けられた予約帯域幅が決定される。次に、ステップ６０８が示すように、各リンクの最大容量およびネットワーク使用量制限を使用して、各リンクの各ｄｉｆｆｓｅｒｖクラスに使用可能な最大帯域幅容量が決定される。したがって、ステップ６１０が示すように、各リンクの各ｄｉｆｆｓｅｒｖクラスに関連付けられた予約帯域幅が、そのリンクのそのクラスに関連付けられた最大使用可能帯域幅から削減されて、各リンクの各ｄｉｆｆｓｅｒｖクラスに関連付けられた使用可能帯域幅が決定される。
【００７１】
その後、再度図５Ａを参照すると、ステップ５０４に示されるように、それぞれの障害ＬＳＰによって各ｄｉｆｆｓｅｒｖクラスについて搬送された帯域幅に基づいて、各ｄｉｆｆｓｅｒｖについての所望帯域幅の合計のリストが決定される。その後、このリストは好ましくは、リスト内の第１の要素が最大の合計帯域幅を必要とするｄｉｆｆｓｅｒｖクラスならびにその必要帯域幅を含み、次の要素が次に合計の大きな必要帯域幅を有するｄｉｆｆｓｅｒｖクラスならびにその帯域幅を含む、などのように、最後の要素が最小帯域幅を必要とするｄｉｆｆｓｅｒｖクラスならびにその帯域幅を含むまで、帯域幅が減少していく順に配列される。有利なことに、所望帯域幅のリストは、第１の置換ＬＳＰが最大帯域幅を必要とするｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために生成されるように、帯域幅が減少していく順に配列される。通常、このｄｉｆｆｓｅｒｖクラスを搬送するために生成されるルートは、他のｄｉｆｆｓｅｒｖクラスの帯域幅を収容するためにも好適である。したがって、この様式で置換ＬＳＰを生成すると、結果としてより少ないＬＳＰが生成されることになる。
【００７２】
次に、ステップ５０６が示すように、所望帯域幅のリストが空でないかどうかが判別される。空でない場合、ステップ５０８が示すように、現在のｄｉｆｆｓｅｒｖクラスが、所望帯域幅のリスト内の第１の要素のｄｉｆｆｓｅｒｖクラスとして定義され、現在の所望帯域幅が、このリストの第１の要素内に含まれる帯域幅として定義される。次に、ステップ５１０が示すように、所望帯域幅のリストの第１の要素が除去され、リスト内の第２の要素が第１の要素となり、リスト内の第３の要素が第２の要素となる、などのように、リスト内の残りの要素が１ポジション進められる。その後、ステップ５１２が示すように、リンクおよびそれらの使用可能帯域幅のリストから、提案ルートが生成される。提案ルートは、現在のｄｉｆｆｓｅｒｖクラス、すなわち、今削除された所望帯域幅リストの第１の要素のｄｉｆｆｓｅｒｖクラスに使用可能な、最大帯域幅を有する。提案ルートは、たとえば「コスト」パラメータが使用可能帯域幅として定義される、知られているダイクストラのアルゴリズムの変形によって生成することができる。こうした計算の例および関係する入力、出力、変数、初期設定、および関数が、表３および４に示される。
【００７３】
次に図５Ｂを参照すると、提案ルートの帯域幅が現在の所望帯域幅よりも大きいかまたは等しい場合、すなわち、提案ルートの帯域幅が、所望帯域幅のリストから除去された第１の要素のｄｉｆｆｓｅｒｖクラスによって必要とされる帯域幅に少なくとも等しい場合、その提案ルートは現在のクラスのトラフィックを搬送することができる。その後、ステップ５２０が示すように、現在のクラスのトラフィックが提案ルートに割り当てられる。ステップ５２２が示すように、提案ルートが使用可能な帯域幅の一部が、現在のクラスが必要とする帯域幅、すなわち現在の所望帯域幅に割り振られる。ステップ５２４が示すように、提案ルートによってトラバースされたリンクの使用可能帯域幅が、割り振られた帯域幅部分だけ削減される。
【００７４】
図５Ｃは、提案ルートの帯域幅の残りの部分が、所望帯域幅のリストからの１つまたは複数の他のクラスのトラフィックを搬送できるかどうかについての、その後の判別を示す。ステップ５２６が示すように、ここで現在のクラスは、所望帯域幅のリストの新しい第１の要素のｄｉｆｆｓｅｒｖクラスの値を有するように定義され、ここで現在の所望帯域幅は、第１の要素に関連付けられた帯域幅となるように定義される。次に、ステップ５２８が示すように、ここで定義された新しい現在のクラスについて、提案ルート上の使用可能帯域幅が現在の所望帯域幅に少なくとも等しいかどうかが決定される。等しい場合、提案ルートには新しい現在のクラスのトラフィックも割り当てられる。具体的には、ステップ５３２が示すように、提案ルートには所望帯域幅のリストの新しい第１の要素のｄｉｆｆｓｅｒｖクラスのトラフィックが割り当てられ、ステップ５３４が示すように、ここで、提案ルートの未割り振り帯域幅の一部がそのｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振られる。提案ルートのリンクに使用可能な帯域幅が、帯域幅の割り振られた部分だけ削減される。次に、所望帯域幅のリストの現在の第１の要素が削除され、リスト内の残りの要素が１ポジション進められた結果、ここでリスト内の元の第３の要素がリスト内の第１の要素となる。
【００７５】
代替の方法として、ステップ５２８で、提案ルートの残りの未割り振り帯域幅が現在の所望帯域幅よりも小さいと判別された場合、次に、ステップ５３０が示すように、現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮されたかどうかが判別される。現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮された場合、プロセスは、図５Ａに示されるステップ５０６に戻る。代替の方法として、現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮されたのではない場合、ここで、ステップ５３１が示すように、現在のクラスおよび現在の所望帯域幅が、所望帯域幅のリストの現在の第２の要素のクラスおよび帯域幅の値を有するように定義され、ステップ５２８で実行される判別が繰り返される。ステップ５２８で、提案ルートの残りの未割り振り帯域幅が、現在の所望帯域幅に少なくとも等しいと判別された場合、前述のように、ステップ５３２、５３４、および５３６が繰り返される。代替の方法として、ステップ５２８で、提案ルートの残りの未割り振り帯域幅が現在の所望帯域幅よりも小さいと判別された場合、ステップ５３０および５３１が繰り返され、結果として、ここで、現在のクラスおよび現在の所望帯域幅がリスト内の現在の第３の要素のクラスおよび帯域幅の値を有するように定義され、ステップ５２８で判別が再度実行される。
【００７６】
図５Ｃの上記ステップは、ステップ５３８が示すように、所望帯域幅のリストのすべての要素が考慮されるまで、すなわち、所望帯域幅のリストの各要素のｄｉｆｆｓｅｒｖクラスおよび関連付けられた帯域幅が、（ｉ）提案ルートに割り当てられてリストから削除されるまで、あるいは（ｉｉ）提案ルートに割り当てられておらずリストに残っているが考慮されるまで、繰り返される。
【００７７】
図５Ｄは、図５Ａのステップ５１４で実施された判別によって、提案ルートの帯域幅が、現在の所望帯域幅に関連付けられた帯域幅、すなわち、使用可能帯域幅のリストの以前の第１の要素に関連付けられた帯域幅より少ないことが判明した場合に実施される操作を示す。第１に、ステップ５４０が示すように、提案ルートが収容できる最大の現在の帯域幅が提案ルートに割り振られる。次に、ステップ５４１が示すように、提案ルートのリンク上の使用可能帯域幅が、帯域幅の割り振られた部分だけ削減される。次に、ステップ５４２が示すように、現在必要な帯域幅が満たされているかどうかが判別される。現在必要な帯域幅が満たされている場合、プロセスは図５Ｅのステップ５４６に進む。現在必要な帯域幅が満たされていない場合、ステップ５４３が示すように、新しい提案ルートの生成が試行される。新しい提案ルートを生成する試行が成功した場合、ステップ５４０、５４１、および５４２が繰り返され、新しい提案ルートを生成する試行が、使用可能帯域幅の欠如などによって失敗した場合、現在必要な帯域幅はこれまでに割り振られた帯域幅で満たされているとみなされ、その後、プロセスは図５Ｅに示されるステップ５４６に進む。
【００７８】
図５Ｅおよび５Ｆは、所望帯域幅の残りの要素のいずれかが、前述の様式で生成された新しいルートを介して搬送可能であるかどうかの、その後の判別を示す。ステップ５４６が示すように、新しいルートのうちの１つが選択され、その後、ステップ５４８が示すように、現在のクラスおよび現在必要な帯域幅が、所望帯域幅のリストの現在の第１の要素に含まれるクラスおよびその関連付けられた帯域幅として定義される。ステップ５５０が示すように、現在のクラスについて、そのルートの残りの使用可能帯域幅が現在の所望帯域幅と比較される。そのルートの使用可能帯域幅が現在の所望帯域幅より大きいかまたは等しい場合、ステップ５６０が示すように、現在のクラスのトラフィックがそのルートに割り当てられる。ステップ５６２が示すように、現在の所望帯域幅がそのルートに割り振られ、そのルートのリンク上の使用可能帯域幅が帯域幅の割り振られた部分だけ削減される。その後、ステップ５６４が示すように、所望帯域幅のリストの第１の要素が所望帯域幅のリストから除去され、リスト内の残りの要素が１ポジション進められる。その後、ステップ５６６が示すように、何らかの要素が所望帯域幅のリスト内に残っている場合、ステップ５６８が示すように、現在のクラスおよび現在の帯域幅の値が上記の様式で再度定義され、新しい現在のクラスおよび現在の帯域幅についてステップ５５０が繰り返される。
【００７９】
代替の方法として、ルートの残りの使用可能帯域幅が現在の所望帯域幅より少ない場合、ステップ５５２が示すように、所望帯域幅のリスト内の次の要素に含まれる値が、現在のクラスおよび現在の所望帯域幅として再定義される。その後、ステップ５５０に示される判別が繰り返され、それに基づいて、所望帯域幅のリストのすべての要素が考慮されるまで、前述のステップ５６０、５６２、および５６４が繰り返されるか、または前述のステップ５５２が繰り返される。その後、新しいルートのうちの１つまたは複数が考慮されていない場合、ステップ５７０および５７２が示すように、これらルートのうちの他のルートが選択され、新しいルートがすべて考慮されるまで図５Ｅおよび図５Ｆに示されるステップが繰り返される。
【００８０】
有利なことには、図４、図５Ａ〜５Ｆ、および図６に示される操作により、入口地点および出口地点の各ペア間の障害トラフィックに対処するために必要な最低数の新しいＬＳＰが生成される。さらに復元は、こうした障害が発生するたびに実行されるように、動的に実行される。
【００８１】
さらに、図４、図５Ａ〜５Ｆ、および図６を参照した前述の操作は、最低数の新しいルートの動的な生成を必要とする他の応用例でも使用可能である。
【００８２】
本発明の他の利点は、障害リンクが復元された後、ネットワークがその以前の最適化された状態に戻るように、ネットワークはその元の状態、すなわち、リンクの障害以前のネットワークの状態に復帰することである。図７は、元のネットワークに復元するために必要な、帯域幅マネージャ、復元ユニット、および構成データベースの間でのメッセージングの例を示す。第１に、帯域幅マネージャは、リンクが復元されたことを検出し、復元スキームに対して復帰要求を発行する。次に、復元ユニットは、復元ＬＳＰによってトラバースされたリンクおよびこれらのリンク上で搬送された各ｄｉｆｆｓｅｒｖクラスの帯域幅を使用可能帯域幅のリストに復元することによって、各リンク上の各ｄｉｆｆｓｅｒｖクラスで使用可能な帯域幅のリストを更新する。次に復元ユニットは、ネットワークの状態、すなわち、構成データベースに格納された構成データを更新する。その後、復元ユニットは、ネットワークがその以前の状態に復元された旨の指示を、帯域幅マネージャに送信する。
【００８３】
以上、本明細書では、特定の諸実施形態を参照しながら本発明について説明してきたが、これらの諸実施形態が本発明の原理および応用例の単なる例示であることを理解されよう。したがって、この例示的な諸実施形態に対して多数の修正形態が実行可能であること、および添付の特許請求の範囲に定義された本発明の趣旨および範囲を逸脱することなく、他の配置構成が考案可能であることを理解されよう。
【図面の簡単な説明】
【００８４】
【図１】本発明を実施するネットワーク管理要素の一例を示すブロック図である。
【図２】本発明に従った、障害リンクを備えたパスを含むネットワークの一部を示し、置換パスを形成するために使用されるリンクを示す図である。
【図３】ネットワークの一部に障害が発生した場合、サービスを復元するための、本発明に従って生成されるコマンドおよび応答のシーケンスを示す図である。
【図４】ネットワークの一部の障害に応答して、本発明に従った置換パスを生成するために実行されるオペレーションの流れを示す図である。
【図５Ａ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｂ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｃ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｄ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｅ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｆ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図６】図５Ａに示されたネットワーク内の使用可能な帯域幅およびリンクのリストを形成するために実行されるオペレーションを示す流れ図である。
【図７】障害リンクがサービスに返された後、元のネットワークパスを復元するために本発明に従って実行されるコマンドおよび応答のシーケンスを示す図である。
【技術分野】
【０００１】
本発明は、情報パケットの転送に使用されるネットワークを対象とし、より具体的に言えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）を組み込んだネットワークを対象とする。
【背景技術】
【０００２】
本出願は、その開示が参照により本明細書に組み込まれた、２００４年５月１９日付け出願の米国特許仮出願第６０／５７２５１２号の利益を主張する。
【０００３】
マルチプロトコルラベルスイッチング（ＭＰＬＳ）を使用するネットワークは、パケットがネットワークを介して転送される前に決定されるエンドツーエンド接続パスを介した、ネットワークを通じたパケットの転送を可能にするものである。パケットがＭＰＬＳネットワークに入ると、そのパケットには、ラベルエッジルータ（ＬＥＲ）とも呼ばれる入口（ｉｎｇｒｅｓｓ）ルータによって「ラベル」が割り当てられ、さらにこのルータがパケットにラベルを添付して、そのパケットをラベルスイッチルータ（ＬＳＲ）と呼ばれる一連のルータのうちの第１のルータに転送し、これらのルータが接続パスに沿ってパケットを転送する。ラベルには、第１のルータがパケットを転送する次のルータを決定するために使用する情報が含まれる。次に第１のルータはパケットを受信し、ラベルを除去した後、次のルータがパケットをスイッチする後続のルータを決定するために使用することになる新しいラベルを添付する。このプロセスは、接続パスに沿って配置された各ルータに対して繰り返される。すなわち、パスに沿った各ルータは、直前のルータによって添付されたラベルの付いたパケットを受け取り、ラベルに含まれる情報を使用して次にパケットを受け取る次のルータを決定し、現在のラベルをはがし、後続のルータが使用することになる新しいラベルを貼付した後、パケットをそのルータに転送する。このプロセスは、パケットがパスに沿って、出口ルータまたはＬＥＲとも呼ばれる最後のルータに送達された時点で終了する。
【０００４】
ラベルは、各ルータが転送トラフィックとも呼ばれる接続パスに沿ってパケットを転送する方法を決定するために使用されることから、この接続パスは、ラベルスイッチパス（ＬＳＰ）とも呼ばれる。各ラベルはＬＳＰの一部のみに関する情報を含み、各ルータまたはスイッチに必要なのは、特定ラベルに対応するルートに関する情報を格納すること、およびパケットに貼付されることになる次のラベルを格納することのみである。
【０００５】
ＬＳＰを含む特定のルートは、通常、ある一定レベルの性能を保証すること、ネットワークの輻輳を避けてルーティングすること、または特定用途の要件に準拠することなどの、様々な理由に基づいて決定される。通常、１次ＬＳＰがセットアップされると同時に、１つまたは複数のバックアップＬＳＰも決定される。バックアップパス用のルートは、１次ＬＳＰのセットアップ時に静的に決定するか、または１次ＬＳＰの障害時にのみ動的に決定することができる。バックアップパスは、通常、１次ＬＳＰと同じ帯域幅を有する。
【０００６】
ルータ障害、ルータインターフェース障害、またはリンク障害が発生した場合などの、ネットワーク内に障害が発生した場合、障害のあるＬＳＰを介して搬送されたパケットは、その対応するバックアップＬＳＰのうちの１つにスイッチされる。しかしながら、時には、ネットワーク障害によって１次ＬＳＰおよびそのバックアップＬＳＰに障害が発生する場合もある。現在のＭＰＬＳネットワーク回復スキームは、こうした状況に対処しない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、ネットワークの可用性およびサービスの可用性を増加させるために、こうした状況を処理するトラフィック復元スキームを有することが望ましい。こうしたスキームに、障害のあったＬＳＰによって搬送されたトラフィックと同量程度のトラフィックをできる限り搬送する、１つまたは複数の置換（ｒｅｐｌａｃｅｍｅｎｔ）ＬＳＰを作成させることも望ましい。さらに復元スキームが、ネットワークリソースの効率的な使用を考慮すること、およびトラフィックエンジニアリングポリシーを使用することによって、置換ＬＳＰを作成することも望ましい。
【課題を解決するための手段】
【０００８】
本発明の方法によれば、ネットワークの複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替（ｓｕｂｓｔｉｔｕｔｅ）パスが提供される。この方法は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを含む。
【０００９】
本発明の前述の方法によれば、複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。提案ルートは使用可能な最大帯域幅を有するルートとすることができる。
【００１０】
複数の既存のパスは、複数のサービスクラスのトラフィックを搬送可能であり、前述の決定ステップは、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップを含むことが可能であり、割り振りステップは、提案ルートの帯域幅の一部を、複数の必要な帯域幅内の選択された要素に割り振るステップと、提案ルートの帯域幅が選択された帯域幅要素よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。選択された帯域幅要素は、複数の必要な帯域幅内で最大の非割り振り帯域幅要素とすることができる。この方法は、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅内の、たとえばＸと呼ばれる他の帯域幅要素に割り振るステップと、提案ルートの帯域幅の残りの部分が帯域幅値Ｘよりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むこともできる。帯域幅要素Ｘは、複数の必要な帯域幅内の残りの非割り振り帯域幅要素のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００１１】
この方法は、複数の必要な帯域幅内のたとえばＸと呼ばれる各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分を帯域幅要素Ｘに連続的に割り振るステップと、提案ルートの帯域幅の残りの部分が帯域幅要素Ｘの帯域幅値よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、さらに含むことができる。
【００１２】
この方法は、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、生成されたすべてのルート間で必要な帯域幅を分割するステップとを、含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、決定するステップは、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップを含むことが可能であり、生成するステップは、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の１つよりも少ない場合、少なくとも１つの他のルートを生成するステップと、生成されたすべてのルート間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを生成されたルートに割り当てるステップとを、含むことができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。この方法は、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、さらに含むことができる。他の帯域幅は、選択されたルートの帯域幅の残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。この方法は、複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、含むこともできる。
【００１３】
この方法は、ネットワークの複数のリンクのそれぞれをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとによって、提案ルートの生成に先立って使用可能帯域幅およびリンクを提供するステップを含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、予約帯域幅、最大帯域幅、および使用可能帯域幅を決定するステップは、複数のリンクのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するために、複数のクラスそれぞれについて実行することができる。
【００１４】
本発明の装置は、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する。この装置は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを、実行するように動作可能な、置換ユニットを含む。
【００１５】
この装置によれば、複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）である。提案ルートは使用可能な最大帯域幅を有することができる。
【００１６】
複数の既存のパスは、複数のサービスクラスに対応するこうした複数の必要な帯域幅を決定するステップと、提案ルートの帯域幅の一部を、複数の使用される帯域幅のうちの所与の１つに割り振るステップと、提案ルートの帯域幅が所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能な、置換ユニットを使用して、複数のサービスクラスのトラフィックを搬送することができる。所与の帯域幅は、複数の必要な帯域幅のうちで最大の非割り振り帯域幅とすることができる。
【００１７】
さらにこの置換ユニットは、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、提案ルートの帯域幅の残りの部分が他の帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。他の帯域幅は、複数の必要な帯域幅の残りの非割り振り帯域幅のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００１８】
さらにこの置換ユニットは、複数の必要な帯域幅のうちの各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、提案ルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。
【００１９】
さらにこの置換ユニットは、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で必要な帯域幅を分割するステップとを、実行するように動作可能であるものとすることができる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、置換ユニットは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを実行するように動作可能であり、さらに、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、提案ルートおよび少なくとも１つの他のルートの間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを少なくとも１つの他のルート内の提案ルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。
【００２０】
さらにこの置換ユニットは、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のうちの一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、実行するように動作可能であるものとすることができる。他の帯域幅は、選択されたルートの帯域幅の残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。
【００２１】
この置換ユニットは、複数の必要な帯域幅の各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、実行するように動作可能であるものとすることもできる。
【００２２】
さらにこの置換ユニットは、提案ルートを生成するように動作可能になるのに先立って、使用可能帯域幅およびリンクを提供するステップを実行するように動作可能であることが可能であり、これには、ネットワークの複数のリンクのそれぞれについてそのリンクをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとを、実行するように動作可能であることも含まれる。複数のクラスのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するように動作可能とすることによって、複数のクラスそれぞれについて、予約帯域幅、最大帯域幅、および使用可能帯域幅を決定するように動作可能な置換ユニットを使用して、複数の既存のパスが複数のサービスクラスのトラフィックを搬送することができる。
【００２３】
本発明の記録媒体には、ネットワークの複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替パスを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録される。この方法は、複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、ネットワーク内の使用可能リンクから提案ルートを生成するステップと、提案ルートの帯域幅が必要な帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部を必要な帯域幅に割り振るステップとを含む。
【００２４】
前述の記録媒体によれば、複数のパスのそれぞれが、少なくとも１つの障害リンクをトラバースすることができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。提案ルートは使用可能な最大帯域幅を有することができる。
【００２５】
複数の既存のパスは、複数のサービスクラスのトラフィックを搬送可能であり、コンピュータ読み取り可能プログラムのこの方法の決定ステップは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含むことが可能であり、この方法の割り振りステップは、提案ルートの帯域幅の一部を、複数の必要な帯域幅内の所与の１つに割り振るステップと、提案ルートの帯域幅が所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。
【００２６】
所与の帯域幅は、複数の必要な帯域幅のうちで最大の非割り振り帯域幅とすることができる。さらに前述の方法は、提案ルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、提案ルートの帯域幅の残りの部分が他の帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、含むことができる。他の帯域幅は、複数の必要な帯域幅内の残りの非割り振り帯域幅のうちの最大の要素であることが可能であり、提案ルートの帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する。
【００２７】
コンピュータ読み取り可能プログラムのこの方法は、複数の必要な帯域幅のうちの各非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、提案ルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップとを、さらに含むことができる。
【００２８】
コンピュータ読み取り可能プログラムのこの方法は、提案ルートの帯域幅が必要な帯域幅よりも少ない場合、１つの他のルートを生成するステップと、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で必要な帯域幅を分割するステップとを、含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、この記録方法のうちの決定するステップは、複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含むことが可能であり、この記録方法のうちの少なくとも１つの他のルートを生成するステップは、提案ルートの帯域幅が複数の必要な帯域幅のうちの所与の１つよりも少ない場合、少なくとも１つの他のルートを生成するステップと、提案ルートおよび少なくとも１つの他のルートの間で所与の帯域幅を分割するステップと、対応するクラスのトラフィックを提案ルートおよび少なくとも１つの他のルートに割り当てるステップとを、含むことができる。所与の帯域幅は、複数の必要な帯域幅のうちの最大の帯域幅とすることができる。
【００２９】
コンピュータ読み取り可能プログラムのこの方法は、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、さらに含むことができる。他の帯域幅は、選択されたルートの残りの部分よりも小さいかまたは等しい帯域幅を有する、複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅とすることができる。
【００３０】
また、コンピュータ読み取り可能プログラムのこの方法は、複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、選択されたルートの帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、対応するクラスのトラフィックを選択されたルートに割り当てるステップとを、含むこともできる。
【００３１】
さらに、コンピュータ読み取り可能プログラムのこの方法は、ネットワークの複数のリンクのそれぞれについて、そのリンクをトラバースする複数の既存のパスのそれぞれを決定するステップと、そのリンクをトラバースする複数の既存のパスのそれぞれに基づいて、複数のリンクのそれぞれについて予約帯域幅を決定するステップと、複数のリンクのそれぞれについて最大帯域幅を決定するステップと、そのリンクの最大帯域幅および予約帯域幅に基づいて、複数のリンクのそれぞれについて使用可能帯域幅を決定するステップとによって、提案ルートの生成に先立って使用可能帯域幅およびリンクを提供するステップを含むこともできる。複数の既存のパスは、複数のサービスクラスのトラフィックを搬送することが可能であり、前述の方法の予約帯域幅を決定するステップ、最大帯域幅を決定するステップ、および使用可能帯域幅を決定するステップは、複数のリンクのそれぞれでそのクラスに関連付けられた予約帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた最大帯域幅と、複数のリンクのそれぞれでそのクラスに関連付けられた使用可能帯域幅とを決定するために、複数のクラスそれぞれについて実行することができる。
【００３２】
本発明の他の方法によれば、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、ネットワーク内の複数の既存のパスの代わりに、その複数の既存のパスによって搬送されたトラフィックを再割り振りするための少なくとも１つの代替パスが提供される。この方法は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップと、を含む。
【００３３】
本発明のこの方法によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。
【００３４】
前述の方法は、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、新しい代替パスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、さらに含むことが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上の代替パスに割り振られる合計帯域幅である。
【００３５】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクをトラバースすることが可能であり、この方法は、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、さらに含むことができる。
【００３６】
本発明の他の装置は、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する。この装置は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップとを、実行するように動作可能な置換ユニットを含む。
【００３７】
前述の装置によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。さらにこの置換ユニットは、複数の代替パスのうちの少なくとも１つを生成するように動作可能であって、代替パスの１次パスは提案ルートおよび少なくとも１つの他のルートのうちの１つであり、代替パスによって搬送される各クラスに割り振られる帯域幅は、提案ルートおよび少なくとも１つの他のルートのうちの１つについて各クラスに割り振られる帯域幅である。この置換ユニットは、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、複数の代替パスのうちの新しいパスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、実行するようにも動作可能であるものとすることが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上のパスに割り振られる合計帯域幅である。
【００３８】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことが可能であり、この置換ユニットは、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、実行するようにさらに動作可能であるものとすることができる。
【００３９】
本発明の他の記録媒体には、複数の既存のパスが複数のサービスクラスのトラフィックを搬送している状態で、複数の既存のパスによって搬送されたトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供する方法を実行するためのコンピュータ読み取り可能プログラムが記録される。この方法は、複数のサービスクラスに対応する複数の必要な帯域幅を決定するステップであって、この複数の必要な帯域幅のそれぞれが、対応するサービスクラスについて複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を含む、決定するステップと、最大の使用可能帯域幅を有するルートである提案ルートを、ネットワーク内の残りの使用可能リンクから生成するステップと、提案ルートの帯域幅が複数の必要な帯域幅のうちで最大の非割り振り帯域幅より大きいかまたは等しい場合、提案ルートの帯域幅の一部をその最大の非割り振り帯域幅に割り振り、対応するクラスのトラフィックを提案ルートに割り当て、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートの帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振り、提案ルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り当てるステップと、提案ルートの帯域幅が、複数の必要な帯域幅のうちで最大の非割り振り帯域幅よりも少ない場合、ネットワーク内の残りの使用可能リンクから少なくとも１つの他のルートを生成し、最低数の他のルートが生成されるように、提案ルートおよび少なくとも１つの他のルートの間で複数の必要な帯域幅のうちで最大の非割り振り帯域幅を分割し、さらに、複数の必要な帯域幅のうちの各残りの非割り振り帯域幅について、帯域幅が減少していく順に、提案ルートおよび少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振り、選択されたルートの帯域幅の残りの部分がその帯域幅より大きいかまたは等しい場合、対応するクラスのトラフィックを提案ルートに割り振るステップと、複数の必要な帯域幅のすべてが割り振られるかまたは考慮されるまで、前述の内容を繰り返すステップとを含む。
【００４０】
前述のコンピュータ読み取り可能プログラムの方法によれば、ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。
【００４１】
このコンピュータ読み取り可能プログラムの方法は、複数の代替パスのうちの少なくとも１つを生成するステップをさらに含むことが可能であり、代替パスの１次パスは提案ルートおよび少なくとも１つの他のルートのうちの１つであり、代替パスによって搬送される各クラスに割り振られる帯域幅は、提案ルートおよび少なくとも１つの他のルートのうちの１つについて各クラスに割り振られる帯域幅である。前述の方法は、２つまたはそれ以上の複数の代替パスのルートによってトラバースされたすべてのリンクが同一であるかどうかを判別するステップと、同一である場合、複数の代替パスのうちの新しいパスを生成するために２つまたはそれ以上の代替パスを組み合わせるステップとを、さらに含むことが可能であり、新しいパスによって搬送される各クラスに割り振られる帯域幅は、そのクラスの２つまたはそれ以上のパスに割り振られる合計帯域幅である。
【００４２】
複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことが可能であり、このコンピュータ読み取り可能プログラムの方法は、複数の障害パスのうちの少なくとも１つが再度動作可能になった場合、複数の置換パスのうちの１つまたは複数がもはや必要でないかどうかを判別するステップと、必要でない場合、１つまたは複数の置換パスによってトラバースされた各リンクから各クラスに割り振られた帯域幅が再度使用可能になるように、その複数の置換パスのうちの１つまたは複数を削除するステップとを、さらに含むことが可能である。
【００４３】
本発明のさらに他の方法によれば、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワーク内の複数の既存のパスの代わりに複数の代替パスがネットワーク内に提供される。複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送し、ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することができる。複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとして指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、現在のクラスの提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされた現在のクラスのリンクの使用可能な帯域幅を割り振られた部分だけ削減し、所望の帯域幅リストから少なくとも他のクラスについて、提案ルートの帯域幅が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、少なくとも他のクラスの提案ルートの帯域幅の一部を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最大数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれのリンクの現在のクラスの使用可能帯域幅を割り振られた部分だけ削減し、複数の提案ルートそれぞれについて反復的に、所望の帯域幅リストから少なくとも他のクラスについて、現在の提案ルートの帯域幅が所望の帯域幅リストから少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００４４】
本発明の他の装置は、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワークの複数の既存のパスの代わりに複数の代替パスをネットワーク内に提供し、この複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送する。ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この装置は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、所望の帯域幅リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅リストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、使用可能な帯域幅およびリンクのリストから提案ルートのリンクを除去するステップと、所望の帯域幅リストから、提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、使用可能な帯域幅およびリンクのリストから複数の他のルートそれぞれのリンクを除去し、複数の他のルートのそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストからの少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップとを、実行できるように動作可能な置換ユニットを含む。
【００４５】
本発明の他の記録媒体には、複数の既存のパスによって搬送されたトラフィックを複数の代替パス間で再割り振りするために、ネットワーク内の複数の既存のパスの代わりに複数の代替パスをネットワーク内に提供する方法を実行するためのコンピュータ読み取り可能プログラムが記録され、この複数の既存のパスは、ネットワークの入口地点からネットワークの出口地点までトラフィックを搬送する。ネットワークは複数のリンクを含み、複数のサービスクラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のクラス、およびそのクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するクラスを現在のクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅として指定し、所望の帯域幅リストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅リストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅だけ削減し、所望の帯域幅リストから、提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートのそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストからの少なくとも他のクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップとを、含む。
【００４６】
本発明の前述の方法、装置、および記録媒体によれば、複数の既存のパスはそれぞれ、少なくとも１つの障害リンクを含むことができる。ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含むことが可能であり、複数の既存のパスおよび複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）とすることができる。複数のクラスは複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスとすることができる。
【００４７】
使用可能な帯域幅およびリンクのリストは以下のように提供可能であって、ネットワークの複数のリンクが決定可能であり、複数のリンクそれぞれをトラバースする複数の既存のパスのそれぞれが決定可能であり、複数のリンクそれぞれについて複数のクラスそれぞれに関連付けられた予約帯域幅が決定可能であり、この決定はそのリンクをトラバースする複数の既存のパスそれぞれに基づくものとすることが可能であり、複数のクラスそれぞれに関連付けられた最大帯域幅は複数のリンクそれぞれについて決定可能であり、複数のクラスそれぞれに関連付けられた使用可能帯域幅は、複数のリンクそれぞれについて、そのリンク上のそのクラスに関連付けられた最大帯域幅および予約帯域幅に基づいて決定可能である。
【００４８】
提案ルートの帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、所望の帯域幅のリストのうち現在の第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、提案ルートの帯域幅の残りの部分が現在の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックが提案ルートに割り当てられ、現在のルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振られ、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去され、現在のルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリスト上で次に高位の要素に対応するクラスが現在のクラスとなるように選択可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の帯域幅となるように選択可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容が繰り返される。
【００４９】
複数のルートそれぞれに関連付けられた帯域幅の残りの部分が少なくとも他のクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、複数の他のルートのうちの１つが選択可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の帯域幅より大きいかまたは等しいかどうかが決定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のクラスのトラフィックが選択されたルートに割り当て可能であり、選択されたルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の帯域幅よりも小さい場合、所望の帯域幅のリストのうち次に高位の要素に対応するクラスが現在のクラスとなるように指定可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の帯域幅となるように指定可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容を繰り返すことが可能であり、所望の帯域幅のリストが空でない場合、複数の他のルートのうちの他のルートが選択可能であり、複数の他のルートそれぞれが考慮されるまで前述の内容が繰り返される。
【００５０】
複数の代替パスのうちの１つが生成可能であり、提案ルートをその１次パスとして、また提案ルートの各クラスに関連付けられた帯域幅をその帯域幅として、有することが可能であるか、または複数の他のルートのそれぞれをその１次パスとして、また複数の他のルートのそれぞれの各クラスに関連付けられた帯域幅をその帯域幅として、有することが可能である。複数の代替パスのうちの２つまたはそれ以上のルートによってトラバースされたリンクのすべてが同一である場合、その２つまたはそれ以上の代替パスを組み合わせて、そのルートをその１次パスとして、また、２つまたはそれ以上の代替パスのそれぞれのクラスについて組み合わせた帯域幅をそのクラスについてのその帯域幅として有する、複数の代替パスのうちの新しいパスを生成することができる。
【００５１】
本発明の他の方法によれば、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークの複数の障害ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰが提供される。複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することができる。複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能な帯域幅を割り振られた帯域幅部分だけ削減し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数のルートが生成されるように現在の所望の帯域幅を複数の他のルート間で分割し、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り当て、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００５２】
本発明の他の装置は、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワーク内の複数の障害置換ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰを提供し、複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この装置は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートのリンクを使用可能な帯域幅およびリンクのリストから除去し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれのリンクを使用可能な帯域幅およびリンクのリストから除去し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を実行するように動作可能な置換ユニットを含む。
【００５３】
本発明の他の記録媒体には、複数の置換ラベルスイッチパス（ＬＳＰ）間で複数の障害ＬＳＰによって搬送されたトラフィックを再割り振りするために、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークの複数の障害ＬＳＰの代わりにＭＰＬＳネットワーク内に複数の置換ＬＳＰを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録され、複数の障害ＬＳＰはＭＰＬＳネットワーク内の入口地点からＭＰＬＳネットワーク内の出口地点までトラフィックを搬送する。ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、複数のリンクのそれぞれは、関連付けられた帯域幅で、複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能である。この方法は、ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、リストの各要素が、複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、所望の帯域幅のリストを提供するステップであって、リストの各要素は、複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、このリストの要素は帯域幅が減少していく順に配列される、提供するステップと、所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定し、現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定し、所望の帯域幅のリストの残りの要素のそれぞれがリスト内で１ポジション進むように、所望の帯域幅のリストから現在の第１の要素を除去するステップと、使用可能な帯域幅およびリンクのリストから、入口地点から出口地点までの現在の提案ルートを生成するステップであって、提案ルートの帯域幅は現在のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しいかどうかを判別するステップと、提案ルートの帯域幅が現在所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の一部を現在所望の帯域幅に割り振り、提案ルートによってトラバースされたリンクの使用可能な帯域幅を割り振られた帯域幅部分だけ削減し、提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを所望の帯域幅リストから搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを提案ルートに割り当て、提案ルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅のリストから除去するステップと、提案ルートの帯域幅が現在所望の帯域幅より小さい場合、使用可能な帯域幅およびリンクのリストから入口地点から出口地点までの複数の他のルートを生成し、他のルートのそれぞれが現在のｄｉｆｆｓｅｒｖクラスのトラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように現在の所望の帯域幅が複数の他のルート間で分割され、複数の他のルートそれぞれによってトラバースされたリンクの使用可能帯域幅を割り振られた帯域幅部分だけ削減し、複数の他のルートそれぞれに関連付けられた帯域幅の残りの部分のいずれかが、所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別し、搬送できる場合、少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを複数の他のルートのうちの少なくとも１つに割り当て、少なくとも１つの他のルートの帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振り、少なくとも１つの対応する要素を所望の帯域幅リストから除去するステップと、所望の帯域幅リストのすべての要素が除去されるまで、前述の内容を繰り返すステップと、を含む。
【００５４】
本発明の前述の方法、装置、および記録媒体によれば、それぞれのリンク上のｄｉｆｆｓｅｒｖクラスごとの使用可能な帯域幅のリストは、以下のように決定可能であって、
ＭＰＬＳネットワークの複数のリンクが決定可能であり、複数のリンクそれぞれをトラバースする複数のＬＳＰのそれぞれが決定可能であり、複数のリンクそれぞれについて、そのリンクをトラバースする複数のＬＳＰそれぞれに基づき、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた予約帯域幅が決定可能であり、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた最大帯域幅は複数のリンクそれぞれについて決定可能であり、複数のｄｉｆｆｓｅｒｖクラスそれぞれに関連付けられた使用可能帯域幅は、複数のリンクそれぞれについて、そのリンク上のそのｄｉｆｆｓｅｒｖクラスに関連付けられた最大帯域幅および予約帯域幅に基づいて決定可能である。
【００５５】
提案ルートの帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、所望の帯域幅のリストのうち現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、提案ルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックが提案ルートに割り当て可能であり、現在のルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、現在のルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリスト上で次に高位の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように選択可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の所望の帯域幅となるように選択可能であり、所望の帯域幅のリストのそれぞれが考慮されるまで、前述の内容が繰り返される。
【００５６】
複数のルートそれぞれに関連付けられた帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかは、以下のように決定可能であって、複数の他のルートのうちの１つが選択可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち現在の第１の要素に対応する帯域幅が現在の所望の帯域幅となるように選択可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しいかどうかが決定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅より大きいかまたは等しい場合、現在のｄｉｆｆｓｅｒｖクラスのトラフィックが選択されたルートに割り当て可能であり、選択されたルートの帯域幅の残りの部分の少なくとも一部が現在の所望の帯域幅に割り振り可能であり、所望の帯域幅のリストの残りの要素それぞれがリスト内で１ポジション進むように、現在の第１の要素が所望の帯域幅のリストから除去可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストのうち新しい第１の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、選択されたルートの帯域幅の残りの部分が現在の所望の帯域幅よりも小さい場合、所望の帯域幅のリストのうち次に高位の要素に対応するｄｉｆｆｓｅｒｖクラスが現在のｄｉｆｆｓｅｒｖクラスとなるように指定可能であり、所望の帯域幅のリストの次に高位の要素に対応する帯域幅が現在の所望の帯域幅となるように指定可能であり、所望の帯域幅のリストの各要素が考慮されるまで、前述の内容を繰り返すことが可能であり、所望の帯域幅のリストが空でない場合、複数の他のルートのうちの他のルートが選択可能であり、複数の他のルートそれぞれが考慮されるまで前述の内容が繰り返される。
【００５７】
複数の置換ＬＳＰのうちの１つが生成可能であり、提案ルートをその１次パスとして、また提案ルートの各ｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅をその帯域幅として、有することが可能であるか、または複数の他のルートのそれぞれをその１次パスとして、また提案ルートの各ｄｉｆｆｓｅｒｖに関連付けられた帯域幅をその帯域幅として、有することが可能である。複数の置換ＬＳＰのうちの２つまたはそれ以上のルートによってトラバースされたリンクのすべてが同一であるかどうかが判別可能であり、同一である場合、その２つまたはそれ以上の置換ＬＳＰを組み合わせて、そのルートをその１次パスとして、また、２つまたはそれ以上の置換ＬＳＰのそれぞれのｄｉｆｆｓｅｒｖクラスについて組み合わせた帯域幅をそのクラスについてのその帯域幅として有する、複数の置換ＬＳＰのうちの新しい置換ＬＳＰを生成することができる。複数の障害ＬＳＰのうちの少なくとも１つが再度動作可能な場合、複数の置換ＬＳＰのうちの１つまたは複数がもはや必要でないかどうかが判別され、必要でない場合、複数の置換ＬＳＰのうちの１つまたは複数が除去され、１つまたは複数の置換ＬＳＰによってトラバースされたリンク、および含まれるリンクのそれぞれについて各ｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅を含むように、使用可能な帯域幅およびリンクのリストが更新される。
【００５８】
本発明の前述の態様、機能、および利点は、好ましい諸実施形態についての以下の説明および添付の図面を参照しながら考察した場合、さらによく理解されるであろう。
【発明を実施するための最良の形態】
【００５９】
図１は、本発明の態様に従った、システムのオペレーションを実行するために使用されるトラフィックエンジニアリング要素１００の一例を示す。要素１００は、差異化サービス（ｄｉｆｆｓｅｒｖ）機能を有するＭＰＬＳネットワークなどの、ネットワーク１０２と情報をやり取りする。トラフィックエンジニアリング要素は、たとえばネットワークオペレーションセンタに位置するネットワーク管理システム内に配置され、帯域幅マネージャ１０４、復元ユニット１０６、および構成データベース１０８を含むことができる。帯域幅マネージャ１０４はネットワーク１０２を通過するトラフィックを制御し、特定のｄｉｆｆｓｅｒｖクラスに帯域幅を割り振る。復元ユニット１０６は、１つまたは複数のＬＳＰに障害が発生した場合、既存のＬＳＰに関する置換ラベルスイッチパスの代替えを制御する。構成データベース１０８は、ネットワーク１０２のトポロジ、ＬＳＰデータ、およびポリシーを格納する。帯域幅マネージャ１０４および復元ユニット１０６は、好ましくはハードウェアプラットフォーム上で動作するソフトウェアモジュールを備える。モジュール自体は、オブジェクト指向プログラム内のオブジェクトを備えることができる。代替の方法として、モジュールはＤＯＳ、Ｗｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘ、またはＭＡＣオペレーティングシステムにおけるプログラムとして実施可能である。その後プログラムはメモリ内に格納され、プロセッサによって命令として実行される。構成データベースは、好ましくは、帯域幅マネージャ１０４および復元ユニット１０６と同じ場所に配置することが可能なメモリである。別の方法として、構成データベースは復元ユニットからリモートに配置することが可能である。
【００６０】
一般に、要素１００は、たとえばＭＰＬＳネットワーク１０２などの、パケット交換網などを管理するために使用されるオペレーションサポートシステム（ＯＳＳ）を備えることができる。この要素は、スタンドアロン型システムを備えるか、あるいは、既存のまたは現在使用可能なＯＳＳに組み込むことができる。このシステムは、たとえばＷｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘなどの汎用マシンを使用して実施することができる。要素１００とネットワーク１０２との間の通信は、たとえばｔｅｌｎｅｔ、ＳＮＭＰなどを使用して実現することができる。要素１００間の通信は、たとえばＣＯＲＢＡ、ＲＭＩなどを使用して実現することができる。一例として、システムは、Ｊａｖａ（登録商標）を使用して、ネットワーク１０２と通信するためにＴｅｌｎｅｔを使用して、および要素１００間の通信を可能にするためにＣＯＲＢＡを使用して、実施される。
【００６１】
ネットワークトポロジには、ネットワークのルータおよび／またはノードならびにルータのペアを接続するリンクのリストが含まれる。さらに各リンクについて、リンクＩＤ、リンクによって接続された２つのインターフェースのインターネットプロトコル（ＩＰ）アドレス、Ｍｂｐｓ単位でのリンクの最大容量、およびリンクの障害または動作可能状況が格納される。各ルータについて、ルータＩＤおよびルータのインターフェースのＩＰアドレスのリストが格納される。ＬＳＰデータには、ネットワーク用にセットアップされたＬＳＰのリストが含まれ、各ＬＳＰについて、ＬＳＰ ＩＤ、ＡおよびＺエンドのＩＰアドレス、ＬＳＰによってサポートされる各ｄｉｆｆｓｅｒｖクラスについての合計の予約帯域幅、ＬＳＰのパス、すなわちＬＳＰによってトラバースされるリンクの順序付けされたシーケンス、ならびにセットアップおよび保持優先順位が含まれる。ｄｉｆｆｓｅｒｖポリシーは、サポートされるｄｉｆｆｓｅｒｖクラス間でネットワークリソースを区分する働きをし、各ｄｉｆｆｓｅｒｖクラスについてのｄｉｆｆｓｅｒｖクラス名およびネットワーク使用量制限を含む。
【００６２】
図２は、ネットワーク内で１つまたは複数の障害が発生した場合の、本発明の一態様に従った、ＭＰＬＳネットワーク２００の一部およびネットワークトラフィックの復元の例を示す。図示されたネットワークの部分には、ルータＲ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、およびＲ６が含まれ、それぞれ２０Ｍｂｐｓ帯域幅容量を有するリンクＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６、Ｌ７、およびＬ８、ならびに６Ｍｂｐｓ帯域幅容量を有するリンクＬ４が含まれる。初期には、ネットワークトラフィックは、リンクＬ１を介してルータＲ１とルータＲ２との間をルーティングされた２つのＬＳＰ、ＬＳＰ１およびＬＳＰ２に沿って搬送される。パスＬＳＰ１は８Ｍｂｐｓのトラフィックを搬送可能である、すなわち、８Ｍｂｐｓの帯域幅を有するが、実際には３ＭｂｐｓのｄｉｆｆｓｅｒｖクラスのＥＦトラフィックしか搬送しないため、５Ｍｂｐｓの帯域幅が未使用である。パスＬＳＰ２も８Ｍｂｐｓの帯域幅を有するが、１ＭｂｐｓのＡＦ１トラフィックしか搬送しないため、７Ｍｂｐｓの帯域幅が使用される。
【００６３】
リンクＬ１に障害が発生すると、現在のＭＰＬＳネットワーク復元スキームは、同じかまたはそれよりも大きい８Ｍｂｐｓの帯域幅を有するリンクを使用してＬＳＰ１を新しいＬＳＰに置き換えようと試み、さらにＬＳＰ２も同様に、少なくとも８Ｍｂｐｓの帯域幅を有するリンクを使用して新しいＬＳＰに置き換えようと試みる。したがって、各置換ＬＳＰは、置き換えるＬＳＰと同じ未使用の帯域幅を有する。
【００６４】
通常、リンクＬ１に障害が発生した場合、トラフィックはそれぞれが２０Ｍｂｐｓの容量を有するリンクＬ２、Ｌ３、およびＬ７に沿ってルーティングされるため、２つの置換ＬＳＰの組み合わせ帯域幅である１６Ｍｂｐｓを搬送することができる。しかしながら、リンクＬ２およびＬ３にも障害が発生すると、リンクＬ４には６Ｍｂｐｓの容量しかなく、２つの置換ＬＳＰのうちの１つのトラフィックでさえも搬送することができない。帯域幅が不十分であることから、トラフィックはＬ４を介して再ルーティングできないため、復元の試みは失敗する。
【００６５】
これに対して、本発明では、できる限り少ない置換ＬＳＰを生成することによって障害トラフィックを復元する。ここでは、新しいＬＳＰであるＬＳＰ３が生成され、そのパスはリンクＬ４、Ｌ５、Ｌ６、およびＬ７をカバーしている。ＬＳＰ３の帯域幅はＬＳＰ１およびＬＳＰ２によって実際に使用される合計帯域幅のみであるため、ＬＳＰ３には４Ｍｂｐｓの帯域幅しかない。したがって、ＬＳＰ３はリンクＬ４を含むことができる。
【００６６】
図３は、本発明に従って１つまたは複数の障害ＬＳＰの復元を実行するために、図１に示された帯域幅マネージャ１０４、復元ユニット１０６、および構成データベース１０８の間で実行されるメッセージングの一例を示す。第１に、帯域幅マネージャはＭＰＬＳネットワーク１０２の１つまたは複数のＬＳＰの障害を検出する。帯域幅マネージャは、復元スキーム、すなわち障害ＬＳＰの代わりに置換ＬＳＰを生成するプロセスを開始する旨の要求を、復元ユニットに送信する。その後復元ユニットは、ネットワークの構成データを取得するための要求を構成データベースに伝送し、構成データベースはこうしたデータを復元ユニットに送達する。次に、本発明の復元スキームが実行され、新しいＬＳＰが生成される。その後復元ユニットは、構成データを更新するために、新しいＬＳＰに関する情報を構成データベースに送信する。その後、復元ユニットは、ネットワークが首尾良く復元されたかどうかを示す応答を帯域幅マネージャに送信する。
【００６７】
本発明に従ったネットワーク復元の概要が、図４に示される。第１に、復元ユニットが帯域幅マネージャから復元要求を受け取り、復元スキームを開始すると、ステップ４０２に示されるように復元が開始される。復元要求は、各要素が（入口、出口、ｄｉｆｆｓｅｒｖクラス、帯域幅）の形である障害トラフィックのリスト、障害リンクのリスト、および、ＭＰＬＳネットワークが障害に応答して再ルーティングしたそれらの新しいパスを備える再ルーティングＬＳＰと呼ばれるＬＳＰのリストという、属性を含むことが可能である。その後、構成データベースからのネットワーク構成データ、障害リンクのリスト、および再ルーティングされたＬＳＰのリストを獲得した後、ステップ４０４が示すように、復元ユニットは、ＭＰＬＳネットワークの現在の状態を決定し、すなわち、ネットワーク内の各リンク上の各ｄｉｆｆｓｅｒｖクラスに使用可能な帯域幅が決定される。次に、ステップ４０６が示すように、それらの間をトラバースしている１つまたは複数の障害ＬＳＰを有する入口地点および出口地点のペアのリストが、復元要求の障害トラフィック属性のリストを使用して決定される。
【００６８】
次に、ステップ４０８および４１０が示すように、リスト内のすべての入口／出口ペアが考慮されるまで、入口地点および出口地点の各ペアの間で１つまたは複数の置換ＬＳＰが動的に生成される。すべての入口／出口ポートが考慮されると、ステップ４１２が示すように復元は終了する。
【００６９】
図５Ａ〜５Ｆは、入口地点および出口地点の所与のペア間での置換ＬＳＰの動的生成をより詳細に示す流れ図である。動的生成のために実行される計算、ならびに使用される入力、出力、および変数の一例が、表１および２に示される。第１に、ステップ５０２に示されるように、各ｄｉｆｆｓｅｒｖクラスについて各リンク上で使用可能な帯域幅のリストが示される。
【００７０】
図６は、ステップ４０４で言及した使用可能な帯域幅のリストの決定をより詳細に示す流れ図である。第１に、ステップ６０２が示すように、ネットワーク内のすべての障害のないリンクのリストが生成される。次に、ステップ６０４が示すように、各リンクをトラバースするＬＳＰのリストが決定される。次に、ステップ６０６が示すように、それぞれのこうしたＬＳＰによってトラバースされたリンクによって占有される帯域幅を決定するために、ＬＳＰのリストを使用して、障害のない各リンクについて、各ｄｉｆｆｓｅｒｖクラスに関連付けられた予約帯域幅が決定される。次に、ステップ６０８が示すように、各リンクの最大容量およびネットワーク使用量制限を使用して、各リンクの各ｄｉｆｆｓｅｒｖクラスに使用可能な最大帯域幅容量が決定される。したがって、ステップ６１０が示すように、各リンクの各ｄｉｆｆｓｅｒｖクラスに関連付けられた予約帯域幅が、そのリンクのそのクラスに関連付けられた最大使用可能帯域幅から削減されて、各リンクの各ｄｉｆｆｓｅｒｖクラスに関連付けられた使用可能帯域幅が決定される。
【００７１】
その後、再度図５Ａを参照すると、ステップ５０４に示されるように、それぞれの障害ＬＳＰによって各ｄｉｆｆｓｅｒｖクラスについて搬送された帯域幅に基づいて、各ｄｉｆｆｓｅｒｖについての所望帯域幅の合計のリストが決定される。その後、このリストは好ましくは、リスト内の第１の要素が最大の合計帯域幅を必要とするｄｉｆｆｓｅｒｖクラスならびにその必要帯域幅を含み、次の要素が次に合計の大きな必要帯域幅を有するｄｉｆｆｓｅｒｖクラスならびにその帯域幅を含む、などのように、最後の要素が最小帯域幅を必要とするｄｉｆｆｓｅｒｖクラスならびにその帯域幅を含むまで、帯域幅が減少していく順に配列される。有利なことに、所望帯域幅のリストは、第１の置換ＬＳＰが最大帯域幅を必要とするｄｉｆｆｓｅｒｖクラスのトラフィックを搬送するために生成されるように、帯域幅が減少していく順に配列される。通常、このｄｉｆｆｓｅｒｖクラスを搬送するために生成されるルートは、他のｄｉｆｆｓｅｒｖクラスの帯域幅を収容するためにも好適である。したがって、この様式で置換ＬＳＰを生成すると、結果としてより少ないＬＳＰが生成されることになる。
【００７２】
次に、ステップ５０６が示すように、所望帯域幅のリストが空でないかどうかが判別される。空でない場合、ステップ５０８が示すように、現在のｄｉｆｆｓｅｒｖクラスが、所望帯域幅のリスト内の第１の要素のｄｉｆｆｓｅｒｖクラスとして定義され、現在の所望帯域幅が、このリストの第１の要素内に含まれる帯域幅として定義される。次に、ステップ５１０が示すように、所望帯域幅のリストの第１の要素が除去され、リスト内の第２の要素が第１の要素となり、リスト内の第３の要素が第２の要素となる、などのように、リスト内の残りの要素が１ポジション進められる。その後、ステップ５１２が示すように、リンクおよびそれらの使用可能帯域幅のリストから、提案ルートが生成される。提案ルートは、現在のｄｉｆｆｓｅｒｖクラス、すなわち、今削除された所望帯域幅リストの第１の要素のｄｉｆｆｓｅｒｖクラスに使用可能な、最大帯域幅を有する。提案ルートは、たとえば「コスト」パラメータが使用可能帯域幅として定義される、知られているダイクストラのアルゴリズムの変形によって生成することができる。こうした計算の例および関係する入力、出力、変数、初期設定、および関数が、表３および４に示される。
【００７３】
次に図５Ｂを参照すると、提案ルートの帯域幅が現在の所望帯域幅よりも大きいかまたは等しい場合、すなわち、提案ルートの帯域幅が、所望帯域幅のリストから除去された第１の要素のｄｉｆｆｓｅｒｖクラスによって必要とされる帯域幅に少なくとも等しい場合、その提案ルートは現在のクラスのトラフィックを搬送することができる。その後、ステップ５２０が示すように、現在のクラスのトラフィックが提案ルートに割り当てられる。ステップ５２２が示すように、提案ルートが使用可能な帯域幅の一部が、現在のクラスが必要とする帯域幅、すなわち現在の所望帯域幅に割り振られる。ステップ５２４が示すように、提案ルートによってトラバースされたリンクの使用可能帯域幅が、割り振られた帯域幅部分だけ削減される。
【００７４】
図５Ｃは、提案ルートの帯域幅の残りの部分が、所望帯域幅のリストからの１つまたは複数の他のクラスのトラフィックを搬送できるかどうかについての、その後の判別を示す。ステップ５２６が示すように、ここで現在のクラスは、所望帯域幅のリストの新しい第１の要素のｄｉｆｆｓｅｒｖクラスの値を有するように定義され、ここで現在の所望帯域幅は、第１の要素に関連付けられた帯域幅となるように定義される。次に、ステップ５２８が示すように、ここで定義された新しい現在のクラスについて、提案ルート上の使用可能帯域幅が現在の所望帯域幅に少なくとも等しいかどうかが決定される。等しい場合、提案ルートには新しい現在のクラスのトラフィックも割り当てられる。具体的には、ステップ５３２が示すように、提案ルートには所望帯域幅のリストの新しい第１の要素のｄｉｆｆｓｅｒｖクラスのトラフィックが割り当てられ、ステップ５３４が示すように、ここで、提案ルートの未割り振り帯域幅の一部がそのｄｉｆｆｓｅｒｖクラスに関連付けられた帯域幅に割り振られる。提案ルートのリンクに使用可能な帯域幅が、帯域幅の割り振られた部分だけ削減される。次に、所望帯域幅のリストの現在の第１の要素が削除され、リスト内の残りの要素が１ポジション進められた結果、ここでリスト内の元の第３の要素がリスト内の第１の要素となる。
【００７５】
代替の方法として、ステップ５２８で、提案ルートの残りの未割り振り帯域幅が現在の所望帯域幅よりも小さいと判別された場合、次に、ステップ５３０が示すように、現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮されたかどうかが判別される。現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮された場合、プロセスは、図５Ａに示されるステップ５０６に戻る。代替の方法として、現在の提案パスについて所望帯域幅のリスト内のすべての要素が考慮されたのではない場合、ここで、ステップ５３１が示すように、現在のクラスおよび現在の所望帯域幅が、所望帯域幅のリストの現在の第２の要素のクラスおよび帯域幅の値を有するように定義され、ステップ５２８で実行される判別が繰り返される。ステップ５２８で、提案ルートの残りの未割り振り帯域幅が、現在の所望帯域幅に少なくとも等しいと判別された場合、前述のように、ステップ５３２、５３４、および５３６が繰り返される。代替の方法として、ステップ５２８で、提案ルートの残りの未割り振り帯域幅が現在の所望帯域幅よりも小さいと判別された場合、ステップ５３０および５３１が繰り返され、結果として、ここで、現在のクラスおよび現在の所望帯域幅がリスト内の現在の第３の要素のクラスおよび帯域幅の値を有するように定義され、ステップ５２８で判別が再度実行される。
【００７６】
図５Ｃの上記ステップは、ステップ５３８が示すように、所望帯域幅のリストのすべての要素が考慮されるまで、すなわち、所望帯域幅のリストの各要素のｄｉｆｆｓｅｒｖクラスおよび関連付けられた帯域幅が、（ｉ）提案ルートに割り当てられてリストから削除されるまで、あるいは（ｉｉ）提案ルートに割り当てられておらずリストに残っているが考慮されるまで、繰り返される。
【００７７】
図５Ｄは、図５Ａのステップ５１４で実施された判別によって、提案ルートの帯域幅が、現在の所望帯域幅に関連付けられた帯域幅、すなわち、使用可能帯域幅のリストの以前の第１の要素に関連付けられた帯域幅より少ないことが判明した場合に実施される操作を示す。第１に、ステップ５４０が示すように、提案ルートが収容できる最大の現在の帯域幅が提案ルートに割り振られる。次に、ステップ５４１が示すように、提案ルートのリンク上の使用可能帯域幅が、帯域幅の割り振られた部分だけ削減される。次に、ステップ５４２が示すように、現在必要な帯域幅が満たされているかどうかが判別される。現在必要な帯域幅が満たされている場合、プロセスは図５Ｅのステップ５４６に進む。現在必要な帯域幅が満たされていない場合、ステップ５４３が示すように、新しい提案ルートの生成が試行される。新しい提案ルートを生成する試行が成功した場合、ステップ５４０、５４１、および５４２が繰り返され、新しい提案ルートを生成する試行が、使用可能帯域幅の欠如などによって失敗した場合、現在必要な帯域幅はこれまでに割り振られた帯域幅で満たされているとみなされ、その後、プロセスは図５Ｅに示されるステップ５４６に進む。
【００７８】
図５Ｅおよび５Ｆは、所望帯域幅の残りの要素のいずれかが、前述の様式で生成された新しいルートを介して搬送可能であるかどうかの、その後の判別を示す。ステップ５４６が示すように、新しいルートのうちの１つが選択され、その後、ステップ５４８が示すように、現在のクラスおよび現在必要な帯域幅が、所望帯域幅のリストの現在の第１の要素に含まれるクラスおよびその関連付けられた帯域幅として定義される。ステップ５５０が示すように、現在のクラスについて、そのルートの残りの使用可能帯域幅が現在の所望帯域幅と比較される。そのルートの使用可能帯域幅が現在の所望帯域幅より大きいかまたは等しい場合、ステップ５６０が示すように、現在のクラスのトラフィックがそのルートに割り当てられる。ステップ５６２が示すように、現在の所望帯域幅がそのルートに割り振られ、そのルートのリンク上の使用可能帯域幅が帯域幅の割り振られた部分だけ削減される。その後、ステップ５６４が示すように、所望帯域幅のリストの第１の要素が所望帯域幅のリストから除去され、リスト内の残りの要素が１ポジション進められる。その後、ステップ５６６が示すように、何らかの要素が所望帯域幅のリスト内に残っている場合、ステップ５６８が示すように、現在のクラスおよび現在の帯域幅の値が上記の様式で再度定義され、新しい現在のクラスおよび現在の帯域幅についてステップ５５０が繰り返される。
【００７９】
代替の方法として、ルートの残りの使用可能帯域幅が現在の所望帯域幅より少ない場合、ステップ５５２が示すように、所望帯域幅のリスト内の次の要素に含まれる値が、現在のクラスおよび現在の所望帯域幅として再定義される。その後、ステップ５５０に示される判別が繰り返され、それに基づいて、所望帯域幅のリストのすべての要素が考慮されるまで、前述のステップ５６０、５６２、および５６４が繰り返されるか、または前述のステップ５５２が繰り返される。その後、新しいルートのうちの１つまたは複数が考慮されていない場合、ステップ５７０および５７２が示すように、これらルートのうちの他のルートが選択され、新しいルートがすべて考慮されるまで図５Ｅおよび図５Ｆに示されるステップが繰り返される。
【００８０】
有利なことには、図４、図５Ａ〜５Ｆ、および図６に示される操作により、入口地点および出口地点の各ペア間の障害トラフィックに対処するために必要な最低数の新しいＬＳＰが生成される。さらに復元は、こうした障害が発生するたびに実行されるように、動的に実行される。
【００８１】
さらに、図４、図５Ａ〜５Ｆ、および図６を参照した前述の操作は、最低数の新しいルートの動的な生成を必要とする他の応用例でも使用可能である。
【００８２】
本発明の他の利点は、障害リンクが復元された後、ネットワークがその以前の最適化された状態に戻るように、ネットワークはその元の状態、すなわち、リンクの障害以前のネットワークの状態に復帰することである。図７は、元のネットワークに復元するために必要な、帯域幅マネージャ、復元ユニット、および構成データベースの間でのメッセージングの例を示す。第１に、帯域幅マネージャは、リンクが復元されたことを検出し、復元スキームに対して復帰要求を発行する。次に、復元ユニットは、復元ＬＳＰによってトラバースされたリンクおよびこれらのリンク上で搬送された各ｄｉｆｆｓｅｒｖクラスの帯域幅を使用可能帯域幅のリストに復元することによって、各リンク上の各ｄｉｆｆｓｅｒｖクラスで使用可能な帯域幅のリストを更新する。次に復元ユニットは、ネットワークの状態、すなわち、構成データベースに格納された構成データを更新する。その後、復元ユニットは、ネットワークがその以前の状態に復元された旨の指示を、帯域幅マネージャに送信する。
【００８３】
以上、本明細書では、特定の諸実施形態を参照しながら本発明について説明してきたが、これらの諸実施形態が本発明の原理および応用例の単なる例示であることを理解されよう。したがって、この例示的な諸実施形態に対して多数の修正形態が実行可能であること、および添付の特許請求の範囲に定義された本発明の趣旨および範囲を逸脱することなく、他の配置構成が考案可能であることを理解されよう。
【図面の簡単な説明】
【００８４】
【図１】本発明を実施するネットワーク管理要素の一例を示すブロック図である。
【図２】本発明に従った、障害リンクを備えたパスを含むネットワークの一部を示し、置換パスを形成するために使用されるリンクを示す図である。
【図３】ネットワークの一部に障害が発生した場合、サービスを復元するための、本発明に従って生成されるコマンドおよび応答のシーケンスを示す図である。
【図４】ネットワークの一部の障害に応答して、本発明に従った置換パスを生成するために実行されるオペレーションの流れを示す図である。
【図５Ａ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｂ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｃ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｄ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｅ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図５Ｆ】図４の置換パスを動的に生成するためのオペレーションの流れを示す図である。
【図６】図５Ａに示されたネットワーク内の使用可能な帯域幅およびリンクのリストを形成するために実行されるオペレーションを示す流れ図である。
【図７】障害リンクがサービスに返された後、元のネットワークパスを復元するために本発明に従って実行されるコマンドおよび応答のシーケンスを示す図である。
【特許請求の範囲】
【請求項１】
複数の既存のパスによって搬送されるトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに少なくとも１つの代替パスを提供する方法であって、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの帯域幅が前記必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの帯域幅の一部を前記必要な帯域幅に割り振るステップと
を含むことを特徴とする方法。
【請求項２】
前記複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、前記複数の既存のパスおよび前記複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）であることを特徴とする請求項１に記載の方法。
【請求項４】
前記提案ルートは、使用可能な最大帯域幅を有するルートであることを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記決定ステップは、前記複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含み、
前記割り振りステップは、
前記提案ルートの前記帯域幅の一部を、前記複数の必要な帯域幅のうちの所与の１つに割り振るステップと、
前記提案ルートの前記帯域幅が前記所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスの前記トラフィックを前記提案ルートに割り当てるステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記所与の帯域幅は、前記複数の必要な帯域幅内で最大の非割り振り帯域幅であることを特徴とする請求項５に記載の方法。
【請求項７】
前記提案ルートの前記帯域幅の残りの部分の一部を、前記複数の必要な帯域幅内の他の帯域幅に割り振るステップと、
前記提案ルートの前記帯域幅の残りの部分が前記他の帯域幅よりも大きいかまたは等しい場合、前記対応するクラスのトラフィックを前記提案ルートに割り当てるステップと、
をさらに含むことを特徴とする請求項５に記載の方法。
【請求項８】
前記他の帯域幅は、前記提案ルートの前記帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する、前記複数の必要な帯域幅内の前記残りの非割り振り帯域幅のうちの最大の要素であることを特徴とする請求項７に記載の方法。
【請求項９】
前記複数の必要な帯域幅内の各非割り振り帯域幅について、帯域幅が減少していく順に、前記提案ルートの前記帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、
前記提案ルートの前記帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、前記対応するクラスの前記トラフィックを前記提案ルートに割り当てるステップと、
をさらに含むことを特徴とする請求項５に記載の方法。
【請求項１０】
前記提案ルートの前記帯域幅が前記必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、
最低数の他のルートが生成されるように、前記提案ルートおよび前記少なくとも１つの他のルートの間で前記必要な帯域幅を分割するステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記決定するステップは、前記複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含み、
前記少なくとも１つの他のルートを生成するステップは、
前記提案ルートの帯域幅が前記複数の必要な帯域幅のうちの所与の１つよりも少ない場合、前記少なくとも１つの他のルートを生成するステップと、
前記提案ルートおよび前記少なくとも１つの他のルートの間で前記所与の帯域幅を分割するステップと、
前記対応するクラスの前記トラフィックを、前記提案ルートおよび前記少なくとも１つの他のルートに割り当てるステップと、
を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記所与の帯域幅は、前記複数の必要な帯域幅のうちの最大の帯域幅であることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記提案ルートおよび前記少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、前記複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、
前記対応するクラスの前記トラフィックを前記選択されたルートに割り当てるステップと、
をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記他の帯域幅は、前記選択されたルートの前記帯域幅の前記残りの部分よりも小さいかまたは等しい帯域幅を有する、前記複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅であることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、前記提案ルートおよび前記少なくとも１つの他のルートのうちの選択されたルートの前記帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、
前記選択されたルートの前記帯域幅の前記残りの部分がその帯域幅よりも大きいかまたは等しい場合、前記対応するクラスの前記トラフィックを前記選択されたルートに割り当てるステップと、
をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１６】
前記提案ルートの生成ステップに先立って、使用可能帯域幅およびリンクを提供するステップをさらに含み、
前記ネットワークの複数のリンクそれぞれについて、そのリンクをトラバースする前記複数の既存のパスのそれぞれを決定するステップと、
そのリンクをトラバースする前記複数の既存のパスのそれぞれに基づいて、前記複数のリンクのそれぞれについて前記予約帯域幅を決定するステップと、
前記複数のリンクのそれぞれについて最大帯域幅を決定するステップと、
そのリンクの前記最大帯域幅および前記予約帯域幅に基づいて、前記複数のリンクのそれぞれについて前記使用可能帯域幅を決定するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項１７】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記予約帯域幅を決定するステップと、前記最大帯域幅を決定するステップと、前記使用可能帯域幅を決定するステップとは、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記予約帯域幅と、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記最大帯域幅と、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記使用可能帯域幅とを決定するために、前記複数のクラスそれぞれについて実行されることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記少なくとも１つの代替パスはマルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワーク内に複数の置換ラベルスイッチパス（ＬＳＰ）を含み、前記複数の既存のパスは、前記ＭＰＬＳネットワーク内に複数の障害ＬＳＰを含み、前記複数の障害ＬＳＰは、前記ＭＰＬＳネットワーク内の入口地点から前記ＭＰＬＳネットワーク内の出口地点までトラフィックを搬送し、前記ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、前記複数のリンクのそれぞれは、関連付けられた帯域幅で、前記複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能であって、
前記決定するステップは、
前記ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、前記リストの各要素が、前記複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、
所望の帯域幅のリストを提供するステップであって、前記リストの各要素は、前記複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスの前記トラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、前記リストの要素は帯域幅が減少していく順に配列される、提供するステップと、
を含み、
前記生成するステップは、
前記所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定するステップと、前記現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定するステップと、所望の帯域幅の前記リストの前記残りの要素のそれぞれが前記リスト内で１ポジション進むように、前記所望の帯域幅のリストから前記現在の第１の要素を除去するステップと、
前記使用可能な帯域幅およびリンクのリストから、前記入口地点から前記出口地点までの現在の提案ルートを生成するステップであって、前記提案ルートの前記帯域幅は前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、
を含み、
前記割り振るステップは、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より大きいかまたは等しいかどうかを判別するステップと、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より大きいかまたは等しい場合、
前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記提案ルートに割り当てるステップと、前記提案ルートの前記帯域幅の一部を前記現在の所望帯域幅に割り振るステップと、
前記提案ルートによってトラバースされた前記リンクの前記使用可能な帯域幅を前記割り振られた部分だけ削減するステップと、
前記所望の帯域幅リストから、前記提案ルートの前記帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別するステップと、搬送できる場合、前記少なくとも他のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記提案ルートに割り当てるステップと、前記提案ルートの前記帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた前記帯域幅に割り振るステップと、少なくとも１つの対応する要素を前記所望の帯域幅のリストから除去するステップと、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より小さい場合、
前記使用可能な帯域幅およびリンクのリストから前記入口地点から前記出口地点までの複数の他のルートを生成するステップであって、他のルートのそれぞれが前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように前記現在の所望帯域幅が前記複数の他のルート間で分割される、生成するステップと、
前記複数の他のルートそれぞれによってトラバースされた前記リンクの前記使用可能帯域幅を、前記割り振られた帯域幅部分だけ削減するステップと、
前記複数の他のルートそれぞれに関連付けられた前記帯域幅の前記残りの部分のいずれかが、前記所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別するステップと、搬送できる場合、前記少なくとも他のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記複数の他のルートのうちの少なくとも１つに割り当てるステップと、前記少なくとも１つの他のルートの前記帯域幅の他の部分を前記少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた前記帯域幅に割り振るステップと、少なくとも１つの対応する要素を前記所望の帯域幅リストから除去するステップと、
を含み、
前記生成するステップおよび前記割り振るステップは、前記所望の帯域幅リストのすべての要素が除去されるまで繰り返されることを特徴とする請求項１６に記載の方法。
【請求項１９】
複数の既存のパスによって搬送されるトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供するための装置であって、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの前記帯域幅が必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの前記帯域幅の一部を前記必要な帯域幅に割り振るステップと、
を実行するように動作可能な、置換ユニットを含むことを特徴とする装置。
【請求項２０】
ネットワークの複数の既存のパスの代わりに、前記複数の既存のパスによって搬送されるトラフィックを再割り振りするための少なくとも１つの代替パスを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録される記録媒体であって、前記方法は、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの前記帯域幅が前記必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの前記帯域幅の一部を前記必要な帯域幅に割り振るステップと、
を含むことを特徴とする記録媒体。
【請求項１】
複数の既存のパスによって搬送されるトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに少なくとも１つの代替パスを提供する方法であって、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの帯域幅が前記必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの帯域幅の一部を前記必要な帯域幅に割り振るステップと
を含むことを特徴とする方法。
【請求項２】
前記複数の既存のパスのそれぞれが、少なくとも１つの障害リンクを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ネットワークは、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークを含み、前記複数の既存のパスおよび前記複数の代替パスは、それぞれが複数のラベルスイッチパス（ＬＳＰ）であることを特徴とする請求項１に記載の方法。
【請求項４】
前記提案ルートは、使用可能な最大帯域幅を有するルートであることを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記決定ステップは、前記複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含み、
前記割り振りステップは、
前記提案ルートの前記帯域幅の一部を、前記複数の必要な帯域幅のうちの所与の１つに割り振るステップと、
前記提案ルートの前記帯域幅が前記所与の帯域幅よりも大きいかまたは等しい場合、その対応するクラスの前記トラフィックを前記提案ルートに割り当てるステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記所与の帯域幅は、前記複数の必要な帯域幅内で最大の非割り振り帯域幅であることを特徴とする請求項５に記載の方法。
【請求項７】
前記提案ルートの前記帯域幅の残りの部分の一部を、前記複数の必要な帯域幅内の他の帯域幅に割り振るステップと、
前記提案ルートの前記帯域幅の残りの部分が前記他の帯域幅よりも大きいかまたは等しい場合、前記対応するクラスのトラフィックを前記提案ルートに割り当てるステップと、
をさらに含むことを特徴とする請求項５に記載の方法。
【請求項８】
前記他の帯域幅は、前記提案ルートの前記帯域幅の残りの部分より小さいかまたは等しい帯域幅を有する、前記複数の必要な帯域幅内の前記残りの非割り振り帯域幅のうちの最大の要素であることを特徴とする請求項７に記載の方法。
【請求項９】
前記複数の必要な帯域幅内の各非割り振り帯域幅について、帯域幅が減少していく順に、前記提案ルートの前記帯域幅の残りの部分のそれぞれの部分をその帯域幅に連続的に割り振るステップと、
前記提案ルートの前記帯域幅の残りの部分がその帯域幅よりも大きいかまたは等しい場合、前記対応するクラスの前記トラフィックを前記提案ルートに割り当てるステップと、
をさらに含むことを特徴とする請求項５に記載の方法。
【請求項１０】
前記提案ルートの前記帯域幅が前記必要な帯域幅よりも少ない場合、少なくとも１つの他のルートを生成するステップと、
最低数の他のルートが生成されるように、前記提案ルートおよび前記少なくとも１つの他のルートの間で前記必要な帯域幅を分割するステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記決定するステップは、前記複数のサービスクラスに対応する複数のこうした必要な帯域幅を決定するステップを含み、
前記少なくとも１つの他のルートを生成するステップは、
前記提案ルートの帯域幅が前記複数の必要な帯域幅のうちの所与の１つよりも少ない場合、前記少なくとも１つの他のルートを生成するステップと、
前記提案ルートおよび前記少なくとも１つの他のルートの間で前記所与の帯域幅を分割するステップと、
前記対応するクラスの前記トラフィックを、前記提案ルートおよび前記少なくとも１つの他のルートに割り当てるステップと、
を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記所与の帯域幅は、前記複数の必要な帯域幅のうちの最大の帯域幅であることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記提案ルートおよび前記少なくとも１つの他のルートのうちの選択されたルートの帯域幅の残りの部分の一部を、前記複数の必要な帯域幅のうちの他の帯域幅に割り振るステップと、
前記対応するクラスの前記トラフィックを前記選択されたルートに割り当てるステップと、
をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記他の帯域幅は、前記選択されたルートの前記帯域幅の前記残りの部分よりも小さいかまたは等しい帯域幅を有する、前記複数の必要な帯域幅のうちの残りの非割り振り帯域幅のうちで最大の帯域幅であることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記複数の必要な帯域幅の各非割り振り帯域幅要素について、帯域幅が減少していく順に、前記提案ルートおよび前記少なくとも１つの他のルートのうちの選択されたルートの前記帯域幅の残りの部分のそれぞれの部分を、その帯域幅に連続的に割り振るステップと、
前記選択されたルートの前記帯域幅の前記残りの部分がその帯域幅よりも大きいかまたは等しい場合、前記対応するクラスの前記トラフィックを前記選択されたルートに割り当てるステップと、
をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１６】
前記提案ルートの生成ステップに先立って、使用可能帯域幅およびリンクを提供するステップをさらに含み、
前記ネットワークの複数のリンクそれぞれについて、そのリンクをトラバースする前記複数の既存のパスのそれぞれを決定するステップと、
そのリンクをトラバースする前記複数の既存のパスのそれぞれに基づいて、前記複数のリンクのそれぞれについて前記予約帯域幅を決定するステップと、
前記複数のリンクのそれぞれについて最大帯域幅を決定するステップと、
そのリンクの前記最大帯域幅および前記予約帯域幅に基づいて、前記複数のリンクのそれぞれについて前記使用可能帯域幅を決定するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項１７】
前記複数の既存のパスは、複数のサービスクラスのトラフィックを搬送し、
前記予約帯域幅を決定するステップと、前記最大帯域幅を決定するステップと、前記使用可能帯域幅を決定するステップとは、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記予約帯域幅と、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記最大帯域幅と、前記複数のリンクのそれぞれでそのクラスに関連付けられた前記使用可能帯域幅とを決定するために、前記複数のクラスそれぞれについて実行されることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記少なくとも１つの代替パスはマルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワーク内に複数の置換ラベルスイッチパス（ＬＳＰ）を含み、前記複数の既存のパスは、前記ＭＰＬＳネットワーク内に複数の障害ＬＳＰを含み、前記複数の障害ＬＳＰは、前記ＭＰＬＳネットワーク内の入口地点から前記ＭＰＬＳネットワーク内の出口地点までトラフィックを搬送し、前記ＭＰＬＳネットワークは複数のリンクを含み、複数の差異化サービス（ｄｉｆｆｓｅｒｖ）クラスのそれぞれについてトラフィックを搬送することが可能であり、前記複数のリンクのそれぞれは、関連付けられた帯域幅で、前記複数のｄｉｆｆｓｅｒｖクラスのうちの少なくとも１つについてトラフィックを搬送するように動作可能であって、
前記決定するステップは、
前記ＭＰＬＳネットワーク内で使用可能な帯域幅およびリンクのリストを提供するステップであって、前記リストの各要素が、前記複数のリンク、およびそのリンク上を搬送される複数のｄｉｆｆｓｅｒｖクラスそれぞれについて使用可能な帯域幅のそれぞれを含む、提供するステップと、
所望の帯域幅のリストを提供するステップであって、前記リストの各要素は、前記複数のｄｉｆｆｓｅｒｖクラス、およびそのｄｉｆｆｓｅｒｖクラスの前記トラフィックを搬送するのに必要な関連付けられた帯域幅のそれぞれを含み、前記リストの要素は帯域幅が減少していく順に配列される、提供するステップと、
を含み、
前記生成するステップは、
前記所望の帯域幅リスト内で現在の第１の要素に対応するｄｉｆｆｓｅｒｖクラスを現在のｄｉｆｆｓｅｒｖクラスとなるように指定するステップと、前記現在の第１の要素に関連付けられた帯域幅を現在の所望の帯域幅となるように指定するステップと、所望の帯域幅の前記リストの前記残りの要素のそれぞれが前記リスト内で１ポジション進むように、前記所望の帯域幅のリストから前記現在の第１の要素を除去するステップと、
前記使用可能な帯域幅およびリンクのリストから、前記入口地点から前記出口地点までの現在の提案ルートを生成するステップであって、前記提案ルートの前記帯域幅は前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックを搬送するために使用可能な最大帯域幅である、生成するステップと、
を含み、
前記割り振るステップは、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より大きいかまたは等しいかどうかを判別するステップと、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より大きいかまたは等しい場合、
前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記提案ルートに割り当てるステップと、前記提案ルートの前記帯域幅の一部を前記現在の所望帯域幅に割り振るステップと、
前記提案ルートによってトラバースされた前記リンクの前記使用可能な帯域幅を前記割り振られた部分だけ削減するステップと、
前記所望の帯域幅リストから、前記提案ルートの前記帯域幅の残りの部分が少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別するステップと、搬送できる場合、前記少なくとも他のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記提案ルートに割り当てるステップと、前記提案ルートの前記帯域幅の他の部分を少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた前記帯域幅に割り振るステップと、少なくとも１つの対応する要素を前記所望の帯域幅のリストから除去するステップと、
前記提案ルートの前記帯域幅が前記現在の所望帯域幅より小さい場合、
前記使用可能な帯域幅およびリンクのリストから前記入口地点から前記出口地点までの複数の他のルートを生成するステップであって、他のルートのそれぞれが前記現在のｄｉｆｆｓｅｒｖクラスの前記トラフィックの一部を搬送するために指定され、最低数の他のルートが生成されるように前記現在の所望帯域幅が前記複数の他のルート間で分割される、生成するステップと、
前記複数の他のルートそれぞれによってトラバースされた前記リンクの前記使用可能帯域幅を、前記割り振られた帯域幅部分だけ削減するステップと、
前記複数の他のルートそれぞれに関連付けられた前記帯域幅の前記残りの部分のいずれかが、前記所望の帯域幅リストから少なくとも他のｄｉｆｆｓｅｒｖクラスのトラフィックを搬送できるかどうかを判別するステップと、搬送できる場合、前記少なくとも他のｄｉｆｆｓｅｒｖクラスの前記トラフィックを前記複数の他のルートのうちの少なくとも１つに割り当てるステップと、前記少なくとも１つの他のルートの前記帯域幅の他の部分を前記少なくとも他のｄｉｆｆｓｅｒｖクラスに関連付けられた前記帯域幅に割り振るステップと、少なくとも１つの対応する要素を前記所望の帯域幅リストから除去するステップと、
を含み、
前記生成するステップおよび前記割り振るステップは、前記所望の帯域幅リストのすべての要素が除去されるまで繰り返されることを特徴とする請求項１６に記載の方法。
【請求項１９】
複数の既存のパスによって搬送されるトラフィックを再割り振りするために、ネットワークの複数の既存のパスの代わりに、少なくとも１つの代替パスを提供するための装置であって、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの前記帯域幅が必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの前記帯域幅の一部を前記必要な帯域幅に割り振るステップと、
を実行するように動作可能な、置換ユニットを含むことを特徴とする装置。
【請求項２０】
ネットワークの複数の既存のパスの代わりに、前記複数の既存のパスによって搬送されるトラフィックを再割り振りするための少なくとも１つの代替パスを提供する方法を実行するための、コンピュータ読み取り可能プログラムが記録される記録媒体であって、前記方法は、
前記複数の既存のパスのトラフィックを搬送するために必要な合計帯域幅を決定するステップと、
前記ネットワーク内の使用可能リンクから提案ルートを生成するステップと、
前記提案ルートの前記帯域幅が前記必要な帯域幅より大きいかまたは等しい場合、前記提案ルートの前記帯域幅の一部を前記必要な帯域幅に割り振るステップと、
を含むことを特徴とする記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図５Ｅ】
【図５Ｆ】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図５Ｅ】
【図５Ｆ】
【図６】
【図７】
【公表番号】特表２００８−５１２００９（Ｐ２００８−５１２００９Ａ）
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願番号】特願２００７−５２７２７０（Ｐ２００７−５２７２７０）
【出願日】平成１７年５月４日（２００５．５．４）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０１５５６６
【国際公開番号】ＷＯ２００５／１１７３１２
【国際公開日】平成１７年１２月８日（２００５．１２．８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｌｉｎｕｘ
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願日】平成１７年５月４日（２００５．５．４）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０１５５６６
【国際公開番号】ＷＯ２００５／１１７３１２
【国際公開日】平成１７年１２月８日（２００５．１２．８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｌｉｎｕｘ
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
[ Back to top ]