路由算法
路由
这一节我们首先通过三个问题来认识什么是 路由，接下来再在此基础上介绍 路由协议。
什么是 路由？在一个 IP 网络中，数据包要从一个设备发送到另一个设备，中间通常需要经过多个路由器的转发。每个路由器就像是一个“交通指挥员”，决定数据包该往哪个方向走。
例如，PC-1（IP 地址为 192.168.1.5）通过如下图所示的网络向 PC-2（IP 地址为 10.1.1.5）发送数据包。当路由器 R1 接收到这些数据包时，它必须知道如何到达目标子网 10.1.1.0/24，否则将丢弃这些数据包。
路由器 R2 知道如何到达 PC-2，因为它有一个接口位于子网 10.1.1.0/24，并在 路由表 中包含了一条直接连接路由。然而，默认情况下，路由器 R1 和 R3 不知道如何到达 10.1.1.0/24。网络管理员需要配置一条 静态路由，或者 R2 必须自动告知 R1 和 R3，它们可以将目的地为 10.1.1.0/24 的数据包发送到 R2，这种方式叫做 动态路由。
路由器 怎么知道往哪里转发？路由器 内部有一个叫 路由表 的数据结构，里面记录了各种目的 IP 地址该怎么走。这个表告诉 路由器：当收到一个 IP Packet 时，应该把包发给哪个 下一跳（下一个路由器)。
路由表 如何建立？路由表 主要包含两种建立方式：
- 静态路由 （Static）：人工手动配置，适合小型或稳定网络。
- 动态路由 （Dynamic）：通过 路由协议 自动学习和更新路由信息。
两个 路由表 建立方式各自适用于不同的场景：
| 特点 | 静态路由 | 动态路由 |
|---|---|---|
| 配置方式 | 手动配置 | 自动学习和适应 |
| 适用性 | 适用于小型网络或需要特定路由策略的情况 | 适用于大型、复杂的网络 |
| 稳定性 | 较稳定 | 可能更灵活，但较复杂 |
| 自动故障恢复 | 不支持自动故障恢复 | 支持自动故障检测和恢复 |
| 网络变化响应速度 | 静态，不会自动适应网络变化 | 自动适应网络变化，响应速度较快 |
| 管理复杂性 | 相对简单 | 较复杂，需要更多计算和资源 |
| 适用情况 | 较小规模的网络，特定路由策略需求 | 大型、复杂网络，需要动态适应 |
路由协议
路由协议 是一种 用于路由器之间交换网络路由信息的通信规则。它的主要作用是让路由器能够自动学习和维护到达各个目的网络的路径，从而实现数据包的正确转发。
路由协议 的主要作用有两个：
- 自动学习路由：当网络结构发生变化（如新增路由器、链路断开），路由协议 能自动更新 路由表，省去了手动配置的麻烦。
- 选择最佳路径：如果到同一个目标有多条路径，路由协议 能根据跳数、带宽、延迟等因素计算出最优路径，提高网络效率。
路由协议 分为不同种类，各自适用于不同场景，在介绍其分类前，首先要理解计算机网络中 自治系统 的概念。
自治系统
一个 自治系统（AS，Autonomous System）是由一个或多个网络组成的集合，这些网络 在统一的管理和策略控制下运行，并对外表现为一个单一的路由实体。
互联网是由无数个独立组织维护的网络组成的。每个组织内部的网络结构和路由策略不同，AS 的概念让每个组织可以作为一个独立的“区域”，既能自主控制路由，又能通过标准协议与外部沟通，保证整个互联网正常运作。
AS 通常由一个 ISP（互联网服务提供商）、大型企业、大学等拥有和运营。AS 之间通过外部 路由协议 互联，组成整个互联网。
分类
路由协议 根据其使用范围的不同，可以分为两大类：内部网关协议（IGP，Interior Gateway Protocol）和外部网关协议（EGP，Exterior Gateway Protocol）。
- 内部网关协议：在单个组织或 自治系统（AS）内部使用的路由协议，常见的 IGP 协议包括 RIP 和 OSPF。这些协议的主要作用是在一个组织的网络内部传播和更新路由信息，以实现高效的网络通信。
- 外部网关协议：用于在不同组织或不同 自治系统 之间交换路由信息。如今，唯一广泛使用的 EGP 协议是 BGP。BGP 的设计初衷是为了控制跨组织网络之间的路由信息传递，从而实现 自治系统 之间的互联和路径控制。
对比
重点掌握 RIP、OSPF、BGP 三个协议的区别，三者的对比如下表所示：
| 项目 | RIP | OSPF | BGP |
|---|---|---|---|
| 封装协议 | UDP | IP | TCP |
| 传播方式 | 逐跳 | 泛洪 | TCP 会话间传递 |
| 更新内容 | 全表，周期性 | 链路状态，事件驱动 | 路径属性，事件驱动 |
| 拓扑视图 | 无全局视图 | 拥有全图 | 无全图，仅路径属性 |
| 计算算法 | Bellman-Ford | Dijkstra | 策略驱动 |
| 收敛速度 | 慢 | 快 | 慢（但更稳定） |
| 带宽占用 | 高（周期发全表） | 中（仅更新变化） | 低（TCP 控制精细） |
| 扩展性 | 差 | 较好 | 极强 |
| 应用场景 | 小型网络 | 企业内部网络 | 运营商/跨 AS 互联 |
RIP
RIP（Routing Information Protocol，路由信息协议）是一种基于 距离向量 的路由协议，主要用于小型和中型网络中的 内部网关协议。
距离向量
一个典型的 距离向量（Distance Vector）可以表示为一个列表，其中每个条目包含以下信息：
- 目的地（To）：目标网络或子网的地址。
- 跳数/度量值（Metric）：从当前路由器到达目标网络的 代价，通常以跳数、延迟、带宽等度量标准表示。
- 下一跳（Next Hop）：到达目标网络的 下一跳 路由器的地址。
下表是一个 距离向量示例：
| 目标网络 | 跳数 | 下一跳 |
|---|---|---|
| 192.168.1.0/24 | 0 | A |
| 192.168.2.0/24 | 1 | B |
| 192.168.3.0/24 | 1 | C |
RIP 规定 最大跳数 为 15，超过 15 则认为 目标网络不可达。
此外，路由器将自己的距离向量广播给其他路由器时，距离向量中的下一跳是可以省略的，因为接收者默认认为所有距离向量中的下一跳就是发送该向量的那个路由器本身。
距离向量算法
在 距离向量算法 中，通过 周期性地 与相邻路由器交换 距离向量 信息，每个路由器能够逐渐获得整个网络的拓扑信息，并更新其路由表以 选择最佳路径。
具体而言，工作流程如下：
- 初始化：每个路由器初始化其 距离向量，只包含自己直接连接的网络，距离设为 0。
- 周期性更新：每个路由器周期性地（30s）将其 距离向量 广播给所有相邻的 路由器。
- 接收和更新：每个路由器接收到相邻路由器的 距离向量 后，检查是否有新的或更短的路径。如果有，则更新自己的 距离向量 和 路由表。
- 收敛：经过多次交换和更新后，所有路由器的 距离向量 和 路由表 最终会收敛到最优路径。
最短路径计算方法
当路由器 $A$ 接收到来自相邻路由器 $B$ 发送的关于某个子网 $N$ 的 距离向量 $V_{B}$ 时，它需要将 $V_{B}$ 中的跳数加一 然后与当前的到达子网 $N$ 的 距离向量 $V_{A}$ 进行比较（需要加一的原因时从 $A$ 出发要经过 $B$，所以多了一跳），具体 比较方式 如下：
- 如果 $A$ 不存在到达子网 $N$ 的路由的话，直接添加 $V_{B}$ 进入路由表
- 如果 $V_{B}$ 的跳数小于 $V_{A}$ 的跳数的话，使用 $V_{B}$ 替换 $V_{A}$
以上过程使用的算法名称叫做 Bellman-Ford 算法，是一种寻找单源最短路径的算法，单源最短路径的意思是从一个结点出发到达其他结点的最短路径。这个算法不会直接考察，了解这个算法的名称即可。
坏消息传得慢
假设一个路由器检测到它无法到达一个网络，这个信息可能需要比较长的时间才能被网络中的所有路由器感知到，这个问题也叫做 “计数到无穷”（count to infinity）问题。
举例说明：
对于以下拓扑结构：
A --- B --- C --- X
🟢 正常情况是这样：
- C 广播：“我可以 1 跳到达 X”
- B 收到后更新：B 到 X 跳数 = 2（通过 C）
- A 收到后更新：A 到 X 跳数 = 3（通过 B）
🔴 C 和 X 之间的连接断开：
- C 发现 X 不可达，设置到 X 的跳数为 16（不可达）。
- 但 B 和 A 互相认为“另一个可能知道路径”。
- A 说：“我能通过 B 到 X”，B 也说：“我能通过 A 到 X”，
- 这个过程导致 跳数慢慢增加（4、5、6…），直到达到 16（不可达），才终止。
这也是 RIP 的 核心缺陷，主要由以下几个 RIP 的特性导致：
📌 1. RIP 是“距离向量协议”，而不是“链路状态协议”：
- RIP 每 30 秒定期广播自己的“路由表”（包含目标网络和跳数），而不是主动通告“链路断了”。
- 也就是说：C 不会特意说“我原本能到 X，现在不能了”，它只是不再提 X，或者说“到 X 是 16（不可达）”。
📌 2. RIP 更新是“基于 下一跳”的，不能判断环
B 不知道“我从 A 学到的这条路径，实际上也是绕了一圈又回到我这里”，因为：
- B 从 A 收到：“X 的跳数是 4”
- B 就以为“哦，那我到 A 是 1 跳，所以我到 X 是 5 跳”
- B 没有办法判断这条路径是否环绕回了自己！
它只根据“谁告诉我能到哪里”来加一跳数做判断，而不会检查路径是否形成了环路。
OSPF
OSPF（Open Shortest Path First）是一种基于 链路状态 的 内部网关协议（IGP），广泛应用于中大型网络中。
链路状态
路由器通过 链路状态通告（LSA，Link State Advertisement）来了解其与邻居之间的链路状态。
在 RIP 路由算法中，路由器会定期将自己的 距离向量 发送给相邻的路由器。在 OSPF 中，也有类似的概念，不过这里传送的不是距离向量，而是 链路状态通告。
路由器将其自身的状态和与邻居的链路状态信息打包成 链路状态包（LSP，Link State Packet），并在网络中 洪泛传播（flooding）。
每个 LSA 专注于描述一种类型的链路状态或网络信息。一个 LSA 包含的信息通常是：
- 路由器与某一特定链路的连接状态（如 Router LSA）。
- 某个网络的状态和与其相连的路由器信息（如 Network LSA）。
- 区域间或外部路由信息（如 Summary LSA 和 AS External LSA）。
链路状态数据库
链路状态数据库（LSDB，Link State Database）是 OSPF 协议中的关键组件，它存储了网络中所有 链路状态通告（LSA）。通过 LSDB，每个路由器可以构建整个网络的拓扑图，并使用 Dijkstra 算法计算最短路径树。
这里举个例子方便大家理解 LSDB 的概念。假设我们有一个简单的网络拓扑，包含 4 个路由器（R1, R2, R3, R4）和几个网络网段（NetA, NetB, NetC）。
在 链路状态算法 收敛之后，某个路由器的 LSDB 可能是如下这种形式：
| LSA 类型 | LSA ID | 路由器ID | 链路 ID | 链路类型 | 路径成本 | 连接的路由器或网络 |
|---|---|---|---|---|---|---|
| Router | 1 | R1 | NetA | 广播链路 | 10 | R2 |
| Router | 1 | R1 | NetC | 广播链路 | 5 | |
| Router | 2 | R2 | NetA | 广播链路 | 10 | R1 |
| Router | 2 | R2 | NetB | 广播链路 | 15 | R4 |
| Router | 2 | R2 | R3 | 点对点链路 | 20 | R3 |
| Router | 3 | R3 | R2 | 点对点链路 | 20 | R2 |
| Router | 3 | R3 | R4 | 点对点链路 | 10 | R4 |
| Router | 4 | R4 | NetB | 广播链路 | 15 | R2 |
| Router | 4 | R4 | R3 | 点对点链路 | 10 | R3 |
链路状态路由算法
距离向量 算法（如 RIP）中，每个路由器只维护到各个目的网络的距离（如跳数）和 下一跳 信息，周期性地 将整个路由表发送给直接相邻的 路由器，依赖邻居的更新来调整自己的 路由表，缺乏全局视角，容易形成路由环路，收敛速度较慢，并且存在坏消息传得慢的问题。
而 链路状态 算法（如 OSPF）则由每个路由器通过 链路状态广播（LSA）将本地链路信息 泛洪 给全网，所有路由器据此构建一致的网络拓扑图，然后独立运行 Dijkstra 最短路径算法计算路由，具备 全局视角，收敛速度 快，稳定性好，适合大型复杂网络。
下图通过一个实例对比了 距离向量 和 链路状态 算法的区别：
BGP
BGP（Border Gateway Protocol，边界网关协议）是互联网的核心路由协议，用于在不同 自治系统 之间交换路由信息，属于路径向量（Path Vector）协议，目前广泛使用的版本是 BGP-4。
在 BGP 中，自治系统（AS）是互联网的基本单位，每个 AS 是一个由单个组织控制的网络集合（如一个运营商或大型企业）。AS 与 AS 之间的路由交换就是通过 BGP 完成的，AS 之内的路由交换通过 内部网关协议 完成。
BGP 原理(1) 选择 AS 发言人
- 每个 AS 内部可以有多个 BGP 路由器，但对外通常由一个或多个 “BGP 发言人” 代表整个 AS 与其他 AS 进行路由信息的交换。
(2) 路径向量信息的交换
- BGP 发言人之间通过 TCP 连接建立 BGP 会话，并交换路由前缀及其路径属性。
- 每个 AS 在接收到路径信息后，可以根据自身策略决定：
- 是否接受该路由
- 是否将其传播给其他邻居
- 是否作为本地的最佳路径使用
(3) 路由更新与维护机制
- BGP 是 事件驱动协议，不像 RIP 周期性更新，而是在以下事件发生时才发送 UPDATE 消息：
- 新的可达前缀出现
- 现有前缀的属性发生变化
- 某个前缀不再可达（发送 Withdraw 消息）