(57)【要約】【課題】開示の接続状態推定装置では、複数の装置を備える通信ネットワークにおいて、装置間のＲＴＴ等ネットワーク距離を利用し、経験や人手によらず自動的に装置間の接続状態を推定することができる。【解決手段】開示の接続状態装置は、はじめに、通信ネットワークを構成する端末装置間のネットワーク距離を取得する。次に、当該装置は、任意の３つの端末装置と接続する分岐地点候補を仮定し、各装置間と分岐地点候補とのネットワーク距離を算出する。この処理は、端末装置から任意の３つを抽出する組合せ全てについて行う。そして、当該装置は、近傍に存在する分岐地点候補を１つに束ね、この束ねられた分岐地点候補に接続すると仮定された全ての端末装置は、当該束ねられた分岐地点候補に接続すると推定する。【選択図】図４
2010233097.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
装置間距離取得手段が、複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得するステップと、
候補距離算出手段が、前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出するステップと、
グルーピング手段が、一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うステップと、
代表値算出手段が、前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出するステップと、
接続状態推定手段が、前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なすステップと、実行させるための接続状態推定プログラム。
【請求項２】
前記分岐地点が２つ以上存在する場合、該２つ以上の分岐地点は相互に接続すると見なし、さらに、前記装置間の前記ネットワーク距離及び該分岐地点と該装置との前記ネットワーク距離に基づき、該分岐地点間の該ネットワーク距離を算出させることを特徴とする請求項１に記載の接続状態推定プログラム。
【請求項３】
前記分岐地点が３つ以上存在する場合、該各分岐地点を前記装置と見なして、前記候補距離算出手段、前記グルーピング手段、前記代表値算出手段、及び前記ネットワーク接続状態推定手段による各ステップを実行させることを特徴とする請求項２に記載の接続状態推定プログラム。
【請求項４】
前記グルーピング手段が、前記一の装置と各分岐地点候補との前記ネットワーク距離の差が所定の閾値以下となる該分岐地点候補を、同一グループに分類する場合、
閾値算出手段が、前記装置間距離取得手段により取得される前記ネットワーク距離の平均値に基づき、前記所定の閾値を算出するステップをさらに有することを特徴とする請求項１乃至３の何れか一に記載の接続状態推定プログラム。
【請求項５】
複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得する装置間距離取得手段と、
前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出する候補距離算出手段と、
一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うグルーピング手段と、
前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出する代表値算出手段と、
前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なす接続状態推定手段と、を有することを特徴とする接続状態推定装置。
【請求項６】
装置間距離取得手段が、複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得するステップと、
候補距離算出手段が、前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出するステップと、
グルーピング手段が、一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うステップと、
代表値算出手段が、前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出するステップと、
接続状態推定手段が、前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なすステップと、を有することを特徴とする接続状態推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の装置を備える通信ネットワークにおいて、装置間の接続状態を推定する技術に関する。
【背景技術】
【０００２】
通信ネットワークのユーザにとって、ネットワークの構成（トポロジーやノードの物理的な位置）を把握することは、ネットワークの利用やネットワーク障害時の対処において大変重要である。
【０００３】
一方、ユーザがネットワークキャリアの提供する広域ネットワークサービスを利用する場合、キャリアはネットワーク網の内部構成を公開しないため、ユーザがネットワーク構造を直接把握することは困難である。
【０００４】
そこで、ユーザは、通信ネットワークを構成する装置間のＲｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ（以下、ＲＴＴという。）に基づき、広域ネットワークの内部構造を推定することが出来る。つまり、広域ネットワークで接続された複数のユーザ拠点間でのＲＴＴを計測し、計測したＲＴＴに基づきネットワーク内部の分岐地点の数、接続関係、および位置（各分岐地点間やユーザ拠点とのＲＴＴ）を推定する。具体的には、少数（例えば、３点）のユーザ拠点間を繋ぐ１点の分岐地点を仮定し、計測されたＲＴＴに矛盾が無いかを試し、または当該仮定及び試行を適宜繰り返すことでネットワークの内部構造を推定する。別の形態としては、上記方法に経験的、地理的な推定を組み合わせて、ネットワークの内部構造を推定する場合もある（図１）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１５８９０７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上記のような推定方法には経験的な要素が含まれるため計算方法も明確でなく、また、人手による推定であるため大規模な通信ネットワークには対応できないという問題点がある。
【０００７】
そこで、本発明では、上記問題点に鑑み、複数の装置を備える通信ネットワークにおいて、装置間のＲＴＴ等ネットワーク距離を利用し、経験や人手によらず自動的に装置間の接続状態を推定する接続状態推定装置、方法およびプログラムを提供する。
【課題を解決するための手段】
【０００８】
開示の接続状態推定装置の一形態では、複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得する装置間距離取得手段と、前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出する候補距離算出手段と、一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うグルーピング手段と、前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出する代表値算出手段と、前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なす接続状態推定手段と、を有することを特徴とする。
【発明の効果】
【０００９】
開示の接続状態推定装置、方法およびプログラムでは、複数の装置を備える通信ネットワークにおいて、装置間のＲＴＴ等ネットワーク距離を利用し、経験や人手によらず自動的に装置間の接続状態を推定することができる。
【図面の簡単な説明】
【００１０】
【図１】従来技術によりネットワーク内の接続状態を推定する技術の模式図である。
【図２】本実施の形態に係る接続状態推定装置によりネットワーク内の接続状態を推定する処理の模式図である。
【図３】本実施の形態に係る接続状態推定装置を含むネットワーク内の接続状態を推定するシステムの構成例である。
【図４】本実施の形態に係る接続状態推定装置の機能ブロック図である。
【図５】本実施の形態に係る接続状態推定装置による処理例における観測装置相互間のＲＴＴを示す図である。
【図６】本実施の形態に係る接続状態推定装置による処理例全体のフローチャートである。
【図７】本実施の形態に係る接続状態推定装置による分岐地点候補を仮定し、該分岐地点候補と観測装置とのＲＴＴを算出する処理のフローチャートである。
【図８】本実施の形態に係る接続状態推定装置による分岐地点候補を融合する処理のフローチャートである。
【図９】本実施の形態に係る接続状態推定装置による分岐地点候補をカテゴリ分けする処理のフローチャートである。
【図１０】本実施の形態に係る接続状態推定装置による処理例における観測装置間のＲＴＴを示す図である。
【図１１】本実施の形態に係る接続状態推定装置による処理例における分岐地点候補リストを示す図である。
【図１２】本実施の形態に係る接続状態推定装置による処理例における観測装置リストを示す図である。
【図１３】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ａに着目した場合、カテゴリ分類前）を示す図である。
【図１４】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ｅに着目した場合、カテゴリ分類前）を示す図である。
【図１５】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ａに着目した場合、カテゴリ分類処理途中（その１））を示す図である。
【図１６】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ａに着目した場合、カテゴリ分類処理途中（その２））を示す図である。
【図１７】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ａに着目した場合、カテゴリ分類処理途中（その３））を示す図である。
【図１８】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ａに着目した場合、カテゴリ分類処理終了時点）を示す図である。
【図１９】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリリスト（観測装置Ｅに着目した場合、カテゴリ分類処理終了時点）を示す図である。
【図２０】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリ代表リスト（観測装置Ａに着目した場合）を示す図である。
【図２１】本実施の形態に係る接続状態推定装置による処理例におけるカテゴリ代表リスト（観測装置Ｅに着目した場合）を示す図である。
【図２２】本実施の形態に係る接続状態推定装置による処理例における分岐地点リストを示す図である。
【図２３】本実施の形態に係る観測装置および分岐地点相互間のＲＴＴを示す図である。
【発明を実施するための形態】
【００１１】
（本実施の形態に係る接続状態推定装置の概要）
図２、図３を用いて、本実施の形態に係る接続状態推定装置１００の概要について説明する。図２は、接続状態推定装置１００により通信ネットワークを構成する装置間の接続状態を推定する模式図であり、図３は、通信ネットワーク及び接続状態推定装置１００のシステム構成図である。
【００１２】
図２、図３で示すように、通信ネットワークを構成する装置間の接続状態を推定するために、広域ネットワークの各所に配置される観測装置間で相互にＲＴＴを計測し、その結果を観測結果統合装置２００に集約する。そして、接続状態推定装置１００は、観測結果統合装置２００に集約した観測結果に対し下記の処理を施すことにより、分岐地点間、分岐地点・観測装置間の接続関係及びＲＴＴを推定する。また、図３においては、観測結果統合装置２００と接続状態推定装置１００とは別の装置として記載されているが、同一の装置として実施しても良い。
【００１３】
（１）観測装置間のＲＴＴ取得
はじめに、接続状態推定装置１００は、接続状態の推定対象となる観測装置間のＲＴＴを取得する。推定対象となる観測装置がＮ個の場合、取得するＲＴＴのデータはＮ×Ｎマトリクス状のデータ形態で表される。ここで、ＲＴＴは、観測装置間での遅延時間であり、接続状態推定装置１００において取り扱うデータ属性が統一されている限り、片道の遅延時間であっても良く、往復の遅延時間であっても良い。
【００１４】
（２）分岐地点候補の仮定と分岐地点候補・観測装置間のＲＴＴ算出
次に、接続状態推定装置１００は、全ての観測装置から３つを選択し、その３つの観測装置と接続する分岐地点候補を仮定する。そして、接続状態推定装置１００は、当該３つの観測装置と分岐地点候補とのＲＴＴを、後述する方程式を解くことにより算出する。
【００１５】
また、接続状態推定装置１００は、全ての観測装置から３つの観測装置を選択する組合せ全通りについて分岐地点候補を仮定し、当該３つの観測装置と分岐地点候補とのＲＴＴを算出する。つまり、推定対象となる観測装置がＮ個の場合、ＮＣ３個の分岐地点候補が仮定される。
【００１６】
（３）分岐地点候補の融合
接続状態推定装置１００は、１つの観測装置に着目し、その観測装置に接続すると仮定される全ての分岐地点候補について、相互距離が所定の閾値以下となる分岐地点候補を融合する。そして、接続状態推定装置１００は、融合前の分岐地点候補に接続すると仮定する観測装置は、融合後の分岐地点候補に接続していると、見なす。
【００１７】
さらに、接続状態推定装置１００は、上記処理により融合した分岐地点候補に接続している観測装置を除く、残りの観測装置に接続すると仮定される分岐地点候補を融合する処理を行う。
【００１８】
接続状態推定装置１００は、（３）のプロセスにより融合後の分岐地点候補が１つとなる場合、全観測装置は当該分岐地点候補に接続していると推定する。また、接続状態推定装置１００では、（３）のプロセスにより融合後の分岐地点候補が２つとなる場合、当該２つの分岐地点候補が接続し、各観測装置は何れか１つの分岐地点候補に接続していると推定する。
【００１９】
（４）分岐地点候補間の接続
接続状態推定装置１００は、上記（３）のプロセスにより融合後の分岐地点候補が３つ以上となる場合、各観測装置は何れか１つの分岐地点候補に接続していると推定すると共に、これらの分岐地点候補を観測装置と見なし、上記（２）（３）のプロセスを再度実行する。この場合、接続状態推定装置１００は、各分岐地点候補間のＲＴＴを算出した上で、上記（２）（３）のプロセスを実行する。
【００２０】
図４で示すように、接続状態推定装置１００は、装置間距離取得手段１１０、候補距離算出手段１２０、グルーピング手段１３０、代表値算出手段１４０、接続状態推定手段１５０、閾値算出手段１６０を有する。装置間距離取得手段１１０は上記（１）に記載した処理を実施し、候補間距離算出手段１２０は上記（２）に記載した処理を実施し、グルーピング手段１３０、代表値算出手段１４０、接続状態推定手段１５０は上記（３）の処理を実施する。また、閾値算出手段１６０は、グルーピング手段１３０において使用する閾値を算出する。
【００２１】
ここで、接続状態推定装置１００はＣＰＵ（Central Processing Unit）、ＲＯＭ（Read-Only Memory）、ＨＤＤ（Hard Disc Drive）等を備える。そして、接続状態推定装置１００が有する各手段は、ＣＰＵがＲＯＭ又はＨＤＤに記憶された各手段に対応するプログラムを実行することにより実現される形態としても良い。また、接続状態推定装置１００が有する各手段は、当該各手段に関する処理をハードウェアとして実現する形態としても良い。
【００２２】
（本実施の形態に係る接続状態推定装置による処理例）
ここでは、図５で示すように、接続状態推定装置１００による処理対象は、６つの観測装置（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ）として説明を行い、これら観測装置間のＲＴＴを図５中に示す。ただし、接続状態推定装置１００の処理対象となる観測装置の数は６つに限られず、各装置間のＲＴＴもここで例示するものに限られない。また、図１０では処理対象である観測装置間のＲＴＴを６×６マトリクス状のデータ形態にしたものを示し、上下同一のデータ構造となるため上半分のデータのみを記載している。図１０では、例えば、装置ＡＢ間のＲＴＴは２２（ｍｓ）、装置ＡＣ間のＲＴＴは２５（ｍｓ）、装置ＢＣ間のＲＴＴは２７（ｍｓ）であることを示している。
【００２３】
なお、以下の説明で用いる図６から図９中の＜Ａ＞、＜Ｂ＞、＜Ｃ＞、＜Ｄ＞、＜Ｅ＞、＜Ｆ＞は、各図に示すフローチャート間の遷移関係を表している。
【００２４】
（１）処理対象となる観測装置間のＲＴＴの取得
図６を用いて、ＲＴＴ取得処理について説明する。Ｓ１０で装置間距離取得手段１１０は、図１０で示すような６×６のマトリクスとなったＲＴＴ情報１７０を、各観測装置又は観測結果統合装置２００から取得する。ここで、ＲＴＴは、各観測装置間での伝搬遅延時間であり、接続状態推定装置１００において取り扱うデータ属性が統一されている限り、片道の伝搬遅延時間であっても良く、往復の伝搬遅延時間であっても良い。
【００２５】
（２）分岐地点候補の仮定と分岐地点候補・観測装置間のＲＴＴの算出
図６、図７を用いて、分岐地点候補を仮定し、該分岐地点候補と観測装置間のＲＴＴを算出する処理について説明する。Ｓ２０で候補距離算出手段１２０は、分岐地点候補を仮定し、該分岐地点候補と観測装置間のＲＴＴを算出する処理を行う。以下、Ｓ２０における候補距離算出手段１２０の処理を詳細に説明する。
【００２６】
Ｓ７０で、候補距離算出手段１２０は、図１０で示すＲＴＴ情報１７０を取得する。そして、Ｓ８０で、候補距離算出手段１２０は、全ての観測装置から３つ（例えば、Ａ、Ｂ、Ｃの３つ）を選択し、この３つの観測装置を接続する分岐地点候補（例えば、Ｘ１）を仮定する。次に、Ｓ９０で、候補距離算出手段１２０は、選択した３つの観測装置相互間のＲＴＴに基づき、各観測装置・分岐地点候補間のＲＴＴを算出し、算出したＲＴＴを図１１で示すようなテーブルに書き出す。
【００２７】
Ｓ８０で観測装置Ａ、Ｂ、Ｃの３つを選択し、分岐地点候補をＸ１とした場合を例として考える。Ａ・Ｂ間のＲＴＴをα（ｍｓ）、Ｂ・Ｃ間のＲＴＴをβ（ｍｓ）、Ａ・Ｃ間のＲＴＴをγ（ｍｓ）、Ｘ１・Ａ間のＲＴＴをａ（ｍｓ）とした場合、Ｘ１・Ｂ間のＲＴＴはα−ａ（ｍｓ）、Ｘ１・Ｃ間のＲＴＴはγ−ａ（ｍｓ）と表すことができる。ここで、「Ｘ１・Ｂ間のＲＴＴ」＋「Ｘ１・Ｃ間のＲＴＴ」＝「Ｂ・Ｃ間のＲＴＴ」であるため、（α−ａ）＋（γ−ａ）＝βとなる。すると、α、β、γは既知なので、Ｘ１・Ａ間のＲＴＴであるａ（ｍｓ）を求めることができる。ａを求めると、Ｘ１・Ｂ間のＲＴＴであるα−ａ、Ｘ１・Ｃ間のＲＴＴであるγ−ａも算出することができる。
【００２８】
そして、候補距離算出手段１２０は、全ての観測装置から３つを抽出する全ての組合せについてＳ８０及びＳ９０における処理を行う（Ｓ１００）。この処理例のように６つの観測装置がある場合、候補距離算出手段１２０は、６Ｃ３＝２０個の分岐地点候補を仮定し、それぞれの分岐地点候補・観測装置間のＲＴＴを算出し、図１１で示すようなテーブルを作成する。
【００２９】
（３）分岐地点候補の融合
図６、図８、図９を用いて、分岐地点候補を融合する処理について説明する。この処理により、近傍にある分岐地点候補を同一のものとして融合する。Ｓ３０でグルーピング手段１３０、代表値算出手段１４０及び接続状態推定手段１５０の各手段は、分岐地点候補を融合する処理を行う。また、Ｓ３０で接続状態推定装置１００では、図１２で示すような観測装置リストを生成する。図１２で示す観測装置リストは、各観測装置が融合後の分岐地点候補と接続されているか否か、つまり、観測装置と融合後の分岐地点候補との接続状態が確定しているか否かの情報を保持するものである。図１２中の「接続済」「未接続」は、観測装置毎に、融合後の分岐地点候補と接続したか否かを示すフラグであり、初期状態において当該フラグは全て「未接続」となっている。以下で、Ｓ３０におけるグルーピング手段１３０、代表値算出手段１４０及び接続状態推定手段１５０の各手段による処理を詳細に説明する。
【００３０】
Ｓ１１０でグルーピング手段１３０は、図１２で示す観測装置リストから接続状態フラグが「未接続」である観測装置を１つ選択する。ここでは、グルーピング手段１３０は、観測装置Ａを選択し、グルーピング手段１３０により選択された観測装置（ここでは、Ａ）をターゲット観測装置と呼ぶものとして説明を行う。
【００３１】
Ｓ１２０でグルーピング手段１３０は、ターゲット観測装置と接続する全ての分岐地点候補についてカテゴリ分けを行う。図９を用いて、Ｓ１２０におけるグルーピング手段１３０による処理の詳細を説明する。なお、図９で示すような手法の他に、一般的なクラスタリングアルゴリズム（例えば、Ｋ平均法等）を用いても良い。
【００３２】
Ｓ１７０でグルーピング手段１３０は、図１３で示すように、ターゲット観測装置と接続する全ての分岐地点候補のリストを作成する。ここで、図１３で示すリストをカテゴリリストと呼び、当該カテゴリリストは分岐地点候補を行方向に配置し、各行は分岐地点候補ＩＤ、分岐地点候補と各装置とのＲＴＴ、カテゴリＩＤ及び評価フラグの各欄を有する。図１３で示すように、カテゴリリストの初期状態において、カテゴリＩＤ及び評価フラグの欄は空である。
【００３３】
Ｓ１８０でグルーピング手段１３０は、カテゴリリストから評価フラグ欄が空の分岐地点候補を１つ選択する。ここでは、グルーピング手段１３０により分岐地点候補Ｘ１が選択されることとする。さらに、Ｓ１８０でグルーピング手段１３０は、図１５で示すように、分岐地点候補Ｘ１のカテゴリＩＤに「Ｃ１」を設定し、分岐地点候補Ｘ１の評価フラグを「済」にする。
【００３４】
Ｓ１９０でグルーピング手段１３０は、Ｓ１８０において選択した分岐地点候補Ｘ１とターゲット観測装置ＡとのＲＴＴを「Ｒ」とする。ここでは、Ｒ＝１０である。
【００３５】
Ｓ２００でグルーピング手段１３０は、Ｓ１８０において選択した分岐地点候補Ｘ１とは異なる、カテゴリリストの評価フラグが「済」でない分岐地点候補を１つ選択する。ここでは、グルーピング手段１３０により分岐地点候補Ｘ２が選択されることとする。さらに、Ｓ１９０でグルーピング手段１３０は、Ｓ１９０において選択した分岐地点候補Ｘ２とターゲット観測装置ＡとのＲＴＴを「Ｓ」とする。ここでは、Ｓ＝１０である。
【００３６】
Ｓ２１０においてグルーピング手段１３０は、「Ｒ」と「Ｓ」とを比較する。当該ステップにより分岐地点候補Ｘ１、Ｘ２が近傍にあるか否かを評価している。そして、予め融合閾値（以下、Ｔｈ−Ｕという。）を設定しておき、ＳがＲ±Ｔｈ−Ｕの範囲内に収まっている場合にはＳ２２０の処理に移行し（Ｓ２１０でＹｅｓ）、ＳがＲ±Ｔｈ−Ｕの範囲内に収まっていない場合にはＳ２３０の処理に移行する（Ｓ２１０でＮｏ）。この処理例では、Ｓ＝Ｒであるため、Ｓ２１０でＹｅｓとなりＳ２２０の処理に移行する。
【００３７】
Ｓ２２０でグルーピング手段１３０は、Ｓ２００で選択した分岐地点候補Ｘ２について、分岐地点候補Ｘ１と同一カテゴリに属すると判定し、図１６で示すように、分岐地点候補Ｘ１と同一のカテゴリＩＤ「Ｃ１」を付与する。
【００３８】
Ｓ２３０でグルーピング手段１３０は、Ｓ２００で選択した分岐地点候補Ｘ２について、図１６で示すように、カテゴリリストの評価フラグを「済」にする。
【００３９】
Ｓ２４０でグルーピング手段１３０は、カテゴリリストに含まれる全ての分岐地点候補についてＳ２００からＳ２３０の処理を実施する。Ｓ２４０では、各分岐地点候補の評価フラグ欄を参照してＳ２００からＳ２３０の処理に移行するか否かを判断する。図１６では、分岐地点候補Ｘ１からＸ９に対し順に、Ｓ２００からＳ２３０の処理を実施し作成されたカテゴリリストを示している。また、図１７では、Ｓ２１０における比較の結果、分岐地点候補Ｘ１０は近傍に存在しないと判断されたためＳ２２０の処理がスキップされ、分岐地点候補Ｘ１０にはカテゴリＩＤが付与されていないことを示している。
【００４０】
Ｓ２５０でグルーピング手段１３０は、全ての分岐地点候補についてカテゴリ分類を終了したか否かを判定する。グルーピング手段１３０は、カテゴリリストを参照して、全ての分岐地点候補にカテゴリＩＤが付与されていれば、全ての分岐地点候補についてカテゴリ分類が終了しないと判定し（Ｓ２５０でＮｏ）、Ｓ１３０の処理に移行する。一方、カテゴリＩＤが付与されていない分岐地点候補があれば、全ての分岐地点候補についてカテゴリ分類が終了したと判定し（Ｓ２５０でＹｅｓ）、Ｓ２６０の処理に移行する。
【００４１】
Ｓ２６０でグルーピング手段１３０は、カテゴリリストにおいてカテゴリＩＤが付与されていない分岐地点候補について、カテゴリリストの評価フラグ欄を空に戻し、Ｓ１８０の処理に移行する。これにより、グルーピング手段１３０は新たなカテゴリ分類を再実行することとなる。図１８では、グルーピング手段１３０によるカテゴリ分類が再実行されることにより、図１７では未分類であった分岐地点候補Ｘ１０がカテゴリＩＤ「Ｃ２」に分類されたことを示している。
【００４２】
Ｓ１３０で代表値算出手段１４０は、Ｓ１２０における処理（図９を用いて説明した処理）によって付与されたカテゴリ毎に一の分岐地点候補を仮定し、当該一の分岐地点候補と各観測装置とのＲＴＴを算出する。ここで、当該ＲＴＴは、同一のカテゴリに含まれる各観測装置のＲＴＴの平均値、最大値又は最小値とするなど所定の計算方法により算出する。なお、Ｓ１３０で代表値算出手段１４０が算出するＲＴＴは、特許請求の範囲におけるネットワーク距離の代表値に対応する。
【００４３】
続けて、Ｓ１３０で代表値算出手段１４０は、算出したカテゴリ毎、観測装置毎のＲＴＴを、図２０で示すようなカテゴリ代表リストに記入する。ここで、図２０で示すカテゴリ代表リストは、１行が１つのカテゴリ（例えば、「Ｃ１」や「Ｃ２」）に相当し、各カテゴリにおける分岐地点候補から各観測装置へのＲＴＴを保持する。
【００４４】
Ｓ１４０で接続状態推定手段１５０は、１つのターゲット観測装置について、Ｓ１２０で分類したカテゴリの中から最も妥当な接続関係を選択する。具体的には、接続状態推定手段１５０は、図２０で示すカテゴリ代表リストの列方向で、つまり、カテゴリ間で各観測装置のＲＴＴを比較し、ＲＴＴの値が１つだけ存在する行（カテゴリ）を選択する。そして、接続状態推定手段１５０は、ＲＴＴの値が１つだけ存在する観測装置が、当該ＲＴＴを以て、選択されたカテゴリに対応する分岐地点候補と接続すると推定する。ここで、接続状態推定手段１５０は、ターゲット観測装置を除いて上記の比較処理を行い、ターゲット観測装置が上記分岐地点候補と選択されたカテゴリのＲＴＴを以て接続すると推定する。Ｓ１８０の処理によって、分岐地点候補は分岐地点と推定される。
【００４５】
図２０で示す例では、観測装置Ｅ、Ｆは、カテゴリＩＤ「Ｃ１」「Ｃ２」の両方にＲＴＴが存在するため、分岐地点候補とは接続していないと見なす。なお、ターゲット観測装置はＡであるため、比較処理から外す。その結果、分岐地点候補として分岐地点Ｙ１が推定される。別形態としては、比較するＲＴＴの差が所定の閾値以内である場合、該当する観測装置は分岐地点候補と接続していると見なす処理を行っても良い。
【００４６】
次に、Ｓ１４０で接続状態推定手段１５０は、図２２で示すような分岐地点リストに、上記処理結果を記入する。例えば、Ｓ１４０で接続状態推定手段１５０は、図２０で示すカテゴリ代表リストに基づき図２２の１行目のデータを記入する。図２２の１行目では、分岐地点ＩＤ「Ｙ１」には観測装置Ａ、Ｂ、Ｃ、ＤがＲＴＴ１０、１２、１５、１２を以てそれぞれ接続すると推定されていることを示す。
【００４７】
Ｓ１５０で接続状態推定装置１００は、図１２で示すような観測装置リストにおいて、Ｓ１４０で分岐地点と接続済みとなった観測装置の欄に「接続済」と記入する。図１２では、ターゲット観測装置を観測装置Ａとして分岐地点を推定した結果、観測装置Ａ、Ｂ、Ｃ、Ｄが既に接続済みであることを示している。
【００４８】
Ｓ１６０で接続状態推定装置１００は、図１２で示すような観測装置リストを参照して、全ての観測装置が「接続済」と記入されるまで、Ｓ１１０からＳ１５０の処理を繰り返す。また、図１４、図１９、図２１、図２２の２行目（分岐地点ＩＤ「Ｙ２」）では、ターゲット観測装置として観測装置Ｅを選択した場合における各段階の処理結果を示している。ここで、図１４は図１３に対応し、図１９は図１８に対応し、図２１は図２０に対応している。また、図２２の２行目は、接続関係推定手段１５０によって、観測装置Ｅ、Ｆは、岐地点ＩＤ「Ｙ２」である分岐地点に、ＲＴＴ１０、８を以てそれぞれ接続すると推定されていることを示す。
【００４９】
（４）分岐地点の接続
図２２を用いて、各分岐地点を接続する処理について説明する。この処理により、Ｓ１０からＳ３０において推定した各分岐地点を接続し、また、必要に応じて再度Ｓ１０からＳ３０の分岐地点を推定する処理を繰り返し行う。
【００５０】
Ｓ４０で接続関係推定装置１００は、Ｓ１０からＳ３０において推定された分岐地点の数を確認する、つまり、図２２で示す分岐地点リスト内の分岐地点ＩＤの数を数える。ここで、分岐地点の数が１つである場合（Ｓ４０でＹｅｓ）、接続関係推定装置１００は、全ての観測装置は当該分岐地点において接続され、図２２の分岐地点リスト内における各装置のＲＴＴを以て当該分岐地点と接続されていると推定する。このように、開示の接続状態推定装置１００では、複数の装置を備える通信ネットワークにおいて、装置間のＲＴＴ等ネットワーク距離を利用し、経験や人手によらず自動的に装置間の接続状態を推定することができる。
【００５１】
一方、Ｓ４０において分岐地点の数が２つ以上である場合（Ｓ４０でＮｏ）、Ｓ５０で接続関係推定装置１００は、Ｓ１０からＳ３０において推定した分岐地点相互間のＲＴＴを算出する。ここで分岐地点相互間のＲＴＴは、分岐地点を通過する２つの観測装置間のＲＴＴから、それぞれの観測装置・分岐地点間のＲＴＴを減じることで算出することができる。例えば、図２２で示す例では、Ｙ１・Ｙ２間のＲＴＴは、「Ａ・Ｅ間のＲＴＴ−Ｙ１・Ａ間のＲＴＴ−Ｙ２・Ｅ間のＲＴＴ」、「Ｂ・Ｅ間のＲＴＴ−Ｙ１・Ｂ間のＲＴＴ−Ｙ２・Ｅ間のＲＴＴ」などとなる。同一の分岐地点間のＲＴＴは、算出に用いる観測装置の選び方で複数算出されるため、この複数算出された値の平均値、最小値、最大値等の何れかを採用する。
【００５２】
ここで、図２３に、図２２で示す最終的に得られた観測装置および分岐地点相互間のＲＴＴを示す。なお、図２３で示すＹ１・Ｙ２間のＲＴＴは、「Ａ・Ｅ間のＲＴＴ−Ｙ１・Ａ間のＲＴＴ−Ｙ２・Ｅ間のＲＴＴ」の式により算出したものである。
【００５３】
Ｓ６０で分岐地点の数が２つである場合（Ｓ６０でＹｅｓ）、接続関係推定装置１００は、当該２つの分岐地点はＳ５０で算出したＲＴＴを以て接続していると推定する。そして、接続関係推定装置１００は、各観測装置は当該１つ又は２つの分岐地点を介して、相互に接続していると推定する。開示の接続状態推定装置１００では、複数の装置を備える通信ネットワークにおいて、経験や人手によらず自動的に、２つの分岐地点を介した装置間の接続状態を推定することができる。
【００５４】
Ｓ６０で分岐地点の数が３つ以上である場合（Ｓ６０でＮｏ）、接続関係推定装置１００は、当該３つ以上の分岐地点それぞれを観測装置と見なしてＳ２０からＳ５０の処理を再度実行し、これら分岐地点の接続状態を推定する。Ｓ１０から５０の処理によって、分岐地点・観測装置間の接続状態が推定されているため、当該再実行によって、通信ネットワーク全体での接続状態が推定される。開示の接続状態推定装置では、複数の装置を備える通信ネットワークにおいて、経験や人手によらず自動的に、装置間の複雑な接続状態を推定することができる。
【００５５】
（５）グルーピング手段１３０が使用する融合閾値の算出
Ｓ２１０でグルーピング手段１３０が使用する融合閾値Ｔｈ−Ｕは、接続状態推定装置１００の処理対象となる通信ネットワークの大きさ、つまり、観測装置間のＲＴＴレンジに応じて適切に設定される必要がある。そして、接続状態推定装置１００では、ユーザが適宜融合閾値を設定するのではなく、以下で説明する方法により自動的に融合閾値を設定することで、ユーザの手間を軽減することができる。
【００５６】
融合閾値を自動的に設定するための閾値算出手段１６０は、観測装置間ＲＴＴの平均値をＭで除した値や該平均値に１０−Ｍを乗じた値を算出し、算出した値を融合閾値Ｔｈ−Ｕとする。ここで、Ｍは精度を表す数値であり、ユーザは当該Ｍを予め指定する。また、このＭは、ユーザにより１度設定された後は変更する必要は無い。これにより、接続状態推定装置１００を複数の通信ネットワークに適用する場合等、ユーザは都度パラメータ（融合閾値Ｔｈ−Ｕ）を設定する必要が無い。
【００５７】
以上、本発明の実施の形態について詳述したが、本発明は係る特定の実施の形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲において、種々の変形・変更が可能である。
（付記１）
コンピュータに、
装置間距離取得手段が、複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得するステップと、
候補距離算出手段が、前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出するステップと、
グルーピング手段が、一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うステップと、
代表値算出手段が、前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出するステップと、
接続状態推定手段が、前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なすステップと、実行させるための接続状態推定プログラム。
（付記２）
前記分岐地点が２つ以上存在する場合、該２つ以上の分岐地点は相互に接続すると見なし、さらに、前記装置間の前記ネットワーク距離及び該分岐地点と該装置との前記ネットワーク距離に基づき、該分岐地点間の該ネットワーク距離を算出させることを特徴とする付記１に記載の接続状態推定プログラム。
（付記３）
前記分岐地点が３つ以上存在する場合、該各分岐地点を前記装置と見なして、前記候補距離算出手段、前記グルーピング手段、前記代表値算出手段、及び前記ネットワーク接続状態推定手段による各ステップを実行させることを特徴とする付記２に記載の接続状態推定プログラム。
（付記４）
前記グルーピング手段が、前記一の装置と各分岐地点候補との前記ネットワーク距離の差が所定の閾値以下となる該分岐地点候補を、同一グループに分類する場合、
閾値算出手段が、前記装置間距離取得手段により取得される前記ネットワーク距離の平均値に基づき、前記所定の閾値を算出するステップをさらに有することを特徴とする付記１乃至３の何れか一に記載の接続状態推定プログラム。
（付記５）
複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得する装置間距離取得手段と、
前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出する候補距離算出手段と、
一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うグルーピング手段と、
前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出する代表値算出手段と、
前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なす接続状態推定手段と、を有することを特徴とする接続状態推定装置。
（付記６）
前記分岐地点が２つ以上存在する場合、該２つ以上の分岐地点は相互に接続すると見なし、さらに、前記装置間の前記ネットワーク距離及び該分岐地点と該装置との前記ネットワーク距離に基づき、該分岐地点間の該ネットワーク距離を算出することを特徴とする付記５に記載の接続状態推定装置。
（付記７）
前記分岐地点が３つ以上存在する場合、該各分岐地点を前記装置と見なして、前記候補距離算出手段、前記グルーピング手段、前記代表値算出手段、及び前記ネットワーク接続状態推定手段による各処理を実行することを特徴とする付記６に記載の接続状態推定装置。
（付記８）
前記グルーピング手段は、前記一の装置と各分岐地点候補との前記ネットワーク距離の差が所定の閾値以下となる該分岐地点候補を、同一グループに分類する場合、
前記装置間距離取得手段により取得される前記ネットワーク距離の平均値に基づき、前記所定の閾値を算出する閾値算出手段を有することを特徴とする付記５乃至７の何れか一に記載の接続状態推定装置。
（付記９）
装置間距離取得手段が、複数の装置を備える通信ネットワークにおける該各装置間のネットワーク距離を取得するステップと、
候補距離算出手段が、前記複数の装置から抽出した３つの装置が接続する分岐地点候補を仮定し、仮定した該分岐地点候補と該抽出した３つの装置との前記ネットワーク距離をそれぞれ算出するステップと、
グルーピング手段が、一の前記装置に接続すると仮定される全ての前記分岐地点候補について、該一の装置と該各分岐地点候補との前記ネットワーク距離に基づき、グループ分けを行うステップと、
代表値算出手段が、前記グルーピング手段により分けられたグループ毎に、かつ、一の該グループに属する前記分岐地点候補に接続すると仮定される前記装置毎に、前記候補距離算出手段により算出された前記ネットワーク距離の代表値を算出するステップと、
接続状態推定手段が、前記装置毎の前記代表値の算出結果に基づき、前記全ての分岐地点候補のうち何れかに接続すると仮定される前記装置の中から１つ以上の前記装置及び該各装置に関する前記代表値を選択し、選択された該各装置に関する代表値を、該選択された各装置と選択された全装置が接続する分岐地点との前記ネットワーク距離と見なすステップと、を有することを特徴とする接続状態推定方法。
（付記１０）
前記分岐地点が２つ以上存在する場合、該２つ以上の分岐地点は相互に接続すると見なし、さらに、前記装置間の前記ネットワーク距離及び該分岐地点と該装置との前記ネットワーク距離に基づき、該分岐地点間の該ネットワーク距離を算出させることを特徴とする付記９に記載の接続状態推定方法。
（付記１１）
前記分岐地点が３つ以上存在する場合、該各分岐地点を前記装置と見なして、前記候補距離算出手段、前記グルーピング手段、前記代表値算出手段、及び前記ネットワーク接続状態推定手段による各ステップを実行させることを特徴とする付記１０に記載の接続状態推定方法。
（付記１２）
前記グルーピング手段が、前記一の装置と各分岐地点候補との前記ネットワーク距離の差が所定の閾値以下となる該分岐地点候補を、同一グループに分類する場合、
閾値算出手段が、前記装置間距離取得手段により取得される前記ネットワーク距離の平均値に基づき、前記所定の閾値を算出するステップをさらに有することを特徴とする付記９乃至１１の何れか一に記載の接続状態推定方法。
【符号の説明】
【００５８】
１００  接続状態推定装置
１１０  装置間距離取得手段
１２０  候補距離算出手段
１３０  グルーピング手段
１４０  代表値算出手段
１５０  接続状態推定手段
１６０  閾値算出手段
１７０  ＲＴＴ情報
１８０  分岐地点推定結果
２００  観測結果統合装置
【図１】
2010233097.tif 000003
【図２】
2010233097.tif 000004
【図３】
2010233097.tif 000005
【図４】
2010233097.tif 000006
【図５】
2010233097.tif 000007
【図６】
2010233097.tif 000008
【図７】
2010233097.tif 000009
【図８】
2010233097.tif 000010
【図９】
2010233097.tif 000011
【図１０】
2010233097.tif 000012
【図１１】
2010233097.tif 000013
【図１２】
2010233097.tif 000014
【図１３】
2010233097.tif 000015
【図１４】
2010233097.tif 000016
【図１５】
2010233097.tif 000017
【図１６】
2010233097.tif 000018
【図１７】
2010233097.tif 000019
【図１８】
2010233097.tif 000020
【図１９】
2010233097.tif 000021
【図２０】
2010233097.tif 000022
【図２１】
2010233097.tif 000023
【図２２】
2010233097.tif 000024
【図２３】
2010233097.tif 000025