JP5915522B2

JP5915522B2 - 隣接ノード選択方法、ノード、及びプログラム

Info

Publication number: JP5915522B2
Application number: JP2012504361A
Authority: JP
Inventors: 藤田　範人; 範人藤田
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2010-03-10
Filing date: 2011-02-04
Publication date: 2016-05-11
Anticipated expiration: 2031-02-04
Also published as: WO2011111449A1; JPWO2011111449A1

Description

本発明は、分散ハッシュテーブルを構成する場合に用いられる隣接ノード選択方法、ノード、及びプログラムに関する。

ピアツーピア（Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ：Ｐ２Ｐ）ネットワークや分散データベースなどの分野において効率的なデータ検索を実現するために、分散ハッシュテーブル（ＤｉｓｔｒｉｂｕｔｅｄＨａｓｈＴａｂｌｅ：ＤＨＴ）が広く用いられている。

ＤＨＴを用いた検索では、データの検索対象キーワードからハッシュ関数を用いてハッシュ値を生成し、そのハッシュ値に対応するノードごとにデータを格納する。そして、データを検索する場合は、その検索対象キーワードからハッシュ関数を用いてハッシュ値を生成し、そのハッシュ値に対応するノード内のみを検索する。ＤＨＴプロトコルの例として、Ｃｈｏｒｄ、Ｐａｓｔｒｙ、Ｔａｐｅｓｔｒｙ、ＣＡＮ（ＣｏｎｔｅｎｔＡｄｄｒｅｓｓａｂｌｅＮｅｔｗｏｒｋ）などが広く知られている。これらのＤＨＴプロトコルにおいて、ノードは、予め定められた規則に従い、ノードＩＤ（ＩＤ：識別子）を基に隣接ノードを選択する。ここで、「隣接ノード」とは、自ノードと接続するノードのことである。

ここで、ノードＩＤはノード間の近接性（すなわち遅延の大小）とは全く関係なく割り当てられる。このため、必ずしも近接している（すなわち遅延の小さい）ノードが隣接ノードとして選択されるわけではない。したがって、データ検索時のエンド−エンドの遅延が大きくなる可能性があることが課題とされている。

このような課題に対して、特許文献１に開示されているように、ノードＩＤ自体をノードの近接性に基づいて割り当てて、エンド−エンドの検索時の遅延を小さくする方法も存在する。ただし、このような方法はＣＡＮのようなｎ次元直交座標空間にノードＩＤがマッピングされ、かつ、ショートカットリンクがないＤＨＴプロトコルにおいて適用可能である。上記方法は、ＣｈｏｒｄやＴａｐｅｓｔｒｙのような、リング構造やＰｌａｘｔｏｎ構造をとるＤＨＴプロトコルでは適用できない。

そこで、ＣｈｏｒｄやＴａｐｅｓｔｒｙのような、リング構造やＰｌａｘｔｏｎ構造をとるＤＨＴプロトコルにおいて、検索時の遅延を短縮する技術として、非特許文献１などに開示されている、近接ベース隣接ノード選択法（ＰＮＳ：ＰｒｏｘｉｍｉｔｙＮｅｉｇｈｂｏｒＳｅｌｅｃｔｉｏｎ）が提案されている。ＰＮＳは、複数の候補から隣接ノードが選択可能な場合に、最も遅延の短い候補ノードを隣接ノードとして選ぶ方法である。このようにして各ホップの遅延をできるだけ小さくすることで検索時のエンド−エンドの遅延を小さくする効果が得られる。

ＣｈｏｒｄにおいてＰＮＳを実現する方法について図８Ａおよび図８Ｂを参照しながら説明する。Ｃｈｏｒｄでは、ｎというＩＤを持つノード（ノードｎ）は、式（１）に示す領域ごとに、当該領域の中から隣接ノード（Ｃｈｏｒｄではｆｉｎｇｅｒと呼ぶ）を選択する。

但し、ｉは、ＩＤの最大ビット長以下の自然数である。また、ＩＤは、隣接ノードのＩＤを示す。
ＰＮＳを行わない通常のＣｈｏｒｄプロトコルでは、ノードｎは、式（１）に示す領域において、ＩＤがｎ＋２ｉ−１より大きいノードの中で最も小さいＩＤを持つノードを隣接ノードとして選択する。図８Ａは、通常のＣｈｏｒｄプロトコルにおける隣接ノードの選択方法を示している。
一方、ＣｈｏｒｄでＰＮＳを行う場合、ノードｎは、式（１）に示す領域で自ノードから最も遅延の小さいノードを隣接ノードとして選択する。図８Ｂは、ＰＮＳを適用した場合のＣｈｏｒｄプロトコルにおける隣接ノードの選択方法を示している。

また、ピアツーピアの情報転送技術としては、特許文献２に、次のような技術が記載されている。特許文献２の情報転送装置は、メッセージを転送先のノードとの間で送受信する通信部と、宛先のノードについて、メッセージの属性に応じて変化しうる距離である論理的距離を測定する論理的距離測定部と、論理的距離測定部で計測した論理的距離を、メッセージの属性と宛先のノードの識別符号と転送先のノードのネットワークアドレスとに対応付けて格納する論理的距離格納部と、転送するメッセージの宛先のノードとそのメッセージの属性に従って、論理的距離を用いて、メッセージの転送先のノードを決定する転送先決定部とを備えている。こうした構成とすることで、メッセージの属性に応じて、メッセージ転送を効率化するようにしている。この特許文献２に記載されている技術では、各ノードが物理的距離を測定し、その各ノードがその物理的距離を格納部に出力する必要がある。

日本特開２００８−２９９５８６号公報日本特開２００９−２１８７２８号公報

