JP7644064B2 - 伝送経路故障を処理するための方法と装置、及びシステム - Google Patents

Description

この出願は、通信技術の分野に関する。そして、特には、伝送経路（transmission path）故障を処理するための方法と装置、及びシステムに関する。

この出願は、2018年6月30日に中国特許庁に出願された、タイトルが“METHOD AND APPARATUS FOR PROCESSING TRANSMISSION PATH FAULT, AND SYSYTEM”の中国特許出願第２01810703248.2号について優先権を主張するものであり、その全体が参照によりここにおいて組み込まれている。

セグメント・ルーティング・トラフィックエンジニアリング(segment routing-traffic engineering、SR-TE)は、制御シグナリングとして、内部ゲートウェイプロトコル(interior gateway protocol、IGP)または境界ゲートウェイプロトコル(border gateway protocol、BGP)を使用する、新しいマルチプロトコル・ラベルスイッチング(multiprotocol label switching、MPLS)TEトンネル技術である。コントローラは、トンネルについて転送パス（forwarding path）を計算し、そして、トランスポンダへのパスに対して厳密にマッピングされたラベルスタックを配送する責任を負う。SR-TEトンネルの入口ノード（ingress node）において、トランスポンダは、ラベルスタックに基づいてネットワーク上のパケットの伝送経路を制御することができる。

プライマリパス（primary path）上のノードが故障している場合に、現在は、高速再ルーティング(fast routing、FRR)技術に基づいてパケットを転送するために、バックアップパス（backup path）が使用されている。

例えば、プライマリパス上のノードAが故障している場合には、プライマリパス上でノードAの以前ホップ（previous-hop）ノードBが、ノードAが故障していることを了解した後で、以前ホップノードBは、ノードAについて事前に生成されたラベル情報テーブル(コンテキストテーブルとしても参照されるもの)、および、ノードAについて事前に生成されたプライマリおよびセカンダリ転送テーブルに基づいて、送信のためにデータパケットをバックアップパスへ切り替える。コンテキストテーブルは、ネットワーク全体における全てのノードに対応するノード(プレフィックス)ラベル情報、および、ノードAによってアドバタイズされる（advertised）隣のラベル（adjacency label）を含んでいる。

コンテキストテーブルが事前に生成されるので、SR-TE FRRソリューションにおいて、ノードBは、ノードAの各隣接（neighbor）についてコンテキストテーブルを生成する。従って、コンテキストテーブルの仕様（specification）は、ネットワーク全体におけるノードの数量と、隣接するノード（neighboring node）の隣接の数量とを足したものであり、そして、各ノードは、コンテキストテーブルに係る以下の数量を生成する必要がある。つまり、隣接の数量＊(ネットワーク全体におけるノードの数量と、隣接するノードの隣接の数量とを足したもの)、である。

ネットワークが比較的大量のノードを含み、そして、いくつかのノードによってサポートされるコンテキストテーブルの容量が、隣接の数量＊(ネットワーク全体におけるノード数と、隣接するノードの隣接の数量とを足したもの)に到達できない場合には、ノードによって生成されるコンテキストテーブル内のコンテンツは、不完全であるか、または、生成に失敗する。ネットワーク内のノードが故障している場合には、コンテキストテーブルに基づいて正しいバックアップパスへ切り替えることができないので、データパケットの転送に失敗することがある。

この出願は、伝送経路故障を処理するための方法と装置、及びシステムを提供して、ノードによってサポートされるコンテキストテーブルの容量が不十分であるために、データパケットの転送に失敗するという先行技術の問題を解決する。

第１態様に従って、この出願の一つの実施形態は、伝送経路故障を処理するための方法を提供する。本方法は、であって、第１ネットワーク装置によって、第２ネットワーク装置により送信された第１パケットを受信するステップであり、前記第２ネットワーク装置は、プライマリパス上で前記第１ネットワーク装置の以前ホップネットワーク装置である、ステップと、第３ネットワーク装置が故障していることを決定するときに、前記第１ネットワーク装置によって、第１ネットワーク装置のセグメントルーティンググローバルブロックSRGBの初期値と、前記第３ネットワーク装置のSRGBの初期値との間の差異を決定するステップであり、前記第３ネットワーク装置は、前記プライマリパス上で前記第１ネットワーク装置のネクストホップネットワーク装置である、ステップと、前記第１ネットワーク装置によって、前記第１パケットから第１ラベルを獲得するステップであり、前記第１ラベルは、第３ネットワーク装置のSRGBの前記初期値および第４ネットワーク装置のノードセグメント識別子に基づいて決定され、かつ、前記第４ネットワーク装置は、前記プライマリパス上で第３ネットワーク装置のネクストホップネットワーク装置である、ステップと、前記第１ネットワーク装置によって、前記第１ネットワーク装置から前記第４ネットワーク装置へのバックアップパスの入来（incoming）ラベルとして、前記第１ラベルと前記差異との合計値を使用するステップであり、かつ、バックアップ転送テーブルから、前記第１ネットワーク装置から前記第４ネットワーク装置への前記バックアップパスの外出（outgoing）ラベルを決定する、ステップと、前記第１ネットワーク装置によって、前記第１パケットを、前記外出ラベルに基づいて、前記バックアップパス上で前記第１ネットワーク装置のネクストホップネットワーク装置に対して送信するステップと、を含む。

前述のソリューションを使用することにより、バックアップパスは、SRGB差異およびバックアップ転送テーブルを使用して決定される。そうして、ノードがサポートするコンテキストテーブルの容量が不十分であるために、データパケットの転送に失敗するという問題を克服することができる。

可能なデザインにおいて、前記第１パケットは、前記プライマリパスにおける前記第１パケットの転送についてガイダンスを提供するために使用されるラベルスタックリストを含む。そして、第１ネットワーク装置のSRGBの初期値と第３ネットワーク装置のSRGBの初期値との間の差異を決定するステップは、前記第１ネットワーク装置によって、前記ラベルスタックリストの上部（top）から第２ラベルを獲得するステップであり、前記第２ラベルは、前記第３ネットワーク装置のノードセグメント識別子、および、前記第１ネットワーク装置のSRGBの前記初期値に基づいて決定されるステップと、記第１ネットワーク装置によって、バックアップ転送テーブルにおいて、前記第２ラベルに対応する第１転送挙動を決定するステップであり、前記第１転送挙動は、ラベル情報テーブルをサーチするために使用され、かつ、前記ラベル情報テーブルは、前記第２ラベルに対応する前記差異を含むステップと、前記第１ネットワーク装置によって、前記ラベル情報テーブルからの前記差異を獲得するステップと、を含む。

上記のデザインを使用することにより、２つの隣接するノードのSRGB初期値が事前にラベル情報テーブルに保管され、そうして、第１ネットワーク装置のSRGB初期値と第３ネットワーク装置のSRGB初期値との間の差異が決定されると、ストレージを備えるラベル情報テーブルから差異が直接的に獲得され、それによって、処理リソースを節約している。加えて、ラベル情報テーブルは、その差異、および、第３ネットワーク装置に隣接するネットワーク装置のノードセグメント識別子に関する情報だけを含んでおり、そして、ネットワーク全体の全てのノードのノードセグメント識別子が、コンテキストテーブル内に保管される必要がなく、それによって、ストレージリソース節約し、かつ、ノードによりサポートされるコンテキストテーブルの容量が不十分であるためにデータパケットの転送に失敗するという問題を克服している。

可能なデザインにおいて、前記第１ネットワーク装置によって、前記第１パケットから第１ラベルを獲得する前記ステップは、前記第１ネットワーク装置によって、前記ラベルスタックリストの上部から前記第２ラベルをポップした後で、前記第２ラベルがポップされた前記ラベルスタックリストの上部から前記第１ラベルを獲得するステップ、を含む。そして、前記第１ネットワーク装置によって、前記第１パケットを、前記外出ラベルに基づいて、前記バックアップパス上で前記第１ネットワーク装置のネクストホップネットワーク装置に対して送信する前記ステップは、前記第１ネットワーク装置によって、前記外出ラベルについて前記ラベルスタックリストにおける前記第１ラベルを切り替えるステップ、および、更新された第１パケットを、前記バックアップパス上で前記第１ネットワーク装置のネクストホップネットワーク装置に対して送信するステップ、を含む。

可能なデザインにおいて、前記第３ネットワーク装置によりネットワーク内にフラッディングされた前記第３ネットワーク装置の前記ノードセグメント識別子を受信した後で、前記第１ネットワーク装置は、前記第３ネットワーク装置の前記ノードセグメント識別子を、前記ネットワーク内の別のネットワーク装置にフラッディングする。ここで、前記第１ラベルは、前記第３ネットワーク装置のものであり、かつ、前記第１ネットワーク装置によってフラッディングされた、前記ノードセグメント識別子、および、第１ネットワーク装置のSRBGの前記初期値に基づいて、前記第２ネットワーク装置によって、決定される。

転送パス内に緩いパス（loose path）が存在しており、かつ、緩いパスセグメント上の宛先ノードが故障している場合には、ノードの故障情報がネットワーク全体にフラッディングされた後で、ネットワーク全体における全てのノードは、故障ノードへの対応するプライマリおよびセカンダリ転送テーブルを削除する。緩いパスセグメント上の宛先ノードが故障している場合には、プライマリパスおよびバックアップパスの両方において、第１ノードから最後のノードまで、全てのノードが緩いパスセグメントを通過する必要があり、そして、故障ノードの以前ホップノードから故障ノードをバイパスすることによって最後のノードに到達することができる。故障ノードへのプライマリおよびセカンダリ転送テーブルが削除された後で、パスセグメント上のソースノードは、故障ノードの以前ホップノードへデータパケットを転送することができない。その結果として、パケット転送の失敗が生じる。従って、上記のデザインを使用することにより、緩いパスセグメント上の宛先ノードのノードセグメント識別子を受信した後で、緩いパスセグメント上の宛先ノードの以前ホップノードは、宛先ノードのノードセグメント識別子をネットワーク全体にフラッディングする。このようにして、緩いパスセグメント上のソースノードは、宛先ノードのノードセグメント識別子に基づいて転送パスを決定し、そして、データパケットを転送することができる。

可能なデザインにおいて、第３ネットワーク装置が故障していると決定するとき、第１ネットワーク装置は、第３ネットワーク装置のノードセグメント識別子をネットワーク全体にフラッディングし得る。

可能なデザインにおいて、本方法は、さらに、前記故障が回復した後で、前記第１ネットワーク装置によって、前記第３ネットワーク装置により送信された指示情報を受信するステップであり、前記指示情報は、前記第３ネットワーク装置がパケットを正しく転送できないことを示すために使用されるステップ、および、前記第２ネットワーク装置により送信された第２パケットを受信したときに、前記第１ネットワーク装置によって、決定された前記外出ラベルに基づいて前記第２パケットを送信するステップ、を含む。

プライマリパス上の転送ノードが故障している場合に、以前ホップノードは、パケットを転送するために、バックアップパスへ切り替える。故障ノードが回復し、かつ、再始動した後で、故障が回復した後のノードは、ノード(プレフィックス)ラベルおよびノードのものである隣のラベル、といった情報をネットワーク内の別のノードに再フラッディングする。故障が回復した後、ノードによってフラッディングされた情報を受信した後で、以前ホップノードは、データパケットをプライマリパスへ戻すように切り替える。つまり、パケットは、故障が回復した後でノードを再利用することにより送信される。しかしながら、故障が回復した後のノードは再始動されたばかりなので、ローカルデータベースは不完全なことがある。例えば、ローカルデータベースは、別のノードに関する情報を含まない。プライマリパス上で故障が回復された後の、ノードラベル、および、ノードのネクストホップノードの隣接性ラベル、に関する情報といったものである。この場合、RT3がパケットを受信した後で、パケットは、ネクストホップノードへ転送することができない。その結果として、データパケット損失が発生する。これに基づいて、上記のデザインを使用することにより、故障ノードは、回復された後の故障ノードがパケットを正しく転送できないことを、故障ノードの以前ホップのネットワーク装置に示すための指示情報を優先的に送信する。従って、以前ホップのネットワーク装置は、バックアップパスを使用することにより、なおもデータパケットを転送する。

第２態様に従って、この出願の実施形態は、伝送経路故障を処理するための方法を提供する。本方法は、前記第２ネットワーク装置によって、プライマリパスを使用することによりパケットを送信するプロセスにおいて、第３ネットワーク装置が故障していると決定するステップと、前記第２ネットワーク装置によって、第１ネットワーク装置によりネットワーク内にフラッディングされた前記第３ネットワーク装置のノードセグメント識別子を受信するステップであり、前記第３ネットワーク装置は、前記第１ネットワーク装置の隣接するネットワーク装置であり、前記第１ネットワーク装置は、前記プライマリパス上で前記第２ネットワーク装置のネクストホップネットワーク装置であり、かつ、前記第３ネットワーク装置は、前記プライマリパス上で前記第１ネットワーク装置のネクストホップネットワーク装置である、ステップと、前記第１ネットワーク装置によりフラッディングされた前記第３ネットワーク装置の前記ノードセグメント識別子に基づいて、前記第２ネットワーク装置によって、バックアップパスを使用することにより、前記パケットを前記第１ネットワーク装置に対して送信するステップであり、前記第１ネットワーク装置は、前記バックアップパス上で前記第２ネットワーク装置のネクストホップネットワーク装置である、ステップと、を含む。

転送パス内に緩いパスが存在しており、かつ、緩いパスセグメント上の宛先ノードが故障している場合には、ノードの故障情報がネットワーク全体にフラッディングされた後で、ネットワーク全体における全てのノードは、故障ノードへの対応するプライマリおよびセカンダリ転送テーブルを削除する。緩いパスセグメント上の宛先ノードが故障している場合には、プライマリパスおよびバックアップパスの両方において、第１ノードから最後のノードまで、全てのノードが緩いパスセグメントを通過する必要があり、そして、故障ノードの以前ホップノードから故障ノードをバイパスすることによって最後のノードに到達することができる。故障ノードへのプライマリおよびセカンダリ転送テーブルが削除された後で、パスセグメント上のソースノードは、故障ノードの以前ホップノードへデータパケットを転送することができない。その結果として、パケット転送の失敗が生じる。従って、上記のデザインを使用することにより、緩いパスセグメント上の宛先ノードのノードセグメント識別子を受信した後で、緩いパスセグメント上の宛先ノードの以前ホップノードは、宛先ノードのノードセグメント識別子をネットワーク全体にフラッディングする。このようにして、緩いパスセグメント上のソースノードは、宛先ノードのノードセグメント識別子に基づいて転送パスを決定し、そして、データパケットを転送することができる。

第３態様に従って、第１態様の方法の実施態様と同じ発明の概念に基づいて、この出願の実施態様は、伝送経路故障を処理するための装置を提供する。本装置は、第１態様に従った第１ネットワーク装置に適用される。別の言葉で言えば、本装置は、第１ネットワーク装置であってよく、または、第１ネットワーク装置に適用可能なチップであってよい。本装置は、第１態様の実施形態を実施する機能を有している。本機能は、ハードウェアを使用することにより実施されてよく、または、対応するソフトウェアを実行することによりハードウェアによって実施されてよい。ハードウェアまたはソフトウェアは、上記の機能に対応する１つ以上のモジュールを含んでいる。

第４態様に従って、第２態様の方法の実施形態と同じ発明の概念に基づいて、この出願の実施形態は、伝送経路故障を処理するための装置を提供する。本装置は、第２態様に従ったネットワーク装置に適用される。別の言葉で言えば、本装置は、ネットワーク装置であってよく、または、ネットワーク装置に適用可能なチップであってよい。本装置は、第２態様の実施形態を実施する機能を有している。本機能は、ハードウェアによって実現されてよく、または、対応するソフトウェアを実行することによりハードウェアによって実施されてよい。ハードウェアまたはソフトウェアは、上記の機能に対応する１つ以上のモジュールを含んでいる。

第５態様に従って、この出願の実施形態は、伝送経路故障を処理するための装置を提供し、そして、本装置は、プロセッサおよびメモリを含んでおり、ここで、メモリは、命令を保管するように構成されている。本装置が動作すると、プロセッサは、メモリに保管された命令を実行し、そうして、本装置は、第１態様または第１態様の実施形態のいずれか１つに従って、伝送経路故障を処理する方法を実行する。メモリは、プロセッサの中へ統合されてよく、または、プロセッサから独立していてよいことが留意されるべきである。本装置は、さらに、バスを含み得る。プロセッサは、バスを使用することによりメモリに結合されている。メモリは、読み出し専用メモリおよびランダムアクセスメモリを含み得る。実行する必要があるときに、本装置は、読み出し専用メモリにおいて固化（solidified）された基本入出力システム、または、組み込みシステムにおけるブートローダ・ブートシステムを使用することにより開始されて、本装置を正常な実行状態に導く。正常な実行状態に入った後で、本装置は、ランダムアクセスメモリ内のアプリケーションプログラムおよびオペレーティングシステムを実行し、そうして、プロセッサは、第１態様または第１態様の可能な実装デザインのいずれか１つに従って、方法を実行する。

第６態様に従って、この出願の実施形態は、伝送経路故障を処理するための装置を提供し、そして、本装置は、プロセッサおよびメモリを含んでおり、ここで、メモリは、命令を保管するように構成されている。本装置が動作すると、プロセッサは、メモリに保管された命令を実行し、そうして、本装置は、第２態様または第２態様の実施形態のいずれか１つに従って、伝送経路故障を処理する方法を実行する。メモリは、プロセッサの中へ統合されてよく、または、プロセッサから独立していてよいことが留意されるべきである。本装置は、さらに、バスを含み得る。プロセッサは、バスを使用することによりメモリに結合されている。メモリは、読み出し専用メモリおよびランダムアクセスメモリを含み得る。実行する必要があるときに、本装置は、読み出し専用メモリにおいて固化された基本入出力システム、または、組み込みシステムにおけるブートローダ・ブートシステムを使用することにより開始されて、本装置を正常な実行状態に導く。正常な実行状態に入った後で、本装置は、ランダムアクセスメモリ内のアプリケーションプログラムおよびオペレーティングシステムを実行し、そうして、プロセッサは、第２態様または第２態様の可能な実装デザインのいずれか１つに従って、方法を実行する。

第７態様に従って、この出願の実施形態は、さらに、第３態様または第５態様の装置、および、第４態様または第６態様の装置を含む、システムを提供する。可能なデザインにおいて、本システムは、さらに、この出願のこの実施形態において提供されるソリューション内に存在し、かつ、２つのネットワーク装置とインタラクションする、別のネットワーク装置を含み得る。例えば、別のネットワーク装置は、伝送経路上の別のネットワーク装置であってよい。

第８態様に従って、この出願の実施形態は、さらに、読取り可能な記憶媒体を提供する。本読取り可能な記憶媒体は、プログラムまたは命令を保管する。プログラムが実行され、または、コンピュータ上で命令が実行されると、上記の態様における伝送経路故障を処理するための任意の方法が実行される。

第９態様に従って、この出願の実施形態は、さらに、命令を含むコンピュータプログラム製品を提供する。本コンピュータプログラム製品がコンピュータ上で実行されると、コンピュータは、上記の態様における伝送経路故障を処理するための任意の方法を実行することが可能である。

加えて、第３態様から第９態様までの任意のデザイン方法によってもたらされる技術的効果については、第１態様から第２態様までにおける異なる実装によってもたらされる技術的効果を参照のこと。詳細は、ここにおいて説明されない。

図1Aは、この出願の一実施形態に従った、ネットワークシステムのアーキテクチャに係る概略図である。 図1Bは、この出願の一実施形態に従った、別のネットワークシステムのアーキテクチャに係る概略図である。 図2は、この出願の一実施形態に従った、伝送経路故障を処理するための方法に係るフローチャートである。 図3は、この出願の一実施形態に従った、さらに別のネットワークシステムのアーキテクチャに係る概略図である。 図4は、この出願の一実施形態に従った、伝送経路故障を処理するための方法に係る概略図である。 図5は、この出願の一実施形態に従った、TLVフォーマットに係る概略図である。 図6は、この出願の一実施形態に従った、フラグフォーマットに係る概略図である。 図7は、この出願の一実施形態に従った、装置700の構造に係る概略図である。 図8は、この出願の一実施形態に従った、ネットワーク装置800の構造に係る概略図である。

この出願は、SR-TEをサポートするノードに対して適用される。この出願の実施形態において、ノードは、また、ネットワーク装置（network device）としても参照されている。ネットワーク装置は、ネットワークにおいてルーティング（routing）および転送（forwarding）機能を提供するデバイスであり、例えば、ルータ、スイッチ、トランスポンダ、または、ラベルスイッチングルータ(label switching router、LSR)であってよい。これに限定されるものではない。以降の説明プロセスにおいて、ノードは、説明のための一つの例として使用されている。

SR-TE技術においては、コントロールプレーン（control plane）が、リンク状態または境界ゲートウェイプロトコル(border gateway protocol、BGP)に基づくIGPプロトコルを使用することにより、ノードのMPLSラベルを配布し、そして、データプレーンが、コントロールプレーンによって配布されたラベルに基づいてMPLSパケットを転送する。

SR-TE(Segment Routing-Traffic Engineering)は、制御シグナリングとして、内部ゲートウェイプロトコル(interior gateway protocol、IGP)または境界ゲートウェイプロトコル(border gateway protocol、BGP)を使用する、新しいTEトンネル技術である。コントローラは、トンネルの転送パスを計算し、そして、トランスポンダへのパスに対して厳密に対応するラベルスタックを配送する責任を負う。SR-TEトンネルの入口ノードにおいて、トランスポンダは、ラベルスタックに基づいてネットワークにおけるパケットの伝送経路を制御することができる。

この出願の実施態様における用語が、最初に以下に説明される。

(1)セグメント・ルーティング・グローバルブロック(Segment Routing Global Block、SRGB)：セグメント(segment)のために予約されるユーザによって指定される一式のラベル。

(2)セグメント(segment)：セグメントは、セグメントラベル(Segment ID、SID)を使用することによって識別される。この出願の実施形態におけるセグメントラベルは、セグメント識別子として参照され得る。フォワーディングプレーン（forwarding plane）上では、SIDがMPLSラベルに対してマッピングされ得る。

セグメントは、３つのタイプのセグメント、すなわち、プレフィックスセグメント(Prefix Segment)、隣のセグメント(Adjacency Segment)、および、ノードセグメント(Node Segment)へと分類される。

