计网自顶向下 路由选择环路的疑问？

[amiwrong123]

如上这个图，我对照了英文的 pdf ，也是这么写的。然后就有很多疑问。。。 第一：从 x 到 z 的距离在图里明明是 50 ，但原文就是说是 5 ，好，那这里我当是图里的数字错了，其实应该是 5.

第二：书里说：“经过 z 的这个新费用是错误的”，但我看就是正确的阿。y 到 x 的话，最小消耗，就是 y => z => x 啊。

第三：z 会更新自己的路由表。所以 Dz(x)=5,即从 z 到 x 的最小消耗是直接从 z 到 x 。所以一个包从 y 到达 z 后，就会直接转到 x 啊，也就不会出现 路由选择环路 了阿？

[coolan]

没仔细看，但是 x-z 最短距离为 4+1

[amiwrong123]

@coolan #1
嗯，但说的是消耗从 4 变成 60. 的之后的过程

[coolan]

我看他写挺明白了，就是由于 4 变为 60 ，z 没更新，导致 y 以为从 z 到 x 是 5 ，然后给 z 发，但是 z 那个 5 的路径是给 y ，这样就回路了。这里你得认为 z 始终没有更新它的路由费用。

[dai201617]

楼上老哥解释的挺清楚了。你的第一个问题出发点错了，Dz(x) = Dz(y) +Dy(x) = 4+1 ，所以书上 x 到 z 距离为 50 并没错。这个问题想明白，后面就好理解了

[xiaopc]

Dz(x) 是 z 通报给 y 的，y 不知道 z 其实是通过自己 (y) 来达到 Dz(x)=5 ，z 也不知道 c(y,x) 改变了

[lmshsqlc]

变更前：
y 知道直接去 x 的路只要 4 块
z 知道直接去 y 的路只要 1 块
z 想去 x ，y 告诉他要 4 块，自己的路要 50 块。所以 z 核算成本，走 y 只要 5 块钱，所以 z 记下来了。
所以这时候：
y 觉得直接去 x 要 4 块，走 z 要 51 块
z 觉得直接去 x 要 50 块，走 y 要 5 块

那么价格一改：
y 发现直接去 x 要 60 块，但是他那边记得走 z 只要 51
z 记得直接去 x 要 50 块，走 y 要 5 块

于是咋的：
y 觉得走 z 只要 51 ，就发到 z 去了。
z 觉得走 y 只要 5 块，就发给 y 了。

大概是这么个故事？

[2i2Re2PLMaDnghL]

c(z,x)=50 没错
因为 z 不知道 c(y,x) 改变了，所以 Dz(x) 错误地被认为是 5 ，实应为 50
所以他们为什么不加撇号，数学推演不加撇号谁知道你改变了
Dy'(x) = min{c'(y,x)+Dx(x), c(y,z)+Dz(x)} = min {60+0,1+5} = 6

理论上来说，每次被请求发送时回传 cost 应该是可以做到趋稳的。

[2i2Re2PLMaDnghL]

@2i2Re2PLMaDnghL 没撇全，不过又想起撇号可能和导数混淆？虽然这里不太可能涉及导数，还是标数字
Dy1(x) = min{c1(y,x)+Dx1(x), c1(y,z)+Dz0(x)} = min {60+0,1+5} = 6
当然 Dx1(x) = Dx0(x) 且 c1(y,z) = c0(y,z)，所以这两个没问题，然而最后一项还是 Dz0(x)
意思就是 Dz(x) 的根据 t=0 状态计算了。
如果每次回复代价，则会在 45 次沟通后重新趋稳，然而这就是 45 倍风暴了…… 总体代价也颇高。

[amiwrong123]

老哥，再问下，这里之所以叫做无限计数，只是单纯因为从 6 加到>9999 需要很多次吗，所以就叫做 无穷计数吗？或者还是说 跟其他原因有关
@2i2Re2PLMaDnghL #8

[2i2Re2PLMaDnghL]

@amiwrong123 看上去是在说随着成本增量的增加，上涨消息传递时间会任意提升。
1e4 需要这么这么多次，那么如果是 1e5 呢？ 1e10 呢？ 1e20 呢？
所以需要次线性，最好是对数时间复杂度的算法，或者说上涨消息传递时实际上涨应当是超线性甚至是指数性的。