フラッディング
隣接するノードに次々と探索クエリを発行、やりとり
→何も工夫をしないと、探索クエリで帯域を占領してしまい、肝心のファイル交換に支障をきたす
工夫1 探索結果のキャッシュ化
工夫2 TTL(TimeToLive)の設定
以下の論文を参照
Revisiting the TTL-based Controlled Flooding Search:Optimality and Randomization
ABSTRACT
In this paper we consider the problem of searching for a node or an object (i.e., piece of data, ?le, etc.) in a large network.
Applications of this problem include searching for a destination node in a mobile ad hoc network, querying for a piece of desired data in a wireless sensor network,
and searching for a shared ?le in an unstructured peer-to-peer network.
この論文で、我々は巨大なネットワークから一つのノードやオブジェクトをどのように探し出すべきなのかを述べることにする。
この問題を抱えているアプリケーションはアドホック(P2Pテクノロジ-基礎1参照：一過性の物)な関係にあるうちのなかから目的のノードを探し出すもの、
無線センサのネットワーク上においてほしい情報の断片を求める物、そしてP2Pネットワークにおいて共有ファイルを探し出す物も含む。
We limit our attention in this study to the class of controlled ?ooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires.
今回はパケットのTTLの期限が切れるまで、クエリ/探索のパケットが送信され、伝搬していくフラッディング検索戦略の類にのみ焦点をあてて考えていくことにしましょう。
Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated.
検索が失敗するときはTTLの値の増加や同じ処理を繰り返すことを試みる。
The primary goal of this study is to derive search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions.
この研究の目的は検索のパケットによって送受信のパケットが最小のコストになるような探索戦略を得ることである。
The main results of this paper are as follows.
この論文では結果は以下のようになる。
When the probability distribution of the location of the object is known a priori, we present a dynamic programming formulation with which optimal search strategies can be derived that minimize the expected search cost.
もし目的のオブジェクトの流通している可能性のある場所を経験的に知りうるとき、私たちは最小の探索コストで、ダイナミックな策定によって最適な探索戦略を示すことが出来る。
We also derive the necessary and su?cient conditions for two very commonly used search strategies to be optimal.
我々はさらに、探索戦略を最適にするために使う2つの非常に共通している必要十分条件を得る。
When the probability distribution of the location of the object is not known a priori and the object is to minimize the worst-case search cost,we show that the best strategies are randomized strategies, i.e., successive TTL values are chosen from certain probability distributions rather than deterministic values.
目的のオブジェクトが流通している可能性のある場所を経験的に知りえないとき、また、目的のオブジェクトが小さすぎて検索コストが最悪になるとき、我々は最良の戦略としてランダマイズされた戦略を提案する。TTLの値は決定的な値よりも配布物の可能性を重視して決定される。
We show that given any deterministic TTL sequence, there exists a randomized version that has a lower worst-case expected search cost.
我々は既に決定されたTTLシーケンスを示す、その中にはランダマイズされたものもあって最大のコストを消費してしまうケースがより少ない。
We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.
我々はさらに、ランダマイズされた戦略により、漸近的に最適な戦略を得ることを示す。
フラッディングとは、送信したいパケットをブロードキャストにて電波到達範囲内の全ノードへ送信し、受信したノードが再びそのパケットをブロードキャストすることを繰り返すことで、ネットワーク内の不特定ノードへ同一情報の配信を行うものである。
不特定ノードへ送信するのではなく、自身のルーティングテーブルに載っていない特定のノードへ送信するために利用することもある。
この場合は、目的のノードに届いたら、そのノードは転送をしない。また、TTL（Time To Live）にて転送回数を制限することもある。
フラッディングでは、新しいパケットを受け取ったノードは、必ず１度だけブロードキャストして近隣ノードへ転送することになる。
近隣ノードが全て受け取っていたとしても、それを認識することができないからである。
フラッディングされるパケットには、送信元ノード ID とシーケンス番号のような、他のフラッディングパケットと区別できるようなデータが入れられており、受け取ったノードはこの情報をローカルで保存しておく。
この情報を用いて、ノードが同一内容のパケットを２度目以降受け取った場合には転送はしない。
Design of P2P Communication System with using Flashより抜粋
工夫3 検索対象の工夫
データ構造の工夫。
EX.オブジェクト一つ一つではなくて、オブジェクト群のようなものを定義しておき、その群のリストに対してクエリを発行する。
分散ハッシュテーブル
従来の探索技術の限界
・インデックス鯖の利用/フラッディング・・・利用者増加により、検索クエリの増大による、ファイル転送帯域の減少。
分散ハッシュテーブル(DHT)・・ハッシュ値とデータの存在する位置(ノードのハッシュ値)とのマッピングが行われる。
・データとデータの保存場所のハッシュ値の組
・インデクスノード同士、近いハッシュ値のものを登録先として選ぶ。
・探索要求ノードも同じように近いハッシュ値のインデクスノードに投げる。投げられたノードになければ、そのノードも同じようにハッシュ値の近いインデクスノードに投げる。
・これを繰り返すことにより探索範囲が1/d(dは2以上)になる。
→フラッディングのように発散することがなく、効率的に探索が行える。
→インデクスを分散してもつことで安定性を保っている。
→クエリをダイナミックに処理することでアドホック性も担保されている。
0 件のコメント:
コメントを投稿