(57)【要約】  ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいてＬＤＰ（Label  Distribution  Protocol）の収束時間を改善するための方法が説明される。階層的ＬＳＰが確立されて、出口ＬＳＲに帰属させられるＦＥＣに属するパケットが伝送される。階層的ＬＳＰは、出口ＬＳＲに帰属させられるＦＥＣの各々に共通し、入口ＬＳＲから１つ以上の中間ＬＳＲを介して出口ＬＳＲへのパスを形成する出口ＬＳＲ  ＬＳＰを含む。出口ＬＳＲ  ＬＳＰは、出口ＬＳＲに帰属させられるＦＥＣを宛先とするパケットをラベルスイッチングする場合に用いられる。階層的ＬＳＰは、各ＦＥＣについての一意のＦＥＣ  ＬＳＰも含み、当該ＦＥＣ  ＬＳＰは、出口ＬＳＲによってパケットを識別し及び当該ＦＥＣに転送するために用いられる。出口ＬＳＲに到達するための入口ＬＳＲのネクストホップを変化させるトポロジー変化に応じて、入口ＬＳＲは転送構造におけるエントリを変更して、出口ＬＳＲ  ＬＳＰへのネクストホップを変化させ、ＦＥＣ  ＬＳＰについての如何なる転送構造エンティティも実質的に変更しない。トポロジー変化の後の転送構造の変更の低減を通じて、ＬＤＰの収束時間が低減される。【選択図】図１
2013541896.tif 000002
【特許請求の範囲】
【請求項１】
ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいてＬＳＲ（Label  Switched  Router）として動作する第１のネットワークエレメントにおけるＬＤＰ（Label  Distribution  Protocol）の収束時間を改善するための方法であって、当該方法は、
複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）についての階層的ＬＳＰ（Label  Switched  Path）を確立するステップと、
各ＦＥＣについての当該階層的ＬＳＰは、
前記ＦＥＣの各々について共通し、前記複数のＦＥＣについての出口ＬＳＲとして動作している第２のネットワークエレメントへのパスを形成し、前記ＭＰＬＳネットワークにおいてパケットをラベルスイッチングする場合に用いられる出口ＬＳＲ  ＬＳＰ、並びに、
パケットを識別し及び前記ＦＥＣに転送するために前記第２のネットワークエレメントによって用いられる一意のＦＥＣ  ＬＳＰ、
を含むことと、
前記出口ＬＳＲ  ＬＳＰについての前記第１のネットワークエレメントのネクストホップを変化させるトポロジー変化に応答して、前記ＦＥＣ  ＬＳＰについてのいかなる転送構造エントリも実質的に変更することなく、前記出口ＬＳＲ  ＬＳＰについての少なくとも前記ネクストホップを変化させるために転送構造を変更するステップと、
を含み、
それにより、前記トポロジー変化の後の転送構造の変更の低減を通じて、ＬＤＰの収束時間が改善される、方法。
【請求項２】
前記第１のネットワークエレメントは入口ＬＳＲとして動作し、前記階層的ＬＳＰを確立する前記ステップは、
中間ＬＳＲとして動作する第３のネットワークエレメントから、複数のラベルマッピングメッセージを受信するステップと、
当該複数のラベルマッピングメッセージは、
前記第２のネットワークエレメントのＩＰアドレスにマッピングされ、前記第３のネットワークエレメントによって値が割り当てられるラベルを示す第１の出口ＬＳＲラベルマッピングメッセージ、及び、
前記複数のＦＥＣの各々についての一意の階層的ラベルマッピングメッセージ、
を含むことと、
前記階層的ラベルマッピングメッセージの各々は、当該ＦＥＣにマッピングされる前記出口ＬＳＲによって発信されるラベルを示し、当該ラベルを発信した前記出口ＬＳＲのＩＤも示すことと、
示された前記ラベルが前記複数のＦＥＣのうちのいずれかを宛先とするアウトゴーイングパケットについてのラベルスタックにプッシュされ、当該パケットが前記第３のネットワークエレメントに送信されることになるように、前記出口ＬＳＲラベルマッピングメッセージに基づいて転送構造に出口ＬＳＲラベルエントリをインストールするステップと、
一意の階層的ラベルマッピングメッセージ各々について、示された前記ラベルが当該ＦＥＣを宛先とするアウトゴーイングパケットについてのラベルスタックにプッシュされ、前記出口ＬＳＲラベルエントリがアクセスされることとなるように、前記階層的ラベルマッピングメッセージに基づいて前記転送構造に階層的ラベルエントリをインストールするステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記第２のネットワークエレメントへの別のネクストホップを提供する中間ＬＳＲとして動作する第４のネットワークエレメントから複数のラベルマッピングメッセージを受信するステップ、
をさらに含み、
当該複数のラベルマッピングメッセージは、
前記第２のネットワークエレメントのＩＰアドレスにマッピングされ、前記第４のネットワークエレメントによって値が割り当てられるラベルを示す第２の出口ＬＳＲラベルマッピングメッセージ、及び
前記複数のＦＥＣについての前記一意の階層的ラベルマッピングメッセージ、
を含み、
前記トポロジー変化は、前記出口ＬＳＲ  ＬＳＰについての前記第１のネットワークエレメントの前記ネクストホップを、前記第３のネットワークエレメントから前記第４のネットワークエレメントに変化させ、
前記出口ＬＳＲ  ＬＳＰについての少なくとも前記ネクストホップを変化させるために前記転送構造を変更する前記ステップは、前記第４のネットワークエレメントによって割り当てられる前記ラベルが前記複数のＦＥＣのうちのいずれかを宛先とする前記アウトゴーイングパケットにプッシュされ、当該パケットが前記第４のネットワークエレメントに送信されることになるように、前記転送構造における前記出口ＬＳＲラベルエントリを変化させることを含む、請求項２に記載の方法。
【請求項４】
前記複数の終端局うちの第１の終端局を宛先とする、ラベル無しのパケットを受信するステップと、
前記パケットにおける前記宛先ＩＰアドレスに基づいて、前記第１の終端局の前記ＦＥＣを判定するステップと、
前記ＦＥＣに基づいて、前記階層的ラベルエントリにアクセスするステップと、
アクセスされる前記階層的ラベルエントリにおいて示される前記ラベルを、前記パケットについてのラベルスタックにプッシュするステップと、
アクセスされる前記階層的ラベルエントリによって示される前記出口ＬＳＲラベルエントリにアクセスするステップと、
アクセスされる前記出口ＬＳＲラベルエントリにおいて示される前記ラベルを、前記パケットについての前記ラベルスタックにプッシュするステップと、
前記出口ＬＳＲラベルエントリにおいて識別される前記ネクストホップへ、ラベル有りの前記パケットを送信するステップと、
をさらに含む、請求項２に記載の方法。
【請求項５】
前記トポロジー変化は、リンク障害、ノード障害、メトリックの変化、及び前記第２のネットワークエレメントへのより最適なパスを有する新たなルート、のうちの１つである、請求項１に記載の方法。
【請求項６】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいて出口ＬＳＲ（Label  Switched  Router）として動作する第１のネットワークエレメントにおいて、入口ＬＳＲとして動作する第２のネットワークエレメントからの中間ＬＳＲとして動作する１つ以上の第３のネットワークエレメントのセットを介する前記第１のネットワークエレメントへの階層的ＬＳＰ（Label  Switched  Path）を確立するためにラベルマッピングメッセージを発信するための方法であって、前記方法は、
前記第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成するステップと、
前記第１のネットワークエレメントが出口となる複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）の各々について、当該ＦＥＣについて前記第１のネットワークエレメントによって発信されるラベルを示し、前記第１のネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージを生成するステップと、
前記出口ＬＳＲラベルマッピングメッセージ及び前記階層的ラベルマッピングメッセージを、前記第１のネットワークエレメントの１つ以上のピアに送信して、前記第１のネットワークエレメントに到達するためのパスを定義するアウターＬＳＰ、並びにパケットを識別し及び当該ＦＥＣに転送するために前記第１のネットワークエレメントによって用いられる当該ＦＥＣに固有のインナーＬＳＰを含む、前記複数のＦＥＣの各々についての前記階層的ＬＳＰの確立を可能にするステップと、
を含み、
それにより、前記第２のネットワークエレメントが、前記インナーＬＳＰのうちのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、前記アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、前記第１のネットワークエレメントへの到達可能性に影響を及ぼすトポロジー変化に対処することを、前記階層的ＬＳＰが可能にする、方法。
【請求項７】
前記出口ＬＳＲラベルマッピングメッセージに含まれる前記ラベルは、ＮＵＬＬラベルであり、前記第１のネットワークエレメントの前記ＩＰアドレスは、前記第１のネットワークエレメントのループバックＩＰアドレスである、請求項６に記載の方法。
【請求項８】
前記階層的ラベルマッピングメッセージのうちの少なくとも１つは、前記第２のネットワークエレメントからのラベル要求メッセージを受信することに応じて生成される、請求項６に記載の方法。
【請求項９】
前記階層的なラベルマッピングメッセージは、階層的ラベルＴＬＶ（type-length-value）を含み、当該階層的ラベルＴＬＶは、
前記ＦＥＣについて前記第１のネットワークエレメントによって発信される前記ラベルを含むジェネリックラベルサブＴＬＶと、
前記第１のネットワークエレメントの前記ＩＰアドレスを含むＦＥＣサブＴＶＬと、
を含む、
請求項６に記載の方法。
【請求項１０】
前記ＦＥＣのうちの少なくとも１つについての前記階層的ラベルマッピングメッセージのうちの少なくとも１つは、当該ＦＥＣについてのメトリックタイプ及びメトリック値を含む、請求項６に記載の方法。
【請求項１１】
ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいて入口ＬＳＲ（Label  Switched  Router）として動作して、当該ＭＰＬＳネットワークにわたって終端局に属するパケットを階層的ＬＳＰ（Label  Switched  Path）を用いて伝送するネットワークエレメントであって、当該ネットワークエレメントは、
階層的ラベルモジュールを含む制御カード、
を備え、
当該階層的ラベルモジュールは、
ＦＥＣについて出口ＬＳＲによって発信されるラベルのマッピングを各々含み、前記出口ＬＳＲが当該ラベルを発信したことを示す、前記終端局に属する複数のＦＥＣ（Forwarding  Equivalence  Classes）について前記出口ＬＳＲから発信される階層的ラベルマッピングメッセージと、前記出口ＬＳＲのＩＰアドレスにマッピングされるラベルを各々含む、前記出口ＬＳＲから発信される出口ＬＳＲラベルマッピングメッセージと、を処理し、それにより、前記複数のＦＥＣの各々について階層的ＬＳＰが確立されるようにし、
なお、各ＦＥＣについての前記階層的ＬＳＰは、
前記ＦＥＣの各々に共通し、前記出口ＬＳＲへのネクストホップを提供する、前記出口ＬＳＲラベルマッピングメッセージに基づく出口ＬＳＲ  ＬＳＰと、
パケットを識別し及び前記ＦＥＣに転送するための情報を搬送する一意のＦＥＣ  ＬＳＰと、
を含み、
前記階層的ＬＳＰを表す１つ以上の転送構造エントリを、前記ネットワークエレメントの１つ以上のラインカードにダウンロードし、
前記出口ＬＳＲへの前記ネクストホップを変化させるトポロジー変化に応じて、前記出口ＬＳＲ  ＬＳＰについての１つ以上の転送構造エントリを変更し及び前記１つ以上のラインカードにダウンロードして、前記ＦＥＣ  ＬＳＰについての如何なる転送構造エントリも実質的に変更し及びダウンロードすること無く、前記出口ＬＳＲについての前記ネクストホップを変化させる、
ように動作し、
それにより、前記トポロジー変化の後の転送構造の変更の低減を通じて、ＬＤＰの収束時間が改善される、ネットワークエレメント。
【請求項１２】
前記階層的ラベルモジュールは、前記複数のＦＥＣに関連付けられるメトリック値を示す階層的ラベルマッピングメッセージを処理して、異なる出口ＬＳＲによって発信される単一のＦＥＣについて複数の階層的ラベルマッピングメッセージが受信される場合に、どの階層的ラベルマッピングメッセージをインストールすべきかを判定するようにさらに動作する、請求項１１に記載のネットワークエレメント。
【請求項１３】
前記階層的ラベルモジュールは、前記出口ＬＳＲに到達するためにラベルスタックにプッシュするべきラベルを示す、受信される前記出口ＬＳＲラベルマッピングメッセージに基づいて、出口ＬＳＲラベルエントリを前記１つ以上のラインカード上の転送構造にダウンロードする、請求項１１に記載のネットワークエレメント。
【請求項１４】
前記階層的ラベルマッピングメッセージの各々を処理することは、前記階層的ラベルモジュールが、当該階層的ラベルマッピングメッセージに基づいて、階層的ラベルエントリを前記１つ以上のラインカード上の転送構造にダウンロードし、それにより、前記階層的ラベルマッピングメッセージにおいて示される前記ＦＥＣを宛先とするアウトゴーイングパケットについてのラベルスタックに、示される前記ラベルがプッシュされ、前記出口ＬＳＲに到達するための前記ラベルを前記ラベルスタックにプッシュするために前記出口ＬＳＲラベルエントリがアクセスされる必要があるようにすることを含む、請求項１３に記載のネットワークエレメント。
【請求項１５】
階層的ＬＳＰを用いて前記終端局を宛先とするパケットを転送するための１つ以上のパケット処理エンティティを含む前記１つ以上のラインカードをさらに備え、当該１つ以上のパケット処理エンティティは、当該終端局のうちの１つを宛先とする、受信されるラベル無しのパケットの各々について、下記を実行することを含む、請求項１４に記載のネットワークエレメント：
前記パケットの前記宛先ＩＰアドレスに基づいて、当該終端局の前記ＦＥＣを判定すること；
当該ＦＥＣに基づいて、階層的ラベルエントリにアクセスすること；
アクセスされる前記階層的ラベルエントリにおいて示される前記ラベルを、前記パケットについてのラベルスタックにプッシュすること；
アクセスされる前記階層的ラベルエントリによって示されるように出口ＬＳＲラベルエントリにアクセスすること；
アクセスされる前記出口ＬＳＲラベルエントリにおいて示される前記ラベルを、前記パケットについての前記ラベルスタックにプッシュすること；及び
ラベル有りの前記パケットを、アクセスされる前記出口ＬＳＲラベルエントリにおいて識別されるネクストホップに送信すること。
【請求項１６】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいて、複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）についての出口ＬＳＲ（Label  Switched  Router）として動作し、前記ＦＥＣについての入口ＬＳＲとして動作する第２のネットワークエレメントからの中間ＬＳＲとして動作する１つ以上の第３のネットワークエレメントのセットを介する階層的ＬＳＰ（Label  Switched  Path）を確立するためにラベルマッピングメッセージを発信するための第１のネットワークエレメントであって、当該第１のネットワークエレメントは、
階層的ラベルモジュールを含む制御カード、
を備え、
当該階層的ラベルモジュールは、
前記第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成し、
前記複数のＦＥＣの各々について、当該ＦＥＣについて前記第１のネットワークエレメントによって発信されるラベルを示し、前記第１のネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージを生成し、
前記ＭＰＬＳネットワークを通じて伝搬されるべき、生成された前記出口ＬＳＲラベルマッピングメッセージ及び前記階層的ラベルマッピングメッセージの、前記第３のネットワークエレメントのセットへの送信を生じさせて、前記第１のネットワークエレメントの前記ＩＰアドレスに到達するためのパスを定義するアウターＬＳＰ、及びパケットを識別し及び当該ＦＥＣへ転送するために前記第１のネットワークエレメントによって用いられる当該ＦＥＣに固有のインナーＬＳＰを含む、前記ＦＥＣの各々についての階層的ＬＳＰの確立を可能にする
ように動作し、
それにより、前記第２のネットワークエレメントが、前記インナーＬＳＰのうちのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、前記アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、前記第１のネットワークエレメントへの到達可能性に影響を及ぼすトポロジー変化に対処することを、前記階層的ＬＳＰが可能にする、
第１のネットワークエレメント。
【請求項１７】
前記出口ＬＳＲラベルマッピングメッセージに含まれる前記ラベルは、ＮＵＬＬラベルであり、前記第１のネットワークエレメントの前記ＩＰアドレスは、前記第１のネットワークエレメントのループバックＩＰアドレスである、請求項１６に記載のネットワークエレメント。
【請求項１８】
前記階層的ラベルモジュールは、前記第２のネットワークエレメントからのラベル要求メッセージの受信に応じて、前記階層的ラベルマッピングメッセージのうちの少なくとも１つを生成するように動作する、請求項１６に記載のネットワークエレメント。
【請求項１９】
各階層的ラベルマッピングメッセージは、階層的ラベルＴＬＶ（type-length-value）を含み、当該階層的ラベルＴＬＶは、
前記ＦＥＣについて前記第１のネットワークエレメントによって発信される前記ラベルを含むジェネリックラベルサブＴＬＶと、
前記第１のネットワークエレメントの前記ＩＰアドレスを含むＦＥＣサブＴＶＬと、
を含む、
請求項１６に記載のネットワークエレメント。
【請求項２０】
前記階層的ラベルモジュールは、前記階層的ラベルマッピングメッセージに、前記ＦＥＣについてのメトリックタイプ及びメトリック値をさらに含める、請求項１６に記載のネットワークエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ネットワーキングの分野に関し、特に、階層的ラベルスタッキングを用いてＬＤＰの収束を改善することに関する。
【背景技術】
【０００２】
（２００７年１０月のＲＦＣ（Request  For  Comments）５０３６において説明される）ラベル配布プロトコル（ＬＤＰ：Label  Distribution  Protocol）は、ＦＥＣ（Forward  Equivalence  Classes）のラベルへのマッピングを広告するために用いられる。ＩＰプレフィックスＦＥＣは、ルーティングされるパスに沿ってラベルスイッチパス（ＬＳＰ：Label  Switched  Paths）をセットアップするために用いられる。ＬＤＰは、ＩＰプレフィックスＦＥＣについてのラベルマッピングを、ルーティングテーブルにおけるルートを用いて広告する。ネットワークにおけるＦＥＣの数が増加すると、対応してラベルの数が増加する。例えば、各々がＬＤＰを実行する複数のラベルスイッチルータ（ＬＳＲ：Label  Switched  Routers）のラベル交換ネットワークにおいて、出口ＬＳＲは、一意の出口ネクストホップの各々について非ＮＵＬＬラベルを割り当てる。各プレフィックスが一意のネクストホップを有する場合、一意のラベルはプレフィックスごとに割り当てられなければならないであろう。多くの加入局（例えば、潜在的に数千から数百万）を有する無線及び／又は有線の加入者終端シナリオにおいて、関連付けられるラベルの数は大きい。
【０００３】
プレフィックスについての出口ではないＬＳＲは、下記の技法のうちの１つを用いて、（関連付けられるラベルと共に）プレフィックスと当該プレフィックスについての出口ＬＳＲとの間の関連性を知得することができる：ＩＰルーティングテーブルを用いて、ラベルをＦＥＣについて割り当てること；リンク状態プロトコル（例えば、１９９８年４月のＲＦＣ２３２８において説明されるＯＳＰＦ（Open  Shortest  Path  First）、１９９０年２月のＲＦＣ１１４２において説明されるＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System））を実行し、又は追加的なプロトコル（例えば、２００６年１月のＲＦＣ４２７１において説明されるＢＧＰ（Border  Gateway  Protocol））を実行すること。
【０００４】
しかしながら、上記の技法は、場合によっては、可能ではなく又は好適ではないことがある。例えば、多くの場合において、冗長性のためにスタティック又はＢＦＤ（Bidirectional  Forwarding  Detection）を伴うＲＩＰ（Routing  Information  Protocol）といった単純なルーティングプロトコルをエッジＬＳＲが実行するという要件がある。例えば、比較的単純なリンク状態ルーティングプロトコルを実行するために、無線加入者端末シナリオにおける基地局ネットワークエレメントである入口ＬＳＲがネットワークプロバイダによって要求されることがある。これらのプロトコルは、ＦＥＣと出口ＬＳＲとの間に関連性を与えない。
【０００５】
また、ＩＧＰについての収束時間は比較的長い。例えば、多数のプレフィックスが存在し、これらが高いレートでルーティングテーブルに追加され及びルーティングテーブルから削除される（例えば、局間を移動するモバイル加入者は、ルーティングテーブルが比較的頻繁に変更されることを引き起こし得る）場合、ＩＧＰが収束する時間は比較的長くなる。例えば、無線ネットワーク（例えば、４Ｇ又はＬＴＥネットワーク）における典型的なエッジＬＳＲは、数十万人又は数百万人の加入者（この各々がＩＧＰにおいて一意のプレフィックスを有し得る）をサポートし得る。ＩＧＰには、収束時間を増加させ得るダンプニング（dampening）メカニズム（例えば、（例えば、ＲＦＣ２３２８に説明されるMinLSIntervalの使用による）リンク状態広告（ＬＳＡ：link  state  advertisement）生成遅延；ＬＳＡペーシングタイマ（例えば、ＲＦＣ２３２８に説明される再送信タイマ（RxmtInterval）の使用）；及びＳＰＦ（Shortest  Path  First）ダンプニングタイマ）もある。さらに、リンク状態データベース（ＬＳＤＢ：Link  State  Database）が大きい場合、ＳＰＦは、典型的なＳＰＦ実行の期間中に多くのメモリアクセスを実行し、ルートを共通のストア（例えば、ＲＩＢ（ルーティング情報ベース））にダウンロードする場合に著しい量の処理及び／又はメモリアクセス要求する。これらは全て、ＩＧＰについての収束時間を増加させる。
【０００６】
ＢＧＰなどの追加的なプロトコルを実行することは、（設備投資（ＣａｐＥｘ）及び運用コスト（ＯｐＥｘ）の双方において）間接費を追加するため、好適ではない。例えば、ＣａｐＥｘにおける間接費が含むものは、スケーラビリティ、高い可用性（availability）及び／又は冗長性などの機能（features）を開発し及び／又はサポートするために要求される開発リソース；冗長性に伴って増加する、追加的なプロトコルを実行するために必要となる余分なＣＰＵ及び／又はメモリ；フルメッシュの接続（ネットワークにおけるＬＳＲのあらゆるペア間の１つの接続）の要件が、ネットワークにおけるＬＳＲの数が増加するにつれて計算リソース（ＣＰＵサイクル、メモリ等）の量を増加させること；及び、フルメッシュが回避される場合、ネットワークエレメントの別個のタイプである、別個のルータリフレクタ（ＲＲ）を要求すること、である。ＯｐＥｘにおける間接費が含むものは、ＢＧＰがＬＳＲの各々において設定されなければならないことによる、ネットワーク設計における複雑さの導入；（典型的には別個のネットワークエレメントである）ＲＲが用いられる場合、当該ＲＲはオペレータによって維持される必要があること；及び、ＢＧＰプロトコルを設定し及び維持することが専門的かつ高価な人材の専門技術を要求すること、である。
【発明の概要】
【課題を解決するための手段】
【０００７】
階層的ＬＳＰ（Label  Switched  Path）の使用を通じてＬＤＰ（Label  Distribution  Protocol）の収束時間を改善することが、本明細書において説明される。一実施形態において、階層的ＬＳＰは、ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいて、複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）について確立される。各ＦＥＣについての階層的ＬＳＰは、ＦＥＣの各々について共通し、ＦＥＣについて出口ＬＳＲへのパスを形成し、ＭＰＬＳネットワークにおいてパケットをラベルスイッチングする場合に用いられる出口ＬＳＲ（Label  Switched  Router）ＬＳＰを含み；パケットを識別し及びＦＥＣに転送するために出口によって用いられる一意のＦＥＣ  ＬＳＰをさらに含む。出口ＬＳＲ  ＬＳＰについての第１のネットワークエレメントのネクストホップを変化させるトポロジー変化に応じて、ＦＥＣ  ＬＳＰについての如何なる転送構造エントリも実質的に変更すること無く、少なくとも出口ＬＳＲ  ＬＳＰについてのネクストホップを変化させるために転送構造が変更される。ＬＤＰの収束時間は、トポロジー変化の後の転送構造の変更の低減を通じて改善される。
【０００８】
一実施形態において、ＭＰＬＳネットワークにおいて出口ＬＳＲとして動作するネットワークエレメントは、次の動作を実行する。ネットワークエレメントは、第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成する。ネットワークエレメントが出口となる終端局に属する各ＦＥＣについて、当該ＦＥＣについてネットワークエレメントによって発信されたラベルを示し、ネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージをネットワークエレメントは生成する。出口ラベルマッピングメッセージ及び階層的ラベルマッピングメッセージは、ネットワークエレメントのピアに送信されて、ネットワークエレメントに到達するためのパスを定義するアウターＬＳＰを含み、並びにパケットを識別し及びＦＥＣに転送するためにネットワークエレメントによって用いられるＦＥＣに固有のインナーＬＳＰを含む、各ＦＥＣについての階層的ＬＳＰの確立を可能にする。階層的ＬＳＰは、インナーＬＳＰのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、出口ＬＳＲへの到達可能性に影響を及ぼすトポロジー変化に入口ＬＳＲが対処することを可能にし、それにより、ＬＤＰの収束時間を改善する。
【０００９】
一実施形態において、入口ＬＳＲとして動作するネットワークエレメントは、階層的ラベルモジュールを含む制御カードを含む。階層的ラベルモジュールは、ＦＥＣについて出口ＬＳＲによって発信されるラベルのマッピングを各々含み、出口ＬＳＲが当該ラベルを発信したことを示す、終端局に属する複数のＦＥＣについて出口ＬＳＲから発信される階層的ラベルマッピングメッセージと、出口ＬＳＲのＩＰアドレスにマッピングされるラベルを各々含む、出口ＬＳＲから発信される出口ＬＳＲラベルマッピングメッセージと、を処理し、それにより、複数のＦＥＣの各々について階層的ＬＳＰが確立されるように動作する。各ＦＥＣについての階層的ＬＳＰは、ＦＥＣの各々に共通し、出口ＬＳＲへのネクストホップを提供する出口ＬＳＲラベルマッピングメッセージに基づく出口ＬＳＲ  ＬＳＰと、パケットを識別し及びＦＥＣに転送するための情報を伝送する一意のＦＥＣ  ＬＳＰと、を含む。階層的ラベルモジュールは、階層的ＬＳＰを表す１つ以上の転送構造エントリを、ネットワークエレメントの１つ以上のラインカードにダウンロードするようにさらに動作する。出口ＬＳＲへのネクストホップを変化させるトポロジー変化に応じて、階層的ラベルモジュールは、出口ＬＳＲ  ＬＳＰについての１つ以上の転送構造エントリを変更し及び１つ以上のラインカードにダウンロードして、ＦＥＣ  ＬＳＰについての如何なる転送構造エントリも実質的に変更し及びダウンロードすること無く、出口ＬＳＲへのネクストホップを変化させるように動作する。ＬＤＰの収束時間は、トポロジー変化の後の転送構造の変更の低減を通じて改善される。
【００１０】
一実施形態において、複数のＦＥＣについての出口ＬＳＲとして動作するネットワークエレメントは、第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成するように動作する階層的ラベルモジュールを含む制御カードを備える。ＦＥＣの各々について、階層的ラベルモジュールは、当該ＦＥＣについてネットワークエレメントによって発信されたラベルを示し、ネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージを生成するように動作し、生成された出口ＬＳＲラベルマッピングメッセージ及び階層的ラベルマッピングメッセージが中間又は中継ＬＳＲとして動作する１つ以上のネットワークエレメントに送信されることを生じさせて、出口ＬＳＲとして動作するネットワークエレメントのＩＰアドレスに到達するためのパスを定義するアウターＬＳＰ、並びにパケットを識別し及び当該ＦＥＣに転送するために出口ＬＳＲとして動作するネットワークエレメントによって用いられる当該ＦＥＣに固有のインナーＬＳＰを含む、ＦＥＣの各々についての階層的ＬＳＰの確立を可能にするようにさらに動作する。階層的ＬＳＰは、インナーＬＳＰのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、出口ＬＳＲへの到達可能性に影響を及ぼすトポロジー変化に入口ＬＳＲが対処することを可能にし、それにより、ＬＤＰの収束を改善する。
【図面の簡単な説明】
【００１１】
本発明は、本発明の実施形態を説明するために用いられる下記の説明及び添付の図面を参照することによって、最も理解され得る。図面において：
【００１２】
【図１】一実施形態に係る、階層的ラベルマッピングメッセージの配布及び階層的ラベルの管理を図示するデータフロー図である。
【図２】一実施形態に係る、ＬＳＲとして動作する例示的なネットワークエレメントを、より詳細に図示するブロック図である。
【図３】一実施形態に係る、ラベルマッピングメッセージにおいて用いられる階層的ラベルマッピングについての例示的なメッセージフォーマットを図示する。
【図４】一実施形態に係る、ラベルマッピングメッセージにおいて用いられるメトリックＴＬＶについての例示的なメッセージフォーマットを図示する。
【図５】一実施形態に係る、ラベルマッピングメッセージについての例示的なメッセージフォーマットを図示する。
【図６】一実施形態に係る、ラベル要求メッセージについての例示的なメッセージフォーマットを図示する。
【図７】一実施形態に係る、特定のＦＥＣに属するパケットを伝送する場合にＬＳＰ階層が用いられるようにラベルマッピングメッセージをインストールする入口ＬＳＲの例示的な動作を図示するフロー図である。
【図８】一実施形態に係る、ＬＳＰの階層を用いる例示的なパケットフローを図示する。
【図９】一実施形態に係る、リモートＦＥＣを宛先とするパケットを受信する場合に入口ＬＳＲによって実行される例示的な動作を図示する。
【図１０】一実施形態に係る、トポロジー変化が出口ＬＳＲの到達可能性に影響を及ぼす場合に実行される例示的な動作を図示するデータフロー図である。
【図１１】一実施形態に係る、図１０に図示されるトポロジー変化の後にＬＳＰの階層を用いる例示的なパケットフローを図示する。
【発明を実施するための形態】
【００１３】
下記の説明において、多くの具体的な詳細が述べられる。しかしながら、本発明の実施形態はそれらの具体的な詳細無しに実施をされ得ることが理解される。他の例において、本説明の理解を曖昧にしないために、周知の回路、構造及び技法は詳細には示されていない。当業者は、記載される説明により、過度の実験無しに適当な機能性を実装することが可能である。
【００１４】
本明細書における「一実施形態」、「ある実施形態」、「例示的な実施形態」等への言及は、説明される実施形態が特定の機能、構造、又は特性を含み得るが、全ての実施形態が必ずしも当該特定の機能、構造、又は特性を含まなくてもよいことを示す。また、そのような表現は、必ずしも同じ実施形態に言及しない。さらに、特定の機能、構造、又は特性がある実施形態に関連して説明される場合、明示的に説明されていてもいなくても、そのような機能、構造、又は特性を他の実施形態に関連して達成することは当業者の知識の範囲内であることが提示される。
【００１５】
下記の説明及び特許請求の範囲においては、「結合される（coupled）」及び「接続される（connected）」という用語がこれらの派生語と共に用いられ得る。これらの用語は互いに同義語として意図されないことが理解されるべきである。「結合される」は、互いに直接物理的に又は電気的に接触してもしなくてもよい２つ以上のエレメントが互いに協働し又は相互作用することを示すために用いられる。「接続される」は、互いに結合される２つ以上のエレメント間における通信の確立を示すために用いられる。
【００１６】
本明細書において用いられるように、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジ、基地局等）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、終端局等）と通信可能に相互接続されるハードウェア及びソフトウェアを含むネットワーキング機器の一部品である。加入者終端局（subscriber  end  stations）（例えば、サーバ、ワークステーション、ラップトップ、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、ＶｏＩＰ（Voice  Over  Internet  Protocol）電話、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲーム機、セットトップボックス等）は、インターネット上で提供されるコンテンツ／サービス、及び／又はインターネット上に重ねられる仮想プライベートネットワーク（ＶＰＮ：virtual  private  networks）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的に、サービスプロバイダ又はコンテンツプロバイダに属する１つ以上の終端局（例えば、サーバ端局（server  end  stations））又はピアツーピアサービスに参加する終端局によって提供され、公開ウェブページ（フリーコンテンツ、ストアフロント、検索サービス等）、プライベートなウェブページ（例えば、ユーザ名／パスワードによってアクセスされる、電子メールサービスを提供するウェブページ等）、ＶＰＮ上の企業ネットワーク等を含み得る。典型的に、加入者終端局は、エッジネットワークエレメントに（例えば、（有線又は無線で）アクセスネットワークに結合される顧客構内の機器を介して）結合される。当該エッジネットワークエレメントは、（例えば、１つ以上のコアネットワークエレメントを介して）他のエッジネットワークエレメントに結合される。当該他のエッジネットワークエレメントは、他の終端局（例えば、サーバ端局）に結合される。
【００１７】
階層的ラベルスイッチパス（ＬＳＰ）を用いてＬＤＰの収束を改善するための方法及び装置が説明される。一実施形態において、ＦＥＣについての出口ＬＳＲとして動作するネットワークエレメントは、階層的ＬＳＰのアウターＬＳＰ（本明細書において出口ＬＳＲ  ＬＳＰと呼ばれることもある）に属する出口ＬＳＲのＩＰアドレス（例えば、出口ＬＳＲに属し、他のＬＳＲからのパスを有するループバックアドレス又は他のアドレス）に関連付けられるラベル（例えば、ＮＵＬＬラベル）（本明細書において、出口ＬＳＲラベルマッピングと呼ばれる）を広告することに加えて、対応する階層的ＬＳＰのインナーＬＳＰ（本明細書において、ＦＥＣ  ＬＳＰと呼ばれることもある）に属する当該ＦＥＣ（本明細書において、階層的ラベルマッピングと呼ばれる）についての当該出口ＬＳＲによって発信されるラベルを広告する。そうすることによって、ＦＥＣのその対応する出口ＬＳＲへのマッピング及びそのラベルマッピング（ラベルは当該出口ＬＳＲによって発信される）は、ＬＤＰを用いて配布される。これらのラベルマッピングを用いることで、ＬＳＰ階層が当該ＦＥＣに属するパケットを伝送するために用いられる。当該ＦＥＣについての出口ＬＳＲへのパスは低層であり、その上で（当該ＦＥＣに固有の）より高層のＬＳＰがトンネリングされる。
【００１８】
ネクストホップの変化という結果をもたらす出口ＬＳＲへのパスの変化に応じて、データプレーンにおいて再プログラミングされる必要があるのはより低層のパスに対応するネクストホップのみであり、これはＬＤＰについての収束時間を改善し、リンク又はノードの故障期間中のトラフィックロスを低減し得る。また、リンク状態ＩＧＰなどのルーティングプロトコルにおいて搬送されなければならないのは出口ＬＳＲへのラベルマッピングのみであり、これにより、当該ルーティングプロトコルにおいて搬送される情報のサイズが削減され、より速いルーティングプロトコルの収束という結果になる。
【００１９】
入口ＬＳＲとして動作しているネットワークエレメント及び中継ＬＳＲとして動作しているネットワークエレメントは、アウターＬＳＰに属するラベルマッピング（出口ＬＳＲラベルマッピング）をインストールし、これは出口ＬＳＲから入口ＬＳＲへと横断するにつれて変更され得る。例えば、中継ＬＳＲは、アウターＬＳＰに属するラベルの値を、中継ＬＳＲ自身のラベル空間のうちの１つに交換する（出口ＬＳＲのアドレスとの関連性は残存する）。階層的ＬＳＰについての入口ＬＳＲとして動作するネットワークエレメントは、ＦＥＣについての階層的ラベルマッピングをそのＮＨＬＦＥ（Next-Hop  Label  Forwarding  Entry）構造にインストールし、これにより、パケットを当該ＦＥＣに転送する場合に階層的ＬＳＰが用いられる。例えば、一実施形態において、入口ＬＳＲとして動作するネットワークエレメントは、そのＮＨＬＦＥにおけるアウターＬＳＰに対応するラベルマッピングについてのエントリ（本明細書において、出口ＬＳＲラベルマッピングエントリと呼ばれる）をインストールし、アウターＬＳＰに対応するラベルマッピングへの再帰的（recursive）ネクストホップを含む階層的ラベルマッピングについてのエントリ（本明細書において、階層的ラベルマッピングエントリと呼ばれる）をインストールする。ＦＥＣのうちの１つを宛先とするパケットを転送する場合、入口ＬＳＲは、そのＦＴＮにおけるＦＥＣをルックアップして、対応するＮＨＬＦＥ構造を判定する。結果として得られるＮＨＬＦＥは、ラベルスタックにプッシュすべきＦＥＣラベル（当該ＦＥＣについての出口ＬＳＲによって発信されるラベル）を示し、出口ＬＳＲラベルマッピングへの再帰的ネクストホップを含む。入口ＬＳＲは、ＦＥＣラベルをスタックにプッシュし、出口ＬＳＲラベルマッピングに対応するＮＨＬＦＥにアクセスする。当該出口ＬＳＲラベルマッピングは、スタックにプッシュすべきラベル、及び出口ＬＳＲに向かうネクストホップを含む。入口ＬＳＲは、当該ラベルをラベルスタックにプッシュし、出口ＬＳＲに到達するためにラベルマッピングにおいて識別されるネクストホップへラベル有りパケットを送信する。階層的ラベル有りパケットは、出口ＬＳＲ（及び、場合により、最終前の（penultimate）ホップポッピングを実行する最終前の中間ＬＳＲ）を除き、アウターラベルに基づいてネットワークにおいてラベルスイッチングされる。
【００２０】
出口ＬＳＲの到達可能性に影響を及ぼすトポロジー変化（例えば、リンクの故障（failure）、ノードの故障、メトリックの変化、新たなルートの存在等）に応じて、及び、（次善のルートではあり得るが）出口ＬＳＲへの異なるルートが存在すると仮定すると、出口ＬＳＲに帰属させられる各ＦＥＣについての各エントリではなく、アウターＬＳＰに属するＮＨＬＦＥ構造におけるラベルエントリ（出口ＬＳＲラベルマッピングエントリ）のみが変化させられる必要がある。従って、ＦＥＣについてのエントリの各々の変更を要求する代わりに、これらのＦＥＣについての出口ＬＳＲに到達することに対応するエントリのみが変更される必要がある。これは、ＬＤＰについての収束時間を改善し、リンク又はノードの故障期間中のトラフィックロスを低減し得る。
【００２１】
図１は、一実施形態に係る、階層的ラベルマッピングメッセージの配布及び階層的ラベルの管理を図示するデータフロー図である。ネットワーク１００は、ＬＳＲ（ラベルスイッチルータ）１１０、１２０、１３０、及び１４０を含み、これらは同じＭＰＬＳドメインの一部である。ＬＳＲ１１０、１２０、１３０、及び１４０の各々は、ネットワークエレメント上に実装される。ＬＳＲ１４０は、ＬＳＲ１２０とリンク１４５上で結合され、ＬＳＲ１３０とリンク１３５上で結合される。ＬＳＲ１１０は、ＬＳＲ１２０とリンク１１５上で結合され、ＬＳＲ１３０ともリンク１２５上で結合される。図示されるＬＳＲの数は例示であり、より多くの又はより少ないＬＳＲがネットワークにおいて存在し得ることが理解されるべきである。
【００２２】
図２は、一実施形態に係る、ＬＳＲとして動作する例示的なネットワークエレメントをより詳細に図示する。ネットワークエレメント２００は、制御プレーン２１０及びデータプレーン２５０（転送プレーン又はメディアプレーンと呼ばれることもある）を含む。制御プレーン２１０は、データ（例えば、パケット）がどのようにルーティングされるか（例えば、当該データについてのネクストホップ、及び当該データについてのアウトゴーイングポート）を判定し、データプレーン２５０は、当該データの転送を担う。制御プレーン２１０は、ＩＧＰ（Interior  Gateway  Protocol）モジュール２１５及びＬＤＰ（Label  Distribution  Module）２２０を含む。ＩＧＰモジュール２１５は、ＯＳＰＦ（Open  Shortest  Path  First）若しくはＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）などのリンク状態プロトコルを実行し、又はＲＩＰ（Routing  Information  Protocol）などの別のプロトコルを実行し得る。ＩＧＰモジュール２１５は、他のネットワークエレメントと通信して、ルートを交換し、それらのルートを１つ以上のルーティングメトリックに基づいて選択する。選択されたＩＧＰルートは、ＲＩＢ（Routing  Information  Base：ルーティング情報ベース）２２５に記憶される。ＩＧＰモジュール２１５は、選択されずにＲＩＢ２２５に記憶されるルートエントリがローカルＲＩＢ（例えば、ＩＧＰローカルＲＩＢ）に記憶されるようにすることもできる。
【００２３】
ＬＤＰモジュール２２０は、ラベルマッピング情報をそのピア（ＬＤＰピア）と交換する。例えば、ＬＤＰモジュール２２０は、ラベルマッピングメッセージを生成し、ラベルマッピングメッセージをそのピアから受信し得る。ＬＤＰモジュール２２０は、ラベルパケットを転送するために、ＩＧＰモジュール２１５によってＲＩＢ２２５に提供される、基礎を為すルーティング情報に依存する。ＬＤＰモジュール２２０は、ラベルを割当て、ラベルパケットを転送することに関連する他の情報（例えば、ＮＨＬＦＥ情報、ＩＬＭ（Incoming  Label  Map）情報、ＦＴＮ情報）をＭＰＬＳ情報ベース２３０に記憶する。ＬＤＰモジュール２２０は、階層的ラベルモジュール２２２を含む。当該階層的ラベルモジュール２２２は、ＬＤＰモジュール２２０の機能性を拡張して、ラベルマッピングの発信及びラベル管理の期間中に階層的ラベルをサポートし、これは本明細書で後により詳細に説明されるであろう。
【００２４】
制御プレーン２１０は、ＲＩＢ２２５及びＭＰＬＳ情報ベース２３０に基づくルート情報によりデータプレーン２５０をプログラミングする。具体的には、ＲＩＢ２２５からのある情報は、ＦＩＢ（Forwarding  Information  Base：転送情報ベース）２５５にプログラミングされ、ＭＰＬＳ情報ベース２３０からのある情報は、ＩＬＭ構造２６０、ＮＨＬＦＥ構造２６５、及びＦＴＮ構造２７０にプログラミングされる。
【００２５】
一実施形態において、ネットワークエレメント２００は、１つ以上のラインカード（転送カードと呼ばれることもある）のセット及び１つ以上の制御カードのセットを含む。ラインカード及び制御カードのセットは、１つ以上のメカニズム（例えば、ラインカードを結合する第１のフルメッシュ及び全てのカードを結合する第２のフルメッシュ）を介して互いに結合される。ラインカードのセットは、典型的にデータプレーンを構成し、各々がＦＩＢ２５５、ＩＬＭ２６０、ＮＨＬＦＥ２６５、及びＦＴＮ２７０を記憶してもよく、これらはパケットを転送する場合に用いられるであろう。具体的には、ＦＴＮ２７０は、ラベルが付けられていないパケット（例えば、これらは入口ＬＳＲにおいてＭＰＬＳドメインの外部から受信される）であるが転送前にラベルが付けられるべきであるパケットを転送するために用いられる。ＩＬＭ２６０は、ラベル有りパケットを転送するために用いられる。制御カードは、典型的に、ＩＧＰモジュール２１５、ＬＤＰモジュール２２０を含むルーティングプロトコルを実行し、ＲＩＢ２２５及びＭＰＬＳ情報ベース２３０を記憶する。
【００２６】
図１及びそれ以降の図面は、ＦＥＣ１〜Ｎをそれぞれ有する終端局１５０Ａ〜Ｎについての出口ＬＳＲとして動作するＬＳＲ１１０、入口ＬＳＲとして動作するＬＳＲ１４０、並びに中間（中継）ＬＳＲとして動作するＬＳＲ１２０及び１３０を参照しつつ説明されるであろう。従って、終端局１５０Ａ〜Ｎは、パケットの宛先であることに関して説明されるであろう（ただし、終端局１５０Ａ〜Ｎはパケットのソースでもあり得ることが理解されるべきである）。従って、終端局１５０Ａ〜Ｎに到達するために、パケットはＬＳＲ１１０を介して伝達されなければならない。ＬＳＲ１１０と終端局１５０Ａ〜Ｎとの間には他のネットワークエレメント及び／又は機器（例えば、アクセスネットワークエレメント）が存在し得ることが理解されるべきである。ＦＥＣ１〜Ｎの各々は、ＬＤＰ  ＬＳＰ上のパケットの送信について宛先を識別する識別子（例えば、ＩＰアドレスプレフィックス、ホストアドレス、疑似ワイヤ（pseudowire）を伝送するための疑似ワイヤＩＤ（ＰＷＩＤ））である。図１に示されるように、終端局１５０Ａ〜Ｎの各々は、異なるＦＥＣに関連付けられる。簡単のため、終端局１５０Ａ〜ＮについてのＦＥＣはＩＰアドレスプレフィックスであるものとして説明されるであろうが、ＦＥＣのうちの１つ以上が異なっていてもよい（例えば、ホストアドレス、ＰＷＩＤ）ことが理解されるべきである。加入者終端局又はサーバ端局のいずれかであり得る終端局１６０Ａ〜Ｌは、図１及びそれ以降の図面において、終端局１５０Ａ〜Ｎに送信されるべきパケットのソースであるものとして説明される。ただし、終端局１６０Ａ〜Ｌはパケットの宛先にもなり得ることが理解されるべきである。
【００２７】
一実施形態において、ＬＳＲ１１０、１２０、１３０、及び１４０の各々は、ネットワークエレメント２００と同様のアーキテクチャを有する一方、他の実施形態において、中間ＬＳＲ１２０及び１３０は、階層的ラベルモジュールを含まない。ＬＳＲ１１０、１２０、１３０、及び１４０の各々は、ソースから宛先までの最良のパスを判定するＩＧＰ実装（例えば、ＯＳＰＦ又はＩＳ−ＩＳ、ＲＩＰ、スタティックなどのリンク状態プロトコル）を実行する。ＬＳＲ１１０、１２０、１３０、及び１４０の各々は、ＩＧＰプロトコルによって判定されるような当該最良のパスに従うＬＤＰ実装も実行する。図１を参照すると、ＬＳＲ１４０からＬＳＲ１１０に到達するための最良のパスは、ＬＳＲ１２０を介する（破線の最良のパス１９６によって表される）。ＬＳＲ１４０からＬＳＲ１１０に到達するための第２のパスは、ＬＳＲ１３０を介する（破線の第２のパス１９８によって表される）。従って、終端局１６０Ａ〜Ｌによって送信されるトラフィックから終端局１５０Ａ〜Ｎへの最良のパスは、ＬＳＲ１２０を介して進む。
【００２８】
ＬＳＲ１１０は、階層的ラベル（Ｈ−Ｌａｂｅｌ：hierarchical  label）モジュール１１２を含み、ＬＳＲ１４０は、Ｈ−Ｌａｂｅｌモジュール１４２を含む（一実施形態において、これらのモジュールは、ＬＳＲ１１０及びＬＳＲ１４０それぞれの制御プレーンの一部である）。Ｈ−Ｌａｂｅｌモジュール１１２は、当該Ｈ−Ｌａｂｅｌモジュール１１２が出口となるＦＥＣについての階層的ラベルマッピングを含むラベルマッピングメッセージを生成し及び生じさせる。Ｈ−Ｌａｂｅｌモジュール１４２は、１つ以上の構造における階層的ラベルエントリをインストールすること、及び出口ＬＳＲ１１０への再帰的ネクストホップを伴うＦＥＣラベルをインストールすることを含めて、階層的ラベルマッピングを含む、受信されるラベルマッピングメッセージを処理する。従って、Ｈ−Ｌａｂｅｌモジュール１１２は、既存のＬＤＰラベルマッピング発信の機能性を拡張して、階層的ラベルマッピングをサポートし、Ｈ−Ｌａｂｅｌモジュール１４２は、既存のＬＤＰラベル管理の機能性を拡張して、階層的ラベルマッピングをサポートする。Ｈ−Ｌａｂｅｌモジュール１１２は階層的ラベルマッピングを発信する（実質的に、出口Ｈ−Ｌａｂｅｌモジュールとして動作する）ものとして説明され、Ｈ−Ｌａｂｅｌモジュール１４２は受信される階層的ラベルマッピングを処理する（実質的に、入口Ｈ−Ｌａｂｅｌモジュールとして動作する）ものとして説明されるが、１つ以上のモジュールが双方の機能性を含み得ることが理解されるべきである。一実施形態によれば、Ｈ−Ｌａｂｅｌモジュール１１２及び１４２は、ＬＳＲ１１０及び１４０のＬＤＰを実行するＬＤＰモジュールの一部である。一実施形態によれば、中間ＬＳＲ１２０及び１３０は、特定のＨ−Ｌａｂｅｌモジュールを含まず、代わりに標準的なＬＤＰメカニズムを実行する。ＬＳＲ１１０は、ＦＴＮ構造１６２及びＮＨＬＦＥ構造１８０をさらに含み、これらはそれぞれＨ−Ｌａｂｅｌモジュール１４２によって管理される。一実施形態において、ＦＴＮ構造１６２及びＮＨＬＦＥ構造１８０は、ＬＳＲ１４０のデータプレーンの一部であり、ＬＳＲ１４０の１つ以上のラインカード上に少なくとも部分的に記憶され得る。
【００２９】
出口ＬＳＲ１１０が出口として動作している異なるＦＥＣの各々についてのピアにラベルバインディングを広告するためにラベルマッピングメッセージを生成する場合、当該ＦＥＣを非ＮＵＬＬラベルにマッピングし、当該ラベルが出口ＬＳＲ１１０によって発信されたことを示す階層的ラベルマッピングを、出口ＬＳＲ１１０のＨ−Ｌａｂｅｌモジュール１１２は含む。また、出口ＬＳＲ１１０は、出口ＬＳＲ１１０のＩＰアドレスをラベル（例えば、ＮＵＬＬラベル）にマッピングする出口ＬＳＲラベルマッピングメッセージを含むラベルマッピングメッセージを広告する。これらのラベルマッピングは、ＬＳＲ１４０の近隣局（neighbors）の各々（例えば、ＬＳＲ１２０及び１３０）に送信される。
【００３０】
ＬＤＰを介して伝搬される階層的ラベルマッピングと出口ＬＳＲラベルマッピングとの組み合わせは、出口ＬＳＲとＦＥＣとの間の関連性を提供する。従って、たとえＩＧＰ実装がＲＩＰ又はスタティックルートなどの非リンク状態プロトコルである場合においても、出口ＬＳＲとＦＥＣとの間の関連性は取得されることができる。これは、ＩＧＰがＯＳＰＦ又はＩＳ−ＩＳといったリンク状態プロトコルを用いて情報を搬送する必要を取り除き；多数のＦＥＣ／ルートを搬送することに起因するＩＧＰ収束の減速の問題を除去し（例えば、本発明の実施形態において、ＩＧＰは、ＦＥＣではなく、ループバックアドレス及びラベルスイッチルータ間のリンクといった最小限の情報のみを搬送することができる）、それにより、より高速なＩＧＰの収束という結果になり；及び、ＢＧＰなどの別のプロトコルを実行し、ネットワーク全体にＦＥＣ情報を運搬するためにフルメッシュのＬＤＰピアを有する複雑さも回避する。従って、ラベルスイッチングは、ＦＥＣデバイスの到達可能性というよりむしろ出口ＬＳＲの到達可能性に基づく。
【００３１】
図３は、一実施形態に係る、ラベルマッピングメッセージにおいて用いられる階層的ラベルマッピングについての例示的なメッセージフォーマットを図示する。階層的ラベルＴＬＶ（type-length-value：タイプ−長さ−値）３１０は、ジェネリックラベルサブＴＬＶ３２０及びＦＥＣサブＴＬＶ３３０を値３４０として含む。階層的ラベルＴＬＶ３１０のタイプ３３５は、当該メッセージが階層的ラベルマッピングを含むことを示す。ジェネリックラベルサブＴＬＶ３２０は、ＲＦＣ５０３６において説明されるジェネリックラベルＴＬＶと同様である。ジェネリックラベルサブＴＬＶ３２０は、ＦＥＣについてのラベルをエンコードするために用いられる。ジェネリックラベルサブＴＬＶ３２０は、それがジェネリックラベルであることを示すタイプ３４５、及びラベルを値３５０（ラベルは典型的に非ＮＵＬＬラベルである）として含む。ＦＥＣサブＴＬＶ３３０は、ＲＦＣ５０３６において説明されるＦＥＣ  ＴＬＶと同様である。ＦＥＣサブＴＬＶ３３０は、出口ＬＳＲのＦＥＣ（例えば、出口ＬＳＲのループバックアドレス）をエンコードするために用いられる。ＦＥＣサブＴＬＶ３３０は、それがＦＥＣ  ＴＬＶであることを示すタイプ３５５、及び出口ＬＳＲアドレスプレフィックスＦＥＣエレメントを値３６０（例えば、出口ＬＳＲのループバックアドレス）として含む。一実施形態において、単一のアドレスのみが値３６０として存在する。
【００３２】
幾つかの実施形態において、メトリックＴＬＶは、階層的ラベルマッピングメッセージにも含まれる。メトリックＴＬＶは、ＦＥＣに関連付けられるメトリックを伝搬するために用いられる。図４は、一実施形態に係る、メトリックＴＬＶについての例示的なフォーマットを図示する。メトリックＴＬＶ４１０は、メッセージがメトリックＴＬＶであることを示すタイプ４２０、長さ４３０、メトリックタイプ４４０、及びメトリック値４５０を含む。メトリックタイプ４４０は、メトリックのタイプを示す（例えば、０はエリア内を示し、１はエリア間を示し、０ｘｆは任意の内部のメトリックよりも高い外部のルートのメトリックを示す）。メトリックタイプ４４０の特定の値は、用いられているＩＧＰ実装のタイプに依存し得る。メトリック値４５０は、メトリックについての値を示す。幾つかの実施形態において、階層的ラベルマッピングを含むラベルマッピングメッセージにメトリックＴＬＶが含まれない場合、ラベルマッピングメッセージは、メトリックタイプ０及びメトリック値０を有するものとして取り扱われる。
【００３３】
ＬＳＲは、異なる出口ＬＳＲから発信された単一のＦＥＣについての複数の階層的ラベルマッピングを受信する場合、メトリックＴＬＶを用いて、どの階層的ラベルマッピングをインストールするかを判定する。例えば、入口ＬＳＲが異なる出口ＬＳＲから発信された単一のＦＥＣについての複数の階層的ラベルマッピングを異なる近隣局から受信する場合、ＬＳＲは、これらの階層的ラベルマッピングのうちの１つを選択してインストールするであろう。一実施形態において、メトリックタイプＮを有するメトリックＴＬＶは、メトリック値に関わらず、メトリックタイプＮ＋１を有するメトリックＴＬＶよりも低い。複数のメトリックＴＬＶが同じメトリックタイプを有する場合（タイプ０ｘ０ｆを除く）、（Ｈ−Ｌａｂｅｌ  ＴＬＶにおいて識別される）出口アドレスプレフィックスＦＥＣエレメントへのルートについてのＲＩＢからのメトリックをメトリックＴＬＶのメトリック値に追加することによって取得される値について比較が為される。複数のメトリックＴＬＶが同じメトリックタイプ０ｘ０ｆを有する場合、メトリックＴＬＶのメトリック値のみを用いて比較が為される。比較の後、これらの値が同じである場合、これらは同じコストと見なされる（これらのうちの１つがランダムに選択され得る）。
【００３４】
図１を再び参照し、終端局１５０Ａに関連付けられるＦＥＣ１についてのラベルマッピングメッセージを生成し及び送信するＬＳＲ１１０を検討する。動作１．１において、Ｈ−Ｌａｂｅｌモジュール１１２は、ＮＵＬＬラベルにマッピングされるＬＳＲ１１０のＩＰアドレス（例えば、ＬＳＲ１１０のループバックアドレス）を含む出口ＬＳＲラベルマッピングメッセージ１１６を含み、ＬＳＲ１１０によって発信される非ＮＵＬＬラベル（ラベル１）にマッピングされるＦＥＣ１をマッピングし、ＬＳＲ１１０が当該非ＮＵＬＬラベルを発信したことの標識を含む階層的ラベルマッピングメッセージ１１８をさらに含むラベルマッピングメッセージ１１４を生成する。出口ＬＳＲラベルマッピングメッセージ１１６は、階層的ラベルマッピングメッセージ１１８の生成及び／又は送信に先立って、生成され及び送信され得る。総合して、出口ＬＳＲラベルマッピングメッセージ１１６及び階層的ラベルマッピングメッセージ１１８は、出口ＬＳＲ  ＬＳＰ及びＦＥＣ  ＬＳＰを含む階層的ＬＳＰの確立を可能にする。出口ＬＳＲ  ＬＳＰは、ラベルスイッチングパケットがＦＥＣを宛先とする場合に用いられ、ＦＥＣ  ＬＳＰは、パケットを識別し及びパケットを当該ＦＥＣに転送するために出口ＬＳＲによって用いられるであろう。ＦＥＣ  ＬＳＰは、出口ＬＳＲ  ＬＳＰ内でトンネリングされる。出口ＬＳＲ  ＬＳＰは、終端局１５０Ａ〜Ｎにそれぞれ関連付けられるＦＥＣ１〜Ｎの各々に共通するであろう。
【００３５】
一実施形態において、階層的ラベルマッピングについての（ＲＦＣ５０３６において定義されるような）ラベルＴＬＶの代わりに又はこれに加えて、図３において説明される階層的ラベルＴＬＶが用いられる。図５は、ＦＥＣ  ＴＬＶ５１０の上にスタッキングされる階層的ラベルＴＬＶ３１０を含む階層的ラベルマッピングメッセージ５００の例示的なフォーマットを図示する。図１に示される例において用いられる場合、階層的ラベルＴＬＶ３１０は、非ＮＵＬＬラベル（ラベル１）と出口ＬＳＲ１１０のＩＰアドレスとの間のマッピングを示し、ＦＥＣ  ＴＬＶ５１０は、ＦＥＣ１（例えば、終端局１５０ＡのＩＰアドレスプレフィックス）を示す。
【００３６】
幾つかの実施形態において、ＬＳＲ１１０は、ラベル要求メッセージに応答して、ラベルマッピングメッセージ１１４（例えば、出口ＬＳＲラベルマッピングメッセージ１１６及び／又は階層的ラベルマッピングメッセージ１１８）を生成する。ラベル要求メッセージは、１つ以上のＦＥＣについてのラベルバインディング（マッピング）を要求するために用いられる（例えば、当該メッセージは、ワイルドカードのＦＥＣ  ＴＬＶエレメントを含んで、複数のラベルバインディングを要求することができる）。図６は、一実施形態に係る、ラベル要求メッセージ６００についての例示的なフォーマットを図示する。ラベル要求メッセージ６００は、ラベルが要求される対象であるＦＥＣを識別するＦＥＣ  ＴＬＶ６１０を含み（ＦＥＣ  ＴＬＶ６１０はワイルドカードを含み得る）、随意的なパラメータ６２０を含む。随意的なパラメータ６２０は、階層的ラベルＴＬＶを含み得る。ＦＥＣ  ＴＬＶ６１０がワイルドカードである場合、全てのラベルマッピングが応答において返される（これは複数のラベルマッピングメッセージが生成され及び送信されることをもたらす）。ラベル要求メッセージに応答して、ＬＳＲ１１０は、ラベルマッピングメッセージにおいてＭｏｒｅ  Ｌａｂｅｌ  ＴＬＶを含み得る。Ｍｏｒｅ  Ｌａｂｅｌ  ＴＬＶの存在は、ラベル要求メッセージに応答して、さらなるラベルマッピングがＦＥＣについて送信されることになることを示す。
【００３７】
ラベルマッピングメッセージ１１４を生成した後のある時に、メッセージはＬＳＲ１１０のピアに送信される。従って、出口ＬＳＲラベルマッピングメッセージ１１６及び階層的ラベルマッピングメッセージ１１８を含む、生成されたラベルマッピングメッセージ１１４は、動作１．２Ａにおいてリンク１１５上でＬＳＲ１２０に送信され、動作１．２Ｂにおいてリンク１２５上でＬＳＲ１３０に送信される。
【００３８】
ラベルマッピングメッセージを受信した後、中間ＬＳＲ１２０及び１３０は、それぞれ動作１．３及び１．４において、少なくとも出口ＬＳＲラベルマッピングをインストールする。例えば、中間ＬＳＲ１２０及び１３０は、これらのＮＨＬＦＥ構造にラベル及び出口ＬＳＲ１１０のＩＰアドレスをインストールし、これらがラベルスワッピング（又は最終前のポップ）を実行できるように、これらのＩＬＭ構造におけるエントリを作成する。例えば、ＬＳＲ１２０及び１３０の各々は、これらのＮＨＬＦＥに、アウトゴーイングラベル（階層的ＬＳＰのアウターラベルに属する）（例えば、ＮＵＬＬラベル）、スワップアクション（又は、最終前のポッピングを実行する場合にはポップアクション）、ＬＳＲ１１０に到達するためのネクストホップ（この場合、ＬＳＲ１１０）、アウトゴーイングインタフェースを含むエントリをインストールし、他のデータ処理情報を含み得る。ＬＳＲ１２０及び１３０の各々は、出口ＬＳＲラベルマッピングについてこれらそれぞれのラベル空間からラベルを割り当てる。例えば、ＬＳＲ１２０は、出口ＬＳＲラベルマッピングについてラベル２を割り当て、ＬＳＲ１３０は出口ＬＳＲラベルマッピングについてラベル３を割当てる。ＬＳＲ１２０及び１３０は、これらそれぞれのＩＬＭ構造においてエントリを作成して、出口ＬＳＲラベルマッピングについての割り当てられたラベル（これはパケット転送の期間中にインカミングラベルとして受信されるであろう）をＬＳＲ１１０のＩＰアドレスについてのＮＨＬＦＥにマッピングする。従って、ＬＳＲ１２０が、インカミングラベルとしてラベル２を有するラベル有りパケットを受信する場合（これは、図８に関してより詳細に説明されるであろう）、ＬＳＲ１１０のＩＰアドレスについてのＮＨＬＦＥ構造におけるエントリへのポインタを含むラベル２についてのＩＬＭエントリがアクセスされる。幾つかの実施形態において、中間ＬＳＲ１２０及び１３０は、階層的ラベルマッピングメッセージ１１８をこれらそれぞれのピア（これは、図１に示される例においてはＬＳＲ１４０である）に転送すること以上に、当該メッセージを処理しない。
【００３９】
図１は、ＬＳＲ１２０及びＬＳＲ１３０の各々が、ＦＥＣごとに単一の階層的ラベルマッピングメッセージを受信することを図示するが、ＬＳＲ１２０及びＬＳＲ１３０が単一のＦＥＣについて複数の階層的ラベルマッピングメッセージを複数の近隣局から受信する状況があることが理解されるべきである。一実施形態において、中継ＬＳＲが単一のＦＥＣについて複数の階層的ラベルマッピングメッセージを複数の近隣局から受信する場合、当該中継ＬＳＲは、広告及び／又はインストールのためにこれらのラベルマッピングのうちの幾つかを選択する（中継ＬＳＲは、本明細書において説明される階層的ラベルマッピングを処理する能力を有しない近隣局を有する場合には、ラベルマッピングをインストールするであろう）。一実施形態において、階層的ラベルにおいて示されるＩＰアドレスについてのネクストホップである近隣局から受信される階層的ラベルマッピングは、選択され、全てのＬＤＰ近隣局に広告される（これらＬＤＰ近隣局が階層的ラベルマッピングを処理することが可能であると仮定する）。階層的ラベルマッピングを処理することが可能ではない近隣局が存在する場合、中間ＬＳＲは、入口ＬＳＲが階層的ラベルマッピングをインストールするのと同様の手法で、階層的ラベルマッピングをインストールするべきである（適用可能な場合には、メトリックＴＬＶにおいて示されるメトリックタイプ及びメトリック値の比較を含む）。
【００４０】
出口ＬＳＲラベルマッピングをインストールした後のある時に、中間ＬＳＲ１２０及び１３０は、それぞれ動作１．５及び１．６において、ラベルマッピングメッセージ１２２及び１３２を生成し及びＬＳＲ１４０に送信する。図１に図示されるように、ラベルマッピングメッセージ１２２は、出口ＬＳＲ１１０のＩＰアドレスとラベル２をマッピングする出口ＬＳＲラベルマッピングメッセージ１２４含み、及び、階層的ラベルマッピングメッセージ１１８を含む。ラベルマッピングメッセージ１３２は、出口ＬＳＲ１１０のＩＰアドレスをラベル３にマッピングする出口ＬＳＲラベルマッピングメッセージ１３４を含み、及び、階層的ラベルマッピングメッセージ１１８を含む。従って、ＬＳＲ１２０及び１３０が各々、出口ＬＳＲラベルをこれらのラベル空間における１つに変化させることによって出口ＬＳＲラベルマッピングを変更した一方で、階層的ラベルマッピング１１８は不変のままである。
【００４１】
ＬＳＲ１４０は、ラベルマッピングメッセージ１２２及びラベルマッピングメッセージ１３２に含まれる情報をＩＧＰデータ構造に記憶し得る。例えば、一実施形態において、情報はリンク状態データベース（ＬＳＤＢ：Link  State  Database）に記憶される。ラベルマッピングメッセージを受信した後、動作１．７において、ＬＳＲ１４０のＨ−ｌａｂｅｌモジュール１４２は、ＬＳＲ１３０から受信されるラベルマッピングメッセージ１３２よりも、ＬＳＲ１２０から受信されるラベルマッピングメッセージ１２２をそのデータプレーンにインストールすることを選択することを判定する。一実施形態において、この決定は、ＩＧＰによって判定され及び（例えば、メトリックＴＬＶがラベルマッピングメッセージに含まれる場合）メトリック値によって（必要ならば）さらに精緻化される最良のルートに基づく。
【００４２】
動作１．８において、Ｈ−Ｌａｂｅｌモジュール１４２は、ＦＥＣ１に属するパケットを転送する場合にＬＳＰ階層が用いられることになるように、ラベルマッピングメッセージ１２２をインストールする。従って、ＦＥＣ１についてのパケットを受信する場合、入口ＬＳＲ１４０は、ＦＥＣ１についてＬＳＲ１１０によって発信されるラベルをラベルスタック（インナーラベル）にプッシュし、出口ＬＳＲ１１０に到達するためのラベル（図示される例におけるラベル２）（アウターラベル）をラベルスタックにプッシュするであろう。例えば、Ｈ−Ｌａｂｅｌモジュール１４２は、出口ＬＳＲラベルマッピングメッセージ１２４に含まれる出口ＬＳＲラベルマッピング及び階層的ラベルマッピングメッセージ１１８に含まれる階層的ラベルマッピングについてのエントリがＮＨＬＦＥ構造１８０にインストールされるようにする。出口ＬＳＲラベルマッピングについてのＮＨＬＦＥは、ラベル２、プッシュアクション、及びネクストホップ（ＬＳＲ１２０へのＩＰアドレス）を含む。このＮＨＬＦＥは、階層的ＬＳＰのアウターラベルを付ける場合に用いられるであろう。ＦＥＣ１に属するラベルについてのＮＨＬＦＥは、ラベル１、プッシュアクション、及び出口ＬＳＲ１１０のＩＰアドレスへの再帰的ネクストホップを含む。Ｈ−Ｌａｂｅｌモジュール１４２は、終端局１５０Ａに関連付けられるＦＥＣ１についてのエントリがＦＴＮ構造１６２にインストールされるようにもする。
【００４３】
図１に図示されるように、ＦＴＮ構造１６２は、ＦＥＣインデックス１６４、及びＮＨＬＦＥ構造１８０へのポインタとして動作するＮＨＬＦＥインデックス１６６を含む。ＮＨＬＦＥ構造１８０は、ＮＨＬＦＥインデックス１６６に対応するインデックス１８２、アウトゴーイングラベルフィールド１８４、アクションフィールド１８６、及びネクストホップフィールド１８８を含む。ＮＨＬＦＥ構造１８０は、付加的な情報（例えば、アウトゴーイングインタフェース、他のデータ処理情報）も含み得る。図１に図示されるように、ＦＴＮ構造１６２は、終端局１５０Ａ〜Ｎに関連付けられるＦＥＣの各々についてのエントリを含む。また、ＮＨＬＦＥ構造１８０は、出口ＬＳＲラベルマッピングについての出口ＬＳＲラベルエントリ１９０（例えば、出口ＬＳＲラベルマッピングメッセージ１２４から生成される）、及び階層的ラベルマッピングについての階層的ラベルエントリ１９２（例えば、図１に示される例において、ＦＥＣ１についてのエントリは階層的ラベルマッピングメッセージ１１８に基づいて生成される）を含む。ＦＴＮ及びＮＨＬＦＥについての別個の構造が図示される一方、幾つかの実施形態ではＦＴＮ及びＮＨＬＦＥを表す単一の構造が存在することが理解されるべきである。図１は、ＦＥＣ１に属するパケットを伝送する場合にＬＳＰ階層が用いられることになるように、ラベルマッピングメッセージ１２２をインストールする特定の手法を図示するが、これは例示であり、ＦＥＣ１に属するパケットを伝送する場合にＬＳＰ階層を依然として作成しつつも、ラベルマッピングメッセージ１２２は異なる手法でインストールされてもよいことが理解されるべきである。また、図１において示される例はＦＥＣ１に固有であるが、同様の動作はＦＥＣ１〜Ｎの各々について実行されることが理解されるべきである。
【００４４】
図７は、一実施形態に係る、特定のＦＥＣに属するパケットを伝送する場合にＬＳＰ階層が用いられるようにラベルマッピングメッセージをインストールする入口ＬＳＲの例示的な動作を図示するフロー図である。図７の動作は、図１を参照しつつ説明されるであろう。ただし、図７の動作は、図１を参照しつつ議論される実施形態以外の本発明の実施形態によって実行されることができ、図１を参照しつつ議論される実施形態は、図７を参照しつつ議論される動作とは異なる動作を実行することができることが理解されるべきである。
【００４５】
ブロック７１０において、ＬＳＲ１４０は、出口ＬＳＲラベルマッピングメッセージ及び階層的ラベルマッピングメッセージをＬＳＲ１２０から受信する。複数のラベルマッピングメッセージは、異なる時間に受信されることができる。出口ＬＳＲラベルマッピングメッセージは、出口ＬＳＲ１１０のＦＥＣ（例えば、ＩＰアドレスプレフィックス）についてのラベルとのマッピングを示す。階層的ラベルマッピングメッセージは、終端局（終端局１５０Ａ〜Ｎのうちの１つ）に関連付けられるＦＥＣについての出口ＬＳＲによって発信されるラベルとのマッピングを示し、当該ラベルを発信した出口ＬＳＲをも識別する。
【００４６】
フローは次いでブロック７２０に移り、Ｈ−Ｌａｂｅｌモジュール１４２は、識別されたラベルについてのプッシュ動作及びＬＳＲ１２０へのネクストホップを含む、出口ＬＳＲ１１０と識別されたラベルとのマッピングについてのＮＨＬＦＥを作成する。フローはブロック７３０に移り、Ｈ−Ｌａｂｅｌモジュール１４２は、階層的ラベルマッピングメッセージにおいて示されるラベルについてのプッシュ動作、及び出口ＬＳＲ１１０についてのＮＨＬＦＥへの再帰的ネクストホップを含む階層的ラベルマッピングメッセージにおいて示されるＦＥＣについてＮＨＬＦＥを作成する。出口ＬＳＲ１１０についてのＮＨＬＦＥへの再帰的ネクストホップは、別のルックアップが実行されること（出口ＬＳＲ１１０についてのＮＨＬＦＥがアクセスされること）を引き起こすであろう。
【００４７】
フローは次いでブロック７４０に移り、Ｈ−Ｌａｂｅｌモジュール１４２は、階層的ラベルマッピングメッセージにおいて示されるＦＥＣに対応する階層的ラベルマッピングについてのＦＴＮエントリを作成し、及び、出口ＬＳＲ１４０のＩＰアドレスプレフィックスに対応する出口ＬＳＲラベルマッピングについてのＦＴＮエントリを随意的に作成する。フローは次いでブロック７５０に移り、作成されたエントリは、ＬＳＲ１４０の１つ以上のラインカードにダウンロードされる。例えば、ＮＨＬＦＥエントリは、ＮＨＬＦＥ構造１８０（これは１つ以上のラインカード上に記憶され得る）にダウンロードされ、ＦＴＮエントリは、ＦＴＮ構造１６２（これは１つ以上のラインカードに記憶され得る）にダウンロードされる。
【００４８】
図１に図示されるように、出口ＬＳＲエントリ１９０は、出口ＬＳＲラベルマッピングメッセージ１２４において出口ＬＳＲ１１０のＩＰアドレスにマッピングされたラベル２、プッシュ動作、及びＬＳＲ１２０のネクストホップを含む。終端局１５０Ａに関連付けられるＦＥＣについてインストールされるＦＥＣラベルエントリは、階層的ラベルマッピングメッセージ１１８に含まれた対応するラベル１、プッシュ動作、及び出口ＬＳＲ１１０についてのＮＨＬＦＥへの再帰的ネクストホップを含む。再帰的ネクストホップは、パケットを転送する場合に、出口ＬＳＲ１１０のＩＰアドレスに基づく追加的なルックアップが実行されることになることを示す。
【００４９】
図８は、一実施形態に係るＬＳＰの階層を用いる終端局１６０Ａから終端局１５０Ａへの例示的なパケットフローを図示する。図８は、図１及び図９を参照しつつ説明されるであろう。図９は、リモートＦＥＣを宛先とするパケットを受信する場合に入口ＬＳＲによって実行される例示的な動作を図示する。ただし、図９の動作は図１及び図９を参照しつつ説明されるもの以外の本願発明の実施形態によって実行されることができること、及び図１及び図９を参照しつつ議論される実施形態は図９を参照しつつ議論されるものとは異なる動作を実行することができることが理解されるべきである。
【００５０】
終端局１６０Ａは、ＩＰヘッダ（終端局１５０ＡのＩＰ宛先アドレスを伴う）及びデータペイロードを含むパケット８１０を送信する。図９を参照すると、ブロック９１０において、入口ＬＳＲは、パケット８１０を受信する。フローは次いでブロック９２０に移り、入口ＬＳＲ１４０は、パケット８１０の宛先ＩＰアドレスのＦＥＣを判定する。例えば、入口ＬＳＲ１４０は、宛先ＩＰアドレスをＦＥＣにマッピングするＩＰ対ＦＥＣルールのセットを含む。結果として得られるＦＥＣは、終端局１５０ＡのＩＰアドレスプレフィックスに対応する。フローは次いでブロック９３０に移る。
【００５１】
ブロック９３０において、入口ＬＳＲ１４０は、ＦＥＣに対応するＮＨＬＦＥにアクセスする。例えば、ＦＥＣに基づいてＦＴＮ構造１６２が最初にアクセスされ、ＦＥＣに対応するＮＨＬＦＥへのＮＨＬＦＥインデックス（ポインタ）が判定される。図１の例において、ＦＥＣ  ＩＰプレフィックス１に対応するＮＨＬＦＥインデックスは２である。判定されたインデックス２に対応するＮＨＬＦＥがアクセスされる。ＮＨＬＦＥは、ラベル、プッシュアクション、及び出口ＬＳＲ１１０についてのＮＨＬＦＥへの再帰的ネクストホップを含む。フローは次いでブロック９４０に移り、ラベル１がラベルスタックにプッシュされる。フローは次いでブロック９５０に移る。
【００５２】
ブロック９５０において、ＦＥＣについてのＮＨＬＦＥの再帰的ネクストホップのために、入口ＬＳＲ１４０は、出口ＬＳＲ１１０についてのＮＨＬＦＥ（出口ＬＳＲラベルエントリ１９０）にアクセスする。図１の例において、出口ＬＳＲラベルエントリ１９０は、ラベル２、プッシュアクション、及びＬＳＲ１２０のネクストホップを含む。フローは次いでブロック９６０に移り、ラベル２がラベルスタックにプッシュされる。フローは次いでブロック９７０に移り、パケット８１５はネクストホップＬＳＲ１２０へ送信される。図８に図示されるように、パケット８１５はラベル２をラベル１の上に含む。
【００５３】
ＬＳＲ１２０は、パケット８１５を受信する。インカミングラベル２に基づいて、ＬＳＲ１２０は、どのようにパケットを転送するかを判定する。例えば、ＬＳＲ１２０は、インカミングラベル２について自身のＩＬＭエントリにアクセスし、どのようにパケットが処理されるべきかを示すことになる対応するＮＨＬＦＥを判定する。幾つかの実施形態において、中間ＬＳＲ１２０は、メッセージをＬＳＲ１１０に送信することに先立って、最アウターラベル（出口ＬＳＲ１１０へ到達するためのラベル）を除去するように、最終前のホップポッピングを実行する。他の実施形態において、中間ＬＳＲ１２０は、ラベルスワップを実行する。例えば、中間ＬＳＲ１２０は、インカミングラベルを出口ＬＳＲ１１０によって広告されるラベル（例えば、ＮＵＬＬラベル）とスワップする。図８に図示されるように、ＬＳＲ１２０は、パケット８２０を出口ＬＳＲ１１０に送信することに先立って、パケットのラベルスタックからラベル２をポッピングする。入口ＬＳＲ１１０は、パケット８２０を受信し、ラベル１に基づいてパケットの宛先を判定する。例えば、入口ＬＳＲ１１０は、インカミングラベル１に基づいて自身のＩＬＭエントリを調べ、宛先が終端局１５０Ａであることを判定する。ＬＳＲ１１０は、ラベル１をポッピングし、パケット８１０を終端局１５０Ａに送信する。
【００５４】
従って、アウターラベルのＬＳＰが出口ＬＳＲに属し、インナーラベルのＬＳＰがアウターＬＳＰの出口におけるＦＥＣを識別するＬＳＰの階層を用いて、ラベル有りパケットが送信される。
【００５５】
出口ＬＳＲ１１０の到達可能性（及び、それ故に、終端局１５０Ａ〜Ｎの各々の到達可能性）に影響を及ぼすトポロジー変化に応じて、出口ＬＳＲラベルエントリのみが変更される必要がある。図１０は、トポロジー変化が出口ＬＳＲ１１０の到達可能性に影響を及ぼす場合に実行される例示的な動作を図示するデータフロー図である。動作１０．１において、最良のパスをパス１９６からパス１９８に変化させるトポロジー変化が発生する。トポロジー変化は、リンク（例えば、リンク１４５及び／又はリンク１１５）がダウンしたこと、メトリックの変化がパス１９８をより最適にすること、スタティックルートが変化したこと、ノードがダウンした（例えば、ＬＳＲ１２０がダウンした）こと、又はより最適である新たなパスが確立されたことを含む多くの理由により発生し得る。一実施形態において、ＩＧＰモジュールは、ＬＤＰモジュールに、トポロジーにおける変化を通知する。
【００５６】
図１０に図示される例において、トポロジー変化は、終端局１６０Ａ〜Ｌから送信される終端局１５０Ａ〜Ｎを宛先とするパケットについてのネクストホップを、ＬＳＲ１２０からＬＳＲ１３０に変化させる。パケットは、宛先ＦＥＣの到達可能性に基づいてではなく、当該パケットの出口ＬＳＲの到達可能性に基づいてラベルスイッチングされるため、出口ＬＳＲに対応するエントリのみが更新される必要がある。従って、トポロジー変化に応じて、動作１０．２において、Ｈ−ｌａｂｅｌモジュール１４２は、出口ＬＳＲラベルエントリ１９０のみを変化させて、パケットがＬＳＲ１２０の代わりにＬＳＲ１３０にラベルスイッチングされるようにする。具体的には、Ｈ−ｌａｂｅｌモジュール１４２は、ラベルを（出口ＬＳＲラベルマッピングメッセージ１３４においてＬＳＲ１３０によって広告された）ラベル３に、及びネクストホップをＬＳＲ１３０に変化させる。階層的ラベルエントリ１９２のいずれも変化させられる必要がないことが理解されるべきである。図１０には図示されないが、幾つかの実施形態において、Ｈ−ｌａｂｅｌモジュール２２２は、自身の制御カード上の自身のＭＰＬＳ情報ベースにおけるエントリを変化させ、変化されたエントリのみをＬＳＲ１４０のラインカード上に記憶されるＮＨＬＦＥ構造１８０にダウンロードする。
【００５７】
従って、出口ＬＳＲの到達可能性に影響を及ぼすトポロジー変化によって影響を及ぼされるＦＥＣ  ＩＰプレフィックス（例えば、ＦＥＣ  ＩＰプレフィックスについてのＮＨＬＦＥ構造におけるエントリ及び場合によりＩＬＭ構造におけるエントリ）についてのエントリの各々を変化させ及びダウンロードする代わりに、出口ＬＳＲについてのエントリのみが変化させられる必要があり、それにより、収束時間が低減される。それ故に、出口ＬＳＲへのパスが変化し、ネクストホップの変化がもたらされる場合、出口ＬＳＲに到達するためのパスに対応するネクストホップのみがデータプレーンにおいて再プログラミングされる必要がある。階層的ラベルの使用は、出口ＬＳＲに到達するトポロジーを変化させるリンク障害又はノード障害の状況の期間におけるトラフィックロスの継続時間も低減する。例えば、リンク１４５及び／若しくはリンク１１４、又はＬＳＲ１２０がダウンする場合を考慮されたい。階層的ラベルマッピングを用いない従来技術の解決法において、トラフィックの復旧は、（少なくとも制御プレーンにおける）ＩＧＰの収束に続き、ＬＳＲの算出及び更新後のＮＨＬＦＥエントリ（及び、場合によりＩＬＭエントリ）をデータプレーンにダウンロードすることを要する。ＩＰプレフィックスの数が増加するにつれて、（少なくとも制御プレーンにおける）ＩＧＰの収束についての継続時間、及び更新後のエントリの全てを算出し及びデータプレーンにダウンロードすることについての継続時間も増加する。従って、階層的ラベルマッピングを用いない従来技術の解決法において、リンク障害又はノード障害は、ネットワークにおけるプレフィックス／ラベルの数が増加するにつれて、トラフィックロスの継続時間の増加をもたらす。対照的に、階層的ラベルの使用は、出口ＬＳＲについてのエントリのみが更新されることを可能にする。従って、本発明の実施形態を用いれば、トラフィックの復旧が要するのは、（少なくとも制御プレーンにおいて）ＩＧＰが収束するための時間及び更新後のエントリのみを変化させ及びデータプレーンにダウンロードするための時間のみである。
【００５８】
図１１は、一実施形態に係る、図１０に図示されるトポロジー変化の後にＬＳＰの階層を用いる終端局１６０Ａから終端局１５０Ａへの例示的なパケットフローを図示する。終端局１６０Ａは、ＩＰヘッダ（終端局１５０ＡのＩＰ宛先を伴う）及びデータペイロードを含むパケット１１１０を送信する。ＬＳＲ１４０は、パケットを受信し、ＩＰヘッダに含まれる宛先ＩＰアドレスのＦＥＣを判定する。ＦＥＣに基づいて、対応するＮＨＬＦＥがアクセスされる。当該対応するＮＨＬＦＥは、ラベル１、プッシュ動作、及び出口ＬＳＲ１１０のＮＨＬＦＥへの再帰的ネクストホップを含む。ＬＳＲ１４０は、ラベル１をラベルスタックにプッシュし、再帰的ネクストホップに対応するＮＨＬＦＥにアクセスする。当該ＮＨＬＦＥは、ラベル３、プッシュ動作、及びＬＳＲ１３０へのネクストホップを含む。ＬＳＲ１４０は、ラベル３をラベルスタックにプッシュし、パケット１１１５をＬＳＲ１３０に送信する。
【００５９】
ＬＳＲ１３０は、パケット１１１５を受信する。インカミングラベル３に基づいて、ＬＳＲ１３０は、どのようにパケットを転送するかを判定する。例えば、ＬＳＲ１３０は、インカミングラベル３についての自身のＩＬＭエントリにアクセスし、対応するＮＨＬＦＥを判定する。幾つかの実施形態において、中間ＬＳＲ１３０は、メッセージをＬＳＲ１１０に送信することに先立って、最アウターラベル（出口ＬＳＲ１１０に到達するためのラベル）を除去するように、最終前のホップポッピングを実行する。他の実施形態において、中間ＬＳＲ１３０は、ラベルスワップを実行する。例えば、中間ＬＳＲ１３０は、インカミングラベルを出口ＬＳＲ１１０によって広告されるラベル（例えば、ＮＵＬＬラベル）とスワッピングする。図１１に図示されるように、ＬＳＲ１３０は、パケット１１２０を出口ＬＳＲ１１０に送信することに先立って、パケットのラベルスタックからラベル３をポッピングする。入口ＬＳＲ１１０は、パケット１１２０を受信し、ラベル１に基づいてパケットの宛先を判定する。例えば、入口ＬＳＲ１１０は、インカミングラベル１に基づいて自身のＩＬＭエントリを調べ、宛先が終端局１５０Ａであると判定する。ＬＳＲ１１０は、ラベル１をポッピングし、パケット１１１０を終端局１５０Ａに送信する。
【００６０】
幾つかの実施形態において、階層的ラベル機能（capability）がサポートされているかを判定するための情報を、ネットワーク内のＬＳＲは交換する。例えば、階層的ラベル機能ＴＬＶは、階層的ラベル機能がサポートされているかを示すＬＤＰ上で、ＬＳＲ間で交換され得る。一実施形態において、ルーティングされるパスに沿ったＬＳＲが本明細書において説明される階層的ラベルマッピングを処理することをサポートしない場合、アウターＬＳＰは、階層的ラベル処理が不可能であるＬＳＲの出現の前の、出口ＬＳＲへのルーティングされるパスに沿った階層的ラベルの処理をサポートする最も遠い下流のＬＳＲまで進む。一実施形態において、アウターＬＳＰは、ＴＥ（Traffic  Engineering：トラフィックエンジニアリング）ＬＳＰである。一実施形態において、階層的ラベルマッピングが存在するＦＥＣが階層的ラベルマッピング無しにＬＳＲによって広告された場合（例えば、近隣局が階層的ラベルマッピングを処理することが不可能であった場合）、当該ＬＳＲ上のＩＬＭエントリは、階層的ＬＳＰへのスワップ動作と共にインストールされるべきであり、階層的ラベルマッピングは、入口ＬＳＲが当該階層的ラベルマッピングをインストールするのと同様の手法で当該ＬＳＲにインストールされるべきである。
【００６１】
幾つかの実施形態において、階層的ラベルマッピングを広告する場合、独立した又は順序付けられたＬＳＰ制御が用いられることができる。例えば、Ｈ−ｌａｂｅｌ機能付きの（capable）ＬＳＲは、独立したラベル配布制御を用いて、当該ＬＳＲが望む時にいつでもそのピアに階層的ラベルマッピングを広告し得る。従って、ＬＳＲは、階層的ラベルマッピングを受信しない場合（ＬＳＲはＦＥＣのネクストホップのうちの１つから階層的マッピングを受信しないと仮定する）、ＦＥＣについての階層的ラベルマッピングをそのアドレスと共に広告することができる。
【００６２】
階層的ラベル機能付きのＬＳＲは、順序付けられたラベル配布制御を用いても動作し得る。順序付けられたラベル配布制御モードにおいて、ＦＥＣへの複数の階層的ラベルマッピングをその近隣局から受信するＬＳＲは、当該ＦＥＣへの最も低いコストのパスを伴うＨ−ｌａｂｅｌマッピングを選択する。ＦＥＣについての選択された階層的ラベルマッピングは、その近隣局（少なくとも、階層的ラベル機能付きの近隣局）に広告される。ＦＥＣに対応するルートは、近隣のＬＳＲに階層的ラベルマッピングを広告する前に、ＩＧＰを介してＲＩＢ（又はＦＩＢ）に現れる必要がない。
【００６３】
幾つかの実施形態において、ＬＳＲは、ＦＥＣについての自身のネクストホップではない近隣局から学習されるＦＥＣについてラベルバインディングを維持するための保守的なラベル保持（retention）モードなどのラベル保持モードを用い得る。当該保守的なラベル保持モードにおいて、ＦＥＣについての全てのパス／ネクストホップが共通の共有リスクリンクグループ（ＳＲＬＧ：shared  risk  link  group）を有する場合、ＬＳＲは、バックアップとして、ＳＲＬＧを共有しない別のネクストホップを有し得る。これは、別のラベルからラベルを要求することを必要とし得る。共通のＳＲＬＧは、２つのリンクによって共有されるリスクである。一例として、複数のファイバーが共通のダクトを介して運搬される場合、当該ダクトが切断される場合には双方のファイバーも切断されることになる点で、これらのファイバーはＳＲＬＧを共有する。
【００６４】
幾つかのネットワークトポロジーにおいて、終端局は、複数の出口ＬＳＲへマルチホームされる（multi-homed）ことができる。そのような場合、出口ＬＳＲの各々は、それらの終端局に関連付けられるＦＥＣについての階層的ラベルマッピング及び出口ＬＳＲラベルマッピングを広告する。第１の出口ＬＳＲが到達不可能になる（例えば、当該ＬＳＲがダウンする）場合、入口ＬＳＲは、第２の出口ＬＳＲに到達するためのアウターＬＳＰ及びインナーＬＳＰの双方を変化させる。ただし、本発明の実施形態において、終端局に属するＦＥＣはＩＧＰにおいて広告されない（例えば、ループバックアドレス及びラベルスイッチングされるルータ間のリンクのみがＩＧＰにおいて広告される）ため、入口ＬＳＲ上のＩＧＰデータベース（例えば、リンク状態データベース（ＬＳＤＢ：Link  State  Database））は比較的小さいであろう。このことは、ＩＧＰの収束に必要な時間を低減し、入口ＬＳＲが第２のＬＳＲにより迅速にスイッチングすることを可能にするであろう。
【００６５】
図面において示される技法は、１つ以上の電子デバイス（例えば、終端局、ネットワークエレメント等）上に記憶され及び実行されるコード及びデータを用いて実装されることができる。そのような電子デバイスは、機械読み取り可能な記憶媒体（例えば、磁気ディスク、光ディスク、ＲＡＭ（random  access  memory）、ＲＯＭ（read  only  memory）、フラッシュメモリデバイス、相変化メモリ）、及び機械読み取り可能な通信媒体（例えば、伝搬信号の電気的、光学的、音響的又は他の形態−搬送波、赤外線信号、デジタル信号等）といった機械読み取り可能な媒体を用いてコード及びデータを記憶し並びに（内部的に及び／又はネットワーク上で他の電子デバイスと）通信する。また、そのようなデジタルデバイスは、典型的に、１つ以上のストレージデバイス、ユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、及び／又はディスプレイ）、並びにネットワーク接続といった、１つ以上の他のコンポーネントに結合される１つ以上のプロセッサのセットを含む。例えば、制御カード及びラインカードを含むネットワークエレメントの場合、これらのカードの各々が１つ以上のプロセッサのセットを含む（例えば、ラインカードは、１つ以上のパケット処理エンティティ（例えば、パケット処理ＡＳＩＣ）のセットを含む）。プロセッサのセットと他のコンポーネントとの結合は、典型的に、１つ以上のバス及びブリッジ（バスコントローラとも称される）を介する。ストレージデバイス及びネットワークトラフィックを搬送する信号は、それぞれ１つ以上の機械読み取り可能な記憶媒体及び機械読み取り可能な通信媒体を表す。従って、所与の電子デバイスのストレージデバイスは、典型的に、当該電子デバイスの１つ以上のプロセッサのセット上での実行のためのコード及び／又はデータを記憶する。当然ながら、本発明の実施形態の１つ以上の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの様々な組み合わせを用いて実装され得る。
【００６６】
図面におけるフロー図は、本発明のある実施形態によって実行される動作の特定の順序を示すが、そのような順序は例示的である（例えば、別の実施形態は、当該動作を異なる順序で実行し、ある動作を組み合わせ、ある動作を重複させるなどしてもよい）ことが理解されるべきである。
【００６７】
本発明は幾つかの実施形態の観点から説明されたが、本発明が説明された実施形態に限定されず、添付の特許請求の範囲の思想及び範囲内における変更及び変形と共に実施をされ得ることを当業者は認識するであろう。従って、説明は、限定ではなく例示としてみなされるべきである。
【図１】
2013541896.tif 000003
【図２】
2013541896.tif 000004
【図３】
2013541896.tif 000005
【図４】
2013541896.tif 000006
【図５】
2013541896.tif 000007
【図６】
2013541896.tif 000008
【図７】
2013541896.tif 000009
【図８】
2013541896.tif 000010
【図９】
2013541896.tif 000011
【図１０】
2013541896.tif 000012
【図１１】
2013541896.tif 000013
【手続補正書】
【提出日】平成25年3月25日(2013.3.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいてＬＳＲ（Label  Switched  Router）として動作する第１のネットワークエレメントにおけるＬＤＰ（Label  Distribution  Protocol）の収束時間を改善するための方法であって、当該方法は、
複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）についての階層的ＬＳＰ（Label  Switched  Path）を確立するステップと、
各ＦＥＣについての当該階層的ＬＳＰは、
前記ＦＥＣの各々について共通し、前記複数のＦＥＣについての出口ＬＳＲとして動作している第２のネットワークエレメントへのパスを形成し、前記ＭＰＬＳネットワークにおいてパケットをラベルスイッチングする場合に用いられる出口ＬＳＲ  ＬＳＰ、並びに、
パケットを識別し及び前記ＦＥＣに転送するために前記第２のネットワークエレメントによって用いられる一意のＦＥＣ  ＬＳＰ、
を含むことと、
前記出口ＬＳＲ  ＬＳＰについての前記第１のネットワークエレメントのネクストホップを変化させるトポロジー変化に応答して、前記ＦＥＣ  ＬＳＰについてのいかなる転送構造エントリも実質的に変更することなく、前記出口ＬＳＲ  ＬＳＰについての少なくとも前記ネクストホップを変化させるために転送構造を変更するステップと、
を含み、
それにより、前記トポロジー変化の後の転送構造の変更の低減を通じて、ＬＤＰの収束時間が改善される、方法。
【請求項２】
前記第１のネットワークエレメントは入口ＬＳＲとして動作し、前記階層的ＬＳＰを確立する前記ステップは、
中間ＬＳＲとして動作する第３のネットワークエレメントから、複数のラベルマッピングメッセージを受信するステップと、
当該複数のラベルマッピングメッセージは、
前記第２のネットワークエレメントのＩＰアドレスにマッピングされ、前記第３のネットワークエレメントによって値が割り当てられるラベルを示す第１の出口ＬＳＲラベルマッピングメッセージ、及び、
前記複数のＦＥＣの各々についての一意の階層的ラベルマッピングメッセージ、
を含むことと、
前記階層的ラベルマッピングメッセージの各々は、当該ＦＥＣにマッピングされる前記出口ＬＳＲによって発信されるラベルを示し、当該ラベルを発信した前記出口ＬＳＲのＩＤも示すことと、
示された前記ラベルが前記複数のＦＥＣのうちのいずれかを宛先とするアウトゴーイングパケットについてのラベルスタックにプッシュされ、当該パケットが前記第３のネットワークエレメントに送信されることになるように、前記出口ＬＳＲラベルマッピングメッセージに基づいて転送構造に出口ＬＳＲラベルエントリをインストールするステップと、
一意の階層的ラベルマッピングメッセージ各々について、示された前記ラベルが当該ＦＥＣを宛先とするアウトゴーイングパケットについてのラベルスタックにプッシュされ、前記出口ＬＳＲラベルエントリがアクセスされることとなるように、前記階層的ラベルマッピングメッセージに基づいて前記転送構造に階層的ラベルエントリをインストールするステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記第２のネットワークエレメントへの別のネクストホップを提供する中間ＬＳＲとして動作する第４のネットワークエレメントから複数のラベルマッピングメッセージを受信するステップ、
をさらに含み、
当該複数のラベルマッピングメッセージは、
前記第２のネットワークエレメントのＩＰアドレスにマッピングされ、前記第４のネットワークエレメントによって値が割り当てられるラベルを示す第２の出口ＬＳＲラベルマッピングメッセージ、及び
前記複数のＦＥＣについての前記一意の階層的ラベルマッピングメッセージ、
を含み、
前記トポロジー変化は、前記出口ＬＳＲ  ＬＳＰについての前記第１のネットワークエレメントの前記ネクストホップを、前記第３のネットワークエレメントから前記第４のネットワークエレメントに変化させ、
前記出口ＬＳＲ  ＬＳＰについての少なくとも前記ネクストホップを変化させるために前記転送構造を変更する前記ステップは、前記第４のネットワークエレメントによって割り当てられる前記ラベルが前記複数のＦＥＣのうちのいずれかを宛先とする前記アウトゴーイングパケットにプッシュされ、当該パケットが前記第４のネットワークエレメントに送信されることになるように、前記転送構造における前記出口ＬＳＲラベルエントリを変化させることを含む、請求項２に記載の方法。
【請求項４】
前記複数の終端局うちの第１の終端局を宛先とする、ラベル無しのパケットを受信するステップと、
前記パケットにおける前記宛先ＩＰアドレスに基づいて、前記第１の終端局の前記ＦＥＣを判定するステップと、
前記ＦＥＣに基づいて、前記階層的ラベルエントリにアクセスするステップと、
アクセスされる前記階層的ラベルエントリにおいて示される前記ラベルを、前記パケットについてのラベルスタックにプッシュするステップと、
アクセスされる前記階層的ラベルエントリによって示される前記出口ＬＳＲラベルエントリにアクセスするステップと、
アクセスされる前記出口ＬＳＲラベルエントリにおいて示される前記ラベルを、前記パケットについての前記ラベルスタックにプッシュするステップと、
前記出口ＬＳＲラベルエントリにおいて識別される前記ネクストホップへ、ラベル有りの前記パケットを送信するステップと、
をさらに含む、請求項２に記載の方法。
【請求項５】
前記トポロジー変化は、リンク障害、ノード障害、メトリックの変化、及び前記第２のネットワークエレメントへのより最適なパスを有する新たなルート、のうちの１つである、請求項１に記載の方法。
【請求項６】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいて出口ＬＳＲ（Label  Switched  Router）として動作する第１のネットワークエレメントにおいて、入口ＬＳＲとして動作する第２のネットワークエレメントからの中間ＬＳＲとして動作する１つ以上の第３のネットワークエレメントのセットを介する前記第１のネットワークエレメントへの階層的ＬＳＰ（Label  Switched  Path）を確立するためにラベルマッピングメッセージを発信するための方法であって、前記方法は、
前記第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成するステップと、
前記第１のネットワークエレメントが出口となる複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）の各々について、当該ＦＥＣについて前記第１のネットワークエレメントによって発信されるラベルを示し、前記第１のネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージを生成するステップと、
前記出口ＬＳＲラベルマッピングメッセージ及び前記階層的ラベルマッピングメッセージを、前記第１のネットワークエレメントの１つ以上のピアに送信して、前記第１のネットワークエレメントに到達するためのパスを定義するアウターＬＳＰ、並びにパケットを識別し及び当該ＦＥＣに転送するために前記第１のネットワークエレメントによって用いられる当該ＦＥＣに固有のインナーＬＳＰを含む、前記複数のＦＥＣの各々についての前記階層的ＬＳＰの確立を可能にするステップと、
を含み、
それにより、前記第２のネットワークエレメントが、前記インナーＬＳＰのうちのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、前記アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、前記第１のネットワークエレメントへの到達可能性に影響を及ぼすトポロジー変化に対処することを、前記階層的ＬＳＰが可能にする、方法。
【請求項７】
前記出口ＬＳＲラベルマッピングメッセージに含まれる前記ラベルは、ＮＵＬＬラベルであり、前記第１のネットワークエレメントの前記ＩＰアドレスは、前記第１のネットワークエレメントのループバックＩＰアドレスである、請求項６に記載の方法。
【請求項８】
前記階層的ラベルマッピングメッセージのうちの少なくとも１つは、前記第２のネットワークエレメントからのラベル要求メッセージを受信することに応じて生成される、請求項６に記載の方法。
【請求項９】
前記階層的なラベルマッピングメッセージは、階層的ラベルＴＬＶ（type-length-value）を含み、当該階層的ラベルＴＬＶは、
前記ＦＥＣについて前記第１のネットワークエレメントによって発信される前記ラベルを含むジェネリックラベルサブＴＬＶと、
前記第１のネットワークエレメントの前記ＩＰアドレスを含むＦＥＣサブＴＶＬと、
を含む、
請求項６に記載の方法。
【請求項１０】
前記ＦＥＣのうちの少なくとも１つについての前記階層的ラベルマッピングメッセージのうちの少なくとも１つは、当該ＦＥＣについてのメトリックタイプ及びメトリック値を含む、請求項６に記載の方法。
【請求項１１】
ＭＰＬＳ（Multi-Protocol  Label  Switching）ネットワークにおいて入口ＬＳＲ（Label  Switched  Router）として動作して、当該ＭＰＬＳネットワークにわたって終端局に属するパケットを階層的ＬＳＰ（Label  Switched  Path）を用いて伝送するネットワークエレメントであって、当該ネットワークエレメントは、
階層的ラベルモジュールを含む制御カード、
を備え、
当該階層的ラベルモジュールは、
ＦＥＣについて出口ＬＳＲによって発信されるラベルのマッピングを各々含み、前記出口ＬＳＲが当該ラベルを発信したことを示す、前記終端局に属する複数のＦＥＣ（Forwarding  Equivalence  Classes）について前記出口ＬＳＲから発信される階層的ラベルマッピングメッセージと、前記出口ＬＳＲのＩＰアドレスにマッピングされるラベルを各々含む、前記出口ＬＳＲから発信される出口ＬＳＲラベルマッピングメッセージと、を処理し、それにより、前記複数のＦＥＣの各々について階層的ＬＳＰが確立されるようにし、
なお、各ＦＥＣについての前記階層的ＬＳＰは、
前記ＦＥＣの各々に共通し、前記出口ＬＳＲへのネクストホップを提供する、前記出口ＬＳＲラベルマッピングメッセージに基づく出口ＬＳＲ  ＬＳＰと、
パケットを識別し及び前記ＦＥＣに転送するための情報を搬送する一意のＦＥＣ  ＬＳＰと、
を含み、
前記階層的ＬＳＰを表す１つ以上の転送構造エントリを、前記ネットワークエレメントの１つ以上のラインカードにダウンロードし、
前記出口ＬＳＲへの前記ネクストホップを変化させるトポロジー変化に応じて、前記出口ＬＳＲ  ＬＳＰについての１つ以上の転送構造エントリを変更し及び前記１つ以上のラインカードにダウンロードして、前記ＦＥＣ  ＬＳＰについての如何なる転送構造エントリも実質的に変更し及びダウンロードすること無く、前記出口ＬＳＲについての前記ネクストホップを変化させる、
ように動作し、
それにより、前記トポロジー変化の後の転送構造の変更の低減を通じて、ＬＤＰの収束時間が改善される、ネットワークエレメント。
【請求項１２】
前記階層的ラベルモジュールは、前記複数のＦＥＣに関連付けられるメトリック値を示す階層的ラベルマッピングメッセージを処理して、異なる出口ＬＳＲによって発信される単一のＦＥＣについて複数の階層的ラベルマッピングメッセージが受信される場合に、どの階層的ラベルマッピングメッセージをインストールすべきかを判定するようにさらに動作する、請求項１１に記載のネットワークエレメント。
【請求項１３】
前記階層的ラベルモジュールは、前記出口ＬＳＲに到達するためにラベルスタックにプッシュするべきラベルを示す、受信される前記出口ＬＳＲラベルマッピングメッセージに基づいて、出口ＬＳＲラベルエントリを前記１つ以上のラインカード上の転送構造にダウンロードする、請求項１１に記載のネットワークエレメント。
【請求項１４】
前記階層的ラベルマッピングメッセージの各々を処理することは、前記階層的ラベルモジュールが、当該階層的ラベルマッピングメッセージに基づいて、階層的ラベルエントリを前記１つ以上のラインカード上の転送構造にダウンロードし、それにより、前記階層的ラベルマッピングメッセージにおいて示される前記ＦＥＣを宛先とするアウトゴーイングパケットについてのラベルスタックに、示される前記ラベルがプッシュされ、前記出口ＬＳＲに到達するための前記ラベルを前記ラベルスタックにプッシュするために前記出口ＬＳＲラベルエントリがアクセスされる必要があるようにすることを含む、請求項１３に記載のネットワークエレメント。
【請求項１５】
階層的ＬＳＰを用いて前記終端局を宛先とするパケットを転送するための１つ以上のパケット処理エンティティを含む１つ以上のラインカードをさらに備え、当該１つ以上のパケット処理エンティティは、当該終端局のうちの１つを宛先とする、受信されるラベル無しのパケットの各々について、下記を実行することを含む、請求項１４に記載のネットワークエレメント：
前記パケットの前記宛先ＩＰアドレスに基づいて、当該終端局の前記ＦＥＣを判定すること；
当該ＦＥＣに基づいて、階層的ラベルエントリにアクセスすること；
アクセスされる前記階層的ラベルエントリにおいて示される前記ラベルを、前記パケットについてのラベルスタックにプッシュすること；
アクセスされる前記階層的ラベルエントリによって示されるように出口ＬＳＲラベルエントリにアクセスすること；
アクセスされる前記出口ＬＳＲラベルエントリにおいて示される前記ラベルを、前記パケットについての前記ラベルスタックにプッシュすること；及び
ラベル有りの前記パケットを、アクセスされる前記出口ＬＳＲラベルエントリにおいて識別されるネクストホップに送信すること。
【請求項１６】
ＭＰＬＳ（Multiprotocol  Label  Switching）ネットワークにおいて、複数の終端局にそれぞれ属する複数のＦＥＣ（Forwarding  Equivalence  Classes）についての出口ＬＳＲ（Label  Switched  Router）として動作し、前記ＦＥＣについての入口ＬＳＲとして動作する第２のネットワークエレメントからの中間ＬＳＲとして動作する１つ以上の第３のネットワークエレメントのセットを介する階層的ＬＳＰ（Label  Switched  Path）を確立するためにラベルマッピングメッセージを発信するための第１のネットワークエレメントであって、当該第１のネットワークエレメントは、
階層的ラベルモジュールを含む制御カード、
を備え、
当該階層的ラベルモジュールは、
前記第１のネットワークエレメントのＩＰアドレスにマッピングされるラベルを含む出口ＬＳＲラベルマッピングメッセージを生成し、
前記複数のＦＥＣの各々について、当該ＦＥＣについて前記第１のネットワークエレメントによって発信されるラベルを示し、前記第１のネットワークエレメントが当該ラベルを発信したことを示す、当該ＦＥＣについての階層的ラベルマッピングメッセージを生成し、
前記ＭＰＬＳネットワークを通じて伝搬されるべき、生成された前記出口ＬＳＲラベルマッピングメッセージ及び前記階層的ラベルマッピングメッセージの、前記第３のネットワークエレメントのセットへの送信を生じさせて、前記第１のネットワークエレメントの前記ＩＰアドレスに到達するためのパスを定義するアウターＬＳＰ、及びパケットを識別し及び当該ＦＥＣへ転送するために前記第１のネットワークエレメントによって用いられる当該ＦＥＣに固有のインナーＬＳＰを含む、前記ＦＥＣの各々についての階層的ＬＳＰの確立を可能にする
ように動作し、
それにより、前記第２のネットワークエレメントが、前記インナーＬＳＰのうちのいずれかに関連付けられる如何なる転送エントリも実質的に変更すること無く、前記アウターＬＳＰに関連付けられる１つ以上の転送エントリを変化させることを通じて、前記第１のネットワークエレメントへの到達可能性に影響を及ぼすトポロジー変化に対処することを、前記階層的ＬＳＰが可能にする、
第１のネットワークエレメント。
【請求項１７】
前記出口ＬＳＲラベルマッピングメッセージに含まれる前記ラベルは、ＮＵＬＬラベルであり、前記第１のネットワークエレメントの前記ＩＰアドレスは、前記第１のネットワークエレメントのループバックＩＰアドレスである、請求項１６に記載のネットワークエレメント。
【請求項１８】
前記階層的ラベルモジュールは、前記第２のネットワークエレメントからのラベル要求メッセージの受信に応じて、前記階層的ラベルマッピングメッセージのうちの少なくとも１つを生成するように動作する、請求項１６に記載のネットワークエレメント。
【請求項１９】
各階層的ラベルマッピングメッセージは、階層的ラベルＴＬＶ（type-length-value）を含み、当該階層的ラベルＴＬＶは、
前記ＦＥＣについて前記第１のネットワークエレメントによって発信される前記ラベルを含むジェネリックラベルサブＴＬＶと、
前記第１のネットワークエレメントの前記ＩＰアドレスを含むＦＥＣサブＴＶＬと、
を含む、
請求項１６に記載のネットワークエレメント。
【請求項２０】
前記階層的ラベルモジュールは、前記階層的ラベルマッピングメッセージに、前記ＦＥＣについてのメトリックタイプ及びメトリック値をさらに含める、請求項１６に記載のネットワークエレメント。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
図２は、一実施形態に係る、ＬＳＲとして動作する例示的なネットワークエレメントをより詳細に図示する。ネットワークエレメント２００は、制御プレーン２１０及びデータプレーン２５０（転送プレーン又はメディアプレーンと呼ばれることもある）を含む。制御プレーン２１０は、データ（例えば、パケット）がどのようにルーティングされるか（例えば、当該データについてのネクストホップ、及び当該データについてのアウトゴーイングポート）を判定し、データプレーン２５０は、当該データの転送を担う。制御プレーン２１０は、ＩＧＰ（Interior  Gateway  Protocol）モジュール２１５及びＬＤＰ（Label  Distribution  Protocol）モジュール２２０を含む。ＩＧＰモジュール２１５は、ＯＳＰＦ（Open  Shortest  Path  First）若しくはＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）などのリンク状態プロトコルを実行し、又はＲＩＰ（Routing  Information  Protocol）などの別のプロトコルを実行し得る。ＩＧＰモジュール２１５は、他のネットワークエレメントと通信して、ルートを交換し、それらのルートを１つ以上のルーティングメトリックに基づいて選択する。選択されたＩＧＰルートは、ＲＩＢ（Routing  Information  Base：ルーティング情報ベース）２２５に記憶される。ＩＧＰモジュール２１５は、選択されずにＲＩＢ２２５に記憶されるルートエントリがローカルＲＩＢ（例えば、ＩＧＰローカルＲＩＢ）に記憶されるようにすることもできる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
ＬＳＲ１１０は、階層的ラベル（Ｈ−Ｌａｂｅｌ：hierarchical  label）モジュール１１２を含み、ＬＳＲ１４０は、Ｈ−Ｌａｂｅｌモジュール１４２を含む（一実施形態において、これらのモジュールは、ＬＳＲ１１０及びＬＳＲ１４０それぞれの制御プレーンの一部である）。Ｈ−Ｌａｂｅｌモジュール１１２は、当該Ｈ−Ｌａｂｅｌモジュール１１２が出口となるＦＥＣについての階層的ラベルマッピングを含むラベルマッピングメッセージを生成し及び生じさせる。Ｈ−Ｌａｂｅｌモジュール１４２は、１つ以上の構造における階層的ラベルエントリをインストールすること、及び出口ＬＳＲ１１０への再帰的ネクストホップを伴うＦＥＣラベルをインストールすることを含めて、階層的ラベルマッピングを含む、受信されるラベルマッピングメッセージを処理する。従って、Ｈ−Ｌａｂｅｌモジュール１１２は、既存のＬＤＰラベルマッピング発信の機能性を拡張して、階層的ラベルマッピングをサポートし、Ｈ−Ｌａｂｅｌモジュール１４２は、既存のＬＤＰラベル管理の機能性を拡張して、階層的ラベルマッピングをサポートする。Ｈ−Ｌａｂｅｌモジュール１１２は階層的ラベルマッピングを発信する（実質的に、出口Ｈ−Ｌａｂｅｌモジュールとして動作する）ものとして説明され、Ｈ−Ｌａｂｅｌモジュール１４２は受信される階層的ラベルマッピングを処理する（実質的に、入口Ｈ−Ｌａｂｅｌモジュールとして動作する）ものとして説明されるが、１つ以上のモジュールが双方の機能性を含み得ることが理解されるべきである。一実施形態によれば、Ｈ−Ｌａｂｅｌモジュール１１２及び１４２は、ＬＳＲ１１０及び１４０のＬＤＰを実行するＬＤＰモジュールの一部である。一実施形態によれば、中間ＬＳＲ１２０及び１３０は、特定のＨ−Ｌａｂｅｌモジュールを含まず、代わりに標準的なＬＤＰメカニズムを実行する。ＬＳＲ１４０は、ＦＴＮ構造１６２及びＮＨＬＦＥ構造１８０をさらに含み、これらはそれぞれＨ−Ｌａｂｅｌモジュール１４２によって管理される。一実施形態において、ＦＴＮ構造１６２及びＮＨＬＦＥ構造１８０は、ＬＳＲ１４０のデータプレーンの一部であり、ＬＳＲ１４０の１つ以上のラインカード上に少なくとも部分的に記憶され得る。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
フローは次いでブロック７４０に移り、Ｈ−Ｌａｂｅｌモジュール１４２は、階層的ラベルマッピングメッセージにおいて示されるＦＥＣに対応する階層的ラベルマッピングについてのＦＴＮエントリを作成し、及び、入口ＬＳＲ１４０のＩＰアドレスプレフィックスに対応する出口ＬＳＲラベルマッピングについてのＦＴＮエントリを随意的に作成する。フローは次いでブロック７５０に移り、作成されたエントリは、ＬＳＲ１４０の１つ以上のラインカードにダウンロードされる。例えば、ＮＨＬＦＥエントリは、ＮＨＬＦＥ構造１８０（これは１つ以上のラインカード上に記憶され得る）にダウンロードされ、ＦＴＮエントリは、ＦＴＮ構造１６２（これは１つ以上のラインカードに記憶され得る）にダウンロードされる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
図８は、一実施形態に係るＬＳＰの階層を用いる終端局１６０Ａから終端局１５０Ａへの例示的なパケットフローを図示する。図８は、図１及び図９を参照しつつ説明されるであろう。図９は、リモートＦＥＣを宛先とするパケットを受信する場合に入口ＬＳＲによって実行される例示的な動作を図示する。ただし、図９の動作は図１及び図８を参照しつつ説明されるもの以外の本願発明の実施形態によって実行されることができること、及び図１及び図９を参照しつつ議論される実施形態は図９を参照しつつ議論されるものとは異なる動作を実行することができることが理解されるべきである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
ＬＳＲ１２０は、パケット８１５を受信する。インカミングラベル２に基づいて、ＬＳＲ１２０は、どのようにパケットを転送するかを判定する。例えば、ＬＳＲ１２０は、インカミングラベル２について自身のＩＬＭエントリにアクセスし、どのようにパケットが処理されるべきかを示すことになる対応するＮＨＬＦＥを判定する。幾つかの実施形態において、中間ＬＳＲ１２０は、メッセージをＬＳＲ１１０に送信することに先立って、最アウターラベル（出口ＬＳＲ１１０へ到達するためのラベル）を除去するように、最終前のホップポッピングを実行する。他の実施形態において、中間ＬＳＲ１２０は、ラベルスワップを実行する。例えば、中間ＬＳＲ１２０は、インカミングラベルを出口ＬＳＲ１１０によって広告されるラベル（例えば、ＮＵＬＬラベル）とスワップする。図８に図示されるように、ＬＳＲ１２０は、パケット８２０を出口ＬＳＲ１１０に送信することに先立って、パケットのラベルスタックからラベル２をポッピングする。出口ＬＳＲ１１０は、パケット８２０を受信し、ラベル１に基づいてパケットの宛先を判定する。例えば、出口ＬＳＲ１１０は、インカミングラベル１に基づいて自身のＩＬＭエントリを調べ、宛先が終端局１５０Ａであることを判定する。ＬＳＲ１１０は、ラベル１をポッピングし、パケット８１０を終端局１５０Ａに送信する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
図１０に図示される例において、トポロジー変化は、終端局１６０Ａ〜Ｌから送信される終端局１５０Ａ〜Ｎを宛先とするパケットについてのネクストホップを、ＬＳＲ１２０からＬＳＲ１３０に変化させる。パケットは、宛先ＦＥＣの到達可能性に基づいてではなく、当該パケットの出口ＬＳＲの到達可能性に基づいてラベルスイッチングされるため、出口ＬＳＲに対応するエントリのみが更新される必要がある。従って、トポロジー変化に応じて、動作１０．２において、Ｈ−ｌａｂｅｌモジュール１４２は、出口ＬＳＲラベルエントリ１９０のみを変化させて、パケットがＬＳＲ１２０の代わりにＬＳＲ１３０にラベルスイッチングされるようにする。具体的には、Ｈ−ｌａｂｅｌモジュール１４２は、ラベルを（出口ＬＳＲラベルマッピングメッセージ１３４においてＬＳＲ１３０によって広告された）ラベル３に、及びネクストホップをＬＳＲ１３０に変化させる。階層的ラベルエントリ１９２のいずれも変化させられる必要がないことが理解されるべきである。図１０には図示されないが、幾つかの実施形態において、Ｈ−ｌａｂｅｌモジュール１４２は、自身の制御カード上の自身のＭＰＬＳ情報ベースにおけるエントリを変化させ、変化されたエントリのみをＬＳＲ１４０のラインカード上に記憶されるＮＨＬＦＥ構造１８０にダウンロードする。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５８
【補正方法】変更
【補正の内容】
【００５８】
図１１は、一実施形態に係る、図１０に図示されるトポロジー変化の後にＬＳＰの階層を用いる終端局１６０Ａから終端局１５０Ａへの例示的なパケットフローを図示する。終端局１６０Ａは、ＩＰヘッダ（終端局１５０Ａの宛先ＩＰアドレスを伴う）及びデータペイロードを含むパケット１１１０を送信する。ＬＳＲ１４０は、パケットを受信し、ＩＰヘッダに含まれる宛先ＩＰアドレスのＦＥＣを判定する。ＦＥＣに基づいて、対応するＮＨＬＦＥがアクセスされる。当該対応するＮＨＬＦＥは、ラベル１、プッシュ動作、及び出口ＬＳＲ１１０のＮＨＬＦＥへの再帰的ネクストホップを含む。ＬＳＲ１４０は、ラベル１をラベルスタックにプッシュし、再帰的ネクストホップに対応するＮＨＬＦＥにアクセスする。当該ＮＨＬＦＥは、ラベル３、プッシュ動作、及びＬＳＲ１３０へのネクストホップを含む。ＬＳＲ１４０は、ラベル３をラベルスタックにプッシュし、パケット１１１５をＬＳＲ１３０に送信する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
ＬＳＲ１３０は、パケット１１１５を受信する。インカミングラベル３に基づいて、ＬＳＲ１３０は、どのようにパケットを転送するかを判定する。例えば、ＬＳＲ１３０は、インカミングラベル３についての自身のＩＬＭエントリにアクセスし、対応するＮＨＬＦＥを判定する。幾つかの実施形態において、中間ＬＳＲ１３０は、メッセージをＬＳＲ１１０に送信することに先立って、最アウターラベル（出口ＬＳＲ１１０に到達するためのラベル）を除去するように、最終前のホップポッピングを実行する。他の実施形態において、中間ＬＳＲ１３０は、ラベルスワップを実行する。例えば、中間ＬＳＲ１３０は、インカミングラベルを出口ＬＳＲ１１０によって広告されるラベル（例えば、ＮＵＬＬラベル）とスワッピングする。図１１に図示されるように、ＬＳＲ１３０は、パケット１１２０を出口ＬＳＲ１１０に送信することに先立って、パケットのラベルスタックからラベル３をポッピングする。出口ＬＳＲ１１０は、パケット１１２０を受信し、ラベル１に基づいてパケットの宛先を判定する。例えば、出口ＬＳＲ１１０は、インカミングラベル１に基づいて自身のＩＬＭエントリを調べ、宛先が終端局１５０Ａであると判定する。ＬＳＲ１１０は、ラベル１をポッピングし、パケット１１１０を終端局１５０Ａに送信する。
【国際調査報告】
2013541896.tif 000014
2013541896.tif 000015