P 2 PのKademlia(一)
5479 ワード
:http://en.wikipedia.org/wiki/Kademlia :http://blog.csdn.net/tsingmei/archive/2008/09/13/2924368.aspxKademliaは分散型ハッシュ・テーブルによって実現されるプロトコル・アルゴリズムであり、彼はPetarとDavidによって非集中型P 2 Pコンピュータ・ネットワークのために設計された.Kademliaはネットワークの構造を規定しており、ノードクエリによって情報交換を行う方式も規定している.Kademliaネットワークノード間でUDPを用いて通信する.通信に参加するすべてのノードは仮想ネットワーク(またはカバーネットワーク)を形成する.これらのノードは、1組の数字(またはノードID)を介して識別される.ノードIDは、識別情報としてだけでなく、値の位置付け(一般的にはファイルのハッシュまたはキーワード)のために使用されてもよい.実は、ノードIDはファイルのハッシュに直接対応していて、それが示すノードは、どこでファイルとリソースを取得できるかに関する情報を記憶している.
私たちは、ネットワーク内でいくつかの値(すなわち、通常はファイルのハッシュまたはキーワードを格納するノードを検索する)を検索するとき、Kademliaアルゴリズムは、これらの値に関連するキーを知る必要があり、その後、段階的にネットワーク内で検索を開始する.各ステップは、これらのノードのIDとキーがより近くにあり、ノードが直接に検索の値を返したり、キーにより近いノードIDを見つけられなくなったりすると、検索が停止されます.このような探索値の方法は、他の分散型ハッシュテーブルの実装と同様に、n個のノードを含むシステムの値の探索において、KademliaはO(log(n)個のノードにのみアクセスすることができる.
非集中的なネットワーク構造は、より大きな利点があります.それはサービス攻撃を拒否する能力を大幅に強化することができます.ネットワークの一部のノードが洪水によって攻撃されても、ネットワークの利用可能性に大きな影響を与えることはなく、これらの脆弱性(攻撃されたノード)を回避してネットワークを再構築することで、ネットワークの利用可能性が回復される.
内容
1システムの詳細
1.1ルーティングテーブル 1.2システムの詳細 1.3位置決めノード 1.4位置決めリソース 1.5 Kademliaネットワークに参加する 1.6クエリ加速
2学術的意義
3ファイル共有ネットワークでのアプリケーション
1システムの詳細
第一世代P 2 Pファイル共有ネットワークは、Napsterのように、中央データベースに依存してネットワークのクエリを調整し、第二世代P 2 Pネットワークは、Gnutellaのように、泛洪を使用してファイルを検索し、第三世代p 2 pネットワークは、分散型ハッシュテーブルを使用して、ネットワーク内のファイルを検索し、分散型ハッシュテーブルは、ネットワーク全体にリソースを格納する場所にある.これらのプロトコルの追求の主な目的は、希望のノードを迅速に位置決めすることである.
Kademliaは、2つのネットワークノードID番号の不一致である距離に基づいて計算し、結果は最終的に整形値として返される.キーワードとノードIDは同じフォーマットと長さがあるので、同じ方法でキーワードとノードIDとの距離を計算することができる.ノードIDは、一般的には大きな乱数であり、その数を選択する際に求められる目標の一つがその一意性である(ネットワーク全体でノードIDが一意であることが望ましい).異距離は実際の地理的位置とは何の関係もなく、IDのみ関連しています.したがって、ドイツとオーストラリアからのノードは、類似のランダムIDを選択したことによって、近隣になる可能性が高い.
異種を選択するということは、その計算距離を通じて幾何学的距離公式のいくつかの特徴があるからです.特に以下の点に現れます.
ノードとその自身の間の異質または距離は0である.
異種距離は対称である:すなわちAからBまでの異種距離はBからAまでの異種距離と同じである.
異和距離は三角形の不等式に適合しています.AC間の異和距離が最大であれば、AC間の異和距離はAB異和距離とBC異和距離の和より小さい必要があります.
以上のような属性のために、実際のノード距離の測定過程における計算量は大幅に減少する.Kademlia検索の反復は、ターゲットから少なくとも1 bit近くなる.基本的に2つのn番目のノードを有するKademliaネットワークは、最悪の場合はnステップだけで検索されたノードまたは値を見つけることができる.
1.1ルーティングテーブル
説明を簡単にするために、この部分は単一のbitに基づいてルーティングテーブルを構築します.実際のルーティングテーブルについてもっと多くの情報が必要なら、「クエリ加速」部分を見てください.
Kademliaルーティングテーブルは、複数のリストから構成され、各リストは、ノードIDの1ビット(例えば、ノードIDが128ビットある場合、ノードのルーティングテーブルは、128リストを含む)に対応し、複数のエントリを含み、エントリには、他のノードを特定するために必要ないくつかのデータが含まれている.リスト項目のこれらのデータは、通常、他のノードのIPアドレス、ポート、およびノードIDから構成される.各リストは、ノードから特定の範囲の距離のあるノードに対応しており、ノードのn番目のリストにおいて発見されたノードのn番目のビットは、ノードのn番目のビットとは確かに異なるが、n−1番目のビットは同じであり、これは、ネットワーク内のノードの半分から離れたノードを使用して、最初のリスト(第1のビットの異なるノードの最大半分)を満たすことが容易であることを意味する.一方、ネットワークの4分の1のノードを用いて、第2のリスト(第1のリストのノードよりもノードに近い)を充填し、順次類推する.
IDが128のバイナリビットを持っている場合、ネットワーク内の各ノードは、他のすべてのノードを異なる異種または距離で128種類に分割し、IDの各ビットは、そのクラスに対応する.
ネットワーク内のノードがあるノードによって発見されるにつれて、それらはノードの対応するリストに徐々に追加され、このプロセスにはノードリストに情報を保存する動作と、ノードリストから情報を取り出す動作とが含まれ、さらに、他のノードに対応するキーの値を探すために協力する他のノードの動作も含まれている.このプロセスで発見されたすべてのノードがノードのリストに追加されるので、ノードはネットワーク全体の知覚を動的にし、これによりネットワークは常に頻繁に更新され、誤りと攻撃を防ぐ能力を強化する.
Kademliaに関するテキスト作品では、リストはKバケットとも呼ばれ、ここで、Kはシステム変数であり、20のように、Kバケット毎に最大K個のエントリを含むリストであり、つまり、ネットワーク内の全てのノードのリスト(あるビットに対応し、ノードから特定の距離)は最大20個のノードを含む.
対応するビットが低くなる(すなわち対応する非同期距離が短くなる)につれて、Kバケットに含まれる可能性のあるノード数は急速に低下する(これは、Kバケットに対応する非同期距離が近くなるほど、ノード数が少なくなるため)ので、より低いビットに対応するKバケットは、明らかにネットワーク内のすべての関連する部分のノードを含む.ネットワーク中のノードの実際の数は可能なID番号の数よりもはるかに小さいので、それらの短い距離に対応するKバケツは常に空であるかもしれない(もし異種または距離が1であれば、可能な数は最大で1しかない.この異種または距離が1のノードが発見されていなければ、異種または距離が1のKバケツに対応するものは空である).
上の簡単なネットワークを見てみましょう.このネットワークは最大で2^3、つまり8つのキーワードとノードがあります.現在は7つのノードが参加しています.各ノードは小さな輪で表しています.黒い丸で表示されたノード6を考えます.全部で3つのKバケツがあり、ノード0、1、2(バイナリは000、001、010と表しています.)は最初のKバケツの候補ノードで、ノード3は現在(バイナリは011と表しています.)はまだネットワークに加入していません.ノード4とノード5(バイナリはそれぞれ100と101を表しています.)は第2のKバケツの候補ノードです.ノード7だけあります.3番目のKバケツの候補ノードであり、図中の3つのKバケツはいずれも灰色の丸で表されており、Kバケツのサイズ(すなわちK値)が2である場合、最初のKバケツは3つのノードのうち2つしか含まれない.
長い間オンライン接続されているノードは、将来、より長い時間オンラインの可能性が高いことが知られています.このような静的統計分布の法則に基づいて、Kademliaは、それらの長い時間オンラインのノードをKバケツに預け入れることを選択し、この方法は、将来のある時点で有効ノードの数を増加させ、より安定したネットワークを提供します.
Kバケットが満タンになって、そのバケットに対応する新しいノードが発見されると、まず、Kバケットの中で最初に訪問したノードを確認し、ノードがまだ生存しているなら、新しいノードは付属リストに配置される(代替キャッシュとして).Kバケツの中のあるノードが応答を停止したときに、cacheの代わりに使用されるのは、すなわち、新しい発見されたノードは古いノードが消えてからのみ使用される.
1.2プロトコルメッセージ
Kademliaプロトコルには4つのメッセージがあります.
PINGメッセージ—ノードがまだオンラインであるかどうかをテストするために使用されます. STOREメッセージ—あるノードにキーパッドのペアを格納します. FIND＿Hodeメッセージ−メッセージ要求の受信者は、要求キーの値に最も近いK個のノードに戻る.
FINDUVALEメッセージは、FINDUNODEと同じですが、要求された受信者が要求者から要求されたキーを持っている場合、該当キーの値を返します.
各RPCメッセージには、応答メッセージが受信されたときに前に送信された要求メッセージと一致することができるように、1つの送信者が加入するランダム値が含まれる.