1 路由器与路由选择

1.1 路由器

路由器是一种具有多个输入端口和输出端口的专用计算机，其任务是转发分组和路由选择。

实现的网络模型：物理层、数据链路层、网络层。

路由器的结构分为两个部分：

• 路由选择部分（控制部分）：核心是路由选择处理机，它根据路由选择协议构造出路由表，路由表需要对网络拓扑变化的计算最优化。
• 分组转发部分：由三部分组成：交换结构、输入端口、输出端口。
  • 输入端口：物理层的比特流–>数据链路层中解析出帧–>网络层中解析出 IP 数据报–>输入端口。
  • 输出端口：输出端口–>网络层封装 IP 首部–>数据链路层封装帧首部–>物理层传输比特流。
  • 交换结构：路由器的关键部件，它根据转发表对分组进行处理。转发表是由路由器得来的，转发表的结构应当使查找过程最优化。

【注】实现交换结构的三种基本方式是：通过存储器、通过总线以及通过互连网络。这三种交换结构可实现的路由器转发速率依次提高。

1.2 路由表（RIB 表）

1.2.1 路由表项

路由表（Route Information Base，RIB）的主要用途是路由选择。路由表的每一表项都是一条路由信息，一般包含以下信息：

• 目的地/子网掩码（Destination/Genmask）：若掩码长度为 32，则目的地是一个目的主机地址；否则，目的地是一个目的网络地址。
• 下一跳（Next Hop）：分组到达下一个路由器的 IP 地址。
• 接口（Interface）：从该路由器的哪个接口将分组发送出去。

1.2.2 动态路由

• 动态路由：路由器通过路由选择协议自动获取路由信息。
• 动态路由选择算法（自适应路由算法）：路由器间彼此交换信息，按照路由算法优化出路由表项。
• 动态路由选择算法比较复杂、开销比较大，但能较好地适应网络状态的变化。
• 动态路由选择算法适用于大规模网络。

1.2.3 静态路由

• 静态路由：采用人工配置的方式给路由器添加网络路由、默认路由和特定主机路由等路由条目。
• 静态路由选择算法（非自适应路由算法）：管理员手工配置路由信息。
• 静态路由选择算法简单、开销小，但不能及时适应网络状态（流量、拓扑等）的变化。
• 静态路由选择算法一般只在小规模网络中采用。

静态路由有两种特殊的路由：

【注】进行静态路由配置需要注意：

• 路由条目配置错误，甚至导致出现路由环路。
• 聚合路由条目时可能引入不存在的网络。

1.2.4 直连路由

• 直连路由：由链路层协议发现的，一般指去往路由器的接口地址所在网段的路径，该路径信息不需要网络管理员维护，也不需要路由器通过某种算法进行计算获得，只要该接口处于活动状态（Active），路由器就会把通向该网段的路由信息填写到路由表中去。

例如以下网络：

初始时，各路由器往路由表中填写直连路由，如下：

• 路由器 R1 的路由表：

• 路由器 R2 的路由表：

但是 R1 到目的网络 192.168.2.0/24 的路由没有配置，R2 到目的网络 192.168.1.0/24 的路由也没有配置，除此之外，R1 和 R2 去往因特网的路由也没有配置。我们可以进行人工配置，也可以依据路由选择协议（下面将详细介绍）让路由器自己获取路由。以下是人工配置后的路由表：

• 路由器 R1 的路由表：

【注】最后一个路由表项即为默认路由，默认路由必须为人工配置。R2 成为该网络的默认网关，它是本网络与外网连接的设备，就像古代扼守出入的“关口”。当分组目的地址找不到对应的目的网络时，路由器 R1 便认为该分组的目的地址在互联网中，因此将该分组从接口 1 转发出去。

• 路由器 R2 的路由表：

如果新增加的路由是依据路由选择协议得出的，则类型应为“动态”。

1.3 转发表（FIB 表）

转发表（Forward Information Base，FIB）是从路由表得出的，其表项和路由表项有直接的对应关系。分组抵达路由器后，解析出分组的目的地址，并根据转发表将分组从适当的端口转发出去。

转发表项的格式为：

路由表存在下一跳非直连的表项，而转发表不存在这样的表项。

【注】转发和路由选择（路由转发）的区别：

• 转发：路由器根据 IP 数据报的要求从正确的端口转发出去。
• 路由选择：涉及很多路由器，根据从各相邻路由器得到的网络拓扑情况，动态改变自己的路由表。可以这么认为，路由表将整个网络拓扑结构都记录了下来。

1.4 自治系统 AS

