(57)【要約】【課題】分散ハッシュテーブルではP2Pオーバーレイ上のピア間の隣接関係が物理ネットワーク上のピアの距離と無関係に決められる。オーバーレイ上で，最短距離でルーティングされても、物理ネットワーク上では遠く離れている可能性がある。本発明では、物理ネットワーク上のノード間の近接性を考慮したP2PDHTを構築する装置と手法を与える。【解決手段】CANのゾーン空間をインデックス管理用のゾーン空間とルーティング用のゾーン空間の二重構造とする。インデックス用のゾーン空間はピアの負荷に応じてゾーンを分割し、ルーティング用のゾーン空間はインデックス用のゾーン空間と同様に分割するが、ピアの配置はノードの近接性を考慮したものとする。2つのゾーン空間で同じ位置のゾーンを管理するピア同士を互いにリンクすると、ピアの負荷の偏りはインデックス用のゾーン空間の分割で解消し、ルーティング効率はルーティング用のゾーン空間により改善する。【選択図】  なし【特許請求の範囲】
【請求項１】
ネットワークに遍在する資源に対してアクセスをするためのネットワーク検索プログラムに於いて，
Ｐ２ＰＤＨＴのゾーン空間がインデックス管理用のゾーン空間とルーティング用のゾーン空間の二重構造であることを特徴とするネットワーク検索プログラム。
【請求項２】
インデックス用のゾーン空間はピアの負荷に応じてゾーン分割を行い、
ルーティング用のゾーン空間はインデックス用のゾーン空間と同様の形状に分割するが、
ピアの配置はインデックス用のゾーン空間とは異なりノードの近接性を考慮したものにすることを特徴とする
請求項１に記載のネットワーク検索プログラム。
【請求項３】
請求項１または請求項２に記載のネットワーク検索プログラムをより，
ネットワーク全体のオーバーレイを行うことを特徴とするオーバーレイ構築装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ネットワークのためのオーバーレイ構築装置、およびネットワーク検索プログラムに関する。
【背景技術】
【０００２】
P2Pはネットワーク通信技術やセキュリティ技術など、さまざまな基礎技術によって支えられているが、その中でも特に分散ハッシュテーブル(DHT)を用いた分散インデックス管理手法は、ネットワーク上に遍在する資源に対して効率的なアクセスを実現する手法のひとつとして、近年高い注目を集めている。
【０００３】
DHTを用いたインデックス情報の管理は、P2Pオーバーレイネットワーク(P2P DHT)を用いて分散的に行われ、各資源に対するインデックスは、すべてのピアが共通に参照することのできるハッシュ関数によって仮想的な論理空間(ハッシュ表)に写像される。
【０００４】
ハッシュ表はいくつかの部分に適切に分割され、各部分に写像されたインデックスの集合は、P2P DHTに参加しているピアたちによって分散的に管理される。
これまでに、CAN、Chord、Pastryなどの様々なP2P DHTが提案されている。
【０００５】
【特許文献１】特開２００７−１０９０６２号公報
【特許文献２】特開２００６−４８５１１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
DHTの問題点のひとつは、P2Pオーバーレイ上のピア間の隣接関係が、物理ネットワークにおけるピアの近さとは無関係に決められているという点である。
【０００７】
すなわち通常のP2P DHTでは、仮にオーバーレイ上で最短距離(最小ホップ数)のルーティングがなされていたとしても、物理的なネットワーク上では，遠く離れたピア間で無駄にメッセージがやり取りされている可能性を排除することができない。
【０００８】
本発明ではこの課題に対して、物理ネットワークにおけるノード間の近接性を考慮した効率のよいP2P DHTを構築するための装置と手法を与える。
【課題を解決するための手段】
【０００９】
ネットワーク上のノード間の近接性を推定する方法として、NCS (Network Coordinate System)と総称される、座標系に基づく遅延推定システムが知られている。
【００１０】
NCSの目的は、実際に測定された複数ノード間のRTT(Round Trip Time)値からインターネット上の任意のノード間のRTT値を正確に推定することであり、これまでにGNP、PIC、Vivaldiなどが提案されている。
【００１１】
中でもVivaldiには、RTT推定値の座標空間を、特別なランドマークノードを用いることなく構成できるという利点がある。
【００１２】
具体的にはVivaldiでは、ノードの推定誤差を、ノードi,j間の実測遅延Lijとノードiの座標xiを用いてε = Σi Σj (Lij−| xi −xj |)2と定義し、物理ネットワークをバネをつなぎ合わせて作った網に見立て、推定誤差が最小値となるように、バネを緩めるごとく座標値を座標軸ごとに調整していく。
【００１３】
Vivaldiアルゴリズムは分散アルゴリズムであり、各ノードは完全に自立的に動作し、上記の処理は、アプリケーションレベルのトラフィックに便乗して座標の更新を行うことができるため、遅延推定のための特別なトラフィックが必要ない。
【００１４】
基本座標系としては、低次元直交座標系や、球面座標、極座標などが推奨されている。
【００１５】
本発明の基本的なアイデアは、Vivaldiアルゴリズムによる各ノードの座標(以下 Vivaldi座標)の位置関係とDHT上のピアが管理するゾーンの中点(以下，DHT座標)の位置関係の間に対応関係を想定した上で、Vivaldi座標の位置関係をDHT座標の位置関係へと変換するアフィン変換を推定し新規ピアのVivaldi座標を変換することで、DHTのゾーンへの、近接性を考慮した適切な参加座標を決定することである。
【００１６】
DHT上の適切な位置へ参加していないピアは、DHTを離脱し新たにDHTに参加する際に提案手法により適切な参加座標を選ぶことが出来るため、ノードのVivaldi座標とDHT座標の間に対応関係が無かったとしても、新規ピアが提案手法を用いてDHTに参加することを繰り返すうちに、ノードのVivaldi座標とDHT座標に徐々に対応関係が生じる。
【００１７】
検索クエリに偏りがある場合にはピアの負荷を考慮したゾーン分割を行う必要がある。
【００１８】
負荷の大きいピアをなくすには、負荷の大きいゾーンを管理するピアがゾーンを分割すれば良いが、ピアの負荷のみによってゾーン分割を行うと、ノードの近接性を考慮して参加座標を選ぶことが出来なくなる。
【００１９】
そこで本手法では、CANのゾーン空間をインデックス管理用のゾーン空間とルーティング用のゾーン空間の二重構造にすることを考える。
【００２０】
インデックス用のゾーン空間はピアの負荷に応じてゾーン分割を行い、ルーティング用のゾーン空間はインデックス用のゾーン空間と同様の形状に分割するが、ピアの配置はインデックス用のゾーン空間とは異なりノードの近接性を考慮したものにする。
【００２１】
またピアの負荷に応じてゾーン分割を行うために、各ピアは負荷の情報を持たせる。
負荷は整数値で、CAN上でクエリやメッセージを受けとるたびに1ずつ増加し、新規ピアがCANに参加したときには引き継いだゾーンを管理していたピアの負荷の半分の値を負荷の初期値として設定し、CAN上でゾーンを半分に分割したピアは負荷の値を半分にする。
【発明の効果】
【００２２】
2つのゾーン空間で同じ位置のゾーンを管理するピア同士を互いにリンクすることで、ピアの負荷の偏りはインデックス用のゾーン空間の分割で解消し、ルーティングの効率はルーティング用のゾーン空間によって改善することが出来る。
【発明を実施するための最良の形態】
【００２３】
座標系
VivaldiとDHTがともに二次元直交座標空間上に構築されている状況を想定する。
以下では、二次元直交座標系をもつ具体的なDHTとして、CAN(Content Addressable Network)を考える。
【００２４】
・  ピアの参加手続き
【００２５】
具体的な新規ピアの手続きは以下のようになる。
【００２６】
新規ピアiはCANに参加する際にCAN上のk個のピアjと通信を行い，それらのピアとの間のRTT値を実測するとともに，それらのピアの管理するゾーンの中心座標pjとVivaldi座標vjとからなる座標対を獲得する。
【００２７】
新規ピアはCAN上のピアと通信を行った際にVivaldiアルゴリズムを実行し、自身のVivaldi座標viとピアjのVivaldi座標vjを更新する。
【００２８】
CAN上でピアiがうけもつべきゾーンの中心座標piは、座標対から推定したアフィン変換によってviを変換して求める。
【００２９】
新規ピアはCAN上のk個のピアと通信してk個の座標対を得て、アフィン変換の各係数を推定する。
【００３０】
Vivaldi座標とCAN座標の関係はアフィン変換によって正確に対応づけることはできないために推定する係数には誤差が生じるが、この点を解決するため、新規ピアは通信で得たk個の座標対から最小2乗法によってアフィン変換の係数を推定する。
【００３１】
３．検索クエリに偏りが無い場合
【００３２】
新規ピアはCANへ参加する際に、プローブ数k個のCAN上のピアと通信を行い、それらのピアの座標対を得ると共にVivaldiアルゴリズムを実行する。
【００３３】
まず新規ピアはk個のピアと通信するために、CANのゾーン空間上の座標をランダムにk個選び、これらの座標へプローブメッセージを送信する。
【００３４】
プローブメッセージはCAN上を検索クエリと同様に転送されていき、目的の座標を管理するピアまで届けられる。
【００３５】
プローブメッセージを受けとったピアはメッセージの送信元へ自身の座標対を送信するとともに送信元のピアとVivaldiアルゴリズムを実行する。
【００３６】
新規ピアはk個の座標対を得てアフィン変換を推定し、自身のVivaldi座標を変換してCAN上の参加座標を計算する。
【００３７】
このとき変換によって得られた点がCANの座標空間の範囲外であった場合は、x座標とy座標をそれぞれ座標空間の外周の辺上まで移動させる。
【００３８】
CANへの参加座標が決まれば、その座標へ参加要求を行いCANへ参加する。
【００３９】
この手順は従来のCANとほぼ同様であるが、従来のCANでは参加座標を含むゾーンを管理するピアがゾーンを分割し、分割したゾーンの一方をランダムに選び新規ピアに引き継いでいたのに対して、本手法では参加座標が含まれる側のゾーンを新規ピアへと引き継ぐという点が異なっている。
【００４０】
４．検索クエリに偏りが有る場合の参加手続き
【００４１】
新規ピアがCANに参加する際には、プローブ数k個のCAN上のピアと通信を行い、それらのピアの座標対を得ると共にVivaldiアルゴリズムを実行し、さらに各ピアの負荷の値を得る。
【００４２】
新規ピアは、通信したk個のピアの中で負荷の値が最大のピアのCAN座標を参加座標として、インデックス用のゾーン空間に参加する。
【００４３】
このとき新規ピアは、ルーティング用のゾーン空間上の同じ位置のゾーンにも参加する。
【００４４】
５．検索クエリに偏りが有る場合のルーティング用ゾーン空間のメンテナンス法
【００４５】
新規ピアはインデックス用のゾーン空間に参加手続きを行った後、ルーティング用ゾーン空間上で近接性を考慮したピアの配置を実現するため、自身が管理するゾーンを他のピアと交換する。
新規ピアがAのゾーンに参加したとき，新規ピアはルーティング用のゾーン空間上で，アフィン変換によって求めた参加座標(Gのゾーン内の点とする)へ向けてプローブメッセージを送信する。
【００４６】
メッセージはAからGのゾーンへと転送されていくが、このときメッセージが転送されたのとは逆方向にピアが管理するゾーンを交換する。
具体的には、FのゾーンをGが、EのゾーンをFが、DのゾーンをEが、CのゾーンをDが、BのゾーンをCがAのゾーンをBが，GのゾーンをAが管理する。
このように、プローブメッセージの転送された経路上で、ピアの管理するゾーンが1つずつずれていく。
これによって、ルーティング用のゾーン空間はインデックス用のゾーン空間と同じ形状に分割されていながら、ノードの近接性を反映したピアの配置を実現することができる。
【００４７】
インデックス用のゾーン空間においては、新規ピアの参加が完了するまで、プローブメッセージの経路上のピアは元のゾーンの情報と新たに引き継いだゾーン情報の両方を管理する。
新規ピアのゾーンの交換が完了した後に、新規ピアは経路上のピアへメッセージを送信する。
【００４８】
このメッセージを受けとった経路上のピアは、新たに引き継いだゾーンの隣接ピアにゾーンを引き継いだことを知らせ、元のゾーンの情報を破棄する。
こうすることで、新規ピアの参加処理中でもゾーン空間の隣接関係が壊れることがなくなり、他ピアからのルーティングメッセージを安全に転送できる。
【産業上の利用可能性】
【００４９】
これまで本発明の一実施形態について説明したが、本発明は上述の実施形態に限定されず、その技術的思想の範囲内において種々異なる形態にて実施されてよいことは言うまでもない。