(57)【要約】【課題】ピア・ツー・ピアネットワークなどのネットワークにおいて、ネットワークを構成する各端末の接続状況を監視するためのサーバを用いることなく、ネットワークサイズ（そのネットワークを構成する端末数）を推定する。【解決手段】通信ネットワークに属する端末の１つを基準端末とし、Ｌを正の整数として、その基準端末に近傍に位置してその基準端末からの最短経路長がｌである端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を求める段階（ステップ１０１〜１０２）と、端末の個数ｎlとネットワークサイズとの関係を示す近似式を用いて、ネットワークサイズを決定する段階（ステップ１０３〜１０５）と、を設ける。【選択図】        図２
2005167806.tif 000002
【特許請求の範囲】
【請求項１】
複数の端末から構成される通信ネットワークのサイズを推定するネットワークサイズ推定方法であって、前記通信ネットワークに属する端末の１つを基準端末とし、該基準端末の近傍のネットワークの構造に関する情報を収集し、該情報に基づいて前記サイズを推定する、ネットワークサイズ推定方法。
【請求項２】
複数の端末から構成される通信ネットワークのサイズを推定するネットワークサイズ推定方法であって、
前記通信ネットワークに属する端末の１つを基準端末とし、Ｌを正の整数として、前記通信ネットワークにおいて前記基準端末の近傍に位置して前記基準端末からの最短経路長がｌである端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を求める段階と、
前記端末の個数ｎlと前記サイズとの関係を示す近似式を用いて、前記サイズを決定する段階と、
を有するネットワークサイズ推定方法。
【請求項３】
前記サイズをＮとし、ｎを正の定数として、前記近似式が
【数１】
2005167806.tif 000017
で表される、請求項２に記載のネットワークサイズ推定方法。
【請求項４】
前記正の定数ｎを
【数２】
2005167806.tif 000018
と推定する、請求項３に記載のネットワークサイズ推定方法。
【請求項５】
前記通信ネットワークを構成する端末の接続次数Ｄが従う確率分布Ｐｒ｛Ｄ＝ｄ｝が既知の場合に、
【数３】
2005167806.tif 000019
を非負の整数全体の集合として、前記正の定数ｎを
【数４】
2005167806.tif 000020
と推定する、請求項３に記載のネットワーク推定方法。
【請求項６】
さらに、前記基準端末からの最短経路長がＬ以下である端末に対して前記基準端末からその端末に接続した端末の数を問い合わせる段階を有し、該問い合わせの結果に基づいて前記基準端末からの最短経路長がｌである端末の個数ｎlが求められる、請求項２乃至５のいずれか１項に記載のネットワーク推定方法。
【請求項７】
複数の端末から構成される通信ネットワークに対して接続されて前記通信ネットワークのサイズを推定するネットワークサイズ推定装置であって、
Ｌを正の整数として、前記通信ネットワークにおいて前記ネットワークサイズ推定装置の近傍に位置して前記ネットワークサイズ推定装置からの最短経路長がｌである端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を近傍情報として入力する近傍情報入力手段と、
前記端末の個数ｎlと前記サイズとの関係を示す近似式を用いて、前記サイズを決定するネットワークサイズ推定手段と、
ネットワークサイズ推定手段で決定されたサイズを出力する推定結果出力手段と、
を有するネットワークサイズ推定装置。
【請求項８】
前記ネットワークサイズ推定手段は、前記サイズをＮとし、ｎを正の定数として、
【数５】
2005167806.tif 000021
で表される前記近似式を使用する、請求項７に記載のネットワークサイズ推定装置。
【請求項９】
前記ネットワークサイズ推定手段は、前記正の定数ｎを
【数６】
2005167806.tif 000022
と推定する、請求項８に記載のネットワークサイズ推定装置。
【請求項１０】
前記通信ネットワークを構成する端末の接続次数Ｄが従う確率分布Ｐｒ｛Ｄ＝ｄ｝が既知の場合に、前記ネットワークサイズ推定手段は、
【数７】
2005167806.tif 000023
を非負の整数全体の集合として、前記正の定数ｎを
【数８】
2005167806.tif 000024
と推定する、請求項８に記載のネットワーク推定装置。
【請求項１１】
複数の端末から構成された通信ネットワークに対し前記複数の端末のうちの１つとして接続されたコンピュータを、
Ｌを正の整数として、前記通信ネットワークにおいて前記コンピュータの近傍に位置して前記コンピュータからの最短経路長がｌである端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を近傍情報として入力する近傍情報入力手段、
前記端末の個数ｎlと前記サイズとの関係を示す近似式を用いて、前記サイズを決定するネットワークサイズ推定手段、
ネットワークサイズ推定手段で決定されたサイズを出力する推定結果出力手段、
として機能させるプログラム。
【請求項１２】
前記サイズをＮとし、ｎを正の定数として、
【数９】
2005167806.tif 000025
で表される前記近似式を使用する、請求項７に記載のプログラム。
【請求項１３】
前記通信ネットワークを構成する端末の接続次数Ｄが従う確率分布Ｐｒ｛Ｄ＝ｄ｝が未知の場合に、前記正の定数ｎを
【数１０】
2005167806.tif 000026
と推定し、前記確率分布が既知の場合に、
【数１１】
2005167806.tif 000027
を非負の整数全体の集合として、前記正の定数ｎを
【数１２】
2005167806.tif 000028
と推定する、請求項１２に記載のプログラム。
【請求項１４】
コンピュータが読み取り可能な記録媒体であって、請求項１１乃至１３のいずれか１項に記載のプログラムを格納した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークサイズの推定方法及びその装置に関し、特に、複数の端末が相互に近隣の端末と接続する（あるいはリンクを形成する）ことによって構成された通信ネットワークにおける、そのネットワークのサイズとしてそのネットワークを構成する端末の台数を推定する方法及び装置に関する。
【背景技術】
【０００２】
近年、ピア・ツー・ピア(peer-to-peer)型のネットワークを注目を浴びている。このようなネットワークでは、端末（ノードともいう）がその近隣にある１または複数の端末と接続し（あるいはそれらの端末に対してリンクを形成し）、そのように接続された端末がさらにその近隣にある１または複数の端末と接続することによって、非常に多数の端末を有するネットワークが構築されている。そして、第１の端末から、その端末に直接は接続していない第２の端末にアクセスする場合には、ネットワークのトポロジにおいて第１の端末と第２の端末との間に位置する１または複数の端末を媒介にして、アクセスが実現される。
【０００３】
このようなネットワークにおいては、例えば、通信品質を保つためにネットワーク内でのトラヒックを把握したり、各端末からのリクエストに応えるためにそのネットワークに含まれる端末数に応じて各端末の設備を増強する必要があったりするので、ネットワークサイズすなわちそのネットワークを構成する端末数を把握する必要がある。ネットワークサイズを把握するための従来技術としては、第１に、ネットワークを構成する各端末の接続状況を監視するためのサーバを設置するという技術が挙げられる。例えば、Ｎａｐｓｔｅｒ（ナップスター）型のピア・ツー・ピアネットワークでは、ネットワークを構成する各端末の接続状況を監視するためのサーバが設置されており、このサーバに蓄積される情報を用いることで、ネットワークを構成する端末の数（ネットワークサイズ）を把握することができる。
【非特許文献１】伊藤直樹、Ｐ２Ｐコンピューティング〜技術解説とアプリケーション〜、ソフト・リサーチ・センター、２００１
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、ネットワークを構成する端末数が大きい場合や、ネットワーク構造が時々刻々変化するような場合には、こうしたサーバの負荷が増大してしまう可能性が高い。また、Ｇｎｕｔｅｌｌａ（グヌーテラ）型のピア・ツー・ピアネットワークでは、ネットワークを構成する各端末の接続状況を把握するためのサーバそのものが設置されておらず、かつ、各端末は自由に他端末と接続することができるため、ネットワークを構成する各端末の接続状況を監視することはもちろん、ネットワークを構成する端末の数（ネットワークサイズ）を把握することもできない。したがって、このような課題を解決するために、ネットワークを構成する各端末の接続状況を監視するためのサーバを必要としない、ネットワークサイズ推定法が必要となる。
【０００５】
本発明は、上記の点に鑑みなされたものであって、ネットワークを構成する各端末の接続状況を監視するためのサーバを用いることなく、ネットワークのサイズを推定する方法、装置、そのプログラムおよびそのプログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のネットワークサイズの推定方法は、複数の端末から構成される通信ネットワークのサイズを推定するネットワークサイズ推定方法であって、通信ネットワークに属する端末の１つを基準端末とし、基準端末の近傍のネットワークを構造に関する情報を収集し、その情報に基づいてサイズを推定する。
【０００７】
具体的には、本発明のネットワークサイズ推定方法は、複数の端末から構成される通信ネットワークのサイズを推定するネットワークサイズ推定方法であって、通信ネットワークに属する端末の１つを基準端末とし、Ｌを正の整数として、その通信ネットワークにおいて基準端末の近傍に位置して基準端末からの最短経路長がｌである端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を求める段階と、端末の個数ｎl情報入力手段と、端末の個数ｎlとサイズとの関係を示す近似式を用いて、サイズを決定するネットワークサイズ推定手段と、ネットワークサイズ推定手段で決定されたサイズを出力する推定結果出力手段と、を有する。
【０００８】
すなわち本発明では、対象とする通信ネットワークに属する任意の端末（基準端末と呼ぶ）について、その端末の近傍でのネットワーク構成のみを用いて、その通信ネットワークのサイズを推定する。近傍情報としては、Ｌが正の整数であるとして、基準端末からの最短経路長がｌ以下である端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を用いることができる。ここで最短経路長とは、最短ホップ数とも呼ばれ、そのネットワークにおいて端末Ａから端末Ｂにアクセスするために、最短で何個の端末を経由しなければならないかを示すものである。端末Ａからそれ自体（端末Ａ）に対する最短経路長は０であると定義する。端末Ｂが端末Ａに直接接続していて、他の端末を経由することなく端末Ａから端末Ｂにアクセスできるときには、端末Ａから端末Ｂへの最短経路長は１となる。端末Ａから端末Ｂにアクセスする場合に、端末Ａと端末Ｂとが直接は接続しておらず、これら端末Ａ，Ｂの両方に接続した端末Ｃを経由しなければならないときは、端末Ａから端末Ｂへの最短経路長は２となる。以下、同様にして最短経路長が定められる。最短経路長の定義から、ｎ0＝１であることが直ちに導かれる。
【０００９】
以下の説明においては、端末Ａが端末Ｂに接続しているとは、これら２つの端末Ａ，Ｂが直接接続し、あるいはこれらの端末Ａ，Ｂを相互に接続するリンクが存在していて、他の端末を経由することなく端末Ａから端末Ｂにアクセスできることをいう。
【００１０】
また、本発明において、ネットワークサイズすなわちそのネットワークを構成する端末の台数の推定方法としては、ｎl，（ｌ＝０，１，…，Ｌ）の関係を近似する方法を用いることができる。すなわち上述のように最短経路長がｌ以下である端末の数をｎlとおき、最短経路長がｌである端末の数をｍlとおくと、
ｍl+1＝ｎl+1−ｎl            (1)
となる。またネットワークサイズをＮとおくと、基準端末から見て最短経路長がｌ＋２以上である端末の数はＮ−ｎl+1となり、最短経路長がｌ＋３以上である端末の数はＮ−ｎl+2となる。
【００１１】
一方、このネットワークにおいて、ある１つの端末が他の１つの端末と接続している確率（あるいはある端末と他の端末との間にリンクが存在する確率）をｐとおく。このとき、ある１つの端末が他のｍ個の端末のうちの１つとでも直接は接続していない確率は（１−ｐ）mとなる。
【００１２】
以上より、最短経路長がｌ＋２以上である端末のうち、最短経路長がｌ＋１の端末と接続していない端末の数は、
【００１３】
【数１】
2005167806.tif 000003
【００１４】
であることがわかる。これは、最短経路長がｌ＋３以上である端末の数を表すので、
【００１５】
【数２】
2005167806.tif 000004
【００１６】
となる。さらに、この関係式は、
【００１７】
【数３】
2005167806.tif 000005
【００１８】
と変形できる。
【００１９】
ところで、１台の端末が接続する他の端末の個数の平均値がネットワークサイズによらずに一定であるとすると、ある端末が他の端末と接続している確率ｐは、ネットワークサイズに反比例する。すなわち、ある正の定数ｎを用いて、
【００２０】
【数４】
2005167806.tif 000006
【００２１】
となる。したがって、近似式として、
【００２２】
【数５】
2005167806.tif 000007
【００２３】
が導かれる。ここでｎは、１台の端末が接続する他の端末の個数の平均値に関連する定数である。
【００２４】
さらに、式(5)におけるｎを
【００２５】
【数６】
2005167806.tif 000008
【００２６】
と推定することができる。
【００２７】
ただし、対象とする通信ネットワークを構成する端末の接続次数Ｄが従う確率分布Ｐｒ｛Ｄ＝ｄ｝が既知の場合、式(5)におけるｎを以下のように推定することもできる。ここで、
【００２８】
【数７】
2005167806.tif 000009
【００２９】
は非負の整数全体の集合を表す。ここで端末の接続次数Ｄとは、その端末からの最短経路長が１である端末の数を表している。
【００３０】
【数８】
2005167806.tif 000010
【００３１】
式(5)において、ｎl，ｎl+1，ｎl+2は、近傍情報として基準端末において入手可能である。また、ｎの値が上記のように推定されるとすると、これらのｎ，ｎl，ｎl+1，ｎl+2を式(5)に代入することによって、ネットワークサイズＮの値を推定することが可能である。式(5)はＮについての高次の多項式となるから、式(5)をＮについて代数的に解くことは困難である。そこで、誤差関数などを導入して数値解法によってＮを求めることが好ましい。
【発明の効果】
【００３２】
ネットワークサイズは、通信品質やネットワーク設計に大きな影響を与えるため、ネットワークサイズを簡便に推定する方法は重要である。しかし、従来の技術では、ネットワークサイズを把握するために、ネットワークを構成する端末の接続状況を監視するサーバを設置する必要がある。また、ネットワークを構成する端末が多い場合や、ネットワーク構造が時々刻々変化するような場合では、こうしたサーバの負荷が増大してしまう可能性が高い。また、このようなサーバそのものを持たないネットワークも存在する。したがってこのような課題を解決するために、ネットワークを構成をする端末の接続状況を監視するサーバを必要としないネットワークサイズ推定方法が必要となる。
【００３３】
本発明は、ネットワークを構成する端末の接続状況を監視するサーバを必要とせず、かつ、ネットワークの部分的な構造に関する情報のみを用いることで、ネットワークサイズを推定することを可能としている。
【発明を実施するための最良の形態】
【００３４】
次に、本発明の好ましい実施の形態について、図面を参照して説明する。
【００３５】
図１は、本発明の実施の一形態のネットワークサイズ推定方法が適用されるネットワークの構成の一例を示す図である。ネットワークは、端末Ｔ10，Ｔ11，…，Ｔ12，…で構成されている。ここでは、図示中央にある端末Ｔ10に注目し、この端末Ｔ10を基準端末して、端末Ｔ10においてネットワークサイズＮの推定を行うものとする。図示されるネットワークでは、端末Ｔ10は、端末Ｔ11，…，Ｔ41と接続し、端末Ｔ11は、端末Ｔ10，Ｔ41，Ｔ112，Ｔ122，Ｔ132，Ｔ142と接続している。
【００３６】
本実施形態では、基準端末Ｔ10の近傍でのネットワーク構成のみを用いて、その通信ネットワークのサイズＮを推定する。近傍情報としては、Ｌが正の整数であるとして、基準端末からの最短経路長がｌ以下である端末の個数ｎl，（ｌ＝０，１，…，Ｌ）を用いる。また、ｎを正の定数として、これらの関係を式(8)で近似する。
【００３７】
【数９】
2005167806.tif 000011
【００３８】
式(8)をＮについて解くことにより、ネットワークサイズＮが推定される。ただし、式(8)を代数的に解くことは困難であり、また、ｌの値によって異なるＮが解となり得るので、以下では、複数のｌの値に対応した最小二乗計算によってＮを数値的に求めることとし、そのために、以下の式(9)のように誤差関数ｅ（Ｎ，ｎ，Ｌ）を定義し、誤差関数を最小にするＮをもってネットワークサイズＮの推定値としている。
【００３９】
【数１０】
2005167806.tif 000012
【００４０】
式(9)により誤差関数ｅ（Ｎ，ｎ，Ｌ）の値を定めるためには、正の定数ｎの値を与えなければならない。本実施形態では、ネットワークサイズＮの推定に際し、ネットワークを構成する端末の接続次数Ｄの従う確率分布が未知であるか否かによって、以下のように場合分けして正の定数ｎを推定するものとする。
【００４１】
（１）Ｄの従う確率分布が未知の場合：
Ｄの従う確率分布が未知の場合には、最短経路長が２までの範囲内の端末数に基づき、正の定数ｎを
【００４２】
【数１１】
2005167806.tif 000013
【００４３】
のように推定する。
【００４４】
（２）Ｄの従う確率分布が既知の場合：
Ｄの従う確率分布Ｐｒ｛Ｄ＝ｄ｝が既知の場合には、その確率分布を用いて、正の定数ｎを
【００４５】
【数１２】
2005167806.tif 000014
【００４６】
のように推定する。ここで
【００４７】
【数１３】
2005167806.tif 000015
【００４８】
は、非負の整数全体の集合である。
【００４９】
（１），（２）のいずれの場合であっても、Ｎの値を変えながら誤差関数е（Ｎ，ｎ，Ｌ）の値を算出し、誤差関数е（Ｎ，ｎ，Ｌ）を最小にするＮをもってネットワークサイズの推定値とすればよい。
【００５０】
図２は、ここで説明したネットワークサイズ推定方法での処理をフローチャートとして示したものである。まず、ステップ１０１において、基準端末からその近隣に位置する端末に対して問合せを行うなどして、ｎ0，ｎ1，…，ｎlの値を求め、それらの値を入力する（ステップ１０２）。そのような問合せは、例えば、基準端末からの最短経路長がＬ以下である端末に対して、その端末に接続した端末の数を問い合わせることによって実現される。最短経路長がＬ以下である端末のみに問合せを行うためには、問合せのためのデータ中に、いわゆるＴＴＬ(time to live)フィールドとして、端末で１回中継されるごとに値が１だけ小さくされるようなフィールドであって、そのフィールドの値が正のときのみ中継が行われるようにするフィールドを設け、そのフィールドの値にＬを設定して基準端末が問合せを行うようにすればよい。
【００５１】
次に、端末の接続次数Ｄが既知である場合か未知である場合かを判別し（ステップ１０３）、未知である場合には、式(10)によってｎが表されるとして上述の式(9)に示す誤差関数е（Ｎ，ｎ，Ｌ）を最小にするＮの値をネットワークサイズの推定値とし（ステップ１０４）、既知である場合には式(11)によってｎが表されるとして上述の式(9)に示す誤差関数е（Ｎ，ｎ，Ｌ）を最小にするＮの値をネットワークサイズの推定値とする（ステップ１０５）。その後、このようにして求めたネットワークサイズＮの推定値を出力する（ステップ１０６）。
【００５２】
図３は、上述したネットワークサイズの推定を行うことができる端末の構成を示すブロック図である。この端末は、ネットワークサイズ推定装置１として機能するものであり、近隣の１乃至複数の端末に対して接続するための通信インタフェース１１と、通信インタフェース１１を介して近傍情報が入力する近傍情報入力部１２と、入力した近傍情報すなわちｎ0，ｎ1，…，ｎlに基づいて、上述したステップ１０２〜１０４の処理を行うことによってネットワークサイズＮを推定するネットワークサイズ推定部１３と、推定したネットワークサイズを出力する推定結果出力部１４と、ネットワークサイズ推定装置１の全体の動作する制御部１５と、を備えている。
【００５３】
以下、図１に示したネットワークにおいて、実際にネットワークサイズＮを推定した結果を説明する。図１に示したネットワークでは、基準端末Ｔ10からの最短経路長が１である端末はＴ11，Ｔ21，Ｔ31，Ｔ41であるため、ｎ1＝５となり、Ｔ10からの最短経路長が２である端末はＴ12，Ｔ22，…，Ｔ162であるため、ｎ2＝２１となる。また定義により、ｎ0＝１である。さらに、ここではＬ＝４とし、図示していないが、ｎ3＝８４，ｎ4＝３３０であるとする。ここでは、接続次数Ｄの従う確立分布は未知であることを前提としているので、ｎの値を
【００５４】
【数１４】
2005167806.tif 000016
【００５５】
と推定する。ｎ＝４，Ｌ＝４を代入するとともにＮの値を変えながら式(9)に示す誤差関数е（Ｎ，ｎ，Ｌ）を計算すると、以下のようになる。
【００５６】
е（８０００，４，４）＝９．０９×１０-9
е（８５００，４，４）＝５．４３×１０-9
е（８６００，４，４）＝５．２６×１０-9
е（８７００，４，４）＝５．２３×１０-9
е（８８００，４，４）＝５．３１×１０-9
е（８９００，４，４）＝５．５０×１０-9
е（９０００，４，４）＝５．７８×１０-9
е（９５００，４，４）＝８．０９×１０-9
したがって、図１に示したネットワークにおけるネットワークサイズＮの推定値はおよそ８７００となる。
【００５７】
以上、本発明の好ましい実施形態を説明したが、本発明の対象となるネットワークでは、端末としては、一般に、通信機能を有するパーソナルコンピュータなどが用いられる。したがって、本実施形態におけるネットワークサイズ推定装置は、それを実現するためのコンピュータプログラムを、パーソナルコンピュータなどの計算機に読み込ませ、そのプログラムを実行させることによっても実現できる。ネットワークサイズの推定を行うためのプログラムは、ＣＤ−ＲＯＭなどの記録媒体によって、あるいはネットワークを介して、コンピュータに読み込まれる。言うまでもないが、このコンピュータは、ネットワークにおける端末としても機能するものである。
【００５８】
そのようなコンピュータは、一般に、ＣＰＵ（中央処理装置）と、プログラムやデータを格納するためのハードディスク装置と、主メモリと、キーボードやマウスなどの入力装置と、ＣＲＴや液晶表示装置（ＬＣＤ）などの表示装置と、ＣＤ−ＲＯＭ等の記録媒体を読み取る読み取り装置と、ネットワークに接続するための通信インタフェースとから構成されている。ハードディスク装置、主メモリ、入力装置、表示装置、読み取り装置及び通信インタフェースは、いずれもＣＰＵに接続している。このコンピュータでは、上述した手順によってネットワークサイズの推定を行うためのプログラムを格納した記録媒体を読み取り装置に装着し、記録媒体からプログラムを読み出してハードディスク装置に格納し、あるいは、ネットワークを介してそのようなプログラムをダウンロードしてハードディスク装置内に格納し、その後、ハードディスク装置内に格納されたプログラムをＣＰＵが実行することにより、例えば、通信インタフェースを介してそのコンピュータの近傍のネットワーク構造に関する情報を取得し、その情報に基づいて、上述したような手順でネットワークサイズの推定が行われる。
【図面の簡単な説明】
【００５９】
【図１】本発明のネットワークサイズ推定方法が適用されるネットワークの構成の一例を示す図である。
【図２】本発明の実施の一形態におけるネットワークサイズ推定の手順を示すフローチャートである。
【図３】本発明の実施の一形態のネットワークサイズ推定装置の構成を示すブロック図である。
【符号の説明】
【００６０】
１    ネットワークサイズ推定装置
２    通信インタフェース
３    近隣情報入力部
４    ネットワークサイズ推定部
５    推定結果出力部
１０１〜１０４    ステップ
Ｔ10，Ｔ11，…，Ｔ12，…    端末
【図１】
2005167806.tif 000029
【図２】
2005167806.tif 000030
【図３】
2005167806.tif 000031