(57)【要約】【課題】Ｐ２Ｐネットワークにおいて、検索の成功率を下げることなく、各サーバントがファイル検索を行う際に転送するＱｕｅｒｙパケット数を抑制する。【解決手段】転送先サーバント数決定部１５は予め定められた関数Ｎに基づいて転送先サーバント数をＮ（ｈ，ｃ，ｐ）と決定する。次に、転送先サーバント選択部１６は予め定められた方法に基づいて、転送先のサーバントをＮ（ｈ，ｃ，ｐ）個選択する。次に、ＴＴＬ値・Ｈｏｐｓ値変更部１７がＴＴＬ値ｔを調べ、ｔが１であればＱｕｅｒｙパケットを廃棄して処理を終了する。そうでなければ、ＴＴＬ値ｔをｔ−１とし、Ｈｏｐｓ値ｈをｈ＋１とし、Ｑｕｅｒｙパケット出力部１８が選択されたサーバントへＱｕｅｒｙパケットを転送する。【選択図】    図１
2004258994.tif 000002
【特許請求の範囲】
【請求項１】
複数の端末が接続され、ファイルを検索するためのサーバを持たないＰ２Ｐネットワークにおける、ファイルを検索する方法であって、
ファイル検索元の端末が作成し、Ｐ２Ｐネットワーク内に送出した、検索条件を記録したパケットを受信するステップと、
該パケットに記録された検索条件に合致するファイルを自端末が保持しているか否か調べるステップと、
前記パケットに記録された検索条件に合致するファイルを自端末が保持している場合には、予め定められた方法にしたがってファイル検索元の端末にその旨を通知するステップと、
過去に行なわれた検索の結果を少なくとも含む情報に基づいて、該パケットの転送先の端末を決定するステップと、
ＴＴＬ値が１でなければ、ＴＴＬ値を１つ減らし、Ｈｏｐｓ値を１つ増やして、決定された転送先の端末へ前記パケットを転送するステップと、
前記ＴＴＬ値が１の場合、前記パケットを廃棄するステップを有するファイル検索方法。
【請求項２】
前記情報が、前記パケットに記録されている情報と前記Ｐ２Ｐネットワークの状態の少なくとも一方をさらに含む、請求項１に記載のファイル検索方法。
【請求項３】
自端末が保持するパケットのＨｏｐｓ値と、前記Ｐ２Ｐネットワークを構成する端末の平均接続数と、それまでに行なわれた検索の成功確率からなる関数に基づいて転送先の端末の数、および転送先の端末を決定する、請求項１に記載のファイル検索方法。
【請求項４】
ファイルを検索するためのサーバを持たないＰ２Ｐネットワークに接続された端末であって、
ファイル検索元の端末が作成し、Ｐ２Ｐネットワーク内に送出した、検索条件を記録したパケットを受信する手段と、
該パケットに記録された検索条件に合致するファイルを自端末が保持しているか否か調べる手段と、
前記パケットに記録された検索条件に合致するファイルを自端末が保持している場合には、予め定められた方法にしたがってファイル検索元の端末にその旨を通知する手段と、
過去に行なわれた検索の結果を少なくとも含む情報に基づいて、該パケットの転送先の端末を決定する手段と、
ＴＴＬ値が１でなければ、ＴＴＬ値を１つ減らし、Ｈｏｐｓ値を１つ増やして、決定された転送先の端末へ前記パケットを転送する手段と、
前記ＴＴＬ値が１の場合、前記パケットを廃棄する手段を有する端末。
【請求項５】
請求項１から３のいずれかに記載のファイル検索方法をコンピュータに実行させるためのファイル検索プログラム。
【請求項６】
請求項５に記載のファイル検索プログラムを記録した、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、Ｐ２Ｐ（ピア・ツー・ピア）型のネットワーク（Ｐ２Ｐネットワーク）において用いられる検索方法、端末、プログラム、および記録媒体に関する。
【０００２】
【従来の技術】
最近注目を集めているＰ２Ｐ型のネットワークは、従来のクライアント・サーバ（Ｃ／Ｓ）型とは異なり、サーバに頼ることなくコンピュータ資源やサービスをシステム間で直接共有する。
【０００３】
例えば、端末間で音楽などのファイルを交換するためのＰ２Ｐネットワークを構成するプログラムとして、従来より「Ｇｎｕｔｅｌｌａ」と呼ばれるソフトウェアを用いたネットワークが知られている（非特許文献１）。Ｇｎｕｔｅｌｌａのネットワークは、ファイル検索機能を備えるサーバが接続されていない純粋なＰ２Ｐネットワークである。Ｇｎｕｔｅｌｌａのネットワークに接続している各端末は、ファイルの検索機能を備えており、サーバントと呼ばれる。
【０００４】
Ｇｎｕｔｅｌｌａのネットワークにおけるファイル検索は次のようにして行われる。
１．ファイル検索元のサーバントは直接接続しているサーバントに対して、Ｑｕｅｒｙパケット（「Ｑｕｅｒｙ」は「問い合わせ」の意味）を送信する。Ｑｕｅｒｙパケットのペイロードには、“この検索要求に応じるサーバントの最低通信速度”や“検索キーワード”といった検索条件が記録されている。また、そのＱｕｅｒｙパケットのヘッダーに記録されているＨｏｐｓ値は“１”に設定される。
２．Ｑｕｅｒｙパケットを受け取ったサーバントはＱｕｅｒｙパケットのヘッダーに記録されているＴＴＬ（Ｔｉｍｅ  Ｔｏ  Ｌｉｖｅ）値を１つ減らし、それが０でなければ、自サーバントの接続している全てのサーバント（Ｑｕｅｒｙパケットを送信してきたサーバントは含まない）へＱｕｅｒｙパケットをそれぞれ転送する。また、その際、Ｑｕｅｒｙパケットのヘッダーに記録されているＨｏｐｓ値（パケットが転送されてきたサーバントの数）を１つ増やす。
３．転送されてきたＱｕｅｒｙパケットの条件に合致するファイルを持っているサーバントは、Ｑｕｅｒｙ  Ｈｉｔパケットを返す。持っていないサーバントは、単にパケットを転送するだけである。
４．Ｑｕｅｒｙ  Ｈｉｔパケットは、Ｑｕｅｒｙパケットが転送されてきた経路を逆順にたどって発信元に戻っていく。Ｑｕｅｒｙ  Ｈｉｔパケットのペイロードには、条件に合ったファイルの総数、Ｑｕｅｒｙ  Ｈｉｔしたサーバントの待ち受けＴＣＰポート番号、Ｑｕｅｒｙ  ＨｉｔしたサーバントのＩＰアドレス、Ｑｕｅｒｙ  Ｈｉｔしたサーバントの接続通信速度、条件に合ったファイルの名前とサイズとファイルインデックス（どのファイルであるかを示すために、サーバント側で付けている一連の番号）、Ｑｕｅｒｙ  ＨｉｔしたサーバントのＧＵＩＤ（Ｇｒｏｂａｌｌｙ  Ｕｎｉｑｕｅ  Ｉｄｅｎｔｉｆｉｅｒ）といった情報が記録されている。
【０００５】
また、転送されてきたＱｕｅｒｙパケットのヘッダーに記録されている情報に基づいて転送先のサーバント数（転送するＱｕｅｒｙパケット数）を抑制する（減らす）手法も知られている（特許文献１）。
【０００６】
【非特許文献１】
伊藤直樹、“Ｐ２Ｐコンピューティング〜技術解説とアプリケーション〜、ソフト・リサーチセンター”、２００１
【特許文献１】
特願２００２−２９２２４６
【特許文献２】
特願２００２−３５４９８８
【０００７】
【発明が解決しようとする課題】
ファイルを検索するためのサーバを持たないＰ２Ｐネットワークにおいて、Ｇｎｕｔｅｌｌａのようなファイル検索手法を用いる場合、ファイル検索条件が記録されたパケット（以下、Ｑｕｅｒｙパケット）は各端末（以下、サーバント）において中継されるたびに複製され増加し続ける。このことは、ファイル検索に伴う回線帯域、あるいはサーバントのＣＰＵへの負荷につながる。しかし、中継の際に複製されるＱｕｅｒｙパケットの数をむやみに少なくしてしまうと、十分な検索結果が得られない（検索が失敗してしまう）という懸念がある。
【０００８】
本発明の目的は、複数の端末が接続され、ファイルを検索するためのサーバを持たないＰ２ＰネットワークにおいてＱｕｅｒｙパケットを用いてファイル検索する際に、検索の成功率を下げることなく、転送するＱｕｅｒｙパケット数（あるいは転送先のサーバント数）を抑制するファイル検索方法、端末、プログラム、および記録媒体を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的を達成するために、本発明は、ファイル検索元の端末が作成し、Ｐ２Ｐネットワーク内に送出した、検索条件を記録したパケットの転送先の端末を、過去に行なわれた検索の結果を少なくとも含む情報に基づいて決定する。
【００１０】
これにより、検索の成功率を下げることなく、Ｑｕｅｒｙパケット数（あるいは、転送先のサーバント数）を抑制することができる。
【００１１】
過去に行なわれた検索の結果の例として検索の成功率が挙げられる。また、受信したパケットに記録されている情報（例：Ｈｏｐｓ値、ＴＴＬ値）やネットワークの状態（例：ネットワークのトポロジ、ネットワークを構成するサーバントの平均接続数）をさらに用いて、パケットの転送先の端末を決定することもできる。
【００１２】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１３】
図１はＰ２Ｐネットワークを構成する端末（サーバント）の構成、図２はその処理の流れ図、図３はＱｕｅｒｙパケットの転送先のサーバントの例を示している。
【００１４】
サーバントＳｏはＱｕｅｒｙパケット入力部１１とＴＴＬ値・Ｈｏｐｓ値読み取り部１２とサーバント平均接続数推定部１３と検索成功確率計算部１４と転送先サーバント数決定部１５と転送先サーバント選択部１６とＴＴＬ値・Ｈｏｐｓ値変更部１７とＱｕｅｒｙパケット出力部１８を有している。ここで、該サーバントＳｏが転送可能なサーバントの数をｎとする。
【００１５】
本実施形態でのパケット転送方法は、Ｇｎｕｔｅｌｌａの転送方法を基礎にしているが、保持するＱｕｅｒｙパケット（自サーバントが検索元サーバントとして作成したＱｕｅｒｙパケットである場合と、他サーバントから受信したＱｕｅｒｙパケットである場合がある）のＨｏｐｓ値ｈと、ネットワークを構成するサーバントの平均接続数ｃと、それまでに行われた検索の成功確率ｐに基づいて、転送先サーバントと転送先サーバント数が変化する点が異なる転送方法である。
【００１６】
まず、Ｑｕｅｒｙパケット入力部１１は、ファイル検索元のサーバント（図示せず）が作成し、Ｐ２Ｐネットワークに送出した、検索条件を記録したＱｕｅｒｙパケットを受信し（ステップ２０）、該パケットに記録された検索条件に合致するファイルを自サーバントが保持しているか否かを調べる（ステップ２１）。保持していれば、予め定められた方法にしたがってファイル検索元のサーバントにその旨を通知する（ステップ２２）。次に、ＴＴＬ値・Ｈｏｐｓ値読み取り部１２がＱｕｅｒｙパケットに記録されているＴＴＬ値ｔとＨｏｐｓ値ｈを読み取る（ステップ２３）。次に、サーバント平均接続数推定部１３が、特許文献３に記載された手法を用い、接続先サーバントの分布の平均からサーバント平均接続数ｃを計算する（ステップ２４）。次に、検索成功確率計算部１４が検索成功確率ｐを計算する（ステップ２５）。例えば検索要求が１００回あって、３０回ファイルが見つかると、検索成功確率ｐは３０／１００＝３０（％）となる。次に、転送先サーバント数決定部１５が予め定められた関数Ｎに基づいて転送先サーバント数をＮ（ｈ，ｃ，ｐ）と決定する（ステップ２６）。Ｎ（ｈ，ｃ，ｐ）は転送可能なサーバント（直接接続しているサーバントから、Ｑｕｅｒｙパケットを転送してきたサーバントを除いたもの）の数以下の値を取る。次に、転送先サーバント選択部１６が予め定められた方法（例えばランダム選択法）に基づいて、転送先のサーバントをＮ（ｈ，ｃ，ｐ）個選択する（ステップ２７）。図３の例では、サーバントＳ１、Ｓ２、Ｓ５・・・、Ｓｎ−２、Ｓｎが転送先のサーバントである。次に、ＴＴＬ値・Ｈｏｐｓ値変更部１７がＴＴＬ値ｔを調べ（ステップ２８）、ｔが１であればＱｕｅｒｙパケットを廃棄して処理を終了する（ステップ３１）。そうでなければ、ＴＴＬ値ｔをｔ−１とし、Ｈｏｐｓ値ｈをｈ＋１とし（ステップ２９）、Ｑｕｅｒｙパケット出力部１８がステップ２７で選択したサーバントへＱｕｅｒｙパケットを転送する（ステップ３０）。
【００１７】
次に、関数Ｎの具体例を示す。
【００１８】
Ｎ（ｈ，ｃ，ｐ）＝ｍｉｎ｛ｎ，Ｎ１（ｈ）＋Ｎ２（ｃ）＋Ｎ３（ｐ）｝
ただし
【００１９】
【数１】
2004258994.tif 000003
である。ここで、
【００２０】
【数２】
2004258994.tif 000004
および
【００２１】
【数３】
2004258994.tif 000005
である。
【００２２】
ｖｈｏｐｓはＨｏｐｓ値ｈの閾値、ｖｃｏｎｎｅｃｔｉｏｎはサーバント平均接続数ｃの閾値、ｖｐｒｏｂａｂｉｌｉｔｙは検索成功確率ｐの閾値である。
【００２３】
Ｎ１（ｈ）はＨｏｐｓ値ｈが閾値Ｖｈｏｐｓ以下の場合にはα１（＞０）、閾値ｖｈｏｐｓを超えた場合にα２（＞０）の値をとることを示している。Ｎ２（ｃ）は、サーバント平均接続数ｃがｖｃｏｎｎｅｃｔｉｏｎ以下、つまりネットワークが切れかかっている場合にはβ１（＞０）の値をとり、ネットワークにサーバントが十分接続されている場合には−β２（＜０）の値をとることを示している。Ｎ３（ｐ）は、検索成功率ｐがＶｐｒｏｂａｂｉｌｉｔｙ以下、つまり検索がうまくいっていない場合、γ１（＞０）の値をとって転送先を増やし、検索成功率ｐがＶｐｒｏｂａｂｉｌｉｔｙより大きい場合、つまり検索がうまくいっているので、−γ２（＜０）の値をとって、転送先を減らす（転送するＱｕｅｒｙパケット数を抑制する）ことを示している。
【００２４】
なお、本発明は専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。
【００２５】
【発明の効果】
以上説明したように、本発明によれば、検索の成功率を下げることなく、各サーバントがファイル検索を行う際に転送するＱｕｅｒｙパケット数を抑制することが可能になる。
【図面の簡単な説明】
【図１】本発明の一実施形態の、Ｐ２Ｐネットワークを構成する端末（サーバント）の構成図である。
【図２】図１の端末で行なわれる処理の流れ図である。
【図３】図１の端末で行なわれる、Ｑｕｅｒｙパケットの転送先サーバントの決定方法の説明図である。
【符号の説明】
１１    Ｑｕｅｒｙパケット入力部
１２    ＴＴＬ値・Ｈｏｐｓ値読み取り部
１３    サーバント平均接続数推定部
１４    検索成功確率計算部
１５    転送先サーバント数決定部
１６    転送先サーバント選択部
１７    ＴＴＬ値・Ｈｏｐｓ値変更部
１８    Ｑｕｅｒｙパケット出力部
２０〜３１    ステップ
Ｓｏ          サーバント
Ｓ１〜Ｓｎ    Ｑｕｅｒｙパケットを転送可能なサーバント
【図１】
2004258994.tif 000006
【図２】
2004258994.tif 000007
【図３】
2004258994.tif 000008