Kademlia中的K值是如何选择的？

Question

我阅读了这篇关于Kademlia的论文，链接在这里。

我不理解k（指k-bucket中的k值）是如何选择的。

我不明白这个句子的意思：“k的选择是这样的，任何给定的k个节点很难在一个小时内同时失效。”

我不明白节点故障是什么意思。

- salt

Answer 1

Kademlia是一个抽象算法。不同的实现可以根据网络中节点的预期特征选择自己的k值。例如，如果您想在高可靠性数据中心形成几百个节点的小型覆盖层，则k=2可能足够。BitTorrent使用k=8，并散布在整个互联网上的大量国内节点（即相当不可靠）完成其工作，但其工作并不特别苛刻。因此，仅从这一点就不能推断出这是上限。计算机崩溃、离线、更改互联网连接、重启、进入休眠等都是从网络角度看有效的节点故障。

- the8472

---

那么选择k-bucket大小的确切标准是什么？如果我正确理解了您的回答，您是这样说的：“如果您的网络预计不可靠，请选择更大的k”。这是可以理解的：更大的k意味着我存储有关联系人信息的节点更多。但是为什么我想要保持k值较低呢？是什么阻止我将k设置为无限大，这意味着：不拒绝任何人，只保存所有联系人信息。这不会更好吗？甚至更可靠？我在这里错过了什么吗？ - Piotrek

“k被选择为这样一个数字，即任何给定的k个节点在一小时内同时失败的可能性非常小。” 一旦k足够高以实现该目标，进一步增加将只会产生低效，如过多的路由表维护流量。请记住，Kademlia的目标是提供O(log(n))的行为。 k = ∞意味着将整个网络保留在内存中，这将是O(n)。 - the8472

“过度路由表维护流量”到底是什么？我需要定期向存储在k-bucket列表中的每个节点发送ping消息吗？还是只有在其他新节点请求添加到k-bucket列表时可能替换的那个节点？ - Piotrek

这听起来对我来说像是一个单独的问题，关于Kademlia路由表维护如何工作的问题？ - the8472

Answer 2

以下是我在Kademlia网络行为中发现的k-bucket值重要性的相关信息：

根据使用两级分层DHT覆盖改进社区管理绩效论文：

• 低k值意味着网络更加分散
• 高k值意味着在查找期间跳数较少，但维护流量较高

k值（指Kademlia特定参数的桶大小）对Kademlia DHT的操作有重大影响。一方面，该值不应设置得太低；否则，网络可能会变得分散，从而使某些节点之间的消息路由变得复杂甚至无法实现。另一方面，该值也不应设置得太高，否则将对网络造成大量不必要的维护流量负担。

应该是多少（在大小为100和500的网络上测试）：

测量结果表明，k值为1和2不足以防止网络的分段。选择k值为3足以在两种网络尺寸下实现一致的网络结构。使用k值为4及更大值时，节点对网络的了解进一步发展，但代价是增加了维护流量。虽然平均跳数减少了，但更大的路由表会引起更多的KeepAlive消息。

“维护流量”是指发送的KeepAlive消息数量。 KeepAlive消息被发送到k-buckets中的所有设备，以确保连接处于活动状态。如果我们不发送它们，有一天可能会没有连接，无法参与网络。虽然在本文中，他们每分钟发送了几条这样的消息，但我不确定在现实生活中是否需要那么多。

k-buckets 的另一个用例出现在与本问题链接的论文中：Kademlia: A Peer-to-peer Information System Based on the XOR Metric。一开始我没有注意到它，因为我以为这是原始的 Kademlia 论文。但是，尽管作者相同，结果表明它们的内容不同，它们实际上在讨论 k-buckets 的重要性：

• 他们提倡网络内节点存在时间更长（您越稳定的节点，在网络中的意义就越大）
• 它们可以防止 DoS 攻击，因为新节点不能淹没旧节点所占据的 k-buckets，从而使网络崩溃。

k-buckets 的第二个好处是它们对某些 DoS 攻击提供了抵抗力。通过用新节点淹没系统，无法清除节点的路由状态。只有当旧节点离开系统时，Kademlia 节点才会将新节点插入 k-buckets 中。

因此，我想在选择 k 值时应考虑第二个因素：较高的 k 值意味着你的网络更容易被 Sybil/Eclipse 攻击劫持。

- Piotrek