网络层：控制平面

控制平面的作用

回顾网络层的两大核心功能：

1. 转发（Forwarding）：将数据包从路由器的输入端口移动到正确的输出端口。这是数据平面（Data Plane）的功能，处理的是单个数据包的快速路径选择。
2. 路由（Routing）：确定数据包从源到目的地所经过的端到端路径。这是控制平面（Control Plane）的功能，负责构建和维护指导转发决策所需的信息（即转发表）。

数据平面 vs 控制平面

• 数据平面：关注局部，每个路由器内部的操作，通常由硬件实现以保证高速。
• 控制平面：关注网络全局，涉及路由器之间的交互以确定路径，运行速度相对较慢，允许软件实现。

控制平面的两种主要实现方法：

1. 每路由器控制（Per-Router Control）：

   • 传统方式。
   • 每个路由器都运行一个路由算法，通过相互交换路由信息来共同计算路由路径，并生成各自的转发表。
   • 路由算法在路由器内部的控制平面组件中执行。

   graph LR
       subgraph Router1
           direction TB
           R1_CP[路由算法] --> R1_DP(转发表)
       end
       subgraph Router2
           direction TB
           R2_CP[路由算法] --> R2_DP(转发表)
       end
       subgraph Router3
           direction TB
           R3_CP[路由算法] --> R3_DP(转发表)
       end
       R1_CP <-- 控制信息 --> R2_CP
       R2_CP <-- 控制信息 --> R3_CP
       R1_CP <-- 控制信息 --> R3_CP
   
       style R1_CP fill:#ccf,stroke:#888
       style R2_CP fill:#ccf,stroke:#888
       style R3_CP fill:#ccf,stroke:#888
       style R1_DP fill:#fcc,stroke:#888
       style R2_DP fill:#fcc,stroke:#888
       style R3_DP fill:#fcc,stroke:#888

2. 逻辑集中式控制（Logically Centralized Control）：

   • 软件定义网络（Software-Defined Networking, SDN）采用的方式。
   • 一个远程的控制器负责计算整个网络的路由路径。
   • 控制器将计算好的转发表分发并安装到各个路由器中。
   • 路由器主要负责数据平面的转发，控制逻辑大大简化。

   graph TD
       Controller[远程控制器] -->|计算转发表| R1(路由器 1 转发表)
       Controller -->|计算转发表| R2(路由器 2 转发表)
       Controller -->|计算转发表| R3(路由器 3 转发表)
   
       R1 -- 控制器指令 --> R1_DP[数据平面]
       R2 -- 控制器指令 --> R2_DP[数据平面]
       R3 -- 控制器指令 --> R3_DP[数据平面]
   
       style Controller fill:#ccf,stroke:#888
       style R1 fill:#fcc,stroke:#888
       style R2 fill:#fcc,stroke:#888
       style R3 fill:#fcc,stroke:#888

本章主要关注传统的每路由器控制方式下的路由协议。

路由协议

路由协议的目标与概念

• 目标：在路由器网络中，为数据包确定从发送主机到接收主机的「好」路径（或称为路由 Route）。
• 路径（Path）：数据包从初始源主机到最终目的主机所经过的路由器序列。
• 「好」路径：通常指满足某些优化标准的路径，例如：
  • 最低成本（Least Cost）：路径上各链路成本之和最小。成本可以代表跳数、延迟、带宽的倒数或拥塞程度等。
  • 最快（Fastest）：通常指延迟最低。
  • 最低拥塞（Least Congested）。

路由：核心网络挑战

路由选择是网络领域的核心问题之一，其复杂性在于网络状态（如链路拥塞、节点故障）是动态变化的，且需要分布式地、高效地、准确地计算和维护路径信息。

网络图抽象：链路成本

为了运行路由算法，我们将网络抽象为一个图 $G = (N, E)$：

• $N$：节点的集合，代表「路由器」。
• $E$：边或链路的集合，代表「路由器之间的物理连接」。

链路成本（Link Cost）：为图中的每条边 $(a, b)$ 分配一个成本 $c(a, b)$，表示通过该直连链路传输数据的代价。

• 成本 $c(a, b)$ 可以由网络运营商定义，例如：
  • 固定为 1（此时最低成本路径即为跳数最少的路径）。
  • 与链路带宽成反比（高带宽链路成本低）。
  • 与链路拥塞程度相关（拥塞链路成本高）。
• 如果节点 $a$ 和 $b$ 之间没有直接链路，则 $c(a, b) = \infty$（除非 $a=b$，此时 $c(a, a) = 0$）。
• 路径成本：一条路径 $(x_1, x_2, \dots, x_p)$ 的成本是该路径上所有链路成本之和：$c(x_1, x_2) + c(x_2, x_3) + \dots + c(x_{p-1}, x_p)$。

示例：

• 节点集合 $N = \{u, v, w, x, y, z\}$
• 链路集合 $E = \{(u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)\}$
• 链路成本示例：$c(w, z) = 5, c(u, z) = \infty$（无直连链路）

路由算法分类

路由算法可以根据几个维度进行分类：

1. 全局 vs 分散式（Global vs Decentralized）：

   • 全局算法（Global Algorithm）：
     • 所有路由器拥有完整的网络拓扑和链路成本信息。
     • 在此基础上计算最优路径。
     • 代表：链路状态（Link State, LS）算法。
   • 分散式算法（Decentralized Algorithm）：
     • 路由器只知道与其直连邻居的链路成本，不知道整个网络拓扑。
     • 通过与邻居迭代地交换信息和计算，逐步汇聚到最优路径。
     • 代表：距离向量（Distance Vector, DV）算法。

2. 静态 vs 动态（Static vs Dynamic）：

   • 静态算法（Static Algorithm）：
     • 路由变化缓慢，通常是手动配置或不经常更新。
     • 不能适应网络拓扑或负载的实时变化。
   • 动态算法（Dynamic Algorithm）：
     • 路由会随着网络拓扑或链路成本的变化而改变。
     • 通过周期性更新或在链路成本变化时触发更新来实现。
     • 现代路由协议（如 LS、DV）都是动态的。

graph TD
    subgraph "信息范围"
        direction LR
        A[全局信息（LS）]
        B[分散信息（DV）]
    end
    subgraph "更新频率"
        direction TB
        C[静态（变化慢）]
        D[动态（变化快）]
    end

    style A fill:#ccf
    style B fill:#fcc
    style C fill:#cfc
    style D fill:#fcf

本章主要讨论两种动态路由算法：链路状态（LS）和距离向量（DV）。

链路状态（LS）路由算法

核心思想：每个节点（路由器）都学习到整个网络的拓扑结构和所有链路的成本，然后在本地独立计算到达所有其他节点的最短路径。

运作方式：

1. 发现邻居和链路成本：每个节点启动时，首先了解其直连邻居和到这些邻居的链路成本。
2. 链路状态广播（Link State Broadcast）：每个节点将其了解到的本地链路状态（即它的邻居和链路成本）打包成链路状态通告（Link State Advertisement, LSA），并广播（Flood）给网络中的所有其他节点。
   • 广播机制需要确保 LSA 可靠、高效地传递给所有节点，且不会无限循环。
3. 构建拓扑图：每个节点收集来自所有其他节点的 LSA，从而在本地构建出完整的网络拓扑图。
4. 最短路径计算：每个节点使用 Dijkstra 算法（或其他最短路径算法）在本地计算从自身出发到网络中所有其他节点的最短路径树。
5. 生成转发表：根据计算出的最短路径树，确定到达每个目的网络的下一跳，生成转发表。

LS 特点

• 全局信息：每个节点最终都拥有全局网络视图。
• 计算独立：最短路径计算在每个节点本地进行。
• 广播开销：需要广播 LSA，可能产生较大网络开销，尤其是在网络变化频繁时。
• 收敛性：一旦所有节点收到最新的 LSA，计算出的路径是一致的。

Dijkstra 算法

Dijkstra 算法是一种经典的单源最短路径算法，用于在所有链路成本均为非负的图中，计算从一个源节点到所有其他节点的最短路径。

算法思想：

• 维护一个已确定最短路径的节点集合 $N'$。
• 从源节点 $u$ 开始，初始时 $N' = \{u\}$。
• 迭代地选择不在 $N'$ 中但距离源节点 $u$ 当前估计成本最低的节点 $w$，将其加入 $N'$。
• 对于新加入 $N'$ 的节点 $w$，更新其所有邻居 $v$（且 $v \notin N'$）到源节点 $u$ 的距离估计：如果通过 $w$ 到达 $v$ 的路径比当前已知的路径更短，则更新 $v$ 的距离估计和前驱节点。
• 重复此过程，直到所有节点都加入 $N'$。

符号定义：

• $u$：源节点（计算最短路径的起点）。
• $c(x, y)$：节点 $x$ 到节点 $y$ 的直连链路成本（若不直连则为 $\infty$）。
• $D(v)$：从源节点 $u$ 到节点 $v$ 的当前已知最短路径成本的估计值。
• $p(v)$：从源节点 $u$ 到节点 $v$ 的当前最短路径上的前驱节点（Predecessor Node）。
• $N'$：已确定其到源节点 $u$ 的最短路径的节点集合。

