(57)【要約】【課題】ネットワークの近傍性情報を用いながら、ピアの論理識別子の分布を均一にし、特定のピアに負荷が偏らないオーバレイネットワークを構築することを目的とする。【解決手段】各ピアが、オーバレイネットワークに参加する場合に、ピア参加手段４１５が受け付ける参加要求の指示にもとづいて、ネットワーク計測手段４１６が複数のランドマーク４５０，４６０，４７０に対する通信の応答時間を測定し、座標計算手段４１７が取得した応答時間にもとづいて当該ピアの多次元の位置情報（座標）を算出し、空間充填曲線変換手段４１８が空間充填曲線を用いて多次元の位置情報を一次元の位置情報に変換し、空間分布関数適用手段４１９が一次元の位置情報に空間分布関数を適用して均一化された一次元の情報を取得する。そして、ピア参加手段４１５が一次元の情報と論理識別子空間の積をとることによって当該ピアの論理識別子を決定する。【選択図】図１
2008269141.tif 000002
【特許請求の範囲】
【請求項１】
オーバレイネットワーク上に配置され、他の装置と共有するデータを検索するオーバレイ検索装置であって、
他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得手段と、
取得された前記ネットワーク特性をもとづいて当該オーバレイ検索装置の位置情報を算出する位置情報算出手段と、
算出された前記位置情報に対して複数のオーバレイ検索装置の位置情報に関する分布関数を適用して前記位置情報を均一化する分布関数適用手段と、
均一化された情報にもとづいて当該オーバレイ検索装置に割り当てる論理識別子を算出する論理識別子算出手段とを備えた
ことを特徴とするオーバレイ検索装置。
【請求項２】
多次元データを一次元データに変換する次元変換手段を備え、
位置情報算出手段は、ネットワーク特性をもとづいて当該オーバレイ検索装置の多次元の位置情報を算出し、
前記次元変換手段は、算出された多次元の位置情報を一次元の位置情報に変換し、
分布関数適用手段は、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換する
請求項１記載のオーバレイ検索装置。
【請求項３】
次元変換手段は、空間充填曲線を用いて多次元データを一次元データに変換する
請求項１または請求項２記載のオーバレイ検索装置。
【請求項４】
オーバレイネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを検索するオーバレイ検索システムであって、
前記各端末は、
他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得手段と、
取得された前記ネットワーク特性をもとづいて当該端末の位置情報を算出する位置情報算出手段と、
算出された前記位置情報に分布関数を適用して前記位置情報を均一化する分布関数適用手段と、
均一化された情報にもとづいて当該端末に割り当てる論理識別子を算出する論理識別子算出手段とを備えた
ことを特徴とするオーバレイ検索システム。
【請求項５】
オーバレイネットワーク上に配置された、他の装置とデータを共有する端末の制御部が、
他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得ステップと、
取得された前記ネットワーク特性をもとづいて当該端末の位置情報を算出する位置情報算出ステップと、
算出された前記位置情報に分布関数を適用して前記位置情報を均一化する分布関数適用ステップと、
均一化された情報にもとづいて当該端末に割り当てる論理識別子を算出する論理識別子算出ステップとを備えた
ことを特徴とするオーバレイ検索方法。
【請求項６】
多次元データを一次元データに変換する次元変換ステップを備え、
位置情報算出ステップにおいて、ネットワーク特性をもとづいて当該端末の多次元の位置情報を算出し、
前記次元変換ステップにおいて、算出された多次元の位置情報を一次元の位置情報に変換し、
分布関数適用ステップにおいて、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換する
請求項５記載のオーバレイ検索方法。
【請求項７】
次元変換ステップにおいて、空間充填曲線を用いて多次元データを一次元データに変換する
請求項５または請求項６記載のオーバレイ検索方法。
【請求項８】
オーバレイネットワーク上に配置されたコンピュータが他のコンピュータと共有するデータを検索するためのオーバレイ検索用プログラムであって、
他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得処理と、
取得された前記ネットワーク特性をもとづいて当該コンピュータの位置情報を算出する位置情報算出処理と、
算出された前記位置情報に分布関数を適用して前記位置情報を均一化する分布関数適用処理と、
均一化された情報にもとづいて当該コンピュータに割り当てる論理識別子を算出する論理識別子算出処理とを
コンピュータに実行させるためのオーバレイ検索用プログラム。
【請求項９】
多次元データを一次元データに変換する次元変換処理をもコンピュータに実行させ、
位置情報算出処理において、ネットワーク特性をもとづいて当該端末の多次元の位置情報を算出させ、
前記次元変換処理において、算出された多次元の位置情報を一次元の位置情報に変換させ、
分布関数適用処理において、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換させる
請求項８記載のオーバレイ検索用プログラム。
【請求項１０】
次元変換処理において、空間充填曲線を用いて多次元データを一次元データに変換させる
請求項８または請求項９記載のオーバレイ検索用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上における他の装置と共有するデータを検索するオーバレイ検索装置、オーバレイ検索システム、オーバレイ検索方法およびオーバレイ検索プログラムに関し、特に、ネットワークの近傍性情報を考慮して論理識別子を割り当てるオーバレイ検索装置、オーバレイ検索システム、オーバレイ検索方法およびオーバレイ検索用プログラムに関する。
【背景技術】
【０００２】
オーバレイネットワークは、既存のリンクを用いて、その上位層における目的に応じて仮想的なリンクを形成し構成するネットワークである。すなわち、コンピュータネットワークの下位層のトポロジーとは関係なく構築された上位層のネットワークをオーバレイ・ネットワークと呼ぶ。例えば、ＩＰネットワークのトポロジーとは無関係に構築されたＰ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）ネットワークなどを指す。
【０００３】
オーバレイネットワークでは、中央サーバを必要とせず、容易に柔軟な耐故障性に優れたネットワークを構築できる。ノード（ピアともいう）は自由に参加・離脱を行い、ネットワークトポロジは動的に変化する。全てのノードに対等の権限が与えられ、ネットワークに接続されている全てのノードが持つデータにアクセスすることが可能となる。
【０００４】
オーバレイネットワークにおいて、各ノードが隣接するノードの情報（ＩＰアドレス等）のみを持つ場合は、データを検索する方法として、隣接するノードに問合せ（クエリ）をリレーで渡していく方法が採られることになる。このような検索方法の場合、検索用のネットワークトポロジを維持する必要がないためアドホック性に優れ、複製を利用することで耐故障性も優れているが、検索に時間がかかるためスケーラビリティに欠ける。一方、各ノードがネットワーク上の全てのノードの情報を持っている場合は、検索時間はかからないがスケーラビリティとアドホック性の点で適切でない。このように、オーバレイネットワーク（Ｐ２Ｐネットワーク）では、要求されたデータを持つノードをどのように検索するかが重要と問題となる。
【０００５】
オーバレイネットワーク上の各ノードに経路情報として分散ハッシュテーブル（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ：ＤＨＴ）を持たせることにより、膨大なデータを高速（効率的）に検索する手法が用いられている。分散ハッシュテーブルでは、データはハッシュ空間上に配置され、各ノードがある値域を担当して値域内に存在するデータを保持、管理する。所定のノードがキーを通じてデータの検索を行う場合、キーをハッシュ関でハッシュ値に変換してハッシュ空間にマッピングを行い、目的のノードとデータを取得する。多くのＤＨＴでは、ノードのＩＤを衝突なく均一にするために、一意性が担保された下位ネットワークのアドレス（ＩＰアドレスとポートの組み合わせなど）のハッシュ値をＩＤとして用いる。
【０００６】
しかし、分散ハッシュテーブルを利用したオーバレイネットワークでは、実際の物理ネットワーク上のノードの近さと分散ハッシュ空間上のノードの近さは無関係となっている。従って、オーバレイネットワーク上では無駄の無い検索ホップであっても、実際の物理ネットワークでは、一度遠くのネットワークに存在するノードまで検索が進んだ後、検索要求を行った（検索を開始した）ノードの近くのノードに検索が戻ってきてしまうような無駄が含まれる可能性がある。そこで、非特許文献１には、物理ネットワークの近傍性を考慮したオーバレイ検索システムの一例が記載されている。以下、非特許文献１に記載されたオーバレイ検索システムの構成について説明する。
【０００７】
図５は、従来のオーバレイ検索システムの構成を示すブロック図である。図５に示すように、従来のオーバレイ検索システムは、ネットワーク１００上でのアドレスを有する複数のピア１１０，１３０，１４０、および各ピア１１０，１３０，１４０がネットワーク計測の接続先として用いるランドマーク１５０，１６０，１７０から構成されている。なお、図５において、ピア１１０，１３０，１４０しか示されていないが、他の複数のピアもネットワーク１００に接続されている。
【０００８】
ピア１１０は、当該ピア１１０がオーバレイネットワークに参加するときに当該ピア１１０の論理識別子とルーティングテーブルを生成する処理を行うピア初期化部１１１と、検索対象のデータの登録処理およびデータの検索処理を行う登録・検索実行部１２０とを備えている。なお、ピア１３０，１４０も、ピア１１０と同一の構成を備えている。
【０００９】
ピア初期化部１１１は、図５に示すように、ランドマーク設定格納部１１２と、計測結果格納部１１３と、ネットワーク計測手段１１４と、近傍順序論理識別子決定手段１１５と、ルーティングテーブル生成手段１１６と、ピア参加手段１１７とを備えている。
【００１０】
ランドマーク設定格納部１１２には、当該ピア１１０がネットワーク計測（ランドマークとの応答時間の計測）を行うために必要なランドマーク１５０，１６０，１７０のアドレス等が格納される。計測結果格納部１１３には、当該ピアとランドマーク１５０，１６０，１７０との間の応答時間（ＲＴＴ：Ｒｏｕｎｄ  Ｔｒｉｐ  Ｔｉｍｅ）等が格納される。ネットワーク計測手段１１４は、ランドマーク設定格納部１１２に格納されているアドレスのランドマーク１５０，１６０，１７０に対して応答時間ＲＴＴの計測を行い、その計測結果を計測結果格納部１１３に格納する。
【００１１】
近傍順序論理識別子決定手段１１５は、計測結果格納部１１３からＲＴＴを取得し、取得したＲＴＴにもとづいてランドマークを順序づけ、この順序から後述する一意に決定可能な手法で当該ピアの論理識別子を決定する。ここで決定される論理識別子は、他のピア１３０，１４０とは異なる、オーバレイネットワークの中で一意な論理識別子である。
【００１２】
ルーティングテーブル生成手段１１６は、近傍順序論理識別子決定手段１１５によって決定（計算）された論理識別子をもとに、ルーティングテーブルを作成する。ルーティングテーブルとは、各ピアがメッセージのルーティングを行うときに参照するテーブルである。ルーティングテーブルには、当該ピアの接続先ピアの論理識別子とネットワークアドレス（例えばＩＰアドレス）とが格納されている。
【００１３】
ピア参加手段１１７は、当該システムの外部（外部インタフェース）からのオーバレイネットワークへの参加要求を受け付ける手段である。ピア参加手段１１７は、参加要求を受け付けると、ネットワーク計測手段１１４に対して計測結果を取得するように指示し、ネットワーク計測手段１１４によって取得された計測結果の情報をもとに論理識別子とルーティングテーブルを作成するように近傍順序論理識別子決定手段１１５とルーティングテーブル生成手段１１６に対して逐次指示を行う。
【００１４】
登録・検索実行部１２０は、図５に示すように、ピア論理識別子格納部１２６と、ローカルデータ格納部１２１と、ルーティングテーブル１２２と、メッセージ転送手段１２３と、通信手段１２４と、登録・検索実行手段１２５とを備えている。
【００１５】
ピア論理識別子格納部１２６には、近傍順序論理識別子決定手段１１５によって決定（算出）された論理識別子が格納される。ローカルデータ格納部１２１には、オーバレイネットワーク上における他のピア１３０，１４０と共有されるデータのうち、ピア１１０が管理するデータ（当該ピア１１０の論理識別子と関連する識別子を持つデータ）が格納される。ルーティングテーブル１２２には、ルーティングテーブル生成手段１１６によって生成されたルーティングテーブルが格納される。
【００１６】
メッセージ転送手段１２３は、当該ピア１１０の登録・検索実行手段１２５、あるいは他ピアのメッセージ転送手段１２３から渡されるメッセージ（検索要求のメッセージ）を、ピア論理識別子格納部１２６あるいはルーティングテーブル１２２を参照しながら、他ピアへのメッセージの転送あるいはローカルデータ格納部１２１からのデータ取得などを行う。通信手段１２４は、他ピアのネットワーク１００上でのアドレスを指定して、ネットワーク１００上にメッセージを送受信する処理を担う。これにより、他ピアとのネットワーク１００を介した通信が実行される。
【００１７】
登録・検索実行手段１２５は、当該システムの外部（外部インタフェース）からの要求によりデータの登録やデータの検索を受け付ける手段である。登録・検索実行手段１２５は、データの登録の要求を受け付けると、当該データを格納する先のピアを発見して、そのピアに対するデータ登録を指示するメッセージを発行し、そのメッセージをメッセージ転送手段１２３に受け渡す。また、登録・検索実行手段１２５は、データの検索の要求を受け付けると、当該データを格納しているピアを検索し、そのピアに対するデータ取得を指示するメッセージを発行し、そのメッセージをメッセージ転送手段１２３に受け渡す。
【００１８】
次に、従来のオーバレイ検索システムの動作について図５〜図７を参照して説明する。
【００１９】
ピア１１０において、ピア参加手段１１７は、外部からのオーバレイネットワークへのピア１１０の参加要求を受け付けると、ネットワーク計測手段１１４に対して計測結果を取得するように指示する。ネットワーク計測手段１１４は、ピア参加手段１１７からの計測結果の取得の指示を受けると、ランドマーク設定格納部１１２に格納されているアドレスのランドマーク１５０，１６０，１７０に対して応答時間ＲＴＴの計測を行う。例えば、ネットワーク計測手段１１４が、各ランドマーク１５０，１６０，１７０のアドレスにメッセージを送信すると同時に計測を開始し、各ランドマーク１５０，１６０，１７０からのメッセージに対する応答メッセージを受信した時点で計測を停止する。このような処理により、メッセージを送信してから応答メッセージを受信するまでの時間を応答時間として計測することが可能となる。そして、ネットワーク計測手段１１４は、応答時間の計測結果を計測結果格納部１１３に格納する。
【００２０】
ここで、図５に示すランドマークＡ１５０の応答時間が２３２ｍｓ、図５に示すランドマークＢ１６０の応答時間が５１ｍｓ、図５に示すランドマークＣ１７０の応答時間が１７ｍｓであるものとする。
【００２１】
図６は、オーバレイネットワークに参加しているピアとランドマークの物理的ネットワーク上における配置例を示す説明図である。図６に示すように、各ランドマーク１５０，１６０，１７０の応答時間と、計測を行ったピア２０１（図５のピア１１０）と各ランドマーク１５０，１６０，１７０との距離は比例している。すなわち、ランドマークＢ１６０の応答時間が最も短いので、ピア２０１とランドマークＢ１６０との距離が一番近い。次にランドマークＣ１７０の応答時間が短いので、ピア２０１とランドマークＣ１７０との距離が次に短い。そして、ランドマークＡ１５０の応答時間が最も長いので、ピア２０１とランドマークＡ１５０との距離が一番長い。
【００２２】
次に、ピア参加手段１１７は、ネットワーク計測手段１１４によって取得された計測結果の情報をもとに論理識別子を作成するように近傍順序論理識別子決定手段１１５に対して指示を行う。近傍順序論理識別子決定手段１１５は、ピア参加手段１１７からの指示を受けると、この従来技術の特徴的な方法により、当該ピアの論理識別子を決定する。
【００２３】
具体的には、近傍順序論理識別子決定手段１１５は、計測結果格納部１１３から各ランドマーク１５０，１６０、１７０の応答時間ＲＴＴを取得する。そして、近傍順序論理識別子決定手段１１５は、取得した各ランドマーク毎の応答時間ＲＴＴをもとに、ランドマークを順序づける。ここで、上述したように、ランドマークＡ１５０、ランドマークＢ１６０、ランドマークＣ１７０とのＲＴＴがそれぞれ２３２ｍｓ，５１ｍｓ，１１７ｍｓであるとすると、順序は［Ｂ，Ｃ，Ａ］となる。そして、近傍順序論理識別子決定手段１１５は、応答時間の順序から一意に決定可能な手法で当該ピアの論理識別子を決定する。このように、応答時間の順序から一意に決定可能な手法で論理識別子の範囲を求めることで、ランドマークに対して同一の応答時間の順序を持つピア、すなわちネットワーク距離の近いピアが近い論理識別子を持つこととなる。
【００２４】
論理識別子を一意に決定する手法として、オーバレイネットワーク（ハッシュ空間）における論理識別子を決定するアルゴリズムであるＣＡＮ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ−Ｎｅｔｗｏｒｋ）を用いることができる。ＣＡＮは非特許文献２に記載されている。
【００２５】
多次元の論理識別子を持つＣＡＮにおいて、まず、一つ目の次元の論理識別子空間（ハッシュ空間）をランドマーク数で分割し、２つ目の次元の論理識別子空間をランドマーク数−１で分割する。仮に、論理識別子空間が２次元であり、その範囲が［０，１）であるとすると、ランドマーク数が３であるので、図７に示すように、１次元目の論理識別子空間を［０，０．３３），［０．３３，０．６６），［０．６６，１）の３つに分割し、２次元目の論理識別子空間を［０，０．５），［０．５，１）の２つに分割する。よって、論理識別子空間が６つのセグメントに分割されることになる。
【００２６】
次に、応答時間の順序が先頭（１番目）のランドマークから１次元目の論理識別子空間のどこの範囲に当該ピアが属するかを決定し、応答時間の順序が２番目のランドマークから２次元目の論理識別子空間のどこの範囲に当該ピアが属するかを決定する。例えば、図７に示すように、応答時間の順序が［Ｂ，Ｃ，Ａ］であるピアは、順序が１番目のランドマークは「Ｂ」であるため、そのアルファベット順序から［０．３３，０．６６）が１次元目の範囲となる。また、順序が２番目のランドマークは「Ｃ」であるため、そのアルファベット順序から［０，０．５）が２次元目の範囲となる。
【００２７】
このようにして、同一のランドマーク順序（例えば、［Ｂ，Ｃ，Ａ］）を持つピア同士が近い論理識別子を持つようになるが、論理識別子の衝突を避けるために、当該範囲の中でランダムに割り当てられる範囲がこのピアの論理識別子となる。
【００２８】
以上は、ピア初期化部１１１の動作について説明であるが、登録・検索実行部１２０の動作については、一般的に用いられているオーバレイネットワークにおけるデータ検索アルゴリズム（例えばＣＡＮ）を利用して実現されるため、説明を省略する。
【００２９】
なお、別の従来のオーバレイ検索システムが特許文献１に記載されている。この従来の検索システムでは、図５に示すピア初期化部１１１の中で行われる手順と対応するオーバレイネットワークに参加する処理の中で、複数の他ピアと当該ピアとの通信負荷を計測し、その結果に基づいて、それら他ピアの中から接続先ピアを選択する手段を有する。
【００３０】
【非特許文献１】Ｓｙｌｖｉａ  Ｒａｔｎａｓａｍｙ，  Ｍａｒｋ  Ｈａｎｄｌｅｙ，  Ｒｉｃｈａｒｄ  Ｋａｒｐ  ａｎｄ  Ｓｃｏｔｔ  Ｓｈｅｎｋｅｒ，“Ｔｏｐｏｌｏｇｙ−Ａｗａｒｅ  Ｏｖｅｒｌａｙ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ａｎｄ  Ｓｅｒｖｅｒ  Ｓｅｌｅｃｔｉｏｎ”，  ＩＰ．．．．
【非特許文献２】Ｓｙｌｖｉａ  Ｒａｔｎａｓａｍｙ，  Ｐ．Ｆｒａｎｃｉｓ，  Ｍａｒｋ  Ｈａｎｄｌｅｙ，  Ｒｉｃｈａｒｄ  Ｋａｒｐ  ａｎｄ  Ｓｃｏｔｔ  Ｓｈｅｎｋｅｒ，“Ａ  Ｓｃａｌａｂｌｅ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ，”  ＳＩＧＣＯＭＭ  ２００１
【特許文献１】特開２００６−１９１４８９号公報
【発明の開示】
【発明が解決しようとする課題】
【００３１】
従来のオーバレイデータ検索システムでは、オーバレイネットワークへの参加時に、ランドマークとのＲＴＴを計測することによって、図６の各ピア２０１〜２１２は、図中の［］内に記載された順序を算出する。この順序にもとづいて、各ピアには図７の論理識別子空間に示された論理識別子が割り当てられる。ここで問題となるのが、論理識別子空間の特定の範囲（第１次元＝[０．６６，１．０），第２次元＝[０．５，１．０））内に存在するピア数が多く、全体として不均一であるという点である。これは、ネットワーク内に存在するピア分布が不均一であることによる。図６に示す例では、ランドマークＣに最も近く、次にランドマークＢ、最後にランドマークＡであるようなピアが、他の組み合わせに比べて多いため、これと対応する論理識別子空間の範囲内に存在するピア数が増加する。
【００３２】
このようにピアの論理識別子が不均一であると、特定のピアにデータの集中が発生するという問題が発生する。すなわち、オーバレイネットワークのデータ検索システムにおいては、データに論理識別子を与えて、そのデータを管理するピアを対応づけるが（データの論理識別子に対応する論理識別子を持つピアにデータを管理（カバー）させるが）、ここで算出される論理識別子空間（データに割り当てる論理識別子の空間）は均一分布であるために、ピアの論理識別子の分布が不均一であると、特定のピアにデータが集中する。例えば、２次元の論理識別子空間に均一な分布を持つデータの論理識別子の算出方法としては、２つのＨａｓｈ関数を利用する方法がある。この場合、“Ｆｏｏ”というキーで指定されるデータの格納場所を決定する際には、第１のＨａｓｈ関数Ｈ１（ｘ）に当該値（“Ｆｏｏ”）を入力して０．２８を得る。第２のＨａｓｈ関数Ｈ２（ｘ）にも同様に当該値を入力して０．７８を得る。そして、これらをそれぞれ論理識別子の第１次元・第２次元の値とする。このようにして得られたデータの論理識別子にもとづいて、図７に示すようにデータがピア３１０に格納される。このことから明らかなように、Ｈａｓｈ関数の出力が［０，１）に均一分布するのであれば、ピア３０９，ピア３１１，ピア３０２，ピア３１０に存在するデータ数は、ピア３０４，ピア３０８，ピア２３０，ピア３０７に存在するデータ数の８倍となる。
【００３３】
以上のように、ネットワーク内においてピアは均一には分布していないため、ピアの論理識別子の分布も特定の論理識別子の範囲に偏る。よって、通信の応答時間などのネットワークの近傍性情報をもとにオーバレイピアの論理識別子を決定すると、特定のピアに負荷が偏ってしまう。
【００３４】
本発明は、上記のような課題を解決するためになされたものであり、ネットワークの近傍性情報を用いながら、ピアの論理識別子の分布を均一にし、特定のピアに負荷が偏らないオーバレイネットワークを構築することができるオーバレイ検索装置、オーバレイ検索システム、オーバレイ検索方法およびオーバレイ検索用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
以上の目的を達成するため、本発明のオーバレイ検索装置は、オーバレイネットワーク上に配置され、他の装置と共有するデータを検索するオーバレイ検索装置であって、他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得手段と、取得されたネットワーク特性をもとづいて当該オーバレイ検索装置の位置情報を算出する位置情報算出手段と、算出された位置情報に対して複数のオーバレイ検索装置の位置情報に関する分布関数を適用して位置情報を均一化する分布関数適用手段と、均一化された情報にもとづいて当該オーバレイ検索装置に割り当てる論理識別子を算出する論理識別子算出手段とを備えたことを特徴とする。
【００３６】
多次元データを一次元データに変換する次元変換手段を備え、位置情報算出手段は、ネットワーク特性をもとづいて当該オーバレイ検索装置の多次元の位置情報を算出し、次元変換手段は、算出された多次元の位置情報を一次元の位置情報に変換し、分布関数適用手段は、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換するように構成されていてもよい。このような構成によれば、ネットワークの近傍性を考慮しつつ、オーバレイネットワーク全体におけるピアの論理識別子の分布を確実に均一にすることができる。
【００３７】
次元変換手段は、空間充填曲線を用いて多次元データを一次元データに変換するように構成されていてもよい。このような構成によれば、容易かつ確実に、ピアの多次元の位置情報（座標）を一次元の情報に変換することができる。
【００３８】
また、本発明のオーバレイ検索システムは、オーバレイネットワーク上に配置された複数の端末を備え、各端末間で共有するデータを検索するオーバレイ検索システムであって、各端末は、他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得手段と、取得されたネットワーク特性をもとづいて当該端末の位置情報を算出する位置情報算出手段と、算出された位置情報に分布関数を適用して位置情報を均一化する分布関数適用手段と、均一化された情報にもとづいて当該端末に割り当てる論理識別子を算出する論理識別子算出手段とを備えたことを特徴とする。
【００３９】
また、本発明のオーバレイ検索方法は、オーバレイネットワーク上に配置された、他の装置とデータを共有する端末の制御部が、他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得ステップと、取得されたネットワーク特性をもとづいて当該端末の位置情報を算出する位置情報算出ステップと、算出された位置情報に分布関数を適用して位置情報を均一化する分布関数適用ステップと、均一化された情報にもとづいて当該端末に割り当てる論理識別子を算出する論理識別子算出ステップとを備えたことを特徴とする。
【００４０】
多次元データを一次元データに変換する次元変換ステップを備え、位置情報算出ステップにおいて、ネットワーク特性をもとづいて当該端末の多次元の位置情報を算出し、次元変換ステップにおいて、算出された多次元の位置情報を一次元の位置情報に変換し、分布関数適用ステップにおいて、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換するように構成されていてもよい。このような構成によれば、ネットワークの近傍性を考慮しつつ、オーバレイネットワーク全体におけるピアの論理識別子の分布を確実に均一にすることができる。
【００４１】
次元変換ステップにおいて、空間充填曲線を用いて多次元データを一次元データに変換するように構成されていてもよい。このような構成によれば、容易かつ確実に、ピアの多次元の位置情報（座標）を一次元の情報に変換することができる。
【００４２】
また、本発明のオーバレイ検索用プログラムは、オーバレイネットワーク上に配置されたコンピュータが他のコンピュータと共有するデータを検索するためのオーバレイ検索用プログラムであって、他の特定のコンピュータとの間の近傍性に関するネットワーク特性を取得するネットワーク特性取得処理と、取得されたネットワーク特性をもとづいて当該コンピュータの位置情報を算出する位置情報算出処理と、算出された位置情報に分布関数を適用して位置情報を均一化する分布関数適用処理と、均一化された情報にもとづいて当該コンピュータに割り当てる論理識別子を算出する論理識別子算出処理とをコンピュータに実行させることを特徴とする。
【００４３】
多次元データを一次元データに変換する次元変換処理をもコンピュータに実行させ、位置情報算出処理において、ネットワーク特性をもとづいて当該端末の多次元の位置情報を算出させ、次元変換処理において、算出された多次元の位置情報を一次元の位置情報に変換させ、分布関数適用処理において、変換された一次元の位置情報に分布関数を適用して均一化された一次元の情報に変換させるように構成されていてもよい。このような構成によれば、ネットワークの近傍性を考慮しつつ、オーバレイネットワーク全体におけるピアの論理識別子の分布を確実に均一にすることができる。
【００４４】
次元変換処理において、空間充填曲線を用いて多次元データを一次元データに変換させるように構成されていてもよい。このような構成によれば、容易かつ確実に、ピアの多次元の位置情報（座標）を一次元の情報に変換することができる。
【発明の効果】
【００４５】
以上のように、本発明では、オーバレイネットワーク上の各装置（ピア）が、他の特定のコンピュータ（ランドマークまたは他の特定のピア）との間の近傍性に関するネットワーク特性を取得するネットワーク特性取得手段と、取得されたネットワーク特性をもとづいて当該装置の位置情報を算出する位置情報算出手段と、算出された位置情報に分布関数を適用して位置情報を均一化する分布関数適用手段と、均一化された情報にもとづいて当該装置に割り当てる論理識別子を算出する論理識別子算出手段とを備えているので、近傍の装置（ピア）間の論理識別子の距離を小さくしつつ、全体では均一な論理識別子分布をとるように、各装置（ピア）の論理識別子を決定することができる。その結果、本発明の目的である、データ管理負荷の偏りを生じさせずに、オーバレイデータ検索の応答速度を高めることができるという効果を達成することができる。
【発明を実施するための最良の形態】
【００４６】
以下、本発明の実施の一形態を図面を参照して説明する。
【００４７】
図１は、本発明のオーバレイ検索システムの構成を示すブロック図である。図１に示すように、本発明のオーバレイ検索システムは、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）であるピア４１０，４３０，４４０と、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）であるランドマーク４５０，４６０，４７０とから構成されている。図１に示すように、各ピア４１０，４３０，４４０および各ランドマーク４５０，４６０，４７０は、ネットワーク４００に接続されている。
【００４８】
なお、図１において、ネットワーク４００にはピア４１０，４３０，４４０およびランドマーク４５０，４６０，４７０だけが接続されているが、ほかにも複数のピアやランドマークがネットワーク４００に接続されている。
【００４９】
図１に示すように、ピア４１０は、当該ピア４１０がオーバレイネットワークに参加するときに当該ピア４１０の論理識別子とルーティングテーブルを生成する処理を行うピア初期化部４１１と、検索対象のデータの登録処理およびデータの検索処理を行う登録・検索実行部４２１とを備えている。なお、ピア４３０，４４０も、ピア４１０と同一の構成を備えている。
【００５０】
登録・検索実行部４２１は、ピア論理識別子格納部４２２と、ルーティングテーブル４２３と、ローカルデータ格納部４２４と、メッセージ転送手段４２６と、通信処理手段４２７と、登録検索実行手段４２５とを備えている。
【００５１】
登録・検索実行部４２１を構成する格納部（ピア論理識別子格納部４２２、ルーティングテーブル４２３、ローカルデータ格納部４２４）には、それぞれ概略つぎのようなデータが格納されている。
【００５２】
ピア論理識別子格納部４２２には、オーバレイネットワークでの当該ピア（例えばピア４１０）の論理識別子（ノードＩＤともいう）が格納されている。論理識別子はオーバレイネットワーク上で各ピアを識別するための識別子である。
【００５３】
ローカルデータ格納部４２４には、全ピアで共有するデータのうち当該ピア４１０が担当（管理）するデータが格納される。どの部分を担当するかは、当該ピア４１０の論理識別子によって異なる。
【００５４】
ルーティングテーブル４２３は、当該ピア４１０がルーティングを行うときに参照するテーブルである。ルーティングテーブル４２３には、他のピアの論理識別子と、ネットワーク４００上でのアドレス（例えば、Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ（ＩＰ）アドレス）の組を複数有する。このルーティングテーブルの管理方式は、任意のオーバレイネットワークアルゴリズム（ＣＡＮ、Ｃｈｏｒｄなど）に応じた方式でよい。
【００５５】
登録・検索実行部４２１を構成する手段（登録・検索実行手段４２５、メッセージ転送手段４２６、通信手段４２７）は、それぞれ概略つぎのように動作する。
【００５６】
メッセージ転送手段４２６は、当該ピア４１０の登録・検索実行手段４２５、あるいは他ピアのメッセージ転送手段４２６から渡されるメッセージ（検索要求のメッセージ）を、ピア論理識別子格納部１２６あるいはルーティングテーブル１２２を参照しながら、他ピアへのメッセージの転送あるいはローカルデータ格納部１２１からのデータ取得などを行う。通信手段４２７は、他ピアのネットワーク４００上でのアドレスを指定して、ネットワーク４００上にメッセージを送受信する処理を担う。これにより、あるピアのメッセージ転送手段４２６が、他のピアのメッセージ転送手段４２６を呼び出すことを可能とする。
【００５７】
登録・検索実行手段４２５は、外部（外部インタフェース）から要求（データ登録要求、データ検索要求）があった場合に呼ばれ、要求に対応する宛先となる論理識別子範囲を決定し、決定した論理識別子範囲をメッセージ転送手段４２６に渡し、返ってきた結果（登録結果、検索結果）を外部プログラムに与える役割を担う。
【００５８】
また、ピア初期化部４１１は、ランドマーク情報格納部４１２と、計測結果格納部４１３と、空間分布格納部４１４と、ピア参加手段４１５と、ネットワーク計測手段４１６と、座標計算手段４１７と、空間充填曲線変換手段４１８と、空間分布関数適用手段４１９と、ルーティングテーブル生成手段４２０とを備えている。
【００５９】
ピア初期化部４１１を構成する格納部（ランドマーク情報格納部４１２、計測結果格納部４１３、空間分布格納部４１４）には、それぞれ概略つぎのようなデータが格納される。
【００６０】
ランドマーク情報格納部４１２には、当該ピア４１０がネットワーク計測を行う宛先のコンピュータ（ランドマーク）のアドレスが格納される。ここで、ランドーマークは、計測専用に設置されたコンピュータでも、他のピアであってもよい。
【００６１】
計測結果格納部４１３には、ランドマークに対してネットワーク計測した結果（応答時間）が格納される。空間分布格納部４１４には、オーバレイネットワークに参加しているピアの多次元の座標分布情報を一次元の分布関数として保持している。好適には、このデータは他のピア４３０，４４０と共有される。
【００６２】
ピア初期化部４１１を構成する手段（ピア参加手段４１５、ネットワーク計測手段４１６、座標計算手段４１７、空間充填曲線変換手段４１８、空間分布関数適用手段４１９、ルーティングテーブル生成手段４２０）は、それぞれ概略つぎのように動作する。
【００６３】
ネットワーク計測手段４１６は、ピア参加手段４１５から計測指示を受けると、ランドマーク情報格納部４１２から計測先のランドマークのアドレスを複数取得し、それらの宛先に対してＰｉｎｇプロトコルなどを用いて応答時間などを計測し、その応答時間を結果として計測結果格納部４１３に格納する。
【００６４】
座標計算手段４１７は、ピア参加手段４１５から座標計算指示を受けると、計測結果格納部４１３に格納された計測結果を用いて、当該ピア４１０のネットワーク４００内での座標を計算し、計算した結果をピア参加手段４１５に返す。
【００６５】
空間充填曲線変換手段４１８は、ピア参加手段４１５から変換指示を受けると、受け付けた多次元の座標（ピア４１０のネットワーク４００内での座標）を、空間充填曲線を用いて一次元の値に変換し、変換した結果をピア参加手段４１５に返す。このときに用いる空間充填曲線として、ヒルベルト空間充填曲線やＺカーブ空間充填曲線などがある。
【００６６】
空間分布関数適用手段４１９は、ピア参加手段４１５からの変換指示を受けると、空間充填曲線変換手段４１８にて変換された一次元の値（一次元の位置情報）を、空間分布格納部４１４に格納されている一次元の分布関数（空間分布関数）を用いて、均一化された一次元の値（一次元の位置情報）に変換し、変換した結果をピア参加手段４１５に返す。
【００６７】
ルーティングテーブル生成手段４２０は、ピア参加手段４１５から生成指示を受けると、当該ピア４１０の論理識別子をピア論理識別子格納部４２２から取得し、この論理識別子に応じたルーティングテーブルを作成し、ルーティングテーブル４２３に格納する。論理識別子の生成方法は、任意のオーバレイネットワークアルゴリズム（例えばＣＡＮ、Ｃｈｏｒｄなど）に応じた方式でよい。
【００６８】
ピア参加手段４１５は、外部プログラム（外部インタフェース）からのオーバレイネットワークへの参加要求を受け付ける手段である。ピア参加手段４１５は、参加要求を受け付けると、ネットワーク計測手段４１６に対して計測結果を取得するように指示する。そして、ピア参加手段４１５は、ネットワーク計測手段４１６によって取得された計測結果の情報をもとに、当該ピア４１０のネットワーク４００内での座標を計算するように座標計算手段４１７に対して指示する。また、ピア参加手段４１５は、座標計算手段４１７によって計算された座標を一次元の値に変換するように空間充填曲線変換手段４１８に指示する。さらに、ピア参加手段４１５は、空間充填曲線変換手段４１８によって変換された一次元の値を均一化するように空間分布関数適用手段４１９に指示する。そして、ピア参加手段４１５は、空間分布関数適用手段４１９から得られた一次元の値と論理識別子空間のサイズとの積を当該ピア４１０の論理識別子と決定し、決定した論理識別子をピア論理識別子格納部４２２に格納する。
【００６９】
次に、ピア初期化部４１１（ピア参加手段４１５）の動作について、図２に示すフローチャートを参照して詳細に説明する。
【００７０】
ピア参加手段４１５が外部プログラムからピア参加指示を受けると、ピアの論理識別子が決定され、その論理識別子がピア論理識別子格納部４２２に格納される。その後、ルーティングテーブル生成手段４２０によってルーティングテーブル４２３に他ピアの情報（論理識別子、アドレス）が格納される。このような処理によって、登録・検索実行手段４２５が外部からの要求（登録要求、検索要求）を受付可能な状態となる。このうち、ピアの論理識別子の決定は、図２に示すフローチャートの各処理（手順）によって行われる。
【００７１】
図２に示す処理において、まず、ピア参加手段４１５が外部プログラムからピア参加指示を受けると、ネットワーク計測手段４１６に対して計測指示を行う（ステップＳ５０１）。上述したように、ネットワーク計測手段４１６は、ピア参加手段４１５からの計測指示にもとづいて、ランドマーク情報格納部４１２から計測先のランドマークのアドレスを複数取得し、それらの宛先（他の複数のランドマーク）に対する応答時間（当該ピア４１０と各ランドマーク４５０，４６０，４７０との間の応答時間）を計測し、その応答時間を計測結果として計測結果格納部４１３に格納する。
【００７２】
次いで、ピア参加手段４１５は、座標計算手段４１７に対して座標計算指示を行う（ステップＳ５０２）。上述したように、座標計算手段４１７は、ピア参加手段４１５からの座標計算指示にもとづいて、計測結果格納部４１３に格納された計測結果（各ランドマーク４５０，４６０，４７０との複数の応答時間）を用いて、当該ピア４１０のネットワーク４００内での多次元の座標を計算（算出）し、計算した結果をピア参加手段４１５に返す。
【００７３】
次いで、ピア参加手段４１５は、空間充填曲線変換手段４１８に対して変換指示を行う（ステップＳ５０３）。上述したように、空間充填曲線変換手段４１８は、ピア参加手段４１５からの変換指示にもとづいて、座標計算手段４１７によって算出された多次元の座標（ピア４１０のネットワーク４００内での座標）を、空間充填曲線を用いて一次元の値に変換し、変換した結果をピア参加手段４１５に返す。
【００７４】
また、ピア参加手段４１５は、空間分布関数適用手段４１９に対して変換指示を行う（ステップＳ５０４）。上述したように、空間分布関数適用手段４１９は、ピア参加手段４１５からの変換指示にもとづいて、空間充填曲線変換手段４１８にて変換された一次元の値（一次元の位置情報）を、空間分布格納部４１４に格納されている一次元の分布関数（空間分布関数）を用いて、均一化された一次元の値（一次元の位置情報）に変換し、変換した結果をピア参加手段４１５に返す。
【００７５】
そして、ピア参加手段４１５は、空間分布関数適用手段４１９から取得した一次元の値と論理識別子空間のサイズＮとの積を算出し、算出した値を当該ピア４１０の論理識別子ｍと決定する（ステップＳ５０５）。そして、空間分布関数適用手段４１９は、決定した論理識別子ｍをピア論理識別子格納部４２２に格納する。
【００７６】
その後、ルーティングテーブル生成手段４２０は、ピア参加手段４１５から生成指示にもとづいて、当該ピア４１０の論理識別子をピア論理識別子格納部４２２から取得する。そして、ルーティングテーブル生成手段４２０は、取得した論理識別子に応じたルーティングテーブルを作成し、ルーティングテーブル４２３に格納する。
【００７７】
以上の処理によって、登録・検索実行手段４２５が外部プログラムからの要求を受付可能な状態となる。なお、登録・検索実行部１２０の動作については、一般的に用いられているオーバレイネットワークにおけるデータ検索アルゴリズム（例えばＣＡＮ、Ｃｈｏｒｄなど）を利用して実現可能であるため、説明を省略する。
【実施例】
【００７８】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
【００７９】
図３は、本発明の具体的な実施例を説明するための説明図である。図３において、左側上段の図（図３の６００）は、ピアとランドマークの物理ネットワーク上における配置例を示す図である。右側上段の図（図３の６１０）は、座標計算手段４１７により算出されたピアの多次元の座標を示す図である。左側中段の図（図３の６２０）は、空間充填曲線変換手段４１８により空間充填曲線を用いて変換された一次元の位置情報を示す図である。右側中段の図（図３の６３０）は、空間分布関数適用手段４１９により空間分布関数を用いて均一化された一次元の位置情報を示す図である。左側下段の図（図３の６４０）は、ピア間でのメッセージの流れの具体例を示す図である。
【００８０】
図３の右側上段の図（図３の６００）に示すように、インターネットなどのネットワーク６００内に、ピア６０１と計測先のコンピュータであるランドマーク６０２，６０３，６０４が存在するとする。なお、図３の右側上段の図におけるドット（点）は、複数のピアの分布を示している。図３の右側上段の図に示す例では、ランドマーク６０２，６０３，６０４の近くに多数のピアが分布している。
【００８１】
ピア６０１がオーバレイネットワークに参加する際には、ピア参加手段４１５が起動され、図２に示したステップＳ５０１〜Ｓ５０５の処理が実行される。まず、ステップＳ５０１では、当該ピア６０１のピア参加手段４１５がネットワーク計測手段４１６を用いて、複数のランドマーク６０２，６０３，６０４との応答時間を測定する。この場合、ネットワーク計測手段４１６は、ランドマーク情報格納部４１２からランドマーク６０２，６０３，６０４のアドレスを取得する。
【００８２】
ここでは、ランドマーク６０２，６０３，６０４のＩＰアドレスとして「１０．１０．１．１」、「１９２．１６８．１．１」、「１７２．１６．１．１」がランドマーク情報格納部４１２に格納されているものとする。アドレスを取得したネットワーク計測手段４１６は、ランドマーク６０１，６０２，６０３それぞれのアドレスに対して、Ｐｉｎｇなどを用いて応答時間を計測する。この例では、ランドマーク６０２，６０３，６０４との応答時間が、それぞれ「５１ｍｓ」、「２３２ｍｓ」、「１１７ｍｓ」であったものとする。この計測結果は、計測結果格納部４１３に格納される。
【００８３】
次に、ピア参加手段４１５は、ネットワーク６００内での当該ピア６０１の位置を座標として取得するために、座標計算手段４１７に座標の算出処理を実行させる（ステップＳ５０２）。ここでは、座標計算手段４１７は、先に計測した応答時間を計測結果格納部４１３から取得し、任意の座標計算アルゴリズムを用いて、当該ピア６０１の座標を算出する。仮に、ピア６０１の位置を図３の右側上段の図（図３の６１０）に示すような２次元の座標に写像し、先の計測結果から、ピア６０１の座標として、（ｘ，ｙ）＝（７５，１１０）が得られたとする。この場合、ピア６０１は、座標６１１に写像されたこととなる。この座標上では２点間のユークリッド距離が、当該コンピュータ間の応答時間に相当するため、例えば座標が（７５，１００）であるコンピュータと座標が（３００，２００）であるコンピュータとは、およそ２４２ｍｓの応答時間であると推測される。なお、良く知られた座標計算アルゴリズムとしては、ＧＮＰ（Ｇｌｏｂａｌ  Ｎｅｔｗｏｒｋ  Ｐｏｓｉｔｉｏｎｉｎｇ）、Ｌｉｇｈｔｈｏｕｓｅｓ、主成分分析を用いるＶｉｒｔｕａｌ  ＬａｎｄｍａｋｒやＩＣＳといった方法がある。
【００８４】
ピア参加手段４１５は、座標計算手段４１７にて計算された座標を受け取ると、この２次元の座標を、空間充填曲線変換手段４１８を用いて一次元の位置情報に変換するために、空間充填曲線変換手段４１８に座標の変換処理を実行させる（ステップＳ５０３）。空間充填曲線に対する入力はビット列であるため、この座標を正規化して８ビットで表すと２５６×（（ｘ＋１００）／４００）や２５６×（（ｙ＋１００）／４００）などの変換が考えられ、これを適用すると１０進数表記で（１１２，１３４）、２進数表記で（０１１１００００，１００００１１０）となる。この先頭３ビットのみを軸上に表記した座標が図３の左側中段の図（図３の６２０）となる。これを空間充填曲線に適用して一次元の値「３２６６２」が得られたとする（図３の６２１）。
【００８５】
なお、この空間充填曲線変換をするために用いる２次元データからの変換用のデータ構造の例を図４に示す。まず、２次元の値（０１１１００００，１００００１１０）の第１ビットの組「０１」を、第１階層７１０の下段から探し（図４の７１３）、対応する上段「０１」を記憶する（図４の７１２）。次に、第２ビットの組「１０」を、先に探した第１階層の下段（図４の７１３）の下の第２階層７２０の下段から探し（図４の７２３）、対応する上段「１１」を記憶する（図４の７１２）。以下同様に、８ビット目まで対応する各階層の上段の値を取得し、記憶した上段の値を結合させて、ビット列０１１１１１１１１００１１０１１０（１０進数で３２６６２）を取得する。
【００８６】
ピア参加手段４１５は、空間充填曲線変換手段４１８にて計算された一次元の位置情報を取得すると、空間分布関数適用手段４１９に均一化された一次元の位置情報に変換する処理を実行させる（ステップＳ５０４）。空間分布関数適用手段４１９は、変換指示を受けると、空間分布格納部４１４から空間分布関数Ｄ（ｋ）を取得する。この関数は、図３の右側上段の図（図３の６１０）に示すような多次元の分布の偏り情報にもとづき偏りのある一次元の位置情報を単調増加な一次元の位置情報（０〜１の範囲内で均一に分布された一次元の情報）に変換する関数である。ここでは、先に算出された３２６６２（図３の６３１）にＤ（ｋ）を適用して、０．６３（図３の６３２）が得られたものとする。
【００８７】
ピア参加手段４１５は、空間分布関数適用手段４１９にて均一化された一次元の位置情報を取得すると、取得した位置情報と、オーバレイネットワークの論理識別子空間のサイズとの積を算出する（ステップＳ５０５）。ここでは、図３の左側下段の図（図３の６４０）に示すような論理識別子が０から２５５までの論理識別子空間（２８ の空間）を想定すると、当該ピア６４１の論理識別子は１６０（０．６３×２５５≒１６０）となる。
【００８８】
ピア論理識別子が決定すると、ピア参加手段４１５は、ピア論理識別子格納部４２２に当該情報を格納する。そして、ピア参加手段４１５は、ルーティングテーブル生成手段４２０にルーティングテーブルを生成させる。ルーティングテーブル生成手段４２０は、決定されたピア論理識別子を参照しながら、ルーティングテーブル４２３のデータを更新し、登録・検索実行部４２１を起動する。
【００８９】
登録・検索実行部４２１におけるルーティングテーブルやメッセージ転送手段のアルゴリズムは様々であるが、Ｃｈｏｒｄを用いた場合の例を、図３の左側下段の図（図３の６４０）に示す。
【００９０】
論理識別子１６０を持つピア６４１が、論理識別子が４６であるデータを取得する際には、論理識別子が３２であるピア６４２、論理識別子が４０であるピア６４３、論理識別子が４４であるピア６４４、論理識別子が４６であるピア６４５と取得要求（検索メッセージ）が転送される。このとき、最初のピア６４２へのメッセージ転送は、論理識別子空間での距離が１２８と大きいため、ネットワーク上でも遠いところに所在している可能性が高いが、第２のピア６４３、第３のピア６４４、第４のピア６４５までの転送は、論理識別子空間での距離が小さいため、ネットワーク上で近いピアにメッセージ転送を行っていることとなり、全体としては、検索時間を短縮させる可能性が高くなる。
【００９１】
以上のように、この実施の形態では、ピアが自身のピア論理識別子を決定する際に、ネットワーク内の他のコンピュータ（ランドマーク）との応答時間等を計測して、その結果に対して、オーバレイネットワークに参加しているピアの位置情報を含んだ分布関数を適用することで、ネットワーク的に近いピア間における、論理識別子空間内での距離を小さくしつつ、論理識別子空間内で均一に分布するように、各ピアの論理識別子を決定することができる。従って、オーバレイネットワーク上でのメッセージ転送時間を短縮することができるとともに、特定のピアに対して負荷が偏ってしまうのを防止することができる。
【００９２】
なお、分布関数について補足説明を行う。分布関数は、偏りのある位置情報を単調増加で連続な０以上１以下の値に変換する関数である。確率変数に対して、Ｆ（ｘ）＝Ｐｒ（Ｘ＜ｘ）（−∞＜ｘ＜∞）を確率変数ｘの分布関数と定義される。分布関数を累積分布関数ともいう。
【００９３】
分布関数が確率で定義されていることより，次の性質が成り立っている。
（１）０≦Ｆ（ｘ）≦１（非負性）、
（２）Ｆ（ｘ１）＜Ｆ（ｘ２）（ｘ１＜ｘ２）（単調性）、
（３）ｌｉｍｘ→ａ＋０Ｆ（ｘ）＝Ｆ（ａ）（右連続性）、
（４）ｌｉｍｘ→−∞ Ｆ（ｘ）＝０，ｌｉｍｘ→∞Ｆ（ｘ）＝１（極限）
【００９４】
例えば、日本の年齢の密度関数を考える。この場合、６０歳の年齢の人は、全体の０．０５だとする。この密度関数を積分して得られるものが分布関数Ｄ（ｋ）である。すなわち、６０歳以下の人の割合が全体の０．７であり、およそ１２０歳で１となる。このＤ（ｋ）は、同一分布に従うデータサンプルを０〜１の間に均一化させるという特徴を持つ。例えば、任意の日本人を選んで、その人の年齢ｋを聞くと、２０代くらいまでの年齢の人が比較的少なく、３０代、４０代が徐々に多くなり、５８歳あたり（団塊の世代）の割合が最も多く、その後の年代では割合が少なくなっていく。しかし、分布関数Ｄ（ｋ）を求めると０〜１に均一に分布する。
【００９５】
２＾ｍ−１は、上述したように、オーバレイネットワークにおけるＩＤ（論理識別子）の最大値で、ｍビットの最大値を表わす。例えば、８ビットの数値は００００００００〜１１１１１１１１の範囲となるが、この場合の最大値は２＾８−１＝２５５（２進数表示で１１１１１１１１）である。
【００９６】
分布関数Ｄ（ｋ）と２ｍ −１の積をとることで、位置情報は０〜２ｍ −１に均一に分布することになる。仮に、各ＩＤ毎にサーバ（端末）が存在するとすると、このデータ（位置情報）は同一確率で各サーバに配置されるため、負荷の偏りがおきないというメリットがある。
【００９７】
上記の実施例では、空間分布関数適用手段４１９が、空間分布関数Ｄ（ｋ）を偏りのある一次元の位置情報に適用して、偏りのない均一化された一次元の位置情報を取得することになる。このとき、空間分布関数Ｄ（ｋ）は、図３の右側上段の図（図３の６１０）に示すような多次元の位置情報（オーバレイネットワーク上の各ピアの座標の分布を示す情報）を一次元の位置情報として表わされた（各ピアの座標の分布を示す情報が一次元に変換された）関数（情報）である。
【００９８】
あるピアがオーバレイネットワークに参加する際に、他のピアから空間分布関数Ｄ（ｋ）を取得し、空間分布格納部４１４に格納しておく必要がある。例えば、オーバレイネットワークに参加しようとするピアが、オーバレイネットワークに既に参加している既存のピア（このピアのＩＰアドレスを事前に知っている場合）に対して空間分布関数Ｄ（ｋ）を要求して取得する。または、オーバレイネットワークに既に参加している任意のピアに対して空間分布関数Ｄ（ｋ）を要求して取得する。また、あるピアがオーバレイネットワークに参加した場合は、そのことがオーバレイネットワーク上の他のピアに通知され、他のピアが保持している空間分布関数Ｄ（ｋ）に反映される。また、あるピアがオーバレイネットワークから離脱した場合も、そのことがオーバレイネットワーク上の他のピアに通知され、他のピアが保持している空間分布関数Ｄ（ｋ）に反映される。
【００９９】
なお、上記の実施の形態では、空間充填曲線変換手段４１８が、多次元の位置情報を一次元の位置情報に変換した後に、空間分布関数適用手段４１９が、空間分布関数を適用して一次元の位置情報を均一化するように構成されていたが、空間分布関数適用手段４１９が、多次元の位置情報を均一化した後に、空間充填曲線変換手段４１８が、均一化された多次元の位置情報を一次元の位置情報に変換するように構成することが考えられる。
【０１００】
なお、上記の実施の形態において、各ピア（および各ランドマーク）において、ＣＰＵなどの制御部がハードディスクなどの記憶手段に記憶されているプログラム（オーバレイ検索用プログラム）に従って実施の形態で説明した処理を実行することにより各構成部（手段）が実現される。また、各ピアにおいて、格納部、テーブルなどはハードディスクなどの記憶手段で実現される。
【産業上の利用可能性】
【０１０１】
本発明は、広域でデータを共有するリレーショナルデータベースに適用できる。また、特定の属性データが発生した際に通知を受けることを可能とする広域メッセージ通知サービスにも適用できる。さらに、広域でのコンテンツ配信システムにも適用できる。特に、リレーショナルデータベースとしては、Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ  Ｉｄｅｎｔｉｆｉｅｒ（ＲＦＩＤ）データの格納といった用途や、システム運用管理におけるログの格納といった用途や、メールやＷｅｂページの格納、Ｓｏｃｉａｌ  Ｎｅｔｗｏｒｋ  Ｓｅｒｖｉｃｅ（ＳＮＳ）データの格納などにも適用可能である。また、メッセージ通知システムとしては、株価通知システムや、温度などのＲＦＩＤデータ値の変化を検知するといった用途にも利用可能である。さらに、コンテンツ配信システムとしては、映画やテレビ映像、ビデオの配信といった用途にも利用可能である。
【図面の簡単な説明】
【０１０２】
【図１】本発明のオーバレイ検索システムの構成を示すブロック図である。
【図２】ピア参加手段（ピア初期化部）の動作を示すフローチャートである。
【図３】本発明の具体的な実施例を説明するための説明図である。
【図４】空間充填曲線を用いて２次元データを１次元データに変換する処理のアルゴリズムを視覚的に表わすデータ構造を示す説明図である。
【図５】従来のオーバレイ検索システムの構成を示すブロック図である。
【図６】オーバレイネットワークに参加しているピアとランドマークの物理的ネットワーク上における配置例を示す説明図である。
【図７】論理識別子空間におけるピアの配置例を示す説明図である。
【符号の説明】
【０１０３】
４１０，４３０，４４０  ピア
４１１  ピア初期化部
４１２  ランドマーク情報格納部
４１３  計測結果格納部
４１４  空間分布格納部
４１５  ピア参加手段
４１６  ネットワーク計測手段
４１７  座標計算手段
４１８  空間充填曲線変換手段
４１９  空間分布関数適用手段
４２０ルーティングテーブル生成手段
４５０，４６０，４７０  ランドマーク
【図１】
2008269141.tif 000003
【図２】
2008269141.tif 000004
【図３】
2008269141.tif 000005
【図４】
2008269141.tif 000006
【図５】
2008269141.tif 000007
【図６】
2008269141.tif 000008
【図７】
2008269141.tif 000009