Ｋ．Ｇｕｍｍａｄｉ、Ｒ．Ｇｕｍｍａｄｉ、Ｓ．Ｇｒｉｂｂｌｅ、Ｓ．Ｒａｔｎａｓａｍｙ、Ｓ．Ｓｈｅｎｋｅｒ、Ｉ．Ｓｔｏｉｃａ、「ＴｈｅＩｍｐａｃｔｏｆＤＨＴＲｏｕｔｉｎｇＧｅｏｍｅｔｒｙｏｎＲｅｓｉｌｉｅｎｃｅａｎｄＰｒｏｘｉｍｉｔｙ」、Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００３ＳＩＧＣＯＭＭ、２００３年８月

上述のように、ＣｈｏｒｄやＴａｐｅｓｔｒｙのような、リング構造やＰｌａｘｔｏｎ構造をとるＤＨＴプロトコルにおいて、データ検索時のエンド−エンドの遅延を小さくするためには、ＰＮＳが有効な方法である。しかしながら、理想的なＰＮＳを実現するためには、式（１）に示す領域に存在する全ノードを知ることが必要である。また、各ノードへの遅延計測を行う必要がある。このため、オーバーヘッドがかかる。したがって、理想的なＰＮＳを実現することは困難とされている。

本発明は、上記の課題を解決することが可能な隣接ノード選択方法、ノード、及びプログラムを提供することを目的としている。
本発明は、分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子領域毎に、隣接ノードに関する情報を受信ノードで記憶し、送信ノードに関する情報が含まれたメッセージを前記受信ノードで受信し、前記送信ノードに関する前記情報に基づいて、前記送信ノードと前記受信ノードとの間の第１の通信環境を前記受信ノードで導出し、前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣接ノードと前記受信ノードとの間の第２の通信環境を前記受信ノードで導出し、前記第１の通信環境と前記第２の通信環境とを前記受信ノードで比較し、前記第１の通信環境が前記第２の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換える隣接ノード選択方法であって、前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、前記各ノードには、前記各ノードが属するサイトから他の各サイトまでの遅延時間が保持され、前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、前記受信ノードは、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた前記受信ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、前記受信ノードは、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、前記受信ノードは、前記第１の遅延時間と前記第２の遅延時間とを比較し、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換える隣接ノード選択方法である。

また、本発明は、分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子領域毎に、隣接ノードに関する情報を記憶する記憶部と、送信ノードに関する情報が含まれたメッセージを受信するメッセージ受信部と、前記送信ノードに関する前記情報に基づいて、前記メッセージの送信元である前記送信ノードと自ノードとの間の第１の通信環境を導出する第１の通信環境導出部と、前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣接ノードと自ノードとの間の第２の通信環境を導出する第２の通信環境導出部と、前記第１の通信環境と前記第２の通信環境とを比較し、前記第１の通信環境が前記第２の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換える隣接ノード選択部とを備えるノードであって、前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、自ノードには、自ノードが属するサイトから他の各サイトまでの遅延時間が保持され、前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、前記第１の通信環境導出部は、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた自ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、前記第２の通信環境導出部は、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、前記隣接ノード選択部は、前記第１の遅延時間と前記第２の遅延時間とを比較し、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換えるノードである。

また、本発明は、分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子領域毎に、隣接ノードに関する情報を記憶するステップと、送信ノードに関する情報が含まれたメッセージを受信するステップと、前記送信ノードに関する前記情報に基づいて、前記メッセージの送信元である前記送信ノードと自ノードとの間の第１の通信環境を導出するステップと、前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣接ノードと自ノードとの間の第２の通信環境を導出するステップと、前記第１の通信環境と前記第２の通信環境とを比較するステップと、前記第１の通信環境が前記第２の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換えるステップとをコンピュータに実行させるプログラムであって、前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、自ノードには、自ノードが属するサイトから他の各サイトまでの遅延時間が保持され、前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、前記第１の通信環境を導出するステップでは、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた自ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、前記第２の通信環境を導出するステップでは、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、前記第１の通信環境と前記第２の通信環境とを比較するステップでは、前記第１の遅延時間と前記第２の遅延時間とを比較し、前記現隣接ノードを前記送信ノードで置き換えるステップでは、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換えるプログラムである。

本発明では、ノードは、他のノードからのメッセージを受信し、メッセージの送信元のノードと自ノードとの間の通信環境を導出する。そして、送信元のノードと自ノードとの間の通信環境が、現在隣接ノードとして選択されている現隣接ノードと自ノードとの間の通信環境よりも良好であれば、現隣接ノードを送信ノードで置き換えている。このように、他のノードからメッセージを受信し、自ノードとの通信環境がより良いノードを隣接ノードとして更新するので、少ないオーバーヘッドで隣接ノードを選択することができ、理想的なＰＮＳの状況に近づけることができる。

本発明の第１の実施形態に係るシステムの全体構成を示すブロック図である。本発明の第１の実施形態における隣接ノード・座標テーブルの一例の説明図である。本発明の第１の実施形態の説明に用いるフローチャートである。本発明の第２の実施形態に係るシステムの全体構成を示すブロック図である。本発明の第２の実施形態におけるサイト間遅延のテーブルの一例の説明図である。本発明の第２の実施形態における隣接ノード・サイトＩＤテーブルの一例の説明図である。本発明の第２の実施形態の説明に用いるフローチャートである。通常のＣｈｏｒｄプロトコルにおける隣接ノードの選択方法を示す説明図である。ＰＮＳを適用した場合のＣｈｏｒｄプロトコルにおける隣接ノードの選択方法を示す説明図である。

以下、本発明の実施形態について図面を参照しながら説明する。
＜第１の実施形態＞
図１は、本発明の第１の実施形態に係るシステムの全体構成を示すブロック図である。図１を参照すると、本発明の第１の実施形態に係るシステムは、ノードＡ１と、ノードＡ２と、ベースネットワークＢ１とを備えている。