• 自治系统（Autonomous System，AS）：单一技术管理下的一组路由器，这组路由器使用同一个路由选择协议，并且所有路由器都是互相连通的。同时，在自治系统的外部，采用其他的路由选择协议。
• 域内路由选择：指的是在自治系统内部的路由选择，采用内部网关协议（Interior Gateway Protocol，IGP）。IGP 不是一个具体的协议，而是一个分类名称，包括 RIP 和 OSPF。
• 域间路由选择：指的是在自治系统之间的路由选择，采用外部网关协议（External Gateway Protocol，EGP）。EGP 不是一个具体的协议，而是一个分类名称，包括 BGP。

2 内部网关协议 IGP——路由信息协议 RIP

路由信息协议（Routing Information Protocol，RIP）是内部网关协议中最先得到广泛使用的协议之一，其相关标准文档为[RFC 1058]。

RIP 是应用层协议，它使用 UDP 封装数据，UDP 端口号为 520。所以当传输到网络层时，报文将会是这个样子：

2.1 RIP 规定

• 自治系统 AS 内的每一个路由器，都要维护从它自己到 AS 内其他每一个网络的距离记录。这是一组距离，称为距离向量（Distance-Vector，D-V）。
• 使用跳数（Hop Count）作为度量（Metric）来衡量到达目的网络的距离。
  • 路由器到直连网络的距离 ::= 1。
  • 路由器到非直连网络的距离 ::= 所经过的路由器数 + 1。
  • 距离 ≤ 15，距离 = 16表示该网络不可达。

【注 1】由于距离限制，RIP 只适用于小型互联网。规定最高跳数是为了防止出现路由环路的情况。

【注 2】哪怕存在另一条传输速率更快、路由器更多的路径，RIP 依然会选择路由器最少的路径。

• 最优路由：通过路由器数量最少的路由。
• 等价负载均衡：若有多条 RIP 距离相等的路由，则可以进行等价负载均衡，也就是将通信量均衡地分布到多条等价的路径上。
• 交换信息：和相邻路由器交换自己的路由表，每隔一段周期（比如 30s）交换一次。
• 收敛速度：指把一个信息传遍所有路由的速度。

【注 1】为了加快 RIP 的收敛速度，当网络拓扑发生变化时，路由器要及时向相邻路由器通告拓扑变化后的路由信息，这称为触发更新。

【注 2】什么是相邻路由器？例如：R1—R2—R3，则 R1 和 R2、R2 和 R3 均为相邻路由器，而 R1 和 R3 不是相邻路由器。

• 使用 RIP 的路由表：

• 为方便后续讨论，我们将每一个路由表项写为<目的网络, RIP 距离, 下一跳>。

2.2 RIP 的工作原理

假设有以下自治系统 AS：

• 路由器刚开始工作时，只知道自己到直连网络的 RIP 距离为 1。如下表为各路由器的路由表：

• 每个路由器仅和相邻路由器周期性地交换并更新路由信息。若干次交换和更新后，每个路由器都知道到达本自治系统 AS 内各网络的最短距离和下一跳路由器，称为收敛。如下表为收敛后各路由器的路由表：

各路由器是通过怎样的步骤得出各自的路由表？这就是距离向量算法所处理的事情。

2.3 RIP 的距离向量算法

假设有两个相邻的路由器：路由器C--------路由器D

路由器 C 和 D 的路由表如下：

现路由器 C 发送一个 RIP 更新报文给路由器 D。路由器 D 收到报文后，将该报文作修改，然后与自己的路由表对比，并修改自己的路由表。步骤如下：

• 把“下一跳”改为路由器 C，并将所有“RIP 距离”加 1。为何加 1？因为有N2----(距离4)----路由器C----(距离1)----路由器D。

• 若“目的网络”相同，“下一跳”相同，则更新对应条目。为什么需要更新？因为网络拓扑结构是动态变化的，需要不断更新。例如：N2----(距离2)----路由器C----(距离1)----路由器D，网络拓扑结构变化后：N2----(距离4)----路由器C----(距离1)----路由器D。

• 若发现新的“目的网络”，加入该条目。

• 若“目的网络”相同，“下一跳”不同，“RIP 距离”比之前的更小，则更新对应条目。如果“RIP 距离”比之前的更大，则不更新对应条目。

• 若“目的网络”相同，“下一跳”不同，“RIP 距离”相等，则加入该条目，以实现等价负载均衡。

• 路由器每隔大约 30 秒向其所有相邻路由器发送路由更新报文。
• 若 180 秒（默认超时时间）没有收到某条路由条目的更新报文，则把该路由条目标记为无效（即把 RIP 距离设置为 16，表示不可达），若再过一段时间（如 120 秒），还没有收到该路由条目的更新报文，则将该路由条目从路由表中删除。

2.4 RIP 存在的问题

假设网络 N1 到路由器 R1 之间出现了故障：N1----x----路由器R1--------路由器R2

