ONEWAN is better than two: Unifying a split WAN architecture（SDN、流量工程）

nsdi23

摘要

大规模云服务商通常同时运营两个WAN：一个软件定义网络用于承载数据中心之间的流量，另一个基于标准协议的网络用于处理互联网流量。然而我们长期运营两套异构的全球级WAN架构后发现，这种“分裂式”架构带来了极高的运营复杂度和成本开销。

为此，我们提出并实现了一个统一的WAN架构——ONEWAN，将微软原有的SWAN（承载数据中心间流量的那个WAN）与CORE网络（处理互联网流量的那个WAN）整合为一个整体。ONEWAN首次将SDN技术应用于互联网骨干网，实现了对数据中心间流量与互联网流量的统一调度。

面对网络规模扩大一个数量级所带来的路由表膨胀与流量工程（简称TE）优化难题，我们提出了一种新的路由与转发机制——Traffic Steering（§3），在无需更换现有网络设备的前提下（§2），有效应对了网络规模的跃迁。

此外，ONEWAN还引入了可扩展的路径计算与线性规划优化技术（§5），使得在数秒内即可完成大规模流量路径的重新分配。

通过这一系统，我们成功将原本分裂的两套网络无缝迁移至统一的SDN控制架构中，实现了10倍于SWAN的网络规模扩展。

8 相关工作

我们是首个将 SDN 技术应用于互联网骨干网以取代 RSVP-TE 的团队。基于 SDN 的流量工程最初应用于数据中心间网络[9, 14, 15, 17, 20, 24, 25]。一个数据中心间网络的存在点（PoP）更少，扩展要求更简单，并且易于从头构建。我们的工作表明，可扩展性、可靠性、功能对等和迁移等挑战是可以克服的，并能在互联网骨干网中取代 RSVP-TE。这引领了使用单一 SDN 控制骨干网的云网络统一化。

SDN 控制器在互联网对等领域的应用已在 [4, 7, 13, 34, 35, 37] 中讨论。它们解决了一个重要的相邻问题：对等边缘的互联网流量工程。这些控制器支持感知性能的出口对等点选择以及自治系统之间的入站流量工程。我们的工作重点在于，当流量在自治系统内的骨干网中传输时，在对等边缘与数据中心内的终端主机之间对此类流量进行动态路径选择和负载均衡。微软的对等边缘使用了一个类似的 SDN 控制器，但这已超出本文讨论范围。OneWAN 控制器测量对等流量并使骨干网适应对等边缘流量的需求。

通过模型和链路数据进行的流量矩阵估计已在 [8, 26, 32, 38] 中得到研究。根据我们的经验，不幸的是，在运营网络中进行在线 TE 必须直接测量流量矩阵。我们通过评估我们基于 IPFIX 采样的测量系统，并呈现真实世界流量矩阵的数据，对先前的工作进行了扩展。

先前的工作 [14, 18, 23] 指出，在 WAN 中编程端到端路径需要数分钟时间，并且存储流量工程规则的表大小是一个限制因素。我们的工作表明，即使在超大规模网络中，网络更新也仅需数秒。造成这种差异的一个关键原因是，先前的工作使用了基于 TCAM 的策略引擎，虽然灵活但资源有限；而我们的工作使用了 IP 和 MPLS 查找表，这些表即使是在商用交换机中也经过优化且容量巨大，并使用先建后断语义进行并行编程。路径选择通常是离线进行的 [6]，而在选定路径上的负载均衡是在线的。在 onewan-te 中，两者都是在线的，使用动态拓扑和流量矩阵。流量工程通常被研究为对单一目标的优化，例如最小化链路利用率 [36]。onewan-te 使用不同的目标优化每个流量类别，并使用基于类别的转发在数据平面实现意图。[1, 25] 研究了带故障的 TE 问题。onewan-te 的表述针对更大的网络进行了调整。它在光风险组的粒度上保护故障，并平衡了主动故障保护与不在非故障条件下增加延迟这两个相对立的需求。