ノードＡ１およびノードＡ２は、ベースネットワークＢ１に接続されている。なお、ノードＡ１とノードＡ２は同様に構成されている。以下、原則としてノードＡ１についてだけ説明する。また、実際にはノードＡ１およびノードＡ２の他に複数のノードが存在する構成が一般的である。しかし、ここでは簡単のためにノードＡ１の他のノードを代表してノードＡ２が存在するものとして説明する。なお、本実施形態では、ノードＡ１およびノードＡ２が用いるＤＨＴプロトコルとしてＣｈｏｒｄを用いる場合を例として説明する。

ノードＡ１は、ＤＨＴプロトコル部１１と、ＴＣＰ／ＩＰ（ＴｒａｎｓｍｉｓｓｉｏｎＣｏｎｔｒｏｌＰｒｏｔｏｃｏｌ／ＩｎｔｅｒｎｅｔＰｒｏｔｏｃｏｌ）通信部１２とを備える。なお、ノードＡ２は、同様に、ＤＨＴプロトコル部２１とＴＣＰ／ＩＰ通信部２２とを備える。ＤＨＴプロトコル部１１は、座標計算部１１１と、メッセージ送信部１１２と、メッセージ受信部１１３と、ＤＨＴプロトコル処理部１１４と、距離計算部１１５と、隣接ノード選択部１１６と、隣接ノード・座標記憶部１１７とから構成される。

座標計算部１１１は、ＤＨＴプロトコルに参加するノード間の遅延に基づいて、ノードＡ１のネットワーク内の位置を、予め決められた座標空間内の座標にマッピングする。すなわち、座標計算部１１１は、ノード間遅延のマトリクスから、ノードＡ１のネットワーク内での近似された位置の座標を計算する。このように各ノードを近似された座標にマッピングすると、任意の２ノード間の遅延は、これらノードの座標間の距離を用いて推定することが可能となる。また、座標計算部１１１は、計算したノードＡ１の座標を保持し、適宜更新を行う。

このような近似された座標へのマッピング方法の一例として、下記の参考文献（Ｖｉｖａｌｄｉ）で開示されている座標計算を用いる方法が挙げられる。
［参考文献］
Ｆ．Ｄａｂｅｋ，Ｒ．Ｃｏｘ，Ｆ．Ｋａａｓｈｏｅｋ，Ｒ．Ｍｏｒｒｉｓ，“Ｖｉｖａｌｄｉ：ＡＤｅｃｅｎｔｒａｌｉｚｅｄＮｅｔｗｏｒｋＣｏｏｒｄｉｎａｔｅＳｙｓｔｅｍ，”ＩｎＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００４ＳＩＧＣＯＭＭ，Ａｕｇｕｓｔ２００４．

Ｖｉｖａｌｄｉでは、ノードｉおよびノードｊの現座標をそれぞれｐｉ（ｏｌｄ）およびｐｊ（ｏｌｄ）とし、計測されたノードｉおよびノードｊ間の遅延をｒｔｔとしたとき、ノードｉの座標ｐｉ（ｎｅｗ）を式（２）に従い更新する。

ここで、δは定数であり、ｕは単位ベクトルである。すなわち、Ｖｉｖａｌｄｉは、ノード間遅延と座標間距離との差が最小化されるように、各ノードが自律分散的に座標を更新していくアルゴリズムを採用している。また、Ｖｉｖａｌｄｉでは、座標系としては、ユークリッド空間や球面座標などを用いることが想定されている。

メッセージ送信部１１２は、ＤＨＴプロトコルにおけるメッセージを送信する機能を備える。送信されるメッセージは、ＴＣＰ／ＩＰ通信部１２を介して他のノードへ転送される。メッセージの種類の例として、Ｃｈｏｒｄの場合、あるハッシュ値を管理するノードを返すｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒメッセージや、検索要求（クエリ）メッセージが挙げられる。また、メッセージ送信部１１２は、メッセージの送信時に、座標計算部１１１が計算したノードＡ１の座標およびノードＡ１のノードＩＤを該メッセージ内に含める。ここで、該メッセージ内にノードＡ１の座標およびノードＩＤを含めるか否かはメッセージの種類に応じて変えてもよい。

メッセージ受信部１１３は、ＤＨＴプロトコルにおけるメッセージを受信する機能を備える。受信されるメッセージは、ＴＣＰ／ＩＰ通信部１２を介して受け渡される。メッセージ受信部１１３は、受信したメッセージ内に座標に関する情報（以下、「座標情報」という）が含まれる場合に、含まれる座標情報と該座標情報が示す座標に対応するノードの情報を受信したメッセージから抽出し、距離計算部１１５へ抽出した情報を渡す。また、メッセージ受信部１１３は、受信したメッセージにおける座標情報およびノードＩＤ以外の部分をＤＨＴプロトコル処理部１１４へ渡す。

ＤＨＴプロトコル処理部１１４は、受信したＤＨＴメッセージに対してメッセージの種類に従ったプロトコル処理を行う機能を備える。例えば、Ｃｈｏｒｄプロトコルにおいて、ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒメッセージ（キーとして含められるＩＤのｓｕｃｃｅｓｓｏｒのノードのＩＤを見つけるメッセージ）を受信した場合、ＤＨＴプロトコル処理部１１４は、キーとして含められるＩＤに基づき、該メッセージを適切な隣接ノード（ｆｉｎｇｅｒ）に転送するか、ｒｅｐｌｙメッセージを返す処理を行う。座標情報を含むメッセージを転送する際には、ＤＨＴプロトコル処理部１１４は、該座標情報も含めてそのままメッセージを転送する。また、Ｃｈｏｒｄプロトコル以外のプロトコルが用いられる場合、ＤＨＴプロトコル処理部１１４は、用いられるプロトコルに応じた処理を行う。

