距离向量路由算法 |
您所在的位置:网站首页 › 分布式路由选择 › 距离向量路由算法 |
一、距离向量路由算法特点
距离向量路由算法是一种迭代的、异步的和分布式的算法。 (1)分布式:每个节点都从其直接相连邻居接受信息,进行计算,再将计算结果分发给邻居。 (2)迭代:计算过程一直持续到邻居之间无更多信息交换为止。 (3)异步:不要求所有节点相同之间步伐一致地操作。 (4)自我终结:算法能自行停止。 最低费用表示: d
x
_x
x(y)=min
v
_v
v{c(x,v)+d
v
_v
v(y)}。 d
x
_x
x(y):节点x到节点y地最低费用路径的费用; v:节点x的邻居节点; c(x,v)+d
v
_v
v(y):x与某个邻居v之间的直接链路费用c(x,v)加上邻居v到y的最小费用,即x经v到节点y的最小路径费用。 对每个节点x (1)在每个节点建立自己的距离向量表并初始化。 (2)在每个节点将自己维护的距离向量表向其邻居节点转发。 (3)每个节点收到邻居节点发送的距离向量表以后基于新的信息采用方程来更新自己的距离向量表。 (4)当自己的距离向量表发生变化时,将新的距离向量表发送给自己的邻居节点,如果与以前的向量表相同则不向其邻居节点转发,直到每个节点的距离向量表达到稳定为止。 当一个节点检测到从它到邻居的链路费用发生变化时,就更新其距离变量,如果最低费用路径的费用发生变化,通知其邻居。 (1)某条链路费用减少时 如图所示,假设x与y之间的链路费用从4增加到60。 链路费用变化前: Dy(x)=4,Dy(z)=1,Dz(y)=1,Dz(x)=5 t0时刻:在t0时刻,y检测到链路费用从4变为60。更新到x的最低路径费用 d y _y y(x)=min{d x _x x(x)+c(y,x),d z _z z(x)+c(y,z)}=min{0+60,1+5}=6 经节点z到x费用最低,此新费用错误,发给节点z。 t1时刻;t1时刻z收到新费用,更新其到x的最低路径费用 d z _z z(x)=min{d x _x x(x)+c(y,z),d y _y y(x)+c(z,y)}=min{0+50,1+6}=7 经节点y到x费用最低,发给节点y。 t2时刻:y收到新费用,更新到x的最低路径费用 d y _y y(x)=min{d x _x x(x)+c(y,x),d z _z z(x)+c(y,z)}=min{0+60,1+7}=8 经节点z到x费用最低,发给节点z。 以此节点y或节点z的最低费用不断更新。 这里就产生了选路循环:为到达x,y通过z选路,z又通过y选路。即目的地为x的分组到达y或z后,将在这两个节点之间不停地来回反复,直到转发表发送改变为止。 上述循环将持续44次迭代,直到z最终算出它经由y地路径费用大于50为止。并确定z到x地最低费用路径是zx,y到x地最低费用路径是yzx。 通过上述两个变化我们可知链路费用减少地好消息传播的快,而链路费用增加的坏消息传播很慢。甚至当链路费用增加很大时会出现“计数到无穷”问题。 四、链路状态路由算法和向量路由算法对比(1)消息复杂度 链路状态路由算法(LS):需要知道每条链路的费用,需发送O(nE)个报文;当一条链路的费用发生变化时,必须通知所有节点。 距离向量路由算法(DV):迭代时,仅在两个直接相连邻居之间交换报文;当链路费用改变时,只有该链路相连的节点的最低费用路径发生改变时,才传播已经、改变的链路费用。 (2)收敛速度 LS:需要O(nE)个报文和O(n 2 ^2 2)的搜寻。 DV:收敛较慢。可能会遇到选路回环,或计数到无穷的问题。 (3)健壮性:当一台路由器发生故障、操作错误或受到破坏时 LS:路由器向其连接的一条链路广播不正确费用,路由计算基本独立(仅计算自己的转发表),有一定健壮性。 DV:一个节点可向任意或所有目的节点发布其不正确的最低费用路径,一个节点的计算值会传递给它的邻居,并间接地传递给邻居的邻居。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |