(57)【特許請求の範囲】
【請求項１】
ＬＤＰ（Label  Distribution  Protocol）を用いるＭＰＬＳ（Multiprotocol  Label  Switching）高速再ルーティングのための、第１のネットワークエレメントにおける方法であって、当該第１のネットワークエレメントは、ＭＰＬＳネットワークにおける複数のネットワークエレメントのうちの１つであり、当該方法は、
前記ＭＰＬＳネットワークにおける第２のネットワークエレメントから広告される第１のラベルを受信するステップと、
前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメントのうちの１つの障害である潜在的障害条件の下で宛先ネットワークエレメントに到達するための最短パスツリー（ＳＰＴ）である排除ＳＰＴを算出するステップと、前記第２のネットワークエレメントは、前記排除ＳＰＴにおける前記第１のネットワークエレメントのネクストホップであって、且つ、前記潜在的障害条件の前記障害から上流ではないことと、
前記潜在的障害条件が現実化した場合にバックアップとしての役割を果たすこととなるバックアップＬＤＰ  ＬＳＰ（Label  Switched  Path）についての第２のラベルを１つ以上の第３のネットワークエレメントのセットに広告することと、当該第３のネットワークエレメントのセットは、前記第１のネットワークエレメントを基準として、前記排除ＳＰＴ上で上流にあり且つ近隣のネットワークエレメントであることと、
前記潜在的障害条件の現実化に先立って、前記第２のラベルから前記第１のラベルへのスワップアクションをインストールすることと、
を含む、方法。
【請求項２】
前記第３のネットワークエレメントのセットのうちの１つから、前記第２のラベルを含むパケットを受信するステップと、
前記第２のラベルを前記第１のラベルとスワッピングするステップと、
前記第１のラベルと共に前記第２のネットワークエレメントに前記パケットを送信するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記第１のネットワークエレメントは、バックアップスイッチパスマージポイントである、請求項１に記載の方法。
【請求項４】
前記第２のネットワークエレメントは、前記潜在的障害条件を横切る現在の最短パスＬＳＰ上で前記第１のネットワークエレメントからの最初のホップである、請求項１に記載の方法。
【請求項５】
前記第２のネットワークエレメントから広告される前記第１のラベルは、前記潜在的障害条件に関わらず前記第２のネットワークエレメントにパケットを送信する際に前記第１のネットワークエレメントによって用いられる、請求項１に記載の方法。
【請求項６】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいてＬＤＰ（Label  Distribution  Protocol）を用いるＭＰＬＳ高速再ルーティングに参加するための第１のネットワークエレメントであって、
１つ以上のプロセッサのセットと、
ＬＤＰモジュールを含む制御プレーンと、
を備え、
当該制御プレーンは、前記プロセッサのセットによって実行される場合、当該プロセッサのセットに以下を実行させる、第１のネットワークエレメント：
前記ＭＰＬＳネットワークにおける第２のネットワークエレメントから広告される第１のラベルを受信することと、
前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメントのうちの１つの障害である潜在的障害条件の下で宛先ネットワークエレメントに到達するための最短パスツリー（ＳＰＴ）である排除ＳＰＴを算出することと、前記第２のネットワークエレメントは、前記排除ＳＰＴにおける前記第１のネットワークエレメントのネクストホップであって、且つ、前記潜在的障害条件の前記障害から上流ではないことと、
前記潜在的障害条件が現実化した場合にバックアップとしての役割を果たすこととなるバックアップＬＤＰ  ＬＳＰ（Label  Switched  Path）についての第２のラベルを１つ以上の第３のネットワークエレメントのセットに広告することと、当該第３のネットワークエレメントのセットは、前記第１のネットワークエレメントを基準として、前記排除ＳＰＴ上で上流にあり且つ近隣のネットワークエレメントであることと、
前記潜在的障害条件の現実化に先立って、前記第１のネットワークエレメントのデータプレーンにおける１つ以上の転送構造に前記第２のラベルから前記第１のラベルへのスワップアクションをインストールすること。
【請求項７】
前記データプレーン、
をさらに含み、
当該データプレーンは、前記プロセッサのセットによって実行される場合、当該プロセッサのセットに以下をさらに実行させる、請求項６に記載のネットワークエレメント：
前記第３のネットワークエレメントのセットのうちの１つから、前記第２のラベルを含むパケットを受信することと、
前記１つ以上の転送構造を用いて前記第２のラベルを前記第１のラベルとスワッピングすることと、
前記第１のラベルと共に前記第２のネットワークエレメントに前記パケットを送信すること。
【請求項８】
前記第１のネットワークエレメントは、バックアップスイッチパスマージポイントである、請求項６に記載のネットワークエレメント。
【請求項９】
前記第２のネットワークエレメントは、前記潜在的障害条件を横切る現在の最短パスＬＳＰ上で前記第１のネットワークエレメントからの最初のホップである、請求項６に記載のネットワークエレメント。
【請求項１０】
前記第２のネットワークエレメントから広告される前記第１のラベルは、前記潜在的障害条件に関わらず前記第２のネットワークエレメントにパケットを送信する際に前記第１のネットワークエレメントによって用いられる、請求項６に記載のネットワークエレメント。
【請求項１１】
ＬＤＰ（Label  Distribution  Protocol）を用いるＭＰＬＳ（Multiprotocol  Label  Switching）高速再ルーティングのための、第１のネットワークエレメントにおける方法であって、当該第１のネットワークエレメントは、ＭＰＬＳネットワークにおける複数のネットワークエレメントのうちの１つであり、当該方法は、
前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメントのうちの１つの障害である潜在的障害条件の下で宛先ネットワークエレメントに到達するための最短パスツリー（ＳＰＴ）である排除ＳＰＴを算出するステップと、
前記潜在的障害条件が現実化した場合にバックアップとしての役割を果たすこととなるバックアップＬＤＰ  ＬＳＰ（Label  Switched  Path）についてのラベルを第２のネットワークエレメントから受信するステップと、当該第２のネットワークエレメントは、前記第１のネットワークエレメントを基準として、前記排除ＳＰＴ上で上流にあり且つ近隣のネットワークエレメントであることと、
前記潜在的障害条件の現実化に先立って前記潜在的障害条件についての障害トリガアクションをインストールして、受信される前記ラベルを、前記潜在的障害条件が現実化した場合にトラフィックを前記第２のネットワークエレメントに送るために使用されるようにすることと、
を含む、方法。
【請求項１２】
前記潜在的障害条件に相当する障害条件を検出するステップと、
前記検出するステップに応じて、前記バックアップＬＤＰ  ＬＳＰについての受信される前記ラベルを用いて、前記第２のネットワークエレメントから受信され及び前記宛先ネットワークエレメントを宛先とするトラフィックを前記第２のネットワークエレメントに再ルーティングするステップと、
をさらに含む、請求項１１に記載の方法。
【請求項１３】
前記第１のネットワークエレメントは、ＰＬＲ（Point  of  Local  Repair）である、請求項１１に記載の方法。
【請求項１４】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいてＬＤＰ（Label  Distribution  Protocol）を用いるＭＰＬＳ高速再ルーティングに参加するための第１のネットワークエレメントであって、
１つ以上のプロセッサのセットと、
ＬＤＰモジュールを含む制御プレーンと、
を備え、
前記制御プレーンは、前記プロセッサのセットによって実行される場合、当該プロセッサのセットに以下を実行させる、第１のネットワークエレメント：
前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメントのうちの１つの障害である潜在的障害条件の下で宛先ネットワークエレメントに到達するための最短パスツリー（ＳＰＴ）である排除ＳＰＴを算出することと、
前記潜在的障害条件が現実化した場合にバックアップとしての役割を果たすこととなるバックアップＬＤＰ  ＬＳＰ（Label  Switched  Path）についてのラベルを第２のネットワークエレメントから受信することと、当該第２のネットワークエレメントは、前記第１のネットワークエレメントを基準として、前記排除ＳＰＴ上で上流にあり且つ近隣のネットワークエレメントであることと、
前記潜在的障害条件の現実化に先立って前記第１のネットワークエレメントのデータプレーンにおける１つ以上の転送構造のセットに前記潜在的障害条件についての障害トリガアクションをインストールして、受信される前記ラベルを、前記潜在的障害条件が現実化した場合にトラフィックを前記第２のネットワークエレメントに送るために使用されるようにすること。
【請求項１５】
前記データプレーン、
をさらに含み、
当該データプレーンは、前記プロセッサのセットによって実行される場合、当該プロセッサのセットに以下をさらに実行させる、請求項１４に記載のネットワークエレメント：
前記潜在的障害条件に相当する障害条件の検出に応じて、前記バックアップＬＤＰ  ＬＳＰについての受信される前記ラベルを用いて、前記第２のネットワークエレメントから受信されるトラフィックを当該第２のネットワークエレメントに再ルーティングすること。
【請求項１６】
前記第１のネットワークエレメントは、ＰＬＲ（Point  of  Local  Repair）である、請求項１４に記載のネットワークエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への参照
本願は、２０１１年３月６日に出願された米国仮出願第６１／４４９，６９６号及び２０１１年２月２８日に出願された米国仮出願第６１／４４７，６７１号の利益を主張し、これらの出願は、参照によって本明細書に包含される。
【０００２】
本発明の実施形態は、ネットワーキングの分野に関し、特に、ＭＰＬＳ（MultiProtocol  Label  Switching）高速再ルーティングに関する。
【背景技術】
【０００３】
最小限の損失でトラフィックを回復することは、キャリアクラスネットワークにおける基本的な要件である。高速再ルーティング（ＦＲＲ：Fast-Reroute）は、ネットワークにおける障害条件下で最小限の損失でトラフィックを回復するための技法である。
【０００４】
ＲＦＣ５０３６において定義されるＬＤＰ（Label  Distribution  Protocol：ラベル配布プロトコル）は、（ＲＦＣ３０３１及びＲＦＣ３０３２において定義される）ＭＰＬＳ実装においてラベルスイッチパス（ＬＳＰ：Label  Switched  Paths）をセットアップするために広く展開されるプロトコルである。ＬＤＰは、（例えば、ＲＦＣ２３２８において定義される）ＩＧＰ（Interior  Gateway  Protocol：内部ゲートウェイプロトコル）によってセットアップされるルーティングされるパスに沿ってＬＳＰを確立する。従って、障害条件下でＬＤＰを用いて確立されるＬＳＰの収束は、ＩＧＰの収束を要する。
【０００５】
ＲＳＶＰ−ＴＥ（Resource  Reservation  Protocol−Traffic  Engineering：リソース予約プロトコル−トラフィックエンジニアリング）ベースのＦＲＲは、標準化され（ＲＦＣ４０９０）及び幾つかのベンダプラットフォームにおいて実装されている。幾つかの事業者及びベンダは、ＲＳＶＰ−ＴＥを用いることによってＬＤＰの高速収束に対処しようと試みている。この機能は、典型的に、ＬＤＰ−ｏｖｅｒ−ＲＳＶＰと呼ばれる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＬＤＰはＩＧＰによってセットアップされるルーティングされるパスに従うため、ＬＤＰの収束はＩＰＧ収束を要する。しかしながら、ＩＧＰの収束は、伝統的に遅い。この問題の詳しい説明は、ＲＦＣ５７１４のセクション４に存在する。例えば、そのような理由は、以下を含む：障害を検出するために要する時間、ローカルルータが障害に反応するための時間、障害に関する情報をネットワーク中の他のルータに送信するための時間、転送テーブルを再計算するための時間、及び再計算された転送テーブルを転送ハードウェアにダウンロードするための時間。幾つかのアプローチはＦＲＲをＩＧＰに導入してＩＧＰの収束を改善しようと試みてきたが、当該アプローチの各々は、幾つかの問題によって悩まされてきた。例えば、draft-ietf-rtgwg-ipfrr-notvia-addresses-0Xなどの、この問題を解決するためのアプローチは、配備及び実装上の複雑さを有し、それ故に、採用されていない。（ＲＦＣ５２８６において定義される）Loop  Free  Alternatesなどのアプローチは、完全なカバレッジを有さず、それ故に、キャリアは、それらを配備する際に予約をする。
【０００７】
ＬＤＰ  ＬＳＰについてＦＲＲを提供するための別のアプローチは、ＲＳＶＰ−ＴＥを障害バイパスメカニズムとして用いることである（ＬＤＰ−ｏｖｅｒ−ＲＳＶＰ）。しかしながら、ＲＳＶＰ−ＴＥなどの付加的な、かなり複雑なプロトコルが用いられると、事業費の増加につながるため、広範囲にわたる設定及び保守経験要件を含む幾つかの理由に起因して、キャリアによるＲＳＶＰ−ＴＥの配備は遅々としていた。ＬＤＰ−ｏｖｅｒ−ＲＳＶＰは、多くの実装において利用可能ではないかもしれない、ＲＳＶＰ−ＴＥにおける（高い可用性及び信頼性などの）多くの特徴をベンダがサポートすることも必要とする。
【課題を解決するための手段】
【０００８】
ＬＤＰを用いるＭＰＬＳ高速再ルーティングが説明される。潜在的障害条件の下で宛先ネットワークエレメントに到達するためのＬＤＰ  ＬＳＰが算出される。当該算出されるＬＤＰ  ＬＳＰは、算出されるＬＤＰ  ＬＳＰに沿った第１のネットワークエレメントであって、且つ現在の最短パスＬＤＰ  ＬＳＰへのネクストホップを有する複数のネットワークエレメントのうちの当該１つにおいて、現在の最短パスＬＤＰ  ＬＳＰと統合される。
【０００９】
一実施形態において、ＭＰＬＳネットワークにおける第１のネットワークエレメントは、当該ＭＰＬＳネットワークにおける第２のネットワークエレメントから広告される第１のラベルを受信する。第１のネットワークエレメントは、潜在的障害条件の下で宛先ネットワークエレメントに到達するための最短パスツリー（ＳＰＴ）を算出する。第２のネットワークエレメントは、算出されるＳＰＴにおける第１のネットワークエレメントのネクストホップであって、且つ、潜在的障害条件から上流ではない。第１のネットワークエレメントは、潜在的障害条件が現実化した場合にバックアップとしての役割を果たすバックアップＬＤＰ  ＬＳＰについての第２のラベルを１つ以上の第３のネットワークエレメントに広告する。第３のネットワークエレメントは、第１のネットワークエレメントを基準として、算出されるＳＰＴ上の上流のネイバーである。第１のネットワークエレメントは、第２のラベルから第１のラベルへのスワップアクションをインストールする。この実施形態において、第１のネットワークエレメントは、バックアップスイッチパスマージポイントである。
【００１０】
一実施形態において、ＭＰＬＳネットワークにおける第１のネットワークエレメントは、潜在的障害条件の下で宛先ネットワークエレメントに到達するためのＳＰＴを算出する。第１のネットワークエレメントは、潜在的障害条件が現実化した場合にバックアップとしての役割を果たすバックアップＬＤＰ  ＬＳＰについてのラベルを第２のネットワークエレメントから受信する。第２のネットワークエレメントは、第１のネットワークエレメントを基準として、算出されるＳＰＴ上の上流のネイバーである。第１のネットワークエレメントは、障害を迂回してトラフィックを再ルーティングするために、潜在的障害条件についての障害トリガアクションをインストールする。障害トリガアクションは、受信される上記ラベルを、潜在的障害条件が現実化した場合に第２のネットワークエレメントにトラフィックを送る際に用いられるようにする。潜在的障害条件に相当する障害条件を検出することに応じて、第２のネットワークエレメントから受信される宛先ネットワークエレメントに向けてのトラフィックは、バックアップＬＤＰ  ＬＳＰについての受信されるラベルを用いて第２のネットワークエレメントに再ルーティングされる。この実施形態において、第１のネットワークエレメントは、ＰＬＲ（Point  of  Local  Repair）である。
【図面の簡単な説明】
【００１１】
本発明は、本発明の実施形態を例示するために用いられる添付の図面及び以下の説明を参照することによって最もよく理解され得る。図面において：
【００１２】
【図１】一実施形態に係る、ＬＤＰ−ＦＲＲを用いる例示的なＭＰＬＳネットワークを示す。
【図２】一実施形態に係る、リンクの潜在的障害を越えて所与の宛先ネットワークエレメントに到達するためのＢＳＰ  ＬＳＰをネットワークエレメントが設定する、図１のネットワークを示す。
【図３】一実施形態に係る、単一のリンク障害についてのＬＤＰ−ＦＲＲを設定する例示的な動作を示すフロー図である。
【図４】一実施形態に係る、ネットワークエレメントの潜在的障害を越えて所与の宛先ネットワークエレメントに到達するためのＢＳＰ  ＬＳＰをネットワークエレメントが設定する、図１のネットワークを示す。
【図５】一実施形態に係る、単一のノード障害についてＬＤＰ−ＦＲＲを設定するための例示的な動作を示すフロー図である。
【図６】一実施形態に係る、ＬＤＰ  ＦＲＲを実装する例示的なネットワークエレメントを示す。
【発明を実施するための形態】
【００１３】
以下の説明において、多くの具体的な詳細が述べられる。しかしながら、本発明の実施形態はこれらの具体的な詳細無しに実施をされ得ることが理解される。他の例において、周知の回路、構造及び技法は、本説明の理解を曖昧にしないために詳細には示されていない。当業者は、含まれた説明により、過度の実験無しに適当な機能性を実装することが可能であろう。
【００１４】
本明細書における「一実施形態」、「ある実施形態」、「例示的な実施形態」等への言及は、説明される実施形態が特定の機能、構造、又は特性を有し得るが、全ての実施形態が必ずしも当該特定の機能、構造、又は特性を有しなくてもよいことを示す。また、そのような表現は、必ずしも同じ実施形態に言及しない。さらに、特定の機能、構造、又は特性がある実施形態に関連して説明される場合、明示的に説明されていてもいなくても、そのような機能、構造、又は特性を他の実施形態に関連して達成することは当業者の知識の範囲内であることが提示される。
【００１５】
以下の説明及び特許請求の範囲において、「結合される（coupled）」及び「接続される（connected）」という用語は、それらの派生語と共に用いられ得る。これらの用語は互いに同義語として意図されないことが理解されるべきである。「結合される」は、直接物理的に又は電気的に互いに接触し得る２つ以上のエレメントが互いに協働し又はインタラクションすることを示すために用いられる。「接続される」は、互いに結合される2つ以上のエレメントの間における通信の確立を示すために用いられる。
【００１６】
本発明の一実施形態において、ＬＤＰ  ＬＳＰについての高速再ルーティングは、ＩＧＰの高速収束、ＩＰ−ＦＲＲ、又はＲＳＶＰ−ＴＥベースのＦＲＲに依存することなく提供される。ＬＤＰは現行の広い採用をもたらした非常に単純で簡単な設定手続きを有するため、本発明の実施形態を採用する実装は、単純な設定モデルを維持することができる。大抵の状況において、キャリアは、本発明の実施形態の実装のためにいかなる運用手続きをも変更する必要がないであろう。従って、本発明の実施形態は、ＬＤＰを運用することの単純さを維持し、並びにあらゆる異常シナリオをカバーしつつＩＰ−ＦＲＲ及びＬＤＰ−ｏｖｅｒ−ＲＳＶＰの複雑さを克服する。
【００１７】
一実施形態において、ネットワークエレメントは、潜在的障害条件の下で宛先に到達するためのＬＳＰを算出する。このＬＳＰは、統合が可能なパスに沿った第１のノードにおいて現在の最短パスＬＳＰと統合される。これは、必要とされる余分なラベルの数を最小化し、及びＩＧＰが再収束する際にトラフィックの攪乱（churn）が存在しないことも確実にする。
【００１８】
以下の専門用語は、本発明の実施形態を説明するために用いられる。ＰＬＲ（Point  of  Local  Repair）は、バックアップスイッチパス（ＢＳＰ：backup-switched  path）ＬＳＰのヘッドエンドＬＳＲ（ラベルスイッチルータ）である。ＰＬＲは、障害を検出し、及び代替的なルート（ＢＳＰ  ＬＳＰ）上でトラフィックを送ることによってリンク又はノードの当該障害を修復するノードである。ＢＳＰ  ＬＳＰは、最短パスＬＤＰ  ＬＳＰ上の特定の障害エンティティについてバックアップを提供するＬＤＰ  ＬＳＰである。障害エンティティは、リンク、ノード、又はＳＲＬＧであり得る。ＢＳＰ  ＬＳＰは、ＰＬＲを起点とする。バックアップスイッチパスマージポイント（ＢＳＰ−ＭＰ）は、ＢＳＰ  ＬＳＰが最短パスＬＤＰ  ＬＳＰについて割り当てられるラベルにラベルスイッチングされるＬＳＲである。ＢＳＰ−ＭＰは、潜在的障害の下流にある必要はない。排除ＳＰＴ（exclude  Shortest  Path  Tree）は、特定の障害ポイントがネットワークから排除される場合の、ＰＬＲからＦＥＣ（Forwarding  Equivalence  Class）への最短パスツリーである。
【００１９】
ＦＥＣに向かう最短パスツリー上の所与の障害ポイントについて、当該障害ポイントの上流のＬＳＲは、当該ＬＳＲが障害ポイントのＰＬＲからの当該ＦＥＣについての排除ＳＰＴ上にあり、且つ当該ＬＳＲが障害ポイントを横切らない、当該ＦＥＣへの最短パスＬＤＰ  ＬＳＰ上に所属する場合、ＢＳＰ−ＭＰとして動作し、及びＢＳＰ  ＬＳＰについてのラベル（当該ＬＳＰは障害が発生しない限りたどられないため、本明細書において代替ラベルと呼ばれる）を広告する。ＢＳＰ−ＭＰは、排除ＳＰＴに沿ってＢＳＰ  ＬＳＰについての代替ラベルを広告する。
【００２０】
ＰＬＲからＢＳＰ−ＭＰへの最短パスが排除ＳＰＴに含まれない場合、中間ＬＳＲの各々は、ＢＳＰ  ＬＳＰについての代替ラベルを割り当て、及びそれらの転送構造（例えは、それらのＩＬＭ（Incoming  Label  Map））にラベルスワップ動作をインストールする。
【００２１】
ＰＬＲは、障害の発生時にＬＳＰが当該ＦＥＣについてのＢＳＰ  ＬＳＰにスイッチングされるように障害アクションをインストールする。一実施形態において、リンク障害よりもノード障害が優先される。ＢＳＰ  ＬＳＰが障害のために当該ＦＥＣについて利用可能ではないが、ネクストホップ又はネクストネクストホップへのＢＳＰ  ＬＳＰは利用可能である場合、それは、対応するラベルをラベルスタックにプッシュすることによって用いられる。
【００２２】
一実施形態において、ある障害の後、当該障害以前のトポロジーに対応するＢＳＰ  ＬＳＰは、短い遅延の後に除去されるべきである。
【００２３】
図１は、一実施形態に係る、ＬＤＰ−ＦＲＲを用いる例示的なＭＰＬＳネットワークを示す。図１に示されるネットワークは、ネットワークエレメント１１０Ａ〜Ｇを含む。ネットワークエレメントの各々は、ＬＳＲとして動作する。ネットワークエレメント１１０Ａは、ネットワークエレメント１１０Ｂ、１１０Ｄ、及び１１０Ｅにそれぞれリンク１２２、１２１、及び１２０上で結合される。ネットワークエレメント１１０Ｂは、ネットワークエレメント１１０Ｃにリンク１２３上でさらに結合される。ネットワークエレメント１１０Ｃは、ネットワークエレメント１１０Ｆにリンク１２４上でさらに結合される。ネットワークエレメント１１０Ｆは、ネットワークエレメント１１０Ｅ及び１１０Ｇにそれぞれリンク１２５及び１２７上でさらに結合される。リンク１２１、１２２、１２３、１２４、及び１２５の各々は、コスト１を有する。リンク１２０は、コスト５を有し、リンク１２６は、コスト３を有する。
【００２４】
図１は、ネットワークエレメント間で確立された複数のＬＳＰセグメントを示す。一実施形態において、ＬＳＰセグメントは、ＬＤＰを用いて確立されている。例えば、ネットワークエレメント１１０Ａは、ＬＳＰセグメント１３１を確立することの一部としてネットワークエレメント１１０ＤにラベルＬ４を広告する。ネットワークエレメント１１０Ｂは、ＬＳＰセグメント１３９を確立することの一部としてネットワークエレメント１１０ＡにラベルＬ３を広告する。ネットワークエレメント１１０Ｃは、ＬＳＰセグメント１３８を確立することの一部としてネットワークエレメント１１０ＢにラベルＬ２を広告する。ネットワークエレメント１１０Ｆは、ＬＳＰセグメント１３７を確立することの一部としてネットワークエレメント１１０ＣにラベルＬ１を広告し、及びＬＳＰセグメント１３４を確立することの一部としてネットワークエレメント１１０ＥにラベルＬ６を広告する。ネットワークエレメント１１０Ｇは、ＬＳＰセグメント１３６を確立することの一部としてネットワークエレメント１１０ＦにラベルＬ８を広告し、及びＬＳＰセグメント１３５を確立することの一部としてネットワークエレメント１１０ＥにラベルＬ７を広告する。ネットワークエレメント１１０Ｅは、ＬＳＰセグメント１３３を確立することの一部としてネットワークエレメント１１０にラベルＬ５を広告する。ネットワークエレメント１１０Ｆは、ＬＳＰセグメント１３４を確立することの一部としてネットワークエレメント１１０ＥにラベルＬ６を広告する。
【００２５】
図１は、最短パスツリーも示す。例えば、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｇへのトラフィックは、以下のパスをたどる：１１０Ｄ→１１０Ａ→１１０Ｂ→１１０Ｃ→１１０Ｆ→１１０Ｇ。ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｇへのトラフィックは、リンク１２０のコスト（当該コストは５である）が当該リンク１２０をより望ましくないパスにするため、ネットワークエレメント１１０Ｅを介して伝わらない。従って、リンク１２０及びＬＳＰセグメント１３３は、ネットワークエレメント１１０ＧへのＳＰＴの一部ではないため、破線で示されている。リンク１２６及びＬＳＰセグメント１３５も、ネットワークエレメント１１Ｅからネットワークエレメント１１０ＧへのＳＰＴの一部ではないため、破線で示される。
【００２６】
ネットワークエレメントは、ラベルスイッチングを実行するための転送構造を備える。例えば、ネットワークエレメント１１０Ａは、ネットワークエレメント１１０ＤからラベルＬ４を有するパケットを受信する場合に当該ラベルＬ４をラベルＬ３とスワッピングし及び当該パケットをネットワークエレメント１１０Ｂに送信すべきであることを特定する転送構造を備える。一実施形態において、転送構造は、ＩＬＭ（インカミングラベルマップ）データ構造及びＮＨＬＦＥ（next  hop  label  forwarding  entry：ネクストホップラベル転送エントリ）データ構造を含む。
【００２７】
一実施形態において、図１に示されるネットワークエレメントは、複数の潜在的障害についてのＢＳＰ  ＬＳＰを当該障害が発生する場合に備えて計算する。代替パスについて生成されるＢＳＰ  ＬＳＰの数は、幾つかの通常のＬＳＰセグメント（非障害シナリオについて確立されるＬＳＰセグメント）が用いられることができるため最小限に抑えられる。例えば、特定の障害についてのＢＳＰ−ＭＰとして動作するネットワークエレメントは、ＢＳＰ−ＬＳＰを確立されたＬＳＰと統合して、障害を迂回して再ルーティングすることができる。
【００２８】
以下の専門用語は、ＬＤＰ  ＦＲＲを確立するためにネットワークエレメントによって実行される動作を説明するために用いられる。
【００２９】
１．有向グラフは、Ｇによって表される。ノードは、Ｓ、Ｄ、Ｎ、Ｍ、Ｏ、及びＰによって表される。リンクは、Ｌ、Ｋ、Ｊ、及びＩによって表される。
２．Ｇにおける全てのリンクは、コスト＞０を有する。
３．Ｎｏｄｅ（Ｇ，Ｄ）は、グラフＧにおけるノードＤを表す。
４．ＳＰＴは、（例えば、ダイクストラアルゴリズム（Dijkstra's  algorithm）によって計算されるような）最短パスツリーを表す。
５．ＳＰＴ（Ｇ，Ｓ）は、（グラフＧにおける）ノードＳからＧにおける全ての他のノードへのＳＰＴを表す。なお、ＳＰＴ（Ｇ，Ｄ）は、有向非巡回グラフ（ＤＡＧ：directed  acyclic  graph）であり、当然ながら、グラフである。
６．ｐａｉｒＳＰＴ（Ｇ，Ｓ，Ｄ）は、ＧにおけるＳからＤへのノードのペア間のＳＰＴを表す。
７．ｐａｉｒＳＰＴ（Ｇ，Ｓ，Ｄ，Ｄ１，Ｄ２，．．．）は、ＳからＤ、Ｄ１、Ｄ２、．．．のいずれかに到達する最短パスを表す。
８．ｔｏＳＰＴ（Ｇ，Ｄ）は、グラフＧにおける他のノード全てからＧにおけるノードＤへの（例えば、ダイクストラアルゴリズムによって計算されるような）最短パスツリーである。なお、ｔｏＳＰＴ（Ｇ，Ｄ）も、ＳＰＴ（Ｇ，Ｓ）に類似したＤＡＧであり、当然ながら、グラフである。
９．Ｌｉｎｋ（Ｇ，Ｌ）は、グラフＧにおける有向リンクＬを表す。
１０．ＵｐＮｏｄｅ（Ｇ，Ｌ）は、リンクＬの上流端にある、グラフＧにおけるノードを表す。
１１．ＤｎＮｏｄｅ（Ｇ，Ｌ）は、Ｌの下流端にある、グラフＧにおけるノードを表す。
１２．なお、ＵｐＮｏｄｅ（ｔｏＳＰＴ（Ｇ，Ｄ），Ｌ）は、代替ルート上でトラフィックを送ることによってＬにおける異常を修復するであろうノードとなる。これは、典型的に、Ｌにおける異常を修復するためのＰＬＲと呼ばれる。また、ＤｎＮｏｄｅ（ｔｏＳＰＴ（Ｇ，Ｄ），Ｌ）は、直接接続されるＬＤＰピアについてリンク保護がＰＬＲによって為され、ラベルスタッキングが用いられる場合にトラフィックが再統合（merge  back）するノードであろうということにも留意されたい。
１３．ｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）は、ｔｏＳＰＴ（Ｇ，Ｄ）におけるＬの上流にある全てのノードと、これらのノード間の全てのリンクと、から成る、Ｇのサブツリーを表す。ＬがｔｏＳＰＴ（Ｇ，Ｄ）に所属しない場合、それはＮＵＬＬグラフである。なお、ｕｐｓｔｒはグラフであるが、必ずしもＤＡＧとは限らない。
１４．Ｇ−Ｌは、リンクＬを有しないグラフＧを表す。
１５．Ｇ−Ｆは、グラフＧのサブセットを表す。ここで、Ｆは、Ｇからのリンク及びノード（これらに付属するリンクを有する）のセットである。Ｆは、Ｇから除去されて、Ｇ−Ｆが与えられる。
【００３０】
連結グラフＧにおいて、ｔｏＳＰＴ（Ｇ，Ｄ）における任意のリンクＬについて（即ち、任意のＤについて）、ＵｐＮｏｄｅ（Ｌ）からＧ−ＬにおけるＤへのパスが存在する場合、ｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）内ではないがＧ内のノードへのＬ以外のリンクを有する、ｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）におけるノードが存在する。そのようなノードが存在しない場合、リンクＬは、グラフＧのカットエッジであり、ＵｐＮｏｄｅ（Ｇ，Ｌ）からＧ−ＬにおけるＤへのパスは無い。目標は、代替パスについて生成される新たなＬＳＰに番号を付けることであり、ＬＤＰのルーティングの原理を最短パスに沿わせることである。
【００３１】
一実施形態において、ネットワークエレメント１１０Ａ〜Ｇの各々は、以下を実行して、単一リンク障害の場合におけるＬＤＰ  ＬＳＰについての高速ルーティングを確立する。
【００３２】
１．ＧにおけるあらゆるＤについて、以下を実行
ａ．ｔｏＳＰＴ（Ｇ，Ｄ）を算出
ｂ．ｔｏＳＰＴ（Ｇ，Ｄ）におけるあらゆるリンクＬについて、以下を実行：
ｉ．ｔｏＳＰＴ（Ｇ−Ｌ，Ｄ）を算出
ｉｉ．ノードがｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）内にあり、ｐａｉｒＳＰＴ（Ｇ−Ｌ，ＵｐＮｏｄｅ（Ｇ，Ｄ，Ｌ），Ｄ）に所属する場合、ｐａｉｒＳＰＴにおける上流のネイバーに（代替ラベル又はＡＬと呼ばれる）Ｄについてのラベルを割り当てる（及び配信する）。ＩＬＭ（インカミングラベルマップ）エントリを以下のようにセットアップ：
１．このノードが上記のｕｐｓｔｒ内ではない上記のｐａｉｒＳＰＴ内のネクストホップを有する場合、当該ノードは、割り当てられたＡＬについてのピアから受信されるラベルへのスワップアクションをインストールする
２．さもなければ、当該ノードは、当該ノードが割り当てたＡＬからｐａｉｒＳＰＴ内の下流のＬＤＰピアから受信されるＡＬへのスワップアクションを割り当てる
３．ＰＬＲであるＵｐＮｏｄｅ（Ｇ，Ｄ，Ｌ）は、Ｌについての障害トリガアクションをインストールし、ここで、リンクＬが障害を起こす場合、ＤｎＮｏｄｅ（Ｇ，Ｄ，Ｌ）によって割り当てられるラベルを用いる代わりに、ＡＬを使用し及びＩＬＭによって示されるようにパケットを転送する。
４．ＡＬがＤについては受信されないが、ＤｎＮｏｄｅ（Ｇ，Ｄ，Ｌ）のループバックアドレスについて受信されている場合、障害アクションをセットアップして、当該ラベルをスタッキングし及びそれに応じてパケットを転送する。
【００３３】
単一リンク障害に関する上述された手続きについての複雑さは、Ｏ（Ｎ＾４）であるが、Ｏ（Ｎ＾３）において為されることができると考えられる。
【００３４】
図２は、リンク１２４の潜在的障害を越えて宛先ネットワークエレメント１１０Ｇに到達するためのＢＳＰ  ＬＳＰをネットワークエレメントが設定する、図１のネットワークを示す。図２は、図３に関して説明されることとなり、図３は、一実施形態に係る、ＬＤＰ  ＦＲＲを設定するための例示的な動作を示すフロー図である。一実施形態において、ネットワークエレメント１１０Ａ〜Ｇの各々は、図３において説明される動作を実行する。
【００３５】
動作３１０において、ノードのうちの１つ（ネットワークエレメント１１０Ａ〜Ｇのうちの１つ）が選択される。図２に関して、選択ノードは、ネットワークエレメント１１０Ｇである。フローは動作３１５に移り、ネットワークにおける他のノード全てから、選択ノード１１０までのＳＰＴが算出される。フローは動作３２０に移り、算出されたＳＰＴから除外すべきリンクが選択される。図２に関して、選択された除外すべきリンクは、リンク１２４である。フローは動作３２５に移り、選択リンクを除外した状態で、選択ノードまでのＳＰＴが算出される。従って、選択ノードまでのＳＰＴは、選択リンクがネットワークの一部ではないと仮定して算出される。
【００３６】
フローは動作３３０に移り、算出を実行するネットワークエレメントが選択リンクの上流にあり、且つ、選択リンクを除外した状態でＰＬＲから選択ノードまでのＳＰＴに所属するか判定が為される。選択リンクを排除した状態における、ＰＬＲから選択ノードまでのＳＰＴは、図３の動作に関して本明細書において排除ＳＰＴ（exclude-SPT）と呼ばれる。
【００３７】
図２に関して、ＰＬＲは、ネットワークエレメント１１０Ｃである。選択リンクの上流のノードは、ネットワークエレメント１１０Ａ、１１０Ｂ、及び１１０Ｃを含む。排除ＳＰＴに所属するノードは、ネットワークエレメント１１０Ａ及び１１０Ｂである（ネットワークエレメント１１０Ｄは、排除ＳＰＴの一部ではない）。算出を実行するネットワークエレメントが、選択リンクの上流にあり、且つ、選択リンクが排除された状態の、ＰＬＲから第２のノードまでのＳＰＴに所属する場合、フローは動作３３５に移る；さもなければ、フローは動作３５０に移る。
【００３８】
動作３３５において、算出を実行するネットワークエレメントは、選択ノードまでのＢＳＰ−ＬＳＰについてのラベルを排除ＳＰＴにおける上流のネイバーに（例えば、ＬＤＰを用いて）割り当て及び配信する。例えば、図２に関して、ネットワークエレメント１１０Ａは、ＢＳＰ−ＬＳＰセグメント２４０を確立することの一部としてネットワークエレメント１１０Ｂに代替ラベルＡＬ１を割り当て及び配信し、ネットワークエレメント１１０Ｂは、ＢＳＰ−ＬＳＰセグメント２１４を確立することの一部としてネットワークエレメント１１０Ｃに代替ラベルＡＬ２を割り当て及び配信する。フローは、動作３４０に移る。
【００３９】
動作３４０において、動作を実行しているネットワークエレメントが、選択リンク（排除されたリンク）から上流ではない、排除ＳＰＴにおけるネクストホップを有する場合、フローは動作３４５に移り（当該ネットワークエレメントはマージポイントである）、さもなければ、フローは動作３６０に移る。別の言い方をすれば、ネットワークエレメントが排除ＳＰＴ上にあり、且つ、障害ポイントを横切らない、選択ノードまでの最短パスＬＤＰ  ＬＳＰ上に属する場合、当該ネットワークエレメントは、マージポイントであり、フローは動作３４５に移るであろう。図２に関して、ネットワークエレメント１１０Ａは、リンク１２４から上流ではない、排除ＳＰＴにおけるネクストホップを有する（当該ネクストホップは、ネットワークエレメント１１０Ｅである）。
【００４０】
動作３４５において、ネットワークエレメントは、当該ネットワークエレメントが割り当て及び配信した代替ラベルについての、そのネクストホップのネットワークエレメントから受信されるラベルへのスワップアクションをインストールする。例えば、図２に関して、ネットワークエレメント１１０Ａは、代替ラベルＡＬ１についてネットワークエレメント１１０Ｅから過去に受信されたラベルＬ５へのスワップアクションをインストールする。従って、この例においてＢＳＰ−ＭＰとして動作しているネットワークエレメント１１０Ｅは、リンク１２４の障害を迂回して再ルーティングするために確立されつつあるＢＳＰ−ＬＳＰを現在の最短パスＬＳＰと統合する。これは、必要とされる余分な代替ラベルの数を最小化し、及びＩＧＰが再収束する際にトラフィックの攪乱が存在しないことも確実にする。フローは、動作３４５から動作３６５に移る。
【００４１】
動作３５０において、動作を実行しているネットワークエレメントがＰＬＲである場合、フローは動作３５５に移り、さもなければ、フローは動作３６５に移る。動作３５５において、ネットワークエレメントは、（排除される）選択リンクについての障害トリガアクションをインストールして、上流のネイバーから受信した代替ラベルが用いられるようにする。例えば、図２に関して、ＰＬＲとして動作しているネットワークエレメント１１０Ｃは、障害トリガアクションをインストールし、それによって、リンク１２４の障害発生時、ネットワークエレメント１１０Ｃは、（例えば、その転送構造における１つ以上のエントリを変更することによって）ネットワークエレメント１１０Ｂからラベル２を有する到来するトラフィックがＢＳＰ  ＬＳＰセグメント２４１に沿って送られるようにするであろう。一実施形態において、ＢＳＰ  ＬＳＰに沿ってトラフィックが送られるようにすることによって障害発生時にアクションを取る必要があるのは、ＰＬＲのみである。フローは、動作３５５から動作３６５に移る。
【００４２】
動作３６０において、ネットワークエレメントはＢＳＰ−ＭＰではないが、選択リンクの上流であり且つ排除ＳＰＴに所属するため、当該ネットワークエレメントは、排除ＳＰＴに沿った中間ノードであり、それ故に、当該ネットワークエレメントがＢＳＰ−ＬＳＰについて割り当て及び配信した代替ラベルから排除ＳＰＴにおける下流のＬＤＰピアから受信されるＢＳＰ−ＬＳＰについての代替ラベルへのスワップアクションをインストールする。例えば、図２に関して、ネットワークエレメント１１０Ｂは、当該ネットワークエレメント１１０Ｂがネットワークエレメント１１０Ｃに割り当て及び配信した代替ラベルＡＬ２から当該ネットワークエレメント１１０Ｂがネットワークエレメント１１０Ａから受信した代替ラベルＡＬ１へのスワップアクションをインストールする。フローは、動作３６０から動作３６５に移る。
【００４３】
動作３６５において、選択ノードまでの算出されたＳＰＴにおいて別のリンクが存在するかが判定される。別のリンクが存在する場合、フローは動作３２０に戻り、別のリンクは、算出されたＳＰＴから排除されるように選択される。別のリンクが存在しない場合、フローは動作３７０に移り、別のノードがネットワーク中に存在するかが判定される。別のノードがネットワーク中に存在する場合、フローは動作３１０に戻り、別のノードが選択される。別のノードが存在しない場合、フローは動作３７５に移り、処理は終了する。
【００４４】
一実施形態において、代替ラベルは、選択ノードではなく、選択リンクの下流端にあるノードのループバックアドレスへ配信される。例えば、図２に関して、代替ラベルは、選択リンクの下流端にあるネットワークエレメント１１０Ｆに配信され得る。そのような状況において、障害アクションがセットアップされて、当該ラベルがスタッキングされ及びそれに応じてパケットが転送される。
【００４５】
一実施形態において、ネットワークエレメントは、ノード障害の場合におけるＬＤＰ  ＬＳＰについての高速再ルーティングを以下のように実行する：
ノード障害の場合：
１．ＧにおけるあらゆるＤについて、以下を実行：
ａ．ｔｏＳＰＴ（Ｇ，Ｄ）を算出
ｂ．Ｆは、ＧにおけるあるノードＭをそのすべてのリンクと共に表すものとする。Ｍ１、Ｍ２、．．．Ｍｎは、ｔｏＳＰＴ（Ｇ，Ｄ）においてＭの上流にある直接接続されるノードを表すものとする。Ｎ１、Ｎ２、．．．Ｎｎは、ｔｏＳＰＴ（Ｇ，Ｄ）においてＭの下流にある直接接続されるノードを表すものとする。そのようなあらゆるＦについて、以下を実行：
ｉ．ｔｏＳＰＴ（Ｇ−Ｆ，Ｄ）を算出
ｉｉ．ノードがｕｐｓｔｒ（Ｇ，Ｄ，Ｆ）内にあり、且つ任意のｉ（１，．．，ｎ）についてｐａｉｒＳＰＴ（Ｇ−Ｆ，Ｍｉ，Ｄ）に所属する場合、ｐａｉｒＳＰＴにおける上流のネイバーに（代替ラベル又はＡＬと呼ばれる）Ｄについてのラベルを割り当てる（及び配信する）。ＩＬＭエントリを以下のようにセットアップ：
１．このノードが上記のｕｐｓｔｒ内ではない、上記のｐａｉｒＳＰＴにおいてネクストホップを有する場合、当該ノードは、割り当てられたＡＬについて、ピアから受信されるラベルへのスワップアクションをインストールする。
２．さもなければ、当該ノードは、当該ノードが割り当てたＡＬからｐａｉｒＳＰＴにおける下流のＬＤＰピアから受信されたＡＬへのスワップアクションを割り当てる
３．ＰＬＲであるＵｐＮｏｄｅ（Ｇ，Ｄ，Ｆ）は、Ｌについての障害トリガアクションをインストールする。ここで、リンクＬが障害を起こす場合、ＤｎＮｏｄｅ（Ｇ，Ｄ，Ｌ）によって割り当てられるラベルを用いる代わりに、当該ノードは、ＡＬを使用し及びＩＬＭによって示されるようにパケットを転送する。
４．ＡＬがＤについて受信されていないが、ネクストネクストホップのＬＳＲのループバックアドレスのうちのいずれかについて受信されている場合（ネクストネクストホップはｔｏＳＰＴから推定されることができる）、ラベルをネクストネクストホップによって割り当てられるものとスワッピングし（これについてのシグナリング拡張は、後で定義される）、及びネクストネクストホップについてのＡＬをスタッキングする。
【００４６】
図４は、ネットワークエレメント１１０Ｆの潜在的障害を越えて宛先ネットワークエレメント１１０Ｇに到達するためのＢＳＰ  ＬＳＰをネットワークエレメントが設定する、図１のネットワークを示す。図４は、図５に関して説明されるであろう。図５は、一実施形態に係る、単一ノードの障害の場合においてＬＤＰ  ＦＲＲを設定するための例示的な動作を示すフロー図である。一実施形態において、ネットワークエレメント１１０Ａ〜Ｇの各々は、図５において説明される動作を実行する。
【００４７】
動作５１０において、ノードのうちの１つ（ネットワークエレメント１１０Ａ〜Ｇのうちの１つ）が選択される。図４に関して、選択ノードは、ネットワークエレメント１１０Ｇである。フローは動作５１５に移り、ネットワークにおける他のノード全てから、選択ノード１１０ＧまでのＳＰＴが算出される。フローは動作５２０に移り、算出されたＳＰＴから排除すべきノードが選択される。図４に関して、選択される排除すべきノードは、ネットワークエレメント１１０Ｆであり、当該ネットワークエレメント１１０Ｆは、本明細書において排除ノード（exclude-node）と呼ばれる。フローは動作５２５に移り、排除ノードが排除された状態で、選択ノードまでのＳＰＴが算出される。従って、排除ノードはネットワークの一部ではないと仮定して、選択ノードまでのＳＰＴが算出される。
【００４８】
フローは動作５３０に移り、算出を実行するネットワークエレメントが排除ノードの上流にあり、且つ、排除ノードが排除された状態で、上流のノードから選択ノードまでのＳＰＴに所属するかの判定が為される。排除ノードが排除された状態における、上流のノードから選択ノードまでのＳＰＴは、本明細書において図５に関して排除ＳＰＴと呼ばれる。図４に関して、上流のノードは、ネットワークエレメント１１０Ｃである。算出を実行するネットワークエレメントがそのようなノードである場合、フローは動作５３５に移る；さもなければ、フローは動作５５０に移る。
【００４９】
動作５３５において、算出を実行するネットワークエレメントは、選択ノードまでのＢＳＰ−ＬＳＰについてのラベルを排除ＳＰＴにおける上流のネイバーに（例えば、ＬＤＰを用いて）割り当て及び配信する。例えば、図４に関して、ネットワークエレメント１１０Ａは、ＢＳＰ−ＬＳＰセグメント４４０を確立することの一部としてネットワークエレメント１１０Ｂに代替ラベルＡＬ１を割り当て及び配信し、ネットワークエレメント１１０Ｂは、ＢＳＰ−ＬＳＰセグメント４４１を確立することの一部としてネットワークエレメント１１０Ｃに代替ラベルＡＬ２を割り当て及び配信する。フローは動作５４０に移る。
【００５０】
動作５４０において、動作を実行しているネットワークエレメントが排除ノードから上流ではない、排除ＳＰＴにおけるネクストホップを有する場合、フローは動作５４５に移り（当該ネットワークエレメントは、マージポイントである）、さもなければ、フローは動作５６０に移る。別の言い方をすれば、ネットワークエレメントが排除ＳＰＴ上にあり、且つ、障害ポイントを横切らない、選択ノードまでの最短パスＬＤＰ  ＬＳＰ上に所属する場合、当該ネットワークエレメントはマージポイントであり、フローは動作５４５に移るであろう。図４に関して、ネットワークエレメント１１０Ａは、ネットワークエレメント１１０Ｆから上流ではない、排除ＳＰＴにおけるネクストホップ（これは、ネットワークエレメント１１０Ｅである）を有する。
【００５１】
動作５４５において、ネットワークエレメントは、当該ネットワークエレメントが割り当て及び配信した代替ラベルについての、当該ネクストホップのネットワークエレメントから受信されるラベルへのスワップアクションをインストールする。例えば、図４に関して、ネットワークエレメント１１０Ａは、代替ラベルＡＬ１についてネットワークエレメント１１０Ｅから過去に受信されたラベルＬ５へのスワップアクションをインストールする。従って、この例においてＢＳＰ−ＭＰとして動作しているネットワークエレメント１１０Ｅは、ノードＦの障害を迂回して再ルーティングするために確立されつつあるＢＳＰ−ＬＳＰを現在の最短パスＬＳＰと統合する。これは、必要とされる余分な代替ラベルの数を最小化し、ＩＧＰが再収束する際にトラフィックの攪乱が存在しないことも確実にする。フローは、動作５４５から動作５６５に移る。
【００５２】
動作５５０において、動作を実行しているネットワークエレメントがＰＬＲである場合、フローは動作５５５に移り、さもなければ、フローは動作５６５に移る。動作５５５において、ネットワークエレメントは、選択ノードについての障害トリガアクションをインストールして、当該ネットワークエレメントが上流のネイバーから受信した代替ラベルが用いられるようにする。例えば、図４に関して、ＰＬＲとして動作しているネットワークエレメント１１０Ｃは、障害トリガアクションをインストールし、それによって、ノード１１０Ｆの障害発生時、ネットワークエレメント１１０Ｃは、（例えば、その転送構造における１つ以上のエントリを変更することによって）ネットワークエレメント１１０ＢからラベルＬ２を有する到来するトラフィックがＢＳＰ  ＬＳＰセグメント４４１に沿って送られるようにする。一実施形態において、ＰＬＲのみが、ＢＳＰ  ＬＳＰに沿ってトラフィックが送られるようにすることによって障害発生時にアクションを取る必要がある。フローは、動作５５５から動作５６５に移る。
【００５３】
動作５６０において、ネットワークエレメントはＢＳＰ−ＭＰではないが、選択ノードの上流にあり且つ排除ＳＰＴに所属するため、当該ネットワークエレメントは、排除ＳＰＴに沿った中間ノードであり、それ故に、当該ネットワークエレメントがＢＳＰ−ＬＳＰについて割り当て及び配信した代替ラベルから排除ＳＰＴにおける下流のＬＤＰピアから受信されるＢＳＰ−ＬＳＰについての代替ラベルへのスワップアクションをインストールする。例えば、図４に関して、ネットワークエレメント１１０Ｂは、当該ネットワークエレメント１１０Ｂがネットワークエレメント１１０Ｃに割り当て及び配信した代替ラベルＡＬ２から当該ネットワークエレメント１１０Ｂがネットワークエレメント１１０Ａから受信した代替ラベルＡ１へのスワップアクションをインストールする。フローは、動作５６０から動作５６５に移る。
【００５４】
動作５６５において、選択ノードまでの算出されたＳＰＴ中に潜在的に障害を起こし得る別のノードが存在するかが判定される。そのようなノードが存在する場合、フローは動作５２０に戻り、算出されたＳＰＴから排除されるべき別のノードが選択される。別のノードが存在しない場合、フローは動作５７０に移り、別の宛先ノードがネットワーク中に存在するかが判定される。別の宛先ノードがネットワーク中に存在する場合、フローは動作５１０に戻り、別のノードが選択される。別の宛先ノードが存在しない場合、フローは動作５７５に移り、処理は終了する。
【００５５】
一実施形態において、代替ラベルは、選択される宛先ノードではなく、ネクストネクストホップのＬＳＲのうちのいずれかのループバックアドレスに配信される。そのような状況において、当該ネクストネクストホップによって割り当てられるラベルは、スワッピングされ、当該ネクストネクストホップについての代替ラベルは、スタッキングされる。
【００５６】
一実施形態において、ＳＲＬＧ（Shared  Risk  Link  Group：共有リスクリンクグループ）の障害は、ノード障害と同様の手法で対処される。
【００５７】
幾つかの状況において、障害を起こした特定のＳＲＬＧを推測することができない関係を有する複数のＳＲＬＧにリンクが所属し、その上、代替パスは存在するが算出されない複雑な場合があり得る。このような複雑な場合は、上記の説明によって対処されない。
【００５８】
幾つかの状況において、ヘテロジニアスネットワークが存在する可能性があり、そこでは様々なＬＳＲが様々なラベル転送テーブルのキャパシティの限界を有し得る。そのような状況において、幾つかのＬＳＲがこれらの手続きのために必要とされる余分なラベル（ＡＬ）に適応するための充分なラベル転送エントリを有しないことがあり得る。この場合において、ＡＬは、ループバックアドレスにのみ割り当てられ、ラベルスタッキングは、ネクストホップへのパケットをラベルスイッチングするために用いられる。
【００５９】
ＬＳＰセットアップモード
１．全てのノードが算出を実行し、ラベルを割り当てる、下流未要求型（downstream-unsolicited）。
２．ＰＬＲは、代替ＬＳＰ（Ａｌｔ−ＬＳＰ）の算出を実行し、明示的なパスを介してＬＳＰをシグナリングする。上流オンデマンドモード。
【００６０】
一実施形態において、ＬＤＰ  ＦＲＲを確立するために、シグナリングの拡張が定義される。シグナリング拡張は、ＢＳＰ  ＬＳＰがセットアップされることを必要とすること、及び当該ＢＳＰ  ＬＳＰは特定の障害が生じた場合のためのものであることを、ＢＳＰ−ＭＰがＰＬＲにシグナリングすることを可能にする。従って、シグナリング拡張は、バックアップＬＳＰがセットアップされるべきノードを識別し、及び当該バックアップＬＳＰがセットアップされる対象の障害を識別する。
【００６１】
例えば、以下のシグナリング拡張は、ＬＤＰ  ＦＲＲを確立するために定義される：
１．新たなＴＬＶが定義される（パスベクターＴＬＶと共に有効化されなければならない）。この新たなＴＬＶは、パスベクターＴＬＶがパスと共にＬＳＲのＩｄを記録するのと同様の手法でＬＳＰについてのラベルを記録する。新たなＴＬＶは、「ラベルベクターＴＬＶ（Label  Vector  TLV）」と呼ばれ得る。
２．（リンク（ｐ２ｐ及びマルチアクセス）及びノードをカバーする）プレフィックスのリスト並びにＳＲＬＧを含む新たな随意的なＴＬＶ。この新たな随意的なＴＬＶは、ラベルマップ及びラベル要求メッセージにおいて用いられる。新たな随意的なＴＬＶは、「トポロジー排除ＴＬＶ（Topology  Exclude  TLV）」と呼ばれ得る。
【００６２】
本明細書において説明されるＬＤＰ  ＦＲＲの実施形態を採用する実装は、ＬＤＰの単純な設定モデルを保持することができる。従って、本発明の実施形態は、ＬＤＰを運用することの単純さを保持し、並びにあらゆる異常シナリオをカバーしつつ、ＩＰ−ＦＲＲ及びＬＤＰ−ｏｖｅｒ−ＲＳＶＰの複雑さを克服する。
【００６３】
図６は、一実施形態に係る、ＬＤＰ  ＦＲＲを実装する例示的なネットワークエレメントを示す。ネットワークエレメント６００は、制御プレーン６１０と、（転送プレーン又はメディアプレーンと呼ばれることもある）データプレーン６５０と、を備える。制御プレーン６１０は、どのようにデータ（例えば、パケット）がルーティングされるか（例えば、当該データについてのネクストホップ及び当該データについてのアウトゴーイングポート）を判定し、データプレーン６５０は、当該データを転送することを担う。制御プレーン６１０は、ＩＧＰモジュール６１５と、ＬＤＰモジュール６２０と、を含む。ＩＧＰモジュール６１５は、ＯＳＰＦ（Open  Shortest  Path  First）又はＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）などのリンク状態プロトコルを実行中であるか、又はＲＩＰ（Routing  Information  Protocol）などの別のプロトコルを実行中であり得る。ＩＧＰモジュール６１５は、他のネットワークエレメントと通信して、ルートを交換し及び１つ以上のルーティングメトリックに基づいて当該ルートを選択する。選択されるＩＧＰルートは、ＲＩＢ（Routing  Information  Base：ルーティング情報ベース）６２５に記憶される。ＩＧＰモジュール６１５は、選択されず及びＲＩＢ６２５に記憶されるルートエントリがローカルＲＩＢ（例えば、ＩＧＰローカルＲＩＢ）に記憶されるようにすることもできる。
【００６４】
ＬＤＰモジュール６２０は、そのピア（ＬＤＰピア）とラベルマッピング情報を交換する。例えば、ＬＤＰモジュール６２０は、ラベルマッピングメッセージを生成し及び当該ＬＤＰモジュール６２０のピアからラベルマッピングメッセージを受信し得る。ＬＤＰモジュール６２０は、ラベルパケットを転送するために、ＩＧＰモジュール６１５によってＲＩＢ６２５に提供される基礎となる（underlying）ルーティング情報に依存する。ＬＤＰモジュール６２０は、ラベルを割り当て、及びラベルパケットを転送することに関連する他の情報（例えば、ＮＨＬＦＥ情報、ＩＬＭ情報、ＦＴＮ情報）をＭＰＬＳ情報ベース６３０に記憶する。ＬＤＰモジュール６２０は、本明細書において説明されるＬＤＰ−ＦＲＲ処理をサポートするようにＬＤＰモジュール６２０の機能性を拡張するＬＤＰ−ＦＲＲモジュール６２２を含む。一実施形態において、ＬＤＰ−ＦＲＲモジュール６２２は、図３及び／又は図５において説明される動作を実行する。
【００６５】
制御プレーン６１０は、ＲＩＢ６２５及びＭＰＬＳ情報ベース６３０に基づくルート情報を用いてデータプレーン６５０をプログラミングする。具体的には、ＲＩＢ６２５からのある情報は、ＦＩＢ（Forwarding  Information  Base：転送情報ベース）６５５にプログラミングされ、ＭＰＬＳ情報ベース６３０からのある情報は、ＩＬＭ構造６６０、ＮＨＬＦＥ構造６６５、及びＦＴＮ構造６７０にプログラミングされる。例えば、障害が発生する場合にＢＳＰ  ＬＳＰに応じてトラフィックが迅速に（例えば、ラインレートで）再ルーティングされることができるように、ＢＳＰ  ＬＳＰについての代替ラベルは、データプレーン６５０のＩＬＭ構造６６０及びＮＨＬＦＥ構造６６５のうちの１つ以上に必要に応じてプログラミングされる。
【００６６】
一実施形態において、ネットワークエレメント６００は、（転送カードと呼ばれることもある）１つ以上のラインカードのセットと、１つ以上の制御カードのセットと、を含む。ラインカード及び制御カードのセットは、１つ以上のメカニズム（例えば、ラインカードを結合する第１のフルメッシュ及び全てのカードを結合する第２のフルメッシュ）を通じて互いに結合される。ラインカードのセットは、典型的に、データプレーンを構成し、各々が、パケットを転送する際に用いられることとなるＦＩＢ６５５、ＩＬＭ６６０、ＮＨＬＦＥ６６５、及びＦＴＮ６７０を記憶し得る。具体的には、ＦＴＮ６７０は、ラベルが付けられていないが転送前にラベルが付けられるべきであるパケット（例えば、当該パケットは、入口ＬＳＲにおいてＭＰＬＳドメイン外から受信される）を転送するために用いられる。ＩＬＭ６６０は、ラベルが付けられたパケットを転送するために用いられる。制御カードは、典型的に、ＩＧＰモジュール６１５、ＬＤＰモジュール６２０を含むルーティングプロトコルを実行し、並びにＲＩＢ６２５及びＭＰＬＳ情報ベース６３０を記憶する。
【００６７】
本明細書において、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジ）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、端局）と通信可能に相互接続する、ハードウェア及びソフトウェアを含むネットワーキング機器である。幾つかのネットワークエレメントは、複数のネットワーキング機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２アグリゲーション、セッションボーダコントロール、サービス品質、及び／若しくは加入者管理）のためのサポートを提供し、並びに／又は、複数のアプリケーションサービス（例えば、データ、音声、及びビデオ）のためのサポートを提供する「マルチサービスネットワークエレメント（multiple  services  network  elements）」である。加入者端局（Subscriber  end  stations）（例えば、サーバ、ワークステーション、ラップトップ、ネットブック、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、ＶＯＩＰ（Voice  Over  Internet  Protocol）電話）、ユーザ機器、端末、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲーム機、セットトップボックス）は、インターネット上で提供されるコンテンツ／サービス、及び／又はインターネット上に重ねられる（例えば、インターネットを通じてトンネリングされる）バーチャルプライベートネットワーク（ＶＰＮ）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的に、サービスプロバイダ又はコンテンツプロバイダに属する１つ以上の終端局（例えば、サーバ端局（server  end  stations））又はピアツーピアサービスに参加する終端局によって提供され、公開ウェブページ（例えば、フリーコンテンツ、ストアフロント、検索サービス）、プライベートなウェブページ（例えば、ユーザ名／パスワードによってアクセスされる、電子メールサービスを提供するウェブページ）、及び／又はＶＰＮ上の企業ネットワークを含み得る。典型的に、加入者終端局は、エッジネットワークエレメントに（例えば、（有線又は無線で）アクセスネットワークに結合される顧客構内の機器を介して）結合される。当該エッジネットワークエレメントは、（例えば、１つ以上のコアネットワークエレメントを介して）他のエッジネットワークエレメントに結合される。当該他のエッジネットワークエレメントは、他の終端局（例えば、サーバ端局）に結合される。
【００６８】
本明細書において説明されるように、命令は、ある動作を実行するように構成され、又は所定の機能性若しくは非一時的なコンピュータ読取可能な媒体において具現化されるメモリに記憶されるソフトウェア命令を有する特定用途向け集積回路（ＡＳＩＣ：application  specific  integrated  circuits）などのハードウェアの特定の設定を指し得る。従って、図面に示される技法は、１つ以上の電子デバイス（例えば、端局、ネットワークエレメント）上に記憶され及び実行されるコード及びデータを用いて実装されることができる。そのような電子デバイスは、非一時的なコンピュータ読取可能な記憶媒体（例えば、磁気ディスク、光ディスク、ＲＡＭ、ＲＯＭ、フラッシュメモリデバイス、相変化メモリ）及び一時的なコンピュータ読取可能な通信媒体（例えば、搬送波、赤外線信号、デジタル信号といった、電気的、光学的、音響的な形態又は他の形態の伝搬信号）といったコンピュータ読取可能な媒体を用いて、コード及びデータを記憶し並びに（内部的に及び／又はネットワーク上で他の電子デバイスと）通信する。また、そのような電子デバイスは、典型的に、１つ以上のストレージデバイス（非一時的な機械読取可能な記憶媒体）、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、及び／又はディスプレイ）、並びにネットワーク接続といった１つ以上の他のコンポーネントに結合される１つ以上のプロセッサを含む。プロセッサのセットと他のコンポーネントとの結合は、典型的に、１つ以上のバス及び（バスコントローラとも称される）ブリッジを介する。従って、所与の電子デバイスのストレージデバイスは、典型的に、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明のある実施形態の１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの様々な組み合わせを用いて実装され得る。
【００６９】
本発明は幾つかの実施形態の観点から説明されたが、本発明が説明された実施形態に限定されず、添付の特許請求の範囲の思想及び範囲内における変更及び変形と共に実施をされ得ることを当業者は認識するであろう。従って、説明は、限定ではなく例示としてみなされるべきである。
【図１】
0005934724.tif 000002
【図２】
0005934724.tif 000003
【図３】
0005934724.tif 000004
【図４】
0005934724.tif 000005
【図５】
0005934724.tif 000006
【図６】
0005934724.tif 000007