距離計算部１１５は、メッセージ受信部１１３において抽出した座標情報に基づいて、自ノードとメッセージを最初に送信したノードとの間の距離を計算する。座標情報を含むメッセージをノードＡ２が送信したとすると、距離計算部１１５は、距離の計算においては、ノードＡ２の座標と、座標計算部１１１に保持されているノードＡ１の座標とから、これらノード間の距離を割り出す。座標系が２次元ユークリッド空間であり、ノードＡ１およびノードＡ２の座標がそれぞれ（ｘｉ，ｙｉ）および（ｘｊ，ｙｊ）であったとすると、距離ｄは、式（３）に従って求められる。

距離計算部１１５は、計算した距離を、ノードＡ２のＩＤ（すなわち座標情報を含むメッセージを送信したノードのＩＤ）とともに、隣接ノード選択部１１６へ渡す。

隣接ノード選択部１１６は、距離計算部１１５から渡された、座標情報を含むメッセージを送信したノード（以下、「送信ノード」という）のＩＤと、該送信ノードと自ノードとの間の距離に基づいて、該送信ノードを隣接ノードとして選択するかを判断する。ここで、該送信ノードを隣接ノードとして選択するかどうかの判断は、例えば、以下のように行う。
まず、隣接ノード選択部１１６は、隣接ノード・座標記憶部１１７に保持されている現在の隣接ノードリストを参照して、該送信ノードのＩＤに対応する領域における現在の隣接ノードの情報を得る。そして、隣接ノード選択部１１６は、対応する領域における現在の隣接ノードと自ノードとの間の距離を計算し、この計算された距離と、該送信ノードと自ノードとの間の距離とを比較する。隣接ノード選択部１１６は、該送信ノードと自ノードとの距離の方が小さければ、該送信ノードを隣接ノードとして選択すると判断し、対応する領域における現在の隣接ノードを該送信ノードで置き換える。現在の隣接ノードを該送信ノードで置き換える場合、隣接ノード選択部１１６は、隣接ノード・座標記憶部１１７における隣接ノードの情報を該送信ノードの情報に書き換える。反対に、該送信ノードと自ノードとの距離の方が小さくない場合、隣接ノード選択部１１６は、該送信ノードを隣接ノードとして選択しないと判断し、隣接ノードは現在のままとする。

隣接ノード・座標記憶部１１７は、ノードＡ１における現在の隣接ノードをリスト形式で保持する。隣接ノード・座標記憶部１１７に保持された情報の例を図２に示す。
図２は、隣接ノード・座標記憶部１１７に保持される隣接ノード・座標テーブル１０１を示している。図２の隣接ノード・座標テーブル１０１を参照すると、Ｃｈｏｒｄにおいて隣接ノードを選ぶ領域（図中の「ＩＤ領域」）ごとに、現在選ばれている隣接ノード（ｆｉｎｇｅｒ）の情報が示されている。隣接ノード・座標テーブル１０１の例では、座標系として２次元ユークリッド空間が用いられ、ノードＡ１のＩＤがｎであるとしている。図２から、１番目の隣接ノードは、対応するＩＤ領域が式（４）に示すとおりであり、ＩＤ＝ｎ１であり、その座標は（ｘ１，ｙ１）であることがわかる。

同様に２〜４番目の隣接ノード情報および対応する座標が示されている。隣接ノード・座標テーブル１０１のエントリは、ＩＤの最大ビット長をｍとするとｍ個作成される。

ここでは、ＤＨＴプロトコルとしてＣｈｏｒｄを例にしたため、隣接ノードは予め定められたＩＤ領域ごとに選ばれる。これに対して、ＴａｐｅｓｔｒｙやＰａｓｔｒｙなどのＰｌａｘｔｏｎ構造をとるＤＨＴプロトコルの場合は、ＩＤのプレフィクス（又はサフィクス）が同一であるノードの中から隣接ノードが選ばれる。ここで、隣接ノードは同一のプレフィクス（又はサフィクス）の長さごとに選ばれる。したがって、Ｐｌａｘｔｏｎ構造をとるＤＨＴプロトコルの場合、ＩＤ領域は、同一のプレフィクス（又はサフィクス）を持つＩＤ群から構成される。

ＴＣＰ／ＩＰ通信部１２は、ＴＣＰ／ＩＰプロトコルを用いて他のノードとの通信を行う機能を備える。ノードＡ１のＯＳ（ＯｐｅｒａｔｉｎｇＳｙｓｔｅｍ）が備えるＴＣＰ／ＩＰスタックがＴＣＰ／ＩＰ通信部１２に相当する。

ベースネットワークＢ１は、ノードＡ１およびノードＡ２が接続されるネットワークであり、任意の２ノード間で通信を行うことを可能とする。

次に、図３を参照して、本発明の第１の実施形態においてノードＡ１が他のノードＡ２からメッセージを受信した際の動作について詳細に説明する。図３は、本発明の第１の実施形態においてノードＡ１が他のノードであるノードＡ２からメッセージを受信した際の動作を示すフローチャートである。この動作例では、各ノードが持つ座標の座標系として２次元ユークリッド空間が用いられるものとする。

まず、ノードＡ１のメッセージ受信部１１３がノードＡ２からメッセージを受信する（ステップＳ１０１）。次に、メッセージ受信部１１３は、ステップＳ１０１で受信したメッセージに座標情報が含まれているかどうかをチェックする（ステップＳ１０２）。

