引入

网络层的主要功能

网络层主要是进行路由和转发。

  • 路由（Routing），是指寻找源到目的主机的一条合适的路。路由通常由路由算法驱动。对于单个路由器来说，这条合适的路就是从哪个端口转发出去。
  • 转发（Forwarding），是指将路由器一个口收到的东西发到另一个口上去。

路由器的工作原理介绍

转发表（Forwarding table）

路由器的内部会维护一张转发表（Forwarding table），路由表会记录每一个网段应该转发到哪个接口。

转发表依赖于路由表，但它不是路由表。路由表主要用于路由选择过程，决定数据包的传输路径，这是属于控制面的表；而转发表则是为了在转发平面快速转发数据包，它的结构更适合高速查找，以实现数据包的高效转发，这是数据数据面的表。路由表会记录为了达到目标网段，下一跳是哪里。而转发表只记录某一段该转发到哪个接口。

例如下面这个表：

目的地址范围（数字 IP 地址） 链路接口
200.23.24.0 到 200.23.23.255 0
200.23.24.0 到 200.23.24.255 1
200.23.25.0 到 200.23.31.255 2
others 3

为解决转发表过大的问题，采用最长前缀匹配的方法。表格中列出了前缀匹配（Prefix Match）和对应的链路接口。

对于给定的目的地址（DA），找到与目的地址前缀匹配最长的条目，从而确定对应的链路接口。这样可以在减少转发表规模的同时，准确地进行数据包转发。

路由的总体架构

路由器包含多个输入端口（input ports）、多个输出端口（output ports）、交换结构（switching fabric）以及路由处理器（routing processor）。

输入和输出端口负责数据的接收与发送，交换结构在输入 / 输出端口之间起到数据转发的桥梁作用，路由处理器则用于处理路由相关的决策等任务，整体呈现出路由器各组件协同工作以实现数据转发的架构。

路由的内部工作方式

交换方式

总的来说，路由的交换结构有三种：内存交换、总线交换、交叉开关交换（crossbar）

内存交换

image-20251006185644240

内存交换将数据先暂存到内存，再从内存转发到输出端口。

这类路由器本质上是受 CPU 直接控制的传统计算机，数据包会被复制到系统内存中。其交换速度受内存带宽限制，并且每个数据报需要经过 2 次总线传输（从输入端口到内存，再从内存到输出端口）

一些现代路由器仍在使用这种通过内存交换的方式，目的地址的查找和数据包存储到合适内存位置的操作，通常由输入线卡上的处理器完成，从某种程度上看，这样的路由器类似共享内存的多处理器，输入线卡上的处理器负责将数据包交换到相应输出端口的内存中

总线交换

image-20251006185818306

总线交换借助共享总线实现输入端口到输出端口的数据传输，接收数据报从输入端口内存通过共享总线传输到输出端口内存。

它存在总线竞争（bus contention）问题，因为多个输入端口共享总线，交换速度受总线带宽限制。以 1Gbps 带宽的总线为例，Cisco 1900 系列路由器使用这种总线，对于接入和企业级路由器通常足够，但对于区域或骨干路由器可能带宽不足。并且路由器的交换带宽整体受总线速度限制。

通过交叉开关（crossbar）交换

image-20251006190138435

通过交叉开关网络来连接输入和输出端口，能更灵活、高效地进行数据交换，可同时建立多个输入与输出的连接。这种方式被称为Blocking Switch，目的是克服总线带宽的限制。以 Cisco 12000 为例，它通过这种互连网络能实现高达 60Gbps 的交换速度。

在先进设计中，会将数据报分割成固定长度的信元，通过交换结构进行交换，提升交换效率。

交叉开关是一种严格的无阻塞交换，只要目的输出端口可用，数据包就能通过交换，不会因交换结构资源耗尽而被阻塞。不过，大规模实现高速交叉开关矩阵可能困难且昂贵，因此存在一些权衡解决方案（如阻塞交换结构、可重排无阻塞交换等），这些详细内容超出了本课程范围，高速、低成本的交换技术仍是研究前沿。

队列

路由器的输入输出数据包有可能一下非常多，因此需要Buffer与队列来缓冲处理。在缓冲处理时，需要用相应的调度策略（Scheduling discipline）来对入队出队进行管控。

输入端口队列（Input port queue）

当交换结构（switch fabric）的处理速度慢于所有输入端口的总数据传输速度时，输入端口就会出现排队现象。此时就需要输入队列。输入端口队列通常是一个FIFO。如下图所示。

image-20251013133743938

输入端口队列会出现头阻塞（Head-of-the-Line, HOL）现象，在队列前端的数据包会阻碍队列中后面的数据包向前传输。哪怕后面的数据包已经可以可以被直接传输，也得等前端的数据包完成传输。例如上图，两个红色数据包在竞争一个输出端口，因此红色数据包产生了阻塞；对于下侧的绿色数据包，尽管它的目标不是竞争端口，它也需要等红色输出包传完才能传输，它还是受到了端口竞争的影响。

对于采用FIFO输入缓冲的情况，当数据包的目的地址是均匀分布的，且网络中链路数量很大时，这种头阻塞会导致交换结构的吞吐量被限制在总容量的58.6%左右。这意味着即使硬件理论上能处理更多数据，头阻塞会让实际有效吞吐量大幅下降。

一个头阻塞容量计算的例子

假设现在有一个2in 2out的路由器，数据包目的地是均匀分布的。那么它的平均吞吐量是理论最大吞吐量的百分之多少？

对于2in 2out路由，有以下四种情况：

  • In1的数据包想要传递给Out1，In2的数据包想要传递给Out2，无阻塞，实际吞吐量=最大吞吐量
  • In1的数据包想要传递给Out2，In2的数据包想要传递给Out1，无阻塞，实际吞吐量=最大吞吐量
  • In1的数据包想要传递给Out1，In2的数据包想要传递给Out1，阻塞需排队，吞吐量=50%最大吞吐量
  • In1的数据包想要传递给Out2，In2的数据包想要传递给Out2，阻塞需排队，吞吐量=50%最大吞吐量

对于均匀分布，这四种情况出现的概率均为25%，因此最终的平均吞吐量是

虚拟输出队列（Virtual output queue）

image-20251006191240050

为解决 HOL 阻塞问题，提出了虚拟输出队列技术。在输入端口为每个输出端口设置单独的队列。

上图展示了 VOQ 的结构，输入端口的数据包会根据目的输出端口进入相应的虚拟队列，然后通过交叉开关（Crossbar Switch）进行交换，交叉开关由集中调度器（Centralized Scheduler）进行调度，从而避免 HOL 阻塞。不过，这种解决方案成本可能很高。

输出端口队列（Output queue）

