ネットワーク共有情報の探索法

ネットワーク共有情報を探索するためのモデルとして,各ノードが有する情報のindexを中央に全て集め,そこに探索を依頼する集中管理方式,各ノードが自分が保持していない情報に関して隣接するノードに次々に聞いてまわるバケツリレー方式をこれまで考えていた.今回は新たにジオメトリック・リ-ジョン(GR)方式という,この2つの中間的なモデルも考え,3者の探索におけるネットワークに与える負荷について,式による予測とシミュレーションを行った.GR方式とは,ネットワークを幾つかのリ-ジョンと呼ばれる部分に分割し,リ-ジョンの内部では集中管理方式,リ-ジョン内部で検索に失敗した場合は,外のリ-ジョンとの間でバケツリレー方式の探索を行う方式である.探索要求の発生頻度を一定とし,index更新のコストも考慮すると,バケツリレー方式にあっては自分の隣接するノードの数が,集中管理方式にあってはindexの大きさと更新頻度が探索のためにネットワークに与える負荷を左右する要因であり,GR方式ではこのバランスがリ-ジョン数によって変化する.リ-ジョン数1の場合は集中管理方式であり,全部のノードが別々のリ-ジョンと考えるとバケツリレー方式となる.式による予測とシミュレーションの結果から,GR方式では隣接ノード数の平均が1.9以下なら集中管理方式の部分が,3.4以上になるとバケツリレー方式の部分が負荷に対して支配的となる.また,indexの更新にかかるパケット数と探索のために送出されるパケット数の比についてそれが5以下なら集中管理方式が,11以上ならバケツリレー方式が負荷に対して支配的となる.本研究の結果,上の様な範囲であればリ-ジョン数が2,3程度の付近で,GR方式が情報検索のためにネットワークに与える負荷が小さくなることが判明した.

ネットワーク共有情報を探索するためのモデルとして,各ノードが有する情報のindexを中央に全て集め,そこに探索を依頼する集中管理方式,各ノードが自分が保持していない情報に関して隣接するノードに次々に聞いてまわるバケツリレー方式をこれまで考えていた.今回は新たにジオメトリック・リ-ジョン(GR)方式という,この2つの中間的なモデルも考え,3者の探索におけるネットワークに与える負荷について,式による予測とシミュレーションを行った.GR方式とは,ネットワークを幾つかのリ-ジョンと呼ばれる部分に分割し,リ-ジョンの内部では集中管理方式,リ-ジョン内部で検索に失敗した場合は,外のリ-ジョンとの間でバケツリレー方式の探索を行う方式である.探索要求の発生頻度を一定とし,index更新のコストも考慮すると,バケツリレー方式にあっては自分の隣接するノードの数が,集中管理方式にあってはindexの大きさと更新頻度が探索のためにネットワークに与える負荷を左右する要因であり,GR方式ではこのバランスがリ-ジョン数によって変化する.リ-ジョン数1の場合は集中管理方式であり,全部のノードが別々のリ-ジョンと考えるとバケツリレー方式となる.式による予測とシミュレーションの結果から,GR方式では隣接ノード数の平均が1.9以下なら集中管理方式の部分が,3.4以上になるとバケツリレー方式の部分が負荷に対して支配的となる.また,indexの更新にかかるパケット数と探索のために送出されるパケット数の比についてそれが5以下なら集中管理方式が,11以上ならバケツリレー方式が負荷に対して支配的となる.本研究の結果,上の様な範囲であればリ-ジョン数が2,3程度の付近で,GR方式が情報検索のためにネットワークに与える負荷が小さくなることが判明した.