路由器 R1 的路由：<N1, 16, 直连>，路由器 R2 的路由：<N1, 2, R1>（R2 还不知道 N1 与 R1 之间出了故障）

• 若 R2 的 RIP 更新报文先到 R1，则 R1 被“谣言”所误导，修改了自己的路由：<N1, 3, R2>
• R1 向 R2 发送 RIP 更新报文，则 R2 路由：<N1, 4, R1>
• 30s 后，R2 向 R1 发送 RIP 更新报文，则 R1 路由：<N1, 5, R2>
• R1 向 R2 发送 RIP 更新报文，则 R2 路由：<N1, 6, R1>
• 30s 后，R2 向 R1 发送 RIP 更新报文，则 R1 路由：<N1, 7, R2>
• R1 向 R2 发送 RIP 更新报文，则 R2 路由：<N1, 8, R1>
• …
• 30s 后，R2 向 R1 发送 RIP 更新报文，则 R1 路由：<N1, 13, R2>
• R1 向 R2 发送 RIP 更新报文，则 R2 路由：<N1, 14, R1>
• 30s 后，R2 向 R1 发送 RIP 更新报文，则 R1 路由：<N1, 15, R2>
• R1 向 R2 发送 RIP 更新报文，则 R2 路由：<N1, 16, R2>

此时路由器 R2 才发现 N1 是不可达的，整个自治系统才达到收敛，即 R1 和 R2 均知道 N1 不可达。

如果一个路由器发现了 RIP 距离更短的路由，那么这种更新信息就传播得很快，即“好消息传得快”。

但一旦出现不可达的故障，则更新过程的收敛时间长，收敛速度很慢，即“坏消息传得慢”。

2.5 RIP 的优缺点

• 优点：
  • 实现简单，路由器开销小。
  • 如果一个路由器发现了 RIP 距离更短的路由，那么这种更新信息就传播得很快，即“好消息传播得快”。
• 缺点：
  • RIP 限制了最大 RIP 距离为 15，这就限制了使用 RIP 的自治系统 AS 的规模。
  • 相邻路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也随之增大。
  • “坏消息传播得慢”，使更新过程的收敛时间过长。因此，对于规模较大的自治系统 AS，应当使用 OSPF 协议。

3 内部网关协议 IGP——开放最短路径优先协议 OSPF

开放最短路径优先（Open Shortest Path First，OSPF）协议是为了克服路由信息协议 RIP 的缺点而开发出来的。

OSPF 不使用 UDP 数据报传送，而是直接使用 IP 数据报传送。

OSPF 是基于链路状态的，而不像 RIP 是基于距离向量的。

3.1 OSPF 的相关概念

• 链路状态（Link State，LS）：指本路由器都和哪些路由器相邻，以及相应链路的“代价”。
• 代价（度量，metric）：用来表示费用、距离、时延和带宽等，这些都由网络管理人员来决定。

【注】“代价”可理解为图上的边的权重值，在 OSPF 中一般称为成本度量 metric。

• OSPF 的五种报文类型：

3.2 OSPF 的工作原理

假设有以下自治系统 AS，连线上的数值即为度量代价 metric，该自治系统连接了外部网络 N1。

R1------(1)------R2
|                |
|                |
|                |
(5)             (2)
|                |
|                |
|                |
R3------(4)------R4---(6)---N1

3.2.1 邻居关系的维护

OSPF 相邻路由器之间通过交互问候（Hello）分组来建立和维护邻居关系。

• 问候分组封装在 IP 数据报中，发往组播地址 224.0.0.5。IP 数据报首部中的协议号字段的取值为 89，表明 IP 数据报的数据载荷为 OSPF 分组：

• 问候分组的发送周期为 10 秒。若 40 秒未收到来自邻居路由器的问候分组，则认为邻居路由器不可达。
• 每个路由器都会建立一张邻居表。比如 R1 的邻居表：

• 不仅如此，每个路由器都会产生链路状态通告（Link State Advertisement，LSA），其包含两种信息：
  • 直连网络的链路状态信息；
  • 邻居路由器的链路状态信息。
• 例如，R4 的链路状态通告见下表：

3.2.2 链路状态数据库的建立

• 链路状态通告 LSA 被封装在链路状态更新（Link State Update，LSU）分组中，采用可靠的洪泛法（Flooding）进行发送。
  • 洪泛法：路由器向自己所有的邻居路由器发送链路状态更新分组，收到该分组的各路由器又将该分组转发给自己所有的邻居路由器（但其上游路由器除外），以此类推。
  • 可靠：指收到链路状态更新分组后要发送确认，收到重复的更新分组无需再次转发，但要发送一次确认。
• 如下图所示为洪泛法（^ 和 < 表示传送方向）：

