(57)【要約】【課題】本発明は、通信網の２つのノード間が通信不能となる故障頻度を高速に計算できるようにする新たな通信網故障頻度計算技術の提供を目的とする。【解決手段】処理対象の通信網を、２つのノードのいずれか一方又は双方が故障しないと見なした通信網に変換する。そして、変換した通信網の持つリンクの中からいずれか一方の端点が故障しないノードに接続されるリンクを選択して、そのリンクとそれに接続される２つのノードとを１つの故障しないノードとした通信網の持つ信頼度及び故障頻度と、そのリンクを除去し、かつ、そのリンクが接続するノードの１つを故障しうるとした通信網の持つ信頼度及び故障頻度とをパラメータ値とする計算式に従って、変換した通信網の信頼度及び故障頻度を計算する。そして、その計算した信頼度及び故障頻度に基づいて、処理対象の通信網の信頼度及び故障頻度を計算する。【選択図】          図５
2004363855.tif 000002
【特許請求の範囲】
【請求項１】
リンクもノードも故障しうるという条件下で、通信網の持つ２つのノード間が通信不能となる故障頻度を計算する方法であって、
処理対象の通信網を、上記２つのノードのいずれか一方又は双方が故障しないと見なした通信網に変換する第１の過程と、
上記変換した通信網の持つリンクの中からいずれか一方の端点が故障しないノードに接続されるリンクを選択して、そのリンクを短絡することにより得られる、そのリンクとそれに接続される２つのノードとを１つの故障しないノードとした通信網の持つ信頼度及び故障頻度と、そのリンクを開放することにより得られる、そのリンクを除去し、かつ、そのリンクが接続するノードの１つを故障しうるとした通信網の持つ信頼度及び故障頻度とをパラメータ値とする計算式に従って、上記変換した通信網の信頼度及び故障頻度を計算する第２の過程と、
上記計算した信頼度及び故障頻度に基づいて、処理対象の通信網の信頼度及び故障頻度を計算する第３の過程とを備えることを、
特徴とする通信網故障頻度計算方法。
【請求項２】
請求項１記載の通信網故障頻度計算方法において、
上記第２の過程では、上記短絡及び開放前の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、上記短絡後の通信網の信頼度をＲ（Ｇｅ  ）、故障頻度をＦ（Ｇｅ  ）、上記開放後の通信網の信頼度をＲ（Ｇｅ  ＊  ）、故障頻度をＦ（Ｇｅ  ＊  ）で表すならば、
2004363855.tif 000025
但し、ｐｅ  ：上記選択リンクの正常確率
λｅ  ：上記選択リンクの故障率
ｐｘ  ：上記選択リンクに接続される故障しうるノードの正常確率
λｘ  ：上記選択リンクに接続される故障しうるノードの故障率
という計算式に従って、上記変換した通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算方法。
【請求項３】
請求項２記載の通信網故障頻度計算方法において、
上記第２の過程では、上記開放後の通信網に残されたノードの正常確率ｐｘ’、故障率λｘ’を、
ｐｘ’＝ｐｘ  （１−ｐｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
λｘ’＝（１−ｐｘ  ）（λｘ  ＋μｘ  −μｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
但し、μｘ  ＝ｐｘ  λｘ  ／（１−ｐｘ  ）
で与えることを、
特徴とする通信網故障頻度計算方法。
【請求項４】
請求項１記載の通信網故障頻度計算方法において、
上記第３の過程では、上記２つのノードの双方が故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐＳ  ｐＴ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐＳ  ｐＴ  （λＳ  ＋λＴ  ）Ｒ（Ｇ０  ）＋ｐＳ  ｐＴ  Ｆ（Ｇ０  ）
但し、ｐＳ  ：いずれか一方のノードＳの正常確率
λＳ  ：いずれか一方のノードＳの故障率
ｐＴ  ：もう一方のノードＴの正常確率
λＴ  ：もう一方のノードＴの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算方法。
【請求項５】
請求項１記載の通信網故障頻度計算方法において、
上記第３の過程では、上記２つのノードのいずれか一方だけが故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐｋ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐｋ  λｋ  Ｒ（Ｇ０  ）＋ｐｋ  Ｆ（Ｇ０  ）
但し、ｐｋ  ：故障しないと見なされない方のノードの正常確率
λｋ  ：故障しないと見なされない方のノードの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算方法。
【請求項６】
リンクもノードも故障しうるという条件下で、通信網の持つ２つのノード間が通信不能となる故障頻度を計算する装置であって、
処理対象の通信網を、上記２つのノードのいずれか一方又は双方が故障しないと見なした通信網に変換する第１の手段と、
上記変換した通信網の持つリンクの中からいずれか一方の端点が故障しないノードに接続されるリンクを選択して、そのリンクを短絡することにより得られる、そのリンクとそれに接続される２つのノードとを１つの故障しないノードとした通信網の持つ信頼度及び故障頻度と、そのリンクを開放することにより得られる、そのリンクを除去し、かつ、そのリンクが接続するノードの１つを故障しうるとした通信網の持つ信頼度及び故障頻度とをパラメータ値とする計算式に従って、上記変換した通信網の信頼度及び故障頻度を計算する第２の手段と、
上記計算した信頼度及び故障頻度に基づいて、処理対象の通信網の信頼度及び故障頻度を計算する第３の手段とを備えることを、
特徴とする通信網故障頻度計算装置。
【請求項７】
請求項６記載の通信網故障頻度計算装置において、
上記第２の手段は、上記短絡及び開放前の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、上記短絡後の通信網の信頼度をＲ（Ｇｅ  ）、故障頻度をＦ（Ｇｅ  ）、上記開放後の通信網の信頼度をＲ（Ｇｅ  ＊  ）、故障頻度をＦ（Ｇｅ  ＊  ）で表すならば、
2004363855.tif 000026
但し、ｐｅ  ：上記選択リンクの正常確率
λｅ  ：上記選択リンクの故障率
ｐｘ  ：上記選択リンクに接続される故障しうるノードの正常確率
λｘ  ：上記選択リンクに接続される故障しうるノードの故障率
という計算式に従って、上記変換した通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算装置。
【請求項８】
請求項７記載の通信網故障頻度計算装置において、
上記第２の手段は、上記開放後の通信網に残されたノードの正常確率ｐｘ’、故障率λｘ’を、
ｐｘ’＝ｐｘ  （１−ｐｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
λｘ’＝（１−ｐｘ  ）（λｘ  ＋μｘ  −μｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
但し、μｘ  ＝ｐｘ  λｘ  ／（１−ｐｘ  ）
で与えることを、
特徴とする通信網故障頻度計算装置。
【請求項９】
請求項６記載の通信網故障頻度計算装置において、
上記第３の手段は、上記２つのノードの双方が故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐＳ  ｐＴ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐＳ  ｐＴ  （λＳ  ＋λＴ  ）Ｒ（Ｇ０  ）＋ｐＳ  ｐＴ  Ｆ（Ｇ０  ）
但し、ｐＳ  ：いずれか一方のノードＳの正常確率
λＳ  ：いずれか一方のノードＳの故障率
ｐＴ  ：もう一方のノードＴの正常確率
λＴ  ：もう一方のノードＴの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算装置。
【請求項１０】
請求項６記載の通信網故障頻度計算装置において、
上記第３の手段は、上記２つのノードのいずれか一方だけが故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐｋ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐｋ  λｋ  Ｒ（Ｇ０  ）＋ｐｋ  Ｆ（Ｇ０  ）
但し、ｐｋ  ：故障しないと見なされない方のノードの正常確率
λｋ  ：故障しないと見なされない方のノードの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算装置。
【請求項１１】
請求項１ないし５のいずれか１項に記載の通信網故障頻度計算方法の実現に用いられる処理をコンピュータに実行させるための通信網故障頻度計算プログラム。
【請求項１２】
請求項１ないし５のいずれか１項に記載の通信網故障頻度計算方法の実現に用いられる処理をコンピュータに実行させるための通信網故障頻度計算プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信網の持つ２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算方法及びその装置と、その通信網故障頻度計算方法の実現に用いられる通信網故障頻度計算プログラム及びそのプログラムを記録した記録媒体とに関する。
【０００２】
更に具体的に説明するならば、本発明は、通信網において、リンクもノードも故障しうるという条件下で、あるノードとあるノードとの間が通信不能となる故障が発生する頻度の平均値を分解法を使って高速に計算する技術に関するものである。
【０００３】
【従来の技術】
通信網の信頼性とは、通信が安定して行われる度合いまたは性質を表す。通信網は点と線とからなり、点は通信装置（交換機、多重化装置等）、線は回線装置を表す。点で表される通信装置のことを、以下ではノードと呼び、線で表される回線装置のことを、以下ではリンクと呼ぶ。
【０００４】
通信網の信頼性は、まず、特定の二つのノード（それぞれＳ，Ｔと書く）に着目し、この着目ノード間が通信可能である確率（Ｓ，Ｔ間の信頼度。以下、Ｓ−Ｔ間信頼度と記載することがある）で評価されるか、あるいは、この着目ノード間が通信不可能となる故障の平均発生頻度（Ｓ，Ｔ間の故障頻度。以下、Ｓ−Ｔ間故障頻度と記載することがある）で評価される。
【０００５】
Ｓ−Ｔ間信頼度は、０から１の範囲の値をとる確率として表され、一方、Ｓ−Ｔ間故障頻度は、例えば、年に何回という尺度で表される。Ｓ−Ｔ間信頼度もＳ−Ｔ間故障頻度も共に、重要な信頼性評価尺度として用いられている。
【０００６】
最初に、説明の容易さのために、ノードは故障しないという前提で、Ｓ−Ｔ間信頼度の計算方法について説明する。
【０００７】
この計算方法にはいくつかあるが、以下の二つの方法が代表的である。
（１）通信網の信頼度を保存しながら、通信網の形状を単純化する（縮退法）。
（２）あるリンクに着目し、そのリンクが接続する二つのノードを一つと見なした通信網と、そのリンクを除去した通信網という二つの通信網に分解して、分解によって得られた二つの通信網の信頼度から、最初の通信網の信頼度を計算する（分解法）。
【０００８】
簡単な例で、これらの二つの手法の概要について説明する。
【０００９】
図２５の通信網構成で、Ｓ−Ｔ間信頼度を計算する場合について説明する。説明のため、リンクには図中のような番号が与えられているとする。以下、各リンクは、この番号で識別される。そして、リンクｉが正常である確率をそれぞれｐｉ  とする。
【００１０】
図２５に示す通信網において、リンク１，２は、その何れかが故障しても、他方が正常であれば、通信の確保に支障は無い。リンク１，２の何れかが正常であれば、通信は確保できる（このような関係を並列と呼ぶ）。
【００１１】
つまり、リンク１，２という二つのリンクは、図２６に示すように、リンク１，２の何れかが正常である確率を、改めてリンクの正常確率として与えられた一つのリンク４に置き換えても、Ｓ−Ｔ間信頼度の計算上は等価である。ここで、リンク４が正常である確率ｐ４  は、「ｐ４  ＝ｐ１  ＋ｐ２  −ｐ１  ｐ２  」で与えられる。
【００１２】
このようにＳ−Ｔ間信頼度を変えずに、通信網をより簡単な構成に置き換えることを縮退と呼び、図２６のように、並列構成のリンクを１リンクに置き換える操作を並列の縮退と呼ぶ。
【００１３】
図２６の縮退で得られた通信網は、リンク４とリンク３とから構成されるが、これらの二つのリンクは、両方が正常であって初めてＳ，Ｔ間の通信が確保できる（このような関係を直列の関係と呼ぶ）。
【００１４】
つまり、リンク４，３という二つのリンクは、図２７に示すように、リンク４，３の両方が正常である確率を、改めてリンクの正常確率として与えられた一つのリンク５に置き換えても、Ｓ−Ｔ間信頼度の計算上は等価である。ここで、リンク５が正常である確率ｐ５  は、「ｐ５  ＝ｐ４  ｐ３  」で与えられる。
【００１５】
図２７のように、直列構成のリンクを１リンクに置き換える操作を直列の縮退と呼ぶ。
【００１６】
結局、図２５の通信網は、図２７のように等価な１リンクに置き換えることができる。この場合、Ｓ−Ｔ間信頼度は、ＳとＴとが通信できる確率であるから、明らかにｐ５  である。
【００１７】
図２７の直列の縮退の変換式より、
Ｓ−Ｔ間信頼度＝ｐ５  ＝ｐ４  ｐ３  
となる。ところが、図２６の並列の縮退の変換式より、
ｐ４  ＝ｐ１  ＋ｐ２  −ｐ１  ｐ２  
であるから、結局、Ｓ−Ｔ間信頼度は、
Ｓ−Ｔ間信頼度＝ｐ５  ＝ｐ４  ｐ３  ＝（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）ｐ３  
というように求められる。
【００１８】
このように、通信網が、直列と並列で構成されていれば、縮退を用いて、そのＳ−Ｔ間信頼度を求めることができる。しかし、直列でも並列でもない構成を含む場合、例えばブリッジと呼ばれる図２８のような場合には、縮退法だけでは、Ｓ−Ｔ間信頼度を求めることは出来ない。
【００１９】
この場合には、分解法が用いられる。これは、以下の操作に基づいた計算法である。
【００２０】
この分解法では、
＜１＞先ず最初に、Ｓ−Ｔ間信頼度を求めたい通信網の一つのリンクに着目して、通信網と着目リンクを取り除いた上で、着目リンクの両端ノードを一つのノードと見なした（以下、この操作を短絡除去と呼ぶ）通信網を生成し、
＜２＞続いて、その着目リンクを取り除いた（以下、この操作を開放除去と呼ぶ）通信網を生成し（＜１＞＜２＞によって二つの通信網を生成する操作を「通信網を分解する」と呼ぶ）、
＜３＞続いて、その得られた二つの通信網のＳ−Ｔ間信頼度から、分解前の通信網のＳ−Ｔ間信頼度を一定の変換式によって計算する、
という手順に従って、任意の形状の通信網のＳ−Ｔ間信頼度を計算する。
【００２１】
例えば、図２８の通信網をリンク４に着目して分解すると、図２９のようになる。
【００２２】
今、通信網をＧで表し、ＧのＳ−Ｔ間信頼度をＲ（Ｇ）で表す。また、Ｇにおいて、リンクｅを短絡除去して得られた通信網をＧｅ  、リンクｅを開放除去して得られた通信網をＧｅ  ＊  と書けば、
Ｒ（Ｇ）＝ｐｅ  Ｒ（Ｇｅ  ）＋（１−ｐｅ  ）Ｒ（Ｇｅ  ＊  ）  ・・・式（１）
但し、ｐｅ  ：リンクｅの正常である確率
という式（１）の成立することが知られている。
【００２３】
図２９の場合、求めたいＳ−Ｔ間信頼度は、直並列の縮退と式（１）とを用いて計算できる。
【００２４】
すなわち、リンク４を短絡除去して得られた通信網（図２９の左側の通信網）については、直並列の縮退を用いて、
Ｓ−Ｔ間信頼度＝（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）（ｐ３  ＋ｐ５  −ｐ３  ｐ５  ）
が成り立つ。一方、リンク４を開放除去して得られた通信網（図２９の右側の通信網）については、同様に直並列の縮退を用いて、
Ｓ−Ｔ間信頼度＝ｐ１  ｐ３  ＋ｐ２  ｐ５  −ｐ１  ｐ２  ｐ３  ｐ５  
が成り立つ。
【００２５】
従って、求めたい分解前の通信網のＳ−Ｔ間信頼度は、上述の式（１）を用いて、
2004363855.tif 000003
と求められる。
【００２６】
分解によって得られた通信網が、直列と並列の組み合わせで表現できる構成であれば、以上の方法によって、その信頼度を計算できる。もし、直列と並列のみで表現できなければ、さらに分解を繰り返せばよい。図３０に、より複雑な分解の例を示す。
【００２７】
このようにして、任意の形状の通信網のＳ−Ｔ間信頼度を、縮退法と分解法とに基づいて計算することができる。
【００２８】
縮退法、分解法以外にもいくつかの信頼性計算法が提案されているが、縮退法と分解法とに基づく方法が計算速度の面で高速であることが知られている（例えば、非特許文献１参照）。
【００２９】
以上、Ｓ−Ｔ間信頼度の計算方法について述べたが、Ｓ−Ｔ間故障頻度を求めようとする場合でも、Ｓ−Ｔ間信頼度と同様な計算手続きが利用できる。
【００３０】
この場合、リンクｉには、正常確率ｐｉ  とともに、故障率λｉ  （１／（修理されてから再び故障するまでの平均時間））が与えられているとする。
【００３１】
並列の縮退については、
ｐｃ  ＝（ｐａ  ＋ｐｂ  −ｐａ  ｐｂ  ）
2004363855.tif 000004
という変換式で縮退ができることが知られている（例えば、非特許文献２参照）。ここで、ａ，ｂは縮退前の２つのリンクの番号、ｃは縮退後のリンク番号である。
【００３２】
一方、直列の縮退については、
ｐｃ  ＝ｐａ  ｐｂ  
λｃ  ＝λａ  ＋λｂ  
という変換式で縮退ができることが知られている（例えば、非特許文献２参照）。ここで、同様に、ａ，ｂは縮退前の２つのリンクの番号、ｃは縮退後のリンク番号である。
【００３３】
これらの式に従って、例えば、図２５の通信網では、最終的な縮退後の故障率が、
（ｐ１  λ１  ＋ｐ２  λ２  −ｐ１  ｐ２  （λ１  ＋λ２  ））／（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）＋λ３  
となる。
【００３４】
ここで、リンクが一つからなる通信網のＳ，Ｔ間の故障頻度、信頼度、故障率に関しては、
Ｓ−Ｔ間故障頻度＝（Ｓ−Ｔ間信頼度）×（Ｓ−Ｔ間故障率）
という関係式が成立することが知られている（例えば、非特許文献２参照）。
【００３５】
この関係式に従って、図２５の通信網におけるＳ−Ｔ間故障頻度は、
2004363855.tif 000005
で求められる。
【００３６】
このようにして、Ｓ−Ｔ間故障頻度の計算については縮退法が利用できるのである。
【００３７】
以上に説明した計算法は極めて有効な方法ではあるが、ノードが故障しないという前提での計算法であるという点で限界があった。
【００３８】
しかし、最近の通信網の実態として、リンク故障よりもノード故障（局舎内設備の故障）が致命的となる場合もある。例えば、ルータ等がネットワーク設備管理会社ではなくてユーザビルに収容されている場合には、管理が行き届かず故障が多発することになる。
【００３９】
このようなことを背景にして、非特許文献１では、ノードが故障する場合のＳ−Ｔ間信頼度の計算に分解法を利用するための改善案を提示した。
【００４０】
この改善案は、以下の性質１〜４を利用したものである。
〔性質１〕
通信網Ｇにおいて、Ｓ−Ｔ間信頼度を計算する際、着目リンクｅが接続する二つのノードのうち、片方が故障しないノードならば、着目リンクｅについて分解法を利用できる。
〔性質２〕
通信網Ｇにおいて、Ｓ−Ｔ間信頼度を計算する際、ノードが故障するという条件でも、並列の縮退は、ノードが故障しない場合と同様に適用できる。
〔性質３〕
通信網Ｇにおいて、Ｓ−Ｔ間信頼度を計算する際、ノードが故障するという条件では、直列の縮退は、ノード故障を考慮して、後述する図３３のような形で適用できる。
〔性質４〕
通信網Ｇにおいて、ＳとＴとが故障しないとした通信網をＧ０  とすると、ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）と、Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０）との間には、後述する式（６）という関係式が成立する。
【００４１】
次に、性質１について具体的に説明する。
【００４２】
リンクだけでなく、ノードにも番号が与えられ、ノード番号ｊのノードが正常である確率をｐｊ  と書く。また、図中で、故障しないノードを「丸印」で示し、故障しうるノードを「二重丸」で示す。
【００４３】
今、図３１に示すように、リンクｅの接続する二つのノードのノード番号をｘ，ｙとし、ノードｙは故障しない（ｐｙ  ＝１）とする。
【００４４】
このとき、リンクｅを短絡除去して得られたノードを改めてｙとし（ｙは故障せず）、リンクｅを開放除去して残された故障しうるノードｘ’の正常である確率を
ｐｘ’＝ｐｘ  （１−ｐｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］  ・・・式（２）
で与えれば、分解前の通信網ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）は、
Ｒ（Ｇ）＝ｐｅ  ｐｘ  Ｒ（Ｇｅ  ）＋（１−ｐｅ  ｐｘ  ）Ｒ（Ｇｅ  ＊  ）  ・・式（３）
但し、Ｇｅ    ：通信網Ｇの持つリンクｅを短絡した通信網
Ｇｅ  ＊  ：通信網Ｇの持つリンクｅを開放した通信網
という式で求められる。
【００４５】
一方、性質２は、図３２に示すように、ノードが故障するという条件でも、並列の縮退については、ノードが故障しない場合と同様に適用できるという性質を示しており、このときの変換式は、
ｐｃ  ＝ｐａ  ＋ｐｂ  −ｐａ  ｐｂ    ・・・・・式（４）
であるということを示している。
【００４６】
一方、性質３は、直列の縮退については、ノード故障を考慮して、図３３のような形で適用できるという性質を示しており、このときの変換式は、
ｐｄ  ＝ｐａ  ｐｂ  ｐｃ            ・・・・・式（５）
であるということを示している。
【００４７】
一方、性質４は、通信網Ｇにおいて、ＳとＴが故障しないとした通信網をＧ０  とすると、ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）と、Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０）との間には、
Ｒ（Ｇ）＝ｐＳ  ｐＴ  Ｒ（Ｇ０）  ・・・・・式（６）
但し、ｐＳ  ：ノードＳの正常確率
ｐＴ  ：ノードＴの正常確率
という関係式が成り立つことを示している。
【００４８】
これらの性質１〜４を用いてＲ（Ｇ）を求める様子を、具体例を用いて説明する。
【００４９】
通信網Ｇを図２８に示したようなブリッジ型の通信網（ただし、各ノードは故障しうる）とすると、Ｇは、図３４に示すように、まずＧ０  に変換された後、性質１に従って、リンク１に従ってＧ０１とＧ０１＊  とに分解できる。
【００５０】
この図３４において、Ｒ（Ｇ０１）は、直並列の縮退、すなわち、性質２，３を用いて、
2004363855.tif 000006
と求められる。
【００５１】
一方、Ｒ（Ｇ０１＊  ）も、直並列の縮退を用いて、
Ｒ（Ｇ０１＊  ）＝ｐ２  ｐ７  （ｐ４  ｐ６’ｐ３  ＋ｐ５  −ｐ４  ｐ６’ｐ３  ｐ５  ）
と求められる。ここで、ｐ６’の値は、性質１の式（２）より、
ｐ６’＝ｐ６  （１−ｐ１  ）／〔（１−ｐ６  ）＋ｐ６  （１−ｐ１  ）〕
で求められる。
【００５２】
これらの式に、性質１の式（３）を適用すれば、分解前の通信網Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０  ）は、次のように求められる。
【００５３】
【数１】
2004363855.tif 000007
【００５４】
さらに、性質４の式（６）を適用すれば、Ｇ０  の変化元となった通信網ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）は、次のように求められる。
【００５５】
【数２】
2004363855.tif 000008
【００５６】
ここで、本分解法を適用するためには、故障しないノードを見つけなければならないが、性質４から、Ｇ０  については必ず故障しないノードが存在する。また、分解後の通信網については、性質１より必ず故障しないノードを含んでいる。従って、任意の形状の通信網について、どのノードが故障するとしても、分解法を繰り返し用いることができ、Ｓ−Ｔ間信頼度を計算することができる。
【００５７】
【非特許文献１】
Ｏｌｙｍｐｉａ  Ｒ．Ｔｈｏｌｏｇｏｕ，Ｊａｃｑｕｅｓ  Ｇ．Ｃａｒｌｉｅｒ，”Ｆａｃｔｏｒｉｎｇ  ＆  Ｒｅｄｕｃｔｉｏｎｓ  ｆｏｒ  Ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  Ｉｍｐｅｒｆｅｃｔ  Ｖｅｒｔｉｃｅｓ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．２１０−２１７（１９９１）
【非特許文献２】
Ｍ．Ｈａｙａｓｈｉ，”Ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｏｐｅｒａｔｏｒ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．６０１−６０９（１９９１）
【００５８】
【発明が解決しようとする課題】
以上説明したように、従来技術では、通信網のＳ−Ｔ間信頼度については、ノードが故障しないという条件下でも、ノードが故障しうるという条件下でも、縮退法と分解法とを用いて高速に求めることができた。
【００５９】
ところが、従来技術では、式（１）に相当する、分解後の通信網から分解前の通信網のＳ，Ｔ間の故障頻度の計算に必要なパラメータを算出する手続きが知られていなかったために、通信網のＳ−Ｔ間故障頻度については、ノードが故障しないという条件下でも、分解法を用いて計算することはできなかった。
【００６０】
また、従来技術では、性質１〜４に対応する変換式が知られていなかったために、通信網のＳ−Ｔ間故障頻度については、ノードが故障しうるという条件下で、分解法を用いて計算することはできなかった。
【００６１】
これから、従来技術では、Ｓ−Ｔ間故障頻度については、縮退法を用いて計算していた。
【００６２】
しかるに、縮退法を用いての計算は、通信網のノード数、リンク数が大きくなると、計算項が莫大となり、高速計算機を用いても、計算時間の点での困難が生じていた。
【００６３】
これから、Ｓ−Ｔ間故障頻度の計算についても、Ｓ−Ｔ間信頼度の計算と同様に、高速な分解法を用いる手法が要望されている。
【００６４】
ところが、ノードが故障しないという条件下でも、従来技術では、式（１）に相当する、分解後の通信網から分解前の通信網のＳ−Ｔ間故障頻度の計算に必要なパラメータを算出する手続きが知られていなかったために、分解法を用いて故障頻度を計算することはできなかった。
【００６５】
このようなことを背景にして、本発明者らは、先に出願した特願２００３−６９０１１で、分解法によるＳ−Ｔ間故障頻度の計算を可能とするために、分解後の通信網から分解前の通信網の故障頻度計算に必要なパラメータを算出する手続きとして、次の式（１）’を用いる方法を提案した。
【００６６】
【数３】
2004363855.tif 000009
【００６７】
ここで、Ｒ（Ｇ）は通信網ＧのＳ−Ｔ間信頼度、Ｆ（Ｇ）は通信網ＧのＳ−Ｔ間故障頻度、ｅは分解を適用する際に着目するリンク、Ｇｅ  は通信網Ｇの持つリンクｅを短絡した通信網、Ｇｅ  ＊  は通信網Ｇの持つリンクｅを開放した通信網、ｐｅ  はリンクｅの正常確率、λｅ  はリンクｅの故障率を示している。
【００６８】
上述の式（１）の代わりに、この式（１）’を用いれば、縮退法と分解法とを用いて、通信網Ｇの故障頻度を求めることができるようになる。
【００６９】
先に出願した特願２００３−６９０１１で提案した方式の適用イメージを明らかにするために、図２８の通信網に対して、式（１）’を適用した例について説明する。今、図２８の通信網で、ｐ１  ＝ｐ２  ＝ｐ３  ＝ｐ４  ＝ｐ５  ＝０．９９、λ１  ＝λ２  ＝λ３  ＝λ４  ＝λ５  ＝０．０２とする。
【００７０】
図２８の通信網を図２９のように分解し、分解後の通信網に縮退法を用いれば、
Ｒ（Ｇ４  ）  ＝０．９９９８，  Ｆ（Ｇ４  ）  ＝０．０００７９
Ｒ（Ｇ４  ＊  ）＝０．９９９６，  Ｆ（Ｇ４  ＊  ）＝０．０１５６
と求められる。
【００７１】
これから、式（１）’を用いると、下記に示す式に従って、図２８の通信網において、Ｓ−Ｔ間故障頻度は“０．０００８０”と求められることになる。
【００７２】
【数４】
2004363855.tif 000010
【００７３】
このようにして、本発明者らが出願した特願２００３−６９０１１で提案した方法によれば、通信網のＳ−Ｔ間故障頻度について、ノードが故障しないという条件下であれば、分解法を用いて高速に計算することができるようになる。
【００７４】
しかしながら、性質１〜４に対応する変換式が知られていなかったために、ノードが故障しうるという条件下で、分解法を用いて計算することはできないという問題が残されている。
【００７５】
本発明はかかる事情に鑑みてなされたものであって、ノードが故障しうるという条件下で適用される性質１〜４に相当する変換式を導出し、この変換式に基づいて、ノードが故障しうるという条件下で、通信網の持つ指定される２つのノード間が通信不能となる故障頻度を高速に計算できるようにする新たな通信網故障頻度計算技術の提供を目的とする。
【００７６】
【課題を解決するための手段】
この目的を達成するために、本発明は、性質１〜４に代わって、以下の性質１’〜４’を用いる分解法を提案することで、ノードが故障しうるという条件下で、通信網の持つ２つのノード間が通信不能となる故障頻度を高速に計算できるようにすることを実現する。
【００７７】
〔性質１’〕
通信網Ｇにおいて、Ｓ−Ｔ間故障頻度を計算する際にも、着目リンクｅが接続する二つのノードのうち、片方が故障しないノードならば、着目リンクｅについて分解法を利用できる。
【００７８】
次に、性質１’を具体的に説明する。
【００７９】
ノード番号ｎのノードが正常である確率をｐｎ  、故障率をλｎ  と書く。また、性質１と同様に、リンクｅの接続する二つのノードのノード番号をｘ，ｙとし、ノードｙは故障しない（ｐｙ  ＝１，λｙ  ＝０）とする。
【００８０】
このとき、リンクｅを短絡除去して得られたノードを改めてｙとし（ｙは故障せず）、リンクｅを開放除去して残されたノードｘ’の正常である確率と故障率とを次の式（２）’で与えれば、分解前の通信網ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）とＳ−Ｔ間故障頻度Ｆ（Ｇ）とは、以下の式（３）’で求められる。ここで、ｘをノード番号あるいはリンク番号とするとき、μｘ  ＝ｐｘ  λｘ  ／（１−ｐｘ  ）である。
【００８１】
【数５】
2004363855.tif 000011
【００８２】
【数６】
2004363855.tif 000012
【００８３】
〔性質２’〕
通信網Ｇにおいて、Ｓ−Ｔ間故障頻度を計算する際、ノードが故障するという条件でも、並列の縮退は、ノードが故障しない場合と同様に図３２のように適用できる。変換式は次の式（４）’のとおりである。
【００８４】
【数７】
2004363855.tif 000013
【００８５】
〔性質３’〕
通信網Ｇにおいて、Ｓ−Ｔ間故障頻度を計算する際、ノードが故障するという条件では、直列の縮退は、ノード故障を考慮して、上述した図３３のような形で適用できる。変換式は次の式（５）’のとおりである。
【００８６】
【数８】
2004363855.tif 000014
【００８７】
〔性質４’〕
通信網Ｇにおいて、ＳとＴとが故障しないとした通信網をＧ０  とすると、ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）とＳ−Ｔ間故障頻度Ｆ（Ｇ）、Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０）とＳ−Ｔ間故障頻度Ｆ（Ｇ０）の間には、次の式（６）’の関係式が成立する。
【００８８】
【数９】
2004363855.tif 000015
【００８９】
これらの性質１’〜４’を用いて、任意の形状の通信網ＧのＳ−Ｔ間故障頻度を分解法により計算することができる。
【００９０】
図３４に示した通信網Ｇにおいて、
ｐＳ  ＝ｐＴ  ＝ｐ１  ＝ｐ２  ＝ｐ３  ＝ｐ４  ＝ｐ５  ＝ｐ６  ＝ｐ７  ＝０．９９
λＳ  ＝λＴ  ＝λ１  ＝λ２  ＝λ３  ＝λ４  ＝λ５  ＝λ６  ＝λ７  ＝０．２
とするならば、Ｓ−Ｔ間故障頻度は、図１に示すような形で、
Ｆ（Ｇ）＝０．４１８４６７
と求められることになる。
【００９１】
すなわち、先ず最初に、ＳとＴとが故障しないとした通信網Ｇ０  を生成し、それが持つ着目リンク１に従って、性質２’，３’を用いて、Ｒ（Ｇ０１）とＦ（Ｇ０１）とを計算するとともに、Ｒ（Ｇ０１＊  ）とＦ（Ｇ０１＊  ）とを計算し、続いて、式（３）’を使って、分解前の通信網Ｇ０  のＲ（Ｇ０  ）とＦ（Ｇ０  ）とを計算し、続いて、式（６）’を使って、Ｇ０  の変換元となった通信網ＧのＲ（Ｇ）とＦ（Ｇ）とを計算することで、Ｓ−Ｔ間故障頻度は、
Ｆ（Ｇ）＝０．４１８４６７
と求められることになる。
【００９２】
以下、式（２）’〜（６）’の正当性について示す。
【００９３】
通信網Ｇのリンク及びノード番号の集合をＬ｛１，２，・・・，Ｎ｝とする。さらに、ｐ１，ｐ２，・・・，  ｐＮ  を変数に持つ関数の全体をＸとし、ｐ１，ｐ２，・・・，  ｐＮ，λ１，λ２，・・・，  λＮ  を変数に持つ関数の全体をＹとする。
【００９４】
ＸからＹへの写像Ｄを、
条件１．任意のｉ∈Ｌに対して、Ｄ（ｐｉ  ）＝ｐｉ  λｉ    ・・・式（７）
条件２．任意のｆ，ｇ∈Ｘに対して、
Ｄ（ｆ＋ｇ）＝Ｄ（ｆ）＋Ｄ（ｇ）          ・・・式（８）
Ｄ（ｆｇ）＝Ｄ（ｆ）ｇ＋ｆＤ（ｇ）        ・・・式（９）
という条件を満足する写像と定義する。
【００９５】
このとき、
性質５．Ｄは存在し、かつ唯一である
性質６．以下の式が成立する
Ｆ（Ｇ）＝Ｄ（Ｒ（Ｇ））                  ・・・式（１０）
性質７．任意のｆ，ｇ∈Ｘに対して、以下の式が成り立つ
Ｄ（ｆ−ｇ）＝Ｄ（ｆ）−Ｄ（ｇ）                  ・・・式（１１）
Ｄ（１）＝０                                      ・・・式（１２）
Ｄ（ｆ／ｇ）＝｛ｇＤ（ｆ）−Ｄ（ｇ）ｆ｝／（ｇ２  ）・・・式（１３）
Ｄ（１−ｐｉ  ）＝（１−ｐｉ  ）μｉ                    ・・・式（１４）
但し、μｉ  ＝ｐｉ  λｉ  ／（１−ｐｉ  ）
という性質のあることが知られている（例えば、非特許文献２参照）。
【００９６】
次に、式（２）’の正当性を示す。
【００９７】
性質１の式（２）の両辺にＤを適用することで次の関係式が得られる。
【００９８】
【数１０】
2004363855.tif 000016
【００９９】
この関係式に対して式（７）と式（１４）とを適用することで、図２（ａ）に示す関係式が得られる。これに対して式（２）を利用してｐｘ’を消去することで、図２（ｂ）に示す関係式が得られ、これに対して式（７）〜式（１４）を用いることで、図２（ｃ）に示す関係式が得られる。この図２（ｃ）に示す関係式と式（２）とを並べてベクトル表現すれば、式（２）’が得られる。
【０１００】
次に、式（３）’の正当性を示す。
【０１０１】
性質１の式（３）に対して式（７）〜式（１４）を用いることで、図３（ａ）に示す関係式が得られ、この図３（ａ）に示す関係式と式（３）とを変形した上で並べると、図３（ｂ）に示す関係式が得られる。従って、図３（ｃ）に示す関係式が成り立ち、これを変形することで図３（ｄ）に示す関係式が得られる。この図３（ｄ）に示す関係式は式（３）’に一致する。
【０１０２】
次に、式（４）’の正当性を示す。
【０１０３】
式（４）’については、ノードが故障しない場合の並列の縮退と、故障に関する条件とが並列という意味では同一であることから、自ずと導かれる。
【０１０４】
次に、式（５）’の正当性を示す。
【０１０５】
式（５）’については、故障し得るノードが、二つの直列構成のリンクの間に挿入されていると考えれば、二つのリンクとその間にあるノードとの三つとが直列の関係にあることを考えることで、自ずと導かれる。
【０１０６】
次に、式（６）’の正当性を示す。
【０１０７】
性質４の式（６）に対して式（７）〜式（１４）を用いることで、図４（ａ）に示す関係式が得られ、この図４（ａ）に示す関係式と式（６）とを整理して並べると、図４（ｂ）に示す関係式が得られる。これから、図４（ｃ）に示す関係式が得られる。この図４（ｃ）に示す関係式は式（６）’に一致する。
【０１０８】
本発明は、この性質１’〜４’を用いる分解法に基づいて、ノードが故障しうるという条件下で、通信網の持つ指定される２つのノード間が通信不能となる故障頻度を高速に計算できるようにすることを実現する。
【０１０９】
次に、本発明の構成について説明する。
【０１１０】
本発明の通信網故障頻度計算装置は、リンクもノードも故障しうるという条件下で、通信網の持つ２つのノード間が通信不能となる故障頻度を計算する処理を行うものであって、（１）処理対象の通信網を、その２つのノードのいずれか一方又は双方が故障しないと見なした通信網に変換する第１の手段と、（２）第１の手段の変換した通信網の持つリンクの中からいずれか一方の端点が故障しないノードに接続されるリンクを選択して、そのリンクを短絡することにより得られる、そのリンクとそれに接続される２つのノードとを１つの故障しないノードとした通信網の持つ信頼度及び故障頻度と、そのリンクを開放することにより得られる、そのリンクを除去し、かつ、そのリンクが接続するノードの１つを故障しうるとした通信網の持つ信頼度及び故障頻度とをパラメータ値とする計算式に従って、第１の手段の変換した通信網の信頼度及び故障頻度を計算する第２の手段と、（３）第２の手段の計算した信頼度及び故障頻度に基づいて、処理対象の通信網の信頼度及び故障頻度を計算する第３の手段とを備えるように構成する。
【０１１１】
以上の各処理過程が動作することで実現される本発明の通信網故障頻度計算方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【０１１２】
このように構成されるときにあって、第２の手段は、短絡及び開放前の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、短絡後の通信網の信頼度をＲ（Ｇｅ  ）、故障頻度をＦ（Ｇｅ  ）、開放後の通信網の信頼度をＲ（Ｇｅ  ＊  ）、故障頻度をＦ（Ｇｅ  ＊  ）で表すならば、
2004363855.tif 000017
但し、ｐｅ  ：上記選択リンクの正常確率
λｅ  ：上記選択リンクの故障率
ｐｘ  ：上記選択リンクに接続される故障しうるノードの正常確率
λｘ  ：上記選択リンクに接続される故障しうるノードの故障率
という計算式に従って、第１の手段の変換した通信網の信頼度及び故障頻度を計算する。
【０１１３】
このとき、第２の手段は、開放後の通信網に残されたノードの正常確率ｐｘ’、故障率λｘ’を、
ｐｘ’＝ｐｘ  （１−ｐｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
λｘ’＝（１−ｐｘ  ）（λｘ  ＋μｘ  −μｅ  ）／［（１−ｐｘ  ）＋ｐｘ  （１−ｐｅ  ）］
但し、μｘ  ＝ｐｘ  λｘ  ／（１−ｐｘ  ）
で与えることになる。
【０１１４】
また、第３の手段は、第１の手段により２つのノードの双方が故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐＳ  ｐＴ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐＳ  ｐＴ  （λＳ  ＋λＴ  ）Ｒ（Ｇ０  ）＋ｐＳ  ｐＴ  Ｆ（Ｇ０  ）
但し、ｐＳ  ：いずれか一方のノードＳの正常確率
λＳ  ：いずれか一方のノードＳの故障率
ｐＴ  ：もう一方のノードＴの正常確率
λＴ  ：もう一方のノードＴの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算する。
【０１１５】
また、第３の手段は、第１の手段により２つのノードのいずれか一方だけが故障しないと見なした通信網に変換される場合に、その変換元の通信網Ｇの信頼度をＲ（Ｇ）、故障頻度をＦ（Ｇ）、その変換された通信網Ｇ０  の信頼度をＲ（Ｇ０  ）、故障頻度をＦ（Ｇ０  ）で表すならば、
Ｒ（Ｇ）＝ｐｋ  Ｒ（Ｇ０  ）＋０×Ｆ（Ｇ０  ）
Ｆ（Ｇ）＝ｐｋ  λｋ  Ｒ（Ｇ０  ）＋ｐｋ  Ｆ（Ｇ０  ）
但し、ｐｋ  ：故障しないと見なされない方のノードの正常確率
λｋ  ：故障しないと見なされない方のノードの故障率
という計算式に従って、処理対象の通信網の信頼度及び故障頻度を計算する。
【０１１６】
この構成に従って、本発明によれば、通信網において、リンクもノードも故障しうるという条件下で、あるノードとあるノードとの間が通信不能となる故障が発生する頻度の平均値（故障頻度）を分解法を使って計算できるようになることから、通信網の故障頻度を高速に計算できるようになるとともに、ノードの故障も考慮に入れて故障頻度を計算することから、通信網の故障頻度を高精度に計算できるようになる。
【０１１７】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
【０１１８】
図５に、本発明を具備する通信網故障頻度計算装置１の装置構成の一例を図示する。
【０１１９】
この図に示すように、本発明の通信網故障頻度計算装置１は、通信網の形状を表すデータと故障頻度計算に必要なデータとを格納する記憶部１０と、そのデータに縮退の処理を行う縮退部１１と、そのデータに分解の処理を行う分解部１２と、計算全体を統括する制御部１３とを備えるとともに、入力装置として、キーホード１４を備え、出力装置として、表示制御部１５／表示メモリ１６／ＣＲＴ１７を備える。
【０１２０】
先ず最初に、記憶部１０に記憶されるデータの構造について説明し、続いて、縮退部１１の処理機能、分解部１２の処理機能、制御部１３の処理機能のそれぞれについて説明する。
【０１２１】
（１）記憶部１０に記憶されるデータの構造
記憶部１０は、故障頻度計算に必要となる通信網データを記憶する。
【０１２２】
図６に、記憶部１０に記憶される通信網データの構造を示す。なお、図６中に示す数値は、一例を示すための仮想値である。
【０１２３】
この図に示すように、記憶部１０に記憶される通信網データは、通信網形状データとノードデータと暫定パラメータとから構成される。
【０１２４】
通信網形状データにおいては、各行が通信網の持つリンクに対応し、各行の成分は、そのリンクのリンク番号、そのリンクが接続するノードのノード番号、そのリンクの正常確率、そのリンクの故障率に対応する。
【０１２５】
ノードデータにおいては、各行が通信網の持つノードに対応し、各行の成分は、そのノードのノード番号、そのノードが信頼性上着目している二つのノード（Ｓ，Ｔ）であるのか否かの情報、そのノードの正常確率、そのノードの故障率に対応する。
【０１２６】
暫定パラメータは、計算の途中に登場する式（６）’の係数（ｐＳ，ｐＴ，λＳ，λＴ  ）を格納する領域として用意され、初期値としては、ノード、リンクの正常確率が１、ノード、リンクの故障率が０となっているものとする。
【０１２７】
本発明の通信網故障頻度計算装置１は、ノード番号Ｓのノードとノード番号Ｔのノードとの間が非連結となる故障頻度を求めることになる。
【０１２８】
以下、説明のために、リンク番号ｘのリンクに接続しているノード番号を、図６のデータ構造において左からｎ１（ｘ），ｎ２（ｘ）と表し、また、リンク番号ｘのリンクが正常である確率をｐｘ  、故障率をλｘ  で表し、ノード番号ｙのノードが正常である確率をｐｙ  、故障率をλｙ  で表すことにする。
【０１２９】
（２）縮退部１１の処理機能
縮退部１１は、記憶部１０に記憶されている通信網データから、直列と並列の縮退が可能な部分を見つけ出して、実際に適用する処理を行う。この処理を行うために、縮退部１１は、ノード次数カウンタ、直列縮退変換部、並列縮退変換部を備える。
【０１３０】
（２−１）ノード次数カウンタの処理機能
ノード次数カウンタは、図７の処理フローを実行することで、記憶部１０に記憶されている通信網データから、各ノードに接続しているリンク数（次数）を数え上げる処理を行って、それを記憶する。
【０１３１】
各ノードの次数のカウント結果については、ｄ（１）〜ｄ（Ｎ）に格納されることになる。
【０１３２】
（２−２）直列縮退変換部の処理機能
直列縮退変換部は、図８の処理フローを実行することで、記憶部１０に記憶されている通信網データから、直列構成の二つのリンクを探索して、直列の縮退を実行する。
【０１３３】
（２−３）並列縮退変換部の処理機能
並列縮退変換部は、図９の処理フローを実行することで、記憶部１０に記憶されている通信網データから、並列構成の二つのリンクを探索して、並列の縮退を実行する。
【０１３４】
縮退部１１は、これらのノード次数カウンタ／直列縮退変換部／並列縮退変換部を使い、図１０の処理フローに示すように、先ず最初に、ステップ１０で、入力された通信網データの全リンク数Ｍを求め、続くステップ１１で、ノード次数カウンタを使って各ノードの次数をカウントする。
【０１３５】
続いて、ステップ１２で、ノードの次数を参照しつつ、直列縮退変換部を使って、ノード次数カウンタによりカウントされたノードの次数を参照しつつ直列縮退変換を実行し、続くステップ１３で、並列縮退変換部を使って、ノード次数カウンタによりカウントされたノードの次数を参照しつつ並列縮退変換を実行する。
【０１３６】
続いて、ステップ１４で、縮退変換を施すことで書き替えた通信網データの全リンク数Ｍ０  を求め、続くステップ１５で、Ｍ０  がＭよりも小さいのか否かを判断して、Ｍ０  がＭよりも小さいことを判断するときには、ステップ１６に進んで、Ｍ０  を新たなＭと設定して、ステップ１１に戻り、Ｍ０  がＭよりも小さくならないことを判断するときには、処理を終了する。
【０１３７】
このようにして、縮退部１１は、入力された通信網データを可能な限り縮退するように処理するのである。
【０１３８】
（３）分解部１２の処理機能
分解部１２は、記憶部１０に記憶されている通信網データにおいて特定のリンクに着目し、その着目リンクを短絡除去した通信網に対応するデータと、その着目リンクを開放除去した通信網に対応するデータとを生成する処理を行う。この処理を行うために、分解部１２は、短絡除去部と開放除去部とを備える。
【０１３９】
（３−１）短絡除去部の処理機能
短絡除去部は、図１１の処理フローを実行することで、通信網データから、着目リンク（リンク番号ｅ）を短絡除去した通信網Ｇｅ  のデータを生成する。
【０１４０】
ここで、上述したように、ノードｘの両端のノードはｎ１（ｘ），ｎ２（ｘ）で表している。
【０１４１】
（３−２）開放除去部の処理機能
開放除去部は、図１２の処理フローを実行することで、通信網データから、着目リンク（リンク番号ｅ）を開放除去した通信網Ｇｅ  ＊  のデータを生成する。
【０１４２】
（４）制御部１３の処理機能
制御部１３は、縮退部１１及び分解部１２を制御して、Ｓ，Ｔ間の故障頻度を計算する処理を行う。説明のために、次の記号を導入する。
【０１４３】
【数１１】
2004363855.tif 000018
【０１４４】
（４−１）制御部１３の主手続き
制御部１３は、先ず最初に、Ｇの通信網データをその二つのノードＳ，Ｔが故障しないとしたＧ０  の通信網データに変換する。正常確率ｐＳ，ｐＴ  と故障率λＳ，λＴ  については、記憶部１０の暫定パラメータ記憶領域に保存しておく。
【０１４５】
制御部１３は、続いて、後述する関数ｆを用いて、Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０  ）とＳ−Ｔ間故障頻度Ｆ（Ｇ０  ）とを求める。
【０１４６】
制御部１３は、続いて、式（６）’と等価な次の関係式に従って、ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）とＳ−Ｔ間故障頻度Ｆ（Ｇ）とを求める。
【０１４７】
【数１２】
2004363855.tif 000019
【０１４８】
このようにして、制御部１３は、Ｓ−Ｔ間故障頻度Ｆ（Ｇ）を求めるのである。
【０１４９】
（４−２）制御部１３の主手続き中の関数ｆの詳細
関数ｆは通信網Ｇ０  の通信網データを受け取り、Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０  ）とＳ−Ｔ間故障頻度Ｆ（Ｇ０  ）とを算出する処理を行う。すなわち、関数ｆ（Ｇ０  ）は次の関数演算を実行する。
【０１５０】
【数１３】
2004363855.tif 000020
【０１５１】
関数ｆ（Ｇ０  ）は再帰的な手順を用いる。この関数ｆ（Ｇ）は、以下の処理を実行する。
【０１５２】
すなわち、先ず最初に、通信網Ｇ０  を表すデータに、縮退部１１を用いて、直並列の縮退をこれ以上縮退できなくなるまで（縮退を適用してもリンク数が減らなくなるまで）繰り返す。
【０１５３】
直並列の縮退をこれ以上縮退できなくなるまで繰り返した結果、縮退した通信網Ｇ０  が１リンクとなった場合には、そのリンクの信頼度Ｒ０  と、そのリンクの故障率ＦＲ０  とから、関数ｆ（Ｇ０  ）の値として、次の値を計算して返す。
【０１５４】
【数１４】
2004363855.tif 000021
【０１５５】
一方、直並列の縮退をこれ以上縮退できなくなるまで繰り返した結果、縮退した通信網が１リンクとならない場合には、故障しないノードに接続する任意のリンクｅを選択して、分解部１２を用いて、Ｇ０  ｅ  とＧ０  ｅ  ＊  とを表すデータを生成し、自分自身（関数ｆ）をコールすることでｆ（Ｇ０  ｅ  ）とｆ（Ｇ０  ｅ  ＊  ）とを算出する。
【０１５６】
そして、式（３）’と等価となる
ｆ（Ｇ０  ）＝Ｐｅ  ・ｆ（Ｇ０  ｅ  ）＋（Ｅ−Ｐｅ  ）・ｆ（Ｇ０  ｅ  ＊  ）
という式に従って、関数ｆ（Ｇ０  ）の値を計算して返す。ここで、ＥとＰｅ  は次の式で定義されるものである。
【０１５７】
【数１５】
2004363855.tif 000022
【０１５８】
次に、図１３（ａ）に示す通信網Ｇを具体例にして、本発明による故障頻度計算処理について具体的に説明する。
【０１５９】
ここで、図１３（ａ）に示す通信網Ｇについての通信網形状データ、ノードデータ、暫定パラメータについては、図１３（ｂ）に示すものを想定するとともに、ノード９とノード１０との間の故障頻度について計算することを想定する。
【０１６０】
先ず最初に、制御部１３の主手続きのステップとして、Ｇの通信網データをノードＳ，Ｔが故障しないとしたＧ０  の通信網データに変換する。この変換処理に従って、図１３（ｂ）に示す通信網データは図１４のように書き換えられることになる。すなわち、ノード９の正常確率が１、故障率が０に書き換えられるとともに、ノード１０の正常確率が１、故障率が０に書き換えられ、さらに、暫定パラメータが初期値から、正規の値に書き換えられることになる。
【０１６１】
続いて、関数ｆが適用される。関数ｆの中では、まず直並列の縮退が実行される。図１４の通信網データの場合には、リンク６を着目リンクとして並列の縮退が実行され、これにより、Ｇ０  を表す通信網データは、図１４に示すものから図１５のように書き換えられることになる。なお、以下では暫定パラメータは変更されないので、その記述を省略してある。
【０１６２】
これ以上縮退を適用してもリンク数が減らないので、続いて、Ｇ０  を分解する操作が適用され、図１６の通信網データを持つＧ０  ｅ  と、図１７の通信網データを持つＧ０  ｅ  ＊  とが生成される。ここで、この場合には、着目するリンクとしてリンク１が選択されたことを想定している（リンク１を接続するノード９が故障しないので分解を適用できる）。
【０１６３】
続いて、関数ｆの次のステップとして、関数ｆ（Ｇ０  ｅ  ）とｆ（Ｇ０  ｅ  ＊  ）とが計算される。
【０１６４】
ｆ（Ｇ０  ｅ  ）の計算については、図１６に示す通信網データを持つＧ０  ｅ  に縮退が適用されることで、図１８及び図１９に示すような形で縮退が実行されて、１リンクまで縮退されたことにより、関数ｆは以下の値を返す。
【０１６５】
【数１６】
2004363855.tif 000023
【０１６６】
そして、ｆ（Ｇ０  ｅ  ＊  ）の計算については、図１７に示す通信網データを持つＧ０  ｅ  ＊  に縮退が適用されることで、図２０及び図２１に示すような形で縮退が実行されて、１リンクまで縮退されたことにより、関数ｆは以下の値を返す。
【０１６７】
【数１７】
2004363855.tif 000024
【０１６８】
これから、式（３）’を使って、図２２（ａ）に示すように、分解前の通信網Ｇ０  のＲ（Ｇ０  ）とＦ（Ｇ０  ）とが計算され、最後に、式（６）’と暫定パラメータとを使って、図２２（ｂ）に示すように、Ｇ０  の変換元となった通信網ＧのＲ（Ｇ）とＦ（Ｇ）とが計算されることで、
Ｆ（Ｇ）＝０．３００
と、Ｓ−Ｔ間故障頻度が求められることになる。
【０１６９】
このようにして、本発明の通信網故障頻度計算装置１によれば、ノードが故障しうるという条件下において、分解法を使って、あるノードＳとあるノードＴとの間が通信不能となる故障発生の故障頻度を計算できるようになる。
【０１７０】
次に、図２３及び図２４に従って、制御部１３の実行する故障頻度計算処理のための制御処理について、さらに詳細に説明する。
【０１７１】
制御部１３は、図２３の処理フローに示すように、先ず最初に、ステップ１０で、通信網Ｇを２つのノードＳ，Ｔが故障しないとした通信網Ｇ０  に変換し、続くステップ１１で、関数ｆを用いて、その変換した通信網Ｇ０  のＳ−Ｔ間信頼度Ｒ（Ｇ０  ）とＳ−Ｔ間故障頻度Ｆ（Ｇ０  ）を計算し、続くステップ１２で、式（６）’に従って、通信網Ｇ０  の変換元となった通信網ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）とＳ−Ｔ間故障頻度Ｆ（Ｇ）を計算する処理を行う。
【０１７２】
この関数ｆは、主手続きから通信網Ｇ０  を指定して呼び出されると、図２４の処理フローに示すように、先ず最初に、ステップ２０で、通信網Ｇ０  を処理対象の通信網として設定する。
【０１７３】
続いて、ステップ２１で、処理対象の通信網に対して、縮退部１１を用いて、これ以上縮退できなくなるまで直並列の縮退を繰り返す。このとき、式（４）’及び式（５）’を使って、ノードやリンクの正常確率や故障率を算出することになる。
【０１７４】
続いて、ステップ２２で、ステップ２１の処理に従って処理対象の通信網が１リンクまで縮退できたのか否かを判断して、１リンクまで縮退できないことを判断するときには、ステップ２３に進んで、分解部１２を使って、処理対象の通信網の持つ故障しないノードに接続されるリンクを選択して分解することで、新たな処理対象の通信網を設定してから、ステップ２１に戻る。このとき、式（２）’を使って、ノードやリンクの正常確率や故障率を算出することになる。
【０１７５】
一方、ステップ２２で処理対象の通信網が１リンクまで縮退できたことを判断するときには、ステップ２４に進んで、処理対象の通信網のＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算し、続くステップ２５で、全ての処理対象の通信網についてＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算したのか否かを判断して、未計算のものが残されているときには、ステップ２１に戻る。
【０１７６】
一方、ステップ２５で、全ての処理対象の通信網についてＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算したことを判断するときには、ステップ２６に進んで、式（３）’に従って、分解前通信網のＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算することを繰り返すことで、通信網Ｇ０  のＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算して、呼び出し元である主手続きに返却する。
【０１７７】
このようにして、制御部１３は、通信網ＧのＳ−Ｔ間信頼度Ｒ（Ｇ）とＳ−Ｔ間故障頻度Ｆ（Ｇ）を計算するのである。
【０１７８】
ここで、図２４の処理フローでは、全ての処理対象の通信網を１リンクまで縮退させてから分割前の通信網のＳ−Ｔ間信頼度やＳ−Ｔ間故障頻度の計算に入るようにしているが、分割前の通信網のＳ−Ｔ間信頼度やＳ−Ｔ間故障頻度の計算ができるようになった時点で、その都度、その分割前の通信網のＳ−Ｔ間信頼度やＳ−Ｔ間故障頻度の計算に入るようにしてもよいことは言うまでもない。
【０１７９】
図示実施形態例に従って本発明を説明したが、本発明はこれに限定されるものではない。例えば、実施形態例では、通信網Ｇを２つのノードＳ，Ｔが故障しないとした通信網Ｇ０  に変換するようにしているが、性質１’で説明したように、着目リンクが接続する二つのノードのうち片方が故障しないノードならば着目リンクについて分解法を利用できることから明らかなように、通信網Ｇを２つのノードＳ，Ｔのうちのいずれか一方だけが故障しないとした通信網Ｇ０’に変換することでも本発明は実現可能である。
【０１８０】
通信網Ｇを２つのノードＳ，Ｔが故障しないとした通信網Ｇ０  に変換する場合には、実際にはノードＳ，Ｔが故障することに対応させて、式（６）’においてｐＳ，ｐＴ，λＳ，λＴ  を使ってＲ（Ｇ０  ）とＦ（Ｇ０  ）とを本来のものへと補正するようにしているが、例えばノードＳのみを故障しないとした通信網Ｇ０’に変換する場合には、ノードＴについては元に戻す必要がないことから、式（６）’中のｐＴ，λＴ  をそれぞれ１と０に書き換えたものを使ってＲ（Ｇ０  ）とＦ（Ｇ０  ）とを本来のものへと補正することになる。
【０１８１】
それと同時に、２つのノードＳ，Ｔのうちのいずれか一方だけが故障しないとした通信網Ｇ０’に変換する場合には、１リンクに縮退させてＳ−Ｔ間信頼度とＳ−Ｔ間故障頻度を計算する際に、故障しうるとされるもう一方のノードの正常確率及び故障率を考慮した形で、その計算を行うことになる。
【０１８２】
【発明の効果】
以上説明したように、本発明によれば、通信網において、リンクもノードも故障しうるという条件下で、あるノードとあるノードとの間が通信不能となる故障が発生する頻度の平均値（故障頻度）を分解法を使って計算できるようになることから、通信網の故障頻度を高速に計算できるようになるとともに、ノードの故障も考慮に入れて故障頻度を計算することから、通信網の故障頻度を高精度に計算できるようになる。
【図面の簡単な説明】
【図１】本発明によるＳ−Ｔ間故障頻度の計算処理の説明図である。
【図２】本発明の基礎となる基本的な性質を導出する際の計算式の説明図である。
【図３】本発明の基礎となる基本的な性質を導出する際の計算式の説明図である。
【図４】本発明の基礎となる基本的な性質を導出する際の計算式の説明図である。
【図５】本発明の通信網故障頻度計算装置の装置構成の一例を示す図である。
【図６】記憶部に格納される通信網データの説明図である。
【図７】ノード次数カウンタの実行する処理フローである。
【図８】直列縮退変換部の実行する処理フローである。
【図９】並列縮退変換部の実行する処理フローである。
【図１０】縮退部の実行する処理フローである。
【図１１】短絡除去部の実行する処理フローである。
【図１２】開放除去部の実行する処理フローである。
【図１３】通信網データの一例を示す図である。
【図１４】変換された通信網データの説明図である。
【図１５】縮退された通信網データの説明図である。
【図１６】分解された通信網データの説明図である。
【図１７】分解された通信網データの説明図である。
【図１８】通信網データの縮退の説明図である。
【図１９】通信網データの縮退の説明図である。
【図２０】通信網データの縮退の説明図である。
【図２１】通信網データの縮退の説明図である。
【図２２】Ｓ−Ｔ間故障頻度の計算処理の説明図である。
【図２３】制御部の実行する処理フローである。
【図２４】制御部の実行する処理フローである。
【図２５】通信網の一例を示す図である。
【図２６】通信網の並列縮退の説明図である。
【図２７】通信網の直列縮退の説明図である。
【図２８】通信網の一例を示す図である。
【図２９】通信網の分解の説明図である。
【図３０】通信網の分解の説明図である。
【図３１】通信網の短絡・開放の説明図である。
【図３２】通信網の並列縮退の説明図である。
【図３３】通信網の直列縮退の説明図である。
【図３４】通信網の分解の説明図である。
【符号の説明】
１    通信網故障頻度計算装置
１０  記憶部
１１  縮退部
１２  分解部
１３  制御部
１４  キーホード
１５  表示制御部
１６  表示メモリ
１７  ＣＲＴ
【図１】
2004363855.tif 000027
【図２】
2004363855.tif 000028
【図３】
2004363855.tif 000029
【図４】
2004363855.tif 000030
【図５】
2004363855.tif 000031
【図６】
2004363855.tif 000032
【図７】
2004363855.tif 000033
【図８】
2004363855.tif 000034
【図９】
2004363855.tif 000035
【図１０】
2004363855.tif 000036
【図１１】
2004363855.tif 000037
【図１２】
2004363855.tif 000038
【図１３】
2004363855.tif 000039
【図１４】
2004363855.tif 000040
【図１５】
2004363855.tif 000041
【図１６】
2004363855.tif 000042
【図１７】
2004363855.tif 000043
【図１８】
2004363855.tif 000044
【図１９】
2004363855.tif 000045
【図２０】
2004363855.tif 000046
【図２１】
2004363855.tif 000047
【図２２】
2004363855.tif 000048
【図２３】
2004363855.tif 000049
【図２４】
2004363855.tif 000050
【図２５】
2004363855.tif 000051
【図２６】
2004363855.tif 000052
【図２７】
2004363855.tif 000053
【図２８】
2004363855.tif 000054
【図２９】
2004363855.tif 000055
【図３０】
2004363855.tif 000056
【図３１】
2004363855.tif 000057
【図３２】
2004363855.tif 000058
【図３３】
2004363855.tif 000059
【図３４】
2004363855.tif 000060