Dijkstra 算法执行追踪表（源节点 $u$）

步骤	$N'$	被选节点	$D(u), p(u)$	$D(v), p(v)$	$D(x), p(x)$	$D(y), p(y)$	$D(w), p(w)$	$D(z), p(z)$	日志（更新基于 Chosen 节点）
0	$\{u\}$	$u$	(0, -)	$(2, u)$	$(1, u)$	$(\infty, -)$	$(5, u)$	$(\infty, -)$	初始化。更新 $u$ 的邻居 $v, x, w$。
1	$\{u, x\}$	$x$	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(4, x)$	$(\infty, -)$	选择 $x$（成本 1 最小）。更新 $y$: $1+c(x,y)=1+1=2$; 更新 $w$: $1+c(x,w)=1+3=4$。
2	$\{u, x, v\}$	$v$	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(4, x)$	$(\infty, -)$	选择 $v$（成本 2 最小，与 $y$ 并列，选 $v$）。检查 $w$: $2+c(v,w)=2+3=5 > 4$，不更新。
3	$\{u, x, v, y\}$	$y$	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(3, y)$	$(4, y)$	选择 $y$（成本 2 最小）。更新 $w$: $2+c(y,w)=2+1=3 < 4$; 更新 $z$: $2+c(y,z)=2+2=4 < \infty$。
4	$\{u, x, v, y, w\}$	$w$	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(3, y)$	$(4, y)$	选择 $w$（成本 3 最小）。检查 $z$: $3+c(w,z)=3+5=8 > 4$，不更新。
5	$\{u, x, v, y, w, z\}$	$z$	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(3, y)$	$(4, y)$	选择 $z$（成本 4 最小）。无未访问邻居。
End	$\{u, x, v, y, w, z\}$	-	$(0, -)$	$(2, u)$	$(1, u)$	$(2, x)$	$(3, y)$	$(4, y)$	所有节点已加入 $N'$，算法结束。

说明:

• 每一行代表一次迭代。
• 「被选节点」列显示该迭代中被选入 $N'$ 的节点（因为它具有当前最小的 $D$ 值）。
• $(D(\cdot), p(\cdot))$ 列显示了在该步骤结束时，每个节点当前的成本估计值和前驱节点。加粗的项表示该节点在本步骤被最终确定最短路径。
• 「日志」列解释了选择该节点的原因以及基于该节点进行的距离更新。

最终结果：

• 最短路径成本：$D(v)=2, D(x)=1, D(y)=2, D(w)=3, D(z)=4$。
• 最短路径树（通过前驱节点 $p(v)$ 构建）：
  • $u \to v$
  • $u \to x$
  • $u \to x \to y$
  • $u \to x \to y \to w$
  • $u \to x \to y \to z$

节点 $u$ 的转发表：

目的节点	下一跳路由器
v	v
x	x
y	x
w	x
z	x

转发表生成

转发表的下一跳是沿着最短路径树从源节点出发的第一跳。例如，到 $w$ 的最短路径是 $u \to x \to y \to w$，从 $u$ 出发的第一跳是 $x$，所以到 $w$ 的下一跳是 $x$。

Dijkstra 算法复杂度：

• 算法复杂度：
  • 简单实现（每次查找最小值扫描所有节点）：$O(n^2)$，其中 $n$ 是节点数。
  • 使用二叉堆或斐波那契堆优化查找最小值：$O(E + n \log n)$（使用斐波那契堆理论上更好，但实践中常数因子较大），其中 $E$ 是边数。
• 消息复杂度（指 LS 算法整体）：
  • 每个节点广播其 LSA。如果网络稳定，广播次数有限。
  • 每次广播 LSA 可能需要 $O(E)$ 条消息（使用受控洪泛）。
  • 在最坏情况下（例如，链路成本频繁变化），消息复杂度可能较高。课件中提到的 $O(n^2)$ 可能是指一种简化的分析，即每个节点向其他 $n-1$ 个节点发送信息，且信息可能跨越 $O(n)$ 条链路。

Dijkstra 算法可能的问题：震荡（Oscillations）

• 如果链路成本依赖于该链路上承载的流量（例如，成本随拥塞程度增加），则可能发生「路由震荡」。
• 场景：多条路径根据当前流量计算成本，所有路由器同时选择当前最优路径，导致流量全部涌向该路径，使其成本升高；下一轮计算时，原路径成本变高，流量又涌向其他路径，如此反复。
• 流量在两条或多条路径之间来回摆动，无法稳定。
• 解决方法：
  • 确保并非所有路由器同时重新计算路由。
  • 设计不那么敏感的成本函数。
  • 使用多路径路由（Multipath Routing）将流量分散到多条路径。

距离向量（DV）路由算法

核心思想：每个节点维护一个到网络中所有其他节点的距离（成本）向量，并周期性地与其「邻居」交换这个向量。节点根据从邻居收到的距离向量和到邻居的链路成本，更新自己的距离向量。

基于 Bellman-Ford 方程：令 $D_x(y)$ 为从节点 $x$ 到节点 $y$ 的已知最低成本路径的成本。Bellman-Ford 方程指出：

$$D_x(y) = \min_{v} \{ c(x, v) + D_v(y) \}$$

其中，$v$ 是 $x$ 的邻居。

含义：从 $x$ 到 $y$ 的最短路径成本，等于「先走一步到邻居 $v$ 的成本 $c(x, v)$」加上「从邻居 $v$ 到 $y$ 的已知最短路径成本 $D_v(y)$」之和，并在所有邻居 $v$ 中取最小值。

DV 算法运作方式：

1. 初始化：每个节点 $x$ 初始化其距离向量 $D_x = [D_x(y_1), D_x(y_2), \dots]$。对于邻居 $v$，$D_x(v) = c(x, v)$；对于非邻居 $y$，$D_x(y) = \infty$；$D_x(x) = 0$。
2. 周期性/触发式交换：每个节点 $x$ 将其当前的距离向量 $D_x$ 发送给所有邻居。
3. 更新距离向量：当节点 $x$ 收到来自任何邻居 $v$ 的新距离向量 $D_v$ 时，它使用 Bellman-Ford 方程为网络中的每个目的节点 $y$ 重新计算 $D_x(y)$：
   $D_x(y) \leftarrow \min_{v} \{ c(x, v) + D_v(y) \}$
4. 通知邻居：如果节点 $x$ 的距离向量 $D_x$ 因为步骤 3 的计算而发生了改变，则将更新后的 $D_x$ 发送给所有邻居。
5. 重复：持续进行步骤 3 和 4。

具体流程

距离向量（Distance Vector, DV）算法与 Dijkstra 算法不同，DV 算法是一种分布式算法，每个节点只与它的「直接邻居」交换信息，并基于邻居告知的信息和自己到邻居的成本来更新自己的路径估计。

其核心是贝尔曼-福特（Bellman-Ford）方程。对于一个节点 $x$ 来说，它到目的节点 $y$ 的最短路径成本估计 $D_x(y)$ 是通过其所有邻居 $v$ 计算得出的：

$$D_x(y) = \min_{v} \{ c(x, v) + D_v(y) \}$$

这里

• $c(x, v)$ 是节点 $x$ 到其邻居 $v$ 的链路成本
• $D_v(y)$ 是邻居 $v$ 当前告知 $x$ 的它自己到 $y$ 的最短路径成本估计
  • 节点 $x$ 会选择那个使得 $c(x, v) + D_v(y)$ 最小的邻居 $v$ 作为到达 $y$ 的下一跳

DV 算法是迭代和异步的。节点会周期性地或在成本变化时，将其自身的距离向量（即它到所有其他节点的当前成本估计列表）发送给它的所有邻居。下面是这个过程逐步进行的流程，重点关注节点 $u$ 的视角，以及其他节点信息如何影响 $u$。

符号:

• $D_x = [D_x(u), D_x(v), D_x(w), D_x(x), D_x(y), D_x(z)]$ 是节点 $x$ 的距离向量。
• 初始时，每个节点只知道到自己的距离（0）和到直接邻居的距离（链路成本），到其他所有节点的距离为 $\infty$。

0. 初始化 (Time $t_0$)：每个节点初始化自己的距离向量

   • $D_u = [0, 2, 5, 1, \infty, \infty]$（知道 $u, v, w, x$）
   • $D_v = [2, 0, 3, 2, \infty, \infty]$（知道 $u, v, w, x$）
   • $D_w = [5, 3, 0, 3, 1, 5]$（知道 $u, v, w, x, y, z$）
   • $D_x = [1, 2, 3, 0, 1, \infty]$（知道 $u, v, w, x, y$）
   • $D_y = [\infty, \infty, 1, 1, 0, 2]$（知道 $w, x, y, z$）
   • $D_z = [\infty, \infty, 5, \infty, 2, 0]$（知道 $w, y, z$）

