距离矢量算法解析.ppt

距离矢量算法解析 主要内容 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 0D i j 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 开销为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大 因此新的信息被忽略 距离矢量详解 发送包含自己距离表的消息给其他邻接点 结点A的初始路由表 结点A的最终路由表 距离矢量详解 存储在每个结点的最终距离 路由环路 1 R1 R2 R3 10 0 0 0 20 0 0 0 30 0 0 0 40 0 0 0 1 1 2 2 路由环路 2 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的跳数为1的更新信息 被标记为无效 路由环路 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 路由环路 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跳 解决路由环路的方法 水平分割毒性反转触发更新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 X X C B A 水平分割 RIP从某个接口学到的路由不再从该接口发布给其他路由器 当一条路径信息变为无效之后 路由器并不立即将它从路由表中删除 而是用16 即不可达的度量值将它广播出去 缺点增加了路由表的大小 毒性反转 10 1 0 0 10 2 0 0 10 3 0 0 E0 S0 S0 S1 S0 E0 X Subnet10 4 0 0metric16 A B C 触发更新 10 2 0 0 10 3 0 0 10 4 0 0 E0 S0 S0 S1 S0 E0 X subnet10 4 0 0 metric16 10 1 0 0 subnet10 4 0 0 metric16 subnet10 4 0 0 metric16 A C B 得知网络拓扑结构发生改变 不等待发送周期 立刻通告更新后全部的路由表 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秒 在倒记时其间继续向其它路由器发送毒化信息 RIP 讲解RIP时注意几个数字520 RIP协议是应用层协议 基于UDP 端口52015 RIP协议规定两点间最大跳数为1516 当RIP产生路由信息metric为16时 表示该路由信息不可达30 RIP协议每隔30秒发送一次更新报文180 路由器如果180没有收到来