虚拟输出队列的方式因其过高的硬件成本和很高的队列管理复杂性，在大型交换机上并不适用。因此提出了输出端口队列。如果我们的交换结构（Switch fabric）工作速度足够快，可以同时允许多个数据包交换到同一端口，此时在输出端口设置buffer，让同时被交换过来的数据包队列传输。

image-20251013172806780

例如上图，有三个数据包同时发给输出端口1，交换结构可以让他们同时抵达；此时输出端口1把它们放进队列中，挨个输出。

这种方式在输出Buffer排队时，会造成队列延迟（Queuing Delay）；在输出Buffer溢出时，会造成丢包。

可以将多种Buffer自由组合起来，来满足特定的需求，这被称为combined input-output queue (CIOQ) 。队列的组合是IO端口速度、交换结构带宽、阻塞性能间的平衡。

队列调度算法的作用（Queue Algorithms）

队列调度算法是另一种解决头阻塞的方案，不妨想象以下场景，在IN1端口中有两个数据包，目的地分别是OUT2和OUT4；同时IN2有一个数据包需要去OUT4，如下图。

image-20251013173619260

如果保持原始顺序，则一次传输周期内只能传输一个到OUT4的包。但是如果队列调度器可以执行乱序调度，发现IN1的第二个包想去OUT2，那么第一次传输的时候就让IN2的包去OUT4，同时IN1要去OUT2的包先传输。这样就能达到更大的吞吐量。

路由算法

引入

路由算法要干什么

路由算法本质是让路由器了解链路的信息，以选择最合适的抵达目的地的路径。链路的当前状态信息是通过路由协议来分发的，分发的方式一般是广播或泛洪。交换信息的频率会直接影响网络的性能。

路由算法根据路由协议搞来的信息，根据不同的度量生成可能的路径。路由算法的路径有两个核心的“问题”：

  • 如何找到最短路径？
  • 最短路径是否一定就是最优的？如果不是，还能做些什么？（例如使用路径代价做为替代度量）

路由的两种控制方式

路由的控制方式主要可以分为：

  • 集中式路由（Centralized Routing）：
    • 所有的路由由一个中央控制器决定，或者所有路由器做出相同的一组决策。所有的链路状态信息都被发送到中央控制器或所有路由器都共享一样的状态信息。
    • 这种路由难以适应频繁的网络拓扑变化，尤其是在大型网络中。因为中央控制器需要收集全网的状态信息才能做出决策，当网络拓扑（比如链路断开、新增节点等）频繁变化时，中央控制器收集信息和调整路由的速度会跟不上变化，导致路由决策滞后。
    • 不具备可扩展性。随着网络规模（节点数、链路数等）的扩大，中央控制器需要处理的状态信息呈指数级增长，其计算和管理负担会急剧加重，无法高效地为大规模网络提供路由服务
  • 分布式路由（Distributed Routing）：
    • 路由器使用分布式算法来决定路由。每个路由器会根据自身收集到的周边网络信息，结合分布式算法（如距离矢量算法、链路状态算法等），独立或与相邻路由器协作进行路由决策。
    • 路由器通过与相邻的路由器通信，共享各自了解的网络状态信息，从而构建出对网络的整体认知。
    • 能够适应拓扑和其他变化，不过不一定能非常快速地适应。
    • 具有更强的可扩展性。由于路由决策是分布式进行的，每个路由器只需处理局部的网络信息，当网络规模扩大时，新增的路由器可以通过与相邻节点交互，轻松融入现有路由系统，不会像集中式路由那样出现中央节点的瓶颈问题。

寻路算法旨在根据已知的网络拓补，寻找到去往目的地的最小成本。这个成本通常是路径长度或跳数。

  • 针对集中路由这种每个路由器都有完整拓补，所有路由器都做出同一组决策的，有迪杰斯特拉算法（Dijkstra Algorithm）算法来找到最短路径。
  • 而针对于每个路由器只有邻接拓补的的分布式路由，通常使用距离向量来寻找最短路径，其代表是贝尔曼-福特（Bellman-Ford）算法。

迪杰斯特拉算法（Dijkstra Algorithm）

引入

迪杰斯特拉算法认为网络拓补是已知的，并为每条路径标记一个链路成本。如下图所示

image-20251016153925347

其优化目标是寻找从源到目的地的最小成本路径。Dijkstra算法的约束条件是链路成本必须是正数，如果有负成本链路，那么这个算法求到的结果并非最优。

迪杰斯特拉算法是一种贪心算法(greedy algorithm)，每一跳都在选择最小成本路径。

迪杰斯特拉算法

Dijkstra算法可视化网站：Dijkstra(迪杰斯特拉)最短路径算法可视化

Dijkstra算法维护一张表，这张表中记录着每经过一次迭代（增加一跳），可以找到的通向某个节点的最短路径。已经找到最短路径的节点被称为“已着色（coloured）”。Dijkstra算法会逐一着色网络中的节点，直到目标节点的最短路径被找到或所有节点被着色。

通过这个例子来看Dijkstra算法，寻找下图节点u到z的最短路径。

image-20251016153925347

1.首先构建Dijkstra的表，表头如下：

Step N’ D(v),p(v) D(x),p(x) D(w),p(w) D(y),p(y) D(z),p(z)
  • Step代表此时是第几次迭代
  • $N’$代表当前已着色的节点的集合。
  • D(xx),p(xx)分别表示去往点xx的当前成本和当前节点名称。例如从u到v总成本为2，就记作$2,u$。如果从当前点无法到达，则记为无穷。例如从u无法一步到达y，则给$D(y),p(y)$记为无穷。

2. 首先进行初始化，也就是Step 0：

从点u看出去，点v可以通过成本为2的路径到达；点x可以通过一条成本为1的路径到达；点w可以通过一条成本为5的路径到达。其余点不可达，因此记作：
| Step | N’ | D(v),p(v) | D(x),p(x) | D(w),p(w) | D(y),p(y) | D(z),p(z) |
| :—: | :—: | :———-: | :———-: | :———-: | :———-: | :———-: |
| 0 | u | 2,u | 1,u | 5,u | $\infty$ | $\infty$ |

3. 选择邻接最短路径，迭代到Step1：

image-20251016161904252

从u到下一跳的最优路径是x，因此前往x将x着色。到达x之后，又有v,w,y三个未着色节点可达。

在更新表时，需要对比路径成本来决定是否更新。例如uv的总成本是2，uxv总成本是3，因此不对它更新。uw的总成本是5，而uxw的总成本是4，因此对它更新为$4,x$。

对于已经着色的节点，表不再更新。即，这一步着色了x，$D(x),p(x)$就不再更新了

因此更新这张表为

Step N’ D(v),p(v) D(x),p(x) D(w),p(w) D(y),p(y) D(z),p(z)
0 u 2,u 1,u 5,u $\infty$ $\infty$
1 ux 2,u 4,x 2,x $\infty$

