なんか偉そうな名前を付けていますが、 Winny上でのノードの相互評価メカニズムの話です。
P2Pファイル共有アプリケーションは参加者同士が資源を提供しあうことで成り立っていますが、 GnutellaにおけるFree Riding(ただ乗り)に関する論文 にもあるように、何らかの手を打つ必要があります。 先日のGNUnetの論文では、 お互いのノードの挙動をtrustという数値で表し評価していました。 同様にWinnyではいくつかの方法でノードを評価しそれに基づいてネットワークを動的に組み替えています。 この手法はGNUnetよりも優れているというのが私の主観的な感想です。
というわけで、Winnyでのノード評価モデルについてまとめてみました。
関連リンク:
Winnyでは、3つの要素に基づいて接続先のノードを評価します。
まず最初に、Winnyの動作を簡単に説明します。
Winnyでは、まず自分が保持しているファイルやBBSの存在情報(キー)を周囲のノードに告知します。 これらキーはさらにその隣接ノード、へと徐々に伝達していきます。 このキーには、ファイルの情報(ファイル名,サイズ,ハッシュ値)とファイルを保持するノードのIPアドレスが含まれます。 また、キーを隣接ノードに転送する際、自分がそのファイルのキャッシュを持っていれば、 キーに書かれたIPアドレスを自分のものへと書き換えます。
次に、検索を行うと検索クエリが周囲のノードに転送されます。 この検索クエリもキーと同様にノード間を転送されていきます。 検索クエリを受け取ったノードは、 自分が持っているキーのなかから検索条件に適合するものを探します。 もし見つかれば、キーのIPアドレスを自分に書き換えた上で、 適合したキーの情報を検索クエリの送り主に送り返します。
検索クエリの返答として検索条件に見合うキーを受け取ることができれば、 そのキーに書かれたIPアドレスに接続し、ダウンロードを要求します。 上述したようにキーに書かれたIPアドレスが書き換えられていればそのノードに接続し、 そのノードを中継して間接的に転送することになります。
相互に接続するノードのうち高速なものを上流、低速なものを下流とし、
上下流それぞれに接続数上限を課すことで、
回線速度による緩やかな階層構造を持たせています。
それぞれのノードはこの階層で上流にあたるノードにファイルやBBSの存在情報(キー)を流します。
これにより、
上流になるほどキーの流量が増えます。
ノードの処理が増える代わりに、様々なキーを捕まえやすくなります。
キー転送という貢献が多いノードほど、キーの見つけやすさという利益を得ているわけです。
この回線速度は各ノードが設定するものであり評価としては弱いこともあり、 現在のWinnyでは階層構造自体はそれほど重要視されていません。 ただし、自分が持つ接続数上限が多いほど数多くの接続先を持ち、それに比例して入ってくるキーが多くなります。 つまり、高速なノードほどキー流量が増える点は同じです。
ここで補足をしておくと、
Winny内に保持するキーの最大数をまた設定することもできます。
これまでは、Winnyに入ってくるキー流量だけを考えていましたが、
入ってきたキーは設定された許容量を増えると古い順に捨てられます。
当然ながら、保存するキー最大数が多いほどCPU資源を使うことになりますし、
少なければ検索結果等をすぐに忘れてしまうことになります。
このトレードオフは、回線速度とほぼ同じようなものと考えて良いでしょう。
ファイル検索のキーワードから三つをダウン情報とし、 接続する際に互いのダウン情報の類似度を計算します。 これをノードの評価値である優先度の初期値として利用します。
Winnyの検索ネットワークには既に述べたように接続数上限がありますが、
この上限を超過した場合、この優先度が低いノードから切断されます。
お互いに優先度が高いノードと接続することで、
保持しているファイルや検索条件(ダウン情報)が似た傾向を持つノード同士が直接接続するようになり、
傾向が異なるノード同士はネットワーク上で離れていきます。
Winnyでは、この同傾向のノード群をクラスタと呼び、
クラスタ内のノードのお互いの傾向の偏りの強さをクラスタの密度と表したりします。
このダウン情報の類似度は、 全く異なる場合を0とし、一定の条件により加算されていきます。
ダウン情報の類似度から求めた優先度は静的ですが、 さらにその相手からのダウンロードに成功したら1を加算、 ダウンロードに失敗したら減算することで優先度の信頼性を高めます。 実際にファイル(または、そのキャッシュ)を保持しているノードの優先度は高くなり、 自分と似たような検索条件(＝ダウン情報)であってもファイルを持っていなければ優先度は は周囲のノードから切断されにくくなり、 クラスタの密度を高めます。
出せる資源を適切に配分するという観点から、 この3種類を考察してみます。