(57)【要約】【課題】Ｐ２Ｐネットワークのような大規模なネットワークシステムに属するノードの規模を推定することを可能にする。【解決手段】同じネットワーク５上の複数の地点に設置された測定ノード１，２，３で、同ネットワークに属するノードの識別情報を収集し、また、他の測定ノードの識別情報も収集し、上記のノード識別情報と他の測定ノード識別情報を突合させて、他の測定ノードを発見するまでの時間を計測し、ネットワークサービスシステム５に属するノードの総数を推定する。【選択図】図１
2006324957.tif 000002
【特許請求の範囲】
【請求項１】
同一のネットワークサービスシステムに属するノードの総数を算出するネットワーク規模推定システムであって、
同一ネットワークサービスシステム上の複数地点に設置された各々の測定ノードで、該ネットワークシステムに属するノードの識別情報を収集するノード識別情報収集手段と、
該ノード識別情報収集手段により収集された他の測定ノードの識別情報を取得して、該情報を記憶する測定ノード識別情報取得記憶手段と、
該ノード識別情報収集手段により収集されたノード識別情報と、該測定ノード識別情報記憶手段により記憶されている他の測定ノードの識別情報とを突合させることにより、他の測定ノードを発見するまでの時間を計測するノード発見時間計測手段と、
該ノード発見時間計測手段により計測した時間から、該ネットワークサービスシステムに属するノードの総数を求めるノード数推定手段と、
該ノード数推定手段により求めたノードの総数を出力する出力手段と
を有することを特徴とする複数地点測定を用いたネットワーク規模推定システム。
【請求項２】
請求項１に記載の複数地点測定を用いたネットワーク規模推定システムにおいて、
前記ノード発見時間計測手段においては、測定ノードの総数をｎ（≧１）とし、測定ノードｉ（１≦ｉ≦ｎ）が他の測定ノードのうちのいずれか１つを発見するまでの測定時間をｔｉ（秒）とし、測定ノードｉがノード識別情報を収集する速度をｖｉ（個／秒）としたとき、測定ノードｉが他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）ｘｉは、ｘｉ＝ｔｉ×ｖｉであり、
ある測定ノードｉが他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）の平均ｘは、
【数１】
2006324957.tif 000012
であることを特徴とする複数地点測定を用いたネットワーク規模推定システム。
【請求項３】
請求項１に記載の複数地点測定を用いたネットワーク規模推定システムにおいて、
前記ノード数推定手段においては、測定ノードの総数をｎ（≧１）とし、ある測定ノードｉが他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）の平均をｘとしたとき、前記ネットワークサービスシステムに属するノードの総数Ｎは、
【数２】
2006324957.tif 000013
で求めることを特徴とする複数地点測定を用いたネットワーク規模推定システム。
【請求項４】
同一のネットワークサービスシステムに属するノードの総数を算出するネットワーク規模推定方法であって、
ノード情報収集手段は、他のノードに対してアドレスを送信して、該送信に対する回答を受信することにより、該ノードとの通信を確認し、
ノード数推定手段は、確認された該ノード情報収集手段で収集された情報を用いて、演算回路により、他のノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数の平均値を算出し、
該演算回路により、該ノード識別情報の総数の平均値を用いて総ノード数Ｎの値を算出することで、推定を行い、
算出結果を表示装置、プリンタあるいは外部記憶装置のいずれかに出力する
ことを特徴とする複数地点測定を用いたネットワーク規模推定方法。
【請求項５】
同一のネットワークサービスシステムに属するノードの総数を算出するネットワーク規模推定用プログラムであって、
ネットワーク規模推定システムのコンピュータに、ノード情報収集手段の各々が、他のノードに対してアドレスを送信して、該送信に対する回答を受信することにより、該ノードとの通信を確認する手順、ノード数推定手段が、確認された該ノード情報収集手段で収集された情報を用いて、演算回路により、他のノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数の平均値を算出する手順、該演算回路により、該ノード識別情報の総数の平均値を用いて総ノード数Ｎの値を算出し、推定する手順、算出結果を表示装置、プリンタあるいは外部記憶装置のいずれかに出力する手順を、それぞれ実行させるためのネットワーク規模推定用プログラム。
【請求項６】
請求項５に記載のネットワーク規模推定用プログラムを記録したコンピュータ読み出し可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｐ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）等のように、膨大な規模のサービスが提供されるネットワークシステムにおけるノード規模の推定を効率的に行うためのシステムと方法に関し、特に、複数地点を測定することによりノードの識別情報を収集し、それらを突合わせて他の測定ノードの発見までの時間を計測し、ノードの総数を推定する複数地点測定を用いたネットワーク規模推定システムおよびその方法、ならびにそのプログラムとプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
インターネット環境の普及に伴って、その上で動作する様々なネットワークサービスを提供するネットワークサービスシステムが登場している。従来、大きな規模に達する代表的なネットワークシステムとして、『Ｐ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）』システムがあるが、例えばこのシステムにおける全ノードの情報を得ることは、その規模の膨大さのために不可能である。
【０００３】
亀井聡、内田真人、“Ｐ２Ｐネットワークの規模推定”（非特許文献１参照）では、異なる測定手段Ａ，Ｂを用いて収集したノード識別情報の重なりを用いて、Ｐ２Ｐシステムのノード総数を推定する技術が提案されている。すなわち、Ｐ２Ｐシステムの総ノード数をＮ、測定手段Ａが捕捉したノード数をＮＡ、測定手段Ｂが捕捉したノード数をＮＢ、測定手段Ａと測定手段Ｂが共通に捕捉したノード数をＮＡ，Ｂとした時、測定手段Ａ，Ｂが捕捉したノード集合が統計的に独立であると仮定すると、次式が成り立つ。
【０００４】
【数１】
2006324957.tif 000003
従って、上式（１）より総ノード数は、次式で推定される。
【０００５】
【数２】
2006324957.tif 000004
なお、上記非特許文献１では、ＳｔｅｖｅＬａｗｒｅｎｃｅ  ａｎｄ  Ｃ．Ｌｅｅ  Ｇｉｌｅｓ，Ｓｅａｒｃｈｉｎｇ  ｔｈｅ  Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ，ＳＣＩＥＮＣＥ，ＶＯＬ．２８０（非特許文献２参照）の手法を拡張し、参加ノードの生存確認を行った上で、総ノード数の推定を行っている。
【０００６】
【非特許文献１】亀井聡、内田真人、“Ｐ２Ｐネットワークの規模推定”電子情報通信学会  情報ネットワーク研究会，ＩＮ２００３−２０４，２００４年２月
【非特許文献２】ＳｔｅｖｅＬａｗｒｅｎｃｅ  ａｎｄ  Ｃ．Ｌｅｅ  Ｇｉｌｅｓ，Ｓｅａｒｃｈｉｎｇ  ｔｈｅ  Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ，ＳＣＩＥＮＣＥ，ＶＯＬ．２８０，ＰＰ．９８−１００，３Ａｐｒｉｌ  １９９８
【非特許文献３】亀井，森，大井，“Ｐ２Ｐファイル共有の実態と課題〜トラヒック測定・設定・制御・管理法の確立に向けて〜”信学技報ＣＱ２００３〜０７，２００３．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述のように、従来の技術の問題点は、測定手段Ａ，Ｂが捕捉したノード集合が統計的に独立であるという仮定が成り立たない場合には、上記非特許文献１の技術を適用することができないという点である。何故ならば、この仮定が成り立たない場合にはＮＡ，Ｂの値が大きくなるため、上式（２）を用いた総ノード数の推定値が過小評価されてしまうためである。
【０００８】
（目的）
本発明の目的は、上記の問題点を抱える上記非特許文献１の技術を用いることなく、Ｐ２Ｐネットワークのような大規模なネットワークシステムに属するノードの規模を推定することが可能な複数地点測定を用いたネットワーク規模推定システムおよびその方法、ならびにそのプログラムとプログラムを記録した記録媒体を提供することにある。
【課題を解決するための手段】
【０００９】
本発明により複数地点測定を用いてネットワーク規模を推定する方法は、膨大な規模のサービスが提供されるネットワークシステムのノード規模の推定方法であって、同じネットワーク上の複数の地点に設置された測定ノードで同ネットワークに属するノードの識別情報を収集し、また他の測定ノードの識別情報も収集し、上記のノード識別情報と他の測定ノード識別情報を突合させて他の測定ノードを発見するまでの時間を計測し、ネットワークサービスシステムに属するノードの総数を推定することを特徴としている。
これにより、測定手段に対する特別な仮定を設けることなく、総ノード数を推定することが可能になる。
【００１０】
また、本発明による複数地点測定を用いたネットワーク規模推定システムは、同じネットワークサービスシステムに属するノードの総数を算出するネットワーク規模推定システムであって、下記の各手段を具備することを特徴としている。
（イ）同じネットワークサービスシステム上の複数地点に設置された各々の測定ノードにおいて、該ネットワークサービスシステムに属するノードの識別情報を収集するノード識別情報収集手段と、（ロ）各々の測定ノードにおいて、他の測定ノードの識別情報を取得し記憶する測定ノード識別情報取得記憶手段と、（ハ）各々の測定ノードにおいて、上記ノード識別情報収集手段によりノード識別情報を収集し、その識別情報と測定ノード識別情報取得記憶手段により記憶されている他の測定ノードの識別情報を突合させることにより、他の測定ノードを発見するまでの時間を計測するノード発見時間計測手段と、（ニ）上記ノード発見時間計測手段で計測した時間から、該ネットワークサービスシステムに属するノードの総数を求めるノード数推定手段と、（ホ）上記ノード数推定手段で求めたノードの総数を出力する手段。
【発明の効果】
【００１１】
本発明によれば、上記非特許文献１における仮定（測定手段Ａ，Ｂが捕捉したノード集合が統計的に独立である）を設けることなく、ネットワークサービスシステムに属するノードの総数を推定することが可能になる。その結果として、総ノード数の推定値が過小評価されることなく、適切な推定値を得ることができる。なお、自律分散オーバーレイネットワークの下位レイヤに当るＩＰネットワークの網設計に際して、このようなサービス参加ノードの規模を把握することは重要であるため、自律分散システム開発の観点からも、本発明によるネットワーク規模の把握は有用である。
【発明を実施するための最良の形態】
【００１２】
（原理）
本発明においては、以下の関係式が成り立つことに着目する。
まず、測定ノードの総数をｎ（≧１）とし、このネットワークサービスシステムに属するノードの総数をＮとする。また、また、測定ノードｉ（１≦ｉ≦ｎ）が他の測定ノードのうちのいずれか１つを発見するまでの測定時間をｔｉ（秒）とし、測定ノードｉがノード識別情報を収集する速度をｖｉ（個／秒）とする。このとき、測定ノードｉが他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）は、ｘｉ＝ｔｉ×ｖｉとなる。測定回数ｘｉの従う確率分布は、下式となる。
【００１３】
【数３】
2006324957.tif 000005
また、期待値は、下式となる。
【００１４】
【数４】
2006324957.tif 000006
ただし、
【００１５】
【数５】
2006324957.tif 000007
である。式（４），式（５）より、下式が成り立つ。
【００１６】
【数６】
2006324957.tif 000008
一方、ある測定ノードが他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）の平均は、下式となる。
【００１７】
【数７】
2006324957.tif 000009
従って、式（６）のＥ〔Ｘ〕を
【００１８】
【数８】
2006324957.tif 000010
に置き換えることで、以下の関係式を得る。
【００１９】
【数９】
2006324957.tif 000011
本発明においては、上記式（８）を用いてこのネットワークシステムに属するノードの総数を算出する。
【００２０】
（実施例）
以下、本発明の実施例を、図面により詳細に説明する。
図１は、本発明の一実施例に係るネットワーク規模推定システムの構成図である。
本実施例に係るネットワーク規模推定システムは、ノード情報収集装置（Ａ）１、（Ｂ）２、（Ｃ）３およびノード数推定部４から構成される。例えば、インターネット上のＰ２Ｐサービスシステム等の測定対象となるシステム５におけるノード総数を、これらの収集装置１，２，３と推定部４により算出して、当該ネットワークサービスシステム５の規模推定を行う。
【００２１】
なお、ノード情報収集装置１，２，３、ノード数推定部４のそれぞれは、ＣＰＵや主メモリ、表示装置、入力装置、外部記憶装置からなるコンピュータシステムで実現され、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記録媒体に記録されたプログラムや、データを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込み、ＣＰＵで処理することにより、それぞれの機能を実行する。
【００２２】
ノード情報収集装置１，２，３は、それぞれ測定対象となるネットワークサービスシステム５に属する通信先ノードの識別情報を収集し、ノード数推定部４は、ノード情報収集装置１，２，３が収集した情報を用いて、ネットワークサービスシステム５全体に属するノード数の推定値を算出する。これにより、複数地点における測定結果からネットワークの全体規模の推定を行うことができる。
【００２３】
また、ノード情報収集装置１，２，３は、アプリケーションを実際に動作させることにより、システム５へ参加しているノードの情報を収集する装置であり、図１の例では、このような装置を３台配置して動作させ、サービス種別毎に独立して各ノードの識別情報の収集を行う。
なお、このようなノード情報（サービス種別、ノード識別情報）の収集技術については、例えば、亀井，森，大井，“Ｐ２Ｐファイル共有の実態と課題〜トラヒック測定・設定・制御・管理法の確立に向けて〜”信学技報ＣＱ２００３〜０７，２００３．（非特許文献３参照）に記載されている。これによれば、論理網に接続されたアプリケーションノードにおいて、ＩＰレイヤでの測定を行い、通信相手のＩＰアドレス（ノード識別情報）と利用ポート（サービス種別）を収集する技術を用いている。
【００２４】
ノード情報収集装置１，２，３で収集されたノード情報（サービス種別、ノード識別情報）は、ノード数推定部４と共有される。
ノード数推定部４では、まず、ノード情報収集装置１，２，３で収集されたノード情報を用いて測定ノードが互いの存在を発見するまでの測定回数の平均値ｘを求め、この値を用いて総ノード数Ｎを前式（８）により算出し、推定値とする。ただし、本実施例の場合、ｎ＝３である。
【００２５】
図３は、図１を詳細に示した構成図である。
ノード情報収集装置１，２，３で収集された測定ノード識別情報はそれぞれ測定ノード識別情報記憶装置６に蓄積される。また、ノード情報収集装置１，２，３は、それぞれ他の測定ノードのうちのいずれか１つを発見するまでの時間を計測するとき、ノード発見時間計測装置７を利用することにより計測する。
ノード数推定部４は、測定ノード識別情報記憶装置６からノード情報収集装置の総数ｎを受け取るとともに、ノード発見時間計測装置７からノード情報収集装置１，２，３が他の測定ノードのうちのいずれか１つを発見するまでに収集したノード識別情報の総数（測定回数）の平均値を受け取り、それらを用いて、ネットワークサービスシステムに属するノードの総数Ｎ＝ｎ×ｘを計算する。計算結果は、出力部８により表示装置、プリンタ、あるいは外部記憶装置のいずれかに出力される。
【００２６】
図２は、本発明の一実施例に係るネットワーク規模推定方法の処理手順を示すフローチャートである。
まず、ノード情報収集装置１，２，３において、アドレスＸの通信を確認し（ステップＳ１）、確認されたアドレス情報を測定された装置名と共に順番に記憶装置に蓄積する（ステップＳ２）。
次に、ノード数推定部４において、ノード情報収集装置１，２，３で収集された情報（サービス種別、ノード識別情報）を用いて前式（８）のｘの値を計算し（ステップＳ３）。この値を用いて総ノード数Ｎの値を推定する（ステップＳ４）。この結果は、表示装置やプリンタ、もしくは外部記憶装置等に出力される（ステップＳ５）。
【００２７】
（具体例）
本実施例を具体的な数値を用いて説明する。
各ノード情報収集装置１，２，３は、ステップＳ１において、あるアドレスＸを持つ装置との通信を確認した場合には（Ｙｅｓ）、その装置のアドレスを記憶する（ステップＳ２）。また、どの装置との通信も確認できない場合には（Ｎｏ）、通信を確認するまで待機する。
【００２８】
一方、ステップＳ３では、ステップＳ２で記憶したアドレス集合を用いて、他の測定ノードを初めて発見するまでの測定回数を求める。例えば、ノード情報収集装置（Ａ）１が初めて発見した測定ノードがノード情報収集装置（Ｂ）２であり、それまでの測定回数が１０００であるとする。また、ノード情報収集装置（Ｂ）２が初めて発見した測定ノードがノード情報収集装置（Ｃ）３であり、それまでの測定回数が２０００であるとする。
また、ノード情報収集装置（Ｃ）３が初めて発見した測定ノードがノード情報収集装置（Ａ）１であり、それまでの測定回数が３０００であるとする。
【００２９】
このとき、ｘの値は、（１０００＋２０００＋３０００）／３＝２０００となる。今、測定ノードの総数はｎ＝３であるから、これらのｘ，ｎの値を前式（７），（８）に代入して計算することにより、ネットワークサービスシステム５に属するノードの総数Ｎは、３×２０００＝６０００（台）となる。
【００３０】
以上、図１〜図２を用いて説明したように、本実施例では、３点において同じサービスネットワークシステムに属するノードの情報を取得し、その推定結果を利用した結果、参加ノード数の推定を行うことが可能となる。
【００３１】
なお、本発明は、図１、図２を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々に変更が可能である。
また、本発明では、光ディスクを記録媒体として用い、プログラムのインストールを行う例を示しているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでもよい。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでもよい。
【図面の簡単な説明】
【００３２】
【図１】本発明の一実施例に係るネットワーク規模推定システムの構成図である。
【図２】本発明の一実施例に係るネットワーク規模推定方法の動作フローチャートである。
【図３】図１における詳細なシステム構成図である。
【符号の説明】
【００３３】
１，２，３：ノード情報収集装置（Ａ），（Ｂ），（Ｃ）
４：ノード数推定部
５：測定対象となるシステム
６：測定ノード識別情報記憶装置
７：ノード発見時間計測装置
８：出力部
【図１】
2006324957.tif 000014
【図２】
2006324957.tif 000015
【図３】
2006324957.tif 000016