4.再次选择最短路径，进行迭代到Step2

此时会发现$2,u$和$2,x$的路径成本都是2，他们一样小。此时可以随机选择一个进入下一步。这里以选择$2,x$为例继续做。（选择$2,u$也是可以的）。

在选择$2,x$之后，前往y对y进行着色

image-20251016163042568

同时将表更新为：
| Step | N’ | D(v),p(v) | D(x),p(x) | D(w),p(w) | D(y),p(y) | D(z),p(z) |
| :—: | :—: | :———-: | :———-: | :———-: | :———-: | :———-: |
| 0 | u | 2,u | 1,u | 5,u | $\infty$ | $\infty$ |
| 1 | ux | 2,u | | 4,x | 2,x | $\infty$ |
| 2 | uxy | 2,u | | 3,y | | 4,y |

5.再次迭代到Step3

此时表中路径成本最小的是$2,u$，因此触发路径回溯，不走y了，走v继续推。把v也加入已着色集合。

image-20251016163806877

从v可以到uxwy，其中未着色的只剩w了，因此检查去w的成本为$5,v$，相较于之前的$3,y$竞争力不够，不更新。此时z变成了不可达，相较于$4,y$也不够，不更新。

Step N’ D(v),p(v) D(x),p(x) D(w),p(w) D(y),p(y) D(z),p(z)
0 u 2,u 1,u 5,u $\infty$ $\infty$
1 ux 2,u 4,x 2,x $\infty$
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y

6.回溯失败，继续走原来的路迭代到step4

此时发现成本最低的仍旧是$3,y$到节点w。因此还是走之前的路去染色w：

image-20251016163927758

到了w之后，前往未染色节点z的成本是5，那w到z的成本就是3+5=8，$8,w$相对于$4,y$没有竞争力。因此保留4,y。

Step N’ D(v),p(v) D(x),p(x) D(w),p(w) D(y),p(y) D(z),p(z)
0 u 2,u 1,u 5,u $\infty$ $\infty$
1 ux 2,u 4,x 2,x $\infty$
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
  1. 所有节点着色完成，求得最终答案

此时走$4,y$去染色z，最终得到路径如下：

image-20251016164309083

表格也最后定格为：
| Step | N’ | D(v),p(v) | D(x),p(x) | D(w),p(w) | D(y),p(y) | D(z),p(z) |
| :—: | :——: | :———-: | :———-: | :———-: | :———-: | :———-: |
| 0 | u | 2,u | 1,u | 5,u | $\infty$ | $\infty$ |
| 1 | ux | 2,u | | 4,x | 2,x | $\infty$ |
| 2 | uxy | 2,u | | 3,y | | 4,y |
| 3 | uxyv | | | 3,y | | 4,y |
| 4 | uxyvw | | | | | 4,y |
| 5 | uxyvwz | | | | | |

各条最下面的$D(xx),p(xx)$就记录着从u节点去往这个节点的成本与上一跳地址：

  • 对于v，最小成本是2，上一跳是u
  • 对于x，最小成本是1，上一跳是u
  • 对于y，最小成本是2，上一跳是x
  • 对于w，最小成本是3，上一跳是y
  • 对于z，最小成本是4，上一跳是y

这样只要是被着色的节点，都知道了去往它们的最优路径。例如去y的最优径是从x到y，从u到x，即{uxy}。

image-20251016165459467

在这个例子中，我们的目标是寻找去z的路径，在寻找过程中是将所有节点都染色了。如果目标节点是y，则可能迭代到选择 $2,x$就停止了。也有可能我们想知道去拓补给所有节点的最短路径，那就和这个例子一样，迭代到所有节点都被染色再停止。

Dijkstra的伪代码表达

重新捋一捋Dijkstra算法的流程：

  1. 初始化时，检查所有节点，如果与源节点领接则邻接节点的cost，将其添加到表中
  2. 从表中选择路径最短的一个节点，将其着色（着色的添加到着色节点集N’中）
  3. 遍历所有未着色节点，如果与已着色节点领接则邻接，则将cost添加到表中
  4. 重复步骤2，直到所有节点被着色

这个过程可以用伪代码表达：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化
N' = {u}  // u为源节点，N'是已着色节点集合
for all nodes v://v代表所有节点
    if v adjacent to u :
        then D(v) = c(u, v)  // D(v)为源到v的当前路径成本
    else:
        D(v) = ∞  // 非邻居节点初始成本为无穷大

// 循环计算最短路径
Loop:
    find w not in N' such that D(w) is a minimum//遍历所有未着色节点，找到最小cost
    add w to N'//前往着色
    update D(v) for all v adjacent to w and not in N' : D(v) = min( D(v), D(w) + c(w,v) ) 
until all nodes in N'
  • (c(x,y))：节点x到节点y的链路成本；若不是直接邻居，(c(x,y) = \infty)（无穷大）。
  • (D(v))：从源节点到节点v的当前路径成本。
  • (p(v))：从源节点到节点v的路径上的前驱节点（用于记录路径）。
  • (\mathbf{N’})：已找到最短路径的节点集合。

这个代码

为什么迪杰斯特拉算法无法处理负权边

迪杰斯特拉算法无法处理负代价的情况是由于它是贪心算法导致的。比如下图，一旦迪杰斯特拉算法确定了A-C的代价比A-B小，它就会定下来从A-C的代价就是3了；全然不顾从A-B-C的代价是2。

image-20251017020222528

距离向量算法（Distance Vector Algorithm）

引入

距离向量算法的核心是：某一节点并不知道所有节点的拓补与路径代价。但是去往某一节点的路径代价由邻居转述给他，基于此，它计算自己去某一节点的路径代价。

如果用$d_x(y)$来表示从节点x到y的最少代价，$c(x,v)$表示节点x到v的代价，$d_v(y)$表示节点v到y的最少代价，则距离向量算法就是在寻找

这个方程被称为贝尔曼-福特方程（Bellman-Ford equation）。因此在讨论DV算法时，经典的例子就是贝尔曼-福特算法。

相较于Dijkstra算法，贝尔曼福特算法不再限制每条路线的代价必须为正数，可以引入负代价。

贝尔曼-福特算法（Bellman-Ford Algorithm）

贝尔曼-福特算法遵循如下流程：

  1. 初始化距离：设起始点距离为0，其他点是无穷大
  2. 遍历优化：节点将新的距离向量发送给直接邻居（通过本地链路）。
  3. 遍历优化：节点从邻居处收到消息时，与自己的缓存比较，如果更优则更新换船
  4. 遍历优化：只要自己有更新，就要对外发送一次，重复发送-接收，直到迭代中无更新。

