(57)【要約】【課題】本発明は、通信網の２つのノード間が通信不能となる故障頻度を高速に計算できるようにする新たな通信網故障頻度計算技術の提供を目的とする。【解決手段】計算したい通信網の持つあるリンクを短絡した通信網の信頼度及び故障頻度と、計算したい通信網からそのリンクを開放した通信網の信頼度及び故障頻度とをパラメータ値とする計算式に従って、計算したい通信網の信頼度及び故障頻度を計算するという構成を採る。これにより、あるノードＳとあるノードＴとの間が通信不能となる故障が発生する故障頻度を分解法を使って計算できるようになることから、通信網の故障頻度を高速に計算できるようになる。【選択図】          図１
2004282275.tif 000002
【特許請求の範囲】
【請求項１】
通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算方法であって、
計算したい通信網の持つあるリンクを短絡した通信網の信頼度及び故障頻度と、計算したい通信網からそのリンクを開放した通信網の信頼度及び故障頻度とをパラメータ値とする計算式に従って、計算したい通信網の信頼度及び故障頻度を計算することを、
特徴とする通信網故障頻度計算方法。
【請求項２】
処理対象となる通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算方法であって、
処理対象の通信網を計算対象の通信網の起点として、計算対象の通信網を縮退して、１リンクへ縮退できる場合には、その１リンクの信頼度及び故障頻度から計算対象の通信網の信頼度及び故障頻度を計算し、１リンクへ縮退できない場合には、計算対象の通信網の持つあるリンクを短絡した通信網とそのリンクを開放した通信網とを新たな計算対象の通信網として、この処理を繰り返す過程と、
上記短絡した通信網の信頼度及び故障頻度と、上記開放した通信網の信頼度及び故障頻度とをパラメータ値とする計算式に従って、その短絡及び開放前の通信網の信頼度及び故障頻度を計算して、処理対象の通信網の信頼度及び故障頻度が計算できるまで、この処理を繰り返す過程とを備えることを、
特徴とする通信網故障頻度計算方法。
【請求項３】
請求項１又は２記載の通信網故障頻度計算方法において、
上記計算式は、上記短絡及び開放前の通信網の信頼度をＲ（Ｇ）、その通信網の故障頻度をＦ（Ｇ）、あるリンクｅを短絡した通信網の信頼度をＲ（Ｇｅ  ）、その通信網の故障頻度をＦ（Ｇｅ  ）、そのリンクｅを開放した通信網の信頼度をＲ（Ｇｅ  ＊  ）、その通信網の故障頻度をＦ（Ｇｅ  ＊  ）、そのリンクｅの正常確率をｐｅ  、そのリンクｅの故障率をλｅ  とするならば、
2004282275.tif 000021
という式構造を持つことを、
特徴とする通信網故障頻度計算方法。
【請求項４】
通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算装置であって、
計算したい通信網の持つあるリンクを短絡した通信網の信頼度及び故障頻度と、計算したい通信網からそのリンクを開放した通信網の信頼度及び故障頻度とをパラメータ値とする計算式に従って、計算したい通信網の信頼度及び故障頻度を計算する手段を備えることを、
特徴とする通信網故障頻度計算装置。
【請求項５】
処理対象となる通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算装置であって、
処理対象の通信網を計算対象の通信網の起点として、計算対象の通信網を縮退して、１リンクへ縮退できる場合には、その１リンクの信頼度及び故障頻度から計算対象の通信網の信頼度及び故障頻度を計算し、１リンクへ縮退できない場合には、計算対象の通信網の持つあるリンクを短絡した通信網とそのリンクを開放した通信網とを新たな計算対象の通信網として、この処理を繰り返す手段と、
上記短絡した通信網の信頼度及び故障頻度と、上記開放した通信網の信頼度及び故障頻度とをパラメータ値とする計算式に従って、その短絡及び開放前の通信網の信頼度及び故障頻度を計算して、処理対象の通信網の信頼度及び故障頻度が計算できるまで、この処理を繰り返す手段とを備えることを、
特徴とする通信網故障頻度計算装置。
【請求項６】
請求項４又は５記載の通信網故障頻度計算装置において、
上記計算式は、上記短絡及び開放前の通信網の信頼度をＲ（Ｇ）、その通信網の故障頻度をＦ（Ｇ）、あるリンクｅを短絡した通信網の信頼度をＲ（Ｇｅ  ）、その通信網の故障頻度をＦ（Ｇｅ  ）、そのリンクｅを開放した通信網の信頼度をＲ（Ｇｅ  ＊  ）、その通信網の故障頻度をＦ（Ｇｅ  ＊  ）、そのリンクｅの正常確率をｐｅ  、そのリンクｅの故障率をλｅ  とするならば、
2004282275.tif 000022
という式構造を持つことを、
特徴とする通信網故障頻度計算装置。
【請求項７】
請求項１ないし３のいずれか１項に記載の通信網故障頻度計算方法の実現に用いられる処理をコンピュータに実行させるための通信網故障頻度計算プログラム。
【請求項８】
請求項１ないし３のいずれか１項に記載の通信網故障頻度計算方法の実現に用いられる処理をコンピュータに実行させるための通信網故障頻度計算プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する通信網故障頻度計算方法及びその装置と、その通信網故障頻度計算方法の実現に用いられる通信網故障頻度計算プログラム及びそのプログラムを記録した記録媒体とに関する。
【０００２】
更に具体的に説明するならば、本発明は、通信網において、あるノードＳとあるノードＴとの間が通信不能となる故障が発生する頻度の平均値（故障頻度）を計算する技術に関するものである。
【０００３】
【従来の技術】
通信網の信頼性とは、通信が安定して行われる度合いまたは性質を表す。通信網は点と線とからなり、点は通信装置（交換機、多重化装置等）、線は回線装置を表す。点で表される通信装置のことを、以下ではノードと呼び、線で表される回線装置のことを、以下ではリンクと呼ぶ。
【０００４】
通信網の信頼性は、まず、特定の二つのノード（それぞれＳ，Ｔと書く）に着目し、この着目ノード間が通信可能である確率（Ｓ，Ｔ間の信頼度。以下、Ｓ−Ｔ間信頼度と記載することがある）、あるいは、この着目ノード間が通信不可能となる故障の平均発生頻度（Ｓ，Ｔ間の故障頻度。以下、Ｓ−Ｔ間故障頻度と記載することがある）で評価される。
【０００５】
Ｓ−Ｔ間信頼度は、０から１の範囲の値をとる確率として表され、一方、Ｓ−Ｔ間故障頻度は、例えば、年に何回という尺度で表される。Ｓ−Ｔ間信頼度もＳ−Ｔ間故障頻度も共に、重要な信頼性評価尺度として用いられている。
【０００６】
ここで、ノードは故障しないと仮定する。何故ならば、ノードは通信網内で、頑丈な局舎に囲まれていると想定されることが多いこと、また、局舎内では、故障しても直ちに保守要員が復旧に当たることができること等を考えると、故障した場合の保守が容易ではない局社外ケーブル断によって引き起こされる回線装置の故障に比べれば、故障発生を無視できると考えられるからである。
【０００７】
この前提の下で、各リンクの正常確率（正常である（故障していない）確率）と、各リンクの故障率（単位時間の平均故障回数）とから、Ｓ−Ｔ間信頼度およびＳ−Ｔ間故障頻度を計算する方法にはいくつかの方法あるが、基本的となる三つの方法が考えられる。説明の容易さのため、Ｓ−Ｔ間信頼度について、まず述べる。
【０００８】
Ｓ−Ｔ間信頼度を計算する方法として、下記に示す縮退法、パス法、分解法という三つの手法がある。
（１）通信網の信頼度を保存しながら、通信網の形状を単純化する（縮退法）。
（２）着目ノード間の通信パスを全て列挙し、少なくとも一つの通信パスが存在している確率を計算する（パス法）。
（３）あるリンクに着目し、そのリンクが接続する二つのノードを一つと見なした通信網と、そのリンクを除去した通信網という二つの通信網に分解して、分解によって得られた二つの通信網の信頼度から、最初の通信網の信頼度を計算する（分解法）。
【０００９】
次に、これらの三つの手法の概要について説明する。
【００１０】
図２０の通信網構成で、Ｓ，Ｔ間の信頼度を計算する場合について説明する。説明のため、リンクには図中のような番号が与えられているとする。以下、各リンクは、この番号で識別される。そして、リンクｉが正常である確率をそれぞれｐｉ  する。
【００１１】
図２０に示す通信網において、リンク１，２は、その何れかが故障しても、他方が正常であれば、通信の確保に支障は無い。リンク１，２の何れかが正常であれば、通信は確保できる（このような関係を並列と呼ぶ）。
【００１２】
つまり、リンク１，２という二つのリンクは、図２１に示すように、リンク１，２の何れかが正常である確率を改めて、リンクの正常確率として与えられた一つのリンク４に置き換えても、Ｓ−Ｔ間信頼度の計算上は等価である。ここで、リンク４が正常である確率ｐ４  は、「ｐ４  ＝ｐ１  ＋ｐ２  −ｐ１  ｐ２  」で与えられる。
【００１３】
このようにＳ，Ｔ間の信頼度を変えずに、通信網をより簡単な構成に置き換えることを縮退と呼び、図２１のように、並列構成のリンクを１リンクに置き換える操作を並列の縮退と呼ぶ。
【００１４】
図２１の縮退で得られた通信網は、リンク４とリンク３とから構成されるが、これらの二つのリンクは、両方が正常であって初めてＳ，Ｔ間の通信が確保できる（このような関係を直列の関係と呼ぶ）。
【００１５】
つまり、リンク４，３という二つのリンクは、図２２に示すように、リンク４，３の両方が正常である確率を改めて、リンクの正常確率として与えられた一つのリンク５に置き換えても、Ｓ−Ｔ間信頼度の計算上は等価である。ここで、リンク５が正常である確率ｐ５  は、「ｐ５  ＝ｐ４  ｐ３  」で与えられる。
【００１６】
図２２のように、直列構成のリンクを１リンクに置き換える操作を直列の縮退と呼ぶ。
【００１７】
結局、図２０の通信網は、図２２のように等価な１リンクに置き換えることができる。この場合、Ｓ−Ｔ間信頼度は、ＳとＴとが通信できる確率であるから、明らかにｐ５  である。
【００１８】
図２２の直列の縮退の変換式より、
Ｓ−Ｔ間信頼度＝ｐ５  ＝ｐ４  ｐ３  
となる。ところが、図２１の並列の縮退の変換式より、
ｐ４  ＝ｐ１  ＋ｐ２  −ｐ１  ｐ２  
であるから、結局、Ｓ−Ｔ間信頼度は、
Ｓ−Ｔ間信頼度＝ｐ５  ＝ｐ４  ｐ３  ＝（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）ｐ３  
というように求められる。
【００１９】
このように、通信網が、直列と並列で構成されていれば、縮退を用いて、そのＳ，Ｔ間の信頼度を求めることができる。しかし、直列でも並列でもない構成を含む場合、例えばブリッジと呼ばれる図２３のような場合には、縮退法だけでは、Ｓ，Ｔ間の信頼度を求めることは出来ない。この場合には、パス法または分解法が用いられる。
【００２０】
パス法は、ＳとＴとの通信を確保するために必要な極小なリンク集合（以下、パスと呼ぶ）を列挙し、少なくとも一つのパスが使用できる確率を求めるものである。
【００２１】
例えば、リンク１，２が正常であれば、他のリンクが故障していても、ＳとＴとの間の通信は確保され、しかし、さらに、リンク１またはリンク２が故障すると、ＳとＴとの間の通信は確保されない場合、リンク集合｛１，２｝は極小なリンク集合を構成して、パスの一つとなる。
【００２２】
このような極小なリンク集合の定義に従って、図２３の場合、パスは、
パス１：｛１，３｝        パス２：｛２，５｝
パス３：｛１，４，５｝    パス４：｛２，４，３｝
という４つであることが分かる。
【００２３】
求める必要のあるＳ，Ｔ間の信頼度は、パスｊ（ｊ＝１，２，  …）に属するリンクが全て正常である事象をＥｊ  とすれば、
Ｓ−Ｔ間信頼度＝Ｐｒ（Ｅ１  ∪Ｅ２  ∪Ｅ３  ∪Ｅ４  ）
となる。
【００２４】
この式の右辺を、例えば包除原理（「藤木，”システムの信頼性理論”，信学誌，  ５９，４，ｐ．３４６（１９８４）」参照）で展開すれば、Ｓ−Ｔ間信頼度は、
2004282275.tif 000003
と求められる。
【００２５】
パス法は、直列と並列とからなる通信網構成に限らず、任意の形状の通信網のＳ，Ｔ間の信頼度計算に適用可能である。
【００２６】
その他に、任意の形状の通信網のＳ，Ｔ間の信頼度の計算法として、分解法と呼ばれる方法がある。これは、以下の操作に基づいた計算法である。
【００２７】
この分解法では、
＜１＞先ず最初に、Ｓ，Ｔ間の信頼度を求めたい通信網の一つのリンクに着目して、通信網と着目リンクを取り除いた上で、着目リンクの両端ノードを一つのノードと見なした（以下、この操作を短絡除去と呼ぶ）通信網を生成し、
＜２＞続いて、その着目リンクを取り除いた（以下、この操作を開放除去と呼ぶ）通信網を生成し（＜１＞＜２＞によって二つの通信網を生成する操作を「通信網を分解する」と呼ぶ）、
＜３＞続いて、その得られた二つの通信網のＳ，Ｔ間の信頼度から、分解前の通信網のＳ，Ｔ間の信頼度を一定の変換式によって計算する、
という手順に従って、任意の形状の通信網のＳ，Ｔ間の信頼度を計算する。
【００２８】
例えば、図２３の通信網をリンク４に着目して分解すると、図２４のようになる。
【００２９】
今、通信網をＧで表し、ＧのＳ，Ｔ間の信頼度をＲ（Ｇ）で表す。また、Ｇにおいて、リンクｅを短絡除去して得られた通信網をＧｅ  、リンクｅを開放除去して得られた通信網をＧｅ  ＊  と書けば、
Ｒ（Ｇ）＝ｐｅ  Ｒ（Ｇｅ  ）＋（１−ｐｅ  ）Ｒ（Ｇｅ  ＊  ）・・・式（１）
但し、ｐｅ  ：リンクｅの正常である確率
という式（１）の成立することが知られている。
【００３０】
図２４の場合、求めたいＳ，Ｔ間の信頼度は、直並列の縮退と式（１）とを用いて計算できる。
【００３１】
すなわち、リンク４を短絡除去して得られた通信網（図２４の左側の通信網）については、直並列の縮退を用いて、
Ｓ−Ｔ間信頼度＝（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）（ｐ３  ＋ｐ５  −ｐ３  ｐ５  ）
が成り立つ。一方、リンク４を開放除去して得られた通信網（図２４の右側の通信網）については、同様に直並列の縮退を用いて、
Ｓ−Ｔ間信頼度＝ｐ１  ｐ３  ＋ｐ２  ｐ５  −ｐ１  ｐ２  ｐ３  ｐ５  
が成り立つ。
【００３２】
従って、求めたい分解前の通信網のＳ，Ｔ間の信頼度は、上述の式（１）を用いて、
2004282275.tif 000004
と求められる。
【００３３】
分解によって得られた通信網が、直列と並列の組み合わせで表現できる構成であれば、以上の方法によって、その信頼度を計算できる。もし、直列と並列のみで表現できなければ、さらに分解を繰り返せばよい。図２５に、より複雑な分解の例を示す。
【００３４】
このようにして、任意の形状の通信網のＳ，Ｔ間の信頼度を分解法に基づいて計算することができる。
【００３５】
以上に説明したように、縮退法、パス法、分解法を用いて、通信網のＳ，Ｔ間の信頼度を求めることができることが知られている。
【００３６】
しかし、通信網のノード数、リンク数が増えると、計算量は膨大となり、大規模な通信網の信頼度計算については計算時間の点で困難性が予想される。
【００３７】
そこで、パス法及び分解法の計算速度に関する検討が既になされており、分解法がパス法よりも極めて高速であり、現在のところ現実的な計算法であると言われている（「林，阿部，”ネットワーク信頼性計算アルゴリズムの性能評価”，電子情報通信学会春季全国大会  Ａ−６（１９９１）」参照）。
【００３８】
一方、Ｓ，Ｔ間の故障頻度を求めようとする場合でも、Ｓ，Ｔ間の信頼度と同様な計算手続きが利用できる。
【００３９】
この場合、リンクｉには、正常確率ｐｉ  とともに、故障率λｉ  （１／（修理されてから再び故障するまでの平均時間）が与えられているとする。
【００４０】
並列の縮退については、
2004282275.tif 000005
という変換式で縮退ができることが知られている（「Ｍ．Ｈａｙａｓｈｉ，”Ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｏｐｅｒａｔｏｒ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．６０１−６０９（１９９１）  」参照）。ここで、ａ，ｂは縮退前の２つのリンクの番号、ｃは縮退後のリンク番号である。
【００４１】
一方、直列の縮退については、
ｐｃ  ＝ｐａ  ｐｂ  
λｃ  ＝λａ  ＋λｂ  
という変換式で縮退ができることが知られている（「Ｍ．Ｈａｙａｓｈｉ，”Ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｏｐｅｒａｔｏｒ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．６０１−６０９（１９９１）  」参照）。同様に、ａ，ｂは縮退前の２つのリンクの番号、ｃは縮退後のリンク番号である。
【００４２】
これらの式に従って、例えば、図２０の通信網では、最終的な縮退後の故障率が、
（ｐ１  λ１  ＋ｐ２  λ２  −ｐ１  ｐ２  （λ１  ＋λ２  ））／（ｐ１  ＋ｐ２  −ｐ１  ｐ２  ）＋λ３  
となる。
【００４３】
ここで、リンクが一つからなる通信網のＳ，Ｔ間の故障頻度、信頼度、故障率に関しては、
Ｓ−Ｔ間故障頻度＝（Ｓ−Ｔ間信頼度）×（Ｓ−Ｔ間故障率）
という関係式が成立することが知られている（「Ｍ．Ｈａｙａｓｈｉ，”Ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｏｐｅｒａｔｏｒ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．６０１−６０９（１９９１）  」参照）。
【００４４】
この関係式に従って、図２０の通信網におけるＳ，Ｔ間の故障頻度は、
2004282275.tif 000006
で求められる。
【００４５】
以上説明したように、Ｓ，Ｔ間の故障頻度の計算には縮退法が利用できるのである。
【００４６】
パス法については、パス法での計算手続き中において、
ｐｘ１ｐｘ２…ｐｘｎ  →  ｐｘ１ｐｘ２…ｐｘｎ（λｘ１＋λｘ２＋…＋λｘｎ）
但し、ｘ１〜ｘｎは任意のリンク番号
という変換を行えば、変換後の計算値が、Ｓ，Ｔ間の故障頻度であることが知られている（「Ｗ．Ｇ．Ｓｃｈｎｅｅｗｅｉｓｓ，”Ｃｏｍｐｕｔｉｎｇ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ，ＭＴＢＦ  ＆  ＭＴＴＲ  ｖｉａ  ｍｉｘｅｄ  ｐｒｏｄｕｃｔｓ  ｏｆ  ａｖａｉｌａｂｉｌｉｔｙ  ａｎｄ  ｕｎａｖａｉｌａｂｉｌｉｔｉｅｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｖｏｌ．Ｒ−３０，ｐｐ．３６２−３６３（１９８１）」参照）。
【００４７】
例えば、図２３の通信網のＳ，Ｔ間の故障頻度は、
Ｓ−Ｔ間故障頻度＝
ｐ１  ｐ３  （λ１  ＋λ３  ）＋ｐ２  ｐ５  （λ２  ＋λ５  ）
＋ｐ１  ｐ４  ｐ５  （λ１  ＋λ４  ＋λ５  ）
＋ｐ２  ｐ４  ｐ３  （λ２  ＋λ４  ＋λ３  ）
−ｐ１  ｐ３  ｐ２  ｐ５  （λ１  ＋λ３  ＋λ２  ＋λ５  ）
−ｐ１  ｐ３  ｐ４  ｐ５  （λ１  ＋λ３  ＋λ４  ＋λ５  ）
−ｐ１  ｐ３  ｐ２  ｐ４  （λ１  ＋λ３  ＋λ２  ＋λ４  ）
−ｐ２  ｐ５  ｐ１  ｐ４  ｐ５  （λ２  ＋λ５  ＋λ１  ＋λ４  ＋λ５  ）
−ｐ２  ｐ５  ｐ４  ｐ３  （λ２  ＋λ５  ＋λ４  ＋λ３  ）
−ｐ１  ｐ４  ｐ５  ｐ２  ｐ４  （λ１  ＋λ４  ＋λ５  ＋λ２  ＋λ４  ）
＋ｐ１  ｐ３  ｐ２  ｐ５  ｐ４  （λ１  ＋λ３  ＋λ２  ＋λ５  ＋λ４  ）
＋ｐ１  ｐ２  ｐ５  ｐ４  ｐ３  （λ１  ＋λ２  ＋λ５  ＋λ４  ＋λ３  ）
＋ｐ１  ｐ３  ｐ４  ｐ５  ｐ２  （λ１  ＋λ３  ＋λ４  ＋λ５  ＋λ２  ）
＋ｐ２  ｐ５  ｐ１  ｐ４  ｐ３  （λ２  ＋λ５  ＋λ１  ＋λ４  ＋λ３  ）
−ｐ１  ｐ３  ｐ２  ｐ５  ｐ４  （λ１  ＋λ３  ＋λ２  ＋λ５  ＋λ４  ）
で求められる。
【００４８】
以上に説明したように、Ｓ，Ｔ間の故障頻度については、縮退法とパス法とによって計算することができることが知られている。
【００４９】
なお、ここでは、２リンクからなる構成を１リンクに変換する縮退法について説明したが、本発明者の一人は、下記の特許文献１で、別の種類の縮退法を提案している。
【００５０】
しかしながら、特許文献１で提案した縮退法は、通信網の容量や通信経路の割り当てまで考慮した場合の縮退法である。これに対して、本発明で対象としている通信網は、通信網を現実に構築する際、まず考慮しなければならないところの、物理的に接続されているか否かに関する信頼性評価尺度に着目したものである。従って、特許文献１で提案した縮退法は、計算手法の利用対象が本発明と異なっている。
【００５１】
【特許文献１】
特開平９−２７８３５号公報
【００５２】
【発明が解決しようとする課題】
以上述べたように、従来技術では、Ｓ，Ｔ間の故障頻度については、縮退法とパス法によって計算していた。
【００５３】
ところが、縮退法、パス法を用いての計算は、通信網のノード数、リンク数が大きくなると、計算項が莫大となり、高速計算機を用いても、計算時間の点での困難が生じていた。
【００５４】
これから、Ｓ，Ｔ間の故障頻度の計算についても、Ｓ，Ｔ間の信頼度の計算（上述したように分解法を用いて計算することが可能である）と同様に、高速な分解法を用いる手法が要望されている。
【００５５】
ところが、従来技術では、式（１）に相当する、分解法に必要な、分解後の通信網から分解前の通信網のＳ，Ｔ間の故障頻度の計算に必要なパラメータを算出する手続きが知られていなかったために、分解法を用いて故障頻度を計算することはできなかった。
【００５６】
なお、この件に関連して、本発明者は、「林，  阿部，”ネットワーク信頼性計算アルゴリズムの性能評価”，春季信学全大，Ａ−６（１９９１）」で、分解法を用いた故障頻度数値実験の結果について報告しているが、この学術論文では、実際にどのように分解法を用いたのかについては一切発表していない。
【００５７】
本発明はかかる事情に鑑みてなされたものであって、分解後の通信網から分解前の故障頻度計算に必要なパラメータを算出する手続きを使うことにより、通信網の持つ指定される２つのノード間が通信不能となる故障頻度を高速に計算できるようにする新たな通信網故障頻度計算技術の提供を目的とする。
【００５８】
【課題を解決するための手段】
この目的を達成するために、本発明は、分解法を用いてＳ，Ｔ間の故障頻度の計算のために必要となる、分解後の通信網から分解前の通信網の故障頻度計算に必要なパラメータを算出する手続きとして、下記の式（２）を用いる手段を用意する。
【００５９】
【数１】
2004282275.tif 000007
ただし、
【００６０】
【数２】
2004282275.tif 000008
である。
【００６１】
ここで、Ｒ（Ｇ）は通信網ＧのＳ，Ｔ間の信頼度、Ｆ（Ｇ）は通信網ＧのＳ，Ｔ間の故障頻度を表す。また、ｅは分解を適用する際に着目するリンク、ｐｅ  はリンクｅの正常確率、λｅ  はリンクｅの故障率を表す。
【００６２】
この式（２）の適用イメージを明らかにするために、図２３の通信網に、この式（２）を適用した例について説明する。
【００６３】
今、図２３の通信網で、ｐ１  ＝ｐ２  ＝ｐ３  ＝ｐ４  ＝ｐ５  ＝０．９９、λ１  ＝λ２  ＝λ３  ＝λ４  ＝λ５  ＝０．０２とする。
【００６４】
リンク４を着目リンクとして、縮退法を用いれば、
Ｒ（Ｇ４  ）  ＝０．９９９８，  Ｆ（Ｇ４  ）  ＝０．０００７９
Ｒ（Ｇ４  ＊  ）＝０．９９９６，  Ｆ（Ｇ４  ＊  ）＝０．０１５６
と求められる。
これから、式（２）を用いると、
【００６５】
【数３】
2004282275.tif 000009
となり、図２３の通信網において、Ｓ，Ｔ間の故障頻度は“０．０００８０”と求められることになる。
【００６６】
次に、式（２）の正当性について説明する。
【００６７】
通信網Ｇのリンク番号の集合をＬ＝｛１，２，・・・，Ｎ｝とする。さらに、ｐ１，ｐ２，・・・，ｐＮ  を変数に持つ関数の全体をＸとし、ｐ１，ｐ２，・・・，ｐＮ  ，  λ１，λ２，・・・，λＮ  を変数に持つ関数の全体をＹとする。
【００６８】
ＸからＹへの写像Ｄを、
条件１．任意のｉ∈Ｌに対して、Ｄ（ｐｉ  ）＝ｐｉ  λｉ    ・・・式（３）
条件２．任意のｆ，ｇ∈Ｘに対して、
Ｄ（ｆ＋ｇ）＝Ｄ（ｆ）＋Ｄ（ｇ）        ・・・式（４）
Ｄ（ｆｇ）＝Ｄ（ｆ）ｇ＋ｆＤ（ｇ）      ・・・式（５）
という条件を満足する写像と定義する。
【００６９】
このとき、
性質１．Ｄは存在し、かつ唯一である
性質２．以下の式が成立する
Ｆ（Ｇ）＝Ｄ（Ｒ（Ｇ））
性質３．任意のｆ，ｇ∈Ｘに対して、
Ｄ（ｆ−ｇ）＝Ｄ（ｆ）−Ｄ（ｇ）        ・・・式（６）
Ｄ（１）＝０                            ・・・式（７）
という性質のあることが知られている（「Ｍ．Ｈａｙａｓｈｉ，”Ｓｙｓｔｅｍ  ｆａｉｌｕｒｅ  ｆｒｅｑｕｅｎｃｙ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｏｐｅｒａｔｏｒ”，ＩＥＥＥ  Ｔｒａｎｓ．，Ｒ−４０，ｐｐ．６０１−６０９（１９９１）  」参照）。
【００７０】
ここで、性質２を式（１）に用いると、
2004282275.tif 000010
となる。
【００７１】
この式に、式（３）〜式（７）を適用して、
2004282275.tif 000011
となる。
【００７２】
式（１）と上式を変形した上で並び替えると、
2004282275.tif 000012
のようになる。
従って、
【００７３】
【数４】
2004282275.tif 000013
という関係式が得られ、これを変形すると、
【００７４】
【数５】
2004282275.tif 000014
が導かれる。この式は式（２）に一致する。
【００７５】
このようにして、本発明は、分解法を使った故障頻度計算を可能にするために、計算したい通信網Ｇの持つあるリンクｅを短絡した通信網の信頼度Ｒ（Ｇｅ  ）及び故障頻度Ｆ（Ｇｅ  ）と、計算したい通信網Ｇからそのリンクｅを開放した通信網の信頼度Ｒ（Ｇｅ  ＊  ）及び故障頻度Ｆ（Ｇｅ  ＊  ）とから、
2004282275.tif 000015
という、式（２）の計算式に従って、計算したい通信網の信頼度Ｒ（Ｇ）及び故障頻度Ｆ（Ｇ）を計算するという構成を基本構成とするものである。
【００７６】
本発明は、この基本構成に従い、
▲１▼処理対象の通信網を計算対象の通信網の起点として、計算対象の通信網を縮退して、１リンクへ縮退できる場合には、その１リンクの信頼度及び故障頻度から計算対象の通信網の信頼度及び故障頻度を計算し、１リンクへ縮退できない場合には、計算対象の通信網の持つあるリンクを短絡した通信網とそのリンクを開放した通信網とを新たな計算対象の通信網として、この処理を繰り返すことで、計算対象の通信網の信頼度及び故障頻度を計算する第１の処理過程と、
▲２▼第１の処理過程で求めた短絡した通信網の信頼度及び故障頻度と、第１の処理過程で求めた開放した通信網の信頼度及び故障頻度とをパラメータ値とする、上述の式（２）の計算式に従って、その短絡及び開放前の通信網の信頼度及び故障頻度を計算して、処理対象の通信網の信頼度及び故障頻度が計算できるまで、この処理を繰り返すことで、処理対象の通信網の信頼度及び故障頻度を計算する第２の処理過程とを備えることで、
処理対象となる通信網の持つ指定される２つのノード間が通信不能となる故障頻度を計算する。
【００７７】
以上の各処理過程が動作することで実現される本発明の通信網故障頻度計算方法はコンピュータプログラムで実現できるものであり、このコンピュータプログラムは、半導体メモリなどのような適当な記録媒体に記録して提供されたり、ネットワークを介して提供され、本発明を実施する際にインストールされてＣＰＵなどの制御手段上で動作することにより本発明を実現することになる。
【００７８】
このようにして、本発明によれば、通信網において、あるノードＳとあるノードＴとの間が通信不能となる故障が発生する頻度の平均値（故障頻度）を分解法を使って計算できるようになることから、通信網の故障頻度を高速に計算できるようになる。
【００７９】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
【００８０】
図１に、本発明を具備する通信網故障頻度計算装置１の装置構成の一例を図示する。
【００８１】
この図に示すように、本発明の通信網故障頻度計算装置１は、通信網の形状を表すデータと故障頻度計算に必要なデータとを格納する記憶部１０と、そのデータに縮退の処理を行う縮退部１１と、そのデータに分解の処理を行う分解部１２と、計算全体を統括する制御部１３とを備えるとともに、入力装置として、キーホード１４を備え、出力装置として、表示制御部１５／表示メモリ１６／ＣＲＴ１７を備える。
【００８２】
先ず最初に、記憶部１０に記憶されるデータの構造について説明し、続いて、縮退部１１の処理機能、分解部１２の処理機能、制御部１３の処理機能について説明する。
【００８３】
（１）記憶部１０に記憶されるデータの構造
記憶部１０は、通信網の形状を表すデータと故障頻度計算に必要なデータとを記憶する。
【００８４】
図２に、記憶部１０に記憶されるデータの構造を示す。なお、図２中に示す数値は、例を示すための仮想値である。
【００８５】
図２において、各行が通信網の持つリンクに対応し、各行の成分は、そのリンクのリンク番号、そのリンクが接続するノード番号、そのリンクの正常確率、そのリンクの故障率に対応する。ノード番号を示す二つの自然数Ｓ，Ｔも入力される。
【００８６】
本発明の通信網故障頻度計算装置１は、ノード番号Ｓのノードとノード番号Ｔのノードとの間が非連結となる故障頻度を求めることになる。
【００８７】
以下、説明のために、リンク番号ｘのリンクに接続しているノード番号を、図２のデータ構造において左からｎ１（ｘ），ｎ２（ｘ）と表し、また、リンク番号ｘのリンクの正常確率をｐｘ  、リンク番号ｘのリンクの故障率をλｘ  と表すことにする。
【００８８】
（２）縮退部１１の処理機能
縮退部１１は、記憶部１０に記憶されている通信網データから、直列と並列の縮退が可能な部分を見つけ出して、実際に適用する処理を行う。この処理を行うために、縮退部１１は、ノード次数カウンタ、直列縮退変換部、並列縮退変換部を備える。
【００８９】
（２−１）ノード次数カウンタの処理機能
ノード次数カウンタは、図３の処理フローを実行することで、通信網データから、各ノードに接続しているリンク数（次数）を数え上げる処理を行って、それを記憶する。
【００９０】
各ノードの次数のカウント結果については、ｄ（１）〜ｄ（Ｎ）に格納されることになる。
【００９１】
（２−２）直列縮退変換部の処理機能
直列縮退変換部は、図４の処理フローを実行することで、直列構成の二つのリンクを探索して、直列の縮退を実行する。
【００９２】
（２−３）並列縮退変換部の処理機能
並列縮退変換部は、図５の処理フローを実行することで、並列構成の二つのリンクを探索して、並列の縮退を実行する。
【００９３】
縮退部１１は、これらのノード次数カウンタ／直列縮退変換部／並列縮退変換部を使い、図６の処理フローに示すように、先ず最初に、ステップ１０で、入力された通信網データの全リンク数Ｍを求め、続くステップ１１で、ノード次数カウンタを使って各ノードの次数をカウントする。
【００９４】
続いて、ステップ１２で、ノードの次数を参照しつつ、直列縮退変換部を使って、ノード次数カウンタによりカウントされたノードの次数を参照しつつ直列縮退変換を実行し、続くステップ１３で、並列縮退変換部を使って、ノード次数カウンタによりカウントされたノードの次数を参照しつつ並列縮退変換を実行する。
【００９５】
続いて、ステップ１４で、縮退変換を施すことで書き替えた通信網データの全リンク数Ｍ０  を求め、続くステップ１５で、Ｍ０  がＭよりも小さいのか否かを判断して、Ｍ０  がＭよりも小さいことを判断するときには、ステップ１６に進んで、Ｍ０  を新たなＭと設定して、ステップ１１に戻り、Ｍ０  がＭよりも小さくならないことを判断するときには、処理を終了する。
【００９６】
このようにして、縮退部１１は、入力された通信網データを可能な限り縮退するように処理するのである。
【００９７】
（３）分解部１２の処理機能
分解部１２は、通信網データにおいて特定のリンクに着目し、その着目リンクを短絡除去した通信網に対応するデータと、その着目リンクを開放除去した通信網に対応するデータとを生成する処理を行う。この処理を行うために、分解部１２は、短絡除去部と開放除去部とを備える。
【００９８】
（３−１）短絡除去部の処理機能
短絡除去部は、図７の処理フローを実行することで、通信網データから、着目リンク（リンク番号ｅ）を短絡除去した通信網Ｇｅ  のデータを生成する。
【００９９】
ここで、上述したように、ノードｘの両端のノードはｎ１（ｘ），ｎ２（ｘ）で表している。
【０１００】
（３−２）開放除去部の処理機能
開放除去部は、図８の処理フローを実行することで、通信網データから、着目リンク（リンク番号ｅ）を開放除去した通信網Ｇｅ  ＊  のデータを生成する。
【０１０１】
（４）制御部１３の処理機能
制御部１３は、縮退部１１及び分解部１２を制御して、Ｓ，Ｔ間の故障頻度を計算する処理を行う。この計算処理を行うために、制御部１３は、再帰的な手続きを用いる。
通信網Ｇを表すデータから、
【０１０２】
【数６】
2004282275.tif 000016
を算出する関数ｆ（Ｇ）を考える。
【０１０３】
この関数ｆ（Ｇ）は、以下の処理を実行する。
【０１０４】
すなわち、先ず最初に、通信網Ｇを表すデータに、縮退部１１を用いて、直並列の縮退をこれ以上縮退できなくなるまで（縮退を適用してもリンク数が減らなくなるまで）繰り返す。
【０１０５】
直並列の縮退をこれ以上縮退できなくなるまで繰り返した結果、縮退した通信網データが１リンクとなった場合には、そのリンクの信頼度Ｒ０  と、そのリンクの故障率Ｆ０  とから、関数ｆ（Ｇ）の値として、
【０１０６】
【数７】
2004282275.tif 000017
を算出する。
【０１０７】
一方、直並列の縮退をこれ以上縮退できなくなるまで繰り返した結果、縮退した通信網データが１リンクとならない場合には、任意のリンクｅを選択して、分解部１２を用いて、Ｇｅ  とＧｅ  ＊  を表すデータを生成し、自分自身（関数ｆ）をコールすることでｆ（Ｇｅ  ）とｆ（Ｇｅ  ＊  ）とを算出する。
【０１０８】
そして、式（２）と等価となる
ｆ（Ｇ）＝Ｐｅ  ・ｆ（Ｇｅ  ）＋（Ｅ−Ｐｅ  ）・ｆ（Ｇｅ  ＊  ）
を算出する。
【０１０９】
関数ｆ（Ｇ）は、この処理を再帰的に繰り返すことで、通信網ＧにおけるＳ，Ｔ間の故障頻度を計算する。
【０１１０】
次に、図９（ａ）に示す通信網データを具体例にして、本発明による故障頻度計算処理について具体的に説明する。
【０１１１】
ここで、図９（ａ）に示す通信網データを構成する各リンクの正常確率及び故障率については、図９（ｂ）に示すものを想定するとともに、ノード１とノード４との間の故障頻度について計算することを想定する。
【０１１２】
制御部１３において、Ｇに関数ｆが適用される。
【０１１３】
関数ｆの最初の手続きとして、直並列の縮退が適用され、図９（ａ）のデータについては並列の縮退が適用されることで、図１０に示すＧ’  に変換されることになる。
【０１１４】
これ以上、縮退を適用してもリンク数が減らないので、Ｇ’  を分解する操作が適用されて、Ｇｅ  ’  とＧｅ  ＊  ’  とが生成される。例えば、着目するリンクとしてリンク４が選択される場合には、図１１（ａ）に示すようなＧｅ  ’  と、図１１（ｂ）に示すようなＧｅ  ＊  ’  とが生成されることになる。
【０１１５】
関数ｆの次の手続きとして、関数ｆ（Ｇｅ  ’  ）と関数ｆ（Ｇｅ  ＊  ’  ）とが計算される。
【０１１６】
先ず、ｆ（Ｇｅ  ’  ）の手続きとして、縮退が適用され、図１１（ａ）に示すＧｅ  ’  は、図１２に示すように１リンクまで縮退される。このようにして１リンクまで縮退できたので、ｆ（Ｇｅ  ’  ）は、
【０１１７】
【数８】
2004282275.tif 000018
を値として返す。
【０１１８】
同様に、ｆ（Ｇｅ  ＊  ’  ）の手続きとして、縮退が適用され、図１１（ｂ）に示すＧｅ  ＊  ’  は、図１３に示すように１リンクまで縮退される。このようにして１リンクまで縮退できたので、ｆ（Ｇｅ  ＊  ’  ）  は、
【０１１９】
【数９】
2004282275.tif 000019
を値として返す。
【０１２０】
このようにして、ｆ（Ｇｅ  ’  ）とｆ（Ｇｅ  ＊  ’  ）とが求められると、式（２）に従って、
【０１２１】
【数１０】
2004282275.tif 000020
というようにｆ（Ｇ）が求められるので、本発明の通信網故障頻度計算装置１は、Ｇの故障頻度Ｆ（Ｇ）として“０．０３６２”という値を出力する。
【０１２２】
このようにして、本発明の通信網故障頻度計算装置１によれば、分解法を使って、通信網において、あるノードＳとあるノードＴとの間が通信不能となる故障発生の故障頻度を計算できるようになる。
【０１２３】
次に、図１４ないし図１７に従って、本発明の通信網故障頻度計算装置１の実行する故障頻度計算処理のための全体的な処理について、さらに詳細に説明する。
【０１２４】
この図１４に示す構成では、本発明の通信網故障頻度計算装置１は、指定通信網信頼度・故障頻度算出ルーチン１００と、分解前通信網信頼度・故障頻度算出ルーチン２００と、メインプログラム３００というプログラム構成に従って、分解法を使って通信網の故障頻度を計算するという構成を採っている。
【０１２５】
この指定通信網信頼度・故障頻度算出ルーチン１００は、メインプログラム３００から、通信網を指定してコールされると、図１５の処理フローに示すように、その指定される通信網を受け取って、これ以上縮退できないというまで縮退を行う。
【０１２６】
そして、その縮退の結果、リンク数が１つとなるまで縮退できたのか否かを判断して、リンク数が１つとなるまで縮退できた場合には、縮退した１リンクの信頼度・故障率から、指定される通信網の信頼度・故障頻度を算出して、それをメインプログラムに返却し、一方、リンク数が１つとなるまで縮退できない場合には、指定される通信網の任意のリンクを選択して、短絡除去と開放除去により２つの分解後通信網を生成して、それをメインプログラムに返却するという処理を実行する。
【０１２７】
また、分解前通信網信頼度・故障頻度算出ルーチン２００は、メインプログラム３００から、短絡除去と開放除去により生成された２つの分解後通信網の信頼度・故障頻度を指定してコールされると、図１６の処理フローに示すように、その２つの分解後通信網の信頼度・故障頻度を受け取り、その分解後通信網の分解に用いられた着目リンクの正常確率及び故障率を取得する。
【０１２８】
そして、上述した式（２）を使って、２つの分解後通信網の信頼度・故障頻度と、その分解後通信網の分解に用いられた着目リンクの正常確率及び故障率とから、分解前通信網の信頼度・故障頻度を算出して、それをメインプログラムに返却するという処理を実行する。
【０１２９】
メインプログラム３００は、この指定通信網信頼度・故障頻度算出ルーチン１００の処理と、分解前通信網信頼度・故障頻度算出ルーチン２００の処理とを受けて、図１７の処理フローに示すように、処理対象の通信網を入力すると、処理対象の通信網を指定して、指定通信網信頼度・故障頻度算出ルーチン１００をコールすることで、指定通信網信頼度・故障頻度算出ルーチン１００から、指定した通信網の信頼度・故障頻度を受け取るか、指定した通信網から分解される分解後通信網を受け取り、分解後通信網を受け取る場合には、分解後通信網を指定して、指定通信網信頼度・故障頻度算出ルーチン１００を再度コールしていく。
【０１３０】
そして、指定通信網信頼度・故障頻度算出ルーチン１００から受け取った全ての分解後通信網についてコールしたことを判断するときには、下位側の分解後通信網からの順番に従って、指定通信網信頼度・故障頻度算出ルーチン１００から受け取った分解後通信網の信頼度・故障頻度を指定して、分解前通信網信頼度・故障頻度算出ルーチン２００をコールすることで、その分解後通信網の分解前の通信網の信頼度・故障頻度を受け取り、処理対象の通信網に戻るまで、そのコールを繰り返していくのである。
【０１３１】
最後に、本発明の有効性を検証するために行った実験の結果について説明する。
【０１３２】
この実験は、図１８（ａ）に示す６完全メッシュの通信網データと、図１８（ｂ）に示す７完全メッシュの通信網データとについて、本発明を用いて計算した場合の計算時間と、パス法を用いる計算方法の中で効率的な方法として知られている「Ｊ．Ａ．Ａｂｒａｈａｍ，”Ａｎ  ｉｍｐｒｏｖｅｄ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｎｅｔｗｏｒｋ  ｒｅｌｉａｂｉｌｉｔｙ”，ＩＥＥＥ，Ｔｒａｎｓ．，Ｒ−２８，ｐｐ．５８−６１（１９７９）  」を用いて計算した場合の計算時間とを比較することで行った。
【０１３３】
図１９に、この実験結果を図示する。この実験結果から本発明の有効性が検証できた。
【０１３４】
【発明の効果】
以上説明したように、本発明によれば、通信網において、あるノードＳとあるノードＴとの間が通信不能となる故障が発生する頻度の平均値（故障頻度）を分解法を使って計算できるようになることから、通信網の故障頻度を高速に計算できるようになる。
【図面の簡単な説明】
【図１】本発明の通信網故障頻度計算装置の装置構成の一例を示す図である。
【図２】記憶部に格納されるデータの構造を示す図である。
【図３】ノード次数カウンタの実行する処理フローである。
【図４】直列縮退変換部の実行する処理フローである。
【図５】並列縮退変換部の実行する処理フローである。
【図６】縮退部の実行する処理フローである。
【図７】短絡除去部の実行する処理フローである。
【図８】開放除去部の実行する処理フローである。
【図９】通信網データの一例を示す図である。
【図１０】縮退された通信網データの説明図である。
【図１１】分解された通信網データの説明図である。
【図１２】通信網データの縮退の説明図である。
【図１３】通信網データの縮退の説明図である。
【図１４】本発明の通信網故障頻度計算装置の備えるプログラム構成の他の一例を示す図である。
【図１５】指定通信網信頼度・故障頻度算出ルーチンの実行する処理フローである。
【図１６】分解前通信網信頼度・故障頻度算出ルーチンの実行する処理フローである。
【図１７】メインプログラムの実行する処理フローである。
【図１８】本発明の有効性を検証するために行った実験で用いた通信網データの説明図である。
【図１９】本発明の有効性を検証するために行った実験結果の説明図である。
【図２０】通信網の一例を示す図である。
【図２１】通信網の並列縮退の説明図である。
【図２２】通信網の直列縮退の説明図である。
【図２３】通信網の一例を示す図である。
【図２４】通信網の分解の説明図である。
【図２５】通信網の分解の説明図である。
【符号の説明】
１    通信網故障頻度計算装置
１０  記憶部
１１  縮退部
１２  分解部
１３  制御部
１４  キーホード
１５  表示制御部
１６  表示メモリ
１７  ＣＲＴ
【図１】
2004282275.tif 000023
【図２】
2004282275.tif 000024
【図３】
2004282275.tif 000025
【図４】
2004282275.tif 000026
【図５】
2004282275.tif 000027
【図６】
2004282275.tif 000028
【図７】
2004282275.tif 000029
【図８】
2004282275.tif 000030
【図９】
2004282275.tif 000031
【図１０】
2004282275.tif 000032
【図１１】
2004282275.tif 000033
【図１２】
2004282275.tif 000034
【図１３】
2004282275.tif 000035
【図１４】
2004282275.tif 000036
【図１５】
2004282275.tif 000037
【図１６】
2004282275.tif 000038
【図１７】
2004282275.tif 000039
【図１８】
2004282275.tif 000040
【図１９】
2004282275.tif 000041
【図２０】
2004282275.tif 000042
【図２１】
2004282275.tif 000043
【図２２】
2004282275.tif 000044
【図２３】
2004282275.tif 000045
【図２４】
2004282275.tif 000046
【図２５】
2004282275.tif 000047