(57)【特許請求の範囲】
【請求項１】
ピアツーピア（Ｐ２Ｐ）ネットワーク内のサーバであって、
前記Ｐ２Ｐネットワーク内の各データノードの座標を、前記Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示す座標情報を記憶する位置情報記憶手段と、
第１のデータアイテムを保有するデータノードの情報を求める要求を受信すると、前記位置情報記憶手段内に記憶された座標情報に基づいて、第１のデータアイテムを保有する前記データノードの中から１つ以上のデータノードを選択し、選択した１つ以上のデータノードを示す情報を提供するノード情報提供手段と、を備え、
前記Ｐ２Ｐネットワークが、Ｍ個のデータノード｛Ｈ１，…，ＨＭ｝を含み（Ｍは１より大きい整数）、
前記座標系は、
【数３】
0005692757.tif 000009
（ここで、Ｅｒｒ（）は、誤差関数、Ｌｉｊは、２つのデータノードＨｉおよびＨｊ間の測定された通信遅延に基づく距離、ｄｉｊは、座標系における２つのデータノードＨｉおよびＨｊの座標間のユークリッド距離）
が最小化されるように生成される、
ことを特徴とするサーバ。
【請求項２】
前記ノード情報提供手段が、前記位置情報記憶手段から、前記第１のデータアイテムを保有する各データノードの座標と第１のデータノードの座標を検索し、検索した座標に基づいて、第１のデータアイテムを保有する各データノードと前記第１のデータノードとの間の距離を計算し、計算した距離の昇順に基づいて第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択するノード選択手段を含むことを特徴とする請求項１に記載のサーバ。
【請求項３】
各データアイテムについて、前記Ｐ２Ｐネットワークにおいてデータアイテムを保有するデータノードを示すノード情報を格納するノード情報記憶手段を、さらに備えることを特徴とする請求項１に記載のサーバ。
【請求項４】
前記ノード情報提供手段は、前記ノード情報記憶手段内において前記第１のデータアイテムを保有するデータノードを検索するノード検索手段を含むことを特徴とする請求項３に記載のサーバ。
【請求項５】
第１のデータノードが第２のデータアイテムを保有することを示す情報を受信すると、前記ノード情報記憶手段に格納されたノード情報に、受信した情報を追加するノード情報更新手段を、さらに備えることを特徴とする請求項３に記載のサーバ。
【請求項６】
前記ノード情報記憶手段に格納されたノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記ノード情報提供手段は、要求を受信すると、前記位置情報記憶手段内において第１のデータノードの座標を検索し、前記第１のデータノードの座標を開始点として、前記ノード情報記憶手段に格納されたノード情報において配置された第１のデータアイテムを保有するデータノードから１つ以上のデータノードを連続して選択することを特徴とする請求項３に記載のサーバ。
【請求項７】
前記ノード情報記憶手段に格納されたノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記ノード情報更新手段は、情報を受信すると、前記位置情報記憶手段内の第１のデータノードの座標を検索し、
第２のデータアイテムを保有するデータノードの中で、第１のデータノードが第１のデータノードの座標に基づいて配置されるように、検索した座標に従って、受信した情報を前記ノード情報記憶手段に格納されたノード情報に追加することを特徴とする請求項５に記載のサーバ。
【請求項８】
第１のデータノードと他のデータノードとの間のデータアイテム交換の状態を示す第１のデータノードからフィードバックされた性能情報を受信すると、受信した性能情報に基づいて前記位置情報記憶手段に格納された座標情報を更新する位置情報更新手段を、さらに備えることを特徴とする請求項１に記載のサーバ。
【請求項９】
ピアツーピア（Ｐ２Ｐ）ネットワーク内のノード情報を提供する方法であって、
第１のデータアイテムを保有するデータノードの情報を求める要求を受信するステップと、
座標情報に基づいて、第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択するステップと、
選択された１つ以上のデータノードを示す情報を提供するステップとを含み、
前記座標情報は、Ｐ２Ｐネットワーク内の各データノードの座標を、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示し、
前記Ｐ２Ｐネットワークが、Ｍ個のデータノード｛Ｈ１，…，ＨＭ｝を含み（Ｍは１より大きい整数）、
前記座標系は、
【数４】
0005692757.tif 000010
（ここで、Ｅｒｒ（）は、誤差関数、Ｌｉｊは、２つのデータノードＨｉおよびＨｊ間の測定された通信遅延に基づく距離、ｄｉｊは、座標系における２つのデータノードＨｉおよびＨｊの座標間のユークリッド距離）
が最小化されるように生成される、
ことを特徴とする方法。
【請求項１０】
前記１つ以上のデータノードを選択するステップが、
各データアイテムを保有するデータノードを示すノード情報内で第１のデータアイテムを保有するデータノードを検索するステップと、
前記座標情報に基づいて、前記第１のデータアイテムを保有する各データノードの座標と第１のデータノードの座標を検索するステップと、
検索した座標に基づいて、第１のデータアイテムを保有する各データノードと前記第１のデータノードとの間の距離を計算するステップと、
計算した距離の昇順に基づいて第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択するステップとを含むことを特徴とする請求項９に記載の方法。
【請求項１１】
第１のデータノードが第２のデータアイテムを保有することを示す情報を受信すると、各データアイテムを保有するデータノードを示すノード情報に、受信した情報を追加するステップをさらに含むことを特徴とする請求項９に記載の方法。
【請求項１２】
各データアイテムを保有するデータノードを示すノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記１つ以上のデータノードを選択するステップが、
座標情報に基づいて第１のデータノードを検索するステップと、
前記第１のデータノードの座標を開始点として、前記ノード情報において配置された第１のデータアイテムを保有するデータノードから１つ以上のデータノードを連続して選択するステップとを含むことを特徴とする請求項９に記載の方法。
【請求項１３】
各データアイテムを保有するデータノードを示すノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記ノード情報に受信した情報を追加するステップが、
前記座標情報に基づいて、第１のデータノードの座標を検索するステップと、
第２のデータアイテムを保有するデータノードの中で、第１のデータノードが第１のデータノードの座標に基づいて配置されるように、検索した座標に従って、受信した情報を前記ノード情報に追加するステップとを含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
第１のデータノードと他のデータノードとの間のデータアイテム交換の状態を示す第１のデータノードからフィードバックされた性能情報を受信すると、受信した性能情報に基づいて前記座標情報を更新するステップをさらに含むことを特徴とする請求項９に記載の方法。
【請求項１５】
ピアツーピア（Ｐ２Ｐ）ネットワーク内のノード情報を提供するためのシステムであって、
データノードとサーバを備え、
前記データノードが、
第１のデータアイテムを保有するデータノードの情報を求める要求をサーバに送信するノード情報要求手段と、
前記サーバによって提供された情報に示されたデータノードと第１のデータアイテムを交換するデータ交換手段とを含み、
前記サーバが、
Ｐ２Ｐネットワーク内の各データノードの座標を、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示す座標情報を記憶する位置情報記憶手段と、
前記第１のデータアイテムを保有するデータノードに関する情報に対する要求を前記データノードから受信すると、前記位置情報記憶手段に記憶された座標情報に基づいて、第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択し、選択された１つ以上のデータノードを示す情報を前記データノードに提供するノード情報提供手段とを含み、
前記Ｐ２Ｐネットワークが、Ｍ個のデータノード｛Ｈ１，…，ＨＭ｝を含み（Ｍは１より大きい整数）、
前記座標系は、
【数５】
0005692757.tif 000011
（ここで、Ｅｒｒ（）は、誤差関数、Ｌｉｊは、２つのデータノードＨｉおよびＨｊ間の測定された通信遅延に基づく距離、ｄｉｊは、座標系における２つのデータノードＨｉおよびＨｊの座標間のユークリッド距離）
が最小化されるように生成される、
ことを特徴とするシステム。
【請求項１６】
前記ノード情報提供手段が、前記位置情報記憶手段から、前記第１のデータアイテムを保有する各データノードの座標と第１のデータノードの座標を検索し、検索した座標に基づいて、第１のデータアイテムを保有する各データノードと前記第１のデータノードとの間の距離を計算し、計算した距離の昇順に基づいて第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択するノード選択手段を含むことを特徴とする請求項１５に記載のシステム。
【請求項１７】
前記サーバが、各データアイテムについて、前記Ｐ２Ｐネットワークにおいてデータアイテムを保有するデータノードを示すノード情報を格納するノード情報記憶手段を、さらに備えることを特徴とする請求項１５に記載のシステム。
【請求項１８】
前記ノード情報提供手段は、前記ノード情報記憶手段内において前記第１のデータアイテムを保有するデータノードを検索するノード検索手段を含むことを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記データノードが、前記データノードが第２のデータアイテムを保有することを示す情報を前記サーバに報告するデータ情報報告手段をさらに含み、
前記サーバが、第１のデータノードが第２のデータアイテムを有することを示す情報を受信すると、前記ノード情報記憶手段に格納されたノード情報に、受信した情報を追加するノード情報更新手段をさらに含む
ことを特徴とする請求項１７に記載のシステム。
【請求項２０】
前記ノード情報記憶手段に格納されたノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記ノード情報提供手段は、要求を受信すると、前記位置情報記憶手段内において第１のデータノードの座標を検索し、前記第１のデータノードの座標を開始点として、前記ノード情報記憶手段に格納されたノード情報において配置された第１のデータアイテムを保有するデータノードから１つ以上のデータノードを連続して選択することを特徴とする請求項１７に記載のシステム。
【請求項２１】
前記ノード情報記憶手段に格納されたノード情報において、各データアイテムを保有するデータノードは、座標系におけるデータノードの座標によって配置され、
前記ノード情報更新手段は、情報を受信すると、前記位置情報記憶手段において第１のデータノードの座標を検索し、
第２のデータアイテムを保有するデータノードの中で、第１のデータノードが第１のデータノードの座標に基づいて配置されるように、検索した座標に従って、受信した情報を前記ノード情報記憶手段に格納されたノード情報に追加することを特徴とする請求項１９に記載のシステム。
【請求項２２】
前記データノードが、前記データノードと他のデータノードとの間のデータアイテム交換の状態を示す性能情報を収集し、収集した性能情報を前記サーバにフィードバックする性能情報フィードバック手段を含み、
前記サーバが、データノードからフィードバックされた性能情報を受信すると、受信した性能情報に基づいて前記位置情報記憶手段に格納された座標情報を更新する位置情報更新手段をさらに含むことを特徴とする請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はピアツーピア（Ｐ２Ｐ）技術に関し、特に、Ｐ２Ｐネットワークのノード情報を提供するサーバ、方法、およびシステムに関する。
【背景技術】
【０００２】
近年、インターネットアプリケーション分野ではＰ２Ｐ技術が注目を集めている。この技術は、インターネットユーザがリソースを効率的に共有するための新しい方式を提供するものである。Ｐ２Ｐネットワークにおいては、ノードの選択が重要な問題となる。データノードは、他のデータノードとリソース（データアイテム）を交換したいときに、Ｐ２Ｐネットワーク内のサーバに対して要求を発行することができる。サーバはこのリソースを保有するデータノードを検索し、その中からいくつかのノードを選び、その情報を要求元に返す。その後、要求元はこれらのノードから目的のリソースを直接ダウンロードすることができる。
【０００３】
既存のＰ２Ｐシステムでは、リソースを保有するノードからいくつかのノードが無作為に選択されるのが一般的である。このような方法では、ネットワークを効率的に利用することはできない。例えば、膨大な量のネットワークトラフィックがインターネットサービスプロバイダ（ＩＳＰ）のバックボーンを通過するため、バックボーンに多大な送信負荷がかかる。また、ネットワークトラフィックは複数のＩＳＰを横断して送信されることが多いため、大量なネットワーク間（ＩＳＰ間）トラフィックが発生する。さらに、このような方法では、提供されるサービスの品質と性能にも影響が出る。それは、Ｐ２Ｐネットワーク内に通信遅延が少ないノードが存在していたとしても、無作為ノード選択機構が通信遅延の多い他のノードを選択する可能性があるからである。
【０００４】
この問題を解決するため、位置情報に基づく新しいＰ２Ｐシステムが提案されている。この方法とは、ノード選択の際に、「近接」ノードを優先的に選択するものである。無作為ノード選択機構の問題は、近接するノードを選択することで解決される。そのため、ネットワークの利用効率は高まり、ネットワーク間トラフィックは減少し、アプリケーションの性能が向上する。
【０００５】
２００７年８月１５日付けの中国特許出願公開ＣＮ１０１０１８１７２Ａ、“Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  Ｐ２Ｐ  Ｔｒａｎｓｍｉｓｓｉｏｎ  ｗｉｔｈｉｎ  Ｍｅｔｒｏｐｏｌｉｔａｎ  Ａｒｅａ  Ｎｅｔｗｏｒｋ”（メトロポリタンエリアネットワークにおけるＰ２Ｐ送信の最適化方法）（特許文献１）では、メトロポリタンエリアネットワーク（都市規模ネットワーク）用Ｐ２Ｐアプリケーションのための最適化方法が開示されている。特許文献１では、トポロジサーバとインデキシングサーバを追加することにより、Ｐ２Ｐトラフィックの発生をネットワークの縁部のみに限定してバックボーンにかかる送信負荷を軽減し、それによりＰ２Ｐに起因するネットワークの輻輳を回避することが試みられる。
【０００６】
Ｓｉｇｃｏｍｍ  ２００８で発表された“Ｐ４Ｐ：Ｐｒｏｖｉｄｅｒ  Ｐｏｒｔａｌ  ｆｏｒ  Ａｐｐｌｉｃａｔｉｏｎｓ”（Ｐ４Ｐ：アプリケーション用プロバイダポータル）、Ｈａｉｙｏｎｇ  Ｘｉｅ，Ｙ．Ｒｉｃｈａｒｄ  Ｙａｎｇ，Ａｒｖｉｎｄ  Ｋｒｉｓｈｎａｍｕｒｔｈｙ，Ｙａｎｂｉｎ  Ｌｉｕ，Ａｖｉ  Ｓｉｌｂｅｒｓｃｈａｔｚ（非特許文献１）では、Ｐ４Ｐと呼ばれる新しいアーキテクチャが提案されている。このアーキテクチャでは、ネットワークトラフィックの制御において、Ｐ２ＰアプリケーションとＩＳＰ間でより効率的に連携することが可能になる。この機構は、既存のＰ２Ｐアプリケーションの性能を維持し、さらには向上させる一方で、ＩＳＰ側のコストを削減することができる。
【０００７】
２００８年８月６日付けの中国特許出願公開ＣＮ１０１２３７４６７Ａ、“Ｍｏｂｉｌｅ  Ｐ２Ｐ  Ｎｅｔｗｏｒｋ  Ｒｅｓｏｕｒｃｅ  Ｄｉｓｃｏｖｅｒｉｎｇ  Ｍｅｔｈｏｄ  Ｉｎｔｒｏｄｕｃｉｎｇ  Ｖｅｃｔｏｒ  Ｌｏｃａｔｉｎｇ”（ベクトル位置決めを導入したモバイルＰ２Ｐネットワークリソース発見方法）（特許文献２）では、ベクトル位置決めを導入したモバイルＰ２Ｐネットワークリソース発見方法が開示されている。この方法では、極座標位置決め理論を導入して、セルラーネットワーク全体をホーム地域、距離、および方向によって分割し、位置ベクトル情報を保持する新しい経路指定テーブルを確立することにより、セルラーネットワークのための迅速で高精度な位置決めと、リソースの双方向ルックアップとが実現されている。
【０００８】
図１は、特許文献１に記載されるメトロポリタンエリアネットワークの構造を示す。ユーザコンピュータは、Ｐ２Ｐネットワーク内のデータノードとして動作する際には、最初に建物スイッチにアクセスし、次にセルスイッチに接続し、アクセス層スイッチまたはルータ（以下、「アクセススイッチ」という）に接続し、さらに集約層スイッチまたはルータ（以下、「集約スイッチ」という）に接続し、最後にコアスイッチまたはルータに接続するのが一般的である。メトロポリタンエリアネットワークのコアネットワークは、概して、１つ以上のコアスイッチまたはルータで構成される。また、典型的には、建物スイッチは１つのサブネットで構成される。
【０００９】
特許文献１で開示されたメトロポリタンエリアネットワーク内のＰ２Ｐ送信の最適化方法は、１）Ｐ２Ｐノードがリソースのダウンロードを要求してきたときに（このノードは「要求元Ｐ２Ｐノード」と呼ばれる）、Ｐ２Ｐインデキシングサーバを介して、このリソースを保有するＰ２Ｐノード（これらのノードは「リソースＰ２Ｐノード」と呼ばれる）のリストをクエリするステップと、２）リソースＰ２Ｐノードから、ネットワーク上で要求元Ｐ２Ｐノードに最も近接したノードを検索するステップと、３）要求元Ｐ２Ｐノードが、ネットワーク上の１つ以上の最も近接したリソースＰ２Ｐノードからリソースをダウンロードするステップ、とを含む。
【００１０】
要求元Ｐ２Ｐノードのために近接ノードを選択するアルゴリズムは、最初に要求元Ｐ２Ｐノードと同じ建物スイッチに接続されたノードを選択し、次に要求元Ｐ２Ｐノードと同じセルスイッチに接続されたノードを選択し、さらに要求元Ｐ２Ｐノードと同じアクセススイッチに接続されたノードを選択し、最後に要求元Ｐ２Ｐノードと同じ集約スイッチに接続されたノードを選択する。選択されたノードの数が要求された数よりも少ない場合は、当該リソースを保有するすべてのノードが近接ノードとみなされる。この方法では、Ｐ２Ｐトラフィックを可能な限りコアネットワークから遠くして、ネットワークの縁部で送信されるようにすることにより、コアネットワークや集約ネットワークのようなバックボーンネットワークを流れるＰ２Ｐトラフィックが減少される。
【００１１】
近接ノードを検索するためには、メトロポリタンエリアネットワーク内のスイッチまたはルータをコード化する必要がある。図１に示すように、ｓ１は集約スイッチのコードであり、その値は１〜ｎ１である。ｓ２はアクセススイッチのコードであり、その値は１〜ｎ２である。ｓ３はセルスイッチのコードであり、その値は１〜ｎ３である。ｓ４は建物スイッチのコードであり、その値は１〜ｎ４である。コアネットワークから各コンピュータに至るまでに存在するスイッチまたはルータのコードは、当該コンピュータの位置ベクトル（位置情報）を構成し、Ｓ＝（ｓ１，ｓ２，ｓ３，ｓ４）と表現される。
【００１２】
近接ノードを検索するための計算方法は、以下のとおりである。すなわち、まず２つのノードの位置ベクトルが、それぞれＳ＝（ｓ１、ｓ２、ｓ３、ｓ４）およびＳ’＝（ｓ１’、ｓ２’、ｓ３’、ｓ４’）として定義される。これら２つのノード間の距離ベクトルＤは以下のようになる。
Ｄ＝（ｄ１，ｄ２，ｄ３，ｄ４）
＝（ｓ１，ｓ２，ｓ３，ｓ４）−（ｓ１’，ｓ２’，ｓ３’，ｓ４’）
＝（ｓ１−ｓ１’，ｓ２−ｓ２’，ｓ３−ｓ３’，ｓ４−ｓ４’），
【００１３】
ここで、ｓｉ＝ｓｉ’のときｄｉ＝０であり、ｓｉ≠ｓｉ’のときｄｉ＝１である。
【００１４】
２つの距離ベクトル、すなわちＤ＝（ｄ１，ｄ２，ｄ３，ｄ４）およびＤ’＝（ｄ１’，ｄ２’，ｄ３’，ｄ４’）のサイズを比較する方法は、以下のように定義される。
【００１５】
ｄ１＝ｄ１’、ｄ２＝ｄ２’、ｄ３＝ｄ３’、ｄ４＝ｄ４’のとき、Ｄ＝Ｄ’であり、
ｄ１＝１、ｄ１’＝０のとき、
ｄ１＝ｄ１’、ｄ２＝１、ｄ２’＝０のとき、
ｄ１＝ｄ１’、ｄ２＝ｄ２’、ｄ３＝１、ｄ３’＝０のとき、または
ｄ１＝ｄ１’、ｄ２＝ｄ２’、ｄ３＝ｄ３’、ｄ４＝１、ｄ４’＝０のとき、Ｄ＞Ｄ’である。
【００１６】
距離ベクトルＤが小さいほど、２つのノードのネットワーク上での近接度は高くなる。
【００１７】
トポロジサーバ内の位置情報テーブルは、表１に示すような、メトロポリタンエリアネットワークのトポロジ情報を格納している。
【表１】
0005692757.tif 000002
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】ＣＮ１０１０１８１７２Ａ
【特許文献２】ＣＮ１０１２３７４６７Ａ
【非特許文献】
【００１９】
【非特許文献１】“Ｐ４Ｐ：Ｐｒｏｖｉｄｅｒ  Ｐｏｒｔａｌ  ｆｏｒ  Ａｐｐｌｉｃａｔｉｏｎｓ”（Ｐ４Ｐ：アプリケーション用プロバイダポータル）、Ｈａｉｙｏｎｇ  Ｘｉｅ，Ｙ．Ｒｉｃｈａｒｄ  Ｙａｎｇ，Ａｒｖｉｎｄ  Ｋｒｉｓｈｎａｍｕｒｔｈｙ，Ｙａｎｂｉｎ  Ｌｉｕ，Ａｖｉ  Ｓｉｌｂｅｒｓｃｈａｔｚ、Ｓｉｇｃｏｍｍ  ２００８
【非特許文献２】Ｖｉｖａｌｄｉ：Ａ  Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ｎｅｔｗｏｒｋ  Ｃｏｏｒｄｉｎａｔｅ  Ｓｙｓｔｅｍ（分散型ネットワーク座標系），Ｆｒａｎｋ  Ｄａｂｅｋ，ｅｔｃ、ｓｉｇｃｏｍｍ  ２００４
【非特許文献３】Ｐｒｅｄｉｃｔｉｎｇ  Ｉｎｔｅｒｎｅｔ  Ｎｅｔｗｏｒｋ  Ｄｉｓｔａｎｃｅ  ｗｉｔｈ  Ｃｏｏｒｄｉｎａｔｅｓ−Ｂａｓｅｄ  Ａｐｐｒｏａｃｈｅｓ（座標ベース方式によるインターネットネットワーク距離の予測），Ｔ．Ｓ．Ｅｕｇｅｎｅ  Ｎｇ  ｅｔｃ、Ｉｎｆｏｃｏｍ  ２００２
【発明の概要】
【発明が解決しようとする課題】
【００２０】
特許文献１において、Ｐ２Ｐネットワーク内のコンピュータの位置情報は、当該コンピュータのメトロポリタンエリアネットワーク内における特定の物理的位置として表現される。この物理的位置は、メトロポリタンエリアネットワーク内のスイッチまたはルータをコード化した上で、当該コンピュータからコアネットワークに至るまでに存在するスイッチおよびルータのコードでコンピュータの位置ベクトルを構成することにより、表現される。以下では、この表現を「階層的コード化ベースの位置情報表現」と呼ぶ。
【００２１】
この階層的コード化ベースの位置情報表現は、精度と拡張性の両面において限定的である。
【００２２】
ここでいう「精度」とは、システムから返されるノードが実際にネットワークで「近接」したノードであるかどうか、そして、このノード選択によってアプリケーションの性能だけでなくネットワークの利用効率も向上するかどうか、という意味における精度である。例えば、特許文献１で採用される階層的コード化方法は、階層ツリーの同じ階層に複数のノードが存在する場合には、これらのノードと要求元ノード間の距離を比較することはできない。図１に示す例においては、アクセススイッチの直下のノードがある特定のデータアイテムを保有する１０個のノードを要求し、かつこのアクセススイッチの直下にこのデータアイテムを保有するノードが４つ存在する場合には、これら４ノードが近接ノードとして選択される。それでもまだ、アクセススイッチが属する集約スイッチの下にはこのデータアイテムを保有するノードは９６も存在し、しかもその一部のノードはネットワーク上で要求元ノードに上記で選択された４ノードよりも近接しているにもかかわらず、階層的コード化方法ではこれら９６のノードと要求元ノード間の距離を比較することはできない。
【００２３】
ここでいう「拡張性」とは、システムをより大規模なネットワーク（ひいてはインターネット全体）に容易に拡張できるかどうか、という意味における拡張性である。階層的コード化ベースの位置情報表現方法は、トポロジ情報が完全に既知である（すなわち、各コンピュータがどのスイッチまたはルータを通ってコアネットワークに接続されているかが既知である）メトロポリタンエリアネットワークに適している。しかし、この方法をより大規模なネットワークやインターネット全体に拡張することは容易ではない。それは、ネットワークのあらゆる部分のトポロジ情報を知ることは非常に困難だからである。
【００２４】
さらに、階層的コード化ではほとんどの場合、位置情報を表現するために使用される階層数と、各階層で表現される情報とを事前設定する必要がある。例えば、特許文献１の方法では、位置情報は、集約スイッチ、アクセススイッチ、セルスイッチ、建物スイッチという４階層で表現される。これもまた、この方法の柔軟性と拡張性を制限する要因となる。
【課題を解決するための手段】
【００２５】
上記および他の問題を解決するため、本発明は、位置情報に基づいてノード情報を高精度で提供でき、かつ高い柔軟性と拡張性を有することを特徴とする、Ｐ２Ｐネットワーク内のサーバ、Ｐ２Ｐネットワーク内のノード情報を提供するための方法、およびＰ２Ｐネットワーク内のノード情報を提供するためのシステムを提供する。
【００２６】
本発明の１つの態様によれば、ピアツーピア（Ｐ２Ｐ）ネットワーク内のサーバであって、Ｐ２Ｐネットワーク内の各データノードの座標を、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示す座標情報を記憶する位置情報記憶手段と、第１のデータアイテムを保有するデータノードの情報を求める要求を受信すると、位置情報記憶手段内に記憶された座標情報に基づいて、第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択し、選択された１つ以上のデータノードを示す情報を提供するノード情報提供手段とを備えることを特徴とするサーバが提供される。
【００２７】
本発明の他の態様によれば、ピアツーピア（Ｐ２Ｐ）ネットワーク内のノード情報を提供する方法であって、第１のデータアイテムを保有するデータノードの情報を求める要求を受信するステップと、座標情報に基づいて、第１のデータアイテムを保有するデータノードの中から１つ以上のデータノードを選択するステップと、選択された１つ以上のデータノードを示す情報を提供するステップとを含み、当該座標情報は、Ｐ２Ｐネットワーク内の各データノードの座標を、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示すことを特徴とする方法が提供される。
【００２８】
本発明の他の態様によれば、ピアツーピア（Ｐ２Ｐ）ネットワーク内のノード情報を提供するためのシステムであって、データノードは、第１データアイテムを保有するデータノードの情報を求める要求をサーバに送信するノード情報要求手段と、サーバによって提供された情報に示されたデータノードと第１データアイテムを交換するデータ交換手段とを含み、サーバは、Ｐ２Ｐネットワーク内の各データノードの座標を、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成された座標系で示す座標情報を記憶する位置情報記憶手段と、第１データアイテムを保有するデータノードに関する情報に対する要求を前記データノードから受信すると、位置情報記憶手段に記憶された座標情報に基づいて、第１データアイテムを保有するデータノードの中から１つ以上のデータノードを選択し、選択された１つ以上のデータノードを示す情報を前記データノードに提供するノード情報提供手段とを含むことを特徴とするシステムが提供される。
【００２９】
本発明の他の目的、特徴、および利点は、以下の詳細な説明と図面を併せて参照することにより、明らかとなるであろう。
【発明の効果】
【００３０】
位置情報に基づいてノード情報を高精度で提供でき、かつ高い柔軟性と拡張性を有するＰ２Ｐネットワーク内のサーバ、Ｐ２Ｐネットワーク内のノード情報を提供する方法、およびＰ２Ｐネットワーク内のノード情報を提供するシステムが実現される。
【図面の簡単な説明】
【００３１】
【図１】従来技術の階層的コード化方法の概略図を示す。
【図２】本発明の第１の実施例によるシステムのブロック図を示す。
【図３】座標系に対して異なる粒度を選択する場合の概略図を示す。
【図４】本発明の第１の実施例によるシステムにおいて実行される方法のプロセスフローを示す。
【図５】本発明の第１の実施例によるシステムの具体的な実装を示すブロック図である。
【図６】図５に示すシステムにおいて実行される方法のプロセスフローを示す。
【図７】本発明の第２の実施例によるシステムのブロック図を示す。
【図８Ａ】本発明の第２の実施例によるノード情報記憶手段にノード情報テーブルを記憶するときの概略図を示す。
【図８Ｂ】本発明の第２の実施例によるノード情報提供手段がデータノードを順に選択するときの概略図を示す。
【図９】本発明の第２の実施例によるシステムにおいて実行される方法のプロセスフローを示す。
【図１０】本発明の第３の実施例によるシステムのブロック図を示す。
【図１１】本発明の第３の実施例によるシステムにおいて実行される方法のプロセスフローを示す。
【発明を実施するための形態】
【００３２】
最初に、本明細書で使用するいくつかの用語について説明する。
【００３３】
Ｐ２Ｐネットワーク：「Ｐ２Ｐシステム」ともいう。Ｐ２Ｐネットワークには、インデキシングサーバ（「トラッカ」または「ａｐｐＴｒａｃｋｅｒ」ともいう）、トポロジサーバ（「ｉＴｒａｃｋｅｒ」ともいう）、およびデータ交換を行う複数のデータノードなどが含まれる。これらのデータノードは互いにピア（同位）である。インデキシングサーバとトポロジサーバは論理的なカテゴリであり、総称して「サーバ」と呼ぶことができる。
【００３４】
データノード：「ノード」または「ホスト」ともいう。これは、Ｐ２Ｐネットワーク内のユーザ（マシン）である。データノードは、１つ以上の実データアイテムの全体または一部を記憶するエンティティである。データノードは、データアイテムを保有し、Ｐ２Ｐネットワーク内の他のデータノード（ピア）からデータアイテムをダウンロードする（ピアとデータアイテムを交換する）ことができる。データノードとして使用できるのは、データを記憶し、ネットワーク上で他のネットワークノードと通信することのできる、パーソナルコンピュータ（ＰＣ）、携帯電話、携帯情報端末（ＰＤＡ）等の情報処理装置である。
【００３５】
ピア：Ｐ２Ｐシステム内のデータノードは互いにピア接続される。
【００３６】
データアイテム：「データ」、「リソース」、「データファイル」等と呼ばれることもある。データアイテムは、音声ファイル、映像ファイル、テキストファイル等の、Ｐ２Ｐネットワーク内のデータノード間で共有されるリソースである。
【００３７】
ノード情報：サーバによって提供される、データアイテムＤを保有するノードの全部または一部を示す情報である。
【００３８】
位置情報：本発明においては、「位置情報」には、各データノードの座標を本発明による座標系で示す座標情報が含まれる。
【００３９】
データ情報：データノードからサーバに報告される情報であり、データノードがデータアイテムＤを保有することを示す。
【００４０】
性能情報：データ交換中またはデータ交換後にデータノードからサーバにフィードバックされる情報であり、データ交換の状態（通信遅延、帯域幅等）を示す。
【００４１】
Ｐ２Ｐネットワークは複数のデータノードを含むことがあるが、以下の説明では、これらのデータノードのうちの特定のデータノードＰ（後述するデータノード１０）を具体例として使用する。当該技術に精通する当業者には明らかなように、Ｐ２Ｐネットワーク内の他のデータノードはデータノードＰと同一または類似した構造のことがあり、データノードＰと同一または類似した方法でサーバと対話することができる。
【００４２】
以下では、添付図面を参照しながら本発明の実施例について説明する。本明細書および添付図面においては、同一または類似した要素を示すために同一または類似した参照記号を使用していることに注意されたい。また、同一要素を反復して説明することは避けている。
【００４３】
図２は、本発明の第１の実施例によるシステム１のブロック図を示す。図２に示すように、システム１はデータノード１０とサーバ２０とを備える。
【００４４】
ここでのデータノード１０は、Ｐ２Ｐネットワーク内の例示的なデータノードＰであり、ノード情報要求手段１０１とデータ交換手段１０２とデータ情報報告手段１０３とを含む。
【００４５】
サーバ２０は、ノード情報記憶手段２０１と位置情報記憶手段２０２とノード情報提供手段２０３とノード情報更新手段２０４とを含む。
【００４６】
データノード１０がＰ２Ｐネットワーク内の他のデータノード（すなわち、ピア）からデータアイテムＤ１をダウンロードする場合、まずＰ２Ｐネットワーク内のどのデータノードがデータアイテムＤ１を保有するかを知る必要がある。そのため、データノード１０のノード情報要求手段１０１は、データアイテムＤ１を保有するデータノードに関する情報を取得するために、ノード情報要求をサーバ２０に送信する。ここで、「データアイテムを保有する」とは、ダウンロード可能なデータアイテムの少なくとも一部を保有することを意味することに注意されたい。
【００４７】
サーバ２０のノード情報記憶手段２０１は、Ｐ２Ｐネットワーク内で共有されるすべてのデータアイテムに関するノード情報（すなわち、どのノードがどのデータアイテムを保有しているかについての情報）を記憶している。換言すれば、Ｐ２Ｐネットワーク内のデータノード間で共有される各データアイテムについて記憶されたノード情報は、そのデータアイテムを保有するＰ２Ｐネットワーク内のすべてのデータノードを示す。例えば、ノード情報記憶手段２０１は下記のノード情報テーブルのようなノード情報を記憶する。
【表２】
0005692757.tif 000003
【００４８】
位置情報記憶手段２０２は位置情報を記憶する。具体的には、本発明の位置情報は、Ｐ２Ｐネットワークの各データノードの座標を本発明による座標系で示す座標情報を含む。この座標系は、Ｐ２Ｐネットワーク内の少なくとも数個のデータノード間における通信遅延に基づいて生成される。換言すれば、位置情報記憶手段２０２はＰ２Ｐネットワーク全体に存在するすべてのノードの位置情報を座標として記憶する、ということができる。これは特許文献１の階層的コード化ベースの位置情報表現とは異なる。以下では、本発明による位置情報表現について説明する。
【００４９】
本発明においては、既知のＰ２Ｐネットワーク内のデータノード間における通信遅延に基づいて多次元ユークリッド座標系が確立され、任意のノード間の通信遅延を予測するために、座標がデータノードに割り当てられる。予測されたノード間の通信遅延は、ネットワーク上の近接度を表現するので、要求元ノードは、データアイテムをダウンロードするノードとして近接したノードを優先的に選択することができる。
【００５０】
本発明による座標系においては、インターネット内の各データノードは座標空間内の点として表される。例えば、３次元のユークリッド空間の場合であれば、ノードＰの座標はＣｐ＝（ｘｐ，ｙｐ，ｚｐ）である。２つのノード間の距離は、空間内の２つのデータノードを表わす２点間のユークリッド距離によって表現される。例えば、座標（ｘｐ，ｙｐ，ｚｐ）を有するノードＰと座標（ｘｑ，ｙｑ，ｚｑ）を有するノードＱ間の距離ｄは、以下のような式となる。
【数１】
0005692757.tif 000004
【００５１】
距離ｄが小さいほど、２つのノードの近接度は高くなる。
【００５２】
位置情報記憶手段２０２は、位置情報を位置情報テーブルとして記憶することができる。位置情報テーブルは、下記の表３に示すような、Ｐ２Ｐネットワーク内のノードに関する座標情報を格納する。
【表３】
0005692757.tif 000005
【００５３】
上記のノードＩＤは例として示したものである。
【００５４】
座標系は、Ｐ２Ｐネットワーク内のデータノード間の通信遅延に基づいて生成される。ここで、Ｐ２Ｐネットワーク内にＭ個のデータノード｛Ｈ１，…，ＨＭ｝があるとする（Ｍは１より大きい整数）。ノードＨｉおよびＨｊ間の通信遅延が測定され、それに基づいて距離Ｌｉｊが導出される。すべてのＬｉｊを使用して１つのＭ＊Ｍ行列が構成される。ここでの目的は、測定された通信遅延（すなわち、Ｌｉｊ）に基づく距離と、ユークリッド空間座標（「ｄｉｊ」とする）によって計算された距離の間の累積誤差が最小化されるように（すなわち、以下の目的関数のＦが最小化されるように）、各データノードの座標｛Ｃ１，…，ＣＭ｝を計算することである。
【数２】
0005692757.tif 000006
【００５５】
ここで、Ｅｒｒ（）は誤差関数である。例えば、以下のような誤差関数を選択することができる。
Ｅｒｒ（Ｌｉｊ，ｄｉｊ）＝（Ｌｉｊ−ｄｉｊ）２
【００５６】
Ｌｉｊ行列においては、座標計算は最適化問題である。この問題は、ｓｉｇｃｏｍｍ  ２００４で発表されたＶｉｖａｌｄｉ：Ａ  Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ｎｅｔｗｏｒｋ  Ｃｏｏｒｄｉｎａｔｅ  Ｓｙｓｔｅｍ（分散型ネットワーク座標系），Ｆｒａｎｋ  Ｄａｂｅｋ，ｅｔｃ（非特許文献２）に記載されるバネ力法（ｓｐｒｉｎｇ  ｆｏｒｃｅｓ  ｍｅｔｈｏｄ）や、Ｉｎｆｏｃｏｍ  ２００２で発表されたＰｒｅｄｉｃｔｉｎｇ  Ｉｎｔｅｒｎｅｔ  Ｎｅｔｗｏｒｋ  Ｄｉｓｔａｎｃｅ  ｗｉｔｈ  Ｃｏｏｒｄｉｎａｔｅｓ−Ｂａｓｅｄ  Ａｐｐｒｏａｃｈｅｓ（座標ベース方式によるインターネットネットワーク距離の予測），Ｔ．Ｓ．Ｅｕｇｅｎｅ  Ｎｇ  ｅｔｃ（非特許文献３）に記載される簡易ダウンヒル法等の、既存の研究によってほぼ解決できる。
【００５７】
ただし、実際の使用においては、幅広いネットワーク測定には膨大な費用がかかるため、座標系の最初の確立時に通信遅延を測定できるのは、ノードのごく一部に限られる。そのため、Ｌｉｊによって形成されたＭ＊Ｍ行列においては、当初は多数のＬｉｊが値を持たない。そして、システムの稼働を続ける過程で、通信遅延情報が測定および取得されて値が増えていくのである。具体的な座標系構築方法（すなわち、各ノードの座標値Ｃを計算する方法）は以下のとおりである（非特許文献２のバネ力法を例にとる）。
【００５８】
（１）システムのＭ個のノード｛Ｈ１，…，ＨＭ｝から、以下の２つの特徴を持つＩ個のランドマークノード｛Ｋ１，…，ＫＩ｝を選択する。
【００５９】
ａ．これらのノードＫｉ，１≦ｉ≦Ｉは、可能な最大数の他データノードＨｊ，１≦ｊ≦Ｍを用いて測定された通信遅延値（すなわち、可能な最大数の他データノードＨｊ，１≦ｊ≦Ｍを用いて測定された距離Ｌｉｊ）を有するため、可能な最大数の近隣ノードを有する。
【００６０】
ｂ．これらのノードは、座標空間内で可能な限り広く分散している。これは、Ｋｉ，１≦ｉ≦ＩおよびＫｊ，１≦ｊ≦Ｉ間の距離（Ｌｉｊ）が最大限に大きい、という具体的事実によって示される。
【００６１】
（２）非特許文献２のバネ力法により、Ｉ個のランドマークノード間の測定通信遅延ベース距離Ｌｉｊを用いて、Ｉ個のランドマークノードＫｊ，１≦ｊ≦Ｉの座標Ｃ（Ｋｉ）を計算する。
【００６２】
（３）他のＲ＝Ｍ−Ｉ個のノード｛Ｎ１，…，ＮＲ｝に関して座標を計算する。各ノードＮｉにつき、以下を行う。
【００６３】
ａ．非特許文献２のバネ力法により、当該ノードＮｉとＩ個のランドマークノードＫｊ，１≦ｊ≦Ｉの間の測定通信遅延ベース距離Ｌｉｊを用いて、当該ノードの座標ＣＩを計算する。
【００６４】
ｂ．次に、非特許文献２のバネ力法により、当該ノードに比較的近い（すなわち、当該ノードとのＬｉｊが比較的小さい）ノードと当該ノードＮｉの間の測定通信遅延ベース距離Ｌｉｊを用いてＣＩを更新し、座標空間内における当該ノードの正確な位置、すなわちＮｉの座標Ｃ（Ｎｉ）、を導出する。
【００６５】
図２に戻ると、ノード情報提供手段２０３は、データノード１０からノード情報要求を受信した後、位置情報記憶手段２０２に記憶された座標情報に基づいて、ノード情報記憶手段２０１に記憶されたノード情報によって示されるデータアイテムＤ１を保有するデータノードの中から１つ以上のデータノードを選択し、選択された１つ以上のデータノードを示す情報をデータノード１０に提供する。
【００６６】
具体的には、ノード情報提供手段２０３は要求を受信すると、ノード情報記憶手段２０１内のデータアイテムＤ１を保有するすべてのデータノード（例えば、Ｔ個のノード｛Ｐ１，…，ＰＴ｝）を検索する。ノード情報提供手段２０３はその後、例えばノードＩＤやノードのサブネットＩＰアドレスを用いて、位置情報記憶手段２０２内の、データアイテムＤ１を有するこれらのデータノード｛Ｐ１，…，ＰＴ｝の各々の座標とデータノード１０の座標とを検索する。次に、ノード情報提供手段２０３は、検索された座標に基づいて、データアイテムＤ１を保有する各データノードとデータノード１０との間の距離を計算する。その後、ノード情報提供手段２０３は、計算された距離の昇順に基づいて、データアイテムＤ１を保有するすべてのデータノードの中からいくつかのデータノード（例えば、Ｓ個のノード｛Ｐｉ１，…，Ｐｉｓ｝）を選択する。本発明においては、選択されるデータノード数Ｓを事前に決定することも、あるいはデータノード１０またはサーバ２０によって任意の数に指定することもできる。また、「距離が所定のしきい値を下回る」という条件を設定し、この条件を満足するすべてのデータノードが選択されるようにすることもできる。これらはすべて当業者にはよく知られている方法である。選択されたこれらのデータノードは、データノード１０に最も近接したデータノードである。ノード情報提供手段２０３はその後、選択された近接データノードをデータノード１０に通知する。
【００６７】
データノード１０内のノード情報要求手段１０１は、サーバ２０から通知された情報を受信すると、その情報をデータ交換手段１０２に伝える。データ交換手段１０２はその後、サーバ２０から提供された情報に示される近接データノードからデータアイテムＤ１をダウンロード（または、近接データノードとデータアイテムＤ１を交換）する。
【００６８】
データノード１０（すなわち、ノードＰ）はさらに、図示するように、データ情報報告手段１０３も含む。データノード１０がＰ２Ｐネットワーク内の他のデータノードと交換できるデータアイテムＤ２を保有している場合には、サーバ２０およびＰ２Ｐネットワーク内の他のデータノードがこの情報を学習できるように、データ情報報告手段１０３はサーバ２０に対し、データノード１０がデータアイテムＤ２（例：｛Ｄ２：Ｐ｝）を保有することを示すデータ情報を報告する。
【００６９】
そのため、サーバ２０はノード情報更新手段２０４も含む。ノード情報更新手段２０４は、データノード１０のデータ情報報告手段１０３から報告されてきたデータ情報を受信すると、受信した情報（例：｛Ｄ２：Ｐ｝）をノード情報記憶手段に格納されるノード情報に追加して、そのノード情報を更新する。例えば、この情報を追加されたノード情報テーブルは、下記の表４のようになる（太字は追加されたエントリ）。
【表４】
0005692757.tif 000007
【００７０】
前述したように、本発明による座標系を確立するために、データノードの地理的な位置情報（このノードが所在する国や都市等）や、他のネットワークトポロジ情報（ユーザコンピュータからコアネットワークに至るまでに存在するスイッチまたはルータ等）の知識は不要である。その代わりに、測定されたノード間の通信遅延情報に基づいて、ノードの座標が決定される。
【００７１】
さらに、特許文献１の従来技術とは異なり、座標系は非階層的である。すなわち、座標の複数次元を使用して異なるレベルの情報（国、都市等）や異なるタイプの情報（アクセススイッチ、セルスイッチ等）を表わすのではなく、座標の次元はすべて並列である。そのため、レベルの数と、各レベルが表す情報を事前に設定する必要はない。
【００７２】
本発明による位置情報表現方法は、従来技術よりも高い精度と拡張性を実現する。ある２つのノード間について予測された通信遅延は、ネットワーク上におけるこれらのノード間の近接度を表現する。ファイルをダウンロードする際には、近接したデータノードが優先的に選択される。そのため、ダウンロードの性能が向上し、無作為ノード選択によって生じる大量なネットワーク間トラフィックが回避される。座標系は測定により得られるノード間通信遅延情報に基づいた計算によって確立されるため、データノードに関する地理的位置情報や他のネットワークトポロジ情報を知る必要はない。したがって、座標系は高い拡張性を有し、メトロポリタンエリアネットワークや自律システム（ＡＳ）、ひいてはインターネット全体にも適用することができる。また、座標系は非階層的なので、レベル数と、各レベルによって表される情報とを事前に設定する必要はない。そのため、使用上の柔軟性と利便性も向上する。
【００７３】
さらに、システムをインターネット全体に拡張する際には、ネットワーク毎に座標系の粒度を柔軟に選択することができる。図３に示すように、既知の情報が多い（通信遅延の測定が可能な範囲が広い）ネットワークの場合は粒度の細かい座標を使用し、既知の情報が少ないネットワークの場合は粒度の粗い座標を使用することができる。
【００７４】
図４は、本発明の第１の実施例によるシステム１において実行される方法のプロセスフローを示す。
【００７５】
図４に示すように、データノード１０とサーバ２０間の対話は、データ情報を報告する第１の部分とノード情報を提供する第２の部分との２部構成とすることができる。
【００７６】
データ情報を報告する第１の部分では、ステップＳ１１０において、データノード１０がＰ２Ｐネットワーク内の他のデータノードと交換できるデータアイテムＤ２を保有している場合には、データ情報報告手段１０３が、データノード１０がデータアイテムＤ２を保有していることを示すデータ情報をサーバ２０に報告する。
【００７７】
続いてステップＳ１２０において、サーバ２０のノード情報更新手段２０４が、データノード１０のデータ情報報告手段１０３から報告されてきた情報の受信後、受信した情報を反映するために、ノード情報記憶手段２０１に格納されるノード情報を更新する。
【００７８】
ノード情報を提供する第２の部分では、ステップＳ２１０において、データノード１０のノード情報要求手段１０１が、データアイテムＤ１を保有するデータノードに関する情報を取得するために、ノード情報要求をサーバ２０に送信する。
【００７９】
ノード情報提供手段２０３は、データノード１０からノード情報要求を受信すると、ステップＳ２２０において、ノード情報記憶手段２０１内のデータアイテムＤ１を保有するすべてのデータノードを検索する。
【００８０】
その後、ノード情報提供手段２０３はステップＳ２３０において、位置情報記憶手段２０２内で、データアイテムＤ１を保有する各データノードすべての座標とデータノード１０の座標とを検索し、検索した座標に基づいて、データアイテムＤ１を保有する各データノードとデータノード１０間の距離を計算する。
【００８１】
次に、ノード情報提供手段２０３はステップＳ２４０において、計算した距離の昇順に基づいて、データアイテムＤ１を保有するすべてのデータノードの中から１つ以上のデータノードを選択する。選択されたこれらのデータノードは、データノード１０に最も近接したデータノードである。
【００８２】
次にステップＳ２５０において、ノード情報提供手段２０３は、選択された近接データノードをデータノード１０に通知する。
【００８３】
当該技術に精通した当業者には明らかなように、上述した第１の部分と第２の部分の相対的順序は一例にすぎない。例えば、データ情報の報告を行う第１の部分をノード情報の提供を行う第２の部分の後に実行したり、あるいは双方を並列で実行したりすることも可能である。また、データ情報を報告するデータノードとサーバから提供されたノード情報を受信するデータノードは異なるデータノードであってもよく、処理対象となるデータアイテムは同一のデータアイテムであっても異なるデータアイテムであってもよい。
【００８４】
図５は、本発明の第１の実施例によるシステム１の具体的な実装を示すブロック図である。
【００８５】
図５に示す具体的な実装では、サーバ２０はさらに、機能に応じて２つのサーバに分割されている。すなわち、サーバ２０はインデキシングサーバ２０−１とトポロジサーバ２０−２とを備える。こうした分割は概して論理的な機能上の分割であり、必ずしも物理的に分割する必要はない。例えば、インデキシングサーバ２０−１とトポロジサーバ２０−２とを物理的に同じ位置に置いて、１つのサーバに統合する、という実装も可能である。また、インデキシングサーバ２０−１とトポロジサーバ２０−２を別々に配置して２つの独立したサーバとする、という実装もありうる。
【００８６】
そのため、ノード情報提供手段２０３が、ノード検索手段２０３−１とノード選択手段２０３−２の両方を含むこともある。
【００８７】
さらに、ノード検索手段２０３−１とノード情報記憶手段２０１とノード情報更新手段２０４とを、インデキシングサーバ２０−１内にすべて含めることもできる。また、ノード選択手段２０３−２と位置情報記憶手段２０２とをトポロジサーバ２０−２内に含めることも可能である。
【００８８】
データノード１０の構造は図２に示す構造と同一とすることができる。
【００８９】
ノード検索手段２０３−１は、データノード１０内のノード情報要求手段１０１からデータアイテムＤ１を保有するデータノードの情報を求める要求を受信すると、ノード情報記憶手段２０１内でデータアイテムＤ１を保有するデータノードを検索し、ノード選択手段２０３−２に対して、データアイテムＤ１を保有するデータノードの中からデータノード１０に近接した１つ以上のデータノードを選択するよう要求する。
【００９０】
ノード選択手段２０３−２は、ノード検索手段２０３−１からの要求の受信後、位置情報記憶手段２０２内でデータアイテムＤ１を保有する各データノードの座標とデータノード１０の座標とを検索し、検索した座標に基づいて、データアイテムＤ１を保有する各データノードとデータノード１０との間の距離を計算し、計算した距離の昇順に基づいてデータアイテムＤ１を保有するデータノードの中から１つ以上のデータノードを選択し、選択した１つ以上のデータノードをノード検索手段２０３−１に通知する。
【００９１】
ノード検索手段２０３−１は、選択された１つ以上のデータノードを示す情報を、データノード１０のノード情報要求手段１０１に提供する。
【００９２】
図６は、図５に示すシステムにおいて実行される方法のプロセスフローを示す。
【００９３】
図６に示すデータ情報を報告するための第１の部分は、図４に示す第１の部分と実質的に同じであるため、その説明を書略する。また前述したように、第１の部分と第２の部分の順序は一例にすぎない。例えば、データ情報を報告する第１の部分をノード情報を提供する第２の部分の後に実行したり、あるいは２つの部分を並列で実行したりすることも可能である。また、データ情報を報告するデータノードとサーバから提供されたノード情報を受信するデータノードは異なるデータノードであってもよく、対象となるデータアイテムは同一のデータアイテムであっても異なるデータアイテムであってもよい。
【００９４】
ノード情報を提供する第２の部分では、ステップＳ２１０において、データノード１０のノード情報要求手段１０１が、データアイテムＤ１を保有するデータノードに関する情報を取得するために、ノード情報要求をサーバ２０に発行する。
【００９５】
ノード情報提供手段２０３のノード検索手段２０３−１は、データノード１０からノード情報要求を受信すると、ステップＳ２２０において、ノード情報記憶手段２０１内のデータアイテムＤ１を保有するすべてのデータノードを検索する。
【００９６】
ノード検索手段２０３−１は、次のステップＳ２２１において、ノード選択手段２０３−２に対してデータアイテムＤ１を保有するすべてのデータノードの中からいくつかのデータノードを選択するよう求めるために、ノード選択手段２０３−２に要求を発行する。
【００９７】
その後、ステップＳ２３０において、ノード選択手段２０３−２が位置情報記憶手段２０２内で、データアイテムＤ１を保有する各データノードの座標とデータノード１０の座標とを検索し、検索した座標に基づいて、データアイテムＤ１を保有する各データノードとデータノード１０間の距離を計算する。
【００９８】
次に、ノード選択手段２０３−２はステップＳ２４０において、計算した距離の昇順に基づいて、データアイテムＤ１を保有するすべてのデータノードの中から１つ以上のデータノードを選択する。選択されたこれらのデータノードは、データノード１０に最も近接したデータノードである。
【００９９】
次のステップＳ２４１において、ノード選択手段２０３−２は、選択した１つ以上のデータノードをノード検索手段２０３−１に通知する。
【０１００】
ステップＳ２５０において、ノード検索手段２０３−１はさらに、選択された近接データノードをデータノード１０に通知する。
【０１０１】
図７は、本発明の第２の実施例によるシステム１ａのブロック図を示す。
【０１０２】
第２の実施例によるシステム１ａは、データノード１０とサーバ２０ａとを備えるが、データノード１０は図２に示すデータノード１０と同じであってもよい。
【０１０３】
本発明の第２の実施例は、近接ノードを選択するための改良型アルゴリズムを適用する。ノードの選択において解決すべき問題は、ノードＰがデータアイテムＤ１を保有するノードを要求する際に、データアイテムＤ１を保有し、かつ要求元ノードＰに近接した位置にあるＳ個のノードをどのように検索するかということである。第１の実施例では、最初に、Ｐ２Ｐネットワーク内のデータアイテムＤ１を保有する全Ｔ個のノード｛Ｐ１，…，ＰＴ｝が検索され、その後、要求元ノードＰとデータアイテムＤ１を保有する各ノード｛Ｐ１，…，ＰＴ｝との間の距離ｄｉ＝距離（Ｐ，Ｐｉ）が計算され、最後に、Ｐに近接するノードとしてｄｉの昇順に基づいてＳ個のノードが選択されていた。このような方法は、Ｔ＞＞Ｓのときに効率的ではない。
【０１０４】
第２の実施例によれば、サーバ２０ａは、ノード情報記憶手段２０１ａと位置情報記憶手段２０２とノード情報提供手段２０３ａとノード情報更新手段２０４ａとを含む。
【０１０５】
ノード情報記憶手段２０１ａに記憶されるノード情報においては、各データアイテムを保有するデータノードは、座標系内にこれらデータノードの座標別に格納される。
【０１０６】
具体的には、第２の実施例において、位置情報はノード情報テーブルに格納される。すなわち、｛Ｐ１，…，ＰＴ｝がデータアイテムＤ１を保有すると想定すると、この情報がノード情報テーブル内に格納されるときには、ユークリッド空間内のこれらＴ個のノードの位置の順序に従って格納される。要求元ノードＰの近接ノードを探索する際には、Ｐの座標を起点として、ユークリッド空間内におけるＰの隣接ノードが検索される。このように、Ｔ個のノードが比較されるのではなく、約Ｓ個のノードがアクセスされ比較されるので、Ｔ＞＞Ｓの場合には近接ノードを検索する速度が大幅に向上する。
【０１０７】
下記の表５は、２次元ユークリッド空間の場合のノード情報テーブルの例を示す。この表に示すように、本実施例によるノード情報テーブルは、各ノードの座標情報を含む。
【表５】
0005692757.tif 000008
【０１０８】
図８Ａは、本実施例によるノード情報記憶手段２０１ａにノード情報テーブルを記憶するときの概略図を示す。図８Ａに示すように、データアイテムＤ１を保有する全ノードの情報は各次元の座標順に格納される。データアイテムＤ１に対しては、例えば、データアイテムＤ１を保有するすべてのノードのｘおよびｙ座標と、それに対応するノードへのポインタとを格納するために、ｘ［］およびｙ［］という２つの配列を設けることができる。例えば、配列ｘ［］のｉ番目の要素は、データアイテムＤ１を保有する全ノードのｘ座標においてｉ番目のｘ座標であるｘｉと、データアイテムＤ１を保有するノードのうちｘｉというｘ座標を有する全ノードの情報への１つ以上のポインタを格納する。同様に、配列ｙ［］のｊ番目の要素は、データアイテムＤ１を保有する全ノードのｙ座標においてｊ番目のｙ座標であるｙｊと、データアイテムＤ１を保有するノードのうちｙｊというｙ座標を有する全ノードの情報への１つ以上のポインタを格納する。
【０１０９】
ノード情報更新手段２０４ａは、データノード（例：データノード１０）から報告された、データアイテム（例：データアイテムＤ２）を有することについての情報の受信後、まず位置情報記憶手段２０２内においてデータノード１０の座標を検索し、次に検索した座標に基づいて、受信した情報とノードの座標とを、ノード情報記憶手段に記憶されるノード情報へ当該ノードの情報として追加する。そのため、元のノード情報テーブルは、当該ノードの情報を追加された後も上記の形のまま座標内に格納されている。さらに、ノード情報提供手段２０３ａは、データノード（例：データノード１０、すなわちノードＰ）からデータアイテム（例：データアイテムＤ１）を保有するデータノードの情報を求める要求を受信後、位置情報記憶手段２０２内でデータノード１０の座標を検索し、このデータノード１０の座標を起点として、ノード情報記憶手段２０１ａ内に記憶されたノード情報にリストされるデータアイテムＤ１を保有するデータノードの中から、座標系のデータノードを順に選択する。図８Ｂはノード情報提供手段２０３ａがデータノードを順に選択するときの概略図を示す。（６，７）の座標を有するノードＰが、データアイテムＤ１を保有するＳ＝５のノードを要求したと想定すると、例えば図８Ａに示すような形式でノード情報を記憶するノード情報記憶手段２０１ａ内において、ノード情報提供手段２０３ａはノードＰの座標から開始して、各次元の２つの方向に沿って検索の範囲を徐々に拡張していく。このとき検索された範囲内に存在するノードが、ノードＰの隣接ノードである。十分な数の隣接ノードが検索されたとき（例えば、ノード数が指定された数に達したとき、または距離がしきい値に達したとき等）、検索範囲の拡張は停止される。
【０１１０】
例えば、ノード情報提供手段２０３ａは最初に、上記のｘ［］配列内にｘ座標＝６を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝７を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（６，７）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１１】
次に、ノード情報提供手段２０３ａは、ｘ［］配列内にｘ座標＝６を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝６を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（６，６）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１２】
その後、ノード情報提供手段２０３ａは、ｘ［］配列内にｘ座標＝６を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝８を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（６，８）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１３】
続いて、ｘ［］配列内にｘ座標＝５を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝７を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（５，７）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１４】
さらに、ｘ［］配列内にｘ座標＝７を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝７を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（７，７）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１５】
さらに、ｘ［］配列内にｘ座標＝５を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝６を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（５，６）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示すように、この時点でノードＰ１（５，６）が発見される。よって、このノードが、ノードデータアイテムＤ１を保有し、ノードＰに最も近接したノードとして選択される。
【０１１６】
さらに、ｘ［］配列内にｘ座標＝５を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝８を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（５，８）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１７】
続いて、ｘ［］配列内にｘ座標＝７を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝６を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（７，６）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示す例では、このようなノードは存在しない。
【０１１８】
さらに、ｘ［］配列内にｘ座標＝７を格納する要素が存在し、同時にｙ［］配列内にｙ座標＝８を格納する要素が存在し、かつこれら２つの要素に格納されているポインタが同じノードをポイントしているかどうかをチェックする。この条件が満足される場合、それは、データアイテムＤ１を保有し、かつ座標（７，８）を有するもう１つのノードが存在することを意味し、このノードが選択可能である。図８Ａと図８Ｂに示すように、この時点でノードＰ２（７，８）が発見される。よって、このノードが、データアイテムＤ１を保有し、ノードＰに近接したノードとして選択される。
【０１１９】
同様にして、ノードＰ４（５，９）、Ｐ７（１０，８）、およびＰ９（４，１１）が順に発見される。この時点で、データアイテムＤ１を保有し、かつノードＰに比較的近接したノードとして、計５個のノードが発見されたことになる。その後、これら５ノードの情報が、要求を発行したデータノードＰに返すノード情報に含められる。
【０１２０】
前述したように、ノード情報記憶手段２０１ａに記憶されるノード情報テーブルには、各次元の座標値の順序に従ってノードが格納されている。そのため、指定されたノードに隣接するノードを簡単に発見することができる。
【０１２１】
図９は、本発明の第２の実施例によるシステム１ａにおいて実行される方法のプロセスフローを示す。
【０１２２】
図４と同様に図９でも、データノード１０とサーバ２０ａ間の対話は、データ情報を報告する第１の部分とノード情報を提供する第２の部分との２部構成となっている。
【０１２３】
データ情報を報告する第１の部分では、ステップＳ１１０において、データノード１０がＰ２Ｐネットワーク内の他のデータノードと交換できるデータアイテムＤ２を保有している場合には、データ情報報告手段１０３が、データノード１０がデータアイテムＤ２を保有していることを示すデータ情報をサーバ２０ａに報告する。
【０１２４】
続いてステップＳ１２１において、サーバ２０ａのノード情報更新手段２０４ａが、データノード１０のデータ情報報告手段１０３から報告されてきた情報の受信後、データノード１０の位置情報、すなわち座標Ｃ（Ｐ）を、位置情報記憶手段２０２に格納する。
【０１２５】
ステップＳ１２２において、ノード情報更新手段２０４ａは、検索された座標に従って、受信した情報をノード情報記憶手段に記憶されるノード情報に追加する。このとき、データアイテムＤ２を有するデータノードの中で、データノード１０がその座標に基づいて配置されるようにする。
【０１２６】
第２の部分では、ステップＳ２１０においてノード情報提供手段２０３ａが、データノード１０から送られてきた、データアイテムＤ１を保有するデータノードに関する情報を取得するための要求を受信すると、ステップＳ２４１においてノード情報提供手段２０３ａが、位置情報記憶手段２０２内でデータノード１０の座標Ｃ（Ｐ）を検索する。
【０１２７】
ステップＳ２４２において、ノード情報提供手段２０３ａが、データノード１０の座標を起点として、ノード情報記憶手段２０１ａに記憶されたノード情報にリストされるデータアイテムＤ１を保有するデータノードからデータノードを順に選択する。
【０１２８】
ステップＳ２５０において、ノード情報提供手段２０３ａは、選択されたデータノードをデータノード１０に通知する。
【０１２９】
ここでも、当該技術に精通した当業者には明らかなように、上述した第１の部分と第２の部分の相対的順序は一例にすぎない。例えば、データ情報を報告する第１の部分をノード情報を提供する第２の部分の後に実行したり、あるいは２つの部分を並列で実行したりすることも可能である。また、データ情報を報告するデータノードとサーバから提供されたノード情報を受信するデータノードは異なるデータノードであってもよく、対象となるデータアイテムは同一のデータアイテムであっても異なるデータアイテムであってもよい。
【０１３０】
図１０は、本発明の第３の実施例によるシステム１ｂのブロック図を示す。
【０１３１】
座標系の最初の確立時に通信遅延を測定できるのは一部のノードのみであり、その後のシステムの稼働を続ける過程で、通信遅延情報が測定および取得されて値が増えていく。そのため、ネットワークの状態に応じて位置情報テーブルを更新することができる。ある方法では、ノードが性能情報（通信遅延、帯域幅等）を収集するステップと、データ交換の状態を反映するステップと、ノードの位置情報を更新するためにサーバにそれをフィードバックするステップとを含む。
【０１３２】
第３の実施例によるシステム１ｂは、データノード１０ｂとサーバ２０ｂとを含む。
【０１３３】
データノード１０ｂは、ノード情報要求手段１０１、データ交換手段１０２、およびデータ情報報告手段１０３に加えて、性能情報フィードバック手段１０４を含む。
【０１３４】
性能情報フィードバック手段１０４は、データノード１０ｂと他のデータノードとの間のデータアイテム交換の状態を示す性能情報を収集し、それをサーバ２０ｂにフィードバックする。性能情報とは、データノード１０ｂと他のデータノードとの間のデータアイテム交換中に取得された性能統計情報であり、これには例えば通信遅延や帯域幅等が含まれる。
【０１３５】
そのため、サーバ２０ｂは位置情報更新手段２０５も含む。位置情報更新手段２０５は、データノード１０ｂの性能情報フィードバック手段１０４からフィードバックされた情報を受信後、受信した情報に基づいて位置情報記憶手段２０２に記憶された座標情報を更新する。受信された情報に含まれる通信遅延に基づいて座標情報を更新する方法は、前述した通信遅延に基づいて座標情報を計算する方法と同様である。
【０１３６】
図１１は、本発明の第３の実施例によるシステム１ｂにおいて実行される方法のプロセスフローを示す。
【０１３７】
図１１に示すように、データノード１０ｂとサーバ２０ｂ間の対話は、データ情報を報告する第１の部分と、ノード情報を提供する第２の部分と、位置情報を更新する第３の部分という３つに分割することができる。
【０１３８】
第１の部分と第２の部分は図９と同じなので、以下では説明を省略する。
【０１３９】
第３の部分では、ステップＳ３１０において、性能情報フィードバック手段１０４が、データノード１０ｂと他のデータノードとの間のデータアイテム交換の状態を反映した性能情報を収集する。
【０１４０】
ステップＳ３２０において、性能情報フィードバック手段１０４は、収集した性能情報をサーバ２０ｂにフィードバックする。
【０１４１】
ステップＳ３３において、サーバ２０ｂの位置情報更新手段２０５は、サーバ２０ｂの性能情報フィードバック手段１０４からフィードバックされた情報を受信後、受信した情報に基づいて位置情報記憶手段２０２に記憶された座標情報を更新する。
【０１４２】
ここでも、当該技術に精通した当業者には明らかなように、上述した第１の部分、第２の部分、および第２の部分の相対的順序は一例にすぎない。第１の部分、第２の部分、および第３の部分は、他の順序で実行することも、あるいは並列で実行することも可能である。また、データ情報を報告するデータノード、サーバから提供されたノード情報を受信するデータノード、および性能情報をフィードバックするノードは異なるデータノードであってもよく、対象となるデータアイテムは同一のデータアイテムであっても異なるデータアイテムであってもよい。
【０１４３】
上記では本発明の特定の実施例をいくつか取り上げて説明したが、本発明には様々な修正、組み合わせ、改変をなすことが可能であり、これらの修正、組み合わせ、改変は付記された請求項の範囲内にある限りにおいて本発明に含まれることは、当業者に理解されるであろう。
【０１４４】
例えば、図５には第１の実施例による特定の実装を示しているが、こうした特定の実装は第２の実施例や第３の実施例にも同様に適用することができる。
【符号の説明】
【０１４５】
１０１：ノード情報要求手段
１０２：データ交換手段
１０３：データ情報報告手段
２０１：ノード情報記憶手段
２０２：位置情報記憶手段（座標系）
２０３：ノード情報提供手段
２０４：ノード情報更新手段
１０：ノードＰ
２０：サーバ
２０３−１：ノード検索手段
２０３−２：ノード選択手段
２０−１：インデキシングサーバ
２０−２：トポロジサーバ
２０１ａ：ノード情報記憶手段（座標情報の詳細を示す）
２０３ａ：ノード情報提供手段
２０４ａ：ノード情報更新手段
２０ａ：サーバ
１０４：性能情報フィードバック手段
２０５：位置情報更新手段
１０ｂ：ノードＰ
２０ｂ：サーバ
【図１】
0005692757.tif 000012
【図２】
0005692757.tif 000013
【図３】
0005692757.tif 000014
【図４】
0005692757.tif 000015
【図５】
0005692757.tif 000016
【図６】
0005692757.tif 000017
【図７】
0005692757.tif 000018
【図８Ａ】
0005692757.tif 000019
【図８Ｂ】
0005692757.tif 000020
【図９】
0005692757.tif 000021
【図１０】
0005692757.tif 000022
【図１１】
0005692757.tif 000023