在贝尔曼福特算法中究竟会导致计数到无穷大的究竟是什么

Question

根据我的理解,当一个路由器提供另一个旧信息时,会发生计数到无穷大,这些旧信息继续通过网络向无限远传播.根据我的阅读,删除链接时肯定会发生这种情况.

因此,在此示例中,Bellman-Ford算法将针对每个路由器进行收敛,它们将具有彼此的条目.R2将知道它可以以1的成本到达R3,并且R1将知道它可以通过R2以2的成本到达R3.

如果R2和R3之间的链路断开连接,则R2将知道它不能再通过该链路到达R3并将其从表中删除.在它可以发送任何更新之前,它可能会收到来自R1的更新,它将宣传它可以以2的成本到达R3.R2可以以1的成本到达R1,因此它将更新到R3通过R1,成本为3.然后,R1将从R2接收更新,并将其成本更新为4.然后,他们将继续向无穷大提供不良信息.

我所看到的一件事提到了一些地方,除了只是一个离线的链接,比如改变一个链接的成本,还有其他可以计数到无穷大的原因.我开始考虑这个问题,从我所知道的情况来看,在我看来,链接的成本增加可能会导致问题.但是,我没有看到降低成本可能导致问题.

例如,在上面的示例中,当算法收敛并且R2具有到成本为1的到R3的路由时,并且R1具有到R2经由R2的路由,成本为2.如果R2和R3之间的成本增加到5.然后这会导致同样的问题,R2可以从R1获得更新广告,成本为2,并通过R1,R1将其成本更改为3,然后通过R2将其路由更改为4,依此类推.但是,如果成本在融合路线上降低,则不会导致变化.它是否正确？链接之间的成本增加可能导致问题,而不是降低成本？还有其他可能的原因吗？将路由器脱机与链接出去是一样的吗？

Answer 1

看看这个例子:

路由表将是:

    R1   R2    R3
R1  0    1     2
R2  1    0     1
R3  2    1     0

现在,假设R2和R3之间的连接丢失(你可以断线或者它们之间的中间路由器掉线).

在发送信息一次迭代后,您将获得以下路由表:

    R1   R2    R3
R1  0    1     2
R2  1    0     3
R3  2    3     0

这是因为R2,R3不再连接,因此R2"认为"它可以通过R1将路径重定向到R3,路径为2 - 因此它将获得权重3的路径.

在额外的迭代之后,R1"看到"R2比以前更昂贵,因此它修改了它的路由表:

    R1   R2    R3
R1  0    1     4
R2  1    0     3
R3  4    3     0

等等,直到它们收敛到正确的值 - 但这可能需要很长时间,特别是如果(R1,R3)价格昂贵.
这被称为"数到无穷大"(如果w(R1,R3)=infinity并且是唯一的路径 - 它将继续永远计数).

请注意,当两个路由器之间的成本上升时,您将遇到相同的问题(假设w(R2,R3)在上面的示例中最多为50).同样的事情将发生 - R2将尝试路由到R3通过R1而不依赖于"实现" (R2,R3),并且一旦找到正确的成本,您将得到相同的第一步并收敛.
但是,如果成本下降 - 由于新成本优于当前成本,将不会发生 - 并且路由器R2将坚持使用相同的路由并降低成本,并且不会尝试路由R1.