algorithm - 如何估计P2P网络中的节点总数？

Question

我正在创建一个没有主节点的 p2p 网络。如何统计总活跃节点数？精度不是关键，但轻量化和性能很重要。

目前我正在考虑两种方法，它们都有很大的缺点......

1. 每个节点都有一个随机数作为其 ID。每个节点都有一个巨大的位数组，最初只有索引== ID处的位为1，其他为0。每个节点与已知的对等节点交换其位数组。节点的位数组使用位或与对等点合并。随着这个过程的进行，最终每个节点都应该有相似的位数组，1的数量表示网络中节点的数量。优点是这可以并行且随时间完成。在查询时，响应可能非常快(因为结果已经存在)。缺点:a)。很难处理已经消失的节点。 b).如果有数百万个节点，则位数组太大。

2. 类似 BFS 的东西。从初始节点开始，它会询问所有已知的对等点有多少个节点已连接。然后将所有响应相加作为待探测网络的总大小。这是一种递归方法。如果一个节点已经收到这样的查询，它将忽略来自其他节点的进一步相同的查询。就像BFS一样。缺点是这很可能不准确。查看 BFS 树，对于每个节点都可能出现单点故障，从而导致该节点的所有查询丢失。考虑从节点 A 初始化查询，查询连接的对等点 B 和 C。B 和 C 然后将查询传播到它们连接的网络。由于某种原因C失败，无法响应A。那么所有从C接收到的直接或间接查询的节点将不被统计。此问题可能发生在网络的任何节点，并可能导致极小的不准确度或较大的不准确度(如上述方法所示)，可能会导致网络的 50% 的不准确度。

知道如何实际估计 P2P 网络中的节点总数吗？

Answer 1

没有完美的方法。如果关键部分上有一个节点不稳定(经常下降和上升)，那么您很可能会因此错过部分网络，并且不知道该部分有多大。即使假设网络连接良好，也很难给出正确的计数，因为算法运行时网络状态可能会发生变化。

您可能不想要第二种方法，因为您将更多的权重放在靠近起点的节点上，就像您所说的那样。

然而，这是对第一种方法的不同看法，它消除了位数组太长的问题，但以牺牲一些准确性为代价。

这个想法非常相似，但是不必计算所有节点(您的 id 必须是唯一且相当连续的)和一个非常大的位数组，您可以拥有随机 id(每台机器选择一个随机的 32/64 位 id) )，而不是传递位数组，而是传递布隆过滤器和计数器。布隆过滤器与数组类似，它可以判断 id 是否尚未插入。然而，它的空间效率更高。缺点是，虽然它有 100% 的召回率(如果过滤器说 id 不存在，那么它确实不存在)，但它没有 100% 的精度(过滤器可能会说 id 已被插入，但实际上它不是)。对于算法来说，这意味着您一定会避免重复计算(很好)，但根据插入的顺序，您可能会错过一些节点。

算法的其余部分是相同的。首先插入您自己的 id 并将计数器设置为 1。将状态发送给所有对等点。当您收到状态时，检查您的 id 是否已插入，如果没有插入，则添加 1 并将状态发送给所有对等点。如果您具有相同的布隆过滤器状态但计数不同，请选择较大的一个(因为我们确信不会重复计数)。最终这些状态将会收敛，这就是你的答案。

Here's有关布隆过滤器如何工作的链接。