CN-距离向量链路算法2

[[CN-NotesView]]

Bellman-Ford方程（动态规划）

令：

$d_x(y) = min_distance(x \to y) = min{c(x,v) + d_v(y)}$

c(x,v) 代表的是x到v的费用

$dv(y)$ 从邻居v到目的y的费用

Bellman-Ford举例

显然：$d_v(z) = 5,\ \ \ d_x = 3,\ \ \ d_w(z)=3$

根据B-F方程：

$d_u(z) = min {c(u,v) + d_v(z), \ \ c(u,x) + d_x(z), \ \ c(u,w) + d_w (z)} \ = min{\ 2+5,\ 1+3,\ 5+3} = 4$

重点: 结点获得最短路径的下一跳,该信息用于转发表中

距离向量路由算法

$D_x(y) =$ 从结点x到结点y的最小费用估计

x 维护距离向量(DV) ： $D_x = [D_x(y): y \in N]$

结点x:

已知到达每个邻居的费用: c(x,y)
维护其所有邻居的距离向量：$D_v = [D_v(y): y \in N]$

核心思想

每个结点不定时的把其自身的DV估计发送给其邻居

当接收到邻居的新的DV估计的时候，也就是根据B-F更新其自身的路由向量估计：

$D_x(y) \leftarrow min{c(x,y) \ + \ D_v(y)} \ for \ each \ node\ y \in N$

最后$D_x(y)$将会收敛到最小值。

异步迭代

引发每次局部迭代的因素

局部链路费用改变
来自邻居的DV更新

分布式算法

每个结点只有当DV变化的时候才通告邻居

邻居在必要的时候再通告它们的邻居

每个节点的阶段：

等待：每个路由器在没有发生变化的时候就保持这种状态（邻居DV没有发生更新）

重新计算 DV估计

如果DV中到达任一一个目的距离发生改变，通告所有的邻居

然后再次进入等待状态

举例

初始的距离向量为：

距离向量DV：链路费用变化

链路费用的变化：

结点检测本地链路费用的变化
更新路由信息，重新计算距离向量
如果DV改变，通告所有的邻居

$t_0$ : y检测到链路费用的改变，更新DV，通告其邻居

$t_1$ : z收到y的DV更新，更新其距离向量表，计算到达x的最新最小费用，更新其DV，并发送其所有的邻居。

$t_2$ ：y收到z的DV更新，更新其距离向量表，重新计算y的DV，未发生改变，不再像z发送DV

“好消息传播的快”

但是可能出现无穷计数问题（如上所示）

毒性逆转

如果一个结点(e.g.z)到达某目的(e.g.X)的最小费用路径是通过某个邻居(e.g.Y)，则:

通告给该邻居结点到达该目的的距离为无穷大

毒性逆转是不是能够彻底的消除无穷计数问题？

简单的环路是可以消除的，更复杂的环境其实未必可以满足。

定义最大的一个距离度量值(maximum metric)

定义一个最大的有效费用值，比如15跳步，16跳步标识无穷

如果一直不可达，就会在有效费用值耗尽的时候结束传输