1. 第 1 轮信息交换与计算（Time $t_1$）：

   1. 信息交换：所有节点将自己的初始 DV 发送给它们的邻居。
   2. 节点 $u$ 的计算：节点 $u$ 收到了来自邻居 $v, w, x$ 的初始 DV。现在 $u$ 使用 Bellman-Ford 方程重新计算自己的 DV：
      • $D_u(u) = 0$（始终为 0）
      • $\begin{aligned} D_u(v) &= \min \{ c(u,v) + D_v(v), c(u,w) + D_w(v), c(u,x) + D_x(v) \} \\ &= \min \{ 2 + 0, 5 + 3, 1 + 2 \} \\ &= 2 \end{aligned}$
        • 下一跳是 $v$
      • $\begin{aligned} D_u(w) &= \min \{ c(u,v) + D_v(w), c(u,w) + D_w(w), c(u,x) + D_x(w) \} \\ &= \min \{ 2 + 3, 5 + 0, 1 + 3 \} \\ &= 4 \end{aligned}$
        • 下一跳是 $x$，因为发现通过 $x$ 到 $w$ 更近了。
      • $\begin{aligned} D_u(x) &= \min \{ c(u,v) + D_v(x), c(u,w) + D_w(x), c(u,x) + D_x(x) \} \\ &= \min \{ 2 + 2, 5 + 3, 1 + 0 \} \\ &= 1 \end{aligned}$
        • 下一跳是 $x$
      • $\begin{aligned} D_u(y) &= \min \{ c(u,v) + D_v(y), c(u,w) + D_w(y), c(u,x) + D_x(y) \} \\ &= \min \{ 2 + \infty, 5 + 1, 1 + 1 \} \\ &= 2 \end{aligned}$
        • 下一跳是 $x$，发现了到 $y$ 的路径。
      • $\begin{aligned} D_u(z) &= \min \{ c(u,v) + D_v(z), c(u,w) + D_w(z), c(u,x) + D_x(z) \} \\ &= \min \{ 2 + \infty, 5 + 5, 1 + \infty \} \\ &= 10 \end{aligned}$
        • 下一跳是 $w$，发现了到 $z$ 的路径，虽然不是最优的。
   3. 节点 $u$ 更新后的 DV（待发送）：$D_u = [0, 2, 4, 1, 2, 10]$

注意：在同一轮 $t_1$，所有其他节点（$v, w, x, y, z$）也在执行类似计算，基于它们收到的邻居的 初始 DV。

2. 第 2 轮信息交换与计算（Time $t_2$）

   1. 信息交换：所有节点将它们在 $t_1$ 计算出的 新 DV 发送给邻居。
      • 例如，节点 $u$ 发送 $[0, 2, 4, 1, 2, 10]$。节点 $x$ 可能也更新了自己的 DV（比如它从 $y$ 那里得知了到 $z$ 的路径），并发送给 $u$。
   2. 节点 $u$ 的计算：$u$ 收到来自 $v, w, x$ 在 $t_1$ 计算出的新 DV。
      • 假设 $x$ 在 $t_1$ 计算出 $D_x(z) = D_x(y) + c(y,z) = 1 + 2 = 3$（因为它从 $y$ 收到了 $D_y(z)=2$）。现在 $u$ 重新计算：
        • …（对 $v, w, x, y$ 的计算可能不变，也可能因为邻居的更新而改变，但在这个例子中，前几项可能已经稳定）
        • $D_u(z) = \min \{ c(u,v) + D_v(z)_{\text{new}}, c(u,w) + D_w(z)_{\text{new}}, c(u,x) + D_x(z)_{\text{new}} \}$
        • 假设 $v$ 和 $w$ 的 $D(z)$ 更新不如 $x$ 快，$u$ 的计算可能像这样：
          • $\begin{aligned} D_u(z) &= \min \{ 2 + \dots, 5 + \dots, 1 + 3 \} \\ &= 4 \end{aligned}$
        • 下一跳是 $x$，发现了 $u \to x \to y \to z$ 这条更短的路径。
   3. 节点 $u$ 更新后的 DV (待发送)：$D_u = [0, 2, 4, 1, 2, 4]$ (这里 $D_u(w)$ 可能也因为 $x$ 或 $y$ 的更新而变为 3，我们简化一下流程，假设 $z$ 先更新了)

3. 后续迭代（Time $t_3, t_4, ...$）

   • 这个过程不断重复：交换 DV $\to$ 重新计算 $\to$ 更新 DV。
   • 信息（尤其是关于更短路径的信息）会像波浪一样在网络中传播。
   • 最终，如果没有链路成本变化，算法会收敛。也就是说，不再有节点的 DV 在计算后发生变化，此时所有节点都找到了最短路径。

收敛后，节点 $u$ 的距离向量会是：$D_u = [0, 2, 3, 1, 2, 4]$

同时，$u$ 也记录了到达每个目的地的最佳下一跳邻居：

• 到 $v$: 下一跳 $v$（成本 2）
• 到 $w$: 下一跳 $x$（因为 $c(u,x) + D_x(w)_{\text{final}} = 1 + 2 = 3$）
• 到 $x$: 下一跳 $x$（成本 1）
• 到 $y$: 下一跳 $x$（因为 $c(u,x) + D_x(y)_{\text{final}} = 1 + 1 = 2$）
• 到 $z$: 下一跳 $x$（因为 $c(u,x) + D_x(z)_{\text{final}} = 1 + 3 = 4$）

节点 $u$ 的最终转发表:

目的节点	成本	下一跳路由器
v	2	v
w	3	x
x	1	x
y	2	x
z	4	x

DV 算法特点：

• 迭代（Iterative）：节点通过重复计算和交换信息逐步逼近最终结果。
• 异步（Asynchronous）：节点不必同步操作，可以独立响应本地链路成本变化或收到的邻居消息。
• 分布式（Distributed）：计算分散在各个节点上，没有中心控制点。
• 自停止（Self-stopping）：当没有节点再更新其距离向量时，算法收敛，信息交换停止。

DV 算法示例：

• 状态信息扩散（State Information Diffusion）：

  • DV 算法通过邻居间迭代的通信和计算，逐步将网络状态（特别是链路成本变化）信息扩散到整个网络。
  • 
  • 如上图所示，一个节点（如 c）的状态信息在 $t=0$ 时只影响自身；在 $t=1$ 时，通过一次距离向量交换，影响到其 1 跳邻居（如 b）；在 $t=2$ 时，影响到 2 跳邻居（如 a, e），以此类推。
  • 信息传播的速度取决于网络的拓扑结构和更新频率。

