（四）路由协议

1. 自治系统（AS）

在单一的技术管理下的一组路由器；
这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由；
使用一种 AS 之间的路由选择协议用以确定分组在不同 AS 之间的路由；
AS 内部可以使用多种路由协议和度量，但是对其他 AS 而言，其表现出的路由策略要是单一和一致的；

2. 域内和域间路由

img_DjpjRBJ0yK

域内路由选择：内部网关协议（IGP，Interior Gateway Protocol）
- 在一个 AS 内部使用的路由选择协议；
- 典型代表：RIP，OSPF；
域间路由选择：外部网关协议（EGP，External Gateway Protocol）
- 不同 AS 间传递数据时使用的路由选择协议；
- 典型代表：BGP-4（BGP v4）

3. RIP 路由协议

3.1. 特点

分布式的，基于距离向量的路由选择协议；
要求网络中的每个路由器维护一个自己达到其他每一个网络的距离记录；
采用 UDP 协议传输数据报；

3.2. 距离

从路由器到其直接连接的网络的距离为 1；
从路由器到非直连网络的距离 = 经过的路由器数 + 1；
- 例：路由器 R1 在网络 A，R2 在网络 B，R1 访问 B 的链路为 R1 → R2。则经过 1 个路由器 R2，距离为 2；
取最短距离，距离也称为跳数（jump count）；

3.3. 要求

RIP 要求每条路径最多经过 15 个路由器，即 $d_{max} = 16$ ，超过时，认为该路径不可达；
RIP 只适用于小型互联网；

3.4. 三个要点

1）只和相邻路由器交换信息；
2）交换的路由信息是当前己知的全部信息，即全部路由表；
3）按照固定的时间间隔交换信息（一般取 30s）；

3.5. 距离向量算法

路由器收到相邻路由器（地址为 $X$ ）的报文时：
- 1）修改 RIP 报文中的路由表项：将所有 "下一跳" 地址修改为 $X$ ，并把所有表项的距离值 +1；
- 2）对于 RIP 报文中的每一个表项 $i$ ：
  - 若目的网络不在路由表中，则加入；
  - 若目的网络在路由表中（设为 $j$ ）：（1）若 $j$ 的下一跳地址等于 $X$ ，则直接更新该项；（2）否则，判断 $i$ 的距离和 $j$ 的地址，在 $d_{i} < d_{j}$ 时才更新；
实例分析
- 网络 2 下一跳相同，更新距离为 5；
- 网络 3 为新表项，加入路由表；
- 网络 6 经过 C 的距离更小，所以替换；
- 网络 8 和 9 经过 C 的距离相同或更大，所以不变；

3.6. 优缺点

缺点：网络故障时，错误消息传播慢，要经过较长时间传递到所有路由器；适用规模小；
优点：实现简单，开销小（规模很小时）；
实例分析：RIP 错误消息传播慢的推导
- 初始：路由器 R1 直连网 1，R2 通过 R1 连接网 1。R1 到网 1 的距离为 1，R2 为 2；
- 1）网 1 出现故障，R1 更新网 1 距离为 16（不可达），此时未更新的 R2 发送 RIP 报文到 R1；
- 2）R1 收到 R2 报文，误认为通过 R2 可到达网 1，故更新距离为 3。之后，R2 收到 R1 的 RIP 报文，又将距离修改为 4；
- 3）如此循环直到 R1 和 R2 的距离都加至 16，才能确认网 1 都是不可达，浪费较长时间；

4. OSPF 路由协议

4.1. 特点

OSPF - Open SPF：Open 表示开源协议，SPF 表示使用 Dijkstra 的最短路径算法 SPF；
路由器向自治系统中所有的路由器发送信息（使用洪水填充法 Floodfill）；
发送的消息为与本路由器相邻路由器的链路状态（即相连的路由器和距离度量）；
仅当链路状态发生变化时，才用洪水填充法发送消息，且发送的消息为变化的链路状态（差分）；
链路状态带有一个 32 位时间戳，时间戳越大表示该数据越新；
OSPF 直接使用 ip 数据报，而不采用 UDP。减少通信量，且不必将数据报分片（分片数据报只要丢失一个就要全部重传）；
OSPF 的分组均支持可变长度子网划分和 CIDR；
规定每隔一段时间（一般 30min）要更新链路数据库中的链路状态；
对网络变化响应速度快（一般在 100ms 以内）；

4.2. 链路状态数据库

本质是网络中所有路由器构成的拓扑图；
更新速度和收敛速度快，且在全网络范围内一致；

4.3. 区域（Area）

为了应用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，称为区域（Area）；
每一个区域都有一个32位的区域标识符（点分十进制表示）；
一个区域内的路由器最好不超过 200 个；
洪水填充法的范围局限在区域内，减少了整个网络的通信量；
区域内的路由器只具有本区域的拓扑图，不具有其他区域的
两种不同的区域（主干区域和普通区域）
- 主干区域（backbone area）的标识为 0.0.0.0，其作用为连通其他区域；

4.4. OSPF 的五种分组

1）问候（Hello）：维持和更新相邻路由器的可达性；
2）数据库描述（DD）：向相邻路由器发送数据库摘要信息；
3）链路状态请求（LSR）：请求目标发送链路状态详细信息；
4）链路状态更新（LSU）：洪水填充法，向全部路由器更新链路状态；
5）链路状态确认（LSA）：确认收到了 LSU 分组；

4.5. OSPF 的基本操作

img_0sEZpMyiu6

5. BGP-4 路由协议

5.1. BGP 发言人（BGP speaker）

每一个 AS 选择至少一个路由器作为该 AS 的 BGP 发言人；
不同 AS 的发言人通过一个共享网络连接在一起；
一般来说选择 AS 网络边界的路由器作为发言人，但也可以不是边界的；

5.2. BGP 路由信息交换

方式：建立 TCP 连接，在 TCP 连接上建立 BGP 会话（session），利用 BGP 会话交换信息；
使用 TCP 协议，能提供可靠的连接服务，也简化了路由选择协议；
使用 TCP 交换信息的发言人称为彼此的邻站或对等站；

5.3. BGP 发言人和 AS 的关系

img_LNmSK9FjTU

5.4. BGP 报文

打开（OPEN）：与相邻的 BGP 发言人建立关系；
更新（UPDATE）：发送或撤销路由信息；
保活（KEEPALIVE）：确认收到 OPEN 报文，以及周期性确认邻站可达性；
通知（NOTIFICATION）：发送检测到的错误；
（RFC 2918 新加）刷新（ROUTE-REFRESH）：用于请求对等站重新通告；