CN-距离向量路由算法

[[CN-NotesView]]

距离向量(Distance Vector)路由算法

Bellman-Ford方程(动态规划)

令：dx(y):从x到y最短路径的费用(距离)

dx(y) = min {c(x,y) + dv(y)}

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

dv(y) 代表从邻居v到达目的y的费用（距离）

在x的所有邻居v中取最小值

Bellman-Ford举例

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

距离向量路由算法

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

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

结点x：

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

核心思想：

• 每个结点不定时的将其自身的DV估计发送给其邻居
• x当收到另据的新的DV估计的时候，根据B-F方程来更新自身的距离向量估计

将最终收敛于实际的最小费用

特点

异步迭代

引发每次局部迭代的因素

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

分布式

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

邻居在必要的时候（其DV更新后发生改变）

• 邻居在必要的时候(其DV更新后发生改变)再通告它们的邻居

每个节点：

等待本地局部链路费用变化或者收到邻居的DV的更新

重新计算DV估计

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