(57)【特許請求の範囲】
【請求項１】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、
前記故障復旧システムの各ノードは、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、
前記テーブル探索部は、
前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、
前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とする故障復旧システム。
【請求項２】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、
前記故障復旧システムの各ノードは、
パケットを送受信する通信部と、
前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、
前記テーブル探索部は、
前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、
前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、
前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、
前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、
前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とする故障復旧システム。
【請求項３】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、
パケットを送受信する通信部と、
各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ−ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、
前記テーブル探索部は、
前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、
前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とするノード。
【請求項４】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、
パケットを送受信する通信部と、
各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、
前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ−ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、
前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、
前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、
前記テーブル探索部は、
前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、
前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、
前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、
前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、
前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とするノード。
【請求項５】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、
前記故障復旧システムのノードは、
各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、
前記トポロジ情報に基づき、パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成するステップと、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するステップと、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するステップと、
前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、
前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得するステップと、
前記次ＦＩＢ-ＩＤを付した前記パケットを受信し、当該次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次ＦＩＢ-ＩＤを取得するステップを実行し、
前記ＦＩＢ-ＩＤ探索テーブルを作成するステップでの、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とする故障復旧方法。
【請求項６】
複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、
前記故障復旧システムのノードは、
各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、
前記トポロジ情報に基づき、パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成するステップと、
１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するステップと、
前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するステップと、
前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、
前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得するステップと、
前記次ＦＩＢ-ＩＤを付した前記パケットを受信し、当該次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次ＦＩＢ-ＩＤを取得するステップを実行し、
前記ＦＩＢ-ＩＤ探索テーブルを作成するステップでの、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、
前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、
前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、
前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、
前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択すること
を特徴とする故障復旧方法。
【請求項７】
請求項５または請求項６に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Internet Protocol）ネットワーク等のパケット交換網における、故障復旧時の転送経路再設定技術に関する。
【背景技術】
【０００２】
ネットワークにおいては、予期しない故障の発生に対して迅速に転送経路を切り替えることで故障復旧を行い、転送品質の維持を行うことが重要である。ＩＰネットワークにおける故障復旧方式として、ＯＳＰＦ（Open Shortest Path First）等のルーチングプロトコルを用いた動的な復旧方式がある（非特許文献１参照）。
【０００３】
ＯＳＰＦでは、故障を検知したノードは、全ノードに故障情報を通知（フラッディング）する。故障情報を受け取ったノードは、新規に作成される故障箇所を除いた網トポロジ情報をもとに迂回経路を計算することで、自動的に転送経路を切り替えることが可能となる。しかし、ＯＳＰＦでは故障発生後に迂回経路を計算するため、故障の復旧に秒単位の時間を必要とする問題がある。また、故障情報の通知や迂回経路の計算は、ＩＰネットワークの規模に依存して増加する。
【０００４】
このような問題を解決する方法として、事前に迂回経路を計算しておくことで高速な故障復旧を実現するＩＰ−ＦＲＲ（IP Fast Reroute）方式が提案されている（非特許文献２参照）。ＩＰ−ＦＲＲ方式は、事前に予備トポロジを作成し、故障発生時には該当故障箇所をプロテクトする（迂回する）予備トポロジに従った転送経路に切り替えることで故障復旧を行う。
【０００５】
ＩＰ−ＦＲＲ方式における予備トポロジを用いた故障復旧方法の具体例を、図１を参照して説明する。図１（ａ）は、通常のトポロジの一例を示し、図１（ｂ）は、予備トポロジの一例を示す。
【０００６】
まず、各ノードは、リンク断絶（故障）に備えた予備トポロジを予め作成しておく。例えば、リンク１−２（ノード番号「１」のノードと、ノード番号「２」のノードとの間のリンク）が断絶した場合に備え、このリンク１−２をプロテクトする予備トポロジを事前に作成する。ここで、予備トポロジにおけるプロテクトリンクのリンクコストは、このプロテクトリングが経路として選択されないようにするため、設定可能な最大値を付与する。これにより、予備トポロジ上でリンクコストの総和が最小となる最小コストルーティングにより経路を計算すると、プロテクトリンクを使用しない経路が算出される。この予備トポロジは全てのノードに記憶され、各ノードは予備トポロジに従った経路を事前に（トラヒック転送前に）計算しておく。
【０００７】
ここで、ノード番号「１」のノードをｓｒｃ（source：送信元）とし、ノード番号「５」のノードをｄｓｔ（destination：宛先）とする経路上において、リンク１−２の故障を検出した場合を考える。例えば、図１（ａ）に示す通常のトポロジ上で、（１）リンク１−２の故障を検出すると、故障検出ノード（ノード番号「１」のノード）は、故障リンクをプロテクトする予備トポロジＡに従ってパケットをノード番号「４」のノードに転送する（図１（ｂ）参照）。このとき、故障検出ノード（ノード番号「１」のノード）は、リンク１−２が故障ノードしたことを知っているので、予備トポロジＡを使用すれば故障箇所を迂回できることを知っている。
【０００８】
しかし、他のノード（例えば、ノード番号「４」のノード）は、故障箇所を把握できていない。そこで、故障検出ノード（ノード番号「１」のノード）は、（２）使用する予備トポロジＡを選択し、この予備トポロジＡのＩＤ（Identification）をノード番号「４」のノードに転送するパケットのヘッダに記述しておく。そして、迂回経路上に存在する他のノード（ここでは、ノード番号「４」のノード）はパケットを受信すると、（３）このパケットのヘッダを参照し、使用すべき予備トポロジＡを選択し、その選択した予備トポロジＡに従って、パケットをノード番号「５」のノードに転送する。このように、故障検出ノードは、使用する予備トポロジのＩＤをパケットに付与することで、データ転送と同時に故障箇所を間接的に伝搬する。
【０００９】
図２は、任意の単一リンクの故障をプロテクトする予備トポロジの設計例を示す。図２（ａ）は、通常のトポロジであり、図２（ｂ）〜（ｄ）は、図２（ａ）の通常のトポロジの予備トポロジを示す。予備トポロジは、全体の予備トポロジの数を削減するため、単一のトポロジで複数のリンクをプロテクトするように設計される。
【００１０】
また、これまでに、予備トポロジ数を最小化したり（非特許文献３参照）、迂回後の負荷を平滑化したり（非特許文献４参照）する予備トポロジ設計アルゴリズムが提案されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】“OSPF Version 2”,[online], April 1998, IETF RFC2328, ［平成２３年８月３１日検索］,インターネット<URL:http://www.ietf.org/rfc/rfc2328.txt>
【非特許文献２】A.Kvalbein, A.F.Hansen, et al.,“Fast IP Network Recovery using Multiple Routing Configurations,” in Proceedings of INFOCOM, Apr.2006.
【非特許文献３】S.Kamamura, T.Miyamura, et al.,“Scalable Backup Configurations Creation for IP Fast Reroute,”IEICE Trans. Commun Vol.E94-B  No.1  pp.109-117, 2011.1.
【非特許文献４】R.Takahashi, S.Tembo, et al.,“Dispersing Hotspot Traffic in Backup Topology for IP Fast Reroute,”submitted to IEEE ICC, 2011.6.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、既存の方式は、単一のリンクやノードの故障に対しては安定的に動作するが、多重故障の発生によって転送ループが発生する問題がある。なお、パケット交換網上の転送ループは、該当パケットがロスするだけでなく、ループするパケットによる帯域消費が、他のパケット通信に悪影響を与える可能性があるため、極力避ける必要がある。
【００１３】
転送ループ発生の具体例を、図３を参照して説明する。ノード「ｉ」からノード「ｄｓｔ」に向けてパケットを転送する際に、図３（ａ）に示すリンク故障ｘ，ｙが発生する場合を考える。故障ｘを検出したノード「ｉ」は、予備トポロジ＃２を選択し、予備トポロジ＃２に従った予備経路「１」−「２」−「３」−「８」−「７」−「６」に沿った転送を試みる（図３（ｂ）参照）。一方で、予備経路上には２つ目の故障である故障ｙが存在するため、故障ｙを検出したノード「ｊ」は、故障ｙをプロテクトする予備トポロジ＃１を選択する（図３（ｃ）参照）。ここで、予備トポロジ＃１に従った予備経路「２」−「１」−「６」は、再度リンク故障ｘを含む経路となる。結果として、この例ではノード「ｉ」とノード「ｊ」との間で、転送ループが発生する。
【００１４】
この問題は、既存技術では、故障検出ノード以外のノードには、予備トポロジのＩＤのみが伝搬されるため、故障箇所の特定ができないことに起因する。例えば、二重故障の場合、２番目の故障を検出したノードは、２番目の故障を回避する予備トポロジを選択することは可能であるが、１番目の故障の故障箇所が既知ではないため、再度１番目の故障を含む予備トポロジを選択する可能性があり、このような場合には、転送ループが発生する。
【００１５】
このような背景に鑑みて本発明がなされたのであり、本発明は、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１６】
前記した課題を解決するため、請求項１に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードが、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ−ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、前記テーブル探索部が、前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とする故障復旧システムとした。
【００１７】
また、請求項３に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ−ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、前記テーブル探索部が、前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とするノードとした。
【００１８】
また、請求項５に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードが、各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成するステップと、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するステップと、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得するステップと、前記次ＦＩＢ-ＩＤを付した前記パケットを受信し、当該次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次ＦＩＢ-ＩＤを取得するステップを実行し、前記ＦＩＢ-ＩＤ探索テーブルを作成するステップでの、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、全プロテクトリンク数に対し、前記第１の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第２の予備トポロジのうち、前記類似性の最も高い前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とする故障復旧方法とした。
【００１９】
このようにすることで、２番目のリンク故障が発生した場合であっても、１番目のリンク故障をプロテクトするために選択された第１の予備トポロジに基づき、２番目のリンク故障をプロテクトしつつ、１番目の故障リンクを回避するように第２の予備トポロジを選択し、パケットを転送することができる。これにより、転送ループの発生する確率を低下させることができる。
さらに、第１の予備トポロジと第２の予備トポロジの類似性を計算し、最も類似性の高い第２の予備トポロジを抽出して、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとし、ＦＩＢ-ＩＤ探索テーブルを作成することができる。これにより、１番目の故障リンクを回避するような第２の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【００２０】
請求項２に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードが、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、前記テーブル探索部が、前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とする故障復旧システムとした。
【００２１】
また、請求項４に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成する経路テーブル（ＦＩＢ）作成部と、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ−ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するＦＩＢ-ＩＤ探索テーブル作成部と、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを、前記通信部を介して受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをＦＩＢ-ＩＤ更新部に引き渡す出力ポート確認部と、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得し、当該次ＦＩＢ-ＩＤを付した前記パケットを、前記テーブル探索部に引き渡す前記ＦＩＢ-ＩＤ更新部と、を備え、前記テーブル探索部が、前記次ＦＩＢ-ＩＤが付されたパケットを受信すると、前記次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡し、前記ＦＩＢ-ＩＤ探索テーブル作成部は、前記ＦＩＢ-ＩＤ探索テーブルの作成の際に行う、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の���備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とするノードとした。
【００２２】
また、請求項６に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードが、各前記ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力ポートとを対応付けた経路テーブル（ＦＩＢ）を、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブル（ＦＩＢ）の識別子であるＦＩＢ-ＩＤに対応付けて作成するステップと、１番目の前記故障リンクをプロテクトする前記予備トポロジを示す第１の予備トポロジの現ＦＩＢ-ＩＤと、前記パケットの送信元アドレスを示すｓｒｃ-ＩＤと、前記ｄｓｔ-ＩＤとを、２番目の前記故障リンクをプロテクトする前記予備トポロジを示す第２の予備トポロジの前記ＦＩＢ-ＩＤであり、前記第１の予備トポロジに基づき選択された次ＦＩＢ-ＩＤに対応付けたＦＩＢ-ＩＤ探索テーブルを作成するステップと、前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤが付された前記パケットを受信し、前記ＦＩＢ-ＩＤをキーとして、前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記ＦＩＢ-ＩＤ、前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、前記パケットに付された前記ＦＩＢ-ＩＤを前記現ＦＩＢ-ＩＤとして、前記ＦＩＢ-ＩＤ探索テーブルを探索し、前記次ＦＩＢ-ＩＤを取得するステップと、前記次ＦＩＢ-ＩＤを付した前記パケットを受信し、当該次ＦＩＢ-ＩＤをキーとして前記経路テーブル（ＦＩＢ）を探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次ＦＩＢ-ＩＤを取得するステップを実行し、前記ＦＩＢ-ＩＤ探索テーブルを作成するステップでの、前記第１の予備トポロジに基づく前記次ＦＩＢ-ＩＤの選択において、前記パケットに付された前記ｓｒｃ-ＩＤおよび前記ｄｓｔ-ＩＤに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記１番目の前記故障リンクをプロテクトする前記第１の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第１の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記２番目の故障リンクをプロテクトする前記予備トポロジとして抽出される１つ以上の前記第２の予備トポロジについて、転送ループが発生するか否かを判定し、前記第２の予備トポロジのうち、前記転送ループの発生が最も少ない前記第２の予備トポロジを抽出し、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとして選択することを特徴とする故障復旧方法とした。
【００２３】
このようにすることで、２番目のリンク故障が発生した場合であっても、１番目のリンク故障をプロテクトするために選択された第１の予備トポロジに基づき、２番目のリンク故障をプロテクトしつつ、１番目の故障リンクを回避するように第２の予備トポロジを選択し、パケットを転送することができる。これにより、転送ループの発生する確率を低下させることができる。
さらに、１番目のリンク故障の発生箇所を推定し、推定故障リンクで故障が発生するとした場合に、２番目の故障リンクをプロテクトする第２の予備トポロジにおいて、転送ループが発生するか否かを判定し、転送ループの発生が最も少ない第２の予備トポロジを抽出して、そのＦＩＢ-ＩＤを次ＦＩＢ-ＩＤとし、ＦＩＢ-ＩＤ探索テーブルを作成することができる。これにより、１番目の故障リンクを回避するような第２の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。
【００２４】
請求項７に記載の発明は、請求項５または請求項６に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラムとした。
【００２５】
このようなプログラムによれば、請求項５または請求項６に記載の故障復旧方法を、一般的なコンピュータであるノードで実現することができる。
【発明の効果】
【００２６】
本発明によれば、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することができる。
【図面の簡単な説明】
【００２７】
【図１】ＩＰ−ＦＲＲ方式における予備トポロジを用いた故障復旧方法を説明するための図である。
【図２】予備トポロジの設計例を示す図である。
【図３】多重故障による転送ループの発生を説明するための図である。
【図４】本実施形態に係る故障復旧システムの概要を説明するための図である。
【図５】本実施形態に係る通信ネットワーク（故障復旧システム）の構成例を示す図である。
【図６】本実施形態に係るノードの構成例を示す機能ブロック図である。
【図７】本実施形態に係る記憶部に記憶される情報のデータ構成を説明するための図である。
【図８】本実施形態に係る類似判定法によるＦＩＢ-ＩＤ探索テーブルの作成処理を示すフローチャートである。
【図９】本実施形態に係る故障箇所推定法によるＦＩＢ-ＩＤ探索テーブルの作成処理を示すフローチャートである。
【図１０】本実施形態に係る故障箇所推定法の概要を説明するための図である。
【図１１】本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【図１２】本実施形態に係る通信ネットワーク（故障復旧システム）の変形例の構成を示す図である。
【発明を実施するための形態】
【００２８】
次に、本発明を実施するための形態（以下、「本実施形態」という）における故障復旧システム等について説明する。
【００２９】
≪概要≫
まず、本実施形態に係る故障復旧システムの概要について説明する。
図４は、本実施形態に係る故障復旧システムの概要を説明するための図である。
【００３０】
図４（ａ）に示すように、従来の故障復旧の方式では、１番目の故障である故障ｘのみを考慮して予備経路を決定するため、２番目の故障である故障ｙが発生すると、１番目の故障である故障ｘを再び選び、転送ループが発生する問題があった。
【００３１】
本実施形態に係る故障復旧システムでは、１番目の故障を回避するために選択された予備トポロジの情報に基づいて、２番目の故障に対して、適切な予備トポロジを選択することで、検出した故障ｘ，ｙの両方を迂回し、転送ループの発生する確率を低下させる。図４（ｂ）に示す例においては、２番目の故障である故障ｙをプロテクトする際に、予備トポロジ＃１（図２（ｂ）参照）を選択すると転送ループが発生するが、予備トポロジ＃３（図２（ｄ）参照）を選択した場合には、転送ループは発生しない。このように、２番目の故障に対して、適切な予備トポロジを選択することで、転送ループの発生する確率を低下させる。
【００３２】
この２番目の予備トポロジの選択方法として、本実施形態に係る故障復旧システムでは、（１）予備トポロジ間の類似性に基づく選択方法（類似性判定法）、または、（２）１番目の故障位置の推定結果に基づく選択方法（故障箇所推定法）という本発明に特有な処理を実行することにより、検出した故障を回避しつつ転送ループの発生しにくい予備トポロジを選択することが可能となる。この類似性判定法および故障箇所推定法については、後記し詳細に説明する。
【００３３】
≪故障復旧システム構成≫
次に、本実施形態に係る故障復旧システムとしての通信ネットワーク１０００の構成について説明する。
図５は、本実施形態に係る通信ネットワーク１０００の構成例を示す図である。
【００３４】
故障復旧システムとしての通信ネットワーク１０００は、複数のノード１と、各ノード１間を接続することにより通信経路を提供するリンクとで構成される。このノード１間には、トラヒックが発生しており、トラヒックは、ＩＰパケット単位でノード１に到着するものとする。
また、この通信ネットワーク１０００を構成する各ノード１それぞれには、後記するノード１の制御部により実現される故障回復機能が備わっている。
【００３５】
≪ノードの構成≫
続いて、本実施形態に係るノード１について説明する。
図６は、本実施形態に係るノード１の構成例を示す機能ブロック図である。
【００３６】
ノード１は、ＩＰパケット（以下単に「パケット」と呼ぶ）を転送する中継装置であり、例えば、ルータである。このノード１は、不図示の制御部と、通信部と、記憶部とを備える。
【００３７】
通信部は、入力インタフェース（Ｉ／Ｆ）３１と出力インタフェース（Ｉ／Ｆ）３２とを含んで構成され、それぞれのインタフェースには、接続先のノード１別のリンクが各ポートを介して接続され、パケットの受信および送信を実行する。
【００３８】
制御部は、通信ネットワーク１０００におけるパケットの転送処理や、パケット交換における故障復旧処理の全般を制御し、経路テーブル（ＦＩＢ：Forwarding Information Base）作成部１１と、ＦＩＢ-ＩＤ探索テーブル作成部１２と、テーブル探索部１３と、出力ポート確認部１４と、ＦＩＢ-ＩＤ更新部１５とを含んで構成される。
【００３９】
経路テーブル（ＦＩＢ）作成部１１は、後記するトポロジ情報１００に基づき転送経路の計算を行い、経路テーブル（ＦＩＢ）２００を作成する。具体的には、経路テーブル（ＦＩＢ）作成部１１は、トポロジ情報１００に記憶される、通常のトポロジと、複数の予備トポロジに基づき、通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）２１０、および複数の予備経路テーブル(Ｂａｃｋｕｐ ＦＩＢ)２２０の作成を行う。
この経路テーブル（ＦＩＢ）２００としての通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）２１０および予備経路テーブル(Ｂａｃｋｕｐ ＦＩＢ)２２０には、本故障復旧システムに固有な番号であるＦＩＢ-ＩＤが付されている。そして、各経路テーブル（ＦＩＢ）２００には、パケットの宛先アドレスを示すｄｓｔ-ＩＤと、出力インタフェース３２である出力ポートとの対応関係を示す情報が格納される。
また、この経路テーブル（ＦＩＢ）作成部１１が行う処理は、既存の予備トポロジ設計アルゴリズムにより行われる。
【００４０】
ＦＩＢ-ＩＤ探索テーブル作成部１２は、ＦＩＢ-ＩＤ探索テーブル３００を、最短経路探索法や、類似性判定法、故障箇所推定法を用いて作成する。
図７に示すように、ＦＩＢ-ＩＤ探索テーブル３００には、現時点でのパケットに付与されている経路テーブル（ＦＩＢ）２００のＩＤを示す「現ＦＩＢ-ＩＤ」、送信元アドレスを示す「ｓｒｃ-ＩＤ」、および、宛先アドレスを示す「ｄｓｔ-ＩＤ」が、次に選択すべき経路テーブル（ＦＩＢ）２００のＩＤを示す「次ＦＩＢ-ＩＤ」に対応付けられて記憶される。
このＦＩＢ-ＩＤ探索テーブル作成部１２による、ＦＩＢ-ＩＤ探索テーブル３００の作成法については、後記し詳細に説明する。
【００４１】
図６に戻り、テーブル探索部１３は、入力インタフェース（Ｉ／Ｆ）３１を介してパケットを受信し、そのパケットのヘッダに付与されたＦＩＢ−ＩＤおよび宛先アドレスを示すｄｓｔ-ＩＤを取得する。そして、テーブル探索部１３は、ＦＩＢ-ＩＤを用いて、通常の経路テーブル２１０および予備経路テーブル２２０を探索し、該当するＦＩＢ−ＩＤの経路テーブル（ＦＩＢ）２００を抽出し、ｄｓｔ-ＩＤをキーとして、出力ポートを決定する。テーブル探索部１３は、決定した出力ポートの情報を出力ポート確認部１４に引き渡す。
また、テーブル探索部１３は、ＦＩＢ-ＩＤ更新部１５から、次ＦＩＢ-ＩＤが付されたパケットを受信すると、その次ＦＩＢ-ＩＤとｄｓｔ-ＩＤとを用いて、予備経路テーブル２２０を探索し、出力ポートを決定する。そして、テーブル探索部１３は、決定した出力ポートの情報を出力ポート確認部１４に引き渡す。
【００４２】
出力ポート確認部１４は、テーブル探索部１３から受信した出力ポートが起動しているかを確認する。つまり、そのリンクを介して正常に他のノード１に送信可能か否かを確認する。
出力ポート確認部１４は、出力ポートが起動している場合には、その出力ポートへパケットを引き渡し、出力インタフェース（Ｉ／Ｆ）３２を介してパケットを送信する。一方、出力ポート確認部１４は、出力ポートが起動していない場合には、そのパケットをＦＩＢ-ＩＤ更新部１５に引き渡す。
【００４３】
ＦＩＢ-ＩＤ更新部１５は、出力ポート確認部１４から、パケットを受信すると、そのパケットのヘッダから、現ＦＩＢ-ＩＤ、ｓｒｃ-ＩＤ、ｄｓｔ-ＩＤを取得し、これらをキーとして、ＦＩＢ-ＩＤ探索テーブル３００を探索し、更新後のＦＩＢ-ＩＤである次ＦＩＢ-ＩＤを取得する。
そして、ＦＩＢ-ＩＤ更新部１５は、取得した次ＦＩＢ-ＩＤを付したパケットを、テーブル探索部１３に引き渡す。
【００４４】
また、記憶部には、トポロジ情報１００と、経路テーブル（ＦＩＢ）２００と、ＦＩＢ-ＩＤ探索テーブル３００とを含む情報が記憶される。図７は、記憶部に記憶される各情報についての、データ構成（情報要素）と、その取得・生成方法を示している。
ここで、トポロジ情報１００は、通信ネットワーク１０００内の各ノード１間のリンクによる接続関係を示し、経路テーブル（ＦＩＢ）作成部１１が、ＯＳＰＦ等のルーチングプロトコルを用いて取得する。また、このトポロジ情報１００には、経路テーブル（ＦＩＢ）作成部１１が、既存の予備トポロジ設計アルゴリズムにより生成した予備トポロジが記憶される。なお、経路テーブル（ＦＩＢ）２００およびＦＩＢ-ＩＤ探索テーブル３００については、既に説明を行っているので、ここでは説明を省略する。
【００４５】
そして、この記憶部は、ＲＡＭ（Random Access Memory）や、ＨＤＤ（Hard Dick Drive）、フラッシュメモリ等の記憶媒体から構成される。ノード１をプログラム実行処理により実現する場合、記憶部には、ノード１の制御部の機能を実現するためのプログラムが格納される。そして、制御部は、記憶部に記憶されたプログラムを、不図示のＣＰＵ（Central Processing Unit）が、ＲＡＭ等に展開し実行することで実現される。
【００４６】
≪ＦＩＢ-ＩＤ探索テーブルの作成方法≫
次に、本実施形態に係る故障復旧システムの各ノード１が、パケット転送の処理前に事前に行っておく、ＦＩＢ-ＩＤ探索テーブル３００の作成処理について説明する。
ＦＩＢ-ＩＤ探索テーブル３００は、前記したように、現時点でのパケットに付与されている経路テーブル（ＦＩＢ）２００のＩＤを示す「現ＦＩＢ-ＩＤ」、送信元アドレスを示す「ｓｒｃ-ＩＤ」、および、宛先アドレスを示す「ｄｓｔ-ＩＤ」が、次に選択すべき経路テーブル（ＦＩＢ）２００のＩＤを示す「次ＦＩＢ-ＩＤ」に対応付けられて記憶される情報である。
各ノード１のＦＩＢ-ＩＤ探索テーブル作成部１２は、ＦＩＢ-ＩＤ探索テーブル３００を、最短経路探索法、類似性判定法、故障箇所推定法を用いて作成する。
【００４７】
（最短経路探索法）
まず、１番目の故障リンクの検出時の予備トポロジを決定し、ＦＩＢ-ＩＤ探索テーブル３００を作成するために用いる、最短経路探索法について説明する。
【００４８】
最短経路探索法（Shortest Method）は、検出した故障リンクをプロテクトしつつ、予備経路の経路長が最短となる予備トポロジを選択する方法である。予備経路の経路長は、パケットのヘッダに付与された宛先ノードの情報をもとに、各予備トポロジにおいて、故障検出ノードから宛先ノードまでの経路を計算することにより算出される。
【００４９】
まず、ＦＩＢ-ＩＤ探索テーブル作成部１２は、１番目の故障リンクをプロテクトする予備経路を、故障検出ノードから宛先ノードまでの経路長が最短となる予備トポロジを探索することにより決定し、その予備トポロジにより作成された予備経路テーブル(Ｂａｃｋｕｐ ＦＩＢ)２２０のＦＩＢ-ＩＤを取得する。
そして、ＦＩＢ-ＩＤ探索テーブル作成部１２は、ＦＩＢ-ＩＤ探索テーブル３００の「現ＦＩＢ-ＩＤ」に、通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）２１０のＦＩＢ-ＩＤを格納し、「次ＦＩＢ-ＩＤ」に、経路長が最短となる予備経路テーブル（Ｂａｃｋｕｐ ＦＩＢ)２２０のＦＩＢ-ＩＤを格納して、ｓｒｃ-ＩＤ、ｄｓｔ-ＩＤを含めた、ＦＩＢ-ＩＤ探索テーブル３００を作成する。
【００５０】
次に、ＦＩＢ-ＩＤ探索テーブル作成部１２は、２番目の故障リンクの検出時に備えたＦＩＢ-ＩＤ探索テーブル３００を、類似性判定法、または、故障箇所推定法を用いて作成する。なお、２番目の故障検出時に備えたＦＩＢ-ＩＤ探索テーブル３００の作成を、最短経路探索法を用いて行ってもよいが、以下に説明する、類似性判定法、故障箇所推定法に比べると、転送ループの発生する確率を低下させる効果は低いものとなる。
【００５１】
（類似性判定法）
類似性判定法（Similarity Method）は、２番目に検出した故障リンクをプロテクトしつつ、１番目に選択した予備トポロジとの類似性が最大となる予備トポロジを、２番目の故障検出時に備えた予備トポロジとして選択する。ここで、類似性とは、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合として定義される。この類似性判定法の基本的な考え方は、類似性の高い２つの予備トポロジは、提供する経路に関しても類似性が高いと考えられるため、１番目の故障リンクをプロテクトするために選ばれた予備トポロジに類似する予備トポロジは、同様に１番目の故障リンクをプロテクトしている確率が高いとの考えに基づく。
【００５２】
この類似性判定法に基づく、２番目の故障検出時に備えたＦＩＢ-ＩＤ探索テーブル３００の作成法を、図８を参照して説明する。図８は、本実施形態に係る類似判定法によるＦＩＢ-ＩＤ探索テーブル３００の作成処理を示すフローチャートである。
【００５３】
まず、ＦＩＢ-ＩＤ探索テーブル作成部１２は、１番目の故障検出時に備えて作成されたＦＩＢ-ＩＤ探索テーブル３００内の「次ＦＩＢ-ＩＤ」を抽出する（ステップＳ１０１）。
【００５４】
次に、ＦＩＢ-ＩＤ探索テーブル作成部１２は、トポロジ情報１００に記憶されている予備トポロジ全体の中から、２番目の故障リンクをプロテクトする予備トポロジ（「第２の予備トポロジ」と呼ぶ）を抽出する（ステップＳ１０２）。
【００５５】
そして、ＦＩＢ-ＩＤ探索テーブル作成部１２は、ステップＳ１０１において「次ＦＩＢ-ＩＤ」として抽出されたＦＩＢ-ＩＤの予備トポロジ（「第１の予備トポロジ」と呼ぶ）と、ステップＳ１０２で抽出された第２の予備トポロジとの類似性を判定し、第２の予備トポロジのうち最も類似性が高い、つまり、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合が最も高い第２の予備トポロジを選択する（ステップＳ１０３）。
【００５６】
続いて、ＦＩＢ-ＩＤ探索テーブル作成部１２は、ＦＩＢ-ＩＤ探索テーブル３００の「現ＦＩＢ-ＩＤ」に、第１の予備トポロジのＦＩＢ-ＩＤを格納し、「次ＦＩＢ-ＩＤ」に、最も類似性の高い第２の予備トポロジのＦＩＢ-ＩＤを格納して、ｓｒｃ-ＩＤ、ｄｓｔ-ＩＤを含めた、ＦＩＢ-ＩＤ探索テーブル３００を作成する（ステップＳ１０４）。
【００５７】
このようにして、ＦＩＢ-ＩＤ探索テーブル作成部１２は、パケットの転送処理を実行する前に、ＦＩＢ-ＩＤ探索テーブル３００を、類似性判定法に基づき作成することができる。
【００５８】
（故障箇所推定法）
故障箇所推定法（Estimation Method）は、２番目に検出した故障リンクをプロテクトしつつ、１番目の故障リンク位置を推定することで、転送ループが最も発生しにくい予備トポロジを選択する方法である。
【００５９】
この故障箇所推定法に基づく、２番目の故障検出時に備えたＦＩＢ-ＩＤ探索テーブル３００の作成法を、図９および図１０を参照して説明する。図９は、本実施形態に係る故障箇所推定法によるＦＩＢ-ＩＤ探索テーブル３００の作成処理を示すフローチャートである。図１０は、本実施形態に係る故障箇所推定法の概要を説明するための図である。なお、図１０においては、図３および図４で示したリンク故障ｘ，ｙの例とは、別の例として説明する。
【００６０】
図９に示すように、まず、ＦＩＢ-ＩＤ探索テーブル作成部１２は、パケットのヘッダに付与される、送信元アドレスを示す「ｓｒｃ-ＩＤ」と、宛先アドレスを示す「ｄｓｔ-ＩＤ」から、故障が発生する前の最短経路を計算する。そして、その最短経路を構成するリンクの集合を「Ｅ１」として抽出する（ステップＳ２０１）。
図１０（ａ）に示す例では、最短経路「１」−「４」−「７」が計算され、そのリンク集合「Ｅ１」として、リンク１−４，４−７が抽出される。
【００６１】
次に、ＦＩＢ-ＩＤ探索テーブル作成部１２は、１番目の故障検出時に備えて作成されたＦＩＢ-ＩＤ探索テーブル３００内の「次ＦＩＢ-ＩＤ」を抽出し、「次ＦＩＢ-ＩＤ」として抽出されたＦＩＢ-ＩＤの予備トポロジ（第１の予備トポロジ）上のプロテクトリンクの集合を「Ｅ２」として抽出する（ステップＳ２０２）。
図１０（ｂ）に示す例では、予備トポロジ＃１のプロテクトリンクの集合「Ｅ２」として、リンク１−２，１−６，２−３，２−４，３−８，４−７，７−８が抽出される。
【００６２】
続いて、ＦＩＢ-ＩＤ探索テーブル作成部１２は、「Ｅ１」と「Ｅ２」の論理積をとった積集合を「Ｅ３」として抽出する（ステップＳ２０３）。この「Ｅ３」が推定故障リンクの集合となる。
図１０に示す例では、「Ｅ１」と「Ｅ２」の積集合はリンク４−７となり、故障箇所が推定される。なお、図１０の例では、故障箇所が１つ推定されるが、複数推定される場合もある。
【００６３】
そして、ＦＩＢ-ＩＤ探索テーブル作成部１２は、トポロジ情報１００に記憶されている予備トポロジ全体の中から、２番目の故障リンクをプロテクトする予備トポロジ（第２の予備トポロジ）を抽出する（ステップＳ２０４）。
【００６４】
続いて、ＦＩＢ-ＩＤ探索テーブル作成部１２は、ステップＳ２０３の推定故障リンクで故障が発生したと想定し、ステップＳ２０４で抽出した第２の予備トポロジの１つを選択した場合に、転送ループが発生するか否かを評価する（ステップＳ２０５）。
ここでは、ＦＩＢ-ＩＤ探索テーブル作成部１２は、抽出した第２の予備トポロジ毎に、転送ループが発生しない場合の評価値を「０」、転送ループが１箇所発生する場合の評価値を「１」、転送ループが２箇所発生する場合の評価値を「２」等のようにし、結果として、最も転送ループの発生に関する評価値の値が小さい第２の予備トポロジを選択する。なお、ステップＳ２０３において、推定故障リンクが複数抽出される場合があるため、転送ループが複数の箇所で発生するとの評価される場合がある。
【００６５】
次に、ＦＩＢ-ＩＤ探索テーブル作成部１２は、評価値の値が最も小さい第２の予備トポロジを選択する（ステップＳ２０６）。
【００６６】
そして、ＦＩＢ-ＩＤ探索テーブル３００の「現ＦＩＢ-ＩＤ」に、第１の予備トポロジのＦＩＢ-ＩＤを格納し、「次ＦＩＢ-ＩＤ」に、最も評価値の値が小さい第２の予備トポロジのＦＩＢ-ＩＤを格納して、ｓｒｃ-ＩＤ、ｄｓｔ-ＩＤを含めた、ＦＩＢ-ＩＤ探索テーブル３００を作成する（ステップＳ２０７）。
【００６７】
このようにして、ＦＩＢ-ＩＤ探索テーブル作成部１２は、パケットの転送処理を実行する前に、ＦＩＢ-ＩＤ探索テーブル３００を、故障箇所推定法に基づき作成することができる。
【００６８】
≪故障箇所復旧方法の全体の処理≫
次に、本実施形態に係る故障復旧システムにおける、故障復旧方法の全体の処理の流れを説明する（適宜図６参照）。
図１１は、本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。
【００６９】
まず、経路テーブル（ＦＩＢ）作成部１１は、トポロジ情報１００に基づき転送経路の計算を行い、通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）２１０、および予備経路テーブル(Ｂａｃｋｕｐ ＦＩＢ)２２０の作成を行う（ステップＳ３０１）。
【００７０】
次に、ＦＩＢ-ＩＤ探索テーブル作成部１２は、最短経路探索法と、類似性判定法、故障箇所推定法のいずれかを用いて、ＦＩＢ-ＩＤ探索テーブル３００を作成する（ステップＳ３０２）。
ＦＩＢ-ＩＤ探索テーブル作成部１２が、ＦＩＢ-ＩＤ探索テーブル３００の作成の際に、類似性判定法、故障箇所推定法のいずれを用いるかは、ネットワーク管理者等により任意に設定されるが、類似性判定法の方が、故障箇所推定法に比べ処理負荷が少ないが、故障箇所推定法の方が、類似性判定法に比べ、転送ループの発生する確率をより低下させることができるという特徴がある。
【００７１】
このステップＳ３０１とステップＳ３０２の処理は、パケット転送処理の前に各ノード１が予め計算しておく処理である。つまり、パケット転送時にリアルタイムで実行される計算ではないため、処理負荷の影響を考慮する必要はない。
【００７２】
そして、ノード１のテーブル探索部１３は、入力インタフェース（Ｉ／Ｆ）３１を介して、パケットを受信すると、パケットのヘッダに付されたＦＩＢ-ＩＤおよびｄｓｔ-ＩＤ（宛先アドレス）をキーとして、通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）２１０、および予備経路テーブル(Ｂａｃｋｕｐ ＦＩＢ)２２０を探索し、出力ポートを取得する（ステップ３０３）。
【００７３】
次に、出力ポート確認部１４は、出力ポートが起動しているか否かを確認する（ステップＳ３０４）。出力ポート確認部１４は、出力ポートが起動している場合には（ステップＳ３０４→Ｙｅｓ）、その出力ポートへパケットを引き渡し、出力インタフェース（Ｉ／Ｆ）３２を介して、パケットを送信して（ステップＳ３０５）、処理を終える。
【００７４】
一方、出力ポート確認部１４は、出力ポートが起動していない場合には（ステップＳ３０４→Ｎｏ）、次のステップＳ３０６に進む。
【００７５】
ステップＳ３０６において、出力ポート確認部１４は、そのパケットをＦＩＢ-ＩＤ更新部１５に引き渡す。
【００７６】
続いて、ＦＩＢ-ＩＤ更新部１５は、出力ポート確認部１４から、パケットを受信すると、そのパケットのヘッダ情報から、現ＦＩＢ-ＩＤ、ｓｒｃ-ＩＤ、ｄｓｔ-ＩＤを取得し、これらをキーとして、ＦＩＢ-ＩＤ探索テーブル３００を探索し、更新後のＦＩＢ-ＩＤである次ＦＩＢ-ＩＤを取得する（ステップＳ３０７）。そして、ＦＩＢ-ＩＤ更新部１５は、取得した次ＦＩＢ-ＩＤを付したパケットを、テーブル探索部１３に引き渡し、ステップＳ３０３に戻る。
【００７７】
そして、テーブル探索部１３が、ＦＩＢ-ＩＤ更新部１５から次ＦＩＢ-ＩＤが付されたパケットを受信すると、その次ＦＩＢ-ＩＤとｄｓｔ-ＩＤとを用いて、予備経路テーブル２２０を探索し、出力ポートを決定する。そして、テーブル探索部１３は、決定した出力ポートの情報を出力ポート確認部１４に引き渡し、ステップＳ３０４以降の処理を続ける。
【００７８】
以上説明したように、本実施形態に係る故障復旧システム、ノード、故障復旧方法およびプログラムによれば、パケット交換網の多重故障復旧時に発生していた転送ループについて、類似性判定法や、故障箇所推定法を用いたＦＩＢ-ＩＤ探索テーブル３００を予め作成しておき、２番目の故障に対して適切な予備トポロジを、ＦＩＢ-ＩＤ探索テーブル３００を参照して選択することで、転送ループの発生する確率を低下させることができる。
【００７９】
≪変形例≫
本実施形態に係る故障復旧システムとしての通信ネットワーク１０００は、図５に示したように、通信ネットワーク１０００内のノードそれぞれが、故障回復機能を備える構成とした。しかし、本発明はこれに限定されず、例えば、図１２に示すように、故障復旧サーバ１１００を、ネットワーク情報取得装置１２００を介して通信ネットワーク１０００に接続する構成にすることもできる。
【００８０】
この場合、故障復旧サーバ１１００が、経路テーブル（ＦＩＢ）作成部１１とＦＩＢ-ＩＤ探索テーブル作成部１２とを備え、ネットワーク情報取得装置１２００を介して、各ノード間のトポロジ情報１００を取得する。そして、故障復旧サーバ１１００が、経路テーブル（ＦＩＢ）２００およびＦＩＢ-ＩＤ探索テーブル３００を作成し、各ノード１ａに対して、パケット転送処理の開始前に配信するようにしてもよい。
【符号の説明】
【００８１】
１      ノード
１１    経路テーブル（ＦＩＢ）作成部
１２    ＦＩＢ-ＩＤ探索テーブル作成部
１３    テーブル探索部
１４    出力ポート確認部
１５    ＦＩＢ-ＩＤ更新部
３１    入力インタフェース（Ｉ／Ｆ）
３２    出力インタフェース（Ｉ／Ｆ）
１００  トポロジ情報
２００  経路テーブル（ＦＩＢ）
２１０  通常の経路テーブル（Ｐｒｉｍａｒｙ ＦＩＢ）
２２０  予備経路テーブル（Ｂａｃｋｕｐ ＦＩＢ）
３００  ＦＩＢ-ＩＤ探索テーブル
１０００  通信ネットワーク
１１００  故障復旧サーバ
１２００  ネットワーク情報取得装置
【図１】
0005697211.tif 000002
【図２】
0005697211.tif 000003
【図３】
0005697211.tif 000004
【図４】
0005697211.tif 000005
【図５】
0005697211.tif 000006
【図６】
0005697211.tif 000007
【図７】
0005697211.tif 000008
【図８】
0005697211.tif 000009
【図９】
0005697211.tif 000010
【図１０】
0005697211.tif 000011
【図１１】
0005697211.tif 000012
【図１２】
0005697211.tif 000013