• 处理链路成本变化：DV 算法是动态的，能够适应链路成本的变化。然而，其收敛速度对「好消息」和「坏消息」的处理方式不同。

  • 好消息传播快（Good News Travels Fast）：当一条链路成本降低时，信息会迅速传播。

    • 示例：
      • 
      • 初始：Y 到 X 成本为 4，Z 到 X 成本为 50（直连），Y 到 Z 成本为 1。Z 通过 Y 到 X 的成本为 $1+4=5$。Z 选择经 Y 到 X。
      • $t_0$：Y 检测到 Y 到 X 的链路成本从 4 降为 1。Y 更新 $D_Y(X)=1$，并通知邻居 Z。
      • $t_1$：Z 收到 Y 的更新。Z 重新计算到 X 的成本：$\min \{ c(Z, Y) + D_Y(X), c(Z, X) \} = \min \{ 1 + 1, 50 \} = 2$。Z 更新 $D_Z(X)=2$（下一跳为 Y）。由于 $D_Z$ 改变，Z 通知邻居 Y。
      • $t_2$：Y 收到 Z 的更新。Y 重新计算到 X 的成本（虽然不太可能改变，但按协议执行）：$\min \{ c(Y, X), c(Y, Z) + D_Z(X) \} = \min \{ 1, 1 + 2 \} = 1$。Y 的 $D_Y(X)$ 未改变，无需通知邻居。
      • 算法快速收敛到新的最短路径。

    sequenceDiagram
        participant Y
        participant Z
        Note over Y, Z: 初始 D_Y(X)=4, D_Z(X)=5 (via Y)
        Y->>Y: 检测到 c(Y, X) 变为 1，更新 D_Y(X)=1
        Y->>Z: 更新 DV：D_Y(X)=1 (t0)
        Z->>Z: 收到更新，计算 D_Z(X) = min(1+1, 50) = 2
        Z->>Y: 更新 DV：D_Z(X)=2 (t1)
        Y->>Y: 收到更新，计算 D_Y(X) = min(1, 1+2) = 1（无变化）(t2)
        Note over Y, Z: 快速收敛

  • 坏消息传播慢（Bad News Travels Slow）：当一条链路成本显著增加或链路失效时，可能出现「计数到无穷」问题，导致收敛缓慢。

    • 问题根源：节点可能基于邻居过时的、不准确的（过于乐观的）距离信息做出错误的路由决策，形成路由环路（Routing Loop）。
    • 示例：
      • 
      • 初始：Y 到 X 成本为 4，Z 到 X 成本为 50，Y 到 Z 成本为 1。Z 通过 Y 到 X 的成本为 5。
      • 变化：Y 到 X 的链路成本从 4 变为 60。
      • Y 的视角：Y 检测到 $c(Y, X)=60$。但 Y 记得 Z 曾告诉它 $D_Z(X)=5$（通过 Y）。Y 错误地认为可以通过 Z 到达 X，成本为 $c(Y, Z) + D_Z(X) = 1 + 5 = 6$。Y 更新 $D_Y(X)=6$（下一跳为 Z），并通知 Z。
      • Z 的视角：Z 收到 Y 的更新 $D_Y(X)=6$。Z 重新计算到 X 的成本：$\min \{ c(Z, Y) + D_Y(X), c(Z, X) \} = \min \{ 1 + 6, 50 \} = 7$。Z 更新 $D_Z(X)=7$（下一跳为 Y），并通知 Y。
      • Y 的视角：Y 收到 Z 的更新 $D_Z(X)=7$。Y 重新计算到 X 的成本：$\min \{ c(Y, X), c(Y, Z) + D_Z(X) \} = \min \{ 60, 1 + 7 \} = 8$。Y 更新 $D_Y(X)=8$（下一跳为 Z），并通知 Z。
      • Z 的视角：Z 收到 Y 的更新 $D_Y(X)=8$。Z 重新计算到 X 的成本：$\min \{ c(Z, Y) + D_Y(X), c(Z, X) \} = \min \{ 1 + 8, 50 \} = 9$。Z 更新 $D_Z(X)=9$（下一跳为 Y），并通知 Y。
      • …这个过程会持续下去，Y 和 Z 相互增加到 X 的成本，直到成本达到 50，Z 最终选择直接链路 $c(Z, X)$，然后 Y 才能选择正确的路径（或者直到成本达到某个无穷大值）。这个收敛过程非常缓慢。

    sequenceDiagram
        participant Y
        participant Z
        Note over Y, Z: 初始 D_Y(X)=4, D_Z(X)=5 (via Y)
        Y->>Y: 检测到 c(Y, X) 变为 60
        Y->>Y: 计算 D_Y(X) = min(60, 1+5) = 6（错误地认为 Z 仍有 cost 5 的路径）
        Y->>Z: 更新 DV：D_Y(X)=6
        Z->>Z: 收到更新, 计算 D_Z(X) = min(1+6, 50) = 7
        Z->>Y: 更新 DV：D_Z(X)=7
        Y->>Y: 收到更新, 计算 D_Y(X) = min(60, 1+7) = 8
        Y->>Z: 更新 DV：D_Y(X)=8
        Z->>Z: 收到更新, 计算 D_Z(X) = min(1+8, 50) = 9
        Z->>Y: 更新 DV：D_Z(X)=9
        Note over Y, Z: 成本缓慢增加，形成环路…

  • 计数到无穷问题的解决方案：

    • 定义无穷大：设置一个成本阈值，超过该阈值即视为不可达。
    • 水平分割（Split Horizon）：节点不向其下一跳邻居通告到达某个目的地的路由信息。即，如果 Y 通过 Z 到达 X，则 Y 不会向 Z 通告它能到达 X。这可以防止简单的两节点环路。
    • 毒性逆转（Poisoned Reverse）：如果 Y 通过 Z 到达 X，则 Y 向 Z 通告它到达 X 的成本为无穷大。这比水平分割更强硬，能更快地打破某些环路。
    • 注意：即使有这些技术，复杂的环路问题有时仍可能发生。

LS 与 DV 算法比较

特性	链路状态（LS）算法（如 OSPF）	距离向量（DV）算法（如 RIP, BGP 路径向量）
消息复杂度	广播 LSA，消息量可能较大 $O(n^2)$ 或 $O(E)$	只与邻居交换距离向量，消息量较小
计算复杂度	Dijkstra 算法 $O(n^2)$ 或 $O(E+n\log n)$	Bellman-Ford 迭代计算，相对简单
收敛速度	较快，但可能有震荡问题	可能较慢，尤其遇到「坏消息」（计数到无穷问题）
健壮性	节点独立计算，不易受邻居错误影响；错误 LSA 可能误导全局	错误距离向量会传播，影响邻居；可能导致路由环路和黑洞（Black-holing）
所需信息	需要全局拓扑信息	只需要邻居信息
实现复杂性	相对复杂（LSA 广播、数据库同步、Dijkstra）	相对简单
路由环路	不易产生（基于全局一致视图计算）	可能产生（尤其在收敛过程中）

!!! summary 总结
- LS：信息全面，计算准确，收敛较快，但开销和复杂性较高。适用于规模适中、需要快速收敛和较好稳定性的网络（如单个 ISP 内部）。
- DV：实现简单，开销较小，但收敛慢，易出环路问题。适用于小型网络，或作为大型网络（如互联网）中域间路由协议（如 BGP）的基础（BGP 使用路径向量，是 DV 的变种，增加了环路检测机制）。

ISP 内部路由：OSPF

OSPF（Open Shortest Path First）是互联网中广泛使用的内部网关协议（Interior Gateway Protocol, IGP）之一，用于在单个自治系统（Autonomous System, AS）内部进行路由选择。

OSPF 主要特点

• 开放标准：协议规范公开可用（RFC 2328）。
• 链路状态算法：
  • 使用 Dijkstra 算法计算最短路径。
  • 每个路由器广播链路状态通告，描述其本地连接状态。LSA 直接封装在 IP 数据包中传输（协议号 89），而不是 TCP 或 UDP。
  • 每个路由器维护一个完整的 AS 拓扑数据库（LSDB）。
• 支持多种链路成本度量：管理员可以配置不同的成本度量，如带宽、延迟等。默认通常基于带宽。
• 安全性：支持对 OSPF 消息进行认证（如 MD5），防止恶意或错误的路由信息注入。
• 支持附加功能：
  • 多路径路由：允许将流量分摊到多条成本相同的路径上。
  • 层次化路由：支持将大型 AS 划分为多个区域（Area），以提高可扩展性。

OSPF 层次化结构

为了解决大型 AS 中 LS 算法带来的扩展性问题（LSDB 过大、LSA 洪泛开销高、Dijkstra 计算频繁），OSPF 引入了两级层次结构：

1. 区域（Area）：将 AS 内部的路由器划分为若干个区域。
2. 骨干区域（Backbone Area，Area 0）：所有区域都必须直接或间接连接到骨干区域。骨干区域负责在不同区域之间传递路由信息。

路由器角色：

• 内部路由器：所有接口都在同一个区域内。
• 区域边界路由器（Area Border Router, ABR）：连接一个或多个区域到骨干区域。负责汇总其所连接区域的地址信息，并向骨干区域通告；同时将骨干区域和其他区域的路由信息传播到本地区域。
• 骨干路由器（Backbone Router）：至少有一个接口连接到骨干区域（可以是 ABR 或骨干区域内的内部路由器）。
• 自治系统边界路由器（AS Boundary Router, ASBR）：连接本 AS 到其他 AS 的路由器（运行 OSPF 和其他外部网关协议如 BGP）。负责将外部路由注入到 OSPF 网络中。

层次化路由的优势：

• 减少 LSA 洪泛范围：大部分 LSA 只在本区域内洪泛，减少了网络开销。
• 缩小 LSDB 规模：每个路由器只需要维护其所在区域的详细拓扑和骨干区域的拓扑信息，以及到其他区域的汇总路由。
• 降低计算复杂度：Dijkstra 算法只在区域内部运行，计算量减小。
• 提高稳定性：一个区域内的拓扑变化不会影响其他区域的路由计算（除非是影响到区域间路由）。

graph TD
    subgraph AS
        direction LR
        subgraph Area 1
            direction TB
            R1_1(内部路由) --- ABR1
            R1_2(内部路由) --- ABR1
        end
        subgraph "Area 0 (Backbone)"
            direction LR
            ABR1 --- BB_R1(骨干路由) --- ABR2
            BB_R1 --- ASBR(AS 边界路由)
        end
        subgraph Area 2
            direction TB
            ABR2 --- R2_1(内部路由)
            ABR2 --- R2_2(内部路由)
        end
    end
    ASBR --- External(其他 AS)

    style ABR1 fill:#ccf,stroke:#888
    style ABR2 fill:#ccf,stroke:#888
    style ASBR fill:#fcc,stroke:#888
    style BB_R1 fill:#cfc,stroke:#888

OSPF 运作简述

• 区域内路由：路由器只知道本区域的详细拓扑，运行 Dijkstra 计算区域内最短路径。
• 区域间路由：通过 ABR 获知到其他区域的路径（通常是汇总路由），ABR 会告知到达某个区域需要经过哪个骨干路由器。路由器选择到达相应 ABR 的区域内最短路径。
• 外部路由：通过 ASBR 获知到 AS 外部目的地的路径。路由器选择到达相应 ASBR 的最短路径（可能是区域内或区域间路径）。

