問題タブ [kademlia]

'v'Bittorrent Mainline DHT（MDHT）応答のキー値は何に対応していますか？

バンドルされた応答の例を次に示します。

このキーがどこにも文書化されていません。

プロトコルに関する私の現在の情報源は次のとおりです。

• BEP 5：DHTプロトコル
• Kademlia：設計仕様

内部クラスター用に独自の dht を実装中です。bittorrent のようなファイル共有プログラムで使用されるため、最初に見たのは「Mainline DHT」でした。その後、「絡み合った」（python、ツイストマトリックスを使用したdht）、議会（python、pyev + libevを使用したdht）、そしてもちろんオリジナルの「kademlia」を見つけました。

k-bucket を整理するためのさまざまなアプローチがあります。

1) 議会、kademlia は、0 <= i < 160 の場合、2* i <= (各 ID の差) < 2 *(i+1) の範囲で固定の 160 バケットを使用します。

2) メインラインの DHT と entangled はダイナミック バケットを使用します。最初は、スペース全体をカバーするバケツが 1 つしかありません。8 つの生きているノードでいっぱいになると、バケットは 2 つの新しいノードに分割されます。ただし、そのバケット内に独自の ID がある場合のみ。そうでない場合 -- バケットは決して分割されません。そのため、すぐに 160 個の最も近いバケットとその他のバケットがいくつかあります。

どちらのバリアントでも十分です。しかし、IDがバケットに属しているかどうかを検出するロジックに大きな違いがあることがわかりました。これが私の質問です。

congress と kademlia は、バケット境界線を「私たちからの最小距離」および「私たちからの最大距離」として扱います。したがって、私たち自身の ID は常にbucket0 にあります。バケット 1 の最大 2 つの他の ID (2* 1 <= x < 2 *2 の距離をカバーするため) は、常に私たちに最も近いものになります。だから私の脳は壊れません。

しかし、Mainline DHT または entangled を調べると、xor 距離ではなく、絶対ノード ID 境界として扱われるバケット境界が表示されます。したがって、理論的に完全なテーブル ID では、0、1、2、3、4、5、6、7 が 1 つのバケットになります。

そう。一部の実装では、バケット境界を「私たちからの最大/最小距離」として扱い、他の実装では「最大/最小 160 ビット整数値」として扱うのはなぜですか??

最近、Kademlia プロトコルのドキュメントを読んで、プロトコルを理解しようとしましたが、まだいくつか疑問があります。IP またはポートではなく、ID を知っているノードが別のノードを見つけなければならないのはなぜですか? IP やポートがわからないのに ID を持っているのはなぜですか。どこで ID を取得したのでしょうか。2 つの異なるノード間の「距離」は、ルーティング距離や実際の距離ではなく、アルゴリズムを使用してノードをすばやく見つけることができる仮想距離にすぎないと思います。そうですか?

英語は私の母国語ではないので、私の英語はあまり明確ではないかもしれませんが、必要に応じて自分自身を明確に表現しようとします. どうもありがとう！

Kademlia Distributed Hash Tableは、信頼性が低いにもかかわらず、UDP をネットワーク トランスポート プロトコルとして使用するのはなぜですか?

私は現在、Kademliaピア ツー ピア プロトコルについて調査しています。誰かが情報/メッセージを効率的にブロードキャストするための手法やアプローチを知っているかどうか知りたいですか?

Chordでのブロードキャストの方法について説明している論文Effcient Broadcast in Structured P2P Networksがあります。彼らのアイデアは、ネットワークを 2 つの部分に分割し、これらの各分割の最初のノードにブロードキャスト メッセージを送信することです。接続されたノードは再び「サブネット」を分割し、同じアクションを実行します。この手法を使用すると、ネットワークを介してスパニング ツリーでメッセージをブロードキャストできます。ただし、Kademlia ネットワークを確実に分割することは難しいため、Kademlia に適用する際に問題があります。

これをどのように達成できるか、またはどのような代替アプローチが存在するかについて誰かが考えていますか?

これはネットワーク負荷に悪影響を及ぼし、多くの冗長トラフィックを引き起こすため、ネットワークを大量にフラッディングさせたくありません。

