1

这是一个关于大型可扩展 P2P 网络方法的问题:逻辑环网 ovrlay。

考虑 P2P 网络的环境。有 N 台计算机通过一个环将每个人相互连接起来。每个节点都有一个路由表,用于存储前任节点和后继节点。这是路由表只存储前驱和后继的最简单的情况。每个节点都有一个 id,它是一个数字。环的组织方式使升序的数字按顺时针方向分配。

所以我们可以有这样的情况: * - 12 - 13 - 45 - 55 - 180 - 255 - * 这个网络有 6 个节点,它们相互连接。

当一个节点必须向另一个节点发送消息时,使用路由表,如果通用节点有传入消息,它会查看目标地址,如果不在他的路由表中,则后继或前任将由路由决定它。

现在让我们考虑这个例子。在我的简单网络中,节点 13 想向节点 255 发送消息。由于每个节点只能看到前任和后继,所以每个节点都无法考虑全局网络,在 P2P 中,实际上一个节点只能看到网络的一部分。所以节点 13 需要做出决定:将消息路由到哪里(因为目的地不在其附近)?消息必须发送到 45 还是 12?(顺时针还是逆时针?)。

好吧,显然,发送到 12 是一个更好的决定,但是节点 13 是如何知道这一点的呢?

最简单的解决方案是:总是顺时针走,但在这种情况下,一个非常近的节点将在很长一段时间内到达......而它在拐角处......

如何处理?

PS:有一些解决方案Fingering适用于基于顺时针路由的方法。指法将其他地址放入路由表中以创建跳转链接...这是一种可以使用但仅使用顺时针路由的解决方案...

http://en.wikipedia.org/wiki/File:Chord_route.png

我想知道一个好的解决方案以找到正确的路由方向......它存在吗?Chord 如何处理这个问题?

谢谢你。

4

1 回答 1

2

如果每个节点都记得到下一个、第二个、第四个、第八个等的链接,那么找到任何节点只需要 log(n) 时间。我相信这已经足够快了,可以不用考虑是顺时针还是逆时针。

于 2011-05-14T13:22:36.230 回答