プレフィックスセグメントは、SRネットワーク内の宛先アドレス（destination address）のプレフィックス(Prefix)を識別するために使用されている。プレフィックスセグメントは、IGPプロトコルを使用することによって、別のネットワークエレメントへフラッディングされ（flooded）され得る。ここで、プレフィックスセグメントは、グローバルに可視（visible）であり、かつ、グローバルに有効である。プレフィックスセグメントは、プレフィックスセグメント識別子(Prefix Segment ID、Prefix SID)によって識別される。この出願の実施態様において、プレフィックスセグメントラベルは、略して、プレフィックスラベルとして参照されている。プレフィックスSIDは、宛先ノードによってアドバタイズされるSRGBの範囲内のオフセットである。受信端（receive end）は、受信端のSRGBに基づいて実際のラベルを計算する。

隣のセグメント(Adjacency Segment)は、ネットワーク内の２つの隣接するノード間のルーティングリンクを識別するために使用されている。隣のセグメントは、IGPプロトコルを使用することによって、別のネットワークエレメントへフラッディングされ得る。ここで、プレフィックスセグメントは、グローバルに可視であり、かつ、グローバルに有効である。隣のセグメントは、隣のセグメントラベル(Adjacency Segment ID、Adjacency SID)によって識別される。この出願の実施態様において、隣のセグメントラベルは、略して、隣のラベル（Adjacency Label）として参照されている。

隣のラベルは、指向性のものであり、かつ、パケット転送におけるガイダンスを提供するために使用されている。例えば、隣のラベル9003は、リンクPE1->P3に対応している。隣のSID(Adjacency SID)は、SRGB範囲外のローカルSIDである。

ノードセグメント(Node Segment)は、特定のノード(Node)を識別するために使用される特別なプレフィックスセグメントである。IPアドレスは、ノードのローカルループバック(Loopback)インターフェイスのプレフィックスとして設定されている。ノードのプレフィックスSIDは、ノード・セグメントラベル(Node SID)である。この出願の実施態様において、ノード・セグメントラベルは、略して、ノードラベルとして参照されている。

要するに、プレフィックスセグメントは宛先アドレスを表し、かつ、隣のセグメントはデータパケットの送信リンクを表し、そして、宛先アドレスおよび送信リンクは、それぞれに、従来のIP転送（IP forwarding）における宛先IPアドレスおよびアウトバウンド（outbound）インターフェイスに類似していてよい。IGPエリアにおいて、ノードは、全てのノードが他のノードに関する情報を獲得できるように、ノードSID及びそのノードの隣接SIDをフラッディングするための拡張IGPプロトコルを使用している。

ネットワーク内の任意のパスは、プレフィックス(ノード)SIDと隣接SIDとを組み合わせることによって構築され得る。ネットワーク内の経路は、複数のルーティングセグメントによって形成され得る。構築されたパスは、ラベルスタックリストによって表される。ラベルスタックリストは、転送パス上の各ルーティングセグメントに対応するセグメントラベル(Segment ID)を含んでいる。

宛先ノードは、IGPプロトコルのノード(プレフィックス)SIDを使用することによりノード分析ノード（node analysis node）を転送し、そして、自身のSRGBに基づいてラベル値を計算する。次いで、各ノードは、最短パスアルゴリズムに基づいてラベル転送パスを計算するために、IGPプロトコルによって収集されたトポロジ情報を使用し、そして、データパケット転送についてガイダンスを提供するために、計算されたネクストホップ（next hop）および外出（outgoing）ラベル(Outer Label)情報を転送テーブルへ配送する。

加えて、この出願の実施形態における「複数（“a plurality of”）」は、２つまたはそれ以上を意味するものであることが留意されるべきである。用語「及び／又は（“and/or”）」は、関連するオブジェクトを記述するためのアソシエーション関係を示し、かつ、３つの関係が存在し得ることを表している。例えば、A及び／又はBは、以下の３つの事例を表し得る。すなわち、Aのみが存在すること、AおよびBの両方が存在すること、そして、Bのみが存在すること、である。加えて、この出願の明細書において、「第１」および「第２」といった用語は、説明を区別する目的のために単に使用されているものであるが、相対的な重要性の表示または暗示として理解することはできず、かつ、シーケンスの表示または暗示として理解することはできないことが理解されるべきである。ノード1またはノード2も、また、説明されるノード間を区別するために単に使用されているものであり、そして、相対的な重要性の表示または暗示として理解することはできず、かつ、シーケンスの表示または暗示として理解することはできない。

加えて、この出願の実施形態における転送テーブルは、一般的に、プライマリ転送テーブルだけを含んでよく、または、プライマリ転送テーブルおよびバックアップ転送テーブルを含んでよい。この出願の実施形態におけるプライマリ／バックアップ転送テーブルは、一般的に、プライマリ転送テーブルとバックアップ転送テーブルを含んでいる。

図1Aは、プレフィックスセグメントのセグメントパスの生成、および、データパケットの転送を説明するための一例として使用されている。

例えば、確立されるべきプレフィックスセグメントパスはRT1、RT2、RT3、RT4、およびRT5である。RT1は、プレフィックスセグメントの第１ノードであり、そして、RT5は、プレフィックスセグメントの宛先ノードである。

SRGB=[5000-5999]が、RT5について設定されており、かつ、5であるプレフィックス(ノード)SIDが、RT5のループバックインターフェイスに対して設定されている。RT5は、SRGBおよびプレフィックス(ノード)SIDに基づいて、転送テーブルを生成し、かつ、配送する。RT5のSRGBおよびプレフィックスSIDは、制御パケットへとカプセル化されており、そして、制御パケットは、IGPを使用することによりネットワーク全体へフラッディングされる。制御パケットを受信した後で、ネットワーク内の別のネットワーク装置は、RT5によってアドバタイズされたプレフィックスSIDを解析し、そして、別のネットワーク装置のSRGBに基づいて入来（incoming）ラベル値を計算する。加えて、別のネットワーク装置は、ネクストホップノードによってアドバタイズされたSRGBに基づいて、外出ラベル(Outer Label)値を計算し、IGPトポロジを使用することによりラベル転送パスを計算し、そして、次いで、転送テーブルを生成する。

RT4は、RT5によってアドバタイズされたプレフィックスSIDを解析し、そして、RT4のSRGB=[4000-4999]に基づいてラベル値を計算する。計算式は、以下のとおり、inLabel=SRGBの開始値+プレフィックスSID値、である。従って、inLabel=4000+5=4005である。外出ラベル(OuterLabel)は、IS-ISトポロジを使用することにより計算される。計算式は、以下のとおり、OuterLabel=ネクストホップデバイスによってアドバタイズされたSRGBの開始値+プレフィックスSID値(すなわち、プレフィックスセグメントまたはノードセグメント上の宛先ノードのノードラベル)、である。図1Aに示されるように、RT4のネクストホップデバイスはRT5であり、そして、RT5によってアドバタイズされるSRGBの配置は5000から5999までである。従って、OuterLabel=5000+5=5005、である。

RT3の計算処理は、RT4の計算処理と同様であり、すなわち、inLabel=3000+5=3005であり、かつ、OuterLabel=4000+5=4005である。RT2の計算処理は、RT4の計算処理と同様であり、すなわち、inLabel=2000+5=2005であり、かつ、OuterLabel=3000+5=3005である。RT1の計算処理は、RT4の計算処理と同様であり、すなわち、inLabel=1000+5=1005であり、かつ、OuterLabel=2000+5=2005である。

RT1からRT5へのセグメントパスが確立された後で、RT1は、データパケットを受信し、データパケットへラベル値2005を追加し、そして、データパケットを転送する。RT2ノードは、ラベルを搬送するデータパケットを受信し、ラベルスイッチングを行い、ラベル2005をポップし、そして、ラベルを外出ラベル3005と置き換える。RT3ノードは、データパケットを受信し、ラベルスイッチングを行い、ラベル3005をポップし、そして、ラベルを外出ラベル4004と置き換える。データパケットを受信した後で、RT4は、ラベル4005をポップし、そして、ラベル4005をラベル5005と置き換える。データパケットを受信した後で、RT5は、ラベル5005をポップし、そして、パケットを転送するためのルートを探し続ける。

以下では、厳密なセグメントパス(緩いパスであることは許されないもの)の生成、および、データパケットの転送を説明するために、一例として図1Bを使用する。

トランスポンダは、IGPプロトコルに基づいて隣のラベルを割り当て、そして、割り当てられた隣のラベルをコントローラに報告し、そうして、コントローラは、隣のラベルに基づいてラベルスタックリストを生成する。

隣のラベルは、IGPプロトコルを使用することによりネットワーク全体にフラッディングされる。図1Bに示されるように、一例としてRT1ノードを使用することにより、IGPプロトコルによって隣のラベルを割り当てるプロセスは、以下のとおりである。

RT1は、IGPプロトコルを使用することにより、RT1の全てのリンクについてローカルダイナミックラベルを適用する(例えば、RT1は、リンクRT1->RT2に対して隣のラベル1031を割り当てる)。RT1は、IGPプロトコルを使用することにより、隣のラベルをアドバタイズし、そして、隣のラベルを用いてネットワーク全体をフラッディングする。ネットワーク内の別のデバイスは、IGPプロトコルを使用することにより、RT1によってアドバタイズされた隣のラベルを学習する。具体的に、別のノードは、RT1が行うように隣のラベルを割り当て、かつ、アドバタイズし、そして、隣のラベルを用いてネットワーク内の別のデバイスをフラッディングする。

コントローラは、SR-TEトンネルの制約属性に基づいてパスを計算する。パスを計算した後で、コントローラは、ラベルスタックリストを生成するために、トポロジおよび隣のラベルに基づいて、パス全体の隣のラベルを結合する。例えば、図1Bを参照すると、コントローラは、RT1->RT2->RT3->RT4->RT5としてSR-TEトンネルパスを計算し、対応するラベルスタックリストは{1031,1032,1034,1035}であり、そして、コントローラは、計算を通じて獲得されたラベルスタックリストをトランスポンダの入口ノードRT1へ配送する。従って、トランスポンダは、コントローラによって配送されたラベルスタックリストに基づいて、SR-TEトンネルを獲得する。この出願において、ノードラベルは、また、ラベルスタックリストを形成するために、ここにおいて使用されてもよく、すなわち、ラベルスタックリストは、{1002,2003,3004,4005}である。

トランスポンダは、SR-TEトンネルに対応するラベルスタックリストに基づいてパケット上でラベル操作（label operation）を実行し、スタックの上部ラベルに基づいてホップ毎に転送アウトバウンドインターフェイスホップをサーチし、そして、トンネルの宛先アドレスへ転送されるデータパケットをガイドする。

