(57)【要約】【課題】Ｇｎｕｔｅｌｌａ型のＰ２Ｐネットワークにおいて、時々刻々変化するネットワークトポロジを再現するために、ネットワークを構成する端末の接続先端末数の分布を効率よくかつ容易に推定する。【解決手段】所定期間に自端末を通過するホップ値が記録されたパケットを受信する手段と、受信したパケットに記録されているホップ値ごとにパケット数を集計する手段と、ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手段とを備える。【選択図】        図１
2004187217.tif 000002
【特許請求の範囲】
【請求項１】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信し、
受信したパケットに記録されているホップ値ごとにパケット数を集計し、
ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、
前記パケット数比ｒｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする
ことを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法。
【請求項２】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信し、
前記所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計し、
区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、
前記パケット数比ｒｉ，ｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする
ことを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法。
【請求項３】
前記ホップ値が記録されたパケットは、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットである
ことを特徴とする請求項１または請求項２に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法。
【請求項４】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信する手段と、
受信したパケットに記録されているホップ値ごとにパケット数を集計する手段と、
ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手段と
を備えたことを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定装置。
【請求項５】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信する手段と、
前記所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計する手段と、
区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、そのパケット数比ｒｉ，ｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手段と
を備えたことを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定装置。
【請求項６】
前記ホップ値が記録されたパケットを受信する手段は、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを受信する構成である
ことを特徴とする請求項４または請求項５に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定装置。
【請求項７】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信する手順と、
受信したパケットに記録されているホップ値ごとにパケット数を集計する手順と、
ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手順と
を有することを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定するプログラム。
【請求項８】
Ｐ２Ｐネットワークに接続している端末が、所定期間にその端末を通過するホップ値が記録されたパケットを受信する手順と、
前記所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計する手順と、
区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、そのパケット数比ｒｉ，ｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手順と
を有することを特徴とするＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定するプログラム。
【請求項９】
前記ホップ値が記録されたパケットを受信する手順は、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを受信する
ことを特徴とする請求項７または請求項８に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定するプログラム。
【請求項１０】
請求項７に記載の各手段を機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
請求項８に記載の各手段を機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、Ｐ２Ｐ（ピア・ツー・ピア）ネットワークのトポロジを推定するために、Ｐ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法、推定装置、プログラムおよびそのプログラムを記録した記録媒体に関する。なお、ネットワークトポロジは、例えばＰ２Ｐネットワークにおけるトラヒック制御法をシミュレーション評価する際に必要となるものである。
【０００２】
【従来の技術】
Ｐ２Ｐネットワークは、従来のクライアント・サーバ型とは異なり、専用のサーバを用いず、ネットワーク上の端末自体にサーバ機能を持たせてコンピュータ資源やサービスを端末間で直接共有することが可能になっている（非特許文献１）。
【０００３】
例えば、端末間で音楽などのファイルを交換するためのＰ２Ｐネットワークを構成するプログラムとして、従来より「Ｇｎｕｔｅｌｌａ（グニューテラ）」と呼ばれるソフトウェアを用いたネットワークが知られている。Ｇｎｕｔｅｌｌａのネットワークは、ネットワークへの接続をサポートするサーバや、ファイル検索機能を備えたサーバを持たない純粋なＰ２Ｐネットワークである。このＧｎｕｔｅｌｌａのＰ２Ｐネットワークに接続している各端末は、ネットワークへの接続をサポートする機能やファイルの検索機能を備えており、サーバントと呼ばれる。
【０００４】
各サーバントがＧｎｕｔｅｌｌａのＰ２Ｐネットワークへ接続する手順は次の通りである。
【０００５】
（１）  他のサーバントへ接続し、Ｐｉｎｇパケットを送信する。
（２）  Ｐｉｎｇパケットを受信したサーバントは、ＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）  値が１より大きく、かつまだ受け取ったことがないＧＵＩＤ（Ｇｌｏｂａｌｌｙ  Ｕｎｉｑｕｅ  Ｉｄｅｎｔｉｆｉｅｒ）  をもつパケットならば、ＴＴＬ値を１つ減らし（このとき、ホップ値を１つ増やす）、さらに別のサーバントへ転送する。
【０００６】
（３）  Ｐｉｎｇパケットを受信したサーバントは、まだ受け取ったことがないＧＵＩＤをもつパケットならば、ＩＰアドレス、接続を受け付けるためのＴＣＰポート番号、公開しているファイルの総数などの情報を記録したＰｏｎｇパケットをＰｉｎｇパケットの送信元へ返す。
【０００７】
（４）  Ｐｏｎｇパケットを受信したサーバントは、対応するＰｉｎｇパケットの送信元へそのＰｏｎｇパケットを返す。
【０００８】
（５）  Ｐｉｎｇパケットを送信し、それに対応するＰｏｎｇパケットを受信したサーバントは、指定された数のサーバントの情報が得られたならば、それらのサーバントに接続し、指定された数のサーバントの情報が得られなければ、さらに別のサーバントを見つけて以上のシーケンスを繰り返す。
【０００９】
また、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークにおけるファイル検索の手順は次の通りである。
【００１０】
（１）  ファイル検索元のサーバントは、直接接続しているサーバントに対して、Ｑｕｅｒｙ（問い合わせ）  パケットを送信する。Ｑｕｅｒｙパケットのペイロードには、「この検索要求に応じるサーバントの最低通信速度」や「検索キーワード」などの検索条件が記録される。
【００１１】
（２）  Ｑｕｅｒｙパケットを受信したサーバントは、Ｑｕｅｒｙパケットのヘッダに記録されているＴＴＬ値を１つ減らし（このとき、ホップ値を１つ増やす）、ＴＴＬ値が１より大きければ、自サーバントに接続している全てのサーバント（ただし、Ｑｕｅｒｙパケットを送信したサーバントは除く）へＱｕｅｒｙパケットをそれぞれ転送する。
【００１２】
（３）  転送されたＱｕｅｒｙパケットの条件に合致するファイルをもっているサーバントはＱｕｅｒｙＨｉｔパケットを返し、もっていないサーバントはＱｕｅｒｙパケットをさらに転送する。
【００１３】
（４）  ＱｕｅｒｙＨｉｔパケットは、Ｑｕｅｒｙパケットが転送されてきた経路を逆順にたどって発信元に戻っていく。ＱｕｅｒｙＨｉｔパケットのペイロードには、条件に合ったファイルの総数、ＱｕｅｒｙＨｉｔしたサーバントの各種情報（待ち受けＴＣＰポート番号，ＩＰアドレス，接続通信速度，条件に合ったファイルの名前とサイズとファイルインデックス（どのファイルであるかを示すためにサーバント側で付けている一連の番号），ＧＵＩＤ）が記録されている。
【００１４】
ところで、シミュレーションによりネットワークの通信性能や通信品質を評価することがある。このとき、実際に運用されているネットワークのトポロジを再現するために、ネットワークを構成する端末の接続先端末数の分布を推定することが必要になる。従来から、ネットワークトポロジはＰｏｗｅｒ  Ｌａｗ  に従っている、すなわち接続先端末数の分布はパレート分布であることが知られているが、このパレート分布の分布形を定めるにはデータの収集が必要になる。
【００１５】
従来は、ネットワークトポロジに関する詳細なデータを収集するために、ネットワークを構成する端末に対して、どの端末と接続しているかなどの問い合わせを行う必要があった。例えば、非特許文献２には、上記のネットワーク接続時のプロトコルに着目し、所定のサーバントからＴＴＬ値が２のＰｉｎｇパケットを送信し、それに対するＰｏｎｇパケットを受信することにより、ネットワークトポロジを推定する手法が提案されている。
【００１６】
【非特許文献１】
伊藤直樹、「Ｐ２Ｐコンピューティング〜技術解説とアプリケーション」、ソフト・リサーチ・センター、２００１
【非特許文献２】
Ｍ．Ｊｏｖａｎｏｖｉｃ，  Ｆ．Ｓ．Ａｎｎｅｘｓｔｅｉｎ，  ａｎｄ  Ｋ．Ａ．Ｂｅｒｍａｎ，  ”Ｓｃａｌａｂｉｌｉｔｙ  Ｉｓｓｕｅｓ  ｉｎ  Ｌａｒｇｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｎｅｔｗｏｒｋｓ−Ａ  Ｃａｓｅ  Ｓｔｕｄｙ  ｏｆ  Ｇｎｕｔｅｌｌａ”，  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃｉｎｃｉｎｎａｔｉ，  ２００１
【００１７】
【発明が解決しようとする課題】
しかし、各サーバントが自律分散的にネットワークへ接続するＰ２Ｐネットワークではトポロジが時々刻々変化するので、その変化するネットワークトポロジに追従して正確なデータを収集することは容易ではなかった。例えば、非特許文献２に記載の手法では、時々刻々に変化するネットワークトポロジに追従してデータ収集を行うために、Ｐｉｎｇパケットをアクティブに送信し続ける必要があった。
【００１８】
本発明は、複数の端末が接続され、ネットワークへの接続をサポートするサーバを持たないＧｎｕｔｅｌｌａ型のＰ２Ｐネットワークにおいて、時々刻々変化するネットワークトポロジを再現するために、ネットワークを構成する端末の接続先端末数の分布を効率よくかつ容易に推定することができる推定方法、推定装置、プログラムおよびそのプログラムを記録した記録媒体を提供することを目的とする。
【００１９】
【課題を解決するための手段】
請求項１に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法は、所定期間に自端末を通過するホップ値が記録されたパケットを受信し、受信したパケットに記録されているホップ値ごとにパケット数を集計し、ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、パケット数比ｒｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする。
【００２０】
請求項２に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定方法は、所定期間に自端末を通過するホップ値が記録されたパケットを受信し、所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計し、区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、パケット数比ｒｉ，ｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする。
【００２１】
ここで、ホップ値が記録されたパケットは、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを用いることができる（請求項３）。
【００２２】
請求項４に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定装置は、所定期間に自端末を通過するホップ値が記録されたパケットを受信する手段と、受信したパケットに記録されているホップ値ごとにパケット数を集計する手段と、ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手段とを備える。
【００２３】
請求項５に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定する推定装置は、所定期間に自端末を通過するホップ値が記録されたパケットを受信する手段と、所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計する手段と、区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、そのパケット数比ｒｉ，ｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手段とを備える。
【００２４】
ここで、ホップ値が記録されたパケットを受信する手段は、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを受信する構成である（請求項６）。
【００２５】
請求項７に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定するプログラムは、所定期間に自端末を通過するホップ値が記録されたパケットを受信する手順と、受信したパケットに記録されているホップ値ごとにパケット数を集計する手順と、ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、前記Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手順とを有する。
【００２６】
請求項８に記載のＰ２Ｐネットワークを構成する端末の接続先端末数の分布を推定するプログラムは、所定期間に自端末を通過するホップ値が記録されたパケトを受信する手順と、所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計する手順と、区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、そのパケット数比ｒｉ，ｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする手順とを有する。
【００２７】
ここで、ホップ値が記録されたパケットを受信する手順は、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを受信する（請求項９）。
【００２８】
また、請求項１０の発明は、請求項７に記載の各手段を機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。請求項１１の発明は、請求項８に記載の各手段を機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００２９】
【発明の実施の形態】
図１は、本発明の推定装置の構成例を示す。図において、本発明の推定装置は、Ｐ２Ｐネットワークに接続している端末に備えられるものであり、所定期間に自端末を通過するホップ値が記録されたパケットを受信するパケット受信手段１と、受信したパケットに記録されているホップ値ごとにパケット数を集計するパケット数集計手段２と、接続端末数確率分布推定手段３により構成される。
【００３０】
ここで、パケット受信手段１は、ＧｎｕｔｅｌｌａのＰ２Ｐネットワークでは例えばファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットを受信する構成であるが、ホップ値が記録されたパケットであれば他のパケットでもよい。パケット数集計手段２は、例えばＱｕｅｒｙパケットやＰｉｎｇ  パケットに記録されているホップ値ごとにパケット数を集計する。
【００３１】
接続端末数確率分布推定手段３は、ホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ（＝ｑｊ＋１／ｑｊ  ）を計算し、そのパケット数比ｒｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする。
【００３２】
また、パケット数集計手段２は、所定期間をｎ個（ｎは２以上の整数）の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計するようにしてもよい。このときの接続端末数確率分布推定手段３は、区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  （＝ｑｉ，ｊ＋１  ／ｑｉ，ｊ  ）を計算し、そのパケット数比ｒｉ，ｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）となる確率Ｐｒ（ｋ）を計算し、接続先端末数の確率分布の推定値とする。
【００３３】
図２は、本発明の推定方法の処理手順の一例を示す。
ステップＳ１では、所定期間（例えばｔ秒）に自端末を通過するホップ値が記録されたパケット（例えばＱｕｅｒｙパケットやＰｉｎｇ  パケット）を受信する。
【００３４】
ステップＳ２では、所定期間をｎ個の区間に区切り、各区間で受信したパケットに記録されているホップ値ごとにパケット数を集計する。ここで、区間ｉ（ｉ＝１，２，…，ｎ）  におけるホップ値ｊ（ｊ＝１，２，…，ｍ）  のパケット数をｑｉ，ｊ  と表す。
【００３５】
ステップＳ３では、ホップ値ｊのパケット数ｑｉ，ｊ  と、ホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  のパケット数比ｒｉ，ｊ  を
ｒｉ，ｊ  ＝［ｑｉ，ｊ＋１／ｑｉ，ｊ］
と計算する。ここで、［ｘ］はｘを超えない最大の整数とし、このパケット数比ｒｉ，ｊ  に１を加えた値をパケット数比ｒｉ，ｊ  （＝［ｑｉ，ｊ＋１／ｑｉ，ｊ］＋１）と再定義するが、［ｘ］はｘを四捨五入した整数あるいはｘを超える最小の整数としてもよい。
【００３６】
ステップＳ４では、パケット数比ｒｉ，ｊ  から、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋ（ｋは自然数）以下となる確率Ｐｒ（≦ｋ）を
【００３７】
【数１】
2004187217.tif 000003
【００３８】
と計算する。
次に、接続先端末数がｋとなる確率Ｐｒ（ｋ）を
Ｐｒ（１）＝Ｐｒ（≦１）
Ｐｒ（２）＝Ｐｒ（≦２）−Ｐｒ（≦１）
Ｐｒ（３）＝Ｐｒ（≦３）−Ｐｒ（≦２）
…
Ｐｒ（ｋ）＝Ｐｒ（≦ｋ）−Ｐｒ（≦ｋ−１）
のように計算し、接続先端末数の確率分布の推定値とする。
【００３９】
以下、図３に示すネットワーク構成において、点線で囲まれた端末の接続先端末数の確率分布を推定する具体的な計算例を示す（ｍ＝３）。黒丸で示す端末は、Ｑｕｅｒｙパケットを受信する自端末を表す。白丸内の数字は、その端末の接続先端末数を表す。白丸で示す端末から送信されたＱｕｅｒｙパケットが自端末まで転送されてきたときのホップ値は、自端末からの階層に応じてそれぞれ１，２，３，４となる。図１の点線内の端末について、接続先端末数と端末数の関係を表１に示す。この表１に示す端末の接続先端末数は未知であり、以下の計算によりその確率分布を推定する。
【００４０】
ここでは、所定期間（ｔ秒）中に、白丸の端末はＱｕｅｒｙパケットを１回送信するものと仮定し、自端末はその所定期間を１区間（ｎ＝１）としてＱｕｅｒｙパケットを受信して集計する。このとき、自端末で受信されるホップ値ｊ（ｊ＝１，２，３）のパケット数ｑ１，ｊ  およびホップ値ｊ＋１のパケット数ｑ１，ｊ＋１  は、自端末からみた各階層の端末数に応じて、
ｑ１，１  ＝１
ｑ１，２  ＝３
ｑ１，３  ＝８
ｑ１，４  ＝１１
となる。このとき、パケット数比ｒｉ，ｊ  は、
ｒ１，１  ＝［ｑ１，２／ｑ１，１］＋１＝４
ｒ１，２  ＝［ｑ１，３／ｑ１，２］＋１＝３
ｒ１，３  ＝［ｑ１，４／ｑ１，３］＋１＝２
となる。
【００４１】
以上により、接続先端末数がｋ以下となる確率Ｐｒ（≦ｋ）は、
Ｐｒ（≦１）＝（１／４）（０＋０．５）＝０．５／４＝１／８
Ｐｒ（≦２）＝（１／４）（１＋０．５）＝１．５／４＝３／８
Ｐｒ（≦３）＝（１／４）（２＋０．５）＝２．５／４＝５／８
Ｐｒ（≦４）＝（１／４）（３＋０．５）＝３．５／４＝７／８
と推定され、接続先端末数がｋとなる確率Ｐｒ（ｋ）は、
Ｐｒ（１）＝Ｐｒ（≦１）＝１／８
Ｐｒ（２）＝Ｐｒ（≦２）−Ｐｒ（≦１）＝３／８−１／８＝２／８
Ｐｒ（３）＝Ｐｒ（≦３）−Ｐｒ（≦２）＝５／８−３／８＝２／８
Ｐｒ（４）＝Ｐｒ（≦４）−Ｐｒ（≦３）＝７／８−５／８＝２／８
と推定される。この推定結果を表２にまとめる（推定確率分布１）。
【００４２】
【表１】
2004187217.tif 000004
【００４３】
【表２】
2004187217.tif 000005
【００４４】
次に、所定期間（２ｔ秒）で、白丸の端末はＱｕｅｒｙパケットを２回送信するものと仮定し、自端末はその所定期間を２つの区間に区切り（ｎ＝２）、Ｑｕｅｒｙパケットを受信して集計する。このとき、自端末で受信される区間ｉ（ｉ＝１，２）におけるホップ値ｊ（ｊ＝１，２，３）のパケット数ｑｉ，ｊ  およびホップ値ｊ＋１のパケット数ｑｉ，ｊ＋１  は、
ｑ１，１  ＝１    ｑ２，１  ＝１
ｑ１，２  ＝３    ｑ２，２  ＝３
ｑ１，３  ＝７    ｑ２，３  ＝９
ｑ１，４  ＝１２    ｑ２，４  ＝１０
となるものとする。このとき、パケット数比ｒｉ，ｊ  は、
ｒ１，１  ＝［ｑ１，２／ｑ１，１］＋１＝４
ｒ１，２  ＝［ｑ１，３／ｑ１，２］＋１＝３
ｒ１，３  ＝［ｑ１，４／ｑ１，３］＋１＝２
ｒ２，１  ＝［ｑ２，２／ｑ２，１］＋１＝４
ｒ２，２  ＝［ｑ２，３／ｑ２，２］＋１＝４
ｒ２，３  ＝［ｑ２，４／ｑ２，３］＋１＝２
となる。
【００４５】
以上により、接続先端末数がｋ以下となる確率Ｐｒ（≦ｋ）は、
Ｐｒ（≦１）＝（１／７）（０＋０．５）＝０．５／７＝１／１４
Ｐｒ（≦２）＝（１／７）（２＋０．５）＝２．５／７＝５／１４
Ｐｒ（≦３）＝（１／７）（３＋０．５）＝３．５／７＝７／１４
Ｐｒ（≦４）＝（１／７）（６＋０．５）＝６．５／７＝１３／１４
と推定され、接続先端末数がｋとなる確率Ｐｒ（ｋ）は、
Ｐｒ（１）＝Ｐｒ（≦１）＝１／１４
Ｐｒ（２）＝Ｐｒ（≦２）−Ｐｒ（≦１）＝５／１４−１／１４＝４／１４
Ｐｒ（３）＝Ｐｒ（≦３）−Ｐｒ（≦２）＝７／１４−５／１４＝２／１４
Ｐｒ（４）＝Ｐｒ（≦４）−Ｐｒ（≦３）＝１３／１４−７／１４＝６／１４
と推定される。この推定結果を表２にまとめる（推定確率分布２）。
【００４６】
以上説明した処理ステップは、図１に示すような専用のハードウェアで実現可能であり、また端末のコンピュータ上で動作するソフトウェア（プログラム）を用いて実現することも可能である。このプログラムを記録媒体（例えばＣＤ−ＲＯＭ）に記録し、端末のコンピュータ上で動作させるようにしてもよい。
【００４７】
【発明の効果】
以上説明したように、本発明は、自端末を通過するホップ値が記録されたパケットを受信してホップ値ごとにパケット数を集計し、ホップ値ｊのパケット数ｑｊ  と、ホップ値ｊ＋１のパケット数ｑｊ＋１  のパケット数比ｒｊ  を用い、Ｐ２Ｐネットワークを構成する端末の接続先端末数がｋとなる確率Ｐｒ（ｋ）を計算することにより、Ｐ２Ｐネットワークを構成する端末の接続先端末数の確率分布を推定することができる。
【００４８】
このように、本発明は推定のために新たな測定を行う必要がなく、例えばＧｎｕｔｅｌｌａのＰ２Ｐネットワークではファイル検索時に送信されるＱｕｅｒｙパケット、または端末の接続時に送信されるＰｉｎｇ  パケットをパッシブに受信し、接続先端末数の確率分布を推定することができる。すなわち、パッシブな測定により取得した手持ちのデータ（ホップ値ごとのパケット数）により、Ｐ２Ｐネットワークを構成する端末の接続先端末数の確率分布を効率よくかつ容易に推定することができ、ネットワークトポロジの変化にも柔軟に対応することができる。
【図面の簡単な説明】
【図１】本発明の推定装置の構成例を示すブロック図。
【図２】本発明の推定方法の処理手順を示すフローチャート。
【図３】具体的な計算例を説明するためのネットワークの構成を示す図。
【符号の説明】
１  パケット受信手段
２  パケット数集計手段
３  接続端末数確率分布推定手段
【図１】
2004187217.tif 000006
【図２】
2004187217.tif 000007
【図３】
2004187217.tif 000008