Chapter 5-1：网络层控制平面、链路状态路由与 Dijkstra 算法

引言：转发表是怎样产生的

网络层的数据平面解决的是分组的实际转发问题：当一个分组到达路由器后，路由器读取分组首部、查询转发表，并将分组送往相应的输出端口。

但是，数据平面使用的转发表并不是凭空产生的。在执行转发之前，网络还必须回答一个更基础的问题：

分组从源网络到目的网络，应该经过哪些路由器？

这正是控制平面要解决的问题。控制平面通过路由协议收集网络状态，利用路由算法计算合适的端到端路径，并根据计算结果生成路由表或转发表。

本章的核心逻辑可以概括为：

  flowchart TD
    A[收集网络状态] --> B[建立网络拓扑]
    B --> C[运行路由算法]
    C --> D[得到最短路径树]
    D --> E[生成路由表或转发表]
    E --> F[数据平面执行转发]
  

❗核心主线： 链路状态路由首先让路由器获得一张全网地图，再由每台路由器运行 Dijkstra 算法计算最短路径，最后将计算结果转化为能够直接执行的转发表。

1. 控制平面与数据平面的分工

1.1 数据平面负责本地转发

数据平面关注的是分组到达一台具体路由器之后的处理过程。它需要回答：

• 应该查询哪一项转发表？
• 分组应该进入哪个输出端口？
• 如何排队、交换和发送该分组？

因此，转发是一种局部操作。每台路由器只需要根据已有的转发表，决定当前分组的下一跳。

1.2 控制平面负责全局路径决策

控制平面关注的是分组在整个网络中的路径。它需要回答：

• 从源网络到目的网络可以经过哪些路由器？
• 哪一条路径的代价更低？
• 链路发生故障后应该如何改道？
• 路由表应该怎样更新？

假设从路由器 A 到目的路由器 Z 存在多条路径：

1
2
3

A → B → C → Z
A → D → E → Z
A → F → G → H → Z

数据平面只能执行已经确定的下一跳，而不能独立判断哪一条完整路径更合适。路径选择必须由控制平面提前完成。

❗关键区分： 路由负责计算路径，转发负责执行路径。前者产生决策，后者使用决策。

2. 两种控制平面组织方式

控制平面可以采用传统的逐路由器控制方式，也可以采用软件定义网络中的逻辑集中控制方式。

2.1 传统的 per-router 控制平面

在传统网络中，每台路由器内部都运行路由协议和路由算法。各路由器之间交换控制信息，并根据获得的信息独立计算自己的路由表。

它的基本过程是：

  flowchart LR
    R1[路由器 R1<br/>路由算法] <--> R2[路由器 R2<br/>路由算法]
    R2 <--> R3[路由器 R3<br/>路由算法]
    R1 <--> R3
  

每台路由器同时具有：

• 数据平面功能：执行分组转发；
• 控制平面功能：交换路由信息并计算路径。

2.2 SDN 的逻辑集中控制平面

在软件定义网络中，主要控制逻辑位于远程控制器。网络设备中的本地控制代理与控制器通信，接收控制器下发的流表或转发规则。

SDN 所说的“集中”通常是逻辑集中，并不意味着现实中只能部署一台控制器。为了可靠性和性能，控制器可以由多个物理节点组成，但对网络设备呈现统一的控制逻辑。

❗本节核心结论：

传统控制平面把路由计算分布在各台路由器中；SDN 将控制逻辑集中到控制器。两者都需要最终向数据平面提供可执行的转发规则。

3. 路由协议究竟在计算什么

3.1 路径与“好路径”

路由协议需要确定从发送方到接收方的路径。这里的路径可以理解为：

分组从源网络前往目的网络时依次经过的路由器序列。

所谓“好路径”并不一定只有一种评价标准。它可能表示：

• 总链路代价最小；
• 经过的路由器数量最少；
• 可用带宽更高；
• 时延更低；
• 拥塞程度更低；
• 可靠性更高；
• 更符合运营商的管理策略。

因此，最短路径中的“短”通常指代价最小，而不一定是物理距离最近或经过节点最少。