如果是标准的贝尔曼-福特算法，其步骤是这样的：

  1. 初始化距离：设起始点距离为0，其他点是无穷大
  2. 遍历优化：遍历所有的边，如果没有节点更新自己的路径了，则算法收敛；如果一直有节点更新路径，最多更新V-1轮，其中V是节点个数。
  3. 负权环检测：如果更新到了V-1轮，则额外进行一次遍历，如果这次遍历还可以更新路径，则说明节点中有负代价的路径构成了环，这个环会导致代价无限缩小。

但是对于路由而言，不需要遵循非常标准的遍历操作，而是对邻居进行广播更新，相当于每一轮遍历都是从有更新的节点开始。这样的遍历可以得到更快的收敛速度。

贝尔曼-福特算法的例子

通过这个例子来看看BFA，对于下面这个拓补，寻找从每个节点到Node 6的成本最小路径（也可以说是从Node 6到每个节点的最小成本路径）：

image-20251017011648504

1. 初始化路径表

用（前一跳，成本）来记录每个节点去6的代价。首先，假设从6出发，去每个节点的成本都未更新，算法维护的表如下：

Iteration Node 1 Node 2 Node 3 Node 4 Node 5
Initial $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$

2.第一次迭代

首先，节点6告诉它的邻居：我到Node6的成本是0。这会更新Node3和Node5的表。

image-20251017111053252

Iteration Node 1 Node 2 Node 3 Node 4 Node 5
Initial $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$
1 $(-1,\infty)$ $(-1,\infty)$ $(6,1)$ $(-1,\infty)$ $(6,2)$

对于节点3，去Node6的下一跳是6，代价是1，记作（6,1）。节点5同理。此时Node3和Node5有了去Node6的路：

image-20251017111107116

3.第二次迭代

在3和5收到更新后，它会立刻通知自己的邻居：

image-20251017111146460

此时Node1被告知Node3去Node6的代价是1，而Node3到Node1的代价是2，因此Node1把自己去Node6的下一跳记为3，代价是1+2=3，表更新为（3,3）；Node4同时收到了2条消息，如果从Node3走是（3,3），如果从Node5走是（5,5），取代价小的保留；其余同理。最终表迭代为：

Iteration Node 1 Node 2 Node 3 Node 4 Node 5
Initial $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$
1 $(-1,\infty)$ $(-1,\infty)$ $(6,1)$ $(-1,\infty)$ $(6,2)$
2 $(3,3)$ $(5,6)$ $(6,1)$ $(3,3)$ $(6,2)$

此时所有Node都有了去节点6的路（但还可以迭代，不是最优的）

image-20251017111230463

4.第三次迭代

这一次1 2 4会分别通知自己的邻居，广播消息有点多，挨个看。

首先是Node1，它发送（3,3），它的领接分别存储了：Node3(6,1)，Node(3,3)，Node2(5,6)；分别与经过Node1的(1,5) (1,8) (1,9)进行比较。不更新

image-20251017111327303

最后来看Node4，它发送(3,3)，它的邻接分别存储了：Node5(6,2)，Node3(6,1)，Node1(3,3)，Node2(4,4)。它们分别对比了(4,6) (4,5) (4,8) (4,4)与自己的，Node2发现(4,4)比自己的好，故更新为(4,4)

image-20251017111627423

Iteration Node 1 Node 2 Node 3 Node 4 Node 5
Initial $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$ $(-1,\infty)$
1 $(-1,\infty)$ $(-1,\infty)$ $(6,1)$ $(-1,\infty)$ $(6,2)$
2 $(3,3)$ $(5,6)$ $(6,1)$ $(3,3)$ $(6,2)$
3 $(3,3)$ $(4,4)$ $(6,1)$ $(3,3)$ $(6,2)$

最后来看Node2，它广播更新了的(4,4)，它的邻接分别存储了：Node5(6,2)，Node4(3,3)，Node1(3,3)。它们分别对比了(2,8) (2,5) (2,7)，发现没有优势，不更新。

image-20251017111927081

4.终止迭代

此时没有任何一个被通知的节点发生更新，故向邻居的广播到此结束，算法收敛。

其实老师这个PPT这个地方我个人认为有问题：最后一次迭代应该是1对42广播，4对12广播，2对14广播。这3组广播里面2会因为4的广播产生更新，因此2再对15广播。15没有任何更新，故算法收敛，而非PPT那样从邻居那里全部接收一次。这个地方的笔记是按照我的理解写的，而非老师的PPT。私以为PPT这个地方看个乐呵就好，还是以后面RIP协议的更新为准

贝尔曼-福特：好消息快速传播特性

考虑这个拓补，当XY之间的链路成本由4变成1时：

image-20251017110353591

去往X的路由会发生这些更新：

  1. 在$t_0$时，Y发现了链路成本发生变换，更新它的表为（X,1），并通知X Z。
  2. 在$t_1$时，Z收到Y的通知，并更新它的表为（Y,2），并通知X Y
  3. X Y无更新，算法收敛。

仅仅需要3次通知，算法就完成了收敛

贝尔曼-福特：坏消息慢速传播特性

再次考虑这个拓补，当XY之间的链路成本由4变成60时：

image-20251017112307233

  1. 原来X–Z的直接代价是 5所以 Z曾向 Y 宣告它到 X 的距离为 5。
  2. 在Y节点的直连cost变成60后，Z发送的表内包含自己到X的距离是5，节点 Y会认为经 Z 到 X 是最佳路径，总距离为 6，但这是错误的。
  3. 接着，节点 Z 会更新到 X 的距离为 7，路径是经 Y。
  4. 如此迭代持续进行，算法需要 44 次迭代才能稳定。

这里体现了 “坏消息传播慢（Bad news travels slowly）”，也就是著名的 “无穷计数（count to infinity）” 问题。当网络拓扑变化（如链路成本增加），节点间信息更新滞后，导致错误路由信息不断传播，需多次迭代才会收敛到正确状态。

通过毒性逆转解决坏消息传播慢（poisoned reverse）

若 Z 经 Y 路由到 X，Z在给Y广播时会告知 Y 自己到 X 的距离是无穷大，这样 Y 就不会经 Z 路由到 X。通过这种 “欺骗”，阻止错误的路由选择。

换句话说，Z 对 Y “毒性化” 其到 X 的距离，对于其他相邻节点，Z 仍会如实告知到 X 的距离。

然而，毒性逆转是有局限性的，例如下面这个拓补，当XY之间距离变成60时：

image-20251017113256906

  1. 从Z到X原本存储的是(A,6)。由于毒性逆转，Z 会告知 A，自己到 X 的距离是无穷大，A同样也会毒性化告知 Y，自己到 X 的距离是无穷大。
  2. 但 Z 会告知 Y，自己到 X 的距离是 6
  3. Y 会将自己到 X 的距离更新为 9
  4. A 会把自己到 X 的距离更新为 10
  5. Z 会将自己到 X 的距离更新为 11
  6. Y 又会把自己到 X 的距离更新为 14…… 如此循环