OSPF 通过其链路状态机制和层次化设计，在单个 AS 内部提供了高效、可靠且可扩展的路由解决方案。

域间路由：BGP

互联网由数以万计的自治系统组成。每个 AS 内部使用「域内路由协议」，如 OSPF 或 RIP，来管理内部路由。然而，要在这些 AS 之间进行路由选择，则需要域间路由协议（Exterior Gateway Protocol, EGP）。

目前互联网上实际使用的域间路由协议是边界网关协议（Border Gateway Protocol, BGP）。

BGP 基础

• 事实标准：BGP 是互联网上用于 AS 之间交换路由信息的事实标准，被称为「将互联网粘合在一起的胶水」。
• 核心功能：允许一个 AS 向互联网的其他部分通告：
  1. 它的存在（即它拥有的 IP 地址前缀）。
  2. 它可以到达哪些目的网络（以及如何到达）。
• BGP 的目标：为每个 AS 提供一种机制来：
  1. 从相邻 AS 获取关于目的网络可达性的信息。
  2. 基于可达性信息和自身的路由策略确定到达其他网络的最佳路由。
  3. 将可达性信息传播给 AS 内部的所有路由器。
  4. 向相邻 AS 通告自己（以及通过自己可达的）目的网络的可达性信息。

eBGP 与 iBGP

BGP 连接分为两种类型：

1. 外部 BGP（External BGP, eBGP）：用于连接位于「不同」AS 中的 BGP 路由器（通常是边界路由器）。通过 eBGP 会话，AS 之间交换路由信息。
2. 内部 BGP（Internal BGP, iBGP）：用于连接位于「同一个」AS 内部的 BGP 路由器。iBGP 的主要目的是将通过 eBGP 从外部学到的路由信息，传播给 AS 内部的其他 BGP 路由器（包括其他边界路由器），确保 AS 内部对外部路由有一致的视图。

graph LR
    subgraph AS1
        direction TB
        R1a --- R1c
        R1b --- R1c
        R1d --- R1c
        R1a --- R1d
        R1b --- R1a
        R1d --- R1b
    end
    subgraph AS2
        direction TB
        R2a --- R2c
        R2b --- R2c
        R2d --- R2c
        R2a --- R2d
        R2b --- R2a
        R2d --- R2b
    end
    subgraph AS3
        direction TB
        R3a --- R3c
        R3b --- R3c
        R3d --- R3c
        R3a --- R3d
        R3b --- R3a
        R3d --- R3b
    end

    R1c -- eBGP --> R2a
    R2c -- eBGP --> R3a

    linkStyle 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 stroke-dasharray 5 5, stroke-width:1px;
    linkStyle 16,17 stroke-width:2px;

    style R1c fill:#f9f,stroke:#333,stroke-width:2px
    style R2a fill:#f9f,stroke:#333,stroke-width:2px
    style R2c fill:#f9f,stroke:#333,stroke-width:2px
    style R3a fill:#f9f,stroke:#333,stroke-width:2px

网关路由器

通常，AS 的网关路由器或边界路由器会同时运行 eBGP（与外部 AS 对等体）和 iBGP（与内部 AS 对等体）。iBGP 连接通常是逻辑上的全连接或通过路由反射器优化，确保外部路由信息能在 AS 内部有效传播。

BGP 会话

两个 BGP 路由器（称为「对等体」Peers）通过建立一个半永久的 TCP 连接（端口 179）来交换 BGP 报文。这种连接被称为 BGP 会话。

在会话期间，对等体之间相互通告到达不同目的网络前缀的路径。

路径向量协议

BGP 是一种「路径向量协议」。与距离向量协议类似，它也通过邻居交换路由信息。但与 DV 不同的是，BGP 报文中携带的不仅仅是距离（成本），而是到达目标前缀所必须经过的完整 AS 路径。

例如，当 AS3 的网关路由器 3a 向 AS2 的网关路由器 2c 通告它能到达前缀 X 时，它发送的路径信息是 (AS3, X)。这个信息意味着 AS3 承诺会将发往 X 的数据包进行转发。

BGP 路径属性与路由信息

BGP 路由通告的核心内容是「网络前缀 + 路径属性」。

• 前缀：被通告的目的网络地址范围（例如 138.16.68.0/22）。
• 属性：描述路径特征的信息。BGP 有多种属性，其中两个最重要的属性是：
  1. AS-PATH：包含该路由通告信息所经过的 AS 序列。
     • 当一个路由通告从一个 AS 传递到另一个 AS 时（通过 eBGP），发送方 AS 会将自己的 ASN 添加到 AS-PATH 列表的最前面。
     • 作用：
       • 环路检测：如果一个路由器收到一条 BGP 路由通告，且在其 AS-PATH 属性中发现了自己的 ASN，则说明存在路由环路，该路由将被丢弃。
       • 策略依据：网络管理员可以根据 AS-PATH 的内容（如长度、包含的特定 AS）来制定路由策略。
  2. NEXT-HOP：指示到达该 BGP 路由通告中指定前缀的「下一跳」路由器的 IP 地址。
     • 对于 eBGP 会话，NEXT-HOP 通常是发送该通告的邻居路由器的 IP 地址。
     • 当路由信息通过 iBGP 在 AS 内部传播时，NEXT-HOP 属性通常保持不变。这意味着 AS 内部的路由器需要通过 IGP（如 OSPF）找到到达这个 NEXT-HOP 地址的内部路径。

策略路由

与 IGP（如 OSPF）主要关注寻找「最短」路径不同，BGP 的核心在于策略。AS 之间的路由决策往往基于经济、政治或商业关系，而不仅仅是技术指标。

• 入口策略：当一个网关路由器收到来自邻居 AS 的路由通告时，它会根据本地策略决定是否接受（学习）这条路径。例如，一个 AS 可能配置策略「从不通过 AS Y 路由流量」。
• 出口策略：AS 策略也决定了是否以及向哪些邻居 AS 通告某条路径。例如，一个 ISP 可能只向其客户 AS 通告完整的互联网路由，但只向其对等 ISP 通告到达自己客户的路由。

BGP 路径选择、通告与传播

1. 路径学习：一个网关路由器可能从多个邻居（通过 eBGP 或 iBGP）学习到到达同一个目的前缀的多条路径。

   • 例如，在下图中，AS1 的路由器 1c 可能从 2a 学到路径 (AS2, AS3, X)，也可能从 3a 直接学到路径 (AS3, X)。

   graph LR
       subgraph AS1
           R1c
       end
       subgraph AS2
           R2a -- AS2, AS3, X --> R1c
       end
       subgraph AS3
           R3a -- AS3, X --> R1c
           R3a -- AS3, X --> R2c(AS2 Router 2c)
           R2c -- iBGP: AS3, X --> R2a
       end
       subgraph Destination
          X
       end
      R3a --> X
   
      style R1c fill:#f9f
      style R2a fill:#ccf
      style R3a fill:#cfc

2. 路径选择过程：当存在多条到达同一前缀的路径时，BGP 路由器会根据一套复杂的规则来选择「唯一」的最佳路径。这个过程大致按优先级顺序进行：

   1. 本地偏好值：选择具有最高本地偏好值的路径。这是一个 AS 内部的属性，用于指示离开 AS 的首选出口点（策略决定）。
   2. 最短 AS-PATH：选择 AS-PATH 属性最短的路径（经过的 AS 数量最少）。
   3. 最近的 NEXT-HOP 路由器：如果 AS-PATH 长度相同，选择到达 NEXT-HOP 地址的域内（IGP）成本最低的路径。这被称为热土豆路由。
   4. 附加标准：如果以上步骤仍无法区分，还会使用 MED(Multi-Exit Discriminator)、eBGP 优先于 iBGP、邻居路由器 ID 等附加规则。

热土豆路由（Hot Potato Routing）

假设 AS2 内部路由器 2d 通过 iBGP 从 2a 和 2c 都学到了到达 X 的路径（假设 AS-PATH 长度和 Local Pref 都相同）。

2a 的 NEXT-HOP 是 R1c 的 IP，2c 的 NEXT-HOP 是 R3a 的 IP。2d 会使用其内部的 IGP (如 OSPF) 计算到达 R1c 和 R3a 的内部路径成本。

如果 2d 到达 R2a 的 OSPF 成本（例如 201）低于到达 R2c 的 OSPF 成本（例如 263），即使通过 R2a 的 AS-PATH 可能更长（例如 AS1 $\to$ AS3 $\to$ X vs AS3 $\to$ X），2d 也会选择通过 R2a 作为其出口网关。

核心思想：尽快将数据包扔出自己的 AS，将路由的负担交给下一个 AS，就像扔一个烫手的土豆一样。它优先考虑本 AS 内部的成本，而不是端到端的全局成本或 AS 跳数。

graph LR

subgraph AS2 direction TB R2a -- iBGP: Path via AS1 --> R2d R2c -- iBGP: Path via AS3 --> R2d R2d -- OSPF Cost 201 --> R2a R2d -- OSPF Cost 263 --> R2c end subgraph AS1 R1c end subgraph AS3 R3a end R2a -- eBGP --> R1c R2c -- eBGP --> R3a R1c -- ... --> X(Destination X) R3a -- ... --> X

    即使通过 R2a 的 AS-PATH 可能更长（例如 AS1 $\to$ AS3 $\to$ X vs AS3 $\to$ X），2d 也会选择通过 R2a 作为其出口网关。

3. 路由传播：

   • 当一个网关路由器（如 2c）通过 eBGP 从邻居（如 3a）学到一条路径 (AS3, X)，并且根据入口策略接受了它，它会使用 iBGP 将这条路径传播给 AS2 内部的所有其他 BGP 对等体（如 2a, 2d）。
   • 当内部路由器（如 2a）收到这条 iBGP 路径后，如果它的出口策略允许，它可能会通过 eBGP 将这条路径进一步通告给它的邻居 AS（如 AS1 的 1c）。此时，它会把自己的 ASN(AS2) 加入 AS-PATH，通告的路径变为 (AS2, AS3, X)。

4. 填充转发表：BGP 负责确定 AS 间的路由策略和路径，但最终数据包的转发依赖于每个路由器的数据平面转发表。

   • BGP 确定了到达某个外部前缀 X 的最佳路径及其 NEXT-HOP 地址。
   • AS 内部的路由器（如 1a, 1d）通过 iBGP 从网关（如 1c）学到「去往 X 的路径要经过 1c」。
   • 然后，这些内部路由器使用其 IGP（如 OSPF）计算到达网关 1c 的内部最短路径，并将对应的下一跳接口填入转发表。
   • 例如，如果 1d 通过 OSPF 计算出到达 1c 的最短路径需要从接口 1 发出，那么 1d 的转发表中，目的地址为 X 的条目的下一跳接口就是 1。

BGP 与 IGP 的协作

BGP 决定去哪里（哪个出口路由器/NEXT-HOP），而 IGP 决定怎么去（在 AS 内部如何到达那个出口路由器）。两者协同工作，才能完成端到端的路由。

BGP 策略实施示例

BGP 策略是其核心，以下是一些常见策略：

1. ISP 不为其他 ISP 传输过境流量：

   • 场景：ISP B 连接了客户网络 W 和 A，以及另一个 ISP C。B 只想处理往返于其客户的流量，不想免费为 A 和 C 之间的流量提供传输。
   • 策略：A 向 B 通告路径 Aw（A 可以到达 W）。B 接受此路径。但是，B 不会将这条路径 BAw 通告给 C。因为 C, A, W 都不是 B 的客户，为 C -> B -> A -> w 这样的流量提供服务对 B 没有收益。结果是 C 不会学习到通过 B 到达 W 的路径。

   graph LR
       direction TB
       subgraph "B 的策略"
           direction LR
           Learn_Aw[从 A 学习路径 Aw] --> Accept_Aw[接受路径 Aw]
           Accept_Aw --> No_Advertise_BAw{是否向 C 通告路径 BAw？}
           No_Advertise_BAw --否--> Stop1[停止]
       end
   
       subgraph " "
           W(客户 W) --- A(提供商 A)
           A --- B(提供商 B)
           A --- C(提供商 C)
           B --- X(提供商 X)
           C --- Y(提供商 Y)
       end
   
       style W fill:#ccf,stroke:#333,stroke-width:2px
       style X fill:#ccf,stroke:#333,stroke-width:2px
       style Y fill:#ccf,stroke:#333,stroke-width:2px

2. 多宿主客户的策略（Dual-homed Customer）：

   • 场景：网络 X 是一个客户，它同时连接到两个 ISP：B 和 C（双宿主）。X 不希望成为 B 和 C 之间流量的过境路径。
   • 策略：X 会向 B 和 C 通告自己的前缀 X。但是，当 X 从 C 收到一条到达某个目的地（如 Z）的路径 CZ 时，X 不会将这条路径 XCZ 通告给 B。反之亦然。这样可以防止 B 通过 X 向 C 发送流量。

   graph TD
       direction TB
       subgraph "X 的策略"
           direction LR
           Learn_CZ[从 C 学习路径 CZ] --> No_Advertise_XCZ{是否向 B 通告路径 XCZ？}
           No_Advertise_XCZ --否--> Stop2[停止]
           Learn_BY[从 B 学习路径 BY] --> No_Advertise_XBY{是否向 C 通告路径 XBY？}
           No_Advertise_XBY --否--> Stop3[停止]
       end
   
       subgraph " "
           B(提供商 B) --- X(客户 X)
           C(提供商 C) --- X
       end
   
       %% 样式设置
       style X fill:#ccf,stroke:#333,stroke-width:2px

域内路由 vs. 域间路由比较

特性	域内路由（Intra-AS, IGP）	域间路由（Inter-AS, EGP）
目标	性能优化（如最短路径、最低延迟）	策略实施（控制流量路径、商业关系）
规模	单个 AS 内部	全球互联网范围，连接不同 AS
策略	通常单一管理域，策略问题较少	核心是策略，不同 AS 有不同目标和约束
复杂性	相对简单（LS, DV 算法）	非常复杂（路径向量、大量属性、策略交互）
路由计算	基于链路成本	基于策略、AS-PATH、NEXT-HOP 等属性
关注点	如何最高效地在 AS 内部转发	数据包应该走哪条 AS 路径
例子	OSPF, RIP	BGP

SDN 控制平面

前面讨论了传统的、基于每路由器分布式控制的路由方式（如 OSPF, BGP）。下面回顾并深入探讨软件定义网络（SDN）所采用的逻辑集中式控制平面。

传统控制平面的局限

• 分布式管理复杂：在传统网络中，每个路由器的控制平面独立运行，配置、管理、排错分散且复杂，容易出现配置错误。
• 创新困难：路由器通常是「封闭」的，运行着厂商私有的操作系统和协议实现。引入新的网络功能或协议（如 OpenFlow 之前）非常困难。
• 流量工程受限：网络管理员对流量路径的控制能力有限，主要通过调整 IGP 的链路权重（如 OSPF cost）来间接影响路由，难以实现精细化、策略化的流量调度。例如：
  • 难以强制流量走非最短路径。
  • 难以实现基于流量类型的差异化路由。
  • 负载均衡能力有限。

SDN 架构回顾

SDN 的核心思想是将网络的控制平面（决定流量如何转发的「大脑」）与数据平面（实际执行转发的「肌肉」）分离。

• 数据平面：由快速、简单的网络设备（SDN 交换机）组成，根据流表（Flow Table）进行转发。这些设备通常使用通用硬件。
• 控制平面：由一个（逻辑上）集中的 SDN 控制器负责。控制器拥有全局网络视图，计算转发表（流表），并通过南向接口下发到数据平面的交换机。
• 网络应用：运行在控制器之上，实现各种网络功能（路由、负载均衡、防火墙、访问控制等），通过北向接口与控制器交互。

SDN 的优势

• 简化网络管理：集中式控制使得网络配置、监控和管理更加容易，减少了不一致性和错误。
• 增强流量工程能力：控制器拥有全局视图，可以根据应用需求、网络状态、策略等计算并下发精确的流规则，实现灵活、细粒度的流量控制。
• 促进创新：
  • 开放接口：标准化的南向接口（如 OpenFlow）和开放的北向接口使得开发新的网络应用和服务更加容易。
  • 解耦：控制逻辑与转发硬件解耦，允许独立发展和升级。

SDN 组件详解

SDN 控制器（网络操作系统）

SDN 控制器是 SDN 架构的核心，扮演着「网络操作系统」（NOS）的角色。其主要功能和组件包括：

1. 接口层（面向应用）：
   • 提供北向接口，通常是 RESTful API 或特定语言的库。
   • 向上层网络应用提供网络的抽象视图（如网络图、主机信息、设备能力）和控制能力（如安装流规则、获取统计信息）。
   • 应用开发者无需关心底层协议细节，只需调用 API 即可实现网络控制逻辑。
2. 网络范围状态管理：
   • 维护关于网络状态的全局信息，如：网络拓扑（链路状态）、交换机信息、主机信息、流表信息、统计数据等。
   • 这些信息通常存储在一个分布式数据库或状态管理系统中，以保证一致性、可扩展性和容错性。
3. 通信层（面向设备）：
   • 提供南向接口，如 OpenFlow、NETCONF 等。
   • 负责与数据平面的 SDN 交换机进行通信，包括：发现设备、获取设备能力、下发流规则、收集状态和统计信息等。

控制器的实现

虽然逻辑上是集中的，但为了性能、可扩展性和可靠性，SDN 控制器通常实现为分布式系统，由多个物理或虚拟机实例协同工作。

南向接口：OpenFlow 协议

OpenFlow 是目前最常用和标准化的 SDN 南向接口协议。

