中毒反向 - 循环大小大于 2

Question

据说中毒反向可以防止路由环路，但只能防止大小为2的路由环路。为什么不能防止更大大小的路由环路呢？换句话说，即使反向中毒，是否仍然可能发生循环？我尝试在网上查找，但还没有找到示例。

Answer 1

A ¯¯\
|    C———D
B __/

上图中（我现在甚至无法上传具有 3 点声誉的图像）。现在C-D失败了，假设从B到D的原始最优路径是B-A-C-D，这意味着B将把这条从B看来的最优路径通告给C。

在这种情况下，即使进行了毒性逆转，C 也可以选择 B 作为 D 的下一跳。再次形成环路。

我也尝试在网上搜索一个示例...所以我找到了你的帖子:)，但我终于在以下链接中找到了一个示例：

http://www.mpi-sws.org/~gummadi/teaching/sp07/datanets/homework/homework2solution.pdf

Answer 2

注意：这应该是一条评论。不幸的是我没有足够的声誉。

作为对钟回答的补充，我想指出这可能不是一个大问题。

我们假设每个边缘都有 1 毫秒的延迟。

现在，

a: 2ms, b: 2ms, c: 1ms

。如果

c--d

损坏，则：

a: 2, b: 2, c: 1
  (change c)
a: 2, b: 2, c: 3
  (change a, b)
a: 4, b: 4, c: 3
  (change c)
a: 4, b: 4, c: 7
  (change a, b; now the next hop of a, b is c, because of poison reverse)
a: 11, b: 11, c: 7
... ...

您可以看到延迟增加的速度有多快。事实上，延迟会随着时间呈指数级增长。在不到 30 轮的时间内，延迟将变得如此之大（请参见下面的计算），以至于在所有实际方法中，A 被认为是无法达到的。

>>> l
array([1, 2])
>>> m
array([[1, 3],
       [1, 5]])
>>> np.linalg.matrix_power(m, 1) @ l
array([ 7, 11])
>>> np.linalg.matrix_power(m, 1 + 30 // 4) @ l
array([1296400, 2007584])