4.4.2 分层次的路由选择协议
## 4.4.2 分层次的路由选择协议 互联网采用的是自适应的分布式路由选择协议。由于互联网规模非常庞大，且许多联网单位不愿对外暴露其内部网络细节，因此采用了分层次的路由选择协议。 为此，整个互联网被划分为多个较小的自治系统（Autonomous System，AS）。每个自治系统在对外通信时，表现为一个单一且一致的路由选择策略。自治系统的管理者有权自主决定在其内部使用何种路由选择协议（如RIP或OSPF）。 基于此，互联网的路由选择协议被划分为两大类。 1. 内部网关协议 (Interior Gateway Protocol, IGP) 内部网关协议用于自治系统内部的路由选择，与其他自治系统所采用的协议无关。目前这类路由选择协议使用得最多，如 RIP 和 OSPF。 2. 外部网关协议（External Gateway Protocol，EGP） 当源主机和目的主机位于不同的自治系统中（这两个自治系统可能使用不同的IGP），数据报在到达某一自治系统边界时，就需要借助一种协议将路由信息传递到另一个自治系统。这类协议称为外部网关协议。当前广泛使用的外部网关协议是BGP-4。 自治系统之间的路由选择也称域间路由选择，自治系统内部的路由选择也称域内路由选择。 图4.17是两个自治系统互连的示意图。每个自治系统可以自行选择内部使用的网关协议（如RIP或OSPF）。但每个自治系统都至少有一个或多个边界路由器（图中的R1和R2），这些路由器除运行本系统的内部网关协议外，还需运行外部网关协议（如BGP-4）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图4.17 两个自治系统互连的示意图 ## 4.4.3 路由信息协议 路由信息协议（Routing Information Protocol，RIP）是内部网关协议（IGP）中最早得到广泛应用的协议之一。RIP是一种分布式的、基于距离向量的路由选择协议。 1. RIP 的规定 1）RIP 使用跳数（Hop Count，也称距离）来衡量到达目的网络的远近。规定从一个路由器到其直连网络的距离为 1；每经过一个路由器，跳数加 1。 2）RIP 认为“好”的路由就是所经路由器数量最少的路径，即跳数最少。 <!-- page: 201 --> 第4章 网络层 189 **考点追查** ▶ RIP 中跳数为 16 的含义（2010） 3）RIP 规定一条路径最多包含 15 个路由器，因此跳数为 16 表示目的网络不可达。由此可见，RIP 仅适用于小型自治系统。 4）每个路由表项包含三个关键字段：<目的网络 N，距离 d，下一跳路由器地址 X >，其含义是“我通过下一跳路由器 X 到达目的网络 N 的距离为 d”。 5）网络中的每个路由器都需维护一个距离向量，即其到所有目的网络的距离记录。 ## 2. RIP 的特点 RIP 要求每个路由器持续与其他路由器交换信息，其工作特点主要体现在以下三个方面。 1）和谁交换信息：仅和直接相邻的路由器交换信息。 2）交换什么信息：交换的是本路由器当前的完整路由表，即全部路由信息。 3）何时交换信息：按固定的时间间隔（默认为 30 秒）交换路由信息，路由器据此更新自己的路由表。当网络拓扑发生变化时，路由器也及时向相邻路由器通告最新路由信息。 路由器刚开始工作时，它的路由器表是空的。然后，路由器得知到几个直连网络的距离为 1。接着，它周期性地与邻居交换并更新路由信息。经过若干轮的交换和更新后，所有路由器最终都会获知到达本自治系统内任意网络的最少跳数和对应的下一跳地址，这一过程称为收敛。 **考点追查** ▶ RIP 使用的下层协议（2017） RIP 是应用层协议，它使用 UDP 传送数据（端口 520）。需要注意的是，RIP 选择的路径不一定是时延最短，但一定是跳数最少的路径，因为它仅依据跳数进行路径选择。 ## 3. RIP 的基本工作原理 对于每个相邻路由器发来的 RIP 报文，执行以下步骤： 1）对来自地址为 X 的相邻路由器的 RIP 报文，首先修改其中所有项目：将所有“下一跳”字段都置为 X，并将所有“距离”字段的值加 1。 2）对修改后的每个项目，按如下规则处理： IF (若原路由表中没有目的网络 N) 则将该项目加入路由表（表示发现新网络）。 ELSE IF (若原路由表中已有目的网络 N，且原下一跳地址是 X) 用新收到的项目替换原表项（要以最新的消息为准）。 ELSE IF (若原路由表中已有目的网络 N，但原下一跳地址不是 X) 若新收到的项目中的距离 d 小于当前记录的距离，则替换原表项（表示找到更优路径）。 ELSE 什么也不做。 3）若连续 180 秒（RIP 默认超时时间）未收到某相邻路由器的更新报文，则将其标记为不可达，即将对应路由项的距离置为 16（表示不可达）。 4）处理完毕，返回。 **考点追查** ▶ RIP 路由收敛机制（2024） 下面举例说明 RIP 路由表项的更新过程。已知路由器 R6 和 R4 互为相邻路由器，表 4.4(a) 所示为 R6 的路由表。现在收到相邻路由器 R4 发来的路由表，如表 4.4(b) 所示。 表 4.4(a) R6 的路由表 | 目的网络 | 距离 | 下一跳路由器 | | --- | --- | --- | | Net2 | 3 | R4 | | Net3 | 4 | R5 | | ... | ... | ... | 表 4.4(b) R4 发来的路由表 | 目的网络 | 距离 | 下一跳路由器 | | --- | --- | --- | | Net1 | 3 | R1 | | Net2 | 4 | R2 | | Net3 | 1 | 直接交付 | <!-- page: 202 --> 2027年计算机网络考研复习指导 现对 R6 的路由表进行更新。先把 R4 发来的路由表［表 4.4(b)］中各项的距离都加 1，并把下一跳路由器都改为 R4，得到表 4.5(a)。这么做的意义是：R4 是 R6 的相邻路由器，R6 可通过 R4 到达这些网络，但距离比 R4 到达这些网络的距离大 1。将该表与 R6 的原路由表逐项比较。 表 4.5(a) 修改 R4 发来的路由表 | 目的网络 | 距离 | 下一跳路由器 | | --- | --- | --- | | Net1 | 4 | R4 | | Net2 | 5 | R4 | | Net3 | 2 | R4 | 表 4.5(b) 更新后 R6 的路由表 | 目的网络 | 距离 | 下一跳路由器 | | --- | --- | --- | | Net1 | 4 | R4 | | Net2 | 5 | R4 | | Net3 | 2 | R4 | | ... | ... | ... | 第一行的 Net1 在表 4.4(a) 中没有。这表明：R6 此前没有到达 Net1 的路由，现在知道可通过 R4 到达 Net1。因此，要把这条 Net1 的路由表项添加到 R6 的路由表中。 第二行的 Net2 在表 4.4(a) 中已有，且下一跳路由器也是 R4。这表明：R6 到达 Net2 的最佳路由仍然是通过 R4，但距离发生了变化（通常由网络拓扑变化引起）。因此，要更新目的网络 Net2 的路由表项（无论距离是变大还是变小，都需要更新）。 第三行的 Net3 在表 4.4(a) 中已有，但下一跳路由器不同。此时比较距离，新路由信息的距离为 2，小于原表中的 4。这表明：R6 通过 R4 到达 Net3 的路径比原来经由 R5 的更短，因此应更新 Net3 的路由表项（新路由的距离更大时，不更新）。 更新后的 R6 的路由表如表 4.5(b) 所示。 ## 4. RIP 的优缺点 **修改说明** ▶ RIP 的优缺点（2024） RIP 的优点： 1）实现简单、开销小、收敛过程较快。 2）若一个路由器发现更短的路由，该更新信息会迅速传播，在较短时间内即可传至所有路由器，俗称“好消息传播得快”。 RIP 的缺点： 1）RIP 限制了网络的规模，其最大有效距离为 15（距离 16 表示不可达）。 2）路由器之间交换的是完整的路由表，因此网络规模越大，通信开销也越大。 3）当网络出现故障时，路由器需反复多次交换信息才能完成收敛，故障信息传递缓慢，导致慢收敛现象，俗称“坏消息传播得慢”。 下面举例说明 RIP “好消息传播得快。坏消息传播得慢”的特点。假设图 4.18 中的路由器均采用 RIP 交换路由信息，初始时 R1 到网络 $N$ 的距离为 4，且 R1 和 R2 均已收敛。为简化讨论，此处仅考虑到达网络 $N$ 的路由条目：R1 中为 $<n, 4$，直接$>$，R2 中为 $<n, 5,="" r1="">$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 发现更短的路由
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 链路出现故障 图 4.18 RIP 举例：链路开销改变 在图 4.18(a) 中，某时刻，R1 检测到一条“到 $N$ 更短的链路”（距离由 4 变为 1），于是将到 $N$ 的距离更新为 1，并通知 R2（即便 R1 先收到 R2 发来的更新报文，也不会修改自身到 $N$ 的路由）。R2 收到后，将到 $N$ 的距离更新为 2，并通知 R1；R1 收到后，不再修改自己的路由，算法进入静止状态。可见，R2 到 $N$ 的距离减少的好消息通过 RIP 得到了迅速传播。</n,></n,> <!-- page: 203 --> 第4章 网络层 191 **考虑图表** ▶ RIP “坏消息传播得慢”的分析（2016） 在图 4.18(b)中，某时刻，R1 检测到“N 不可达”（距离由 4 变为 16），于是将到 N 的距离置为 16，但可能需等到下一次周期性更新（默认 30s）才会通知 R2。而在此期间，R2 可能已先将自己的更新报文发给了 R1，其中包含 $<n, 5,="" r1="">$。R1 收到后，误认为可通过 R2 到达 N，于是将路由信息更新为 $<n, 6,="" r2="">$。随后 R1 通知 R2，R2 又据此将路由信息更新为 $<n, 7,="" r1="">$，误认为可通过 R1 到达 N……如此往复，直到两者最终都将距离增至 16，才知道原来 N 是不可达的。可见，RIP 对链路故障或距离增加这类“坏消息”的传播非常缓慢。若无跳数上限（15）的限制，路由器将无限循环转发无效路由信息，因此“坏消息传播得慢”也称无穷计数问题。 ## 4.4.4 开放最短路径优先协议 虽然名称中含有“最短路径优先”，但这并不意味着其他路由协议不采用最短路径原则。实际上，自治系统内使用的所有路由协议都旨在寻找一条最短路径，只是最短的度量标准不同。 ## 1. 开放最短路径优先（OSPF）的基本特点 **考虑图表** ▶ OSPF 与 RIP 特性对比（2024） OSPF 协议是分布式链路状态算法的典型代表，它采用了 Dijkstra 提出的最短路径算法。与 RIP 相比，OSPF 具有以下四个主要特点： 1. OSPF 使用洪泛法向本自治系统中所有路由器发送信息：路由器通过所有输出端口向相邻路由器发送信息，每个相邻路由器再将该信息转发给其所有邻居（但不再回传给刚刚发送信息的路由器）。最终，整个区域内的所有路由器都会收到该信息的一个副本。而 RIP 仅向直接相邻的几个路由器发送信息。 2. OSPF 发送的信息是本路由器与其相邻路由器之间的链路状态（局部拓扑信息），而非全局路由表。而 RIP 发送的是本路由器所知的全部路由信息（完整的路由表）。 3. OSPF 仅在链路状态发生变化时才触发洪泛更新，收敛速度快，不会出现 RIP 中“坏消息传得慢”的问题。而 RIP 不论网络拓扑是否变化，都需定期交换路由信息。 **考虑图表** ▶ OSPF 使用的下层协议（2017） 4. OSPF 是网络层协议，不使用 UDP 或 TCP，而是直接封装在 IP 数据报中（IP 首部的协议字段为 89）。而 RIP 是应用层协议，使用 UDP 传输（端口 520）。 ## 注意 “用 UDP 传送”是指将协议数据作为 UDP 报文的数据部分；“直接使用 IP 数据报传送”则是指将协议数据直接作为 IP 数据报的数据部分。RIP 报文属于前者。 除上述区别外，OSPF 还具有以下优势： 1. OSPF 支持对每条路由设置不同的代价，可针对不同业务类型计算差异化路径。 2. 存在多条到同一目的网络且代价相同的路径时，可实现负载分担（或称负载均衡）。 3. OSPF 分组具备鉴别功能，确保仅在可信路由器之间交换链路状态信息。 4. OSPF 支持可变长子网掩码和无分类编址。 5. 每条链路状态通告均携带一个 32 位序号，序号越大，表示状态越新。 由于各路由器频繁交换链路状态信息，最终所有路由器都能构建出一致的链路状态数据库（LSDB）。随后，每个路由器基于 LSDB，利用 Dijkstra 算法计算到达各目的网络的最优路径，并生成自己的路由表。当链路状态发生变化时，路由器会重新计算并更新路由表。</n,></n,></n,> <!-- page: 204 --> 2027年计算机网络考研复习指导 # 注意 尽管 Dijkstra 算法能计算完整的最优路径，但路由表中不会存储完整路径，而仅存储“下一跳”，只有到了下一跳后，才能确定再下一跳应当怎样走。 为支持大规模网络，OSPF 将一个自治系统划分为若干更小的区域（Area）。划分区域的好处是：将洪泛法交换链路状态信息的范围限制在各区域内，而非整个 AS，从而显著减少网络通信开销。每个区域由一个或多个区域边界路由器负责为进出该区域的分组提供路由。AS 内必须有一个区域配置成主干区域，它包含 AS 内的所有区域边界路由器（可能还包含部分非边界路由器），用于连通其他区域。当分组需在不同区域之间传送时，其转发路径为：源区域 → 本地区域边界路由器 → 主干区域 → 目的区域边界路由器 → 目的地。在图 4.19 中，R3、R4 和 R7 均为区域边界路由器，每个区域至少包含一个区域边界路由器。此外，主干区域中还需指定一个自治系统边界路由器（如 R6），专门负责与本 AS 外的其他 AS 交换路由信息。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 4.19 OSPF 划分区域举例
## 2. OSPF 的五种分组类型
OSPF 定义了以下五种分组类型：
1）问候（Hello）分组，用来发现邻居并维持邻接关系，确认链路双向连通性。
2）数据库描述（Database Description，DD）分组，向邻居发送自己的链路状态数据库（LSDB）中的所有链路状态项目的摘要信息。
3）链路状态请求（Link-State Request，LSR）分组，向邻居请求发送某些链路状态项目的详细信息。
4）链路状态更新（Link-State Update，LSU）分组，通过洪泛法向全网发送链路状态通告（LSA），它是 OSPF 最核心的部分。路由器使用这种分组将其链路状态通知给邻居。
5）链路状态确认（Link-State Acknowledgment，LSAck）分组，对链路更新分组的确认。这五种分组共同支撑了 OSPF 的邻居发现、数据库同步、拓扑更新、可靠确认的全过程。
## 3. OSPF 的基本工作原理
### （1）邻居发现与可达性维护
OSPF 规定，相邻路由器之间需每隔 10s 周期性地交换问候分组，以确认邻接关系并维持彼此的可达性。若某路由器在 40s 内未收到邻居的问候分组，则判定该邻居已不可达，并立即触发链路状态数据库（LSDB）的更新，随后重新运行 Dijkstra 算法以生成新的路由表。
通常，网络中传送的大多数 OSPF 分组都是问候分组。
### （2）链路状态数据库的初始同步
路由器刚启动时，仅能通过问候分组发现其直连邻居，并获知本地链路的基本信息（如接口
<!-- page: 205 -->
第4章 网络层
193
状态和链路开销）。然而，要构建完整的 LSDB，若采用全网广播所有路由器的完整链路状态信息，则会带来巨大的通信开销。为此，OSPF 采用了一种高效且可靠的同步机制。
首先，相邻路由器通过数据库描述分组交换各自 LSDB 中链路状态通告（LSA）的摘要信息；随后，路由器根据摘要对比，使用链路状态请求分组向邻居请求自身缺失或过期的 LSA 详细内容；对方则通过链路状态更新分组发送所请求的 LSA，接收方成功接收后需返回链路状态确认分组以确保可靠传输。通过这一系列交互，相邻路由器最终实现 LSDB 的完全同步。
（3）链路状态变更的实时传播
在网络运行过程中，一旦路由器检测到自己的链路状态发生变化（如接口故障或邻居失效等），就会立即生成新的 LSA，并通过链路状态更新分组以可靠的泛洪方式向整个区域传播。其他路由器收到后，同样必须返回确认，随后更新自己的 LSDB，重新运行 Dijkstra 算法计算路由。
（4）链路状态通告的定期更新
每条 LSA 的最大生存时间为 60 分钟，为防止 LSA 丢失或异常，最初生成该 LSA 的路由器需定期（通常是每隔 30 分钟）刷新该 LSA，从而确保 LSDB 与实际网络拓扑始终保持一致。
由于每个路由器的链路状态信息仅描述其与直连邻居的连接关系及链路代价，与全网规模无直接关联。因此，当网络规模很大时，OSPF 要显著优于基于跳数且收敛缓慢的 RIP。
## 4.4.5 边界网关协议
### 1. BGP 的基本特点
**特点信息** ▶ BGP 的功能（2013）
边界网关协议（Border Gateway Protocol，BGP）是不同自治系统的路由器之间交换路由信息的协议，是一种外部网关协议。BGP 常用于互联网的 AS 之间。而 RIP 和 OSPF 都只能在一个 AS 内工作；若没有 BGP，则全世界数以万计的 AS 都将是一个个彼此孤立的“孤岛”。
内部网关协议主要是设法使分组在一个 AS 内尽可能有效地从源站传送到目的站。在一个 AS 内部通常不需要考虑其他方面的策略。然而 BGP 使用的环境却不同，主要原因如下：
1）互联网的规模太大，使得 AS 之间的路由选择非常困难，每个主干网路由器表中的项目数都非常庞大。对于 AS 之间的路由选择，要寻找最佳路由是很不现实的。
2）AS 之间的路由选择必须考虑政治、安全或经济等有关因素。
**特点信息** ▶ BGP 使用的下层协议（2013、2017）
因此，BGP 只能力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。BGP 采用了路径向量路由选择协议，它与距离向量协议（如 RIP）和链路状态协议（如 OSPF）都有很大的区别。BGP 是应用层协议，基于 TCP 实现。
### 2. BGP 路由
BGP 路由的一般格式如下：
$$
\mathrm{BGP} \text{ 路由} = <\text{前缀, BGP 属性}> = <\text{前缀, AS-PATH, NEXT-HOP}>
$$
BGP 属性有多种类型。当一个路由器通过 BGP 会话向对等方通告一条 BGP 路由时，最重要的两个属性是 AS-PATH（自治系统路径）和 NEXT-HOP（下一跳）。
AS-PATH 记录了该 BGP 路由所经过的自治系统序列。在 BGP 中，每个自治系统由一个全局唯一的自治系统号（ASN）标识。BGP 路由每经过一个 AS，就向其 ASN 加入 AS-PATH。可见，BGP 路由明确指出了所经过的 AS 路径，但不指明具体经过哪些路由器。
NEXT-HOP 表示接收该 BGP 路由的路由器去往目的网络时应使用的下一跳地址。具体而言，
<!-- page: 206 -->
2027年计算机网络考研复习指导
从本 AS 出发时，需将分组发给 NEXT-HOP，其通常是通告此路由的邻居 AS 的边界路由器上与本 AS 直连的接口 IP 地址，即 AS-PATH 中第一个 AS（邻居 AS）对应的入口点。
**考点选注** BGP 会话类型（2024）
在一个 AS 中有两类功能不同的路由器：边界路由器和内部路由器。在这些边界路由器之间，以及在 AS 内部的 BGP 路由器之间，均通过端口号为 179 的半永久 TCP 连接（交换信息后仍保持连接）来交换 BGP 路由信息。每对通过 TCP 连接交换 BGP 报文的路由器称为 BGP 对等方，该 TCP 连接称为 BGP 会话。其中，跨越两个 AS 的 BGP 会话称为外部 BGP（eBGP，external）会话，而位于同一 AS 内的 BGP 会话称为内部 BGP（iBGP，internal）会话。可见，BGP 不仅用于 AS 之间的路由交换，还运行于 AS 内部，以确保外部路由信息在整个 AS 中正确传播。
为避免路由信息丢失，BGP 要求在 AS 内的任意两台路由器之间都要建立 iBGP 会话，但不要求物理直连（如图 4.20 中 R2 与 R4、R2 与 R5 之间的 iBGP 会话）。
下面通过一个简单的例子来说明。
在图 4.20 中，位于 AS2 的 R4 收到一条 BGP 路由 “X, AS-PATH = AS1, NEXT-HOP = R1”，表示“从 R1 出发，经过 AS1，可到达网络 X”，即“R1→X”。R4 为了构造自己的路由表，需要解析该路由的 NEXT-HOP。由于 R1 位于 AS1，AS2 的内部路由器无法直接将分组发往 R1，因此 R4 必须通过 AS2 中的某个边界路由器来抵达 NEXT-HOP。具体地，R4 知道 R1 是其 eBGP 对等方 R2 的邻居，因此通往 R1 的流量必须先发给 R2，形成的路径为“R2→R1→X”。由于 R2 在 AS2 中，AS2 内的所有路由器都能将分组转发到 R2，再经过 R1，最终到达 X。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 4.20 BGP 路由的举例 接着，R4 利用内部网关协议（IGP），找到从自身到 R2 的最优路径，假设查得下一跳为 R3。于是，R4 在路由表中添加表项<x, r3="">。此后，R4 收到目的网络为 X 的分组时，将按路径 R4→R3→R2→R1→X 转发。类似地，R3 也会在其路由表中添加表项<x, r2="">。每个路由器在收到新的 BGP 路由通告后，都需要执行 NEXT-HOP 解析和 IGP 查找，才能将路由正确写入本地路由表。