パケットがSR-TEトンネルに進入するときに、入口ノードは、ラベルスタックリストをパケットに追加する。パケットがSR-TEトンネルを通して転送されるときに、最上位ラベルに基づいて転送・アウトバウンドインターフェイスが探索された後で、入口ノードは最上位ラベルをポップする。例えば、図1Bに示されるように、入口ノードPE1は、ラベルスタックリスト{1031,1032,1034,1035}をデータパケットに追加し、次いで、スタックの上部のラベル1031に一致するリンクに基づいて、対応する転送・アウトバウンドインターフェイスがRT1->RT2リンクであることを見出し、そして、次いで、ラベル1031をポップする。パケットは、ラベルスタック{1032,1034,1035}を搬送し、そして、リンクRT1->RT2を通してネクストホップノードRT2へ転送される。中間ノードRT2がパケットを受信した後で、スタックの上部のラベル1032に一致するリンクに基づいて、対応する転送インターフェイスがRT2->RT3リンクであることが見い出され、次いで、ラベル1032がポップされる、等々。ノードRT3がパケットを受信した後で、ノードRT3は、中間ノードRT3と同じやり方で転送を継続する。ノードRT4が最後のラベル1035をポップした後で、データパケットは、ノードRT5へ転送される。外出ノードRT5によって受信されたパケットは、ラベルを有しておらず、そして、ルーティングテーブルをルックアップする（looking up）ことによって転送され続ける。

厳密なセグメントパスモードにおいては、たとえ同等コスト（equal-cost）パスが存在しても、ロード・バランシングは実行され得ない。この場合に、緩いパスのノードラベルは、ノードラベル、または、ノードラベルおよび隣のラベルによって形成されるハイブリッドラベルスタックに基づいて指定され得る。コントローラは、ラベルスタックをトランスポンダの第１ノードへ送信し、そして、トランスポンダは、ラベルをポップするために、ラベルスタックに基づいてホップ毎にアウトバウンドインターフェイスホップをサーチし、そして、データパケットをトンネルの宛先アドレスへ転送する。例えば、図1Bに示されるように、RT1からRT5までのパスにおいて、交差される（to be crossed）ように指定されるノードは、RT3およびRT4である。この場合には、緩いパスがRT1とRT3との間に形成され、そして、RT2またはRT6によって転送され得る。この場合に、RT1におけるパケット転送に使用されるラベルスタックリストは{2003,3004,4005}である。

リンクまたはノードの障害は、パケットがSR-TEを使用することにより転送されるときに発生し得る。現在は、パスを復元するためにFRRメカニズムが使用され得る。例えば、ノードR2が、故障ノードである。

ノードR2が故障していない場合に、SR-TEのラベルスタックによって識別される転送パスは、RT1->RT2->RT3->RT4->RT5である。ノードRT2が故障している場合に、ノードRT2の隣接するノードRT1は、ラベルポッピング(POP)アクションを実行するためにノードRT2を置き換えて、宛先アドレスとして次のレイヤ（layer）ラベルを使用し、そして、データパケットを転送するために、バックアップパスとして故障ノードRT2をバイパスしているパスを使用する。バックアップパスは、RT1->RT6->RT3->RT4->RT5である。

例えば、データパケットを送信するためにRT1によって使用されるラベルスタックリストは{1002,2003,3004,4005}である。RT1は、ラベルスタックの上部ラベル1002をチェックすることによってRT2が故障ノードであると決定し、そして、次いで、ラベルスタックの上部ラベル1002および第２ラベル2003をチェックすることによって、故障ノードの後のパスが到達する必要があるノードがRT3であると決定することができる。RT1は、第２ラベル2003によって識別されるノード(すなわち、RT3)に到達するように、故障ノードRT2をバイパスするパスを計算し、そして、ネクストホップノードRT2のSR-TE FRRのためのノード保護パスとして、そのパスを使用する。

故障ノードがSR-TE FRRパスに切り替えられるシナリオにおいては、次の３つの問題が存在している。

問題１：ラベル情報テーブルの容量が制限されている。例えば、容量は、ストレージ容量として参照され得ること。

問題２：緩いパスのせいで、パケットの転送に失敗すること。

問題３：不完全なフェールバックエントリのせいで、パケットの転送に失敗すること。

以下は、３つの問題、および、対応する解決策を詳細に説明している。

問題1について：

RT2ノードが故障する前に、各ノードは、事前にIGPを使用することにより、バックアップ転送テーブルおよびラベル情報テーブル(コンテキストテーブル)を計算している。各ノードは、各ノードに係る隣接するノードについてコンテキストテーブルを生成し、そこでは、各ノードに係る隣接するノードの数量が、各ノードにおいて生成されるコンテキストテーブルの量に等しい。コンテキストテーブルは、ネットワーク全体における全てのノードのノード(プレフィックス)ラベル、および、隣接するノードによってアドバタイズされる全ての隣のラベルを含んでいる。

例えば、ノードRT1は、その隣接するノードRT2についてコンテキストテーブルを生成し、そこでは、コンテキストテーブルが、ネットワーク全体における全てのノードに対応するノード(プレフィックス)ラベル情報、および、RT2によってアドバタイズされる隣のラベルを含んでいる。ネットワーク全体における全てのノードの各ノードに対応するノード(プレフィックス)ラベル情報は、ノードのノードラベルと、RT2ノードのSRGBの初期値との合計である。

コンテキストテーブルが事前に生成されるので、SR-TE FRRソリューションにおいて、ノードは、ノードの各隣接（neighbor）についてコンテキストテーブルを生成する。従って、コンテキストテーブルの仕様は、ネットワーク全体におけるノードの数量と、隣接するノードの隣接の数量とを足したものであり、そして、各ノードは、コンテキストテーブルに係る以下の数量を生成する必要がある。つまり、隣接の数量＊(ネットワーク全体におけるノードの数量と、隣接するノードの隣接の数量とを足したもの)、である。

ネットワークが比較的に大量のノードを含み、かつ、いくつかのノードによってサポートされるコンテキストテーブルの仕様が、ネットワーク全体におけるノードの数量と、隣接するノードの隣接の数量とを足したもの、といった仕様をサポートするには不十分である場合に、ノードによって生成されるコンテキストテーブルにおけるコンテンツは不完全である。ネットワーク内のノードが故障している場合には、正しいバックアップパスへ切り替えることができないので、パケットが転送されないことがある。

プライマリパス上のノードが故障しているか、または、ノードからネクストホップへのパスが故障している場合には、プライマリパス上のノードに係る以前ホップノードが、故障を了解した後で、以前ホップノードが、ノードの故障情報を用いてネットワーク内の別のノードにフラッディングすることが、留意されるべきである。

これに基づいて、この出願の実施形態は、伝送経路故障を処理するための方法を提供する。図2を参照する。

S201．第１ノードは、第２ノードから送信された第１パケットを受信する。

第２ノードは、プライマリパス上で第１ノードの以前ホップノードである。

S202．第３ノードが故障していると決定する場合に、第１ノードは、第１ノードのセグメントルーティンググローバルブロックSRGBの初期値と、第３ノードのSRGBの初期値との差異を決定する。

第３ノードは、プライマリパス上で第１ノードのネクストホップノードである。

S203．第１ノードは、第１パケットから第１ラベルを獲得する。ここで、第１ラベルは、第３ノードのSRGBの初期値、および、第４ノードのノードセグメント識別子に基づいて決定される。

第４ノードは、プライマリパス上で第３ノードのネクストホップノードである。

S204．第１ノードは、第１ノードから第４ノードへのバックアップパスの入来（incoming）ラベルとして、第１ラベルと差異との和を使用し、かつ、第１ノードから第４ノードへのバックアップパスの外出（outgoing）ラベルを、バックアップ転送テーブルから決定する。

S205．第１ノードは、外出ラベルに基づいて、第１パケットを、バックアップパス上で第１ノードのネクストホップノードに対して送信する。

前述のソリューションを使用することによって、バックアップパスは、SRGB差異およびバックアップ転送テーブルを使用して決定され、そうして、ノードによってサポートされるコンテキストテーブルの容量が不十分なために、データパケットが転送されない、という問題を克服することができる。

可能な実装において、第１パケットは、プライマリパスにおける第１パケットの転送についてガイダンスを提供するために使用されるラベルスタックリストを含む。そして、第１ノードのSRGBの初期値と第３ノードのSRGBの初期値との間の差異を決定することは、第１ノードによって、ラベルスタックリストの上部から第２ラベルを獲得することであり、ここで、第２ラベルは、第３ノードのノードセグメント識別子および第１ノードのSRGBの初期値に基づいて決定されること、および、第１ノードによって、バックアップ転送テーブルにおいて、第２ラベルに対応する第１転送挙動（forwarding behavior）を決定することであり、ここで、第１転送挙動は、ラベル情報テーブルをサーチするように示すために使用され、かつ、ラベル情報テーブルは、第２ラベルに対応する差異を含むこと、および、第１ノードによって、ラベル情報テーブルから差異を獲得すること、を含んでいる。

従来技術においては、プライマリパス上のノードが故障しているとき、かつ、故障ノードについてコンテキストテーブルを生成することにより、故障ノードの以前ホップノードをプライマリパスからバックアップパスへ切り替えたときに、ラベルスタック内の上部ラベルに従ってバックアップ転送をサーチする。
バックアップテーブル内の上部ラベルに対応している転送エントリにおける転送挙動がコンテキストテーブルをサーチすることであると決定された後で、バックアップパス上でパケットを転送する必要があるネクストホップノードがコンテキストテーブルに従って決定される。つまり、バックアップ転送テーブルは、従来技術においては一度だけクエリされ、そして、バックアップパスはコンテキストテーブルによって実装されることが決定される。しかしながら、この出願の実施形態において提供されるソリューションにおいては、SRGB間の差異が転送プレーンノードへ配送されるとき、故障ノードのネクストホップノードのノードラベルを決定するために、コンテキストテーブルだけが使用されることを必要とする。そして、バックアップパス上でパケットを転送するためのネクストホップノードが決定され、故障ノードのネクストホップノードのノードラベルに従って、バックアップ転送テーブルが再びクエリされる。従って、コンテキストテーブルは、全てのノードに対応しているノードラベルを含む必要はなく、そして、隣接するノードの隣のノード（adjacent node）に対応するラベル情報だけを含む必要があり、それによって、不十分なエントリ容量によって生じるパケット転送障害を回避しており、加えて、ストレージリソースをセーブすることができる。

可能な実装においては、第３ノードによってネットワーク内にフラッディングされた第３ノードのノードセグメント識別子を受信した後で、第１ノードは、第３ノードのノードセグメント識別子を用いて、ネットワーク内の別のノードをフラッディングする。ここで、第１ラベルは、第１ノードによってフラッディングされた第３ノードのノードセグメント識別子、および、第１ノードのSRGBの初期値に基づいて、第２ノードによって決定される。

これに基づいて、第２ノードは、第１ノードによってネットワーク内にフラッディングされた第３ノードのノードセグメント識別子を受信し、第３ノードは、第１ノードの隣のノードであり、そして、第１ノードによってフラッディングされた第３ノードのノードセグメント識別子の優先度（priority）は、第３ノードによってフラッディングされた第３ノードのノードセグメント識別子の優先度よりも低い。プライマリパスを使用することによりパケットを送信するプロセスにおいて、第２ノードは、第３ノードが故障していると決定する。第１ノードは、プライマリパス上で第２ノードのネクストホップノードであり、そして、第３ノードは、プライマリパス上で第１ノードのネクストホップノードである。第２ノードは、第１ノードによってフラッディングされた第３ノードのノードセグメント識別子に基づいて、バックアップパスを通じて、第１ノードへパケットを送信する。そして、第１ノードは、バックアップパス上で第２ノードのネクストホップノードである。

このようにして、問題２が解決され得る。具体的な実装については、以下の問題２の詳細な説明を参照のこと。

