距离矢量算法解析幻灯片

1、距离矢量算法解析,主要内容,1、什么是动态路由 2、动态路由根据算法的分类 3、距离矢量算法详解 4、路由环路 5、水平分割,2020/10/19,动态路由协议,动态路由协议特点 向其他路由器传递路由信息 接收其他路由器的路由信息 根据收到的路由信息计算出到每个目的网络的最优路径，并由此生成路由表 根据网络拓朴变化及时调整路由表，同时向其他路由器宣告拓朴改变的信息,2020/10/19,动态路由协议,根据路由所执行的算法分类 距离矢量路由协议 链路状态路由协议,2020/10/19,距离矢量路由协议,路由器每经过特定时间周期向邻居发送自己的路由表 距离：有多远 矢量：从哪个方向,R1,R2,R

2、,我能够到达路由器R，距离是5,我通过R2可以到达路由器R，R2到R之间的具体细节我不清楚,2020/10/19,距离矢量详解,R1,R2,距离矢量算法思想： 矢量距离算法（简称VD算法）的思想是：网关周期性地向外广播路径刷新报文，主要内容是由若干（V，D）序偶组成的序偶表；（V，D）序偶中的V代表“向量”，标识网关可到达的信宿（网关或主机），D代表距离，指出该网关去往信宿V的距离；距离D按驿站的个数计。其他网关收到某网关的（V，D）报文后，据此按照最短路径原则对各自的路由表进行刷新,2020/10/19,RIP工作原理 - 距离矢量算法,路由算法 D( i, j)= 0 D( i, j) =

3、MIN d(i, k)+ D(k, j) k为所有与i相邻的路由器 图示距离矢量算法,距离矢量详解,A,B,C,F,G,D,E,1、对距离向量路由所做的初始假设是每个结点都知道其邻接点得链路开 销。 到不相邻结点的链路开销被指定为无穷大； 2、每条路径的开销为1，所以开销最小的路径就是包含跳数最少的路径。,距离矢量详解包含到其他所有结点开销,存储在每个结点中的初始距离,距离矢量详解发送包含自己距离表的消息给其他邻接点,1、结点F告诉A它可以到结点G，开销为1，A也知道它能以开销1到达F，因此二者相加就可以知道经F到G的开销；A到G的总开销2小于当前的开销无穷大，因此A记录它可经F到达G，开销为

4、2； 2、类似的，A从C得知，C能以开销1到达D；A将此与到C的开销1相加，决定可通过C以开销2到达D，优于旧的开销无穷大 3、同时，A从C得知，C能以开销1到达B，因此它推断经C到B的开销为2，这比当前A到B的开销1大，因此新的信息被忽略。,2020/10/19,距离矢量详解发送包含自己距离表的消息给其他邻接点,结点A的初始路由表,结点A的最终路由表,距离矢量详解,存储在每个结点的最终距离,2020/10/19,路由环路1,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,Page 13/54,路由环路2,R1,R2,R3,10

5、.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,发送40.0.0.0的跳数为1的更新信息,被标记为无效,2020/10/19,路由环路3,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,发送40.0.0.0的路由更新，跳数为2,将跳数改变为2跳，下一条地址为30.0.0.1,2020/10/19,路由环路4,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0,.1,.1,.2,.2,产生路由环路，直到跳数增加到16为止,将跳数改变为3跳,2020/

6、10/19,解决路由环路的方法,水平分割 毒性反转 触发更新 Hold-down倒计时,2020/10/19,10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,X,X,C,B,A,水平分割,RIP从某个接口学到的路由不再从该接口发布给其他路由器,2020/10/19,当一条路径信息变为无效之后，路由器并不立即将它从路由表中删除，而是用16，即不可达的度量值将它广播出去。缺点增加了路由表的大小。,毒性反转,10.1.0.0,10.2.0.0,10.3.0.0,E0,S0,S0,S1,S0,E0,X,Subnet 10.4.0.0 me

7、tric 16,A,B,C,2020/10/19,触发更新,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,subnet 10.4.0.0, metric 16,10.1.0.0,subnet 10.4.0.0, metric 16,subnet 10.4.0.0, metric 16,A,C,B,得知网络拓扑结构发生改变,不等待发送周期 ,立刻通告更新后全部的路由表,2020/10/19,Hold-down倒记时,10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,X,hold-down倒记时以后更新路由表,A,B,C,等待网络中其它路由器收敛,在该时间内不学习任何与该网络相关的路由信息(RIP缺省180秒),在倒记时其间继续向其它路由器发送毒化信息,2020/10/19,RIP,讲解RIP时注意几个数字 520，RIP协议是应用层协议，基于UDP，端口520 15，RIP协议规定两点间最大跳数为15 16，当RIP产生路由信息metric为16时，表示该路由信息不可达 30，RIP协议每隔30秒发送一次更新报文 180，路由器如果180没有收到来自邻