3.2 为什么通常计算网络到网络的路径

互联网包含大量主机。如果路由器为每一对主机分别计算和保存路径，路由表规模与计算开销都会难以承受。

因此，路由系统通常围绕网络前缀或子网进行计算：

1

源网络 → 中间路由器 → 目的网络

当分组到达目的网络的网关路由器后，网关再通过链路层机制把数据交付给具体主机。在以太网中，这一步通常涉及 IP 地址到 MAC 地址的解析以及帧的本地传输。

由此可以形成以下逻辑链条：

  flowchart TD
    A[路由协议交换信息] --> B[路由算法计算路径]
    B --> C[生成路由表]
    C --> D[形成转发表]
    D --> E[数据平面查询并转发]
  

需要注意以下概念的区别：

• 路由协议：规定路由器之间交换哪些信息以及如何交换；
• 路由算法：根据已有信息计算路径；
• 路由表或转发表：保存计算结果；
• 转发：依据表项处理具体分组。

❗关键结论： 路由协议不是转发动作本身，而是为路由计算提供信息；路由算法不是路由表，而是产生路由表的计算过程。

4. 将网络抽象为带权图

4.1 图模型

为了使用成熟的算法计算路径，可以把路由器网络抽象为带权图：

1

G = (N, E)

其中：

• N 表示节点集合，通常对应路由器；
• E 表示边集合，通常对应路由器之间的链路；
• c(i, j) 表示节点 i 到节点 j 的直接链路代价；
• 如果 i 与 j 不直接相连，则可令 c(i, j) = ∞。

例如：

  flowchart LR
    U((u)) -- 2 --> V((v))
    U -- 1 --> X((x))
    X -- 2 --> Y((y))
    X -- 3 --> W((w))
    Y -- 1 --> Z((z))
    W -- 2 --> Z
  

边上的数字表示链路代价。链路代价可以由网络运营者配置，例如：

• 所有链路统一设为 1，此时算法倾向于选择跳数最少的路径；
• 使用带宽的倒数，使高带宽链路具有更低代价；
• 根据时延、拥塞程度或管理策略设置不同代价。

4.2 为什么图抽象有效

完成图抽象后，路由问题就转化为经典的最短路径问题：

已知网络拓扑、各条链路的代价和一个源节点，求源节点到其他节点的最低代价路径。

这种抽象把复杂的实际网络压缩为“节点—边—代价”三个要素，使路由系统能够应用 Dijkstra 等图算法。

4.3 最短路径树

当路由器以自己为源节点计算到所有其他节点的最短路径时，得到的不是一条孤立路径，而是一棵最短路径树。

例如，从 u 到多个目标节点的路径可能是：

1
2
3
4

u → x
u → x → y
u → x → w
u → x → y → z

这些路径共享前缀 u → x。把所有路径合并后，就形成以 u 为根的最短路径树。

最短路径树能够直接帮助路由器确定下一跳：

• 到目的节点 v 的路径首先经过 v，则输出链路为 (u, v)；
• 到目的节点 y、w、z 的路径都首先经过 x，则对应的输出链路都为 (u, x)。

❗本节核心结论：

图模型把路由选择转化为带权图上的最短路径问题；最短路径树进一步把端到端路径转化为每个目的地对应的第一跳。

5. 路由算法应满足的基本要求

路由算法不能只追求数学意义上的最优，还必须考虑实际网络的运行条件。

这些要求之间可能存在冲突。例如：

• 频繁根据实时拥塞调整路径，可能提高瞬时性能，却降低稳定性；
• 采用复杂算法可能得到更优路径，却增加控制开销；
• 完全追求全局最优，可能对某些流量或节点不公平。

因此，真实路由系统通常是在最优性、稳定性、复杂度与可管理性之间进行折中。

❗关键判断： 路由算法的价值不只在于算出理论最短路，还在于能够以可接受的代价稳定地适应真实网络。

6. 路由算法的主要分类

6.1 按掌握的信息范围分类

路由算法可以分为链路状态算法和距离向量算法。

