algorithm - 如何在不使用节点本身的情况下检查节点的特定邻居与所有其他邻居之间的连接性

Question

我正在开发一个网络协议(protocol)，其中我有以下要求每个节点只有关于其邻居的信息。节点 i 的邻居(j)之一要检查它是否可以在不使用节点 i 的情况下到达节点 i 的所有其他邻居。 (如果可能，路径不应超过 k 个链接)。如果您有解决此问题的想法，请建议我谢谢。

Answer 1

因为除了一个节点的邻居你不能存储任何东西，听起来你需要运行一个 routing protocol每当节点需要执行此检查(然后丢弃结果)时，例如 RIP .使用 RIP，您可以毒化到 i 的直接路径。然后您可以检查路由表以确定哪些路径可用(那些链接少于 k 的路径)。有更多的协议(protocol)可供选择，但 RIP 的优点是简单明了，与 OSPF 之类的协议(protocol)相比开销很小。