可能な実装において、第１ネットワーク装置は、故障が回復された後で、第３ネットワーク装置によって送信された指示情報を受信する。ここで、指示情報は、第３ネットワーク装置がパケットを正しく転送することができないことを示すために使用される。そして、第２ネットワーク装置から送信された第２パケットを受信するとき、第１ネットワーク装置は、決定された外出ラベルに基づいて第２パケットを送信する。このようにして、問題３が解決され得る。具体的な実装については、以下の問題３の詳細な説明を参照のこと。

以下では、特定のシナリオを参照して、この出願のこの実施形態において提供される伝送経路故障を処理するための方法について、より詳細に説明する。以下の方法は比較的に包括的であることが留意されるべきである。いくつかのステップまたは説明は、可能な実装である。方法プロシージャにおける任意の２つ以上のステップは、この出願のこの実施形態において保護される必要があるソリューションを構成し得る。具体的には、いくつかのステップが任意的であるときに、残りのステップは、この出願のこの実施形態において保護される必要があるソリューションを、やはり構成することができ、そして、任意のステップが、さらに、別の可能な実装を有し得る。

この出願のこの実施形態は、コンテキストテーブルを構成する方法を提供する。ノードが、IGPを使用することにより、隣接するノードによってアドバタイズされた隣のラベル（adjacency label）、および、隣接するノードの隣のノードのノードラベルを獲得するとき、そして、隣接するノードのSRGBを学習した後で、ノードは、コンテキストテーブルを生成する。コンテキストテーブルは、隣接するノードによってアドバタイズされる隣のラベル、隣接するノードの隣のノードのノードラベル情報、および、ノードのSRGBの初期値と、隣接するノードのSRGBの初期値との間の差異、を含んでいる。ここで、ここにおけるノードラベル情報は、隣接するノードのSRGBの初期値および隣接するノードの隣のノードのノードラベルの合計である。

一例として図3を使用して、RT2によって生成されたコンテキストテーブルのいくつかのコンテンツが表1に示されている。そして、表1は、コンテキストテーブルにおいて、隣接するノードRT3について生成されたエントリのいくつかのコンテンツを示している。RT2のSRGBの初期値は2000であり、そして、RT2の隣接するノードRT3のSRGBの初期値は3000である。従って、RT2のSRGBの初期値とRT3のSRGBの初期値との間の差異は、-1000である。

表1

インラベル（inlabel）は、入来ラベルを示しており、これは、ノードのSRGBの初期値に隣接するノードのSidを加えたものである。つまり、RT2のSRGBの初期値2000+RT3のノードラベル3=2003、である。入来ラベルは、コンテキストテーブルをクエリするためのキー(KEY)フィールドとして使用されている。

SRGB差異（SRGB difference）は、ノードのSRGBの初期値から隣接するノードのSRGBの初期値を引いたものである。

隣のSid（adj Sid）は、隣接するノードによってアドバタイズされた隣のラベルを示している。RT3によってアドバタイズされた隣のラベルは、RT3とRT4との間のリンクの隣のラベル1034、RT3とRT7との間のリンクの隣のラベル1037、および、RT3とRT6との間のリンクの隣のラベル1036である。

隣のノードSid（adj node Sid）は、隣接するノードによってアドバタイズされた隣接するラベルに対応する宛先ノードを示しており、それは、ノードのSRGBの初期値に宛先ノードによってアドバタイズされたノードSidを加えたものを使用する。例えば、RT3とRT4との間のリンクの隣のラベル1034の宛先ノードがRT4である場合に、1034に対応する隣のノードSidは、RT2のSRGBの初期値+RT4のノードラベル=2004 RT4、である。

以下では、データパケット転送プロセスを詳細に説明するために、一例として図3を使用する。

図3に示されるように、RT1からRT5までの経路について、交差するように指定されるノードは、RT3およびRT4である。この場合には、RT1とRT3との間に緩いパスが形成され、そして、RT2またはRT6によって転送され得る。この出願のこの実施形態において、RT1は、パス計算を実行し、そして、プライマリパスがRT1->RT2->RT3->RT4->RT5であることを決定する。この場合に、RT1におけるパケット転送のために使用されるラベルスタックリストは、{2003,3004,4005}である。例えば、RT3が故障している場合、バックアップパスは、RT1->RT2->RT7->RT4->RT5である。加えて、RT2は、ネットワーク全体において、ノードSidのプライマリ／バックアップ転送テーブルを生成し得る。プライマリ／バックアップ転送テーブルのいくつかのコンテンツについては、表2を参照のこと。図2は、入来ラベルが2003および2004である、２つのエントリの部分的な内容だけを示している。

表2

図3に示されるように、RT3が故障していない場合に、RT1は、データパケットをRT2へ送信する。ここで、データパケットにおけるラベルスタックは{2003,3004,4005}である。プライマリ転送テーブルが、ラベルスタック内の上部ラベルに基づいてサーチされる。例えば、表2がサーチされて、2003、2003である上部ラベルが、インラベルとして使用され、そして、入来ラベルは、サーチされ、かつ、入力ラベル2003に対応する転送エントリである。転送エントリにおいて示される転送挙動は、RT3へ転送され、そうして、RT2は、スタックの上部ラベルを3003に切り替える。つまり、スタックの上部ラベルは、ネクストホップノードのSRGBの初期値(RT3のSRGBの初期値)、および、宛先ノードのノードラベル(RT3のノードラベル)によって決定されるラベル値に基づいて決定されるラベル値へ切り替えられ、そして、次いで、更新されたデータパケットが、RT3へ転送される。RT2によって送信されたデータパケットをRT3が受信した後で、データパケット内のラベルスタックは{3003,3004,4005}であり、そして、スタックの上部ラベルが少なくとも受信ノードによってアドバタイズされたラベルであることが決定される。従って、スタックの上部ラベルがポップされた後で、上部ラベル3004に基づいて、ネクストホップノードがRT4であることが決定され、上部ラベル3004が4004へ切り替えられ、そして、更新されたデータパケットがRT4へ転送される。同様に、RT3によって送信されたデータパケットをRT4が受信した後で、データパケットのラベルスタックは{3004,4005}である。受信ノードはそれ自身であることを、上部ラベルが示すものと決定される。従って、上部ラベルがポップされる。上部ラベル4005に基づいて、ネクストホップノードがRT5であることが決定され、そして、従って、上部ラベルが5005へ切り替えられ、そして、更新されたデータパケットをRT5へ転送する。RT4によって送信されたデータパケットをRT5が受信した後で、データパケットのラベルスタックは{5005}である。受信ノードはそれ自身であることを、上部ラベルが示すものと決定される。従って、上部ラベルがポップされ、そして、転送テーブルが、転送のためにサーチされ続ける。

従って、RT1のデータパケットを受信した後で、データパケットのラベルスタックの上部ラベル2003に基づいて、RT2は、上部ラベルによって示されるネクストホップノードRT3が故障していると決定する。RT2は、RT3をバイパスする、RT3からネクストホップノードRT4への転送経路を見つける必要がある。このようにして、バックアップ転送テーブル(表2)がサーチされ、見つかった転送挙動が上部ラベル2003をポップし、そして、隣接するノードRT3についてRT2によって生成されたコンテキストテーブルがサーチされる。表1におけるコンテキストテーブルに基づいて獲得されたSRGB差異は、-1000であり、そして、上部ラベル2003がポップされている。この場合に、ラベルスタックは{3004,4005}である。RT2は、RT3からネクストホップノードRT4へのラベル、すなわち、上部ラベル3004を獲得する。スタックの上部ラベルとSRGBとの間の差異は合計として使用される。つまり、第２外出ラベル(3004)+SRGBとの差異(-1000)=2004であり、すなわち、入口ノードRT2から出口ノードRT4へのルーティングセグメント内でRT2における入来ラベルが獲得される。2004は、プライマリ転送テーブルをサーチするための入来ラベルとして使用される。見つかったネクストホップノードはRT3である。RT3へのインターフェイスが故障しているので、バックアップパスへ切り替えられ、そして、バックアップ転送テーブルがサーチされる。入来ラベルとして2004を使用することにより見い出された転送挙動はRT7へ転送され、そして、外出ラベルは7004である。そうして、RT2ノードは、スタックの上部ラベルを見い出された外出ラベルと交換する。すなわち、上部ラベル3004をポップし、かつ、7004と交換する。ここにおけるラベルスタックは{7004,4005}である。更新されたデータパケットが、RT7へ転送される。

データパケットを受信した後で、上部ラベル7004に基づいて、RT7は、ネクストホップノードがRT4であると決定して、上部ラベル7004を4004へ交換し、そして、更新されたデータパケットをRT4へ転送する。同様に、データパケットを受信した後で、RT4は、スタックの上部ラベルによって指示される宛先ノードがそれ自体であると決定し、スタックの上部ラベルをポップし、そして、更新されたラベルスタックの上部ラベル4005によって指示されるネクストホップノードがRT5であると決定して、上部ラベル4005を5005へ切り替え、そして、更新されたデータパケットをRT5へ送信する。

従来技術において、プライマリパス上のノードが故障した場合には、故障ノードの以前ホップノードが故障ノードについてコンテキストテーブルを生成し、そして、プライマリ／セカンダリ転送テーブルがプライマリパスからバックアップパスへ切り替えられた場合には、ラベルスタックにおける上部ラベルに従ってバックアップ転送テーブルをサーチし、バックアップ転送テーブルにおける上部ラベルに対応する転送エントリにおける転送挙動がコンテキストテーブルをサーチすることであると決定された後で、コンテキストテーブルに従って、バックアップパス上でパケットを転送する必要のあるネクストホップノードが決定される。つまり、従来技術では、バックアップ転送テーブルが一度だけクエリされ、そして、コンテキストテーブルを使用することによりバックアップパスが実装されることが決定される。しかしながら、この出願のこの実施形態において提供されるソリューションにおいては、SRGB間の差異が転送プレーンノードへ配送される場合には、故障ノードのネクストホップノードのノードラベルを決定するためにコンテキストテーブルだけが使用される必要があり、そして、バックアップパス上でパケットを転送するためのネクストホップノードが決定され、故障ノードのネクストホップノードのノードラベルを使用することによりバックアップ転送テーブルが再びクエリされる。従って、コンテキストテーブルは、全てのノードに対応するノードラベルを含む必要はなく、そして、隣接するノードの隣のノードに対応するラベル情報だけを含む必要があり、それによって、不十分なエントリ容量によって生じるパケット転送故障を回避し、加えて、ストレージリソースがセーブされ得る。

問題２について：

転送パス内に緩いパスが存在しており、かつ、緩いパスセグメント上の宛先ノードが故障している場合には、ノードの故障情報がネットワーク全体にフラッディングされた後で、ネットワーク全体における全てのノードは、故障ノードへの対応するプライマリおよびセカンダリ転送テーブルを削除する。緩いパスセグメント上の宛先ノードが故障している場合には、プライマリパスおよびバックアップパスの両方において、第１ノードから最後のノードまで、全てのノードが緩いパスセグメントを通過する必要があり、そして、故障ノードの以前ホップノードから故障ノードをバイパスすることによって最後のノードに到達することができる。故障ノードへのプライマリおよびセカンダリ転送テーブルが削除された後で、パスセグメント上のソースノードは、故障ノードの以前ホップノードへデータパケットを転送することができない。その結果、パケット転送の障害が生じる。