贝尔曼-福特：无法处理负权环

考虑这个例子，下图中，从1经过2,3再回到1，总cost是负数。这被称为负权环

image-20251103134724042

  • 初始路径：0→1，权重 3。
  • 绕环 1 次：0→1→2→3→1，权重 3 + 2 + (-8) + 2 = -1（更短）。
  • 绕环 2 次：0→1→2→3→1→2→3→1，权重 -1 + 2 + (-8) + 2 = -5（更短）。
  • 绕环次数越多，权重越小（可无限趋近于负无穷），贝尔曼-福特算法不可解。

贝尔曼-福特算法的代码实现：

上面贝尔曼-福特算法在代码上实现可以分为以下几步：

  1. 初始化：将除了源节点的所有节点的上一跳设置为-1，成本设置为$\infty$；源节点成本是0，上一跳是自身。
  2. 遍历所有节点，使得每个节点获取一次邻接节点的表，如果有更优的去往源节点的方式，则更新自己的表。
  3. 重复N-1次步骤2，算法一定会在n-1次或之前收敛。
  4. 再多进行一次遍历，如果第N次遍历仍可以更新，那么就存在负权环，无法通过该算法找到最优解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//初始化
dist[1..v] = ∞ 		// 所有节点初始成本为无穷大，v表示除了源节点的节点集合
prev[1..v] = -1      // 所有节点初始上一跳为-1（无来源）
dist[s] = 0          // 源节点成本设为0
prev[s] = s          // 源节点上一跳设为自身
// 2. 重复n-1次遍历，尝试更新所有节点的成本和上一跳
for i from 1 to n-1:
    for each u in V:
            for each adjacency(u):
                if dist[u] + weight(u, v) < dist[v]: // 若通过u到v的路径更优，则更新v的成本和上一跳
                    dist[v] = dist[u] + weight(u, v)
                    prev[v] = u

// 4. 第n次遍历：检测负权环
    has_negative_cycle = false
    for each u in V:
        for each adjacency(u):
            if dist[u] + weight(u, v) < dist[v]:
                has_negative_cycle = true
                break
        if has_negative_cycle:
            break
    
if has_negative_cycle:
    return false
else:
    return (dist[], prev[])// 返回各节点的最短成本和上一跳路径

路由协议

引入

分层路由的概念（Hierarchical Routing）

互联网规模极大，单一路由协议无法完成所有路由器路由表的更新任务，因此需要分层管理。

就像是划分行政规划一样，我们将一个巨大的网络划分成不同的自治系统（Autonomous Systems，AS）。AS 是由单个组织管理的一组路由器或网络(例如某个运营商或者云服务商)，每个 AS 通过16 位的 AS 编号唯一标识。

image-20251013184157286

每个AS间使用网关路由器（Gateway Router）连接，其负责 AS 之间的路由转发。

这样，路由就被分为了两种：

  • 域内路由（intradomain routing）：AS 内部的路由，由内部路由协议（如 RIP、OSPF）负责。这些内部路由协议也称“内部网关协议（Interior Gateway Protocol，IGP）”
  • 域间路由（interdomain routing）：AS 之间的路由，由外部路由协议（如 BGP）负责。这些外部路由协议又称“外部网关协议（Exterior Gateway Protocol, EGP）”

网关路由器需要同时执行内部网关协议与外部网关协议，因为它既是连接不同AS的网关，也是某一AS中的一个成员。

image-20251013185822368

EGP除了连接各个AS的网关之外，对于一个AS内部，其也需要知道走哪个网关出去才能最好地到达目的地，这也是EGP需要探明的东西。

对于域内选择网关出口的问题，有一种热土豆路由法（Hot potato routing）：直接把数据发送给距离自己最近的网关。就像数据是烫手土豆一样，管他3721往能丢的地方丢

两种路由协议的类型

路由协议总体可以分为：

  • 距离矢量路由协议：核心基于距离向量算法，例如贝尔曼-福特算法，仅通过邻居的距离信息更新路由表。此时路由器间沟通的是各自的路由表。常见的协议有OSPF，IS-IS
  • 链路状态协议：根据诸如迪杰斯特拉算法这样的维护全局链路状态的算法，以全局拓补的视角做出路由决策。此时路由器间沟通的是链路拓补信息。常见的协议有RIP，BGP

经典路由协议RIP、OSPF、BGP

这三大经典路由协议中：

  • 服务域内路由：RIP(Routing Information Protocol)，OSPF(Open Shortest Path First Protocol)
  • 服务域间路由：BGP(Border Gateway Protocol)

下面将逐个介绍

RIP协议

引入-RIP

RIP（Routing Information Protocol）全称路由信息协议。它以路由的跳数作为度量，最大的路由跳数被限制在15跳之内，因此它只适合小型网络（本地网络）。

如果RIP协议记录某一目标位16跳，则表明目标不可达（跳数无穷大）。

RIP因其简单，在小型网络中资源占用少，至今仍在使用。

RIP协议详细内容

  • 每个路由器需要每隔30秒向邻近的路由广播自己的路由表信息给相邻路由器。路由表中的每条记录包含目的网络地址、下一跳路由器地址以及到目的网络的跳数等信息。
  • 当一个路由器接收到相邻路由器发送的路由表时，会根据距离向量算法对自己的路由表进行更新。具体来说，如果接收到的关于某个目的网络的路由信息中，跳数比自己路由表中记录的跳数更小，或者自己的路由表中原本没有该目的网络的记录，就会更新自己的路由表，将该目的网络的信息替换为新接收到的更优信息，并将下一跳设置为发送该路由信息的相邻路由器 。
  • 每过30秒对所有邻居进行一次广播。
  • 如果一个邻居180秒都没给自己广播消息，则认为连接已失效，将其跳数标记为16。

优缺点

  • 优点：
    • 实现简单：算法逻辑相对简单，易于理解和实现，对路由器的硬件要求较低，适合小型网络使用 。
    • 占用资源少：在小型网络中，定期交换的路由表信息规模较小，不会占用过多的网络带宽和路由器的计算资源。
  • 缺点：
    • 收敛速度慢：在网络拓扑变化频繁的情况下，RIP 协议的收敛速度较慢，可能导致网络在一段时间内出现路由错误，影响数据传输 。
    • 跳数限制：最大跳数为 15 的限制，使得 RIP 协议不适合应用于大型网络，限制了网络的规模和扩展能力 。
    • 路由信息不准确：RIP 协议只考虑跳数这一个因素来衡量路径优劣，没有考虑链路带宽、延迟、负载等其他重要因素，可能导致选择的路径并非最优路径 。例如，一条路径只有1跳但是仅有100kbps的带宽，另一条路径有2跳但是有10Gbps的带宽，RIP还是会选择100kbps的那个。