链路状态算法中，每台路由器最终都会获得完整拓扑。距离向量算法中，路由器不需要掌握完整网络结构，而是根据邻居提供的信息逐步更新自己到各目的地的距离。

6.2 按适应变化的方式分类

路由还可以分为静态路由和动态路由。

动态路由并不意味着每转发一个分组都重新计算路径。它表示路由表可以随着网络拓扑或链路状态变化而更新。

❗本节核心结论：

LS 与 DV 的根本区别在于路由器获得的信息范围和计算方式；静态与动态的区别则在于路由能否根据网络变化自动更新。

7. 链路状态路由的完整工作过程

7.1 核心思想

链路状态路由的基本思想是：

每台路由器将自己与邻居之间的链路状态传播给全网，使所有路由器最终获得相同或近似一致的拓扑数据库，然后各自运行最短路径算法。

这一过程可以分为两个阶段：

  flowchart TD
    A[发现邻居] --> B[测量链路代价]
    B --> C[生成链路状态分组]
    C --> D[向全网可靠泛洪]
    D --> E[建立链路状态数据库]
    E --> F[运行 Dijkstra 算法]
    F --> G[生成路由表]
  

前四个步骤负责收集和传播信息，后续步骤负责在完整拓扑上计算路径。

7.2 第一步：发现相邻节点

每台路由器首先要识别与自己直接连接的路由器，并获得邻居的标识或网络地址。

此时，路由器掌握的仍然只是局部信息：

• 自己连接了哪些邻居；
• 哪个接口通向哪个邻居；
• 邻居是否仍然可达。

7.3 第二步：测量链路代价

路由器需要为每条直接链路确定代价。代价可以来自：

• 管理员配置；
• 链路带宽；
• 传播或排队时延；
• 网络负载；
• 其他策略性指标。

链路代价是后续最短路径计算的基础。

7.4 第三步：生成链路状态分组

路由器把自己的局部链路信息封装为链路状态分组。该分组通常描述：

• 产生该信息的路由器；
• 它有哪些直接邻居；
• 到各邻居的链路代价；
• 序列号；
• 生存时间或年龄字段。

链路状态分组属于控制信息，不是普通用户数据。它的作用是帮助路由器建立拓扑数据库，而不是承载用户应用数据。

7.5 第四步：向全网泛洪

链路状态分组需要传播到网络中的其他路由器。路由器收到新的链路状态信息后，会继续向其他接口转发，使信息逐渐扩散到整个网络。

最终，每台路由器都能够获得所有路由器发布的链路状态，并重建完整拓扑。

7.6 第五步：计算最短路径

当链路状态数据库建立后，每台路由器以自己为源节点运行 Dijkstra 算法，得到到其他节点的最低代价路径，并根据最短路径树生成路由表。

LS 机制与 Dijkstra 算法不能混为一谈：

❗关键区分： LS 是一整套路由信息获取与传播机制；Dijkstra 只是其中用于路径计算的算法。

8. 泛洪为什么需要控制

8.1 无控制泛洪的问题

网络中通常存在环路。如果路由器对收到的链路状态分组不加判断地继续转发，同一个分组可能沿不同路径反复传播，造成：

• 重复分组大量增加；
• 控制流量占用链路带宽；
• 路由器反复处理相同信息；
• 极端情况下形成广播风暴；
• 旧拓扑信息长期无法消失。

8.2 Age 字段

链路状态分组可以带有年龄或生存时间字段。该字段会随时间或每次转发而减小，当其降为零时，相关信息被丢弃。

Age 字段解决的是：

如何防止控制分组以及过期拓扑信息永久存在于网络中。

它的作用类似 IP 数据报中的 TTL。

8.3 序列号

每个链路状态分组通常带有序列号。路由器可以通过序列号判断：

• 该分组是否比数据库中的版本更新；
• 是否已经处理过同一版本；
• 收到的是新信息还是重复信息；
• 旧信息是否应该被丢弃。

序列号解决的是版本识别和重复抑制问题。

8.4 可靠泛洪

为了确保链路状态信息能够到达所有路由器，可以对泛洪过程加入确认与重传机制：