一例として図3を使用すると、RT1によって指定されたSR-TEパスが通過するノードは、RT3、RT4、およびRT5である。RT3が故障している場合に、RT2はRT3が故障していることを認識し、そして、IGPを使用することによりRT3の故障情報をフラッディング(Flooding)する。同時に、バックパスRT3、RT4、およびRT5へ切り替えるために、SR-TE FRRスイッチングがトリガされ、そして、故障ポイントRT3がバイパスされる。RT3の故障情報がネットワーク全体における全てのノードにフラッディングされると、RT1は、収束（convergence）を開始し、そして、RT3へのプライマリおよびバックアップ転送テーブルを削除する。結果として、RT1は、RT2へデータパケットを転送することができない。

これに基づいて、この出願の実施形態は、伝送経路故障を処理するための方法を提供する。故障ノードの以前ホップノードは、IGPプロトコルを使用することにより、ネットワーク全体の全てのノードに故障ノードのプレフィックス(ノード)ラベルをフラッディングする。一つの方法では、故障ノードの以前ホップノードが、故障ノードが故障していることを認識すると、IGPプロトコルを使用することにより、故障ノードのプレフィックス(ノード)ラベルがネットワーク全体にフラッディングされる。例えば、以前ホップノードによってフラッディングされた故障ノードのプレフィックスラベルの優先度は、故障ノードが、故障が発生する前に故障ノードのプレフィックスラベルを獲得するときに、故障ノードによってフラッディングされる故障ノードのプレフィックスラベルの優先度よりも低いように設定され得る。他の方法は、故障ノードが故障する前に、故障ノードのプレフィックスラベルを獲得するときに、故障ノードが、故障ノードのプレフィックスラベルをフラッディングし、そして、故障ノードが故障する前に故障ノードによってフラッディングされたプレフィックスラベルを受信するときに、故障ノードの以前ホップノードが、故障ノードのプレフィックスラベルをネットワーク全体にフラッディングする。例えば、以前ホップノードによってフラッディングされた故障ノードのプレフィックスラベルの優先度は、故障ノードが、故障が発生する前に故障ノードのプレフィックスラベルを獲得するときに、故障ノードによってフラッディングされる故障ノードのプレフィックスラベルの優先度よりも低いように設定され得る。

故障ノードのプレフィックスラベルをフラッディングするときに、以前ホップノードは、マッピングTLV(Type-Length-Value)で故障ノードのプレフィックスラベルを搬送し得る。

この出願のこの実施形態におけるマッピングTLVの詳細については、インターネットエンジニアリングタスクフォース(Internet Engineering Task Force、IETF)によってリリースされた文書draft-ietf-isis-segment-routing-extensionsを参照するように留意されるべきである。この文書のコンテンツおよび関連する部分は、全体として、導入（introduction）を使用することにより、一般的には、この明細書の中へ組み込まれている。簡潔のために、詳細は、ここにおいて再び説明されない。

TLV定義においては、３つのフィールドが存在する。ラベル(Tag)フィールド、長さ(Length)フィールド、および、コンテンツ(Value)フィールドである。値は、ラベルを含んでいる。マッピングTLVは、また、ラベル結合TLV(SID/Label Binding TLV)としても参照され得る。例えば、図5に示されるマッピングTLVフォーマットが、一例として使用される。タイプ（Type）はTLVのタイプを示し、長さ（Length）は制御パケットの長さを示し、フラグ（Flags）はフラグビットを示し、そして、リザーブ（RESERVED）は現在使用されていない予約ビットを示している。範囲（Range）フィールドはアドレスセグメントと関連するプレフィックスSIDセグメントを指定する能力を提供する。ここで、プレフィックス長（Prefix length）はプレフィックスの長さを表し、プレフィックス（prefix）はアドバタイズされたパスの最後のノードでの転送等価クラス（forwarding equivalence class）を表し、そして、サブTLV（SubTLV）はプレフィックスSIDを発行したサブTLVを表している。

例えば、この出願のこの実施形態において、以前ホップノードは、再びアドバタイズされたフラグビットを示すために、フラグにRフィールドを追加することができる。つまり、故障ノードに対するプレフィックスラベルが、ネットワーク全体における別のノードへ、以前ホップノードによって再びアドバタイズされる。

フラグのフォーマットについては、図6を参照のこと。Fは、アドレスファミリフラグを示している。このビットが設定されていない場合には、IPv4プレフィックスを示している。このビットが設定されている場合は、IPv6プレフィックスを示している。Mは、ミラーリング環境フラグを示している。アドバタイズされたSIDがミラーリング環境と関連付けられている場合に、このフラグが設定される。Sは、SID／ラベル結合TLVがルーティングドメイン全体においてフラッディングされ得るか否かを示している。このビットが設定されている場合には、SID／ラベル結合TLVが、ルーティングドメイン全体においてフラッディングされる。このビットが設定されていない場合、SID／ラベル結合TLVはレベル間でリークされ得ない。Dは、SID／ラベル結合TLVがレベル2からレベル1へリークされるときにフラグが設定される必要があることを示している。そうでなければ、フラグがクリアされる必要がある。Aは、補助フラグを示している。レベルは、中間システム間(Intermediate System-to-Intermediate system、IS-IS)のルーティングプロトコルにおけるネットワークレイヤリング（layering）の概念である。共通領域は、レベル1領域と呼ばれ、そして、バックボーン領域は、レベル2領域と呼ばれている。

図3に示されるネットワークアーキテクチャが、一例として使用される。RT3が故障していると決定したときに、RT2は、RT3のノードラベルをネットワーク全体にフラッディングする。RT2によってフラッディングされるRT3のノードラベルの優先度は、RT3によってフラッディングされるRT3のノードラベルの優先度よりも低くてよい。RT2によってフラッディングされるRT3のノードラベルを受信した後で、RT1は、RT3のノードラベルに基づいて、データパケットの外出ラベルをRT2へ送信するように決定する。つまり、RT2のSRGBの初期値+RT3のノードラベル=2000+3=2003、である。RT2がパケットを受信した後で、RT2は、連続的な転送のために、バックアップパスへ切り替える。RT2は、既存のコンテキストテーブルの形式でパケットを転送するために、バックアップパスへ切り替えることができ、そして、確実に、また、コンテキストテーブルを設定する前述の方法を使用することもできる。特定の送信プロセスについては、問題１の実施形態において説明されている転送方法を参照のこと。詳細は、ここにおいて再び説明されない。

問題３について：

プライマリパス上の転送ノードが故障している場合に、以前ホップノードは、パケットを転送するために、バックアップパスへ切り替える。故障ノードが回復し、かつ、再始動した後で、故障が回復した後のノードは、ノード(プレフィックス)ラベルおよびノードのものである隣のラベル、といった情報をネットワーク内の別のノードに再フラッディングする。故障が回復した後、ノードによってフラッディングされた情報を受信した後で、以前ホップノードは、データパケットをプライマリパスへ戻すように切り替える。つまり、パケットは、故障が回復した後でノードを再利用することにより送信される。しかしながら、故障が回復した後のノードは再始動されたばかりなので、ローカルデータベースは不完全なことがある。例えば、ローカルデータベースは、別のノードに関する情報を含まない。プライマリパス上で故障が回復された後の、ノードラベル、および、ノードのネクストホップノードの隣のラベル、に関する情報といったものである。この場合、RT3がパケットを受信した後で、パケットは、ネクストホップノードへ転送することができない。その結果として、データパケット損失が発生する。

図3に示されるように、RT1によって指定されるSR-TEパスは、RT3、RT4、およびRT5である。RT3が故障している場合、RT2は、RT3が故障していることを認識した後で、SR-TE FRRスイッチングをトリガし、そして、バックアップパスRT7、RT4、およびRT5へ切り替える。従って、故障ノードRT3は、バイパスされる。RT3が回復し、かつ、再始動した後で、RT3は、ノードSidをネットワーク全体へ再びアドバタイズし、そして、RT2は、データパケットを、RT3へ戻すように切り替える。しかしながら、RT3が再始動したばかりなので、そのローカルデータベースは完全ではないことがある。例えば、RT3は、RT4およびRT5のノードSIDを学習していない。結果として、データパケットは、RT3からネクストホップRT4へ転送することができず、そして、破棄される。

これに基づいて、この出願の実施形態は、伝送経路故障を処理するための方法を提供する。故障ノードが回復し、かつ、再始動されたときには、回復した故障ノードが故障ノードの回復を認識した際に、回復した故障ノードの以前ホップノードが別のノードのプレフィックスSIDを学習することを防止するために、回復した故障ノードは、別のノードのプレフィックスSIDを学習するように試み、そして、その後で、データパケットが失われる。故障ノードが回復した後で、指示情報は、最初に、ネットワーク全体においてリリースされ、そこでは、指示情報が、回復した故障ノードはパケットを正しく転送できないことを示すために使用される。従って、回復した故障ノードに対して送信されるべきデータパケットを受信するときに、以前ホップノードは、依然としてバックアップパスを通してデータパケットを転送する。

例えば、指示情報は、オーバーロード（overload）ビットにおいて搬送され得る。オーバーロードビットは、IS-ISルーティングプロトコルにおいて定義されている。ノードが、全ての接続されたステータスデータ(LSDB)、つまり、ネットワーク全体における全てのノードを回復するためにローカルストレージによって使用されるトポロジ情報、を完了できない場合に、ノードは、完全ではないLSDBを識別するために、自身によってアドバタイズされたリンク状態データパケットのヘッダ内のビットを使用する。その結果として、パケットを正しく転送することができず、そして、このビットのフラグビットはオーバーロード(OL)ビットと呼ばれる。ノードによってアドバタイズされたリンク状態パケット内のオーバーロードビットを使用することにより、別のノードは、ノードが正しいルーティング決定を行うことに失敗し得ること、つまり、ノードのLSDBが完全ではないので、データパケットを正しく転送できないことを知っている。別のノードは、最短経路を計算するときに、このノードを通してデータパケットを転送しない。

図3に示されるネットワークアーキテクチャが、一例として使用される。故障ノードRT3が回復し、かつ、再始動された後で、RT2が、RT3故障の回復を最初に認識するのを防ぐために、そして、この時点で、RT3は、RT4およびRT5のプレフィックスを学習しておらず、データパケットが失われるようになる。RT3は、故障のせいで、再開された後にリンク状態パケットのヘッダにオーバーロードビットフラグを追加する。

RT2は、RT3によってアドバタイズされたリンク状態パケット内のオーバーロードビットを受信し、そして、ネクストホップRT3がオーバーロード状態にあることを感知する。従って、ノードRT2は、故障回復の前にSR-TE FRR転送パスを使用し続け、そして、RT2は、既存のコンテキストテーブルの形式でバックアップパスを使用することによりデータパケットを転送することができ、そして、また、明確に、コンテキストテーブルの設定に係る前述の方法を使用することもでき、これは、ここにおいて限定されるものではない。特定の送信プロセスについては、図4に対応する実施形態における転送方法を参照のこと。詳細は、ここにおいて再び説明されない。

