距离矢量算法解析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,英文目录标题,:33-42pt,颜色,:R204 G51 B0,字体,:Arial,英文目录副标题,:25-32pt,颜色,:R204 G51 B0,字体,:Arial,中文目录标题,:33-42pt,颜色,:R204 G51 B0,字体,:,黑体,中文目录副标题,:33-40pt,颜色,:R204 G51 B0,字体,:,黑体,英文目录正文,:20-30pt,子目录,(2-5,级,):18pt,颜色,:,黑色,字体,:Times NEW Roman,中文目录正文,:20-30pt,子目录,(2-5,级,):18pt,颜色,:,黑色,字体,:,宋体,配色参考方案：,建议同一页面内不超过四种颜色，以下是,6,组配色方案，同一页面内只选择一组使用。,（仅供参考）,距离矢量算法解析,主要内容,1、什么是动态路由,2、动态路由根据算法的分类,3、距离矢量算法详解,4、路由环路,5、水平分割,动态路由协议,动态路由协议特点,向其他路由器传递路由信息,接收其他路由器的路由信息,根据收到的路由信息计算出到每个目的网络的最优路径，并由此生成路由表,根据网络拓朴变化及时调整路由表，同时向其他路由器宣告拓朴改变的信息,动态路由协议,根据路由所执行的算法分类,距离矢量路由协议,链路状态路由协议,距离矢量路由协议,路由器每经过特定时间周期向邻居发送自己的路由表,距离：有多远,矢量：从哪个方向,R1,R2,R,我能够到达路由器R，距离是5,我通过R2可以到达路由器R，R2到R之间的具体细节我不清楚,距离矢量详解,R1,R2,距离矢量算法思想：,矢量距离算法（简称,V,D,算法）的思想是：网关周期性地向外广播路径刷新报文，主要内容是由若干（,V,，,D,）序偶组成的序偶表；（,V,，,D,）序偶中的,V,代表“向量”，标识网关可到达的信宿（网关或主机），,D,代表距离，指出该网关去往信宿,V,的距离；距离,D,按驿站的个数计。其他网关收到某网关的（,V,，,D,）报文后，据此按照最短路径原则对各自的路由表进行刷新,RIP工作原理-距离矢量算法,路由算法,D(i,j)=0,D(i,j)=MIN d(i,k)+D(k,j)k,为所有与,i,相邻的路由器,图示距离矢量算法,d(i,k),D(k,j),j,d(i,k)+D(k,j)=,i,k1,k2,距离矢量详解,A,B,C,F,G,D,E,1,、对距离向量路由所做的初始假设是每个结点都知道其邻接点得链路开 销。到不相邻结点的链路开销被指定为无穷大；,2,、每条路径的开销为,1,，所以开销最小的路径就是包含跳数最少的路径。,距离矢量详解,包含到其他所有结点开销,存储在结点的信息,到每个结点的距离,A,B,C,D,E,F,G,A,0,1,1,1,1,B,1,0,1,C,1,1,0,1,D,1,0,1,E,1,0,F,1,0,1,G,1,1,0,存储在每个结点中的初始距离,距离矢量详解,发送包含自己距离表的消息给其他邻接点,1,、结点,F,告诉,A,它可以到结点,G,，开销为,1,，,A,也知道它能以开销,1,到达,F,，因此二者相加就可以知道经,F,到,G,的开销；,A,到,G,的总开销,2,小于当前的开销无穷大，因此,A,记录它可经,F,到达,G,，开销为,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,大，因此新的信息被忽略。,距离矢量详解,发送包含自己距离表的消息给其他邻接点,目标,开销,下一跳,B,1,B,C,1,C,D,E,1,E,F,1,F,G,目标,开销,下一跳,B,1,B,C,1,C,D,2,C,E,1,E,F,1,F,G,2,C,结点,A,的初始路由表,结点,A,的最终路由表,距离矢量详解,存储在结点的信息,到每个结点的距离,A,B,C,D,E,F,G,A,0,1,1,2,1,1,2,B,1,0,1,2,2,2,3,C,1,1,0,1,2,2,2,D,2,2,1,0,3,2,1,E,1,2,2,3,0,2,3,F,1,2,2,2,2,0,1,G,2,3,2,1,3,1,0,存储在每个结点的最终距离,路由环路,1,Routing Table,Net,Hop,Next Hop,10.0.0.0,1,20.0.0.1,20.0.0.0,0,30.0.0.0,0,40.0.0.0,1,30.0.0.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,2,30.0.0.1,20.0.0.0,1,30.0.0.1,30.0.0.0,0,40.0.0.0,0,Routing Table,Net,Hop,Next Hop,10.0.0.0,0,20.0.0.0,0,30.0.0.0,1,20.0.0.2,40.0.0.0,2,20.0.0.2,R1,R2,R3,.1,.1,.2,.2,路由环路,2,R1,R2,R3,.1,.1,.2,.2,发送的跳数为1的更新信息,Routing Table,Net,Hop,Next Hop,10.0.0.0,1,20.0.0.1,20.0.0.0,0,30.0.0.0,0,40.0.0.0,1,30.0.0.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,2,30.0.0.1,20.0.0.0,1,30.0.0.1,30.0.0.0,0,40.0.0.0,16,Routing Table,Net,Hop,Next Hop,10.0.0.0,0,20.0.0.0,0,30.0.0.0,1,20.0.0.2,40.0.0.0,2,20.0.0.2,被标记为无效,路由环路,3,R1,R2,R3,.1,.1,.2,.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,1,20.0.0.1,20.0.0.0,0,30.0.0.0,0,40.0.0.0,1,30.0.0.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,2,30.0.0.1,20.0.0.0,1,30.0.0.1,30.0.0.0,0,40.0.0.0,2,30.0.0.1,Routing Table,Net,Hop,Next Hop,10.0.0.0,0,20.0.0.0,0,30.0.0.0,1,20.0.0.2,40.0.0.0,2,20.0.0.2,发送的路由更新，跳数为2,将跳数改变为2跳，下一条地址为,路由环路,4,R1,R2,R3,.1,.1,.2,.2,产生路由环路，直到跳数增加到16为止,Routing Table,Net,Hop,Next Hop,10.0.0.0,1,20.0.0.1,20.0.0.0,0,30.0.0.0,0,40.0.0.0,3,30.0.0.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,2,30.0.0.1,20.0.0.0,1,30.0.0.1,30.0.0.0,0,40.0.0.0,2,30.0.0.2,Routing Table,Net,Hop,Next Hop,10.0.0.0,0,20.0.0.0,0,30.0.0.0,1,20.0.0.2,40.0.0.0,2,20.0.0.2,将跳数改变为3跳,解决路由环路的方法,水平分割,毒性反转,触发更新,Hold-down,倒计时,E0,S0,S0,S1,S0,E0,X,X,X,10.3.0.0,S0,S0,S0,S0,1,2,10.1.0.0,10.2.0.0,10.4.0.0,0,0,E0,S0,S0,S0,1,2,10.1.0.0,10.4.0.0,10.3.0.0,10.2.0.0,0,0,S0,S1,S1,E1,1,2,10.2.0.0,10.1.0.0,10.4.0.0,10.3.0.0,0,0,C,B,A,水平分割,RIP从某个接口学到的路由不再从该接口发布给其他路由器,当一条路径信息变为无效之后，路由器并不立即将它从路由表中删除，而是用,16,，即不可达的度量值将它广播出去。缺点增加了路由表的大小。,毒性反转,E0,S0,S0,S1,S0,E0,X,10.3.0.0,S0,S0,S0,S0,1,2,10.1.0.0,10.2.0.0,10.4.0.0,0,16,10.1.0.0,E0,S0,S0,S0,1,2,10.4.0.0,10.3.0.0,10.2.0.0,0,0,10.2.0.0,S0,S1,S1,E1,PossiblyDown,2,10.1.0.0,10.4.0.0,10.3.0.0,0,0,Subnet 10.4.0.0 metric 16,A,B,C,触发更新,E0,S0,S0,S1,S0,E0,X,subnet 10.4.0.0,metric 16,subnet 10.4.0.0,metric 16,subnet 10.4.0.0,metric 16,A,C,B,得知网络拓扑结构发生改变,不等待发送周期,立刻通告更新后全部的路由表,Hold-down,倒记时,E0,S0,S0,S1,S0,E0,X,hold-down,倒记时以后更新路由表,A,B,C,等待网络中其它路由器收敛,在该时间内不学习任何与该网络相关的路由信息(RIP缺省180秒),在倒记时其间继续向其它路由器发送毒化信息,RIP,讲解,RIP,时注意几个数字,520,，,RIP,协议是应用层协议，基于,UDP,，端口,520,15,，,RIP,协议规定两点间最大跳数为,15,16,，当,RIP,产生路由信息,metric,为,16,时，表示该路由信息不可达,30,，,RIP,协议每隔,30,秒发送一次更新报文,180,，路由器如果,180,没有收到来自邻居的更新报文，则将对方标识为不可达,240,，路由器如果,240,没有收到来自邻居的更新报文，将该路由器相关的路由信息删除,，,RIPv2,采用组播的方式发送协议报文，该地址代表所有运行了,RIPv2,协议的路由器。,