• 接收方确认收到新的链路状态信息；
• 未收到确认时，发送方可以再次发送；
• 路由器只继续传播更新或尚未处理的信息。

通过 Age、序列号、确认和重传，可以在控制重复传播的同时提高拓扑数据库的一致性。

8.5 典型链路状态协议

常见的链路状态协议包括：

• OSPF；
• IS-IS。

它们都遵循“传播链路状态—建立拓扑数据库—运行最短路径算法”的基本思想，但在报文格式、层次化组织和工程实现上有所不同。

❗本节核心结论：

泛洪负责让每台路由器获得全网状态，但必须使用 Age、序列号和可靠传输机制抑制重复、清除旧信息并保证传播完整性。

9. Dijkstra 算法的基本思想

9.1 算法目标

Dijkstra 算法用于在链路代价非负的带权图中，计算一个源节点到其他所有节点的最低代价路径。

在链路状态路由中，每台路由器都可以：

1. 获得相同的网络拓扑；
2. 以自己为源节点运行 Dijkstra；
3. 得到自己的最短路径树；
4. 生成适用于自己的路由表。

Dijkstra 被称为全局或集中式算法，是因为算法运行时需要完整的拓扑和链路代价。它不意味着全网只能由一台中央设备计算。

9.2 常用符号

设源节点为 u。

其中：

• D(v) 用于判断哪条路径更短；
• p(v) 用于恢复完整路径；
• N' 中节点的最短路径已经最终确定。

9.3 初始化

算法开始时：

1

N' = {u}

对于其他每个节点 v：

1
2
3
4
5

如果 v 与 u 直接相连：
    D(v) = c(u, v)
    p(v) = u
否则：
    D(v) = ∞

此时，算法只知道源节点到直接邻居的代价。

9.4 迭代过程

每一轮执行以下操作：

1. 在所有不属于 N' 的节点中，选择 D(w) 最小的节点 w；
2. 将 w 加入 N'；
3. 检查经过 w 是否能缩短到其邻居 v 的路径；
4. 如果能够缩短，则更新 D(v) 和 p(v)；
5. 重复上述过程，直到所有节点都进入 N'。

路径更新公式为：

1

D(v) = min(D(v), D(w) + c(w, v))

它比较两种方案：

• 保持原有路径，代价为 D(v)；
• 先从源节点到达 w，再沿链路 (w, v) 到达 v，代价为 D(w) + c(w, v)。

如果后一种代价更小，则：

1
2

D(v) = D(w) + c(w, v)
p(v) = w

9.5 为什么每次选择最小的临时节点

在链路代价非负的条件下，当前所有未确定节点中，D(w) 最小的节点不可能再通过其他未确定节点得到更短路径。

假设还要绕过另一个尚未确定的节点再到达 w，由于后续链路代价不会为负，新路径只会更长或相等。因此，可以安全地把 w 的最短路径固定下来。

