1

我有一个节点网络,受以下属性的约束:

  • 全局集包含 N 个节点。
  • 每个节点都能够发现 X 个邻居,其中 X << N。
  • 发现邻居是单向操作(即邻居不一定知道自己被发现了,也不一定发现原来的节点)。

我需要完成的是让这些节点自组装一个有效的网络拓扑,这样所有节点都可以用最少的跳数进行通信(我感兴趣的是实用的最小值,而不是理论上的优化最小值,如果它需要解决方案携带额外的复杂性)。这已经是一个普遍解决的问题了吗?也就是说,是否有标准的最佳实践解决方案?

如果我要手动组装节点,我可能会创建一个层次结构,其中一些节点充当其他节点组之间的网关。但是,我不太确定让这些节点自组装的最佳方法是什么。组/层次结构拓扑不是必需的,它只是一个直观的示例。

请注意,一旦拓扑就位,我并不是在寻找有效的消息路由算法(尽管我当然希望拓扑尽可能高效,并且每个节点都尽可能使用接近 X 的通信通道)。

4

1 回答 1

1

听起来您正在寻找分布式哈希表。尽管有这个名字,但它们不仅仅可以用于存储——它们用作通用路由网格,在任意两个节点之间路由消息的预期跳数为 O(log n)。

尽管基本原理保持不变,但至少有几种不同的方法可以实现它们;您可能需要查看KademliaChord作为示例。Kademlia 实现起来更简单,但专注于数据存储和检索;和弦更复杂但更通用。

于 2011-02-21T23:25:52.357 回答