(57)【特許請求の範囲】
【請求項１】
ネットワークを構成するノード間の接続関係を推定するトポロジ推定装置であって、
前記ノードが備えるＩＦ(Interface)を、サブネットを構成するＩＦの数であるｋ個（ｋ≧２）全てのＩＦが同一ノードに備えられることを除き、ｋ個組合せたＩＦの組合せを接続関係の判定候補として生成する生成部と、
前記生成されたｋ個のＩＦ毎の送受信トラフィック量を所定間隔の時刻毎に取得して、前記ｋ個のＩＦの送受信トラフィック量の合計値に対するＩＦ毎の送受信トラフィック量の比率を前記時刻毎に求め、当該時刻毎に当該比率の中で最小の比率に基づく判定値を生成し、当該判定値が予め定められた閾値以上となる時刻を解析対象時刻として選定する選定部と、
前記解析対象時刻における、各ＩＦの送信トラフィック量の合計値と受信トラフィック量の合計値との差分の絶対値である平衡度を求めるトラフィック計算部と、
前記解析対象時刻の平衡度が予め定められた第１誤差未満であることを判定する第１判定条件と、同解析対象時刻の前記判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの前記受信トラフィック量の合計以下であることを判定する第２判定条件との双方を満たす場合に、当該双方を満たした全てのＩＦの組合せを選択し、この選択した各ＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する判定計算部と
を備えることを特徴とするトポロジ推定装置。
【請求項２】
前記第２判定条件は、同解析対象時刻の前記判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの前記受信トラフィック量の合計に予め定められた第２誤差を加算した値以下であることを判定する条件である
ことを特徴とする請求項１に記載のトポロジ推定装置。
【請求項３】
請求項１又は２に記載のトポロジ推定装置の各機能を、コンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを構成する装置間の接続関係を推定するためのトポロジ推定装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワークを運用して管理する上では、ネットワークを構成する装置間の接続関係（以下、「トポロジ」という）を正確に把握することが重要となる。例えば、装置に故障が発生した場合、トポロジを用いて故障がネットワーク全体に与える影響を把握し、サービスへの影響を最小限にするために通信経路の切換え等を実行する。その際に、トポロジの情報が正確でなければ、故障の影響を正しく把握することができない。更には、誤った経路への切換えにより正常な通信を中断させる可能性すらある。
【０００３】
そこで、トポロジを推定する手法として、装置が備えるＩＦ（インタフェース）毎の送受信トラフィック量を用いる手法が、非特許文献１又は特許文献１に開示されている。この開示されたトポロジの推定手法では、次の２つの原則を利用する。
（原則１）あるサブネットへの流入トラフィックの量と流出トラフィックの量は等しい。
（原則２）あるノードからのサブネットへの流入トラフィックは同一サブネットの異なるノードへ出ていく。
この２つの原則を利用し、サブネットを共有するノードをネットワークの中から全て求めることにより、トポロジを推定する。なお、ここでサブネットとは、複数のＩＦが接続された閉じたネットワークのことを意味する。以下、具体的に説明する。
【０００４】
図１に示すように、あるサブネットにｓ個のノードＮ（ノードＮ１〜ＮＳ）が接続されているものとする。サブネットには、各ノードＮが備えるＩＦが最低１つ以上接続され、合計ｍ個（ｍ≧ｓ）のＩＦが接続される。このサブネットに接続されたノードＮ１のＩＦの集合を「φ１」と定め、同様に、ノードＮ２〜ＮＳについても、「φ２」〜「φＳ」と定めたとする。この場合、サブネットへの流入／流出トラフィックはそれぞれ「φ１」〜「φＳ」の送信トラフィック量・受信トラフィック量それぞれの合計となる。そのため、（原則１）は、「φ１」〜「φＳ」を用いて、以下の判定式１として読み替えることができる。
（φ１〜φＳの送信トラフィック量の合計）＝（φ１〜φＳの受信トラフィック量の合計）
…  判定式１
そのため、判定式１が成立した場合、（原則１）を満たしていると判定することができる。
【０００５】
また、ノードＮ１からこのサブネットへの流入トラフィックは、「φ１」の送信トラフィック量の合計であり、（原則２）に従えば、このトラフィックは、ノードＮ１以外の残りｓ−１個のノードＮが有するＩＦのうち、このサブネットに接続されたＩＦ、すなわち、「φ２」〜「φＳ」の中の一つ以上のＩＦが受信することになる。そのため、以下の式が成立することになる。
（φ１の送信トラフィック量の合計）≦（φ２〜φＳの受信トラフィック量の合計）
これは、ノードＮ２〜ＮＳについても同様である。よって、（原則２）は、以下の判定式２として読み替えることができる。
（φｉの送信トラフィック量の合計）≦（φｉを除く、φ１〜φＳの受信トラフィック量の合計）
［ｉ＝１，２，…，ｓ］
…  判定式２
そのため、判定式２が成立した場合、（原則２）を満たしていると判定することができる。
【０００６】
このようなトポロジの推定手法では、ｓ個のノードＮが判定式１、判定式２の両条件を満たす場合に、それらのノード間に接続関係があるとみなす。よって、推定対象の各ノードＮが備えるＩＦの送信トラフィック量及び受信トラフィック量の値を基に、判定式１、判定式２の両方の条件を満たすノードＮの組を求めることで、ノード間の接続関係を全て求めることができる。
【０００７】
また、非特許文献１には、図２に示すように、サブネットに接続された３つ以上のＩＦ１〜ＩＦ３から成るノードＮ１〜Ｎ３の接続関係の推定について記載されている。この推定は、各ノードＮ１〜Ｎ３の３つ以上のＩＦ１〜ＩＦ３における平衡度を求めて行う。平衡度は、次の（式１）により求められる。
平衡度＝(φ1〜φＳの送信トラフィック量合計値)
−(φ1〜φＳの受信トラフィック量合計値)  …（式１）
但し、平衡度は絶対値で表される。
【０００８】
図２の例の場合、ノードＮ１のＩＦ３、ノードＮ２のＩＦ１、ノードＮ３のＩＦ１における平衡度は、３つのＩＦ３，ＩＦ１，ＩＦ１のサブネットへの流入トラフィック量（送信トラフィック量）の合計値と、サブネットからの流出トラフィック量（受信トラフィック量）の合計値とを、次のように（式１）に当て嵌めて求める。
平衡度＝（送信トラフィック量の合計値）−（受信トラフィック量の合計値）
＝（５０＋５＋３０）−（１５＋４５＋２５）
＝０
このように、流入と流出が完全に一致した場合、平衡度は「０」となる。この平衡度が「０」に近いほど、送信トラフィック量と受信トラフィック量との同期性が高いといえる。
【０００９】
ＩＦ数が３以上の場合は、平衡度が所定値（後述する許容誤差σと同等の値）未満で且つ逆流していないと判定されたＩＦが、接続関係にあると推定される。但し、「逆流していない」との判定は、判定式２が成立時に「逆流していない」と判定されるようになっている。以降、平衡度が所定値以下で且つ逆流していないとの判定を、３以上接続判定という。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１４−４９８５１号公報
【非特許文献】
【００１１】
【非特許文献１】丹治  直幸、他３名、「トラフィック量を用いたネットワークトポロジー推定技術の検討」、社団法人電子情報通信学会、信学技報、ｖｏｌ．１１２、ｎｏ．４９２、ＩＣＭ２０１２−７５、ｐｐ．９５−１００、２０１３年３月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、非特許文献１に記載の内容において、図２を参照して説明したように、サブネットに接続されている各ノードのＩＦが３つ以上ある場合は、次に説明するようにトポロジ推定が高精度に行えないことがある。
【００１３】
例えば、図３に示すように、５つのＩＦ１，ＩＦ２，ＩＦ３，ＩＦ４，ＩＦ５からサブネットへ流入されるトラフィック量（送信トラフィック量）が「５０００」、「５００」、「２６５０」、「２０」、「１５」であり、サブネットから各ＩＦ１〜ＩＦ５へ流出されるトラフィック量（受信トラフィック量）が「２６５０」、「１５００」、「４０００」、「５」、「３０」であるとする。但し、各ＩＦ１〜ＩＦ５は、図３には示さないが、図２に示したように各ノードに備えられている。
【００１４】
このように、各ＩＦ１〜ＩＦ５の送受信トラフィック量（単に、トラフィック量ともいう）に大幅な差がある場合、換言すれば、トラフィック量の比率に大幅な差がある場合を想定する。但し、各ＩＦ１〜ＩＦ５のトラフィック量の比率とは、ＩＦ１〜ＩＦ５の送受信トラフィック量の合計値に対するＩＦ１〜ＩＦ５毎の送受信トラフィック量の割合である。図３の例において各トラフィック量の比率を１００分率で表すと次のようになる。各トラフィック量の比率は、ＩＦ１が４６．７％、ＩＦ２が１２．２％、ＩＦ３が４０．６％、ＩＦ４が０．２％、ＩＦ５が０．３％となる。
【００１５】
また、５つのＩＦ１〜ＩＦ５の組合せは、図４の表の１行目から７行目に○印で示すように７種類あるとする。１行目の組合せの平衡度は、上述した（式１）により、（５００＋２６５０＋２０＋１５）−（１５００＋４０００＋５＋３０）＝｜２３５０｜（以降、絶対値記号は省略）と求められる。同様に、２行目の平衡度は「１０００」、３行目の平衡度は「１３５０」、４行目の平衡度は「１５」、５行目の平衡度は「１５」、６行目の平衡度は「６」、７行目の平衡度は「０」と求められる。
【００１６】
ここで、図３の接続例において正しい接続関係が、図４の７行目に示すように、平衡度が「０」となるＩＦ１，ＩＦ２，ＩＦ３，ＩＦ４，ＩＦ５の５つの組合せであるとする。１行目〜３行目に示すように、トラフィック量の比率の大きいＩＦ１〜ＩＦ３の何れかが存在しない組合せの場合は、平衡度も「２３５０」「１０００」「１３５０」のように大きくなる。この場合は、平衡度が「０」から懸け離れて大きいので、ＩＦ１〜ＩＦ５に接続関係は無いと判定することができる。つまり、上述した３以上接続判定を行うための所定値が例えば「５０」であると仮定した場合、平衡度「２３５０」「１０００」「１３５０」の何れも所定値「５０」以上なので、３以上接続判定の結果は成立しない。
【００１７】
しかし、４行目〜６行目に示すように、トラフィック量の比率が大幅に小さいＩＦ４，ＩＦ５の何れか一方又は双方が存在しない組合せの場合は、平衡度が「１５」「１５」「０」のように大幅に小さくなる。このＩＦ４，ＩＦ５のようにトラフィック量の比率が他のＩＦ１，ＩＦ２，ＩＦ３のトラフィック量の比率よりも大幅に小さい場合、ＩＦ４，ＩＦ５が有っても無くても平衡度に寄与する影響は殆ど皆無である。
【００１８】
このような平衡度「１５」又は「０」は所定値「５０」未満なので、３以上接続判定の結果は、もう１つの条件が「逆流していない」と判定された場合に成立してしまう。つまり、４行目〜６行目のように、ＩＦ４，ＩＦ５の何れか１つ又は双方が存在しない組合せの場合は、本来接続関係が無いが、接続関係が有るというトポロジ推定が行われてしまう。このように、サブネットに接続されるノードのＩＦが３つ以上ある場合は、トポロジ推定の精度が低いという問題があった。
【００１９】
本発明は、このような背景に鑑みてなされたものであり、サブネットに接続されるノードのＩＦが３つ以上ある場合でも、ノード間のトポロジ推定を高精度に行うことができるトポロジ推定装置及びプログラムを提供することを課題とする。
【課題を解決するための手段】
【００２０】
前記した課題を解決するため、請求項１に記載の発明は、ネットワークを構成するノード間の接続関係を推定するトポロジ推定装置であって、前記ノードが備えるＩＦ(Interface)を、サブネットを構成するＩＦの数であるｋ個（ｋ≧２）全てのＩＦが同一ノードに備えられることを除き、ｋ個組合せたＩＦの組合せを接続関係の判定候補として生成する生成部と、前記生成されたｋ個のＩＦ毎の送受信トラフィック量を所定間隔の時刻毎に取得して、前記ｋ個のＩＦの送受信トラフィック量の合計値に対するＩＦ毎の送受信トラフィック量の比率を前記時刻毎に求め、当該時刻毎に当該比率の中で最小の比率に基づく判定値を生成し、当該判定値が予め定められた閾値以上となる時刻を解析対象時刻として選定する選定部と、前記解析対象時刻における、各ＩＦの送信トラフィック量の合計値と受信トラフィック量の合計値との差分の絶対値である平衡度を求めるトラフィック計算部と、前記解析対象時刻の平衡度が予め定められた第１誤差未満であることを判定する第１判定条件と、同解析対象時刻の前記判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの前記受信トラフィック量の合計以下であることを判定する第２判定条件との双方を満たす場合に、当該双方を満たした全てのＩＦの組合せを選択し、この選択した各ＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する判定計算部とを備えることを特徴とするトポロジ推定装置とした。
【００２１】
この構成によれば、次のような作用効果を得ることができる。ｋ＝３の場合に、トポロジ推定の対象となる３つのＩＦの組合せにおける各ＩＦの送受信トラフィック量の比率（トラフィック比率）を所定間隔の時刻毎に算出し、各時刻の中から、各ＩＦの比率が極端に離れていないトラフィック比率を有する時刻ｔを選定する。この選定された解析対象時刻毎に各ＩＦの送受信トラフィック量の平衡度を求めたとする。この場合、３つのＩＦの比率が極端に離れたトラフィック比率を除いて、３つのＩＦの比率が極端に離れていないトラフィック比率のＩＦ群のみで、平衡度を求めることができる。このため、その平衡度の値は、解析対象時刻間で極端に離れることが少なくなる。
【００２２】
更に、平衡度が第１及び第２判定条件の双方を満たす場合に、双方を満たした全ての３つのＩＦの組合せの平衡度を、所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。このため、解析対象時刻間で値が極端に離れていない平衡度の中から、更に、より小さい値の平衡度を選出するので、「０」又はより「０」に近い平衡度を選出することができる。
【００２３】
平衡度は「０」に近いほど、送信トラフィック量と受信トラフィック量との同期性が高いので、平衡度が「０」又はより「０」に近いＩＦの組合せは、高い確率で接続関係にあると言えることが分かっている。このことから、上述で選出された、より小さい値の平衡度のＩＦの組合せ、即ち、最適なＩＦの組合せは、高い確率で接続関係にあると言える。このようにサブネットに接続されるノードのＩＦが３つ以上ある場合でも、ノード間のトポロジ推定を高精度に行うことができる。
【００２４】
請求項２に係る発明は、前記第２判定条件は、同解析対象時刻の前記判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの前記受信トラフィック量の合計に予め定められた第２誤差を加算した値以下であることを判定する条件であることを特徴とする請求項１に記載のトポロジ推定装置である。
【００２５】
この構成によれば、第２判定条件を、更に第２誤差を加算した値以下であることを判定する条件として、第１及び第２誤差を、各ＩＦの送受信トラフィック量のデータ取得タイミングのズレ等による誤差に対応する値としておけば、時刻毎の取得時に取得された送受信トラフィック量のデータの誤差を容認することができる。
【００２６】
請求項３に係る発明は、請求項１又は２に記載のトポロジ推定装置の各機能を、コンピュータに実現させるためのプログラムである。
【００２７】
この構成によっても、請求項１又は２と同様な作用効果を得ることができる。
【発明の効果】
【００２８】
本発明によれば、サブネットに接続されているノードのＩＦが３つ以上ある場合でも、ノード間のトポロジ推定を高精度に行うことができるトポロジ推定装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００２９】
【図１】接続関係のある複数のＩＦで構成されるサブネットを説明するための図である。
【図２】各ノードのＩＦ間の送受信トラフィック量を示す図である。
【図３】５つのＩＦ間の送受信トラフィック量を示す図である。
【図４】図３に示す５つのＩＦ１〜ＩＦ５の各組合せパターンの平衡度を示す図である。
【図５】本実施形態に係る各ノードのサブネットに接続された３つのＩＦのトラフィック比率を時刻ｔ毎に１００分率で示した棒グラフを示す図である。
【図６】本実施形態に係るノードＩＦ対応リストのデータ構成例を示す図である。
【図７】（ａ）本実施形態に係るＩＦリストのデータ構成例を示し、（ｂ）ＩＦデータリストのデータ構成例を示し、（ｃ）接続判定済フラグリストのデータ構成例を示す図である。
【図８】本実施形態に係る接続判定候補リストのデータ構成例を示す図である。
【図９】本実施形態に係るＩＦ接続リストのデータ構成例を示す図である。
【図１０】本実施形態に係る解析対象時刻リストのデータ構成例を示す図である。
【図１１】（ａ）本実施形態に係る許容誤差σ及び許容誤差γを含む許容誤差リストのデータ構成例を示し、（ｂ）閾値リストのデータ構成例を示す図である。
【図１２】本実施形態に係るＩＦ接続関係の最適化処理を説明するための図である。
【図１３】本実施形態に係るトポロジ推定装置の構成を示すブロック図である。
【図１４】本実施形態に係るトポロジ推定装置によるトポロジ推定処理の流れを示す第１のフローチャートである。
【図１５】本実施形態に係るトポロジ推定装置によるトポロジ推定処理の流れを示す第２のフローチャートである。
【発明を実施するための形態】
【００３０】
次に、本発明を実施するための形態（以下、「本実施形態」と称する）について説明する。
【００３１】
＜概要＞
まず、本実施形態に係るトポロジ推定装置１（図１３参照）及びプログラムが実行するトポロジ推定処理の基本概念と処理概要について説明する。
（基本概念）
本実施形態に係るトポロジ推定装置１は、ネットワークを構成するノード（装置）間のトポロジを推定する。トポロジ推定装置１の特徴は、サブネットに接続されているノードのＩＦが３つ以上ある場合でも、後述のように、ノード間のトポロジ推定を高精度に行えるようにした点にある。
【００３２】
図５は、図２に示した各ノードＮ１〜Ｎ３のサブネットに接続された３つ以上のＩＦ１〜ＩＦ３のトラフィック量の比率（トラフィック比率ともいう）ｒ１，ｒ２，ｒ３を、時刻ｔ毎に１００分率で示した棒グラフを示す図である。但し、図２に記載した送受信トラヒック量は無視するものとする。
【００３３】
図５に示す棒グラフは、枠Ｗ１，Ｗ２，Ｗ３で囲む棒グラフを代表に挙げると、枠Ｗ１内の時刻ｔ４の棒グラフは、ＩＦ１の比率ｒ１が４２％、ＩＦ２の比率ｒ２が８％、ＩＦ３の比率ｒ３が５０％であることを示す。枠Ｗ２内の時刻ｔ９の棒グラフは、ＩＦ１の比率ｒ１が４％、ＩＦ２の比率ｒ２が５７％、ＩＦ３の比率ｒ３が３９％であり、枠Ｗ３内の時刻ｔ２９の棒グラフは、ＩＦ１の比率ｒ１が２１％、ＩＦ２の比率ｒ２が４３％、ＩＦ３の比率ｒ３が３６％であることを示す。
【００３４】
時刻ｔ４の棒グラフは、ＩＦ２の比率ｒ２が８％と極端に少なく、時刻ｔ９の棒グラフは、ＩＦ１の比率ｒ１が４％と極端に少ない。また、時刻ｔ２９の棒グラフは、極端に少ない比率Ｒが無く、ＩＦ１〜ＩＦ３の比率ｒ１〜ｒ３がバランス良く組み合わされている。
【００３５】
本発明では、図５に示すような時刻ｔ毎の各ＩＦ１〜ＩＦ３のトラフィック量の比率ｒ１〜ｒ３において、他と比べ極端に少ない比率ｒを含む時刻（例えばｔ４，ｔ９）のトラフィック量をトポロジ推定のための計算対象から外し、極端に少ない比率Ｒを含まない時刻（例えばｔ２９）の送受信トラフィック量を計算対象とする。この計算対象の送受信トラフィック量を原則１に基づく判定式３（後述）と、原則２に基づく判定式４（後述）とに当て嵌め、判定式３，４に適合した際に、適合した複数のＩＦの組合せの中から最適な組合せを選択するようにした。このように最適な組合せのＩＦを求めることにより、サブネットに接続されるノードのＩＦが３つ以上ある場合でも、精度良くトポロジ推定を行えるようにした。
【００３６】
（処理概要）
次に、本実施形態に係るトポロジ推定装置１が実行するトポロジ推定処理の概要について説明する。
まず、前提として、以下に示す手順を行うに当たって、トポロジ推定装置１の記憶手段（後述の図１３に示す記憶部３０に対応）に、図６に示すノードＩＦ対応リスト３１ａと、図７（ａ）〜（ｃ）に示すＩＦリスト３２ａ、ＩＦデータリスト３２ｂ及び接続判定済フラグリスト３２ｃと、図８に示す接続判定候補リスト３３ａと、図９に示すＩＦ接続リスト３４ａと、図１０に示す解析対象時刻リスト３５ａと、図１１に示す許容誤差σ及び許容誤差γを含む許容誤差リスト３６ａ及び閾値ε（ｋ）を含む閾値リスト３６ｂとが記憶されているものとする。なお、図６〜図１１は上述した各リスト３１ａ，３２ａ，３２ｂ，３２ｃ，３３ａ，３４ａ，３５ａ，３６ａ，３６ｂの一構成例を示している。
【００３７】
（処理手順）
≪手順１：初期設定処理≫
トポロジ推定装置１は、トポロジ推定の対象となるＩＦの数ｋを、初期値として設定する。最初は、ＩＦの接続関係の最小値が「２」なので、ｋ＝「２」が初期値として設定される。以降、トポロジ推定の対象となるＩＦの数を、推定対象ＩＦ数とも称し、推定対象ＩＦ数のｋを、ｋの値ともいう。
【００３８】
≪手順２：時刻ｔ毎の各ＩＦのトラフィック比率の判定値Ｒ（ｔ）の算出処理≫
まず、ｋ個のＩＦ（ＩＦ１，ＩＦ２，…，ＩＦｋ）について、時刻ｔ毎の各ＩＦの送受信トラフィック量の比率ｒ１（ｔ）〜ｒ３（ｔ）を算出する。例えば、手順１にてｋ＝３の場合に、３個のＩＦについて算出した場合は、図５に示す棒グラフのようになる。
【００３９】
ここで、ｎ個のＩＦ１〜ＩＦｎを有するＩＦリスト３２ａ｛図７（ａ）｝からｋ個のＩＦの組（例えば初期値では、ｋ＝２個のＩＦの組）を選ぶ組合せは「ｎＣｋ個」ある。このため、ｋ個のＩＦの全ての組合せについて後述の手順２〜５を繰り返したのち、後述の手順６へ進む。但し、選んだｋ個のＩＦが全て同一ノードに所属しているパターンは無視する。なお、ＩＦデータリスト３２ｂは、後述で詳細に説明するが、ｎ個のＩＦ毎に設けられる情報である。ｎ個のＩＦは、図７（ａ）に示すＩＦリスト３２ａに、ＩＦ１〜ＩＦｎとして格納されている。
【００４０】
次に、選んだｋ個のＩＦの各組を構成するＩＦ毎に、ＩＦデータリスト３２ｂ｛図７（ｂ）｝から時刻ｔ毎の送信トラフィック量及び受信トラフィック量を取得する。次に、ＩＦの数をｋ、時刻ｔの各ＩＦ（ＩＦ１，ＩＦ２，…，ＩＦｋ）の送受信トラフィック量の合計をＩＦ１（ｔ），ＩＦ２（ｔ），…，ＩＦｋ（ｔ）とした時、時刻ｔ毎の各ＩＦのトラフィック比率の判定値Ｒ（ｔ）を次の（式２）から算出する。
【００４１】
【数１】
0006300369.tif 000002
但し、ｘ＝１，２，…，ｋとする。
【００４２】
（式２）において、（）内は各ＩＦ１〜ＩＦｋについて、時刻ｔ毎のトラフィック量の比率の最小値ｍｉｎを求める計算式である。例えば、図５に示す枠Ｗ１内の時刻ｔ４における棒グラフのＩＦ１〜ＩＦ３の比率ｒ１〜ｒ３であれば、最小のＩＦ２の比率ｒ２＝０．０８（８％）が計算される。
【００４３】
時刻ｔ毎の各ＩＦのトラフィック比率の判定値Ｒ（ｔ）を（式２）から算出する場合、例えば、枠Ｗ１内の時刻ｔ４の棒グラフは、ＩＦ１の比率ｒ１が０．４２、ＩＦ２の比率ｒ２が０．０８、ＩＦ３の比率ｒ３が０．５０なので、（式２）からＲ（ｔ）＝０．０８×３＝０．２４が求められる。
枠Ｗ２内の時刻ｔ９の棒グラフは、比率ｒ１が０．０４、比率ｒ２が０．５７、比率ｒ３が０．３９なので、Ｒ（ｔ）＝０．０４×３＝０．１２が求められる。
枠Ｗ３内の時刻ｔ２９の棒グラフは、比率ｒ１が０．２１、比率ｒ２が０．４３、比率ｒ３が０．３６なので、上述した（式２）からＲ（ｔ）＝０．２１×３＝０．６３が求められる。
【００４４】
≪手順３：判定値Ｒ（ｔ）と閾値ε（ｋ）による解析対象時刻の選定処理≫
この手順３の処理では、トポロジ推定の対象となるＩＦ群のトラフィック比率を所定間隔の時刻ｔ毎に算出し、各時刻ｔの中から、比率が極端に離れていないトラフィック比率を有する時刻ｔを選定する処理を行う。
【００４５】
閾値ε（ｋ）は、時刻ｔ毎の各ＩＦのトラフィック比率の判定値Ｒ（ｔ）が、閾値ε（ｋ）以上の場合の時刻ｔを、トポロジ推定のための解析対象として選定するための閾値である。この解析対象として選定される時刻を、解析対象時刻という。
上述した（式２）によって算出された判定値Ｒ（ｔ）は、０≦Ｒ（ｔ）≦１の範囲を取る値であり、次の（式３）のように、判定値Ｒ（ｔ）が閾値ε（ｋ）以上となる時刻ｔを解析対象時刻として選定する。
【００４６】
Ｒ（ｔ）≧ε（ｋ）  …（式３）
【００４７】
例えば、閾値ε（ｋ）＝０．５（５０％）とした場合、図５に示す枠Ｗ１内の時刻ｔ４のＲ（ｔ）は上述で求めたように０．２４であり、枠Ｗ２内の時刻ｔ９のＲ（ｔ）は０．１２である。これら０．２４及び０．１２は、何れも閾値ε（ｋ）＝０．５未満なので時刻ｔ４，ｔ９は、×印で示すように解析対象時刻から外される。
【００４８】
一方、枠Ｗ３内の時刻ｔ２９のＲ（ｔ）は０．６３である。この０．６３は、閾値ε（ｋ）＝０．５以上なので時刻ｔ２９は、○印で示すように解析対象時刻として選定される。解析対象時刻ｔ２９の各ＩＦ１〜ＩＦ３のトラフィック量は、トポロジ推定のための計算対象となる。
【００４９】
≪手順４：解析対象時刻の出力処理≫
手順３によって選定された解析対象時刻（例えばｔ１，ｔ２９）を解析対象時刻リスト３５ａ（図１０）に選定順に記載する。この記載により作成された解析対象時刻リスト３５ａを、記憶手段へ出力する。
【００５０】
≪手順５：原則１ａ，２ａの成立判定処理≫
手順４により作成された解析対象時刻リスト３５ａから例えばＩＦ１，ＩＦ２，ＩＦ３の組合せの解析対象時刻（例えばｔ１，ｔ２９）を取得する。この取得された解析対象時刻ｔ１，ｔ２９の各ＩＦ１〜ＩＦ３の送受信トラフィック量をＩＦデータリスト３２ｂ｛図７（ｂ）｝から取得する。この取得した送受信トラフィック量が、前述の原則１，２に対応する下記の判定式３，４を満たすかどうかを確認する。
【００５１】
但し、判定式３，４を満たすことは、原則１，２を満たすことと同等である。しかし、判定式３，４には、後述のように許容誤差σ，γを容認することが加味されているので、判定式３，４を満たすことを、原則１ａ，２ａを満たすことと表現する。
【００５２】
なお、原則１ａは、請求項記載の第１誤差としての許容誤差σを容認する第１判定条件であり、原則１は、許容誤差σを含まず、所定値を容認する第１判定条件である。原則２ａは、請求項記載の第２誤差としての許容誤差γを容認する第２判定条件であり、原則２は、許容誤差γを含まない第２判定条件である。
【００５３】
但し、各ＩＦ１〜ＩＦ３の送受信トラフィック量は、当該トラフィック量のデータ取得タイミングのズレ等により誤差を含むため判定式３は許容誤差σ、判定式４は許容誤差γを容認するようにする。つまり、判定式３は原則１を満たすことを判定する判定式１に許容誤差σを容認するようにする。判定式４は原則２を満たすことを判定する判定式２に許容誤差γを容認するようにする。
【００５４】
判定式３では、各ＩＦ１〜ＩＦ３の送信トラフィック量の合計値と、受信トラフィック量の合計値との差分の絶対値から平衡度が求められ、この平衡度が許容誤差σよりも小さいことの条件が判定される。なお、各ＩＦ１〜ＩＦ３の送信トラフィック量の合計値と、受信トラフィック量の合計値を、各ＩＦ１〜ＩＦ３の送受信トラフィック量の各合計値とも表現する。
【００５５】
平衡度＝(φ1〜φＳの送信トラフィック量合計値)
−(φ1〜φＳの受信トラフィック量合計値)＜σ  …判定式３
（φｉの送信トラフィック量の合計）≦（φｉを除く、φ１〜φＳの受信トラフィック量の合計）＋γ［ｉ＝１，２，…，ｓ］  …判定式４
【００５６】
但し、判定式３，４において、φ1〜φＳは、前述の［背景技術］で図１を参照して説明したように、各ノードＮ１〜ＮＳを有する場合に、ノードＮ１のＩＦの集合を「φ１」と定め、同様に、ノードＮ２〜ＮＳについても、「φ２」〜「φＳ」と定めたものである。
≪手順６：ＩＦ接続関係の最適化処理≫
手順５で判定式３，４を満たした全てのＩＦの組合せを選択し、この選択した各ＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。この選出されたＩＦの組合せを、ＩＦ接続リスト３４ａ（図９）へ保存する。
【００５７】
この接続関係の最適化処理の例を説明する。例えば、図１２に示すように、７つのＩＦ１〜ＩＦ７がある場合に、この中から、ｋ＝３の、３つのＩＦの接続関係を推定するものとする。この際、３つのＩＦを組合せた平衡度は次の値を取るものとする。
１行目（１）に示す３つのＩＦ１，ＩＦ２，ＩＦ３の平衡度＝０．０３
２行目（２）に示す３つのＩＦ２，ＩＦ３，ＩＦ４の平衡度＝０．０５
３行目（３）に示す３つのＩＦ３，ＩＦ４，ＩＦ５の平衡度＝０．０４
４行目（４）に示す３つのＩＦ４，ＩＦ５，ＩＦ６の平衡度＝０．１２
ｊ行目（ｊ）に示す３つのＩＦ５，ＩＦ６，ＩＦ７の平衡度＝０．０５
【００５８】
この場合に、３つのＩＦを組合せた際の平衡度を、更に２つ組合せ、２つの平衡度の合計値を求める。例えば図１２に示すように、第１の組合せとして（１）＋（４）を組合せ、この平衡度の合計値を求めると、０．０３＋０．１２＝０．１５となる。第２の組合せの（１）＋（ｊ）の平衡度の合計値は、０．０３＋０．０５＝０．０８、第３の組合せの（２）＋（ｊ）の平衡度の合計値は、０．０５＋０．０５＝０．１０となる。
【００５９】
次に、複数（上記例では２つ）の平衡度の合計値の中から最小値を選び、この最小値の組合せを、最適なＩＦの組合せとして選出する。このように選出するのは、平衡度が、送受信トラフィック量が完全に一致した場合に「０」となり、平衡度が「０」に近いほど、送信トラフィック量と受信トラフィック量との同期性が高くなる。同期性が高いほどにＩＦの接続関係を確定できるためである。
【００６０】
即ち、図１２の例では、合計値「０．１５」「０．０８」「０．１０」の中から最小値「０．０８」を選び、この最小値「０．０８」の第２の組合せを、最適なＩＦの組合せ（１）＋（ｊ）として選出する。この選出されたＩＦ１〜ＩＦ３，ＩＦ５〜ＩＦ７の各々の接続判定済フラグ｛図７（ｃ）｝を「１」に更新する。この「１」は、各々のＩＦ１〜ＩＦ３，ＩＦ５〜ＩＦ７が接続済みであることを示す。そのフラグを「１」に更新した後、ＩＦ接続リスト３４ａ（図９）に、選出した接続関係ＩＦ１〜ＩＦ３とＩＦ５〜ＩＦ７とを保存する。
【００６１】
但し、３つのＩＦを組合せた際の平衡度の２つの合計値は、（１）＋（３）＝０．０３＋０．０４＝０．０７が最も小さいが、（１）と（３）にはＩＦ３が共通してある。１つのＩＦ３には、他の１つのＩＦ（ＩＦ１，ＩＦ２，ＩＦ４〜ＩＦ７の何れか１つ）しか繋がらないので、同一ＩＦが共通してある組合せは接続関係が成立しない。よって、平衡度を所定数ずつ合計する組合せに、共通のＩＦが存在する場合は、最適な組合せを選出する対象から除く。
【００６２】
≪手順７：終了判定処理≫
接続判定済フラグが「０」のＩＦの数（「０」ＩＦ数ともいう）よりも、ｋの値が大きい場合は、推定対象ＩＦ数ｋが、未接続で残っている「０」ＩＦ数よりも多い状態である。この状態では、残った「０」ＩＦ数が推定対象ＩＦ数ｋよりも少ないので、推定対象とするＩＦ数による接続関係が成立しない。従って、全ての手順１〜７を終了する。それ以外の場合は、手順１に戻り、ｋの値を「１」増やして手順２〜６を繰り返す。
【００６３】
例えば、手順６を終了後に「０」のＩＦ数＝「３」、ｋの値＝「２」であれば、手順７でｋの値が小さいと判定されるので手順１に戻って、ｋの値＝２＋１＝「３」とする。この後、手順２〜手順６の処理を行い、手順７で「０」のＩＦ数＜ｋの値となったか否かを判定する。このような手順１〜７を繰り返し、手順６において「０」のＩＦ数＝「３」、ｋの値＝「４」となれば、手順７においてｋの値「４」が大きいと判定されるので、全ての手順１〜７を終了する。
【００６４】
＜トポロジ推定装置の構成＞
次に、本実施形態に係るトポロジ推定装置１の構成について具体的に説明する。
図１３は、本実施形態に係るトポロジ推定装置１の構成を示すブロック図である。トポロジ推定装置１は、ネットワーク全体を管理するネットワーク管理装置やネットワークを構成する各ノード（装置）と接続されることにより、各ノードのＩＦに関する情報を取得し、ネットワークを構成するノード間のトポロジを推定する。この際に、サブネットに接続されるノードのＩＦが３つ以上ある場合でも、ノード間のトポロジ推定を高精度に行う。トポロジ推定装置１は、処理部１０と、入出力部２０と、記憶部３０とを備えて構成されている。
【００６５】
記憶部３０は、ハードディスクやフラッシュメモリ、ＲＡＭ(Random Access Memory)等の記憶手段からなり、その記憶領域として、ノードリスト保存部３１、ＩＦデータリスト保存部３２、接続判定候補リスト保存部３３、接続リスト保存部３４、解析対象時刻保存部３５及びパラメータ保存部３６が設定されている。
【００６６】
ノードリスト保存部３１には、ノードＩＦ対応リスト３１ａ（図６）が格納される。ＩＦデータリスト保存部３２には、ＩＦリスト３２ａ｛図７（ａ）｝、ＩＦデータリスト３２ｂ｛図７（ｂ）｝及び接続判定済フラグリスト３２ｃ｛図７（ｃ）｝が格納される。接続判定候補リスト保存部３３には、接続判定候補リスト３３ａ（図８）が格納される。接続リスト保存部３４には、ＩＦ接続リスト３４ａ（図９）が格納される。解析対象時刻保存部３５には、解析対象時刻リスト３５ａ（図１０）が格納される。また、パラメータ保存部３６には、許容誤差リスト３６ａ及び閾値リスト３６ｂ（図１１）が格納される。
【００６７】
図６に示すノードＩＦ対応リスト３１ａは、各ノード（装置）が、どのＩＦを備えているかを示す情報であり、各ノードの「ノード名」に対応付けて、ＩＦの識別情報である「ＩＦ名」が格納される。例えば、１行目のノードＮ１には「ＩＦ１」，「ＩＦ３」，…等が対応付けて格納され、２行目のノードＮ２には「ＩＦ１」，「ＩＦ２」，…等が、Ｓ行目のノードＮＳには「ＩＦ３」，「ＩＦ１」，…等が対応付けて格納されている。
【００６８】
図７（ａ）に示すＩＦリスト３２ａは、ノード毎に設けられる全てのＩＦ１〜ＩＦｎが格納されている。
【００６９】
図７（ｂ）に示すＩＦデータリスト３２ｂは、ＩＦ毎に設けられる情報であり、時刻ｔ毎に、「送信トラフィック量」及び「受信トラフィック量」が対応付けられて格納されている。ＩＦデータリスト３２ｂが例えばＩＦ１のものである場合、時刻ｔ１，ｔ２，…，ｔｘ毎に、送信トラフィック量の「５」，「１０」，…，「２５」と、受信トラフィック量の「４３」，「３５」，…，「４５」とが対応付けられて格納されている。
【００７０】
図７（ｃ）に示す接続判定済フラグリスト３２ｃは、各ノードのＩＦ毎、つまり、トポロジの推定対象のＩＦ毎（ＩＦリスト３２ａのＩＦ１〜ＩＦｎ毎）に対応付けて設定される情報であり、「ＩＦ名」のＩＦ１，ＩＦ２，…，ＩＦｎ毎に、接続判定済フラグ「０」又は「１」が対応付けられて格納される。接続判定済フラグ（単に、フラグともいう）は、他のＩＦとの間に接続関係が無いと判定された場合に「０」が付され、接続関係が有ると判定された場合に「１」が付される。なお、フラグの初期値は全て「０」が設定される。また、接続判定済フラグリスト３２ｃには、例えば、ＩＦデータリスト保存部３２に、新たなＩＦのＩＦデータリスト３２ｂが記憶される都度、そのリスト３２ｂのＩＦに対応付けてフラグが設定されるようになっている。
【００７１】
図８に示す接続判定候補リスト３３ａは、「ＩＦの組合せ」毎に、「平衡度」を対応付けて設定する情報である。例えば、「ＩＦの組合せ」である１行目のＩＦ１，ＩＦ２，ＩＦ３に、「平衡度」の「０．０３」が対応付けられて格納されている。
【００７２】
図９に示すＩＦ接続リスト３４ａは、接続関係があるＩＦ同士、つまり、サブネットを構成すると判定されたＩＦの組合せが１行毎に格納される。例えば、１行目に「ＩＦ１，ＩＦ２，ＩＦ３」が、接続関係があるＩＦの組合せの情報として格納されている。
【００７３】
図１０に示す解析対象時刻リスト３５ａは、閾値ε（ｋ）を用いて選定された「解析対象時刻」と、この時刻においてトラフィック比率を構成する「ＩＦの組合せ」とを対応付けた情報である。例えば、ＩＦの組合せのＩＦ１，ＩＦ２，ＩＦ３に、解析対称時刻のｔ１，ｔ２９（図５参照）が対応付けられ、…、ＩＦ４，ＩＦ５にｔ３，ｔ８が対応付けられている。
【００７４】
図１１（ａ）に示す許容誤差リスト３６ａは、原則１に基づく判定式３の判定に用いる許容誤差σ＝０．１と、原則２に基づく判定式４に用いる許容誤差γ＝０．１とを含む情報である。
【００７５】
図１１（ｂ）に示す閾値リスト３６ｂは、閾値ε（ｋ）を格納するものであり、例えば閾値ε（ｋ）＝０．５が格納されている。
【００７６】
図１３に示す入出力部２０は、図示せぬネットワーク管理装置や、ネットワークを構成する各ノード等との装置間の情報の入出力を行う。また、入出力部２０は、通信回線を介して情報の送受信を行う図示せぬ通信インタフェース、並びに、キーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースを備えて構成されている。
【００７７】
入出力部２０は、ネットワーク管理装置等からノードＩＦ対応リスト３１ａ、ＩＦリスト３２ａ、ＩＦ毎のＩＦデータリスト３２ｂ、並びに、許容誤差σ及び許容誤差γを含む許容誤差リスト３６ａ及び閾値リスト３６ｂを受信して記憶部３０に記憶する。ノードＩＦ対応リスト３１ａはノードリスト保存部３１に格納され、ＩＦリスト３２ａ及びＩＦデータリスト３２ｂはＩＦデータリスト保存部３２に、許容誤差リスト３６ａ及び閾値リスト３６ｂはパラメータ保存部３６に格納される。
【００７８】
また、入出力部２０は、接続リスト保存部３４に保存されたＩＦ接続リスト３４ａをネットワーク管理装置や、トポロジ推定装置１に備えられた図示せぬモニタ等に出力する。
【００７９】
処理部１０は、トポロジ推定装置１の全体の制御を司り、ノード間のトポロジ推定処理を実行するものである。処理部１０は、判定候補生成部１１と、解析対象時刻選定部１２と、トラフィック計算部１３と、判定計算部１４と、推定終了判定部１５とを備えて構成されている。なお、処理部１０は、例えば、記憶部３０に記憶されたプログラムをＣＰＵ（Central Processing Unit)がＲＡＭに展開して、実行することで実現される。なお、判定候補生成部１１は請求項記載の生成部であり、解析対象時刻選定部１２は、請求項記載の選定部である。以降、判定候補生成部１１を単に生成部１１、解析対象時刻選定部１２を単に選定部１２とも称する。
【００８０】
判定候補生成部１１は、記憶部３０に記憶されたノードＩＦ対応リスト３１ａ、ＩＦリスト３２ａ、ＩＦデータリスト３２ｂ及び接続判定済フラグリスト３２ｃを取得し、推定対象とするＩＦの組合せを生成する。この生成のため、生成部１１は、接続判定済フラグリスト３２ｃの接続判定済フラグが「０」｛図７（ｃ）｝となっているＩＦの数（「０」ＩＦ数）をｎ個とし、入出力部２０から受け取ったｋの値を、上述の手順１で説明した初期値として設定する。この設定されるｋの値は、上述の手順１〜７の動作を繰り返す場合に、「１」ずつ増加されて上書きされる。
【００８１】
次に、生成部１１は、手順２で説明したように、ｎ個のＩＦデータリスト３２ｂ｛図７（ｂ）｝からｋ個のＩＦの組合せ「ｎＣｋパターン」を生成する。この際、生成部１１は、ノードＩＦ対応リスト３１ａを参照して、ｋ個のＩＦが全て同一のノードに所属しているパターンについては生成を行わない。生成部１１は、生成したｋ個のＩＦの組合せを、接続判定候補リスト保存部３３の接続判定候補リスト３３ａへ格納する。また、生成部１１は、推定終了判定部１５から手順７での判定が終了せず、手順１で新たなｋの値が入力された場合も、上記の入出力部２０からｋの値を受け取った場合と同様の動作を行う。
【００８２】
解析対象時刻選定部（単に、選定部ともいう）１２は、手順２，３で説明したように、解析対象時刻の選定を次のように行う。まず、選定部１２は、記憶部３０からＩＦ毎のＩＦデータリスト３２ｂ｛図７（ｂ）｝と、閾値リスト３６ｂ｛図１１（ｂ）｝とを取得する。この取得したＩＦデータリスト３２ｂには、時刻ｔ１〜ｔｘ毎に計測された送信トラフィック量及び受信トラフィック量が格納されている。また、閾値リスト３６ｂには、例えば閾値ε（ｋ）＝０．５が格納されている。
【００８３】
選定部１２は、例えば、生成部１１にｋ＝３が設定されている場合に、３つのＩＦ１〜ＩＦ３のＩＦデータリスト３２ｂから送受信トラフィック量を取得し、図５に棒グラフで示したように、時刻ｔ毎の各ＩＦ１〜ＩＦ３のトラフィック比率ｒ１（ｔ）〜ｒ３（ｔ）を算出する。
【００８４】
次に、選定部１２は、時刻ｔ毎の各ＩＦ１〜ＩＦ３のトラフィック比率ｒ１（ｔ）〜ｒ３（ｔ）の判定値Ｒ（ｔ）を、上述の（式２）から算出する。例えば、手順２で説明したように、図５の枠Ｗ１内の時刻ｔ４の判定値Ｒ（ｔ）が０．２４、枠Ｗ２内の時刻ｔ９のＲ（ｔ）が０．１２、枠Ｗ３内の時刻ｔ２９のＲ（ｔ）が０．６３と算出される。
【００８５】
次に、選定部１２は、閾値ε（ｋ）＝「０．５」と、上述の各時刻ｔ４，ｔ９，ｔ２９の判定値Ｒ（ｔ）＝「０．２４」，「０．１２」，「０．６３」の各々とを比較する。この比較により、上述の（式３）のように、判定値Ｒ（ｔ）が閾値ε（ｋ）以上となる時刻ｔを解析対象時刻として選定する。
上記の例では、時刻ｔ４のＲ（ｔ）＝０．２４と時刻ｔ９のＲ（ｔ）＝０．１２は、何れも閾値ε（ｋ）＝０．５未満なので解析対象時刻から外す。
一方、時刻ｔ２９のＲ（ｔ）＝０．６３は、閾値ε（ｋ）＝０．５以上なので、当該時刻ｔ２９は解析対象時刻として選定する。この解析対象時刻ｔ２９の各ＩＦ１〜ＩＦ３のトラフィック量が、トポロジ推定のための計算対象となる。
【００８６】
次に、選定部１２は、手順４で説明したように、上記で選定した解析対象時刻ｔ２９を、該当のＩＦの組合せＩＦ１〜ＩＦ３に対応付けて解析対象時刻リスト３５ａ（図１０）に記載する。この記載は選定順に行われる。更に、選定部１２は、所定時刻分の解析対象時刻を記載して作成した解析対象時刻リスト３５ａを、記憶部３０の解析対象時刻保存部３５へ出力して保存する。
【００８７】
トラフィック計算部１３は、手順５で説明した平衡度の計算を行う。トラフィック計算部１３は、記憶部３０から解析対象時刻リスト３５ａを取得し、このリスト３５ａに記載された解析対象時刻（例えばｔ１，ｔ２９）及びこれに対応付けられたＩＦの組合せ「ＩＦ１〜ＩＦ３」を取得する。更に、トラフィック計算部１３は、そのＩＦの組合せ「ＩＦ１〜ＩＦ３」に対応するＩＦデータリスト３２ｂにおいて、解析対象時刻ｔ１，ｔ２９毎の送信トラフィック量及び受信トラフィック量を取得する。
【００８８】
次に、トラフィック計算部１３は、時刻ｔ１，ｔ２９毎の各ＩＦ１〜ＩＦ３の送受信トラフィック量の各合計値を上述の（式１）に当て嵌めて平衡度を算出し、この平衡度を接続判定候補リスト３３ａ（図８）の平衡度欄に、該当ＩＦ１〜ＩＦ３から成るＩＦの組合せに対応付けて記載する。この記載後のリスト３３ａは接続判定候補リスト保存部３３のリスト３３ａに上書きされる。
【００８９】
判定計算部１４は、手順５で説明した原則１ａ，２ａの成立判定を行う。判定計算部１４は、記憶部３０から接続判定候補リスト３３ａと、このリスト３３ａに記載されたＩＦの組合せの各ＩＦ１〜ＩＦ３に対応するＩＦデータリスト３２ｂと、許容誤差リスト３６ａとを取得する。この取得後、判定計算部１４は、接続判定候補リスト３３ａに記載された平衡度と、許容誤差リスト３６ａに記載された許容誤差σとを用いて、該当解析対象時刻ｔにおいて、上述の判定式３を満たすか否かを判定する。この判定では原則１ａを満たすか否かが判定されることになる。例えば、接続判定候補リスト３３ａに記載されたＩＦ１〜ＩＦ３の平衡度０．０３は、許容誤差σ＝０．１よりも小さいので、原則１ａを満たすと判定される。
【００９０】
更に、判定計算部１４は、各ＩＦ１〜ＩＦ３のＩＦデータリスト３２ｂに記載された送受信トラフィック量の各々を合計した合計値を用いて、該当解析対象時刻ｔにおいて、上述の判定式４を満たすか否かを判定する。この判定では原則２ａを満たすか否かが判定されることになる。
例えば、時刻ｔ１におけるＩＦ１の送信トラフィック量の合計値が「１５」で、ＩＦ１を除くＩＦ２，ＩＦ３の受信トラフィック量の合計値が「３５」の場合は、判定式４を満たすので、原則２ａを満たすと判定される。
【００９１】
この後、判定計算部１４は、手順６で説明した接続関係の特定処理を行う。まず、判定計算部１４は、原則１ａ，２ａを満たした全てのＩＦの組合せの平衡度を、接続判定候補リスト３３ａから選択する。次に、判定計算部１４は、その選択したＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。そして、判定計算部１４は、その選出されたＩＦの組合せを、ＩＦ接続リスト３４ａ（図９）へ保存する。
【００９２】
例えば、図１２に示す７つのＩＦ１〜ＩＦ７において、原則１ａ，２ａを満たした３つのＩＦの組合せが、１行目〜ｊ行目に示すように存在するものとする。
この場合、判定計算部１４は、原則１ａ，２ａを満たした全てのＩＦの組合せの平衡度を、接続判定候補リスト３３ａ（図８）から選択し、この選択したＩＦの組合せの平衡度を２つずつ組合せてその合計値を得る（この場合、所定数は「２」）。例えば、第１の組合せとして（１）＋（４）を組合せて平衡度を合計して０．１５を得る。同様に、第２の組合せとして（１）＋（ｊ）を組合せて平衡度を合計して０．０８を得る。第３の組合せとして（２）＋（ｊ）を組合せて平衡度を合計して０．１０を得る。
【００９３】
次に、判定計算部１４は、各合計値「０．１５」「０．０８」「０．１０」の中から最小値「０．０８」を選び、この最小値「０．０８」の第２の組合せを、最適なＩＦの組合せＩＦ１〜ＩＦ３，ＩＦ５〜ＩＦ７として選出する。判定計算部１４は、その選出されたＩＦ１〜ＩＦ３，ＩＦ５〜ＩＦ７の各々の接続判定済フラグ｛図７（ｃ）｝を「１」に更新した後、ＩＦ接続リスト３４ａ（図９）に、選出した各接続関係ＩＦ１〜ＩＦ３とＩＦ５〜ＩＦ７とを保存する。
【００９４】
推定終了判定部１５は、手順７による終了判定処理を行う。即ち、推定終了判定部１５は、ＩＦデータリスト保存部３２に保存された各ＩＦに対応する接続判定済フラグリスト３２ｃのフラグを参照し、フラグが「０」のＩＦの数と、現時点のｋの値とを比較する。推定終了判定部１５は、「０」ＩＦ数がｋの値よりも大きい場合は、ｋの値を「１」増やして、生成部１１へ出力し、トポロジの推定処理を続行する。一方、「０」ＩＦ数がｋの値以下の場合は、トポロジ推定の処理を終了する。
【００９５】
＜処理の流れ＞
次に、本実施形態に係るトポロジ推定装置１のトポロジ推定処理の流れについて説明する。図１４は、本実施形態に係るトポロジ推定装置１のトポロジ推定処理の流れを示すフローチャートである。
【００９６】
まず、図１４に示すステップＳ１において、トポロジ推定装置１の入出力部２０は、ネットワーク管理装置等から、ノードＩＦ対応リスト３１ａ、ＩＦ毎のＩＦデータリスト３２ｂ、許容誤差σ、許容誤差γ、閾値ε（ｋ）を取得し、記憶部３０に記憶する。ここで、許容誤差σ＝０．１、許容誤差γ＝０．１、閾値ε（ｋ）＝０．５であるとする。
この際、ＩＦデータリスト３２ｂが記憶部３０に記憶されると、判定候補生成部１１が、そのＩＦデータリスト３２ｂのＩＦに対応する接続判定済フラグリスト３２ｃのフラグを初期値「０」とする。
【００９７】
次に、ステップＳ２において、生成部１１はｋの値を設定する。この際、入出力部２０が、ｋの値（初期値ｋ＝２）を生成部１１へ出力し、生成部１１が、そのｋの値「２」を初期値として設定する。ここで、ｋの値は、初期時にはｋ＝２であるが、後述のステップＳ１１においてｋ＝３とされて、再度ステップＳ２に戻ってきた場合のｋ＝３であるとする。
【００９８】
次に、ステップＳ３において、生成部１１は、ｎ個のＩＦデータリスト３２ｂからｋ個のＩＦの組合せ「ｎＣｋパターン」を生成する。この時点でｋ＝３なのでＩＦの組合せは、３個のＩＦによるものである。但し、接続判定済フラグリスト３２ｃのフラグ「０」のＩＦ数が、ｎ個あったとする。また、生成部１１は、３個のＩＦが全て同一のノードに所属しているパターンについては生成を行わない。更に、生成部１１は、前記で生成した３個のＩＦの組合せを、接続判定候補リスト保存部３３の接続判定候補リスト３３ａへ保存する。
【００９９】
次に、ステップＳ４において、解析対象時刻選定部１２は、解析対象時刻の選定を行う。まず、選定部１２は、ｋ＝３なので、３つのＩＦ１〜ＩＦ３の各ＩＦデータリスト３２ｂから送受信トラフィック量を取得し、図５に棒グラフで示したように、時刻ｔ１〜ｔ３８毎の各ＩＦ１〜ＩＦ３のトラフィック比率ｒ１（ｔ）〜ｒ３（ｔ）を算出する。
【０１００】
次に、選定部１２は、時刻ｔ１〜ｔ３８毎の各ＩＦ１〜ＩＦ３のトラフィック比率ｒ１（ｔ）〜ｒ３（ｔ）の判定値Ｒ（ｔ）を、上述の（式２）から算出する。例えば、図５の時刻ｔ４の判定値Ｒ（ｔ）＝０．２４、時刻ｔ９のＲ（ｔ）＝０．１２、時刻ｔ２９のＲ（ｔ）＝０．６３と算出する。
【０１０１】
次に、選定部１２は、閾値リスト３６ｂの閾値ε（ｋ）＝「０．５」と、各時刻ｔ４，ｔ９，ｔ２９の判定値Ｒ（ｔ）＝「０．２４」，「０．１２」，「０．６３」の各々とを比較し、上述の（式３）のように、判定値Ｒ（ｔ）が閾値ε（ｋ）以上となる時刻ｔ１、ｔ２９を解析対象時刻として選定する。選定部１２は、その選定した解析対象時刻ｔ１，ｔ２９を、解析対象時刻リスト３５ａの解析対称時刻欄に、該当ＩＦの組合せＩＦ１〜ＩＦ３に対応付けて保存する。
【０１０２】
次に、ステップＳ５において、トラフィック計算部１３は平衡度の計算を行う。まず、トラフィック計算部１３は、解析対象時刻リスト３５ａに記載された解析対象時刻ｔ１，ｔ２９及びこれに対応付けられたＩＦの組合せ「ＩＦ１〜ＩＦ３」を検出する。更に、トラフィック計算部１３は、そのＩＦの組合せ「ＩＦ１〜ＩＦ３」に対応する各ＩＦデータリスト３２ｂにおいて、解析対象時刻ｔ１，ｔ２９毎の送信トラフィック量及び受信トラフィック量を取得する。
【０１０３】
次に、トラフィック計算部１３は、時刻ｔ１，ｔ２９毎の各ＩＦ１〜ＩＦ３の送受信トラフィック量の各合計値を上述の（式１）に当て嵌めて平衡度を算出し、この平衡度を接続判定候補リスト３３ａの平衡度欄に、該当ＩＦ１〜ＩＦ３に対応付けて保存する。
【０１０４】
次に、ステップＳ６において、判定計算部１４は、原則１ａ，２ａの成立判定処理を行う。まず、判定計算部１４は、接続判定候補リスト３３ａのＩＦ１〜ＩＦ３に記載された平衡度０．０３と、許容誤差リスト３６ａに記載された許容誤差σ＝０．１とを用いて、上述の判定式３を満たすか否かを判定する。この場合、ＩＦ１〜ＩＦ３の平衡度０．０３は、許容誤差σ＝０．１よりも小さいので、原則１ａを満たすと判定される。
【０１０５】
更に、判定計算部１４は、各ＩＦ１〜ＩＦ３のＩＦデータリスト３２ｂの解析対象時刻ｔ１，ｔ２９毎の送受信トラフィック量の各々を合計した合計値を用いて、上述の判定式４を満たすか否かを判定する。例えば、時刻ｔ１におけるＩＦ１の送信トラフィック量の合計値が「１５」で、ＩＦ１を除くＩＦ２，ＩＦ３の受信トラフィック量の合計値が「３５」の場合は、判定式４を満たすので、原則２ａを満たすと判定される。この判定は、時刻ｔ２９においても同様に行われ、更に、ＩＦ２，ＩＦ３においても同様に行われる。
【０１０６】
次に、図１５に示すステップＳ７において、判定計算部１４は、上記ステップＳ４〜Ｓ６の処理を、「ｎＣｋパターン」のＩＦの組合せ全てについて行ったか否かを判定する。この判定結果、全てについて行っていなければ、上記ステップＳ４に戻って処理を行う。一方、全てについて行った場合は、ステップＳ８へ進む。
【０１０７】
次に、ステップＳ８において、判定計算部１４は、原則１ａ，２ａの双方を満たしたか否かを判定する。満たしていればステップＳ９へ進み、満たしていなければステップＳ１０へ進む。
【０１０８】
上記満たした場合のステップＳ９において、判定計算部１４は、ＩＦ接続関係の最適化処理を行う。まず、判定計算部１４は、上記ステップＳ８で原則１ａ，２ａを満たした全てのＩＦの組合せの平衡度を、接続判定候補リスト３３ａから選択する。次に、判定計算部１４は、その選択したＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。そして、判定計算部１４は、その選出された組合せの各ＩＦに対応する接続判定済フラグを「１」に更新した後、選出されたＩＦの組合せをＩＦ接続リスト３４ａに保存する。
【０１０９】
この保存後、又は上記ステップＳ８を満たしていない場合は、ステップＳ１０において、推定終了判定部１５が、トポロジ推定の終了判定を行う。即ち、推定終了判定部１５は、現時点における接続判定済フラグリスト３２ｃのフラグが「０」のＩＦの数「ｎ」が、上記ステップＳ３で設定されたｋの値（例えばｋ＝３）以下であるか否かを判定する。この結果、ｋ以下でない場合、即ちｋの値よりも大きい場合（Ｎｏ）は、ステップＳ１１に進み、ｋの値を、現時点のｋに「１」を加えた値とした後に、上記ステップＳ３へ戻り、処理を続ける。
一方、ｋ以下である場合（Ｙｅｓ）は、推定終了判定部１５はトポロジ推定処理を終了する。
【０１１０】
その終了後、ステップＳ１２において、入出力部２０は、接続リスト保存部３４に保存されたＩＦ接続リスト３４ａをネットワーク管理装置や、トポロジ推定装置１に備えられた図示せぬモニタ等に出力する。
【０１１１】
＜実施形態の効果＞
以上説明したように、本実施形態に係るネットワークを構成する装置（ノード）間の接続関係を推定するトポロジ推定装置１は、判定候補生成部（生成部）１１と、解析対象時刻選定部（選定部）１２と、トラフィック計算部１３と、判定計算部１４とを備える構成とした。
【０１１２】
生成部１１は、ノードが備えるＩＦ(Interface)を、サブネットを構成するＩＦの数であるｋ個（ｋ≧２）全てのＩＦが同一ノードに備えられることを除き、ｋ個組合せたＩＦの組合せを接続関係の判定候補（トポロジ推定候補）として生成する。
【０１１３】
選定部１２は、その生成されたｋ個のＩＦ毎の送受信トラフィック量を所定間隔の時刻毎に取得して、ｋ個のＩＦの送受信トラフィック量の合計値に対するＩＦ毎の送受信トラフィック量の比率（トラフィック比率）を時刻毎に求め、当該時刻毎に当該比率の中で最小の比率に基づく判定値を生成し、当該判定値が予め定められた閾値以上となる時刻を解析対象時刻として選定する。
【０１１４】
トラフィック計算部１３は、解析対象時刻毎に各ＩＦの送信トラフィック量の合計値と受信トラフィック量の合計値との差分の絶対値である平衡度を求める。
【０１１５】
判定計算部１４は、解析対象時刻の平衡度が予め定められた第１誤差σ未満であることを判定する原則１としての第１判定条件と、同解析対象時刻の前記の判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの受信トラフィック量以下であることを判定する原則２としての第２判定条件との双方を満たす場合に、当該双方を満たした全てのＩＦの組合せの平衡度を所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。
【０１１６】
この構成によれば、次のような効果を得ることができる。ｋ＝３の場合に、トポロジ推定の対象となる３つのＩＦの組合せにおける各ＩＦのトラフィック比率を所定間隔の時刻毎に算出し、各時刻の中から、各ＩＦの比率が極端に離れていないトラフィック比率を有する時刻ｔを選定する。この選定された解析対象時刻毎に各ＩＦの送受信トラフィック量の平衡度を求めたとする。この場合、従来のように３つのＩＦの比率が極端に離れたトラフィック比率を除いて、３つのＩＦの比率が極端に離れていないトラフィック比率のＩＦ群のみで、平衡度を求めることができる。このため、その平衡度の値は、解析対象時刻間で極端に離れることが少なくなる。
【０１１７】
更に、平衡度が原則１，２の双方を満たす場合に、双方を満たした全ての３つのＩＦの組合せの平衡度を、所定数ずつ合計した合計値が、最も小さくなるＩＦの組合せを、最適なＩＦの組合せとして選出する。このため、解析対象時刻間で値が極端に離れていない平衡度の中から、更に、より小さい値の平衡度を選出するので、「０」又はより「０」に近い平衡度を選出することができる。
【０１１８】
平衡度は「０」に近いほど、送信トラフィック量と受信トラフィック量との同期性が高いので、平衡度が「０」又はより「０」に近いＩＦの組合せは、高い確率で接続関係にあると言えることが分かっている。このことから、上述で選出された、より小さい値の平衡度のＩＦの組合せ、即ち、最適なＩＦの組合せは、高い確率で接続関係にあると言える。このようにサブネットに接続されるノードのＩＦが３つ以上ある場合でも、ノード間のトポロジ推定を高精度に行うことができる。
【０１１９】
また、上述の第２判定条件は、同解析対象時刻の前記の判定候補となるＩＦの組合せの中から、１つのＩＦを抽出し、当該抽出したＩＦの前記送信トラフィック量が、当該抽出したＩＦを除く全てのＩＦの受信トラフィック量の合計に予め定められた第２誤差γを加算した値以下であることを判定する条件であることとした。
【０１２０】
この構成によれば、第２判定条件を、更に第２誤差γを加算した値以下であることを判定する条件として、第１及び第２誤差を、各ＩＦの送受信トラフィック量のデータ取得タイミングのズレ等による誤差に対応する値としておけば、時刻毎の取得時に取得された送受信トラフィック量のデータの誤差を容認することができる。
【０１２１】
また、本発明は、コンピュータを、トポロジ推定装置１として機能させるためのプログラムとしても具現化することができる。
その他、具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０１２２】
１  トポロジ推定装置
１０  処理部
１１  判定候補生成部
１２  解析対象時刻選定部
１３  トラフィック計算部
１４  判定計算部
１５  推定終了判定部
２０  入出力部
３０  記憶部
３１ａ  ノードＩＦ対応リスト
３２ａ  ＩＦリスト
３２ｂ  ＩＦデータリスト
３２ｃ  接続判定済フラグリスト
３３ａ  接続判定候補リスト
３４ａ  ＩＦ接続リスト
３５ａ  解析対象時刻リスト
３６ａ  許容誤差リスト
３６ｂ  閾値リスト
【図１】
0006300369.tif 000003
【図２】
0006300369.tif 000004
【図３】
0006300369.tif 000005
【図４】
0006300369.tif 000006
【図５】
0006300369.tif 000007
【図６】
0006300369.tif 000008
【図７】
0006300369.tif 000009
【図８】
0006300369.tif 000010
【図９】
0006300369.tif 000011
【図１０】
0006300369.tif 000012
【図１１】
0006300369.tif 000013
【図１２】
0006300369.tif 000014
【図１３】
0006300369.tif 000015
【図１４】
0006300369.tif 000016
【図１５】
0006300369.tif 000017