(57)【特許請求の範囲】
【請求項１】
複数のノードが物理リンクで接続される通信ネットワーク上に論理パスを形成して通信を行う通信システムの複数箇所で障害が発生した場合に、全論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、各論理パスのトラヒック流量が所望値になるように、故障リンクの最適な復旧順序を計算する復旧順序決定方法であって、
故障リンク数が予め設定された閾値よりも多い場合に複数のグループに分割してグループ間の復旧順序を計算する処理を階層的に行い、グループ内の故障リンク数が予め設定された閾値以下になった場合にグループ内の故障リンク間の復旧順序を計算し、
故障リンクを最大グループ数Ｋ（Ｋは正の整数）以下に階層的に分割する場合に、階層番号ｉ（ｉは正の整数）におけるグループ数Ｋｉ（Ｋｉは正の整数）と各グループの故障リンク数Ｌｉ（Ｌｉは正の整数）とが以下の条件を満たすように複数の前記グループを生成し、
Ｋｉ≦Ｋ  ａｎｄ  Ｋｉ＊Ｌｉ  ≧  Ｌｉ−１
復旧の工程数ｐｈ（ｐｈは正の整数）の各工程当たりの最大リンク復旧数ｍ（ｍは正の整数）として、生成した複数の前記グループ間の復旧順序を線形計画法により以下の条件を満たすように計算する
ｐｈ≦Ｋｉ  ａｎｄ  ｍ  ＝  Ｌｉ＊２
ことを特徴とする復旧順序決定方法。
【請求項２】
請求項１に記載の復旧順序決定方法において、
前記階層毎に生成する複数の前記グループは、それぞれ同数の故障リンクを有することを特徴とする復旧順序決定方法。
【請求項３】
請求項１に記載の復旧順序決定方法において、
前記階層毎に生成する複数の前記グループは、少なくとも２つの前記グループで異なる数の故障リンクを有することを特徴とする復旧順序決定方法。
【請求項４】
複数のノードが物理リンクで接続される通信ネットワーク上に論理パスを形成して通信を行う通信システムの複数箇所で障害が発生した場合に、全論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、各論理パスのトラヒック流量が所望値になるように、故障リンクの最適な復旧順序を計算する処理をコンピュータで実行する復旧順序決定プログラムであって、
故障リンク数を予め設定された閾値と比較する第１ステップと、
故障リンク数が予め設定された閾値よりも多い場合に複数のグループに分割する第２ステップと、
分割された複数のグループ間の復旧順序を計算する処理を行う第３ステップと、
前記第１ステップから前記第３ステップまでの処理を階層的に繰り返し実行し、分割されたグループ内の故障リンク数が予め設定された閾値以下になった場合にグループ内の故障リンク間の復旧順序を計算する第４ステップと
をコンピュータに実行させ、
前記第２ステップでは、故障リンクを最大グループ数Ｋ（Ｋは正の整数）以下に階層的に分割する場合に、階層番号ｉ（ｉは正の整数）におけるグループ数Ｋｉ（Ｋｉは正の整数）と各グループの故障リンク数Ｌｉ（Ｌｉは正の整数）とが以下の条件を満たすように複数の前記グループを生成し、
Ｋｉ≦Ｋ  ａｎｄ  Ｋｉ＊Ｌｉ  ≧  Ｌｉ−１
前記第３ステップでは、復旧の工程数ｐｈ（ｐｈは正の整数）の各工程当たりの最大リンク復旧数ｍ（ｍは正の整数）として、生成した複数の前記グループ間の復旧順序を線形計画法により以下の条件を満たすように計算する
ｐｈ≦Ｋｉ  ａｎｄ  ｍ  ＝  Ｌｉ＊２
ことを特徴とする復旧順序決定プログラム。
【請求項５】
請求項４に記載の復旧順序決定プログラムにおいて、
前記階層毎に生成する複数の前記グループは、それぞれ同数の故障リンクを有することを特徴とする復旧順序決定プログラム。
【請求項６】
請求項４に記載の復旧順序決定プログラムにおいて、
前記階層毎に生成する複数の前記グループは、少なくとも２つの前記グループで異なる数の故障リンクを有することを特徴とする復旧順序決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広域ネットワークで大規模な故障が発生した場合に故障リンクの復旧順序を決定する技術に関する。
【背景技術】
【０００２】
ネットワーク事業者は、激甚災害等の大規模な故障発生時においても、障害のある伝送装置や伝送路の復旧を速やかに実施することが重要であり、信頼性の高いネットワークを提供することが求められている。例えば、通信事業者の独自のネットワークであるキャリア網では、物理的な光インフラ網上に波長などによる論理パスを設定して、論理パスによって上位レイヤのネットワーク（ＩＰ(Internet Protocol)等）で転送ノード間を接続する論理リンクを提供し、ユーザトラヒックの転送路を構成する。また、ビル倒壊等も含む激甚災害を想定した場合、物理的な資源の復旧は一斉に行われるのではなく、数週間から数ヶ月のスパンで複数の復旧ステージを遷移して段階的に行われることが想定される。
【０００３】
上述の段階的な復旧が行われるネットワークを前提とした場合に、中間の復旧ステージの疎通トラヒック量も含めてトラヒック流量を最大化する復旧順序の最適化計算方法が考案されている（例えば、非特許文献１参照）。非特許文献１では、中間の復旧ステージを含むすべての復旧ステージのトラヒック流量の総和を最大化する復旧順序を求める問題を線形計画問題として定式化することで、厳密な最適解を算出する。しかし、非特許文献１は、全論理パスのトラヒック流量の総和に着目しているため、論理パスそれぞれのトラヒック流量は明示的に考慮されていない。このため、一部の優先度の高い論理パスにトラヒック流量が偏り、他の論理パスにはトラヒック流量が全く割り当てられない可能性があり、それぞれの論理パスに一定のトラヒック流量を確保することは難しい。
【０００４】
そこで、それぞれの論理パスのトラヒック流量を線形計画問題の目的関数や制約条件として明示することにより、それぞれの論理パスに一定のトラヒック流量を確保する制御を実現できる（例えば、非特許文献２参照）。非特許文献２では、論理パス間のトラヒック流量の差分を極力小さくする変数を目的関数として組み込むことで、中間の復旧ステージにおける全ての論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、中間の復旧ステージにおける論理パス間のトラヒック流量差の総和を最小化する復旧順序を求める問題を線形計画問題として定式化している。
【０００５】
ここで、線形計画問題は、制約式（いくつかの１次式を満たす変数の値）の中で、１次関数で与えられる目的関数を最大化（又は最小化）する値を求める線形計画法により解くことができる。下式は目的関数の一例であり、変数Ｆplは工程ｌにおける論理パスｐのフロー量である。なお、工程は、段階的に行われる復旧ステージに対応する。
【数１】
0006367150.tif 000002
そして、第一項は全工程を通したパスフロー間のフロー量の差分の累積値であり、この累積値を最小化することでパスフロー間の均一化を図る。第二項は全工程を通した全パスのフロー量の累積値（フロー累積値）であり、正常時の最大フロー量に相当する定数Ｍからの差分を最小化することで総フロー量の最大化を図る。ｗpはパスフローｐの重みを意味するが、ここではパスフロー間の均一性を目指すため各論理パスｐで同一値とする。λは両項の重み付けのための係数であり、λが小さいほどパスフロー間の均一性が重視され、大きくなるほど総フロー量が重視された復旧順序となる。ｐｈは、工程数であり、従来技術では工程当たり１つの故障リンクを復旧するため、故障リンク数と同一値である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】J.Wang,C.Qiao,H.Yu,“On Progressive Network Recovery After a Major Disruption,”in Infocom 2011
【非特許文献２】源田，山本，鎌村，“パスフロー公平性に着目した大規模故障からの段階的復旧順序の最適化検討”，電子情報通信学会，総合大会，2015年3月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述の線形計画法による定式化では、シンプレックス法や内点法等の古典的アルゴリズムにより多項式時間で問題を解くことが可能である。しかしながら、これらの方法は問題を解く計算時間の観点では必ずしも効率的ではなく、故障規模が大きくなると、復旧順序を求める対象数が増え、現実的な時間で計算が完了しないという課題が生じる。
【０００８】
このように、激甚災害の発生時には、物理資源の復旧は一斉に行われるのではなく、複数の復旧ステージを遷移して段階的に行われることが想定される。特にキャリア網では、中間の復旧ステージにおいても一定値以上のトラヒック流量を担保しつつ、論理パスそれぞれのトラヒック流量を制御できることが重要である。しかし、故障リンクの復旧順序の決定方法は線形計画問題としての定式化が可能であるが、大規模故障への適用を想定すると現実的な計算時間で問題を解くことができないという課題がある。
【０００９】
本発明は、激甚災害の発生時における故障リンクの復旧順序を求める計算において、全体の計算時間を短縮することができる故障リンクの復旧順序決定方法、および復旧順序決定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、複数のノードが物理リンクで接続される通信ネットワーク上に論理パスを形成して通信を行う通信システムの複数箇所で障害が発生した場合に、全論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、各論理パスのトラヒック流量が所望値になるように、故障リンクの最適な復旧順序を計算する復旧順序決定方法であって、故障リンク数が予め設定された閾値よりも多い場合に複数のグループに分割してグループ間の復旧順序を計算する処理を階層的に行い、グループ内の故障リンク数が予め設定された閾値以下になった場合にグループ内の故障リンク間の復旧順序を計算する。
【００１１】
そして、故障リンクを最大グループ数Ｋ（Ｋは正の整数）以下に階層的に分割する場合に、階層番号ｉ（ｉは正の整数）におけるグループ数Ｋｉ（Ｋｉは正の整数）と各グループの故障リンク数Ｌｉ（Ｌｉは正の整数）とが以下の条件を満たすように複数のグループを生成し、
Ｋｉ≦Ｋ  ａｎｄ  Ｋｉ＊Ｌｉ  ≧  Ｌｉ−１
復旧の工程数ｐｈ（ｐｈは正の整数）の各工程当たりの最大リンク復旧数ｍ（ｍは正の整数）として、生成した複数のグループ間の復旧順序を線形計画法により以下の条件を満たすように計算することを特徴とする。
ｐｈ≦Ｋｉ  ａｎｄ  ｍ  ＝  Ｌｉ＊２
【００１２】
第２の発明は、階層毎に生成する複数のグループは、それぞれ同数の故障リンクを有することを特徴とする。
【００１３】
第３の発明は、階層毎に生成する複数のグループは、少なくとも２つのグループで異なる数の故障リンクを有することを特徴とする。
【００１４】
第４の発明は、複数のノードが物理リンクで接続される通信ネットワーク上に論理パスを形成して通信を行う通信システムの複数箇所で障害が発生した場合に、全論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、各論理パスのトラヒック流量が所望値になるように、故障リンクの最適な復旧順序を計算する処理をコンピュータで実行する復旧順序決定プログラムであって、故障リンク数を予め設定された閾値と比較する第１ステップと、故障リンク数が予め設定された閾値よりも多い場合に複数のグループに分割する第２ステップと、分割された複数のグループ間の復旧順序を計算する処理を行う第３ステップと、第１ステップから第３ステップまでの処理を階層的に繰り返し実行し、分割されたグループ内の故障リンク数が予め設定された閾値以下になった場合にグループ内の故障リンク間の復旧順序を計算する第４ステップとをコンピュータに実行させる。
【００１５】
そして、第２ステップでは、故障リンクを最大グループ数Ｋ（Ｋは正の整数）以下に階層的に分割する場合に、階層番号ｉ（ｉは正の整数）におけるグループ数Ｋｉ（Ｋｉは正の整数）と各グループの故障リンク数Ｌｉ（Ｌｉは正の整数）とが以下の条件を満たすように複数のグループを生成し、
Ｋｉ≦Ｋ  ａｎｄ  Ｋｉ＊Ｌｉ  ≧  Ｌｉ−１
第３ステップでは、復旧の工程数ｐｈ（ｐｈは正の整数）の各工程当たりの最大リンク復旧数ｍ（ｍは正の整数）として、生成した複数のグループ間の復旧順序を線形計画法により以下の条件を満たすように計算することを特徴とする。
ｐｈ≦Ｋｉ  ａｎｄ  ｍ  ＝  Ｌｉ＊２
【００１６】
第５の発明は、階層毎に生成する複数のグループは、それぞれ同数の故障リンクを有することを特徴とする。
【００１７】
第６の発明は、階層毎に生成する複数のグループは、少なくとも２つのグループで異なる数の故障リンクを有することを特徴とする。
【発明の効果】
【００１８】
本発明に係る故障リンクの復旧順序決定方法、および復旧順序決定プログラムは、激甚災害の発生時における故障リンクの復旧順序を求める計算において、復旧対象の故障リンクをグループ化して一定数以下のグループ間の復旧順序を計算する処理を階層化して、複数回に分けて復旧順序の計算を行うことにより、全体の計算時間を短縮することができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態および比較例に共通の通信ネットワークの構成例を示す図である。
【図２】ネットワークの段階復旧の一例を示す図である。
【図３】ネットワークモデル例を示す図である。
【図４】従来技術の計算時間の一例を示す図である。
【図５】本実施形態における復旧順序の階層的計算の一例を示す図である。
【図６】復旧順序のアルゴリズムの一例を示す図である。
【図７】プログラムの一例を示す図である。
【図８】本実施形態における計算時間の一例を示す図である。
【図９】本実施形態における計算精度の一例を示す図である。
【図１０】ＧＳの作成パターン例を示す図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明に係る復旧順序決定方法および復旧順序決定プログラムの実施形態について説明する。
【００２１】
本実施形態に係る復旧順序決定方法は、激甚災害等により大規模故障が発生した場合に、故障箇所（故障リンクと称する）の復旧順序を決定する計算を従来技術よりも短時間で行うことができる。本実施形態に係る復旧順序決定方法は、全ての故障リンクの復旧順序を決定する計算を一度に実行するのではなく、復旧順序を一度に復旧する故障範囲（故障リンク範囲と称する）を定めてグループ化する。そして、一定数以下のグループをまとめて復旧順序を計算する処理を階層化し、階層毎に復旧順序の計算を行うことにより、全体の計算時間を短縮する。なお、従来技術で現実的な時間で計算可能な範囲（例えばグループ内の復旧対象の故障リンク数が予め決められた一定数以下の場合）は、従来技術と同様に、当該範囲内の故障リンクの復旧順序の計算を一度に実行する。なお、本実施形態に係る復旧順序決定方法は、コンピュータの実行する復旧順序決定プログラムにより実現される。例えば、本実施形態に係る復旧順序決定方法に基づく復旧順序決定プログラムをコンピュータで実行することで故障リンクの復旧順序を求め、求めた復旧順序に基づき作業者が故障リンクを順次復旧することとなる。
【００２２】
図１は、本実施形態および比較例に共通の通信ネットワーク１００の構成例を示す。図１において、通信ネットワーク１００は、物理レイヤ１０１と、ネットワーク制御装置１０２とを有し、物理レイヤ１０１上にパケットレイヤ１０３を構成する。ここで、図１において、通信ネットワーク１００に大規模故障が発生した場合、通信事業者は、コンピュータ１０により、最適な復旧順序を計算する。コンピュータ１０は、本実施形態に係る復旧順序決定プログラムを実行するＣＰＵ１１と、パラメータやプログラムなどを記憶するメモリ１２とを少なくとも有する。なお、パラメータやプログラムなどは、外部の記憶媒体１３に予め記憶しておき、コンピュータ１０にインストールするようにしてもよい。そして、コンピュータ１０が計算した復旧順序に基づいて、ネットワーク制御部１０２は、通信ネットワーク１００の各部の制御や設定を行う。
【００２３】
図１において、物理レイヤ１０１は、レイヤ１とレイヤ２とに対応する。物理レイヤ１０１は、転送ノード２０１Ａ、転送ノード２０１Ｂ、転送ノード２０１Ｃおよび転送ノード２０１Ｄと、伝送ノード３０１Ａ、伝送ノード３０１Ｂ、伝送ノード３０１Ｃ、伝送ノード３０１Ｄ、伝送ノード３０１Ｅ、伝送ノード３０１Ｆおよび伝送ノード３０１Ｇと、物理リンク３０２Ａ、物理リンク３０２Ｂ、物理リンク３０２Ｃ、物理リンク３０２Ｄ、物理リンク３０２Ｅ、物理リンク３０２Ｆ、物理リンク３０２Ｇ、物理リンク３０２Ｈ、物理リンク３０２Ｉ、物理リンク３０２Ｊおよび物理リンク３０２Ｋとを有する。そして、物理レイヤ１０１は、例えば通信事業者の独自のネットワークであるキャリア網の場合、光インフラ網上の光信号の波長や電気信号による論理パスが設定され、論理パスによって上位レイヤ（パケットレイヤ１０３）上にユーザトラフィックの転送路（論理リンク２０２Ａ、論理リンク２０２Ｂおよび論理リンク２０２Ｃ）が構成される。
【００２４】
ここで、以降の説明において、転送ノード２０１Ａ、転送ノード２０１Ｂ、転送ノード２０１Ｃおよび転送ノード２０１Ｄに共通の事項を説明する場合は符号末尾のアルファベットを省略して転送ノード２０１のように表記する。また、論理リンク２０２Ａ、論理リンク２０２Ｂおよび論理リンク２０２Ｃについても、共通の事項を説明する場合は符号末尾のアルファベットを省略して論理リンク２０２のように表記する。同様に、伝送ノード３０１Ａ、伝送ノード３０１Ｂ、伝送ノード３０１Ｃ、伝送ノード３０１Ｄ、伝送ノード３０１Ｅ、伝送ノード３０１Ｆおよび伝送ノード３０１Ｇに共通の事項を説明する場合は符号末尾のアルファベットを省略して伝送ノード３０１のように表記する。また、物理リンク３０２Ａ、物理リンク３０２Ｂ、物理リンク３０２Ｃ、物理リンク３０２Ｄ、物理リンク３０２Ｅ、物理リンク３０２Ｆ、物理リンク３０２Ｇ、物理リンク３０２Ｈ、物理リンク３０２Ｉ、物理リンク３０２Ｊおよび物理リンク３０２Ｋについても、共通の事項を説明する場合は符号末尾のアルファベットを省略して物理リンク３０２のように表記する。また、数字＋アルファベットで記載された他の符号についても、同数字の符号は同一又は同様のブロックを示し、特定のブロックを指す場合に末尾にアルファベットを付加して表記する。
【００２５】
図１において、伝送ノード３０１は物理リンク３０２により接続され、転送ノード２０１は、物理レイヤ１０１上に構成される論理パスを用いた論理リンク２０２をパケットレイヤ１０３上に形成して通信を行う。
【００２６】
図１において、ネットワーク制御装置１０２は、転送ノード２０１および伝送ノード３０１を制御して論理パスの設定を行う。例えば図１において、ネットワーク制御装置１０２は、伝送ノード３０１Ａ、物理リンク３０２Ｆ、伝送ノード３０１Ｄ、物理リンク３０２Ｈおよび伝送ノード３０１Ｆを経由して、転送ノード２０１Ａと転送ノード２０１Ｄとの間にＬ３終端パス４０１Ａを設定する。また、ネットワーク制御装置１０２は、伝送ノード３０１Ｆ、物理リンク３０２Ｋおよび伝送ノード３０１Ｇを経由して、転送ノード２０１Ｄと転送ノード２０１Ｃとの間にＬ３終端パス４０１Ｂを設定する。同様に、ネットワーク制御装置１０２は、伝送ノード３０１Ｇ、物理リンク３０２Ｅおよび伝送ノード３０１Ｅを経由して、転送ノード２０１Ｃと転送ノード２０１Ｂとの間にＬ３終端パス４０１Ｃを設定する。ここで、Ｌ３終端パス４０１は論理パスに対応し、以降の説明では、Ｌ３終端パス４０１を論理パス４０１とも称する。
【００２７】
パケットレイヤ１０３の論理リンク２０２Ａは、例えば物理レイヤ１０１上のＬ３終端パス４０１Ａの一部又は全てを利用して、転送ノード２０１Ａと転送ノード２０１Ｄとの間でユーザトラフィックの伝送路を構成する。また、パケットレイヤ１０３の論理リンク２０２Ｂは、例えば物理レイヤ１０１上のＬ３終端パス４０１Ｂの一部又は全てを利用して、転送ノード２０１Ｄと転送ノード２０１Ｃとの間でユーザトラフィックの伝送路を構成する。同様に、パケットレイヤ１０３の論理リンク２０２Ｃは、例えば物理レイヤ１０１上のＬ３終端パス４０１Ｃの一部又は全てを利用して、転送ノード２０１Ｃと転送ノード２０１Ｂとの間でユーザトラフィックの伝送路を構成する。
【００２８】
図２は、障害発生時に段階的に行われる通信ネットワーク１００の復旧ステージ例を示す。図２に示すように、ビル倒壊等も含む激甚災害により通信ネットワーク１００に障害が発生した場合、物理的な資源（伝送ノード３０１や物理リンク３０２）の復旧を一斉に行うのではなく、一般的に数週間から数ヶ月のスパンで複数の復旧ステージを遷移して段階的に行われる。図２の例では、図２（ａ）に示す障害発生時をステージ０として、図２（ｂ）に示す一次復旧（ステージ１）、図２（ｃ）に示す二次復旧（ステージ２）および図２（ｄ）に示す三次復旧（ステージ３）のように３段階の復旧ステージを経て、通信ネットワーク１００が障害発生前の状態に完全復旧される。ここで、図２において、図１で説明した転送ノード２０１、伝送ノード３０１および物理リンク３０２の配置は、図１と同じである。なお、図２において、各物理リンク３０２の符号は省略してある。
【００２９】
図２（ａ）において、伝送ノード３０１Ｂ、伝送ノード３０１Ｄおよび伝送ノード３０１Ｅと、物理リンク３０２Ａ、物理リンク３０２Ｂ、物理リンク３０２Ｃ、物理リンク３０２Ｄ、物理リンク３０２Ｅ、物理リンク３０２Ｆ、物理リンク３０２Ｇおよび物理リンク３０２Ｈとが障害発生により通信ができない状態になっている。なお、伝送ノード３０１Ａ、伝送ノード３０１Ｃ、伝送ノード３０１Ｆおよび伝送ノード３０１Ｇと、物理リンク３０２Ｉ、物理リンク３０２Ｊおよび物理リンク３０２Ｋは通信できる状態にある。
【００３０】
ここで、障害が発生している物理資源の復旧を行う前に、ネットワーク制御装置１０２は、通信可能な状態にある物理資源を利用して、故障リンクを迂回するパスの設定を行う。例えば図２（ａ）において、ネットワーク制御装置１０２は、残存している物理資源である転送ノード２０１Ａと転送ノード２０１Ｄとの間に、伝送ノード３０１Ａ、伝送ノード３０１Ｃおよび伝送ノード３０１Ｆと、物理リンク３０２Ｉおよび物理リンク３０２Ｊとを経由するＬ３終端パス４０１Ｄを設定し、転送ノード２０１Ａと転送ノード２０１Ｄとの間の通信を可能にする。同様に、ネットワーク制御装置１０２は、転送ノード２０１Ｄと転送ノード２０１Ｃとの間にＬ３終端パス４０１Ｂを設定し、転送ノード２０１Ｄおよび転送ノード２０１Ｃとの間の通信を可能にする。しかし、転送ノード２０１Ｂは、伝送ノード３０１Ｅが障害を受けているため、転送ノード２０１Ｃとの間で通信を行うことができない。
【００３１】
このような状態において、故障リンクの最適な復旧順序を線形計画法により計算し、計算結果の復旧順序に基づいて段階的に故障リンクの復旧を行う。例えば、全ての論理パス４０１の疎通トラヒック量の総和を最大化しつつ、かつ、各々の論理パス４０１のトラヒック流量が均一になるように、故障リンクの最適な復旧順序を数理計画法により計算する。ここで、故障リンクは、例えば伝送ノード３０１間の物理リンク３０２に相当し、伝送ノード３０１間で故障リンクを通信可能な状態に復旧する必要がある。そこで、本実施形態では、数理計画法の一つである線形計画法により、故障リンクの最適な復旧順序を決定するための線形計画問題の解を求め、故障リンクの復旧を行う。
【００３２】
ここで、復旧対象とする故障リンクは、災害などにより通信に障害が発生している物理リンク３０２に相当する。なお、ビルの倒壊などにより、伝送ノード３０１にも障害が発生するが、一般に、伝送ノード３０１などの装置の復旧は、道路などに広範囲に敷設されている物理リンク３０２の復旧よりも早く行われる。本実施形態は、伝送ノード３０１が物理リンク３０２より先に復旧された後、物理リンク３０２の復旧順序を決定する場合に対応する。
【００３３】
例えば図２（ａ）の状態において、先ず、図２（ｂ）に示すような一次復旧（ステージ１）が行われ、先に伝送ノード３０１Ｄおよび伝送ノード３０１Ｅが復旧され、次に物理リンク３０２Ｄおよび物理リンク３０２Ｅが復旧される。これにより、ネットワーク制御装置１０２は、転送ノード２０１Ｂと転送ノード２０１Ｃとの間にＬ３終端パス４０１Ｃを設定し、転送ノード２０１Ｂおよび転送ノード２０１Ｃとの間の通信が復旧する。
【００３４】
次に、図２（ｂ）の状態において、図２（ｃ）に示すような二次復旧（ステージ２）が行われ、先に伝送ノード３０１Ｂが復旧され、次に物理リンク３０２Ａ，物理リンク３０２Ｂおよび物理リンク３０２Ｃが復旧される。これにより、ネットワーク制御装置１０２は、転送ノード２０１Ａと転送ノード２０１Ｂとの間にＬ３終端パス４０１Ｅを設定し、転送ノード２０１Ａおよび転送ノード２０１Ｂとの間の通信が復旧する。
【００３５】
次に、図２（ｃ）の状態において、図２（ｄ）に示すような三次復旧（ステージ３）が行われ、物理リンク３０２Ｆ，物理リンク３０２Ｇおよび物理リンク３０２Ｈが復旧される。これにより、ネットワーク制御装置１０２は、転送ノード２０１Ａと転送ノード２０１Ｄとの間のＬ３終端パス４０１Ａを設定する。そして、ネットワーク制御装置１０２は、Ｌ３終端パス４０１Ｄを障害発生前のＬ３終端パス４０１Ａに切り替える。
【００３６】
このように、ビル倒壊等も含む激甚災害を想定した場合、物理的な資源の復旧は一斉に行われるのではなく、数週間から数ヶ月のスパンで複数の復旧ステージを遷移して段階的に行われる。なお、図２に示した通信ネットワーク１００の場合は、３段階のステージ３で完全復旧するが、４段階以上であってもよい。
【００３７】
ここで、従来技術では、図２に示したステージ０からステージ３までの最適な故障リンクの復旧順序を求める計算を一度に行うので、計算結果が出るまでに時間が掛かるという問題がある。本実施形態においても、従来技術と同様に線形計画法を用いて故障リンクの復旧順序を計算するが、故障リンク数が多い場合は故障リンクを複数のグループに分けて階層化し、階層毎に復旧順序の計算を行う。これにより、本実施形態では、故障リンク数が多い場合に、故障リンクの復旧順序の計算を複数回に分けて行うので、トータルの計算時間を従来技術よりも短縮できる。
【００３８】
［線形計画法を用いた計算方法］
次に、復旧順序を求める計算方法について説明する。なお、復旧順序を求める基本的な計算は従来技術と同じであるが、本実施形態では、一度に全ての故障リンクを計算対象とせずに、故障リンクを複数のグループに分けて階層化し、階層毎に復旧順序を求める計算を行う。
【００３９】
復旧順序の計算自体は、従来技術で説明した通り、論理パス間のトラヒック流量の差分を極力小さくする変数を目的関数として組み込むことで、階層毎の全ての論理パスの疎通トラヒック量の総和を最大化しつつ、かつ、中間の復旧ステージの論理パス間のトラヒック流量差の総和を最小化する復旧順序を線形計画問題として求めることができる。式（１）は、線形計画問題として定式化された目的関数である。
【数２】
0006367150.tif 000003
【００４０】
ここで、変数Ｆplは工程ｌにおける論理パスｐのフロー量である。また、従来技術で説明した通り、式（１）において、第一項は全工程を通したパスフロー間のフロー量の差分の累積値であり、この累積値を最小化することでパスフロー間の均一化を図る。第二項は全工程を通した全論理パスのフロー量の累積値（フロー累積値）であり、正常時の最大フローに相当する定数Ｍからの差分を最小化することで総フロー量の最大化を図る。ｗpは論理パスｐのフローの重みを意味するが、ここではパスフロー間の均一性を目指すため各論理パスｐで同一値とする。λは両項の重み付けのための係数であり、λが小さいほどパスフロー間の均一性が重視され、大きくなるほど総フロー量が重視された復旧順序となる。ｐｈは、工程数である。なお、従来技術では工程当たり１リンクの復旧とするため、故障リンク数と同一値であるが、本実施形態では、複数の故障リンクをグループにまとめて復旧順序を計算する。ここで、工程は復旧ステージに相当する。
【００４１】
式（１）に示した目的関数の制約式は以下の通りである。なお、以降の説明において、式（１）から式（６）までをＬＰ(Linear Programming(線形計画法))計算式と称する。
【００４２】
（フロー保存則）
【数３】
0006367150.tif 000004
【数４】
0006367150.tif 000005
式（２）において、S(p)はパスpの始点ノード、ｔ(p)はパスpの終点ノードをそれぞれ示し、ノードへ入出力する総フローが一致することを意味する。
【００４３】
（容量制約）
【数５】
0006367150.tif 000006
ここで、式（３）は、ステージｌまで復旧が終了した時点における物理リンク(i,j)のフロー量の総和は、物理リンク容量（物理リンクの最大フロー量Ｃij）を超えないという制約である。また、Ｅは全ての物理リンクの集合である。
【００４４】
（リンク復旧制約）
【数６】
0006367150.tif 000007
ここで、式（４）は、各ステージで復旧する故障リンク数が最大でｍ以下であることを制約する。
【数７】
0006367150.tif 000008
ここで、式（５）は、全ての故障リンク（ｙ0ij=0）がいずれかのステージで復旧されることを制約する。
【数８】
0006367150.tif 000009
ここで、式（６）は、ｉからｊへの物理リンク(i,j)と、ｊからｉへの物理リンク(j,i)とが一緒に復旧されることを意味する。
【００４５】
（変数制約）
【数９】
0006367150.tif 000010
【数１０】
0006367150.tif 000011
【数１１】
0006367150.tif 000012
【００４６】
（パラメータ）
【数１２】
0006367150.tif 000013
【数１３】
0006367150.tif 000014
Ｍ：十分大きな値（例えば正常時の総フロー×工程数）
【００４７】
ここで、正常時の総フローは、全故障が復旧時の全ての論理フローの合計値である。この場合、Ｍは、各工程における総フローを全工程で累積した時の上限値に相当する。
λ：復旧対象とする物理リンク選定条件の重み係数
Ｃij：物理リンク(i,j)の正常時容量（容量：最大フロー量）
ｐｈ：工程数（復旧ステージ数）（従来技術では故障リンク数と同一）
ｇij：物理リンク(i,j)の復旧可能ステージ
ｍ：工程当たり（復旧ステージ当たり）の最大リンク復旧数
【００４８】
ここで、従来技術では、上記の目的関数を満足する全ての故障リンクの復旧順序を一度に計算するので、一度の計算で対象とする復旧ステージ数は全故障リンク数Ｌ（Ｌ：正の整数）と同一となる。一方、本実施形態では、復旧対象の故障リンク数とは独立に復旧ステージ数を一定数Ｋ（Ｋ：正の整数）以下に設定する。このときの復旧ステージをＧＳ（Grouped Stage：グループドステージ）と称する。そして、全故障リンクを複数のＧＳに分けて階層化し、上記のＬＰ計算式（１）から式（６）を用いてＧＳ毎に復旧順序を最適化する計算を行う。ここで、一度の計算で対象とするＧＳ数は最大でも予め定めた値Ｋ（最大ＧＳ数と称する）を超えない。また、全故障リンク数をＬとして、最大ＧＳ数Ｋは（０＜Ｋ≦Ｌ）を満たし、計算時間が現実的となる値を初期値として設定する。このように、本実施形態では、階層毎に故障リンクの復旧順序を計算する。このため、一度に計算対象とする故障リンク数が従来技術に比べて少なくなり、トータルの計算時間を従来技術よりも短縮できる。
【００４９】
ここで、従来技術では、全ての故障リンクの復旧順序を一度に計算するので計算回数は一回であるが、計算時間が指数関数的に増加し、現実的な時間で計算が完了しない恐れがある。一方、本実施形態では、故障リンクの復旧順序を階層的に計算するので、計算回数は従来技術よりも多くなるが、一度の計算で対象とする復旧ステージ数は従来技術よりも少なくなる。各ステージにおける復旧順序を従来技術よりも速く求めることができ、迅速に復旧作業に着手することができる。
【００５０】
［比較例における計算時間］
図３は、計算時間を比較するためのネットワークモデル(トポロジー)の一例を示す。図３（ａ）は、Abilene modelの一例を示し、１１個の伝送ノードの６ヶ所に転送ノードが接続されている。図３（ｂ）は、Waxman model baseの一例を示し、２０個の伝送ノードの７ヶ所に転送ノードが接続されている。図３（ｃ）は、Waxman modelの一例を示し、３０個の伝送ノードの７ヶ所に転送ノードが接続されている。図３（ｄ）は、図３（ｃ）と同じWaxman modelの一例であるが、５０個の伝送ノードの場合を示す。
【００５１】
図４は、図３に示したネットワークモデルにおいて、従来技術を用いた場合の計算時間の一例を示す。図４において、横軸は復旧ステージ数を示し、縦軸は復旧順序の計算時間[sec]を対数軸で示す。
【００５２】
図４において、a(10)がAbilene model（11 nodes）、b(10)がWaxman model base（20 nodes）、c(10)がWaxman model（30 nodes）、ｄ(10)がWaxman model（50 nodes）の場合の復旧順序の計算時間をそれぞれ示し、いずれもステージ数は１０である。一方、図４において、b(15)がWaxman model base（20 nodes）、c(15)がWaxman model（30 nodes）、ｄ(15)がWaxman model（50 nodes）の場合の復旧順序の計算時間をそれぞれ示し、いずれもステージ数は１５である。なお、Abilene modelは、リンク数が１４であるため、ステージ数１５は対象外である。また、図４の結果は、CPU:Xeon 3.4GHz(Quad-core)、memories:16GByte、GPLK Solver、lambda=0.7(Abilene),0.5(others)の条件で復旧順序を計算したときの時間である。
【００５３】
図４において、ステージ数が１０の場合、d(10)に示したWaxman model（50 nodes）が10h(時間)を経過しても計算結果が得られずに計算不可である。また、ステージ数が１５の場合、c(15)に示したWaxman model（30 nodes）が10h(時間)を経過しても計算結果が得られずに計算不可である。なお、ステージ数が１０の場合に計算不可であったWaxman model（50 nodes）は、ステージ数が１５の場合（c(15)）も計算不可である。また、b(15)に示したWaxman model base（20 nodes）は、ステージ数が１５の場合、ステージ数が１０の場合に比べて復旧順序の計算時間が１０倍以上に増加している。
【００５４】
このように、全ての故障リンクの復旧順序を一度に計算する従来技術では、計算回数は一回であるが、ステージ数が増加すると復旧時間の計算時間が指数関数的に増加し、現実的な時間で計算が完了しない恐れがある。
【００５５】
［本実施形態における復旧順序の計算方法］
図５は、本実施形態における復旧順序の階層的計算の一例を示す。なお、図５において、各記号は以下のように定義される。
L:全故障リンク数
K:復旧順序計算時の最大ＧＳ数
Li:階層レベル＃ｉのＧＳ内の故障リンク数  (L0＝L, i(整数)＞0)
Ki:階層レベル＃ｉのＧＳ数  (K0=1 , Ki≦K, i(整数)＞0)
X：最終の階層レベル (LX ≦ K)
【００５６】
ここで、本実施形態では、一度の復旧順序を最適化する計算において、復旧対象の故障リンク数とは独立に復旧ステージ数（ＧＳ数）を一定数（最大ＧＳ数Ｋ）以下のＫｉ個（Ｋｉ≧１の整数）に設定する。１つのＧＳでは、Ｌｉ個（Ｌｉ≧１の整数）の故障リンクが復旧対象となる（これを復旧リンク群と称する）。復旧リンク群の故障リンク数が最大ＧＳ数Ｋ以下となるまで、繰り返し同様の処理を繰り返し、ＧＳ間の復旧順序を計算する。そして、復旧対象とする故障リンク数が最大ＧＳ数Ｋ以下になったとき、図５に示した階層レベルＸ（Level#X(Final)）のように、残りの故障リンク（ＬＸ個）をまとめた復旧リンク群を１つのＧＳ＃１とする。そして、残りの故障リンク数ＬＸに対して、従来技術と同様に、故障リンクの復旧順序を計算する。なお、図５、図６および図７で説明する変数ｉおよびｊは、［線形計画法を用いた計算方法］の欄で説明したリンク（ｉ，ｊ）の変数ｉおよびｊとは異なり、図５から図７のアルゴリズム上でのみ用いる。
【００５７】
以下、図５に示した処理を順番に説明する。先ず、階層レベル＃０（Level#0(First)）は、全故障リンクが１つのＧＳ＃１としてグループ化されているが、ＧＳ＃１内の故障リンクの復旧順序は決めない。階層レベル＃０では、従来技術とは異なる本実施形態の手法を適用すべきか否かを判別する。具体的には、ＧＳ数を１として、ＧＳ内における復旧対象の故障リンク数が最大ＧＳ数Ｋを超える場合に、従来技術とは異なる本実施形態特有の手法を適用し、ＧＳ内における復旧対象の故障リンク数Ｌが最大ＧＳ数Ｋ以下の場合には、従来技術と同じ手法を適用する。そして、ＧＳ内における復旧対象の故障リンク数が最大ＧＳ数Ｋを超える場合、分割するＧＳ数Ｋ１と、ＧＳ毎の故障リンク数Ｌ１とを決めて、複数のＧＳに分割する。そして、ＧＳ間の復旧順序をＬＰ計算式（１）から式（６）により計算する。
【００５８】
階層レベル＃１（Level#1）において、階層レベル＃０で計算したＧＳ間の復旧順序の計算結果に基づいて、例えば復旧順序の高い方から順番に、階層レベル＃１のＧＳ＃１、ＧＳ＃２、・・・、ＧＳ＃Ｋ１のように並べ替える。なお、各ＧＳ内にはＬ１個の故障リンクがグループ化されている。そして、各ＧＳ内の故障リンク数Ｌ１が最大ＧＳ数Ｋを超える場合に、従来技術とは異なる本実施形態特有の手法を適用し、ＧＳ内における復旧対象の故障リンク数が最大ＧＳ数Ｋ以下の場合には、従来技術と同じ手法を適用する。例えば、ＧＳ内における復旧対象の故障リンク数Ｌ１が最大ＧＳ数Ｋを超える場合、複数のＧＳに分割するために、分割するＧＳ数Ｋ２と、ＧＳ毎の故障リンク数Ｌ２とを決めて、複数のＧＳに分割する。そして、ＧＳ間の復旧順序をＬＰ計算式（１）から式（６）により計算する。
【００５９】
さらに、階層レベル＃２（Level#2）において、階層レベル＃１で計算したＧＳ間の復旧順序の計算結果に基づいて、例えば復旧順序の高い方から順番に、階層レベル＃２のＧＳ＃１、ＧＳ＃２、・・・、ＧＳ＃Ｋ２のように並べ替える。なお、各ＧＳ内にはＬ２個の故障リンクがグループ化されている。そして、各ＧＳ内の故障リンク数Ｌ２が最大ＧＳ数Ｋを超える場合は、階層レベル＃３が存在し、階層レベル＃２と同様の処理を繰り返し実行する。そして、階層レベル＃２の各ＧＳ内の故障リンク数Ｌ２が最大ＧＳ数Ｋ以下の場合、階層レベル＃２の各ＧＳ内のＬ２個の故障リンクを複数のＧＳに分割する処理は行われず、階層レベル＃Ｘ（Level#X(Final)）に示すように、１つのＧＳ＃１にＬ２個の故障リンクをグループ化して、故障リンク間の復旧順序をＬＰ計算式（１）から式（６）により計算する。
【００６０】
ここで、図５において、Level#1のＧＳ数Ｋ１とLevel#2のＧＳ数Ｋ2は同値でもよいし、異なっていてもよい。
【００６１】
このように、本実施形態では、故障リンク数が最大ＧＳ数Ｋ以下になるまで、階層的に故障リンクを複数のＧＳに分割し、分割されたＧＳ間で復旧順序を計算し、故障リンク数がＧＳ数以下になったときにＧＳ内の残存する故障リンクの復旧順序を計算する。これにより、一度に復旧順序を計算する対象が最大ＧＳ数Ｋ以下のＧＳ間の復旧順序または最大ＧＳ数Ｋ以下の故障リンク間の復旧順序に制限されるので、線形計画法で復旧順序を計算する対象が少なくなり、従来技術に比べて計算時間を短縮することができる。
【００６２】
図６は、ネットワーク復旧順序のアルゴリズムの一例を示す。図６において、ネットワーク復旧順序のアルゴリズムは、最初のＧＳに対する復旧順序を計算する階層レベル＃０の処理と、２番目以降のＧＳに対する復旧順序を計算する階層レベル＃１以降の処理とを有する。ここで、図６に示したアルゴリズムは、図１に示したコンピュータ１０により実行され、最適な復旧順序が求められる。なお、図６に示したアルゴリズムに基づくソフトウェアやＬＰ計算式（１）から式（６）および各制約式やパラメータなどは、記憶媒体１３に記憶しておいて、外部からコンピュータ１０に与えるようにしてもよいし、予めコンピュータ１０のメモリ１２に記憶しておいてもよい。
【００６３】
階層レベル＃０はステップＳ１０２からステップＳ１０５までの処理、階層レベル＃１以降はステップＳ１０６からステップＳ１１０までの処理、がそれぞれ対応する。
【００６４】
ステップＳ１０１において、コンピュータ１０は、一度の復旧順序の計算で対象とする最大ＧＳ数Ｋを決定する。なお、最大ＧＳ数Ｋは、ＬＰ計算式（１）から式（６）により復旧順序を計算する時間が現実的な時間になるように予め設定されている。現実的な時間は、例えば数時間以下などのように決められるが、線形計画法によるプログラムを実行させるコンピュータの能力などに応じて最大ＧＳ数Ｋが決定される。
【００６５】
ステップＳ１０２において、コンピュータ１０は、復旧対象の全故障リンク数Ｌと最大ＧＳ数Ｋとを比較して、Ｌ＞Ｋの場合はステップＳ１０４の処理に進み、Ｌ≦Ｋの場合はステップＳ１０３の処理に進む。
【００６６】
ステップＳ１０３において、コンピュータ１０は、ＬＰ計算式（１）から式（６）を以下の条件下で計算し、復旧順序の計算を終了する。
（条件）ph = L and m = 2(双方向)
つまり、工程数ｐｈを故障リンク数Ｌとし、工程当りの最大リンク復旧数ｍを２とする。ここで、ｍ＝２は、通常、物理リンク３０２が復旧すると、双方向のリンクが同時に復旧するからである。なお、ステップＳ１０３は、従来技術と同様に、全故障リンクの復旧順序の計算を一度に行うが、復旧対象の全故障リンク数Ｌが最大ＧＳ数Ｋ以下なので、全故障リンク数の復旧順序の計算時間は短く抑えることができる。
【００６７】
ステップＳ１０４において、コンピュータ１０は、Ｌ１とＫ１を以下の条件下で決定する。
（条件）K1 ≦ K and K1*L1 ≧ L    （＊：乗算を示す）
ここで、Ｌ１は、階層レベル＃１のＧＳ化された故障リンク数であり、Ｋ１は、階層レベル＃１のＧＳ数である。
【００６８】
ステップＳ１０５において、コンピュータ１０は、ＬＰ計算式（１）から式（６）を以下の条件下で計算し、ＧＳ間の復旧順序を決定する。
（条件）ph = K1 and m = L1*2(双方向) 
そして、コンピュータ１０は、次の階層レベル＃１におけるＧＳ＃ｊ（ｊ＝１  ｔｏ  Ｋ１）を生成する。
【００６９】
ステップＳ１０６において、コンピュータ１０は、処理対象のＧＳ＃ｊに対して、ＧＳ＃ｊよりも後の復旧順序となった物理リンク（ｓ，ｔ）の正常時容量（リンク帯域）Ｃｓｔ＝０とし、ＧＳ＃ｊよりも前の復旧順序となった物理リンク（ｓ，ｔ）のリンク稼動状態ｙ０ｓｔ＝１とする。つまり、本ステップは、処理対象ＧＳ＃ｊよりも後の復旧順序の物理リンクは復旧していないのでフロー量が０であり、処理対象ＧＳ＃ｊよりも前の復旧順序の物理リンクは復旧しているのでリンク稼動中であることを定義するための処理である。
【００７０】
ステップＳ１０７において、コンピュータ１０は、ＧＳ＃ｊにおける復旧対象の故障リンク数Ｌｉと最大ＧＳ数Ｋとを比較して、Ｌｉ＞Ｋの場合はステップＳ１０９の処理に進み、Ｌｉ≦Ｋの場合はステップＳ１０８の処理に進む。
【００７１】
ステップＳ１０８において、Ｌｉ≦Ｋの場合、コンピュータ１０は、ＬＰ計算式（１）から式（６）を以下の条件下で計算し、復旧順序の計算を終了する。
（条件）ph =Ｌｉ and m = 2(双方向)
ここで、ステップＳ１０３と同様に、工程数ｐｈを故障リンク数Ｌとし、工程当りの最大リンク復旧数ｍは２である。また、ステップＳ１０８の処理は、ステップＳ１０３で説明したように、全故障リンクの復旧順序の計算を一度に行うが、復旧対象の全故障リンク数Ｌが最大ＧＳ数Ｋ以下なので、全故障リンク数の復旧順序の計算時間は短く抑えることができる。
【００７２】
ステップＳ１０９において、コンピュータ１０は、Ｌｉ＋１とＫｉ＋１を以下の条件下で決定する。
（条件）Ki+1 ≦ K and Ki+1*Li+1≧ Li
ここで、Ｌｉ＋１は、階層レベル＃（ｉ＋１）のＧＳ化された故障リンク数であり、Ｋｉ＋１は、階層レベル＃（ｉ＋１）のＧＳ数である。
【００７３】
ステップＳ１１０において、コンピュータ１０は、ＬＰ計算式（１）から式（６）を以下の条件下で計算し、ＧＳ間の復旧順序を決定する。
（条件）ph = Ki+1 and m = Li+1*2(双方向)
そして、コンピュータ１０は、次の階層レベル＃（ｉ＋１）における新たなＧＳ＃ｊ（ｊ＝１  ｔｏ  Ｋ１）を生成する。
【００７４】
ステップＳ１１１において、コンピュータ１０は、階層レベル＃ｉ毎に、ｊ＝１からｊ＝Ｋｉまでの全ＧＳ＃ｊでステップＳ１０６からステップＳ１１０までの処理を繰り返し実施した後、次の階層レベル＃（ｉ＋１）の処理に移行し、階層レベル＃（ｉ＋１）の全ＧＳ＃ｊに対してステップＳ１０６からステップＳ１１０までの処理を繰り返し実行する。図５の例では、ｉ＝Ｘまで実行され、階層レベル＃ＸのときにステップＳ１０８の処理が実行される。
【００７５】
図７は、図６に示したアルゴリズムを実現するプログラムの一例を示す。ここで、図７に示したプログラムは、図１に示したコンピュータ１０により実行される。
【００７６】
ステップＳ２０１およびＳ２０２は、図６のステップＳ１０６の処理に対応する。
【００７７】
ステップＳ２０３は、図６のステップＳ１０２およびＳ１０７の処理に対応する。
【００７８】
ステップＳ２０４は、図６のステップＳ１０４およびＳ１０９の処理に対応する。
【００７９】
ステップＳ２０５およびＳ２０６は、図６のステップＳ１０５およびＳ１１０の処理に対応する。
【００８０】
ステップＳ２０７は、図６のステップＳ１１１の処理に対応する。
【００８１】
ステップＳ２０８およびＳ２０９は、図６のステップＳ１０３およびＳ１０８の処理に対応する。
【００８２】
このようにして、図６で説明した故障リンクの復旧順序を計算するアルゴリズムをプログラム化してコンピュータで実行することができる。なお、図７で説明する変数ｓおよびｔは、図３で説明したｓ（ｐ）およびｔ（ｐ）とは異なる変数であり、図３で説明したリンク（ｉ，ｊ）の変数１およびｊと同様にリンクを現す変数である。
【００８３】
［本実施形態における計算時間］
図８は、図３に示したネットワークモデルにおいて、本実施形態の計算方法を用いた場合の計算時間の一例を示す。なお、図８に示した計算時間は、全てのＧＳで要した計算時間の総和である。また、図８は、従来技術の計算結果を示す図４に対応し、横軸はステージ数を示し、縦軸は復旧順序の計算時間[sec]を対数軸で示す。また、図８において、図４と同様に、a(10)がAbilene model（11 nodes）、b(10)がWaxman model base（20 nodes）、c(10)がWaxman model（30 nodes）、ｄ(10)がWaxman model（50 nodes）の場合の復旧順序の計算時間をそれぞれ示し、いずれもステージ数は１０である。一方、図８において、b(15)がWaxman model base（20 nodes）、c(15)がWaxman model（30 nodes）、ｄ(15)がWaxman model（50 nodes）の場合の復旧順序の計算時間をそれぞれ示し、いずれもステージ数は１５である。なお、Abilene modelは、リンク数が１４であるため、ステージ数１５は対象外である。また、図８の結果は、図４に示した従来技術と比較できるように、CPUなどの環境条件（CPU:Xeon 3.4GHz(Quad-core)、memories:16GByte、GPLK Solver、lambda=0.7(Abilene),0.5(others)は、図４と同じ条件で計算している。
【００８４】
図８において、ステージ数が１０の場合、図４に示した従来技術のd(10)のWaxman model（50 nodes）が計算不可であったのに対して、本実施形態に係る計算方法では１００ｓｅｃ以下の時間で計算結果が得られている。また、本実施形態の計算方法では、a(10)のAbilene model（11 nodes）およびb(10)のWaxman model base（20 nodes）についても、図４に示した従来技術の計算時間と比較して大幅に短い時間で復旧順序の計算結果が得られている。さらに、本実施形態の計算方法は、ステージ数が１５の場合においても、図４に示した従来技術では計算不可であったc(15)のWaxman model（30 nodes）およびd(15)のWaxman model（50 nodes）の計算結果が得られている。
【００８５】
このように、本実施形態に係る復旧順序の計算方法は、故障リンクの復旧順序をＧＳ毎に階層的に計算するので、計算回数は従来技術よりも多くなるが、従来技術に比べて復旧順序の計算時間を短縮することができる。特に、従来技術では、計算時間が10000秒を超えるような現実的な時間で計算が困難と判断されるネットワークモデルに対しても現実的な短い時間で復旧順序を計算することができる。
【００８６】
図９は、本実施形態における計算精度の一例を示す。図９において、ネットワークモデル(Network model)は、Abilene model（11 nodes）、Waxman model base（20 nodes）およびWaxman model（30 nodes）の３種類である。各ネットワークモデルにおいて、故障リンク数が１０リンクで故障位置がランダムに生成される３種類の故障形態の場合について、式（１）の値の計算精度を求めている。ここで、計算精度の欄に示した値は誤差を表しており、例えば０．０６は６％の誤差を意味し、０は誤差無しを意味する。図９に示した計算精度は、参考値ではあるが、本実施形態に係る復旧順序の計算方法は、いずれの条件においても０．１未満（１０％以内の誤差）であり、高い計算精度で復旧順序を求めることができる。
【００８７】
［ＧＳの作成パターン例］
本実施形態に係る復旧順序の計算方法は、全故障リンクの復旧順序を一度に計算するのではなく、図５で説明したように、現実的な計算時間になるように予め設定された最大ＧＳ数Ｋよりも全故障リンク数Ｌが多い場合、予め決められた条件下で分割するＧＳ数とＧＳ毎の故障リンク数とを決定して複数のＧＳに分割し、ＧＳ間の復旧順序をＬＰ計算式により計算する。ここで、複数のＧＳの作成パターン例について説明する。
【００８８】
図１０は、ＧＳの作成パターン例を示す。ここで、図１０に示すＧＳの作成パターン例は、例えば図５の階層レベル＃１のＧＳ＃１のＬ１個の故障リンクを階層レベル＃２のＧＳ＃１からＧＳ＃Ｋ２までのＫ２個のＧＳに分割する場合に適用される。なお、図１０に示すＧＳの作成パターン例は、全故障リンク数Ｌが１０、最大ＧＳ数Ｋが５の場合の一例である。つまり、図１０は、例えば図５において、階層レベル＃１のＧＳ＃１の故障リンク数Ｌ１が１０、階層レベル＃２のＧＳ＃１からＧＳ＃Ｋ２までのＫ２が５の場合に相当する。
【００８９】
図１０（ａ）は、同数（２つ）の故障リンクを１つのＧＳとして分割し、ＧＳ＃１からＧＳ＃５までの５つのＧＳを作成するパターン例Ａを示す。なお、図１０（ａ）では、故障リンク１から故障リンク１０の１０個の故障リンクのうち、故障リンク１および故障リンク２がＧＳ＃１、故障リンク３および故障リンク４がＧＳ＃２、・・・、故障リンク９および故障リンク１０がＧＳ＃５のように、５つのＧＳが作成される。ここで、図１０（ａ）では、２つの故障リンクを５つのＧＳに分割する例を示したが、２つ以上の同数の故障リンクを複数のＧＳに分割する場合についても同様に適用可能である。なお、全てのＧＳがそれぞれ１つの故障リンクを持つ場合は、最大ＧＳ数Ｋと全故障リンク数Ｌとが同数の場合に相当し、従来技術と同様の処理を行うことになるが、全故障リンク数Ｌが最大ＧＳ数Ｋと同じなので、現実的な計算時間で復旧順序を計算することができる。
【００９０】
図１０（ｂ）は、異なる数の故障リンクを複数のＧＳに分割するパターン例Ｂを示す。図１０（ｂ）では、故障リンク１がＧＳ＃１、故障リンク２がＧＳ＃２、故障リンク３および故障リンク４がＧＳ＃３、故障リンク５および故障リンク６がＧＳ＃４、故障リンク７から故障リンク１０がＧＳ＃５のように分割し、５つのＧＳが作成される。図１０（ｂ）の例では、早い工程で復旧しようとする故障リンク数を高い精度で見つけるようにＧＳ当たりのリンク数を調整している。
【００９１】
図１０（ｃ）は、図１０（ｂ）と同様に、異なる数の故障リンクを複数のＧＳに分割するパターン例Ｃを示す。図１０（ｃ）では、故障リンク１から故障リンク４がＧＳ＃１、故障リンク５および故障リンク６がＧＳ＃２、故障リンク７および故障リンク８がＧＳ＃３、故障リンク９がＧＳ＃４、故障リンク１０がＧＳ＃５のように分割し、５つのＧＳが作成される。図１０（ｃ）の例では、遅い工程で復旧しようとする故障リンク数を高い精度で見つけるようにＧＳ当たりのリンク数を調整している。
【００９２】
なお、図１０に示したＧＳの作成パターンは一例であり、他のパターンでＧＳを作成した場合についても本実施形態に係る復旧順序の計算方法は、同様に適用可能である。
【００９３】
このように、本実施形態に係る復旧順序の計算方法では、全故障リンクの復旧順序を一度に計算するのではなく、図５で説明したように、現実的な計算時間になるように予め設定された最大ＧＳ数Ｋよりも全故障リンク数Ｌが多い場合、全故障リンクを複数のＧＳに分割する。そして、分割された複数のＧＳを１つの階層としてＧＳ間の復旧順序をＬＰ計算式（１）から式（６）により計算する。さらに、分割した各ＧＳ内の故障リンク数が最大ＧＳ数Ｋよりも多い場合は、分割した各ＧＳ内の故障リンク数が最大ＧＳ数Ｋ以下になるまで同様の処理を繰り返し実行する。そして、分割した各ＧＳ内の故障リンク数が最大ＧＳ数Ｋ以下になった場合に、各ＧＳ内の故障リンク間の復旧順序をＬＰ計算式（１）から式（６）により計算する。これにより、本実施形態に係る復旧順序の計算方法は、全故障リンクの復旧順序を一度に計算する従来技術に比べて、全体の計算時間を短縮することができる。
【００９４】
以上、説明してきたように、本実施形態に係る故障リンクの復旧順序決定方法および復旧順序決定プログラムは、激甚災害の発生時における故障リンクの復旧順序を求める計算において、復旧対象の故障リンクを予め設定された一定数以下のグループにして階層化し、階層毎に複数回に分けて復旧順序の計算を行うことにより、全体の計算時間を短縮することができる。
【符号の説明】
【００９５】
１００・・・通信ネットワーク；１０１・・・物理レイヤ；１０２・・・ネットワーク制御装置；１０３・・・パケットレイヤ送信装置；２０１・・・転送ノード；２０２・・・論理リンク；３０１・・・伝送ノード；３０２・・・物理リンク；４０１・・・Ｌ３終端パス（論理パス）
【図１】
0006367150.tif 000015
【図２】
0006367150.tif 000016
【図３】
0006367150.tif 000017
【図４】
0006367150.tif 000018
【図５】
0006367150.tif 000019
【図６】
0006367150.tif 000020
【図７】
0006367150.tif 000021
【図８】
0006367150.tif 000022
【図９】
0006367150.tif 000023
【図１０】
0006367150.tif 000024