距离矢量算法解析[竹菊书苑]

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

2、 我通过R2可以到达路由 器R，R2到R之间的具 体细节我不清楚 向上教学 距离矢量详解 R1R2 距离矢量算法思想： 矢量距离算法（简称VD算法）的思想是：网关周期性地 向外广播路径刷新报文，主要内容是由若干（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)

3、 k为所有与i相邻的路由器 图示距离矢量算法 d(i,k)D(k,j) j d(i, k)+ D(k, j) =i k1 k2 距离矢量详解 A B C FG D E 1、对距离向量路由所做的初始假设是每个结点都知道其邻接点得链路开 销。 到不相邻结点的链路开销被指定为无穷大； 2、每条路径的开销为1，所以开销最小的路径就是包含跳数最少的路径。 距离矢量详解包含到其他所有结点开销 存 储 在 结 点存 储 在 结 点 的信息的信息 到每个结点的距离到每个结点的距离 ABCDEFG A01111 B101 C1101 D101 E10 F101 G110 存储在每个结点中的初始距离 距离矢量详解

4、发送包含自己距离表的消息给其他邻接点 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大，因此新的信息 被忽略。 向上教学 距离矢量详解发送包含自己距离表的消息给其他邻接点 目标目标开销开销下一跳下一跳 B1B C1C D E1E F1F

5、G 目标目标开销开销下一跳下一跳 B1B C1C D2C E1E F1F G2C 结点A的初始路由表结点A的最终路由表 距离矢量详解 存 储 在 结 点存 储 在 结 点 的信息的信息 到每个结点的距离到每个结点的距离 ABCDEFG A0112112 B1012223 C1101222 D2210321 E1223023 F1222201 G2321310 存储在每个结点的最终距离 向上教学 路由环路1 Routing Table NetHopNext Hop 10.0.0.0120.0.0.1 20.0.0.00 30.0.0.00 40.0.0.0130.0.0.2 Routing Ta

6、ble NetHopNext Hop 10.0.0.0230.0.0.1 20.0.0.0130.0.0.1 30.0.0.00 40.0.0.00 Routing Table NetHopNext Hop 10.0.0.00 20.0.0.00 30.0.0.0120.0.0.2 40.0.0.0220.0.0.2 R1 R2R3 10.0.0.020.0.0.030.0.0.040.0.0.0 .1.1.2.2 向上教学 路由环路2 R1 R2R3 10.0.0.020.0.0.030.0.0.040.0.0.0 .1.1.2.2 发送40.0.0.0的跳数 为1的更新信息 Routing

7、 Table NetHopNext Hop 10.0.0.0120.0.0.1 20.0.0.00 30.0.0.00 40.0.0.0130.0.0.2 Routing Table NetHopNext Hop 10.0.0.0230.0.0.1 20.0.0.0130.0.0.1 30.0.0.00 40.0.0.016 Routing Table NetHopNext Hop 10.0.0.00 20.0.0.00 30.0.0.0120.0.0.2 40.0.0.0220.0.0.2 被标记为无 效 向上教学 路由环路3 R1 R2R3 10.0.0.020.0.0.030.0.0.0

8、40.0.0.0 .1.1.2.2 Routing Table NetHopNext Hop 10.0.0.0120.0.0.1 20.0.0.00 30.0.0.00 40.0.0.0130.0.0.2 Routing Table NetHopNext Hop 10.0.0.0230.0.0.1 20.0.0.0130.0.0.1 30.0.0.00 40.0.0.0230.0.0.1 Routing Table NetHopNext Hop 10.0.0.00 20.0.0.00 30.0.0.0120.0.0.2 40.0.0.0220.0.0.2 发送40.0.0.0的路 由更新，跳数

9、为2 将跳数改变为2跳， 下一条地址为 30.0.0.1 向上教学 路由环路4 R1 R2R3 10.0.0.020.0.0.030.0.0.040.0.0.0 .1.1.2.2 产生路由环路，直 到跳数增加到16为 止 Routing Table NetHopNext Hop 10.0.0.0120.0.0.1 20.0.0.00 30.0.0.00 40.0.0.0330.0.0.2 Routing Table NetHopNext Hop 10.0.0.0230.0.0.1 20.0.0.0130.0.0.1 30.0.0.00 40.0.0.0230.0.0.2 Routing Tab

10、le NetHopNext Hop 10.0.0.00 20.0.0.00 30.0.0.0120.0.0.2 40.0.0.0220.0.0.2 将跳数改变为3跳 向上教学 解决路由环路的方法 水平分割 毒性反转 触发更新 Hold-down倒计时 向上教学 10.1.0.010.2.0.010.3.0.010.4.0.0 E0S0 S0S1S0E0 10.3.0.0S0 S0 S0 S0 1 210.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

11、1 2 10.2.0.0 10.1.0.0 10.4.0.0 10.3.0.0 0 0 水平分割 RIP从某个接口学到的路由不再从该接口发布给其他路由器 向上教学 毒性反转 10.1.0.010.2.0.010.3.0.0 E0S0 S0S1S0E0 10.3.0.0 S0 S0 S0 S0 1 210.1.0.0 10.2.0.0 10.4.0.0 0 16 10.1.0.0E0 S0 S0 S0210.4.0.0 10.3.0.0 10.2.0.0 0 0 10.2.0.0S0 S1 S1 E1 Possibly Down 210.1.0.0 10.4.0.0 10.3.0.0 0 0 S

12、ubnet 10.4.0.0 metric 16 向上教学 触发更新 10.2.0.010.3.0.010.4.0.0 E0S0 S0S1S0E0 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 得知网络拓扑结构发生改变,不等待发送周 期 ,立刻通告更新后全部的路由表 向上教学 Hold-down倒记时 10.1.0.010.2.0.010.3.0.010.4.0.0 E0S0 S0S1S0E0 等待网络中其它路由器收敛,在该时间内不学 习任何与该网络相关的路由信息(RIP缺省180 秒),在倒记时其间继续向其它路由器发送毒 化信息 向上教学 RIP 讲解RIP时注意几个数字 520，RIP协议是应用层协议，基于UDP，端口520 15，RIP协议规定两点间最大跳数为15 1