七、路由选择协议 ★
路由选择协议分类 :
① 内部网管协议 IGP : 在 自治系统 ( Autonomous System ) 内部 使用的协议 ;
RIP 协议 : 使用 距离向量 算法 ; 用于 小型网络 ;
OSPF 协议 : 使用 链路状态 算法 ; 用于 大型网络 ;
② 外部网关协议 EGP : 在 自治系统 ( Autonomous System ) 之间 使用的协议 ;
下图中 自治系统 A AA 内部使用 RIP 协议 , 自治系统 B BB 内部使用 OSPF 协议 , 两个自治系统 A , B A,BA,B 之间使用 BGP 协议 ;
RIP 协议
RIP 协议 :
① 概念 : RIP 协议 是 分布式的 , 基于 距离向量 的 , 路由选择协议 ; 该协议是因特网协议标准 ;
② 特点 : 简单 ;
③ RIP 协议内容 : 要求网络中 , 每个路由器 都维护一个路由表 , 路由表内容是 从 路由器本身 到 目的网络 的 唯一最佳距离记录 ;
④ 距离 : 路由器 跳数 , 每经过一个路由器 , 跳数加一 ;
⑤ 直接连接距离 : 路由器 到 直接连接的网络 , 距离是 1 11 ;
⑥ 最大距离 : RIP 协议中要求 , 一条路由只能包含 15 1515 个路由器 ( 包含其本身 ) , 距离 最大是 15 1515 , 如果距离为 16 1616 , 该目标主机就会被判定为 网络不可达 ;
路由表 形成 需要进行信息 交换 , 需要与 指定的路由器 , 在指定的时机 , 交换指定信息 ;
RIP 协议 信息交换
RIP 协议 信息交换 :
① 交换对象 : 本路由器 只 与 相邻路由器 进行信息交换 ;
② 交换信息 : 交换的信息是路由器的 本身的路由表 ; 将本路由器的路由表所有信息, 封装在 RIP 报文中 , 发送给相邻路由器 ;
③ 交换周期 : 每隔 30 3030 秒 , 交换一次路由信息 , 根据新的信息更新路由表 , 如果超过 180 180180 秒没有收到 邻居路由器的 交换信息 , 则判定旁边的 邻居路由器没了 , 更新自身的路由表 ;
交换过程 : 刚开始时 , 每个路由器 只知道 直连的网络的距离 1 11 , 之后每个路由器想换交换信息 , 并更新路由信息 , 若干次交换后 , 所有的路由器都知道 本 自治系统 ( Autonomous System ) 中从任何路由器 到达 任何网络的最短距离 , 和 下一跳路由地址 ;
路由表内容 : 网络地址 , 跳数 , 下一跳地址 ;
RIP 协议是 应用层协议 , 使用 UDP 协议传输数据 ;
单个 RIP 报文中 , 最多存储 25 2525 个路由信息 , 如果路由表很大 , 那么发送多个 RIP 报文 ;
RIP 协议特点 : 好消息更新快 , 坏消息更新慢 ; 网络出现故障后 , 要经过几分钟 , 才能将该信息送达所有的路由 , 收敛慢 ;
OSPF 协议
OSPF 协议 简介 :
① 全称 : 开放最短路径优先协议 ;
“开放” 说明该协议是公开发表的
“最短路径优先” 指的是使用了 最短路径算法 ;
② 主要特征 : 使用 分布式 链路状态协议 ;
OSPF 协议 信息交换
OSPF 协议 信息交换 细节 :
① 交换对象 : OSPF 中使用 洪泛法 向 自治系统 ( Autonomous System ) 内部 所有路由器 发送消息 ; 本路由器 向 相邻路由器 发送消息 , 相邻路由器 再向 其相邻路由器 发送消息 , 直到所有的路由器收到消息为止 , 相当于广播 ;
② 交换信息 : OSPF 中发送消息内容是 , 本路由器 与 所有 相邻路由器 的链路状态 , 包括 有哪些相邻路由器 , 链路状态 如 距离 , 时延 , 带宽 等指标 ;
③ 交换时机 : 只有当 链路状态发生变化 时 , 路由器才使用 洪范法 向 AS 内所有路由器 广播 本身与所有相邻的路由器的链路状态 ;
最终目的 : 所有的路由器 都有一个 链路状态数据库 ( 全网拓扑图 ) ;
八、路由算法 ★
距离向量算法
距离向量算法 :
① 修改 RIP 报文 : 修改 相邻 路由器 发送的 RIP 报文 中的 所有表项 ;
相邻路由器 地址为 X XX , 发送来 RIP 报文 , ① 将 下一跳 地址改为 X XX 相邻路由器地址 , ② 将距离 加一 ;
② 更新 本路由器 路由表 :
路由表内容 : 网络地址 , 跳数 , 下一跳地址 ;
针对修改后的 RIP 报文 , 执行下面的操作 :
没有的表项 : 没有报文中路由表表项的 网络地址 , 直接插入即可 ;
已有的表项 : 存在报文中路由表表项的 网络地址 , 查看下一跳路由器地址 ,
下一跳就是 X XX 相邻路由器 : 使用该新的路由表项替换原来的路由表项 ; 这种情况下 , 不管距离变大还是变小 , 只要下一跳路由器一样 , 就更新 , 这说明了网络拓扑发生了改变 ; 始终以新的数据为标准 ;
下一跳不是 X XX 相邻路由器 : 比较距离 , 如果 本次的距离 比 原来的距离 近 , 就更新路由表项 , 如果远 , 不做处理 ; ( 更新原则是 , 同一个目的地址 , 始终保持跳数较少的路由路径 )
③ 删除路由 : 如果 180 180180 秒 , 还没有收到相邻路由器 X XX 的 RIP 报文数据 , 那么将 路由器 X XX 记为不可达路由器 , 将距离设置为 16 1616 ;
④ 返回 ;
距离向量算法示例 1
距离向量算法 计算示例 :
R 6 R6R6 本身路由表 :
表项 1 11 : 目的网络 Net 2 22 , 距离 3 33 , 下一跳路由 R 4 R4R4 ;
表项 2 22 : 目的网络 Net 3 33 , 距离 4 44 , 下一跳路由 R 5 R5R5 ;
收到 R 4 R4R4 发来的 RIP 报文 ( 路由更新信息 ) :
表项 1 11 : 目的网络 Net 1 11 , 距离 3 33 , 下一跳路由 R 1 R1R1 ;
表项 2 22 : 目的网络 Net 2 22 , 距离 4 44 , 下一跳路由 R 2 R2R2 ;
表项 3 33 : 目的网络 Net 3 33 , 距离 1 11 , 下一跳路由 直接交付 ;
计算更新后的 R 6 R6R6 路由器路由表 ?
计算过程 :
① 修改 RIP 报文 :
① 将 下一跳 地址改为 X XX 相邻路由器地址
② 将距离 加一 ;
按照上述 两个步骤 修改 收到 R 4 R4R4 发来的 RIP 报文 ( 路由更新信息 ) :
表项 1 11 : 目的网络 Net 1 11 , 距离 4 44 , 下一跳路由 R 4 R4R4 ;
表项 2 22 : 目的网络 Net 2 22 , 距离 5 55 , 下一跳路由 R 4 R4R4 ;
表项 3 33 : 目的网络 Net 3 33 , 距离 2 22 , 下一跳路由 R 4 R4R4 ;
② 更新 路由表 :
针对 "表项 1 11 : 目的网络 Net 1 11 , 距离 4 44 , 下一跳路由 R 4 R4R4 " , 原来 R 6 R6R6 路由表中没有 目的网络 Net 1 11 , 直接将该路由表表项插入到 R 6 R6R6 路由表zh9ong ;
针对 "表项 2 22 : 目的网络 Net 2 22 , 距离 5 55 , 下一跳路由 R 4 R4R4" , 原来 R 6 R6R6 路由表中 有 目的网络 Net 2 22 , 对比下一跳地址 , 原来的路由表项中下一跳地址是 R 4 R4R4 , 不管距离是否远近 , 这说明网络的拓扑结构发生变化 , 直接使用新的路由表项 , 替换原来的 ;
( 本步骤与距离远近无关 , 是网络拓扑发生的变化 )
针对 "表项 3 33 : 目的网络 Net 3 33 , 距离 2 22 , 下一跳路由 R 4 R4R4" , 原来 R 6 R6R6 路由表中 有 目的网络 Net 3 33 , 对比下一跳地址 , 下一跳地址不同 , 那么开始对比距离远近 , 原来的距离是 4 44 , 新的距离是 2 22 , 这里选择距离较近的 , 即将 RIP 报文中的路由表表项更新到 R 6 R6R6 路由器中 ;
更新后的 R 6 R6R6 路由器表项 : ( 全都更改了一遍 )
表项 1 11 : 目的网络 Net 1 11 , 距离 4 44 , 下一跳路由 R 4 R4R4 ;
表项 2 22 : 目的网络 Net 2 22 , 距离 5 55 , 下一跳路由 R 4 R4R4 ;
表项 3 33 : 目的网络 Net 3 33 , 距离 2 22 , 下一跳路由 R 4 R4R4 ;
距离向量算法示例 2
某子网 有 A , B , C , D , E , F A, B, C,D,E,FA,B,C,D,E,F 六个路由器 , 使用 距离-向量 算法 , 下面的向量 , 达到路由器 C CC :
来自 B BB 的向量为 ( 5 , 0 , 8 , 12 , 6 , 2 ) ( 5, 0, 8 , 12 , 6, 2 )(5,0,8,12,6,2)
来自 D DD 的向量为 ( 16 , 12 , 6 , 0 , 9 , 10 ) ( 16, 12, 6 , 0 , 9, 10 )(16,12,6,0,9,10)
来自 E EE 的向量为 ( 7 , 6 , 3 , 9 , 0 , 4 ) ( 7, 6, 3 , 9 , 0 , 4 )(7,6,3,9,0,4)
C CC 到 B , D , E B, D, EB,D,E 的延迟分别是 6 , 3 , 5 6,3,56,3,5 , 求 C CC 到达所有节点的最短路径 ;
计算过程 :
B BB 的向量为 ( 5 , 0 , 8 , 12 , 6 , 2 ) ( 5, 0, 8 , 12 , 6, 2 )(5,0,8,12,6,2) , 即 B BB 到 A , B , C , D , E , F A, B, C,D,E,FA,B,C,D,E,F 六个路由器的跳数 ;
D DD 的向量为 ( 16 , 12 , 6 , 0 , 9 , 10 ) ( 16, 12, 6 , 0 , 9, 10 )(16,12,6,0,9,10) , 即 D DD 到 A , B , C , D , E , F A, B, C,D,E,FA,B,C,D,E,F 六个路由器的跳数 ;
E EE 的向量为 ( 7 , 6 , 3 , 9 , 0 , 4 ) ( 7, 6, 3 , 9 , 0 , 4 )(7,6,3,9,0,4) , 即 E EE 到 A , B , C , D , E , F A, B, C,D,E,FA,B,C,D,E,F 六个路由器的跳数 ;
C CC 到 B BB 再到 其它路由器跳数为 ( 11 , 6 , 14 , 18 , 12 , 8 ) ( 11, 6, 14 , 18 , 12, 8 )(11,6,14,18,12,8)
C CC 到 D DD 再到 其它路由器跳数为 ( 19 , 15 , 9 , 3 , 12 , 13 ) ( 19, 15, 9 , 3 , 12, 13 )(19,15,9,3,12,13)
C CC 到 E EE 再到 其它路由器跳数为 ( 12 , 11 , 8 , 14 , 5 , 9 ) ( 12, 11, 8 , 14 , 5, 9 )(12,11,8,14,5,9)
C CC 到 A AA 最短 跳数 是 11 , 19 , 12 11 , 19, 1211,19,12 中最小值 11 1111 ;
C CC 到 B BB 最短 跳数 是 6 , 15 , 11 6 , 15, 116,15,11 中最小值 6 66 ;
C CC 到 C CC 最短 跳数 是 0 00 ;
C CC 到 D DD 最短 跳数 是 8 , 3 , 14 8 , 3, 148,3,14 中最小值 3 33 ;
C CC 到 E EE 最短 跳数 是 12 , 12 , 5 12 , 12, 512,12,5 中最小值 5 55 ;
C CC 到 F FF 最短 跳数 是 8 , 13 , 9 8 , 13, 98,13,9 中最小值 8 88 ;
C CC 达到所有节点的路径是 ( 11 , 6 , 0 , 3 , 5 , 8 ) ( 11, 6, 0 , 3, 5, 8 )(11,6,0,3,5,8)
链路状态路由算法
链路状态路由算法 :
① HELLO 问候分组 : 路由器 通过发送 HELLO 问候分组 , 发现邻居节点 ;
② 度量 : 设置 路由器 到 每个邻居 的成本度量 ;
③ DD 数据库描述分组 : 路由器 向 相邻路由器 给出自己的 链路状态数据库 中 所有链路状态 的 摘要信息 ; ( 注意不是所有信息 )
④ LSR 链路状态请求分组 :
存在摘要对应信息 : 如果 收到的 DD 数据库描述分组 中的摘要 , 自己都有 , 不做任何处理 ;
不存在摘要对应信息 : 如果 没有 或者 有最新的 , 发送 LSR 链路状态请求分组 , 请求自己 没有 或者 有更新 的详细信息 ; ( 这一这里是详细信息 )
⑤ LSU 链路状态更新分组 : 收到 LSR 链路状态请求分组 后 , 发送 LSU 链路状态更新分组 , 更新对方路由器的 链路状态数据库信息 ;
⑥ LSAck 链路状态确认分组 : 收到 LSU 链路状态更新分组 后 , 返回 LSAck 链路状态确认分组 进行确认 ;
某个 路由器 链路状态 发生变化 后的操作 :
① LSU 链路状态更新分组 : 泛洪法 发送 LSU 链路状态更新分组 , 更新所有路由器的 链路状态数据库 ;
② LSAck 链路状态确认分组 : 路由器更新完毕后 , 回送 LSAck 链路状态确认分组 ;
③ 构造最短路径 : 每个路由器 根据自身的 链路状态数据库 , 构造本节点到其它节点的最短路径 ;
