algorithm - 在距离矢量路由协议的情况下，什么时候说系统已经收敛？

Question

我了解距离矢量路由协议是 Bellman-Ford 算法的分布式版本。它用于找到从每个节点到网络中每个其他节点的最短路径。

因此，每个节点都向其邻居通告其路由表信息（到网络中所有其他节点的计算距离），同时从相邻节点学习。

所以，我的问题是这些广告在邻居之间持续发生多长时间？即，既然这是一个分布式系统，那么每个节点如何知道整个系统已经收敛，我应该停止广告。

就像 Bellman-Ford（集中式）算法一样，我们可以说当迭代次数等于图中边数的 1 倍（网络中链接数的 1 倍）时，收敛已经发生，并且我们可以停止算法执行...

标签： algorithmgraphroutingdistributed

Answer 1

关于该主题的更多学习和搜索不同的文章使我得出以下结论。以下是维基百科的摘录 - https://en.wikipedia.org/wiki/Distance-vector_routing_protocol#Example

没有一个路由器有任何新的最短路径可以广播。因此，没有一个路由器会收到任何可能更改其路由表的新信息。算法停止。

所以这表明 - 在使用距离矢量协议的分布式网络中，当估计的最短路径距离没有更多变化时，节点停止发布信息。而在这个阶段，可以说分布式网络已经融合了。

1. 一旦网络中的节点成为网络的一部分，网络中的节点就会开始公布其初始表（其中将包含到直接连接节点的距离信息）。
2. 并且它不断地向它的邻居通告距离信息，直到它的表发生变化。