(57)【要約】【課題】故障が生じ得て、その故障が必ずしも常に顕在化しないシステムに対して、外部からのプローブにて、当該故障の構成要素を推定する。【解決手段】プローブによる検査は、見かけ上、少なくとも１つの構成要素に故障がある場合に、故障であるとの検査結果になる検査であり、システムの各構成要素は、0が正常、0より大きい場合が故障を示す状態tを有し、状態tのときに、プローブが当該構成要素を正常と判定する確率をp(t→0)とし、第i種類のプローブについての複数の検査結果から、当該プローブの検査について正常と判定された比率riを求め、第i種類のプローブが検査した第j要素の状態をk(i,j)とおいた場合において、プローブが第j要素を正常であると判定する確率p(k(i,j)→0)に基づき表現される第i種類のプローブによる正常判定率が前記比率riと等しいか、近似的に等しくなるようにk(i,j)を求めることで、前記システムにおける故障要素を推定する。【選択図】図１
2014170332.tif 000002
【特許請求の範囲】
【請求項１】
複数の構成要素を備えるシステムにおける故障要素の推定を行う故障要素推定装置が実行する故障要素推定方法であって、
前記システムは、外部から送信端に入力され、受信端から出力されるプローブにより構成要素の正常性を検査可能に構成されており、当該プローブによる検査は、見かけ上、検査される構成要素のうち少なくとも１つの構成要素に故障がある場合に、故障であるとの検査結果になる検査であり、
前記システムの各構成要素は、0が正常、0より大きい場合が故障を示す状態tを有し、状態tのときに、プローブが当該構成要素を正常と判定する確率をp(t→0)とし、
前記故障要素推定装置は、
第i種類のプローブについての複数の検査結果から、当該プローブの検査について正常と判定された比率riを求め、
第i種類のプローブが検査した第j要素の状態をk(i,j)とおいた場合において、プローブが第j要素を正常であると判定する確率p(k(i,j)→0)に基づき表現される第i種類のプローブによる正常判定率が前記比率riと等しいか、近似的に等しくなるようにk(i,j)を求めることで、前記システムにおける故障要素を推定する
ことを特徴とする故障要素推定方法。
【請求項２】
log(ri)を縦に並べた列ベクトルをqとし、第i行を第i種類のプローブが検査できる要素を表す行ベクトルとした行例をAとし、log(p(0→0)),…,log(p(nt→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをeとし、
a(i)が第i構成要素の試験をしているかいないかを示す0又は１であり、nsが構成要素の数であり、k(a)=a(1)+ …. + a(ns)である場合に、（log(ri)−k(a)log(p(0→0))を縦に並べた列ベクトルをq'とし、log(p(1→0)/p(0→0)),…,log(p(nt→0)/p(0→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをeとした場合において、
前記故障要素推定装置は、
q=ATu+e
あるいは
q'=ATu+e'
を成立させる、または、近似的に成立させる行列Tあるいは行列Tを得ることで、故障要素を推定することを特徴とする請求項１に記載の故障要素推定方法。
【請求項３】
前記故障要素推定装置は、
|q−(ATu+e)|2  あるいは|q'−(ATu+e')|2  を最小化する行列Tあるいは行列Tを得ることで、故障要素を推定することを特徴とする請求項２に記載の故障要素推定方法。
【請求項４】
複数の構成要素を備えるシステムにおける故障要素の推定を行う故障要素推定装置であって、
前記システムは、外部から送信端に入力され、受信端から出力されるプローブにより構成要素の正常性を検査可能に構成されており、当該プローブによる検査は、見かけ上、検査される構成要素のうち少なくとも１つの構成要素に故障がある場合に、故障であるとの検査結果になる検査であり、
前記システムの各構成要素は、0が正常、0より大きい場合が故障を示す状態tを有し、状態tのときに、プローブが当該構成要素を正常と判定する確率をp(t→0)とし、
前記故障要素推定装置は、
第i種類のプローブについての複数の検査結果から、当該プローブの検査について正常と判定された比率riを求める手段と、
第i種類のプローブが検査した第j要素の状態をk(i,j)とおいた場合において、プローブが第j要素を正常であると判定する確率p(k(i,j)→0)に基づき表現される第i種類のプローブによる正常判定率が前記比率riと等しいか、近似的に等しくなるようにk(i,j)を求めることで、前記システムにおける故障要素を推定する推定手段と
を備えることを特徴とする故障要素推定装置。
【請求項５】
log(ri)を縦に並べた列ベクトルをqとし、第i行を第i種類のプローブが検査できる要素を表す行ベクトルとした行例をAとし、log(p(0→0)),…,log(p(nt→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをeとし、
a(i)が第i構成要素の試験をしているかいないかを示す0又は１であり、nsが構成要素の数であり、k(a)=a(1)+ …. + a(ns)である場合に、（log(ri)−k(a)log(p(0→0))を縦に並べた列ベクトルをq'とし、log(p(1→0)/p(0→0)),…,log(p(nt→0)/p(0→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをe'とした場合において、
前記推定手段は、
q=ATu+e
あるいは
q'=ATu+e'
を成立させる、または、近似的に成立させる行列Tあるいは行列Tを得ることで、故障要素を推定することを特徴とする請求項４に記載の故障要素推定装置。
【請求項６】
前記故推定手段は、
|q−(ATu+e)|2  あるいは|q'−(ATu+e')|2  を最小化する行列Tあるいは行列Tを得ることで、故障要素を推定することを特徴とする請求項５に記載の故障要素推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークや電子回路等において、外部から、テストパタンを送出し、その結果を持って、当該システムの障害個所を推定する技術分野に関わるものである。
【背景技術】
【０００２】
ネットワークや電子回路等、複数の構成要素からなるシステムで、各構成要素が自律的に故障を通知し得ない場合、外部からのプローブにより故障を特定することが必要となる。あるいは、外部からのプローブにより、故障要素の特定が可能であれば、各構成要素には、自律的な故障通知機能は必要ではなくなる。
【０００３】
例えば、インターネットや光ネットワークでは、該当するレイヤの送信端から試験パケットを送出し、受信端にて受信し（あるいは、受信できないことを判定し）、構成要素であるリンクのいずれが故障であるか、あるいは、非常に品質が悪くなっているか、特定しようという研究がある（非特許文献１〜３）。
【０００４】
さらには、電子回路に対して、テストパタンを入力し、電子回路の要素の故障を効率的に見出す研究もある（非特許文献４）。
【０００５】
これらに共通の前提は、（１）プローブ（試験パケットあるいはテストパタン）が検査した構成要素に１つでも故障がある場合は、プローブの検査結果は、「故障」であり、それ以外の場合は、「正常」と判定されること、（２）故障は、常に、故障であり、検査時に、たまたま正常に見えることは、想定されていないこと、である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Nick Duffield, Network Tomography of Binary Network Performance Characteristics, IEEE Trans. Information Theory, 52, 12, pp. 5373-5388, 2006.
【非特許文献２】Hongyi Zeng,Peyman Kazemian, George Varghese, and Nick McKeown, Automatic Test Packet Generation, CoNEXT 2012, 2012.
【非特許文献３】Janos Tapolcai, Pin-HanHo, Lajos Ronyai, and Bin Wu, Network-Wide Local Unambiguous Failure Localization (NWL-UFL) via Monitoring Trails, IEEE/ACM Trans. Networking, 20, 6, pp. 1762- 1773, 2012.
【非特許文献４】Sreejit Chakravarty and Harry B. Hunt III, On Computing Signal Probability and Detection Probability of Stuck-at Faults, IEEE Trans. COMPUTERS, 39, 11, pp. 1369--1377, 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の従来技術には、以下のような課題がある。
【０００８】
従来技術に記載のシステムとプローブに対して、実際のシステムでは、故障が常に顕在化しているわけではないため、故障の見逃しや、故障構成要素の特定誤りが生じている。また、顕在化のしやすさが一様ではないことも、困難さに拍車をかけている。
【０００９】
本発明は上記の点に鑑みてなされたものであり、常に顕在化するとは限らず、顕在化のしやすさも一様ではない故障を生じ得る構成要素からなるシステムに対し、外部からのプローブにより、故障要素を推定する技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明は、複数の構成要素を備えるシステムにおける故障要素の推定を行う故障要素推定装置が実行する故障要素推定方法であって、
前記システムは、外部から送信端に入力され、受信端から出力されるプローブにより構成要素の正常性を検査可能に構成されており、当該プローブによる検査は、見かけ上、検査される構成要素のうち少なくとも１つの構成要素に故障がある場合に、故障であるとの検査結果になる検査であり、
前記システムの各構成要素は、0が正常、0より大きい場合が故障を示す状態tを有し、状態tのときに、プローブが当該構成要素を正常と判定する確率をp(t→0)とし、
前記故障要素推定装置は、
第i種類のプローブについての複数の検査結果から、当該プローブの検査について正常と判定された比率riを求め、
第i種類のプローブが検査した第j要素の状態をk(i,j)とおいた場合において、プローブが第j要素を正常であると判定する確率p(k(i,j)→0)に基づき表現される第i種類のプローブによる正常判定率が前記比率riと等しいか、近似的に等しくなるようにk(i,j)を求めることで、前記システムにおける故障要素を推定することを特徴とする故障要素推定方法として構成される。
【００１１】
log(ri)を縦に並べた列ベクトルをqとし、第i行を第i種類のプローブが検査できる要素を表す行ベクトルとした行例をAとし、log(p(0→0)),…,log(p(nt→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをeとし、
a(i)が第i構成要素の試験をしているかいないかを示す0又は１であり、nsが構成要素の数であり、k(a)=a(1)+ …. + a(ns)である場合に、（log(ri)−k(a)log(p(0→0))を縦に並べた列ベクトルをq'とし、log(p(1→0)/p(0→0)),…,log(p(nt→0)/p(0→0))（ntは故障の状態の数）を縦に並べた列べクトルをuとし、誤差項を縦に並べた列べクトルをeとした場合において、
前記故障要素推定装置は、
q=ATu+e
あるいは
q'=ATu+e'
を成立させる、または、近似的に成立させる行列Tあるいは行列Tを得ることで、故障要素を推定するようにしてもよい。
【００１２】
また、前記故障要素推定装置は、|q−(ATu+e)|2  あるいは|q'−(ATu+e')|2  を最小化する行列Tあるいは行列Tを得ることで、故障要素を推定するようにしてもよい。
【００１３】
また、本発明は、上述した故障要素推定方法を実施する故障要素推定装置として構成してもよい。
【発明の効果】
【００１４】
本発明によれば、故障が生じ得て、その故障が必ずしも常に顕在化しないシステムに対して、外部からのプローブにて、当該故障の構成要素を推定することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態において故障要素推定を行う際の全体構成例を示す図である。
【図２】故障推定器105の機能構成を示す図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１７】
（システム構成）
図１は、本発明の実施の形態において故障要素推定を行う際の全体構成の例を示す図である。図１に示すように、当該構成には、システム101、プローブ送信装置102、プローブ受信装置103、プローブ送受信装置104、故障推定器105が含まれる。
【００１８】
図１に示すとおり、本実施の形態のシステム101は、ns個の要素からなる。システム101には、プローブを送受することができる送受信端が存在する。送受信端は、プローブの送受信装置102-104が接続され、所定のプローブの送信や受信（あるいは、タイムアウト設定およびタイムアウトまでに受信されないこと）や、受信プローブ情報の読み取りなどを行う。図１には、例として、プローブ送信装置102がプローブ送信端aに接続され、プローブ受信装置103がプローブ受信端bに接続され、プローブ送信装置102からプローブ送信端aを経由してシステム101にプローブが入力され、プローブ受信端bからプローブが出力されて、プローブ受信装置103により受信されることが示されている。
【００１９】
プローブにより、検査できる構成要素が異なる。例えば、対象システムがネットワークであり、構成要素がリンクである場合、送信端xから受信端yまで、あるいは、送信端xから、yで折り返し、xで受信することで試験できるネットワークの構成要素は、試験パケット経路上のリンクであり、経路上にないリンクは、検査できない。
【００２０】
図１に示すとおり、プローブの送受信装置102-104は、故障推定器105に接続されている。図２に、故障推定器105（故障要素推定装置と称してもよい）の機能構成例を示す。図２に示すように、故障推定器105は、試験部201、故障推定部202、記憶部203（記憶装置）を有する。
【００２１】
試験部201は、プローブの試験条件設定や試験（検査）を行い、故障推定部202は後述する故障要素推定を行う。故障推定器105の記憶部203には、システム101の構成（構成要素数や構成要素間の接続情報など）や、推定の前提となるパラメータ値（例えば、下記p(j→k)の値）などを保持する。そして、試験部201が、プローブの送受信ルートが最低限１回は各構成要素を通ることなどを判定し、プローブの試験条件設定を支援する。また、試験部201は、プローブ送信装置にプローブへの設定指示（送信先等）と送信指示（送信回数と間隔を含む）を行う。同指示を受信したプローブ送信装置は、指示に従い、プローブを送信する。送信されたプローブは、プローブ受信装置にて受信されるあるいは、タイムアウト設定およびタイムアウトまでに受信されない。受信されなかったことを含めた受信情報が、プローブ受信装置から、故障推定器105の試験部201に通知され、検査結果として記憶部203に格納される。各受信装置からの同通知をもとに、故障推定器105（故障推定部202）は、後述する方法で故障要素の推定を行う。
【００２２】
故障推定器105は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、故障推定器105の各部が有する機能は、故障推定器105を構成するコンピュータに内蔵されるＣＰＵやメモリ、ハードディスクなどのハードウェア資源を用いて、各部で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００２３】
（故障要素の推定の詳細）
以下、故障推定器105が実行する故障要素の推定方法を詳細に説明する。
【００２４】
各要素の正常/故障を表す変数をtiとする（i=1,..,ns)。tiは0からntの間の整数値を取るものとし、ti=0は正常を、ti>0は故障を表す。1からntの間の整数は、故障の顕在化しやすさのレベル（故障の状態の種類）を表す。第(i,j)要素がti=jであるとき1、そうでないとき0とするns×nt行列をTとする(j>0)。さらに、第(i,j)要素がti=j-1であるとき1、そうでないとき0とするns×(nt＋1)行列をTとする。Tは、各行に１か所だけ１があり、それ以外は0である行列、Tは、そこから１列目を取り除いた行列であり各行には高々１か所の１があり、それ以外は0である行列である。なお、TあるいはTは、推定の対象である。
【００２５】
あるプローブにより検査可能な要素を表す行ベクトルを、ベクトルa=(a(1),…,a(ns))とする。ここで、a(i)=0/1は、第i構成要素の検査をしていない/しているに対応する。例えば、送信端xから受信端yまでの試験パケットが第1リンクだけ通る場合は、a=(1,0,….,0)である。できるだけ多くの構成要素をカバーするため、通常、複数種のプローブを使用する。ネットワーク例で言えば、送受信端x,yが異なる試験パケットを使用する。それらのプローブを表す行列をAとする。Aの第i行は、第i種類のプローブが検査できる要素を表す行ベクトルである。Aのデータは、例えば、故障推定器105の試験部201により、予め準備され、記憶部203に格納されている。あるいは、外部で予め準備し、記憶部203に格納しておくこととしてもよい。
【００２６】
さらに、故障が常に発現しているとは限らないため、故障があっても、試験時には、正常と見えることがある。p(j→k)を、ti=jだが、その見かけ上の状態si=kとなる確率とする。k=0は正常、k>0は故障である。p(j→k)は、予め記憶部203に格納されるパラメータ値である。
【００２７】
プローブによる検査結果は、試験した構成要素のうち、見かけ上、１つでも、故障の要素があると「故障」、それ以外の場合は、「正常」となるとする。例えば、ネットワークの場合、途中のリンクが１つでも途絶していると、時間内に、受信端に到達しないことにより、「故障」と判定する。すなわち、あるプローブの試験において、(a(1)s1+ …. + a(ns)sns) が0なら正常、0より大きければ故障と判定する。各種のプローブの試験結果（「正常」か「故障」）は、試験部201により記憶部203に格納される。また、試験部203は、プローブの種類i毎に多数の試験結果を得て記憶部203に格納し、故障推定部202は、記憶部203に格納された試験結果に基づき、プローブの種類i毎に正常判定率ri（全体の試験回数のうちの「正常」の回数の比率）を求める。
【００２８】
ここで、要素の状態(t1,…..,tns)が(k1,…..,kns)のとき、プローブによる試験結果が正常と判定される確率は、独立性の仮定のもとで、p(ki1→0)・p(ki2→0)・・・p(kij→0)である。なお、a(i1),…,a(ij)は１、その他のa(i)は0である。
【００２９】
よって、十分に多く第i種プローブを使用することにより、正常判定率riは、
log(ri)=log(p(ki1→0))+・・・・+log(p(kij→0))+ei
となる。ここでeiは平均値からの乖離を表す誤差項である。
【００３０】
log(ri)をqiとし、第1からna種までのプローブがあることから、上記式を行列表現すれば、
q=ATu+e
となる。ここで、qは、qiを縦に並べた列べクトル、uは、log(p(0→0)),…,log(p(nt→0))を縦にならべた列べクトル、eはeiを縦に並べた列べクトルである。
【００３１】
別の表現として
log(ri)=k(a)log(p(0→0))+log(p(ki1→0)/p(0→0))+・・・・+log(p(kij→0)/p(0→0))+ei'
もある。ここでei'は誤差項、k(a)=a(1)+ …. + a(ns)である。
【００３２】
log(ri)−k(a)log(p(0→0))をqi'とし、第1からna種までのプローブがあることから、上記式を行列表現すれば、
q'=ATu+e'
となる。ここで、q'は、qi'を縦に並べた列べクトル、uは、log(p(1→0)/p(0→0)),…,log(p(nt→0)/p(0→0))を縦にならべた列べクトル、e'はei'を縦に並べた列べクトルである。
【００３３】
故障推定器105の故障推定部202は、上記のいずれかを用いて、TまたはTを推定する。
【００３４】
例えば、|q−(ATu+e)|2  あるいは|q'−(ATu+e')|2  の最小化を実現するTやTを求めればよい。（Tの場合は、第i行に1が１つもなければ、ti=0と推定される。）これらの最小化は、既存のパラメータ推定法で推定できる。
【００３５】
すなわち、第i種類のプローブが検査した第j要素の状態をk(i,j)とおいた場合において、プローブが第j要素を正常であると判定する確率p(k(i,j)→0)に基づき表現される第i種類のプローブによる正常判定率が、検査結果から得られた比率riと等しいか、近似的に等しくなるようにk(i,j)を求めることで、システムにおける故障要素を推定することとしている。
【００３６】
ここで、q=ATu+eにおいて、qは、プローブ試験により得られた結果（正常性比率）から得られる値（の集合）であり、Aもプローブ試験に応じて得られる値である。また、uは、予め保持したパラメータ値から得られる値である。また、eは、プローブ試験の結果から得られる値である。故障推定器105は、試験結果や予め保持した値を用いて、q、A、u、eを算出し、既存のパラメータ推定法により|q−(ATu+e)|2を最小化するTを求める。なお、各log(p(j→0))は、必ずしも既知である必要はない。
【００３７】
また、q'=ATu+e'において、q'は、プローブ試験により得られた結果と、予め保持したパラメータ値から得られる値であり、Aはプローブ試験に応じて得られる値であり、uは、予め保持したパラメータ値から得られる値である。また、e'は、プローブ試験の結果から得られる値である。故障推定器105は、試験結果や予め保持した値を用いて、q'、A、u、e'を算出し、既存のパラメータ推定法により|q'−(ATu+e')|2を最小化するTを求める。なお、各log(p(j→0))は、必ずしも既知である必要はない。
【００３８】
（他の推定法の例）
nsが大きい場合には、推定は容易ではないので、そのような場合は、以下のような推定法を用いることができる。つまり、本実施の形態に係る故障推定器105（故障推定部202）は、以下の推定法を実行することも可能である。
【００３９】
通常、意味のある答えが得られるのは、rank(A)がnaの場合であるので、これを前提とする。
【００４０】
a)各log(p(j→0))が既知の場合
FAの第１からns行目までの部分を単位行列化する行列Fが存在する。そのFを用い、Fqの第１からns行目までの要素からなるベクトルをwとする。するとTu=wである。これから、各jについて、(log(p(i→0))−wj)2を最小化するiを求めて、そのiをi*とおく。ここで、wjは、wの第j要素である。そして、tjの推定値としてi*を得る。
【００４１】
b)各log(p(j→0))も共に推定したい場合
a)で求めたwの要素を昇順に並べ直す行列Gが存在する。wの第i要素がGwでは第j要素となる場合、G(i)=jと表記する。Gwの第(i+1)、i要素間の距離di=(Gw)i+1−(Gw)iを定義する。diの大きい方からnt-1個を抽出する。それらを添え字の小さい方から順に、i(1),…,i(nt-1)と表記する。i(0)=0、i(nt)=nsと約束する。log(p(k→0))の推定値として、Σj=i(k-1)+1,….,i(k)(Gw)j/(i(k)-i(k-1))を計算する。G(j)がi(k-1)+1,….,i(k)に含まれれば、tj=kと推定される。
【００４２】
c)推定値の改良
a)あるいはb)で求めたtjの推定値は、得られた情報のうち、FAの第１からns行目までの部分に相当する部分しか使っていない。そこで、以下で、これらの推定値を改良する方法を説明する。以下では、a)あるいはb)で求めたtjの推定値に基づくTを[T]と記載する。
【００４３】
step1)|(q−A[T]u)i|を最大にするiをi'と表記する。|(q−A[T]u)i'|が規定値以下なら改良終了。
【００４４】
step2)[T]の第j行の第i成分が1あとは0であるとき、T'(j)として第j行以外は[T]と同じ、第j行は第(i-1)成分が1であとは0か、第(i+1)成分が1であとは0か、である行列とする。このいずれであるかは、|(q−AT'(j)u)i'|を小さくする方を採用する。各jに対して、|(q−AT'(j)u)i'|を最小化したT'(j)を[T]として採用する。step1へ戻る。
【００４５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４６】
１０１  システム
１０２  プローブ送信装置
１０３  プローブ受信装置
１０４  プローブ送受信装置
１０５  故障推定器
２０１  試験部
２０２  故障推定部
２０３  記憶部
【図１】
2014170332.tif 000003
【図２】
2014170332.tif 000004