4

私は現在、古典的な論文Kademlia: A Peer-to-peer Information System Based on the XOR Metric を読んで Kademlia ネットワークを学んでいます。その操作の複雑さを理解したいのですが、まだ理解できません。

3 証明のスケッチセクションでは、この論文は 2 つの定義を示しています。

  1. ノードの深さ (h) : 160 − i、i は空でないバケットの最小インデックス
  2. ノード x におけるノード y のバケットの高さ: x が y を挿入するバケットのインデックスから、x の最下位の空のバケットのインデックスを引いたもの。

そして3つの結論：

  1. 圧倒的な確率で、任意のノードの高さは、n 個のノードを持つシステムのlog nの定数内になります。
  2. k 番目に近いノードの ID に最も近いノードのバケットの高さは、log kの定数内にある可能性があります。
  3. このノードの h個の最上位 k バケットが空でない場合、ルックアップ手順は、各ステップで半分ほど近い (または距離が 1 ビット短い) ノードを見つけ、そのノードをh − log kステップで上げます。 .

だから私の質問は：

  1. 「最下位の空のバケット」と「最上位の k バケット」とは何ですか?
  2. 深さとバケットの高さを視覚的に説明するにはどうすればよいですか?
  3. 2 番目と 3 番目の結論を理解する方法、たとえばlog kとh - log kの理由は?
4

1 に答える 1

4

この論文を実際に読んでからしばらく時間が経っているので、頭の中にある概念をこの論文の正式な定義に一致させようとするのではなく、実装経験からこれをつなぎ合わせています。次に少しの塩を加えます

「最下位の空のバケット」と「最上位の k バケット」とは何ですか?

これは基本的に、ノード自身の ID に対する XOR 距離でソートされたバケットを指します。

深さとバケットの高さを視覚的に説明するにはどうすればよいですか?

各バケットはキースペース リージョンをカバーします。たとえば、 2 バイトに簡略化された 0x0000 から、キースペースの 1/16 の 0x0FFF まで。これは、CIDR のようなマスク 0x0/4 (4 プレフィックス ビット) で表すことができます。それは多かれ少なかれバケツの深さです。

ルーティング テーブルを編成するには、いくつかの方法があります。「正しい」方法は、バケットによって表される最小の ID に基づいて、ツリーまたはソートされたリストとして表すことです。このアプローチは、一部のルーティング テーブルの最適化が必要なため、任意のバケット分割操作を可能にし、ノード マルチホーミングの実装にも使用できます。

単純化された実装では、代わりに固定長配列を使用し、各バケットをノード自身の ID に対する共有プレフィックス ビットの位置に配置することができます。つまり、配列の位置 0 には 0 の共有プレフィックス ビットがあり、これは最も遠いバケットであり、キースペースの 50% をカバーするバケットであり、最上位ビットがノード自身の ID の逆 MSB であるバケットです。

その場合、深さは単に配列の位置です。

2 番目と 3 番目の結論を理解するにはどうすればよいでしょうか。

自分のノードの ID から最も離れた ID を探しているとします。次に、キースペースのその部分をカバーするバケットは 1 つだけになります。つまり、キースペースの半分をカバーし、最上位ビットがあなたのものとは異なります。したがって、そのバケットから 1 つ (または複数) のノードを要求します。ID ビットの最初のビットがルックアップ ターゲットと共通しているため、多かれ少なかれそれが 2 つ以上に分割されることが保証されます。つまり、ターゲット スペースのキースペース カバレッジが少なくとも 2 倍になります。そのため、少なくとも 1 ビットはより良い情報を提供できます。

ターゲットに近いノードをクエリすると、ターゲット領域の近くのキースペース カバレッジも向上します。これは、それ自体のノード ID にも近いためです。

すすぎ、より近いノードが見つからなくなるまで繰り返します。

各ホップは一度に少なくとも 1 ビットの距離を削るため、基本的に O(log(n)) ホップ カウントが必要です。ここで、n はネットワーク サイズです。ネットワークサイズは基本的にノード間の平均距離を決定するため、ホームバケットに必要なバケットの深さを決定します。

ターゲット キーが自分の ID に近い場合、キースペースのその領域をより適切にカバーできるため、必要な手順は少なくなります。

kは定数 (バケットあたりのノード数) であるため、log kも同様です。バケット内のノード数を 2 倍にすると、指定されたキースペース領域の解像度が 2 倍になり、(確率的に) k/2 サイズのバケットよりもターゲットに 1 ビット近いノードが生成されます。つまり、保存したいホップごとの追加ビットごとに、バケットごとのエントリ数を 2 倍にする必要があります。

編集: これは、実際のシングルホームの bittorrent DHT ルーティング テーブルの視覚化です。プレフィックスで並べ替えられています。つまり、ローカル ノード ID に関連していません。

Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4
buckets: 23 / entries: 173
000...   entries:8 replacements:8
00100...   entries:8 replacements:0
0010100...   entries:8 replacements:2
0010101000...   entries:8 replacements:4
00101010010...   entries:8 replacements:7
001010100110000...   entries:8 replacements:3
0010101001100010...   entries:8 replacements:3
00101010011000110000...   entries:8 replacements:1
001010100110001100010...   entries:3 replacements:0
0010101001100011000110...   entries:6 replacements:0
0010101001100011000111...   entries:6 replacements:0
0010101001100011001...   entries:8 replacements:2
001010100110001101...   entries:8 replacements:1
00101010011000111...   entries:8 replacements:2
00101010011001...   entries:7 replacements:0
0010101001101...   entries:8 replacements:0
001010100111...   entries:8 replacements:0
001010101...   entries:8 replacements:1
00101011...   entries:7 replacements:0
001011...   entries:8 replacements:0
0011...   entries:8 replacements:8
01...   entries:8 replacements:8
1...   entries:8 replacements:8
于 2015-03-13T21:19:50.397 に答える