一个RIP的例子

案例来自：【网络数据通信基础】13 - 路由基础 - RIP原理_哔哩哔哩_bilibili。华为比南洋理工的老师讲得好。

考虑这个拓补，首先ABC 3个路由器根据直连信息可以构建出自己的直连路由表：

image-20251017144103223

下表是ABC三个路由器的初始路由表：

网段(A) 出口(A) 跳数(A) 网段(B) 下一跳(B) 出口(B) 网段(C) 出口(C) 跳数(C)
10.0.1.0 GE0/0/0 0 10.0.2.0 GE0/0/0 0 10.0.3.0 GE0/0/0 0
10.0.2.0 GE0/0/1 0 10.0.3.0 GE0/0/1 0 10.0.4.0 GE0/0/1 0

当A通过GE0/0/0和GE0/0/1广播自己路由表时，B路由会学习到10.0.1.0网段可以通过A走，跳数为1。
| 网段(A) | 出口(A) | 跳数(A) | 网段(B) | 下一跳(B) | 出口(B) | 网段(C) | 出口(C) | 跳数(C) |
| :———: | :——-: | :——-: | :———: | :———-: | :——-: | :———: | :——-: | :——-: |
| 10.0.1.0 | GE0/0/0 | 0 | 10.0.2.0 | GE0/0/0 | 0 | 10.0.3.0 | GE0/0/0 | 0 |
| 10.0.2.0 | GE0/0/1 | 0 | 10.0.3.0 | GE0/0/1 | 0 | 10.0.4.0 | GE0/0/1 | 0 |
| | | | 10.0.1.0 | GE0/0/0 | 1 | | | |

当B通过GE0/0/0和GE0/0/1广播自己路由表时，A路由会学习到10.0.3.0网段可以通过B走，跳数为1；C路由会学习到10.0.2.0和10.0.1.0可以通过B走，跳数分别为1和2。
| 网段(A) | 出口(A) | 跳数(A) | 网段(B) | 下一跳(B) | 出口(B) | 网段(C) | 出口(C) | 跳数(C) |
| :———: | :——-: | :——-: | :———: | :———-: | :——-: | :———: | :——-: | :——-: |
| 10.0.1.0 | GE0/0/0 | 0 | 10.0.2.0 | GE0/0/0 | 0 | 10.0.3.0 | GE0/0/0 | 0 |
| 10.0.2.0 | GE0/0/1 | 0 | 10.0.3.0 | GE0/0/1 | 0 | 10.0.4.0 | GE0/0/1 | 0 |
| 10.0.3.0 | GE0/0/1 | 1 | 10.0.1.0 | GE0/0/0 | 1 | 10.0.2.0 | GE0/0/0 | 1 |
| | | | | | | 10.0.1.0 | GE0/0/0 | 2 |

当C广播自己路由表时，B检查发现10.0.4.0是自己没有的，可以通过C走，跳数为1：
| 网段(A) | 出口(A) | 跳数(A) | 网段(B) | 下一跳(B) | 出口(B) | 网段(C) | 出口(C) | 跳数(C) |
| :———: | :——-: | :——-: | :———: | :———-: | :——-: | :———: | :——-: | :——-: |
| 10.0.1.0 | GE0/0/0 | 0 | 10.0.2.0 | GE0/0/0 | 0 | 10.0.3.0 | GE0/0/0 | 0 |
| 10.0.2.0 | GE0/0/1 | 0 | 10.0.3.0 | GE0/0/1 | 0 | 10.0.4.0 | GE0/0/1 | 0 |
| 10.0.3.0 | GE0/0/1 | 1 | 10.0.1.0 | GE0/0/0 | 1 | 10.0.2.0 | GE0/0/0 | 1 |
| | | | 10.0.4.0 | GE0/0/1 | 1 | 10.0.1.0 | GE0/0/0 | 2 |

下一次A广播，无更新；下一次B广播，A会学习到10.0.4.0可以通过B走，跳数为2
| 网段(A) | 出口(A) | 跳数(A) | 网段(B) | 下一跳(B) | 出口(B) | 网段(C) | 出口(C) | 跳数(C) |
| :———: | :——-: | :——-: | :———: | :———-: | :——-: | :———: | :——-: | :——-: |
| 10.0.1.0 | GE0/0/0 | 0 | 10.0.2.0 | GE0/0/0 | 0 | 10.0.3.0 | GE0/0/0 | 0 |
| 10.0.2.0 | GE0/0/1 | 0 | 10.0.3.0 | GE0/0/1 | 0 | 10.0.4.0 | GE0/0/1 | 0 |
| 10.0.3.0 | GE0/0/1 | 1 | 10.0.1.0 | GE0/0/0 | 1 | 10.0.2.0 | GE0/0/0 | 1 |
| 10.0.4.0 | GE0/0/1 | 2 | 10.0.4.0 | GE0/0/1 | 1 | 10.0.1.0 | GE0/0/0 | 2 |

后面每30s进行一次广播，但是不会有更新发生了，RIP收敛

RIP环问题及其解决方案

还是看到这个例子，假设现在10.0.4.0网段故障不可达，C会删掉10.0.4.0的路由。假设C还没有到自己的泛洪时间点，但是B开始了自己的泛洪，C学习到了从B可以经过2跳到达10.0.4.0，下一跳是B。

image-20251017144103223

那么此时如果B内有一个计算机尝试往10.0.4.0网段发送消息，就会发生B发给C，C又发给B，B又发给C的现象，这就是RIP环。

要解决RIP环，可以有这些方式：

  • 定义最大度量，防止计数到无穷大：RIP 使用跳数作为度量，最大允许跳数为 15，这样可以防止路由表无限增长，及时终止错误路径传播。这也限制了RIP只能在小范围网络中使用。
  • 水平分割（Split Horizon）：路由器不会将某个接口学到的路由信息再通过该接口发送出去。也就是说，B是GE0/0/1学到的10.0.4.0的路径，它不会在这个口上发送含10.0.4.0的路由表。
  • 路由中毒&毒性逆转（Route Poisoning & Poison Reverse）：一旦某条路由不可达，更新源立即将其度量设置为 16跳并广播出去，而不是直接将它删掉。令居在收到这条中毒路由后，也立在自己路由表内将其标记为16跳，并泛洪一份自己的路由表。这相当于发了一条“有毒”的路由，去让其他路由的表也“中毒”。此时如果再收到这条路由的其他更新，它会不予理会，直到邻居路由器把中毒路由泛洪回原路由器，告诉它：“我也认为这条路由不可达”，这被称为毒性逆转。（注：毒性路由与水平分割不能同时开启）。
  • 抑制计时器（Hold-Down Timer）：路由器在检测到某条路由失效后，会暂时忽略任何关于该路由的更新，防止错误信息快速传播，等待稳定的正确信息。
  • 触发更新（Triggered Update）：当路由表发生变化时，立即发送更新信息，而不是等周期性更新，以此加快收敛速度，减少错误路由的持续时间。