• 作用：定义了 SDN 控制器与 OpenFlow 兼容交换机之间的通信方式和内容。
• 通信方式：通常使用 TCP 连接，可选加密。
• 主要消息类别：
  1. 控制器到交换机：
     • Features：控制器查询交换机的特性（如端口、支持的表等），交换机回复。
     • Configure：控制器查询或设置交换机的配置参数。
     • Modify-State：核心消息，用于添加、删除、修改交换机流表中的流规则。
     • Packet-Out：控制器指示交换机将一个特定的数据包从指定端口发出。这常用于控制器处理第一个到达的、没有匹配流规则的数据包后，将处理结果（如转发决策）告知交换机，并让交换机将该数据包发出。
  2. 交换机到控制器：
     • Packet-In：核心消息，当一个数据包到达交换机，但在流表中找不到匹配的规则时，交换机将该数据包（或其一部分）封装在 Packet-In 消息中发送给控制器，请求处理指令。
     • Flow-Removed：当流表中的一个条目因为超时或被控制器删除时，交换机通知控制器。
     • Port-Status：当交换机的端口状态发生变化（如链路断开、启用/禁用）时，交换机通知控制器。
  3. 对称消息：用于维护连接、心跳检测等，如 Hello, Echo, Error。

OpenFlow 协议 vs. OpenFlow API

需要区分 OpenFlow 协议（定义控制器和交换机之间的消息格式和交互）与 OpenFlow API（控制器内部或北向应用使用的、用于编程控制流规则的接口）。

网络管理员或应用开发者通常使用更高级别的抽象（如控制器提供的 API），而不是直接构造和发送 OpenFlow 协议消息。

北向接口与网络应用

北向接口是 SDN 控制器向上层应用提供的接口，形式多样，如 REST API、Java API 等。它允许应用程序访问网络状态信息并下达控制指令。

网络控制应用是 SDN 的「大脑」，实现了具体的网络功能。它们利用北向接口与控制器交互，获取网络视图，并根据需要计算和下发流规则来实现所需功能，例如：

• 路由应用（如基于 Dijkstra 算法计算路径并下发流规则）
• 负载均衡应用
• 访问控制/防火墙应用
• 网络监控应用

SDN 控制/数据平面交互示例（链路故障处理）

以下是一个典型的 SDN 交互流程，展示了网络如何响应链路故障：

sequenceDiagram
    participant App as 路由应用（部署在控制器上）
    participant Ctrl as SDN 控制器
    participant SW1 as 交换机 S1
    participant SW2 as 交换机 S2

    Note over SW1, SW2: S1 和 S2 之间的链路故障

    SW1->>Ctrl: 1. 端口状态消息（Port Down），通过 OpenFlow 协议
    Ctrl->>Ctrl: 2. 更新内部链路状态信息
    Ctrl->>App: 3. 通知路由应用（链路状态变更事件）
    App->>Ctrl: 4. 请求网络拓扑及状态信息（通过北向接口）
    Ctrl-->>App: 提供网络信息
    App->>App: 5. 重新计算路由（例如，使用 Dijkstra 算法）
    App->>Ctrl: 6. 请求更新流表（通过北向接口）
    Ctrl->>Ctrl: 7. 根据应用请求生成新的流规则
    Ctrl->>SW1: 8. 安装/修改流规则（通过 OpenFlow Modify-State 消息）
    Ctrl->>SW2: 8. 安装/修改流规则（通过 OpenFlow Modify-State 消息）
    Note over SW1, SW2: 流量现在绕过故障链路

1. 链路故障检测：交换机 S1 检测到其连接 S2 的端口失效。
2. 通知控制器：S1 通过 OpenFlow 的 Port-Status 消息将端口状态变化通知给 SDN 控制器。
3. 更新状态与通知应用：控制器更新其内部维护的网络拓扑状态，并触发一个事件通知已注册的、对链路状态变化感兴趣的网络应用（如路由应用）。
4. 应用获取信息：路由应用收到通知后，通过北向接口向控制器查询最新的网络拓扑图和相关状态信息。
5. 重新计算路由：路由应用基于新的拓扑信息重新计算路由（例如，运行 Dijkstra 算法）。
6. 请求更新流表：路由应用将计算出的新路由结果（需要更新哪些交换机的哪些流规则）通过北向接口告知控制器。
7. 控制器生成流规则：控制器内部的流表计算组件根据应用请求，生成具体的 OpenFlow 流规则。
8. 下发流规则：控制器通过 OpenFlow 的 Modify-State 消息，将新的流规则下发到需要更新的交换机（如 S1, S2 等）。
9. 流量恢复：交换机更新流表后，后续的数据包将按照新的路由路径转发，绕过故障链路。

ICMP：互联网控制报文协议

互联网控制报文协议（Internet Control Message Protocol, ICMP）是 IP 协议的一个必要组成部分，尽管它在 OSI 模型中与 IP 位于同一层（网络层），但其报文是封装在 IP 数据报中传输的。

ICMP 的作用

ICMP 主要用于在 IP 主机、路由器之间传递控制消息和差错报告。它弥补了 IP 协议本身缺乏的某些反馈机制。主要功能包括：

• 差错报告：报告数据包在传输过程中遇到的问题，例如：目的网络/主机/协议/端口不可达。
  • 数据包生存时间（TTL）耗尽。
  • IP 首部参数错误。
• 网络探测与诊断：用于获取网络信息或测试连通性，例如：
  • 回显请求与应答，常用于 ping 命令。
  • 路由器通告与发现。
  • 时间戳请求与应答。

ICMP 报文格式

ICMP 报文封装在 IP 数据报的数据部分。其基本格式包含：

• 类型：8 位，标识 ICMP 报文的类型（差错报告或查询）。
• 代码：8 位，进一步细化报文类型（例如，「目的不可达」类型下有不同的代码表示具体原因）。
• 校验和：16 位，用于校验 ICMP 报文自身的错误。
• 报文内容：根据类型和代码的不同而变化。
  • 对于差错报告报文，通常包含导致错误的 IP 数据报的首部和数据部分的前 8 个字节。这有助于源主机了解是哪个数据包出了问题。
  • 对于查询报文，包含查询相关的信息（如标识符、序号）。

主要 ICMP 消息类型（示例）

Type	Code	描述	分类
0	0	Echo Reply (ping 回复)	查询/应答
3	0	Destination Network Unreachable (网络不可达)	差错报告
3	1	Destination Host Unreachable (主机不可达)	差错报告
3	2	Destination Protocol Unreachable (协议不可达)	差错报告
3	3	Destination Port Unreachable (端口不可达)	差错报告
3	6	Destination Network Unknown (目标网络未知)	差错报告
3	7	Destination Host Unknown (目标主机未知)	差错报告
4	0	Source Quench (源抑制 - 已废弃)	差错报告
8	0	Echo Request (ping 请求)	查询/请求
9	0	Router Advertisement (路由器通告)	信息
10	0	Router Solicitation (路由器请求)	信息
11	0	Time Exceeded (TTL 超时)	差错报告
12	0	Parameter Problem (IP 首部参数错误)	差错报告

应用示例：Traceroute

traceroute（或 Windows 下的 tracert）是一个常用的网络诊断工具，用于探测数据包从源主机到目的主机所经过的路由器路径。它巧妙地利用了 IP 协议的 TTL 字段和 ICMP 的「TTL 超时」及「端口不可达」消息。

工作原理：

1. 发送 UDP 探测包：源主机向目的主机发送一系列 UDP 数据包。这些 UDP 包的目的端口号通常选择一个不太可能被使用的值。
2. 递增 TTL：
   • 第一批（通常 3 个）探测包的 IP 首部 TTL 字段设置为 1。
   • 第二批探测包的 TTL 设置为 2。
   • 以此类推，第 $n$ 批探测包的 TTL 设置为 $n$。
3. 中间路由器响应：
   • 当 TTL=1 的数据包到达路径上的第一个路由器时，该路由器将 TTL 减 1 变为 0。此时，路由器丢弃该数据包，并向源主机发送一个 ICMP Time Exceeded(Type 11, Code 0) 消息。该 ICMP 消息的源 IP 地址就是该路由器的 IP 地址。
   • 当 TTL=2 的数据包到达路径上的第二个路由器时，同样发生 TTL 超时，第二个路由器发回 ICMP Time Exceeded 消息。
   • …
   • 当 TTL=n 的数据包到达路径上的第 $n$ 个路由器时，第 $n$ 个路由器发回 ICMP Time Exceeded 消息。
4. 目的主机响应：
   • 当某批探测包（假设 TTL=k）最终到达目的主机时，由于目的端口不可用，目的主机的 IP 协议栈会向源主机发送一个 ICMP Destination Port Unreachable(Type 3, Code 3) 消息。
5. 源主机处理：
   • 源主机接收到来自中间路由器的 ICMP Time Exceeded 消息时，记录下该路由器的 IP 地址和往返时间（RTT）。
   • 当源主机接收到来自目的主机的 ICMP Port Unreachable 消息时，就知道探测已经到达终点，停止发送探测包。
   • 通过收集所有中间路由器发回的 ICMP 消息，源主机就能描绘出到达目的地的路径，并估算出每跳的 RTT。

