(57)【要約】【課題】リンク故障回数ごとの経路再計算が必要になる故障パターン数を効率良く計算する。【解決手段】削除部１２は、ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する。また、パターン数加算部１３は、削除部１２によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの故障パターン数を合計する。【選択図】図４
2017108300.tif 000002
【特許請求の範囲】
【請求項１】
ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する削除部と、
前記削除部によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの削除のパターン数を合計するパターン数加算部と、
を有することを特徴とするリンク故障パターン数計算システム。
【請求項２】
トポロジごとに、該トポロジを生成可能なリンクの削除のパターン数を記憶するパターン記憶部と、
前記削除部によってトポロジが生成されるたびに、前記全てのノードがリンクを有する同一種類のトポロジの数と、前記パターン記憶部に記憶されている前記削除部によってリンクが削除される前のトポロジの削除のパターン数とをかけ、該生成されたトポロジが前記パターン記憶部に記憶されている場合、該かけた数を、該生成されたトポロジの削除のパターン数に加算し、該生成されたトポロジが前記パターン記憶部に記憶されていない場合、該かけた数を該生成されたトポロジの削除のパターン数として前記パターン記憶部に記憶させるパターン更新部をさらに有することを特徴とする請求項１に記載のリンク故障パターン数計算システム。
【請求項３】
前記パターン記憶部は、トポロジごとに、該トポロジを生成可能なリンクの削除のパターン数の、該トポロジが前記削除部によってリンクを削除される前のトポロジを生成可能なリンクの削除のパターン数に対する割合である故障パターン割合をさらに記憶し、
前記パターン更新部は、前記削除部によってトポロジが生成されるたびに、前記全てのノードがリンクを有する同一種類のトポロジの数を、前記パターン記憶部に記憶されている前記削除部によってリンクが削除される前のトポロジの削除のパターン数で割った数を、前記削除部によってリンクが削除される前のトポロジの故障パターン割合にかけ、該生成されたトポロジが前記パターン記憶部に記憶されている場合、該かけた数を、該生成されたトポロジの故障パターン割合に加算し、該生成されたトポロジが前記パターン記憶部に記憶されていない場合、該かけた数を該生成されたトポロジの故障パターン割合として前記パターン記憶部に記憶させることを特徴とする請求項２に記載のリンク故障パターン数計算システム。
【請求項４】
前記削除部は、入力されたトポロジのうち、該トポロジの生成までに削除したリンクの削除数が多いトポロジから順にリンクの削除を行うことを特徴とする請求項１から３のいずれか１項に記載のリンク故障パターン数計算システム。
【請求項５】
前記削除部は、入力されたトポロジのうち、該トポロジの生成までに削除したリンクの削除数が少ないトポロジから順にリンクの削除を行うことを特徴とする請求項１から３のいずれか１項に記載のリンク故障パターン数計算システム。
【請求項６】
ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する削除工程と、
前記削除工程によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの削除のパターン数を合計するパターン数加算工程と、
を含んだことを特徴とするリンク故障パターン数計算方法。
【請求項７】
コンピュータを、請求項１から５のいずれか１項に記載のリンク故障パターン数計算システムとして機能させるためのリンク故障パターン数計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リンク故障パターン数計算システム、リンク故障パターン数計算方法およびリンク故障パターン数計算プログラムに関する。
【背景技術】
【０００２】
例えば故障等により、複数のルータによって構成されるネットワークのトポロジが変化するとき、ルータは、最新のトポロジに基づきパケットを転送するよう経路を再計算することが必要になる場合がある。このとき、全ルータの経路情報が更新されるまでの間、ループやパケットドロップが生じるため、通信品質は大きく悪化することになる。
【０００３】
そこで、経路の再計算が行われる場合に、あらかじめ設定されたバックアップＭＰＬＳ（Multi-Protocol  Label  Switching）トンネルに経路を切り替えることで経路の更新時間を削減する技術として、ＦａｓｔＲｅｒｏｕｔｅが知られている。
【０００４】
さらに、全ての故障パターンに対応するためには、膨大な数のトンネルを用意することが必要になるというＦａｓｔＲｅｒｏｕｔｅの持つ課題を解決するための技術として、ネクストホップの切り替えのみでパケット転送を続行する方法が知られている（例えば、非特許文献１）。
【０００５】
非特許文献１の方法では、リンクの故障等により物理トポロジが変化した場合に、ネクストホップ（ＮＨ）の切り替えによりパケット転送を続行できるか否かを、物理トポロジを基に作成した論理トポロジを用いて判定する。このとき、物理トポロジは変化するが、論理トポロジには変更が生じず、ＮＨの切り替えによりパケット転送を続行できると判定された場合、各ルータはＮＨを切り替えることでパケット転送を継続する。一方、論理トポロジに変更が生じる場合、ルータは経路の再計算を行う。
【０００６】
このように、経路の再計算の要否を判定し、必要に応じて再計算を行う場合、ネットワークの設計を行う際に、故障リンク数ごとの経路再計算発生確率、および故障リンク数ごとの経路再計算発生確率に基づいて計算される平均リンク故障回数を知っておくことが重要である。ここで、故障リンク数ごとの経路再計算発生確率は、全体の故障パターン数に対する、リンク故障回数ごとの経路再計算が必要になる故障パターン数を計算することで求められる。
【０００７】
経路再計算が必要になる故障パターン数の計算方法として、具体的には以下の方法が知られている。まず、実際のネットワークトポロジの論理ネットワークトポロジから隣接する論理ノード間を結ぶ物理リンクの構成を取得する。次に、決められた順番で物理リンクを削除していき、経路の再計算が必要になったときのリンク削除回数を計測する。そして、これらの手順を考えられる全ての順番に対し行うことで、リンク故障回数ごとの経路再計算が必要になる故障パターン数を求める。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】杉園  幸司、福岡  亜希、山崎  裕史、山本  太三  "経路再計算の回避を考慮したパケット転送方法に関する提案"  電子情報通信学会全国大会  2015年3月
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来の方法には、リンク故障回数ごとの経路再計算が必要になる故障パターン数を効率良く計算することができないという問題があった。
【００１０】
例えば、従来の方法でリンク故障回数ごとの経路再計算が必要になる故障パターン数を計算する場合、リンク数が増加するにしたがって、計算時間が急激に増大し、計算の効率も急激に悪化する。これは、全ての故障パターンがリンク数の階乗だけ存在するためである。
【課題を解決するための手段】
【００１１】
本発明のリンク故障パターン数計算システムは、ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する削除部と、前記削除部によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの削除のパターン数を合計するパターン数加算部と、を有することを特徴とする。
【００１２】
また、本発明のリンク故障パターン数計算方法は、ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する削除工程と、前記削除工程によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの削除のパターン数を合計するパターン数加算工程と、を含んだことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、リンク故障回数ごとの経路再計算が必要になる故障パターン数を効率良く計算することができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、ネットワークについて説明するための図である。
【図２】図２は、リンクの故障について説明するための図である。
【図３】図３は、全てのリンク故障パターン数について説明するための図である。
【図４】図４は、第１の実施形態に係るリンク故障パターン数計算システムの構成の一例を示す図である。
【図５】図５は、同じトポロジになる故障パターンについて説明するための図である。
【図６】図６は、パターン記憶部に保存されるデータについて説明するための図である。
【図７】図７は、異なるトポロジになる故障パターンについて説明するための図である。
【図８】図８は、トポロジＧ１について説明するための図である。
【図９】図９は、トポロジＧ２について説明するための図である。
【図１０】図１０は、パターン記憶部に保存されるデータについて説明するための図である。
【図１１】図１１は、経路の再計算が必要な故障パターンについて説明するための図である。
【図１２】図１２は、パターン記憶部に保存されるデータについて説明するための図である。
【図１３】図１３は、第１の実施形態に係るリンク故障パターン数計算システムの処理の流れを示すフローチャートである。
【図１４】図１４は、第２の実施形態について説明するための図である。
【図１５】図１５は、第２の実施形態について説明するための図である。
【図１６】図１６は、第３の実施形態について説明するための図である。
【図１７】図１７は、第３の実施形態に係るリンク故障パターン数計算システムの処理の流れを示すフローチャートである。
【図１８】図１８は、プログラムが実行されることにより、リンク故障パターン数計算システムが実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下に、本願に係るリンク故障パターン数計算システムの実施形態を図面に基づいて詳細に説明する。なお、この実施形態により本発明が限定されるものではない。また、各実施形態は適宜組み合わせることができる。
【００１６】
［第１の実施形態］
まず、第１の実施形態に係るポリシ制御システムおよびポリシ制御装置の構成、処理の流れおよび効果を説明する。
【００１７】
まず、本実施形態で対象とするネットワークおよびリンクの故障について説明する。まず、図１に示すように、ネットワーク１００の論理トポロジは、ルータの集合である論理ノード（ＬＮ）と論理リンクにより構成される。図１は、ネットワークについて説明するための図である。
【００１８】
ここで、ルータ間にリンクが存在する場合、すなわちルータ同士が隣接関係にある場合、各ルータが属する論理ノード間に論理リンクが存在する。このとき、これらの論理ノードは隣接しているという。
【００１９】
ここで、各ルータは下記の性質を持つものとする。
・ルータが属する論理ノードに隣接する全ての論理ノードに隣接ルータを持つ。
・ルータが属する論理ノードに隣接しない論理ノードに隣接ルータを持たない。
（ただし、同一論理ノードに属するルータ同士が隣接関係にある場合を許容する。）
【００２０】
図１に示すように、論理ノード１１０に属するルータ１１１〜１１３は、論理ノード１２０および１３０に属するルータへのリンクを持っている。また、論理ノード１２０に属するルータ１２１〜１２３は、論理ノード１１０に属するルータへのリンクを持っている。また、論理ノード１３０に属するルータ１３１〜１３３は、論理ノード１１０に属するルータへのリンクを持っている。
【００２１】
このとき、例えばルータ１１１とルータ１２１の間にリンクが存在しているため、ルータ１１１とルータ１２１は隣接しているといえ、論理ノード１１０と論理ノード１２０についても隣接しているといえる。同様に論理ノード１１０と論理ノード１３０についても隣接しているといえる。
【００２２】
ここで、図２に示すように、例えばルータ１１１とルータ１２１の間のリンクが故障した場合、論理ノード１１０と論理ノード１２０が隣接しないことになり、経路の再計算が必要になる。図２は、リンクの故障について説明するための図である。このように、特定の隣接論理ノード間を結ぶリンクの接続状況に着目し、論理トポロジの条件が崩れるようなリンク故障の発生パターンに着目することで、経路の再計算が生じるリンク故障回数の確率を計算できる。
【００２３】
ただし、このような故障の発生パターンは、例えば図３に示すようにリンク数の階乗だけ存在するため、膨大な計算時間がかかる場合がある。図３は、全てのリンク故障パターン数について説明するための図である。例えば、図３に示すように、リンクの数が９である場合、９！通りの故障パターンが存在する。そこで、本実施形態では、全パターンに着目することなくリンク故障回数ごとの経路再計算が必要になる故障パターン数を計算する。
【００２４】
［第１の実施形態の構成］
まず、図４を用いて第１の実施形態に係るリンク故障パターン数計算システムの構成について説明する。図４は、第１の実施形態に係るリンク故障パターン数計算システムの構成の一例を示す図である。
【００２５】
図４に示すように、リンク故障パターン数計算システム１は、制御部１０および記憶部２０を有する。また、制御部１０は、取得部１１、削除部１２、パターン数加算部１３およびパターン更新部１４を有する。また、記憶部２０は、パターン記憶部２１およびパターン数記憶部２２を有する。
【００２６】
まず、図５に示すように、隣接論理ノードへのリンクを３本持つルータ１１１〜１１３が存在する論理ノード１１０において、各ルータを同等なものとして扱うとすると、ルータ１１１からのリンクが１本切れた場合、ルータ１１２からのリンクが１本切れた場合、ルータ１１３からのリンクが１本切れた場合のいずれの場合においても、ネットワークは同じ状態になる。図５は、同じトポロジになる故障パターンについて説明するための図である。
【００２７】
このとき、論理ノード１１０には、隣接論理ノードへのリンクを３本持つルータが２つ、隣接論理ノードへのリンクを２本持つルータが１つ存在することになる。これより、図３の例のように、経路再計算が必要になる故障パターン数を計算する際に、常に全ての発生順を考慮する必要はないということがいえる。
【００２８】
図６〜１２を用いて、リンク故障パターン数計算システム１による故障パターン数の計算について説明する。まず、リンク故障パターン数計算システム１は、図６に示すようなデータをパターン記憶部２１に保存する。図６は、パターン記憶部に保存されるデータについて説明するための図である。
【００２９】
具体的に、まず、取得部１１は、初期状態となるトポロジを取得する。図６の例では、初期状態のトポロジにおいては、入側論理ノードに属するノードが３つ、出側論理ノードに属するノードが３つ存在し、入側論理ノードに属するノードと出側論理ノードに属するノードの間はフルメッシュ接続されている。このとき、初期状態のトポロジ故障パターン数を１、故障リンク数を０とする。
【００３０】
なお、トポロジ故障パターン数とは、リンク故障の結果、当該トポロジになりうるリンク故障パターンの数である。また、故障リンク数とは、当該トポロジになるまでに故障したリンクの数である。また、トポロジと、トポロジ故障パターン数および故障リンク数をセットにしたデータがパターン記憶部２１に保存される。
【００３１】
削除部１２は、ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する。また、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについては、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとしてパターン記憶部２１に記憶されているため、削除部１２は、このようなトポロジを同一種類のトポロジとして各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する。
【００３２】
上述のように、削除部１２は、初期状態のトポロジにおけるリンクを削除することで、リンクが故障した結果生じるトポロジを計算する。このとき、故障するリンクにより結果は異なるので、削除部１２は、各リンクを削除した場合についてトポロジを計算する。図６の例では、初期状態のトポロジにはリンクが９本存在するため、削除部１２は、９種類のトポロジを計算する。また、削除部１２は、計算が完了したトポロジのデータをパターン記憶部２１から削除する。ここでは、削除部１２は、初期状態のトポロジのデータをパターン記憶部２１から削除する。
【００３３】
ただし、これら９種類のトポロジは、図５を用いて説明した通り、同じトポロジである。すなわち、初期状態のトポロジにおけるノードをナンバリングし、リンク故障の結果生じるトポロジのノード番号を入れ替えると全て同じトポロジになる。よって、初期状態からリンク故障が起こった場合、常に同じトポロジになる。
【００３４】
以降の説明でも、ノードの番号を入れ替えることで同じトポロジになるトポロジは、同じトポロジであるとする。
【００３５】
また、パターン記憶部２１は、トポロジごとに、該トポロジを生成可能なリンクの削除のパターン数である故障パターン数を記憶する。そして、パターン更新部１４は、削除部１２によってトポロジが生成されるたびに、全てのノードがリンクを有する同一種類のトポロジの数と、パターン記憶部２１に記憶されている削除部１２によってリンクが削除される前のトポロジの故障パターン数とをかけ、該生成されたトポロジがパターン記憶部２１に記憶されている場合、該かけた数を、該生成されたトポロジの故障パターン数に加算し、該生成されたトポロジがパターン記憶部２１に記憶されていない場合、該かけた数を該生成されたトポロジの故障パターン数としてパターン記憶部２１に記憶させる。
【００３６】
具体的に、パターン更新部１４は、ここで得られたトポロジＧ０の故障パターン数を９、故障リンク数を１としてパターン記憶部２１に保存する。なお、トポロジＧ０は経路の再計算が必要になるパターンではないため、パターン数加算部１３は処理を行わない。
【００３７】
図６の場合、初期状態のトポロジから生じるトポロジはＧ０のみであったが、図７に示すように１つのトポロジから複数の異なるトポロジが生じる場合もある。図７は、異なるトポロジになる故障パターンについて説明するための図である。
【００３８】
取得部１１は、パターン記憶部２１から、故障リンク数が最も小さいデータを取得する。このとき、パターン記憶部２１に保存されているのはＧ０のデータのみであるため、取得部１１はＧ０を取得する。なお、パターン記憶部２１に故障リンク数が最も小さいデータが複数存在する場合、取得部１１は、任意のデータを取得する。
【００３９】
そして、削除部１２は、トポロジＧ０のリンクを削除し、トポロジを計算する。このとき、削除部１２は、計算の結果、トポロジＧ１およびＧ２を得る。トポロジＧ０からトポロジＧ１およびＧ２となるリンク故障のパターンはそれぞれ４通りである。なお、トポロジＧ１およびＧ２はいずれも経路の再計算が必要になるパターンではないため、パターン数加算部１３は処理を行わない。
【００４０】
図８を用いて、トポロジＧ１について説明する。図８は、トポロジＧ１について説明するための図である。まず、図８においては、説明のため、各ノードに番号を振り、またノードの位置を変化させる。図８において、トポロジＧ１となるパターンは、リンク１−６、リンク２−６、リンク３−４およびリンク３−５のいずれかが故障した場合である。なお、例えばノード１および６の間のリンクをリンク１−６と表す。
【００４１】
図８では、最下部にリンク１−６が故障した結果生じるトポロジを例として示す。仮に、最下部に示すトポロジをＧ１とする。ここで、リンク２−６が故障した場合に生じたトポロジのノード１と２の番号を入れ替えると、当該トポロジはトポロジＧ１と一致する。また、リンク３−４が故障した場合に生じたトポロジのノード３と６、ノード２と５、ノード１と４を入れ替えると、当該トポロジはトポロジＧ１と一致する。また、リンク３−５が故障した場合に生じたトポロジのノード３と６、ノード１と５、ノード２と４を入れ替えると、当該トポロジはトポロジＧ１と一致する。これより、リンク故障が生じた結果、トポロジＧ１になるリンク故障パターンは４通り存在することがわかる。
【００４２】
このとき、パターン更新部１４は、リンク削除後のトポロジと同じトポロジのデータがパターン記憶部２１に保存されていないかを確認し、保存されていない場合は、当該トポロジについてのデータをパターン記憶部２１に保存する。また、保存されている場合は、保存済みのデータの故障パターン数を加算する。
【００４３】
図８の例では、まず、削除部１２によりリンク１−６が故障したトポロジＧ１が計算されると、パターン更新部１４は、トポロジをＧ１、故障パターン数を９、故障リンク数を２としたデータをパターン記憶部２１に保存する。次に、削除部１２によりリンク１−５が故障したトポロジＧ１が計算されると、パターン更新部１４は、故障パターン数９を保存済みのデータの故障パターン数に加算する。
【００４４】
図１０に示すように、各故障パターンについて同様の処理を繰り返すと、パターン記憶部２１に保存されているトポロジＧ１の故障パターン数は３６となる。また、図９に示すように、トポロジＧ２についてもトポロジＧ１の場合と同様の処理が行われる。図９は、トポロジＧ２について説明するための図である。
【００４５】
取得部１１は、さらにパターン記憶部２１からトポロジＧ１のデータを取得する。そして、削除部１２は、リンクを削除する。このとき、図１１に示すように、トポロジＧ１からリンクを削除すると、出力リンク数が０であるノードが生じる場合がある。このような故障パターンが、経路再計算が必要になる故障パターンである。
【００４６】
また、パターン数加算部１３は、削除部１２によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数、すなわち故障リンク数ごとに、該トポロジを生成可能なリンクの故障パターン数を合計して保存する。
【００４７】
具体的に、パターン数加算部１３は、パターン数記憶部２２に、故障リンク数３と故障パターン数３６を対応付けて保存する。また、パターン数加算部１３は、既にパターン数記憶部２２に故障リンク数３と対応する故障パターン数が保存されている場合は、故障パターン数に３６を加算する。パターン数記憶部２２は、故障リンク数と故障パターン数を、例えば配列として記憶する。この場合、パターン数記憶部２２は、例えば故障リンク数３に対応する故障パターン数３６を配列Ａの要素として、Ａ［３］＝３６のように記憶する。
【００４８】
図１２に示すように、パターン更新部１４は、トポロジＧ１→Ｇ２の順に処理が行われた場合、パターン記憶部２１内のデータにトポロジＧ２についての処理で計算された故障パターン数を加算する。図１２は、パターン記憶部に保存されるデータについて説明するための図である。
【００４９】
図１２の例では、トポロジＧ１におけるリンク故障の結果、トポロジＧ３になるリンク故障パターンが４パターン存在する。また、初期状態からトポロジＧ１になるリンク故障パターン数は３６であるため、Ｇ３になる故障パターン数は、３６に４をかけた１４４である。そして、初期状態のトポロジからトポロジＧ３になるまでの故障リンク数は３である。
【００５０】
トポロジＧ１に関する処理が終了した時点では、パターン記憶部２１内にはトポロジＧ２とトポロジＧ３が存在する。そして、トポロジＧ２におけるリンクの故障パターンのうち、トポロジＧ３となる故障パターンが２つ存在する。ここで、トポロジＧ３のデータは既にパターン記憶部２１に保存済みなので、３６に２をかけた７２が、保存済みの故障パターン数１４４に加算される。
【００５１】
なお、故障リンク数ごとのリンク故障パターン数は、経路の再計算を必要とする場合が生じるときの平均故障リンク数を計算するときに必要となる。その場合、故障リンク数ごとの再計算発生確率を算出する必要がある。故障リンク数ごとの再計算発生確率の計算方法は次の通りである。
【００５２】
まず、本実施形態で計算した故障パターン数に、残存リンク数が切れた時のリンク故障パターン数である、残存リンク数の階乗の値をかけた値を算出する。次に、算出した値を初期状態のトポロジから生じる全リンク故障パターン数である、初期状態のリンク数の階乗の値で割る。このとき得られる値が、故障リンク数ごとの再計算発生確率である。
【００５３】
ただし、ここで算出される故障リンク数ごとの再計算発生確率は、全てのリンクの故障確率が同じであることを前提としている。そして、全ての故障リンク数について、故障リンク数と、故障リンク数ごとの再計算発生確率をかけ、得られた値の総和をとることで、経路再計算が生じるときの平均故障リンク数を計算することができる。
【００５４】
［第１の実施形態の処理］
図１３を用いて、第１の実施形態の処理について説明する。図１３は、第１の実施形態に係るリンク故障パターン数計算システムの処理の流れを示すフローチャートである。まず、図１３に示すように、取得部１１は、初期状態のトポロジを取得し、取得したトポロジを関数Ｆに入力する（ステップＳ１０１）。なお、ここでは一連の処理を関数Ｆにより行うこととする。
【００５５】
次に、パターン更新部１４は、入力したトポロジと、故障リンク数０と、故障パターン数１を組み合わせたデータをパターン記憶部２１に登録する（ステップＳ１０２）。そして、取得部１１は、パターン記憶部２１にデータが存在する場合（ステップＳ１０３、Ｙｅｓ）、パターン記憶部２１からデータを取り出し処理対象にする（ステップＳ１０４）。また、パターン記憶部２１にデータが存在しない場合（ステップＳ１０３、Ｎｏ）、処理を終了する。
【００５６】
削除部１２は、データに含まれるトポロジのリンクを１本削除し、１本リンクが故障したときに生じるトポロジを生成する（ステップＳ１０５）。そして、パターン更新部１４は、生成されたトポロジのうち、同じトポロジが存在する場合、そのトポロジになるリンク故障パターンをカウントする（ステップＳ１０６）。
【００５７】
ここで、生成したトポロジと同じトポロジを含むデータがパターン記憶部２１に存在している場合（ステップＳ１０７、Ｙｅｓ）、パターン更新部１４は、同じトポロジを含むデータの故障パターン数に、カウントしたパターン数と、パターン記憶部２１から出したデータが含むリンク故障パターン数をかけた数を足す（ステップＳ１０９）。
【００５８】
ここで、生成したトポロジと同じトポロジを含むデータがパターン記憶部２１に存在しない場合（ステップＳ１０７、Ｎｏ）において、さらに生成したトポロジに出力リンク数が０であるノードが存在している場合（ステップＳ１０８、Ｙｅｓ）、パターン数加算部１３は、パターン数記憶部２２に記憶されている故障パターン数をカウントする配列における、データの故障リンク数番目の値に、データのリンク故障パターン数の値を足し合わせる（ステップＳ１１１）。生成したトポロジに出力リンク数が０であるノードが存在していない場合（ステップＳ１０８、Ｎｏ）は次の処理に進む。
【００５９】
最後に、パターン更新部１４は、生成したトポロジをトポロジ、カウントしたパターン数と、パターン記憶部２１から出したデータが含むリンク故障パターン数をかけた数を故障パターン数、取り出したデータの故障リンク数に１を足した数を故障リンク数とするデータをパターン記憶部２１に保存する（ステップＳ１１０）。そして、ステップＳ１０３に戻り、処理を繰り返す。
【００６０】
［第１の実施形態の効果］
削除部１２は、ノード同士がリンクで接続されるネットワークのトポロジにおいて、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成するとともに、生成したトポロジのいずれかにおいて、全てのノードがリンクを有する場合には、該全てのノードがリンクを有するトポロジについて、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとして、各リンクが１つずつ削除された場合のトポロジをそれぞれ生成する。
【００６１】
また、パターン数加算部１３は、削除部１２によって生成されたトポロジのうち、リンクを有しないノードが存在するトポロジについて、該トポロジの生成までに削除したリンクの削除数ごとに、該トポロジを生成可能なリンクの故障パターン数を合計する。
【００６２】
このように、第１の実施形態では、ノードにつながるリンクの接続関係が同一である複数のトポロジを同一種類のトポロジとみなしている。そのため、全故障パターンについて再計算の要否を検討する必要がなくなり、リンク故障回数ごとの経路再計算が必要になる故障パターン数を効率良く計算することができる。
【００６３】
また、パターン記憶部２１は、トポロジごとに、該トポロジを生成可能なリンクの故障パターン数である故障パターン数を記憶する。そして、パターン更新部１４は、削除部１２によってトポロジが生成されるたびに、全てのノードがリンクを有する同一種類のトポロジの数と、パターン記憶部２１に記憶されている削除部１２によってリンクが削除される前のトポロジの故障パターン数とをかけ、該生成されたトポロジがパターン記憶部２１に記憶されている場合、該かけた数を、該生成されたトポロジの故障パターン数に加算し、該生成されたトポロジがパターン記憶部２１に記憶されていない場合、該かけた数を該生成されたトポロジの故障パターン数としてパターン記憶部２１に記憶させる。これにより、パターン数加算部１３は、パターン記憶部２１から取得した故障パターン数を基に、故障リンク数ごとの故障パターン数を計算することができる。
【００６４】
［第２の実施形態］
第１の実施形態においては、故障パターン数をパターン記憶部２１に記憶させていた。これに対し、第２の実施形態においては、各パターンの発生率を故障パターン割合としてパターン記憶部２１に記憶させておくようにすることで、再計算発生確率の計算を簡略化する。
【００６５】
第２の実施形態において、パターン記憶部２１は、トポロジごとに、該トポロジを生成可能なリンクの故障パターン数の、該トポロジが削除部１２によってリンクを削除される前のトポロジを生成可能なリンクの故障パターン数に対する割合である故障パターン割合をさらに記憶する。また、パターン更新部１４は、削除部１２によってトポロジが生成されるたびに、全てのノードがリンクを有する同一種類のトポロジの数を、パターン記憶部２１に記憶されている削除部１２によってリンクが削除される前のトポロジの故障パターン数で割った数を、削除部１２によってリンクが削除される前のトポロジの故障パターン割合にかけ、該生成されたトポロジがパターン記憶部２１に記憶されている場合、該かけた数を、該生成されたトポロジの故障パターン割合に加算し、該生成されたトポロジがパターン記憶部２１に記憶されていない場合、該かけた数を該生成されたトポロジの故障パターン割合としてとしてパターン記憶部２１に記憶させる。
【００６６】
図１４に示すように、パターン更新部１４は、故障パターン割合をパターン記憶部２１に記憶させる。図１４は、第２の実施形態について説明するための図である。図１４に示すように、故障パターン割合は、例えばトポロジＧ０になるリンク故障パターン数９を、初期状態のトポロジのリンク数９で割ることで求められる。なお、故障リンク数が１の場合、全ての故障パターンがＧ０になるため、故障パターン割合は１となる。
【００６７】
さらに、トポロジＧ１およびＧ２については、図１５に示す通りである。トポロジＧ０からＧ１、Ｇ２に変化するリンク故障パターン数は、前述の通りそれぞれ４パターン存在する。図１５に示すように、Ｇ０の故障パターン割合１に、トポロジＧ０からトポロジＧ１に変化するリンク故障パターン数４をトポロジＧ０の残存リンク数である８で割った数である１／２をかけることで、Ｇ１の故障パターン割合が求められる。このとき、Ｇ１の故障パターン割合は１／２となる。
【００６８】
［第２の実施形態の効果］
パターン記憶部２１は、トポロジごとに、該トポロジを生成可能なリンクの故障パターン数の、該トポロジが削除部１２によってリンクを削除される前のトポロジを生成可能なリンクの故障パターン数に対する割合である故障パターン割合をさらに記憶する。また、パターン更新部１４は、削除部１２によってトポロジが生成されるたびに、全てのノードがリンクを有する同一種類のトポロジの数を、パターン記憶部２１に記憶されている削除部１２によってリンクが削除される前のトポロジの故障パターン数で割った数を、削除部１２によってリンクが削除される前のトポロジの故障パターン割合にかけ、該生成されたトポロジがパターン記憶部２１に記憶されている場合、該かけた数を、該生成されたトポロジの故障パターン割合に加算し、該生成されたトポロジがパターン記憶部２１に記憶されていない場合、該かけた数を該生成されたトポロジの故障パターン割合としてとしてパターン記憶部２１に記憶させる。これにより、再計算発生確率を計算する際に、故障パターン割合を利用することができるため、計算量を削減することができる。
【００６９】
［第３の実施形態］
第１の実施形態では、パターン記憶部２１に保存されているトポロジのうち、故障リンク数が小さい順番に処理を行っていたが、第３の実施形態においては、再帰関数を呼び出すことで、トポロジが生成されるたびに生成されたトポロジを対象として処理を行う。
【００７０】
図１６を用いて、第３の実施形態について説明する。図１６は、第３の実施形態について説明するための図である。図１６に示すように、第３の実施形態においては、関数が処理しているトポロジからリンクを削除してトポロジを生成した後、処理中のトポロジと故障リンク数が同じであるトポロジが存在する場合であっても、先に生成したトポロジを関数に入力して処理を行う。
【００７１】
まず、再帰関数Ｆに、初期状態のトポロジが入力される。再帰関数Ｆは、初期状態からリンクが故障することにより生じる全てのトポロジを算出し、それぞれのトポロジに変化するリンク故障パターン数を算出する。前述の通り、初期状態からリンクを削除すると、どのリンクを削除してもトポロジＧ０となる。
【００７２】
次に、算出した全てのトポロジについて、各トポロジと、各トポロジのリンク故障パターン数が関数Ｆに入力される。ここでは、算出されるトポロジがＧ０のみであるため、トポロジＧ０と、初期状態からトポロジＧ０になるリンク故障パターン数である９が再帰関数Ｆに入力される。
【００７３】
次に、再帰関数Ｆは、トポロジＧ０のリンクが故障した場合の処理を行う。前述の通り、トポロジＧ０からはトポロジＧ１とＧ２が生成される。ここで、Ｇ１になるリンク故障パターン数およびＧ２になる故障パターン数はいずれも４である。そこで、４と、再帰関数Ｆに入力されたリンク故障パターン数とをかけた数、すなわち４×９＝３６がトポロジＧ１およびＧ２の故障パターン数である。
【００７４】
ここで、トポロジＧ１およびＧ２が順に再帰関数Ｆへ入力される。なお、トポロジＧ１を入力として再帰関数Ｆが実行される間に、トポロジＧ１から生成されるトポロジＧ３、Ｇ４、Ｇ５を入力とする再帰関数Ｆの処理が実行される。これらの処理が全て終了した後、トポロジＧ１を入力とする再帰関数Ｆの処理は終了する。その後、トポロジＧ２を入力とする再帰関数Ｆの処理が実行される。
【００７５】
第１の実施形態ではＧ０→Ｇ１→Ｇ２→Ｇ３→Ｇ４…という順番で処理が行われていたのに対し、第３の実施形態ではＧ０→Ｇ１→Ｇ３→Ｇ４…→Ｇ２→…という順番で処理が行われる。すなわち、第１の実施形態では故障リンク数が少ないトポロジから順に処理を行っていたのに対し、第３の実施形態では故障リンク数が多いトポロジから順に処理を行う。
【００７６】
このように、削除部１２は、入力されたトポロジのうち、故障リンク数が多いトポロジから順にリンクの削除を行ってもよいし、故障リンク数が少ないトポロジから順にリンクの削除を行ってもよい。
【００７７】
［第３の実施形態の処理］
図１７を用いて、第３の実施形態の処理について説明する。図１７は、第３の実施形態に係るリンク故障パターン数計算システムの処理の流れを示すフローチャートである。図１７に示すように、まず、取得部１１は初期状態のトポロジと故障パターン数１を再帰関数Ｆに入力する（ステップＳ２０１）。ここで、入力されたトポロジを注目するトポロジとする（ステップＳ２０２）。
【００７８】
再帰関数Ｆは、注目したトポロジにおいて、１本リンクを削除したときに生じるトポロジを生成する（ステップＳ２０３）。再帰関数Ｆは、生成されたトポロジのうち、同じトポロジが存在するか確認し、存在する場合、そのトポロジの故障パターン数をカウントする（ステップＳ２０４）。ここで、再帰関数Ｆは、出力リンク数が０であるノードが存在するトポロジに注目している場合（ステップＳ２０５、Ｙｅｓ）、その時点での組み合わせ数を、配列Ａの、初期状態のトポロジのリンク数から注目しているトポロジのリンク数を引いた値番目の値に足し合わせる（ステップＳ２０６）。
【００７９】
また、再帰関数Ｆは、出力リンク数が０であるノードが存在するトポロジに注目していない場合（ステップＳ２０５、Ｎｏ）、注目しているトポロジの故障パターン数とカウント数をかけた数を再帰関数Ｆに入力する（ステップＳ２０７）。そして、全てのトポロジに注目している場合（ステップＳ２０８、Ｙｅｓ）、処理を終了する。また、全てのトポロジに注目していない場合（ステップＳ２０８、Ｎｏ）、次のトポロジに注目し（ステップＳ２０９）、ステップＳ２０３に戻り処理を繰り返す。
【００８０】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）および当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８１】
また、本実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８２】
［プログラム］
一実施形態として、リンク故障パターン数計算システムは、パッケージソフトウェアやオンラインソフトウェアとして上記のリンク故障パターン数計算を実行するリンク故障パターン数計算プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記のリンク故障パターン数計算プログラムを情報処理装置に実行させることにより、情報処理装置をリンク故障パターン数計算システムとして機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等のスレート端末等がその範疇に含まれる。
【００８３】
また、リンク故障パターン数計算システムは、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記のリンク故障パターン数計算に関するサービスを提供するサーバ装置として実装することもできる。例えば、リンク故障パターン数計算システムは、ネットワークの物理トポロジを入力とし、リンク故障パターン数を出力とするリンク故障パターン数計算サービスを提供するサーバ装置として実装される。この場合、リンク故障パターン数計算システムは、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記のリンク故障パターン数計算に関するサービスを提供するクラウドとして実装することとしてもかまわない。
【００８４】
図１８は、プログラムが実行されることにより、リンク故障パターン数計算システムが実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００８５】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００８６】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、リンク故障パターン数計算システムの各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、リンク故障パターン数計算システムにおける機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００８７】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００８８】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００８９】
１  リンク故障パターン数計算システム
１０  制御部
１１  取得部
１２  削除部
１３  パターン数加算部
１４  パターン更新部
２０  記憶部
２１  パターン記憶部
２２  パターン数記憶部
【図１】
2017108300.tif 000003
【図２】
2017108300.tif 000004
【図３】
2017108300.tif 000005
【図４】
2017108300.tif 000006
【図５】
2017108300.tif 000007
【図６】
2017108300.tif 000008
【図７】
2017108300.tif 000009
【図８】
2017108300.tif 000010
【図９】
2017108300.tif 000011
【図１０】
2017108300.tif 000012
【図１１】
2017108300.tif 000013
【図１２】
2017108300.tif 000014
【図１３】
2017108300.tif 000015
【図１４】
2017108300.tif 000016
【図１５】
2017108300.tif 000017
【図１６】
2017108300.tif 000018
【図１７】
2017108300.tif 000019
【図１８】
2017108300.tif 000020