如何向其它所有的邻居节点的specfic邻居之间检查连接，而无需使用节点本身

我开发在我所下列要求每个节点都只有关于其邻居信息的网络协议。节点i的邻居（j）之一想要检查它是否可以在不使用节点i的情况下到达节点i的所有其他邻居。（如果可能的路径不应超过k个链接）。请建议我，如果你有任何想法解决这个问题感谢。如何向其它所有的邻居节点的specfic邻居之间检查连接，而无需使用节点本身

来源

2012-03-22 Rupesh

我想你想要的东西更好，然后琐碎的“删除'i'和'j'运行BFS”？或者它是一个很好的解决方案吗？如果不是 - 您期望什么复杂性？ – amit 2012-03-22 08:23:08

由于您不能存储除节点的邻居以外的任何内容，因此听起来您需要在节点需要执行此检查（然后丢弃结果）时运行routing protocol，如RIP。用RIP你可能会毒害我的直接路径。然后，您可以检查路由表以确定可用路径（那些路径少于k个链路）。还有更多的协议可供选择，但是RIP具有简单易用的优点，并且与OSPF等类似的开销很小。

来源

2012-03-22 12:51:35 jello

I * *觉得RIP将是非常脆弱的[计数到无穷的问题（http://en.wikipedia.org/wiki/Count_to_infinity#Count-to-infinity_problem）在此之情况，因为我们在调用它的触发器[deleing节点'我']很多次...如果你认为我错了（这是很可能的）或解决这个问题 - 请详细说明，我很乐意阅读它，因为我也在思考RIP和找不到解决这个问题的办法。 – amit 2012-03-22 13:12:27

节点i通过j不可达的事实应该传播到所有节点。因此，如果他们使用路径ij，他们将不得不重新评估他们的最佳路线。我认为这不会成为RIP中已经内置的环路预防机制 - 毒性反转，水平分割等问题。 – jello 2012-03-22 17:00:12

如何向其它所有的邻居节点的specfic邻居之间检查连接，而无需使用节点本身

回答

相关问题