"複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードは、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成する経路テーブルFIB作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するFIBID探索テーブル作成部と、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを、前記通信部を介して受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIBID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得し、当該次FIBIDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIBID更新部と、を備え、前記テーブル探索部は、前記次FIBIDが付されたパケットを受信すると、前記次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とする故障復旧システム。前記FIBID探索テーブル作成部は、前記FIBID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIBIDの選択において、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIBIDを次FIBIDとして選択することを特徴とする請求項1に記載の故障復旧システム。前記FIBID探索テーブル作成部は、前記FIBID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIBIDの選択において、前記パケットに付された前記srcIDおよび前記dstIDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIBIDを次FIBIDとして選択することを特徴とする請求項1に記載の故障復旧システム。複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成する経路テーブルFIB作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するFIBID探索テーブル作成部と、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを、前記通信部を介して受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIBID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得し、当該次FIBIDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIBID更新部と、を備え、前記テーブル探索部は、前記次FIBIDが付されたパケットを受信すると、前記次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とするノード。複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードは、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成するステップと、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するステップと、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得するステップと、前記次FIBIDを付した前記パケットを受信し、当該次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIBIDを取得するステップを実行することを特徴とする故障復旧方法。請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラム。しかしながら、既存の方式は、単一のリンクやノードの故障に対しては安定的に動作するが、多重故障の発生によって転送ループが発生する問題がある。なお、パケット交換網上の転送ループは、該当パケットがロスするだけでなく、ループするパケットによる帯域消費が、他のパケット通信に悪影響を与える可能性があるため、極力避ける必要がある。転送ループ発生の具体例を、図3を参照して説明する。ノードiからノードdstに向けてパケットを転送する際に、図3aに示すリンク故障x,yが発生する場合を考える。故障xを検出したノードiは、予備トポロジ2を選択し、予備トポロジ2に従った予備経路1-2-3-8-7-6に沿った転送を試みる図3b参照。一方で、予備経路上には2つ目の故障である故障yが存在するため、故障yを検出したノードjは、故障yをプロテクトする予備トポロジ1を選択する図3c参照。ここで、予備トポロジ1に従った予備経路2-1-6は、再度リンク故障xを含む経路となる。結果として、この例ではノードiとノードjとの間で、転送ループが発生する。この問題は、既存技術では、故障検出ノード以外のノードには、予備トポロジのIDのみが伝搬されるため、故障箇所の特定ができないことに起因する。例えば、二重故障の場合、2番目の故障を検出したノードは、2番目の故障を回避する予備トポロジを選択することは可能であるが、1番目の故障の故障箇所が既知ではないため、再度1番目の故障を含む予備トポロジを選択する可能性があり、このような場合には、転送ループが発生する。このような背景に鑑みて本発明がなされたのであり、本発明は、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することを課題とする。前記した課題を解決するため、請求項1に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムであって、前記故障復旧システムの各ノードが、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成する経路テーブルFIB作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するFIBID探索テーブル作成部と、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを、前記通信部を介して受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIBID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得し、当該次FIBIDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIBID更新部と、を備え、前記テーブル探索部が、前記次FIBIDが付されたパケットを受信すると、前記次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とする故障復旧システムとした。また、請求項4に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの前記ノードであって、パケットを送受信する通信部と、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部と、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成する経路テーブルFIB作成部と、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するFIBID探索テーブル作成部と、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを、前記通信部を介して受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するテーブル探索部と、前記出力ポートが起動しているか否かを判定し、前記起動していると判定した場合には、当該出力ポートから前記パケットを送信し、前記起動してないと判定した場合には、前記パケットをFIBID更新部に引き渡す出力ポート確認部と、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得し、当該次FIBIDを付した前記パケットを、前記テーブル探索部に引き渡す前記FIBID更新部と、を備え、前記テーブル探索部が、前記次FIBIDが付されたパケットを受信すると、前記次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、前記出力ポート確認部に引き渡すことを特徴とするノードとした。また、請求項5に記載の発明は、複数のノードをリンクにより接続することで構成されるパケット交換網において、故障発生時に、予備経路に切り替えることで故障復旧を行う故障復旧システムの故障復旧方法であって、前記故障復旧システムのノードが、前記各ノード間の接続関係を示すトポロジ情報が記憶される記憶部を備えており、前記トポロジ情報に基づき、前記パケットの宛先アドレスを示すdstIDと、出力ポートとを対応付けた経路テーブルFIBを、リンク故障が発生していない通常のトポロジと、前記リンク故障が発生した故障リンクをプロテクトする複数の予備トポロジとについて、前記故障復旧システムに固有な前記経路テーブルFIBの識別子であるFIBIDに対応付けて作成するステップと、1番目の前記故障リンクをプロテクトする前記予備トポロジを示す第1の予備トポロジの現FIB-IDと、前記パケットの送信元アドレスを示すsrcIDと、前記dstIDとを、2番目の前記故障リンクをプロテクトする前記予備トポロジを示す第2の予備トポロジの前記FIBIDであり、前記第1の予備トポロジに基づき選択された次FIBIDに対応付けたFIBID探索テーブルを作成するステップと、前記FIBID、前記srcIDおよび前記dstIDが付された前記パケットを受信し、前記FIBIDをキーとして、前記経路テーブルFIBを探索し、前記出力ポートを取得するステップと、前記出力ポートが起動しているか否かを判定し、前記出力ポートが起動していると判定した場合に、当該出力ポートから前記パケットを送信するステップと、前記出力ポートが起動してないと判定した場合に、前記パケットに付された前記FIBID、前記srcIDおよび前記dstIDに基づき、前記パケットに付された前記FIBIDを前記現FIBIDとして、前記FIBID探索テーブルを探索し、前記次FIBIDを取得するステップと、前記次FIBIDを付した前記パケットを受信し、当該次FIBIDをキーとして前記経路テーブルFIBを探索し、前記出力ポートを取得して、当該取得した出力ポートが起動しているか否かを判定して、前記パケットの送信するステップ、または、前記次FIBIDを取得するステップを実行することを特徴とする故障復旧方法とした。このようにすることで、2番目のリンク故障が発生した場合であっても、1番目のリンク故障をプロテクトするために選択された第1の予備トポロジに基づき、2番目のリンク故障をプロテクトしつつ、1番目の故障リンクを回避するように第2の予備トポロジを選択し、パケットを転送することができる。これにより、転送ループの発生する確率を低下させることができる。請求項2に記載の発明は、前記FIBID探索テーブル作成部が、前記FIBID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIBIDの選択において、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、全プロテクトリンク数に対し、前記第1の予備トポロジがプロテクトしているリンクと同一のリンクをプロテクトしている数の割合を示す類似性を計算し、前記第2の予備トポロジのうち、前記類似性の最も高い前記第2の予備トポロジを抽出し、そのFIBIDを次FIBIDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。このようにすることで、FIBID探索テーブル作成部は、第1の予備トポロジと第2の予備トポロジの類似性を計算し、最も類似性の高い第2の予備トポロジを抽出して、そのFIBIDを次FIBIDとし、FIBID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。請求項3に記載の発明は、前記FIBID探索テーブル作成部は、前記FIBID探索テーブルの作成の際に行う、前記第1の予備トポロジに基づく前記次FIBIDの選択において、前記パケットに付された前記srcIDおよび前記dstIDに基づき、故障発生前の最短経路を計算し、その最短経路上のリンクを抽出し、前記1番目の前記故障リンクをプロテクトする前記第1の予備トポロジのプロテクトリンクを抽出し、前記最短経路上のリンクと前記第1の予備トポロジのプロテクトリンクとに重複するリンクを、推定故障リンクとして抽出し、前記抽出した推定故障リンクと、前記2番目の故障リンクをプロテクトする前記予備トポロジとして抽出される1つ以上の前記第2の予備トポロジについて、転送ループが発生するか否かを判定し、前記第2の予備トポロジのうち、前記転送ループの発生が最も少ない前記第2の予備トポロジを抽出し、そのFIBIDを次FIBIDとして選択することを特徴とする請求項1に記載の故障復旧システムとした。このようにすることで、FIBID探索テーブル作成部は、1番目のリンク故障の発生箇所を推定し、推定故障リンクで故障が発生するとした場合に、2番目の故障リンクをプロテクトする第2の予備トポロジにおいて、転送ループが発生するか否かを判定し、転送ループの発生が最も少ない第2の予備トポロジを抽出して、そのFIBIDを次FIBIDとし、FIBID探索テーブルを作成することができる。これにより、1番目の故障リンクを回避するような第2の予備トポロジが選択され、転送ループの発生する確率を低下させることができる。請求項6に記載の発明は、請求項5に記載の故障復旧方法を、コンピュータである前記ノードに実行させるためのプログラムとした。このようなプログラムによれば、請求項5に記載の故障復旧方法を、一般的なコンピュータであるノードで実現することができる。本発明によれば、パケット交換網における多重故障復旧時に、転送ループの発生する確率を低下させることができる、故障復旧システム、ノード、故障復旧方法およびプログラムを提供することができる。次に、本発明を実施するための形態以下、本実施形態というにおける故障復旧システム等について説明する。≪概要≫まず、本実施形態に係る故障復旧システムの概要について説明する。図4は、本実施形態に係る故障復旧システムの概要を説明するための図である。図4aに示すように、従来の故障復旧の方式では、1番目の故障である故障xのみを考慮して予備経路を決定するため、2番目の故障である故障yが発生すると、1番目の故障である故障xを再び選び、転送ループが発生する問題があった。本実施形態に係る故障復旧システムでは、1番目の故障を回避するために選択された予備トポロジの情報に基づいて、2番目の故障に対して、適切な予備トポロジを選択することで、検出した故障x,yの両方を迂回し、転送ループの発生する確率を低下させる。図4bに示す例においては、2番目の故障である故障yをプロテクトする際に、予備トポロジ1図2b参照を選択すると転送ループが発生するが、予備トポロジ3図2d参照を選択した場合には、転送ループは発生しない。このように、2番目の故障に対して、適切な予備トポロジを選択することで、転送ループの発生する確率を低下させる。この2番目の予備トポロジの選択方法として、本実施形態に係る故障復旧システムでは、1予備トポロジ間の類似性に基づく選択方法類似性判定法、または、21番目の故障位置の推定結果に基づく選択方法故障箇所推定法という本発明に特有な処理を実行することにより、検出した故障を回避しつつ転送ループの発生しにくい予備トポロジを選択することが可能となる。この類似性判定法および故障箇所推定法については、後記し詳細に説明する。≪故障復旧システム構成≫次に、本実施形態に係る故障復旧システムとしての通信ネットワーク1000の構成について説明する。図5は、本実施形態に係る通信ネットワーク1000の構成例を示す図である。故障復旧システムとしての通信ネットワーク1000は、複数のノード1と、各ノード1間を接続することにより通信経路を提供するリンクとで構成される。このノード1間には、トラヒックが発生しており、トラヒックは、IPパケット単位でノード1に到着するものとする。また、この通信ネットワーク1000を構成する各ノード1それぞれには、後記するノード1の制御部により実現される故障回復機能が備わっている。≪ノードの構成≫続いて、本実施形態に係るノード1について説明する。図6は、本実施形態に係るノード1の構成例を示す機能ブロック図である。ノード1は、IPパケット以下単にパケットと呼ぶを転送する中継装置であり、例えば、ルータである。このノード1は、不図示の制御部と、通信部と、記憶部とを備える。通信部は、入力インタフェースI/F31と出力インタフェースI/F32とを含んで構成され、それぞれのインタフェースには、接続先のノード1別のリンクが各ポートを介して接続され、パケットの受信および送信を実行する。制御部は、通信ネットワーク1000におけるパケットの転送処理や、パケット交換における故障復旧処理の全般を制御し、経路テーブルFIB:ForwardingInformationBase作成部11と、FIBID探索テーブル作成部12と、テーブル探索部13と、出力ポート確認部14と、FIBID更新部15とを含んで構成される。経路テーブルFIB作成部11は、後記するトポロジ情報100に基づき転送経路の計算を行い、経路テーブルFIB200を作成する。具体的には、経路テーブルFIB作成部11は、トポロジ情報100に記憶される、通常のトポロジと、複数の予備トポロジに基づき、通常の経路テーブルPrimaryFIB210、および複数の予備経路テーブル220の作成を行う。この経路テーブルFIB200としての通常の経路テーブルPrimaryFIB210および予備経路テーブル220には、本故障復旧システムに固有な番号であるFIBIDが付されている。そして、各経路テーブルFIB200には、パケットの宛先アドレスを示すdstIDと、出力インタフェース32である出力ポートとの対応関係を示す情報が格納される。また、この経路テーブルFIB作成部11が行う処理は、既存の予備トポロジ設計アルゴリズムにより行われる。FIBID探索テーブル作成部12は、FIBID探索テーブル300を、最短経路探索法や、類似性判定法、故障箇所推定法を用いて作成する。図7に示すように、FIBID探索テーブル300には、現時点でのパケットに付与されている経路テーブルFIB200のIDを示す現FIBID、送信元アドレスを示すsrcID、および、宛先アドレスを示すdstIDが、次に選択すべき経路テーブルFIB200のIDを示す次FIBIDに対応付けられて記憶される。このFIBID探索テーブル作成部12による、FIBID探索テーブル300の作成法については、後記し詳細に説明する。図6に戻り、テーブル探索部13は、入力インタフェースI/F31を介してパケットを受信し、そのパケットのヘッダに付与されたFIB-IDおよび宛先アドレスを示すdstIDを取得する。そして、テーブル探索部13は、FIBIDを用いて、通常の経路テーブル210および予備経路テーブル220を探索し、該当するFIB-IDの経路テーブルFIB200を抽出し、dstIDをキーとして、出力ポートを決定する。テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。また、テーブル探索部13は、FIBID更新部15から、次FIBIDが付されたパケットを受信すると、その次FIBIDとdstIDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡す。出力ポート確認部14は、テーブル探索部13から受信した出力ポートが起動しているかを確認する。つまり、そのリンクを介して正常に他のノード1に送信可能か否かを確認する。出力ポート確認部14は、出力ポートが起動している場合には、その出力ポートへパケットを引き渡し、出力インタフェースI/F32を介してパケットを送信する。一方、出力ポート確認部14は、出力ポートが起動していない場合には、そのパケットをFIBID更新部15に引き渡す。FIBID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダから、現FIBID、srcID、dstIDを取得し、これらをキーとして、FIBID探索テーブル300を探索し、更新後のFIBIDである次FIBIDを取得する。そして、FIBID更新部15は、取得した次FIBIDを付したパケットを、テーブル探索部13に引き渡す。また、記憶部には、トポロジ情報100と、経路テーブルFIB200と、FIBID探索テーブル300とを含む情報が記憶される。図7は、記憶部に記憶される各情報についての、データ構成情報要素と、その取得生成方法を示している。ここで、トポロジ情報100は、通信ネットワーク1000内の各ノード1間のリンクによる接続関係を示し、経路テーブルFIB作成部11が、OSPF等のルーチングプロトコルを用いて取得する。また、このトポロジ情報100には、経路テーブルFIB作成部11が、既存の予備トポロジ設計アルゴリズムにより生成した予備トポロジが記憶される。なお、経路テーブルFIB200およびFIBID探索テーブル300については、既に説明を行っているので、ここでは説明を省略する。そして、この記憶部は、RAMRandomAccessMemoryや、HDDHardDickDrive、フラッシュメモリ等の記憶媒体から構成される。ノード1をプログラム実行処理により実現する場合、記憶部には、ノード1の制御部の機能を実現するためのプログラムが格納される。そして、制御部は、記憶部に記憶されたプログラムを、不図示のCPUCentralProcessingUnitが、RAM等に展開し実行することで実現される。≪FIBID探索テーブルの作成方法≫次に、本実施形態に係る故障復旧システムの各ノード1が、パケット転送の処理前に事前に行っておく、FIBID探索テーブル300の作成処理について説明する。FIBID探索テーブル300は、前記したように、現時点でのパケットに付与されている経路テーブルFIB200のIDを示す現FIBID、送信元アドレスを示すsrcID、および、宛先アドレスを示すdstIDが、次に選択すべき経路テーブルFIB200のIDを示す次FIBIDに対応付けられて記憶される情報である。各ノード1のFIBID探索テーブル作成部12は、FIBID探索テーブル300を、最短経路探索法、類似性判定法、故障箇所推定法を用いて作成する。最短経路探索法まず、1番目の故障リンクの検出時の予備トポロジを決定し、FIBID探索テーブル300を作成するために用いる、最短経路探索法について説明する。最短経路探索法ShortestMethodは、検出した故障リンクをプロテクトしつつ、予備経路の経路長が最短となる予備トポロジを選択する方法である。予備経路の経路長は、パケットのヘッダに付与された宛先ノードの情報をもとに、各予備トポロジにおいて、故障検出ノードから宛先ノードまでの経路を計算することにより算出される。まず、FIBID探索テーブル作成部12は、1番目の故障リンクをプロテクトする予備経路を、故障検出ノードから宛先ノードまでの経路長が最短となる予備トポロジを探索することにより決定し、その予備トポロジにより作成された予備経路テーブル220のFIBIDを取得する。そして、FIBID探索テーブル作成部12は、FIBID探索テーブル300の現FIBIDに、通常の経路テーブルPrimaryFIB210のFIBIDを格納し、次FIBIDに、経路長が最短となる予備経路テーブルBackupFIB220のFIBIDを格納して、srcID、dstIDを含めた、FIBID探索テーブル300を作成する。次に、FIBID探索テーブル作成部12は、2番目の故障リンクの検出時に備えたFIBID探索テーブル300を、類似性判定法、または、故障箇所推定法を用いて作成する。なお、2番目の故障検出時に備えたFIBID探索テーブル300の作成を、最短経路探索法を用いて行ってもよいが、以下に説明する、類似性判定法、故障箇所推定法に比べると、転送ループの発生する確率を低下させる効果は低いものとなる。類似性判定法類似性判定法SimilarityMethodは、2番目に検出した故障リンクをプロテクトしつつ、1番目に選択した予備トポロジとの類似性が最大となる予備トポロジを、2番目の故障検出時に備えた予備トポロジとして選択する。ここで、類似性とは、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合として定義される。この類似性判定法の基本的な考え方は、類似性の高い2つの予備トポロジは、提供する経路に関しても類似性が高いと考えられるため、1番目の故障リンクをプロテクトするために選ばれた予備トポロジに類似する予備トポロジは、同様に1番目の故障リンクをプロテクトしている確率が高いとの考えに基づく。この類似性判定法に基づく、2番目の故障検出時に備えたFIBID探索テーブル300の作成法を、図8を参照して説明する。図8は、本実施形態に係る類似判定法によるFIBID探索テーブル300の作成処理を示すフローチャートである。まず、FIBID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIBID探索テーブル300内の次FIBIDを抽出するステップS101。次に、FIBID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ第2の予備トポロジと呼ぶを抽出するステップS102。そして、FIBID探索テーブル作成部12は、ステップS101において次FIBIDとして抽出されたFIBIDの予備トポロジ第1の予備トポロジと呼ぶと、ステップS102で抽出された第2の予備トポロジとの類似性を判定し、第2の予備トポロジのうち最も類似性が高い、つまり、全プロテクトリンク数に対し、同一のリンクをプロテクトしている数の割合が最も高い第2の予備トポロジを選択するステップS103。続いて、FIBID探索テーブル作成部12は、FIBID探索テーブル300の現FIBIDに、第1の予備トポロジのFIBIDを格納し、次FIBIDに、最も類似性の高い第2の予備トポロジのFIBIDを格納して、srcID、dstIDを含めた、FIBID探索テーブル300を作成するステップS104。このようにして、FIBID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIBID探索テーブル300を、類似性判定法に基づき作成することができる。故障箇所推定法故障箇所推定法EstimationMethodは、2番目に検出した故障リンクをプロテクトしつつ、1番目の故障リンク位置を推定することで、転送ループが最も発生しにくい予備トポロジを選択する方法である。この故障箇所推定法に基づく、2番目の故障検出時に備えたFIBID探索テーブル300の作成法を、図9および図10を参照して説明する。図9は、本実施形態に係る故障箇所推定法によるFIBID探索テーブル300の作成処理を示すフローチャートである。図10は、本実施形態に係る故障箇所推定法の概要を説明するための図である。なお、図10においては、図3および図4で示したリンク故障x,yの例とは、別の例として説明する。図9に示すように、まず、FIBID探索テーブル作成部12は、パケットのヘッダに付与される、送信元アドレスを示すsrcIDと、宛先アドレスを示すdstIDから、故障が発生する前の最短経路を計算する。そして、その最短経路を構成するリンクの集合をE1として抽出するステップS201。図10aに示す例では、最短経路1-4-7が計算され、そのリンク集合E1として、リンク1-4,4-7が抽出される。次に、FIBID探索テーブル作成部12は、1番目の故障検出時に備えて作成されたFIBID探索テーブル300内の次FIBIDを抽出し、次FIBIDとして抽出されたFIBIDの予備トポロジ第1の予備トポロジ上のプロテクトリンクの集合をE2として抽出するステップS202。図10bに示す例では、予備トポロジ1のプロテクトリンクの集合E2として、リンク1-2,1-6,2-3,2-4,3-8,4-7,7-8が抽出される。続いて、FIBID探索テーブル作成部12は、E1とE2の論理積をとった積集合をE3として抽出するステップS203。このE3が推定故障リンクの集合となる。図10に示す例では、E1とE2の積集合はリンク4-7となり、故障箇所が推定される。なお、図10の例では、故障箇所が1つ推定されるが、複数推定される場合もある。そして、FIBID探索テーブル作成部12は、トポロジ情報100に記憶されている予備トポロジ全体の中から、2番目の故障リンクをプロテクトする予備トポロジ第2の予備トポロジを抽出するステップS204。続いて、FIBID探索テーブル作成部12は、ステップS203の推定故障リンクで故障が発生したと想定し、ステップS204で抽出した第2の予備トポロジの1つを選択した場合に、転送ループが発生するか否かを評価するステップS205。ここでは、FIBID探索テーブル作成部12は、抽出した第2の予備トポロジ毎に、転送ループが発生しない場合の評価値を0、転送ループが1箇所発生する場合の評価値を1、転送ループが2箇所発生する場合の評価値を2等のようにし、結果として、最も転送ループの発生に関する評価値の値が小さい第2の予備トポロジを選択する。なお、ステップS203において、推定故障リンクが複数抽出される場合があるため、転送ループが複数の箇所で発生するとの評価される場合がある。次に、FIBID探索テーブル作成部12は、評価値の値が最も小さい第2の予備トポロジを選択するステップS206。そして、FIBID探索テーブル300の現FIBIDに、第1の予備トポロジのFIBIDを格納し、次FIBIDに、最も評価値の値が小さい第2の予備トポロジのFIBIDを格納して、srcID、dstIDを含めた、FIBID探索テーブル300を作成するステップS207。このようにして、FIBID探索テーブル作成部12は、パケットの転送処理を実行する前に、FIBID探索テーブル300を、故障箇所推定法に基づき作成することができる。≪故障箇所復旧方法の全体の処理≫次に、本実施形態に係る故障復旧システムにおける、故障復旧方法の全体の処理の流れを説明する適宜図6参照。図11は、本実施形態に係る故障復旧方法の全体の処理の流れを示すフローチャートである。まず、経路テーブルFIB作成部11は、トポロジ情報100に基づき転送経路の計算を行い、通常の経路テーブルPrimaryFIB210、および予備経路テーブル220の作成を行うステップS301。次に、FIBID探索テーブル作成部12は、最短経路探索法と、類似性判定法、故障箇所推定法のいずれかを用いて、FIBID探索テーブル300を作成するステップS302。FIBID探索テーブル作成部12が、FIBID探索テーブル300の作成の際に、類似性判定法、故障箇所推定法のいずれを用いるかは、ネットワーク管理者等により任意に設定されるが、類似性判定法の方が、故障箇所推定法に比べ処理負荷が少ないが、故障箇所推定法の方が、類似性判定法に比べ、転送ループの発生する確率をより低下させることができるという特徴がある。このステップS301とステップS302の処理は、パケット転送処理の前に各ノード1が予め計算しておく処理である。つまり、パケット転送時にリアルタイムで実行される計算ではないため、処理負荷の影響を考慮する必要はない。そして、ノード1のテーブル探索部13は、入力インタフェースI/F31を介して、パケットを受信すると、パケットのヘッダに付されたFIBIDおよびdstID宛先アドレスをキーとして、通常の経路テーブルPrimaryFIB210、および予備経路テーブル220を探索し、出力ポートを取得するステップ303。次に、出力ポート確認部14は、出力ポートが起動しているか否かを確認するステップS304。出力ポート確認部14は、出力ポートが起動している場合にはステップS304→Yes、その出力ポートへパケットを引き渡し、出力インタフェースI/F32を介して、パケットを送信してステップS305、処理を終える。一方、出力ポート確認部14は、出力ポートが起動していない場合にはステップS304→No、次のステップS306に進む。ステップS306において、出力ポート確認部14は、そのパケットをFIBID更新部15に引き渡す。続いて、FIBID更新部15は、出力ポート確認部14から、パケットを受信すると、そのパケットのヘッダ情報から、現FIBID、srcID、dstIDを取得し、これらをキーとして、FIBID探索テーブル300を探索し、更新後のFIBIDである次FIBIDを取得するステップS307。そして、FIBID更新部15は、取得した次FIBIDを付したパケットを、テーブル探索部13に引き渡し、ステップS303に戻る。そして、テーブル探索部13が、FIBID更新部15から次FIBIDが付されたパケットを受信すると、その次FIBIDとdstIDとを用いて、予備経路テーブル220を探索し、出力ポートを決定する。そして、テーブル探索部13は、決定した出力ポートの情報を出力ポート確認部14に引き渡し、ステップS304以降の処理を続ける。以上説明したように、本実施形態に係る故障復旧システム、ノード、故障復旧方法およびプログラムによれば、パケット交換網の多重故障復旧時に発生していた転送ループについて、類似性判定法や、故障箇所推定法を用いたFIBID探索テーブル300を予め作成しておき、2番目の故障に対して適切な予備トポロジを、FIBID探索テーブル300を参照して選択することで、転送ループの発生する確率を低下させることができる。≪変形例≫本実施形態に係る故障復旧システムとしての通信ネットワーク1000は、図5に示したように、通信ネットワーク1000内のノードそれぞれが、故障回復機能を備える構成とした。しかし、本発明はこれに限定されず、例えば、図12に示すように、故障復旧サーバ1100を、ネットワーク情報取得装置1200を介して通信ネットワーク1000に接続する構成にすることもできる。この場合、故障復旧サーバ1100が、経路テーブルFIB作成部11とFIBID探索テーブル作成部12とを備え、ネットワーク情報取得装置1200を介して、各ノード間のトポロジ情報100を取得する。そして、故障復旧サーバ1100が、経路テーブルFIB200およびFIBID探索テーブル300を作成し、各ノード1aに対して、パケット転送処理の開始前に配信するようにしてもよい。"