(57)【特許請求の範囲】
【請求項１】
パケットを第１のノードにおいて受信することであって、パケットが、第２のノードから受信され、宛先ノードに向けられたものであり、
パケットが、インターネットプロトコル（ＩＰ）パケットと、ＩＰパケットの前に付加されたＵターンラベルと、Ｕターンラベルの前に付加されたラベル配布プロトコル（ＬＤＰ）ラベルとを含み、
Ｕターンラベルが、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成されたものであること、および、
第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択することを含む、方法。
【請求項２】
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することをさらに含む、請求項１に記載の方法。
【請求項３】
ＬＤＰラベルが第１のＬＤＰラベルであり、第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することが、
パケットの第２のＬＤＰラベルを決定すること、
パケットから、ＩＰパケットと第２のＬＤＰラベルとを含む修正パケットを形成すること、および、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することを含む、請求項２に記載の方法。
【請求項４】
Ｕターンラベルが第１のＵターンラベルであり、ＬＤＰラベルが第１のＬＤＰラベルであり、第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することが、
パケットの第２のＵターンラベル、およびパケットの第２のＬＤＰラベルを決定すること、
パケット中で受け取られた第１のＵターンラベルを第２のＵターンラベルで置き換え、パケット中で受け取られた第１のＬＤＰラベルを第２のＬＤＰラベルで置き換えて、それにより修正パケットを形成すること、ならびに、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することを含む、請求項２に記載の方法。
【請求項５】
第１のパケットを第１のノードにおいて受信する前に、
ＩＰパケットを第１のノードにおいて受信することであって、ＩＰパケットが第２のノードから受信され、ＩＰパケットが宛先ノードに向けられたものであること、
ＩＰパケットを宛先ノードに向けてルーティングするための第１のルーティングパスを選択すること、および、
選択された第１のルーティングパスに基づいてＩＰパケットを第２のノードに向けて送信することをさらに含む、請求項１に記載の方法。
【請求項６】
第１のルーティングパスのコストが第２のルーティングパスのコストよりも低い、請求項１に記載の方法。
【請求項７】
プロセッサと、プロセッサに通信可能に接続されたメモリとを備える装置であって、プロセッサが、
パケットを第１のノードにおいて受信するように構成され、パケットが、第２のノードから受信され、宛先ノードに向けられたものであり、
パケットが、インターネットプロトコル（ＩＰ）パケットと、ＩＰパケットの前に付加されたＵターンラベルと、Ｕターンラベルの前に付加されたラベル配布プロトコル（ＬＤＰ）ラベルとを含み、
Ｕターンラベルが、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成され、プロセッサが、
第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択するように構成された、装置。
【請求項８】
プロセッサが、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、請求項７に記載の装置。
【請求項９】
ＬＤＰラベルが第１のＬＤＰラベルであり、プロセッサが、
パケットの第２のＬＤＰラベルを決定すること、
パケットから、ＩＰパケットと第２のＬＤＰラベルとを含む修正パケットを形成すること、および、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することによって、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、請求項８に記載の装置。
【請求項１０】
Ｕターンラベルが第１のＵターンラベルであり、ＬＤＰラベルが第１のＬＤＰラベルであり、プロセッサが、
パケットの第２のＵターンラベル、およびパケットの第２のＬＤＰラベルを決定すること、
パケット中で受け取られた第１のＵターンラベルを第２のＵターンラベルで置き換え、パケット中で受け取られた第１のＬＤＰラベルを第２のＬＤＰラベルで置き換えて、それにより修正パケットを形成すること、ならびに、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することによって、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、請求項８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、通信ネットワークに関し、限定ではないがより詳細には、通信ネットワークにおけるパケットの再ルーティングに関する。
【背景技術】
【０００２】
ＲＦＣ（Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔ）５２８６に記載のようなインターネットプロトコル（ＩＰ）ファストリルート（Ｆａｓｔ  Ｒｅｒｏｕｔｅ）は、代替パスをサポートするのに十分な冗長性がネットワーク中にあるときに、機能停止中の損失を被ることなくネットワーク内でトラフィックを転送する技法である。より具体的には、ＲＦＣ５２８６は、障害条件（例えば、リンク、ノード、または共有リスクリンクグループ（ＳＲＬＧ、ｓｈａｒｅｄ  ｒｉｓｋ  ｌｉｎｋ  ｇｒｏｕｐ）の障害）が発生した場合に、純粋なＩＰネットワーク中で、およびラベル配布プロトコル（ＬＤＰ、Ｌａｂｅｌ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）を使用するマルチプロトコルラベルスイッチング（ＭＰＬＳ、Ｍｕｌｔｉｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）ネットワーク中で、ループフリー代替（ｌｏｏｐ−ｆｒｅｅ  ａｌｔｅｒｎａｔｅ）を使用してトラフィックのための局所的保護を提供する技法について述べている。
【０００３】
ＩＰファストリルートを利用する多くのＩＰネットワーク中では、例えば、ＩＰネットワークは、障害が発生したコンポーネントがＩＰネットワーク中に存在するのではないと仮定して、最短パスアルゴリズムを再実行することによって障害から回復することができる。これは一般に、ＩＰネットワークがそれを介してトラフィックの転送を再開できる代替ルートに至る。しかし、不利なことに、ＬＤＰのコンテキスト内で代替ルートを介してパケットを再ルーティングするのは一般に、音声および他のアプリケーションに対する顧客サービス品質（ＱｏＳ）期待に添うには遅すぎ（例えば、関連する回復／リルート時間は数秒を超える）、さらに、ドロップされたリンクに関連するノードに転送されたパケットは、ネットワークの一部を使用不可能にする恐れのあるループ条件を生み出すような形でルーティングされることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
Ｕターン高速再ルーティング能力の実施形態により、従来技術における様々な欠陥に対処する。
【課題を解決するための手段】
【０００５】
一実施形態では、方法は、パケットを第１のノードにおいて受信することを含み、パケットは、第２のノードから受信され、宛先ノードに向けられたものであり、パケットは、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成されたＵターンラベルを含む。方法はまた、第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択することを含む。
【０００６】
一実施形態では、装置はプロセッサを備え、プロセッサは、パケットを第１のノードにおいて受信するように構成され、パケットは、第２のノードから受信され、宛先ノードに向けられたものであり、パケットは、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成されたＵターンラベルを含む。プロセッサはまた、第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択するように構成される。
【０００７】
一実施形態では、方法は、宛先ノードに向けられたパケットを第１において受信することを含み、パケットは、第２のノードによる、パケットのための第１のルーティングパスの選択に基づいて、第２のノードから受信される。方法はまた、第１のノードにおいてＵターンラベルをパケットに挿入して、それにより修正パケットを形成することを含み、Ｕターンラベルは、第２のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第１のノードによって第２のノードに返されつつあることを第２のノードに知らせるように構成される。方法はまた、パケットを宛先ノードに向けてルーティングするために第２のルーティングパスが第２のノードによって選択されるべきであることを第２のノードに示すために、修正パケットを第１のノードから第２のノードに向けて送信することを含む。
【０００８】
一実施形態では、装置はプロセッサを備え、プロセッサは、宛先ノードに向けられたパケットを第１において受信するように構成され、パケットは、第２のノードによる、パケットのための第１のルーティングパスの選択に基づいて、第２のノードから受信される。プロセッサはまた、第１のノードにおいてＵターンラベルをパケットに挿入して、それにより修正パケットを形成するように構成され、Ｕターンラベルは、第２のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第１のノードによって第２のノードに返されつつあることを第２のノードに知らせるように構成される。プロセッサはまた、パケットを宛先ノードに向けてルーティングするために第２のルーティングパスが第２のノードによって選択されるべきであることを第２のノードに示すために、修正パケットを第１のノードから第２のノードに向けて送信するように構成される。
【０００９】
本明細書の教示は、添付の図面と共に後続の詳細な記述を考察することによって、すぐに理解することができる。
【図面の簡単な説明】
【００１０】
【図１】Ｕターンラベルを使用してＬＤＰパケットの迅速な再ルーティングを容易にすることを示す例示的な通信ネットワークを示す図である。
【図２】ＬＤＰラベルを有する元のパケットと、ＬＤＰラベルおよびＵターンラベルを有する元のパケットとを例示する一実施形態を示す図である。
【図３】Ｕターンラベルを使用したＬＤＰパケットの迅速な再ルーティングをサポートするように図１の例示的な通信システムのノードを構成する方法の一実施形態を示す図である。
【図４】Ｕターンラベルを使用したＬＤＰパケットの迅速な再ルーティングの方法の一実施形態を示す図である。
【図５】パケットが故意にノードに返されつつあることをパケット送信元ノードに知らせるためにターゲットノードがＵターンラベルをパケットに追加できるようにする方法の一実施形態を示す図である。
【図６】ノードにおいて受信されたパケットを処理する方法の一実施形態を示す図である。
【図７】ノードにおいて受信されたパケットを処理する方法の一実施形態を示す図である。
【図８】本明細書に記述される機能を実施する際に使用するのに適したコンピュータの、高レベルのブロック図である。
【発明を実施するための形態】
【００１１】
理解を容易にするために、可能な場合には、各図に共通の同一要素を示すのに同一の参照番号が使用されている。
【００１２】
本明細書では、Ｕターン高速再ルーティング能力が図示および記述される。Ｕターン高速再ルーティング能力は、パケットのドロップを防止し転送ループの形成を防止するようにして、パケットの高速再ルーティングを可能にする。
【００１３】
本明細書では主に、ラベル配布プロトコル（ＬＤＰ）を実行するインターネットプロトコル（ＩＰ）／マルチプロトコルラベルスイッチング（ＭＰＬＳ）ネットワークのコンテキスト内で、Ｕターン高速再ルーティング能力が図示および記述されるが、他の適切なプロトコルを使用する他の適切なタイプの通信ネットワーク中でＵターン高速再ルーティング能力が利用されてもよいことは理解されるであろう。
【００１４】
Ｕターン高速再ルーティング能力の様々な実施形態は、ソースノード（Ｓ）が宛先ノード（Ｄ）にトラフィックを送信しており、ネットワークがＳからＤへの２つの異なるパスを含むような、ネットワークの例を最初に考察することによって、よりよく理解することができる。この例では、２つのパスのうちの第１のパスが、第１の中間ノード（Ａ）を横断してパスＳ−Ａ−Ｄを形成し、２つのパスのうちの第２のパスが、第２の中間ノード（Ｂ）を横断してパスＳ−Ｂ−Ｄを形成するものとする。この例ではさらに、ノード間の全てのリンクのリンク重みは同じであるものとする。
【００１５】
この例では、トラフィックは、Ｓ−Ａリンクに障害が発生するまでは第１の（通常）パスＳ−Ａ−Ｄ上を流れており、Ｓ−Ａリンクに障害が発生した時点で、ネットワークのルーティングプロトコルは、Ｓ−Ａリンクを無視して最短パスアルゴリズムを実行し、したがって第２の（代替）パスＳ−Ｂ−Ｄを識別するものとする。この回復時間は、通常は約数秒であり、この間に、Ｄに宛てられたパケットは、Ｄへの代替パスがないせいで、Ｓにおいてドロップされる。トラフィックが向けられた対象である、Ｄにおけるアプリケーションが、損失から回復できる場合、アプリケーションは、回復期間中におそらくは些細な不調を伴うだけで、継続することができる。このことは、Ｄにおけるアプリケーションが紛失パケットを無視できる（例えば音声もしくはビデオアプリケーションがそうすることがあるように）か、または、Ｓにおけるアプリケーションが紛失パケットをＤに再送できる（例えばＦＴＰ転送がそうすることがあるように）ことを意味し得る。しかし、この手法では、多くのアプリケーションにとっては回復時間が重大である可能性がある（例えば、音声アプリケーションは通常、妥当な対話性のためには２５０ミリ秒未満の往復応答時間を予期し、したがって、前述の例におけるような機能停止回復シナリオの間に３秒から５秒の不足音声パケットがあるのは許容できない）。
【００１６】
前述の例の問題に対する一解決法は、パケットが紛失しないようにＢがＤにパケットを転送するであろうと予期して、ＳがＢにパケットを送信することである。例えば、Ｓが、ＢからＤへのパスを計算し、このパスがＤへのパケット転送に安全なパスであると判定した場合は、Ｓは、Ｂが、Ｓから受信したパケットを転送するための最良のパスとしてパスＢ−Ｄを識別することによってＤにパケットを転送するであろうと予期して、Ｂにパケットを送信することができる。上の例では、ノード間の全てのリンクのリンク重みが同じであると仮定すると、Ｂは、Ｓから受信したパケットを転送するための最良のパスとしてパスＢ−Ｄを識別することになり、したがってＤにパケットを転送することになる。しかし、Ｂが、Ｓから受信したパケットを転送するための最良のパスとしてパスＢ−Ｄを識別せず、したがってパケットをパスＢ−Ｄに沿ってＤに向けて転送するのではなくパスＢ−Ｓ−Ａ−Ｄに沿ってＳに転送することになるような、いくつかの状況が生じる場合がある。これらの状況は、前述の例に対する２つの修正形を考察することによって、よりよく理解することができる。
【００１７】
上の元の例では、ノードＢとＤの間にリンクがある。ここで、ノードＢとＤの間にリンクがない、上の例の修正バージョンを考えてみる。この場合、ＢからＤへの最良の（かつ唯一の）パスは、パスＢ−Ｓ−Ａ−Ｄを経由するものである。この結果、この修正例では、Ｂは、リンクＳ−Ａに障害が発生したことを知るまで、Ｓから受信したパケットをＳに転送し返し続けることになる。しかし、この結果、ＳとＢの間の転送ループがきつくなり、これによりネットワークの一部が使用不可能になる（例えば、パケットの生存時間（ＴＴＬ）フィールドが０に達してパケットがドロップされるまで）。したがって、Ｓは、パスが安全である（すなわちＢからＤへのパスがＳに戻らない）場合にのみ、Ｂにパケットを転送すべきである。この例では、ＢからＤへのパスがないので、Ｓがすべき最善のことは、Ｄに向けられたパケットをドロップすることである（これは、障害が検出されて最短パスアルゴリズムが実行された後に行われることになる）。
【００１８】
上の元の例では、ノード間の全てのリンクの重みは同じである。ここで、リンクＢ−Ｄの重みが、リンクＢ−Ｓ、Ｓ−Ａ、Ａ−Ｄの重みを結合した重みよりも大きい、上の例の修正バージョンを考えてみる。この場合、ＢからＤへのパスは２つあるが、重みが異なるため、Ｂは、パスＢ−Ｓ−Ａ−ＤをパスＢ−Ｄよりもよいパスと見なすことになる。この結果、この修正例では、Ｂは、リンクＳ−Ａに障害が発生したと知りルーティングプロトコルが収束するまで、パスＢ−Ｓ−Ａ−Ｄを最良パスとして識別し続けることになり、したがって、ループ条件が結果的に生み出されるようにしてパケットを転送し続けることになる。これにより、やはりネットワークのこの部分が使用不可能になる。
【００１９】
このようなループが形成されるのを防止することのできる、Ｕターン再ルーティング能力の様々な実施形態は、最初に図１を考察することによってよりよく理解することができる。
【００２０】
図１に、Ｕターンラベルを使用してＬＤＰパケットの迅速な再ルーティングを容易にすることを示す例示的な通信ネットワークを示す。
【００２１】
一般に、通信ネットワーク１００は、任意の適切なネットワークとして実現されてよく、したがって、任意の適切なプロトコルを実行する任意の適切なタイプ（複数可）のノードを含むことができる。一実施形態では、例えば、通信ネットワーク１００は、ＬＤＰを実行するラベルスイッチングルータ（ＬＳＲ）を含むＩＰ／ＭＰＬＳネットワークとして実現される。通信ネットワーク１００がいずれか他の適切な方式で実現されてもよいことは理解されるであろう。
【００２２】
図１に示されるように、通信ネットワーク１００は、ソースノード１１０Ｓ（本明細書ではノードＳとも呼ばれる）および宛先ノード１１０Ｄ（本明細書ではノードＤとも呼ばれる）を含み、これらはそれぞれ、２つの中間ノード１１０Ａおよび１１０Ｂ（本明細書ではそれぞれノードＡおよびＢとも呼ばれる）に接続される。ノードＳは、１対のリンク１２０ＳＡおよび１２０ＳＢ（本明細書ではそれぞれリンクＳ−ＡおよびＳ−Ｂとも呼ばれる）を介して、ノードＡおよびＢに接続される。ノードＤは、１対のリンク１２０ＤＡおよび１２０ＤＢ（本明細書ではそれぞれリンクＤ−ＡおよびＤ−Ｂとも呼ばれる）を介して、ノードＡおよびＢに接続される。リンク１２０ＳＡ、１２０ＳＢ、１２０ＤＡおよび１２０ＤＢのリンク重みは、それぞれ１、１、１、および４である。
【００２３】
図１にさらに示されるように、各ノード１１０は、本明細書に図示および記述されるＵターン高速再ルーティング能力の様々な機能をサポートするように構成される。例えば、各ノード１１０は、プロセッサ１１１およびメモリ１１２を備え、メモリ１１２は、ルーティングテーブル１１３およびＵターンプログラム１１４を含む。
【００２４】
ノード１１０のルーティングテーブル１１３は、第１の規則（通常ルーティングパスに関連する）を使用してＩＰパケットをルーティングし、第２の規則（通常ルーティングパスに関連する）を使用してＵターンラベルを含まないＬＤＰパケットをルーティングし、第３の規則（代替ルーティングパスに関連する）を使用してＵターンラベルを含むＬＤＰパケットをルーティングするなど、異なるタイプの規則を使用して異なるタイプのパケットをルーティングすることをサポートするように構成される。
【００２５】
一実施形態では、例えば、所与の宛先ノードに対して、ルーティングテーブル１１３は以下のように３つの規則を含む。
【００２６】
（１）ＩＰパケットが受信されたとき：転送等価クラス（ＦＥＣ、Ｆｏｒｗａｒｄｉｎｇ  Ｅｑｕｉｖａｌｅｎｃｅ  Ｃｌａｓｓ）を使用してパケットのネクストホップラベルを見つけ、ネクストホップラベルを挿入し、パケットを通常ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する。
【００２７】
（２）現在のネクストホップＬＤＰラベルを有するＬＤＰラベルパケット（すなわち、Ｕターンラベルが関連付けられていない、通常どおりにラベル付けされたＬＤＰパケット）が受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットを通常ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する。
【００２８】
（３）現在のネクストホップＬＤＰラベルおよびＵターンラベルを有するＬＤＰラベルパケットが受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットを代替ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する（任意選択で、ノード１１０のローカルＵターンラベルを決定し、Ｕターンラベルをノード１１０のローカルＵターンラベルで置き換えることも含んでよい）。
【００２９】
Ｕターンプログラム１１４は、Ｕターン高速再ルーティング能力の様々な機能をサポートするように構成される。例えば、ノード１１０のＵターンプログラム１１４は、ノード１１０が、ＬＤＰパケットの迅速な再ルーティングを容易にするためのＵターンラベルの使用をサポートするようにノード１１０自体を構成する際に使用されるＵターンラベルをピアノード１１０と交換できるようにすること、Ｕターンラベルを含むパケットが受信されたときにノード１１０によって使用される代替ルーティングパスを含めるようにノード１１０のルーティングテーブル１１３を構成すること、いくつかの条件下で代替ルーティングパスを使用するようピアノード１１０に知らせるためにＵターンラベルをパケットに挿入することなど、ならびにこれらの様々な組合せを行うように構成されてよい。
【００３０】
本明細書に記述されるように、本明細書でＵターンラベルとして示される特別なラベルの使用を通して、パケットルーティングループ条件を回避することができる。Ｕターンラベルを使用してパケットルーティングループ条件を回避することは、図１の通信ネットワーク１００内におけるＵターンラベルの例示的な使用を考察することによって、よりよく理解することができる。この例では、ノードＳは、リンクＳ−Ａに障害が発生するまではノードＡを介してノードＤにパケットを送信しており、リンクＳ−Ａに障害が発生した時点で、ノードＳはノードＢを介してノードＤにパケットを送信しようとし始めるものとする。ノードＢは、ノードＤに向けられたパケットをノードＳから受信すると、そのルーティングテーブルを使用してノードＤへの最良パスを決定し、決定したパスに従ってパケットを転送する。この例では、ノードＢはリンクＳ−Ａが利用不可能であることを意識していないので、また、リンク１２０のリンク重みを仮定すると、ノードＢのルーティングテーブルは、パスＢ−Ｓ−Ａ−ＤがノードＤへの通常ルーティングパスでありパスＢ−ＤがノードＤへの代替ルーティングパスであるように、構成される。この結果、パケットがＵターンラベルを含まないので、ノードＢは、ノードＳから受信したパケットをノードＳに向けて転送し返す。ノードＳは、ノードＢからパケットを受信すると、パケットがノードＡを介してノードＤに転送できないことに気付き、したがってパケットをノードＢに返送する。しかし、ノードＳは、それ自体とノードＢとの間のパケットルーティングループを回避するために、パケットをノードＢに返送する前にＵターンラベルをパケットに挿入する。Ｕターンラベルは、パケットがノードＳによって故意にノードＢに返されつつあること（すなわち、通常ルーティングに基づいてノードＢによってそのルーティングテーブルから選択された通常ルーティングパスには、条件が関連するので）、および、パケットをノードＤにルーティングする際に使用される代替ルーティングパスをノードＢが選択すべきであることを、ノードＢに知らせるように構成される。前述のように、ノードＢが最初にパケットを受信したとき、ノードＢは、通常ルーティングパスＢ−Ｓ−Ａ−Ｄを、ノードＤへの最良パスであるとして選択した（パケット中にＵターンラベルがないため）。しかし、Ｕターンラベルを含むパケットを受信すると、次いでノードＢは、通常ルーティングパスＢ−Ｓ−Ａ−Ｄを選択するのではなく代替ルーティングパスＢ−Ｄを選択する（すなわち、ノードＳではなくノードＤにパケットを転送する）ことを知る。このようにして、Ｕターンラベルにより、ノードＢは、パケットのネクストホップノード（例えば、通常ルーティングが適用されるときはノードＳ）を選択するときにその通常ルーティングを迂回し、その代わり、パケットのネクストホップノード（例えば、Ｕターン機構が適用されるときはノードＤ）を選択するときにそのＵターン機構を利用することができる。次いでノードＢは、パケットをノードＳではなくノードＤに転送し、それにより、Ｕターン高速再ルーティング能力がなければノードＢとＳの間で通常なら生じたであろうパケットルーティングループを回避する。本明細書に記述されるように、ノードＢは、ノードＳから返されたパケットを受信すると、そのルーティングテーブルを使用して通常ルーティングパスの代わりに代替ルーティングパスを選択することができ、そのルーティングテーブルは、受信パケットがＵターンラベルを含むか否かに応じて、受信パケット転送のために異なるパケットルーティング規則を適用するように構成される。ノードＢは、パケットをノードＤに転送するとき、それ自体のＵターンラベルをパケットに挿入することができる（これはこの例では必須ではないが、ノードＢとノードＤとの間に１つまたは複数の中間ノードがある場合に、Ｕターン手法が適用されていることを中間ノード（複数可）に知らせることができるように、使用することができる）。
【００３１】
上の例に関して述べたように、各ノード１１０は、いくつかの条件下でＵターンラベルをパケットに挿入するように、かつ、受信パケットがＵターンラベルを含むか否かに基づいてこれらの受信パケットを処理するように構成される。したがって、各ノード１１０は、Ｕターンラベルの使用をサポートするように構成され、このサポートは、以下を含み得る。すなわち、各ノード１１０をそれ自体のＵターンラベル（複数可）で構成すること、各ノード１１０を、そのピアノード（複数可）１１０によって使用されているＵターンラベル（複数可）に関する情報を有するように構成すること、Ｕターンラベルを含まないパケットについては通常ルーティングパスを選択し、Ｕターンラベルを含むパケットについては代替ルーティングパスを選択することができるようにして、各ノード１１０のルーティングテーブル１１３を構成することなど、ならびにこれらの様々な組合せを含み得る。
【００３２】
一実施形態では、各ノード１１０には、１つまたは複数のＵターンラベルが割り当てられてよい。ノード１１０に１つまたは複数のＵターンラベルが割り当てられるかどうかの判定は、ノード１１０間で交換されているパケットの構造、および、例示的な通信ネットワーク１００内での転送等価クラス（ＦＥＣ、Ｆｏｒｗａｒｄｉｎｇ  Ｅｑｕｉｖａｌｅｎｃｅ  Ｃｌａｓｓ）の扱いに基づくことができる。
【００３３】
一般に、ＦＥＣは、パケットに対する転送決定が常に同じであるような１組のパケットを識別する。例えば、ルート１０．１０．１／２４がノードＤによって広告された場合は、ノードＢは、このルートに宛てられた全てのパケット（すなわち、１０．１０．１１から１０．１０．１．２４までの宛先ＩＰアドレスを有する全てのパケット）がノードＳに送信されるべきであることを知る（例示的な通信ネットワーク１００の全てのリンクが動作していると仮定して）。
【００３４】
ＬＤＰでは、Ｕターン高速再ルーティング能力が使用されない場合、このＦＥＣを示すためにＬＤＰラベルが割り当てられることになる。例えば、パケット交換前に、ノードＳは、ＦＥＣ１０．１０．１／２４についてのラベル（例えばラベル１００またはいずれか他の適切な値）をノードＢに送信済みであることになり、このラベルは、１０１．１０．１／２４中のＩＰアドレスのいずれかに宛てられたパケットをノードＢが有する場合にノードＢがこのＬＤＰラベル（すなわち１００）をパケット上に配置すべきであることを、ノードＢに示す。同様に、例えば、パケット交換前に、ノードＢは、ＦＥＣ１０．１０．１／２４についてのラベル（例えばラベル２００またはいずれか他の適切な値）をノードＳに送信済みであることになり、このラベルは、１０．１０．１／２４中のＩＰアドレスのいずれかに宛てられたパケットをノードＳが有する場合にノードＳがこのＬＤＰラベル（すなわち２００）をパケット上に配置すべきであることを、ノードＳに示す。これにより、ノードＳおよびＢは、どのようにパケットが転送されるかを素早く決定することができる。
【００３５】
Ｕターンラベルを有するパケットが、ＦＥＣを識別するのに使用される元のＬＤＰラベルとＵターンラベルとの両方を含むような一実施形態では、ＬＤＰラベルがあることにより、単一のＵターンラベルを全てのＦＥＣにわたって使用することができ、したがって、各ノード１１０は、そのピアノード１１０と交換するために単一のＵターンラベルを割り振るだけで済む。このような一実施形態による例示的なパケットが、図２に関して図示および記述される。
【００３６】
例として、ノードＢは、ノードＤのＦＥＣについての通常のＬＤＰラベルと、ノードＢがパケットをルーティングする先である任意のＦＥＣと共に使用されるＵターンラベルとを、ノードＳに提供することができる。この例では、ノードＡに障害が発生したとき、ノードＳは、ノードＤのＦＥＣについての通常のＬＤＰラベルと、ノードＢのＵターンラベルとを含む２ラベルスタックを使用して、ノードＢにパケットを送信することになる。この結果、次いでノードＢは、通常のパケット転送をオーバライドすることになり（パケットが、ノードＤのＦＥＣについての通常のＬＤＰに加えて、ノードＢのＵターンラベルも含むので）、したがって、パケットをノードＳに返すのではなくノードＤに転送することになる。この手法の利点の１つは、サポートされるＦＥＣの数にかかわらず単一のラベルＵターンラベルを使用するだけで済むことである。しかし、この利点は、Ｕターン高速再ルーティング能力をサポートするためにパケットルーティング時に２ラベルスタックを使用しなければならないことを代償とする。
【００３７】
Ｕターンラベルを有するパケットが、Ｕターンラベルしか含まず、ＦＥＣを識別するのに使用される元のＬＤＰラベルを含まないような一実施形態では、ＬＤＰラベルがパケット内にないことにより、複数のＦＥＣに対して複数のＵターンラベルを使用することが必要とされる場合があり、したがって、各ノード１１０は、そのピアノード１１０と交換するために複数のＵターンラベル（例えば各ＦＥＣにつき１つ）を割り振る必要がある場合がある。
【００３８】
例として、ノードＢは、ノードＤのＦＥＣについての通常のＬＤＰラベルと、ノードＤのＦＥＣについてのＵターンラベルとをノードＳに提供することができ、したがって、ノードＡに障害が発生したとき、ノードＳは、２つのラベル（すなわちノードＤのＦＥＣについての通常のＬＤＰラベルと、ノードＤのＦＥＣについてのＵターンラベル）を使用するのではなく、単一のラベル（すなわちノードＤのＦＥＣのＵターンラベル）を使用して、ノードＢにパケットを送信することを選択することができる。この結果、次いでノードＢは、通常のパケット転送をオーバライドすることになり（パケットが、ノードＤのＦＥＣについての通常のＬＤＰラベルではなく、ノードＤのＦＥＣのＵターンラベルを含むので）、したがって、パケットをノードＳに返すのではなくノードＤに転送することになる。この手法の利点の１つは、通常ルーティングとＵターンルーティングとを区別するのに、パケット中で単一のラベル（２つのラベルのスタックではなく）しか必要とされないことである。しかし、この利点は、Ｕターン高速再ルーティング能力がない場合に通常なら必要とされることになるよりも多数のラベルを使用および管理しなければならないことを代償とする（例えば、あらゆるＦＥＣに、通常のラベルとＵターンラベルとが割り当てられる必要があるので）。
【００３９】
上に示されるように、各ノード１１０は、Ｕターンベースのパケット再ルーティングを示すときに使用することになるＵターンラベル（複数可）をピアノード（複数可）に知らせるために、そのＵターンラベル（複数可）をそのピアノード（複数可）１１０と交換する。ノード１１０は、任意の適切な方式でＵターンラベルを交換することができる。一実施形態では、例えば、ノード１１０は、ＬＤＰセッション確立処理の一部として、Ｕターンラベルを交換することができる。例えば、２つのピアノード１１０間でＬＤＰセッションが確立されつつあるとき、ピアノード１１０は、それらのＵターンラベルを交換する（例えば、ノード１１０のうちの一方がそのＵターンラベル（複数可）をノード１１０のうちの他方に送信し、またその逆も行う）。一実施形態では、例えば、ノード１１０は、別個のＵターンラベル交換処理の一部として、Ｕターンラベルを交換することができる。ノード１１０は、いずれか他の適切な方式でＵターンラベル１１０を交換することもできる。
【００４０】
本明細書に記述されるように、ノード１１０によって交換されたＵターンラベルは、後でパケットルーティングの間にノード１１０によって使用されるが、この場合、ノード１１０は、パケットがＵターンラベルを含むか否かに基づいて、異なるようにパケットをルーティングする（例えば、パケットがＵターンラベルを含まないときは通常ルーティングパスを使用し、パケットがＵターンラベルを含むときは代替ルーティングパスを使用する）ように構成される。したがって、Ｕターンラベルをノード１１０に関連付けてノード１１０がそれらのＵターンラベルをそれらのピアノード１１０と交換できるようにすることによってノード１１０を構成することに加えて、ノード１１０はまた、Ｕターンラベルを有するパケットがノード１１０において受信されたときに代替ルーティングパスの選択をサポートするようにも構成される。
【００４１】
一実施形態では、Ｕターンラベルをこのようにして後で使用できるようにするために、ターゲットノード１１０がＵターンラベル交換中にピアノード１１０からＵターンラベルを受信すると、ターゲットノード１１０は、Ｕターンラベルを有するパケットが受信されたときに使用されることになる１つまたは複数の代替ルーティングパスを計算し、代替ルーティングパス（複数可）を含むようにそのルーティングテーブル１１３を更新する。
【００４２】
ターゲットノード１１０によって計算された代替ルーティングパス（複数可）は、ターゲットノード１１０がＵターンラベルを交換した相手であるピアノード１１０から受信したパケットのためにターゲットノード１１０によって必要とされる場合のある、任意の代替ルーティングパス（複数可）を含んでよい。
【００４３】
ターゲットノードのルーティングテーブル１１３は、任意の適切な方式で更新することができる（例えば、ある宛先ノードに関連する単一のエントリに複数の規則を関連付けること、ある宛先ノードに対して複数のエントリを提供すること（各エントリは、受信パケットに関連する異なる条件下でアクセスされる）など、ならびにこれらの様々な組合せ）。ルーティングテーブルは各宛先ノードにつき２つの規則／エントリをすでに含む場合があるので、ある宛先ノードに向けられたパケットがＵターンラベルを含むときにこの宛先ノードに対して使用されることになる代替パスを計算する結果として、各宛先ノード当たりの規則／エントリは３つになる。前述のように、この３つの規則／エントリは、以下のように定義することができる。
【００４４】
（１）ＩＰパケットが受信されたとき：ＦＥＣを使用してパケットのネクストホップラベルを見つけ、ネクストホップラベルを挿入し、パケットを通常ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する。
【００４５】
（２）現在のネクストホップＬＤＰラベルを有するＬＤＰラベルパケット（すなわち、Ｕターンラベルが関連付けられていない、通常どおりにラベル付けされたＬＤＰパケット）が受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットを通常ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する。
【００４６】
（３）現在のネクストホップＬＤＰラベルおよびＵターンラベルを有するＬＤＰラベルパケットが受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットを代替ルーティングパスに沿ってノード１１０から宛先ノードに向けて転送する（任意選択で、ノード１１０のローカルＵターンラベルを決定し、Ｕターンラベルをノード１１０のローカルＵターンラベルで置き換えることも含んでよい）。
【００４７】
例えば、前述の図１の例では、ノードＢおよびＳがそれらのＬＤＰセッションの確立中にＵターンラベルを交換したとき、ノードＢは、ノードＳのＵターンラベルを有するパケットをノードＢがノードＳから受信する状況に対して、ノードＤへの代替ルーティングパスを計算した。この例では、ノードＢにおいて、ノードＤへの通常ルーティングパスは、ルーティングパスＢ−Ｓ−Ａ−Ｄであり、ノードＳから受信されたＵターンラベルに対してノードＢによって計算された代替ルーティングパスは、ルーティングパスＢ−Ｄである。この結果、宛先ノードＤについての、ノードＢのルーティングテーブルは、以下の３つの規則／エントリを含むことになる。
【００４８】
（１）ＩＰパケットが受信されたとき：ＦＥＣを使用してパケットのネクストホップラベルを見つけ、ネクストホップラベルを挿入し、パケットをノードＢからノードＳに向けて転送する。
【００４９】
（２）現在のネクストホップＬＤＰラベルを有するＬＤＰラベルパケット（すなわち、Ｕターンラベルが関連付けられていない、通常どおりにラベル付けされたＬＤＰパケット）が受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットをノードＢからノードＳに向けて転送する。
【００５０】
（３）現在のネクストホップＬＤＰラベルおよびＵターンラベルを有するＬＤＰラベルパケットが受信されたとき：ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットをノードＢからノードＤに向けて転送する。
【００５１】
本明細書に記述されるように、Ｕターンラベルは、第１のノードによって第２のノードに返されつつあるパケット（このパケットは、第２のノードが、第２のノードにおいて選択された通常ルーティングパスを使用して第１のノードに送信した）が、通常ルーティングパスを使用したパケットのルーティングを妨げる条件のために故意に第２のノードに返されつつあることを第１のノードが第２のノードに知らせ、それにより、パケットのルーティングで使用される代替ルーティングパスを選択するよう第２のノードに指示することができるように、構成される。したがって、ノード１１０によって使用されるＵターンラベルは、任意の適切な方式で（例えば任意の適切なフォーマット、値などを使用して）構成することができる。Ｕターンラベルは、ＩＰパケットのＩＰヘッダ内では伝搬できないであろう情報の通信を可能にする（例えば、Ｕターンラベルによって通信される情報を通信するのに使用できるビットがＩＰパケットのＩＰヘッダ中にない場合に）ことは、理解されるであろう。一実施形態では、Ｕターンラベルは、図２に示すように実現することができる。
【００５２】
図２に、ＬＤＰラベルを有する元のパケットと、ＬＤＰラベルおよびＵターンラベルを有する元のパケットとを例示する一実施形態を示す。ＬＤＰラベルを有する元のパケット２１０は、ＩＰパケット２１１（ペイロード２１２およびＩＰヘッダ２１３を有する）を含み、ＩＰパケット２１１の前にはＬＤＰラベル２１５が付加されている。ＬＤＰラベルおよびＵターンラベルを有する元のパケット２２０は、ＩＰパケット２２１（ペイロード２２２およびＩＰヘッダ２２３を有する）を含み、ＩＰパケット２２１の前にはＵターンラベル２２４が付加されており、Ｕターンラベル２２４の前にはＬＤＰラベル２２５が付加されている。本明細書では主に、ＩＰパケット２２１およびＬＤＰラベル２２５に対するＵターンラベル２２４の特定の配置に関して図示および記述されるが、ＩＰパケット２２１およびＬＤＰラベル２２５に対するＵターンラベル２２４の、いずれか他の適切な配置（複数可）を使用してもよいことは理解されるであろう。
【００５３】
図３に、Ｕターンラベルを使用したＬＤＰパケットの迅速な再ルーティングをサポートするように図１の例示的な通信システムのノードを構成する方法の一実施形態を示す。方法３００は、ターゲットノードによるピアノードとの対話に基づいて、ターゲットノードによって実行される。
【００５４】
ステップ３０２で、方法３００が開始する。
【００５５】
ステップ３０４で、ターゲットノードは、ピアノードとＵターンラベルを交換する。ターゲットノードは、１つまたは複数のＵターンラベルをピアノードに送信し、１つまたは複数のＵターンラベルをピアノードから受信する。本明細書に記述されるように、Ｕターンラベルの交換は、ターゲットノードおよびピアノードが参加するＬＤＰセッション確立処理の一部として実施することができる。
【００５６】
ステップ３０６で、ターゲットノードは、ピアノードから受信したパケットが、Ｕターンラベル交換中にピアノードから提供されたＵターンラベル（複数可）を含むときに使用されることになる、１つまたは複数の代替ルーティングパスを計算する。
【００５７】
ステップ３０８で、ターゲットノードは、代替ルーティングパス（複数可）と、Ｕターンラベル交換中に受信したＵターンラベル（複数可）とを使用して、そのルーティングテーブルを更新する。ルーティングテーブルは、任意の適切な方式で、代替パスを反映するように更新することができる（例えば、ルーティングテーブルの既存のエントリ内で代替パスに対する新しい規則を含めること、ルーティングテーブル内で代替パスに対する新しいエントリを作成することなど、ならびにこれらの様々な組合せ）。
【００５８】
ステップ３１０で、方法３００は終了する。
【００５９】
図４に、Ｕターンラベルを使用したＬＤＰパケットの迅速な再ルーティングの方法の一実施形態を示す。
【００６０】
図４に示されるように、方法４００は、第１のノードおよび第２のノードによって実施されるステップを含み、方法４００のステップの一部は第１のノードによって実施され、方法４００のステップの一部は第２のノードによって実施される。よって、方法４００は、単一の方法として示されているが、第１のノード上で実行される１つまたは複数の処理、および第２のノード上で実行される１つまたは複数の処理として実施することができ、したがって２つ以上の協働処理と見なすことができることは、理解されるであろう。
【００６１】
方法４００に関して、第２のノードは、第１のノードおよび第３のノードに接続される。第２のノードはルーティングテーブルを有し、このルーティングテーブルは、所与の宛先ノードについて、第１のノードを宛先ノードに向けたネクストホップノードとして識別する通常ルーティングパスと、第３のノードを宛先ノードに向けたネクストホップノードとして識別する代替ルーティングパスとを含む。
【００６２】
方法４００に関して、方法４００に関連する第１、第２、および第３のノードは、図１のいずれかのピアノード１１０に対応し得る。例えば、図１のコンテキスト内で提供される例では、ノードＳが第１のノードであり、ノードＢが第２のノードであり、ノードＤが第３のノードである。
【００６３】
ステップ４０２で、方法４００が開始する。
【００６４】
ステップ４０４で、第１のノードは、第２のノードに向けてパケットを送信する。ステップ４０６で、第２のノードは、第１のノードからパケットを受信する。一実施形態では、パケットは、ＬＤＰパケット（すなわちネクストホップＬＤＰラベルが前に付加されたＩＰパケット）である。パケットは、宛先ノードに向けられている。
【００６５】
ステップ４０８で、第２のノードは、パケットの転送を決定する。第２のノードは、宛先ノードと、パケットがＵターンラベルを含むか否かに関する第２のノードによる決定とに基づいて、パケットの転送先となるネクストホップノードを決定する（すなわち、パケットがＵターンラベルを含まないときは、宛先ノードへの通常ルーティングパスが選択され、パケットがＵターンラベルを含むときは、宛先ノードへの代替ルーティングパスが選択される）。この場合は、パケットがＵターンラベルを含まないので、第２のノードは、意図された宛先ノードに向けたパケットのルーティングに使用されることになる通常ルーティングパスを識別する。前述のように、通常ルーティングパスは、第１のノードをネクストホップノードとして識別する。
【００６６】
ステップ４１０で、第２のノードは、決定されたネクストホップノード（すなわち第１のノード）への転送のためにパケットを修正する。第２のノードは、パケットのネクストホップＬＤＰラベルを決定し、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換える。
【００６７】
ステップ４１２で、第２のノードは、修正パケットを第１のノードに向けて転送する。ステップ４１４で、第１のノードは、第２のノードからパケットを受信する。パケットはＬＤＰパケットだが、これは、前に第１のノードから第２のノードに送信されたのと同じＩＰパケットであり、また、第２のノードによってＬＤＰパケットの前に付加されたネクストホップＬＤＰラベルを含む。
【００６８】
ステップ４１６で、第１のノードは、パケットを、前に第１のノードによって第２のノードに送信されたパケットであると識別する。
【００６９】
ステップ４１８で、第１のノードは、そのルーティングテーブルを使用して、宛先ノードに基づいて、パケットの転送先となるネクストホップノードを決定する。この場合は、パケットがＵターンラベルを含まないので、第１のノードは、意図された宛先ノード（この場合もやはり第２のノード）に向けたパケットのルーティングに使用されることになる通常ルーティングパスを識別する。この結果、第１のノードがパケットを故意に第２のノードに返しつつあること、および第２のノードがパケットをルーティングするための代替ルーティングパスを選択すべきであることを、第２のノードに知らせるために（すなわち第１のノードと第２のノードとの間で転送ループが形成されるのを防ぐために）、第１のノードは、第２のノードに返されるパケットにＵターンラベルが挿入されるべきであると決定する。
【００７０】
ステップ４２０で、第１のノードは、決定されたネクストホップノードへの転送（すなわち第２のノードへの返送）のために、パケットを修正する。第１のノードは、パケットのネクストホップＬＤＰラベルを決定し、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換える。第１のノードはまた、Ｕターンラベル（例えば、Ｕターンラベルの交換中に第２のノードから第１のノードに提供されたＵターンラベル）を決定し、Ｕターンラベルをパケットに挿入する。
【００７１】
ステップ４２２で、第１のノードは、修正パケットを第２のノードに向けて転送する。ステップ４２４で、第２のノードは、第１のノードからパケットを受信する。パケットはＬＤＰパケットだが、これは、前に第１のノードから第２のノードに送信されて、第２のノードから第１のノードに返送されたのと同じＩＰパケットであり、また、第１のノードによってＬＤＰパケットの前に付加されたネクストホップＬＤＰラベルと、第１のノードによってＬＤＰパケットの前に付加されたＵターンラベルとを含む。
【００７２】
ステップ４２６で、第２のノードは、パケットを転送することを決定する。第２のノードは、宛先ノードと、パケットがＵターンラベルを含むか否かに関する第２のノードによる決定とに基づいて、パケットの転送先となるネクストホップノードを決定する（すなわち、パケットがＵターンラベルを含まないときは、宛先ノードへの通常ルーティングパスが選択され、パケットがＵターンラベルを含むときは、宛先ノードへの代替ルーティングパスが選択される）。この場合は、パケットがＵターンラベルを含むので、第２のノードは、意図された宛先ノードに向けたパケットのルーティングに使用されることになる代替ルーティングパスを識別する。前述のように、代替ルーティングパスは、第３のノードをネクストホップノードとして識別する。
【００７３】
ステップ４２８で、第２のノードは、決定されたネクストホップノード（すなわち第３のノード）への転送のためにパケットを修正する。第２のノードは、パケットのネクストホップＬＤＰラベルを決定し、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換える。第２のノードはまた、現在のＵターンラベルをそれ自体のＵターンラベルで置き換えてもよい。
【００７４】
ステップ４３０で、第２のノードは、修正パケットを第３のノードに向けて転送する。
【００７５】
ステップ４３２で、方法４００は終了する。
【００７６】
上に言及したように、方法４００は、第１のノード上で実行される１つまたは複数の処理、および第２のノード上で実行される１つまたは複数の処理として実施することができ、したがって２つ以上の協働処理と見なすことができる。ノード１１０によって実施できる処理（例えば方法４００の一部）の例示的な実施形態が、図５−７に関して図示および記述される。
【００７７】
図５に、パケットが故意にノードに返されつつあることをパケット送信元ノードに知らせるためにターゲットノードがＵターンラベルをパケットに追加できるようにする方法の一実施形態を示す。
【００７８】
ステップ５０２で、方法５００が開始する。
【００７９】
ステップ５０４で、パケットがノードから受信される。
【００８０】
ステップ５０６で、受信パケットが前にパケット送信元ノードに送信されたかどうかが判定される。受信パケットが前にパケット送信元ノードに送信されていない場合は、方法５００はステップ５０９に進み、この時点で、ターゲットノードは、パケットをその意図された宛先に転送するための標準的なパケット転送を実施する（パケットのＵターンルーティングを実施して送信元ノードに返すのではなく）。受信パケットが前にパケット送信元ノードに送信された場合は、方法５００はステップ５０８に進む。
【００８１】
ステップ５０８で、障害条件がターゲットノードによる受信パケットの転送を妨げるかどうかが判定される。障害条件がターゲットノードによる受信パケットの転送を妨げない場合は、方法５００はステップ５０９に進み、この時点で、ターゲットノードは、パケットをその意図された宛先に転送するための標準的なパケット転送を実施する（この場合もやはり、パケットのＵターンルーティングを実施して送信元ノードに返すのではなく）。障害条件がターゲットノードによる受信パケットの転送を妨げる場合は、方法５００はステップ５１０に進む。
【００８２】
ステップ５１０で、Ｕターンラベルがパケットに追加されて、修正パケットが形成される。本明細書に記述されるように、Ｕターンラベルは、代替ルーティングパスを使用してパケットを転送できるように、ターゲットノードがパケットを故意に返しつつあることを、ノードに示すように構成される。
【００８３】
ステップ５１２で、修正パケットは、ターゲットノードから送信元ノードに返送される。
【００８４】
ステップ５１４で、方法５００は終了する。
【００８５】
図１の例のコンテキスト内では、方法５００はノードＳによって実施することができ、ノードＳはパケットをノードＢに返す前にＵターンラベルをパケットに挿入することは、理解されるであろう。さらに、図５の方法５００は、図１の任意のノード１１０によって実施できることも理解されるであろう。
【００８６】
図６に、ノードにおいて受信されたパケットを処理する方法の一実施形態を示す。
【００８７】
ステップ６０２で、方法６００が開始する。
【００８８】
ステップ６０４で、ノードにおいてＬＤＰパケットが受信される。
【００８９】
ステップ６０６で、受信されたＬＤＰパケットがＵターンラベルを含むかどうかが判定される。
【００９０】
受信されたＬＤＰパケットがＵターンラベルを含まない場合は、方法６００はステップ６０８に進み、この時点で、ＬＤＰパケットは、受信されたＬＤＰパケットの宛先ノードに向けられたパケットについてノードによって決定された通常ルーティングパスを使用して、転送される。ステップ６０８から、方法６００はステップ６１２に進む。
【００９１】
受信されたＬＤＰパケットがＵターンラベルを含む場合は、方法６００はステップ６１０に進み、この時点で、ＬＤＰパケットは、受信されたＬＤＰパケットの宛先ノードに向けられたパケットについてノードによって決定された代替ルーティングパスを使用して、転送される。ステップ６１０から、方法６００はステップ６１２に進む。
【００９２】
ステップ６１２で、方法６００は終了する。
【００９３】
図１の例のコンテキスト内では、方法６００は、少なくともノードＳおよびＢによって実施できることは理解されるであろう。さらに、図６の方法６００は、図１の任意のノード１１０によって実施できることも理解されるであろう。
【００９４】
図７に、ノードにおいて受信されたパケットを処理する方法の一実施形態を示す。
【００９５】
ステップ７０２で、方法７００が開始する。
【００９６】
ステップ７０４で、ノードにおいてパケットが受信される。
【００９７】
ステップ７０６で、受信パケットのパケットタイプがノードによって決定される。パケットタイプの決定により、パケットがノードによって転送される方式に関する決定が可能になる。一実施形態では、例えば、以下のような３つのパケットタイプをサポートすることができる。すなわち、ＩＰパケット、Ｕターンラベルを含まないＬＤＰパケット、および、Ｕターンラベルを含むＬＤＰパケットである。
【００９８】
パケットがＩＰパケットであると識別された場合は、方法７００はステップ７０８に進み、この時点で、通常ＩＰパケットルーティング処理を使用してパケットの転送が実施される（例えば、パケットのネクストホップラベルを見つけ、ネクストホップラベルを挿入し、パケットをその宛先ノードに向けて通常ルーティングパスに沿って転送する）。ステップ７０８から、方法７００はステップ７１４に進む。
【００９９】
パケットが、Ｕターンラベルを含まないＬＤＰパケットであると識別された場合は、方法７００はステップ７１０に進み、この時点で、ＬＤＰパケットルーティング処理および通常ルーティングパスを使用してパケットの転送が実施される（例えば、ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットをその宛先ノードに向けて通常ルーティングパスに沿って転送する）。ステップ７１０から、方法７００はステップ７１４に進む。
【０１００】
パケットが、Ｕターンラベルを含まないＬＤＰパケットであると識別された場合は、方法７００はステップ７１２に進み、この時点で、ＬＤＰパケットルーティング処理および代替ルーティングパスを使用してパケットの転送が実施される（例えば、ＬＤＰラベル付きパケットのネクストホップＬＤＰラベルを見つけ、現在のネクストホップＬＤＰラベルを決定されたネクストホップＬＤＰラベルで置き換え、パケットをその宛先ノードに向けて代替ルーティングパスに沿って転送する）。ステップ７１２から、方法７００はステップ７１４に進む。
【０１０１】
ステップ７１４で、方法７００は終了する。
【０１０２】
一実施形態では、本明細書に図示および記述されるＵターン高速再ルーティング能力は、１つまたは複数の他の再ルーティング方式との組合せで利用することができる。Ｕターン高速再ルーティング能力により、ＬＤＰは、サービスプロバイダネットワーク内でＵターン高速再ルーティングを達成するための高速かつコスト効果のある方法を提供することができるが、Ｕターン高速再ルーティング能力は、サービスプロバイダネットワーク内で実現され得る全ての可能なネットワークトポロジをカバーするわけではない場合がある。このような一実施形態では、サービスプロバイダネットワーク内でループフリー代替（ＬＦＡ）方式を実施して、Ｕターン高速再ルーティング能力によってカバーされないトポロジを少なくともカバーすることができる。Ｕターン高速再ルーティング能力とＬＦＡ方式との組合せがサービスプロバイダネットワーク内で使用されるとき、サービスプロバイダネットワーク内で使用され得るほぼ全てのタイプのトポロジのためのファストリルートを提供することができる。
【０１０３】
本明細書では主に、ＬＤＰを実行するＩＰ／ＭＰＬＳネットワークのコンテキスト内でＵターン高速再ルーティング能力が図示および記述されるが、他の適切なプロトコルを使用する他の適切なタイプの通信ネットワーク中でＵターン高速再ルーティング能力が利用されてもよいことは理解されるであろう。
【０１０４】
本明細書では主に、特定の数、タイプ、および配置のラベルを使用する実施形態に関してＵターン高速再ルーティング能力が図示および記述されるが、他の数、タイプ、および／または配置のラベルを使用してＵターン高速再ルーティング能力の様々な実施形態が提供されてもよいことは理解されるであろう。
【０１０５】
図８に、本明細書に記述される機能を実施する際に使用するのに適したコンピュータの、高レベルのブロック図を示す。
【０１０６】
図８に示すように、コンピュータ８００は、プロセッサ要素８０２（例えば中央処理装置（ＣＰＵ）および／または他の適切なプロセッサ（複数可））と、メモリ８０４（例えばランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）など）と、協働モジュール／処理８０５と、様々な入出力デバイス８０６（例えばユーザ入力デバイス（キーボード、キーパッド、マウスなど）、ユーザ出力デバイス（表示装置、スピーカなど）、入力ポート、出力ポート、受信機、送信機、および記憶デバイス（例えばテープドライブ、フロッピー（登録商標）ドライブ、ハードディスクドライブ、コンパクトディスクドライブなど））とを備える。
【０１０７】
本明細書に図示および記述される機能は、ソフトウェアにおいて実施されてもよく（例えば１つまたは複数のプロセッサ上でのソフトウェアの実装を介して）、かつ／あるいはハードウェアにおいて実施されてもよい（例えば汎用コンピュータ、１つもしくは複数の特定用途向け集積回路（ＡＳＩＣ）、および／またはいずれか他のハードウェア均等物を使用して）ことは、理解されるであろう。
【０１０８】
本明細書に図示および記述される機能は、専用コンピュータを実現するように汎用コンピュータ上で実行されるソフトウェアにおいて実施されてもよく（例えば１つまたは複数のプロセッサによる実行を介して）、かつ／あるいはハードウェアにおいて実施されてもよい（例えば１つもしくは複数の特定用途向け集積回路（ＡＳＩＣ）、および／または１つもしくは複数の他のハードウェア均等物を使用して）ことは、理解されるであろう。
【０１０９】
一実施形態では、協働処理８０５は、メモリ８０４にロードされプロセッサ８０２によって実行されて、本明細書に論じられるような機能を実施することができる。したがって、協働処理８０５（関連するデータ構造を含む）は、コンピュータ可読記憶媒体（例えば、ＲＡＭメモリ、磁気または光学ドライブまたはディスケットなど）に記憶されてよい。
【０１１０】
図８に示されるコンピュータ８００は、本明細書に記述される機能要素、および／または本明細書に記述される機能要素の一部を実現するのに適した、一般的なアーキテクチャおよび機能性を提供することは理解されるであろう。例えば、コンピュータ８００は、１つもしくは複数のノード１１０、またはノード１１０の一部を実現するのに適した、一般的なアーキテクチャおよび機能性を提供する。
【０１１１】
ソフトウェア方法として本明細書に論じられるステップのいくつかを、ハードウェア内で、例えばプロセッサと協働して様々な方法ステップを実施する回路として、実施できることが企図される。本明細書に論じられる機能／要素の一部は、コンピュータプログラム製品として実現することができ、この場合、コンピュータ命令がコンピュータによって処理されると、コンピュータ命令は、本明細書に記述される方法および／または技法が呼び出されるかまたは他の方法で提供されるように、コンピュータの動作を構成する。本発明の方法を呼び出すための命令は、固定または取外し可能な媒体に記憶されてよく、ブロードキャストもしくは他の信号担持媒体中のデータストリームを介して伝送されてよく、かつ／または、命令に従って動作するコンピューティングデバイス内のメモリ内に記憶されてよい。
【０１１２】
様々な実施形態の態様が、特許請求の範囲において指定される。様々な実施形態のこれらおよび他の態様が、以下の番号付き条項において指定される。
【０１１３】
１．パケットを第１のノードにおいて受信することであって、パケットが、第２のノードから受信され、宛先ノードに向けられたものであり、パケットが、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成されたＵターンラベルを含むものであること、および、
第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択することを含む、方法。
【０１１４】
２．第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することをさらに含む、第１条の方法。
【０１１５】
３．第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することが、
パケットの新しいネクストホップラベルを決定し、パケット中で受け取られたネクストホップラベルを新しいネクストホップラベルで置き換えて、それにより修正パケットを形成すること、および、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することを含む、第１条の方法。
【０１１６】
４．第２のルーティングパスを使用してパケットを宛先ノードに向けて転送することが、
パケットの新しいＵターンラベル、およびパケットの新しいネクストホップラベルを決定すること、
パケット中で受け取られたＵターンラベルを新しいＵターンラベルで置き換え、パケット中で受け取られたネクストホップラベルを新しいネクストホップラベルで置き換えて、それにより修正パケットを形成すること、ならびに、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することを含む、第１条の方法。
【０１１７】
５．受信するステップの前に、
パケットを第１のノードにおいて受信することであって、パケットが第２のノードから受信され、パケットが宛先ノードに向けられたものであること、
パケットを宛先ノードに向けてルーティングするための第１のルーティングパスを選択すること、および、
選択された第１のルーティングパスに基づいてパケットを第２のノードに向けて送信することをさらに含む、第１条の方法。
【０１１８】
６．第１のルーティングパスのコストが第２のルーティングパスのコストよりも低い、第１条の方法。
【０１１９】
７．パケットがインターネットプロトコル（ＩＰ）パケットおよびラベル配布プロトコル（ＬＤＰ）ラベルを含み、ＵターンラベルがＩＰパケットの前に付加され、ＬＤＰラベルがＵターンラベルの前に付加された、第１条の方法。
【０１２０】
８．プロセッサを備える装置であって、プロセッサが、
パケットを第１のノードにおいて受信するように構成され、パケットが、第２のノードから受信され、宛先ノードに向けられたものであり、パケットが、パケットを宛先ノードに向けてルーティングするために第１のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第２のノードによって第１のノードに返されつつあることを第１のノードに示すように構成されたＵターンラベルを含み、プロセッサが、
第１のノードにおいて、パケット内にＵターンラベルが含まれることに基づいて、パケットを宛先ノードに向けてルーティングするための第２のルーティングパスを選択するように構成された、装置。
【０１２１】
９．プロセッサが、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、第８条の装置。
【０１２２】
１０．プロセッサが、
パケットの新しいネクストホップラベルを決定し、パケット中で受け取られたネクストホップラベルを新しいネクストホップラベルで置き換えて、それにより修正パケットを形成すること、および、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することによって、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、第８条の装置。
【０１２３】
１１．プロセッサが、
パケットの新しいＵターンラベル、およびパケットの新しいネクストホップラベルを決定すること、
パケット中で受け取られたＵターンラベルを新しいＵターンラベルで置き換え、パケット中で受け取られたネクストホップラベルを新しいネクストホップラベルで置き換えて、それにより修正パケットを形成すること、ならびに、
第２のルーティングパスに基づいて修正パケットを宛先ノードに向けて転送することによって、
第２のルーティングパスを使用してパケットを宛先ノードに向けて転送するように構成された、第８条の装置。
【０１２４】
１２．プロセッサが、
パケットを第１のノードにおいて受信する前に、
パケットを第１のノードにおいて受信することであって、パケットが第２のノードから受信され、パケットが宛先ノードに向けられたものであること、
パケットを宛先ノードに向けてルーティングするための第１のルーティングパスを選択すること、および、
選択された第１のルーティングパスに基づいてパケットを第２のノードに向けて送信することを行うように構成された、第８条の装置。
【０１２５】
１３．第１のルーティングパスのコストが第２のルーティングパスのコストよりも低い、第８条の装置。
【０１２６】
１４．パケットがインターネットプロトコル（ＩＰ）パケットおよびラベル配布プロトコル（ＬＤＰ）ラベルを含み、ＵターンラベルがＩＰパケットの前に付加され、ＬＤＰラベルがＵターンラベルの前に付加された、第８条の装置。
【０１２７】
１５．宛先ノードに向けられたパケットを第１のノードにおいて受信することであって、パケットが、第２のノードによる、パケットのための第１のルーティングパスの選択に基づいて、第２のノードから受信されること、
第１のノードにおいてＵターンラベルをパケットに挿入して、それにより修正パケットを形成することであって、Ｕターンラベルが、第２のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第１のノードによって第２のノードに返されつつあることを第２のノードに知らせるように構成されたものであること、
パケットを宛先ノードに向けてルーティングするために第２のルーティングパスが第２のノードによって選択されるべきであることを第２のノードに示すために、修正パケットを第１のノードから第２のノードに向けて送信することを含む、方法。
【０１２８】
１６．受信するステップの前にパケットを第１のノードから第２のノードに向けて送信することをさらに含む、第１５条の方法。
【０１２９】
１７．第１のルーティングパスのコストが第２のルーティングパスのコストよりも低い、第１５条の方法。
【０１３０】
１８．パケットがインターネットプロトコル（ＩＰ）パケットおよび第１のラベル配布プロトコル（ＬＤＰ）ラベルを含み、修正パケットの場合、ＵターンラベルがＩＰパケットの前に付加され、第２のＬＤＰラベルがＵターンラベルの前に付加された、第１５条の方法。
【０１３１】
１９．プロセッサを備える装置であって、プロセッサが、
宛先ノードに向けられたパケットを第１のノードにおいて受信するように構成され、パケットが、第２のノードによる、パケットのための第１のルーティングパスの選択に基づいて、第２のノードから受信され、プロセッサが、
第１のノードにおいてＵターンラベルをパケットに挿入して、それにより修正パケットを形成するように構成され、Ｕターンラベルが、第２のノードによって選択された第１のルーティングパスを使用してパケットを宛先ノードに向けて伝搬するのを妨げる条件のためにパケットが第１のノードによって第２のノードに返されつつあることを第２のノードに知らせるように構成され、プロセッサが、
パケットを宛先ノードに向けてルーティングするために第２のルーティングパスが第２のノードによって選択されるべきであることを第２のノードに示すために、修正パケットを第１のノードから第２のノードに向けて送信するように構成された、装置。
【０１３２】
２０．プロセッサが、
受信するステップの前にパケットを第１のノードから第２のノードに向けて送信するように構成された、第１９条の装置。
【０１３３】
２１．第１のルーティングパスのコストが第２のルーティングパスのコストよりも低い、第１９条の装置。
【０１３４】
２２．パケットがインターネットプロトコル（ＩＰ）パケットおよび第１のラベル配布プロトコル（ＬＤＰ）ラベルを含み、修正パケットの場合、ＵターンラベルがＩＰパケットの前に付加され、第２のＬＤＰラベルがＵターンラベルの前に付加された、第１９条の装置。
【０１３５】
本発明の教示を組み込む様々な実施形態が本明細書に詳細に図示および記述されたが、当業者なら、これらの教示をやはり組み込む多くの他の多様な実施形態をすぐに考案することができる。
【図１】
0005728595.tif 000002
【図２】
0005728595.tif 000003
【図３】
0005728595.tif 000004
【図４】
0005728595.tif 000005
【図５】
0005728595.tif 000006
【図６】
0005728595.tif 000007
【図７】
0005728595.tif 000008
【図８】
0005728595.tif 000009