Kademliaルーティングテーブルは160個のバケットで構成されていることを理解しています。

ノードは、プレフィックス長（ローカルノードキーとノードのXORの先頭の未設定ビットの数）に応じて、バケット0〜159に配置されます。

なぜそうなのですか（160 * 20ノードを反復処理して最も近いノードを見つけることが不可能であるという事実以外に）パフォーマンス上の利点はありますか？

私はデータが（理論的には）DHTにどのように保存されているかを知っています。ただし、キーに関連付けられたデータを更新する方法についてはわかりません。これは可能ですか？また、競合はDHTでどのように処理されますか。

今日、Kademlia について読んだのは初めてで、正しく理解できていないと思う点がいくつかあります。

ノードとキーの間の距離は、それらの値の xor です。

したがって、キー x とノード y がある場合、それらの間の距離は x xor y です。

しかし、私が知っているノードをバケット化し、プレフィックスの長さで並べ替えるポイントは何ですか? 私に最も近いノードを見つけるために、ノードIDのxorと直接接続されているようには見えませんか?

値のリクエストを受け取ると、自分に最も近いバケットのノードを検索します。これは、自分と最大の共有プレフィックスを持つノード、つまり 160 個のバケットの最初のいくつかのバケットですか?

または代わりに、すべてのバケットで知っているすべてのノードをチェックし、探しているキーとそれらのノード ID の間の xor を計算し、キー ID を使用した xor の結果に基づいて上位 k 件の一致にリクエストを送信します。 ?

申し訳ありませんが、私はDHTに少し慣れていないため、オンラインでの説明が少し明確ではありません.

少し前に、Kademlia (KAD) プロトコルをいじりました。私はそれがどのように機能するかを理解し、それを使用して分散データストアを作成する可能性があるという考えを得ました.

いずれにしても、問題が 1 つあります。Kademlia には、データ パッケージごとにそれを「所有」するノードがあります。データが要求されると、次のノードに伝播されますが、TTL が割り当てられます。その後、削除されています。Kademlia の考え方は、「所有者」ノードは、データが期限切れになる前に他のノードのデータを更新するというものです。

私が理解している限り、これは「所有者」ノードがネットワークを離れてもデータをキャッシュすることにつながりますが、それはしばらくの間だけです。所有者ノードが戻ってこない場合、そこから他のノードにコピーされたすべてのデータは遅かれ早かれ期限切れになるため、しばらくするとデータがなくなります。

これは、人々がファイルを共有したい P2P ネットワークでは問題ありませんが、分散型データ ストアではそれほどうまくいきません。

どうすればこれに対処できますか？

または - これを考慮した Kademlia に似た別の P2P プロトコルはありますか? 私の想像では、「完璧な」解決策は、複製されたデータを保持する N 個のノードが常に存在する場合です。そのうちの 1 つが離れるとすぐに、残りの N-1 ノードが別のノードを探してデータをプッシュするため、再び N ノードになります。

そのようなプロトコルは存在しますか?

私はトレントマグネットテクノロジーを理解しようとしてきましたが、マグネットリンクを開いたときに最初のピアに接続する方法がわからないようです。

以下のようなマグネットリンクを取得すると、最初のピアは含まれず、BitTorrent Info Hash（btih）とファイル名のみが含まれます。

BitTorrent＆Magnetsによると：それらはどのように機能しますか？（MakeUseOf）

trトラッカー（ ）を指定していないマグネットリンクをクリックすると、DHTを使用して最初のピアが検出されます。ピアを取得すると、ピア交換も開始されます。

ウィキペディアのDHTの記事では、ピアを見つける方法は指定されていませんが、Kademliaの記事（BitTorrent DHTのベースとなっている）では、次のように述べています。

ネットに参加したいノードは、最初にブートストラッププロセスを経る必要があります。このフェーズでは、参加ノードは、すでにKademliaネットワークに参加している別のノード（ブートストラップノード（ユーザーまたは保存されたリストから取得））のIPアドレスとポートを知っている必要があります。

しかし、どこからそのノードを知っているのでしょうか？マグネットリンクにアドレスなどが表示されません。分散型（トラッカーレス）なので、事前にノードを知っているとは思いません。それとも、DHTは実際には分散化されていませんか？