(57)【要約】      （修正有）【課題】最小同時不具合率、又は信頼性保証に伴う最小コストを達成するセグメント保護の最適な組合せ(ＯＣＳＰ)を提供するための方法。【解決手段】データ送信を不具合から保護するための方法であって、データ送信は、マルチプロトコルラベルスイッチング(ＭＰＬＳ)ネットワークにおいて始点から終点までであり、データ送信は、保護領域内のセグメント保護を有するラベル付きスイッチパス(ＬＳＰ)を経由する。保護領域ごとに最大回復時間が制約され、保護領域ごとに１つ又は複数のバックアップトンネルが確定される。ＬＳＰ及びバックアップトンネルのノードのグラフが構築される。各エッジに重みが割り当られて、加重グラフが生成される。セグメント保護の最適な組合せ及び信頼性保証最低コストを用いることによって、加重グラフに基づいて、最小コストで信頼性制約を満たす、始点から終点までのパスが確定される。【選択図】図３
2013214965.tif 000002
【特許請求の範囲】
【請求項１】
データ送信を不具合から保護するための方法であって、該データ送信は、マルチプロトコルラベルスイッチング(ＭＰＬＳ)ネットワークにおいて始点から終点までであり、該データ送信は、保護領域内のセグメント保護を有するラベル付きスイッチパス(ＬＳＰ)を介し、該方法は、
前記保護領域ごとに最大回復時間を制約するステップと、
前記保護領域ごとに１つ又は複数のバックアップトンネルを確定するステップと、
前記ＬＳＰ及び前記バックアップトンネルのノードのグラフを構築するステップであって、該グラフ内のエッジは前記ノード間のリンクを表すものと、
前記各エッジに重みを割り当てて加重グラフを生成するステップと、
以下の式に従って、セグメント保護の最適な組合せ(ＯＣＳＰ)及び信頼性保証最低コスト(ＲＧＬＣ)を用いることによって、前記加重グラフに基づいて、最小コストで信頼性制約を満たす、前記始点から前記終点までのパスを確定するステップであって、
【数１】
2013214965.tif 000014
ここで、(ｉ，ｊ)は前記パスの前記エッジを表し、ｃは該エッジ(ｉ，ｊ)と関連付けられた前記コストを表し、Ｆ(Ｐ)は選択されたバックアップトンネルとの前記ＬＳＰのリスク加重同時不具合率であり、ｐｒｅｑは前記ＬＳＰの要求される最大不具合率であるもの、
を含み、前記ステップはプロセッサにおいて実行される、不具合からのデータ送信を保護するための方法。
【請求項２】
前記ＭＰＬＳネットワークは、前記ネットワークの様々なユーザーに差別化されたサービス信頼性を提供する、請求項１に記載の方法。
【請求項３】
前記ＭＰＬＳネットワークは光ネットワークである、請求項１に記載の方法。
【請求項４】
前記最小コストは、前記ネットワークの特定のユーザーに対するものである、請求項１に記載の方法。
【請求項５】
特定の不具合の条件付き確率は
【数２】
2013214965.tif 000015
であり、ここで、ｒはリスクイベントであり、stは特定のリンクを表し、不具合の確率は以下の式である
【数３】
2013214965.tif 000016
請求項１に記載の方法。
【請求項６】
前記最大回復時間は、前記保護領域の最大サイズに対する制約である、請求項１に記載の方法。
【請求項７】
最大回復時間要件によって前記各保護領域のホップカウントを制約するステップを更に含む、請求項１に記載の方法。
【請求項８】
前記重みは、前記保護のために選択された前記リンクにおけるコストと、不具合率に関するリンク重みとを含む、請求項１に記載の方法。
【請求項９】
前記ＲＧＬＣは、前記グラフに対し前記起点から前記終点まで実行され、前記信頼性が保証された最低コストの保護が確定される、請求項１に記載の方法。
【請求項１０】
前記グラフに対し前記起点から前記終点まで確率に関する最短パス手順を実行して、最も信頼性のある保護を確定するステップを更に含む、請求項１に記載の方法。
【請求項１１】
最小同時不具合率を提供するセグメント保護の最適な組合せが、最短パスプロセスを用いることによって確定される、請求項１に記載の方法。
【請求項１２】
最大回復時間要件によって前記各保護領域の距離を制約するステップを更に含む、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には波長分割多重(ＷＤＭ)ネットワークにおけるマルチプロトコルラベルスイッチング(ＭＰＬＳ)に関し、より詳細には、ＭＰＬＳネットワークにおけるラベルスイッチパス(ＬＳＰ：Label-Switched Path)の存続可能でコスト効率のよいパスの計算及び保護に関する。
【背景技術】
【０００２】
マルチプロトコルラベルスイッチング(ＭＰＬＳ)は、従来のバックボーンネットワークにおける高度に拡張可能であり、プロトコルに無感応なデータ送信メカニズムである。ＭＰＬＳは１つのネットワークノードから別のネットワークノードに、ラベルスイッチパス(ＬＳＰ)を用いてデータを方向付けて送信する。
【０００３】
図１Ａは、ＩＰ層１０１、ＭＰＬＳ層１０２、光トランスポートネットワーク(ＯＴＮ)層１０３、及び物理層１０４を有する従来のプロトコルスタックを示している。ＭＰＬＳは、長いネットワークアドレスではなく短いパスラベルに基づいて、１つのノードから次のノードへデータ送信を方向付け、ルーティングテーブルにおける複雑な参照を回避する。ラベルは、エンドポイント間ではなく遠隔ノード間の仮想リンク(パス)を識別する。
【０００４】
他の標準規格によるネットワーク、例えば同期光ネットワーキング(ＳＯＮＥＴ)及び同期デジタルハイアラーキ(ＳＤＨ)も可能であることに留意されたい。
【０００５】
これらのＭＰＬＳパケットは、ＩＰテーブルへの参照の代わりに、ラベル参照／スイッチの後にスイッチングされる。ラベルに基づくルーターはラベルスイッチルーター(ＬＳＲ)と呼ばれる。ラベルはラベル分配プロトコル(ＬＤＰ)を用いて分配される。
【０００６】
多様なネットワークアプリケーションの登場により、ＭＰＬＳネットワークは、ネットワークの様々なユーザーに差別化されたサービス信頼性を提供することが必要とされる。ＭＰＬＳネットワークは光ネットワークにおいて最も広く用いられており、光ネットワークでは、物理ネットワークリソース(長距離光ファイバー等)はネットワーク接続性に害を及ぼす可能性のある非常に多くのリスク(不具合)に対して脆弱である。
【０００７】
これらのリスクは、陸上環境(例えば、地震、洪水、及びハリケーン等の自然災害)、又は人間の活動(例えば、地下建設、トンネル火災、地引き網、及びアンカー)において生じる可能性がある。海洋環境は、不具合のロケーションを検出及び修復するのが困難であるので、特定の問題を課す。したがって、最もコスト効率のよい形でネットワーク差別化された信頼性要件を満たす方法を提供することが重要である。
【０００８】
通常、最短ルートしか確定しない従来のルーティング方法の結果、不具合率の高いＬＳＰが得られる傾向がある。なぜなら、ＬＳＰは、不具合に関係する要素が検討されないとき、高リスク環境を通る場合があるためである。
【０００９】
最小不具合率を有するＬＳＰを確定するパス計算方法も存在する。しかしながら、これらの方法は、多くの場合にルートの「迂回」を被り、この結果、ネットワークリソースの消費コストが高くなるとともに、終端間に遅延が生じる。
【００１０】
様々なユーザーのＬＳＰ信頼性に対するネットワーク要件が差別化され、これらは多くの場合に、最も信頼性の高い要件ほど厳しくないので、過不足のない信頼性でこれらの要件を満たしながら、ネットワークコストを節減することが可能である。同じ原理が、ＬＳＰ保護にも適用される。ネットワークのリスク情報及び相関不具合モデルを用いて、パス全体の保護又は局所的な保護を大幅に改善するＬＳＰ保護を確定することができる。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、最小同時不具合率、又は信頼性保証に伴う最小コストを達成するセグメント保護の最適な組合せ(ＯＣＳＰ)を提供するための方法が必要とされている。
【課題を解決するための手段】
【００１２】
この発明の実施の形態は、マルチプロトコルラベルスイッチング(ＭＰＬＳ)光ネットワークにおける複数の要件を満たす最適ラベルスイッチパス(ＬＳＰ)を確定する方法を提供する。この目的は、ＭＰＬＳネットワークにおいて不具合からデータ送信を保護することである。
【００１３】
信頼性保証最低コスト(ＲＧＬＣ：reliability-guaranteed least-cost)パス計算と呼ばれる１つの実施の形態では、差別化されたユーザーについて最小コストでネットワーク信頼性要件を満たすＬＳＰが確定される。
【００１４】
最小不具合率を有するセグメント保護の最適な組合せ(ＯＣＳＰ−ＭＦＰ：optimal combination of segment protections with minimum failure probability)と呼ばれる別の実施の形態では、最小同時不具合率を提供する最適ＬＳＰ保護が確定される。
【００１５】
信頼性が保証された最低コストを有するセグメント保護の最適な組合せ(ＯＣＳＰ−ＲＧＬＣ：optimal combination of segment protections with reliability-guaranteed and least-cost)と呼ばれる別の実施の形態では、最小コストでネットワーク信頼性要件を満たす最適ＬＳＰ保護が確定される。
【図面の簡単な説明】
【００１６】
【図１Ａ】光トランスポートネットワークのための従来のプロトコルスタックのブロック図である。
【図１Ｂ】この発明の実施の形態が動作するＭＰＬＳネットワークの概略図である。
【図２】全ての可能なセグメントバックアップトンネルが一次ＬＳＰに沿って付加された後のグラフである。
【図３】図２に基づくリンク重み割当て後のグラフである。
【図４】最小同時不具合率を提供するか、又は最小コストでネットワーク信頼性要件を満たすセグメント保護の最適な組合せを確定する一般的な方法の流れ図である。
【図５】グラフに対し起点から終点までＲＧＬＣプロセスを実行し、信頼性が保証された最低コストの保護を確定するため、および、グラフに対し起点から終点まで確率に関する(probability-wise)最短パス手順を実行し、最も信頼性の高い保護を確定するためのブロック図である。
【発明を実施するための形態】
【００１７】
この発明の実施の形態は、マルチプロトコルラベルスイッチング(ＭＰＬＳ)ネットワークにおいて不具合からデータ送信を保護するための方法を提供する。ＭＰＬＳネットワークにおいて、異なるユーザーの信頼性要件を差別化することができる。
【００１８】
図１Ｂは、幾つかの層を有するＭＰＬＳネットワークを示している。これらの層は、ＭＰＬＳルーター１１４と、光トランスポートネットワーク(ＯＴＮ)スイッチ１１５と、追加／廃棄マルチプレクサー(add/drop multiplexers：アド／ドロップマルチプレクサー)１１６と、波長ルーティングスイッチ１１７とを含む。
【００１９】
ＭＰＬＳネットワークにおける接続要求のパス計算を用いて、起点ノードと終点ノードとの間のＭＰＬＳ層におけるラベルスイッチパス(ＬＳＰ)１１２を確定する。
【００２０】
ＭＰＬＳオーバーＯＴＮオーバーＷＤＭ(MPLS-over-OTN-over-WDN)多層ネットワークでは、ＭＰＬＳリンク１１１は、光波長分割多重(ＷＤＭ)ネットワーク上で構築される光パス１１３のうちの１つ又はそれらの連結によって収容することができる。
【００２１】
光パスは基礎をなす物理トポロジにおいて１つ又は複数のファイバー１１８を通る場合があるので、ファイバーの何らかの不具合(ファイバーの切断等)がＭＰＬＳリンク上のデータ送信の不具合を引き起こし、ＬＳＰの信頼性を下げる場合がある。
【００２２】
本明細書において定義されるとき、「光パス」とは、１つ又は複数のファイバーリンク上を進む始点と終点との間の終端間接続である。単一のファイバー上に複数の光パスが存在することができる。光パスは、光クロスコネクト(例えば、波長ルーティングスイッチ)を通過することによって複数のファイバーをトラバースすることもできる。
【００２３】
用いられる確率的不具合モデルは、以下のように説明される。物理ファイバーネットワークはＧ＝(Ｖ，Ｅ)によって表され、ここで、Ｖはノードを表し、Ｅはノード間のエッジ(リンク)を表す。
【００２４】
Ｅにおける任意のリンクが、ｓ，ｔ∈Ｖの場合に(ｓ，ｔ)によって表される。１つ又は複数のファイバーを不具合にする可能性があるリスクイベントの集合Ｒが存在する。各リスクイベントｒ∈Ｒは確率πｒで発生し、確率的共有リスクリンクグループ(ＰＳＲＬＧ)と呼ばれる影響を受けるファイバーのグループと関連付けられる。リスクイベントｒが発生した後、ＳＲＬＧｒ内の物理リンク(ｓ，ｔ)は、条件付き不具合率
【００２５】
【数１】
2013214965.tif 000003
【００２６】
で不具合(ｆ)となる場合がある。
【００２７】
上位層におけるＭＰＬＳリンク(ｉ，ｊ)がファイバーの集合Ｓｆを物理的に通ると仮定すると、リスクｒの下でのＭＰＬＳリンク(ｉ，ｊ)の不具合率は以下の式となる。
【００２８】
【数２】
2013214965.tif 000004
【００２９】
リスクイベントは通常独立しているので、ＬＳＰ  Ｐのリスク加重不具合率は以下の式となる。
【００３０】
【数３】
2013214965.tif 000005
【００３１】
不具合は相互排他的であると仮定されるので、このパス不具合率は全てのリスクイベントにわたって平均化される。低い不具合率の仮定(すなわち、ｐｒｉｊ＜＜１，∀ｒ，∀(ｉ，ｊ))の下で妥当な近似を検討することができる。
【００３２】
二次以上の項ははるかに小さいので、以下の式が得られる。
【００３３】
【数４】
2013214965.tif 000006
【００３４】
このため、以下の式となり、
【００３５】
【数５】
2013214965.tif 000007
【００３６】
ここで、項
【００３７】
【数６】
2013214965.tif 000008
【００３８】
はＭＰＬＳリンク(ｉ，ｊ)に割り当てられたリスク加重不具合率である。
【００３９】
別の重みも各ＭＰＬＳリンクに割り当てられる。この別の重みは、選択されたＬＳＰがこのＭＰＬＳリンクを通る場合の、このリンク上のｃ(ｉ，ｊ)によって示される「コスト」を表す。ここで、「コスト」は、ネットワークについて柔軟に定義することができる。コストは、パスに沿った加法的な任意の所望のメトリック、例えばリソース消費、物理長、レイテンシ等とすることができる。
【００４０】
信頼性保証最低コスト(ＲＧＬＣ)パス計算方法のモデルは以下の式であり、
【００４１】
【数７】
2013214965.tif 000009
【００４２】
ここで、ｐｒｅｑはＬＳＰの要求される最大不具合率である。
【００４３】
図２においてノード１〜６について示すように、それぞれノード１及びノードｎとしてラベル付けされた起点２１０及び終点２６０が存在する。起点から中間ノードｊまでの最も信頼性のあるパスの加重不具合率をｇｊ(ｃ)によって示す。ここで、コストは最大でｃである。このとき、ＲＧＬＣパス計算の動的プログラミング手順は、ｊ＝２，…，ｎ、ｃ＝１，…，ＯＰＴについて以下の式となる。
【００４４】
【数８】
2013214965.tif 000010
【００４５】
ここで、ＯＰＴは、信頼性制約を満たす全ての１→ｎのパスのうちの最小コスト、すなわちＯＰＴ＝ｍｉｎ｛ｃ|ｇｎ(ｃ)≦ｐｒｅｑ｝である。
【００４６】
ＯＰＴは事前に知られておらず、このため、ｇｊ(ｃ)は、まずｃ＝１及びｊ＝２，…，ｎについて求められ、次にｃ＝２及びｊ＝２，…，ｎについて求められ、以下同様に、コストｃがｇｎ(ｃ)≦ｐｒｅｑを満たすまで求められる。次に、ＯＰＴはこのコストに設定される。
【００４７】
ＬＳＰ保護の場合において、最小同時不具合率又は最小保護コストを目標として、信頼性制約及び／又は回復時間制約の下で、保護領域及び対応するバックアップトンネルの最適な組合せを選択する一般的な方法を説明する。他の制約は、ホップカウント又はパスに沿った距離を含むことができる。
【００４８】
保護領域はＬＳＲの集合を含み、この集合にわたってＬＳＰ及びその対応する保護パスがルーティングされる。このため、保護領域は、ＭＰＬＳ保護のためのスイッチング機能及びマージ機能を提供するＬＳＲによって境界される。これらのノードはそれぞれＰＳＬ(保護スイッチラベルスイッチルーター、保護スイッチＬＳＲとも呼ばれる)及びＰＭＬ(保護マージラベルスイッチルーター、保護マージＬＳＲとも呼ばれる)であり、双方がＬＳＰ並びにその対応する機能中のパス及び保護パスの設定中に識別される。理想的には、保護は始点と終点との間(終端間)で実行されるべきであるが、場合によってはセグメント保護が望ましい。
【００４９】
図２に示すように、保護領域２３０はＰＳＬとＰＭＬとの間の一次ＬＳＰのセグメントである。
【００５０】
ＰＳＬ２１０は、一次セグメント及びその対応するバックアップトンネルの双方の起点であるＬＳＲである。不具合指示信号(ＦＩＳ)又はＰＳＬ自体の検出メカニズムを介してＰＳＬの保護領域において不具合が検出されると、ＰＳＬは保護されるべきデータ送信を、ＰＳＬから対応するバックアップトンネルにスイッチングする。
【００５１】
ＰＭＬ２２０は、一次セグメント及びその対応するバックアップトンネルの双方を終端するＬＳＲであり、データ送信を単一の発信ＬＳＰにマージするか、又はＰＭＬが終点である場合、データ送信を上位層プロトコルに渡す。この発明の実施の形態による保護方法を以下に説明する。
【００５２】
図３は、本明細書において説明するように、リンク重みｑの割当てを有する図２のネットワークを示している。
【００５３】
図４は、この発明の実施の形態による、最小同時不具合率を提供するか、又は最小コストでネットワーク信頼性要件を満たすセグメント保護の最適な組合せを確定するための一般的な方法を示している。
【００５４】
本方法のステップは、当該技術分野において既知のメモリ及び入出力インターフェースに接続されたプロセッサ４００において実行することができる。本方法は、ネットワークにわたって分散したプロセッサにおいて実行して信頼性を高めることもできる。
【００５５】
第１に、最大回復時間制約が存在する場合、回復時間は主にＦＩＳの送信時間で構成されるので、最大回復時間制約４１０は、潜在的な保護領域(物理層にマッピングされたときの物理長又はその保護領域内のリンク数によって測定される)の最大サイズに対する制約に変換される。
【００５６】
最大回復時間制約を満たす全ての保護領域が適格な保護領域となる。
【００５７】
第２に、一次ＬＳＰに基づいて、適格な保護領域からセグメント保護の最適な組合せを選択するのに役立つグラフが構築される(４２０)。
【００５８】
一次ＬＳＰに沿って、適格な保護領域ごとに、各バックアップトンネルが仮想リンクとしてグラフ内に挿入される(図２及び図３における破線の矢印、例えば保護領域２→５のバックアップトンネルとしての２４０)。
【００５９】
バックアップトンネルがルーティングされる場合のセグメント保護の最適な組合せを確定するための一般的な方法は制約されていない。バックアップトンネルは、既知の優先度又は方針に従って、例えばネットワークオペレーターが柔軟に選択することができる。
【００６０】
グラフの構築が完了すると、グラフ内の各リンクがリンク重みを割り当てられる。
【００６１】
次に、ステップ４３０において、リンクに沿ったデータ送信のための最小コストを求めることができる。
【００６２】
一方の重みは、コストが保護の目的で選択されるときのリンク上のコストである。他方の重みは不具合率に関するリンク重みである。
【００６３】
グラフ内の２つのタイプのリンクに２つの異なる割当て戦略が適用される。
【００６４】
特に、一次パス上のＭＰＬＳリンクの場合、これらのリンクの選択によって保護コストが増大しないのでコスト値はゼロに設定される。
【００６５】
これらのリンクの不具合率に関するリンク重みは、リスク加重不具合率のとおりに割り当てられ、すなわち、ＭＰＬＳリンク(ｉ，ｊ)の場合にｐｉｊである。
【００６６】
バックアップトンネルを表す仮想リンクの場合、コストはバックアップトンネルに沿って累積され、それらの不具合率に関するリンク重みは、バックアップトンネルのリスク加重同時不具合率として、そのバックアップトンネルが保護する対応する一次セグメントとともに割り当てられる。リスク加重同時不具合率の計算を以下に説明する。
【００６７】
リスクｒ∈Ｒの下でのノードｉからノードｋへの保護領域、つまりＰＤ［ｉ→ｋ］における一次セグメントの不具合率は、以下の式となる。
【００６８】
【数９】
2013214965.tif 000011
【００６９】
それに応じて、リスクｒの下でのバックアップトンネルの不具合率も上記と同じように評価され、ｂｒｉ→ｋによって表される。リスクｒ∈Ｒの下でのＰＤ［ｉ→ｋ］における一次セグメント及びそのバックアップトンネルの同時不具合率は、以下の式となる。
【００７０】
【数１０】
2013214965.tif 000012
【００７１】
ＰＤ［ｉ→ｋ］のリスク加重同時不具合率は以下の式となる。
【００７２】
【数１１】
2013214965.tif 000013
【００７３】
次に、Ｑｉ→ｋが、不具合率に関するリンク重みとして仮想バックアップトンネルｉ→ｋに割り当てられる。
【００７４】
図３に示すようなこのリンク重み割当ての後に、最小同時不具合率を提供するセグメント保護の最適な組合せ(ＯＣＳＰ−ＭＦＰ)を、グラフにおいてリンク重みを用いて起点から終点まで、当該技術分野において既知の最短パスプロセスを用いることによって確定することができる。
【００７５】
最小コストで要求される信頼性を満たすセグメント保護の最適な組合せ(ＯＣＳＰ−ＲＧＬＣ)は、上述したＲＧＬＣ法をグラフに適用することによって得ることができる。
【００７６】
図５は、２つの選択肢４３１及び４３２を示している。第１のものは、グラフに対し起点から終点までＲＧＬＣプロセスを実行して、信頼性が保証された最低コストの保護を確定する。第２のものは、グラフに対し起点から終点まで確率に関する最短パス手順を実行して、最も信頼性のある保護を確定する。これらの双方の選択肢は上記で説明されている。
【図１Ａ】
2013214965.tif 000017
【図１Ｂ】
2013214965.tif 000018
【図２】
2013214965.tif 000019
【図３】
2013214965.tif 000020
【図４】
2013214965.tif 000021
【図５】
2013214965.tif 000022
【外国語明細書】
2013214965.tif 000023
2013214965.tif 000024
2013214965.tif 000025
2013214965.tif 000026
2013214965.tif 000027
2013214965.tif 000028
2013214965.tif 000029
2013214965.tif 000030
2013214965.tif 000031
2013214965.tif 000032
2013214965.tif 000033
2013214965.tif 000034
2013214965.tif 000035
2013214965.tif 000036
2013214965.tif 000037
2013214965.tif 000038
2013214965.tif 000039
2013214965.tif 000040
2013214965.tif 000041
2013214965.tif 000042
2013214965.tif 000043
2013214965.tif 000044
2013214965.tif 000045