2 OneWAN 架构

就地转换到 OneWAN（物理连接 Core 和 Swan）

利用现有网络硬件

  • 聚合路由器：承担 BGP 全表路由、Traffic Steering 与 TE 隧道端点功能；
  • 骨干路由器：作为转发节点，仅维护 MPLS 标签转发表，无需运行 BGP。

隧道机制的选择（采用 MPLS 标签栈实现隧道封装）

  • 入口聚合路由器根据流量目的地打上两层标签（具体打的label内容就是TE要考虑的问题了）
    • 顶层为出口站点标签（Site Label）；
    • 底层为下一跳节点 SID（Segment ID）。
  • 骨干路由器根据标签进行 TE 隧道转发；
  • 出口骨干路由器通过 Segment Routing 将流量送达最终目的地。

路由器角色（边缘路由器是流量的源或宿；聚合路由器与骨干路由器见上面）。

所有骨干-骨干、聚合-骨干链路均纳入 TE 优化范围。边缘与聚合之间的 Clos 架构因容量极高且部署于本地，不参与 TE 调度。

⇧ OneWAN 是一个统一网络，使用 SDN TE 为互联网和数据中心间流提供服务。OneWAN 在其边界包含聚合路由器，在其内部包含骨干路由器（灰点）。数据中心和对等边缘路由器（黑点）使用 Clos 互连连接到聚合路由器。OneWAN-TE 适用于聚合路由器之间的任何站点间流，无论是数据中心间流还是在边缘站点与数据中心之间。(图 3 的图注)

3 OneWAN Traffic Steering