故障ノードがLSDBを完了するために要する時間、つまり、オーバーロード時間は、一般的に長く、例えば、60秒である。従って、持続時間（duration）内で、RT2は、コンテキストテーブルをルックアップすることにより、SR-TE FRRパス(バックアップパス)に基づいてデータパケットを転送することができる。例えば、オーバーロード持続時間が設定され得る。そして、RT2は、持続時間内にバックアップパスを使用することによりデータパケットを転送する。LSDBが完了すると、RT3は、ネットワーク全体においてリンク状態パケットを再びアドバタイズすることができ、そして、ヘッダは、オーバーロードビットを含んでいない。オーバーロードビットフラグを含まないリンク状態データパケットを受信した後で、RT2は、データパケットを転送するためにRT3へ戻すように切り替える。

本方法の実施形態と同じ発明の概念に基づいて、この出願の実施形態は、さらに、装置を提供し、そして、図7について参照がなされる。装置700は、ネットワーク装置に対して適用される。装置700は、受信モジュール701、処理モジュール702、および、送信モジュール703を含み得る。装置700は、具体的には、ネットワーク装置内のプロセッサ、チップ、チップシステム、機能モジュール、等であり得る。処理モジュール702は、装置700の動作を制御し、かつ、管理するために使用され、受信モジュール701は、情報またはパケットを受信するために使用され、送信モジュール703は、情報またはパケットを送信するために使用され、そして、処理モジュール702は、受信モジュール701によって受信された情報またはパケットを処理するために使用される。処理モジュール702は、また、上述の実施形態のいずれかにおけるネットワーク装置(第１ノードまたはRT2、といったもの)内の処理プロセス、及び／又は、この出願において説明される技術的ソリューションの別のプロセスを示すためにも使用され得る。本装置は、さらに、ストレージモジュール(図7には示されていない)を含んでよく、ここで、ストレージモジュールは、コンテキストテーブルおよびプライマリ／バックアップ転送テーブルを保管するように構成されている。可能な実装において、装置700は、故障ノードの以前ホップノード、例えば、図2に対応する実施形態における第１ノード、または、図3および図4に対応する実施形態におけるRT2、に対して適用され得る。

例えば、装置180は、第１ノードに対して適用される。受信モジュール701は、第２ノードによって送信された第１パケットを受信するように構成されており、ここで、第２ノードは、プライマリパス上で第１ノードの以前ホップノードである。処理モジュール702は、第１ノードのセグメントルーティンググローバルブロックSRGBの初期値と、第３ノードが故障していると決定されたときの第３ノードのSRGBの初期値との差異を決定するように構成されており、ここで、第３ノードは、プライマリパス上で第１ノードのネクストホップノードである。第１パケットから第１ラベルを獲得するように構成され、ここで、第１ラベルは、第３ノードのSRGBの初期値および第４ノードのノードセグメント識別子に基づいて決定されており、ここで、第４ノードはプライマリパス上で第３ノードのネクストホップノードである。第１ラベルおよび差異の合計を、第１ノードから第４ノードへのバックアップパスに係る入来ラベルとして使用し、かつ、バックアップ転送テーブルから、第１ノードから第４ノードへのバックアップパスの外出ラベルを決定するように構成されている。そして、送信モジュール703は、外出ラベルに基づいてバックアップパス上で第１ノードのネクストホップノードへ第１パケットを送信するように構成されている。

可能な実装において、第１パケットは、プライマリパス上で第１パケットを転送することについてガイダンスを提供するために使用されるラベルスタックリストを含んでいる。

処理モジュール702は、具体的には、第１ノードのSRGBの初期値と第３ノードのSRGBの初期値との差異を決定するときに、ラベルスタックリストの上部から第２ラベルを獲得するように構成されており、ここで、第２ラベルは、第３ノードのノードセグメント識別子および第１ノードのSRGBの初期値に基づいて決定されている。バックアップ転送テーブルにおいて、第２ラベルに対応する第１転送挙動を決定するように構成され、ここで、第１転送挙動は、ラベル情報テーブルをサーチするように指示するために使用され、かつ、ラベル情報テーブルは、第２ラベルに対応する差異を含んでいる。そして、ラベル情報テーブルから差異を獲得するように構成されている。

可能な実装において、第１パケットから第１ラベルを獲得するときに、処理モジュール702は、具体的に、ラベルスタックリストの上部で第２ラベルをポップした後で、そこから第２ラベルがポップされるラベルスタックリストの上部から第１ラベルを獲得するように構成されている。処理モジュール702は、さらに、ラベルスタックリスト内の第１ラベルを外出ラベルへ切り替えるようにさらに構成されている。そして、送信モジュール703は、具体的に、更新された第１パケットを、バックアップパス上で第１ノードのネクストホップノードに送信するように構成されている。

可能な実装において、送信モジュール703は、さらに、第２ノードによって送信された第１パケットを受信モジュール701が受信する前で、かつ、第３ノードによってネットワーク内にフラッディングされた第３ノードのノードセグメント識別子が受信された後で、別のノードに対する第３ノードのノードセグメント識別子をネットワークにフラッディングするように構成されており、ここで、第１ノードによってフラッディングされた第３ノードのノードセグメント識別子の優先度は、第３ノードによってフラッディングされた第３ノードのノードセグメント識別子の優先度よりも低い。

第１ラベルは、第３ノードのノードセグメント識別子、および、第１ノードによってフラッディングされた第１ノードのSRGBの初期値に基づいて、第２ノードによって決定される。

可能な実施形態において、受信モジュールは、さらに、故障が回復した後で、第３ネットワーク装置によって送信された指示情報を受信するように構成されており、ここで、指示情報は、第３ネットワーク装置がパケットを正しく転送できないことを示すために使用されている。そして、送信モジュールは、さらに、第２ネットワーク装置によって送信された第２パケットを受信モジュールが受信したときに、決定された外出ラベルに基づいて第２パケットを送信するように構成されている。

可能な実施形態において、装置700は、緩いパスセグメントのソースノード、例えば、図2に示される第２ノード、または、図3および図4に対応する実施形態におけるRT1、に対して適用され得る。

一例として第２ノードへの適用を使用すると、受信モジュール701は、第１ネットワーク装置によってネットワーク内でフラッディングされた第３ネットワーク装置のノードセグメント識別子を受信するように構成されており、ここで、第３ネットワーク装置は、第１ネットワーク装置の隣接するネットワーク装置であり、かつ、第１ネットワーク装置によってフラッディングされた第３ネットワーク装置のノードセグメント識別子の優先度は、第３ネットワーク装置によってフラッディングされた第３ネットワーク装置のノードセグメント識別子の優先度よりも低い。処理モジュール702は、プライマリパスを使用することによりパケットを送信するプロセスで、第３ネットワーク装置において故障が発生したことを決定するように構成されており、ここで、第１ネットワーク装置は、プライマリパス上で第２ネットワーク装置のネクストホップネットワーク装置であり、かつ、第３ネットワーク装置は、プライマリパス上で第１ネットワーク装置のネクストホップネットワーク装置である。そして、送信モジュール703は、第１ネットワーク装置によってフラッディングされた第３ネットワーク装置のノードセグメント識別子に基づいて、バックアップパスにわたりパケットを第１ネットワーク装置へ送信するように構成されており、ここで、第１ネットワーク装置は、バックアップパス上で第２ネットワーク装置のネクストホップネットワーク装置である。

この出願の実施形態は、さらに、ネットワーク装置の構造を提供する。図8に示されるように、ネットワーク装置800は、通信インターフェイス810およびプロセッサ820を含み得る。任意的に、ネットワーク装置800は、さらに、メモリ830を含み得る。メモリ830は、ネットワーク装置の中に配置されてよく、または、ネットワーク装置の外に配置されてよい。図7に示されるように、処理モジュール702は、プロセッサ820によって実装されている。受信モジュール701および送信モジュール703は、通信インターフェイス810によって実装され得る。

可能な実装において、プロセッサ820は、通信インターフェイス810を使用することによりパケットまたはメッセージを受信し、かつ、送信し、そして、図2から図4までにおけるノード(第１ノードまたはRT2)によって実行される任意の方法を実装するように構成されている。実装の最中に、プロセスフローのステップは、プロセッサ820におけるハードウェアの集積論理回路またはソフトウェア内の命令を介して、図2から図4までに記載された第１ノードまたはRT2によって実行される方法を実装し得る。簡潔のために、詳細は、ここにおいて再び説明されない。上述の方法を実施するためにプロセッサ820によって実行されるプログラムコードは、メモリ830内に保管され得る。メモリ830は、プロセッサ820に結合されている。

可能な実装において、プロセッサ820は、通信インターフェイス810を使用することによりパケットまたはメッセージを受信し、かつ、送信し、そして、図2から図4までにおけるノード(第１ノードまたはRT2)によって実行される任意の方法を実装するように構成されている。実装の最中に、プロセスフローのステップは、プロセッサ820におけるハードウェアの集積論理回路またはソフトウェア内の命令を介して、図2から図4までに記載された第１ノードまたはRT2によって実行される方法を実装し得る。簡潔のために、詳細は、ここにおいて再び説明されない。上述の方法を実施するためにプロセッサ820によって実行されるプログラムコードは、メモリ830内に保管され得る。メモリ830は、プロセッサ820に結合されている。

この出願の実施形態における任意の通信インターフェイスは、回路、バス、トランシーバ、または、情報を交換するように構成され得る任意の他の装置であってよい。例えば、ネットワーク装置800内の通信インターフェイス810は、例示的に、ネットワーク装置800の以前ホップノードまたはネクストホップノードといった、ネットワーク装置800に対して接続された装置であり得る。

この出願の実施形態において、プロセッサは、汎用プロセッサ、デジタル信号プロセッサ、特定用途向け集積回路、フィールドプログラマブルゲートアレイまたは別のプログラマブル論理デバイス、個別ゲートまたはトランジスタ論理デバイス、もしくは、個別ハードウェアコンポーネントであってよく、そして、この出願の実施形態において開示される方法、ステップ、および、論理ブロックダイアグラムを実装し、または実行し得る。汎用プロセッサは、マイクロプロセッサ、任意の従来のプロセッサ、等であってよい。この出願の実施形態を参照して開示される方法のステップは、ハードウェアプロセッサによって直接的に実行されてよく、または、プロセッサ内のハードウェアとソフトウェアモジュールとの組み合わせを使用することにより実行されてよい。

この出願の実施形態における接続（coupling）は、装置、モジュール、またはモジュール間の間接的な接続、もしくは、通信接続であり、電気的、機械的、または別の形態であってよく、そして、装置、モジュール、およびモジュール間での情報の相互作用のために使用される。

プロセッサ820は、メモリ830と一緒に動作し得る。メモリ830は、ハードディスク(hard disk drive、HDD)またはソリッドステートドライブ(solid-state drive、SSD)といった、不揮発性メモリであってよく、もしくは、揮発性メモリ(volatile memory)、例えば、ランダムアクセスメモリ(random-access memory、RAM)であってよい。メモリ830は、期待されるプログラムコードを命令またはデータ構造の形態で搬送または保管することができ、かつ、コンピュータによってアクセスされ得る、任意の他の媒体であるが、これらに限定されるわけではない。

この出願のこの実施形態において、通信インターフェイス810、プロセッサ820、および、メモリ830の間の特定の接続媒体は、限定されるものではない。この出願のこの実施形態に従って、図8において、メモリ830、プロセッサ820、および、通信インターフェイス810は、バスを使用することにより相互に接続されている。バスは、図8において太線を使用することにより表されている。他のコンポーネント間における接続の方法は、単に概略的に説明されてだけであるが、限定として使用されるものではない。バスは、アドレスバス、データバス、制御バス、等へ分類することができる。表現を容易にするために、図8におけるバスを表すために、１本の太線だけが使用されているが、このことは、1本だけのバス、または、１つだけのタイプのバスが存在することを意味するものではない。