sequenceDiagram
    participant 源主机
    participant 路由器 1
    participant 路由器 2
    participant 目的主机

    源主机->>路由器 1: UDP 数据包（TTL=1）
    路由器 1->>路由器 1: TTL=0，丢弃数据包
    路由器 1-->>源主机: ICMP Time Exceeded（来自 R1 的 IP）

    源主机->>路由器 2: UDP 数据包（TTL=2）
    路由器 2->>路由器 2: TTL=1
    路由器 2->>路由器 2: TTL=0，丢弃数据包
    路由器 2-->>源主机: ICMP Time Exceeded（来自 R2 的 IP）

    源主机->>目的主机: UDP 数据包（TTL=3，到达目的地）
    目的主机->>目的主机: UDP 端口不可达
    目的主机-->>源主机: ICMP Port Unreachable（来自 Dest 的 IP）

    Note over 源主机: 记录 R1 的 IP 和 RTT
    Note over 源主机: 记录 R2 的 IP 和 RTT
    Note over 源主机: 记录 Dest 的 IP 和 RTT，停止发送。

网络管理

现代网络（如 ISP 网络、大型企业网）通常包含成千上万的硬件和软件组件（路由器、交换机、服务器、链路等），这些组件相互作用，构成一个复杂的自治系统。网络管理就是对这些复杂系统进行监控、配置和控制的过程。

什么是网络管理

网络管理包含了一系列活动，旨在确保网络资源能够高效、可靠地运行，满足性能和服务质量（QoS）要求，其主要任务包括：

• 部署与集成：安装、配置新的网络设备和软件。
• 监控：持续收集网络设备的状态、性能指标（如链路利用率、错误率、延迟）和事件信息。
• 测试与轮询：主动探测设备状态和连通性。
• 配置：修改设备参数（如路由表、接口设置、安全策略）。
• 分析与评估：分析收集到的数据，评估网络性能，诊断问题。
• 控制：根据分析结果采取行动，调整配置，优化性能。

网络管理框架

一个典型的网络管理框架包含以下关键组件：

1. 管理服务器/控制器（Managing Server/Controller）：
   • 运行网络管理应用程序的中心节点。
   • 通常有人类网络管理员通过它与网络交互。
   • 负责收集信息、分析数据、发送指令。
2. 被管设备（Managed Device）：
   • 网络中需要被管理的元素，如路由器、交换机、服务器、防火墙等。
   • 这些设备包含可配置的硬件和软件组件。
3. 网管代理（Agent）：
   • 运行在被管设备上的软件进程。
   • 负责响应来自管理服务器的请求（查询或设置）。
   • 主动向管理服务器发送通知（如发生异常事件时）。
   • 与设备的本地状态和配置信息交互。
4. 管理信息（Data/MIB）：
   • 被管设备的状态、配置和统计数据。
   • 这些信息被组织成管理信息库（Management Information Base, MIB）。MIB 定义了可以通过网管协议访问的数据对象的集合及其结构。
5. 网管协议（Network Management Protocol）：
   • 用于在管理服务器和被管设备（通过代理）之间传递管理信息和命令的协议。
   • 常见的协议有 SNMP 和 NETCONF。

graph TD
    subgraph Managing_Entity [管理实体]
        direction TB
        Server[管理服务器/控制器] -->|发出请求/指令| Protocol
        Protocol -->|接收响应/通知| Server
        Admin(网络管理员) --> Server
    end

    subgraph Managed_Entity [被管实体]
        direction TB
        Device[被管设备（路由器, 交换机等）]
        Agent[网管代理（运行在设备上）] --> Device
        MIB[管理信息库（MIB）<br>存储设备状态/配置] --> Agent
    end

    Protocol(网管协议 <br> e.g., SNMP, NETCONF)

    Server <-.->|通过协议交互| Agent

    style Admin fill:#eee,stroke:#333

网管方法

网络管理员可以通过多种方式与网络设备进行交互和管理：

1. 命令行接口（Command Line Interface, CLI）：
   • 管理员通过 SSH 或 Telnet 直接登录到设备，输入特定于厂商的命令来查询状态或进行配置。
   • 优点：直接、灵活。
   • 缺点：难以自动化、不同厂商命令不统一、不易进行大规模管理。
2. 简单网络管理协议（Simple Network Management Protocol, SNMP）与 MIB：
   • 最广泛使用的传统网管协议。
   • 管理员通过管理服务器使用 SNMP 查询（Get）或设置（Set）被管设备 MIB 中的对象值。
   • 设备代理可以通过 SNMP Trap 主动向服务器报告重要事件。
   • 优点：标准化、广泛支持。
   • 缺点：安全性较弱（早期版本）、Set 操作功能有限、面向单个数据对象而非事务性配置。
3. 网络配置协议（Network Configuration Protocol, NETCONF）与 YANG：
   • 较新的网管协议，旨在克服 SNMP 的一些缺点。
   • 提供更强大、更安全的网络设备配置和管理能力。
   • 面向事务（支持原子提交、回滚）。
   • 使用 YANG(Yet Another Next Generation) 数据建模语言来定义配置数据、状态数据、RPC 操作和通知的结构。
   • 通常运行在 SSH 等安全传输协议之上，使用 XML 编码消息。
   • 优点：功能强大、事务性、安全性好、模型驱动、易于自动化。

SNMP 详解

• 协议操作模式：
  • 请求/响应模式：管理服务器向代理发送请求（如 GetRequest, GetNextRequest, SetRequest），代理处理后返回响应。
  • 陷阱模式：代理在检测到异常或重要事件（如链路断开、设备重启）时，主动向管理服务器发送 Trap 消息。
• 主要消息类型：
  • GetRequest: 获取一个或多个 MIB 变量的值。
  • GetNextRequest: 获取 MIB 树中下一个变量的值（用于遍历 MIB）。
  • GetBulkRequest: 高效获取 MIB 表中的大量数据。
  • SetRequest: 设置一个或多个 MIB 变量的值。
  • Response: 代理对 Get/Set 请求的应答。
  • Trap: 代理主动发送的事件通知。
• MIB 与 SMI：
  • MIB：定义了可管理的网络对象的集合。这些对象通过「对象标识符」（OID）进行唯一标识，形成一个层次化的树状结构。
  • 管理信息结构（Structure of Management Information, SMI）：定义了 MIB 对象的命名规则、数据类型（如 Integer32, Counter32, IpAddress, OctetString）以及如何在 MIB 中组织这些对象。

NETCONF/YANG 详解

• 目标：提供一种标准化的、基于模型的、自动化的方式来配置和管理网络设备。
• 核心特点：
  • 基于模型：使用 YANG 数据模型来描述设备的配置和状态信息。YANG 模型提供了清晰、标准化的数据结构、语法和语义。
  • 配置与状态分离：明确区分设备的配置数据（可读写）和状态数据（只读）。
  • 事务性：支持对配置进行原子化操作（要么全部成功，要么全部回滚），确保配置的一致性。支持配置锁定。
  • RPC 范式：操作通过远程过程调用（Remote Procedure Call, RPC）实现，使用 XML 编码消息。
  • 安全传输：通常运行在 SSH 或 TLS 等安全协议之上。
• 主要 NETCONF 操作（示例）：
  • <get-config>: 获取指定的配置数据存储（如 running, startup, candidate）中的配置。
  • <get>: 获取设备的配置和状态数据。
  • <edit-config>: 修改目标配置数据存储（如 running, candidate）。支持多种操作（merge, replace, create, delete）。
  • <copy-config>: 在不同的配置数据存储之间复制配置。
  • <delete-config>: 删除一个配置数据存储。
  • <lock>, <unlock>: 锁定/解锁配置数据存储，防止冲突。
  • <commit>: 将 candidate 配置应用到 running 配置（如果设备支持 candidate）。
  • <discard-changes>: 丢弃 candidate 配置中的未提交更改。
  • <create-subscription>: 订阅设备产生的通知（事件）。
• YANG 数据建模语言：
  • 用于定义 NETCONF 操作的数据结构、配置数据、状态数据、RPC 和通知。
  • 提供丰富的数据类型、约束机制、模块化和重用能力。
  • YANG 模型可以被编译成 XML Schema Definition(XSD) 或其他格式，用于验证 NETCONF 消息。

<!-- 示例 NETCONF RPC 消息，用于更改 MTU -->
<?xml version="1.0" encoding="UTF-8"?>
<rpc message-id="101"
     xmlns="urn:ietf:params:xml:ns:netconf:base:1.0">
  <edit-config>
    <target>
      <running/> <!-- 目标为当前运行的配置 -->
    </target>
    <config xmlns="http://example.com/schema/1.2/config">
      <!-- 基于 YANG 模型的配置数据 -->
      <interfaces>
        <interface>
          <name>Ethernet0/0</name>
          <mtu>1500</mtu> <!-- 将 MTU 设置为 1500 -->
        </interface>
      </interfaces>
    </config>
  </edit-config>
</rpc>