⇧ OneWAN 路由分三部分进行。第一部分是聚合路由器中的引导路由，第二部分是骨干路由器之间的TE隧道，第三部分是从出口骨干路由器到网络出口点的段路由路径。Traffic Steering 和 TE 路由由 onewan-te 控制器添加。(图 5 的图注）

步骤：

一、Traffic Steering（发生于聚合路由器处）

  1. 一个原始的IP数据包从本地网络进入了OneWAN
  2. 聚合路由器（基于BGP协议）一看这个的目的地址，立刻知道两件事：
    • 最终目的地是哪个大区？（比如：上海站）
    • 最终由谁接收？（比如：上海3号Router）
  3. 于是，它给包裹贴上一个两层MPLS标签栈。
    • 外面一层写上 Site: 上海（出口骨干路由器标签）
    • 里面一层写上 交付给：上海3号Router（出口聚合路由器的节点SID）

二、Traffic Engineering（发生于Backbone Router 之间）

  1. 贴好标签的数据包被送到了Ingress Backbone Router
  2. 入口只关心最外面那层label（Site: 上海）。看了一眼，心想：“去上海的路有好几条，现在哪条最畅通？”
  3. 根据中央的实时调度，决定走隧道T2。于是把外面那层 Site: 上海 的标签撕掉，换上一个新标签，上面写着 走：隧道T2（TE隧道标签）。
  4. 数据包就在这个名为T2的高速通道里被飞速传送，经过一个个中转站，每个中转站只认这个T2标签，就知道往下站哪条路扔。直到到达上海的出口Backbone Router

这一步实现了智能选路。网络可以根据实时拥堵情况，选择最佳路径。

三、 Segment Routing（发生于目的地区域内部）

  1. 到达上海的出口Backbone Router
  2. 这里的把外面那层 走：隧道T2 的标签撕掉，终于看到了里面那层一直没动过的标签：交付给：上海3号（节点SID）。
  3. 这个“上海3号”其实就是最终接收数据包的聚合路由器。出口根据这个信息，把包裹（现在又变回原始的IP包了）送出去，完成“最后一公里”的配送。

最后这一步的路径信息由IS-IS协议提供

不等价负载均衡

⇧ (图 6 的图注) 从聚合路由器 a 到端点 f 的 onewan-te 流示例。引导路由根据最短路径距离和从骨干路由器到出口站点的最大流，将流负载均衡到选定的骨干路由器。骨干路由器执行完整的 TE 优化（§5）。

  • 聚合路由器 a： 现在有一大批数据包要从这里发往目的地 f。
  • 入口有两个： b 和 c。a同时连着这两个入口，而且连接的链路一样宽。
  • 目的地 f 在上海站，而通往上海站的核心枢纽是 T。

聚合路由器a不能简单地把数据包一半给b，一半给c。因为 从b到枢纽T的路的宽窄与从c到枢纽T的不同。中央决策先排除那些去往上海路线太绕的入口，再通过计算剩余的每个入口通往上海的Max-Flow，之后告诉分拣中心：“给你连接的两个入口分配权重：入口A分70%的包裹，入口B分30%的包裹”，因为A那边的路更宽。此为“不等价负载均衡”。

4 OneWAN 代理与本地修复

OneWAN 代理负责安装由 onewan-te 控制器提供的路由。OneWAN 代理还执行本地修复。（本地修复机制检测隧道的转发状态，并重新编程操作以在存活的隧道上发送流量，从而最大限度地减少由路由黑洞或拥塞引起的瞬时数据包丢失。）

OneWAN 代理作为一个进程运行在所有聚合和骨干路由器上，可选择在 Docker 容器内运行。它支持四种不同的固件操作系统。为了支持固件的异构性，该代理被结构化为独立的平台无关和平台相关组件，它们之间具有定义良好的 API。平台无关部分包含了代理中的大部分复杂逻辑。图 7 展示了代理的组织结构。

路由编程。 OneWAN 代理使用 HTTPS 服务器与 onewan-te 控制器通信；不需要路由协议。我们使用 OpenFlow [28] 的匹配动作和组来表示路由。组代表从入口路由器发起的一组流量引导和流量工程隧道、用于不等价负载均衡的隧道权重、指示隧道适用于何种类型流量的流量类别、隧道是主用还是备份，以及用于探测隧道存活状态的属性。中转路由使用不带组的单一动作。

路由编程器通过路由器固件提供的内部 gRPC 或等效连接来实现动态路由操作。它将组转换为具有 32 个成员的加权成本多路径（WCMP）下一跳，并按权重比例复制每个隧道。

目标组是从控制器接收的隧道集合，而动态组是存活的隧道集合，其原始权重在存活的隧道之间重新分配。当一个组中没有存活的主用隧道时，备份隧道会被提升为主用。隧道与一个流量类别相关联，默认为匹配任何流量类别。当一个组中没有存活的默认流量类别的隧道时，下一个流量类别的隧道会被修改为默认流量类别。在图 8 中，目标组有六个隧道 A-F。当 A 和 B 故障时，备份隧道 E 和 F 成为主用。如果 A 恢复，它将成为唯一的主用默认隧道。我们将在 §5.2 和 §5.3 中解释 onewan-te 如何计算多样化备份和感知类别的隧道。

隧道探测。 聚合路由器使用双向转发检测（BFD）[21] 进行单跳隧道探测，以检查到骨干路由器的链路。入口骨干路由器使用带标签的自 ping 机制通过原始套接字执行端到端隧道探测。隧道探测在正向路径上使用与数据包相同的路由。

Swan 中的隧道探测依赖于返回路径中的 IS-IS。这导致备份隧道即使在其正向路径未使用故障链路的情况下也会失败，因为探测返回路径受到了 IS-IS 路由收敛的影响。在没有主用和备份隧道的情况下，代理会移除控制器路由，流量回退到 IS-IS。只要隧道仍然宕机，客户流量就会经历 IS-IS 收敛时间和拥塞丢包。这显著降低了用户体验。因此，OneWAN 中的探测使用控制器路由从隧道目的地返回到隧道源。返回的跳是正向跳的反向，因此不与数据隧道无关的链路共享命运。在图 9 中，探测数据包通过 d-b-a 返回，而不是更短的 d-c-a。onewan-te 控制器尽可能重用反向的可用数据隧道，否则创建新隧道。

可以有多个探测数据包在传输中，探测间隔与路径往返时间无关。丢失配置数量的探测会将隧道标记为宕机，而成功的探测会将隧道标记为正常。我们以 100 毫秒的间隔发送探测，并在丢失 3 个探测后将隧道标记为宕机。因此，故障检测时间是 300 毫秒加上到故障点的距离，在最坏情况下是隧道延迟。

本地修复。 在分离式 WAN 架构中，互联网流量由核心网络中的 RSVP-TE 处理。核心网络中基于标准的 RSVP-TE 实现了快速重路由（FRR）[29] 机制，使其能够在 O(10) 毫秒内从链路故障中恢复。故障检测时间是到故障点的距离，最坏情况下是链路延迟，加上光模块通知路由器的一个小延迟。FRR 在故障点切换到预先计算的旁路隧道，并在线卡网络处理单元（NPU）中或附近运行。切换时间是几毫秒。

与 FRR 相比，OneWAN 的本地修复发生在隧道的入口路由器，而不是故障点。第一跳链路的故障通过接口宕机事件检测，后续跳的故障通过丢失的探测检测。修复在路由处理器中启动，并受到更大的进程间通信和调度延迟的影响。路由编程器会就地修改 WCMP，以减少修复时执行的硬件写入次数。因此，OneWAN 的收敛时间在一秒以内。虽然比 FRR 慢，但 OneWAN 满足了当前网络所服务的视频流、视频会议和其他交互式应用的收敛时间要求。OneWAN 隧道探测还验证了转发，因为它们使用了数据包所使用的路由。备份隧道是基于多样性和剩余带宽选择的，因此经历的因拥塞造成的瞬时丢包更少（在 §5.3 中描述）。

路由编程。 OneWAN 被划分为地理区域，区域性的 onewan-te 控制器对其区域内的设备进行路由编程 [22]。所有路由器在单个阶段并行编程引导路由。骨干路由器上的弹出转发路由消除了同步编程引导和 TE 路由的需要。

TE 路由也使用三个阶段并行更新，每个阶段之间设有屏障。先建后断（Make-before-break）序列确保在编程过程中不会形成路由黑洞或环路。所有路由器的路由集在逻辑上分为两组：中转和隧道出口路由 T，以及隧道入口路由 G。由于 G 路由依赖于 T 路由，先建后断确保在每个后续跳都被编程之前，流量不能进入隧道。OneWAN-TE 路由生成的一个重要特性是，连续迭代之间的标签空间不重叠，除非它们代表的路径完全相同。标签范围足够大，可以在最坏情况下分配唯一的标签。
将迭代 n 的路由 T_n ∪ G_n 替换为迭代 n+1 的路由 T_{n+1} ∪ G_{n+1} 的阶段如下：
– 所有路由器中的初始状态是 T_n ∪ G_n。
– T_n ∪ T_{n+1} ∪ G_n 被发送给代理，代理执行其路由更新并报告成功或错误。
– 编程 T_n ∪ T_{n+1} ∪ G_{n+1}。在此阶段，网络中可能会混合存在 G_n 和 G_{n+1} 路由，但它们所依赖的所有 T 路由都将存在。
– 编程 T_{n+1} ∪ G_{n+1}。

流量在第二阶段发生转移。由于一个阶段在 4 秒内完成，适度的临时缓冲容量可以避免瞬时拥塞。我们保留 15% 的临时缓冲容量来处理编程和流量微突发带来的瞬时状况。如果代理报告错误或连接丢失，控制器会在一个阶段内回滚到初始状态。回滚后的任何不一致都会由 OneWAN 代理的本地修复进行纠正。

4.1 评估

路由规模。 流量工程隧道的数量是核心网（CORE）中 RSVP-TE 的一个显著扩展性问题。大量的 RSVP-TE 隧道增加了链路故障后的网络收敛时间，并超出了旧式聚合路由器的硬件资源。表 2 显示 OneWAN-TE 使用的隧道比 RSVP-TE 少 10 倍。当 OneWAN-TE 进行优化时，它只是在现有隧道中保留更多带宽，或者创建新的并销毁未使用的隧道。另一方面，RSVP-TE 通过增量带宽保留来信令新隧道，其合并频率较低。其次，RSVP-TE 要求在节点之间建立全互联的标签交换路径（LSP），但 OneWAN-TE 只为地理区域内的节点创建隧道，区域间的流重用区域内的隧道。
引导路由的规模与端点数量成正比，流量工程路由的规模与骨干节点数量成正比。即使对于大型网络，这两个转发表（FIB）的规模都很小。更新 FIB 的时间受控制器和路由器之间的往返距离以及 FIB 中的路由数量影响（见图 10）。

基于类别的转发。 OneWAN-TE 的一个目标是为标记为清道夫（scavenger）流量类别的复制或备份流量使用利用率较低的长路径，但为尽力而为和更高流量类别的流量使用多样化的最短路径。OneWAN 代理安装出口站点标签路由时带有一个中间策略查找，该查找由流量类别索引，以从默认类别 WCMP 切换到特定类别的 WCMP。图 11 显示 OneWAN-TE 将 55% 的清道夫流量分配给了更长的路径。差异化的路径减少了因更高流量类别的微突发导致的清道夫丢包。当尽力而为和清道夫队列使用加权轮询队列调度时，差异化的路径也减少了因清道夫微突发导致的尽力而为瞬时丢包。图 12 显示了 2022 年 3 个月期间尽力而为和清道夫流量类别的成功传输率 SLO。

图 7：OneWAN 代理包含平台相关和平台无关的组件。该代理安装由 onewan-te 控制器提供的路由，并关闭经历转发故障的隧道。

(图 7 的图注)

图 8：本地修复。OneWAN 代理根据存活状态自动调整隧道的组成和权重。(a) 如果主用默认隧道 A 和 B 故障，则备份隧道 E 和 F 成为主用。(b) 如果 A 恢复，它成为唯一的主用默认隧道。(c) 如果只有清道夫隧道 C 和 D 存活，它们成为主用。(d) 如果所有隧道都故障，站点标签路由被替换为弹出转发动作。

(图 8 的图注)

图 9：隧道探测在正向使用与数据包相同的路由，并从目的地使用相同的链路返回以避免误报故障。中转路由由控制器和 transit 路由器的代理编程。

(图 9 的图注)

表 2：ONEWAN-TE 在每设备和整个网络的路由、隧道和更新时间方面的规模。

(表 2 内容)

指标 ONEWAN-TE
每设备引导 + TE 路由数 O(10^3)
网络级隧道数 O(10^4)
每设备 FIB 更新时间（p95） 2.0 秒
网络级 FIB 更新时间（p95） 3.7 秒
  • 探测（Probing）： 每个入口骨干路由器会不断地向每条TE隧道发送“探测包”，如果连续几次收不到回复，它就认为这条路断了。
  • 自动切换（Local Repair）： 一旦检测到路断了，路口的OneWAN Agent可以自己立刻做决定，而不用等控制器的命令。它会：
    • 马上把通往断掉那条路的“通道标签”撕掉。
    • 把所有数据包立刻切换到事先准备好的、另一条没断的备份路线上。
    • 这个过程非常快，能在几百毫秒内完成，用户看视频、打电话基本感觉不到卡顿。

这个设计的巧妙之处在于把故障处理的权力下放给了本地节点，大大加快了反应速度。

5 TE 优化

  1. 勘探所有可能的路线（路径计算）
  2. 给不同的流量分配路线和车道（优化求解器）
  3. 准备备用路线（多样化路径求解器）

OneWAN TE 优化器有两个输入：预测的流量矩阵（TM）（在第 6 章描述）和动态拓扑。流量矩阵是流量干线预测带宽的集合。（一个流量干线（traffic trunk）是从源骨干路由器到目标站点、针对特定流量类别的聚合流量流）TE 优化器分两个阶段运行：路径计算阶段和优化阶段。

TE 优化器分两个阶段运行：路径计算阶段和优化阶段。

  1. 路径计算阶段（两种算法）
    • 惩罚路径查找器
      • 先用Dijkstra算法找到最短路径。然后，惩罚这条路径用过的所有“风险组”。接着再找新的最短路径，因为之前的风险组被惩罚（相当于设置了路障或收费特别高），新找到的路径就会自动避开它们。
      • 找到多条风险分离的路径，确保安全。
    • 最大流路径查找器
      • 不关心路距离，只关心路宽。
      • 到那些容量巨大、可以承载海量数据的路径，即使它们可能有点绕远。
    • 技巧
      1. 虚拟出一个“超级目的地”
      2. 只计算那些真正有流量需求的源-目的地对之间的路径，而不是计算所有点对点的路径（没车的地方不修路）
  2. 优化阶段
    • 求解器链
      • 优先级公平求解器根据流量类别为流量干线分配优先级。尽力而为及更高级别的流量类别映射到优先级 0（最高），清道夫流量类别干线为优先级 1。
      • 云网络运营商为每个优先级设置一个committed data rate 确保低优先级干线在网络中不会被饿死。
      • 对于高优先级流量，它调用 Max-Min Fairness（最大最小公平）求解器，确保每个流量流都能公平地分到资源，然后再调用 Min-Cost（最小成本）求解器，在公平的基础上，尽量让它们走最短、最好的路。
      • 然后，调用 Diverse Path（多样化路径）求解器。这个求解 器会检查上面分配的主路径，并为每一条主路径计算一条完全风险分离的备份路径。这样一旦主路径上的某个风险组出事，流量可以立刻切换到备份路径上。
      • 对于清道夫流量，它的目标不同。它调用 Min-Max Utilization（最小化最大利用率）求解器。这个求解器的目标是把整个路网中所有路的利用率尽量拉平，避免有的路堵死，有的路空着。所以它会故意把清道夫流量引到那些空闲的、可能有点绕远的路径上，把整个网络的利用率提到最高。
    • 技巧
      1. 我们通过剪枝小于 500 Mbps 的小流量干线，实现了约束数量的显著减少。这将约束矩阵的行和列分别减少了 5 倍和 7 倍。这些小干线仅占网络流量的 2.5%（§6.2 描述），并在增长变大后的五分钟内得到优化。
      2. 使用 LP 求解器的实用性还取决于设置：对我们的 LP 模型而言，对偶单纯形法优于原始单纯形法。此外，可能出现纯循环，因为最大最小公平模型具有高度退化性——许多列是相同的，因为约束矩阵中的非零元素和成本向量系数为 1。使用成本扰动来摆脱循环。

⇧ 优先级公平求解器根据流量类别的优先级为其保留带宽。然后它为高优先级流量调用最大最小公平、最小成本和多样化路径求解器链。高优先级流量不消耗为低优先级流量保留的带宽。分配完高优先级流量后，它为低优先级流量调用最大最小和最小最大利用率求解器。高和低优先级链之后未使用的带宽可用于优先级公平求解器第二轮中未满足的需求。(图 15 的图注)

6 测量WAN流量矩阵（略）

IPFIX 采样

记录被发送到一个叫 IPFIX Collector 的服务器集群，它们把这些零散的信息拼完整。

↑