ステップＳ１０２において、座標情報がメッセージに含まれていると判断された場合（ステップＳ１０２：ＹＥＳ）、メッセージ受信部１１３は、含まれる座標情報と該座標に対応するノードの情報（すなわちノードＡ２のノードＩＤ）を受信したメッセージから抽出し、距離計算部１１５へ抽出した情報を渡す（ステップＳ１０３）。また、ステップＳ１０２において、座標情報がメッセージに含まれていないと判断された場合（ステップＳ１０２：ＮＯ）、ノードＡ１の処理は後述するステップＳ１０７へ移る。

ステップＳ１０３の後、距離計算部１１５は、ステップＳ１０３で抽出した座標情報に基づいて、式（３）に従って自ノードとノードＡ２との間の距離を計算し、計算した結果をノードＡ２のＩＤとともに隣接ノード選択部１１６へ渡す（ステップＳ１０４）。

次に、隣接ノード選択部１１６は、隣接ノード・座標記憶部１１７を参照し、ノードＡ２に対応するＩＤ領域において、現在隣接ノードとして選択しているノードと自ノードとの間の距離と、ステップＳ１０４で計算した自ノードとノードＡ２との間の距離とを比較する（ステップＳ１０５）。

ステップＳ１０５において、ステップＳ１０４で計算したノードＡ２と自ノードとの間の距離が現在の隣接ノードと自ノードとの間の距離より小さい場合（ステップＳ１０５：ＹＥＳ）、隣接ノード選択部１１６は、ノードＡ２に対応するＩＤ領域において現在選択している隣接ノードを、ノードＡ２に置き換える（ステップＳ１０６）。他方、ステップＳ１０５においてノードＡ２と自ノードとの間の距離が現在の隣接ノードと自ノードとの間の距離以上である場合、隣接ノード選択部１１６は、隣接ノードは現在のままとする。そして、ノードＡ１の処理はステップＳ１０７へ移る。

ステップＳ１０６の後、メッセージ受信部１１３は、受信したメッセージにおける座標情報およびノードＩＤ以外の部分をＤＨＴプロトコル処理部１１４へ渡す。ＤＨＴプロトコル処理部１１４は、メッセージの種類に従ったプロトコル処理を行う（ステップＳ１０７）。

上述した例では、受信したメッセージに座標情報が含まれる場合、該座標に対応するノードは、該メッセージをノードＡ１へ送信したノードＡ２であった。

しかしながら、ノードＡ２以外のノードの座標情報がメッセージに含まれる場合もありうる。例えば、ノードＡ２以外のノード（以下、ノードＸとする）がメッセージを最初に送信し、該メッセージをノードＡ２がノードＡ１に対して転送した場合、該メッセージ内には、ノードＸの座標情報が含まれている。したがって、このような場合は、メッセージ受信部１１３は、座標情報に対応するノードのＩＤとして、ノードＸのノードＩＤを抽出する。

次に本発明の第１の実施形態の効果について説明する。本発明の第１の実施形態では、各ノードがノード間の遅延に基づいて自ノードの座標を計算し、該座標および自ノードのノードＩＤをＤＨＴプロトコルにおけるメッセージ内に含めて送信する。そして、送信ノードの座標が含まれたメッセージを受信したノードは、該送信ノードと自ノードとの間の距離をこれらノードの座標から計算し、計算した距離が、該送信ノードのＩＤに対応するＩＤ領域において現在隣接している隣接ノードと自ノードとの間の距離よりも小さければ、隣接ノードを該送信ノードに置き換える。

上述した処理の結果、他のノードからのメッセージ受信を、自ノードにより近いノードを隣接ノードとして更新する機会とすることができる。したがって、より多くのノードからメッセージを受信するほど理想的なＰＮＳの状況に近づけることが期待できる。

＜第２の実施形態＞
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。図４は、本発明の第２の実施形態に係るシステムの全体構成を示すブロック図である。本発明の第２の実施形態に係るシステムは、図１に示した本発明の第１の実施形態と同様に、ベースネットワークＢ１と、このベースネットワークＢ１に接続されたノードＡ３およびノードＡ４とを備えている。

なお、本実施形態においても、ノードＡ３およびノードＡ４の用いるＤＨＴプロトコルがＣｈｏｒｄである場合を例として説明する。また、ノードＡ３およびノードＡ４は同じ構成を有する。以下、原則としてノードＡ３についてだけ説明する。

図４を参照すると、ノードＡ３は、ＤＨＴプロトコル部３１と、ＴＣＰ／ＩＰ通信部３２とから構成される。なお、ノードＡ４は、同様に、ＤＨＴプロトコル部４１とＴＣＰ／ＩＰ通信部４２とから構成される。ＴＣＰ／ＩＰ通信部３２は、第１の実施形態で示したＴＣＰ／ＩＰ通信部１２と同様の機能を備えており、ＴＣＰ／ＩＰ通信部１２と同様の動作を行うため、詳細な説明は省略する。

ＤＨＴプロトコル部３１は、サイト間遅延記憶部３１１と、メッセージ送信部３１２と、メッセージ受信部３１３と、ＤＨＴプロトコル処理部３１４と、遅延計算部３１５と、隣接ノード選択部３１６と、隣接ノード・サイトＩＤ記憶部３１７とから構成される。

ＤＨＴプロトコル処理部３１４は、第１の実施形態で示したＤＨＴプロトコル処理部１１４と同様の機能を備えており、ＤＨＴプロトコル処理部１１４と同様の動作を行うため、詳細な説明は省略する。