算法的过程可以概括为：

  flowchart TD
    A[初始化源节点及邻居距离] --> B[选择当前 D 最小的未确定节点]
    B --> C[将该节点加入 N']
    C --> D[用该节点更新邻居距离]
    D --> E{是否还有未确定节点}
    E -- 是 --> B
    E -- 否 --> F[得到最短路径树]
  

❗本节核心结论：

Dijkstra 每轮固定一个当前代价最小的节点，再利用该节点尝试改进其他路径。D(v) 保存代价，p(v) 保存路径结构。

10. 如何阅读 Dijkstra 计算表

课件中的 Dijkstra 表格通常每一行表示一轮迭代。阅读时应关注三个问题：

• 哪些节点已经进入 N'？
• 哪个临时节点的 D 值最小？
• 加入该节点后，哪些其他节点的 D 和前驱发生了变化？

以源节点 u 为例：

Step 0：初始化

1

N' = {u}

• 到直接邻居的 D 值等于链路代价；
• 到非邻居节点的 D 值为无穷大；
• 直接邻居的前驱为 u。

后续步骤：选择与更新

每一轮：

1. 选择 D 值最小的临时节点；
2. 将其加入 N'；
3. 通过该节点尝试更新其他节点；
4. 在表格下一行记录新的 D(v) 和 p(v)。

根据前驱恢复路径

假设最终得到：

1
2
3

p(z) = y
p(y) = x
p(x) = u

从 z 向前追溯：

1

z ← y ← x ← u

逆序后得到完整路径：

1

u → x → y → z

因此：

• D(z) 告诉我们路径总成本；
• p(z) 及其他前驱记录告诉我们实际经过哪些节点。

11. 从最短路径树生成转发表

Dijkstra 的输出是以当前路由器为根的最短路径树，但数据平面不需要保存每条完整路径。执行转发时，路由器最关心的是：

要到达某个目的地，第一跳应该走哪个邻居？

假设从 u 出发的最短路径结果如下：

则可以生成类似的转发表：

尽管到 y、w、z 的完整路径不同，但它们从 u 出发时都先经过 x，所以可以共享同一个下一跳。

这说明最短路径树在控制平面与数据平面之间起到了转换作用：

  flowchart LR
    A[完整网络拓扑] --> B[Dijkstra]
    B --> C[最短路径树]
    C --> D[提取各目的地第一跳]
    D --> E[转发表]
  

❗关键结论： 控制平面计算完整路径，但数据平面通常只需要知道下一跳或输出接口。

12. Dijkstra 与链路状态路由的复杂度

12.1 算法复杂度

如果网络中有 n 个节点，普通数组实现需要反复扫描所有未确定节点，选择当前 D 值最小者。

总比较次数大致为：

1

n + (n - 1) + ... + 1

因此时间复杂度为：

1

O(n²)

如果使用优先队列等更高效的数据结构，在合适的图表示下，复杂度可以降低到近似：

1

O(n log n)

更严格的复杂度还会受到边数和具体数据结构影响，但核心思想是避免每轮线性扫描全部节点。

12.2 消息复杂度

链路状态协议不仅有本地计算成本，还有控制信息传播成本。每台路由器都需要把自己的链路状态传播给其他路由器。

在简单分析中：

• 每个路由器产生链路状态信息；
• 信息需要扩散到全网；
• 整体控制消息量可达到约 O(n²) 的数量级。

因此，链路状态路由的成本包括两个部分：

• Dijkstra 的本地计算成本；
• 链路状态泛洪的通信成本。

❗本节核心结论：

LS 路由的开销不能只看 Dijkstra 的运行时间，还要考虑全网泛洪带来的控制消息成本。

13. 三种“全局”与“集中”不能混淆

本章中会同时出现“全局信息”“集中式算法”和“逻辑集中控制”等表述，但它们指向不同层面。

13.1 LS 的全局信息

LS 中可以没有唯一的中央计算节点。每台路由器通过泛洪获得全网信息，并分别运行算法。

13.2 Dijkstra 的集中式

这里的“集中式”描述算法需要完整输入，而不是描述算法一定在哪里执行。多台路由器可以分别运行 Dijkstra。

13.3 SDN 的逻辑集中

SDN 描述的是控制架构。路由和流表计算主要由控制器承担，网络设备侧主要负责执行。

❗关键区分： 信息是全局的、算法输入是集中的、控制架构是逻辑集中的，分别属于信息范围、算法模型和系统架构三个层面。

14. 常见误区

14.1 路由器是否一开始就知道全网拓扑

不是。路由器最初只知道自己的邻居和本地链路。它必须通过链路状态泛洪逐渐收集其他路由器的信息，才能建立完整拓扑。

14.2 Dijkstra 是否只在中央服务器运行

不是。只要每台路由器拥有完整的链路状态数据库，就可以分别以自己为源节点运行 Dijkstra。

14.3 链路状态分组是否属于用户数据

不是。链路状态分组属于控制平面报文，目的是同步拓扑信息；用户 IP 数据报属于数据平面处理的对象。

14.4 Dijkstra 为什么得到一棵树

因为从同一个源节点出发的多条最短路径往往共享前缀。把这些路径合并，就形成一棵以源节点为根的最短路径树。

14.5 D(v) 与 p(v) 是否相同

二者用途不同：

• D(v) 记录当前最低代价；
• p(v) 记录路径中的前驱节点。

没有 D(v)，无法比较路径长短；没有 p(v)，只能知道代价，不能恢复完整路径。

14.6 动态路由是否为每个分组重新算路

不是。动态路由根据拓扑变化、周期性通告或链路状态变化更新路由表。大量普通分组仍然直接查询现有转发表。

15. 知识结构总览

  flowchart TD
    A[网络层控制平面] --> B[控制架构]
    A --> C[路由协议与算法]
    A --> D[路径计算]

    B --> B1[传统 per-router]
    B --> B2[SDN 逻辑集中]

    C --> C1[LS 链路状态]
    C --> C2[DV 距离向量]
    C --> C3[静态路由]
    C --> C4[动态路由]

    D --> D1[带权图 G = N,E]
    D1 --> D2[链路代价]
    D2 --> D3[Dijkstra]
    D3 --> D4[最短路径树]
    D4 --> D5[路由表或转发表]
  

这张图体现了本章的完整关系：

• 控制平面决定网络路径；
• 路由协议负责交换控制信息；
• LS 通过泛洪形成全局拓扑；
• Dijkstra 在拓扑上计算最短路径；
• 最短路径树被转化为下一跳表项；
• 数据平面依据表项完成实际转发。

16. 复习清单

完成本章学习后，应能够回答以下问题：

• 数据平面与控制平面的核心区别是什么？
• 为什么说转发是本地动作，而路由是全局动作？
• 传统 per-router 控制平面与 SDN 控制平面有何区别？
• SDN 的“逻辑集中”为什么不等于只有一台服务器？
• 路由协议中的“好路径”可以采用哪些衡量标准？
• 为什么互联网路由通常面向网络前缀，而不是每台具体主机？
• 路由协议、路由算法、路由表和转发分别承担什么职责？
• 在图 G = (N, E) 中，N、E 和 c(i, j) 分别表示什么？
• 如果两个节点不直接相连，链路代价应如何表示？
• 什么是最短路径树？
• 为什么路由算法不仅要考虑最优性，还要考虑稳定性和健壮性？
• LS 与 DV 在信息范围和计算方式上有何区别？
• 静态路由与动态路由有何区别？
• LS 路由的五个基本步骤是什么？
• 泛洪为什么可能产生广播风暴？
• Age 字段、序列号和确认机制分别解决什么问题？
• 链路状态协议过程与 Dijkstra 算法有何区别？
• N'、D(v)、p(v) 和 c(i, j) 分别表示什么？
• 为什么 Dijkstra 每轮选择当前 D 值最小的节点？
• 更新公式 D(v) = min(D(v), D(w) + c(w, v)) 表达了什么？
• 如何通过前驱节点恢复完整最短路径？
• 为什么多个不同目的地可能对应相同的下一跳？
• Dijkstra 的算法复杂度和 LS 泛洪的消息复杂度分别是什么？
• LS 的全局信息、Dijkstra 的集中式和 SDN 的逻辑集中有何不同？

结论

网络层控制平面的根本任务，是为数据平面的高速转发提供正确、稳定且可更新的路径决策。

链路状态路由通过邻居发现、代价测量、链路状态分组生成和可靠泛洪，使每台路由器逐步获得完整的网络拓扑。随后，每台路由器以自己为源节点运行 Dijkstra 算法，计算到其他节点的最低代价路径，并将最短路径树转化为目的地与下一跳之间的映射。

因此，本章的完整逻辑可以压缩为：

1
2
3
4
5
6
7
8
9
10
11

局部链路状态
    ↓
全网拓扑数据库
    ↓
Dijkstra 最短路径计算
    ↓
最短路径树
    ↓
路由表或转发表
    ↓
数据平面逐跳转发

❗最终结论： 控制平面负责回答“应该走哪条路”，数据平面负责回答“当前这一跳从哪个端口出去”。LS 负责获得地图，Dijkstra 负责在地图上算路，转发表则把计算结果转化为路由器能够高速执行的下一跳决策。