私はすでに、このトピックに関する多くのドキュメントをレビューしましたが、明確でないことがあります。たとえば、ビット トレント ドキュメント ( http://www.bittorrent.org/beps/bep_0005.html ) には次のように記載されています。
ルーティング テーブルは、それぞれがスペースの一部をカバーする「バケット」に分割されます。空のテーブルには、最小 = 0、最大 = 2^160 の ID スペース範囲を持つ 1 つのバケットがあります。ID「N」を持つノードがテーブルに挿入されると、最小 <= N < 最大のバケット内に配置されます。空のテーブルにはバケットが 1 つしかないため、ノードはその中に収まる必要があります。各バケットは、「満杯」になる前に K ノード (現在は 8 つ) しか保持できません。バケットが既知の正常なノードでいっぱいになると、独自のノード ID がバケットの範囲内に収まらない限り、それ以上ノードを追加できません。その場合、バケットは、それぞれが古いバケットの半分の範囲を持つ 2 つの新しいバケットに置き換えられ、古いバケットのノードは 2 つの新しいバケットに分散されます。バケットが 1 つしかない新しいテーブルの場合、
ノードIDのビットプレフィックスに従ってバケットが配置されるkademliaルーティングテーブルに関する他のドキュメントとは少し異なりますが、もう1つ紛らわしいことがあります。「ノードの検索」リクエストに応答するとき、XOR 操作を使用して、リクエストされたノードに最も近い 8 つのノードを見つける必要があります。一部の実装では、XOR 操作を実行するルーティング テーブル内の各アイテムを調べて、最も近い 8 つのアイテムを見つけました。私にもCPUの浪費のようです。
すべてがすでにバケツに入っています。ビット トレント ドキュメント システムによって提案されたものを使用したとしても、バケットを列挙してその最小数と最大数をチェックするだけで、要求されたノード ID を含む可能性のあるバケットをより迅速に見つけることができます。次に、潜在的にそのバケットにクローズノードが含まれている必要がありますが、それらはXORに最も近いノードではなく、値に最も近いノードです(私が理解しているように)。これは多少異なりますが、多少似ています。
0 から 99 までの数字を使用して簡単なテストを実行しました。ここでは、最も近い 8 つの XOR 数字を見つけたいと思っていました。ここで、バケットについて考えてみると、バケット内のすべてのノード ID がマイナーな例外に最も近い可能性があると思います。したがって、たとえば、このバケットを左から 1 つと右から 1 つ取得し、XOR 最も近いノード ID を検索すると、探しているものが見つかります。ルーティングですべてのノードを通過する意味はありません。テーブル。
私は正しいですか、それとも何か不足していますか?