前述の実施形態に基づいて、この出願の実施形態は、さらに、コンピュータ記憶媒体を提供する。記憶媒体は、ソフトウェアプログラムを保管し、そして、１つ以上のプロセッサによって読み出され、かつ、実行されるときに、ソフトウェアプログラムは、前述の実施形態のうちいずれか１つ以上において提供される方法を実装することができる。コンピュータ記憶媒体は、リムーバブルハードディスク、リードオンリーメモリ、ランダムアクセスメモリ、磁気ディスク、または、光ディスクといった、プログラムコードを保管することができる任意の媒体を含み得る。

上述の実施形態に基づいて、この出願のこの実施形態は、また、チップも提供する。ここで、チップは、上述の実施形態のうちいずれか１つ以上の機能を実施するためのプロセッサを含む。例えば、図2から図4までにおける第１ノードまたはRT2によって実行される方法を実装するため、または、図2から図4までにおける第２ノードまたはRT1によって実行される方法を実装するためである。任意的に、チップは、さらに、メモリを含み得る。メモリは、必要であり、かつ、プロセッサによって実行される、プログラム命令およびデータを保管するように構成されている。チップシステムは、チップを含んでよく、または、チップおよび別の個別デバイスを含んでよい。

当業者であれば、この出願の実施形態が、方法、システム、または、コンピュータプログラム製品として提供され得ることを理解すべきである。従って、この出願は、ハードウェアだけの実施形態、ソフトウェアだけの実施形態、または、ソフトウェアおよびハードウェアの組み合わせを用いる実施形態に係る形態を使用することができる。さらに、この出願は、コンピュータで使用可能なプログラムコードを含む、１つ以上のコンピュータで使用可能な記憶媒体(これらに限定されるわけではないが、ディスクメモリ、CD-ROM、光メモリ等、を含む)において実装されるコンピュータプログラム製品の形態を使用することができる。

この出願は、この出願の実施態様に従った方法、装置(システム)、および、コンピュータプログラム製品に係るフローチャート及び／又はブロックダイアグラムを参照して説明されている。コンピュータプログラム命令は、フローチャート及び／又はブロックダイアグラムにおける各プロセス及び／又は各ブロック、および、フローチャート及び／又はブロックダイアグラムにおけるプロセス及び／又はブロックの組み合わせを実施するために使用され得ることが理解されるべきである。これらのコンピュータプログラム命令は、汎用コンピュータ、専用コンピュータ、組み込み（embedded）プロセッサ、または、マシンを生成するための任意の他のプログラマブルデータ処理装置のプロセッサのために提供され得る。そうして、コンピュータ、または、任意の他のプログラマブルデータ処理装置のプロセッサによって実行される命令は、フローチャート内の１つ以上のプロセス、及び／又は、ブロックダイアグラム内の１つ以上のブロックにおいて特定の機能を実現するための装置を生成する。

これらのコンピュータプログラム命令は、特定の方法で動作するようにコンピュータまたは他の任意のプログラマブルデータ処理装置を命令することができる、コンピュータで読取り可能なメモリに保管され得る。そうして、コンピュータで読取り可能なメモリに保管された命令は、命令装置を含むアーチファクトを生成する。命令装置は、フローチャート内の１つ以上のプロセス、及び／又は、ブロックダイアグラム内の１つ以上のブロックにおける特定の機能を実装する。

これらのコンピュータプログラム命令は、コンピュータまたは別のプログラマブルデータ処理装置上へとロードされてよく、そうして、一連の動作およびステップがコンピュータまたは別のプログラマブル装置において実行され、それによって、コンピュータに実装される処理を生成している。従って、コンピュータまたは別のプログラマブル装置において実行される命令は、フローチャート内の１つ以上のプロセス、及び／又は、ブロックダイアグラム内の１つ以上のブロックにおける特定の機能を実装するためのステップを提供する。

当業者であれば、この出願の範囲から逸脱することなく、この出願に対して様々な修正および変更を成し得ることが明らかである。この出願は、これらの修正および変形をカバーするように意図されている。ただし、それらは、以下の請求項およびそれらと均等な技術によって定義される保護の範囲内にある。

７００ 装置700
７０１ 受信モジュール
７０２ 処理モジュール
７０３ 送信モジュール
８００ ネットワーク装置
８１０ 通信インターフェイス
８２０ プロセッサ

Claims (12)

1. 伝送経路故障を処理するための方法であって、
   第１ネットワーク装置によって、第２ネットワーク装置により送信された第１パケットを受信するステップであり、前記第２ネットワーク装置は、プライマリパス上で前記第１ネットワーク装置の以前ホップネットワーク装置である、ステップと、
   第３ネットワーク装置が故障していることを決定したことに応じて、前記第１ネットワーク装置によって、前記第１ネットワーク装置のセグメントルーティンググローバルブロックSRGBの初期値と、前記第３ネットワーク装置のSRGBの初期値との間の差異を決定するステップであり、前記第３ネットワーク装置は、前記プライマリパス上で前記第１ネットワーク装置のネクストホップネットワーク装置である、ステップと、
   前記第１ネットワーク装置によって、前記第１パケットから第１ラベルを獲得するステップであり、前記第１ラベルは、前記プライマリパス上で第３ネットワーク装置のネクストホップネットワーク装置である、第４ネットワーク装置に対応している、ステップと、
   前記第１ネットワーク装置によって、前記第１ラベルと前記差異との合計値に基づいて、前記第１ネットワーク装置から前記第４ネットワーク装置へのバックアップパスを決定する、ステップと、
   前記第１ネットワーク装置によって、前記第１パケットを、前記バックアップパス上で前記第１ネットワーク装置のネクストホップネットワーク装置に対して送信するステップと、
   を含む、方法。
2. 前記第１ラベルは、前記第３ネットワーク装置のSRGBの初期値、および、前記第４ネットワーク装置のノードセグメント識別子に基づいて決定される、
   請求項１に記載の方法。
3. 前記第１ネットワーク装置によって、前記第１ラベルと前記差異との合計値に基づいて、前記第１ネットワーク装置から前記第４ネットワーク装置へのバックアップパスを決定する、前記ステップは、
   前記第１ネットワーク装置によって、前記第１ラベルと前記差異との合計値を、入来ラベルとして使用するステップと、
   前記第１ネットワーク装置によって、転送テーブルから、前記第１ネットワーク装置から前記第４ネットワーク装置への前記バックアップパスの外出ラベルを決定するステップと、
   を含み、
   前記入来ラベルにより前記転送テーブルをサーチして、前記外出ラベルが決定される、
   請求項１に記載の方法。
4. 前記方法は、さらに、
   前記第３ネットワーク装置によりネットワーク内にフラッディングされた前記第３ネットワーク装置のノードセグメント識別子を受信した後で、前記第１ネットワーク装置によって、前記第３ネットワーク装置の前記ノードセグメント識別子を、前記ネットワーク内の別のネットワーク装置にフラッディングするステップ、を含む、
   請求項１乃至３いずれか一項に記載の方法。
5. 前記方法は、さらに、
   前記故障が回復した後で、前記第１ネットワーク装置によって、前記第３ネットワーク装置により送信された指示情報を受信するステップであり、前記指示情報は、前記第３ネットワーク装置がパケットを正しく転送できないことを示すために使用される、ステップと、
   前記第２ネットワーク装置により送信された第２パケットを受信したときに、前記第１ネットワーク装置によって、前記バックアップパスに基づいて前記第２パケットを送信するステップと、
   を含む、請求項１乃至４いずれか一項に記載の方法。
6. 伝送経路故障を処理するための装置であって、該装置は、第１ネットワーク装置に対して適用され、
   受信モジュールであり、第２ネットワーク装置により送信された第１パケットを受信するように構成されており、前記第２ネットワーク装置は、プライマリパス上で前記第１ネットワーク装置の以前ホップネットワーク装置である、受信モジュールと、
   処理モジュールであり、
   第３ネットワーク装置が故障していることを前記処理モジュールが決定したことに応じて、前記第１ネットワーク装置のセグメントルーティンググローバルブロックSRGBの初期値と、前記第３ネットワーク装置のSRGBの初期値との間の差異を決定するように構成されており、前記第３ネットワーク装置は、前記プライマリパス上で前記第１ネットワーク装置のネクストホップネットワーク装置であり、
   前記第１パケットから第１ラベルを獲得するように構成されており、前記第１ラベルは、前記プライマリパス上で第３ネットワーク装置のネクストホップネットワーク装置である、第４ネットワーク装置に対応しており、
   前記第１ラベルと前記差異との合計値に基づいて、前記第１ネットワーク装置から前記第４ネットワーク装置へのバックアップパスを決定するように構成されている、
   処理モジュールと、
   送信モジュールであり、前記第１パケットを、前記バックアップパス上で前記第１ネットワーク装置のネクストホップネットワーク装置に対して送信するように構成されている、送信モジュールと、
   を含む、装置。
7. 前記第１ラベルは、前記第３ネットワーク装置のSRGBの初期値、および、前記第４ネットワーク装置のノードセグメント識別子に基づいて決定される、
   請求項６に記載の装置。
8. 前記処理モジュールは、さらに、
   前記第１ラベルと前記差異との合計値を、入来ラベルとして使用し、かつ、
   転送テーブルから、前記第１ネットワーク装置から前記第４ネットワーク装置への前記バックアップパスの外出ラベルを決定する、
   ように構成されており、
   前記入来ラベルにより前記転送テーブルをサーチして、前記外出ラベルが決定される、
   請求項６に記載の装置。
9. 前記送信モジュールは、さらに、
   前記第３ネットワーク装置によりネットワーク内にフラッディングされた前記第３ネットワーク装置のノードセグメント識別子を受信した後で、前記第３ネットワーク装置の前記ノードセグメント識別子を、前記ネットワーク内の別のネットワーク装置にフラッディングするように構成されている、
   請求項６乃至８いずれか一項に記載の装置。
10. 前記受信モジュールは、さらに、
    前記故障が回復した後で、前記第３ネットワーク装置により送信された指示情報を受信するように構成されており、前記指示情報は、前記第３ネットワーク装置がパケットを正しく転送できないことを示すために使用され、かつ、
    前記送信モジュールは、さらに、
    前記第２ネットワーク装置により送信された第２パケットを前記受信モジュールが受信したときに、前記バックアップパスに基づいて前記第２パケットを送信するように構成されている、
    請求項６乃至９いずれか一項に記載の装置。
11. ネットワーク装置であって、
    通信インターフェイス、プロセッサ、および、メモリを含み、
    前記メモリは、ソフトウェアプログラムを保管するように構成されており、かつ、
    前記プロセッサは、
    前記メモリに格納された前記ソフトウェアプログラムを読み出し、
    前記通信インターフェイスを介してメッセージを受信して、送信し、かつ、
    請求項１乃至５いずれか一項に記載の前記方法を実施する、
    ように構成されている、
    ネットワーク装置。
12. システムであって、
    請求項６乃至１０いずれか一項に記載の装置、もしくは、
    請求項１１に記載のネットワーク装置、
    を含む、システム。

Images