这些解决RIP环的方式在各家不同的路由器中支持程度不同，也有不同的设置方式。

OSPF协议

引入-OSPF

OSPF全称开放最短路径优先（Open Shortest Path First）。OSPF可以让每个路由器学习完整的网络拓补，构建出一个相同的数据库，并允许每个路由器构建以自己为根的最短路径树。其设计目的是解决 RIP 协议的缺陷（如 RIP 跳数限制、收敛慢等问题）。

OSPF相较于RIP更复杂且资源消耗更大，但当网络发生故障时，OSPF比RIP收敛速度更快。除此之外，OSPF相较于RIP，可以支持更大型的网络。

OSPF的特点是：

  • 允许构建到目的地的多条路由。
  • 路由消息中会包含子网掩码，因此它支持CIDR（RIP v2的协议也支持，v1不支持）
  • 更灵活的路由链路范围（不局限于15跳，可以从1到2^16跳）
  • 允许在多个等成本的路径上分配流量（对等价路由进行负载分担）。
  • 提供身份认证，仅与信任的邻居交换信息。
  • 使用区域概念（notion of area）将AS划分为多个区域
  • OSPF的成本是没有预先约定的，可以根据网络情况自定义成本

由于OSPF维护的是链路信息，由路由器根据学习的状态自己计算出路由，因此它泛洪的更新信息就是它自己拿到的一手消息，而非RIP那样自己计算之后的结果。

链路状态（Link state）：对接口及其与邻居路由器关系的描述，包含以下关键信息：

  • 接口的 IP 地址 / 掩码；
  • 接口连接的网络类型；
  • 链路的度量值（cost，用于衡量链路的 “开销”，如带宽、延迟等，开销越小路径越优）。

OSPF中，每个路由器以自身为根，基于链路状态数据库构建最短路径树。的SPF算法(Shortest Path First Algorithm)是多种多样的，可以根据不同场景制定不同的算法，Dijkstra算法就是选择之一。

OSPF目前针对IPv4的版本是V2，针对IPv6的版本是V3。

OSPF基本概念

链路状态数据库：所有链路状态信息的集合。

Router ID：OSPF在一个AS内，使用Router ID来标识路由器，Router ID是一个32字节的无符号整数（也就是说Router ID和IP地址格式是一样的）。通常，将路由器的WAN口IP地址配置为Router ID来标识一台路由器。有的品牌的路由器会默认使用路由器Loopback端口中IP地址最大的一项作为Router ID，若没有Loopback端口，则使用物理端口最大IP。

Loopback口（本地环回接口）是路由器中的一种虚拟接口，它不像物理端口那样依赖实际的硬件连接，而是由软件逻辑创建的，常用于设备的“身份证”IP地址。它的状态始终是“up”，即使没有任何物理链路连接，也不会掉线。运维人员可通过Loopback地址远程访问设备，不受物理端口变化影响。

在家用PC中，Loopback地址通常是127.0.0.1；而路由器的Loopback地址可以自定义，并非固定的127.0.0.1，因此其可以被用作网络标识、管理入口、路由协议ID等。

区域（Area）：OSPF 通过区域（Area）将自治系统（AS）划分为多个逻辑子网。区域用 32 位的区域 ID 标识（格式与 IP 地址相同，如 0.0.0.0 表示骨干区域）

度量值（Cost）：用于衡量链路的 “开销”，是路径选择的核心依据（成本越低，路径越优）。默认基于链路带宽，公式为 Cost = 参考带宽 / 链路带宽（参考带宽默认是 100Mbps，可手动修改）

OSPF原理基础

OSPF使用泛洪来广播路由信息，但泛洪会产生指数级的数据包传输量，可能导致网络拥塞。因此在每个数据包中使用 TTL（生存时间）字段，其初始值为特定数值，每个节点转发时TTL减少，当 TTL 耗尽时停止洪泛。

邻接关系（adjacency）：每个路由器与邻居建立邻接关系。

链路状态通告（LSAs）：OSPF在链路中洪泛的是链路状态通告（Link State Advertisement, LSA）。每台路由器都会产生LSA。

拓扑数据库(LSDB)：路由器将接收到的LSA放入自己的LSDB(Link State Data Base，链路状态数据库)。路由器通过对LSDB中所存储的LSA进行解析，进而了解全网拓扑

最短路径算法：每个路由器利用其链路状态数据库运行最短路径算法（如 Dijkstra 算法），生成到网络中每个节点的路由

OSPF分层架构（Hierarchical OSPF）

OSPF有两级分层结构：分为本地区域（local area）和骨干区域（backbone）。

  • 链路状态通告（LSA）仅在本区域内洪泛，每个非边界路由器只维护本区域的详细拓扑信息；区域间的流量通过区域边界路由器（area border routers）转发。
  • 区域边界路由器（area border routers）：负责 “汇总（summarize）” 本区域内的网络距离信息，再将汇总后的信息广告给其他区域的边界路由器，实现区域间路由的简洁传递。
  • 骨干路由器（backbone routers）：仅在骨干区域内运行 OSPF，专注于骨干区域的路由计算与转发。
  • 边界路由器（boundary routers）：用于连接到其他自治系统（AS），实现 OSPF 域与外部网络的路由交互（如与 BGP 网络对接）。

image-20251103004555430

BGP协议

引入

BGP是一种用于AS之间路由的协议。BGP 基于TCP来发送路由消息，即，它是基于传输层的协议。

BGP是矢量路由协议（path vector protocol），它在广告路由时，会附带到达目的网络所经过的AS 编号序列，以此描述路由路径。BGP 选择路由时优先遵循策略（policy），而非单纯追求路径最优（比如跳数最少）。这是因为不同自治系统间的路由决策会涉及商业合作、安全策略等复杂因素，需要通过自定义策略来控制流量走向。

BGP 能够支撑全球互联网的规模化需求，具体体现在：

  • 提供全球范围的网络连通性；
  • 支持地址聚合（将多个连续的 IP 前缀合并为一个更简洁的前缀，减少路由表规模）；
  • 采用完全分布式的架构，适应互联网的去中心化特点

BGP可以被分为eBGP 和 iBGP。

  • eBGP（外部 BGP）：用于在不同自治系统的边界路由器之间交换子网可达性信息，即获取邻居 AS 的路由信息。
  • iBGP（内部 BGP）：用于在同一自治系统内部的路由器之间传播可达性信息，确保 AS 内部的所有路由器都知晓外部路由。