サイト間遅延記憶部３１１は、自ノードが属するサイトから他のサイトまでの遅延を記憶している。ここで、サイトとは、互いに近傍に存在するノード（例えば、同一管理ドメイン内に存在するノード）で構成されるグループである。具体的には、ＩＰネットワークにおけるＡＳ（ＡｕｔｏｎｏｍｏｕｓＳｙｓｔｅｍ）や、ＶＰＮ（ＶｉｒｔｕａｌＰｒｉｖａｔｅＮｅｔｗｏｒｋ）における拠点などがサイトの単位として用いられ、各ノードは１つのサイトに属する。例えば、ＡＳがサイトの単位として用いられる場合、同一ＡＳ内に属するノードは、同一サイトに属するものとして扱われる。また、各サイトにはユニークなＩＤ（サイトＩＤ）が割り当てられる。また、自ノードが属するサイトから他のサイトまでの遅延を知る方法として、事前又は定期的に自ノードの代表ノードから各サイト内の代表ノードまでの遅延を計測する方法などが挙げられる。

サイト間遅延記憶部３１１に記憶されるサイト間遅延テーブルの例を図５に示す。図５を参照すると、サイト間遅延テーブル１０２が示されており、自ノード（ノードＡ３）が属するサイトから、他のサイトへの遅延が示されている。例えば、ノードＡ３はサイト「３」に属し、サイト「１」に属するノードへは１００ｍｓｅｃの遅延があり、サイト「２」に属するノードへは２０ｍｓｅｃの遅延があり、自サイト（サイト「３」）に属するノードへは１ｍｓｅｃの遅延があり、サイト「４」に属するノードへは５０ｍｓｅｃの遅延があることがわかる。

メッセージ送信部３１２は、第１の実施形態におけるメッセージ送信部１１２と同様、ＤＨＴプロトコルにおけるメッセージを送信する機能を備える。ただし、メッセージの送信時に該メッセージに座標およびノードＩＤを含めるのではなく、ノードＡ３が属するサイトのサイトＩＤおよびノードＡ３のノードＩＤを含める点が異なる。また、該メッセージ内にノードＡ３のサイトＩＤおよびノードＩＤを含めるか否かはメッセージの種類に応じて変えてもよい。

メッセージ受信部３１３は、第１の実施形態におけるメッセージ受信部１１３と同様、ＤＨＴプロトコルにおけるメッセージを受信する機能を備える。ただし、メッセージの受信時に受信したメッセージから座標情報を抽出するのではなく、受信したメッセージ内にサイトＩＤが含まれている場合に、含まれるサイトＩＤと該サイトＩＤに対応するノードの情報を受信したメッセージから抽出し、遅延計算部３１５へ抽出した情報を渡す点が異なる。

遅延計算部３１５は、メッセージ受信部３１３において抽出したサイトＩＤに基づいて、該サイトＩＤを含むメッセージを送信したノードと自ノードとの間の遅延を計算する。例えば、サイトＩＤを含むメッセージをノードＡ３がノードＡ４から受信し、該メッセージにノードＡ４の属するサイトのＩＤであるサイト「４」が含まれていたとする。ノードＡ３の遅延計算部３１５は、サイト間遅延記憶部３１１を参照し、サイトＡ４と自ノードＡ３が属するサイトとの間の遅延を調べる。サイト間遅延が、図５に示すサイト間遅延テーブル１０２の通りであったとすると、ノードＡ３とノードＡ４との間の遅延は、５０ｍｓｅｃであると求められる。遅延計算部３１５は、求めた遅延を、ノードＡ４のＩＤ（すなわちサイトＩＤを含むメッセージを送信したノードのＩＤ）とともに、隣接ノード選択部３１６へ渡す。

隣接ノード選択部３１６は、遅延計算部３１５から渡された、サイトＩＤを含むメッセージを送信したノード（以下、送信ノードという）のＩＤと、該送信ノードと自ノードとの間の遅延に基づいて、該送信ノードを隣接ノードとして選択するかを判断する。該送信ノードを隣接ノードとして選択するかどうかの判断において、隣接ノード選択部３１６は、まず、隣接ノード・サイトＩＤ記憶部３１７に保持されている現在の隣接ノードリストから、該送信ノードのＩＤに対応する領域における現在の隣接ノードの情報を参照する。そして、隣接ノード選択部３１６は、対応する領域における現在の隣接ノードと自ノードとの間の遅延と、該送信ノードと自ノードとの間の遅延とを比較する。該送信ノードと自ノードとの間の遅延の方が小さければ、隣接ノード選択部３１６は、対応する領域における現在の隣接ノードを該送信ノードで置き換える。現在の隣接ノードを該送信ノードで置き換える場合、隣接ノード選択部３１６は、隣接ノード・サイトＩＤ記憶部３１７における隣接ノードの情報を該送信ノードの情報に書き換える。反対に、該送信ノードと自ノードとの間の遅延の方が小さくない場合、隣接ノード選択部３１６は、隣接ノードを現在のままとする。

隣接ノード・サイトＩＤ記憶部３１７は、第１の実施形態における隣接ノード・座標記憶部１１７と同様、ノードＡ３における現在の隣接ノードをリスト形式で保持する。ただし、隣接ノード・サイトＩＤ記憶部３１７は、隣接ノードの座標の代わりに、隣接ノードの属するサイトＩＤを保持する点が、隣接ノード・座標記憶部１１７と異なる。隣接ノード・サイトＩＤ記憶部３１７に保持された情報の例を図６に示す。

図６の隣接ノード・サイトＩＤテーブル１０３を参照すると、１番目の隣接ノードは、対応するＩＤ領域が式（４）に示すとおりであり、ＩＤ＝ｎ５であり、該ノードが属するサイトＩＤはサイト「４」であることがわかる。同様に２〜４番目の隣接ノード情報および対応するサイトＩＤが示されている。

