(57)【要約】【課題】通信ネットワークの物理資源の故障から順次復旧する複数のステージに於いて、最大流問題を解く時間計算量のオーダの発散速度を遅らせて、大規模網にも適用可能とする。【解決手段】ネットワーク制御装置１は、通信ネットワークの物理資源である物理ノードと物理リンク４との接続トポロジ情報を格納する網トポロジ記憶部１４と、各伝送パスのトラヒック量情報を格納するトラヒック記憶部１５と、各ステージで復旧される各物理資源の情報を格納する物理資源復旧順序記憶部１７と、最終ステージに於ける最大流問題の解である伝送パスの最終パス集合のうち、各ステージで復旧可能な部分集合、および、この部分集合を復旧した際の残余資源に於ける最大流問題の解であるパス集合との和集合を算出し、各ステージのパス集合とするパス計算部１２とを備える。【選択図】図１
2014236364.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークの物理資源である物理ノードと物理リンクとの接続トポロジ情報を格納する網トポロジ記憶部と、
各伝送パスのトラヒック量情報を格納するトラヒック記憶部と、
各ステージで復旧される各物理資源の情報を格納する物理資源復旧順序記憶部と、
最終ステージに於ける最大流問題の解である伝送パスの最終パス集合のうち、各ステージで復旧可能な部分集合である最終パス部分集合、および、前記最終パス部分集合を復旧した際の残余資源に於ける最大流問題の解である第１残余資源パス集合を算出して、前記最終パス部分集合と前記第１残余資源パス集合との和集合を算出し、各ステージのパス集合とするパス計算部と、
を備えることを特徴とするネットワーク制御装置。
【請求項２】
前記パス計算部は、
初期ステージに於ける最大流問題の解である初期パス集合を算出し、
前記最終パス集合のうち各ステージで復旧可能な部分集合である前記最終パス部分集合を算出し、
前記最終パス部分集合を復旧した際の残余資源により復旧可能な前記初期パス集合の部分集合である初期パス部分集合を算出し、
前記最終パス部分集合と前記初期パス部分集合とを復旧した際の残余資源に於ける最大流問題の解である第２残余資源パス集合を算出し、
前記最終パス部分集合、前記初期パス部分集合、および、前記第２残余資源パス集合の和集合を算出し、各前記ステージのパス集合とする、
ことを特徴とする請求項１に記載のネットワーク制御装置。
【請求項３】
前記パス計算部は、
初期ステージに於ける最大流問題の解である初期パス集合を算出し、
前記最終パス集合のうち各ステージで復旧可能な部分集合である前記最終パス部分集合を算出し、
前記最終パス部分集合を復旧した際の残余資源により復旧可能な直前のステージに於けるパス集合の部分集合である直前パス部分集合を算出し、
前記最終パス部分集合と前記直前パス部分集合とを復旧した際の残余資源に於ける最大流問題の解である第３残余資源パス集合を算出し、
前記最終パス部分集合、前記直前パス部分集合、および、前記第３残余資源パス集合のとの和集合を算出し、各前記ステージのパス集合とする、
ことを特徴とする請求項１に記載のネットワーク制御装置。
【請求項４】
前記パス計算部は更に、
前記ステージのパス集合が、始点ノードおよび終点ノードの同一組合せに係る複数の伝送パスを含んでいたならば、前記複数の伝送パスのうち最大の疎通トラヒック量のものを採用し、それ以外のものを削除する、
ことを特徴とする請求項２または請求項３に記載のネットワーク制御装置。
【請求項５】
通信ネットワークの物理資源である物理ノードと物理リンクとの接続トポロジ情報を格納する網トポロジ記憶部と、
各伝送パスのトラヒック量情報を格納するトラヒック記憶部と、
各ステージで復旧される各物理資源の情報を格納する物理資源復旧順序記憶部と、
を備えたネットワーク制御装置であるコンピュータに、
最終ステージに於ける最大流問題の解である伝送パスの最終パス集合を算出するステップを実行したのち、
復旧の各ステージに於けるパス集合を算出するため、
前記最終パス集合のうち、このステージで復旧可能な部分集合である最終パス部分集合を算出するステップと、
前記最終パス部分集合を復旧した際の残余資源に於ける最大流問題の解である第１残余資源パス集合を算出するステップと、
前記最終パス部分集合および前記第１残余資源パス集合との和集合を算出し、このステージに於けるパス集合とするステップと、
を繰り返し実行させるためのネットワーク制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークの伝送パスを設定するネットワーク制御装置、および、ネットワーク制御プログラムに関する。
【背景技術】
【０００２】
激甚災害などによる大規模なネットワーク障害が発生した際であっても、ネットワーク事業者は、ネットワークの障害装置や伝送路の復旧を速やかに実施し、信頼性の高いネットワークサービスをユーザに提供することが求められている。ネットワーク事業者が提供するネットワークは、例えば、物理的な光インフラ網上に波長による伝送パスを設定し、この伝送パスによって上位レイヤネットワーク上のノードを接続する論理的なリンクを提供するものである。ここで、上位レイヤネットワークとは、例えばＩＰ（Internet Protocol）ネットワークなどである。論理的なリンクとは、ユーザのトラヒック転送路を構成するものである。
【０００３】
障害発生の際、ネットワーク事業者が提供するネットワークは、高品質なネットワークサービスを提供するため、残存資源を有効活用してユーザの疎通トラヒック量を最大化するように伝送パスを再構成することが求められる。そのため、ネットワーク制御装置は、残存資源に於ける最大流問題の解を算出して伝送パスを再構成する。
【０００４】
ネットワーク事業者は、障害が発生したネットワークの通信機器や光ファイバなどの物理資源を可及的速やかに復旧することが望ましい。しかし、ビル倒壊などを含む激甚災害を想定すると、ネットワーク事業者が、障害が発生した物理資源を一度に復旧することが困難な場合も考えられる。その場合、ネットワーク事業者は、数週間から数ヶ月のスパンで段階的に物理資源を復旧する。ネットワーク制御装置は、物理資源が復旧される毎に、残存資源に於ける最大流問題の解を算出して伝送パスを再構成することとなる。
【０００５】
非特許文献１には、段階的復旧が行われるネットワークを前提とした場合に、中間ステージの疎通トラヒック量も含めて、疎通トラヒック量を最大化する方法が記載されている。非特許文献１に記載の技術は、中間ステージを含む複数ステージの疎通トラヒック量の総和を最大化する問題を線形計画問題として定式化し、最適性が保証された厳密解を算出するものである。
【０００６】
ネットワーク事業者が提供するネットワークは、ネットワークサービスの提供の観点により、中間ステージに於いても所定の疎通トラヒック量の確保が要求され、運用負荷の緩和の観点により、復旧ステージの遷移に於ける伝送パスの張り替え本数の最小化が要求される。ここで伝送パスの張り替え本数とは、新たな復旧ステージに遷移したときに、新たに張った伝送パスの本数のことをいう。この場合、伝送パスの張り替え本数を、数理計画問題の目的関数や制約条件として付与することで、要求を満たす制御が実現可能である。
【０００７】
非特許文献２に記載の技術は、伝送パスの張り替え本数を間接的に制御する変数を目的関数としている。これにより、非特許文献２に記載の技術は、復旧の中間ステージで所定の疎通トラヒック量を担保しつつ、複数のステージに遷移する際の伝送パスの張り替え本数を最小化する問題を、線形計画問題として定式化可能である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】WANG Jianping,QIAO Chunming,YU Hongfang、“On Progressive Network Recovery After a Major Disruption”、The Institute of Electrical and Electronics Engineers, Inc.、Proc IEEE INFOCOM、2011年、2011 Vol.3、1925-1933頁
【非特許文献２】S. Kamamura, D. Shimazaki, T. Miyamura, Y. Uematsu, and K. Sasayama、“Fuss-free Progressive Network Recovery after a Large Scale Disaster”、一般社団法人電子情報通信学会、電子情報通信学会大会講演論文集、２０１３年３月５日、２０１３巻、S.72-S.73頁
【発明の概要】
【発明が解決しようとする課題】
【０００９】
激甚災害を想定すると、物理資源は、一度に復旧されるのではなく、段階的に復旧されることが想定される。各物理資源が段階的に復旧された中間のステージに於いても、キャリアネットワークは、所定の疎通トラヒック量を確保することが望ましい。本問題は、線形計画問題としての定式化が可能であり、シンプレックス法や内点法などの古典的アルゴリズムで問題を解くことができる。本問題の時間計算量のオーダは、多項式関数となる。
【００１０】
しかし、これら古典的アルゴリズムは、時間計算量の発散速度が速いため、数百台規模のノードを有するキャリアネットワークに於いて、実用的な時間で計算が完了しない虞があり、よって実用的な計算時間で問題を解けない虞がある。例えば非特許文献２の技術によれば、ノード数をｎとして、ステージ数をＫとした場合、時間計算量のオーダはＯ（ｎ7Ｋ2）となる。
【００１１】
本発明では、通信ネットワークの物理資源の故障から順次復旧する複数のステージにて、ネットワーク制御装置、および、ネットワーク制御プログラムが、パス張り替えの発生頻度を抑制しつつ最大流問題を解くにあたり、時間計算量のオーダの発散速度を遅らせて、大規模な通信ネットワークにも適用可能とすることを課題とする。
【課題を解決するための手段】
【００１２】
前記課題を解決するため、請求項１に記載の発明では、通信ネットワークの物理資源である物理ノードと物理リンクとの接続トポロジ情報を格納する網トポロジ記憶部と、各伝送パスのトラヒック量情報を格納するトラヒック記憶部と、各ステージで復旧される各物理資源の情報を格納する物理資源復旧順序記憶部と、最終ステージに於ける最大流問題の解である伝送パスの最終パス集合のうち、各ステージで復旧可能な部分集合である最終パス部分集合、および、前記最終パス部分集合を復旧した際の残余資源に於ける最大流問題の解である第１残余資源パス集合を算出して、前記最終パス部分集合と前記第１残余資源パス集合との和集合を算出し、各ステージのパス集合とするパス計算部と、を備えることを特徴とするネットワーク制御装置とした。
【００１３】
請求項５に記載の発明では、通信ネットワークの物理資源である物理ノードと物理リンクとの接続トポロジ情報を格納する網トポロジ記憶部と、各伝送パスのトラヒック量情報を格納するトラヒック記憶部と、各ステージで復旧される各物理資源の情報を格納する物理資源復旧順序記憶部と、を備えたネットワーク制御装置であるコンピュータに、最終ステージに於ける最大流問題の解である伝送パスの最終パス集合を算出するステップを実行したのち、復旧の各ステージに於けるパス集合を算出するため、前記最終パス集合のうち、このステージで復旧可能な部分集合である最終パス部分集合を算出するステップと、前記最終パス部分集合を復旧した際の残余資源に於ける最大流問題の解である第１残余資源パス集合を算出するステップと、前記最終パス部分集合および前記第１残余資源パス集合との和集合を算出し、このステージに於けるパス集合とするステップと、を繰り返し実行させるためのネットワーク制御プログラムとした。
【００１４】
このようにすることで、通信ネットワークの物理資源の故障から順次復旧する複数のステージにて、パス張り替えの発生頻度を抑制しつつ最大流問題を解くにあたり、時間計算量のオーダの発散速度を遅らせることができる。
【００１５】
請求項２に記載の発明では、前記パス計算部は、初期ステージに於ける最大流問題の解である初期パス集合を算出し、前記最終パス集合のうち各ステージで復旧可能な部分集合である前記最終パス部分集合を算出し、前記最終パス部分集合を復旧した際の残余資源により復旧可能な前記初期パス集合の部分集合である初期パス部分集合を算出し、前記最終パス部分集合と前記初期パス部分集合とを復旧した際の残余資源に於ける最大流問題の解である第２残余資源パス集合を算出し、前記最終パス部分集合、前記初期パス部分集合、および、前記第２残余資源パス集合の和集合を算出し、各前記ステージのパス集合とする、ことを特徴とする請求項１に記載のネットワーク制御装置とした。
【００１６】
このようにすることで、初期パス集合に含まれる伝送パスを優先して復旧することができるので、伝送パスの張り替え本数を更に減らすことができる。
【００１７】
請求項３に記載の発明では、前記パス計算部は、初期ステージに於ける最大流問題の解である初期パス集合を算出し、前記最終パス集合のうち各ステージで復旧可能な部分集合である前記最終パス部分集合を算出し、前記最終パス部分集合を復旧した際の残余資源により復旧可能な直前のステージに於けるパス集合の部分集合である直前パス部分集合を算出し、前記最終パス部分集合と前記直前パス部分集合とを復旧した際の残余資源に於ける最大流問題の解である第３残余資源パス集合を算出し、前記最終パス部分集合、前記直前パス部分集合、および、前記第３残余資源パス集合のとの和集合を算出し、各前記ステージのパス集合とする、ことを特徴とする請求項１に記載のネットワーク制御装置とした。
【００１８】
このようにすることで、直前のステージのパス集合に含まれる伝送パスを優先して復旧することができるので、伝送パスの張り替え本数を、請求項２に記載の発明よりも更に減らすことができる。
【００１９】
請求項４に記載の発明では、前記パス計算部は更に、前記ステージのパス集合が、始点ノードおよび終点ノードの同一組合せに係る複数の伝送パスを含んでいたならば、前記複数の伝送パスのうち最大の疎通トラヒック量のものを採用し、それ以外のものを削除する、ことを特徴とする請求項２または請求項３に記載のネットワーク制御装置とした。
【００２０】
このようにすることで、各伝送ノードは、設定が単純化されるので、不具合を未然に防止することができ、よって、通信ネットワークの運用性を向上することができる。
【発明の効果】
【００２１】
本発明によれば、通信ネットワークの物理資源の故障から順次復旧する複数のステージにて、ネットワーク制御装置、および、ネットワーク制御プログラムが、パス張り替えの発生頻度を抑制しつつ最大流問題を解くにあたり、時間計算量のオーダの発散速度を遅らせることができる。よって、大規模な通信ネットワークにも適用可能となる。
【図面の簡単な説明】
【００２２】
【図１】第１の実施形態に於けるネットワーク制御装置を示す概略の構成図である。
【図２】第１の実施形態に於けるパス計算処理を示すフローチャートである。
【図３】第１の実施形態に於ける最終ステージのパス集合を示す図である。
【図４】第１の実施形態に於ける各ステージの状態を示す図である。
【図５】第１の実施形態の変形例に於けるパス計算処理を示すフローチャートである。
【図６】第２の実施形態に於けるパス計算処理を示すフローチャートである。
【図７】第２の実施形態に於ける最終ステージと初期ステージのパス集合を示す図である。
【図８】第２の実施形態に於ける各ステージの状態を示す図である。
【図９】第３の実施形態に於けるパス計算処理を示すフローチャートである。
【図１０】第３の実施形態に於ける各ステージの状態を示す図である。
【図１１】第４の実施形態に於けるパス計算処理を示すフローチャートである。
【図１２】比較例および第１〜第３の実施形態に共通する通信ネットワークを示す概略の構成図である。
【図１３】比較例のネットワーク制御装置を示す概略の構成図である。
【図１４】通信ネットワークの比較例に於ける段階復旧の例を示す図である。
【発明を実施するための形態】
【００２３】
次に、本発明の比較例と、本発明を実施するための形態（「実施形態」という）とについて、適宜図面を参照しながら詳細に説明する。
【００２４】
本発明では、複数ステージを同時に最適化する問題を、単独ステージ毎に最適化する問題に変換することにより、時間計算量のオーダの発散速度を遅らせている。具体的には、完全復旧時の伝送パス構成である最終パス集合や、初回復旧時の伝送パス構成である初期パス集合を個別に計算する。本発明は、これらの結果を中間ステージの伝送パス構成に反映することで、可能な限り伝送パスを固定し、よって伝送パスの張り替えの発生頻度を抑制する。
【００２５】
図１２は、比較例および第１〜第４の実施形態に共通する通信ネットワーク９を示す概略の構成図である。
図１２に示すように、通信ネットワーク９は、物理レイヤ６と、この物理レイヤ６に物理的に接続される比較例のネットワーク制御装置１Ｄ、または、第１〜第４実施形態のネットワーク制御装置１を含んで構成される。以下の説明にて、比較例のネットワーク制御装置１Ｄとして説明する。第１〜第４実施形態では、比較例のネットワーク制御装置１Ｄを、ネットワーク制御装置１として読み替えることができる。通信ネットワーク９は更に、この物理レイヤ６の上位概念としてのパケットレイヤ７としても構成される。
物理レイヤ６は、ＩＰルータなどである転送ノード２ａ〜２ｄと、光スイッチなどである伝送ノード３ａ〜３ｇと、それらを通信可能に結ぶ光ファイバなどである物理リンク４とを含んで構成される。転送ノード２ａ〜２ｄは、この通信ネットワーク９と、他の通信ネットワークとを接続するエッジノードである。伝送ノード３ａ〜３ｇと物理リンク４とは、これら転送ノード２ａ〜２ｄを物理的に接続するものである。
転送ノード２ａ〜２ｄと、伝送ノード３ａ〜３ｇとは、物理レイヤ６の物理ノードを構成する。転送ノード２ａ〜２ｄと、伝送ノード３ａ〜３ｇと、物理リンク４とは、通信ネットワーク９の物理資源である。物理レイヤ６は、データプレーン（Data-Plane）であり、ユーザのトラヒックを転送するものである。
転送ノード２ａは、伝送ノード３ａに通信可能に接続されている。転送ノード２ｂは、伝送ノード３ｂに通信可能に接続されている。転送ノード２ｃは、伝送ノード３ｃに通信可能に接続されている。転送ノード２ｄは、伝送ノード３ｄに通信可能に接続されている。
【００２６】
伝送ノード３ａは、物理リンク４によって伝送ノード３ｆに接続され、物理リンク４によって伝送ノード３ｇに接続され、物理リンク４によって伝送ノード３ｅに接続されている。更に伝送ノード３ｅは、物理リンク４によって伝送ノード３ｇに接続され、物理リンク４によって伝送ノード３ｄに接続されている。更に伝送ノード３ｆは、物理リンク４によって伝送ノード３ｇに接続され、物理リンク４によって伝送ノード３ｂに接続されている。更に伝送ノード３ｇは、物理リンク４によって伝送ノード３ｂに接続され、物理リンク４によって伝送ノード３ｄに接続されている。伝送ノード３ｃは、物理リンク４によって伝送ノード３ｂに接続され、物理リンク４によって伝送ノード３ｄに接続されている。
以下、転送ノード２ａ〜２ｄを特に区別しない場合には、単に転送ノード２と記載する。伝送ノード３ａ〜３ｇを特に区別しない場合には、単に伝送ノード３と記載する。
【００２７】
ネットワーク制御装置１Ｄは、物理レイヤ６上に、転送ノード２ｂ，２ｃを始終点とした伝送パス５１ｂと、転送ノード２ｃ，２ｄを始終点とした伝送パス５１ｃと、転送ノード２ａ，２ｄを始終点とした伝送パス５１ｅとを設定する。ネットワーク制御装置１Ｄは、不図示の制御プレーンを介して、各物理ノードを制御するものである。
伝送パス５１ｂは、転送ノード２ｂから伝送ノード３ｂ，３ｃを介して、転送ノード２ｃに接続されるものである。この伝送パス５１ｂは、方向に関する属性は有していないため、転送ノード２ｃから伝送ノード３ｃ，３ｂを介して、転送ノード２ｃに接続されるものとしてもよい。
伝送パス５１ｃは、転送ノード２ｃから伝送ノード３ｃ，３ｄを介して、転送ノード２ｄに接続されるものである。伝送パス５１ｅは、転送ノード２ｄから伝送ノード３ｄ，３ｇ，３ａを介して、転送ノード２ａに接続されるものである。
以下、伝送パス５１ｂ，５１ｃ，５１ｅと特に区別しない場合には、単に伝送パス５１と記載する。伝送パス５１は、波長パスである。しかし、これに限られず、伝送パス５１は、ＭＰＬＳ−ＴＰ（Multiprotocol Label Switching-Transport Profile）などの電気パスであってもよい。
【００２８】
パケットレイヤ７は、物理レイヤ６の上位レイヤであり、転送ノード２ｂ，２ｃの間に論理リンク７１ｂを構成し、転送ノード２ｃ，２ｄの間に論理リンク７１ｃを構成し、転送ノード２ａ，２ｄの間に論理リンク７１ｄを構成する。論理リンク７１ｂは、物理レイヤ６の伝送パス５１ｂにより構成される。論理リンク７１ｃは、物理レイヤ６の伝送パス５１ｃにより構成される。論理リンク７１ｄは、物理レイヤ６の伝送パス５１ｄにより構成される。以下、論理リンク７１ｂ，７１ｃ，７１ｄなどを特に区別しないときには、単に論理リンク７１と記載する。
【００２９】
ネットワーク制御装置１Ｄは、通信ネットワーク９の情報を収集して、通信ネットワーク９を構成する各ノードに制御情報を設定し、よって伝送パス５１を設定する。ネットワーク制御装置１Ｄは、通信ネットワーク９に対して少なくとも１台が設置されている。しかし、これに限られず、ネットワーク制御装置１Ｄは、通信ネットワーク９に対して機能ごとに複数台を設置したり、制御対象のノードごとに同一機能の複数台を設置してもよい。
【００３０】
図１３（ａ），（ｂ）は、比較例のネットワーク制御装置１Ｄを示す概略の構成図である。図１３（ａ）は、ネットワーク制御装置１Ｄの構成を示している。図１３（ｂ）は、ネットワーク制御装置１Ｄの各部の連携動作を示している。
図１３（ａ），（ｂ）では、ネットワーク制御装置１Ｄは、伝送パス５１の設定や、その設定に必要な情報取得に関する処理部のみを示している。なお、伝送パス５１を、論理リンク７１と見なしたときに構成される論理トポロジ（ＩＰネットワークもしくはＭＰＬＳネットワーク）上のルーティング方法については、一般的なＩＰルーティング機能やＭＰＬＳスイッチング機能によって実現可能であるため、説明は省略する。
【００３１】
図１３（ａ）に示すように、ネットワーク制御装置１Ｄは、処理部としてネットワーク情報収集部１１と、パス計算部１２と、パス設定部１３とを含み、記憶部の情報要素として網トポロジ記憶部１４と、トラヒック記憶部１５と、パス記憶部１６とを含んで構成される。
ネットワーク情報収集部１１は、網トポロジ情報やトラヒック情報を、通信ネットワーク９から取得するものである。
パス計算部１２は、網トポロジ記憶部１４に格納されたトポロジ情報に基づいて、伝送パス５１の設定方法を計算するものである。
パス設定部１３は、パス記憶部１６に格納された伝送パス情報を、通信ネットワーク９上の各物理ノードに対して設定するものである。
【００３２】
網トポロジ記憶部１４は、通信ネットワーク９（図１２参照）の転送ノード２および伝送ノード３と物理リンク４との接続トポロジ情報を格納する記憶部である。転送ノード２および伝送ノード３は、通信ネットワーク９の物理資源かつ物理ノードである。物理リンク４は、通信ネットワーク９の物理資源である。
トラヒック記憶部１５は、通信ネットワーク９上の論理リンク７１かつ伝送パス５１に収容されているトラヒック量を格納する記憶部である。
パス記憶部１６は、パス計算部１２が計算した伝送パス情報を格納する記憶部である。
【００３３】
これらネットワーク情報収集部１１、パス計算部１２、パス設定部１３は、このネットワーク制御装置１Ｄが備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路などにより実現される。網トポロジ記憶部１４、トラヒック記憶部１５、パス記憶部１６は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリなどの記憶媒体から構成される。なお、ネットワーク制御装置１Ｄをプログラム実行処理により実現する場合、この記憶媒体には、このネットワーク制御装置１Ｄの機能を実現するためのネットワーク制御プログラムが格納される。
【００３４】
図１３（ｂ）に示すように、ネットワーク情報収集部１１は、通信ネットワーク９から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納する。
パス計算部１２は、網トポロジ記憶部１４に格納されたトポロジ情報と、トラヒック記憶部１５に格納されたトラヒック情報に基づいて計算した伝送パス情報を、パス記憶部１６に格納する。
パス設定部１３は、パス記憶部１６に格納された伝送パス情報を、通信ネットワーク９上の各物理ノードに対して設定する。
【００３５】
図１４（ａ）〜（ｄ）は、通信ネットワーク９の比較例に於ける段階復旧の例を示す図である。
ビル倒壊などを含む激甚災害によるネットワーク障害が発生した際、通信ネットワーク９のネットワーク制御装置１Ｄは、残存資源を有効活用して最大限にユーザトラヒックを転送するため、伝送パス５１を再構成する。このような激甚災害に於いて、物理資源は、一度で復旧されるのではなく、数週間から数ヶ月のスパンで段階的に複数される。以下の比較例では、この段階的な復旧を、第０ステージから第３ステージに分けて示している。
なお、以降の通信ネットワーク９を示す図では、障害を受けて停止している物理資源を、斜線によるハッチングと、破線による輪郭線で示している。
【００３６】
図１４（ａ）は、通信ネットワーク９の障害発生時（第０ステージ）の状態を示している。
図１４（ａ）に示すように、第０ステージに於いて、通信ネットワーク９の伝送ノード３ｂ，３ｆ，３ｇは、障害を受けて停止している。伝送ノード３ｂ，３ｆ，３ｇの停止により、これら伝送ノード３ｂ，３ｆ，３ｇを相互に接続する各物理リンク４は停止する。例えば、伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａとを接続する物理リンク４は停止する。伝送ノード３ｇの停止により、この伝送ノード３ｇと伝送ノード３ａ，３ｅ，３ｄとを接続する各物理リンク４は停止する。
【００３７】
ネットワーク制御装置１Ｄは、残存資源に於ける最大流問題の解を算出し、転送ノード２ｃ，２ｄを始終点とする伝送パス５１ｃと、転送ノード２ａ，２ｄを始終点とする伝送パス５１ｄとを設定する。これにより、ネットワーク制御装置１Ｄは、通信ネットワーク９に残存している物理資源を有効に活用して、ユーザにネットワークサービスを提供することができる。
しかし、ネットワーク制御装置１Ｄは、伝送ノード３ｂが停止しているので、この伝送ノード３ｂを経由する転送ノード２ｂに対しては、伝送パス５１を設定することができない。
【００３８】
図１４（ｂ）は、通信ネットワーク９の一次復旧時（第１ステージ）の状態を示している。
図１４（ｂ）に示すように、第１ステージに於いて、通信ネットワーク９上には、新たに伝送ノード３ｂが復旧し、伝送ノード３ｆ，３ｇが障害を受けて停止している。このとき、伝送ノード３ｆ，３ｇの停止により、これら伝送ノード３ｆ，３ｇを相互に接続する物理リンク４は停止する。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｂを接続する各物理リンク４は停止する。伝送ノード３ｇの停止により、この伝送ノード３ｇと伝送ノード３ａ，３ｅ，３ｄとを接続する各物理リンク４は停止する。
伝送ノード３ｂの復旧に伴い、ネットワーク制御装置１Ｄは、残存資源に於ける最大流問題の解を算出し、新たに転送ノード２ｂ，２ｃを始終点とする伝送パス５１ｂを設定する。これにより、ネットワーク制御装置１Ｄは、通信ネットワーク９に残存している物理資源を有効に活用して、ユーザにネットワークサービスを提供することができる。
【００３９】
図１４（ｃ）は、通信ネットワーク９の二次復旧時（第２ステージ）の状態を示している。
図１４（ｃ）に示すように、通信ネットワーク９上には、新たに伝送ノード３ｆが復旧し、伝送ノード３ｇが障害を受けて停止している。伝送ノード３ｇの停止により、この伝送ノード３ｇと伝送ノード３ａ，３ｅ，３ｄとを接続する各物理リンク４は停止する。
伝送ノード３ｆの復旧に伴い、ネットワーク制御装置１Ｄは、残存資源に於ける最大流問題の解を算出し、新たに転送ノード２ａ，２ｂを始終点とする伝送パス５１ａを設定する。これにより、ネットワーク制御装置１Ｄは、通信ネットワーク９に残存している物理資源を有効に活用して、ユーザにネットワークサービスを提供することができる。
【００４０】
図１４（ｄ）は、通信ネットワーク９の三次復旧時（第３ステージ）の状態を示している。この第３ステージは、障害から完全に復旧した最終状態である。
図１４（ｄ）に示すように、通信ネットワーク９上には、新たに伝送ノード３ｇが復旧している。伝送ノード３ｇの復旧に伴い、ネットワーク制御装置１Ｄは、残存資源に於ける最大流問題の解を算出し、伝送パス５１ｄの代わりに、新たに転送ノード２ａ，２ｄを始終点とする伝送パス５１ｅを設定する。これは、伝送パス５１ｄの疎通トラヒック量よりも、伝送パス５１ｅの疎通トラヒック量の方が多いためである。これにより、ネットワーク制御装置１Ｄは、通信ネットワーク９の物理資源を有効に活用して、ユーザにネットワークサービスを提供することができる。
【００４１】
（第１の実施形態）
図１（ａ），（ｂ）は、第１の実施形態に於けるネットワーク制御装置１を示す概略の構成図である。図１（ａ）は、ネットワーク制御装置１の構成を示している。図１（ｂ）は、ネットワーク制御装置１の各部の連携動作を示している。図１３（ａ），（ｂ）に示す比較例のネットワーク制御装置１Ｄと同一の要素には同一の符号を付与している。
図１（ａ）に示すように、ネットワーク制御装置１は、比較例のネットワーク制御装置１Ｄ（図１３（ａ））と同様の構成に加えて更に、物理資源復旧順序記憶部１７を備えている。物理資源復旧順序記憶部１７は、各復旧ステージで復旧する転送ノード２、伝送ノード３、物理リンク４などの物理資源の情報が格納されているものである。通信ネットワーク９（図１２参照）の管理者は、例えば不図示の端末などを介して、工事計画などに基づき、物理資源復旧順序記憶部１７に、各物理資源の復旧に関する情報を入力する。
パス計算部１２は、復旧の最終ステージに於ける最大流問題の解である伝送パス５１の最終パス集合のうち、各ステージで復旧可能な部分集合、および、この部分集合を復旧した際の残余資源に於ける最大流問題の解であるパス集合の和集合を算出し、各ステージのパス集合とするものである。これにより、パス計算部１２は、通信ネットワーク９の物理資源の故障から順次復旧する複数のステージにて、伝送パス５１の張り替えの発生頻度を抑制しつつ最大流問題を解くにあたり、時間計算量のオーダの発散速度を遅らせることができる。これにより、通信ネットワーク９が大規模であっても、第１の実施形態のネットワーク制御装置１を適用可能となる。パス計算部１２の処理は、後記する図２で詳細に説明する。
【００４２】
図１（ｂ）に示すように、第１の実施形態のネットワーク情報収集部１１は、比較例と同様に、通信ネットワーク９（図１２参照）から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納する。
第１の実施形態のパス計算部１２は、網トポロジ記憶部１４に格納されたトポロジ情報と、トラヒック記憶部１５に格納されたトラヒック情報に加えて、物理資源復旧順序記憶部１７に格納された物理資源の情報に基づいて伝送パス情報を計算する。パス計算部１２は、計算した伝送パス情報を、パス記憶部１６に格納する。
第１の実施形態のパス設定部１３は、比較例と同様に、パス記憶部１６に格納された伝送パス情報を、通信ネットワーク９（図１２参照）上の各物理ノードに対して設定する。
【００４３】
物理資源の復旧順序は、例えば、通信ネットワーク９（図１２参照）の管理者によって入力される。ここで通信ネットワーク９（図１２参照）は、第０ステージから第Ｋ（Ｋは自然数）ステージまでを遷移して物理資源の復旧が完了するものとする。第０ステージは、初期ステージであり、例えば、激甚災害によって物理資源が故障しているステージである。第Ｋステージは、最終ステージであり、例えば、すべての物理資源が復旧したステージである。このように、通信ネットワーク９の物理資源は、段階的に復旧される場合がある。
【００４４】
図２は、第１の実施形態に於けるパス計算処理を示すフローチャートである。適宜、図１２および図１（ａ）の要素を参照している。
ネットワーク情報収集部１１が通信ネットワーク９（図１２参照）から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納すると、パス計算部１２は、パス計算処理を開始する。
ステップＳ１０に於いて、パス計算部１２は、最終ステージ上で最大流問題の解である最終パス集合を算出する。この最終パス集合は、最終ステージ上にて、疎通トラヒック量を最大化する伝送パス５１の集合である。この最終パス集合は、各伝送パス５１の接続トポロジ情報と、各伝送パス５１の要求帯域の情報とを含んで構成される。
【００４５】
パス計算部１２は、最大流問題の解を算出するため、ヒューリスティックアルゴリズムであるエドモンズ・カープ法を用いる。これにより、パス計算部１２は、最大流問題の解を、転送ノード数の自乗と物理リンク数の自乗とを乗算したオーダの時間計算量で解くことができる。ここで、物理リンク数と転送ノード数がほぼ等しいという前提によれば、転送ノード数ｎに対する時間計算量のオーダは、Ｏ（ｎ4）となる。
ステップＳ１１〜Ｓ１５に於いて、パス計算部１２は、第０ステージから第（Ｋ−１）ステージまでの処理を繰り返す。以下、繰り返しに係る各ステージの順番は、変数ｋで示す。なお、本明細書では、変数を示す符号に於いて、大文字と小文字とを区別して記載している。
【００４６】
ステップＳ１２に於いて、パス計算部１２は、最終パス集合のうち、この第ｋステージで復旧可能な部分集合を算出する。この部分集合は、以下、最終パス部分集合と記載する。このとき、パス計算部１２は、各伝送パス５１単位のトラヒック量などを参考に、伝送パス５１の復旧優先度を設けてもよい。
ステップＳ１３に於いて、パス計算部１２は、残余資源上で最大流問題を解き、パス集合を算出する。残余資源とは、第ｋステージのトポロジから最終パス部分集合の各伝送パス５１の要求帯域を減算したものである。ここで算出したパス集合は、以下、第１残余資源パス集合と記載する。
【００４７】
ステップＳ１４に於いて、パス計算部１２は、算出した最終パス部分集合と、第１残余資源パス集合との和集合を算出し、この第ｋステージのパス集合とする。
ステップＳ１５に於いて、パス計算部１２は、第（Ｋ−１）ステージまでの処理を繰り返したか否かを判断する。パス計算部１２は、当該判断条件が成立しなかったならば、ステップＳ１１の処理に戻る。
ステップＳ１６に於いて、パス計算部１２は、第０ステージから第Ｋステージまでのパス集合をすべて出力する。パス計算部１２は、パス記憶部１６にパス集合を格納することにより、これらパス集合を出力する。パス計算部１２は、ステップＳ１６の処理が終了すると、図２のパス計算処理を終了する。
【００４８】
図２のパス計算処理によれば、パス計算部１２は、ノード数ｎに対する時間計算量のオーダがＯ（ｎ4）である最大流問題をＫ回解く。そのため、時間計算量のオーダは、Ｏ（Ｋｎ4）となる。
【００４９】
図３は、第１の実施形態に於ける最終ステージのパス集合を示す図である。
図３に示す通信ネットワーク９は、図１２の物理レイヤ６に該当する部分が示されている。通信ネットワーク９は、転送ノード２ａ〜２ｄと、伝送ノード３ａ〜３ｇと、それらを通信可能に結ぶ物理リンク４とを含んで構成される。この物理リンク４の帯域は、１００Ｇｂｐｓである。
【００５０】
この最終ステージに於ける最終パス集合５ｚは、最大流問題の解であり、パス計算部１２によって算出されるものである。最終パス集合５ｚは、伝送パス５１ａ〜５１ｅを含んで構成される。
伝送パス５１ａは、転送ノード２ａから伝送ノード３ａ，３ｆ，３ｂを介して、転送ノード２ｂに接続されるものである。伝送パス５１ｂは、転送ノード２ｂから伝送ノード３ｂ，３ｃを介して、転送ノード２ｃに接続されるものである。伝送パス５１ｃは、転送ノード２ｃから伝送ノード３ｃ，３ｄを介して、転送ノード２ｄに接続されるものである。伝送パス５１ｄは、転送ノード２ｄから伝送ノード３ｄ，３ｅ，３ａを介して、転送ノード２ａに接続されるものである。伝送パス５１ｅは、転送ノード２ａから伝送ノード３ａ，３ｇ，３ｄを介して、転送ノード２ｄに接続されるものである。各伝送パス５１は、それぞれ独立した物理リンク４上に設定されているので、１００Ｇｂｐｓの帯域で通信可能である。
【００５１】
図４（ａ）〜（ｃ）は、第１の実施形態に於ける各ステージの状態を示す図である。図４（ａ）〜（ｃ）に於いて、実線で示した伝送パス５１は、直前のステージと共通していることを示している。破線で示した伝送パス５１は、直前のステージとは異なっており、伝送パス５１が張り替えられたことを示している。太い実線および太い破線で示した伝送パス５１の帯域は、１００Ｇｂｐｓである。細い実線および細い破線で示した伝送パス５１の帯域は、５０Ｇｂｐｓである。
【００５２】
図４（ａ）は、通信ネットワーク９の第０ステージの状態を示している。なお、第０ステージの直前は、図３に示した最終ステージとする。
図４（ａ）に示すように、故障が発生した第０ステージに於いて、通信ネットワーク９の伝送ノード３ｆは、障害を受けて停止している。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｇ，３ｂを相互に接続する各物理リンク４は停止する。更に、伝送ノード３ａと伝送ノード３ｇを接続する各物理リンク４は停止する。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚのうち、この第０ステージで復旧可能な部分集合を算出する。この最終パス部分集合は、伝送パス５１ｂ，５１ｃ，５１ｄである。図３に示した最終パス集合５ｚのうち、伝送パス５１ａ，５１ｅは、復旧することができない。
【００５３】
パス計算部１２は更に、残余資源上で最大流問題を解き、第１残余資源パス集合を算出する。第１残余資源パス集合は、破線で示された伝送パス５１ｆである。
最終パス部分集合である伝送パス５１ｂ，５１ｃ，５１ｄと、第１残余資源パス集合である伝送パス５１ｆとの和集合が、この第０ステージのパス集合となる。
第０ステージに於ける伝送パス５１の張り替え本数は、１本である。伝送パス５１ｂ，５１ｃは、それぞれ独立した物理リンク４上に設定されているので、１００Ｇｂｐｓの帯域で通信可能である。伝送パス５１ｄ，５１ｆは、物理リンク４を一部で共有しているので、例えば、それぞれ５０Ｇｂｐｓの帯域で通信可能である。よって、第０ステージのパス集合の疎通トラヒック量は、３００Ｇｂｐｓとなる。
【００５４】
図４（ｂ）は、通信ネットワーク９の第１ステージの状態を示している。
図４（ｂ）に示すように、第１ステージに於いて、伝送ノード３ａと伝送ノード３ｇとを接続する各物理リンク４が復旧する。通信ネットワーク９の伝送ノード３ｆは、障害を受けて停止している。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｇ，３ｂを相互に接続する各物理リンク４は停止する。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚのうち、この第１ステージで復旧可能な部分集合を算出する。この最終パス部分集合は、伝送パス５１ｂ，５１ｃ，５１ｄである。
【００５５】
パス計算部１２は更に、残余資源上で最大流問題を解き、第１残余資源パス集合を算出する。この第１残余資源パス集合は、伝送パス５１ｇである。すなわち、パス計算部１２は、この第１ステージに於いて、転送ノード２ａ，２ｂを接続するため、５０Ｇｂｐｓの帯域の伝送パス５１ｆに代わり、１００Ｇｂｐｓの帯域の伝送パス５１ｇを新たに設定する。
最終パス部分集合である伝送パス５１ｂ，５１ｃ，５１ｄと、第１残余資源パス集合である伝送パス５１ｇとの和集合が、この第１ステージのパス集合となる。
第１ステージに於ける伝送パス５１の張り替え本数は、１本である。第１ステージのパス集合の疎通トラヒック量は、４００Ｇｂｐｓとなる。
【００５６】
図４（ｃ）は、通信ネットワーク９の第２ステージの状態を示している。この第２ステージは、故障していた物理資源がすべて復旧した最終ステージである。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚをすべて復旧可能である。この最終パス集合５ｚは、伝送パス５１ａ，５１ｂ，５１ｃ，５１ｄ，５１ｅである。
この第２ステージに於いて、破線で示す伝送パス５１ａ，５１ｅは、新たに設定される。第２ステージに於ける伝送パス５１の張り替え本数は、２本である。第２ステージのパス集合の疎通トラヒック量は、５００Ｇｂｐｓとなる。
【００５７】
図５は、第１の実施形態の変形例に於けるパス計算処理を示すフローチャートである。図２に示す第１の実施形態のフローチャートと同一の要素には同一の符号を付与している。
第１の実施形態と同様にネットワーク情報収集部１１が通信ネットワーク９から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納すると、パス計算部１２は、パス計算処理を開始する。
ステップＳ１０は、図２に示すステップＳ１０と同様に最大パス集合を算出する処理である。最終パス集合を計算したステップＳ１０以降、この変形例では、各ステージのパス集合を求める処理を、並列演算している。
【００５８】
ステップＳ２０ａ〜Ｓ２２ａの処理は、第０ステージに係る処理である。
ステップＳ２０ａに於いて、パス計算部１２は、最終パス集合５ｚのうち、第０ステージで復旧可能な部分集合を算出する。
ステップＳ２１ａに於いて、パス計算部１２は、残余資源上で最大流問題を解き、パス集合を算出する。
ステップＳ２２ａに於いて、パス計算部１２は、算出したパス集合の和集合を、第０ステージのパス集合とする。
【００５９】
ステップＳ２０ｎ〜Ｓ２２ｎの処理は、第（Ｋ−１）ステージに係る処理である。
ステップＳ２０ｎに於いて、パス計算部１２は、最終パス集合５ｚのうち、第（Ｋ−１）ステージで復旧可能な部分集合を算出する。
ステップＳ２１ｎに於いて、パス計算部１２は、残余資源上で最大流問題を解き、パス集合を算出する。
ステップＳ２２ｎに於いて、パス計算部１２は、算出したパス集合の和集合を、第（Ｋ−１）ステージのパス集合とする。
ステップＳ２０ａ〜Ｓ２２ａの処理から、ステップＳ２０ｎ〜Ｓ２２ｎの処理までは、それぞれ第０〜第（Ｋ−１）ステージまでのパス集合を求める処理であり、複数の処理装置によって並列に処理される。パス計算部１２は、すべてのステージのパス集合の処理が終了したならば、ステップＳ１６の処理を行う。
【００６０】
ステップＳ１６の処理は、図２に示すステップＳ１６の処理と同様である。パス計算部１２は、ステップＳ１６の処理が終了すると、図５のパス計算処理を終了する。
第１の実施形態の変形例によれば、パス計算部１２の時間計算量のオーダは、ノード数ｎに依存するがステージ数Ｋには依存せず、Ｏ（ｎ4）となる。
【００６１】
（第１の実施形態の効果）
以上説明した第１の実施形態では、次の（Ａ），（Ｂ）のような効果がある。
【００６２】
（Ａ）  ネットワーク制御装置１は、パス計算処理に於いて、複数ステージを同時に最適化する問題を、各ステージ単独の最適化問題に変換して解いている。これにより、ネットワーク制御装置１は、この最適化問題の時間計算量のオーダの発散時間を遅らせて、通信ネットワーク９が大規模であっても適用可能としている。
【００６３】
（Ｂ）  ネットワーク制御装置１は、中間ステージの伝送パス５１の集合を算出する上で、障害復旧時の最終パス集合を反映している。これにより、ネットワーク制御装置１は、最終パス集合の伝送パス５１を速やかに復旧して固定することができるので、伝送パス５１の張り替えの発生頻度を抑制し、かつ、所定の疎通トラヒック量を確保することができる。
【００６４】
（第２の実施形態）
第２の実施形態のネットワーク制御装置１は、図１に示す第１の実施形態のネットワーク制御装置１と同様に構成されている。
第２の実施形態のパス計算部１２は、第１の実施形態とは異なり、初期パス集合を算出し、残余資源で復旧可能な初期パス集合の部分集合である初期パス部分集合を算出する。第２の実施形態のパス計算部１２の処理については、図６で詳細に説明する。
【００６５】
図６は、第２の実施形態に於けるパス計算処理を示すフローチャートである。図２に示す第１の実施形態のフローチャートと同一の要素には同一の符号を付与している。
第１の実施形態と同様にネットワーク情報収集部１１が通信ネットワーク９から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納すると、パス計算部１２は、パス計算処理を開始する。
【００６６】
ステップＳ１０は、図２に示すステップＳ１０と同様に、最終パス集合を算出する処理である。
ステップＳ１０Ａに於いて、パス計算部１２は、初期ステージ上で最大流問題の解である初期パス集合を算出する。この初期パス集合は、初期ステージかつ第０ステージ上にて、疎通トラヒック量を最大化する伝送パス５１の集合である。この初期パス集合は、各伝送パス５１の接続トポロジ情報と、各伝送パス５１の要求帯域の情報とを含んで構成される。
【００６７】
ステップＳ１１〜Ｓ１５に於いて、パス計算部１２は、第１の実施形態と同様に、第０ステージから第（Ｋ−１）ステージまでの処理を繰り返す。以下、繰り返しに係る各ステージの順番は、変数ｋで示す。
ステップＳ１２は、図２に示すステップＳ１２と同様に、最終パス部分集合を算出する処理である。
ステップＳ１２Ａに於いて、パス計算部１２は、初期パス集合のうち、この第ｋステージの残余資源で復旧可能な部分集合を算出する。ここで残余資源とは、第ｋステージのトポロジから最終パス部分集合の各伝送パス５１の要求帯域を減算したものである。この部分集合は、以下、初期パス部分集合と記載する。
【００６８】
ステップＳ１３に於いて、パス計算部１２は、残余資源上で最大流問題を解き、パス集合を算出する。ここで残余資源とは、第ｋステージのトポロジから最終パス部分集合と初期パス部分集合の各伝送パス５１の要求帯域を減算したものである。ここで算出したパス集合は、以下、第２残余資源パス集合と記載する。
ステップＳ１４に於いて、パス計算部１２は、算出した最終パス部分集合と、初期パス部分集合と、第２残余資源パス集合との和集合を算出し、この第ｋステージのパス集合とする。
【００６９】
ステップＳ１５に於いて、パス計算部１２は、第１の実施形態と同様に、第（Ｋ−１）ステージまでの処理を繰り返したか否かを判断する。パス計算部１２は、当該判断条件が成立しなかったならば、ステップＳ１１の処理に戻る。
ステップＳ１６は、図２に示すステップＳ１６と同様に、算出したパス集合をすべて出力する処理である。パス計算部１２は、ステップＳ１６の処理が終了すると、図６のパス計算処理を終了する。
このようにすることで、初期パス集合に含まれる伝送パス５１を優先して復旧することができるので、伝送パス５１の張り替え本数を更に減らすことができる。
【００７０】
図７（ａ），（ｂ）は、第２の実施形態に於ける初期ステージと最終ステージのパス集合を示す図である。図７（ａ）は、初期ステージに於ける初期パス集合５ｉを示している。図７（ｂ）は、最終ステージに於ける最終パス集合５ｚを示している。
図７（ａ）に示す通信ネットワーク９の初期ステージは、故障が発生した第０ステージを示している。通信ネットワーク９の伝送ノード３ｆは、障害を受けて停止している。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｇ，３ｂを相互に接続する各物理リンク４は停止する。更に、伝送ノード３ａと伝送ノード３ｇを接続する各物理リンク４は停止する。
初期パス集合５ｉは、伝送パス５１ｂ，５１ｃ，５１ｄ，５１ｆを含んでいる。初期パス集合５ｉは、伝送ノード３ａ，３ｂを接続するため、伝送パス５１ａを代替する伝送パス５１を含んでいる。初期ステージに於ける伝送パス５１の張り替え本数は、１本である。初期パス集合５ｉの伝送パス５１ｄと伝送パス５１ｆとは、同一の物理リンク４を共有するように設定されており、この物理リンク４の帯域を共有している。伝送パス５１ｂ，５１ｃは、独立した物理リンク４上に設定されている。
【００７１】
図７（ｂ）に示す通信ネットワーク９の最終ステージに於ける最終パス集合５ｚは、図３に示した通信ネットワーク９の最終パス集合５ｚと同様である。
【００７２】
図８（ａ）〜（ｃ）は、第２の実施形態に於ける各ステージの状態を示す図である。
図８（ａ）に示す第２の実施形態に於ける通信ネットワーク９の第０ステージの状態は、図７（ａ）に示す初期ステージと同様であり、かつ、図４（ａ）に示す第１の実施形態の状態と同様である。第０ステージに於ける伝送パス５１の張り替え本数は、１本である。第０ステージのパス集合の疎通トラヒック量は、３００Ｇｂｐｓとなる。
【００７３】
図８（ｂ）は、通信ネットワーク９の第１ステージの状態を示している。
図８（ｂ）に示すように、第１ステージに於いて、伝送ノード３ａと伝送ノード３ｇとを接続する各物理リンク４が復旧する。通信ネットワーク９の伝送ノード３ｆは、障害を受けて停止している。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｇ，３ｂを相互に接続する各物理リンク４は停止する。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚのうち、この第１ステージで復旧可能な部分集合を算出する。この最終パス部分集合は、伝送パス５１ｂ，５１ｃ，５１ｄである。
【００７４】
次に、パス計算部１２は、最終パス部分集合を復旧したのち、初期パス集合５ｉのうち、残余資源上で復旧可能な部分集合を算出する。この初期パス部分集合は、伝送パス５１ｆである。
パス計算部１２は更に、残余資源上で最大流問題を解き、第２残余資源パス集合を算出する。この第２残余資源パス集合は、伝送パス５１ｅである。すなわち、パス計算部１２は、この第１ステージに於いて、転送ノード２ａ，２ｄを接続する伝送パス５１ｅを新たに設定する。
最終パス部分集合である伝送パス５１ｂ，５１ｃ，５１ｄと、初期パス部分集合である伝送パス５１ｆと、第２残余資源パス集合である伝送パス５１ｅとの和集合が、この第１ステージのパス集合となる。
第１ステージに於ける伝送パス５１の張り替え本数は、１本である。第１ステージのパス集合の疎通トラヒック量は、４００Ｇｂｐｓとなる。
【００７５】
図８（ｃ）は、通信ネットワーク９の第２ステージの状態を示している。この第２ステージは、故障していた物理資源がすべて復旧した最終ステージである。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚをすべて復旧可能である。この最終パス集合５ｚは、伝送パス５１ａ，５１ｂ，５１ｃ，５１ｄ，５１ｅである。
この第２ステージに於いて、太い破線で示す伝送パス５１ａは、転送ノード２ａ，２ｄを接続するために新たに設定される。第２ステージに於ける伝送パス５１の張り替え本数は、１本である。第２ステージのパス集合の疎通トラヒック量は、５００Ｇｂｐｓとなる。
図８（ｃ）に示すように、第２の実施形態のパス計算処理は、図４（ｃ）に示す第１の実施形態のパス計算処理と比較して、同等の疎通トラヒック量を達成しつつ、伝送パス５１の張り替え本数を抑制することができる。
【００７６】
第２の実施形態に於いて、中間ステージのパス集合は、最終ステージの伝送パス５１で固定されるだけでなく、初期ステージの伝送パス５１でも固定される。そのため、第１の実施形態よりも、伝送パス５１の張り替えの発生頻度が、更に抑制される。
ただし、初期ステージに於ける初期パス集合は、最大流問題の最適解であるという保証は無いため、第１の実施形態と比較して、疎通トラヒック量が低下する虞がある。
すなわち、通信ネットワーク９の管理者は、疎通トラヒック量の増加を優先する際には第１の実施形態の技術を用い、伝送パス５１の張り替えの発生頻度の抑制を優先する場合には第２の実施形態の技術を用いることが考えられる。
【００７７】
伝送パス５１の張り替えの発生頻度の抑制を優先する第１の理由は、伝送パス５１の張り替えにより信号遅延が発生する虞があるためである。例えば、通信ネットワーク９に、動画ストリーミングコンテンツなどに代表されるリアルタイム性の高いトラヒックが流れているときには、信号遅延によって、動画ストリーミングコンテンツの再生が途切れる虞がある。
第２の理由は、伝送パス５１の張り替えにあたって、手作業による設定が必要となる場合があるためである。これにより、新たな作業工数が発生する虞がある。
第３の理由は、伝送パス５１の張り替えは、通信ネットワーク９にインパクトを与え、よって予期しなかった不具合が発生する虞があるためである。
【００７８】
（第２の実施形態の効果）
以上説明した第２の実施形態では、次の（Ｃ）のような効果がある。
（Ｃ）  パス計算部１２は、中間ステージに於けるパス集合である伝送パス５１の構成を計算する上で、障害から復旧した際の最終パス集合を反映したのち、障害発生時の初期パス集合を反映する。これにより、最終パス集合の伝送パス５１を速やかに復旧して固定すると共に、初期パス集合の伝送パス５１を可能な限り長く固定することができるので、伝送パス５１の張り替えの発生頻度を更に抑制することができる。
【００７９】
（第３の実施形態）
第１、第２の実施形態のパス計算処理では、同一の始点と終点との間に複数の伝送パスが設定される場合がある。第３の実施形態のパス計算処理は、運用ポリシなどにより、同一始終点間に複数の伝送パスが設定されることを許容しない場合のものである。これにより、通信ネットワーク９の伝送パス５１の構成を単純化することができる。
【００８０】
図９は、第３の実施形態に於けるパス計算処理を示すフローチャートである。図６に示す第２の実施形態のフローチャートと同一の要素には同一の符号を付与している。
第２の実施形態と同様にネットワーク情報収集部１１が通信ネットワーク９から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納すると、パス計算部１２は、パス計算処理を開始する。
ステップＳ１０は、図６に示すステップＳ１０と同様に、最終パス集合を算出する処理である。
ステップＳ１０Ａは、図６に示すステップＳ１０Ａと同様に、初期パス集合を算出する処理である。
【００８１】
ステップＳ１１〜Ｓ１４，Ｓ３０〜Ｓ３３，Ｓ１５に於いて、パス計算部１２は、第２の実施形態と同様に、第０ステージから第（Ｋ−１）ステージまでの処理を繰り返す。
ステップＳ１２〜Ｓ１４の処理は、図６に示すステップＳ１２〜Ｓ１４の処理と同様である。ステップＳ１４の処理が終了すると、パス計算部１２は、ステップＳ３０の処理を行う。
ステップＳ３０〜Ｓ３３に於いて、パス計算部１２は、ステップＳ１４で算出したパス集合のすべての始終点の組合せを繰り返す。
ステップＳ３１に於いて、パス計算部１２は、現在の始終点の組合せが複数の伝送パス５１によって接続されているか否かを判断する。パス計算部１２は、当該判断条件が成立したならば（Ｙｅｓ）、ステップＳ３２の処理を行い、当該判断条件が成立しなかったならば（Ｎｏ）、ステップＳ３３の処理を行う。
【００８２】
ステップＳ３２に於いて、パス計算部１２は、現在の始終点の組合せを接続する複数の伝送パス５１のうち、疎通トラヒック量が最大となるものを採用する。パス計算部１２は、それ以外の伝送パス５１を削除する。
ステップＳ３３に於いて、パス計算部１２は、ステップＳ１４で算出したパス集合のすべての始終点の組合せを繰り返したか否かを判断する。パス計算部１２は、当該判断条件が成立しなかったならば、ステップＳ３０の処理に戻る。
ステップＳ１５に於いて、パス計算部１２は、第２の実施形態と同様に、第（Ｋ−１）ステージまでの処理を繰り返したか否かを判断する。パス計算部１２は、当該判断条件が成立しなかったならば、ステップＳ１１の処理に戻る。
ステップＳ１６は、図２に示すステップＳ１６と同様に、算出したパス集合をすべて出力する処理である。パス計算部１２は、ステップＳ１６の処理が終了すると、図９のパス計算処理を終了する。
このパス計算処理によれば、始点と終点との組合せが、複数の伝送パス５１で接続されていたならば、複数の伝送パス５１のうち最大の疎通トラヒック量のものだけを採用し、それ以外のものを削除する、このようにすることで、各伝送ノード３は、設定が単純化されるので、不具合の発生を未然に防止することができる。
【００８３】
図１０（ａ）〜（ｃ）は、第３の実施形態に於ける各ステージの状態を示す図である。
図１０（ａ）に示す第３の実施形態に於ける通信ネットワーク９の第０ステージの状態は、図８（ａ）に示す第２の実施形態の状態と同様である。第０ステージに於ける伝送パス５１の張り替え本数は、１本である。第０ステージのパス集合の疎通トラヒック量は、３００Ｇｂｐｓとなる。
【００８４】
図１０（ｂ）は、通信ネットワーク９の第１ステージの状態を示している。
図１０（ｂ）に示すように、第１ステージに於いて、伝送ノード３ａと伝送ノード３ｇとを接続する各物理リンク４が復旧する。通信ネットワーク９の伝送ノード３ｆは、障害を受けて停止している。伝送ノード３ｆの停止により、この伝送ノード３ｆと伝送ノード３ａ，３ｇ，３ｂを相互に接続する各物理リンク４は停止する。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚ（図３参照）のうち、この第１ステージで復旧可能な部分集合を算出する。この最終パス部分集合は、伝送パス５１ｂ，５１ｃと、伝送パス５１ｄ（図８（ｂ）参照）とである。なお、伝送パス５１ｄは、図１０（ｂ）には図示されていない。
次に、パス計算部１２は、最終パス部分集合を復旧したのち、初期パス集合５ｉのうち、残余資源上で復旧可能な部分集合を算出する。この初期パス部分集合は、第２の実施形態と同様に伝送パス５１ｆである。
【００８５】
パス計算部１２は、残余資源上で最大流問題を解き、第２残余資源パス集合を算出する。この第２残余資源パス集合は、第２の実施形態と同様に伝送パス５１ｅである。すなわち、パス計算部１２は、この第１ステージに於いて、伝送パス５１ｅを新たに設定する。
第３の実施形態では更にパス計算部１２は、同一の始点と終点との間が、複数の伝送パス５１で接続されていたならば、疎通トラヒック量が最大の伝送パス５１を採用する。ここでは、転送ノード２ａ，２ｄ間が、図８（ｂ）に示した伝送パス５１ｄ，５１ｅで接続される。伝送パス５１ｄの疎通トラヒック量は、５０Ｇｂｐｓである。伝送パス５１ｅの疎通トラヒック量は、１００Ｇｂｐｓである。よって、パス計算部１２は、疎通トラヒック量が最大となる伝送パス５１ｅを採用し、それ以外の伝送パス５１ｄ（図８（ｂ）参照）を削除する。
この第１ステージのパス集合は、伝送パス５１ｂ，５１ｃ，５１ｅ，５１ｆである。第１ステージに於ける伝送パス５１の張り替え本数は、１本である。第１ステージのパス集合の疎通トラヒック量は、４００Ｇｂｐｓとなる。
【００８６】
図１０（ｃ）は、通信ネットワーク９の第２ステージの状態を示している。この第２ステージは、故障していた物理資源がすべて復旧した最終ステージである。
このとき、ネットワーク制御装置１のパス計算部１２は、最終パス集合５ｚをすべて復旧可能である。この最終パス集合５ｚは、伝送パス５１ａ，５１ｂ，５１ｃ，５１ｄ，５１ｅである。
この第２ステージに於いて、破線で示す伝送パス５１ａ，５１ｄは、新たに設定される。第２ステージに於ける伝送パス５１の張り替え本数は、２本である。第２ステージのパス集合の疎通トラヒック量は、５００Ｇｂｐｓとなる。
【００８７】
以上説明した第３の実施形態によれば、各ステージに於いて、単一の始終点間に単一の伝送パス５１の設定のみを許容している。これにより、各伝送ノード３は、設定が単純化されるので、不具合を未然に防止することができ、よって、通信ネットワーク９の運用性を向上することができる。
【００８８】
（第４の実施形態）
第４の実施形態のネットワーク制御装置１は、図１に示す第１の実施形態のネットワーク制御装置１と同様に構成されている。
【００８９】
第４の実施形態のパス計算部１２は、第２の実施形態とは異なり、初期パス集合に換えて、直前のステージに於けるパス集合が、残余資源で復旧可能な直前パス部分集合を算出する。それ以外は、第４の実施形態のパス計算部１２は、第２の実施形態と同様に動作する。第４の実施形態のパス計算部１２の処理は、図１１で詳細に説明する。
【００９０】
図１１は、第４の実施形態に於けるパス計算処理を示すフローチャートである。図６に示す第２の実施形態のフローチャートと同一の要素には同一の符号を付与している。
第２の実施形態と同様にネットワーク情報収集部１１が通信ネットワーク９から網トポロジ情報を取得して網トポロジ記憶部１４に格納し、通信ネットワーク９からトラヒック情報を取得してトラヒック記憶部１５に格納すると、パス計算部１２は、パス計算処理を開始する。
【００９１】
ステップＳ１０は、図６に示すステップＳ１０と同様に、最終パス集合を算出する処理である。
ステップＳ１０Ａは、図６に示すステップＳ１０Ａと同様に、初期パス集合を算出する処理である。
ステップＳ１１〜Ｓ１５に於いて、パス計算部１２は、第２の実施形態と同様に、第０ステージから第（Ｋ−１）ステージまでの処理を繰り返す。以下、繰り返しに係る各ステージの順番は、変数ｋで示す。
ステップＳ１２の処理は、図６に示すステップＳ１２の処理と同様である。パス計算部１２は、ステップＳ１２の処理が終了すると、ステップＳ４０の処理を行う。
ステップＳ４０に於いて、パス計算部１２は、現在のステージが第０ステージであるか否かを判断する。パス計算部１２は、当該判断条件が成立したならば（Ｙｅｓ）、ステップＳ１２Ａの処理を行い、当該判断条件が成立しなかったならば（Ｎｏ）、ステップＳ４１の処理を行う。
【００９２】
ステップＳ１２Ａの処理は、図６に示すステップＳ１２Ａの処理と同様である。パス計算部１２は、ステップＳ１２Ａの処理が終了すると、ステップＳ１３の処理を行う。
ステップＳ４１に於いて、パス計算部１２は、前回のステージである第（ｋ−１）ステージのパス集合のうち、残余資源で復旧可能な部分集合（直前パス部分集合）を算出する。パス計算部１２は、ステップＳ４１の処理が終了すると、ステップＳ１３の処理を行う。
ステップＳ１３に於いて、パス計算部１２は、第２実施形態と同様に、残余資源上で最大流問題を解き、パス集合を算出する。ここで残余資源とは、第ｋステージのトポロジから最終パス部分集合と直前パス部分集合の各伝送パス５１の要求帯域を減算したものである。ここで算出したパス集合は、以下、第３残余資源パス集合と記載する。
ステップＳ１４に於いて、パス計算部１２は、算出した最終パス部分集合と、直前パス部分集合と、第３残余資源パス集合との和集合を算出し、この第ｋステージのパス集合とする。
ステップＳ１５に於いて、パス計算部１２は、第２の実施形態と同様に、第（Ｋ−１）ステージまでの処理を繰り返したか否かを判断する。パス計算部１２は、当該判断条件が成立しなかったならば、ステップＳ１１の処理に戻る。
ステップＳ１６は、図６に示すステップＳ１６と同様に、算出したパス集合をすべて出力する処理である。パス計算部１２は、ステップＳ１６の処理が終了すると、図１１のパス計算処理を終了する。
このようにすることで、直前のステージのパス集合に含まれる伝送パス５１を優先して復旧することができるので、伝送パス５１の張り替え本数を、第２の実施形態よりも更に減らすことができる。
【００９３】
（変形例）
第１〜第４の実施形態に係るネットワーク制御装置１は、前記したような処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体に記憶して提供することが可能である。また、そのプログラムを、インターネットなどのネットワークを通して提供することも可能である。
本発明は、上記実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で、変更実施が可能であり、例えば、次の（ａ）〜（ｅ）のようなものがある。
【００９４】
（ａ）  第１〜第４の実施形態に於いて、パス計算部１２は、最終ステージを、すべての物理資源が復旧されたステージと定義してパス計算処理を行っている。しかし、これに限られず、パス計算部１２は、いずれかの物理資源が復旧されていない中間状態であっても、これを最終ステージと定義してパス計算処理を行ってもよい。パス計算部１２は、同様に、最終ステージ以前の任意の中間ステージを初期ステージと定義して、パス計算処理を行ってもよい。
【００９５】
（ｂ）  第２、第３の実施形態に於いて、ネットワーク制御装置１は、第１の実施形態の変形例と同様に、パス計算処理をステージごとに並行処理してもよい。これにより、パス計算処理を高速化することができる。
【００９６】
（ｃ）  第１〜第４の実施形態に於いて、パス計算部１２は、ヒューリスティックアルゴリズムであるエドモンズ・カープ法を用いて最大流問題を解いている。しかし、これに限られず、パス計算部１２は、フォード・ファルカーソン法、ディニッツ法、汎用プッシュ再ラベル法、などの任意の方法を用いて、最大流問題を解いてもよい。
【００９７】
（ｄ）  第１〜第４の実施形態に於いて、ネットワーク制御装置１は、制御プレーンを介して物理ノードと接続されている。しかし、これに限られず、ネットワーク制御装置１は、管理情報転送プレーン（Management−Plane）を介して、各物理ノードと接続されていてもよい。
【００９８】
（ｅ）  第２の実施形態に於いて、パス計算部１２は、最終パス集合のうち各ステージで復旧可能な部分集合を算出して、初期パス集合のうち残余資源で復旧可能な部分集合を算出している。しかし、これに限られず、パス計算部１２は、初期パス集合のうち各ステージで復旧可能な部分集合を算出したのちに、最終パス集合のうち残余資源で復旧可能な部分集合を算出してもよい。これにより、パス計算部１２は、物理資源の復旧が進んでいない最初のステージに於いて、伝送パス５１の張り替え頻度を更に抑制することができる。
【符号の説明】
【００９９】
１，１Ｄ  ネットワーク制御装置
１１  ネットワーク情報収集部
１２  パス計算部
１３  パス設定部
１４  網トポロジ記憶部
１５  トラヒック記憶部
１６  パス記憶部
１７  物理資源復旧順序記憶部
２，２ａ〜２ｄ  転送ノード  （物理ノードかつ物理資源）
３，３ａ〜３ｇ  伝送ノード  （物理ノードかつ物理資源）
４  物理リンク  （物理資源）
５ｉ  初期パス集合
５ｚ  最終パス集合
５１，５１ａ〜５１ｇ  伝送パス
６  物理レイヤ
７  パケットレイヤ
７１，７１ｂ，７１ｃ，７１ｄ  論理リンク
９  通信ネットワーク
【図１】
2014236364.tif 000003
【図２】
2014236364.tif 000004
【図３】
2014236364.tif 000005
【図４】
2014236364.tif 000006
【図５】
2014236364.tif 000007
【図６】
2014236364.tif 000008
【図７】
2014236364.tif 000009
【図８】
2014236364.tif 000010
【図９】
2014236364.tif 000011
【図１０】
2014236364.tif 000012
【図１１】
2014236364.tif 000013
【図１２】
2014236364.tif 000014
【図１３】
2014236364.tif 000015
【図１４】
2014236364.tif 000016