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 6
2018/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
2018/4/6 RP2报文 RIP2报文 ·RP2报文由首部和路由部分组成。 ·一个RIP报文最多可包括25个路由，因而RIP ·RP2报文中的路由部分由若干个路由信息组成。每 报文的最大长度是4+20×25=504字节。如超 过，必须再用一个RIP报文来传送。 个路由信息需要用20个字节。地址族标识符（又称 为地址类别)字段用来标志所使用的地址协议。 ·RP2具有简单的鉴别功能。 ·路由标记填入自治系统的号码，这是考虑到RP有 ·若使用鉴别功能，则将原来写入第一个路由信息(20 个字节)的置用作竖别。 可能收到本自治系统以外的路由选择信息。 ·在鉴别数据之后才写入路由信息，但这时最多只能再 ·再后面指出某个网络地址、该网络的子网掩码、下 放入24个路由信息· 一跳路由器地址以及到此网络的距离。 11 11 11/ 好消息传播得快，坏消息传播得慢 正常情况 11m 12B 1 题2 周3 1表示“从本痛由调同1” 一表示“直淡交付 ·RP协议特点：好消息传播得快，坏消息传播得 “1豪示“柜离是1” 慢。 R说：“我到网1的距离是1，是直接交付。 ·RP存在的一个问题：当网络出现故障时，要经 过比较长的时间（例如数分钟）才能将此信息传 送到所有的路由器。 11 11 正 [11-→ 11-→ 12B 网1 23 周3 周2 周3 R 1泰示“从本瑞由●到筒1” R“表示怒过民 周2 两3 R> “2爽示“更南量2 同1出T故障 116-→ 12B☐ 凡说：“我到网1的更离是2，是经过R。” R,说，“要到同1的更离是16（表示无法到达）， 是直赖交付。” 但R在收到凡的更新报文之前，还发送原来的报文， 因为这时凡并不知道凡出了蚊得。 11 7
2018/4/6 7 RIP2 报文 • RIP2 报文由首部和路由部分组成。 • RIP2 报文中的路由部分由若干个路由信息组成。每 个路由信息需要用 20 个字节。地址族标识符（又称 为地址类别）字段用来标志所使用的地址协议。 • 路由标记填入自治系统的号码，这是考虑到 RIP 有 可能收到本自治系统以外的路由选择信息。 • 再后面指出某个网络地址、该网络的子网掩码、下 一跳路由器地址以及到此网络的距离。 RIP2 报文 • 一个 RIP 报文最多可包括 25 个路由，因而 RIP 报文的最大长度是 4 20 25 504 字节。如超 过，必须再用一个 RIP 报文来传送。 • RIP2 具有简单的鉴别功能。 • 若使用鉴别功能，则将原来写入第一个路由信息（20 个字节）的位置用作鉴别。 • 在鉴别数据之后才写入路由信息，但这时最多只能再 放入 24 个路由信息。 好消息传播得快，坏消息传播得慢 • RIP 协议特点：好消息传播得快，坏消息传播得 慢。 • RIP 存在的一个问题：当网络出现故障时，要经 过比较长的时间 (例如数分钟) 才能将此信息传 送到所有的路由器。 R1 R2 网 1 网 2 网 3 正 常 情 况 1 1 1 2 R1 R1 说：“我到网 1 的距离是 1，是直接交付。” “1”表示“从本路由器到网 1” “1”表示“距离是 1” “”表示“直接交付” R1 R2 网 1 网 2 网 3 正 常 情 况 1 1 1 2 R1 R2 说：“我到网 1 的距离是 2，是经过 R1。” “1”表示“从本路由器到网1” “2”表示“距离是 2” “R1 ”表示经过 R1 R1 R2 网 1 网 2 网 3 R1 R2 网 1 网 2 网 3 网1出了故障 正 常 情 况 1 1 1 16 1 2 R1 1 2 R1 R1 说：“我到网 1 的距离是 16 （表示无法到达）， 是直接交付。” 但 R2 在收到 R1 的更新报文之前，还发送原来的报文， 因为这时 R2 并不知道 R1 出了故障
2018/4/6 11-→ 12R 正常 11- 12B☐ ◆ 五 2 同3 2 2 周3 同2 3 两1出了敏神 116-→ 12B 同1出了故神 116-→ 12R 13R→ 13R→ 14 R收到R的更新报文后，误从为可径过R,到 达网1，子量新自己的略由表，说：“爱到 民以后又更新自己的略由表为1,4R”,表 用1的距离是3，下一最经过R”·然后将此更 “我到周1更离是4，下一碱经过R”。 新信惠发送给R2。 1 11, 11/ 这就是好消息传播得快，而坏消惠传滑得慢。网络出故障的 RP协议的优缺点 传播时间往往需要较长的时间（例如数分钟）。这是P的- 个主要缺点。 ·优点： ·实现简单，开销较小。 ·缺点： ·RIP限制了网路的规模，它能使用的最大距离为1S 同1出了故博 116-→ ←12A☐ (16表示不可达)。 13☐→ ←14B,☐ ·资騁器阀務赖般璃騁突是异務电爱韩的定整路由表· 15R■→ ·“坏消息传播得慢”，使更新过程的收敛时间过长。 116R2→ 116B:☐ 这样不膏更新下去，直到R1和R2到网1的距商都增大到16 时，R1和R2才知道网1是不可达的。 11 1/ 4.5.3内部网关协议OSP℉ 1.OSPF协议的基本特点 ·开放最短路径优先OSPF(Open Shortest Path ·“开放”表明OSPF协议不是受某一家厂商控制， Fist)是为克服RIP的缺点在1989年开发出来的。 而是公开发表的。 ·OSPF的原理很简单，但实现起来却较复杂。 “最短路径优先”是因为使用了Dijkstra提出的 最短路径算法SPF ·采用分布式的链路状态协议(link state protocol). ·注意：OSPF只是一个协议的名字，它并不表示 其他的路由选择协议不是“最短路径优先”。 11 8
2018/4/6 8 R1 R2 网 1 网 2 网 3 R1 R2 网 1 网 2 网 3 网1出了故障 正 常 情 况 1 1 1 16 1 2 R1 1 2 R1 R1 收到 R2 的更新报文后，误认为可经过 R2 到 达网 1，于是更新自己的路由表，说：“我到 网 1 的距离是 3，下一跳经过 R2 ”。然后将此更 新信息发送给 R2。 1 3 R2 R1 R2 网 1 网 2 网 3 R1 R2 网 1 网 2 网 3 网1出了故障 正 常 情 况 1 1 1 16 1 2 R1 1 2 R1 R2 以后又更新自己的路由表为“1, 4, R1 ”，表 明 “我到网 1 距离是 4，下一跳经过 R1 ”。 1 3 R2 1 4 R1 R1 R2 网 1 网 2 网 3 R1 R2 网 1 网 2 网 3 网1出了故障 正 常 情 况 1 1 … 1 16 1 3 R2 1 5 R2 1 16 R2 1 2 R1 1 2 R1 1 4 R1 1 16 R1 … 这样不断更新下去，直到 R1和 R2到网 1 的距离都增大到 16 时，R1和 R2 才知道网 1 是不可达的。 这就是好消息传播得快，而坏消息传播得慢。网络出故障的 传播时间往往需要较长的时间(例如数分钟)。这是 RIP 的一 个主要缺点。 RIP 协议的优缺点 • 优点： • 实现简单，开销较小。 • 缺点： • RIP 限制了网络的规模，它能使用的最大距离为 15 （16 表示不可达）。 • 路由器之间交换的路由信息是路由器中的完整路由表， 因而随着网络规模的扩大，开销也就增加。 • “坏消息传播得慢”，使更新过程的收敛时间过长。 4.5.3 内部网关协议 OSPF • 开放最短路径优先 OSPF (Open Shortest Path First)是为克服 RIP 的缺点在 1989 年开发出来的。 • OSPF 的原理很简单，但实现起来却较复杂。 1. OSPF 协议的基本特点 • “开放”表明 OSPF 协议不是受某一家厂商控制， 而是公开发表的。 • “最短路径优先”是因为使用了 Dijkstra 提出的 最短路径算法 SPF • 采用分布式的链路状态协议 (link state protocol)。 • 注意：OSPF 只是一个协议的名字，它并不表示 其他的路由选择协议不是“最短路径优先