在Pastry P2P网络中的节点处创建路由表

Question

这个问题是关于在基于Pastry的p2p网络中的一个节点上创建路由表。

我正在尝试在单个JVM中模拟这种路由表创建方案。我似乎无法理解这些路由表是如何从第一个节点的连接点开始创建的。我有N个独立的节点，每个节点都有一个生成为SHA-1散列的160位nodeId和一个用于确定这些节点之间的接近度的函数。假设第一个节点启动并加入了环。协议说这个节点此时应该已经设置了它的路由表。但是此时环中没有任何其他节点，那么它是如何开始创建其路由表的呢？

当第二个节点希望加入该环时，它向第一个节点发送加入消息(包含其nodeID)，该加入消息以跳的方式传递到该第二个节点的已经存在于该环中的最近的可用邻居。这些跳数有助于为这个新的第2个节点创建路由表条目。同样，在缺乏足够数量的节点的情况下，如何创建所有这些条目？

我刚刚开始研究FreePastry实现，以获得这些答案，但目前似乎还不是很明显。如果有人能在这里提供一些建议，那也是很有帮助的。

Answer 1

我对糕点的理解并不完整，但这足以构建一个或多或少有效的算法版本。也就是说，据我所知，我的实现运行正常。

回答你的第一个问题：

协议说，第一个节点此时应该已经设置了路由表。但是此时环中没有任何其他节点，那么它是如何开始创建其路由表的呢？

我首先创建了Node及其状态/路由表，从而解决了这个问题。仔细想想，路由表只是网络中其他节点的信息。由于这是网络中的唯一节点，因此路由表为空。我假设您有创建空路由表的方法？

回答你的第二个问题：

当第二个节点希望加入该环时，它向第一个节点发送加入消息(包含其nodeID)，该加入消息以跳数的方式传递到该第二个节点的已经存在于该环中的最近的可用邻居。这些跳数有助于为这个新的第2个节点创建路由表条目。同样，在缺乏足够数量的节点的情况下，如何创建所有这些条目？

你应该再看看the paper (PDF警告！)这描述了Pastry；它很好地解释了节点加入和退出集群的过程。

如果内存有效，第二个节点发送的消息不仅包含其节点ID，而且实际上使用其节点ID作为消息的关键字。消息像网络中的任何其他消息一样被路由，这确保它在其ID与新加入的节点的ID最接近的节点处快速结束。消息经过的每个节点都将其状态表发送给新加入的节点，该节点用来填充其状态表。本文解释了一些深入的逻辑，这些逻辑在使用信息填充状态表时考虑了信息的来源，我相信这种方式是为了减少计算成本，但在我的实现中，我忽略了这一点，因为它的实现成本更高，而不是更少。

但是，具体地回答您的问题:第二个节点将向第一个节点发送加入消息。第一个节点将其状态表(空)发送到第二个节点。第二个节点将状态表的发送者(第一个节点)添加到它的状态表中，然后将接收到的状态表中的适当节点添加到它自己的状态表中(在这种情况下，没有节点)。第一个节点将把消息转发到与第二个节点的ID更接近的节点，但是不存在这样的节点，因此该消息被认为是“已传递”的，此时两个节点都被认为是参与网络的。

如果第三个节点加入并将加入消息路由到第二个节点，则第二个节点将向第三个节点发送其状态表。然后，假设第三个节点的ID更接近第一个节点的ID，第二个节点将把消息转发给第一个节点，第一个节点将向第三个节点发送其状态表。第三个节点将从这些接收到的状态表中构建其状态表，并且在这一点上它被认为是参与网络的。

希望这能有所帮助。