在 BGP 中，路由的目标不是具体的主机，而是CIDR 化的前缀（prefixes）。

BGP广播的是 “目标 CIDR 前缀 + 路径 AS 序列 + 各类属性（如本地优先级、MED 等）”。例如，BGP 会告诉邻居 “到达 10.0.0.0/8 网络，需要经过 AS100→AS200，且该路由的本地优先级为 100”。其中，AS 序列是 BGP 的核心特征，它明确了路由经过的自治系统路径，而各类属性则用于实现基于策略的路由选择。

BGP基础

BGP 会话与信息广播的基本逻辑

两个 BGP 路由器（称为 “对等体，peers”）之间通过半永久的 TCP 连接交换 BGP 消息。BGP 本质是 “路径矢量协议”，其核心是广告（advertising）不同目的网络前缀的路径。

当 AS3 向 AS1 广告一个前缀时，意味着AS3 承诺会转发前往该前缀的数据包；同时，AS3 可以对前缀进行地址聚合（将多个连续前缀合并为一个，减少路由表规模）。

image-20251102225446529

软件定义网络（Software Defined Networks）（简要介绍）

引入

控制面与数据面

总体来说，一个巨大的网络可以被分为控制面（Control plane）和数据面（Data plane）

  • 数据面：数据面仅仅关心数据的路由，将数据转发到目的地址。
  • 控制面：负责路由决策，寻找转发数据面的数据的规则。

这里控制面的路由决策有两种实现方式，一种是此前学的OSPF，RIP，BGP等等协议。另一种就是软件定义网络SDN。

在SDN下，路由器的数据面正常转发，控制面通过控制代理（Control Agent，CA）与远程服务器相连，由远程服务器下发指令操控路由器的控制面。即，路由逻辑由远程服务器集中实现，再下发给路由器。如下图所示。

image-20251103011406619

SDN介绍

为何需要SDN

  • 简化网络管理：避免路由器配置错误，对流量的调度更灵活。
  • 基于表的转发支持 “可编程” 路由器：
    • 集中式 “编程” 更简单：控制器集中计算转发表，再分发给路由器。
    • 分布式 “编程” 更困难：每台路由器需通过分布式算法（如 OSPF、BGP）独立计算转发表。

  • 开放（非专有）的控制平面实现：打破传统厂商锁定，支持第三方创新。

  • 传统路由算法在负载均衡或避免某些节点的路由上有局限

SDN的分层架构

SDN 通过分层解耦实现网络的灵活管控，分为三层：

基础设施层（Infrastructure Layer）

  • 由网络设备（如交换机、路由器）组成，负责数据平面的转发操作。
  • 设备通过标准化的 “控制 - 数据平面接口”（如 OpenFlow）与上层交互，接收控制器下发的转发规则。

控制层（Control Layer）

  • 包含 SDN 控制软件和网络服务，是 “逻辑集中式控制平面” 的具体实现。
  • 它掌握全网视图，计算转发策略，并通过 API 为上层应用提供网络能力。

应用层（Application Layer）

  • 包含各类业务应用（如流量调度、安全策略应用），通过 API 调用控制层的网络服务，实现定制化的网络功

image-20251103011702162

SDN的组成

数据平面：交换机(switches)：

  • 特性：快速、简单、商用化，通过硬件实现通用数据平面转发。
  • 转发逻辑：交换机的 “流表” 由控制器计算并下发。
  • 控制接口：通过标准化 API（如 OpenFlow）实现对交换机的控制，定义了 “可控制” 和 “不可控制” 的功能边界。
  • 通信协议：通过 OpenFlow 等协议与控制器通信，完成流表的下发与状态上报。

SDN 控制器（SDN controller / network OS）

  • 状态管理：维护全网的状态信息（拓扑、设备状态、流量等）。
  • 接口交互：
    • 北向 API：与上层 “网络控制应用”（如路由、负载均衡应用）交互，提供网络能力。
    • 南向 API：与下层 “数据平面交换机” 交互，下发流表、收集设备状态。
  • 系统架构：为了性能、可扩展性、容错性，控制器通常以分布式系统实现。

控制应用（network-control apps）

  • 是 SDN 的 “大脑”，基于控制器提供的 API 和服务，实现各类控制功能（如路由、接入控制、负载均衡）。
  • 开放生态：应用 “解绑定” 于厂商，可由第三方提供（如独立软件开发商、企业 IT 团队），不再受限于路由设备厂商的封闭生态。

SDN当前的优势与挑战

优势：

  • 使得网络和IP更加灵活
  • 解耦控制面和数据面
  • 将大脑集中化到中央控制器
  • 以中央的视角观测资源，再做决策
  • 可编程的网络，集中化的管理，可以满足任何需求

挑战：

  • 需要强化控制平面（hardening the control plane）：
    • 故障鲁棒性：需利用可靠分布式系统的成熟理论，确保控制器在部分节点故障时仍能正常运行（如通过冗余、一致性协议实现容错）。
    • 可靠性与安全性：要从设计之初就 “植入”（baked in）高可靠性和安全性机制，避免后期修补的短板（例如防范控制器被攻击、保障控制信令的机密性与完整性）。
  • 针对不同网络场景，需要满足特定任务的网络与协议需求。
  • 网络规模扩大，SDN 需解决大规模场景下的可扩展性问题

介绍：Network Function Virtualization (NFV)

网络功能虚拟化（NFV）的核心是将传统依赖硬件的网络功能（如防火墙、加密功能）从专用硬件中解耦，迁移到虚拟服务器上。

传统网络设备模式依赖 “硬件型设备（Hardware-based Appliances）”，如防火墙、路由器等专用硬件。这些设备形态碎片化（Fragmented, Non-Standard Hardware），部署和维护成本高。NFV 通过 “虚拟设备（Virtualized Appliance）” 实现网络功能，运行在通用的标准服务器（High Volume, Standard Server）、存储（High Volume, Standard Storage）和交换机（High Volume, Standard Switch）上

NFV 带来多方面的显著收益：

  • 减少网络硬件占用空间；
  • 降低网络功耗；
  • 减少网络维护成本；
  • 网络升级更便捷；
  • 延长网络硬件的生命周期；
  • 整体维护和硬件成本降低。

NFV & SDN

  • 二者的共性：都旨在用通用的服务器、存储和交换设备替代专用硬件 / 软件，推动网络架构的革新。
  • 二者的差异：
    • SDN 聚焦 “网络的可编程性与动态控制”，核心是通过集中控制器实现网络的灵活转发与管理。
    • NFV 聚焦 “网络功能的虚拟化”，核心是将防火墙、负载均衡等网络功能从专用硬件迁移到虚拟机 / 容器，优化网络服务的部署与运维。