R1<<<<<<(LSU)------R2
^                  ^
^                  ^
^                  ^
(LSU)            (LSU)
|                  |
|                  |
|                  |
R3<<<<<<(LSU)------R4------N1

• 链路状态数据库（Link State Database，LSDB）：使用 OSPF 的每一个路由器都有一个链路状态数据库，用于存储链路状态通告 LSA。
• 通过各路由器洪泛发送封装有各自链路状态通告 LSA 的链路状态更新分组 LSU，各路由器的链路状态数据库 LSDB 最终将达到一致。
• 如下表为 R1 的数据库：

• 最后，使用 OSPF 的各路由器，基于链路状态数据库 LSDB 进行最短路径优先计算（采用 Dijkstra 算法，用来求单源最短路径），构建出各自到达其他各路由器的最短路径，即构建各自的路由表。
• 如此往复，每隔 30 min 或链路状态变化时，都要经历以上过程，使得各路由器的链路状态数据库 LSDB 重新达到一致。

3.2.3 链路状态路由算法

下面来总结 OSPF 的工作流程。

链路状态数据库的建立：

• 每个路由器发送问候分组，了解邻居的地址和 metric。
• 路由器 A 发送数据库描述分组，向邻居 B 给出自己数据库中的摘要信息。
• 路由器 B 收到邻居 A 发来的数据库描述分组，解析其中的摘要：
  • 若自己数据库都有，则不作处理；
  • 若存在缺失的或需要更新的，发送链路状态请求分组，请求新的信息。
• 路由器 A 收到邻居 B 发来的链路状态请求分组后，向 B 发送链路状态更新分组。
• 路由器 B 收到邻居 A 发来的链路状态更新分组后，B 更新自己的信息，再向邻居 A 发送链路状态确认分组。
• 每个路由器根据自己的数据库，使用 Dijkstra 算法构造去往其他路由器的最优路径。

只要有一个路由器的链路状态发生变化：

• 该路由器泛洪发送链路状态更新分组。
• 更新完毕后，每个路由器返回链路状态确认分组进行确认。
• 每个路由器根据自己的数据库，使用 Dijkstra 算法构造去往其他路由器的最优路径。

【注】OSPF 没有“坏消息传得慢”的问题，收敛速度很快。

3.2.4 多点接入网络中的 OSPF 路由器

为了减少洪泛发送问候分组和链路状态更新分组的数量，OSPF 选举指定路由器（Designated Router，DR）和备用指定路由器（Backup Designated Router，BDR）。

• 所有的非 DR/BDR 只与 DR/BDR 建立邻居关系。
• 非 DR/BDR 之间通过 DR/BDR 交换信息。

3.3 OSPF 划分区域

为使 OSPF 协议能够用于规模很大的网络，OSPF 把一个自治系统 AS 再划分为若干个更小的范围，称为区域（area）。

• 优点：将洪泛的范围限制在每个区域而非整个自治系统中，减少了网络的通信量。
• 缺点：交换信息的种类增多，同时也使 OSPF 协议更加复杂。

• 自治系统边界路由器（AS Border Router，ASBR）：R6
• 主干路由器（Backbone Router，BBR）：R3、R4、R5、R6
• 区域内路由器（Internal Router，IR）：区域 1 的 R1、R2，区域 2 的 R8，区域 3 的 R9
• 区域边界路由器（Area Border Router，ABR）：R3、R4、R7

4 外部网关协议 EGP——边界网关协议 BGP

边界网关协议（Border Gateway Protocol，BGP）属于外部网关协议 EGP，用于自治系统 AS 之间的路由选择协议。

对于 AS 之间的路由选择，使用统一的“代价”作为度量来寻找最佳路由是不行的。因为不同的 AS 可能使用不同的 IGP，且不是每个 AS 都允许经过。

4.1 BGP 的工作原理

• 在配置 BGP 时，每个 AS 的管理员要选择至少一个路由器作为该 AS 的“BGP 发言人”。
• 使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此称为对方的邻站（neighbor）或对等站（peer）。
• BGP 发言人除了运行 BGP 协议外，还必须运行自己所在 AS 所使用的内部网关协议 IGP，例如 RIP 或 OSPF。
• BGP 发言人交换网络可达性的信息，也就是要到达某个网络所要经过的一系列自治系统。
• 为了与其他 AS 中的 BGP 发言人交换路由信息，就要先建立 TCP 连接，然后在此连接上交换 BGP 报文以建立 BGP 会话，利用 BGP 会话交换路由信息。
• BGP 采用路径向量算法：

• BGP 支持 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。
• 在 BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分（交换路径向量）。这样做对节省网络带宽和减少路由器的处理开销都有好处。

4.2 BGP 的报文类型

5 路由选择协议总结