本文仅对LS和DV进行简单的介绍, 由于作者初学计算机网络, 同时也没有学习图论的知识, 若有不妥之处还请指出.
一、链路状态算法(LS)
特殊量:
- D(v):直到本次迭代,从源节点到节点v的最低路径开销
- p(v):从源到v沿着当前最低开销路径的前一节点
- N':已确定最短路径的节点集
- c(a, b):两个相邻节点a, b,c(a, b)是a到b的距离
内容:
//初始化
N' = {u} //将起点u初始化进N中
对于所有节点v
if v与u相邻
then D(v) = c(u,v) //将到u,v的距离记为到v的最小距离
//初始化时的最小距离不一定是真正的最小距离
else D(v) = 正无穷
//循环
在还未记入N'的所有点中找到点w, 使得D(w)最少
将w节点加入N'
新的节点加入后,以这样一种法则更新每个节点的D(v)
D(v) = min(D(v), D(w)+c(w,v))
//看一下w加入后产生新的走法是否要更快
当N' = N 时,结束循环
该算法会不断更新N', 并进一步地更新最佳路径, 最终找到最短路径
二、距离向量路由选择算法(DV)
特殊量:
-
x到y的最短路径 = c(x, v) + v到y的最短路径
其中,对于x的所有邻居, 存在一个节点v使上式满足
-
Dx = [Dx(y): y属于N]
Dx是节点x的距离向量, 包含x到N之中的每一节点的开销估计值
-
使用DV算法, 每个节点应当维护这几个值
- 直接到每个邻居的距离c(x, v)
- 节点x的距离向量Dx
- 每个邻居的距离向量Dv
-
那么由上述的方程
x到y的最短路径 = c(x, v) + v到y的最短路径可以推出距离向量的更新方法:Dx(y) = min( c(x, v) + Dv(y) ) 即,先在x的所有节点中选择一个节点v, 使得c(x, v) + Dv(y)最小 则,x到y的最短路径 = x到v的距离 + v到y的估计最短路径内容:
//初始化 对于N中的所有终点y: Dx(y) = c(x, y) //若x, y不为邻居, 则c(x, y)为正无穷 对于x的每个邻居w Dw(y) = ? for all destination y in N //估计w到y的开销, 式中以?替代 对于x的每个邻居w 向每个w发送距离矢量Dx //循环 wait until 发现到邻居的链路开销变化 or 收到某个邻居w的距离向量 对于N中的每一个y Dx(y) = min( c(x, v) + Dv(y) ) //更新估计值 if x 的距离向量变化了 则, 发送 x 的距离向量给每一个邻居 通过邻里之间的联系不断更新最低开销的预估值, 由于总会有一个v(可能是邻居的邻居的...的邻居)与目的地y相连, Dv若是最短路径便可以依次传回, 最终被源节点x所接收.