2018/4/6 2.距离向量算法 2.距离向量算法 略由收到帽邮略由最（其地址为x)的一个RP报文： ·距离向量算法的基础就是Bellman-Ford算法 山先德改此RP报文中的所南项目：把“下一飘”字股中的地址都成 (或Ford-Fulkerson算法)。 为X,并把所有的“巨言”李最的值加1。 )对棒故后的RP报文中的海一个项目。量复以下步情： ·这种算法的要点是这样的： 若项目中的目的网蜂不在磨由表中，则把该项目加到磨由表中。 设X是结点A到B的最短路径上的一个结点。 若下一藤字段峰出的略由■地址是同样的，则把收到的项目管物 若把路径A→B拆成两段路径A→X和X→B, 原略由囊中的项目。 则每一段路径A+X和X→B也都分别是结点A 否则 到X和结点X到B的最短路径。 若收到项目中的更离小于略由表中的更真，则进行更新， 否则，什么也不输. 3)若3分钟还没有收到相邻路由■的更斯略由表，则把此相郁路由通 记为不可达磨由●，即将距真量为16（表示不可达）。 (4远回。 1 111 路由器之间交换信息与路由表更新 【例4-5】已知路由器R6有表49a)所示的路由表。 现在收到相邻路由器R,发来的路由更新信息，如表 ·RIP协议让互联网中的所有路由器都和自己的相 4-9b)所示。试更新路由器R的路由表。 邻路由器不断交换路由信息，并不断更新其路由 表，使得从每一个路由器到每一个目的网络的路 表4：)】略由疆凡：的略由表 49凡，发来的由更新息 目的网临距离 下一膜燕由香 目的同离 下一院略由■ 由都是最短的（即跳数最少）。 Net? 3 R。 Net1 3 R ·虽然所有的路由器最终都拥有了整个自治系统的 Net3 4 Net? 直技攻付■ 全局路由信总，但由于每一个路由器的位置不同， 它们的路由表当然也应当是不同的。 计德 电高加1 表49)略由顺R:更斯后的略由表 4-9修改看的表4-9b1 目的同墙距高下一酬墙由最 目的同峰更离下一就路由■ Net1 Net1 4 R Net? Net3 Net3 【例】路由表更新 3.RIP2协议的报文格式 4节 从C泰的IF报文 增加麻徽以后 Net1:没有新慎惠，不变 收标识蒋酒 Net2 从C来的P报文 Net2:相同的下一篇，雪执 4字节 阿第地址 t Net2 5 Net3: 于同掩得 Nct6 4 Net3 9 Mt5:不同的下一第，解填骤小，管换 布◆体 的为0 Ncty 3 Net6 5 Net8:不同的下一， 相同，不支 下一由地址 Net9 5 Net8 Net9:不同的下一鹏，新意大，不夜 题真116 6 新嚥由表 Net1 7 略由都分 Net1 7 A Net2 略由黄惠 Net2 2 更斯算法 Net3 R阳P根文 Net6 Net8 录多25个 Net9 UDP用户数量报 P数辑规 41 1 62018/4/6 6 2. 距离向量算法 路由器收到相邻路由器（其地址为X）的一个RIP 报文： (1) 先修改此RIP 报文中的所有项目：把“下一跳”字段中的地址都改 为 X，并把所有的“距离”字段的值加 1。 (2) 对修改后的RIP 报文中的每一个项目，重复以下步骤： 若项目中的目的网络不在路由表中，则把该项目加到路由表中。 否则 若下一跳字段给出的路由器地址是同样的，则把收到的项目替换 原路由表中的项目。 否则 若收到项目中的距离小于路由表中的距离，则进行更新， 否则，什么也不做。 (3) 若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器 记为不可达路由器，即将距离置为16（表示不可达）。 (4) 返回。 2. 距离向量算法 • 距离向量算法的基础就是 Bellman-Ford 算法 （或 Ford-Fulkerson 算法）。 • 这种算法的要点是这样的： 设X是结点 A 到 B 的最短路径上的一个结点。 若把路径 A→B 拆成两段路径 A→X 和 X→B， 则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。 路由器之间交换信息与路由表更新 • RIP 协议让互联网中的所有路由器都和自己的相 邻路由器不断交换路由信息，并不断更新其路由 表，使得从每一个路由器到每一个目的网络的路 由都是最短的（即跳数最少）。 • 虽然所有的路由器最终都拥有了整个自治系统的 全局路由信息，但由于每一个路由器的位置不同， 它们的路由表当然也应当是不同的。 【例4-5】已知路由器 R6 有表 4-9(a) 所示的路由表。 现在收到相邻路由器 R4 发来的路由更新信息，如表 4-9(b) 所示。试更新路由器 R6 的路由表。 目的网络 距离 下一跳路由器 Net2 3 R4 Net3 4 R5 … … … 目的网络 距离 下一跳路由器 Net1 3 R1 Net2 4 R2 Net3 1 直接交付 目的网络 距离 下一跳路由器 Net1 4 R4 Net2 5 R4 Net3 2 R4 目的网络 距离 下一跳路由器 Net1 4 R4 Net2 5 R4 Net3 2 R4 … … … 表 4-9(a) 路由器 R6 的路由表 表 4-9(b) R4 发来的路由更新信息 表 4-9(d) 路由器 R6 更新后的路由表 表 4-9(c) 修改后的表 4-9(b) 计算 距离加 1 更新 【例】路由表更新 Net2 4 Net3 8 Net6 4 Net8 3 Net9 5 Net2 5 Net3 9 Net6 5 Net8 4 Net9 6 Net1 7 A Net2 2 C Net6 8 F Net8 4 E Net9 4 F 从C来的RIP报文 增加跳数以后 从C来的RIP报文 旧路由表 更新算法 Net1 7 A Net2 5 C Net3 9 C Net6 5 C Net8 4 E Net9 4 F 新路由表 Net1: 没有新信息，不变 Net2: 相同的下一跳，替换 Net3: 一条新路由，增加 Net6: 不同的下一跳，新跳数小，替换 Net8: 不同的下一跳，跳数相同，不变 Net9: 不同的下一跳，新跳数大，不变 4 字节 RIP 报文 3. RIP2 协议的报文格式 路由信息 （20 字节/路由） 可重复出现 最多 25 个 IP 数据报 路由标记 网络地址 地址族标识符 距离 (1-16) IP 首部 UDP 首部 路由部分 4 字节 子网掩码 下一跳路由器地址 UDP 用户数据报 首部 命令 版本 必为 0