次に、図７を参照して、本発明の第２の形態においてノードＡ３が他のノードであるノードＡ４からメッセージを受信した際の動作について詳細に説明する。図７は、本発明の第２の形態においてノードＡ３が他のノードであるノードＡ４からメッセージを受信した際の処理を示すフローチャートである。

まず、ノードＡ３のメッセージ受信部３１３がノードＡ４からメッセージを受信する（ステップＳ２０１）。次に、メッセージ受信部３１３は、ステップＳ２０１で受信したメッセージにサイトＩＤが含まれているかどうかをチェックする（ステップＳ２０２）。

ステップＳ２０２において、サイトＩＤがメッセージに含まれていると判断された場合（ステップＳ２０２：ＹＥＳ）、メッセージ受信部３１３は、含まれるサイトＩＤと該サイトＩＤを含むメッセージを送信したノードの情報（すなわちノードＡ４のノードＩＤ）をメッセージから抽出し、遅延計算部３１５へ抽出した情報を渡す（ステップＳ２０３）。また、ステップＳ２０２において、サイトＩＤがメッセージに含まれていないと判断された場合（ステップＳ２０２：ＮＯ）、ノードＡ３の処理は後述するステップＳ２０７へ移る。

ステップＳ２０３の後、遅延計算部３１５は、ステップＳ２０３で抽出したサイトＩＤに基づいて自ノードとノードＡ４との間の遅延を計算し、計算した結果をノードＡ４のＩＤとともに隣接ノード選択部３１６へ渡す（ステップＳ２０４）。

次に、隣接ノード選択部３１６は、隣接ノード・サイトＩＤ記憶部３１７を参照し、ノードＡ４に対応するＩＤ領域において、現在隣接ノードとして選択しているノードと自ノードとの間の遅延と、ステップＳ２０４で計算した自ノードとノードＡ４との間の遅延とを比較する（ステップＳ２０５）。

ステップＳ２０５において、ステップＳ２０４で計算したノードＡ４と自ノードとの間の遅延が現在の隣接ノードと自ノードとの間の遅延より小さい場合（ステップＳ２０５：ＹＥＳ）、隣接ノード選択部３１６は、ノードＡ４に対応するＩＤ領域において現在選択している隣接ノードを、ノードＡ４に置き換える（ステップＳ２０６）。ステップＳ２０５において、ステップＳ２０４で計算したノードＡ４と自ノードとの間の遅延が現在の隣接ノードと自ノードとの間の遅延以上である場合（ステップＳ２０５：ＮＯ）、隣接ノード選択部３１６は、隣接ノードを現在のままとする。そして、ノードＡ３の処理はステップＳ２０７へ移る。

ステップＳ２０６の後、メッセージ受信部３１３は、メッセージにおけるサイトＩＤおよびノードＩＤ以外の部分をＤＨＴプロトコル処理部３１４へ渡す。ＤＨＴプロトコル処理部３１４は、メッセージの種類に従ったプロトコル処理を行う（ステップＳ２０７）。

上述した例では、受信したメッセージにサイトＩＤが含まれる場合、該サイトＩＤに対応するノードは、該メッセージをノードＡ３へ送信したノードＡ４であった。

しかしながら、ノードＡ４以外のノードが属するサイトのサイトＩＤがメッセージに含まれる場合もありうる。例えば、ノードＡ４以外のノード（以下、ノードＹとする）がメッセージを最初に送信し、該メッセージをノードＡ４がノードＡ３に対して転送した場合、該メッセージ内には、ノードＹの属するサイトのサイトＩＤが含まれている。したがって、このような場合は、メッセージ受信部３１３は、メッセージに含まれるサイトＩＤに対応するノードのＩＤとして、ノードＹのＩＤを抽出する必要がある。

次に本発明の第２の実施形態の効果について説明する。本発明の第２の実施形態では、互いに近傍に存在するノード同士が同一のサイトに属するようにし、各ノードは自ノードが属するサイトのサイトＩＤおよび自ノードのノードＩＤをＤＨＴプロトコルにおけるメッセージ内に含めて送信する。そして、送信ノードが属するサイトのサイトＩＤが含まれたメッセージを受信したノードは、該送信ノードと自ノードとの間の遅延を、事前あるいは定期的に計測されたサイト間遅延に基づいて求め、求められた遅延が、該送信ノードのＩＤに対応するＩＤ領域において現在隣接している隣接ノードと自ノードとの間の遅延よりも小さければ、隣接ノードを該送信ノードに置き換える。

このようにすることで、他のノードからのメッセージ受信を、自ノードにより近いノードを隣接ノードとして更新する機会とすることができる。したがって、より多くのノードからメッセージを受信するほど理想的なＰＮＳの状況に近づけることが期待できる。

以上、実施形態を参照して本発明を説明したが、本発明は、上述した実施形態に限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更を加えることができる。

上述のノードは、内部にコンピュータシステムを有していても良い。この場合、上述した各処理部の動作は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されている。そして、このプログラムをコンピュータが読み出し、読み出されたプログラムをコンピュータが実行して、上記処理が行われる。ここで、コンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（ＣｏｍｐａｃｔＤｉｓｃ−ＲｅａｄＯｎｌｙＭｅｍｏｒｙ）、ＤＶＤ（ＤｉｇｉｔａｌＶｅｒｓａｔｉｌｅＤｉｓｃ）−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線経由でコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。

また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。

この出願は、２０１０年３月１０日に出願された日本出願特願２０１０−０５３６５３号を基礎とする優先権を主張し、その開示の全てをここに取り込む。

本発明は、例えば、分散ハッシュテーブルを備えたノードや、こうしたノードを有するシステムに利用することができる。本発明では、少ないオーバーヘッドで隣接ノードを選択できる。

