贝尔曼-福特算法中，什么会导致计数到无限大？

Question

贝尔曼-福特算法中，什么会导致计数到无限大？

15

据我所理解，计数到无穷大是指一个路由器向另一个路由器提供旧信息，这些信息会继续在网络中传播直至无穷大。从我所读的内容来看，当一个链接被移除时，这种情况肯定会发生。

enter image description here

因此，在本例中，Bellman-Ford算法将对每个路由器进行收敛，它们将彼此拥有条目。R2将知道它可以以成本1到达R3，而R1将知道它可以通过R2以成本2到达R3。

如果R2和R3之间的链接断开，则R2将知道它不能再通过该链接到达R3，并将其从表中删除。在发送任何更新之前，可能会收到来自R1的更新，表示它可以以成本2到达R3。R2可以以成本1到达R1，因此它将更新一个路由，通过R1到达R3，成本为3。然后，R1稍后会收到来自R2的更新，并将其成本更新为4。然后他们将互相传递错误信息并持续不断。

我看到有些地方提到，导致计数无限的原因不仅仅是链接离线，还可能包括链接成本的变化。我思考了一下，据我所知，链接成本的增加可能会导致问题。然而，我并没有看到降低成本会导致问题的可能性。

例如，在上面的示例中，当算法收敛时，R2以1的成本到达R3，R1通过R2以2的成本到达R3。如果R2和R3之间的成本增加到5，则会导致相同的问题，R2可以从R1接收到成本为2的更新，并通过R1将其成本更改为3，然后R1通过R2将其路由成本更改为4等等。但是，如果已经收敛的路由成本降低，则不会引起变化。这是正确的吗？是链接成本的增加可能会导致问题，而不是降低成本？还有其他可能的原因吗？将路由器离线是否与链接离线相同？

- Cory Gross

你确定你在谈论贝尔曼-福德算法吗？ - Jun HU

@JunHU：这是一种特殊的分布式BF变体，通常用于路由。 - amit

这听起来像是http://stackoverflow.com/questions/13509348/bellman-ford-distance-vector-algorithm-with-arbitrarily-many-nodes/13522076#13522076。 - ashley

@ashley，我在大学考试中遇到了类似的问题，但它并不完全与我在这里所问的相同。我仍然没有找到许多确切的答案来源来解决这种情况，但我找到的所有信息都指向提高链接成本会导致问题，而降低则不会。 - Cory Gross

4个回答

2

根据维基百科的说法：

RIP使用分割视图和毒性反转技术来减少形成环路的机会，并使用最大跳数来解决“计数无限”问题。这些措施避免了一些情况下的路由环路形成，但并非所有情况都适用。添加保持时间（在路由撤销后拒绝路由更新几分钟）可以在几乎所有情况下避免环路形成，但会显著增加收敛时间。最近，已经开发了许多无环距离向量协议 - 显著的例子包括EIGRP、DSDV和Babel。这些协议在所有情况下都避免了环路形成，但是复杂度增加了，并且它们的部署受到链路状态路由协议（如OSPF）的成功影响而放缓了。

http://en.wikipedia.org/wiki/Distance-vector_routing_protocol#Workarounds_and_solutions

- Anand Srinivasan

1

这并没有涉及Bellman-Ford算法的部分，但这是一个简化的答案。如下所示。

请注意原帖中的图片。有R1、R2和R3；分别代表路由器1、2和3。

每个链接成本为1，每个跳数成本为1。要跳过两个路由器（例如：从R1到R3）需要2的成本。

每个路由器都会跟踪成本并更新信息。然而，如果有缺失值（例如，路由器之间缺少连接），则跳数将被删除，并在路由表更新时由另一个路由器填充。

例如：

如果路由器3到路由器2的链接断开，路由器2将从其表中删除该路由。路由器1仍然认为需要两个跳才能到达路由器3。这被复制到路由器2，现在两个路由器都认为需要两个跳才能到达路由器3。

路由器1进行了一些简单的数学运算：“如果我到路由器2只需要一跳，而路由器2到路由器3需要两跳，那么我到路由器3需要三跳。太聪明了！”路由器2进行类似的数学运算，并在其路线中增加一跳，依此类推。

这就是循环的工作原理。

- BlitzThunderWolf93

0

锁定：

随着度量增加，延迟传播信息

限制：

延迟收敛Loop avoidance
路由广告中包含完整路径信息
显式查询回路（例如DUAL）分割视野
从不通过其下一跳广告目标
- A不会将C广告给B
毒性反转：通过其下一跳广告目标时发送负面信息
A以∞的指标向B广告C
- 限制：仅适用于大小为2的“回路”

- kosai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

来看这个例子：

在此输入图像描述

路由表将会是：

    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会“认为”可以通过路径2重定向数据包到达R3，在经过R1时，路径的权重会变为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 将尝试通过R1 路由到R3，而不“意识到”它也取决于（R2，R3），并且一旦找到正确的成本，您将获得相同的第一步并收敛。
但是，如果成本降低 - 它将不会发生，因为新成本比当前成本更好 - 路由器R2将坚持具有降低成本的相同路由，并且不会尝试通过R1路由。