(57)【特許請求の範囲】
【請求項１】
ＬＤＰ（Label  Distribution  Protocol）を用いたマルチプロトコルラベルスイッチング（ＭＰＬＳ）の高速再ルーティングのための第１のネットワークエレメントにおける方法であって、前記第１のネットワークエレメントは、ＭＰＬＳネットワーク内の複数のネットワークエレメントの１つであり、
前記ＭＰＬＳネットワーク内の第２のネットワークエレメントから広告される第１のラベルを受信するステップと、
潜在的な障害条件下で宛て先ネットワークエレメントへ到達するための最短パスツリー（ＳＰＴ）を計算するステップと、
前記第２のネットワークエレメントは、計算される前記ＳＰＴにおいて前記第１のネットワークエレメントのネクストホップであり、且つ計算される前記ＳＰＴにおいて前記潜在的な障害条件の障害位置から上流にはないことと、
前記潜在的な障害条件が現実化した場合に前記複数のネットワークエレメントの第３のネットワークエレメントがローカルリペア点（ＰＬＲ）であることを判定するステップと、
前記潜在的な障害条件が現実化した場合にバックアップパスとしてサービスすることとなるバックアップＬＤＰラベルスイッチパス（ＬＳＰ）のために、第２のラベルを前記第３のネットワークエレメントへ配布するステップと、
前記第２のラベルから前記第１のラベルへのスワップアクションをインストールするステップと、
を含む方法。
【請求項２】
前記第２のラベルを含むパケットを受信するステップと、
前記第２のラベルを前記第１のラベルとスワップするステップと、
前記第２のネットワークエレメントへ前記第１のラベルと共に前記パケットを送信するステップと、
をさらに含む、請求項１の方法。
【請求項３】
前記潜在的な障害条件は、前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメント、のうち１つの障害である、請求項１の方法。
【請求項４】
前記第１のネットワークエレメントは、バックアップ最短パスマージ点である、請求項１の方法。
【請求項５】
前記第２のネットワークエレメントは、前記潜在的な障害条件を横断するその時点の最短パスＬＳＰ上の、前記第１のネットワークエレメントからの最初のホップである、請求項１の方法。
【請求項６】
前記第２のネットワークエレメントから広告される前記第１のラベルは、将来的な前記障害条件に関わらず、前記第２のネットワークエレメントへパケットを送信する際に前記第１のネットワークエレメントによって使用される、請求項１の方法。
【請求項７】
ＬＤＰ（Label  Distribution  Protocol）を用いたマルチプロトコルラベルスイッチング（ＭＰＬＳ）の高速再ルーティングのための第１のネットワークエレメントにおける方法であって、前記第１のネットワークエレメントは、ＭＰＬＳネットワーク内の複数のネットワークエレメントの１つであり、
潜在的な障害条件下で宛て先ネットワークエレメントへ到達するための最短パスツリー（ＳＰＴ）を計算するステップと、
前記潜在的な障害条件が現実化した場合に、バックアップとしてサービスすることとなる現存するラベルスイッチパス（ＬＳＰ）のための、第２のネットワークエレメントにより割当てられるラベルを受信するステップと、
前記潜在的な障害条件が現実化した場合に、後続して前記第１のネットワークエレメントにおいて受信される、前記宛て先ネットワークエレメントを宛て先とするパケットが、前記現存するＬＳＰを用いて前記第２のネットワークエレメントに向けて再ルーティングされ、当該現存するＬＳＰを前記第２のネットワークエレメントから前記宛て先ネットワークエレメントへの最短パスＬＤＰ  ＬＳＰにマージすべき旨の前記第２のネットワークエレメントへの標識を含むように、前記第１のネットワークエレメントの転送ステートを構成するステップと、
前記第２のネットワークエレメントは、前記宛て先ネットワークエレメントへの前記最短パスＬＤＰ  ＬＳＰ上にネクストホップを有する、計算された前記ＳＰＴ上の上流ネットワークエレメントであることと、
を含み、
前記第１のネットワークエレメントの前記転送ステートを構成することは、前記潜在的な障害条件が現実化した場合に使用されるべき障害トリガアクションであって、前記第２のネットワークエレメントにより割当てられる前記ラベルを、前記宛て先ネットワークエレメントを宛て先とするパケットのラベルスタック内に、非障害条件の間に前記第２のネットワークエレメントに到達するために使用されるラベルの下方に含めるための当該障害トリガアクションをインストールすること、を含む、
方法。
【請求項８】
前記潜在的な障害条件に対応する障害条件を検出するステップと、
検出する前記ステップに応じて、前記障害条件を回避するために、前記宛て先ネットワークエレメントをを宛て先とするパケットを前記第２のネットワークエレメントへ再ルーティングするステップと、
をさらに含み、
前記パケットの再ルーティングは、各パケットについて、
前記現存するＬＳＰのために、前記第２のネットワークエレメントから受信される前記ラベルを、前記パケットのラベルスタックへプッシュすることと、
前記第２のネットワークエレメントへ到達するために使用される前記ラベルを、前記パケットの前記ラベルスタックへプッシュすることと、
ラベリングされた前記パケットを前記第２のネットワークエレメントに向けて送信することと、
を含む、請求項７の方法。
【請求項９】
前記潜在的な障害条件は、前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメント、のうち１つの障害である、請求項７の方法。
【請求項１０】
前記第１のネットワークエレメントは、ローカルリペア点である、請求項７の方法。
【請求項１１】
ＬＤＰ（Label  Distribution  Protocol）を用いたマルチプロトコルラベルスイッチング（ＭＰＬＳ）の高速再ルーティングに参加するための、ＭＰＬＳネットワーク内の複数のネットワークエレメントのうちの第１のネットワークエレメントであるネットワークエレメントであって、
１つ以上のプロセッサのセットと、
当該ネットワークエレメントの制御プレーン内のＬＤＰモジュールを記憶する非一時的なコンピュータ読取可能な媒体と、
を備え、
前記ＬＤＰモジュールは、前記プロセッサのセットにより実行された場合に、
前記ＭＰＬＳネットワーク内の第２のネットワークエレメントから広告される第１のラベルを受信することと、
潜在的な障害条件下で宛て先ネットワークエレメントへ到達するための最短パスツリー（ＳＰＴ）を計算することと、ここで前記第２のネットワークエレメントは計算される当該ＳＰＴにおいて前記第１のネットワークエレメントのネクストホップであり且つ計算される当該ＳＰＴにおいて前記潜在的な障害条件の障害位置から上流にはなく、
前記潜在的な障害条件が現実化した場合に前記複数のネットワークエレメントの第３のネットワークエレメントがローカルリペア点（ＰＬＲ）であることを判定することと、
前記潜在的な障害条件が現実化した場合にバックアップパスとしてサービスすることとなるバックアップＬＤＰラベルスイッチパス（ＬＳＰ）のために、第２のラベルを前記第３のネットワークエレメントへ配布することと、
前記第２のラベルから前記第１のラベルへのスワップアクションを、前記第１のネットワークエレメントのデータプレーン内の１つ以上の転送構造内にインストールすることと、
を前記プロセッサのセットに実行させる、
ネットワークエレメント。
【請求項１２】
前記データプレーンをさらに備え、
前記データプレーンは、前記プロセッサのセットにより実行された場合に、
前記第２のラベルを含むパケットを受信することと、
前記１つ以上の転送構造を用いて、前記第２のラベルを前記第１のラベルとスワップすることと、
前記第２のネットワークエレメントへ前記第１のラベルと共に前記パケットを送信することと、
を前記プロセッサのセットにさらに実行させる、
請求項１１のネットワークエレメント。
【請求項１３】
前記潜在的な障害条件は、前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメント、のうち１つの障害である、請求項１１のネットワークエレメント。
【請求項１４】
前記第１のネットワークエレメントは、バックアップ最短パスマージ点である、請求項１１のネットワークエレメント。
【請求項１５】
前記第２のネットワークエレメントは、前記潜在的な障害条件を横断するその時点の最短パスＬＳＰ上の、前記第１のネットワークエレメントからの最初のホップである、請求項１１のネットワークエレメント。
【請求項１６】
前記第２のネットワークエレメントから広告される前記第１のラベルは、将来的な前記障害条件に関わらず、前記第２のネットワークエレメントへパケットを送信する際に前記第１のネットワークエレメントによって使用される、請求項１１のネットワークエレメント。
【請求項１７】
ＬＤＰ（Label  Distribution  Protocol）を用いたマルチプロトコルラベルスイッチング（ＭＰＬＳ）の高速再ルーティングに参加するための、ＭＰＬＳネットワーク内の複数のネットワークエレメントのうちの第１のネットワークエレメントであるネットワークエレメントであって、
１つ以上のプロセッサのセットと、
当該ネットワークエレメントの制御プレーン内のＬＤＰモジュールを記憶する非一時的なコンピュータ読取可能な媒体と、
を備え、
前記ＬＤＰモジュールは、前記プロセッサのセットにより実行された場合に、
潜在的な障害条件下で宛て先ネットワークエレメントへ到達するための最短パスツリー（ＳＰＴ）を計算することと、
前記潜在的な障害条件が現実化した場合に、バックアップとしてサービスすることとなる現存するラベルスイッチパス（ＬＳＰ）のための、第２のネットワークエレメントにより割当てられるラベルを受信することと、
前記潜在的な障害条件が現実化した場合に、後続して前記第１のネットワークエレメントにおいて受信される、前記宛て先ネットワークエレメントを宛て先とするパケットが、前記現存するＬＳＰを用いて前記第２のネットワークエレメントに向けて再ルーティングされ、当該現存するＬＳＰを前記第２のネットワークエレメントから前記宛て先ネットワークエレメントへの最短パスＬＤＰ  ＬＳＰにマージすべき旨の前記第２のネットワークエレメントへの標識を含むように、前記第１のネットワークエレメントのデータプレーンの転送ステートを構成することと、
を前記プロセッサのセットに実行させ、
前記第２のネットワークエレメントは、前記宛て先ネットワークエレメントへの前記最短パスＬＤＰ  ＬＳＰ上にネクストホップを有する、計算された前記ＳＰＴ上の上流ネットワークエレメントであり、
前記第１のネットワークエレメントの前記転送ステートの構成は、前記潜在的な障害条件が現実化した場合に使用されるべき障害トリガアクションであって、前記第２のネットワークエレメントにより割当てられる前記ラベルを、前記宛て先ネットワークエレメントを宛て先とするパケットのラベルスタック内に、非障害条件の間に前記第２のネットワークエレメントに到達するために使用されるラベルの下方に含めるための当該障害トリガアクションをインストールすること、を含む、
ネットワークエレメント。
【請求項１８】
前記ネットワークエレメントの前記データプレーンは、前記潜在的な障害条件に対応する障害条件の検出後に、
前記現存するＬＳＰのために、前記第２のネットワークエレメントから受信される前記ラベルを、前記パケットのラベルスタックへプッシュすることと、
前記第２のネットワークエレメントへ到達するために使用される前記ラベルを、前記パケットの前記ラベルスタックへプッシュすることと、
ラベリングされた前記パケットを前記第２のネットワークエレメントに向けて送信することと、
を実行する、請求項１７のネットワークエレメント。
【請求項１９】
前記潜在的な障害条件は、前記第１のネットワークエレメントから下流のリンク及び前記第１のネットワークエレメントから下流のネットワークエレメント、のうち１つの障害である、請求項１７のネットワークエレメント。
【請求項２０】
前記第１のネットワークエレメントは、ローカルリペア点である、請求項１７のネットワークエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、２０１１年７月６日に提出された米国仮出願第６１／５０５，０５２号の利益を主張し、それは参照によりここに取り入れられる。
【０００２】
［分野］
本発明の実施形態は、ネットワーキングの分野に関し、より具体的には、ＭＰＬＳ（マルチプロトコルラベルスイッチング）高速再ルーティング（Fast-Reroute）に関する。
【背景技術】
【０００３】
キャリアクラスのネットワークにおいて、最小限のロスでトラフィックを回復させることは、根本的な要件である。高速再ルーティング（ＦＲＲ）は、ネットワーク内の障害条件下で最小限のロスでトラフィックを回復させるための技法である。
【０００４】
ＲＦＣ５０３６において定義されているＬＤＰ（Label  Distribution  Protocol）は、（ＲＦＣ３０３１及びＲＦＣ３０３２において定義されている）ＭＰＬＳ（MultiProtocol  Label  Switching）の実装においてラベルスイッチパス（ＬＳＰ）をセットアップするために広く配備されているプロトコルである。ＬＤＰは、（例えばＲＦＣ２３２８において定義されている）ＩＧＰ（Interior  Gateway  Protocol）によりセットアップされるルーティング対象パスに沿って、ＬＳＰを確立する。よって、障害条件下においてＬＤＰで確立されるＬＳＰの収束は、ＩＧＰの収束が条件となる。
【０００５】
ＲＳＶＰ−ＴＥ（Resource  Reservation  Protocol−Traffic  Engineering）ベースのＦＲＲが標準化されており（ＲＦＣ４０９０）、数々のベンダプラットフォームにおいて実装されてきた。いくつかの事業者及びベンダは、ＲＳＶＰ−ＴＥを用いることにより、ＬＤＰの高速な収束を解決しようと試みてきた。この特徴は、典型的には、ＬＤＰ−ｏｖｅｒ−ＲＳＶＰと呼ばれる。
【０００６】
ＬＤＰは、ＩＧＰによりセットアップされるルーティング対象パスを辿るため、その収束は、ＩＧＰの収束が条件となる。しかしながら、ＩＧＰの収束は、伝統的に遅かった。その問題の良好な説明は、ＲＦＣ５７１４のセクション４にある。例えば、その理由は、障害を検出するために費やされる時間、ローカルルータが障害に対してリアクションする時間量、ネットワーク内の他のルータへ障害に関する情報を送信するための時間量、転送テーブルを再計算するための時間量、及び再計算された転送テーブルを転送ハードウェアへダウンロードするための時間量、を含む。ＩＧＰにＦＲＲを導入してＩＧＰの収束を改善しようとする数々のアプローチが試みられてきたが、その各々は数々の問題に悩まされてきた。例えば、draft-ietf-rtgwg-ipfrr-notvia-addresses-0Xといったこの問題を解決するためのアプローチは、配備及び実装の複雑さを有し、そのために採択されなかった。（ＲＦＣ５２８６において説明されている）ループフリー代替（Loop  Free  Alternates）といったアプローチは、十分な範囲をカバーしていないために、キャリア達は、その配備を猶予している。
【０００７】
ＬＤＰ  ＬＳＰのためにＦＲＲを提供する他のアプローチは、障害バイパスの仕組み（ＬＤＰ−ｏｖｅｒ−ＲＳＶＰ）としてＲＳＶＰ−ＴＥを使用することである。しかしながら、キャリア達によるＲＳＶＰ−ＴＥの配備は複数の理由に起因して遅々としており、その理由は、増加した運用経費をもたらす、ＲＳＶＰ−ＴＥなどの追加的でかなり煩雑なプロトコルが使用されることによる大規模な構成及びメンテナンス体験の要件を含む。ＬＤＰ−ｏｖｅｒ−ＲＳＶＰは、ベンダが多くの特徴（高可用性及び信頼性など）をＲＳＶＰ−ＴＥにおいてサポートすることをも要し、それは多くの実装において利用可能ではないかもしれない。
【発明の概要】
【０００８】
ＬＤＰ（ラベル配布プロトコル）を用いたＭＰＬＳ（マルチプロトコルラベルスイッチング）の高速再ルーティングが説明される。潜在的な障害条件下で宛て先ネットワークへ到達するためのＬＤＰ  ＬＳＰ（ラベルスイッチパス）が計算される。複数のネットワークエレメントのうちの計算される当該ＬＤＰ  ＬＳＰに沿ってその時点の最短パスＬＤＰ  ＬＳＰへのネクストホップを有する第１のネットワークエレメントであるエレメントにおいて、計算される当該ＬＤＰ  ＬＳＰは、その時点の（current）最短パスＬＤＰ  ＬＳＰとマージされる。
【０００９】
１つの実施形態において、潜在的な障害を迂回してトラフィックを再ルーティングするように、ローカルリペア点（ＰＬＲ）からＢＳＰマージ点（ＭＰ）へバックアップ最短パス（ＢＳＰ）ＬＳＰが生成される。障害が発生すると、ＰＬＲは、トラフィックを最短パス（ＳＰ）ＬＳＰからＢＳＰ  ＬＳＰへスイッチングする。ＰＬＲは、ＰＬＲからＢＳＰ−ＭＰへのＳＰ  ＬＳＰに沿うＢＳＰ−ＭＰへトラフィックをスイッチングするために、ラベルスタッキングを使用する。ＢＳＰ−ＭＰラベルは、ＢＳＰ  ＬＳＰから（障害を経由しない）ＳＰ  ＬＳＰへトラフィックをスイッチングし、よってトラフィックが復旧する。ＢＳＰ−ＭＰからＰＬＲへのパスに沿う全てのノードはＢＳＰ  ＬＳＰについてのステートを有しているため、追加的なステートは要求されない。このプロセスは、ネットワークにわたって複数の障害点について実行される（例えば、このプロセスは、ネットワーク内の全ての潜在的な障害条件について実行される）。
【００１０】
１つの実施形態において、ＭＰＬＳネットワーク内の第１のネットワークエレメントは、上記ＭＰＬＳネットワーク内の第２のネットワークエレメントから広告される第１のラベルを受信する。上記第１のネットワークエレメントは、潜在的な障害条件下で宛て先ネットワークエレメントへ到達するための最短パスツリー（ＳＰＴ）を計算する。上記第２のネットワークエレメントは、計算される当該ＳＰＴにおいて上記第１のネットワークエレメントのネクストホップであり、且つ計算される当該ＳＰＴにおいて上記潜在的な障害条件から上流にはない。上記第１のネットワークエレメントは、上記潜在的な障害条件が現実化した場合に上記ＭＰＬＳネットワーク内の第３のネットワークエレメントがＰＬＲであることを判定する。上記第１のネットワークエレメントは、上記潜在的な障害条件が現実化した場合にバックアップパスとしてサービスすることとなるバックアップＬＤＰ  ＬＳＰのために、第２のラベルを上記第３のネットワークエレメントへ配布する。上記第１のネットワークエレメントは、上記第２のラベルから上記第１のラベルへのスワップアクションをインストールする。１つの実施形態において、バックアップＬＤＰ  ＬＳＰは、上記第３のネットワークエレメントから上記第１のネットワークエレメントへの現存する最短パスＬＳＰである。
【００１１】
１つの実施形態において、ＭＰＬＳネットワーク内の第１のネットワークエレメントは、潜在的な障害条件下で宛て先ネットワークエレメントへ到達するためのＳＰＴを計算する。上記第１のネットワークエレメントは、上記潜在的な障害条件が現実化した場合に、後続して上記第１のネットワークエレメントにおいて受信される、上記宛て先ネットワークエレメントを宛て先とするパケットが、現存するＬＳＰを用いて第２のネットワークエレメントに向けて、当該現存するＬＳＰを上記第２のネットワークエレメントから上記宛て先ネットワークエレメントへの最短パスＬＤＰ  ＬＳＰにマージすべき旨の上記第２のネットワークエレメントへの標識と共に再ルーティングされるように、自身の転送ステートを構成する。上記第２のネットワークエレメントは、上記宛て先ネットワークエレメントへの上記最短パスＬＤＰ  ＬＳＰ上にネクストホップを有する、計算された上記ＳＰＴ上の上流ネットワークエレメントである、
【図面の簡単な説明】
【００１２】
本発明は、以下の説明と、本発明の実施形態を例示するために用いられる添付図面とを参照することによって最もよく理解され得る。図面において：
【００１３】
【図１】１つの実施形態に従って、最短パスＬＳＰの再利用と共にＬＤＰ−ＦＲＲを用いる例示的なＭＰＬＳネットワークを示す。
【図２】１つの実施形態に従って、潜在的なリンクの障害を前提として、ネットワークエレメントが所与の宛て先へ到達するためのＢＳＰ  ＬＳＰを構成する、図１のネットワークを示す。
【図３】１つの実施形態に従って、潜在的なネットワークエレメントの障害を前提として、ネットワークエレメントが所与の宛て先へ到達するためのＢＳＰ  ＬＳＰを構成する、図１のネットワークを示す。
【図４】１つの実施形態に従って、単一のリンク障害について最短パスＬＳＰの再利用と共にＬＤＰ−ＦＲＲを構成するための例示的な動作を示すフロー図である。
【図５】１つの実施形態に従って、単一のノード障害について最短パスＬＳＰの再利用と共にＬＤＰ−ＦＲＲを構成するための例示的な動作を示すフロー図である。
【図６】１つの実施形態に従って、複数の障害が存在する場合にネットワークエレメントが所与の宛て先へ到達するためのＢＳＰ  ＬＳＰを構成する、図１のネットワークを示す。
【図７】実施形態において使用され得る例示的な障害エレメントＴＬＶを示す。
【図８】実施形態において使用され得る例示的なバックアップパスベクトルＴＬＶを示す。
【図９】実施形態において使用され得る例示的なトンネルドＦＥＣ  ＴＬＶを示す。
【図１０】１つの実施形態に従ってＬＤＰ  ＦＲＲを実装する例示的なネットワークエレメントを示す。
【発明を実施するための形態】
【００１４】
以下の説明において、多くの具体的な詳細が述べられる。しかしながら、本発明の実施形態はこれらの具体的な詳細無しに実践され得ることが理解される。他の例において、周知の回路、構造及び技法は、本説明の理解を曖昧にしないために詳細には示されていない。当業者は、含まれた説明により、過度の実験無しに適切な機能性を実装することが可能であろう。
【００１５】
本明細書における「１つの実施形態」、「一実施形態」、「例示的な実施形態」などへの言及は、説明される実施形態が特定の特徴、構造、又は特性を有し得ることを示すが、あらゆる実施形態が必ず当該特定の特徴、構造、又は特性を含むというわけではない。その上、そのようなフレーズは、必ずしも同じ実施形態に言及しない。さらに、特定の特徴、構造、又は特性が一実施形態に関連して説明される場合、明示的に説明されていてもいなくても、そのような特徴、構造、又は特性を他の実施形態に関連して作用させることは当業者の知識の範囲内であることが提示される。
【００１６】
以下の説明及び特許請求の範囲において、「結合される（coupled）」及び「接続される（connected）」という用語は、それらの派生語と共に用いられ得る。これらの用語は互いに同義語として意図されないことが理解されるべきである。「結合される」は、直接物理的に又は電気的に互いに接触してもしなくてもよい２つ以上のエレメントが互いに協働し又はインタラクションすることを示すために用いられる。「接続される」は、互いに結合される２つ以上のエレメントの間の通信の確立を示すために用いられる。
【００１７】
１つの実施形態において、ＬＤＰ  ＬＳＰについての高速再ルーティングが、ＩＧＰの高速収束、ＩＰ−ＦＲＲ、又はＲＳＶＰ−ＴＥベースのＦＲＲに依存することなく提供される。ＬＤＰは現行の広い採用をもたらした非常に単純で簡単な構成手続きを有するため、本発明の実施形態を採用する実装は、単純な構成モデルを維持することができる。ほとんどの状況において、キャリアは、本発明の実施形態の実装のためにいかなる運用手続きをも変更する必要がないであろう。よって、本発明の実施形態は、あらゆる異常シナリオにおける収束を提供しつつ、ＬＤＰを運用することの単純さを維持し、並びにＩＰ−ＦＲＲ及びＬＤＰ−ｏｖｅｒ−ＲＳＶＰの複雑さを克服する。
【００１８】
以下の専門用語が、本発明の実施形態を説明するために用いられる。ＰＬＲ（ローカルリペア点（Point  of  Local  Repair））は、バックアップスイッチパス（ＢＳＰ：backup-switched  path）ＬＳＰのヘッドエンドＬＳＲ（ラベルスイッチルータ）である。ＰＬＲは、障害を検出し、及び代替的なルート（ＢＳＰ  ＬＳＰ）上でトラフィックを送ることによってリンク又はノードの当該障害を修復するノードである。ＢＳＰ  ＬＳＰは、最短パスＬＤＰ  ＬＳＰ上の特定の障害エンティティについてバックアップを提供するＬＤＰ  ＬＳＰである。障害エンティティは、リンク、ノード、又はＳＲＬＧであり得る。ＢＳＰ  ＬＳＰは、ＰＬＲを起点とする。バックアップスイッチパスマージ点（ＢＳＰ−ＭＰ）は、ＢＳＰ  ＬＳＰが最短パスＬＤＰ  ＬＳＰについて割り当てられるラベルにラベルスイッチングされるＬＳＲである。ＢＳＰ−ＭＰは、潜在的な障害の下流にある必要はない。排除ＳＰＴ（exclude  Shortest  Path  Tree）は、特定の障害ポイントがネットワークから排除される場合の、ＰＬＲからＦＥＣ（Forwarding  Equivalence  Class）への最短パスツリーである。
【００１９】
１つの実施形態において、潜在的な障害を迂回してトラフィックを再ルーティングするように、ＰＬＲからＢＳＰ−ＭＰへＢＳＰ  ＬＳＰが生成される。障害が発生すると、ＰＬＲは、トラフィックを最短パス（ＳＰ）ＬＳＰからＢＳＰ  ＬＳＰへスイッチングする。ＰＬＲは、ＰＬＲからＢＳＰ−ＭＰへのＳＰ  ＬＳＰに沿うＢＳＰ−ＭＰへトラフィックをスイッチングするために、ラベルスタッキングを使用する。ＢＳＰ−ＭＰラベルは、ＢＳＰ  ＬＳＰから（障害を経由しない）ＳＰ  ＬＳＰへトラフィックスイッチングし、よってトラフィックが復旧する。ＢＳＰ−ＭＰからＰＬＲへのパスに沿う全てのノードはＢＳＰ  ＬＳＰについてのステートを有しているため、追加的なステートは要求されない。このプロセスは、ネットワークにわたって複数の障害点について実行される（例えば、このプロセスは、ネットワーク内の全ての潜在的な障害条件について実行される）。
【００２０】
図１は、１つの実施形態に従って、最短パス（ＳＰ）ＬＳＰの再利用と共にＬＤＰ−ＦＲＲを用いる例示的なＭＰＬＳネットワークを示す。図１に示したネットワークは、ネットワークエレメント１１０Ａ〜Ｇを含む。ネットワークエレメントの各々は、ＬＳＲとして動作する。ネットワークエレメント１１０Ａは、リンク１２２、１２６、１２０及び１２７上でそれぞれネットワークエレメント１１０Ｂ、１１０Ｄ、１１０Ｅ及び１１０Ｇに結合される。ネットワークエレメント１１０Ｂは、さらに、リンク１２３上でネットワークエレメント１１０Ｃに結合され、リンク１２１上でネットワークエレメント１１０Ｄに結合される。ネットワークエレメント１１０Ｃは、さらに、リンク１２４上でネットワークエレメント１１０Ｆに結合される。ネットワークエレメント１１０Ｆは、さらに、リンク１２５上でネットワークエレメント１１０Ｅに結合される。リンク１２１、１２２、１２３、１２４、１２５、１２６及び１２７は、１であるコストを各々有する。リンク１２０は、５であるコストを有する。
【００２１】
図１は、ネットワークエレメントの間で確立された複数のＬＳＰセグメントをも示す（但し、確立されるかもしれない各ＬＳＰセグメントを図１は示していないことが理解されるべきである）。１つの実施形態において、ＬＳＰセグメントは、ＬＤＰを用いて確立されている。例えば、例えば、ラベルＬ：Ｂ，Ｆは、ネットワークエレメント１１０ＢによりプレフィクスＦのために割当てられ、ネットワークエレメント１１０Ｄ及び１１０Ｂの間のＬＳＰセグメント１４１上で（ネットワークエレメント１１０Ｆ上の）プレフィクスＦを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｄにより使用される。ネットワークエレメント１１０Ｃは、ネットワークエレメント１１０Ｂ及び１１０Ｃの間のＬＳＰセグメント１４２上でプレフィクスＦを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｂにより使用されるべきラベルＬ：Ｃ，ＦをプレフィクスＦのために割当てる。ネットワークエレメント１１０Ｆは、ネットワークエレメント１１０Ｆ及び１１０Ｃの間のＬＳＰセグメント１４３上でプレフィクスＦを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｃにより使用されるべきラベルＬ：Ｆ，ＦをプレフィクスＦのために割当てる。同様に、ネットワークエレメント１１０Ｆは、ネットワークエレメント１１０Ｅ及び１１０Ｆの間のＬＳＰセグメント１６１上でプレフィクスＦを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｅにより使用されるべきラベルＬ：Ｆ，ＦをプレフィクスＦのために割当てる。ネットワークエレメント１１０Ｅは、ネットワークエレメント１１０Ａ及びネットワークエレメント１１０Ｅの間のＬＳＰセグメント１６０上でプレフィクスＦを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ａにより使用されるべきラベルＬ：Ｅ，ＦをプレフィクスＦのために割当てる。ネットワークエレメント１１０Ａは、プレフィクスＦを宛て先としてネットワークエレメント１１０Ｇにより使用されるべきラベルＬ：Ａ，ＦをプレフィクスＦのために割当てる。
【００２２】
また、ネットワークエレメント１１０Ｂは、ラベルＬ：Ｂ，Ａを（ネットワークエレメント１１０Ａ上の）プレフィクスＡのために割当て、それはネットワークエレメント１１０Ｃ及び１１０Ｂの間のＬＳＰセグメント１５０上でプレフィクスＡを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｃにより使用される。また、ネットワークエレメント１１０Ａは、ネットワークエレメント１１０Ａ及び１１０Ｂの間のＬＳＰセグメント１５１上でプレフィクスＡを宛て先とするトラフィックを送信する際にネットワークエレメント１１０Ｂにより使用されるべきラベルＬ：Ａ，Ａを、プレフィクスＡのために割当てる。
【００２３】
例示によれば、通常の動作の間（トラフィックのパスに影響を与える障害が無いことを想定）、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｆ上のプレフィクスＦへ流れるトラフィックは、ＬＳＰ１６０の次のようなパスを辿る：（ラベルＬ：Ｂ，Ｆを伴ってＬＳＰセグメント１４１上で）ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、（ラベルＬ：Ｃ，Ｆを伴ってＬＳＰセグメント１４２上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ｃへ、及び（ラベルＬ：Ｆ，Ｆを伴ってＬＳＰセグメント１４３上で）ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ｆへ。他の例として、ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ａ上のプレフィクスＡへ流れるトラフィックは、ＬＳＰ１６５の次のようなパスを辿る：（ラベルＬ：Ｂ，Ａを伴ってＬＳＰセグメント１５０上で）ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ｂへ、及び（ラベルＬ：Ａ，Ａを伴ってＬＳＰセグメント１５１上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ａへ。
【００２４】
ネットワークエレメントは、ラベルスイッチングを実行するために、転送構造（例えば、インカミングラベルマップ（ＩＬＭ）、ネクストホップラベル転送エントリ（ＮＨＬＦＥ）、転送等価クラス（ＦＥＣ）からＮＨＬＦＥへのマップ（ＦＴＮ）など）を含む。これら転送構造は、当該ネットワークエレメントのデータプレーンのステートの少なくとも一部である。例えば、ネットワークエレメント１１０Ｂは、ネットワークエレメント１１０ＤからラベルＬ：Ｂ，Ｆを有するパケットを受信した場合に当該ラベルをネットワークエレメント１１０Ｃによって広告されたラベルＬ：Ｃ，Ｆとスワッピングして当該パケットをネットワークエレメント１１０Ｃへ送信すべきであることを特定する転送構造を含む。
【００２５】
１つの実施形態において、図１に示したネットワークエレメントは、ある数の潜在的な障害についてのＢＳＰ  ＬＳＰを、障害が発生した場合に備えて計算する。ＬＤＰ  ＦＲＲを確立するためにネットワークエレメントにより実行される動作を説明するために、以下の専門用語が使用される。
【００２６】
１．指向性グラフはＧと表記される。ノードはＳ，Ｄ，Ｎ，Ｍ，Ｏ及びＰと表記される。リンクはＬ，Ｋ，Ｊ及びＩと表記される。
２．Ｇ内の全てのリンクは０より大きいコストを有する。
３．ｎｏｄｅ（Ｇ，Ｄ）はグラフＧ内のノードＤの表記である。
４．ＳＰＴは、（例えばダイクストラのアルゴリズムによって計算される通りの）最短パスツリーを意味する。
５．ＳＰＴ（Ｇ，Ｓ）は（グラフＧ内の）ノードＳからＧ内の他の全てのノードへのＳＰＴの表記である。なお、ＳＰＴ（Ｇ，Ｄ）は、指向性非巡回グラフ（ＤＡＧ）であり、当然にグラフである。
６．ｐａｉｒＳＰＴ（Ｇ，Ｓ，Ｄ）は、Ｇ内のＳからＤへのノードのペア間のＳＰＴの表記である。
７．ｐａｉｒＳＰＴ（Ｇ，Ｓ，Ｄ，Ｄ１，Ｄ２，…）は、ＳからＤ，Ｄ１，Ｄ２，…のいずれか１つへ到達するための最短パスの表記である。
８．ｔｏＳＰＴ（Ｇ，Ｄ）は、グラフＧ内のノードＤへのＧ内の他の全てのノードからの（例えばダイクストラのアルゴリズムによって計算される通りの）最短パスツリーである。なお、ｔｏＳＰＴ（Ｇ，Ｄ）もまた、ＳＰＴ（Ｇ，Ｓ）と同様にＤＡＧであり、当然ながらグラフである。
９．ｌｉｎｋ（Ｇ，Ｌ）は、グラフＧ内の指向性リンクＬの表記である。
１０．ｕｐＮｏｄｅ（Ｇ，Ｌ）は、グラフＧ内のリンクＬの上流端にあたるノードの表記である。
１１．ｄｎＮｏｄｅ（Ｇ，Ｌ）は、グラフＧ内のリンクＬの下流端にあたるノードの表記である。
１２．なお、ｕｐＮｏｄｅ（ｔｏＳＰＴ（Ｇ，Ｄ），Ｌ）は、トラフィックを代替ルート上へ送信することによってＬ内の障害をリペアするであろうノードである。これは、典型的には、Ｌ内の障害をリペアするためのローカルリペア点（ＰＬＲ）として言及される。ｄｎＮｏｄｅ（ｔｏＳＰＴ（Ｇ，Ｄ），Ｌ）は、直接的に接続されているＬＤＰピアのためにＰＬＲによりリンク保護が行われラベルスタッキングが使用される場合にトラフィックをマージし直すノードであろうことにも留意されたい。
１３．ｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）は、ｔｏＳＰＴ（Ｇ，Ｄ）内のＬの上流にある全てのノードとそれらノードの間の全てのリンクからなるＧのサブツリーの表記である。ＬがｔｏＳＰＴ（Ｇ，Ｄ）に属しないならば、それはＮＵＬＬグラフである。なお、ｕｐｓｔｒはグラフであるが、必ずしもＤＡＧではない。
１４．Ｇ−Ｌは、リンクＬを除いたグラフＧの表記である。
１５．Ｇ−Ｆは、グラフＧのサブセットの表記である。ここで、Ｆはリンク群及び（付随するリンクを伴う）ノード群のセットである。ＦはＧから除去され、Ｇ−Ｆが与えられる。
【００２７】
接続されたグラフＧ内で、ｔｏＳＰＴ（Ｇ，Ｄ）内の任意のリンクＬについて、（任意のＤについて、）Ｇ内にｕｐＮｏｄｅ（Ｌ）からＤへのパスが存在する場合、Ｇ内であって但しｕｐｓｔｒ（Ｇ，Ｄ，Ｌ）内ではないノードへのＬ以外のリンクを有するノードが存在する。そうしたノードが存在しない場合、リンクＬはグラフＧのカットエッジであり、Ｇ−Ｌ内にｕｐＮｏｄｅ（Ｇ，Ｌ）からＤへのパスは無い。Ｌがカットエッジでなければ、ｕｐＮｏｄｅ（Ｇ，Ｌ）からｄｎＮｏｄｅ（Ｇ，Ｌ）へのＬを含まないパスが存在する。１つのＳＰＴサブツリーから他へのパスが無いとすると、２つのサブツリーの間にリンクは存在せず、２つのサブツリーの間に共通のノードは無い。この場合、２つのツリーの間に接続性が無く、障害は２つのバラバラの（disjoint）サブグラフを生成したことになり、代替的なパスは無い。
【００２８】
図２は、図１のネットワークを示しており、リンク１２４の潜在的な障害に対して、ネットワークエレメント１１０Ｆへ接続されるプレフィクスＦへ到達するためのＢＳＰ  ＬＳＰをネットワークエレメントが構成する。リンク１２４の障害を想定すると、ネットワークエレメント１１０ＣがＰＬＲとして動作し、ネットワークエレメント１１０ＡがＢＳＰ−ＭＰとして動作する。
【００２９】
ネットワークエレメント１１０Ｃは、（それまでの既存の最短パスＬＳＰ）であるＬＳＰ１６０から、当該ＰＬＲからネットワークエレメント１１０Ａ（ＢＳＰ−ＭＰ）への最短パスＬＳＰであってバックアップ最短パス（ＢＳＰ）ＬＳＰとして使用されるＬＳＰ１６５へ、ラベルスタッキングを用いてトラフィックをスイッチングする。例えば、ネットワークエレメント１１０Ｃは、ネットワークエレメント１１０Ａへ到達するためのラベルを、障害を通過しないＳＰ−ＬＳＰのためにネットワークエレメント１１０Ａが使用するラベルの上にスタッキングする。よって、ネットワークエレメント１１０Ｃは、リンク１２４の障害を迂回してトラフィックを再ルーティングするために、現存するＬＳＰ１６５を再利用する。ネットワークエレメント１１０Ａ（ＢＳＰ−ＭＰ）は、ＬＳＰ１６５（ＢＳＰ  ＬＳＰ）からＬＳＰ１６０（障害を通過しないＳＰ−ＬＳＰ）へトラフィックをラベルスイッチングし、それによりトラフィック復旧させる（restore）。ＰＬＲとＢＳＰ−ＭＰとの間のパスに沿った全てのノードはＢＳＰ  ＬＳＰ（ＬＳＰ１６０）についてのステートを有するため、ＰＬＲからＢＳＰ−ＭＰへのパスに沿って追加的なステートは要求されない。しかしながら、ＰＬＲは余分なステート（例えば、ＢＳＰ−ＭＰがパケットをＳＰ−ＬＳＰへ送り返すために使用するラベル）を維持する。最短パスＬＳＰは、多くのプレフィクスのためのＢＳＰ  ＬＳＰとして使用されてよい（例えば、プレフィクスに固有のラベルは、最短パスＬＳＰの当該ラベルをラベルスタック上へプッシュするに先立ってスワップされる）。
【００３０】
よって、ネットワークエレメント１１０Ｃは、リンク１２４の障害からネットワークエレメント１１０ＦにおけるプレフィクスＦへのＬＳＰを保護するためのバックアップ最短パスＬＳＰとして、ネットワークエレメント１１０Ａへの最短パスＬＳＰ（ＬＳＰ１６５）を使用する。ネットワークエレメント１１０Ｃは、リンク１２４のための障害アクションを、まずラベルＬ：Ｃ，ＦをＬ：Ａ，Ｆへスワップし、そしてネットワークエレメント１１０Ａへの最短パスＬＳＰのためのラベル（ラベルＬ：Ｂ，Ａ）をプッシュするように、（例えば自身のＩＬＭのエントリ内に）予めインストールする。ネットワークエレメント１１０Ｂは、Ｌ：Ｂ，Ａというアウターラベルを有するパケットの受信後に当該パケットがラベルＬ：Ａ，Ａへラベルスイッチングされてネットワークエレメント１１０ＡへＬＳＰセグメント１５１上で送信されることになるような転送エントリを含む。ネットワークエレメント１１０Ａは、Ｌ：Ａ，ＡというアウターラベルとＬ：Ａ，Ｆというインナーラベルとを有して受信されたパケットをラベルＬ：Ｅ，Ｆと共にＬＳＰセグメント１６０上へラベルスイッチングさせる転送エントリを含む。ネットワークエレメント１１０Ｅは、ラベルＬ：Ｅ，Ｆを有して受信されたパケットをラベルＬ：Ｆ，Ｆと共にＬＳＰセグメント１６１上へラベルスイッチングさせる転送エントリを含む。
【００３１】
例示によれば、リンク１２４の障害がある場合、プレフィクスＦについてネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｆへ流れるトラフィックは、次のようなパスを辿る：（ラベルＬ：Ｂ，Ｆを伴ってＬＳＰセグメント１４１上で）ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、（ラベルＬ：Ｂ，ＦのラベルＬ：Ｃ，Ｆのためのスワップを伴ってＬＳＰセグメント１４２上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ｃへ、（ラベルＬ：Ｃ，ＦのラベルＬ：Ａ，ＦのためのスワップとラベルＬ：Ｂ，Ａのプッシュとを伴ってＬＳＰセグメント１５０上で）ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ｂへ、（ラベルＬ：Ｂ，ＡのラベルＬ：Ａ，Ａのためのスワップを伴って（ラベルＬ：Ａ，Ｆはラベルスタック上で維持され）ＬＳＰセグメント１５２上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ａへ、（ラベルＬ：Ａ，ＦのラベルＬ：Ｅ，Ｆのためのスワップを伴ってＬＳＰセグメント１６０上で）ネットワークエレメント１１０Ａからネットワークエレメント１１０Ｅへ、（ラベルＬ：Ｅ，ＦのラベルＬ：Ｆ，Ｆのためのスワップを伴ってＬＳＰセグメント１６１上で）ネットワークエレメント１１０Ｅからネットワークエレメント１１０Ｆへ。
【００３２】
図２はリンク１２４の障害後にラベルＬ：Ａ，Ｆ上のラベルＬ：Ａ，Ａというラベルスタックをネットワークエレメント１１０Ａが受信することを示しているものの、最終前ホップポッピング（ＰＨＰ：penultimate  hop-popping）が使用される状況ではパケットがネットワークエレメント１１０Ａにおいて受信される際にバックアップ最短パスＬＳＰ１６５のラベル（ラベルＬ：Ａ，Ａ）が既にポッピングされていてもよいことが理解されるべきである。
【００３３】
図２は、図４を基準としてさらに説明されるであろう。図４は、１つの実施形態に従って、ＳＰ  ＬＳＰの再利用と共にＬＤＰ−ＦＲＲを構成するための例示的な動作を示すフロー図である。１つの実施形態において、ネットワークエレメント１１０Ａ〜Ｆの各々が、ネットワーク内の潜在的な複数の障害条件のために、図４において説明されるような動作を実行する。
【００３４】
動作４１０において、ノードのうちの１つ（ネットワークエレメント１１０Ａ〜Ｆのうち１つ）が選択される。図２を基準として、この例の目的のために、選択されるノードはネットワークエレメント１１０Ｆである。そして、フローは動作４１５へ移り、選択ノード１１０Ｆへのネットワーク内の他の全てのノードからのＳＰＴが計算される。例えば、ネットワークエレメント１１０Ｄからネットワークエレメント１１０ＦへのＳＰＴパスは、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ｃへ、ネットワークエレメント１１０Ｆへとなる。ネットワークエレメント１１０Ａからネットワークエレメント１１０ＦへのＳＰＴパスは、ネットワークエレメント１１０Ａからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ｃへ、ネットワークエレメント１１０Ｆへとなる。ネットワークエレメント１１０ＥからのＳＰＴパスは、ネットワークエレメント１１０Ｅからネットワークエレメント１１０Ｆへとなる。リンク１２０及び１２６は、ネットワークエレメント１１０ＦへのＳＰＴの一部ではない。そして、フローは動作４２０へ移る。
【００３５】
動作４２０において、計算されたＳＰＴからリンクが除外されるものとして選択される。図２を基準として、この例の目的のために、除外されるものとして選択されるリンクは、ネットワークエレメント１１０Ｆと１１０Ｃとの間のリンク１２４である（よって、リンク１２４に障害が生じるものと仮定される）。そして、フローは動作４２５へ移り、選択ノードへのＳＰＴが、選択リンクを除外したものとして計算される。よって、選択リンクがネットワークトポロジーの一部でないものとして、選択ノードへのＳＰＴが計算される。例えば、ネットワークエレメント１１０Ｃからネットワークエレメント１１０ＦへのＳＰＴパスは（リンク１２４が存在しないものとして）、ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ａへ、ネットワークエレメント１１０Ｅへ、ネットワークエレメント１１０Ｆへとなる。
【００３６】
そして、フローは動作４３０へ移り、計算を実行しているネットワークエレメントが選択リンクの上流であって且つ選択リンクを除外した場合のＰＬＲから選択ノードへのＳＰＴに属するかの判定が行われる。ＰＬＲから選択ノードへの選択リンクを伴うＳＰＴを、ここでは図４の動作を基準として除外ＳＰＴという。図２を参照し、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｆへ送信されるトラフィックについてリンク１２４の障害を仮定すると、ＰＬＲはネットワークエレメント１１０Ｃである。選択リンク１２４の上流にあるノードは、ネットワークエレメント１１０Ａ，１１０Ｂ，１１０Ｃ，１１０Ｄ，及び１１０Ｇを含む。除外ＳＰＴに属するノードは、ネットワークエレメント１１０Ａ，１１０Ｂ及び１１０Ｇである（ネットワークエレメント１１０Ｆは、除外ＳＰＴの一部ではない）。計算を実行しているネットワークエレメントが選択リンクの上流であって且つ選択リンクを除外した場合のＰＬＲから第２のノードへのＳＰＴに属する場合、フローは動作４３５へ移り、そうでなければフローは動作４５０へ移る。
【００３７】
動作４３５において、計算を実行しているネットワークエレメントは、自身が除外ＳＰＴの中に当該リンクから上流でないネクストホップを有するかを判定する。言い換えれば、動作４３５において、当該ネットワークエレメントは、自身がマージ点（ＢＳＰ−ＭＰ）であるかを判定する。別の言い方をすれば、ネットワークエレメントが除外ＳＰＴ上にあって且つ障害点を横断しない選択ノードへの最短パスＬＤＰ  ＬＳＰに属する場合、それはマージ点であり、フローは動作４４０へ移ることになる。例えば、図２を参照すると、ネットワークエレメント１１０Ａは、除外ＳＰＴ上であってリンク１２４の上流にあり、選択リンク１２４からの上流ではないネクストホップ（ネットワークエレメント１１０Ｅ）を有し、よってマージ点である。ネットワークエレメント１１０Ｂは、除外ＳＰＴ上にあるものの、選択リンク１２４からの上流ではないネクストホップを有しない。自身がマージ点であればフローは動作４４０へ移り、そうでなければフローは動作４６５へ移る。
【００３８】
動作４４０において、ネットワークエレメントは、障害条件が現実化した場合のバックアップＬＤＰ  ＬＳＰのために、ＰＬＲへラベルを配布する。バックアップＬＳＰは、ＰＬＲと当該ネットワークエレメントとの間の現存するＬＳＰである。例えば、図２を参照すると、ネットワークエレメント１１０Ａは、ネットワークエレメント１１０ＣへラベルＬ：Ａ，Ｆを配布する。ラベルＬ：Ａ，Ｆは、トラフィックをＬＳＰセグメント１６０へマージして当該トラフィックをネットワークエレメント１１０ＦへのＳＰＴ  ＬＳＰ１７０へリダイレクトする際にネットワークエレメント１１０Ａによって使用されるラベルである。ネットワークエレメント１１０Ａは、ラベルＬ：Ａ，Ｆを配布するためにネットワークエレメント１１０ＣとのターゲットＬＤＰセッションを確立してもよく、又は、当該ラベルをネットワークエレメント１１０Ｃへ広告することになるネットワークエレメント１１０Ｂへ、当該ラベルを広告してもよい。フローは、動作４４０から動作４６５へ移る。
【００３９】
動作４５０において、動作を実行中のネットワークエレメントがＰＬＲであるならばフローは動作４５５へ移り、そうでなければフローは動作４６５へ移る。動作４５５において、ネットワークエレメントは、マージ点から受信されるラベルを選択ノードを宛て先とするパケットのラベルスタック内でマージ点に到達するために使用されるラベルの下方に含めるための、選択リンク（除外されたリンク）についての障害トリガアクションをインストールする。例えば、図２を基準とすると、ネットワークエレメント１１０Ｃは、リンク１２４が障害を起こした後に、ネットワークエレメント１１０ＣがラベルＬ：Ｃ，Ｆを伴って到来するトラフィックを（ネットワークエレメント１１０Ａにより割当てられる）ラベルＬ：Ａ，Ｆと（ネットワークエレメント１１０Ｂにより割当てられる）ラベルＬ：Ｂ，ＡとでラベリングしてＬＳＰセグメント１５０上で送信するような、障害トリガアクションをインストールする。よって、（リンク１２４の障害についてＰＬＲとして動作している）ネットワークエレメント１１０Ｃの転送エントリ（例えば、ＩＬＭ内のエントリ）は、リンク１２４の障害が起こるとトラフィックが最短パスＬＳＰ１６０からバックアップ最短パスＬＳＰ１６５へスイッチングされるように変更される。
【００４０】
動作４６５において、選択ノードへの計算されたＳＰＴ内に他のリンクが存在するかが判定される。他のリンクが存在する場合、フローは動作４２０へ戻り、計算されたＳＰＴから除外されるものとして他のリンクが選択される。他のリンクが存在しない場合、フローは動作４７０へ移り、ネットワーク内に他のノードが存在するかが判定される。他のノードがある場合、フローは動作４１０へ戻り、他のノードが選択される。他のノードが存在しない場合、フローは動作４７５へ移り、プロセスが終了する。
【００４１】
図３は、図１のネットワークを示しており、ネットワークエレメント１１０Ｃの潜在的な障害に対して、ＳＰ  ＬＳＰの再利用と共にＬＤＰ  ＦＲＲをネットワークエレメントが構成する。図３は、図５を基準としてさらに説明されるであろう。図５は、１つの実施形態に従って、ネットワークエレメントの潜在的な障害に対してＳＰ  ＬＳＰの再利用と共にＬＤＰ  ＦＲＲを構成するための例示的な動作を示すフロー図である。１つの実施形態において、ネットワークエレメント１１０Ａ〜Ｇの各々が、図５において説明される動作を実行する。
【００４２】
動作５１０において、ノードのうちの１つ（ネットワークエレメント１１０Ａ〜Ｇのうち１つ）が選択される。図３を基準として、選択されるノードはネットワークエレメント１１０Ｆである。そして、フローは動作５１５へ移り、選択ノード１１０Ｆへのネットワーク内の他の全てのノードからのＳＰＴが計算される。例えば、ネットワークエレメント１１０Ｄからネットワークエレメント１１０ＦへのＳＰＴパスは、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ｃへ、ネットワークエレメント１１０Ｆへとなる。ネットワークエレメント１１０Ａからネットワークエレメント１１０ＦへのＳＰＴパスは、ネットワークエレメント１１０Ａからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ｃへ、ネットワークエレメント１１０Ｆへとなる。ネットワークエレメント１１０ＥからのＳＰＴパスは、ネットワークエレメント１１０Ｅからネットワークエレメント１１０Ｆへとなる。リンク１２０及び１２６は、ネットワークエレメント１１０ＦへのＳＰＴの一部ではない。そして、フローは動作５２０へ移る。
【００４３】
動作５２０において、計算されたＳＰＴからノードが除外されるものとして選択される。図３を基準として、除外されるものとして選択されるノードは、ネットワークエレメント１１０Ｃであり、それをここでは除外ノードという（よって、ネットワークエレメント１１０Ｃに障害が生じるものと仮定される）。そして、フローは動作５２５へ移り、選択ノードへのＳＰＴが、除外ノードを除外したものとして計算される。よって、除外ノードがネットワークの一部でないものとして、選択ノードへのＳＰＴが計算される。例えば、ネットワークエレメント１１０Ｄからネットワークエレメント１１０ＦへのＳＰＴパスは（ネットワークエレメント１１０Ｃが存在しないものとして）、ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、ネットワークエレメント１１０Ａへ、ネットワークエレメント１１０Ｅへ、ネットワークエレメント１１０Ｆへとなる。
【００４４】
そして、フローは動作５３０へ移り、計算を実行しているネットワークエレメントが除外ノードの上流であって且つ除外ノードを除外した場合の上流ノードから選択ノードへのＳＰＴに属するかの判定が行われる。除外ノードを除外した場合の上流ノードから選択ノードへのＳＰＴを、ここでは図５の動作を基準として除外ＳＰＴという。図３を参照し、ネットワークエレメント１１０Ｄからネットワークエレメント１１０ＦにおけるプレフィクスＦに向けて送信されるトラフィックについてネットワークエレメント１１０Ｃの障害を仮定すると、ＰＬＲはネットワークエレメント１１０Ｂである。障害の上流にあるノードは、ネットワークエレメント１１０Ａ，１１０Ｂ，１１０Ｄ，及び１１０Ｇを含む。除外ＳＰＴに属するノードは、ネットワークエレメント１１０Ａ及び１１０Ｇである（ネットワークエレメント１１０Ｄは、除外ＳＰＴの一部ではない）。計算を実行しているネットワークエレメントがこうしたノードである場合、フローは動作５３５へ移り、そうでなければフローは動作５５０へ移る。
【００４５】
動作５３５において、計算を実行しているネットワークエレメントは、自身が除外ＳＰＴの中に除外ノードから上流でないネクストホップを有するかを判定する。言い換えれば、動作５３５において、当該ネットワークエレメントは、自身がマージ点（ＢＳＰ−ＭＰ）であるかを判定する。別の言い方をすれば、ネットワークエレメントが除外ＳＰＴ上にあって且つ障害点を横断しない選択ノードへの最短パスＬＤＰ  ＬＳＰに属する場合、それはマージ点であり、フローは動作５４０へ移ることになる。例えば、図３を参照すると、ネットワークエレメント１１０Ａは、除外ＳＰＴ上であってネットワークエレメント１１０Ｃの上流にあり、ネットワークエレメント１１０Ｃからの上流ではないネクストホップ（ネットワークエレメント１１０Ｅである）を有し、よってマージ点である。当該ノードがマージ点であればフローは動作５４０へ移り、そうでなければフローは動作５６５へ移る。
【００４６】
動作５４０において、ネットワークエレメントは、障害条件が現実化した場合のバックアップＬＤＰ  ＬＳＰのために、ＰＬＲへラベルを配布する。バックアップＬＳＰは、ＰＬＲと当該ネットワークエレメントとの間の現存するＬＳＰである。例えば、図３を参照すると、ネットワークエレメント１１０Ａは、ネットワークエレメント１１０ＢへラベルＬ：Ａ，Ｆを配布する。ラベルＬ：Ａ，Ｆは、トラフィックをＬＳＰセグメント１６０へマージして当該トラフィックをネットワークエレメント１１０ＦへのＳＰＴ  ＬＳＰ１７０へリダイレクトする際にネットワークエレメント１１０Ａによって使用されるラベルである。フローは、動作５４０から動作５６５へ移る。
【００４７】
動作５５０において、動作を実行中のネットワークエレメントがＰＬＲであるならばフローは動作５５５へ移り、そうでなければフローは動作５６５へ移る。動作５５５において、ネットワークエレメントは、マージ点から受信されるラベルを上記プレフィクスを宛て先とするパケットのラベルスタック内でマージ点に到達するために使用されるラベルの下方に含めるための、除外ノードについての障害トリガアクションをインストールする。例えば、図３を基準とすると、ネットワークエレメント１１０Ｂは、ネットワークエレメント１１０Ｃが障害を起こした後に、ネットワークエレメント１１０ＢがラベルＬ：Ｂ，Ｆを伴って到来するトラフィックを（ネットワークエレメント１１０Ａにより割当てられる）ラベルＬ：Ａ，Ｆと（ネットワークエレメント１１０Ａにより割当てられる）ラベルＬ：Ａ，ＡとでラベリングしてＬＳＰセグメント１５１上で送信するような、障害トリガアクションをインストールする。よって、（ネットワークエレメント１１０Ｃの障害についてＰＬＲとして動作している）ネットワークエレメント１１０Ｂの転送エントリ（例えば、ＩＬＭ内のエントリ）は、ネットワークエレメント１１０Ｃの障害が起こるとＬＳＰセグメント１４１上で受信されるプレフィクスＦへのトラフィックが（バックアップ最短パスＬＳＰとして動作している）ＬＳＰセグメント１５１へスイッチングされるように変更される。
【００４８】
動作５６５において、選択された宛て先ノードへの計算されたＳＰＴ内に他のノードが存在するかが判定される。他のノードが存在する場合、フローは動作５２０へ戻り、計算されたＳＰＴから除外されるものとして他のノードが選択される。他のノードが存在しない場合、フローは動作５７０へ移り、ネットワーク内に他の宛て先ノードが存在するかが判定される。他のノードがある場合、フローは動作５１０へ戻り、他のノードが宛て先のために選択される。他のノードが無い場合、フローは動作５７５へ移り、プロセスが終了する。
【００４９】
図２及び図３に示した例において、ＰＬＲとＢＳＰ−ＭＰとの間の最短パスＬＳＰは、ＰＬＲにおける障害の際に同時には影響を受けない。言い換えれば、ＰＬＲにおける障害エンティティ及びＰＬＲからＢＳＰ−ＭＰへの最短パスに沿った他のエンティティの双方を含む共有リスクリンクグループ（ＳＲＬＧ）はない。ＰＬＲからＢＳＰ−ＭＰの間に利用可能な最短パスＬＳＰがないという１つの実施形態において、バックアップＳＰパスを生成するために再帰的な技法が適用されてよい。再帰的な適用の結果として、最短パスからバックアップＳＰパスが導出されるごとに１つ、ラベルスタックは増加する。
【００５０】
１つの実施形態において、ＰＬＲからＢＳＰ−ＭＰの間に利用可能な最短パスＬＳＰがなければ、ＢＳＰ−ＭＰからスタートしてＳＰ  ＬＳＰとは異なるバックアップＳＰ  ＬＳＰに沿った最初のノード（ここでは、縫合ノード（stitching  node）という）が、ＰＬＲに向けて上流へホップバイホップで、ＢＳＰ  ＬＳＰについての別個のラベル（障害が起こらなければ当該ＬＳＰは採用されないことになるため、ここでは代替ラベルという）を広告する。縫合ノードは、（上記最初のノードからＰＬＲへの）非最短パスＬＳＰからのパケットを（縫合ノードからＢＳＰ−ＭＰへの）最短パスＬＳＰへ送信するラベルスワップ動作をインストールする。なお、縫合ノードからＢＳＰ−ＭＰへのバックアップＳＰ  ＬＳＰに沿ったパスは最短パスＬＳＰを辿り、同じデータプレーンのステートを有する。これは、追加的なスタッキングが要求されないことを保証する。但し、縫合ノードからＰＬＲへ、データプレーンのステートが要求される
【００５１】
図６は、図１のネットワークを示しており、リンク１２２及びリンク１２４に障害がある（例えば、リンク１２２及び１２４はＳＲＬＧの一部である）場合にネットワークエレメント１１０Ｆに接続されるプレフィクスＦに到達するためのＢＳＰ  ＬＳＰを、ネットワークエレメントが構成する。図２と同様、マージ点（ＢＳＰ−ＭＰ）はネットワークエレメント１１０Ａであり、ＰＬＲはネットワークエレメント１１０Ｃである（プレフィクスＦを宛て先とするトラフィックについてリンク１２２及び１２４の障害を想定する）。ネットワークエレメント１１０Ｄは、縫合ノードである。
【００５２】
ＰＬＲ（ネットワークエレメント１１０Ｃ）からＢＳＰ−ＭＰ（ネットワークエレメント１１０Ａ）への障害を横断しない最短パスＬＳＰは（最短パスＬＳＰの一部であろうリンク１２２を理由として）存在しないため、ネットワークエレメント１１０Ｄは、ネットワークエレメント１１０ＣへのプレフィクスＦについての代替ラベルＬ：Ｄ，Ｆ´を広告する。プレフィクスＦへ向けられるトラフィックについて（その障害を想定）、ネットワークエレメント１１０Ｃは、（ネットワークエレメント１１０Ｂからの）ＬＳＰセグメント１４２からのトラフィックをＬＳＰセグメント１５０を介してネットワークエレメント１１０Ｂへスイッチングし返すためのラベルスタッキングを使用する。ＬＳＰセグメント１５０は、ＰＬＲからネットワークエレメント１１０Ａ（ＢＳＰ−ＭＰ）への最短パスＬＳＰのセグメントであり、バックアップ最短パスＬＳＰのセグメントとして使用される。ネットワークエレメント１１０Ｃは、障害を通過しないバックアップＳＰ−ＬＳＰのためにネットワークエレメント１１０Ｄが使用するラベル上に、ネットワークエレメント１１０Ｄへ到達するためのラベルをスタッキングする。ネットワークエレメント１１０Ｂは、ＬＳＰセグメント１５０からのトラフィックをバックアップＬＳＰセグメント６１５へラベルスイッチングする。ネットワークエレメント１１０Ｄ（縫合ノード）は、（ＢＳＰ  ＬＳＰの一部である）ＬＳＰセグメント６１５からのトラフィックを（ＢＳＰ  ＬＳＰの一部である）ＬＳＰセグメント６２０へラベルスイッチングする。ネットワークエレメント１１０Ａ（ＢＳＰ−ＭＰ）は、ＬＳＰセグメント６２０からのトラフィックをＬＳＰセグメント１６０（障害を通過しないＳＰ  ＬＳＰ）へラベルスイッチングし、よってトラフィックが復旧する。
【００５３】
ネットワークエレメント１１０Ｃは、リンク１２２及び１２４の障害のための障害アクションを、まずラベルＬ：Ｃ，ＦをＬ：Ｄ，Ｆへスワップし、そしてネットワークエレメント１１０Ｄへの最短パスＬＳＰのためのラベル（ラベルＬ：Ｂ，Ｄ）をプッシュするように、（例えば自身のＩＬＭのエントリ内に）予めインストールする。ネットワークエレメント１１０Ｂは、Ｌ：Ｂ，Ｄというアウターラベルを有するパケットの受信後に当該ラベルがラベルＬ：Ｄ，Ｄへスイッチングされてネットワークエレメント１１０ＤへＬＳＰセグメント６１５上で送信されることになるようなデータプレーンのステートを含む。ネットワークエレメント１１０Ｄは、Ｌ：Ｄ，ＤというアウターラベルとＬ：Ｄ，Ｆ´というインナーラベルとを有するパケットの受信後にネットワークエレメント１１０Ｄが当該パケットをラベルＬ：Ａ，Ｆと共にＬＳＰセグメント６２０へスイッチングするようなデータプレーンのステートを含む。ネットワークエレメント１１０Ａは、Ｌ：Ａ，Ｆというラベルを有するパケットをラベルＬ：Ｅ，Ｆと共にＬＳＰセグメント１６０へスイッチングさせるようなデータプレーンのステートを含む。ネットワークエレメント１１０Ｅは、Ｌ：Ｅ，Ｆというラベルを有するパケットをラベルＬ：Ｆ，Ｆと共にＬＳＰセグメント１６１へラベルスイッチングさせるようなデータプレーンのステートを含む。
【００５４】
例示によれば、リンク１２２及び１２４の障害がある場合、プレフィクスＦについてネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｆへ流れるトラフィックは、次のようなパスを辿る：（ラベルＬ：Ｂ，Ｆを伴ってＬＳＰセグメント１４１上で）ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ｂへ、（ラベルＬ：Ｂ，ＦのラベルＬ：Ｃ，Ｆのためのスワップを伴ってＬＳＰセグメント１４２上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ｃへ、（ラベルＬ：Ｃ，ＦのラベルＬ：Ｄ，Ｆ´のためのスワップとラベルＬ：Ｂ，Ｄのプッシュとを伴ってＬＳＰセグメント１５０上で）ネットワークエレメント１１０Ｃからネットワークエレメント１１０Ｂへ、（ラベルＬ：Ｂ，ＤのラベルＬ：Ｄ，Ｄのためのスワップを伴って（ラベルＬ：Ｄ，Ｆ´はラベルスタック上で維持され）ＬＳＰセグメント６１５上で）ネットワークエレメント１１０Ｂからネットワークエレメント１１０Ｄへ、（ラベルＬ：Ｄ，Ｆ´のラベルＬ：Ａ，Ｆのためのスワップを伴ってＬＳＰセグメント６２０上で）ネットワークエレメント１１０Ｄからネットワークエレメント１１０Ａへ、（ラベルＬ：Ａ，ＦのラベルＬ：Ｅ，Ｆのためのスワップを伴ってＬＳＰセグメント１６０上で）ネットワークエレメント１１０Ａからネットワークエレメント１１０Ｅへ、（ラベルＬ：Ｅ，ＦのラベルＬ：Ｆ，Ｆのためのスワップを伴ってＬＳＰセグメント１６１上で）ネットワークエレメント１１０Ｅからネットワークエレメント１１０Ｆへ。
【００５５】
図２はラベルＬ：Ｄ，Ｆ´上のラベルＬ：Ｄ，Ｄというラベルスタックをネットワークエレメント１１０Ｄが受信することを示しているものの、最終前ホップポッピング（ＰＨＰ）が使用される状況ではパケットがネットワークエレメント１１０Ｄにおいて受信される際にネットワークエレメント１１０Ｄに到達するためのラベル（ラベルＬ：Ｄ，Ｄ）が既にポッピングされていてもよいことが理解されるべきである。
【００５６】
１つの実施形態において、ＬＤＰ  ＦＲＲを確立するために、シグナリングの拡張が定義される。例えば、障害エレメント（Failure  Element）ＴＬＶ（Type,  Length,  Value）は、ＢＳＰ  ＬＳＰが保護しようとする障害を識別する。それは、そのメッセージがＢＳＰ  ＬＳＰのためのものであるかを識別する。図７は、１つの実施形態に係る例示的な障害エレメントＴＬＶ７１０を示している。障害エレメントタイプ（Failure  Element  Type）フィールド７１５は、それがリンク障害、ノード障害又はＳＲＬＧ障害のいずれであるかを示す。障害エレメント識別子（Failure  Element  Identifier）フィールド７２０は、障害の識別子を示す。リンクは、その端点（ends）のうち１つのＩＰアドレスによって識別される。ノードは、自身のループバックＩＰアドレスによって識別される。ＳＲＬＧは、ＲＦＣ４２０２において定義された通りに識別される。
【００５７】
バックアップパスベクトルＴＬＶは、ＢＳＰ−ＭＰからＰＬＲへのＢＳＰ  ＬＳＰによって辿られるパスを示す。それは、パスに沿った各ＬＳＲのループバックアドレスを含む。最初のアドレスはＢＳＰ−ＭＰであり、最後のアドレスはＰＬＲのアドレスである。図８は、１つの実施形態に係る例示的なバックアップパスベクトルＴＬＶ８１０を示している。
【００５８】
トンネルド転送等価クラス（ＦＥＣ）ＴＬＶは、トラフィックを再ルーティングするためにそのＦＥＣについてＢＳＰ−ＭＰにより広告されるラベルを、ＰＬＲへ示す。このラベルは、ＢＳＰ  ＬＳＰを通じたトンネリングのために使用されるべきである。中間ノードは、トンネリングされるＦＥＣについていかなるデータプレーンステートをもインストールしない。図９は、１つの実施形態に係る例示的なバックアップパスベクトルＴＬＶ９１０を示している。
【００５９】
例示によれば、ＬＳＲは、障害と、自身がＢＳＰ−ＭＰとして動作することのできる対象のプレフィクスとを計算し、ＢＳＰ  ＬＳＰについてのラベルマッピングを、障害エレメントＴＬＶとバックアップパスベクトルＴＬＶとを含めることにより広告する。ラベルスタッキングが使用される場合（例えば、障害を横断しないＰＬＲからＢＳＰ−ＭＰへの既存の最短パスＬＳＰがある場合）、ＢＳＰ−ＭＰは、トンネリングされるプレフィクスについてのラベルマッピングを、障害エレメントＴＬＶ及びバックアップパスベクトルＴＬＶに加えてトンネリングプレフィクスＴＬＶを含めることにより広告する。ラベルスタッキングが使用され、障害を横断しないＰＬＲからＢＳＰ−ＭＰへの既存の最短パスＬＳＰがある場合、中間のＬＳＲは、ＢＳＰ  ＬＳＰにおいてラベルがトンネリングされるため、ラベルを割当てない；但し、それらは、バックアップパスベクトルＴＬＶを用いてラベルマッピングを転送する。ＰＬＲは、当該ラベルを用いて障害トリガのためのアクションをインストールする。
【００６０】
図１０は、１つの実施形態に従ってＬＤＰ  ＦＲＲを実装する例示的なネットワークエレメントを示す。ネットワークエレメント１０００は、制御プレーン１０１０とデータプレーン１０５０（転送プレーン又はメディアプレーンと呼ばれることもある）とを含む。制御プレーン１０１０は、データ（例えば、パケット）がどのようにルーティングされるか（例えば、データのためのネクストホップ及び当該データのためのアウトゴーイングポート）を決定し、データプレーン１０５０は、当該データを転送することを担当する。制御プレーン１０１０は、ＩＧＰ（Interior  Gateway  Protocol）モジュール１０１５及びＬＤＰ（Label  Distribution  Protocol）モジュール１０２０を含む。ＩＧＰモジュール１０１５は、ＯＳＰＦ（Open  Shortest  Path  First）若しくはＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）などのリンクステートプロトコルを実行中であり、又はＲＩＰ（Routing  Information  Protocol）などの他のプロトコルを実行中であってよい。ＩＧＰモジュール１０１５は、他のネットワークエレメントと通信してルートを交換し、１つ以上のルーティングメトリックに基づいてそれらルートを選択する。選択されたＩＧＰルートは、ＲＩＢ（Routing  Information  Base）１０２５内に記憶される。ＩＧＰモジュールは、選択されずＲＩＢ１０２５内に記憶されなかったルートエントリをローカルＲＩＢ（例えば、ＩＧＰローカルＲＩＢ）内に記憶させることもできる。
【００６１】
ＬＤＰモジュール１０２０は、自身のピア（ＬＤＰピア）との間でラベルマッピング情報を交換する。例えば、ＬＤＰモジュール１０２０は、ラベルマッピングメッセージを生成し、自身のピアからラベルマッピングメッセージを受信し得る。ＬＤＰモジュール１０２０は、ラベルパケットを転送する目的において、ＩＧＰモジュール１０１５によってＲＩＢ１０２５に提供される基礎としてのルーティング情報に依拠する。ＬＤＰモジュール１０２０は、ラベルを割当て、ラベルパケットの転送に関連する他の情報（ＮＨＬＦＥ情報、ＩＬＭ（Incoming  Label  Map）情報、ＦＴＮ情報）を、ＭＰＬＳ情報ベース１０３０内に記憶させる。ＬＤＰモジュール１０２０は、ここで説明したＬＤＰ−ＦＲＲプロセスをサポートするために、ＬＤＰモジュール１０２０の機能性を拡張するＬＤＰ−ＦＲＲモジュール１０２２を含む。
【００６２】
制御プレーン１０１０は、ＲＩＢ１０２５及びＭＰＬＳ情報ベース１０３０に基づいて、データプレーン１０５０をルート情報でプログラミングする。具体的には、ＲＩＢ１０２５からの何らかの情報がＦＩＢ（Forwarding  Information  Base）１０５５にプログラミングされ、ＭＰＬＳ情報ベース１０３０からの何らかの情報がＩＬＭ構造１０６０、ＮＨＬＦＥ構造１０６５及びＦＴＮ構造１０７０にプログラミングされる。例えば、ラベルや障害アクションなどが、障害が発生した場合にトラフィックが迅速に（例えばラインレートで）ＢＳＰ  ＬＳＰに従って再ルーティングされ得るように適切に、データプレーン１０５０のＩＬＭ構造１０６０及びＮＨＬＦＥ構造１０６５の１つ以上にプログラミングされる。
【００６３】
１つの実施形態において、ネットワークエレメント１０００は、（転送カードと呼ばれることもある）１つ以上のラインカードのセットと、１つ以上の制御カードのセットとを含む。ラインカード及び制御カードのセットは、１つ以上のメカニズム（例えば、ラインカードを結合する第１のフルメッシュ及びカードの全てを結合する第２のフルメッシュ）を通じて共に結合される。ラインカードのセットは、典型的には、データプレーンを作り上げ、パケットを転送する際に使用されることになるＦＩＢ１０５５、ＩＬＭ１０６０、ＮＨＬＦＥ１０６５及びＦＴＮ１０７０を各々記憶し得る。具体的には、ＦＴＮ１０７０は、ラベリングされておらず（例えば、入口ＬＳＲにおいてＭＰＬＳドメイン外から受信される）但し転送前にラベリングされるべきパケットを転送するために使用される。ＩＬＭ１０６０は、ラベリングされたパケットを転送するために使用される。制御カードは、典型的には、ＩＧＰモジュール１０１５、ＬＤＰモジュール１０２０を含むルーティングプロトコルを実行し、ＲＩＢ１０２５及びＭＰＬＳ情報ベース１０３０を記憶する。
【００６４】
ここで使用されるように、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジ）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、終端局）と通信可能に相互接続するハードウェア及びソフトウェアを含む１体のネットワーキング機器である。いくつかのネットワークエレメントは、複数のネットワーキング機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２アグリゲーション、セッションボーダー制御、サービス品質（Quality  of  Service）、及び／又は加入者管理）についてのサポートを提供し、及び／又は複数のアプリケーションサービス（例えば、データ、音声、及びビデオ）についてのサポートを提供する「マルチサービスのネットワークエレメント（multiple  services  network  elements）」である。加入者端局（subscriber  end  stations）（例えば、サーバ、ワークステーション、ラップトップ、ネットブック、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、ＶＯＩＰ（Voice  Over  Internet  Protocol）電話、ユーザ機器、端末、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲームシステム、セットトップボックス）は、インターネット上で提供されるコンテンツ／サービス及び／又はインターネット上にオーバーレイされる（例えば、インターネットを通じてトンネリングされる）ＶＰＮ（virtual  private  networks）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的に、サービスプロバイダ若しくはコンテンツプロバイダに属する１つ以上の終端局（例えば、サーバ端局（server  end  stations））又はピアツーピアサービスに参加する終端局によって提供され、及び、例えば、パブリックウェブページ（例えば、無料コンテンツ、ストアフロント、検索サービス）、プライベートウェブページ（例えば、電子メールサービスを提供する、ユーザ名／パスワードによりアクセスされるウェブページ）、及び／又はＶＰＮ上の企業ネットワークを含み得る。典型的に、加入者端局は、（例えば、（無線又は有線で）アクセスネットワークに結合される顧客構内の機器を通じて）エッジネットワークエレメントに結合され、当該エッジネットワークエレメントは、（例えば、１つ以上のコアネットワークエレメントを通じて）他のエッジネットワークエレメントに結合され、当該他のエッジネットワークエレメントは、他の終端局（例えば、サーバ端局）に結合される。
【００６５】
ここで説明される通り、命令は、ある動作を実行するように構成され若しくは所定の機能性を有する特定用途向け集積回路（ＡＳＩＣ：application  specific  integrated  circuit）などのハードウェアの特定の構成、又は非一時的なコンピュータ読取可能な媒体において具現化されるメモリに記憶されるソフトウェア命令を指し得る。従って、図において示される技法は、１つ以上の電子デバイス（例えば、終端局、ネットワークエレメント）上に記憶され及び実行されるコード及びデータを用いて実装されることができる。そのような電子デバイスは、非一時的なコンピュータ読取可能な記憶媒体（例えば、磁気ディスク；光ディスク；ＲＡＭ（random  access  memory）；ＲＯＭ（read  only  memory）；フラッシュメモリデバイス；相変化メモリ）及び一時的なコンピュータ読取可能な通信媒体（例えば、電気的、光学的、音響的又は他の形式の伝搬信号−搬送波、赤外線信号、デジタル信号など）といったコンピュータ読取可能な媒体を用いて、コード及びデータを記憶し及び（内部的に及び／又はネットワーク上で他の電子デバイスと）通信する。また、そのような電子デバイスは、典型的に、１つ以上のストレージデバイス（非一時的な機械読取可能な記憶媒体）、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、及び／又はディスプレイ）、並びにネットワーク接続といった１つ以上の他のコンポーネントに結合される１つ以上のプロセッサのセットを含む。プロセッサのセットと他のコンポーネントとの結合は、典型的に、１つ以上のバス及び（バスコントローラとも呼ばれる）ブリッジを介する。従って、所与の電子デバイスのストレージデバイスは、典型的に、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明のある実施形態のうちの１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの様々な組み合わせを用いて実装されてよい。
【００６６】
本発明はいくつかの実施形態の観点から説明されてきたが、本発明は説明された実施形態に限定されず、添付の特許請求の範囲の思想及び範囲内で修正及び変形と共に実践されることができることを、当業者は認識するであろう。従って、上記説明は、限定ではなく例示として見なされるべきである。
【図１】
0005966001.tif 000002
【図２】
0005966001.tif 000003
【図３】
0005966001.tif 000004
【図４】
0005966001.tif 000005
【図５】
0005966001.tif 000006
【図６】
0005966001.tif 000007
【図７】
0005966001.tif 000008
【図８】
0005966001.tif 000009
【図９】
0005966001.tif 000010
【図１０】
0005966001.tif 000011