１１ＤＨＴプロトコル部
１２ＴＣＰ／ＩＰ通信部
２１ＤＨＴプロトコル部
２２ＴＣＰ／ＩＰ通信部
３１ＤＨＴプロトコル部
３２ＴＣＰ／ＩＰ通信部
４１ＤＨＴプロトコル部
４２ＴＣＰ／ＩＰ通信部
１０１隣接ノード・座標テーブル
１０２サイト間遅延テーブル
１０３隣接ノード・サイトＩＤテーブル
１１１座標計算部
１１２メッセージ送信部
１１３メッセージ受信部
１１４ＤＨＴプロトコル処理部
１１５距離計算部（第１の通信環境導出部）
１１６隣接ノード選択部（第２の通信環境導出部、隣接ノード選択部）
１１７隣接ノード・座標記憶部（記憶部）
３１１サイト間遅延記憶部
３１２メッセージ送信部
３１３メッセージ受信部
３１４ＤＨＴプロトコル処理部
３１５遅延計算部（第１の通信環境導出部）
３１６隣接ノード選択部（第２の通信環境導出部、隣接ノード選択部）
３１７隣接ノード・サイトＩＤ記憶部（記憶部）

Claims

分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子領域毎に、隣接ノードに関する情報を受信ノードで記憶し、
送信ノードに関する情報が含まれたメッセージを前記受信ノードで受信し、
前記送信ノードに関する前記情報に基づいて、前記送信ノードと前記受信ノードとの間の第１の通信環境を前記受信ノードで導出し、
前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣接ノードと前記受信ノードとの間の第２の通信環境を前記受信ノードで導出し、
前記第１の通信環境と前記第２の通信環境とを前記受信ノードで比較し、前記第１の通信環境が前記第２の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換える
隣接ノード選択方法であって、
前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、
前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、
前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、
前記各ノードには、前記各ノードが属するサイトから他の各サイトまでの遅延時間が保持され、
前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、
前記受信ノードは、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた前記受信ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、
前記受信ノードは、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、
前記受信ノードは、前記第１の遅延時間と前記第２の遅延時間とを比較し、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換える
隣接ノード選択方法。
分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子
領域毎に、隣接ノードに関する情報を記憶する記憶部と、
送信ノードに関する情報が含まれたメッセージを受信するメッセージ受信部と、
前記送信ノードに関する前記情報に基づいて、前記メッセージの送信元である前記送信
ノードと自ノードとの間の第１の通信環境を導出する第１の通信環境導出部と、
前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、
前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣
接ノードと自ノードとの間の第２の通信環境を導出する第２の通信環境導出部と、
前記第１の通信環境と前記第２の通信環境とを比較し、前記第１の通信環境が前記第２
の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現
在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換える隣接
ノード選択部と
を備えるノードであって、
前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、
前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、
前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、
自ノードには、自ノードが属するサイトから他の各サイトまでの遅延時間が保持され、
前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、
前記第１の通信環境導出部は、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた自ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、
前記第２の通信環境導出部は、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、
前記隣接ノード選択部は、前記第１の遅延時間と前記第２の遅延時間とを比較し、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換える
ノード。
分散ハッシュテーブルプロトコルに参加する各ノードを特定する識別子の所定の識別子領域毎に、隣接ノードに関する情報を記憶するステップと、
送信ノードに関する情報が含まれたメッセージを受信するステップと、
前記送信ノードに関する前記情報に基づいて、前記メッセージの送信元である前記送信ノードと自ノードとの間の第１の通信環境を導出するステップと、
前記隣接ノードに関する前記情報および前記送信ノードに関する前記情報に基づいて、前記送信ノードに対応する識別子領域について現在隣接ノードとして選択されている現隣接ノードと自ノードとの間の第２の通信環境を導出するステップと、
前記第１の通信環境と前記第２の通信環境とを比較するステップと、
前記第１の通信環境が前記第２の通信環境より良好である場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして選択されている前記現隣接ノードを前記送信ノードで置き換えるステップと
をコンピュータに実行させるプログラムであって、
前記第１の通信環境および前記第２の通信環境は、ノード間の遅延時間であり、
前記分散ハッシュテーブルプロトコルに参加する前記各ノードのうち、同一管理ドメイン内に存在するノードで構成されるグループであるサイトに対して、前記サイトを識別するためのサイト識別子が割り当てられ、
前記隣接ノードに関する前記情報は、前記隣接ノードが属するサイトに割り当てられたサイト識別子と前記隣接ノードを特定する識別子を含み、
自ノードには、自ノードが属するサイトから他の各サイトまでの遅延時間が保持され、
前記メッセージは、前記送信ノードに関する前記情報として、前記送信ノードが属する第１のサイトに割り当てられた第１のサイト識別子と前記送信ノードを特定する第１の識別子を含み、
前記第１の通信環境を導出するステップでは、前記メッセージから前記第１のサイト識別子および前記第１の識別子を抽出し、保持された前記遅延時間に基づいて、第２のサイト識別子が割り当てられた自ノードが属する第２のサイトと前記第１のサイトとの間の第１の遅延時間を求め、
前記第２の通信環境を導出するステップでは、保持された前記遅延時間に基づいて、前記現隣接ノードが属する第３のサイトと前記第２のサイトとの間の第２の遅延時間を求め、
前記第１の通信環境と前記第２の通信環境とを比較するステップでは、前記第１の遅延時間と前記第２の遅延時間とを比較し、
前記現隣接ノードを前記送信ノードで置き換えるステップでは、前記第１の遅延時間が前記第２の遅延時間より小さい場合に、前記送信ノードに対応する前記識別子領域について現在隣接ノードとして記憶されている前記現隣接ノードの第２の識別子を前記第１の識別子で置き換える
プログラム。